Research map / Graph learning / GNN architectures
Even Sparser Graph Transformers
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 Spexphormer, a two-stage method that trains a narrow attention-score estimator on the full expander-augmented graph, then samples a sparse per-layer attention graph from its scores to train a wider final Transformer with much lower memory.
Problem
Graph Transformers need quadratic memory in nodes and sparse variants like Exphormer still need many edges (high-degree expanders, dense input graphs), limiting scalability to large graphs.
Approach
Attention scores are consistent across network widths, so a narrow network (width 4-8) trained on the full augmented graph can identify important neighbors; a wide network is then trained on a layer-wise sampled sparse graph (fixed degree per node, reservoir sampling by attention scores), enabling regular batched matrix operations.
Key results
- Spexphormer matches Exphormer on medium graphs (e.g., Computer 91.09 vs 91.16 for Exphormer*) while using only about 7.6% of edges on Computer.
- On large datasets Spexphormer reaches 80.65 ROC-AUC on ogbn-proteins, 90.40 accuracy on Amazon2M and 74.73 on Pokec, outperforming SGFormer and NodeFormer, using about 2-3 GB GPU memory.
- Attention scores from width-4 networks are much closer to width-64 scores than uniform or random baselines in energy distance experiments on Actor and Photo.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use estimated-attention sampling instead of uniform sampling (ablation) | Spexphormer · Computer, Photo, Minesweeper, Tolokers | accuracy / ROC-AUC (×100): 86.65 ± 0.46 vs 91.09 ± 0.08; 94.21 ± 0.22 vs 95.33 ± 0.49; 84.15 ± 0.22 vs 90.71 ± 0.17; 82.56 ± 0.17 vs 83.34 ± 0.31 | Helped |
| select highest-attention edges instead of sampling (ablation) | Spexphormer · Computer, Photo, Minesweeper, Tolokers | accuracy / ROC-AUC (×100): 89.31 ± 0.31 vs 91.09 ± 0.08; 95.07 ± 0.20 vs 95.33 ± 0.49; 87.92 ± 0.26 vs 90.71 ± 0.17; 80.85 ± 0.23 vs 83.34 ± 0.31 | Mixed |
| anneal estimator temperature instead of keeping it at 1 (ablation) | Spexphormer · Computer and Photo | accuracy: 89.05 ± 0.35 vs 91.09 ± 0.08; 95.30 ± 0.16 vs 95.33 ± 0.49 | Helped |
| add layer normalization to the estimator (ablation) | Spexphormer · Computer, Photo, Minesweeper, Tolokers | accuracy / ROC-AUC (×100): 89.70 ± 0.25 vs 91.09 ± 0.08; 94.91 ± 0.18 vs 95.33 ± 0.49; 89.65 ± 0.10 vs 90.71 ± 0.17; 84.06 ± 0.10 vs 83.34 ± 0.13 | Mixed |
| use Spexphormer rather than Exphormer+GCN | Spexphormer · Computer, CS, Physics, ogbn-arxiv | accuracy: 91.59 ± 0.31 -> 91.09 ± 0.08; 95.77 ± 0.15 -> 95.00 ± 0.15; 97.16 ± 0.13 -> 96.70 ± 0.05; 72.44 ± 0.28 -> 70.82 ± 0.24 | Hurt |
| use Spexphormer rather than the strongest listed baseline | Spexphormer · Photo, WikiCS, Actor, Minesweeper, Tolokers, Roman-Empire, Amazon-Ratings, Questions | accuracy / ROC-AUC (×100): 95.36 ± 0.17 -> 95.33 ± 0.49; 78.66 ± 0.49 -> 78.2 ± 0.14; 39.01 ± 0.69 -> 38.59 ± 0.81; 92.26 ± 0.56 -> 90.71 ± 0.17; 8 | Mixed |
| use Spexphormer rather than the strongest listed baseline | Spexphormer · ogbn-proteins, Amazon2M, Pokec | ROC-AUC (×100) / accuracy: 79.53 ± 0.38 -> 80.65 ± 0.07; 89.09 ± 0.10 -> 90.40 ± 0.03; 73.76 ± 0.24 -> 74.73 ±0.04 | Helped |
Surprising findings
- Removing certain edges improved performance on Roman-Empire and Amazon-Ratings compared to adding an expander.
- Sum of top-k attention scores is substantially below one for many nodes even at k=10, so attention is not concentrated on few neighbors.
Limitations
- Attention score estimation requires large CPU memory (up to 500GB) for the largest datasets, which is infeasible for extremely large graphs.
- Attention scores are computed in a separate stage rather than dynamically with sampling.
- MPNN components and virtual nodes are omitted, and theoretical compressibility results are existence claims rather than the practical narrow network.
Experimental setup
Datasets: Amazon Photo Amazon Computer Coauthor CS Coauthor Physics WikiCS ogbn-arxiv Actor Minesweeper Tolokers Roman-Empire Amazon-Ratings Questions
Benchmarks: Amazon Photo Amazon Computer Coauthor CS Coauthor Physics WikiCS ogbn-arxiv Actor Minesweeper Tolokers Roman-Empire Amazon-Ratings Questions
Metrics: accuracy ROC-AUC GPU memory (MB) energy distance
Baselines: GCN GraphSAGE GAT GraphSAINT NodeFormer SGFormer GraphGPS NAGphormer GOAT GloGNN Exphormer SIGN
Builds on: Exphormer GraphSAGE GraphGPS Johnson-Lindenstrauss lemma
Closest papers by meaning
- Relieving the Over-Aggregating Effect in Graph Transformers (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.88)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.88)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.88)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.88)
- Transformers Learn Faster with Semantic Focus (NeurIPS 2025 · similarity 0.87)
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.