Research map / Graph learning / GNN architectures
Towards Principled 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.
Shows that the Edge Transformer, a triangular-attention model over node pairs, has 3-WL expressive power without positional encodings, and evaluates it on molecular regression, CLRS algorithmic reasoning, and BREC.
Problem
Graph transformers are strong empirically but their expressivity is hard to relate to the k-WL hierarchy because they depend on positional/structural encodings, while higher-order WL-aligned GNNs and transformers often underperform or are too expensive.
Approach
Applies the Edge Transformer (node-pair representations with triangular attention over intermediate nodes and value fusion) to graphs with a node-pair tokenization, proving it simulates folklore 2-WL and thus has exactly 3-WL expressive power with O(n^3) cost and no PEs required.
Key results
- On ZINC (12K), ET+RRWP reaches MAE 0.059 and ET 0.062, and on Alchemy ET reaches 0.099 MAE, outperforming the listed theoretically aligned baselines.
- On CLRS-30 the ET averages 80.13% across all algorithms versus 66.18% for the Relational Transformer and 75.98% for Triplet-GMPNN.
- On BREC the ET distinguishes 258.1 of 400 pairs, more than PPGN (233) and delta-2-LGNN (216), but fewer than the 270 distinguishable by 3-WL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add RRWP positional encodings (ablation) | ET · Zinc (12K) | MAE: 0.062 ±0.004 -> 0.059 ±0.004 | Helped |
| add RRWP positional encodings (ablation) | ET · Alchemy (12K) | MAE: 0.099 ± 0.001 -> 0.098 ± 0.001 | Helped |
| add RRWP positional encodings (ablation) | ET · Zinc-Full | MAE: 0.026 ±0.003 -> 0.024 ±0.003 | Helped |
| add RRWP positional encodings (ablation) | ET · PCQM4Mv2 validation | MAE: 0.0840 -> 0.0832 | Helped |
| use ET instead of SPE | molecular regression models · Zinc (12K) | MAE: 0.069 ±0.004 -> 0.062 ±0.004 | Helped |
| use ET instead of SPE | molecular regression models · Alchemy (12K) | MAE: 0.108 ±0.001 -> 0.099 ± 0.001 | Helped |
| use ET instead of PPGN++ | molecular regression models · Zinc-Full | MAE: 0.020 ±0.001 -> 0.026 ±0.003 | Hurt |
| use ET instead of GPTrans-L | graph transformers · PCQM4Mv2 validation | MAE: 0.0809 -> 0.0840 | Hurt |
| use ET instead of Triplet-GMPNN | CLRS · All algorithms | micro F1: 75.98 -> 80.13 | Helped |
| use ET instead of Triplet-GMPNN | CLRS · Avg. class | micro F1: 74.14 -> 75.51 | Helped |
| use ET instead of strongest baseline | CLRS · algorithm classes | micro F1 | Mixed |
| use ET instead of PPGN | graph isomorphism models · BREC All | distinguished graph pairs: 233 -> 258.1 ±1.9 | Helped |
Surprising findings
- On ZINC-Full the ET does not show superior performance over the best baselines (e.g., ET MAE 0.026 vs. PPGN++ 0.020).
- On the OOD-validation CLRS setting, the ET is weaker than Triplet-GMPNN and TEAM on Strings (51.22 vs. 75.33 and 81.25).
Limitations
- Cubic O(n^3) runtime and memory restrict the ET to mid-sized graphs.
- Expressivity result is non-uniform, holding only for a fixed graph size n.
- On BREC the ET does not distinguish all graphs distinguishable by 3-WL (258.1 vs. 270).
Experimental setup
Datasets: ZINC (12K) ZINC-Full Alchemy (12K) PCQM4Mv2 CLRS-30 BREC
Benchmarks: ZINC (12K) ZINC-Full Alchemy (12K) PCQM4Mv2 CLRS-30 BREC
Metrics: MAE micro F1 number of distinguished graph pairs
Baselines: GIN(E) CIN Graphormer-GD SignNet BasisNet PPGN++ SPE Relational Transformer Triplet-GMPNN Deep Sets GAT MPNN
Builds on: Edge Transformer Relational Transformer PPGN CLRS benchmark GraphGPS
Closest papers by meaning
- Aligning Transformers with Weisfeiler-Leman (ICML 2024 · similarity 0.92)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.91)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.90)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.90)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.89)
- Graph External Attention Enhanced Transformer (ICML 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.