Weisfeiler et Leman vont neuronaux : réseaux neuronaux de graphes d'ordre supérieur

Ces dernières années, les réseaux neuronaux de graphe (GNNs) sont apparus comme une architecture neuronale puissante pour apprendre des représentations vectorielles de nœuds et de graphes de manière supervisée et intégrée. Jusqu'à présent, les GNNs n'ont été évalués que de manière empirique, en montrant des résultats prometteurs. Le travail qui suit examine les GNNs sous un angle théorique et les relie à l'heuristique d'isomorphisme de graphe 1-dimensionnelle de Weisfeiler-Leman (1-WL). Nous démontrons que les GNNs ont la même expressivité que le 1-WL en termes de distinction entre des (sous-)graphes non isomorphes. Par conséquent, ces deux algorithmes partagent également les mêmes limitations. Sur cette base, nous proposons une généralisation des GNNs, appelée réseaux neuronaux de graphe $k$-dimensionnels ($k$-GNNs), capables de prendre en compte des structures de graphe d'ordre supérieur à plusieurs échelles. Ces structures d'ordre supérieur jouent un rôle essentiel dans la caractérisation des réseaux sociaux et des graphes moléculaires. Notre évaluation expérimentale confirme nos résultats théoriques ainsi que l'utilité des informations d'ordre supérieur dans la tâche de classification et de régression de graphes.