On Measuring Long-Range Interactions in Graph Neural Networks
Authors: Jacob Bamberger
Benjamin Gutteridge
Scott le Roux
Michael M. Bronstein
Xiaowen Dong
Venue: ICML 2025 poster (2025)
Keywords: long-range
GNNs
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a formal range measure to evaluate if a graph task or a GNN architecture is long range

Abstract: Long-range graph tasks --- those dependent on interactions between `distant' nodes --- are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of proposed architectures. However, this is an empirical approach that lacks both robustness and theoretical underpinning; a more principled characterization of the long-range problem is required. 
To bridge this gap, we formalize long-range interactions in graph tasks, introduce a **range measure** for operators on graphs, and validate it with synthetic experiments. We then leverage our measure to examine commonly used tasks and architectures, and discuss to what extent they are, in fact, long-range.
We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evaluation of new datasets and architectures.

On Measuring Long-Range Interactions in Graph Neural Networks
Jacob Bamberger' Benjamin Gutteridge"
Scott le Roux
Michael Bronstein 12 Xiaowen Dong'
Abstract
However, MPNNs struggle to capture long-range depen- dencies, where interactions between distant nodes are criti- cal. These difficulties stem from various well-documented pathologies, such as the difficulty building deep GNNs often attributed to over-smoothing and vanishing gradients (Nt & Machara, 2019; Oono & Suzuki, 2019; Li et al., 2019), or the inability to propagate information through graph bottle- necks attributed to over-squashing (Alon & Yahav, 2020). These limitations hinder the ability of MPNNs to model tasks that depend global or long-range interactions.
Long-range graph tasks - those dependent on interactions between 'distant' nodes - are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of pro- posed architectures. However, this is empirical approach that lacks both robustness and theoret- ical underpinning; more principled characteri- zation of the long-range problem is required. To bridge this gap, we formalize long-range interac- tions in graph tasks, introduce range measure for operators on graphs, and validate it with syn- thetic experiments. We then leverage our measure to examine commonly used tasks and architec- tures, and discuss to what extent they are, in fact, long-range. We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evalu- ation of new datasets and architectures.
Various strategies have been proposed to address these is- sues, but a common theme is the effective reduction of dis- lance on a graph - either via explicit static rewiring (Top- ping et al., 2021; Gasteiger al., 2019; Barbero al., 2023), or rewiring of the computational graph via architectural com- ponents such virtual/latent nodes (Gilmer et al., 2017; Southern et al., 2024), fully connected or multi-hop message passing layers (Alon & Yahav, 2020; Abu-EI-Haija et al., 2019; Gutteridge et al., 2023), and global attention (Vaswani et al., 2017; Wu et al., 2021; :: Rampášek et al., 2022). For many of these methods, the argument that they improve per- formance on long-range tasks is based solely on empirical performance on synthetic and real-world benchmarks.
1. Introduction
However, most synthetic long-range tasks (Bodnar et al., 2021; Rampášek & Wolf, 2021) are simplistic and depend on long-range interactions only, such that a simple rewiring converts them into short-range tasks. Few synthetic tasks acknowledge that graph-structured data and graph tasks are, by design, locally biased: solutions should capture long- range interactions, but should usually prioritize local ones.
Graphs have emerged rich data modality, capable of modeling pairwise relationships between entities in diverse applications. Graph neural networks (GNNs) have become the dominant paradigm for learning from such data, with message passing neural networks (MPNNs) (Gilmer et al., 2020) standing out as the most widely used framework. MPNNs operate by iteratively updating a node's 's representa- tion based on information aggregated from its local neigh- borhood. This local cessage-passing mechanism has been highly effective in wide range of tasks, such as social net- works (Monti et al., 2019), computational chemistry (Gilmer et al., 2017) and recommendation systems (Fan et al., (..
woal-world benchmarks face similar problems. While some recent works have introduced and motivated long-range tasks more systematically (I (Liang et al., 2025), the Long Range Graph Benchmark (LRGB) (Dwivedi et al., 2022) remains ubiquitous. LRGB establishes task rangrdnnedneess via graph size/diameter and domain-specifee intuition. These are necessary, but not sufficient conditions for qualifying task as long-range. Furthermore, LRGB's 's sensitivity to hyperparameter tuning has recently come under scrutiny (Tönshoff et al., 2023), raising doubts about the extent to which its tasks are truly long-range. These issues stem from lack of theoretical characterization of the long-range issue, which hampers efforts measuring and addressing it.
'quual contribution 'University of Oxford A Corre- spondence Jacob Bamberger Benjamin Gutteridge <beng wwr.ootso...c..uk.... Scott le Roux <slcroux www.@@roobboooccomm .x..uk........k.................
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Measuring Long-Range Interactions in Graph Neural Networks
Distance dg(v, +)
Influence ly
Node-level Range
PG
Distance da(u,
Influence lu
Figure 1. Illustration of the range measure on an example grid graph. The distance (left) and influence (center) relative to nodes (top) u (bottom) are indicated by node opacity. Taking node-wise product of distance and influence then aggregating over entire graph yields the node-level range (right; also represented by opacity), e.g. Par All node ranges can then be aggregated to obtain graph range Pg. See Table details on range measure different granularities. We use different influence distributions a to show that influence is task-dependent.
In this work, we address these gaps by formalizing, for the first time, the notion of the 'long-range problem' graphs. Our main contributions are three-fold.
influence based measure a specific instantiation. In addi- tion, their work introduces benchmark, while ours aims deeper theoretical investigation of the rangrrage issue.
Alon & Yahav (2020) introduced prototypical range mea- sure, the problem radius, which, for a task, is defined as the minimal number of hops necessary to solve it. The problem radius generally unknown and is approximated by tuning the number of layers; larger radii require deeper MPNNs. They also introduce the over-squashing problem, phenomena that is closely linked to long-range interactions.
We introduce formal definition of long-range interac- tions in graph tasks, grounded in first principles rather than empirical heuristics. This provides systematic foundation for analyzing both tasks and architectures.
We derive family of principled, quantitative measures of GNN's range the extent which it captures long-range dependencies. These measures apply to node- and graph-level tasks, support evaluation at mul- tiple granularities - node, graph, and dataset - and function both inductive and transductive settings.
Sensitivity analysis by Topping et al. (2021); Di Giovanni et al. (2023a) formalized over-squashing, showing that poorly-connected nodes result in small influence scores. Di Giovanni et al. (2023b) studied pair-wise node inter- actions by casting model expressivity as measure of model's capacity míx node features. Their measure is based on the Hessian of pair-wise node features, focuses specifically on mixing rather than range, and is computed for known tasks; Section 6.1 we demonstrate how our measure can be applied to models trained on arbitrary tasks.
We validate our approach through synthetic experi- ments designed capture long-range interactions, and then apply it to critically assess the LRGB benchmark.
2. Background
Existing range measures. handful of existing works consider the notion of node-to-node interaction for- mally. Xu al. (2018h) introduced the influence score measure of an output node's sensitivity to input node the sum of absolute values of their Jacobian. This approach adapts influence functions to graphs, building on the work of Koh Liang (2017), who originally applied them to interpret neural network predictions. Recent work by Liang al. (2025) motivates a novel long-range benchmark us- ing proposed influence-barr based measure. Our work derives family of measures from first principles, of which their
Graphs and features. A graph is tuple (V, E) of a set of nodes V and edges E. We denote the number of nodes by n = MV. and edges are represented as tuples (u, v) E The graphs considered in this work are undirected, and are often represented by an adjaceney matrix E {0. 1 with corresponding degree matrix D diag(Al). We denote the features at node by x, E RR and stack all node features into matrix X E IRaxd We denote by Ag. (u) the k-hop neighbors of node i.c. the nodes at exactly hops as per shortest-path distance (SPD), and by NE (u) the k-hop neighborhood ur all nodes at or fewer hops.
All code for reproducing experiments is available https: /igi thub. com/ Berrutter wtw.tt//eeedeeeeeeeeeeeeeeeeeeee measure
2

---

On Measuring Long-Rang Interactions in Graph Neural Networks
GNNs. In many applications, the goal is to perform predic- tion task starting from data modeled as graph G and node features X E IRa For node-level tasks, predictions are made based on a representation for every node u denoted Yu E Re which can be stacked into a matrix Y E IR GNNS are used to achieve such predictions. Most GNNs, including widely used MPNNs (Kipf& & Welling, 2017; Xu al.. 2018a; Bresson & Laurent. 2017) and graph Trans- formers (GTs) update the nodes features sequentially by computing hidden node features H()) E Raxd, at each of I. layers. with input H = X and final layer output Y = (4), For graph-level tasks, a further pooling opera- tion is applied to obtain a single graph-level output y E R
is better suited to studying how information propagates in MPNNs (Di Giovanni et al., 2023a; Black al., 2023). For full generality of the measure, we simply assume that we are given a metric de V x V + R+ on the graph, with respect to which we measure the range denoted Pu:
For our experiments we focus on SPD and resistance dis- tance, denoted by pid and pu respectively.
3.1. Derivation of node-level range
We first state the desirable properties of the range measure, Pu. which quantifies the range of interactions received by a node u under linear task L.
3. Formalizing the range of a node-level task
Property (Locality) The range at node u should only depend on interactions received by node u. i.e. Pu (1we)
To address the challenge of quantifying long-range rangerange inter- actions in GNNs, we propose a measure of the range of a task, GNN, or, more generally, an operator on graph. This measure captures how strongly distant nodes interact. We derive the measure from first principles as the unique measure that satisfies set of desired properties.
0 if w # u.
Motivation: Ensures that the range measure does not depend on irrelevant parts of the graph.
Property 2 (Unit interaction) If the output of node depends solely on the input of another node at distance de(u, v) = r, then the range should equal r. i.c. Pu (uww) = dG du(u, u)
We first propose a definition of the range of node-level task. By node-level task a graph, mean map F transforming an input signal X E RRxd into an output Y= F(X) E R=xe. The range should be applicable to any map F, including linear ones i.e. such that F(aX- (X))= (F( + (X() for all a, b E R and X, X' E gaxd We restrict our attention linear maps, denoted L, and for simplicity consider the case d c 1, where linear map corresponds to a matrix L E RR and Luv is the interaction from to An example of a linear map is the transformation denoted by luv. This transformation copies the value at position v from the input and places it at position u, setting all other values to zero. Specifically, it transforms the matrix X into a new matrix Y, where Y is zero everywhere except at index u, where y. X
Motivation: Provides a baseline for what constitutes the range of a single interaction.
Property (Additivity) The range of disjoint interac- tions" should be the sum of their individual ranges. If L' and L are disjoint, then P, (L L²) p. (L') + Pa (L²).
Motivation: Ensures that the range appropriately aggre- gates independent contributions to the output.
Property 4 (Homogeneity) Scaling the interaction strength should proportionally scale the range, i.e., Va E R, P,, = |a (L.)
Motivation: Guarantees that the measure meaningfully reflects the strength of interaction.
As task can be long-range around one node and thant-range around another, the range measure should be defined for every node. Our goal is thus to find a suitable definition of the range of a task F at a node u. denoted by (F) E I...
"We say that two linear maps L,,, I consist of disjoint interactions, or are disjoint, if [La > O - L = 0 and L > 0 - L = 0, in other words, they do not capture interactions between the same pairs of nodes.
Distance metric. A critical aspect of defining this measure establishing notion of distance between nodes, with respect to which the range can be defined. While metrics like Euclidean distance are commonly used for sequences and grids, graphs are more complex as there are many choices of metric. Common options include SPD (the length of the shortest path between two nodes in hops), commute-tie distance (based on the expected time for a random walk to travel between nodes), and diffusion distances (capturing connectivity in terms of information flow). While SPD is intuitive, recent work suggest that commute-time distance
Remarkably, from these we can uniquely derive Pa:
Theorem 3.1. Given a graph G, metric de, and node u, there is unique range Pv defined on one-dimensional linear tasks that satisfies Properties 1-4, and, given a linear task Y = I (X), corresponds to the following:
Pu Σ VVV
L |d (u, v).
3

---

On Measuring Long-Rang Interactions in Graph Neural Networks
Table 1. Normalized range measures based on the Jacobian and Hessian, for node-level and graph-level tasks, and at node, graph, and dataset granularities. For node-level tasks, p denotes ranges derived from the Jacobian (the first-order Taylor series term), which we use as it provides a set of pairwise interactions. For graph-leve tasks, the Jacobian does not provide pairwise interaction terms, so we instead use range measures derived from the Hessian (the second-order Taylor term), and denote them by
Jacobian-based (p)
Hessian-based (17)
Granularity
Node
Graph
Dataset
Node
Graph
Dataset
Node-level tasks
Pu (Eq. 2) Pc == +o Evev Pu Em= Pcu
N/A
N/A
N/A
Graph-level tasks
As above; using pre pre-pooiig node features*
Nu (Eq. 4)
n == EnEV Ai
ig = N EE= fG.
1
Proof. The linear tasks form a vector space which is spanned by the maps 1 ue- Any linear map L can there- fore be decomposed into a sum L= = Eis Ly By Prop- erty 3, since each iig are disjoint, we must have Pu (L) Ey Pu. (LLg 12)). By Property 1 the range at u depends only on the terms with i u, i.e. Pa (L) = Σ Seev/e Pue (Luo (T ao)) By Property 4, we deduce that P. (L) = Ep Lu CuolPulC (Lwv).
8 (F(()))
Pu (F) = Σ
do(u, v), and
(1)
OX.
DEV
Pu. (F) = Σ >
Pu.
(F)
((F(X))
8x.
By Property 2, we get Pr. (L) = >. [Lw ddlu,
In particular, when restricted to linear maps, the measures defined in Equations 1 & 2 are the unique measures from Theorems 3.1 & 3.2.
Normalized range. One consequence of the above proper- ties of Pa is that many short-range interactions can increase the range. For example, m disjoint interactions at distance results in a range of m, when we might prefer the range to reflect the average (or in this case, unanimous) range, which in this case would be 1. As a remedy, we consider a normal- ized range, P... by replacing Properties & 4 by:
Since GNN with weights θ parameterizes a differentiable map Fe (X) Y. can straightforwardly use this defi- nition to compute the range of any GNN. Furthermore, we can generalize the measure to the case of multiple input and output channels in an equivalent form as an expectation with respect to the influence distribution Tu:
Property 5 I and L are disjoint, then Va + 0, 3, Pu + 3L3) [al
(L')+
A
Pu (
Pu (F) = En Fu (u, u)]
(3)
normalizing constant and a and B index the output and input channels respectively. This formulation extends natu- rally to higher dimensions, since the influence distribution is not restricted to dimension 1. Using this viewpoint, we can interpret Au as measuring the average distance over all interactions, or as the average displacement after following random walk defined by the influence distribution. Addi- tionally, the probabilistic viewpoint permits fast stochastic approximations of the normalized range. For these reasons, we favor the normalized range in our experiments.
where [v(v)
1
Ea.0
aF 0x
From which we also derive a uniqueness result:
N.
3
Theorem 3.2. Given a graph G, metric dG, and node u, there a unique range Pw.. defined on one-dimensional linear tasks, that satisfies Properties 1, 2 & 5, and given a linear task Y L (X) it corresponds to the following:
Nu = E
8FF 8x
Pu (L) = E. Luvi
Σ VEV
L r)
v))
Proof. As in the above proof, we decompose L By Properties & 1 & we get (L)
Liglis EijLig
Evev bool Evev Luoll,( and by Property 2 we con-
Range granularities. We define a hierarchy of range granu- larities to capture task-specific statisties at different levels. The node-level node range P. is defined for every node u. Averaging over all nodes in graph G yields the node-level graph range PG- Similarly, averaging over all graphs in dataset G gives the node-level dataset range Pgg This hierarchy allows the range measures to be computed on both transductive and inductive tasks. We use the graph and dataset granularity for our figures and experiments in Sections and 6. See Table 1 for details and summary.
clude P.. EneV ILnol Evev (dc,,, v).
0
Range of GNN. In order to apply the above range to GNNs it suffices to extend this measure to any differentiable map F (X) Y. This is done by applying the above to the Jacobian, namely the best linear approximation of F.
For graph-level tasks, the Jacobian-based method is introduced computationally more efficient alternative. See Section 6.2. for details.
4

---

On Measuring Long-Range Interactions in Graph Neural Networks
4. Range of a graph-level task
Range granularities. As in the node-level case, we define hierarchy of range granularities for graph-level tasks. The graph-level node range ny is defined per node u. Averaging over nodes in graph G yields the graph-level graph range Ôg. and averaging over graphs in a dataset 9 gives the graph- level dataset range îg.. See Table for details.
For node-level functions, the Jacobian - corresponding to the first-order term in the Taylor expansion - provides a set of interactions between all nodes, making suitable to cap- ture pairwise node sensitivity. However, for graph-level function y (X) E R the Jacobian is a vector, only captur- ing the sensitivity of the output with respect to individual nodes. This makes it unsuitable for assessing pairwise inter- actions. To capture such interactions, we use the Hessian, which appears the second-order term of the Taylor expan- sion. This is in line with the mixing measure from Giovanni et al. (2024), in which the Hessian is used to study infor- write
5. Task Range Examples
In this section illustrate the proposed range measures, computing them for different tasks and topologies for node- and graph-level tasks, both empirically and analytically.
mation propagation in GNNs. For completeness, down the Taylor expansion of a task in the 1-dimensional case, where A E IR" is a small perturbation applied to X:
5.1. Design of synthetic tasks
We design synthetic examples under general framework of pairwise tasks on graphs. The framework consists of the combination of a distance function D V x V + R and an interaction function I I2 x Rd - RR. A node-level task obtained as F (X).. = + BEE D(u, - x.), where + denotes an aggregation. The interaction function is a general pairwise function and the distance function scales the magnitude of the pairwise interactions. Graph level tasks can then be obtained as y yXX) = X uev Drey D(u, u)- [(x., ) where X is another aggregation. This provides a general framework to design tasks on graphs, which we use to design tasks of varying range.
(X)
y(X + yX
XX
lirst onder
I yx 1 (A.)²
u:3 0x,0xx
Ox2 u 2
second
+ o (1A13)
higher order
We then define the graph-level range in the one- dimensional case as the analogous quantity:
5.2. Empirical examples
In order to investigate the impact of graph topology and task definition on the range measure, we consider several distributions of graph topologies and three linear tasks.
Oy
na (x)
do(u, v),
0xm
VEV
and its normalized version:
Impact of topology. To study the impact of the topology of graph on the range, we consider node-level regres- (4) sion tasks that predict A for some k where A& is k-th power of the symmetric normalized adjacency with self loops, and graph-level regression tasks which consists of the squared difference interaction and the same distance.
Tu (y)
iu (y)
Evev
B²y
Ux.,
As in the nove-level case, we extend this to higher dimen- sions for both input and output channels and represent the measure an expectation:
103.
Grid
nu (y) := Eund, [dc r)],
BA
Sparse ER
1/6
Sparse SBM
where J, is the distribution Ju(v) = No Ensg.
1
Ix: 0x: 02y?
8-y
10-1
SBM
and at, 3,, y are the dimensions of the inputs and the output. The
with normalizing constant N₂, = Enja.t. Oxg 0x
6
term d'y² axaxx
corresponds to the mixing between channel a
Figure 2. Topology of graph impacts range. Ranges of node-level tasks predicting A ' (left) and graph-level tasks using a squared difference interaction function and the same distance function, where D(u, v)- (A )av. averaged over nodes (right) for varying & on graph distributions. While task choice affects range, high range requires topologics with sufficiently large diameter.
of x, and channel / of x, to compute channel 7 of (X), so this quantity measures the total mixing between the two nodes. Similarly to the node-level measure, the normal- ized range generalizes to higher dimensions, enabling fast stochastic approximations of fr.
5

---

On Measuring Long-Range Interactions in Graph Neural Networks
Figure 2 shows the task range for varying values of k on different distributions of graphs, namely on 1-dimensional grid graphs (i.e. line graphs), dense (p 0.3) and sparse (p = 0.1) Erdós-Renyi graphs (ER) with 100 nodes, and on dense (Pimtra = 0.75, Pinter = 0.25) and sparse (Pinta = 0.3, Pinter = 0.1) stochastic block models (SBM) with 100 nodes. We notice that, overall, the ranges of the tasks increase with k. but the topology affects the rate at which the range grows. Indeed, sparse topologies (e.g. grids) that permit large diameters result in larger ranges than those induced by their denser counterparts (ER, SBM).
5.3. Analytic node-level examples
We now consider example tasks whose range can be com- puted analytically.
Example 1. Consider a task that is computable by a node-
level function. That is, there exists a f IR + I such that F is simply applying / node-wise F(X),, := ((X)). In this case, no matter the distance metric chosen, (F) = Pu (F) 0, independently of u and X. This shows that in the extreme case of purely local task, the range is
Example 2. Consider the node-level task which averages the squared difference of node features within the k-hop neighborhood, where the node features are sampled i.i.d. from a standard Gaussian distribution:
Impact of task. We now fix the topology to be a grid-graph and compute the range of the three following tasks:
k- k-Power: Predicting the function F (X) = A where & is the k-th power of the symmetric normalized adjacency matrix without self-loops.
F (X), We (w)
Σ
(X,, x,)
This is a 1-dimensional task whose Jacobian is given by:
k- Rectangle: Predicting the function F (X)... [w)((W] EveNgu(a) X., the mean of inputs over all nodes within & hops.
OF (X),
2
(x. xu) if E Wexx (u)
0x,
otherwise,
k-Dirac: Predicting the function F F(X),. [N] EvENs(u) X., the mean of inputs over all nodes that are exactly k hops away.
and whose normalized range with respect to SPD
2 W (u)
pap (F*))
Xx. X. Xulr; r;
Nu.
We plot the ranges for different k for all three tasks in Figure 3. As expected, all tasks become more long-range with increasing k. with a clear order in the ranges for each fixed k: k-Dirac > k-Rectangle > k-Power. This can be understood by visualizing the shape of the influence distribu- tion of the three tasks (see Figure 3): the mass concentrated furthest away for the Dirac task, spread uniformly for the rectangle task, and concentrated locally for the power task.
(w)
where Nu. = EveNeH(u) [ea(()] 1x, x. is the nor- malizing constant. Since the features i..d. Gaussian,
[ xx| is half-Gaussian with expectation J so the ex- pected N₂ is A and the expected normalized range is:
Ex (F*)]= W (u)
A-Dirac
spp 6 PG
Rectangle Power
k-Dirac & Roctangle
In particular, we have Ex [x[px' (F*+1)] Ex (F+)), with strict inequality if Ne 1 (u) is non-empty, showing that the range increases with k.
k Power
2-
5.4. Analytic graph-level examples
2
4
6
Example 1. Consider task that is computable without mixing between nodes, namely, there exists a node-wise f :R Rd function such that the task y is simply a sum over all nodes: y(X) Σn. fxx.). In this case, no matter the metric chosen, Tg (y) = nG (y) 0.
(a) Per-task ranges
(b) Influence distributions
Figure 3. Task impacts range. (a) illustrates, for each of the synthetic tasks, SPD range on a grid graph for varying k. Owing observe linear
the shape of each influence distrihution, increase for k-Dirac and k-Rectangle, and a sublincar increase for P-Power. (b) illustrates, on a line graph, the influence distribution for the central node for each task when & = 2. For k-Power the influence decays with distance, while k-Dirac influence zero where except at the k-hop.
Example 2. Consider the graph-level task which sums the squared difference of features on nodes within the k-hop neighborhood followed by averaging over the graph:
Σ
(Xa - x,) BEV vENeN(a)
Σ
V
6

---

On Measuring Long-Range Interactions in Graph Neural Networks
The second derivatives are
Q'y 2x
M
and:
1.25
Depth 1.0
True PC
PC
1.00 gres
Depth 7
O'y
i E ENg (u)
Depth 0.5
M
0.75
Depth
0x,
0
otherwise.
Depth
0.50
Depth 0.1
MSE
Hence the normalizing constant is N₂ = o/Ner(W) ing in the following normalized range:
Depth
result-
0.25
Depth 0.0
M
15 Epoch
10
2
5 Depth
1 (y*) 2 S (w)
E.N. (V (u)lr,
Figure 4. Node-level range can be approximated with good model. (Left) Average node-level dataset range evolutions for different GCN depths line graph for the 5-power task. Shaded area corresponds to min/max over 4 seeds. (Right) Range and MSF epoch 20 against number of GCN layers.
showing that the range increases with ls as the task incorpo- rates interaction between more distant nodes.
6. Experiments
True n
In many real-world scenarios, the underlying task is un- known, making it essential to characterize task properties empirically. In this section, we present empirical results in this direction on both synthetic and real- world experiments. First, we demonstrate that the range of a trained model that solves task approximates the range of the underlying task. We then leverage this observation to analyze the LRGB benchmark by the range of models trained on its tasks.
Depth
Depth
0.6
0.6
Depth
Depth
0.4
0.4
Depth
Depth
0.2
0.2
Depth
Depth
0.0
10
20 30
40
0.0
10
20
30
40
Epoch
Epach
While this approximation holds in synthetic settings where the task is solved nearly perfectly, real-world models do not achieve zero error, and thus do not provide a unique or exact estimate of task range. Nevertheless, we find that the correlation between model range and performance across architectures offers useful heuristic: tasks where better- performing models tend to exhibit longer range are plausibly long-range in nature, while those where performance satu- rates at low range are likely dominated by local interactions.
Figure 5. Average dataset range evolutions for different GCN depths on a line graph, using the 5-Power distance function and squared difference interaction function from Section 5.4. Shaded area corresponds to min and max over seeds. (Left) Graph-level range be approximated with good model. (Right) Pre- pooling node-level range correlates with graph-level range.
and plot final MSE vs. depth. Deeper models approach the true task range and achieve lower MSE, while shal- low models under-perform due to limited receptive fields and under-reaching. These results demonstrate that, under ideal conditions, model range converges toward the true task range as training progresses and depth increases.
6.1. Do GNNs approximate the true range of a task?
This section investigates whether the range of a well-trained GNN can approximate the range of the underlying task. When using a GNN, we implicitly assume that the target function is parameterizable and thus admits true range. This raises a central question: under what conditions does the range of GNN align with that of the task? We argue that when the validation error approaches zero - -i.e,, when the model generalizes well - the range of the GNN converges to the task range. We demonstrate this empirically in a controlled synthetic setting, across both node- and graph- level tasks. These results support using the range of a trained GNN practical proxy for the range of real-world task.
We repeat this on graph-level task as shown in Figure 5. We use the same distance function as for the node-level but replace the interaction function with the squared difference followed by averaging over the nodes, as in Section 5.4. This makes the task non-linear and guarantees a non-trivial Hessian. We also use GeLU activation to make the models non-linear. Similarly the node-level case, the graph-level range ig of deeper models tends towards the true task range. Figure 5 also shows the mean node-level range of the pre- pooling node embeddings, i0:; we can see that 2 follows similar trend to f suggesting a correlation between the two measures. This justifies using P over rig in our LRGB experiments in Section 6.2, and allows a greater focus more on pairwise interactions induced by pesssag--passing
Figure 4 illustrates linear GCNs with residual connections of varying depths predicting A on a ID grid graph - a 5-hop task with p = 1.33. Models are trained on 500 samples with i.id. standard Gaussian node features. We track the evolution of the range of a model during training

---

On Measuring Long-Range Interactions in Graph Neural Networks
6.2. Validating real-world benchmarks
not compromise accuracy. Sub-sampling is performed over output nodes as well as input and output feature channels, according to by pre-defined probability hyperparameters (details in Appendix D.4).
The goal of this section is to evaluate (i) whether GNNs trained on existing gang-r benchmarks do indeed learn long-range functions, and (īi) whether the underlying bench- mark tasks themselves are long-range.
app Distance metric. We focus on Pg as (i) SPD is more in- terpretable than resistance distance, and (ii) results were generally similar to those for p In particular, PEPTIDES graphs have similar topologies to line graphs. for which SPD and resistance are equivalent. Figures for resistance range can nevertheless be found in Appendix C.2. VOCSU- PERPIXELS, PEPTIDES-FUNC and PEPTIDES-STRUCT are evaluated on F1 score, average precision (AP) and mean absolute error (MAE) respectively.
As previously mentioned, we acknowledge that the unsolved nature of real-world tasks means that range of a model alone cannot definitively give us the range of the underlying task; furthermore, models might exhibit bias towards par- ticular ranges depending their design. To address this, we analyze the correlation of performance and range for a spectrum of architectures, to determine if a model is a good approximator, and whether long-range interactions are beneficial to the downstream task.
Graph-level tasks. For the graph-level PEPTIDES tasks, we compute the node-level, Jacobian-based range (see Table 1) using node representations obtained after the final message- passing layer, but before global pooling and final MLP. This is partly due to the high computational cost of estimating the Hessian for large graphs with high feature dimensionality. More importantly, since the post-message- paassssi-g compo- nents are standard architectural elements applied uniformly across models, we focus on the long-range interactions in- duced specifically by the GNN layers.
Furthermore, we include additional experiments on CORA, known short-range task, and on heterophilic tasks (Platonov et al., 2023) in Appendix C. These experiments support the intuition that the correlation between performance and model range is suitable heuristic to assess the range of a task, and show that GT's are able to learn to be short-range.
6.2.1. 1. EXPERIMENTAL SETUP
Models. We consider four models, GCN (Kipf & Welling, 2017), GINE (Xu al., 2018a; Hu et al., 2020), GatedGCN (Bresson & Laurent, 2017) and GPS (Rampášek et 2022), from Tönshoff et al. (2023), which reports more accurate baseline LRGB performance than Dwivedi et al. (2022), a hyperparameter search and correct normalization having been performed for each task. We also use a pure graph transformer without peessage-passing (GT: Vaswani et al.
6.2.2. RESULTS
10a
Model: F1f
GPS
.451s.
GT
.392s.00 00
popd
GatedGCN
.3782.00
GINE
.275..00
GCN-VN
.245..00
(2017)) and GCN with a virtual node (GCN+VN) to ensure set of models with broad range tendencies.
GCN
.185..
10a
(4 seeds)
40 60
80 100
Epoch
Epoch
Tasks. From LRGB, we consider VOCSUPERPIXELS node-level classification task, and DEPTIDES-FUN and PEPTIDES-STRUCT, graph-level classification and regres- sion tasks respectively. The models are trained using the hyperparameters from Tönshoff et al. (2023). We track p and n3 throughout training using the Jacobian of node out- put features with respect to input features. Figures 6 & 7 show evolution of model range over training for a subset of the validation split; 500 graphs for VOCSUPERPIXELS, 200 each for PEPTIDES. We use subsets as we found that this approximates the full dataset ranges well, while being significantly less compute-intensioe dation results as range estimates were found to be highly consistent across splits.
Figure 6. pnd for MPNN and GT models during training, evalu- ated on 500-graph subset of the validation split for VOCSUPER- PIXELS. We cut off after 100 epochs as ranges have converged. The fact that pe settles ~2-3 for MPNNs and at ~-10 for GPS, and that range positively correlates with performance, suggests that VOcSUPERPIXELS is, to some degree, rong-range. Standard deviation is over 4 model/sampling seeds. Log scale on y-axis.
VOCSUPERPIXELSS Figure 6 shows that all models in- crease in range during training, primarily within the first few epochs. MPNNs reach a final range of ~2-3 hops, while GPS and GT reach around ~10 This is consistent with the notion that MPNNs learn local information first and incorporate more distant information as training progresses. Additionally, range correlates positively with performance across models, and relative ranges are in line with our un- derstanding of each model.
We report only vali-
Jacobian sampling. To reduce the computational cost of range computation, we use an estimate of the range (see Equation 3) obtained from a sub-sampling of the Jacobian. This is essential due to the large size and feature dimen- sionality of the LRGB tasks, and we observe that it does
GINE and GatedGCN, being more expressive than the
8

---

On Measuring Long-Range Interactions in Graph Neural Networks
training; for PEPTIDES-STRUCH the range of GINE even decreases. This suggests that the PEPTIDES tasks are in- herently local. Although GPS and GT exhibit larger ranges and to lesser extent, GatedGCN on PEPTIDES- these do not translate into improved performance. Similarly, GCN+ VN has higher range than the MPNNs but yields minimal or no performance gains. These findings indicate that while some models are capable of modeling long-rann long-range interactions, such capacity is unnecessary for solving the PEPTIDES tasks effectively.
Model:
AP
GCN+VN
.6952.01
10 5ppd Pg
GINE
.6932.00
.692s.00 00
GatedGCN
.6811.01 01
GPS
.654s.0 01
GT
.593z.06 06
(4 seeds)
1
2 3
4
$
20
40
60 Epoch
80
100
Epoch
(a) PEPTIDES-FUNC
For PEPTIDES-STRUCT this finding is less surprising; Tönshoff et al. (2023) report that GCN remains state-of- the-art, even when compared against an array of more ex- pressive models. For PEPTIDES-FUNC, however, several later works report improved performance compared the models considered here. Notably, these approaches often incorporate some form of long-range information flow, such as dynamically rewired multi-hop (Gutteridge et al., 2023) or global attention with added inductive bias (Ma et al., 2023). However, both of these examples emphasize the im- portance of short-range interactions in their architectures by integrating strong local inductive bias. Indeed, this seems to be a requirement for long-range models perform well PEPTIDES-FUNC Given that our findings suggest that PEPTIDES- FUNC may not be especially long-range, these models' performance is, perhaps, more attributable to how information is propagated than to their range capabilities.
Model: MAE
GatedGCN
.244 00
GCN
.245..00 00
GINE
.0
GCN+VN
.2462.00
GPS
.2562.00
10a
GT
.293..02 02
(4 seeds)
2
Epoch
Epoch
(b) PEPTIDES-STRUCT STRUCT
2nd Figure 7. PC for MPNN and GT models during training, evalu- ated on 200-graph subset of the validation splits for PEPTIDES- FUNC and PEPTIDES- -SRUCC. We cut off after 100 epochs as ranges have converged. The negative correlation between perfor- mance and range may suggest that the PEPTIDES tasks are not as long-range as previously assumed. Standard deviation is over 4 model/sampling seeds. Log scale on y-axis.
7. Discussion
purely convolutional GCN, improve resistance to the over- smoothing and over-squa phenomena that hamper long- range interactions, and therefore attain higher ranges but they are ultimately still MPNNs, so the difference is slight. GCN+VN improves significantly the performance of pure GCN and induces a larger range, as the VN mitigates under-reaching by creating a 2-hop connection between all nodes. GPS, the best-performing model, uses global attention - which permits a large range and mitigates over- squashing - alongside a local GatedGCN component.
This work formalizes long-range interactions for graph tasks, introduces family of principled and quantitative range mea- sures, and applies them to synthetic and real-world tasks. We believe that these measures will serve as tools that af- ford both a greater understanding of the long-range prob- lem in graph machine learning, and as an additional vali- dation method for future proposed architectures and bench- mark tasks. More broadly, our findings highlight the need for GNN evaluation to move beyond performance metrics, incorporating interpretable measures- -uchh as range- for more transparent and principled assessment. Finally, our proposed range measures are not limited to GNNs or graph learning tasks and can be applied to any geometric domain equipped with a notion of distance.
The observed positive correlation between model range and performance suggests that VOCSUPERPIXELS is inherently a long-range task, in that successfully solving it requires incorporating information from distant nodes. The poor performance of MPNNs on this task can therefore be at- tributed to their limited ability to capture long-range depen- dencies, likely due to under-reaching, over-smoothing, and over-squashing.
Future work will further investigate our fessian-basee range measures ú for evaluating real- benchmarks alongside, and in comparison with, the node-level range. Future work will also focus on investigating specific architectural compo- nents such as fully connected layers, graph rewiring, resid- ual connections, and positional or structural encoding, and their impact on the range of model. This will include both empirical and theoretical analysis assess how common GNN building blocks influence range in a principled way.
PEPTIDES. In contrast to VOCSUPERPIXELS. PEPTIDES- FUNC and PEPTIDES-STRUCT exhibit the opposite trend: GT and GPS perform the worst while the three MPNNs all perform similarly well. Notably, the MPNNs maintain a range Pg of ~11 hop after epoch 1, with no increase during

---

On Measuring Long-Rang Interactions in Graph Neural Networks
Impact Statement
Barbero, F., Velingker, A., Saberi, A., Bronstein, M. M., and Di Giovanni, F. Locality-aware graph rewiring in gnns. In The Twelfth International Conference Learning Representations, 2023.
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Black, M., Wan, Z., Nayyeri, A., and Wang, Y. Under- standing oversquashing in gnns through the lens of effec- tive resistance. In International Conference on Machine Learning, pp. 2528 2247. PMLR, 2023.
Acknowledgments
We thank Federico Barbero, ismail Īlkan Ceylan and Francesco Di Giovanni, discussions with whom helped shape the presentation of this work. BG and SLR acknowl- edge funding support from EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems No. EP/S024050/1. MB and JB are partially supported by the EPSRC Turing AI Wordd-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub No. EP/Y028872/1.
Bodnar, C., Frasca, F,, Otter, N., Wang, Y., Lio, P., Montu- far, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34:2625-2644 2021.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv: 2017.
Choi, J., Kim, H., An, M., and Whang, J. J. Spot- mamba: Learning long-range dependency on spatio- temporal graphs with selective state spaces. arXiv preprint arXiv:2406. /244, 2024.
XD acknowledges support from the Oxford-Man Institute of Quantitative Finance and the EPSRC No. EP/T023333/1.
References
Deac, A., Lackenby, M., and Veličković, P. Expander graph propagation. In Learning on Graphs Conference, pp. 38-1. PMLR, 2022.
Abboud, R., Dimitrov, R., and Ceylan, I. Shortest path networks for graph property prediction. In Learning on Graphs Conference, pp. 5-1. PMLR, 2022.
Di Giovanni, F., Giusti, L., Barbero, F,, Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International conference on machine learning, pp. 1885-7885. PMLR, 2023a.
Abu-FI-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In in- ternational conference on machine learning, pp. 21-29. PMLR, 2019.
Di Giovanni, F., Rusch, T. K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veličković, P. How does over-squashing affect the power of gnns? Transactions on Machine Learning Research, 2023b.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205. 2020.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- tems, 01-22226-2224000 2022.
Ardaiz-Rodrguue, A. and Errica, F. Oversmoothing," over- squashing", heterophily, long-range, and more: Demysti- fying common beliefs in graph machine learning. arXiv preprint arXiv:2505.15555 2025.
Fan, W., Ma, Y., Li, Q. He, Y., Zhao, E., Tang, J., and Yin, D. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Amaiz-Rooriguee A., Begga, A., Escolano, F., and Oliver, N. M. Diffwire: Inductive graph rewiring via the lovász bound. In Learning on Graphs Conference, pp. 15-1. PMLR, 2022.
Finkelshtein, B., Huang, X., Bronstein, M. M., and Cey- lan, I. I. Cooperative graph neural networks. In Inter- national Conference on Machine Learning, pp. 13633- 13659. PMLR, 2024.
Arroyo, Á., Gravina, A., Gutteridge, B., Barbero, F., Gal- licchio, C., Dong, X., Bronstein, M., and Vandergheynst, P. On vanishing gradients, over-smoothing, and over- squashing in gnns: Bridging recurrent and graph learning. arXiv preprint arXiv:2502. 10818 2025.
Gasteiger, J., Weißenberger, S., and Günnemann, S. Diffu- sion improves graph learning, Advances in neural infor- mation processing systems, 2019.
Bamberger, J., Barbero, F., Dong, X., and Bronstein, M. M. Bundle neural network for message diffusion on graphs. In The Thirteenth International Conference on Learning Representations, 2025.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning. pp. 12722 PMLR, 2017.
10

---

On Measuring Long- Rong-Range Interactions in Graph Neural Networks
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. F.. Message passing neural networks. In Machine learning meets quantum physics, pp. 199-214. Springer International Publishing Cham, 2020.
Lukovnikov, D., Lehmann, J., and Fischer, A. Improving the long-range performance of gated graph neural networks. arXiv preprint (xXXv:2007.09660 2020.
Ma, L., Lin, C., Lim, D., Comero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases in transformers without message passing. In International Conference Machine Learning, pp. 23321 -23377 PMLR, 2023.
Giovanni, F. D., Rusch, T. K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veličković, P. How does over-squashing affect the power of GNNs? Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Monti, F., Frasca, F., Eynard, D., Mannion, D., and Bronstein, M. M. Fake news detection on social me- dia using geometric deep learning. arXiv preprint arXiv: /902.0667,, 2019.
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Gio- vanni, F. Drew: Dynamically rewired message pass- ing with delay. In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.
Nt, H. and Maehara, T. Revisiting graph neural net- works: All have low-pass filters. arXiv preprint 10XXv:990500955000 2019.
Hariri, A. and Vandergheynst, P. Graph learning for cap- turing long-rann range dependencies protein structures. In Machine Learning for Computational Biology, 2024.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. In International Conference on Learning Representations, 2019.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In International conference machine learning, pp. 22724-127455 PMLR, 2023.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. critical look at the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
Hu, W., Liu, B., Gomes, J., Zitmik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neu- ral networks. In International Conference on Learning Representations (ICLR), 2020.
Karhadkar, K., Banerjee, P. K., and Montufar, G. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. The Eleventh International Conference on Learning Representations, 2022.
Rampášek, L. and Wolf, G. Hierarchical graph neural nets can capture long-rango interactions. 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2021.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T. Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. Advances in Neural Information Processing Systems, 35: 15:14501-145111 2022.
Koh, P. and Liang, P. Understanding black-box predic- tions via influence functions. In International conference machine learning, pp. 1885-1894. PMLR, 2017.
Southern, J., Di Giovanni, F., Bronstein, M., and Lutzeyer, J. F. Understanding virtual nodes: Oversmoothing, oversquashing, and node heterogeneity. arXiv preprint 24Xv:2405.13526 2024.
Li, G., Muller, M., Thabet, A., and Ghanem, B. Deepgens: Can gens go as deep cnns? In Proceedings of the IEEE/CVF international conference computer vision, pp. 9267-9276, 2019.
Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., and Metzler, D. Long range arena A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
Liang, H., de Ocáriz Borde, H. S., Sripathmanathan, B., Bronstein, M., and Dong, X. Towards quantifying long- range interactions in graph machine learning: a large graph dataset and a measurement, 2025.
Tönshoff, J., Ritzert, M., Rosenbluth, E.,, and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. In The Second Learning on Graphs Confer- ence, 2023.
Lukovnikov, D. and Fischer, A. Improving breadth-win backpropagation in graph neural networks helps learning long-range dependencies. In International Conference on Machine Learning, pp. 7180-7191. PMLR, 2021.
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. Understanding over-squashing and

---

On Measuring Long-Range Interactions in Graph Neural Networks
bottlenecks graphs via curvature. In International Conference Learning Representations, 2021.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Wang, C., Tsepa, O., Ma, J., and Wang, B. Graph-mambee Towards long-range graph sequence modeling with se- lective state spaces. arXiv preprint arXiv:2402.00789, 2024.
Wu, Z., Jain, P., Wright, M., Mirhoseini, A., Gonzalez, J. E.,, and Stoica, Representing long-range context for graph neural networks with global attention. Advances in neural information processing systems, 34: 13266-1327, 2021.
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? In International Conference on Learning Representations, 2018a.
Xu, K., Li, C., Tian, Y.. Sonobe, T., Kawarabayashi, K.- i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In International con- ference on machine learning, pp. 5453-5462. PMLR, 2018b.
Zhou, D., Kharlamov, E., and Kostylev, E. V. GLora: A benchmark to evaluate the ability to learn long-range dependencies in graphs. In The Thirteenth International Conference on Learning Representations, 2025.
12

---

On Measuring Long-Range Interactions in Graph Neural Networks
A. Detailed discussion of related work
In this section we review existing attempts at long-range benchmarks, both synthetic and real-world, as well as methods that attempt to solve the long-range problem. and how they validate their claims.
A.1. Long-range benchmarks
Dwivedi et al. (2022) argue that the standard suite of GNN benchmarks are inappropriate for evaluating long-range interactions as they are overwhelmingly local, consisting of graphs with small number of nodes and narrow diameter. They then introduce the Long Range Graph Benchmark (LRGB), a suite of tasks whose long-rangedness established, variably, by (i) large graph size/diameter, (ii) the necessity of graph-level mixing, and (iii) arguments based intuitive understanding of the underlying task - e.g. classifying long peptide chains with globally-dependent properties. They also show performance gap between 'short-range' standard MPNNs and GTs utilizing global attention, though Tönshoff et al. (2023) have since shown that this gap is significantly narrowed by simple hyperparameter tuning, calling into question the extent to which the LRGB tasks are truly long-range. Despite this, LRGB remains the de-facto validator of long-range performance.
Synthetic tasks are also frequently used, Examples include Ring RingTransfer (Bodnar et al., 2021), where source node must infer a distant target node's 's label on a ring graph, color connectivity task where graph with binary-labelled nodes must be classified as having one 'island' of clustered labels or two (Rampášek & Wolf, 2021), and tasks approximating searches on trees (Lukovnikov et al., 2020; Lukovnikov & Fischer, 2021) such as NeighborsMatch (Alon & Yahav, 2020), and GLoRa (Zhou et al., 2025), which introduces synthetic tasks that require identifying specific long paths in graphs. Several of these tasks bear similarities to tasks from the popular Long Range Arena (Tay et al., 2021) benchmark from the sequence literature; they frequently use very simple topologies (lines, rings, trees), are simple tasks with limited or no node features, and usually depend only on long-range interactions, such that a simple rewiring converts them into short-range tasks, Few synthetic tasks acknowledge that graph- graph-structured data and tasks are, by design, locally biased: task may involve long-range interactions, but will likely be primarily based on local ones. In this paper, we design synthetic experiments that better reflect this fact, requiring long-range interactions without neglecting short ones.
A.2. Empirical solutions to the long-range problem
Many methods have been proposed for addressing the long-range problem, often with the correlated goal of reducing over-squashing. Simple methods such as adding virtual or latent nodes (Gilmer et al., 2017; Southern et al., 2024; Hariri & Vandergheynst, 2024) or fully adjacent layers (Alon & Yahav, 2020) remove any meaningful distance between nodes by making them all connected within one or two hops, and are often quite effective. Graph rewiring approaches work in a similar fashion, improving the connectedness of nodes with additional edges, typically reducing the graph diameter, either as a pre-processing step (Topping et al., 2021; Gasteiger al., 2019; Deac et al., 2022; Arnaiz-Rodriguez et al., 2022: Black et al., 2023; Karhadkar al., 2022: Barbero et al., 2023) or acting on the computational graph within the model architecture (Abu-El-Haije et al., 2019; Abboud et al., 2022; Gutteridge et al., 2023; Bamberger et al., 2025; Finkelshtein et al., 2024). Rewiring has been shown to mitigate over-squashing, at the risk of diluting the benefit of the inductive bias afforded by graph topology. Global attention, such as that used by GTs (Vaswani et al., 2017: Wu et al., 2021; Rampášek et al., 2022), also throws away topology in favor of allowing nodes to interact directly, regardless of distance. Reflecting the inherently local nature of most graph tasks, the pest-performing GT architectures tend to be those that combine local with global/long-rang components (Ma et al., 2023; He et al., 2023). Increasingly, the relationship between vanishing gradients and the long-range problem is being studied, with inspiration taken from sequence literature: residual connections (Xu et al., 2018b; Gutteridge al., 2023), gating (Lukovnikov et al., 2020) and state-space models (Choi et al., 2024; Wang et al., 2024; Arroyo et al., 2025), treating the spatial dimension of graphs as analogous to the temporal dimension of sequences.
All of these methods have been argued to improve performance for long-range interactions based on empirical performance on benchmarks. Our work provides an additional and more principled validator by a means of formally measuring the range of a model trained on given task.
13

---

On Measuring Long-Range Interactions in Graph Neural Networks
B. LRGB dataset statisties
In this section we discuss some dataset statistics interest for VOCSUPERPIXELS and PEPTIDES, which can be found in Table 2. These statistics are taken from Dwivedi et al. (2022), but it should be noted that there exist disconnected graphs in the PEPTIDES datasets, which may affect their accuracy.
Table Comparison of VOCSUPERPIXELS and PEPTIDES datasets across various metrics. We report the average validation range over 4 seeds the final epoch. The graph statistics are reported according to Dwivedi al. (2022).
Metric
VOCSUPERPIXELL
PEPTIDES-FUNT
spd GCN Pg snd
2.32 + 0.098
1.04 0.030
GPS Pg
9.15 + 0.525
19.08 = 8.879
Avg. SPD
10.74 + 0.51
20.89 + 9.79
Avg. diameter
27.62 + 2.13 5.65
56.99 + 28.72
Avg. degree
2.04
We note that the range of GPS induces an SPD range approximately close to the average SPD over the graphs in the corresponding datasets. One can conjecture that this is the result of the attention scores being relatively uniform and struggle capture more complex and local structures within the graph. In the case of VOCSUPERPIXELS, GPS is the best-performing model, hence uniform attention may be desired for the downstream task. PEPTIDES-FUNT is the opposite; :spd
the poor performance of GPS and the similarity between SPD and Pg suggests that the attention mechanism is learning global averaging rather than complex pairwise interactions. This suggests that the model is simply not well-aligned to the task, and that local structures, which attention unable to capture, are more important for the downstream task. Further investigation of the influence distributions of these models required to shed light into the types of structures captured by a model when trained specific task.
C. Additional experimental results
In this Section we include additional experiments and ablations excluded from the main text, on synthetic datasets, on LRGB, CORA and the heterophilic datasets AMAZON-RATINGE and ROMAN-EMPIRE.
C.1. Additional synthetic experiments
Node-level range. In Section 6.1 we look at how well a linear GNN with varying depths can approximate the range of a synthetic task with known true range. We extend this analysis to include a non-linear GNN activation (GeLU) and a GNN with a virtual node. The architecture used for the results in Figure 4 a GCN (Kipf & Welling, 2017) with no activation plus skip connections. The hidden dimension of the GCN layers is 64. We use L2 loss and learning rate of 0.001.
Graph-level range. We repeat these ablations for the graph-level range in Figure 5 by adding mean pooling laye in addition to the virtual node. We only include the virtual node ablation here since the original experiment in Figure 5 already has GeLU activation at every layer to guarantee its ability to capture non-linear interactions. We report the results in Figure 9.
C.2. Additional LRGB experiments
In this section we include additional figures for resistance distance range experiments for LRGB, which were excluded from the main text due to the similarity of the figures between p and p.r. This similarity is especially pronounced for PEPTIDES, as the graphs are very similar to line graphs, for which SPD and resistance distance are equivalent.
C.3. CORA: a known short-range task
We primarily evaluate range for models trained on LRGB, as it is the de-facto long-range benchmark, but it is desirable to also analyze our range measure on a reference short-range task. We use CORA, and train a graph Transformer and a GCN to compare the range extremities for GNNs. Results are shown in Figure 12. We also show in Figure 13 that, for this task, the GT capable of learning similar range GCN, This refutes a possible interpretation of our experiments in Section 6.2:
14

---

On Measuring Long-Range Interactions in Graph Neural Networks
1.25
True A
Depth
1.00
1.25
True A
Depth
2.5
PC
1.00
Depth
2res 3
Depth
0
Depth
Depth
1.5
0.75
Dopth
Dopth
Depth
Depth
0.1
MSE
Depth
0.1
MSE
Depth
Depth
0.25
Depth
Depth
0.0
25 Epoch
50
Epoch
Depth
Depth
(a) (Left) Average range of GCN with GeLU activation for different depths on line graph for the k-Poo (--Power task for k = 5. Shaded area corresponds to min/max over 4 seeds. (Right) Range MSE at epoch 20 against number of GCN layers.
(b) (Left) Average range of GCN+VN for different depths line graph for the k-Power task for & = 5. Shaded area corresponds to min/max over 4 seeds. (Right) Range and MSE epoch 50 against number GCN layers.
Figure 8. Node-level range ablations synthetic k- d-Powerr task, further validating the range measure synthetic tasks. Figure 8a shows including oonliinerrtt has little effect on range, Figure 4, whereas adding virtual node Figure 8b induces more longer ranges initialization, but this decreases during training the model successfully learns the task.
True i
Depth
Depth 7
2.0
fres
Depth 6
Depth
Depth
1.0
Depth
Depth 2
Depth
10
20
30
40
Epoch
Figure 9. Average graph-level range of GCN+VN for different depths line graph for the k-Power task for k 5. Shaded area corresponds to min/max over seeds. Adding a virtual node produces similar result to the node-level case; the range is initially higher but trends lower, towards the true range.
that GT's are always long-range and are therefore unsuitable for providing information about the underlying range of the task. For these experiments both models hidden dimension of 64 and 2 layers, following the hyperparamettrrizatoons from Kipf& & Welling (2017).
C.4. AMAZON-RATING: and ROMAN-EMPIRES heterophilic tasks
We now investigate if there is a relationship between the long-range interaction problem and heterophilic tasks (Arnaiz- Rodríguez & Errica, 2025). We use range measure to evaluate models trained the heterophilic datasets AMAZON- RATINGS and ROMAN-EMPIRE (Platonov et al., 2023). Due to the size of these graphs, 24492 and 22662 nodes for AMAZON-RATINGE, and ROMAN-EMPIRE respectively, dense GTss are computationally infeasible. Hence, we test using local MPNN (GCN), local attention (GT; the same architecture referred to as a GT by Platonov et al. (2023)), and an MPNN with a virtual node (GCN+VN).
Figures 14 & 15 show that only the MPNN+VN is long-range (due to the drastic increase in receptive field) but yields zero performance benefit over standard GCN; far more important is how information is propagated. The local GT, i.e. an MPNN using Transformer-style attention, performs better for both tasks, while range is near-identical that of a GCN. This suggests that heterophily is not necessarily related to range, at least for these tasks.
15

---

On Measuring Long-Range Interactions in Graph Neural Networks
1.0
Model: F1
.451t.0
0.8
GT
.392:.00
GatedGCN
.378s.00
0.6
GINE
.275s.00
.245s.00
0.4
.185t.00 00
(4 seeds)
1
40 60 80
100
Epoch
Epoch
Figure 10. P5 for MPNN and GT models during training, evaluated on 500-graph subset of the validation split for VOCSUPERPIXELS We cut off after epochs as ranges have converged. relative range evolutions between models correlation with performance are very similar to the SPD case, reinforcing our earlier argument about the validity of VOCSUPERPIXELS This due to the topology VOCSUPERPIXELS
long-range benchmark.
However, we note that ranges are contracted below 1, even the GPS graphs (see Table 2), which have high average degree (see Table 2), meaning that resistance distance grows sub-linearly against Additionally, the range of GT matches that GINE and GCN+ at epoch which contrasts with the SPD range where GT considerably higher. This confirms the importance of the choice of distance metric, Standard deviation is over 4 model/sampling seeds.
Model:
AP
Model: MAEI
GCN+VN
.695s.01
GatedGCN
.2442.
10A
10a
GINE
.93:..0
GCN
.245..00
pres
GCN
.92:..0
GINE
.255..00
Ga GatedGCN
.681#.01
GCN-VN
.2422.00
GPS
.6542.01
GPS
.2522. 00
10a
GT
.5932.06
10a
GT
.933..02
(4 seeds)
(4 seeds)
20
80 100
20 40 60
80 100
Epoch
Epoch
Epoch
Epoch
(a) PEPTIDES-FUNC
(b) PEPTIDES-STRUCT
Figure 11. Ø for MPNN and GT models during training, evaluated on a 200-graph subset of the validation splits for PEPTIDES FUNC and PEPTIDES STRUCT. We off after 100 epochs ranges have converged. The negative correlation between performance and range may suggest that the PEPTIDES tasks are not as long-range as previously assumed. Standard deviation over model/sampling seeds. We log scaling the y-axis.
D. Additional experimental details
In this section we discuss some additional experimental details excluded from the main text.
D.1. Differentiability of models for PEPTIDES experiments
Node features for PEPTIDES are integer-valued as they represent atomic features. The At Atomnnodeer module (from GraphGym) used to encode these discrete values uses a torch. nn Embedding module directly. This process prohibits differentiating the model output with respect to the input features, which necessary the Jacobian calculation required compute the range. Hence, we replace the At omEncoder with Di Different iableAt omBncoder which pre- processes the PEPTIDES node features into one-hot floating point vectors. This produces a differentiable input and encoder equivalent to the existing At omEncoder and allows to compute the Jacobian for range measures.
D.2. Inefficiency of one-hot encoding for PEPTIDES
The standard At AtomEncoder from GraphGym used for PEPTIDES that one-hot encodes integer node features is extremely inefficient: it converts 9 integer-valued node features into a 174-dimensional one-hot vector, but over 80% of these are zero for all graphs in the PEPTIDES dataset. Only 31 one-hot features are required in practice.
As our range measure involves computing the Jacobian between input and output features, and the complex- ity of this computation scales with the input feature dimension, we reduce the one-hot encoding to for our Di fferent iabl eAtemEncoder This means our model architectures are slightly different than those reported by
16

---

On Measuring Long-Range Interactions in Graph Neural Networks
1.0
3.0
0.8
36 0.6
Model:
Acc
P6
2.0
Model: Acc
GCN
0.857
GCN
0.857
9.4
0.681
1.0
6.681
a
Epoch
Epoch
(a) Pg for CORA.
spd (b) Pg for CORA.
Figure 12. Range experiments CORA for GCN and GT. Pg of the GCN stays at ~1 hop and outperform the GT, we would expect from a known short-range task. We can see that in the initial epochs, the GT is able to learn to be more short-range after a high-range initialization; Figure 13.
3.0
2.5
Model:
Acc
GCN
0.857
15
GT 0.681
1.0
14
Negative Loss
Figure 13. Range against loss during training for the test split of CORA. Each point is labelled with its epoch. We cut off after 25 epochs because both models achieved their highest validation accuracy at epoch 25; after this, the GT overfits, as spiking range from epoch 25 to 50 in Figure 12 shows. We can see that, though the GT learns high range in the very early epochs, it then learns low range, around I hop, hefore overfits and accuracy drops.
Dwivedi et al. (2022); Tönshoff et al. (2023), as the encoding requires fewer parameters, but we found this to have minimal impact on model performance.
We report the updated parameter counts in Table 4.
D.3. Isolated nodes in PEPTIDES
We discovered that the PEPTIDES dataset contains graphs which are disconnected and may have isolated nodes. To the best of our knowledge, this is not reported anywhere in the literature. Though these graphs make up only ~1% of the dataset, still consider it an issue. Firstly, the existence of disconnected nodes means the reported results of average graph diameter are technically erroneous; this value would be infinite. Secondly, many methods propose computing metrics on graphs which assume connectivity such as distance metrics of SPD and effective resistance. Moreover, graph Transformer architectures will induce an edge between components the graph which could never interact in an MPNN, regardless of depth.
To address this, when computing our range measures on these graphs with graph Transformer architectures, we initialize distance values to zero and fill the distances by computing them on the respective connected components.
D.4. Jacobian sampling for range measure estimation
As mentioned main text, we sub-sample the Jacobian matrix order to provide computational speed-ups and avoid out-of-memory issues when computing range measures for real-world experiments. We achieve this by randomly sampling input/output nodes and input/output channels with given probabilities. The unselected node/channels sparsified Jacobian which results in computational advantage in both time and memory while producing an accurate approximation of the range. This is evident in our experiments, where we report multiple seeds across which the resulting range estimates have extremely low variance. We list sampling parameters used in our experiments in Table 3.
masked, producing
Sampling hy hyperparameters. Section we present the normalized range as an expectation over the influence distribution. When computing the node-level range for graph, Ag. this becomes an expectation over input/output nodes and input/output
17

---

On Measuring Long-Range Interactions in Graph Neural Networks
0.8
0.4
Model:
Model:
2dd
0.515
0.515
5.6
GCN
0.453
GCN
0.453
GCN+VN
0.453
GCN-VN 0.453
0.2
0
d
200
400
1500
200
430
800
500
1000
Epoch
Epoch
(a)
Figure 14. Range measures for the AMAZON RATINGS dataset. There is clear performance gain from using an attention based MPNN over convolution. GC induces slightly more long-range range interactions but offers no performance gain, suggesting that AMAZON- RATINGS may not be long-range.
Model:
Acc
Model:
Acc
GT
0.841
GT
0.841
GCN
0.453
GCN
0.453
GCN+VN
0.453
GCN-VN
8.453
Epoch
Epoch
Pg
(b) sppd
Figure 15. Range measures for the convolution. GCN+VN induces long-range interactions but offers no performance gain, suggesting that ROMAN-EMPIC may not be long-range.
dataset. There is a clear performance gain from using attention basdd MPNN over
channels. Using sub-sampling of these allows us approximate this expectation.
If assign the probabilities to be mode-in node-out pehannel-in ychannel-out then reduce the Jacobian size by factor of mode-in x pode-out x pchamael-in x yhhannet-out
We construct a binary mask for each component m E {0,1)" 1)" such that each entry is independently sampled from a Bernoulli distribution with probability p. i.e., Σ m; = p.
We apply the GNN model to the masked input to compute the full output, which is subsequently reduced using the output mask. This selective computation results in a reduced Jacobian and computational graph, offering protection against out-of-memory errors and yielding significant efficiency gains.
Additionally, we found that graphs with n > ~55 can exceed the memory constraints of an A10 NVIDIA GPU (24GB). Hence, we set upper bound of max nodes 256. We also set lower bound of min nodes 16, to ensure we don't under-sample smaller graphs.
D.5. Computational Resources
Preprocessing, training and range calculations were done on in-house CPUs and GPUs. All experiments were feasible and primarily performed on NVIDIA A10s. Some experiments were performed on NVIDIA H100s.
18

---

On Measuring Lang-Range Interactions in Graph Neural Networks
Table Sampling probability hyperparameters used for range experiments. We use probahility of 1.0 for input nodes for experiments found that it introduced bias to the range and did not reduce compute requirements.
Dataset
Input Nodes
Output Nodes
Input Channels
Output Channels
VOCSUPERPIXELS
1.0
0.5
0.5
0.5
PEPTIDES-FUNC
1.0
0.5
0.5
0.5
PEPTIDES-STRUCE
1.0
0.5
0.5
0.5
AMAZON-RATINGS
1.0
0.01
1.0
0.8
ROMAN-EMPIRE
1.0
0.01
1.0
1.0
CORA
1.0
0.2
0.2
1.0
19

---

On Measuring Long- Range Interactions in Graph Neural Networks
Table Hyperparameters LRGB experiments in Section 6.2.2. The #Param. row (b) original parameter count from
Tönshoff et al. (2023) in parentheses alongside our decreased parameter account due to efficient one-hot encodings (see Appendix D).
(a) Hyperparameters for PEPTIDES-FUNG experiments
GCN
GINE
GatedGCN
GPS
GCN+VN
GT
Ir
0.001
0.001
0.001
0.001
0.001
0.001
dropout
0.1
0.1
0.1
0.1
0.1
0.1
#layers
6
8
10
6
6
6
hidden dim.
235
160
95
76
235
76
head depth
3
2
PE/SE
RWSE
RWSE
RWSE
LapPE
RSWE
LapPE
batch size
200
200
200
200
200
200
#epochs
250
250
250
250
250
250
norm
BatchNorm
BatchNorm
MPNN
GatedGCN
GCN
#Param.
456k (486k)
472k (491k)
483k (493k)
470k (479k)
456k
464k
(b) Hyperparameters for PEPTIDES STRUCT experiments
GCN
GINE
GatedGCN
GPS
GCN+VN
GT
Ir
0.001
0.001
0.001
0,001
0.001
0.001
dropout
0.1
0.1
0.1
0.1
0.1
0.1
#layers
6
10
8
hidden dim.
235
145
100
64
235
head depth
3
2
PE/SE
LapPE
LapPE
LapPE
LapPE
LapPE
LapPE
batch size
200
200
200
200
200
200
#epochs
250
250
250
250
250
250
norm
BatchNorm GatedGCN
BatchNorm
MPNN
GCN
#Param.
457k (488k)
473k (492k)
433k (445k)
445k (452k)
457k
472k
(c) Hyperparameters for VOCSUPPERPIXELS experiments
GCN
GINE
GatedGCN
GPS
GCN+VN
GT
0.001
0.001
0.001
0.001
0.001
0.001
dropout
0.0
0.2
0.2
0.3
0.0
0.1
#layers
10
10
10
8
10
8
hidden dim.
200
145
95
68
200
84
head depth
3
3
3
2
3
2
PR/SE
RWSE
none
none
LapPE
RWSE
LapPE
batch size
50
50
50
50
50
50
#epochs
200
200
200
200
200
200
norm
BatchNorm GatedGCN 501k
BatchNorm
MPNN
GCN
#Param.
490k
450k
473k
490k
471k
20


Reviews:
[{"review_id": "jPMlfNV56C", "reviewer": "Reviewer_T8Ph", "summary": "This paper introduces a formal measure for evaluating long-range interactions in Graph Neural Networks (GNNs), addressing the limitations of existing empirical benchmarks like LRGB, which lack theoretical grounding. The proposed measure quantifies a model’s ability to capture long-range dependencies, validated through synthetic experiments and applied to assess common benchmarks. This work provides a principled framework for studying and improving long-range interactions in GNNs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and for appreciating our contributions. We address their concerns below. As suggested, we have performed additional experiments for heterophilous tasks, as well as on Cora, virtual node and activation function ablations for our Fig. 4 synthetic task, and a VN and GT ablation for LRGB. All additional experiments will be included in the final paper. We discuss these results in the relevant reviewer responses; the figures are included in a pdf here: https://fuchsia-lina-52.tiiny.site/\n\n>*“It is not clear why Jacobian is used for node-level task while Hessian is used for graph-level task.”*\n\nBoth our node- and graph-level range measures require a term that captures pairwise interactions between nodes. For node-level tasks, the $(i,j)$-th element of the Jacobian represents the sensitivity of node $i$’s output features to node $j$’s input features. For graph-level tasks with a single output, the Jacobian is a vector and so does not contain pairwise node information. The Hessian, on the other hand, is an $N\\times N$ matrix which does encode this information. Specifically, its elements denote the sensitivity of the output to each pair of input node features. In other words, for node-level tasks we use the first-order Taylor approximation, and for graph-level, since the Jacobian is unsuitable, we use the second-order, the minimal-order approximation to obtain any pairwise information between nodes.\n\n>*“'...solving a task' is not clearly defined … on real-world datasets, the authors evaluate four models, but none achieve perfect performance.”*\n\nWe thank the reviewer for raising this interesting point, which we will clarify in the final version. We informally define a task as ‘solved’ when validation loss of a model approaches zero; Fig. 4 demonstrates this empirically, showing that as loss decreases, the model range approaches the known range of a synthetic task. Theoretical results linking the accuracy of the estimated range with validation error are an important direction which we reserve for future work.\n\nThe reviewer is correct that, in our real-world experiments, models do not achieve perfect performance, meaning that the resulting range measures are only approximations of the true range of the underlying task. In the case of real-world tasks, the range is not just an approximation of the task range, but is also the true range of a model trained on that task. It is not our intention that a single range score be used to draw conclusions about a task. Instead, we infer conclusions about tasks by an examination of both the range and performance across different models: if range and performance correlate positively, it suggests a more long-range task, whereas no correlation suggests a task may be less long-range. In this way, our measure can serve as a practical tool for evaluating tasks for which no existing models can achieve perfect performance (i.e. all non-trivial tasks).\n\n>*“It would be valuable to empirically analyze the range of heterophilous tasks…”*\n\nWe thank the reviewer for this suggestion. While we agree that it is worth investigating the relationship between label heterophily and long-range dependency, we are not aware of work explicitly making this connection. That said, we follow the reviewer’s suggestion and report the range during training for Roman-Empire and Amazon-Ratings in Figs. A1-2 in the linked pdf, taking hyper-parameterizations from [1]. We find that GCN and GT (which perform local convolutional and attentional message passing respectively) converge at a range of ~1 hop or lower for both tasks, but GT performs better, suggesting that range is a less important factor for these tasks than how information is propagated through the graph. This is further supported by the lack of correlation observed between range and performance between GCN and GCN+VN, especially for Roman-Empire.\n\n>*“The proposed method is based on influence scores… I suggest the authors discuss how this concept aligns with related work in the broader literature”*\n\nThe suggested reference is indeed an important prior work. [2] introduced the notion of influence function to study the importance of certain training points on a model’s prediction, from which [3] adapted influence functions to the context of graph learning to study and improve information propagation in GNNs. A discussion of the paper along these lines will be included in the final version. We thank the reviewer for this suggestion, and will make sure to appropriately connect our work to the relevant broader literature. \n\n---\nWe thank the reviewer again for their feedback. We are happy to address any further concerns, and would be grateful if the reviewer would consider raising their score in light of our responses and additional experiments.\n\n[1] Platonov et al. (2023) https://arxiv.org/abs/2302.11640\n\n[2] Koh et al. (2017) https://arxiv.org/abs/1703.04730\n\n[3] Xu et al. (2018) https://arxiv.org/abs/1806.03536", "claims_and_evidence": "- It is not clear why Jacobian is used for node-level task while Hessian is used for graph-level task. Could you please clarify?", "methods_and_evaluation_criteria": "The authors claim that the range of a trained model that solves a task approximates the range of the underlying task. However, \"solving a task\" is not clearly defined. In Section 6.2, where experiments are conducted on real-world datasets, the authors evaluate four models, but none achieve perfect performance. This raises an important question: Is the model failing to capture long-range interactions, or does the task itself not require them? I suggest the authors refine their claim to be more rigorous and explicitly clarify the criteria for determining when a task is truly \"solved.\"", "theoretical_claims": "I did not check the proofs comprehensively.", "experimental_designs_or_analyses": "Heterophilous datasets are known to benefit from long-range interactions. It would be valuable to empirically analyze the range of heterophilous tasks to better understand their dependence on long-range dependencies. I suggest the authors examine datasets such as Roman-Empire and Amazon-Ratings [1] to provide deeper insights into how their proposed measure applies to heterophilous settings.\n\n[1] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. arXiv preprint arXiv:2302.11640.", "relation_to_broader_scientific_literature": "The proposed method is based on influence scores and adapts them to measure the influence from nodes at different ranges. I suggest the authors discuss how this concept aligns with related work in the broader literature, such as [1], to provide readers with a more comprehensive understanding of existing approaches and how their method fits within this context.\n\n[1] Koh, P. W., & Liang, P. (2017, July). Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR.", "essential_references_not_discussed": "N.A", "other_strengths_and_weaknesses": "The adaptation of influence scores to define a range measure is an interesting approach. Additionally, the findings on LRGB, particularly that existing methods may not be effectively learning from long-range interactions is interesting.", "other_comments_or_suggestions": "## update after rebuttal\n\nI have read the rebuttal and would like to keep my score", "questions_for_authors": "Why use Jacobian for node-level task and Hessian for graph-level task? Can you explain in more details for better clarity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rENY9w1Wlh", "reviewer": "Reviewer_7Dgb", "summary": "The paper works in the area of long-range dependencies for graph neural networks. Its main contribution is to define a new metric to measure the range of a task. This metric can also be applied to GNNs that are trained on a task, approximating the true range of the task. Experiments on the LRGB datasets indicate that PASCAL-VOC is indeed a long-range task while the peptides tasks are not.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback, and for appreciating the novelty of our contribution and its significance as an evaluation tool for GNNs and graph tasks. We address their concerns below. As suggested, we have performed additional experiments for GCN and GT on Cora (as a known short-range task to compare with LRGB), as well as virtual node and activation function ablations for our synthetic task corresponding to Fig. 4, and a VN and pure Transformer ablation for LRGB. We also performed additional experiments, as suggested by other reviewers, for the heterophilous tasks Roman-Empire and Amazon-Ratings for a GCN and GT. All additional experiments will be included in the final paper. We discuss these results in the relevant reviewer responses; the figures are compiled in a pdf here: https://fuchsia-lina-52.tiiny.site/\n\n>*“Q1) Does Figure 4 work similarly for GCN with activation functions and possibly VN?”*\n\nWe have extended the synthetic experiment to produce the equivalent of Fig. 4 for both a GCN with GeLU activation, and a GCN with a VN. We report the results in the linked pdf, Figs. A8-9. We notice that adding a nonlinearity does not considerably change the results. Adding a VN, on the other hand, does: where Fig. 4 showed models with an initial negative range bias before converging during training towards the true range from *below*, the addition of a VN appears to induce a positive bias, so models converge to the true range from above — though they do still converge, i.e. the trained model range still approximates the true task range.\n\n>*“Q2) What happens to fig 4/5 for GPS?”*\n\nWe performed this experiment and found that the GPS architecture is not well-aligned with this synthetic task: it trains irregularly and attains poor performance. As a result, there is no clear interpretation of the range of the model on this task. This points to the importance of inferring conclusions about tasks by an examination of both the range and performance across different models (see further discussion below). An analysis of the relationship between performance and range of different Transformer architectures on different tasks is an interesting direction which we leave for future work.\n\n>*“Q3) Is there a way to exclude the alternative claim 'GPS is always more long-range, even if it is not needed' which could also explain the figures”*\n\nWe agree with the reviewer that high range scores for GPS are not sufficient, by themselves, to indicate that a task is long-range. This is clear from Figs. 6-7 in the paper, from which we conclude that the Peptides tasks are not long-range while VOCSuperpixels (in relative terms) is, despite very similar, high range scores for GPS. We base our claim about the long-rangedness of VOC on two factors:\n\n(i) that the *MPNNs*, rather than GPS, have higher relative range (as the reviewer points out, MPNNs are long-range *if needed*, suggesting that for VOC, longer range is necessary);\n\n(ii) that the range gap between GPS and MPNNs is accompanied by a performance gap, indicating that models with higher range are better suited to the task.\n\nNeither of these is the case for Peptides. To summarise, it may be that GPS will have a high range for a task when it is not required, but by comparing *relative range* as well as *relative performance over multiple models*, we can make an assessment about the underlying task.\n\nTo address the second part of the comment, while we do find that GPS and other GTs are biased towards higher range, and often are long-range when it is not needed, they can learn to be short range. See Fig. A4, in which we plot range against validation loss for the first 25 epochs of training a GCN and GT on Cora, a known short-range task. We see that the GT grows rapidly long-range in early epochs, but quickly learns to be short-range until it achieves its maximum validation accuracy at epoch 25 (after which it overfits). This excludes the alternative claim.\n\nWe follow the reviewer’s suggestions for additional experiments to better validate our claims. In addition to Cora, we perform experiments for a GT (GPS without MPNN component) and GCN with a virtual node for the three LRGB tasks; see Figs. A5-7. The results support our findings: GT performs very similarly to GPS, and +VN increases range, with a corresponding increase in performance for VOC but not for Peptides, consistent with our conclusions about each task’s range.\n\n>*“k-Power: is this with or without self-loops?”*\n\nWithout; we will clarify this in the final version.\n\n---\nWe thank the reviewer again for their positive and useful feedback, as well as for their other detailed suggestions, which will be added for the final version. We are happy to address any further concerns. Given the reviewer’s comments about the novelty and utility of our work, and the significant additional experiments we have provided to strengthen the final version, we would be grateful if the reviewer would consider raising their score.", "claims_and_evidence": "Almost all claims are thoroughly supported by evidence. Only the claim that high values in GPS indicate higher long-rangedness of the problem is not properly validated as it could very well be that GPS is always long-ranged (even if it does not need to) while MPNNs are only long-ranged if needed. While I generally agree with the claim, I believe that GPS behaves oddly in the experiments and should thus be checked further.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluations make a lot of sense. It would still be nice to compare to some (known) short-range datasets to see the difference more pronounced.", "theoretical_claims": "The proofs are extremely straightforward and easy to read, and even included in the main paper. I find this very refreshing and very positive.", "experimental_designs_or_analyses": "I did not run the code myself. The experimental design mostly makes sense, except that I would like a few additional experiments to strengthen the claims about the LRGB datasets. It would also be nice to see whether Figure 4 would look the same for networks that do use activation functions and maybe even virtual nodes.", "relation_to_broader_scientific_literature": "The new range metric is novel and a great addition to the arsenal that we have to evaluate what a GNN actually does as well as to evaluate what a graph task actually requires.", "essential_references_not_discussed": "I would have expected to find Gilmer et al as the citation for virtual nodes and not two 2024 papers. The paper is cited, but in an unexpected context (for chemistry, not for virtual nodes).", "other_strengths_and_weaknesses": "The paper is really well-written and easy to read! It is also thoroughly proofread which I greatly appreciate.", "other_comments_or_suggestions": "p1c2: I would have expected virtual nodes to be discussed here as well as it is an effective way to enable long-range interactions.\np2c2: I would have liked a bit more intuition of when the range should be large and when it should be small. And I found the example given there not super helpful as it is quite technical without having an idea what we actually want to achieve, but that might be personal.\np3c2: It would be nice to state more explicitly that the \"Range of a GNN\" is the effective range of what the trained GNN computes (and not something that only depends on the architecture)\np3c2, above eq1: I believe that the connection between Jacobian and best linear approximation is not universally known. (At least I had to stop there for a moment while reading). Since you later mention Taylor anyway, it might be a good idea to mention it here as well since its the first-order Taylor term.\np4c1: It would be nice to mention in which context the influence distribution has been defined (as it is not another way of defining range)\np5c1 k-Power: is this with or without self-loops (I would guess without, but it would be nice to be explicit)\n\nFigure 6/7: Since the range is not that large, it might be nice to write the values as 0.3, 0.6, 1, 10 etc instead of the scientific notation which is a lot slower to parse.\n\np4c1 L187: reason -> reasons\np4c2 L209: Erdős (with that weird o) and L213 increase->increases\np5c1 L250: Figure 2 -> Figure 3. Also Figure 3 has left/right which should be mentioned in the paragraph.\nFigure 3 caption: _a_ linear increase ... and _a_ sublinear increase", "questions_for_authors": "My main questions are about the experiments and resulting claims which are already in the review above, but I try to concisely put them here too:\nQ1) Does Figure 4 work similarly for GCN with activation functions and possibly VN? \nQ2) what happens to fig 4/5 for GPS? Will that behave oddly?\nQ3) Is there a way to exclude the alternative claim \"GPS is always more long-range, even if it is not needed\" which could also explain the figures. A possible way to check that would be using just a transformer without message passing and/or to run everything on one or two datasets that are known to be short-range (e.g. Cora). Effectively: while I agree with the claim, I think using GPS here does not help without additional experiments for e.g. virtual nodes and pure transformers, as well as \"baseline\" results of GPS on known short-range tasks for calibration. Would it be possible to add those experiments to make the claim stronger?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yu9s2WK7q3", "reviewer": "Reviewer_ztSX", "summary": "The Long Range Graph Benchmark (LRGB) is a widely adopted tool for evaluating the long-range capabilities of frameworks in long-range graph tasks. This paper identifies its limitations and introduces a formal range measure for operators on graphs, encompassing both node-level and graph-level tasks. Furthermore, in light of the current simplicity of synthetic tasks (which predominantly rely on long-range interactions) ,this paper propose a redesign of graph synthesis tasks. Experimental results demonstrate that the method proposed in this paper provides a better understanding of long-range task in graph machine learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and recognition of the practical significance and credibility of our work. We address the reviewer’s concerns below. We also note that, following suggestions from other reviewers, we have performed additional experiments for GCN and GT on Cora (as a known short-range dataset to compare with LRGB), virtual node and activation function ablations for our synthetic task corresponding to Fig. 4, a VN and pure Transformer ablation for LRGB, and experiments on the heterophilous tasks Roman-Empire and Amazon-Ratings for a GCN and GT. All additional experiments will be included in the final paper. We discuss these results in the relevant reviewer responses, and would be grateful if the reviewer would consider reading these responses and examining the figures, which are compiled in a pdf at the following link: https://fuchsia-lina-52.tiiny.site/\n\n\n>*“This paper primarily introduces enhancements to the previous graph long-range evaluation tool, LRGB, addressing its limitations…there are concerns regarding the true extent and scope of its impact”*\n\nWe thank the reviewer for their feedback. While assessment of LRGB is indeed one of the aims of our work, we would like to politely emphasise that our contributions are far more general and go significantly beyond testing the appropriateness of an existing benchmark.\nFirstly, our measure can be applied to any model trained on any task; it not only enhances the usefulness of LRGB in assessing range but *any graph learning benchmark* — for example, see our additional experiments, in which we assess the range of Cora as well as two heterophilous tasks. \n\nSecondly, LRGB is purely an empirical evaluation method based on performance gap. Our range measure provides a theoretically robust range measurement tool for *any model trained on any task* that can be considered in addition to (or in the absence of) performance gap. We believe this is a significant theoretical contribution that paves the way for further analysis in this direction.\n\nThirdly, while we use and motivate our range measure only for graph ML tasks, as defined it is a general measure applicable to any operator (including any neural network), and for any data structure for which one can define a distance metric. As a result our method can be applied beyond graphs to the general ML setting, as has been done with other works such as [1]. One example which we leave for future work is a theory-driven evaluation of long-context issues observed for Transformers operating on sequence data, such as is observed with the ‘lost in the middle’ problem [2].\n\n---\n\nWe appreciate the reviewer’s thoughtful feedback and hope that our clarifications have effectively conveyed the broader impact and significance of our work. We are, of course, happy to address any further concerns if the reviewer wishes to elaborate on them. Given the reviewer’s positive comments about our work, our above clarifications, and the significant additional experiments we have provided to strengthen the final version, we would be grateful if the reviewer would consider raising their score.\n\n[1] Barbero, Federico, et al. \"Transformers need glasses! information over-squashing in language tasks.\" Advances in Neural Information Processing Systems 37 (2024): 98111-98142. https://arxiv.org/abs/2406.04267\n\n[2] Liu, Nelson F., et al. \"Lost in the middle: How language models use long contexts.\" Transactions of the Association for Computational Linguistics 12 (2024): 157-173. https://arxiv.org/abs/2307.03172", "claims_and_evidence": "The claims in the material are supported by clear and compelling evidence.", "methods_and_evaluation_criteria": "The graph long-range evaluation metric proposed in this paper has been validated on both synthetic and real-world datasets, demonstrating its practical significance.", "theoretical_claims": "This paper provides clear definitions and analyses of evaluation metrics at the graph level and node level, the scope of their influence, and relevant examples. The corresponding theoretical claims are largely accurate.", "experimental_designs_or_analyses": "The experimental design is conducted on both synthetic and real-world datasets, and the validity of the proposed framework is demonstrated through theoretical analysis and foundational experiments, making the findings convincing.", "relation_to_broader_scientific_literature": "This paper primarily proposes improvements to the previous graph long-range evaluation tool, LRGB, addressing its limitations. It represents a progressive advancement in the field.", "essential_references_not_discussed": "This paper primarily introduces enhancements to the previous graph long-range evaluation tool, LRGB, addressing its limitations. It constitutes a progressive advancement in the field.", "other_strengths_and_weaknesses": "Strengths:\n(1)\tThe paper is written clearly, and the problem is described effectively.\n(2)\tThe theoretical foundation is well-established, and the theoretical and experimental validations are comprehensive and convincing.\n\nWeaknesses:\n(1)\tThis paper primarily proposes a new method for evaluating long-range dependencies in graphs. However, there are concerns regarding the true extent and scope of its impact.", "other_comments_or_suggestions": "## Update for Rebuttal\nI confirm that I have read the author response, I will keep my score", "questions_for_authors": "refer to weakness", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of evaluating long-range dependencies in Graph Neural Networks (GNNs) by introducing a formal metric to measure the range of tasks and models. The proposed metric overcomes limitations of existing empirical benchmarks, such as the Long Range Graph Benchmark (LRGB), with a better theoretical grounding. Using synthetic datasets and real-world tasks like PASCAL-VOC and peptides tasks, the work shows the effectiveness of the new metric in quantifying a model's ability to capture long-range dependencies. The work provides a framework for studying and improving long-range interactions in GNNs, offering a better understanding of long-range tasks in graph machine learning and paving the way for better evaluations and GNN improvements.

The reviewers were generally positive. I support acceptance.
Decision: Accept (poster)