Une base de référence simple mais efficace pour la classification de graphes non attribués

Les graphes sont des objets complexes qui ne se prêtent pas facilement aux tâches d'apprentissage typiques. Récemment, une gamme de méthodes basées sur les noyaux de graphe ou les réseaux neuronaux de graphe a été développée pour la classification de graphes et l'apprentissage de représentations sur les graphes en général. Alors que les méthodologies développées deviennent de plus en plus sophistiquées, il est important de comprendre quels composants des méthodes de plus en plus complexes sont nécessaires ou les plus efficaces.Comme première étape, nous avons élaboré une représentation simple mais significative des graphes, et nous avons exploré son efficacité dans la classification des graphes. Nous avons testé notre représentation de base pour la tâche de classification des graphes sur une variété de jeux de données de graphes. De manière intéressante, cette représentation simple atteint des performances similaires à celles des noyaux de graphe et des réseaux neuronaux de graphe les plus avancés pour la classification des graphes non attribués. Ses performances dans la classification des graphes attribués sont légèrement inférieures car elle n'intègre pas les attributs. Cependant, compte tenu de sa simplicité et de son efficacité, nous pensons qu'elle sert toujours d'une base efficace pour la classification des graphes attribués. Notre représentation du graphe est efficace à calculer (en temps linéaire). Nous fournissons également une connexion simple avec les réseaux neuronaux de graphe.Il convient de noter que ces observations ne concernent que la tâche de classification des graphes, tandis que les méthodes existantes sont souvent conçues pour un spectre plus large incluant l'embedding nodal et la prédiction des liens. Les résultats sont également susceptibles d'être biaisés en raison du nombre limité de jeux de données standards disponibles. Néanmoins, les bonnes performances de notre base simple incitent au développement de nouveaux jeux de données standards plus complets afin d'évaluer et d'analyser différemment les méthodes d'apprentissage sur les graphes. De plus, étant donné l'efficacité computationnelle de notre résumé du graphe, nous croyons qu'il constitue un bon candidat comme méthode baseline pour les futures études sur la classification des graphes (ou même d'autres tâches d'apprentissage sur les graphes).