Les transformateurs de graphes (GT) sont apparus comme une architecture prometteuse, théoriquement plus expressive que les réseaux de neurones sur graphes basés sur le passage de messages (GNN). Toutefois, les modèles GT classiques présentent au moins une complexité quadratique, ce qui les empêche de s’échelonner à de grands graphes. Bien qu’une série de modèles GT linéaires ait été récemment proposée, ils demeurent inférieurs aux modèles GNN sur plusieurs jeux de données graphiques populaires, soulevant ainsi un enjeu critique concernant leur expressivité pratique. Pour équilibrer le compromis entre expressivité et évolutivité des GT, nous proposons Polynormer, un modèle GT à expression polynomiale et complexité linéaire. Polynormer repose sur un modèle de base novateur qui apprend un polynôme de degré élevé à partir des caractéristiques d’entrée. Pour garantir l’équivariance par permutation du modèle de base, nous l’intégrons séparément à la topologie du graphe et aux caractéristiques des nœuds, aboutissant ainsi à des modèles d’attention locaux et globaux équivariants. Par conséquent, Polynormer adopte une stratégie d’attention linéaire locale-vers-globale afin d’apprendre des polynômes équivariants de haut degré, dont les coefficients sont régulés par des scores d’attention. Polynormer a été évalué sur 13 jeux de données homophiles et hétérophiles, incluant des graphes de grande taille comptant des millions de nœuds. Les résultats expérimentaux étendus démontrent que Polynormer surpasser les meilleures architectures GNN et GT existantes sur la majorité des jeux de données, même en l’absence de fonctions d’activation non linéaires.