Research map / Graph learning / GNN architectures
Polynormer: Polynomial-Expressive Graph Transformer in Linear Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Polynormer, a linear-complexity graph transformer that learns high-degree equivariant polynomials on node features via a local-to-global attention scheme, reaching SOTA on 13 node classification datasets even without activations.
Problem
Graph transformers are expressive but have quadratic complexity, and existing linear graph transformers lag behind GNNs on popular node classification benchmarks; the paper targets balancing expressivity and scalability.
Approach
A base attention model whose L-layer stack learns a 2^L-degree polynomial on node features with coefficients set by attention scores; equivariant local (GAT-style sparse) and global (sigmoid-kernel linear) attention are applied sequentially (local-to-global) to make it permutation equivariant and linear in graph size.
Key results
- Polynormer-r reaches 97.46% ROC AUC on minesweeper vs 93.91% for the best baseline (up to 3.55% gain on heterophilic data).
- Polynormer-r outperforms all baselines on the large graphs, with accuracy gain up to 4.06%, e.g., 83.82% on ogbn-products.
- Polynormer without ReLU beats SOTA on 3 of 5 homophilic datasets and 4 of 5 heterophilic datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add ReLU activation (ablation) | Polynormer · ogbn-arxiv | accuracy: 71.82 -> 73.46 | Helped |
| add ReLU activation (ablation) | Polynormer · minesweeper | ROC AUC: 96.96 -> 97.46 | Helped |
| add ReLU activation (ablation) | Polynormer · questions | ROC AUC: 77.95 -> 78.92 | Helped |
| use local attention only, removing global attention (ablation) | Polynormer · roman-empire | accuracy | Hurt |
| use local attention only, removing global attention (ablation) | Polynormer · Computer | accuracy | No clear effect |
| replace sequential local-to-global attention with parallel local-and-global attention (ablation) | Polynormer · Computer | accuracy | Hurt |
| replace sequential local-to-global attention with parallel local-and-global attention (ablation) | Polynormer · Photo | accuracy | Hurt |
| replace Sigmoid with ReLU in linear global attention (ablation) | Polynormer · ogbn-products | training loss stability | Hurt |
| replace Sigmoid with ReLU in linear global attention (ablation) | Polynormer · pokec | training loss stability | Hurt |
| add ReLU activation (ablation) | Polynormer · CS | accuracy: 95.51 -> 95.53 | No clear effect |
Surprising findings
- Polynormer without any activation function outperforms many GNN and GT baselines, indicating high polynomial expressivity can substitute for nonlinearity.
- ReLU in the cosFormer-style linear global attention denominator caused NaN losses on ogbn-products and pokec, so a sigmoid kernel was used instead.
Limitations
- Local attention uses GAT-style sparse attention only; other sparse attention approaches were left to future work.
- Lower-degree monomials depend on the bias term B and the paper's analysis is partly qualitative.
- On ogbn-arxiv Polynormer without ReLU underperforms some baselines (71.82 vs 72.44 for Exphormer), and the local attention is disabled on arxiv and pokec for efficiency.
Experimental setup
Datasets: Computer Photo CS Physics WikiCS roman-empire amazon-ratings minesweeper tolokers questions ogbn-arxiv ogbn-products
Benchmarks: Computer Photo CS Physics WikiCS roman-empire amazon-ratings minesweeper tolokers questions ogbn-arxiv ogbn-products
Metrics: accuracy ROC AUC
Baselines: GCN GraphSAGE GAT GCNII GPRGNN APPNP GGCN OrderedGNN GraphGPS NAGphormer Exphormer NodeFormer
Builds on: GAT Transformer self-attention cosFormer polynomial networks
Closest papers by meaning
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.89)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.89)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.88)
- GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2025 · similarity 0.88)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.