Amélioration de l’expressivité des réseaux de neurones graphes par dénombrement d’isomorphismes de sous-graphes

Bien que les réseaux de neurones sur graphes (GNN) aient obtenu des résultats remarquables dans diverses applications, des études récentes ont mis en évidence des lacunes importantes dans leur capacité à capturer la structure sous-jacente du graphe. Il a été démontré que la puissance expressive des GNN standards est bornée par le test d’isomorphisme de graphes de Weisfeiler-Leman (WL), dont ils héritent des limitations prouvées, telles que l’incapacité à détecter ou à compter des sous-structures de graphe. D’un autre côté, de nombreuses preuves empiriques, notamment en science des réseaux et en bioinformatique, montrent que ces sous-structures sont souvent étroitement liées aux tâches ultérieures. À cet effet, nous proposons les « Graph Substructure Networks » (GSN), un schéma de propagation d’informations sensible à la topologie fondé sur un encodage des sous-structures. Nous analysons théoriquement la puissance expressive de notre architecture, en montrant qu’elle est strictement plus expressive que le test WL, et fournissons des conditions suffisantes pour l’universalité. Plus important encore, nous ne cherchons pas à respecter la hiérarchie de WL ; cette liberté nous permet de préserver plusieurs propriétés attrayantes des GNN standards, telles que la localité et la complexité linéaire du réseau, tout en étant capables de distinguer même les cas difficiles d’isomorphisme de graphes. Nous menons une évaluation expérimentale approfondie sur des tâches de classification et de régression de graphes, obtenant des résultats de pointe dans diverses configurations du monde réel, incluant des graphes moléculaires et des réseaux sociaux. Le code est disponible publiquement à l’adresse suivante : https://github.com/gbouritsas/graph-substructure-networks.