On Measuring Long-Range Interactions in Graph Neural Networks

1. Introduction

• MPNNs struggle when tasks depend on distant-node interactions, with over-smoothing, vanishing gradients, and over-squashing among the cited difficulties.These limitations hinder modeling tasks requiring global or long-range interactions.Source: §1 · p. 1
• Common ways to address these difficulties reduce graph distance through rewiring or architectural changes, but their long-range claims often rely on benchmark performance.Strategies include static rewiring, virtual or latent nodes, multi-hop message passing, and global attention.Source: §1 · p. 1
• Many synthetic tasks isolate long-range interactions, although graph tasks are usually locally biased and should prioritize local interactions too.A simple rewiring can turn tasks that depend only on long-range interactions into short-range tasks.Source: §1 · p. 1
• LRGB uses graph size, diameter, and domain intuition to characterize long-rangedness, but these are necessary rather than sufficient conditions.Sensitivity to hyperparameter tuning has also raised questions about how long-range its tasks are.Source: §1 · p. 1
• The paper formalizes long-range interactions in graph tasks from first principles rather than relying on empirical heuristics.This provides a systematic basis for analyzing tasks and architectures.Source: §1 · p. 2
• It introduces quantitative GNN range measures for node- and graph-level tasks, with evaluation at node, graph, and dataset granularities.The measures apply in inductive and transductive settings.Source: §1 · p. 2
• The measures are validated with synthetic experiments and applied to assess the LRGB benchmark.Source: §1 · p. 2

2. Background

• Xu et al. (2018b) measure an output node’s sensitivity to an input node with the sum of absolute Jacobian values, adapting influence functions to graphs.The paper derives a family of range measures from first principles; the influence-based measure of Liang et al. (2025) is one specific instantiation.Source: §2 · p. 2
• Alon & Yahav (2020) define problem radius as the minimum number of hops needed to solve a task, approximated by tuning MPNN depth.They also introduce over-squashing, described here as closely linked to long-range interactions.Source: §2 · p. 2
• Prior sensitivity analyses connect poorly connected nodes with small influence scores, while a Hessian-based measure studies pairwise feature mixing rather than range.The paper contrasts its task-general application to trained models with work computed for known tasks.Source: §2 · p. 2
• The paper represents graphs as undirected node and edge sets, defines node features and shortest-path neighborhoods, and describes GNN layers as sequential node-feature updates.Node-level tasks predict for each node; graph-level tasks apply pooling to produce a graph output.Source: §2 · pp. 2–3

3. Formalizing the range of a node-level task

• The proposed range quantifies how strongly distant nodes interact for a task, GNN, or more general graph operator.It is derived from first principles as the unique measure satisfying a set of desired properties.Source: §3 · p. 3
• A node-level task maps input signal X to output Y = F(X); for the derivation, the paper restricts attention to linear maps and illustrates an interaction from v to u.The illustrative map copies v’s input value to u’s output and sets other output values to zero.Source: §3 · p. 3
• Range is defined at each node because a task may be long-range around one node and short-range around another.The measure assumes a graph metric; the experiments focus on shortest-path and resistance distance.Source: §3 · p. 3

3.1. Derivation of node-level range

• The desired properties require locality, assigning zero range to interactions not received by u, and unit interaction, assigning a single interaction its graph distance.Additivity and homogeneity require disjoint interaction ranges to sum and interaction scaling to scale range proportionally; disjoint maps do not capture the same node pairs.Source: §3.1 · p. 3
• Those properties uniquely determine the unnormalized node range for a linear task on a graph with a specified metric.The proof decomposes a linear map into elementary node-pair interactions and uses locality and additivity to derive the range.Source: §3.1 · pp. 3–4
• The normalized range weights disjoint interactions by their strengths, avoiding a sum that grows merely because many short-range interactions are present.The paper establishes a unique normalized range satisfying locality, unit interaction, and the normalized disjoint-interaction property.Source: §3.1 · p. 4
• For differentiable GNNs, range is computed from the Jacobian as the best linear approximation; the normalized measure extends to multiple channels as an average distance over interactions.Its influence-distribution interpretation also supports fast stochastic approximations, which the experiments favor.Source: §3.1 · p. 4
• A hierarchy averages node range over nodes in a graph and then over graphs in a dataset, supporting both transductive and inductive tasks.For node-level tasks, Table 1 uses Jacobian-based ρ; for graph-level tasks, it uses Hessian-based η because the Jacobian does not provide pairwise interaction terms.Source: §3.1 · p. 4, Table 1 · p. 4

4. Range of a graph-level task

• The Jacobian captures each node’s first-order sensitivity, but the Hessian captures pairwise interactions in graph-level tasks.The Hessian corresponds to the second-order Taylor term, making it suitable for measuring pairwise interactions.Source: §4 · p. 5
• The graph-level range extends to multiple input and output channels as an expectation over channel interactions, measuring mixing between node pairs.The normalized measure also generalizes to higher dimensions and enables fast stochastic approximations.Source: §4 · p. 5
• Graph-level range is defined per node, then averaged over nodes in a graph and over graphs in a dataset.This hierarchy supports both transductive and inductive tasks.Source: §4 · p. 5

5.1. Design of synthetic tasks

• Pairwise graph tasks combine a distance-scaled interaction function with aggregation, with a further aggregation producing graph-level tasks.The framework supports designing tasks with varying range.Source: §5.1 · p. 5

5.2. Empirical examples

• Sparse graph topologies with larger diameters yield greater range than denser counterparts, and range generally increases with k.The comparison covers line graphs, Erdős–Rényi graphs, and stochastic block models; Figure 2 plots node- and graph-level task ranges across these distributions.Source: Figure 2 · p. 5, §5.2 · p. 6
• On grid graphs, range increases with k in the order k-Dirac > k-Rectangle > k-Power; Dirac concentrates influence at the k-hop, while Power decays with distance.The figure reports linear growth for k-Dirac and k-Rectangle and sublinear growth for k-Power.Source: §5.2 · p. 6, Figure 3 · p. 6

5.3. Analytic node-level examples

• A node-wise task has range zero, while for the k-hop squared-difference task with i.i.d. Gaussian features, range increases with k.The expected normalized range increases strictly when the next-hop neighborhood is nonempty.Source: §5.3 · p. 6

5.4. Analytic graph-level examples

• A graph-level sum of node-wise functions with no mixing has zero range, whereas the squared-difference interaction task’s range increases with k.The latter task averages squared differences between features of nodes within the k-hop neighborhood.Source: §5.4 · pp. 6–7

6.1. Do GNNs approximate the true range of a task?

• For the synthetic node-level 5-hop task, deeper GCNs approach the true task range and achieve lower MSE, supporting trained-model range as a proxy under ideal conditions.The experiments use linear GCNs with residual connections on a line graph; the section argues convergence occurs as validation error approaches zero.Source: §6.1 · p. 7
• For the graph-level synthetic task, deeper models tend toward the true task range, and pre-pooling node-level range correlates with graph-level range.The task uses squared differences followed by node averaging and GeLU activations.Source: §6.1 · p. 7, Figure 5 · p. 7

6.2. Validating real-world benchmarks

• Real-world model range is not an exact task-range estimate because models have nonzero error and may be biased toward particular ranges; performance–range correlation across architectures is used as a heuristic.Tasks where better-performing models tend to exhibit longer range are plausibly long-range, while performance saturation at low range suggests local interactions dominate.Source: §6 · p. 7, §6.2 · p. 8

6.2.1. EXPERIMENTAL SETUP

• The LRGB evaluation covers VOCSUPERPIXELS and both PEPTIDES tasks across MPNNs, graph transformers, and GCN+VN, estimating graph-task range from pre-pooling node representations and sampled Jacobians.The setup uses validation subsets to reduce computation and reports validation results because range estimates were highly consistent across splits.Source: §6.2.1 · p. 8

6.2.2. RESULTS

• On VOCSUPERPIXELS, MPNNs reach ∼2–3 hops while GPS and GT reach around ∼10, and range correlates positively with performance, suggesting a long-range task.The authors attribute MPNN underperformance to limited long-range capture, potentially involving under-reaching, over-smoothing, and over-squashing.Source: §6.2.2 · pp. 8–9
• On PEPTIDES-FUNC and PEPTIDES-STRUCT, GT and GPS perform worst while MPNNs perform similarly well; higher range does not improve performance, suggesting long-range capacity is unnecessary.GCN+VN has higher range than MPNNs but yields minimal or no performance gains.Source: §6.2.2 · p. 9

7. Discussion

• Range measures are proposed as quantitative tools for understanding long-range graph learning and assessing architectures and benchmark tasks beyond performance metrics.The paper also notes that the measures can apply to geometric domains beyond graph learning when a notion of distance is available.Source: §7 · p. 9
• Future work will compare Hessian-based range measures with node-level range on real-world benchmarks and study how common architectural components affect range.The planned work includes empirical and theoretical analysis of fully connected layers, rewiring, residual connections, and positional or structural encodings.Source: §7 · p. 9

A. Detailed discussion of related work

• The related-work discussion reviews synthetic and real-world long-range benchmarks, proposed methods, and how their claims are validated.Source: A. Detailed discussion of related work · p. 13

A.1. Long-range benchmarks

• LRGB uses graph size or diameter, graph-level mixing, and domain intuition to motivate task long-rangedness, but hyperparameter tuning has narrowed its reported performance gap and renewed questions about that designation.Despite these questions, LRGB remains a de-facto validator of long-range performance.Source: §A.1 · p. 13
• Many synthetic benchmarks use simple topologies and tasks that depend only on long-range interactions, so rewiring can make them short-range; the paper instead designs tasks that retain local bias while requiring long-range interactions.Examples in prior work include RingTransfer, color connectivity, tree-search tasks, and GLoRa.Source: §A.1 · p. 13

A.2. Empirical solutions to the long-range problem

• Methods including virtual nodes, fully adjacent layers, rewiring, and global attention reduce effective distances, while rewiring can dilute the inductive bias of graph topology.The review notes that strong graph Transformers tend to combine local and global or long-range components.Source: §A.2 · p. 13
• Because existing methods are often judged by benchmark performance, the paper adds a formal measure of the range of a model trained on a task as another validator.Source: §A.2 · p. 13

B. LRGB dataset statistics

• Disconnected graphs in PEPTIDES may affect dataset accuracy, and the accompanying table compares VOCSUPERPIXELS and PEPTIDES across metrics.The statistics are reported according to Dwivedi et al. (2022); the supplied table passage gives no cell values.Source: B. LRGB dataset statistics · p. 14, Table 2 · p. 14
• GPS range is approximately close to average SPD on both datasets; on VOCSUPERPIXELS, GPS performs best, whereas on PEPTIDES-FUNC its poor performance and range pattern suggest global averaging may not fit the task's local structures.The authors conjecture that relatively uniform attention struggles to capture more complex local structures; they call for further investigation of model influence distributions.Source: B. LRGB dataset statistics · p. 14

C. Additional experimental results

• The additional-results appendix covers experiments on synthetic datasets, LRGB, CORA, and the AMAZON-RATINGS and ROMAN-EMPIRE heterophilic datasets.Source: C. Additional experimental results · p. 14

C.1. Additional synthetic experiments

• On the synthetic k-Power task, adding a virtual node raises range initially but range decreases during training as the model learns the task; non-linearity has little effect on node-level range.For graph-level range, the virtual-node model likewise starts higher and trends down toward the task's true range.Source: §C.1 · p. 14

C.2. Additional LRGB experiments

• Additional LRGB resistance-distance range figures were omitted from the main text because they resemble the SPD figures, especially for PEPTIDES, whose graphs are similar to line graphs where the distances are equivalent.Source: §C.2 · p. 14

C.3. CORA: a known short-range task

• On CORA, a graph Transformer can learn a range similar to a GCN, countering the interpretation that graph Transformers are always long-range and unsuitable for indicating task range.Both models use 64 hidden dimensions and two layers.Source: §C.3 · pp. 14–15

• On the synthetic k-Power task, a virtual node initially increases node-level range, which decreases during training as the model learns the task; adding non-linearity has little effect.Source: Figure 8 · p. 15
• For graph-level range on the k-Power line graph, the virtual-node model starts with higher range and trends downward toward the true range.The figure reports the minimum and maximum across four seeds.Source: Figure 9 · p. 15

C.4. AMAZON-RATINGS and ROMAN-EMPIRE: heterophilic tasks

• Because the graphs have 24,492 and 22,662 nodes, respectively, dense GTs were computationally infeasible; experiments used a local GCN, local GT, and GCN+VN.Source: §C.4 · p. 15
• On both heterophilic tasks, GCN+VN was long-range but offered no performance benefit, while a local GT performed better than GCN with near-identical range.This suggests heterophily is not necessarily related to range for these tasks.Source: §C.4 · p. 15

• On VOCSUPERPIXELS, resistance-distance ranges stayed below 1 even for GPS and GT, unlike shortest-path distance ranges, reflecting the graphs’ high average degree.GT’s initial resistance-distance range also matched GINE and GCN+VN, unlike its higher shortest-path range.Source: Figure 10 · p. 16
• On PEPTIDES-FUNC and PEPTIDES-STRUCT, the negative correlation between performance and range may indicate these tasks are not as long-range as previously assumed.Source: Figure 11 · p. 16

D.1. Differentiability of models for PEPTIDES experiments

• Replacing PEPTIDES’ embedding encoder with a differentiable one-hot encoder enables Jacobian calculation while remaining equivalent to the existing encoder.Source: §D.1 · p. 16

D.2. Inefficiency of one-hot encoding for PEPTIDES

• The standard PEPTIDES encoding expands 9 integer features to 174 dimensions, over 80% always zero; reducing it to 31 features lowers Jacobian cost with minimal performance impact.Updated LRGB hyperparameters report decreased parameter counts alongside the original counts.Source: §D.2 · pp. 16–17, Table 4 · p. 20
• On CORA, the GCN remains near 1-hop range and outperforms the GT; the GT learns low range after high-range initialization before overfitting and losing accuracy.The range-and-loss plot is cut off at epoch 25, when both models reach their highest validation accuracy.Source: §D.2 · p. 17, Figure 13 · p. 17, Figure 12 · p. 17

D.3. Isolated nodes in PEPTIDES

• PEPTIDES includes disconnected graphs and isolated nodes in about 1% of the dataset, making average diameter technically infinite and complicating connectivity-based distance metrics.For Transformer range calculations, distances are computed within connected components.Source: §D.3 · p. 17

D.4. Jacobian sampling for range measure estimation

• Randomly sampling input/output nodes and channels sparsifies the Jacobian to approximate range with lower time and memory use; experiments report extremely low variance across seeds.Masking the input and reducing the full output yields a reduced Jacobian and computational graph.Source: §D.4 · pp. 17–18
• On AMAZON-RATINGS and ROMAN-EMPIRE, attention-based MPNNs improved performance over convolution, while GCN+VN increased range without performance gain; the tasks may not be long-range.The AMAZON-RATINGS figure describes the range increase as slight; the ROMAN-EMPIRE figure reports long-range interactions.Source: Figure 15 · p. 18, Figure 14 · p. 18, §D.4 · p. 18

D.5. Computational Resources

• Sampling uses an input-node probability of 1.0 because lower values introduced bias without reducing compute; graph sizes are bounded to 16–256 nodes, and experiments primarily used NVIDIA A10 GPUs.Some experiments used NVIDIA H100 GPUs.Source: §D.4 · p. 18, §D.5 · p. 18, Table 3 · p. 19