Une généralisation de ViT/MLP-Mixer aux graphes

Les réseaux de neurones graphiques (GNNs) ont démontré un grand potentiel dans le domaine de l'apprentissage des représentations graphiques. Les GNNs classiques définissent un mécanisme local d'échange de messages, qui propage l'information sur l'ensemble du graphe en empilant plusieurs couches. Ce paradigme souffre de deux limitations majeures : le phénomène de sur-écrasement (over-squashing) et une faible prise en compte des dépendances à longue portée, problèmes que l'on peut atténuer à l'aide d'une attention globale, mais au prix d'une augmentation significative du coût computationnel, passant à une complexité quadratique. Dans ce travail, nous proposons une approche alternative pour surmonter ces limites structurelles en exploitant les architectures ViT et MLP-Mixer introduites en vision par ordinateur. Nous introduisons une nouvelle catégorie de GNNs, appelée Graph ViT/MLP-Mixer, qui présente trois propriétés clés. Premièrement, elles captent efficacement les dépendances à longue portée et atténuent le problème du sur-écrasement, comme le montrent les expérimentations sur les benchmarks Long Range Graph Benchmark et TreeNeighbourMatch. Deuxièmement, elles offrent une meilleure efficacité en vitesse et en mémoire, avec une complexité linéaire par rapport au nombre de nœuds et d'arêtes, surpassant ainsi les modèles de type Graph Transformer et les GNNs expressifs existants. Troisièmement, elles présentent une forte expressivité en termes d'isomorphisme de graphes, puisqu'elles sont capables de distinguer au moins les graphes non isomorphes identifiables par le test 3-WL. Nous évaluons notre architecture sur quatre jeux de données simulés et sept benchmarks réels, obtenant des résultats hautement compétitifs dans tous les cas. Le code source est disponible pour assurer la reproductibilité à l'adresse suivante : \url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}.