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

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

Ferran Hernandez Caralt1 Simon Heilig2 Adrián Bazaga3 Asja Fischer2 Moshe Eliasof4 Pietro Liò1

arXiv:2610.03556v1 [cs.LG] 2 Oct 2026

1

Department of Computer Science and Technology, University of Cambridge, UK 2 Faculty of Computer Science, Ruhr University Bochum, Germany 3 Microsoft, London, UK 4 Department of Applied Mathematics, University of Cambridge, UK

fh455@cam.ac.uk, simon.heilig@rub.de, adrianbazaga@microsoft.com, asja.fischer@rub.de, me532@cam.ac.uk, pl219@cam.ac.uk

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 shortrange 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 longrangedness. Code to use the framework and reproduce experiments is released https://github.com/ferranhernandezc/graph-grip.

1

Introduction

The dominant paradigm in graph representation learning, message-passing GNNs, propagates information by iteratively aggregating features from one-hop neighbors [21, 38]. This local inductive bias is highly effective in domains ranging from molecular property prediction to network optimisation [32, 11, 37, 13]. However, it is also known to be limited when learning depends on the communication of distant nodes – a failure mode linked to over-squashing [2, 36, 12, 8]. A sizeable line of work has proposed architectures designed to mitigate over-squashing: graph rewiring [36, 19], dynamical-systems-inspired layers [17, 18, 20, 15, 5], and graph transformers [33, 35]. While 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Track on Evaluations and Datasets.

these methodologies are different in their approach, the common thread is that the alleviation of over-squashing is validated by empirical gains on long-range benchmarks. The Benchmarking Gap. While many graph benchmarks exist, as discussed later, the core shortcoming is that there persists a lack of a principled way to verify that a real-world benchmark genuinely require long-range modeling. The Long Range Graph Benchmark (LRGB) [14], one of the most common benchmarks, has now been thoroughly studied multiple times. In particular, it was shown that careful hyperparameter tuning and stronger final readout layers allow classical GNNs to match or exceed the performance of long-range tailored methods [34, 24, 23]. Moreover, [6] introduced a post-hoc Jacobian-based range measure, showing that the highest-performing models on LRGB use an effective range of at most ≈ 2, i.e., not long-range interactions. Another avenue is synthetic alternatives, that rely on rings [12, 8], periodic grids [26] and DAGs [39], and graph motifs [27]. These benchmarks improved the connection between over-squashing and long-range due to their construction, however, they also remain limited to specific, pre-defined and synthetic topologies. Therefore, the empirical evidence underpinning a substantial fraction of the over-squashing and long-ranged literature rests on benchmarks whose long-rangedness is unverified or limited to specific cases. Our Approach. To address the fundamental limitations discussed above, we seek to address the following question: given a graph task, can we a priori certify that it requires range k, on any graph? To fully answer this question, in this paper, we introduce the following: • An axiomatic characterization of long-range tasks. We state four verifiable axioms: Predictability, Tightness, Strictly k-Range, Topology-Invariance, and prove that any violation admits a benchmark in which sub-k-range models can solve a k-range task (Section 3.1). • A constructive framework that provably satisfies all four axioms. TRIP produces a krange task on any graph by drawing features from a stable distribution; GRIP composes TRIP sub-problems for richer multi-scale tasks (Section 5). • A per-range MLE oracle. For any GRIP-generated task we derive a closed-form MaximumLikelihood predictor conditioned on the k-hop neighborhood. To our knowledge this is the first a priori lower bound on test error available for any long-range graph benchmark (Theorem 5.7), thus enabling direct quantification of how much information GNNs can extract from certain ranges relative to the known optimal. • An audit of existing long-range benchmarks. We identify the specific axiom that LRGB [14], LRIM [26], GLoRa [39] and ECHO [27] violate (Section 4). • Two empirical findings enabled by the framework. On TRIP-instantiated topologies, the curvature described in [36] is uncorrelated with GNN error, supporting the topological-vscomputational bottleneck distinction of [3] (Section 6.1). On TRIP-instantiated problems and the topologies introduced in [27], the model developed in [20] dominates all Message Passing baselines – despite not being dominant on the original tasks – suggesting that the original tasks measure over-squashing influenced by factors other than long-rangedness (Section 6.2).

2

Related Work

Empirical Long-Range Benchmarks. LRGB [14] popularized the use of average graph diameter and domain knowledge as proxies for long-rangedness. Using it, more complex methods were proposed and validated on it [15, 18, 4, 5, 20]. But these were followed by stronger baselines [34, 24, 23]. Differently, the recent LRIM [26] replaces real data with the Ising model on periodic grids and provides a lower bound for short-range predictors; GLoRa [39] introduces synthetic source-to-sink reachability tasks on DAGs; ECHO [27] considers synthetic shortest-path-based tasks, and DFT-based molecular tasks. Overall, all four benchmark suites address the over-squashing problem with different design choices, but none satisfy a uniform, consistent definition of long-rangedness across topologies. Theoretical Measures of Over-squashing. Sensitivity-based analyses [36, 12, 8] bound the (L) (0) (L) Jacobian ∂hv /∂hu (the hidden representation of node v at layer L, hv w.r.t the one of node (0) u at layer 0, hu ) in terms of model parameters and graph topology, identifying low Cheeger 2

constant or negative balanced-Forman curvature as topological bottlenecks [36]. [3] draw a sharper distinction between topological bottlenecks and computational bottlenecks (vanishing gradients, ill-conditioned dynamics), and [4] argue the latter is the dominant driver in practice. [6, 22] introduce the Jacobian-based range measure of a function F on the features X of a graph G = (V, E). P ∂(F(X))u dG (u, v) v∈V ∂xv , (1) ρ̂u (F) := P ∂(F(X))u v∈V

∂xv

and use it to certify that high-performing LRGB models operate at range ≈ 2. Our framework is complementary: we provide a priori task-design conditions guaranteeing minimum range, then use Equation (1) to verify that GNNs trained on TRIP/GRIP indeed learn at the predicted range, and to expose a previously unnoticed averaging artifact of the measure, as discussed in Section 5. Architectural Mitigations of Over-squashing. Approaches to alleviate over-squashing include curvature-aware rewiring [36], multi-hop and dynamic rewiring [19], dynamical-systems-inspired layers [17, 18, 20, 15, 5], and graph transformers [33, 35]. A common and persistent limitation of this vast array of approaches is the available benchmarks, they lack a certification of whether a reported improvement reflects long-range modeling, normalization, read-out capacity [34], or trainability [4, 31]. The framework developed in our work, discussed in Sections 3.1 and 5, is designed to address this limitation by construction.

3

Axiomatic Specification of Long-range Tasks

In this Section we present four axioms that characterize long-range tasks in graph learning. We begin by providing notation used throughout the paper, followed by presenting the axioms in Section 3.1, and we discuss their properties and necessity in Section 3.2. Notation. Let G = (V, E) denote a finite undirected graph. We use xu ∈ Rdx and yu ∈ Rdy for the (random) features and targets of node u ∈ V , with capitals Xu , Yu for the random variables. H denotes (conditional) entropy and I(·; ·) mutual information. Given a node u, we write Gku ⊂ G with nodes Vuk = {v ∈ V : dG (u, v) ≤ k} for the k-hop neighborhood, and overload Gku to denote S closed k k the random variables including {Xv : v ∈ Gu } Eu . We write Nk (u) = {v : dG (u, v) = k} for the k-hop boundary. Finally, P<∞ (R) denotes finite multisets of R. 3.1

Characterizing Long-range Tasks

A task on graphs is a family of joint distributions {(Xu , Yu )u∈V } indexed by graphs G. This statistical formulation is used to reflect that GNNs are statistical approximators, learning from data distributions. So, we argue that to benchmark the k-ranged capabilities of GNNs, tasks should require k-ranged information to be approximated, not solved 1 . So, we say it is a k-range task if it satisfies all of: 1. Predictability. Yu = g(Gku ) for some measurable g, for every u and every G. 2. Tightness. The family {Yu : G, u ∈ V (G)} is uniformly tight: for every δ > 0 there exists M < ∞ such that P(∥Yu ∥ > M ) < δ for all G and all u. ′

3. Strictly k-Range. I(Yu ; Gku ) = 0 for every k ′ < k, and I(Yu ; Gku ) > 0. Equivalently, ′ H(Yu | Gku ) = H(Yu ) for k ′ < k and H(Yu | Gku ) < H(Yu ). 4. Topology-Invariance. For every k ′ < k and every pair of graphs G, G̃ and nodes u ∈ ′ ′ V (G), ũ ∈ V (G̃), H(Yu | Gku ) = H(Yũ | G̃kũ ). What each axiom rules out. Axiom 1 is a sanity check; the proofs below extend straightforwardly to probabilistic g. Axiom 2 (Tightness), the standard notion of distributional boundedness, rules out tasks whose targets blow up as the graph grows; we deliberately avoid the stronger “almostsure boundedness” since that would exclude useful unbounded distributions like the Gaussian and 1 More details in Appendix A.1

3

the Cauchy. Axiom 3 (Strictly k-Range) is the substantive long-range condition: no sub-k-hop neighborhood carries any information about Yu , so any model whose effective range is < k is reduced to predicting Yu as a single random variable, so it cannot beat the constant-mean baseline. Axiom 4 (Topology-Invariance) ensures that the conditional information content available below the target range is identical across nodes and graphs; without it, the same nominal task can be trivial on dense graphs and intractable on sparse ones, voiding cross-topology comparison. ′

What each axiom enables. Together, Axioms 3 and 4 imply that Yu does not depend on Gku for k ′ < k, so the entropy H(Yu ) and the per-range MLE error are graph-independent constants determined only by the task-design parameters. This is what makes test errors on different graphs directly comparable, a property no existing long-range benchmark provides. 3.2

Theoretical Properties

In this Section we discuss the theoretical properties of the 4 proposed axioms in our framework. Notably, we show that not satisfying any one of Axioms 1–4 results in a benchmark whose performance gains can not be attributed to long-range modeling. We provide complete proofs to the theoretical results presented in this Section, in Appendix C and more detailed explanations of the results in Appendix A.2. Proposition 3.1 (Tightness is necessary). Fix k > 1 and let X ∼ N (0, 1). Let {Gn } be a sequence of graphs in which every node u satisfies |Nk (u)| ≥ n, and define Yu = maxv∈Nk (u) Xv . The construction satisfies Axioms 1, 3, and 4, but the family {Yu } is not tight: for every M ∈ R, P(Yu > M ) → 1 as n → ∞.2 This Proposition implies that, if Axiom 3 is not satisfied graphs of increasing size may be built such that the norm of their predictions will become arbitrarily large. This forbids the study of GNN generalization over varying graph sizes. Proposition 3.2 (Strict k-Range is necessary). Suppose a task satisfies Axioms 1, 2, 4 with target ⋆ range k, but there exists i < k with H(Yu | Giu ) < H(Yu | Gi−1 u ). Let fi be the optimal rangei predictor under any continuous error measure err. Considering a finite set of known range-k functions, and f the one where the error measure is minimum, whenever err(f ) > err(fi⋆ ), an ⋆ improvement attained at range i from fi−1 to fi⋆ is reportable as an improvement at range k. Notably, Proposition 3.2 is reflected in real-world experiments — it mirrors the documented shortcomings of LRGB: [34] and [6] show that range-2 models match or exceed putative long-range architectures on it. Proposition 3.3 (Topology-Invariance is necessary). Fix k > 1. Sample xu ∼ X i.i.d. from any distribution with finite variance, and let yu be the average of features at distance exactly k from u. The task satisfies Axioms 1, 2, 3, but for every ε > 0 there exist graphs G on which H(Yu ) < ε. The construction in Proposition 3.3 works by taking G with |Nk (u)| large, so that the average concentrates by the central limit theorem; the marginal entropy of Yu collapses, even though Yu formally depends on range-k features. In practice, it implies that if Axiom 4 is not satisfied, the benchmark might be trivial for certain graphs, thus skewing research on long-range interactions models to not account for these graphs.

4

Auditing Existing Long-range Benchmarks

We now use Axioms 1–4 to audit the four most prominent long-range benchmarks, discussed below, and summarized in Table 1. LRGB [14]. Three independent re-evaluations [34, 24, 23] show that classical short-range GNNs match or exceed self-described long-range methods after careful hyperparameter tuning, and [6] confirms via Equation (1) that the strongest models operate at effective range ≈ 2. This is a quantitative violation of Axiom 3 in the sense of Proposition 3.2: the optimal range-2 predictor is competitive with SOTA, so reported gains cannot be attributed to long-range modeling. 2 If the underlying distribution is instead bounded, Axiom 4 fails; see Appendix C.

4

GCN

Charge

GCNII

GIN

100

PHDGN

MAE

60 40 1 2 Ranged Measure

SSSP

GRIT

3

5.3 5.2

2 1

5.1

20

SWAN

4

5.4

80

MAE

GraphCON

Eccentricity

MAE

ADGN

0

2 3 Ranged Measure

2

3 4 Ranged Measure

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. S LRIM [26]. The Ising-model construction on a periodic grid satisfies Axiom 3 by construction (a non-trivial lower bound for short-range predictors is known). However, since the benchmark is restricted to a single topology family, Axiom 4 cannot be tested – improvements may not transfer to general graphs.

Proportion (%)

40 GLoRa [39]. A purely synthetic benchmark on directed 35 acyclic graphs with a designated source and sink. Node 30 features come in three classes (source, filler, hole); the 25 task is to detect whether a path exists from source to sink 20 15 avoiding hole nodes. The work claims that solving this 10 requires range k equal to the source-hole distance. We 5 point out two issues. First, as a synthetic DAG benchmark 0 1 2 3 4 5 6 7 8 9 restricted to one topology family, the LRIM caveat applies: Range Axiom 4 cannot be tested. Second, GLoRa fails Axiom 3, because its construction does not enforce that every in- Figure 1: Percentage of GLoRa graphs stance requires long-range information: if for example all (alleged range ∈ [10, 15], parameters as neighbors of the source are hole nodes, a range-1 model in [39]) classifiable using only informaclassifies the instance correctly. Figure 1 quantifies this. tion within range ≤ k for k = 1, . . . , 9. On GLoRa graphs generated at requested ranges 10–15, ≈ 35% of instances are correctly classifiable using only information at hops ≤ 9. A range-9 classifier therefore achieves at least ≈ 70% accuracy on GLoRa-15 (correct on the 35% short-resolvable instances; majority-class on the rest), without any range-10–15 information.

ECHO [27]. Three synthetic shortest-path-style sub-tasks (sssp, eccentricity, diameter) on randomized instances of base topology families, plus two real-world DFT-based molecular tasks (charge, Benchmark Ax. 1 Ax. 2 Ax. 3 Ax. 4 Evidence energy). We note that, eccentricity, for instance, is the longest shortest LRGB [14] ✓ ✓ Qv ✓ [34, 24, 23, 6] LRIM [26] ✓ ✓ ✓ ? Periodic grid only path from a node, which is plausibly GLoRa [39] ✓ ✓ × ? DAG only; Figure 1 ECHO-sssp [27] ✓ ✓ Qv ? Figure 2 correlated with the degrees of the ECHO-ecc. [27] ✓ ✓ Qv ? Figure 2 immediate neighbors of that node – ECHO-charge [27] ✓ ✓ Qv ? Figure 2 but the achievable accuracy from such TRIP/GRIP (this work) ✓ ✓ ✓ ✓ Theorem 5.5 correlations alone is not characterized in [27]. To probe this empirically, we trained ECHO baselines with the recommended hyperparameters in [27], and computed their post-hoc range Equation (1). Figure 2 reports the relationship between measured range and test error. Our findings show that only on sssp, a higher measured range correspond to lower error. However, on charge and eccentricity we observe no correlation. Moreover, the trained models reach a measured range of only ≤ 4. Hence, range-> 4 behavior cannot be certified by evaluating with ECHO benchmarks. Moreover, we note that each ECHO sub-task considers a distinct topology family, so Axiom 4 cannot be tested as well.

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. “Q-violation” under Axiom 3 indicates a quantitative violation supported by post-hoc measurement.

5

In conclusion, the long-ranged nature of benchmarks LRGB [14], GLoRa [39] and ECHO [27] is unknown. LRIM [26] provides solid theoretical guarantees of its long-rangedness while using a real-world physics problem, making it a strong benchmark to assess GNNs that focus on longrange interactions modelling. It’s only limitation is that the graph topology is fixed. Consequently, developments tested exclusively on it might not generalize to other topologies. This analysis motivates the need of a general framework to stress test GNNs under arbitrary ranges and topologies.

5

Constructing Certifiable Long-range Benchmarks

The four axioms in Section 3 can be satisfied on any graph or collection of graphs, provided we choose the appropiate g (from Axiom 1) and sample the features from the distributions with the right properties to satisfy the other axioms. More specifically, we will use a concept, called strict stability of distributions under aggregation. In what follows, we formalize this concept as it is a necessary to give the definition of the task that may satisfy axioms 1 through 4. Definition 5.1 (f -stable distribution). 3 For f : P<∞ (R) → R, a real random variable X is f stable if there exists a random variable Y such that, for every n ≥ 1 and every i.i.d. sample d X1 , . . . , Xn ∼ X, f ({X1 , . . . , Xn }) = Y . Example 5.2. We give three examples of such distribution-function pairs covering the normal, heavy√ tailed, and extreme-value regimes: (i) X ∼ N (0, σ 2 ) with f ({x1 , . . . , xn }) = (x1 + · · · + xn )/ n, (ii) X ∼ Cauchy(x0 , γ) with f ({x1 , . . . , xn }) = (x1 + · · · + xn )/n, and (iii) X ∼ Gumbel(µ, β) with f ({x1 , . . . , xn }) = maxi xi − β ln n. Proposition 5.3 (Closure properties). Let X be f -stable and X̃ be f˜-stable. Then: (i) for any measurable g : R → R, X is (g ◦ f )-stable, and (ii) The pair (X, X̃) is F -stable. 5.1

Truly Ranged Interactions Problem (TRIP)

To make sure Axiom 1 is satisfied, it is sufficient to deterministically calculate Yu . To define a task that satisfies Axiom 3, we sample features i.i.d. at each node, and define the target as a function of the features at distance exactly k. To satisfy Axioms 3,4, we use an aggregator f for which the feature distribution is f -stable: the aggregate then has the same distribution regardless of how many neighbors reside at the boundary. Definition 5.4 (TRIP). A Truly Ranged Interactions Problem (TRIP) at range k is parameterized by an f -stable pair (X, f ) and consists, for any graph G = (V, E), of: (i) sampling features xu ∼ X i.i.d. for every u ∈ V , and (ii) setting targets yu = f ({xv : v ∈ Nk (u)}). The task is to predict yu for every u ∈ V given G and {xu }u∈V . Theorem 5.5 (TRIP satisfies all four axioms). For any graph G and any f -stable pair (X, f ), the TRIP task at range k satisfies Axioms 1–4. In particular, the marginal Yu and the entropy H(Yu ) are graph-independent constants determined only by (X, f ). Theorem 5.5 implies that, we can apply TRIP to any kind of graph and the statistical properties of the features X and the targets Y will remain consistent. Thus enabling direct comparisons of over-squashing under long-rangedness accross different graphs. Furthermore, in [1] it was shown that a message-passing neural network (MPNN) equipped with random node features are universal approximators of permutation-invariant functions on graphs of bounded size; Any TRIP-generated benchmark can therefore be learned by MPNN equipped with random node features. The empirical question we address in Section 5.3 is: at which range a given architecture fails to learn them? 5.2

Generalized Ranged Interactions Problem and the per-range MLE oracle

To express tasks combining information from multiple ranges and feature dimensions, we generalize TRIP to a multivariate target whose complexity is controlled by the set of involved ranges and the choice of f -stable distributions. x Definition 5.6 (GRIP). Let {(Xi , fi )}di=1 be dx pairs of fi -stable distributions and let Ki ⊆ N≥1 be a finite set of ranges per feature. For each node u sample xu ∈ Rdx with (xu )i ∼ Xi independently. For

3 Definition 5.1 mirrors the classical notion of strict stability under f , which generalizes the well-known stability of

Gaussian, Cauchy, and Lévy distributions under summation [30]

6

MSE (layers=k-1) Ranged Measure (layers=k-1)

MSE (layers=k) Ranged Measure (layers=k)

cauchy

MSE (layers=k+1) Ranged Measure (layers=k+1)

gumbel

normal

5

6

Ranged Measure

4

MSE

5

3 2

4

1

3 1

2

3

4

5

k

6

7

8

9

1

2

3

4

5

k

6

7

8

9

1

2

3

4

5

k

6

7

8

9

0

Figure 3: TRIP on a 22-cycle isolates an over-squashing transition at k ∈ {7, 8} that is not underreaching. Test MSE (left y-axes) and post-hoc measured range Equation (1) (right y-axes) for residual GCNs of depth {k−1, k, k+1}, k ∈ {1, . . . , 9}, on the three f -stable distributions of Theorem 5.1. The (k−1)-layer GCN uniformly fails; the k- and (k+1)-layer GCNs both succeed at low k and break down together at k ∈ {7, 8}, ruling out under-reaching. P
(i,k) each (i, k) ∈ {1, . . . , dx } × Ki , definePŷu = fi {(xv )i : v ∈ Nk (u)} . Stack into ŷu ∈ R i |Ki | and apply a measurable read-out h : R i |Ki | → Rdy to obtain yu = h(ŷu ). S Following the logic in Theorem 5.5, GRIP satisfies Axioms 1–4 with target range k = max i Ki . Notably, GRIP admits a closed-form per-range Maximum-Likelihood predictor, the only a priori lower bound on test error available for any range on any graph.

Theorem 5.7 (Per-range MLE oracle). Fix a GRIP task with parameters {(Xi , fi , Ki )}i and readout h, and let k ⋆ ≥ 0 be a target observation range. Let X̂i be the MLE realisation of Xi . The ⋆ Maximum-Likelihood predictor of Yu given Gku is h(ỹu ), where for each (i, k),
 fi {(xv )i : v ∈ Nk (u)} if k ≤ k ⋆ ,
ỹu(i,k) = fi {X̂i } if k > k ⋆ . The expected error of this predictor is a graph-independent function of ({(Xi , fi , Ki )}i , h, k ⋆ ) alone, and provides a lower bound for any model with effective range ≤ k ⋆ . Theorem 5.7 is a result of the invariance principle for MLEs [9, §7.2]. Theorem 5.7 allows addressing a question that existing long-range benchmark lack: at what range does a model begins to outperform the optimal range-(k ⋆ −1) predictor? For example: for X ∼ N (0, 1) and f ({x1 , . . . , xn }) = √ (x1 + · · · + xn )/ n, the MLE of X from a single observation is X̂ = 0, hence f ({X̂}) = 0. Cycle-graph Validation MLE

GNN

Ranged Measure

3.0

0.8

2.5

Ranged Measure

To verify that TRIP behaves as predicted, we trained GCN with one residual connection per layer (with complete experimental details provided in Appendix H) on standard TRIP on cycles of length 22 for ranges k ∈ {1, . . . , 9}, with model depths {k−1, k, k+1}, repeated for the three f -stable distributions shown in Section 5. In Figure 3 we show that (i) the (k−1)-layer GCN consistently struggles learning the task (i.e., it yields high MSE; the learned range is ≈ 0, as predicted by Axiom 3); (ii) the k-layer GCN learns the task at low k and its measured range Equation (1) tracks k, with performance degrading for k ∈ {7, 8} across all three distributions, consistent with prior over-squashing observations on cycles; and (iii) the (k+1)-layer GCN does not help past k = 7, ruling out under-reaching [16] as the failure mode [4].

Mean Squared Error

5.3

0.6

2.0

0.4

1.5

0.2 0.0

1.0 2

4

Layers

6

8

Figure 4: GRIP on a 22-cycle reveals an averaging bias in Equation (1). Test MSE (solid; left y-axis) and measured range Equation (1) (dashed; right y-axis) for GCNs trained on a 9-dimensional GRIP (range set {1, . . . , 9}, Gaussiansum aggregation, cubic-root read-out) as The averaging artifact of Equation (1). For GRIP, we a function of model depth (x-axis). The train a GCN [21] on a 22-cycle with 9-dimensional fea- MLE oracle from Theorem 5.7 is shown tures, each aggregated at ranges 1, . . . , 9 via the Gaussian as a dotted line; the GCN matches it for ranges ≤ 5 and saturates afterwards. 7

P9 sum and combined via h(z) = ( k=1 zk )1/3 . Figure 4 shows that (i) on ranges 1–5 the GCN attains the MLE bound from Theorem 5.7; (ii) the model cannot extract information from ranges 6–9 even though messages reach those nodes; and (iii) the post-hoc measure Equation (1) reports an effective range of ≈ 3, despite the model demonstrably using information at ranges 4 and 5. Importantly, we note that this discrepancy is not measurement error: Equation (1) is an influence-weighted average of ranges, hence, it lacks information on the distribution of the weights. For example, a MPNN that needs information from ranges 1 and 9 equally, will have measured range 5, underestimating the range.

6

Empirical Findings

We utilize the TRIP framework to address two research questions where existing benchmarks have so far given ambiguous answers: (i) does the balanced-Forman curvature in [36] predict GNN error on truly long-range tasks? (ii) is performance on the ECHO [27] benchmark solely explained by long-rangedness? Throughout, “standard TRIP” refers to TRIP with X ∼ N (0, 1) and √ f ({x1 , . . . , xn }) = (x1 + · · · + xn )/ n. 6.1

Curvature is uncorrelated with GNN error on TRIP

The balanced-Forman curvature was introduced in [36] as an efficient combinatorial measure of bottlenecks and proposed Stochastic Discrete Ricci Flow (SDRF), a rewiring technique that surgically targets negatively-curved edges. In recent works, the distinction between topological bottlenecks (low Cheeger constant, negative curvature) and computational bottlenecks (model dynamics, vanishing gradients) has been introduced [3]. Posing the conjecture that curvature-based rewiring addresses only the former. The hypothesis we test is as follows: if curvature-based rewiring resolves the long-range component of over-squashing, then on a provably k-range task, (a) the curvature of the input graph should predict GNN error, and (b) SDRF rewiring should reduce that error. We test both predictions under standard TRIP, which by Axiom 4 isolates the long-range component from confounders. Setup and Findings. For k ∈ {1, . . . , 7} we sample 100 random graphs of ≈ 1000 nodes (expecteddegree generator); whenever a node has empty Nk (u) its target is set to 0. We compare a k-layer residual GCN under (i) no rewiring (E XP _D EG) and (ii) SDRF [36], with three seeds each.4 Figure 5a shows that SDRF and the original graph perform nearly identically for k ≤ 5, with the only divergence appearing at k ∈ {6, 7} – precisely where SDRF has made struggles with long-range interaction modeling. Figure 5b reports the Spearman correlation, within each range, between minimum edge curvature and post-training MSE: |ρ| < 0.4 throughout, we see no significant trend. Therefore, we conclude that per-graph curvature is not predictive of GNN error on TRIP, shedding light on how the hypothesis above actually manifest in practice. This provides, for the first time, direct empirical evidence of the topological-vs-computational bottleneck distinction [3, 4]. 6.2

ECHO under TRIP: over-squashing beyond long-rangedness

Our analysis of ECHO in Section 4 shows that on charge and eccentricity, post-hoc measured range is uncorrelated with test error. Thus, it is unclear whether the tasks are guaranteed to require long-range interactions. We now utilize TRIP to make this a controlled test. In particular, we ask the following question: on the same topologies, under a task that is provably k-range, do the same architectures rank the same way as on the original ECHO tasks? A positive answer would imply that the bottleneck to improving performance is, indeed, the long-rangedness of the task. Setup and Findings. We instantiate standard TRIP on the two ECHO topology classes: the molecular graphs of charge and the perturbed synthetic graphs of eccentricity (line, ladder, grid-like, tree, caterpillar, lobster). Because TRIP satisfies Axiom 4, MSE values are directly comparable across these two classes. We train all message-passing baselines released with ECHO5 for ranges k ∈ {2, 4, 6, 8} with the same hyperparameter sweep protocol as [27]; details are provided in Appendix H, and results are reported in Figure 6. Two observations stand out. First, the synthetic 4 Cross-graph error comparison is not fair in this case because |N (u)| is 0 for ∼ 70% (k=6) and ∼ 90% (k=7) of the k nodes of SDRF-rewired graphs. A More detailed discussion on these cases can be found in Appendix F 5 DRew [19] and GPS [28] are excluded since its rewiring operate on topologies in which all nodes reside at distance 1.

8

1.20

Random Graph 1.00

1.00

Correlation

MSE

0.80 0.60 0.40

SDRF Graphs Base Graphs

0.20 0.00 1

2

3

k

5

6

7

Significance threshold

0.50 0.00 -0.50 -1.00

4

SDRF

1

2

3

4 k

5

6

7

(b) Spearman ρ between minimum edge curvature and post-training MSE, per range.

(a) Test MSE per range, original vs. SDRFrewired graphs.

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 ≤ 5; the divergence at k ∈ {6, 7} is an artifact of SDRF eliminating the boundary Nk (u) in most nodes (see footnote). Right: per-range Spearman correlation between minimum edge curvature and MSE stays in |ρ| < 0.4 throughout, opposing the prediction that curvature should track GNN error on a long-range task. Standard deviation is computed across 3 seeds. topologies are systematically harder than the molecular ones, validating their intended design as networks with bottlenecks. Second, PHDGN [20] outperforms all baselines on the TRIP-instantiated synthetic topologies, a gap that is absent on the original ECHO tasks. By k = 4, the classical baselines (GCN [21], GIN [38], GCNII [10], GraphCON [29], ADGN [17], GRIT [25]) saturate at MSE = 1.0 (the constant-mean baseline), and PHDGN and SWAN [18] remain meaningful learners. Implications. If long-rangedness were the dominant bottleneck on ECHO’s eccentricity, sssp, and charge, the PHDGN-vs-baseline gap we observe under TRIP should also appear there. It does not. The gap on ECHO is therefore explained, at least in part, by factors other than pure longrangedness – candidate explanations include computational bottlenecks/vanishing gradients [3, 4], mixing capacity [12], or task-specific inductive biases. Our framework does not adjudicate between these, but it does isolate the long-range component cleanly enough to rule out long-rangedness alone as the driver 6 . More broadly, this experiment illustrates a workflow the framework enables: instantiate TRIP on a benchmark’s topologies; compare relative model rankings under TRIP against the original task; the discrepancy quantifies how much of the original task gap is not long-rangedriven.

7

Conclusion

We demonstrated that the absence of a precise specification of what makes a long-range benchmark long-range has stalled progress on over-squashing. To address this gap, we introduce a certifiable framework: four verifiable axioms (Section 3.1), a constructive procedure – TRIP and GRIP – that satisfies them on any graph topology (Section 5), and a closed-form per-range MLE oracle. To the best of our knowledge, this is the first a priori lower bound on test error available for any long-range graph benchmark (Theorem 5.7). Materializing our framework into real-world benchmarks has produced two non-trivial findings: (i) balanced-Forman curvature is uncorrelated with GNN error on truly long-range tasks (Section 6.1); and (ii) the model-ranking gap on ECHO is not explained by long-rangedness alone (Section 6.2). We also explicitly surfaced how averaging artifact of the post-hoc range measure of [6, 22] can be misleading (Section 5). As future work, kernel-based extensions of f -stability for correlated features and relaxations of Axiom 1 to probabilistic g to model noise could close the gap to real-world data. We envision our framework propelling the community toward long-range comparisons with precisely understood scope.

Acknowledgments and Disclosure of Funding Ferran Hernandez Caralt acknowledges that the project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code 6 One could argue that assuming i.i.d features also enforces low feature homophily, for a more detailed discussion on this

idea see Appendix D

9

Charge

1.2

Synthetic

1.0

Model ADGN

MSE

0.8

GCN2Conv

0.6

GCNConv

0.4

GraphCON

0.2

SWAN

GINConv PHDGN GRIT

0.0 2

4

k

6

8

2

4

k

6

8

Figure 6: Test MSE on TRIP-instantiated ECHO topologies (charge, synth) for k ∈ {2, 4, 6, 8}. PHDGN [20] dominates all baselines, with a gap that is absent on the original ECHO tasks of [27]. By k = 4 the classical baselines (GCN [21], GIN [38], GCNII [10], GraphCON [29], ADGN [17], GRIT [25]) saturate at MSE = 1.0 (constant-mean baseline); only PHDGN and SWAN [18] remain meaningful learners. Standard deviation is computed over 4 seeds [27]. is LCF/BQ/PFA25/11000012. Simon Heilig, Asja Fischer acknowledge funding by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) via the TRR 391 Spatio-temporal Statistics for the Transition of Energy and Transport (project 520388526)

References [1]

[2] [3]

[4]

[5]

[6]

[7]

[8]

[9] [10] [11] [12]

Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. “The Surprising Power of Graph Neural Networks with Random Node Initialization”. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. International Joint Conferences on Artificial Intelligence, 2021. Uri Alon and Eran Yahav. “On the Bottleneck of Graph Neural Networks and its Practical Implications”. In: The Eighth International Conference on Learning Representations. 2020. Adrian Arnaiz-Rodriguez and Federico Errica. “Oversmoothing, oversquashing, heterophily, long-range, and more: Demystifying common beliefs in graph machine learning”. In: The Fourteenth International Conference on Learning Representations. 2026. Alvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong, Michael M Bronstein, and Pierre Vandergheynst. “On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. Jacob Bamberger, Federico Barbero, Xiaowen Dong, and Michael M Bronstein. “Bundle Neural Network for message diffusion on graphs”. In: The Thirteenth International Conference on Learning Representations. 2025. Jacob Bamberger, Benjamin Gutteridge, Scott le Roux, Michael M Bronstein, and Xiaowen Dong. “On Measuring Long-Range Interactions in Graph Neural Networks”. In: Forty-second International Conference on Machine Learning. 2025. Maya Bechler-Speicher, Ido Amos, Ran Gilad-Bachrach, and Amir Globerson. “Graph neural networks use graphs when they shouldn’t”. In: Forty-first International Conference on Machine Learning. 2024. Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. “Understanding oversquashing in gnns through the lens of effective resistance”. In: International Conference on Machine Learning. PMLR. 2023, pp. 2528–2547. George Casella and Roger Berger. Statistical inference. Chapman and Hall/CRC, 2024. Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. In: International Conference on Machine Learning. PMLR. 2020, pp. 1725–1735. Gabriele Corso, Hannes Stark, Stefanie Jegelka, Tommi Jaakkola, and Regina Barzilay. “Graph neural networks”. In: Nature Reviews Methods Primers 4.1 (2024), p. 17. Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. “On over-squashing in message passing neural networks: The impact of width, depth, and topology”. In: International Conference on Machine Learning. PMLR. 2023, pp. 7865–7885.

10

[13] Hongwei Du, Jiamin Wang, Jian Hui, Lanting Zhang, and Hong Wang. “DenseGNN: universal and scalable deeper graph neural networks for high-performance property prediction in crystals and molecules”. In: npj Computational Materials 10.1 (2024), p. 292. [14] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. “Long range graph benchmark”. In: Advances in Neural Information Processing Systems 35 (2022), pp. 22326–22340. [15] Moshe Eliasof, Eldad Haber, and Carola-Bibiane Schönlieb. “TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows”. In: The Fourth Learning on Graphs Conference. 2025. [16] Rickard Brüel Gabrielsson, Mikhail Yurochkin, and Justin Solomon. “Rewiring with positional encodings for graph neural networks”. In: Transactions on Machine Learning Research (2023). [17] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. “Anti-Symmetric DGN: a stable architecture for Deep Graph Networks”. In: The Eleventh International Conference on Learning Representations. 2023. [18] Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, and Carola-Bibiane Schönlieb. “On oversquashing in graph neural networks through the lens of dynamical systems”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. 16. 2025, pp. 16906– 16914. [19] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. “Drew: Dynamically rewired message passing with delay”. In: International Conference on Machine Learning. PMLR. 2023, pp. 12252–12267. [20] Simon Heilig, Alessio Gravina, Alessandro Trenta, Claudio Gallicchio, and Davide Bacciu. “Port-Hamiltonian Architectural Bias for Long-Range Propagation in Deep Graph Networks”. In: The Thirteenth International Conference on Learning Representations. 2025. [21] Thomas N Kipf and Max Welling. “Semi-Supervised Classification with Graph Convolutional Networks”. In: The Fifth International Conference on Learning Representations. 2017. [22] Huidong Liang, Haitz Sáez de Ocáriz Borde, Baskaran Sripathmanathan, Michael Bronstein, and Xiaowen Dong. “Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement”. In: The Fourteenth International Conference on Learning Representations. 2026. [23] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. “Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence”. In: International Conference on Machine Learning. PMLR. 2025, pp. 41290–41310. [24] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. “Classic gnns are strong baselines: Reassessing gnns for node classification”. In: Advances in Neural Information Processing Systems 37 (2024), pp. 97650–97669. [25] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip H.S. Torr, and Ser-Nam Lim. “Graph inductive biases in transformers without message passing”. In: International Conference on Machine Learning. PMLR. 2023, pp. 23321–23337. [26] Joël Mathys, Henrik Christiansen, Federico Errica, Takashi Maruyama, and Francesco Alesiani. “LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning”. In: The Fourteenth International Conference on Learning Representations. 2026. [27] Luca Miglior, Matteo Tolloso, Alessio Gravina, and Davide Bacciu. “Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation”. In: The Fourteenth International Conference on Learning Representations. 2026. [28] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. “Recipe for a general, powerful, scalable graph transformer”. In: Advances in Neural Information Processing Systems 35 (2022), pp. 14501–14515. [29] T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. “Graph-coupled oscillator networks”. In: International Conference on Machine Learning. PMLR. 2022, pp. 18888–18909. [30] Ken-iti Sato. Lévy Processes and Infinitely Divisible Distributions. Vol. 68. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1999. [31] Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael T Schaub. “Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs”. In: The Thirteenth International Conference on Learning Representations. 2024. 11

[32] Yifei Shen, Jun Zhang, SH Song, and Khaled B Letaief. “Graph neural networks for wireless communications: From theory to practice”. In: IEEE Transactions on Wireless Communications 22.5 (2022), pp. 3554–3569. [33] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. “Exphormer: Sparse transformers for graphs”. In: International Conference on Machine Learning. PMLR. 2023, pp. 31613–31632. [34] Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. “Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark”. In: The Second Learning on Graphs Conference (2023). [35] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. “Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing”. In: Transactions on Machine Learning Research (2021). [36] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. “Understanding Over-squashing and Bottlenecks on Graphs via Curvature”. In: International Conference on Learning Representations (ICLR). 2022. [37] Sajith Wettewa, Lei Hou, and Guomin Zhang. “Graph Neural Networks for building and civil infrastructure operation and maintenance enhancement”. In: Advanced Engineering Informatics 62 (2024), p. 102868. [38] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. “How Powerful are Graph Neural Networks?” In: The Seventh International Conference on Learning Representations. 2019. [39] Dongzhuoran Zhou, Evgeny Kharlamov, and Egor V Kostylev. “GLoRa: A Benchmark to Evaluate the Ability to Learn Long-Range Dependencies in Graphs”. In: The Thirteenth International Conference on Learning Representations. 2025.

12

A

Deep Dive into Theoretical Results

A.1

Intuition behind the axioms

The core idea is to change the notion of "a k-range task needs k-ranged information to be solved" to "a k-range task needs k-ranged information to be approximated". This is fundamental for designing long-range benchmarks as GNNs are NOT solvers in the algorithmic sense, they are approximators in the statistical learning sense. For this reason we have chosen joint distributions to formalize the notion of long-range for GNNs, as it enables us to rule out the existence of unknown shorter-ranged correlations that may aid in approximating the task. This phenomenon enabled shorter-ranged models to be presented as long-ranged, as we show in Section 4. One example of this phenomenon is eccentricity, which has been used in ECHO to present a longranged task. Even though to solve the task you need to find the furthest node for each node, when restricting the problem to certain dataset, there likely exist shorter-ranged correlations GNNs can exploit. For example: it is intuitive to think that nodes with higher degrees will tend to have lower eccentricities. Consequently, it is unclear what performance can be achieved with shorter-ranged models. The clearest specific example we show of this is in Figure 2, where models have ranges around 3 but eccentricity is on average between 20 and 25 [27].

A.2

On the theoretical results of the Axioms

These results provide a solid theoretical link between the absence of each axiom with undesirable behaviour that may undermine past and future research. These are essential to provide solid grounds for preventing future research from falling into the same pitfalls that have been repeated in the past. These results are to be seen as cautionary tales that prevent future research from unknowingly designing biased test cases to validate their long-ranged GNN developments. Proposition 3.1 shows that removing axiom 2 opens the door to tasks that will have arbitrarily large targets to be predicted depending on the graph size. So, “long-range” tasks designed on larger graphs without verifying Axiom 2 might be benchmarking the capabilities of GNNs of adapting to larger normed predictions instead of their long-range capabilities. Proposition 3.2 proposition is a formalization using our framework of a documented occurrence, since [6, 23] show range-≈ 2 models matching long-range architectures on LRGB. To highlight the importance of Proposition 3.3 we must point out previous work contextualize it. In [6], to claim that a GNN learned the true range of a task, they used the k-power task, which is analogous to the one described in Proposition 3.3. Our proposition highlights that, had that validation in [6] been done on large enough graphs, the opposite conclusion could’ve been reached. As one could unknowingly generate a problem that is essentially trivial, solve it with a GNN that predicts a constant, thus concluding that the range proposed is meaningless. In current benchmarks [14, 39, 27] there is no objective notion of what is “good” performance. You can only conclude that model A beats model B, but never how far either one is from optimal, or how much of the remaining error is simply irreducible at a given range. Theorem 5.7 fixes this by giving, for each observation range k, a closed-form error εMLE (k) that no model with effective range ≤ k can beat — computable before training, and independent of the graph itself. This enables absolute calibration. Instead of Figure 4 saying "the GCN reached MSE 0.42," we can say it achieves the information-theoretic optimum for ranges up to 5 and extracts essentially nothing from ranges 6–9, even though messages do reach those nodes. This calibration directly enables researchers to attribute a stronger performance to better long-range modelling. If a model’s error drops below εMLE (k ⋆ − 1), that’s provable evidence it used range-k information. "Is this improvement actually long-range?" stops being a rhetorical question and becomes a decidable one. This is precisely the kind of certificate that was missing in LRGB , and its absence is what made the reassessments [34, 23, 6] necessary in the first place. 13

B

f -stability’s Motivation

In the main paper we propose f -stability as a concept which can be used to construct provably long-range benchmarks that satisfy axioms 1 through 4. Theorem 5.5 gives sufficiency, f -stability is enough to satisfy the axioms. Here we add the near-converse Proposition B.1. Fix the design template where features are i.i.d. and yu = f ({xv : v ∈ Nk (u)}). ′ Then H(Yu | Gku ) =
H(Yu ) for k ′ < k, and Axiom 4 holds across all graph families if and only if H f ({X1 , . . . , Xn }) is constant in n. If this entropy depends on n, Axiom 4 fails on any family with non-constant boundary sizes. Proof. Let n = |Nk (u)|. Nodes within distance k ′ < k of u are disjoint from Nk (u), so by the ′ ′ i.i.d. assumption Yu is independent of Gku , and hence H(Yu | Gku ) = H(Yu
). Since the features in Nk (u) are n i.i.d. samples of X, we have H(Yu ) = H f ({X1 , . . . , Xn }) . Axiom 4 therefore requires this quantity to be the same for all boundary sizes n occurring across graphs. If it is constant in n, Axiom 4 holds. If it depends on n, then any family containing two boundary sizes with different entropy violates Axiom 4. So within this template, constancy of the aggregate’s law in n is forced by Axiom 4, and f -stability is the natural (and, up to entropy-equality, necessary) way to obtain it.

C

Proofs and Lemmas

This appendix contains all the proofs of the theoretical results. To do so, we first prove a series of properties that will be used throughout the proofs. C.1

Auxiliary results

Proposition C.1. Given two independent Normal random variables X1 ∼ N (µ1 , σ12 ) and X2 ∼ N (µ2 , σ22 ). Then αX1 + βX2 ∼ N (αµ1 + βµ2 , α2 σ12 + β 2 σ22 ) Proof. Recall that the MGF of a normally distributed random variable X ∼ N (µ, σ 2 ) is:   1 2 2 MX (t) = exp µt + σ t 2 Let Y = αX1 + βX2 . We want to find the MGF of Y , which is MY (t) = E[etY ]. Substituting our expression for Y : h i h i MY (t) = E et(αX1 +βX2 ) = E e(αt)X1 e(βt)X2 Because X1 and X2 are independent, the expectation of their product separates into the product of their expectations: h i h i MY (t) = E e(αt)X1 E e(βt)X2 = MX1 (αt)MX2 (βt) Now, substitute the specific normal MGF formulas for X1 and X2 :     1 1 MY (t) = exp µ1 (αt) + σ12 (αt)2 exp µ2 (βt) + σ22 (βt)2 2 2   1 2 2 2 1 2 2 2 = exp (αµ1 )t + (α σ1 )t + (βµ2 )t + (β σ2 )t 2 2   1 2 2 = exp (αµ1 + βµ2 )t + (α σ1 + β 2 σ22 )t2 2 We recognize this final expression as the exact MGF of a normal distribution with mean µ∗ = αµ1 + βµ2 and variance (σ ∗ )2 = α2 σ12 + β 2 σ22 . Since MGFs are unique, it follows exactly that: αX1 + βX2 ∼ N (αµ1 + βµ2 , α2 σ12 + β 2 σ22 ) 14

Proposition C.2. Given n i.i.d Gumbel random variables Xi maxi=1,...,n {Xi } ∼ Gumbel(µ + β ln(n), β).

∼

Gumbel(µ, β) then

Proof. Let X1 , X2 , . . . , Xn be i.i.d. Gumbel random variables with the cumulative distribution function (CDF):   F (x; µ, β) = exp −e−(x−µ)/β Let Y = max{X1 , . . . , Xn }. Since the variables are independent and identically distributed, the CDF of the maximum is: FY (y) = P (max{X1 , . . . , Xn } ≤ y) =

n Y

P (Xi ≤ y) = [F (y; µ, β)]n

i=1

Substituting the Gumbel CDF: h  in FY (y) = exp −e−(y−µ)/β   FY (y) = exp −n · e−(y−µ)/β We can rewrite n as eln(n) :   FY (y) = exp −eln(n) · e−(y−µ)/β   FY (y) = exp −e−(y−µ−β ln(n))/β Comparing this to the standard form F (y; µ′ , β), we identify the new location parameter: µ′ = µ + β ln(n) Thus, Y ∼ Gumbel(µ + β ln(n), β). n ∼ Proposition C.3. Given n i.i.d Cauchy random variables X ∼ Cauchy(x0 , γ), then X1 +···X n Cauchy(x0 , γ).

Proof. Let X1 , X2 , . . . , Xn be i.i.d. random variables with Xi ∼ Cauchy(x0 , γ). The characteristic function of a Cauchy distribution is given by: φX (t) = E[eitX ] = eitx0 −γ|t| Let X̄ = n1

Pn

j=1 Xj . We find the characteristic function of X̄:

h i P 1 φX̄ (t) = E eit( n Xj )   n Y =E ei(t/n)Xj  j=1

Since the Xj are independent, the expectation of the product is the product of the expectations: φX̄ (t) =

n Y

h i E ei(t/n)Xj

j=1 n Y

  t = φXj n j=1 15

Figure 7: Example of the graph used in the Proposition C.4 for n = 3, k = 4 Substituting the Cauchy characteristic function for each Xj : φX̄ (t) =

n Y

ei(t/n)x0 −γ|t/n|

j=1

 n = ei(t/n)x0 −γ|t/n| |t|

= en(i n x0 −γ n ) t

= eitx0 −γ|t| The resulting characteristic function φX̄ (t) = eitx0 −γ|t| is exactly the characteristic function of a Cauchy(x0 , γ) distribution. By the uniqueness of characteristic functions, we conclude: X1 + · · · + Xn ∼ Cauchy(x0 , γ) n Another resource that will be used throughout is the following: Proposition C.4. Given an n, k ∈ N, there exists Gn,k where ∀u ∈ Gn,k , |{v ∈ Gn,k |dGn,k (u, v) = k}| = n. Proof. Given n, k ∈ N, we set V = {1, ..., 2n(k + 1)}, and E = {(u, v)|u − v ≡ 1 mod 2(k + 1)}, in Figure 7, we can observe how such a graph may look like. By definition, it is immediate that |{v ∈ Gn,k |dGn,k (u, v) = k}| = n. C.2

Necessity of the axioms

Proposition 3.2 (Tightness is necessary). Fix k > 1 and let X ∼ N (0, 1). Let {Gn } be a sequence of graphs in which every node u satisfies |Nk (u)| ≥ n, and define Yu = maxv∈Nk (u) Xv . The construction satisfies Axioms 1, 3, and 4, but the family {Yu } is not tight: for every M ∈ R, P(Yu > M ) → 1 as n → ∞. Proof. Axiom 1 is satisfied by definition. Axiom 3 is also satisfied as the predictions only rely on the samples at distance exactly k and are independent from the rest. By Proposition C.2 (applied to the Gumbel limit of the standard normal maximum), Yu is stochastically dominated below by a variable whose location parameter grows without bound as n → ∞. This verifies Axiom 4 as all entropies will be equal since the only change in distribution is a shift in the expected value. But limn→∞ P (Yu > M ) = 1 because X being unbounded above implies P (X > M ) > 0 for all M , so the maximum of n i.i.d. copies exceeds M with probability 1 − (1 − P (X > M ))n → 1. In the case that a bounded distribution had been chosen, Axiom 4 cannot be satisfied due to the following proposition. 16

Proposition C.3. Given X a random variable with CDF F such that its support is contained in [a, b] for some a, b ∈ R, its second order moment exists. Let’s consider the random variable Yn = max{X1 , ..., Xn } where Xi are i.i.d copies of X. Then for all n1 there exists n2 such that H(Yn1 ) ̸= H(Yn2 ) Proof. To prove this we will use the following known bound for entropy: given any continuous random variable Y with fixed variance var(Y ) = σ 2 , then H(Y ) ≤ 21 log(2πeσ 2 ). With this in mind, if we now prove that limn→∞ var(Mn ) = 0 we will get our desired result, because given any Yn1 we can find n2 such that H(Yn2 ) < log(2πeσn2 2 ) < H(Yn1 ). So let’s prove that Yn converges in probability to the constant b, as convergence in probability implies convergence of all moments, so if Yn converges to a constant, its variance will converge to zero. Indeed, lim P (|Yn − b| > ε) = lim P (b − Yn > ε) = lim P (Yn < b − ε)

n→∞

n→∞

n→∞

(2)

= lim F (b − ε)n = 0 n→∞

Where F is the cumulative density function that satisfies F (x) < 1 for all x < b, otherwise the upper bound would be lesser. This concludes our proof as Mn converges in probability to a constant, which implies that the variance converges to 0, which allows us to always obtain a variable with less entropy. Essentially, using the example introduced in Proposition C.4, given an arbitrary graph G and node u ∈ G we can find another graph with nodes where the entropy of the predictions will be radically different. Thus arbitrarily biasing the benchmark. Proposition 3.3 (Strict k-Range is necessary). Suppose a task satisfies Axioms 1, 2, 4 with target ⋆ range k, but there exists i < k with H(Yu | Giu ) < H(Yu | Gi−1 u ). Let fi be the optimal rangei predictor under any continuous error measure err. Considering a finite set of known range-k functions, and f the one where the error measure is minimum, whenever err(f ) > err(fi⋆ ), an ⋆ improvement attained at range i from fi−1 to fi⋆ is reportable as an improvement at range k. Proof. The proof is immediate, as H(Yu | Giu ) < H(Yu | Gi−1 u ) implies that a model with range i − 1 cannot achieve 0 error as there is information beyond that range. Let’s denote εi−1 the infimum of the error achievable by a model that only accounts for information on i − 1 hops, and εi the infimum of a model accounting for information on i hops. Then εi < εi−1 . Consequently, if the task is claimed to be of range k, then a model of range i can improve on a model of range i − 1 while still getting reported as an improvement on a range-k task. Proposition 3.4 (Topology-Invariance is necessary). Fix k > 1. Sample xu ∼ X i.i.d. from any distribution with finite variance, and let yu be the average of features at distance exactly k from u. The construction satisfies Axioms 1, 2, 3, but for every ε there exist graphs G on which H(Yu ) < ε. Proof. So yu is defined as an average of i.i.d random variables with finite mean and finite variance. As a direct consequence of the Central Limit Theorem, yu will converge to the constant random variable with value µ as the size of the average grows, so its variance converges to 0. Using again the upper bound of the entropy used in the proof of C.3, we can deduce the entropy will tend to −∞. As such, for any ε we can find a graph with sufficiently large sets of nodes at distance exactly k such that H(Yu ) < ε. C.3

TRIP and GRIP

Proposition 5.2 (Closure properties). Let X be f -stable and X̃ be f˜-stable. 1. For any measurable g : R → R, X is (g ◦ f )-stable. 2. The pair (X, X̃) is F -stable with F ({Xi }, {X̃j }) = (f ({Xi }), f˜({X̃j })). d

Proof. For X to be g ◦ f -stable, we need to verify that (g ◦ f )({X1 , ..., Xn }) = Z for some fixed random variable Z. Indeed, (g ◦ f )({X1 , ..., Xn }) = g(Y ) for some Y because X is f -stable. Then, as g is measurable, g(Y ) is a random variable Z. The second point is immediate by definition. Theorem 5.4 (TRIP satisfies all four axioms). For any graph G and any f -stable pair (X, f ), the TRIP task at range k satisfies Axioms 1–4. In particular, the marginal Yu and the entropy H(Yu ) are graph-independent constants determined only by (X, f ). 17

d

Proof. Axiom 1 is immediate from the definition of TRIP. By f -stability, Yu = Y for all G and u, where Y = f ({Xi }ni=1 ) is the same random variable for every n ≥ 1; this yields Axiom 2 (the singleton family {L(Y )} is automatically tight) and Axiom 4 (the conditional entropy below the target range only sees i.i.d. features whose distribution does not depend on (G, u)). For Axiom 3: Nk (u) is disjoint from Gk−1 and the Xv are i.i.d. across nodes, so Yu is independent of every u ′ ′ Gku with k ′ < k, giving I(Yu ; Gku ) = 0. Conversely, Yu is a measurable function of features in Nk (u) ⊆ Gku , so I(Yu ; Gku ) > 0 whenever f is non-constant. The marginal-constant claim follows from L(Yu ) = L(Y ). Theorem 5.6 (Per-range MLE oracle). Fix a GRIP task with parameters {(Xi , fi , Ki )}i and readout h, and let k ⋆ ≥ 0 be a target observation range. Let X̂i be the MLE realisation of Xi . The ⋆ Maximum-Likelihood predictor of Yu given Gku is h(ỹu ), where for each (i, k),
 fi {(xv )i : v ∈ Nk (u)} if k ≤ k ⋆ ,
ỹu(i,k) = fi {X̂i } if k > k ⋆ . The expected error of this predictor is a graph-independent function of ({(Xi , fi , Ki )}i , h, k ⋆ ) alone, and provides a lower bound for any model with effective range ≤ k ⋆ . ⋆

Proof. Since for the ranges conditioned on Gku the Maximum Likelihood estimator is the actual known values. The values at ranges greater than k ⋆ are independent of the rest of the values; as such we obtain their MLE estimator through a direct application of the invariance principle for maximum likelihood estimators described in Pages 319–323 of [9], as we are just composing a function. The same invariance principle is applied to go from ỹu to h(ỹu ). Graph-independence of the expected error follows from Axioms 2 and 4, which guarantee that Yu and all conditional distributions below the target range are graph-independent.

D

Long-rangedness and homophily

Throughout this work we assume i.i.d sampled features. Thus enforcing low feature homophily. In this section we look into the interplay between feature homophily and our notion of long-rangedness through a simple example. Let’s consider the following graph: node1 − − − (node1 , node4 , node5 , ..., noden ) − − − noden+1 Where node1 and noden+1 are connected to the nodes 2, ..., n. Let’s consider a generic range-2 interaction, that is, each node is a function of nodes at distance 2. And we name Xi the features attached to node i. Also, let’s assume that for each node the correlation, i.e covariance between the two variables divided by product of variances, with another node is greater the closer it is in the graph. That is, nodes at distance 1 have greater correlation than those at distance 2 and so on. Since non-zero correlation implies non-zero mutual information, we will now work in terms of mutual information. Now we split this into two cases according to whether the following chain-rule inequality is strict or not, I(X1 ; X2 , ..., Xn ) ≥ I(X1 ; X2 , ..., Xn−1 ). If I(X1 ; X2 , ..., Xn ) > I(X1 ; X2 , ..., Xn − 1), then the more nodes we add, the n-1 nodes in the middle would contain more and more information on nodes 1 and n+1. This implies that how well node1 could infer noden + 1’s features with range-1 information would depend on graph size, thus introducing structural bias. If I(X1 ; X2 , ..., Xn ) = I(X1 ; X2 , ..., Xn−1 ), it implies that all X2 , ..., Xn−1 contain the same information on X1 . This would introduce a structural bias, as node’s 1 and n + 1 would only need to extract information from exactly ONE node, thus ignoring the actual structure of the graph. This very simple example showcases how adding correlations to the setting can cause: structural biases and the range of the interactions to decrease. This example suggests that homophily may be intrinsically related to short-range structure, as correlation (homophily) in the data may collapse long-ranged information on smaller effective ranges. Nevertheless, the example is illustrative rather than a general proof, and we believe there remains a not-yet-fully-understood interplay between homophily and range that merits further investigation. 18

E

Data Generation

Generation is deterministic given (topology collection, k, (X, f ), seed). https://www.kaggle.com/datasets/ferranh/trip-grip-sampled-data contains all the data used for sections 6.1 and 6.2 and a README.md with instructions on where each file should be placed in order to run the experiments.

F

Inter-graph comparisons ablations

To compare the results across graphs there is one thing that must be taken into account. In the (X, f ) pairs such that X is f -stable, f contains terms which are just the features of the other nodes, and also the size n of the set of nodes at distance exactly k. In graphs where n is constant, such as regular graphs, the TRIP problem is easier to fit by a GNN, as the n term does not change across different nodes. To make the comparison between two graphs fair it is necessary to compute the distribution of these values and compute its entropy. To ensure that the amount of bits necessary to capture them is the same between the graphs that we want to compare. In the following tables we report the entropies of all the n values of the graphs we have compared in the paper. That is: the graphs generated using the expected degree algorithm with their SDRF processed version, as well as the charge and synthetic topologies of ECHO [27]. We observe that in the ECHO datasets the entropy difference is, at most 0.7 bits. In the SDRF case there are some larger differences in the cases of 6 and 7, which were appropriately discussed in the main manuscript. k 1 2 3 4 5 6 7 8 synth 2.04 3.02 3.44 3.68 3.84 3.95 4.02 4.06 charge 1.54 2.52 2.87 3.17 3.3 3.33 3.33 3.27 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 k.

k 1 2 3 4 5 6 7 base 3.83 6.68 8.46 7.56 8.29 5.46 1.78 SDRF 4.39 7.43 8.29 8.24 7.27 2.09 0.04 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 k.

G

Limitations and Future Work

To provide the theoretical guarantees described in this work it is necessary to use synthetic data. For this reason, future work directions mostly involve closing the gap between this synthetic framework and real-world settings. For example, further work on the f -stable notion of distributions may reveal ways to build kernels to simulate real-world data. Another potential line of future research is to relax Axiom 1 to make g a non-deterministic function to study the effect of noise in long-range interactions modeling. As mentioned in Appendix F, it is necessary to measure the entropy of certain distributions per graph in order to compare how hard it is to model long-range interactions under those settings. We believe that the mentioned entropy is a good proxy for the complexity of real-world graphs, as the regular topologies will be easier to model than those with varied connectivity patterns. This is in line with the work presented in [7]. 19

H

Hyperparameter configurations

H.1

Synthetic configurations

For the TRIP experiments on cycles we used hidden dimension of 16, a learning rate of 0.001 and 2000 epochs. For the GRIP experiments on cycles we used the same learning rate and number of epochs but increased the hidden dimension to 64. Running all the TRIP and GRIP experiments shown in Section 5 had a runtime of roughly 10 hours on an Apple M5 chip with 16GB of RAM. H.2

Curvature analysis

To generate the graphs an expected degree algorithm was used. In the following manner: Algorithm 1: Graph Generation via Expected Degree Model Input: Graph size n, degree support S = {dmin , . . . , dmax }, target mean µ, std dev σ Output: Connected graph G // Step 1:

Fit Boltzmann distribution over degree support 
2  Solve for center c such that Epc [d] = µ, where pc (d) ∝ exp − 21 d−c ; σ

// Step 2:

Sample a degree sequence i.i.d.

Draw d1 , d2 , . . . , dm ∼ pc over S, where m ≥ n accounts for nodes that will be lost when extracting the largest connected component; // Step 3: Sample a graph from the degree sequence Construct graph G′ using the expected degree model: connect each pair of nodes (i, j) d d independently with probability pij = Pi djk ; k

// Step 4: Extract the largest connected component Identify all connected components C1 , C2 , . . . of G′ ; Set G ← G′ [ arg maxl |Cl | ] ; // subgraph induced by largest component return G; For the curvature experiments we have used a learning rate of 0.001, hidden dimension of 32 and 2000 epochs to train a standard GCN. The SDRF algorithm was run with 1000 loops, 0.5 removal bound and 1.0 as tau. All of these experiments were run on an Apple M5 chip. The runtimes of the various parts were the following: applying SDRF had a runtime of approximately 2 hours and training the models had a runtime of roughly 8 hours. H.3

ECHO

To make the comparison with the real ECHO benchmark fair, we have performed analogous hyperparameter sweeps at each range for each model. All the search intervals and settings are the same as those of [27] except for the number of layers, hidden dimension, learning rate and weight decay. Runtimes per epoch reported were on a single NVIDIA A100-SXM-80GB GPU. In the tables below we report the sweeps as well as the final configurations. To be mindful of computing resources we stopped running sweeps on a model once its performance was equal to that of the model predicting always 0. Because the analysis done in F allows us to ascertain that the problems on the longer ranges will be as, if not more, difficult. Consequently, if a model fails to learn any significant signal at range k, it will also fail at ranges higher than k. The run times per epoch are reported through

20

Table 4: Hyperparameters and their best values across tasks PH-DGN. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−8 − 10−13 ]

4 123 0.0019829 0.00017623

5 65 0.0036591 0.000649

8 90 0.0035931 0.00043574

10 108 0.0032598 0.00017166

2 37 0.0025752 0.000012821

6 128 0.00046393 0.00002681

7 109 0.001766 0.000032552

10 101 0.0016224 0.000010521

ϵ α β p conv mode q conv mode Doubled dimension Final state

0.6 0.62968 0.62319 NaiveAggr NaiveAggr True q

0.62677 0.79134 0.89197 GCN NaiveAggr False p

0.63991 0.96059 0.012745 GCN NaiveAggr False pq

0.50392 0.20735 0.16402 GCN NaiveAggr False pq

0.96703 0.7506 0.85072 NaiveAggr GCN True pq

0.18725 0.019947 0.59061 NaiveAggr NaiveAggr True pq

0.48771 0.24087 0.79638 NaiveAggr NaiveAggr True p

0.62536 0.34108 0.72338 NaiveAggr NaiveAggr False q

param

param

param

MLP4ReLU

param

param

DGNReLU

MLP4ReLU

External mode

[0.001 − 1.0] [0.01 − 1.0] [0.01 − 1.0] [NaiveAggr, GCN] [NaiveAggr, GCN] [True, False] [p, q, pq] [param, param+, MLP4ReLU, DGNReLU,] [MLP4Sin, DGNtanh]

MLP4Sin

MLP4Sin

MLP4Sin

MLP4Sin

MLP4Sin

MLP4Sin

MLP4Sin

MLP4Sin

Runtime/Epoch (s)

-

1.97

1.88

1.99

2.20

6.73

11.42

7.30

10.03

Dampening mode

Table 5: Hyperparameters and their best values across tasks for SWAN. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

4 57 0.0050446 0.00013226

4 45 0.0058967 0.00034166

8 88 0.0028226 0.00099821

-

2 26 0.0023166 0.0000019995

6 91 0.0011137 0.00048812

8 124 0.0061644 0.00079115

-

ϵ γ β

[0.001 − 1.0] [0.001 − 0.5] [−1.0 − 1.0]

0.95111 0.27672 -0.64706

0.94049 0.085026 0.81494

0.64641 0.1858 -0.35339

-

0.75604 0.39086 -0.018684

0.82622 0.38164 -0.98335

0.60167 0.029949 0.87145

-

BNA

BGC

ASNA

-

ASNA

BGC

BNA

-

True

True

True

-

True

True

True

-

1.95

1.86

0.89

-

6.74

3.78

1.64

-

Attention

[AntiSymNaiveAggr (ASNA), BoundedGCNConv (BGC), BoundedNaiveAggr (BNA)] [True, False]

Runtime/Epoch (s)

-

Graph convolution

Table 6: Hyperparameters and their best values across tasks for A-DGN. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

4 111 0.007139 0.000010932

4 96 0.0052292 0.00063737

-

-

3 103 0.0041737 6.3409e-7

6 32 0.0098753 0.00082609

-

-

ϵ γ Graph convolution

[0.001 − 0.5] [0.001 − 0.5] [NaiveAggr, GCN]

0.47645 0.31699 GCN

0.088879 0.27401 GCN

-

-

0.49636 0.1865 GCN

0.35951 0.29602 GCN

-

-

Runtime/Epoch (s)

-

1.68

0.26

-

-

6.29

2.13

-

-

Table 7: Hyperparameters and their best values across tasks for GraphCON. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

4 108 0.0056647 0.00047368

5 80 0.0071248 0.00018787

-

-

4 85 0.0068252 0.00058396

5 99 0.0086757 0.000039939

-

-

ϵ

[0.001 − 1.0]

0.84399

0.24835

-

-

0.86125

0.12498

-

-

Runtime/Epoch (s)

-

1.80

0.10

-

-

6.25

2.98

-

-

Table 8: Hyperparameters and their best values across tasks for GCNII. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

4 32 0.0049859 0.00033804

6 63 0.0021435 0.00056113

7 43 0.0082665 0.00056882

-

4 168 0.0018015 0.00006297

5 149 0.0012101 0.000708

8 16 0.004821 0.00082622

-

α

[0.0 − 0.9]

0.3413

0.1743

0.098132

-

0.56735

0.1486

0.8484

-

Runtime/Epoch (s)

-

1.71

1.81

1.17

-

6.76

5.50

1.46

-

21

Table 9: Hyperparameters and their best values across tasks for GIN. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

3 54 0.0051168 0.00056302

6 22 0.0015522 0.00042337

8 29 0.0057223 0.00068561

-

3 80 0.0072599 0.00020653

6 17 0.0025787 0.00037468

8 26 0.0033032 0.0000010491

-

Runtime/Epoch (s)

-

1.69

1.63

0.56

0.78

6.52

6.74

2.05

-

Table 10: Hyperparameters and their best values across tasks for GCN. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16 − 128] [10−3 − 10−2 ] [10−13 − 10−3 ]

4 20 0.0092326 0.000018562

6 24 0.0013939 0.000089966

-

-

4 114 0.0027285 0.000025323

6 19 0.0011325 0.00038465

-

-

Runtime/Epoch (s)

-

1.58

1.67

-

-

6.53

6.40

-

-

Table 11: Hyperparameters and their best values across tasks for GRIT. Hyperparameter

Search interval

synth-2

synth-4

synth-6

synth-8

charge-2

charge-4

charge-6

charge-8

Number of layers Hidden dimension Learning rate Weight decay

[k − k + 2] [16, 32, 64, 96, 128] [10−4 − 10−2 ] [10−13 − 10−3 ]

4 128 0.0009 0.000062203

5 64 0.0004285 0.00066628

-

-

3 128 0.00097063 0.00099632

5 96 0.00017332 0.00097794

-

-

Attention dropout Number of attention heads

[0 − 0.5] [2]

0.22791 2

0.12143 2

-

-

0.0022844 2

0.16741 2

-

-

Runtime/Epoch (s)

-

1.2

212.0

-

-

10.33

871.00

-

-

22

I

Code

The code that contains the core functionalities involving TRIP and GRIP generation can be found in https://github.com/ferranhernandezc/graph-grip. Using this code the experiments on Sections 5 and 6.1 can be reproduced. To reproduce the other experimental results it is necessary to install the mentioned code, and then use https://github.com/ferranhernandezc/ECHO-grip. The repositories contain further instructions.

J

Disclosure of LLM usage

LLMs were used throughout the development of this project as a supporting tool for coding, which consisted of: reviewing human written code, writing of some unit tests and coding scripts to generate plots and run experiments.

23

1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The claims made in the abstract correspond to sections 3 through 6. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Appendix G discusses the limitations of the proposed work. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: In Appendix C full proofs and hypotheses are given. Guidelines: 24

• The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: All the code is linked in Appendix I Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] 25

Justification: Links to the anonymized code can be found in Appendix I. In the repositories there are instructions on how to obtain the results described on the paper. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //neurips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: All the hyperparameter details and experimental setup is detailed either in the main paper or in Appendix H. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: All appropiate results are reported with standard deviations using crossvalidation over various splits. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). 26

• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: All the details are given in Appendix H. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The authors have read and abided by the Ethics Guidelines. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] Justification: The current work focuses on general and theoretic properties of Graph Neural Networks. There is no direct path to any potential societal impact on the work performed. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. 27

• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper poses no such risk as it does not contain any models or data that have high risk for misuse. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The datasets used are all properly cited in this work. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 28

• If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: All the code released contains sufficient documentation to be used. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: No crowdsourcing or human subjects is involved. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: No crowdsourcing or human subjects is involved. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage 29

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [Yes] Justification: The use of LLMs is discussed in Appendix J Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

30

Related documents

• Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing#1188234
• Reachability is not enough: Diagnosing long-range behavior in GNNs#1118747
• Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey#189224
• Official Review · NEURIPS 2024#787083
• Not Just Oversmoothing: Detecting the Echo Chamber Effect in Graph Neural Networks#974090