Research map / Graph learning / GNN architectures
Generalizable Insights for Graph Transformers in Theory and Practice
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 the Generalized-Distance Transformer (GDT), a standard-attention graph transformer whose expressivity is characterized by GD-WL and PEs, and evaluates PEs and scaling at large scale across molecular, vision, code, and algorithmic tasks.
Problem
Graph transformer architectures vary in attention mechanisms, positional embeddings, and expressivity; existing expressivity results are tied to specific designs and empirical comparisons are on small datasets, leaving generalizable insights lacking.
Approach
A graph transformer using standard softmax attention with an attention bias from edge embeddings and absolute/relative PEs; proves it can simulate GD-WL (via Lindemann–Weierstrass linear independence of exponentials) and derives a PE expressivity hierarchy (RWSE, RRWP, LPE, SPE), then tests PEs empirically at scale.
Key results
- RRWP achieves the best mean rank (2.33) across six tasks at 16M parameters, while LPE and RWSE are competitive with much lower cost.
- GDT with RWSE achieves 203 of 260 BREC graphs distinguished, matching Graphormer-GD with RWSE (203).
- On MST, all PEs extrapolate to 256 nodes (16x training size) with F1 around 85; 15M-model LPE reaches near-perfect 10-shot transfer from Bridges to Cycles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add LPE instead of NoPE (ablation) | GDT · COCO | F1: 43.12 ± 00.85 -> 44.83 ± 00.71 | Helped |
| Add RWSE instead of NoPE (ablation) | GDT · Bridges | F1: 55.36 ± 24.94 -> 87.34 ± 03.97 | Helped |
| Use RRWP instead of NoPE (ablation) | GDT · PCQM4Mv2 | MAE: 93.6 ± 0.5 -> 90.4 ± 0.3 | Helped |
| Use RRWP instead of NoPE (ablation) | GDT · Flow | MAE: 1.73 ± 0.09 -> 1.45 ± 0.06 | Helped |
| Use RRWP instead of NoPE (ablation) | GDT · MST | F1: 93.29 ± 00.88 -> 96.04 ± 00.91 | Helped |
| Use PE variants rather than NoPE (ablation) | GDT · Flow | MAE: 1.73 ± 0.09; 1.75 ± 0.12; 1.98 ± 0.14; 1.49 ± 0.02; 1.45 ± 0.06 | Mixed |
| Scale model size from 15M to 90M | GDT + RWSE · MST | F1: 94.29 ± 00.68 | Helped |
| Scale model size from 90M to 160M | GDT + RWSE · MST | F1: 94.29 ± 00.68 -> 95.80 ± 00.18 | Helped |
| Scale model size from 90M to 160M | GDT + LPE · MST | F1: 92.86 ± 00.17 -> 93.11 ± 01.01 | Mixed |
| Transfer learned representations from Bridges to Cycles with 10 shots | GDT + LPE (15M) · Cycles | performance | Helped |
| Transfer learned representations from COCO to Pascal with up to 1000 shots | GDT + RWSE and GDT + LPE · Pascal | F1: 49.12 F1 | Helped |
| Increase test graph size to 256 nodes | GDT with evaluated PEs and model scales · MST | F1: around 85 | Helped |
Surprising findings
- Theoretical expressivity differences between PEs are less pronounced in predictive performance than efficiency differences.
- SPE, despite being theoretically more expressive, performs worse than RWSE and LPE on most tasks.
Limitations
- Learnable attention bias prevents use of memory-efficient attention (e.g., FlashAttention2, FlexAttention) during training.
- Implementation does not exploit sparsity of attention bias, causing high memory for very large graphs.
- Only four PEs studied; many other PE variants are excluded.
Experimental setup
Datasets: PCQM4Mv2 COCO-SP OGB-Code2 PASCAL-VOC-SP BREC MST Bridges Flow Cycles
Benchmarks: PCQM4Mv2 COCO-SP OGB-Code2 PASCAL-VOC-SP BREC MST Bridges Flow Cycles
Metrics: MAE F1 mean rank tokens per second GPU memory
Baselines: Graphormer-GD GRIT GraphGPS NoPE LPE SPE RWSE RRWP
Builds on: Generalized Distance Weisfeiler-Leman GRIT Graphormer GraphGPS CLRS benchmark
Closest papers by meaning
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.91)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.90)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.89)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.89)
- Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024 · 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.