グラフトランスフォーマー（GTs）は、メッセージパッシング型グラフニューラルネットワーク（GNNs）よりも理論的に表現力が優れているとされる有望なアーキテクチャとして注目されている。しかし、従来のGTモデルは少なくとも二次時間計算量を要するため、大規模なグラフにはスケーラブルでないという課題がある。近年、線形時間計算量を達成するGTモデルがいくつか提案されているが、それらは依然として多くの代表的なグラフデータセットにおいてGNNのパフォーマンスに及ばず、実用的な表現力に対する懸念が残っている。本研究では、GTの表現力とスケーラビリティのトレードオフを適切にバランスさせるために、線形計算量を実現しつつ高次の多項式表現力を有する「Polynormer」という新しいGTモデルを提案する。Polynormerは、入力特徴量上に高次多項式を学習する新たなベースモデルに基づいている。このベースモデルが置換同変性（permutation equivariant）を満たすようにするため、グラフのトポロジーとノード特徴量を別々に統合し、局所的およびグローバルな同変性を保つアテンションモデルを構築している。その結果、Polynormerは線形の局所からグローバルへのアテンションスキームを採用し、アテンションスコアによって制御される係数を持つ高次同変多項式を学習する。Polynormerは、数百万ノードを含む大規模グラフを含む、合計13の同質性（homophilic）および異質性（heterophilic）データセット上で評価された。広範な実験結果から、非線形活性化関数を用いなくても、Polynormerは多数のデータセットにおいて最先端のGNNおよびGTベースラインを上回る性能を発揮することが明らかになった。