Une procédure persistante de Weisfeiler–Lehman pour la classification des graphes

Le noyau de graphe Weisfeiler–Lehman présente des performances compétitives dans de nombreuses tâches de classification de graphes. Toutefois, ses caractéristiques basées sur les sous-arbres ne permettent pas de capturer les composantes connexes ni les cycles, des caractéristiques topologiques essentielles pour décrire les graphes. Pour extraire de telles informations, nous exploitons les informations de labels propagées aux nœuds et transformons les graphes non pondérés en graphes métriques. Cette transformation nous permet d’enrichir les caractéristiques basées sur les sous-arbres avec des informations topologiques obtenues grâce à l’homologie persistante, un concept issu de l’analyse topologique des données. Notre méthode, que nous formelisons comme une généralisation des caractéristiques de sous-arbres Weisfeiler–Lehman, présente une précision de classification favorable, et ses améliorations en termes de performance prédictive sont principalement dues à l’intégration d’informations relatives aux cycles.