cs.LGOct 2, 2026

Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

Authors: Ferran Hernandez Caralt, Simon Heilig, Adrián Bazaga, Asja Fischer, Moshe Eliasof, Pietro Liò

Organizations: Department of Computer Science and Technology, University of Cambridge, UK · Faculty of Computer Science, Ruhr University Bochum, Germany · Microsoft, London, UK · Department of Applied Mathematics, University of Cambridge, UK

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Empirical claims about the connection between over-squashing and long-range interactions in GNNs, can only be trusted if the benchmarks used to validate them genuinely require long-range interactions. The de-facto standard, the Long Range Graph Benchmark, has been repeatedly shown to be saturated by tuned short-range models, with existing synthetic alternatives being tied to specific topologies. As such, there is a lack of principled certificate of long-rangedness on arbitrary graphs. This state reflects the absence of a precise characterization of long-ranged benchmarks. We address this fundamental gap by introducing four verifiable axioms: Predictability, Tightness, Strictly kk-Range, and Topology-Invariance, that any task claiming to test kk-hop interactions must satisfy. We formally prove that violating any one of them admits failure modes that undermine conclusions drawn from the task. Based on these axioms, we introduce TRIP (Truly Ranged Interactions Problem) and its generalisation GRIP (Generally Ranged Interactions Problem), constructive procedures that turn any graph into a provably long-ranged task by drawing features from stable distributions. Moreover, by construction, GRIP admits a closed-form, per-range Maximum-Likelihood oracle that yields the first a priori per-range lower bound on test error available on any benchmark. Using our framework, we: (i) audit 4 common long-range benchmarks and identify their failures modes with respect to our axioms; (ii) on TRIP-instantiated topologies, we find a popular notion of curvature is uncorrelated with GNN performance, supporting topological-vs-computational bottleneck distinction; and (iii) we show that a novel benchmark's over-squashing measures factors beyond pure long-rangedness. Code to use the framework and reproduce experiments is released https://github.com/ferranhernandezc/graph-grip.

Figures & tables

Figure 1: Percentage of GLoRa graphs (alleged range ∈[10,15]\in[10,15] , parameters as in [ 39 ] ) classifiable using only information within range ≤k\leq k for k=1,…,9k=1,\ldots,9 .
BenchmarkAx. 1Ax. 2Ax. 3Ax. 4Evidence
LRGB [ 14 ]✓✓QQ v✓[ 34 , 23 , 24 , 6 ]
LRIM [ 26 ]✓✓✓?Periodic grid only
GLoRa [ 39 ]✓✓×\times?DAG only; Figure 1
ECHO- sssp [ 27 ]✓✓QQ v?Figure 2
ECHO- ecc. [ 27 ]✓✓QQ v?Figure 2
ECHO- charge [ 27 ]✓✓QQ v?Figure 2
Table 1: Axioms satisfied by existing long-range benchmarks. “ ? ” marks an axiom that cannot be tested because the benchmark is restricted to a single topology family. “ QQ -violation” under Axiom 3 indicates a quantitative violation supported by post-hoc measurement.
Figure 2: Test error vs. post-hoc range Equation 1 for ECHO baselines trained with the hyperparameters of [ 27 ] . On none of these node regression tasks does higher measured range correspond to lower error.
Figure 4: GRIP on a 22-cycle reveals an averaging bias in Equation 1 . Test MSE (solid; left yy -axis) and measured range Equation 1 (dashed; right yy -axis) for GCNs trained on a 99 -dimensional GRIP (range set {1,…,9}\{1,\ldots,9\} , Gaussian-sum aggregation, cubic-root read-out) as a function of model depth ( xx -axis). The MLE oracle from Theorem 5.7 is shown as a dotted line; the GCN matches it for ranges ≤5\leq 5 and saturates afterwards.
Figure 3: TRIP on a 22-cycle isolates an over-squashing transition at k∈{7,8}k\in\{7,8\} that is not under-reaching. Test MSE (left yy -axes) and post-hoc measured range Equation 1 (right yy -axes) for residual GCNs of depth {k−1,k,k+1}\{k{-}1,k,k{+}1\} , k∈{1,…,9}k\in\{1,\ldots,9\} , on the three ff -stable distributions of Footnote 3 . The (k−1)(k{-}1) -layer GCN uniformly fails; the kk - and (k+1)(k{+}1) -layer GCNs both succeed at low kk and break down together at k∈{7,8}k\in\{7,8\} , ruling out under-reaching.
Figure 5: We show Balanced-Forman curvature is uncorrelated with GNN error on TRIP . Left: SDRF and original graphs are indistinguishable in MSE for k≤5k\leq 5 ; the divergence at k∈{6,7}k\in\{6,7\} is an artifact of SDRF eliminating the boundary Nk(u)\mathcal{N}_{k}(u) in most nodes (see footnote). Right: per-range Spearman correlation between minimum edge curvature and MSE stays in ∣ρ∣<0.4|\rho|<0.4 throughout, opposing the prediction that curvature should track GNN error on a long-range task. Standard deviation is computed across 33 seeds.
Figure 6: Test MSE on TRIP -instantiated ECHO topologies ( charge , synth ) for k∈{2,4,6,8}k\in\{2,4,6,8\} . PHDGN [ 20 ] dominates all baselines, with a gap that is absent on the original ECHO tasks of [ 27 ] . By k=4k=4 the classical baselines (GCN [ 21 ] , GIN [ 38 ] , GCNII [ 10 ] , GraphCON [ 29 ] , ADGN [ 17 ] , GRIT [ 25 ] ) saturate at MSE=1.0\mathrm{MSE}=1.0 (constant-mean baseline); only PHDGN and SWAN [ 18 ] remain meaningful learners. Standard deviation is computed over 44 seeds [ 27 ] .
Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Example of the graph used in the Proposition C.4 for n=3,k=4n=3,k=4
    k    
 12345678
synth2.043.023.443.683.843.954.024.06
charge1.542.522.873.173.33.333.333.27
Appendix
Table 2: This table shows the entropy of the distribution across all nodes of the ECHO synth and charge topologies of the amount of nodes at distance kk .
   k    
 1234567
base3.836.688.467.568.295.461.78
SDRF4.397.438.298.247.272.090.04
Appendix
Table 3: This table shows the entropy of the distribution across all nodes of the randomly generated graphs and their SDRF processed versions of the amount of nodes at distance kk .
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]4581026710
Hidden dimension[16−128][16-128]123659010837128109101
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00198290.00365910.00359310.00325980.00257520.000463930.0017660.0016224
Weight decay[10−8−10−13][10^{-8}-10^{-13}]0.000176230.0006490.000435740.000171660.0000128210.000026810.0000325520.000010521
ϵ\epsilon[0.001−1.0][0.001-1.0]0.60.626770.639910.503920.967030.187250.487710.62536
α\alpha[0.01−1.0][0.01-1.0]0.629680.791340.960590.207350.75060.0199470.240870.34108
Appendix
Table 4: Hyperparameters and their best values across tasks PH-DGN.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]448-268-
Hidden dimension[16−128][16-128]574588-2691124-
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00504460.00589670.0028226-0.00231660.00111370.0061644-
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.000132260.000341660.00099821-0.00000199950.000488120.00079115-
ϵ\epsilon[0.001−1.0][0.001-1.0]0.951110.940490.64641-0.756040.826220.60167-
γ\gamma[0.001−0.5][0.001-0.5]0.276720.0850260.1858-0.390860.381640.029949-
Appendix
Table 5: Hyperparameters and their best values across tasks for SWAN.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]44--36--
Hidden dimension[16−128][16-128]11196--10332--
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.0071390.0052292--0.00417370.0098753--
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.0000109320.00063737--6.3409e-70.00082609--
ϵ\epsilon[0.001−0.5][0.001-0.5]0.476450.088879--0.496360.35951--
γ\gamma[0.001−0.5][0.001-0.5]0.316990.27401--0.18650.29602--
Appendix
Table 6: Hyperparameters and their best values across tasks for A-DGN.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]45--45--
Hidden dimension[16−128][16-128]10880--8599--
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00566470.0071248--0.00682520.0086757--
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.000473680.00018787--0.000583960.000039939--
ϵ\epsilon[0.001−1.0][0.001-1.0]0.843990.24835--0.861250.12498--
Runtime/Epoch (s)-1.800.10--6.252.98--
Appendix
Table 7: Hyperparameters and their best values across tasks for GraphCON.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]467-458-
Hidden dimension[16−128][16-128]326343-16814916-
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00498590.00214350.0082665-0.00180150.00121010.004821-
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.000338040.000561130.00056882-0.000062970.0007080.00082622-
α\alpha[0.0−0.9][0.0-0.9]0.34130.17430.098132-0.567350.14860.8484-
Runtime/Epoch (s)-1.711.811.17-6.765.501.46-
Appendix
Table 8: Hyperparameters and their best values across tasks for GCNII.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]368-368-
Hidden dimension[16−128][16-128]542229-801726-
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00511680.00155220.0057223-0.00725990.00257870.0033032-
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.000563020.000423370.00068561-0.000206530.000374680.0000010491-
Runtime/Epoch (s)-1.691.630.560.786.526.742.05-
Appendix
Table 9: Hyperparameters and their best values across tasks for GIN.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]46--46--
Hidden dimension[16−128][16-128]2024--11419--
Learning rate[10−3−10−2][10^{-3}-10^{-2}]0.00923260.0013939--0.00272850.0011325--
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.0000185620.000089966--0.0000253230.00038465--
Runtime/Epoch (s)-1.581.67--6.536.40--
Appendix
Table 10: Hyperparameters and their best values across tasks for GCN.
HyperparameterSearch intervalsynth-2synth-4synth-6synth-8charge-2charge-4charge-6charge-8
Number of layers[k−k+2][k-k+2]45--35--
Hidden dimension[16,32,64,96,128][16,32,64,96,128]12864--12896--
Learning rate[10−4−10−2][10^{-4}-10^{-2}]0.00090.0004285--0.000970630.00017332--
Weight decay[10−13−10−3][10^{-13}-10^{-3}]0.0000622030.00066628--0.000996320.00097794--
Attention dropout[0−0.5][0-0.5]0.227910.12143--0.00228440.16741--
Number of attention heads[2][2]22--22--
Appendix
Table 11: Hyperparameters and their best values across tasks for GRIT.

Explore similar work

CardsList

  1. Reachability is not enough: Diagnosing long-range behavior in GNNs

    Sep 27, 2026Filippo Maria BianchiGraph Neural NetworksGNN Expressivity

    UiT The Arctic University of Norway · NORCE Norwegian Research Centre

  2. Understanding over-squashing and bottlenecks on graphs via curvature

    Nov 29, 2021Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain +2Graph RewiringOver-Squashing

    University of Oxford · Imperial College London · Twitter

  3. S3^3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning

    May 22, 2026Dai Shi, Luke Thompson, Linhan Luo +4Graph Neural NetworksGraph Representation Learning

    Department of Engineering, University of Cambridge, Cambridge, UK · University of Sydney, Australia