Algorithmic Graph Tasks
SSSP
Structure
7,040Graphs
2Node Feature Dim
Coverage
32Results
1Variants
3Papers
- TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
- Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning
Node regression on synthetic graphs, predicting every node’s shortest-path distance from a marked source. Uses synthetic topology plus task-specific source indicators or random node features. Evaluated by MSE.
Dataset details
Task
Single Source Shortest Path prediction on synthetic graphs (node-level distances). The primary catalog metric is MSE.
Data
The release has 7,040 synthetic graphs with 25–35 nodes sampled from multiple graph generators: 5,120 train, 640 validation, and 1,280 test graphs.
Features
Synthetic graphs provide task-specific structural inputs such as a designated source. Targets are numeric node quantities computed by the reference algorithm; positional encodings or extra structural features are model additions.
Splits and evaluation
The fixed split is 5,120/640/1,280 graphs. The paper selects models by validation MSE and reports mean log10(MSE) over 20 runs; lower is better.
Quirks and pitfalls
Targets are deterministic functions of generated topology, so generator overlap and size range determine difficulty. Random splits test interpolation; claims about algorithmic generalization require held-out sizes or graph families.
Sources
SOTA Progression
new SOTA
matches SOTA at that time
other proposed result
other baseline result
Leaderboard
| # | Model | MSE ↓ | log10(MSE) | Paper |
|---|---|---|---|---|
| 1 | TANGO-GPS | -5.5263
±
0.0838 | — | |
| 2 | TANGO-GatedGCN | -5.0626
±
0.0742 | — | |
| 3 | PH-DGN | -4.2993
±
0.0721 | — | |
| 4 | GCN-SSM + k-hop | -3.6044
±
0.0291 | — | |
| 5 | GPS | -3.5990
±
0.1949 | — | |
| 6 | GCN-SSM + eig(Λ)≈ 1 | -3.5928
±
0.1026 | — | |
| 7 | SWAN | -3.5425
±
0.0830 | — | |
| 8 | GatedGCN | -3.2610
±
0.0514 | — | |
| 9 | ADGN | -3.2417
±
0.0751 | — | |
| 10 | A-DGN | -3.2417
±
0.0751 | — | |
| 11 | GCN-SSM | -2.8206
±
0.5654 | — | |
| 12 | DRew-GCN + delay | -1.6023
±
0.0078 | — | |
| 13 | DRew-GCN | -1.5905
±
0.0034 | — | |
| 14 | GraphCON | -1.3836
±
0.0092 | — | |
| 15 | GCNII | -1.1329
±
0.0135 | — | |
| 16 | GIN | -0.5408
±
0.4193 | — | |
| 17 | DGC | -0.1483
±
0.0231 | — | |
| 18 | GRAND | -0.0942
±
0.3897 | — | |
| 19 | GraphSAGE | 0.2863
±
0.1843 | — | |
| 20 | GAT | 0.6951
±
0.1499 | — | |
| 21 | GCN | 0.9499
±
0.0001 | — | |
| 22 | A-DGN | — log10(MSE)
-3.2417
±
0.0751 | -3.2417
±
0.0751 | |
| 23 | DGC | — log10(MSE)
-0.1483
±
0.0231 | -0.1483
±
0.0231 | |
| 24 | GAT | — log10(MSE)
0.6951
±
0.1499 | 0.6951
±
0.1499 | |
| 25 | GCN | — log10(MSE)
0.9499
±
0.0001 | 0.9499
±
0.0001 | |
| 26 | GCNII | — log10(MSE)
-1.1329
±
0.0135 | -1.1329
±
0.0135 | |
| 27 | GIN | — log10(MSE)
-0.5408
±
0.4193 | -0.5408
±
0.4193 | |
| 28 | GRAND | — log10(MSE)
-0.0942
±
0.3897 | -0.0942
±
0.3897 | |
| 29 | GraphCON | — log10(MSE)
-1.3836
±
0.0092 | -1.3836
±
0.0092 | |
| 30 | GraphSAGE | — log10(MSE)
0.2863
±
0.1843 | 0.2863
±
0.1843 | |
| 31 | GPS | — log10(MSE)
-3.5990
±
0.1949 | -3.5990
±
0.1949 | |
| 32 | MP-SSM | — log10(MSE)
-4.6321
±
0.0779 | -4.6321
±
0.0779 |
SOTA performance
set a new SOTA at the time
matched the SOTA at the time