Le Graph Transformer (GT) est récemment apparu comme un nouveau paradigme d’algorithmes d’apprentissage sur graphes, dépassant dans plusieurs benchmarks le modèle auparavant dominant, le Message Passing Neural Network (MPNN). Des travaux antérieurs (Kim et al., 2022) ont montré qu’avec une embedding de position adéquate, le GT peut approximer arbitrairement bien le MPNN, ce qui implique que le GT est au moins aussi puissant que le MPNN. Dans cet article, nous étudions la relation inverse et démontrons que le MPNN enrichi d’un nœud virtuel (VN), une heuristique couramment utilisée mais peu comprise du point de vue théorique, est suffisamment puissant pour approximer arbitrairement bien la couche d’attention auto-attention du GT.Plus précisément, nous montrons d’abord que si l’on considère un type particulier de transformateur linéaire, le Performer ou Linear Transformer (Choromanski et al., 2020 ; Katharopoulos et al., 2020), alors un MPNN + VN à profondeur O(1) et largeur O(1) peut approximer une couche d’attention auto-attention dans le cadre du Performer/Linear Transformer. Ensuite, grâce à une connexion entre le MPNN + VN et DeepSets, nous prouvons que le MPNN + VN à largeur O(n^d) et profondeur O(1) peut approximer arbitrairement bien la couche d’attention auto-attention, où d désigne la dimension des caractéristiques d’entrée. Enfin, sous certaines hypothèses, nous proposons une construction explicite du MPNN + VN à largeur O(1) et profondeur O(n) permettant d’approximer arbitrairement bien la couche d’attention auto-attention du GT.Du point de vue expérimental, nous démontrons que : 1) le MPNN + VN constitue une base étonnamment performante, dépassant le GT sur le jeu de données récemment proposé, le Long Range Graph Benchmark (LRGB) ; 2) notre implémentation du MPNN + VN améliore significativement les résultats initiaux sur une large gamme de jeux de données OGB ; 3) le MPNN + VN surpasse à la fois le Linear Transformer et le MPNN pur dans une tâche de modélisation climatique.