Sur l’équivalence entre le test d’isomorphisme de graphes et l’approximation de fonctions avec les GNNs

Les réseaux neuronaux sur graphes (GNNs) ont connu un grand succès dans le traitement de données structurées en graphes. À la lumière de ces avancées, l'intérêt pour l'étude de leur puissance expressive ne cesse de croître. Une branche de la recherche examine la capacité des GNNs à approximer des fonctions invariantes par permutation sur les graphes, tandis qu'une autre se concentre sur leur pouvoir en tant que tests d'isomorphisme de graphes. Notre travail établit un lien entre ces deux approches et démontre leur équivalence. Nous développons également un cadre pour évaluer la puissance expressive des GNNs, qui intègre ces deux points de vue en utilisant le langage des algèbres de σ (sigma-algèbres), permettant ainsi une comparaison de la puissance expressive de différents types de GNNs avec d'autres tests d'isomorphisme de graphes. En particulier, nous prouvons que le réseau neuronal invariant sur graphe d'ordre 2 (Invariant Graph Network) échoue à distinguer des graphes réguliers non isomorphes ayant le même degré. Nous étendons ensuite cette architecture à un nouveau modèle, Ring-GNN, qui réussit à distinguer ces graphes et obtient d'excellentes performances sur des jeux de données du monde réel.