Une nouvelle convolution de graphe de Weisfeiler-Lehman d'ordre supérieur

Les architectures actuelles de réseaux de neurones graphiques (GNN) reposent sur un schéma d’agrégation des voisins des sommets, ce qui limite leur pouvoir discriminant à celui du test d’isomorphisme de graphes de Weisfeiler-Lehman en une dimension (1-WL). Dans cet article, nous proposons un nouvel opérateur de convolution sur les graphes fondé sur le test de Weisfeiler-Lehman en deux dimensions (2-WL). Nous démontrons formellement que l’architecture de GNN résultante, appelée 2-WL-GNN, possède un pouvoir discriminant supérieur à celui des approches GNN existantes. Ce résultat théorique est complété par des études expérimentales menées sur des données synthétiques et réelles. Sur plusieurs benchmarks classiques de classification de graphes, nous montrons que le modèle proposé est compétitif avec les noyaux de graphes d’état de l’art ainsi que les GNN les plus performants.