PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.03556v1cs.LG

TL;DR

The paper addresses the lack of a principled way to certify that graph benchmarks require long-range interactions. It introduces axioms and constructive tasks, then finds that curvature and benchmark rankings do not track long-rangedness alone.

  • Problem

    There is no principled certificate that a graph task requires a specified range on arbitrary topologies; LRGB is matched or exceeded by tuned short-range models, while LRIM has fixed topology.

    Source: §1 · p. 2, §4 · pp. 4, 6

  • Method

    The paper defines four axioms for k-range tasks and introduces TRIP and GRIP, which satisfy them on any graph topology and provide a closed-form per-range MLE oracle.

    Source: §1 · p. 2, §3.1 · p. 3, §7 · p. 9

  • Results

    On TRIP tasks, curvature in [36] is uncorrelated with GNN error, while model [20] dominates Message Passing baselines on TRIP and [27] topologies despite not dominating the original tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Because tuned range-2 predictors are competitive with state of the art on LRGB, its reported gains cannot be attributed to long-range modeling.

    Source: §4 · p. 4

    Axiom 4 fails when the underlying distribution is bounded.

    Source: §4 · p. 4

Abstract

from arXiv · show

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 $k$-Range, and Topology-Invariance, that any task claiming to test $k$-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.

1 Introduction

The paper argues that long-range benchmark claims lack a principled certificate on arbitrary graphs, then proposes axioms and constructions to address that gap. Its framework also supports benchmark audits and empirical findings about curvature and model rankings.

1 Introduction

  • The benchmark gap is the lack of a principled way to verify that real-world tasks require long-range modeling, while synthetic alternatives are tied to specific topologies.On LRGB, tuned short-range models can match or exceed long-range methods, and top models have effective range at most ≈2 [6].Source: §1 · p. 2
  • The paper asks whether a graph task can be certified a priori to require range k on any graph.It frames this as a response to benchmarks whose long-rangedness is unverified or topology-specific.Source: §1 · p. 2
  • Four verifiable axioms—Predictability, Tightness, Strictly k-Range, and Topology-Invariance—characterize long-range tasks, and violating any one admits a task where sub-k-range models solve a k-range task.The axioms are intended to make claims about long-range modeling empirically testable.Source: §1 · p. 2
  • TRIP constructs k-range tasks on any graph from stable-distribution features, while GRIP composes TRIP subproblems for richer multi-scale tasks.For GRIP tasks, a closed-form per-range MLE predictor gives an a priori lower bound on test error.Source: §1 · p. 2
  • The framework audits LRGB [14], LRIM, GLoRa, and ECHO [27] by identifying which axiom each violates.This places the benchmark audit alongside the framework’s construction and oracle contributions.Source: §1 · p. 2
  • On TRIP-instantiated topologies, the curvature in [36] is uncorrelated with GNN error; on TRIP tasks and [27] topologies, the model in [20] dominates message-passing baselines despite not dominating the original tasks.The ranking shift suggests the original tasks measure over-squashing factors beyond long-rangedness.Source: §1 · p. 2

2 Related Work

Prior work includes benchmark suites with distinct designs and architectural strategies for mitigating over-squashing. The paper positions its framework as a way to distinguish gains from long-range modeling from other factors and to complement range measurement.

2 Related Work

  • LRGB [14], LRIM, GLoRa, and ECHO [27] use different benchmark designs, but none provides a uniform definition of long-rangedness across topologies.The suites include real-world data, an Ising model on periodic grids, DAG reachability, and shortest-path or DFT-based tasks.Source: §2 · p. 2
  • Sensitivity-based analyses [36] [12] [8] connect Jacobian behavior to graph properties, while [3] distinguish topological from computational bottlenecks and [4] argue computational bottlenecks dominate in practice.Balanced-Forman curvature and Cheeger constants are among the cited topological measures [36].Source: §2 · pp. 2–3
  • The Jacobian-based range measure in [6, 22] indicates that high-performing LRGB models operate at effective range ≈2; this framework instead sets a priori task-design conditions for minimum range.Equation (1) is also used to check whether trained TRIP/GRIP models learn at the predicted range and to expose an averaging artifact.Source: §2 · pp. 2–3
  • Architectural approaches include rewiring [36] [19], dynamical-systems-inspired layers [17] [18] [20] [15], and graph transformers [33] [35], but benchmarks may confound long-range modeling with normalization, readout capacity, or trainability.The framework is designed to address that benchmark limitation by construction.Source: §2 · p. 3

3 Axiomatic Specification of Long-range Tasks

The paper defines long-range tasks through four axioms intended to make the required range meaningful across graphs. It argues that each axiom rules out a distinct failure mode that could otherwise make apparent long-range performance gains misleading.

3.1 Characterizing Long-range Tasks

  • A task is a family of joint feature-target distributions indexed by graphs, and a k-range task must require k-ranged information to be approximated rather than merely solved.The framework formalizes this setting for statistical approximators such as GNNs.Source: §3.1 · p. 3
  • Predictability requires targets to be functions of the k-hop neighborhood, while Tightness prevents target distributions from becoming unbounded as graphs grow.Tightness deliberately permits useful unbounded distributions such as the Gaussian, rather than requiring almost-sure boundedness.Source: §3.1 · p. 3
  • Strictly k-Range requires no information about the target below k hops and positive information at k hops; Topology-Invariance equalizes below-range conditional information across nodes and graphs.Without Topology-Invariance, the same nominal task can be trivial on dense graphs and intractable on sparse ones.Source: §3.1 · pp. 3–4
  • Axioms 3 and 4 make entropy and per-range MLE error graph-independent, allowing test errors on different graphs to be compared directly.The passage states that no existing long-range benchmark provides this property.Source: §3.1 · p. 4

3.2 Theoretical Properties

  • Without Tightness, a constructed target maximum over k-hop features diverges in probability as graph size grows, undermining generalization study across graph sizes.The example satisfies Axioms 1, 3, and 4 but violates Tightness.Source: §3.2 · p. 4
  • Without Strict k-Range, a shorter-range predictor can be competitive on a nominal k-range task, as illustrated by range-2 models matching or exceeding long-range methods on LRGB [34] [6].Without Topology-Invariance, averaging many k-hop features can collapse target entropy, making the task trivial on some graphs.Source: §3.2 · p. 4

4 Auditing Existing Long-range Benchmarks

The audit finds that LRGB, GLoRa, and ECHO do not establish that their tasks require long-range modeling, while LRIM has a theoretical long-range guarantee but is restricted to one topology family.

4 Auditing Existing Long-range Benchmarks

  • LRGB’s strongest models operate at effective range ≈2, making reported gains unattributable to long-range modeling.Three re-evaluations found classical short-range GNNs matched or exceeded self-described long-range methods after careful hyperparameter tuning.Source: §4 · p. 4
  • A bounded underlying distribution violates Axiom 4.The stated caveat concerns the axiom, not a demonstrated failure on a specific benchmark.Source: §4 · p. 4
  • On ECHO’s sssp task, higher measured range corresponds to lower error, but no such correlation appears for charge or eccentricity.Trained models reach measured ranges of only ≤4, and each ECHO sub-task uses a distinct topology family, so Axiom 4 cannot be tested.Source: Figure 2 · p. 5, §4 · p. 5
  • LRIM satisfies Strictly k-Range by construction, but its single periodic-grid topology means topology invariance cannot be tested.Improvements on LRIM may not transfer to general graphs.Source: §4 · p. 5
  • ≈35% of GLoRa graphs requested at ranges 10–15 are classifiable using only hops ≤9.A range-9 classifier achieves at least ≈70% accuracy on GLoRa-15 without range-10–15 information; the synthetic DAG construction also cannot test topology invariance.Source: Figure 1 · p. 5, §4 · p. 5
  • LRGB’s long-rangedness remains unknown, and LRIM’s guarantee is limited to its fixed topology family.For LRGB, tuned short-range GNNs match or exceed long-range methods; LRIM satisfies Strictly k-Range by construction, but its single topology family leaves transfer to general graphs untested.Source: §4 · pp. 4–6

5 Constructing Certifiable Long-range Benchmarks

The section constructs TRIP and GRIP as axiom-satisfying tasks on arbitrary graph topologies, with GRIP adding multirange targets and a graph-independent per-range MLE oracle. Cycle experiments test model-range behavior and expose a limitation of the post-hoc range measure.

5.1 Truly Ranged Interactions Problem (TRIP)

  • TRIP on any graph samples i.i.d. features from an f-stable distribution and sets each target from features exactly k hops away, satisfying all four axioms.Its target distribution and entropy are graph-independent.Source: §5.1 · p. 6

5.2 Generalized Ranged Interactions Problem and the per-range MLE oracle

  • GRIP combines multiple ranges and feature dimensions, satisfies the four axioms, and provides a closed-form per-range MLE predictor with graph-independent expected error.The oracle supplies an a priori error lower bound for models with a specified observation range.Source: §5.2 · p. 7

5.3 Cycle-graph Validation

  • On 22-cycles, residual GCNs of depth k and k+1 both break down at k ∈{7, 8}, while the shallower k−1 model consistently fails.The joint breakdown of models with sufficient depth rules out under-reaching as the failure mode.Source: §5.3 · p. 7, Figure 3 · p. 7
  • On 9-dimensional GRIP, the cycle-graph GCN matches the MLE oracle through ranges 1–5 but cannot extract information from ranges 6–9.The post-hoc measure reports effective range ≈3 despite demonstrated use of ranges 4 and 5.Source: Figure 4 · p. 7, §5.3 · p. 8
  • Equation (1) is an influence-weighted average that loses information about the distribution of range weights, so it can underestimate the ranges a model uses.Equal reliance on ranges 1 and 9 yields measured range 5.Source: §5.3 · p. 8

6 Empirical Findings

On TRIP-instantiated ECHO topologies, model rankings differ from those on the original tasks, and curvature is not predictive of GNN error. These findings indicate that ECHO’s model gaps are not explained by long-rangedness alone.

6 Empirical Findings

  • The experiments compare curvature predictions and model rankings under standard TRIP, including charge and eccentricity topologies and synthetic ECHO topology families.The model comparison uses ECHO’s released message-passing baselines at ranges k ∈{2, 4, 6, 8}.Source: §6 · p. 8, §6.2 · p. 8

6.1 Curvature is uncorrelated with GNN error on TRIP

  • On TRIP, per-graph curvature is not predictive of GNN error, with per-range Spearman correlation between minimum edge curvature and MSE remaining |ρ| < 0.4.The authors present this as direct empirical evidence for the topological-versus-computational bottleneck distinction.Source: §6.1 · p. 8
  • SDRF and original graphs have nearly identical MSE for k ≤5; their divergence at k ∈{6, 7} coincides with many rewired nodes having empty k-hop boundaries.Cross-graph error comparison is not fair when |N_k(u)| is 0 for approximately 70% of nodes at k=6 and 90% at k=7.Source: §6.1 · p. 8, §6.2 · p. 8

6.2 ECHO under TRIP: over-squashing beyond long-rangedness

  • On TRIP-instantiated ECHO synthetic topologies, PHDGN outperforms all message-passing baselines, while that gap is absent on the original ECHO tasks.By k = 4, GCN, GIN, GCNII, GraphCON, ADGN, and GRIT reach MSE = 1.0; PHDGN and SWAN remain meaningful learners.Source: §6.2 · p. 9
  • The ECHO model-ranking gap is explained at least in part by factors beyond pure long-rangedness, though the framework does not distinguish among candidate explanations.Candidates include computational bottlenecks, mixing capacity, and task-specific inductive biases.Source: §6.2 · p. 9

7 Conclusion

The conclusion presents a framework for certifying long-range graph tasks and reports findings on curvature and ECHO. Its accompanying intuition highlights how shorter-range correlations can make nominally long-range tasks ambiguous.

7 Conclusion

  • The paper combines four verifiable axioms, TRIP and GRIP constructions, and a closed-form per-range MLE oracle to characterize and calibrate long-range tasks.Its reported findings are that balanced-Forman curvature is uncorrelated with GNN error on truly long-range tasks and ECHO’s model-ranking gap is not explained by long-rangedness alone.Source: §7 · p. 9

A.1 Intuition behind the axioms

  • For GNNs as statistical approximators, requiring k-ranged information for approximation rather than exact solution helps rule out shorter-range correlations that could aid prediction.The authors identify such correlations as a way shorter-range models can appear to solve long-range tasks.Source: §A.1 · p. 13
  • Eccentricity may correlate with local degree, and models with range around 3 were reported despite average eccentricity of 20–25.The example illustrates why the task’s nominal distance does not characterize what shorter-range models can predict.Source: §A.1 · p. 13

A.2 On the theoretical results of the Axioms

The axioms’ propositions formalize how their violation can undermine long-range task evaluation, while the per-range MLE oracle provides an absolute error benchmark. Within an i.i.d.-feature design template, f-stability is sufficient for the axioms and aggregate-law constancy is required by Axiom 4.

A.2 On the theoretical results of the Axioms

  • Removing Axiom 2 permits targets to grow arbitrarily large with graph size, so evaluation may measure adaptation to larger predictions rather than long-range capability.This is the failure mode established by Proposition 3.1.Source: §A.2 · p. 13
  • Proposition 3.2 formalizes the documented case of range-≈2 models matching long-range architectures on LRGB [6] [23].Source: §A.2 · p. 13
  • Proposition 3.3 shows that on sufficiently large graphs, a k-power validation task can become trivial enough for a constant predictor to succeed.That could lead evaluators to conclude that the proposed range is meaningless.Source: §A.2 · p. 13
  • Theorem 5.7 gives each observation range k a closed-form error εMLE(k) that no model with effective range ≤k can beat, enabling absolute calibration of long-range information use.The error is computable before training and independent of the graph itself.Source: §A.2 · p. 13

B f-stability’s Motivation

  • Within the i.i.d.-feature design template, Axiom 4 requires the aggregate’s entropy to remain constant as boundary size n varies; f-stability is sufficient and near-necessary.Theorem 5.5 establishes sufficiency, while the near-converse is up to entropy equality.Source: B f-stability’s Motivation · p. 14

C Proofs and Lemmas

  • Appendix C contains proofs of the theoretical results, beginning with properties used throughout those proofs.Source: C Proofs and Lemmas · p. 14

C.1 Auxiliary results

The appendix supplies distributional and graph-construction results, shows how violating the axioms can undermine long-range tasks, and establishes guarantees for TRIP and GRIP. It also illustrates how feature correlations can reduce effective interaction range.

C.1 Auxiliary results

  • The appendix establishes closure results: independent normal linear combinations remain normal, Gumbel maxima shift location, and Cauchy averages remain Cauchy.For the Gumbel maximum, the location changes from µ to µ + β ln(n).Source: §C.1 · pp. 14–16
  • For any n and k, the auxiliary construction provides a graph in which every node has exactly n nodes at distance k.The proof specifies a vertex and edge construction for such graphs.Source: §C.1 · p. 16

C.2 Necessity of the axioms

  • Without Tightness, Gaussian neighborhood maxima satisfy the other stated axioms yet exceed every fixed threshold with probability tending to one as graph size grows.The proof uses the unbounded upper tail of the Gaussian maximum.Source: §C.2 · p. 16
  • Without Strict k-Range, a shorter-range predictor can improve over an even shorter-range model while still appearing to improve on a nominal range-k task.The condition excluded is that some sub-k neighborhood already contains information about the target.Source: §C.2 · p. 17
  • Without Topology-Invariance, distance-k averages can have arbitrarily low target entropy on graphs with sufficiently large distance-k neighborhoods.The construction uses concentration of averages as their size grows.Source: §C.2 · p. 17

C.3 TRIP and GRIP

  • TRIP satisfies all four axioms on any graph when built from an f-stable pair, with graph-independent target marginals and entropy.The proof uses iid features and the stability of the aggregation function.Source: §C.3 · pp. 17–18
  • GRIP’s per-range MLE predictor has expected error determined only by task parameters, readout, and observation range, independent of the graph.The result provides a graph-independent error reference for each observation range.Source: §C.3 · p. 18

D Long-rangedness and homophily

  • In the range-2 example, correlations between nearby features can introduce structural bias and reduce the effective interaction range; the authors describe this as illustrative, not a general proof.The proposed homophily–range relationship remains an open topic for further investigation.Source: D Long-rangedness and homophily · p. 18

E Data Generation

Data generation is deterministic given the topology collection, range, stable pair, and seed.

E Data Generation

  • Data generation is deterministic given the topology collection, k, the (X, f) pair, and the seed.The data and instructions for reproducing Sections 6.1 and 6.2 are identified in the passage.Source: E Data Generation · p. 19

F Inter-graph comparisons ablations

The inter-graph comparison reports node-count entropy for ECHO and randomly generated topologies, including their SDRF-processed versions.

F Inter-graph comparisons ablations

  • ECHO topology node-count entropy differs by at most 0.7 bits, while SDRF-processed graphs show larger differences in cases 6 and 7.The passage says these larger SDRF differences are discussed in the main manuscript.Source: F Inter-graph comparisons ablations · p. 19
  • Table 2 reports entropy across nodes of the number of nodes at distance k for ECHO synth and charge topologies.Source: Table 2 · p. 19
  • Table 3 reports the corresponding distance-k node-count entropy for randomly generated graphs and their SDRF-processed versions.Source: Table 3 · p. 19

G Limitations and Future Work

The framework’s theoretical guarantees require synthetic data, and future work aims to bridge that gap to real-world settings. The authors also discuss per-graph entropy as a proxy for graph complexity and report cycle-experiment configurations and runtime.

G Limitations and Future Work

  • Theoretical guarantees require synthetic data, so future work focuses on closing the gap between this framework and real-world settings.Suggested directions include using f-stable distributions to build kernels that simulate real-world data and relaxing Axiom 1 to study noise in long-range interactions.Source: G Limitations and Future Work · p. 19
  • Per-graph entropy is proposed as a proxy for real-world graph complexity, with regular topologies expected to be easier to model than varied-connectivity ones [7].The authors say this comparison requires measuring entropy for certain distributions on each graph.Source: G Limitations and Future Work · p. 19

H.1 Synthetic configurations

  • TRIP cycle experiments used hidden dimension 16, while GRIP used 64; both used learning rate 0.001 and 2,000 epochs.The Section 5 TRIP and GRIP experiments took roughly 10 hours on an Apple M5 with 16GB RAM.Source: §H.1 · p. 20

H.2 Curvature analysis

This appendix section documents curvature-experiment graph generation and settings, the ECHO hyperparameter-sweep protocol, reproduction code, and the authors’ reported use of LLMs. It also states that the supplied passages report no crowdsourcing or human-subjects research and that LLM use is discussed in Appendix J.

H.2 Curvature analysis

  • Curvature experiments generated connected graphs with an expected-degree algorithm and trained a standard GCN alongside SDRF using specified settings and runtimes.The GCN used a 0.001 learning rate, hidden dimension 32, and 2000 epochs; SDRF used 1000 loops, a 0.5 removal bound, and tau 1.0, with runtimes of roughly 8 hours and 2 hours, respectively.Source: §H.2 · p. 20

H.3 ECHO

  • ECHO models received analogous per-range hyperparameter sweeps, which stopped when a model matched the always-0 predictor; Appendix F indicates longer ranges are at least as difficult.Search settings followed [27] except for number of layers, hidden dimension, learning rate, and weight decay.Source: §H.3 · p. 20

I Code

  • The TRIP/GRIP code reproduces experiments in Sections 5 and 6.1, while other experimental results require the ECHO-grip repository.Both repositories provide further instructions.Source: I Code · p. 23

J Disclosure of LLM usage

  • The authors report using LLMs to review human-written code, write some unit tests, and script plot generation and experiments.They state that limitations are discussed in Appendix G, proofs and hypotheses are given in Appendix C, and appropriate results include standard deviations across cross-validation splits.Source: J Disclosure of LLM usage · pp. 23, 24, 26
  • The paper marks crowdsourcing, human-subjects research, participant compensation, and IRB review as not applicable.The justification states that no crowdsourcing or human-subjects research is involved.Source: J Disclosure of LLM usage · p. 29
  • The paper answers yes to describing LLM use and directs readers to Appendix J for the discussion.Source: J Disclosure of LLM usage · p. 30
Loading 2610.03556v1…