AI Paper Atlas

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

ICML 2026 · Graph learning › Graph algorithms and clustering · approach: Graph comparison and random features · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
restrict training graphs to within-capacity (diameter <= 3^L) (ablation)2-layer standard Transformer · OOD 2Chain graphs (ER n=20 training)exact match accuracyImproved
restrict training graphs to within-capacity (diameter <= 3^L) (ablation)2-layer standard Transformer · OOD 2Clique graphsexact match accuracyImproved
restrict training graphs to within-capacity (diameter <= 3) (ablation)1-layer Disentangled Transformer · ER(n=8, p=0.2) channel sharealgorithmic channel energy shareImproved
train only on graphs with diameter < 3 (cutoff below capacity) (ablation)1-layer Disentangled Transformer · OOD 2Chain graphsgeneralization to longer pathsHurt
train on graphs with diameter cutoff d > 3 (includes beyond-capacity graphs) (ablation)1-layer Disentangled Transformer · OOD 2Chain graphsgeneralizationHurt
mix in a small proportion of beyond-capacity graphs (ablation)Disentangled Transformer · OOD 2Chain graphsexact match accuracyNo clear effect
increase the proportion of beyond-capacity graphs (ablation)Disentangled Transformer · OOD 2Chain graphsexact match accuracyHurt
train on unrestricted Erdos-Renyi graphs2-layer standard Transformer · ER in-distribution vs 2Chain and 2Clique OODexact match accuracyMixed
increase number of layers / hyperparameter search under unrestricted ER trainingstandard Transformer · OOD 2Chain/2Cliqueexact match accuracyNo 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^LImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy