Exphormer : Transformateurs creux pour les graphes

Les transformateurs de graphes se sont imposés comme une architecture prometteuse pour diverses tâches d’apprentissage et de représentation de graphes. Malgré leurs succès, il reste difficile d’échelonner les transformateurs de graphes à de grands graphes tout en maintenant une précision compétitive par rapport aux réseaux de passage de messages. Dans cet article, nous introduisons Exphormer, un cadre permettant de concevoir des transformateurs de graphes puissants et échelonnables. Exphormer repose sur un mécanisme d’attention creuse fondé sur deux composants : des nœuds globaux virtuels et des graphes expandeurs, dont les propriétés mathématiques — telles que l’expansion spectrale, la pseudorandomité et la densité faible — permettent d’obtenir des transformateurs de graphes dont la complexité est linéaire en taille du graphe, tout en permettant de démontrer des propriétés théoriques souhaitables des modèles transformateurs résultants. Nous montrons qu’en intégrant Exphormer dans le cadre récemment proposé GraphGPS, on obtient des modèles avec des résultats empiriques compétitifs sur une large variété de jeux de données de graphes, incluant des résultats de pointe sur trois d’entre eux. Nous démontrons également qu’Exphormer peut être échelonné à des jeux de données impliquant des graphes plus grands que ceux traités par les architectures antérieures de transformateurs de graphes. Le code est disponible à l’adresse suivante : \url{https://github.com/hamed1375/Exphormer}.