Noyau de graphes basés sur des motifs linéaires : comparaisons théoriques et expérimentales

Les noyaux de graphes constituent des outils puissants pour combler le fossé entre l’apprentissage automatique et les données encodées sous forme de graphes. La plupart des noyaux de graphes reposent sur la décomposition des graphes en un ensemble de motifs. La similarité entre deux graphes est ensuite déduite de la similarité entre les motifs correspondants. Les noyaux fondés sur des motifs linéaires offrent un bon compromis entre précision des performances et complexité computationnelle. Dans ce travail, nous proposons une étude approfondie et une comparaison des noyaux de graphes basés sur différents motifs linéaires, notamment les chemins (walks) et les chaînes (paths). Premièrement, tous ces noyaux sont examinés en détail, incluant leurs fondements mathématiques, leurs structures de motifs et leur complexité computationnelle. Ensuite, des expériences sont menées sur divers jeux de données standard présentant différents types de graphes, notamment des graphes étiquetés et non étiquetés, des graphes avec un nombre variable de sommets, des graphes à degrés moyens de sommets différents, ainsi que des graphes cycliques et acycliques. Enfin, pour des tâches de régression et de classification, les performances et la complexité computationnelle des noyaux sont comparées et analysées, et des recommandations sont formulées pour sélectionner les noyaux en fonction du type de jeu de données graphiques. Ce travail permet une comparaison claire des forces et faiblesses de ces noyaux. Une bibliothèque open source en Python, implémentant tous les noyaux discutés, est mise à disposition publiquement sur GitHub, afin de favoriser et faciliter l’utilisation des noyaux de graphes dans les problèmes d’apprentissage automatique.