Research map / Graph learning / GNN architectures
Exphormer: Sparse Transformers for Graphs
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Exphormer sparse attention (expander + global + local) to GraphGPS instead of full transformer | GraphGPS on CIFAR10 · CIFAR10 | Accuracy: +2.39 (74.69 vs 72.30) | Improved |
| add Exphormer sparse attention instead of full transformer | GraphGPS on MalNet-Tiny · MalNet-Tiny | Accuracy: +0.52 (94.02 vs 93.50) | Improved |
| add Exphormer sparse attention instead of full transformer | GraphGPS on Peptides-Func · Peptides-Func | AP: -0.0008 (0.6527 vs 0.6535) | Hurt |
| add Exphormer sparse attention instead of full transformer | GraphGPS on PCQM-Contact · PCQM-Contact | MRR: +0.03 (0.3637 vs 0.3337) | Improved |
| add Exphormer sparse attention instead of full transformer | GraphGPS on ogbn-arxiv (GCN backbone) · ogbn-arxiv | Accuracy: +1.09 (72.44 vs 71.35 GCN only) | Improved |
| remove expander edges from Exphormer (keep local + global) (ablation) | Exphormer on PascalVOC-SP · PascalVOC-SP | F1 score: expander edges add +0.0387 (0.3975 vs 0.3588) | Improved |
| remove global virtual nodes from Exphormer (ablation) | Exphormer on PascalVOC-SP · PascalVOC-SP | F1 score: -0.0293 (0.3682 vs 0.3975 all components, table shows all-components value 0.3682) | Mixed |
| remove expander edges from Exphormer (ablation) | Exphormer on MalNet-Tiny · MalNet-Tiny | Accuracy: 94.02 without expander vs 92.06 with all components | Mixed |
| remove local neighborhood edges from Exphormer (ablation) | Exphormer on CIFAR10, MalNet-Tiny, PATTERN, PascalVOC-SP · multiple | accuracy/F1: CIFAR10 -0.07; PATTERN -0.15; MalNet-Tiny +0.58 (ablation higher); PascalVOC-SP -0.0274 | Hurt |
| remove expander edges from Exphormer (ablation) | Exphormer on Peptides-Struct · Peptides-Struct | MAE: 0.2481 without expander vs 0.2643 all components (lower is better, so removing expander is better) | Improved |
| add expander edges to global+local Exphormer (ablation) | GCN+Exphormer on ogbn-arxiv · ogbn-arxiv | Accuracy: +0.22 (72.44 vs 72.22 with virtual nodes only) | Improved |
| use BigBird or Performer sparse attention in GraphGPS on ogbn-arxiv | GCN backbone · ogbn-arxiv | Accuracy: -0.19 (BigBird 71.16) and -0.43 (Performer 70.92) vs GCN only 71.35 | Hurt |
Later papers that compared with this method
21 later accepted papers report Exphormer as a baseline in their results tables; 14 of them report a better number on most of the results they share with it.
- L2G-NET: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations (ICML 2026 · better on 2 of 4 shared results)
- Adaptive Recurrent Message Passing for Test Time Computing on Graphs (ICML 2026 · better on 2 of 2 shared results)
- Graph Tokenization for Bridging Graphs and Transformers (ICLR 2026 · better on 1 of 2 shared results)
- Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs (AAAI 2026 · better on 1 of 1 shared result)
- Graph in Graph Neural Network (IJCV 2026 · better on 1 of 1 shared result)
- Primphormer: Efficient Graph Transformers with Primal Representations (ICML 2025 · better on 4 of 7 shared results)
- Best of Both Worlds: Advantages of Hybrid Graph Sequence Models (ICML 2025 · better on 2 of 2 shared results)
- Relieving the Over-Aggregating Effect in Graph Transformers (NeurIPS 2025 · better on 1 of 1 shared result)
13 more not listed.
Earlier methods this paper compares with
Named baselines from earlier accepted papers in this paper's results tables: better than 1 of 1 on most shared results.
- NAGphormer — NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs (ICLR 2023) · better on 1 of 1 shared result
Matched by method name in results tables read by AI. Authors' own tables tend to favour the newer method, and a comparison can be missed when a method is renamed.
Closest papers by meaning
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.95)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.89)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.89)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.89)
- VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections (ICLR 2024 · similarity 0.89)
- Primphormer: Efficient Graph Transformers with Primal Representations (ICML 2025 · similarity 0.89)
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.
