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
Sep 27, 2026

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

Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.

Filippo Maria Bianchi

UiT The Arctic University of Norway · NORCE Norwegian Research Centre

Graph Neural NetworksGNN ExpressivityMessage Passing Neural Networks
AskPDF
Nov 29, 2021

Understanding over-squashing and bottlenecks on graphs via curvature

Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of kk-hop neighbors grows rapidly with kk. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.

Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain +2

University of Oxford · Imperial College London · Twitter

Graph RewiringOver-SquashingMessage Passing Neural Networks
AskPDF
May 22, 2026

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

Message-passing neural networks (MPNNs) often suffer from an information bottleneck when capturing long-range dependencies, leading to the oversquashing (OSQ) phenomenon. Alongside spatial connectivity enrichment (e.g., rewiring), recent studies have shown that spectral filtering can yield strong long-range learning outcomes, as spectral operators enable global information mixing that alleviates OSQ. These approaches achieve this either by stabilizing the Jacobian energies in deep propagation or by guaranteeing OSQ mitigation under strong theoretical assumptions. We revisit these conclusions and show that the associated Jacobian sensitivity lower bound is generally difficult to achieve in practice. We then propose S3^3GNN, which mitigates OSQ without such restrictive assumptions by lightweightly reintroducing omitted components with substantially lower computational complexity, while standard stability constraints on feature transformations remain effective under our new dynamics. Extensive experiments across diverse domains (e.g., long-range benchmarks, KGQA, and mesh-based fluid dynamics) demonstrate that S3^3GNN achieves up to an order-of-magnitude error reduction with up to 50% fewer parameters. Our code can be found in https://github.com/EEthanShi/S3-GNN.git.

Dai Shi, Luke Thompson, Linhan Luo +4

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

Graph Neural NetworksGraph Representation LearningMessage Passing Neural Networks
AskPDF