acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural networks, long-range dependencies, realized interaction range, message passing, influence analysis, spectral graph filters, numerical stability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pCQZOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper deals with the, well studied but still highly contentious, problem of long-range dependencies in graph neural networks. Although there has been a heap of theoretical studies and architecture innovations, there is still no clear consensus as to whether simple or modified GNNs can or cannot make use of long-range context. In this work, authors argue that the problem comes from a divide between the properties one can prove such models have (how far they can reach), versus how these models actually tap into these properties to solve a given task (or even if they tap into such properties at all for a given task). The paper therefore suggest to compute how a given model actually makes use of long-range context, versus it's idealized behaviour and finds out several failure modes related to either a model's structure or computational approximations. These failure modes are then revealed and tested on controlled benchmarks and for different recent and classical architectures, illustrating discrepancies between realized and idealized behaviour.

Critical strengths
  • clear scope, does one thing but does it well: in this case clearly identifies how architecture that optimise reachability of distant information actually realise their potential when trained.
  • Proposes well-motivated diagnostic tools (interaction profiles) that are architecture agnostics
  • simple but clear theoretical developments: provides clear theoretical insights
  • convincing illustrations on controlled benchmarks allow to distinguish various failure modes on simple tasks and for different architectures.
Critical weaknesses

. re-wiring approaches are not dealt, the theoretical machinery being linked to diffusion approaches. But the diagnostic tools introduced in the paper (interaction profiles) seem much more architecture agnostic. Is it possible to use them to compare diffusion and re-wiring approaches ? Or compare how re-wired models perform by comparing performances wrt to original and re-wired graph distances ? . good on controlled benchmarks and ECHO but does that tell us much for benchmarks closer to real world ? In particular how "long-range" does effectively occur in practice ? I worry that all this could be nice on paper but that in practice models don't need to access regimes of long-range interactions that make such a difference. In its present form the paper convincingly explores actual model performances as function of the distance variable. It does not tell us if real-world graph learning tasks really require interaction ranges that goes beyond what current architectures actually realize.

A more modest but still interesting claim should be : Existing architectures (within a certain class) often fail to implement the communication range they theoretically permit.

Questions for authors

. what can you say about re-wiring approaches based on your proposed interaction profiles ? . are there real-world tasks where such long range interactions do make a clear difference (and are not solved by simply adjusting the receptive field) ?

Minor comments for the manuscript :

please add a bit of context at the beginning of Section 2, it reads like a list of definitions

Theorem does not tell us anything about the fixed point H^star, in particular one may want to stop strictly before this point because it is non-informative ?

section 3.3 and theorem 2 really need more context. it is difficult to understand how the various quantities involved relate to the paper

Reviewer_46TTOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the problem of long-range interactions in Graph Neural Networks. Specifically, 4 aspects support, approximation, alignment and execution are proposed. The paper then studies the problem with outlined metrics both qualitatively and empirically.

Critical strengths
  • I believe the problem of studying the theoretical possible vs the empirical realized interactions is important and interesting
  • I find the observation of the sqaure root behaviour of iterative processes promising
Critical weaknesses
  • my main concern: while I find the proposed investigation into 4 distinct aspects reasonable; i find it hard to pinpoint the most important findings or novel insights from these. How should this framework be applied to architectures beyond the synthetic tasks. Is the contribution the introduction and discussion of these aspects? Is it more about the introduced metrics? Moreover, I believe these discussion points are not completely novel by itself, compared to the recent proposal of specific long-range benchmarks or measures over the past year.
  • My second concern regards the empirical tests, which are more about extrapolation, rather than quantifying learned long-range behavior. This should be better separated into an OOD and a long-range analysis.
  • The main theoretical results consider a linearized version of the computation (fixed point, sqrt diffusion), which limits their applicability to the non-linear models used in practice
Questions for authors

-It is not clear if the the discussed metrics (influence and Rq) should be considered new contributions, and if so, how they exactly differ to existing measures such as proposed by Bamberger et al. (influence measure).

Reviewer_qp5TOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a diagnostic framework distinguishing architectural support, finite-approximation error, task-alignment error, and numerical execution error in long-range GNNs.

Critical strengths

Clear conceptual distinction between potential receptive fields and realized functional dependence, supported by well-defined interaction profiles based on input-output sensitivity.

Broad comparison across GNN families, including message-passing, spectral, recurrent, and global-attention architectures.

Demonstration that low aggregate prediction error can conceal substantial failures in capturing long-range dependencies.

Interesting causal-style diagnostics: source substitution, distractor variation, role swaps, and query relocation (Table 11) help localize PathCopy failures to distance-dependent source utilization. These experiments provide evidence against alternative explanations, such as failure to learn the task or graph-size effects.

Rigorous molecular benchmark design, providing an application beyond purely synthetic graph-learning tasks.

Critical weaknesses

The central premise is that architectural reachability does not necessarily imply effective long-range information propagation. However, this limitation has been widely recognized in the GNN literature, particularly since the early studies on oversmoothing and related information-propagation bottlenecks. In my opinion, this substantially limits the conceptual novelty and potential impact of the paper.

The contribution is primarily a diagnostic framework rather than a new learning algorithm. This is not necessarily problematic, provided the framework offers sufficiently novel insights or substantially advances our understanding of GNN behavior. However, given the point above, I am not entirely convinced that the findings represent a sufficiently significant advance. Several theoretical components also appear to follow established results concerning finite-support computation, contractive iterations, diffusion, and numerical conditioning. The authors should more clearly identify which theoretical contributions are genuinely novel and how the proposed framework advances beyond existing analyses.

Questions for authors

Robustness of the diagnostic metrics: How sensitive are the proposed metrics to the input distribution, model initialization, training checkpoint, and perturbation magnitude?

Node-level sensitivity estimation and counterfactual analyses may become computationally expensive for large graphs. How does the computational cost scale with graph size, and what practical limitations might arise when applying the framework to large-scale datasets?

Generalizability: A substantial part of the analysis relies on synthetic tasks. To what extent can the conclusions be generalized to more complex, real-world graph-learning problems?

The comparisons in the bottom panels of Figure 3 would benefit from a more explicit assessment of statistical significance. In particular, the observation that ChebNet and Stable-ChebNet nearly overlap appears to be based on only three runs. Additional repetitions or uncertainty estimates would strengthen these conclusions.

Node-level sensitivity estimation and counterfactual analyses may become computationally expensive for large graphs. How does the computational cost scale with graph size, and what practical limitations might arise when applying the framework to large-scale datasets?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.