Graph kernels based on linear patterns: Theoretical and experimental comparisons - Normandie Université Accéder directement au contenu
Article Dans Une Revue Expert Systems with Applications Année : 2022

Graph kernels based on linear patterns: Theoretical and experimental comparisons

Linlin Jia
Benoit Gaüzère
Paul Honeine

Résumé

Graph kernels are powerful tools to bridge the gap between machine learning and data encoded as graphs. Most graph kernels are based on the decomposition of graphs into a set of patterns. The similarity between two graphs is then deduced to the similarity between corresponding patterns. Kernels based on linear patterns constitute a good trade-off between accuracy and computational complexity. In this work, we propose a thorough investigation and comparison of graph kernels based on different linear patterns, namely walks and paths. First, all these kernels are explored in detail, including their mathematical foundations, structures of patterns and computational complexity. After that, experiments are performed on various benchmark datasets exhibiting different types of graphs, including labeled and unlabeled graphs, graphs with different numbers of vertices, graphs with different average vertex degrees, linear and non-linear graphs. Finally, for regression and classification tasks, accuracy and computational complexity of these kernels are compared and analyzed, in the light of baseline kernels based on non-linear patterns. Suggestions are proposed to choose kernels according to the types of graph datasets. This work leads to a clear comparison of strengths and weaknesses of these kernels. An open-source Python library containing an implementation of all discussed kernels is publicly available on GitHub to the community, thus allowing to promote and facilitate the use of graph kernels in machine learning problems.
Fichier principal
Vignette du fichier
S0957417421014299.pdf (725.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03410508 , version 1 (05-01-2024)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Linlin Jia, Benoit Gaüzère, Paul Honeine. Graph kernels based on linear patterns: Theoretical and experimental comparisons. Expert Systems with Applications, 2022, 189, pp.116095. ⟨10.1016/j.eswa.2021.116095⟩. ⟨hal-03410508⟩
51 Consultations
2 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More