# Polynormer: Polynomial-Expressive Graph Transformer in Linear Time

arXiv: https://arxiv.org/abs/2403.01232 · HTML: https://mlsanity.com/paper/2403.01232/

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 64 references that are in the map.
- First posted on arXiv 2 Mar 2024.

## Builds on (most cited first, 30 of 52)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Squeeze-and-Excitation Networks](https://mlsanity.com/paper/1709.01507/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [DCN V2: Improved Deep & Cross Network and Practical Lessons for Web-scale Learning to Rank Systems](https://mlsanity.com/paper/2008.13535/) (2020)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)

## Built on by (most cited first, 30 of 65)

- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning](https://mlsanity.com/paper/2412.10669/) (2024)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [Biologically Plausible Brain Graph Transformer](https://mlsanity.com/paper/2502.08958/) (2025)
- [Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling](https://mlsanity.com/paper/2505.18728/) (2025)
- [Can TabPFN Compete with GNNs for Node Classification via Graph Tabularization?](https://mlsanity.com/paper/2512.08798/) (2025)
- [Best of Both Worlds: Advantages of Hybrid Graph Sequence Models](https://mlsanity.com/paper/2411.15671/) (2024)
- [Rethinking Tokenized Graph Transformers for Node Classification](https://mlsanity.com/paper/2502.08101/) (2025)
- [Uncertainty-Aware Graph Structure Learning](https://mlsanity.com/paper/2502.12618/) (2025)
- [FairGE: Fairness-Aware Graph Encoding in Incomplete Social Networks](https://mlsanity.com/paper/2601.09394/) (2026)
- [Fixed Aggregation Features Can Rival GNNs](https://mlsanity.com/paper/2601.19449/) (2026)
- [Bridging Academia and Industry: A Comprehensive Benchmark for Attributed Graph Clustering](https://mlsanity.com/paper/2602.08519/) (2026)
- [AI Research Agents Narrow Scientific Exploration](https://mlsanity.com/paper/2605.27905/) (2026)
- [Improving Graph Neural Networks by Learning Continuous Edge Directions](https://mlsanity.com/paper/2410.14109/) (2024)
- [Beyond Grid Data: Exploring Graph Neural Networks for Earth Observation](https://mlsanity.com/paper/2411.03223/) (2024)
- [A Theory for Compressibility of Graph Transformers for Transductive Learning](https://mlsanity.com/paper/2411.13028/) (2024)
- [NTSFormer: A Self-Teaching Graph Transformer for Multimodal Isolated Cold-Start Node Classification](https://mlsanity.com/paper/2507.04870/) (2025)
- [Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs](https://mlsanity.com/paper/2511.13010/) (2025)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [Neural Interpretable PDEs: Harmonizing Fourier Insights with Attention for Scalable and Interpretable Physics Discovery](https://mlsanity.com/paper/2505.23106/) (2025)
- [Invariant Graph Transformer for Out-of-Distribution Generalization](https://mlsanity.com/paper/2508.00304/) (2025)
- [GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus](https://mlsanity.com/paper/2510.10631/) (2025)
- [Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework](https://mlsanity.com/paper/2510.18825/) (2025)

## Abstract (arXiv)

Graph transformers (GTs) have emerged as a promising architecture that is theoretically more expressive than message-passing graph neural networks (GNNs). However, typical GT models have at least quadratic complexity and thus cannot scale to large graphs. While there are several linear GTs recently proposed, they still lag behind GNN counterparts on several popular graph datasets, which poses a critical concern on their practical expressivity. To balance the trade-off between expressivity and scalability of GTs, we propose Polynormer, a polynomial-expressive GT model with linear complexity. Polynormer is built upon a novel base model that learns a high-degree polynomial on input features. To enable the base model permutation equivariant, we integrate it with graph topology and node features separately, resulting in local and global equivariant attention models. Consequently, Polynormer adopts a linear local-to-global attention scheme to learn high-degree equivariant polynomials whose coefficients are controlled by attention scores. Polynormer has been evaluated on 13 homophilic and heterophilic datasets, including large graphs with millions of nodes. Our extensive experiment results show that Polynormer outperforms state-of-the-art GNN and GT baselines on most datasets, even without the use of nonlinear activation functions.