Research map / Graph learning / Graph algorithms and clustering
Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data
Qilin Ye, Deqing Fu, Robin Jia, Vatsal Sharan
Read the paperCheck your idea against 137,217 papers
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 |
|---|---|---|---|
| restrict training graphs to within-capacity (diameter <= 3^L) (ablation) | 2-layer standard Transformer · OOD 2Chain graphs (ER n=20 training) | exact match accuracy | Improved |
| restrict training graphs to within-capacity (diameter <= 3^L) (ablation) | 2-layer standard Transformer · OOD 2Clique graphs | exact match accuracy | Improved |
| restrict training graphs to within-capacity (diameter <= 3) (ablation) | 1-layer Disentangled Transformer · ER(n=8, p=0.2) channel share | algorithmic channel energy share | Improved |
| train only on graphs with diameter < 3 (cutoff below capacity) (ablation) | 1-layer Disentangled Transformer · OOD 2Chain graphs | generalization to longer paths | Hurt |
| train on graphs with diameter cutoff d > 3 (includes beyond-capacity graphs) (ablation) | 1-layer Disentangled Transformer · OOD 2Chain graphs | generalization | Hurt |
| mix in a small proportion of beyond-capacity graphs (ablation) | Disentangled Transformer · OOD 2Chain graphs | exact match accuracy | No clear effect |
| increase the proportion of beyond-capacity graphs (ablation) | Disentangled Transformer · OOD 2Chain graphs | exact match accuracy | Hurt |
| train on unrestricted Erdos-Renyi graphs | 2-layer standard Transformer · ER in-distribution vs 2Chain and 2Clique OOD | exact match accuracy | Mixed |
| increase number of layers / hyperparameter search under unrestricted ER training | standard Transformer · OOD 2Chain/2Clique | exact match accuracy | No clear effect |
| increase depth to L layers (ablation) | Disentangled Transformer · ER n=24 (2 layers) and n=64 (3 layers) | max perfect path length: reliable up to distance 3^L | Improved |
Closest papers by meaning
- Understanding Transformer Reasoning Capabilities via Graph Algorithms (NeurIPS 2024 · similarity 0.90)
- Transformers Struggle to Learn to Search (ICLR 2025 · similarity 0.90)
- Simulation of Graph Algorithms with Looped Transformers (ICML 2024 · similarity 0.88)
- Graph Transformers Dream of Electric Flow (ICLR 2025 · similarity 0.86)
- Dynamics of the Transformer Residual Stream: Coupling Spectral Geometry to Network Topology (NeurIPS 2026 · similarity 0.86)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.86)
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.
