Transformateurs de graphes sans encodages positionnels

Récemment, les Transformers pour l'apprentissage de représentations de graphes ont connu une popularité croissante, atteignant des performances de pointe sur une variété de jeux de données de graphes, que ce soit seuls ou en combinaison avec des réseaux neuronaux à passage de messages sur les graphes (MP-GNNs). L'intégration d'inductions graphiques dans l'architecture intrinsèquement agnostique en structure des Transformers sous forme d'encodages structurels ou positionnels (PEs) est essentielle pour obtenir ces résultats impressionnants. Cependant, la conception de tels encodages est délicate et diverses tentatives ont été faites pour élaborer ces encodages, notamment en utilisant les vecteurs propres du Laplacien, les probabilités relatives de marches aléatoires (RRWP), les encodages spatiaux, les encodages de centralité, les encodages d'arêtes, etc. Dans cette étude, nous soutenons que ces encodages ne sont peut-être pas nécessaires du tout, à condition que le mécanisme d'attention lui-même intègre des informations sur la structure du graphe. Nous introduisons l’Eigenformer, un Transformer de graphe utilisant un mécanisme d'attention novateur et sensible au spectre du Laplacien du graphe, et nous montrons empiriquement qu'il obtient des performances compétitives par rapport aux Transformers de graphe de pointe sur plusieurs benchmarks standards des GNN. De plus, nous prouvons théoriquement que l’Eigenformer peut exprimer diverses matrices de connectivité structurale de graphe, ce qui est particulièrement crucial lors de l'apprentissage sur des petits graphes.