Recette pour un Transformers de graphe général, puissant et évolutif

Nous proposons une recette pour construire un Transformer de graphe général, puissant et évolutif (GPS) avec une complexité linéaire et des résultats de pointe sur un ensemble diversifié de benchmarks. Les Transformers de graphe (GTs) ont gagné en popularité dans le domaine de l'apprentissage des représentations de graphe grâce à une variété de publications récentes, mais ils manquent d'une base commune concernant ce qui constitue une bonne codification positionnelle ou structurelle, ainsi que leurs différences. Dans cet article, nous résumons les différents types de codifications avec une définition plus claire et les classifions comme étant $\textit{locale}$, $\textit{globale}$ ou $\textit{relative}$. Les GTs précédents étaient limités aux petits graphes comportant quelques centaines de nœuds ; ici, nous proposons la première architecture dont la complexité est linéaire en fonction du nombre de nœuds et d'arêtes $O(N+E)$ en dissociant l'agrégation locale des arêtes réelles du Transformer entièrement connecté. Nous soutenons que cette dissociation n'affecte pas négativement l'expressivité, notre architecture étant un approximateur universel de fonctions sur les graphes. Notre recette GPS se compose de trois ingrédients principaux : (i) la codification positionnelle/structurelle, (ii) le mécanisme de passage de messages local, et (iii) le mécanisme d'attention globale. Nous fournissons un cadre modulaire $\textit{GraphGPS}$ qui prend en charge plusieurs types de codifications et offre efficacité et évolutivité tant pour les petits que pour les grands graphes. Nous testons notre architecture sur 16 benchmarks et montrons des résultats hautement compétitifs dans chacun d'eux, mettant en évidence les avantages empiriques apportés par la modularité et la combinaison de différentes stratégies.