À Quelle Puissance les Réseaux Neuronaux Graphiques Sont-ils Capables ?

Les Réseaux Neuraux sur Graphes (RNG) constituent un cadre efficace pour l'apprentissage de représentations de graphes. Les RNG suivent un schéma d'agrégation de voisinage, où le vecteur de représentation d'un nœud est calculé en agrégant et transformant récursivement les vecteurs de représentation de ses nœuds voisins. De nombreuses variantes de RNG ont été proposées et ont obtenu des résultats à la pointe de l'art dans les tâches de classification des nœuds et des graphes. Cependant, malgré la révolution apportée par les RNG dans l'apprentissage de représentations de graphes, il existe une compréhension limitée de leurs propriétés représentatives et de leurs limites. Dans cet article, nous présentons un cadre théorique pour analyser la puissance expressive des RNG pour capturer différentes structures de graphes. Nos résultats caractérisent la capacité discriminante des variantes populaires de RNG, telles que les Réseaux Neuraux Convolutifs sur Graphes (Graph Convolutional Networks) et GraphSAGE, et montrent qu'ils ne peuvent pas apprendre à distinguer certaines structures simples de graphes. Nous développons ensuite une architecture simple qui est prouvée être la plus expressive parmi la classe des RNG et qui est aussi puissante que le test d'isomorphisme de Weisfeiler-Lehman. Nous validons empiriquement nos résultats théoriques sur plusieurs benchmarks de classification de graphes, et démontrons que notre modèle atteint des performances à la pointe de l'art.