Graph neural networks (GNNs) are models that update each node's vector by repeatedly mixing in its neighbors' vectors. Each round of mixing, or layer, lets information travel one more hop. In principle, a 64-layer GNN should know about nodes 64 hops away. In practice, deep GNNs either lose accuracy or are rescued by shortcut connections, and it is disputed whether the rescued models actually use distant information. We propose a simple instrument for settling this. Freeze a trained GNN and, at every layer, fit a linear classifier or regressor (a "linear probe") that tries to recover information from nodes at exactly distance $k$. We build the probe's target so that it cannot be predicted from anything closer than $k$ hops. The result is a reach map: for each layer, how much exclusively $k$-hop information can still be read out linearly.
The opportunity comes from a direct contradiction in the literature. Simple and Deep Graph Convolutional Networks (GCNII) reports its best Cora result with a 64-layer model. Analyzing the effect of residual connections to oversmoothing in graph neural networks argues that GCNII's link back to the input features acts as an "anchor": the deep model behaves like a weighted sum of shallow ones and scores about 65%, no better than chance, on a synthetic Star graph whose informative leaves sit 10 or more hops away. Neither paper looks inside the network. Separately, Model Degradation Hinders Deep Graph Neural Networks attributes early collapse to the stacked weight layers rather than to neighbor averaging, but again only from end-to-end accuracy and gradients. A reach map would show directly whether depth buys reach, where reach is lost, and which architectural component loses it.
Core Claim
Existing depth diagnostics measure the wrong thing for the depth question. Effective rank and Dirichlet energy measure how spread out node vectors are, not how far their information comes from. End-to-end accuracy mixes reach with optimization. We claim that the residualized $k$-hop linear probe isolates reach. Concretely, let $h_v^{(\ell)}$ be node $v$'s frozen vector at layer $\ell$, and let $s_k(v)$ be the mean input feature over nodes at shortest-path distance exactly $k$ from $v$. The probe target is the part of $s_k(v)$ that cannot be predicted linearly from the closer shells:
$$t_k(v) = s_k(v) - \Pi_{<k}\big[s_0(v), \dots, s_{k-1}(v)\big],$$
where $\Pi_{<k}$ is the best linear prediction fit on held-out nodes. The reach map is the held-out $R^2$ of a ridge regression from $h_v^{(\ell)}$ to $t_k(v)$, written $R(\ell, k)$.
Residualization is the essential ingredient. On homophilous graphs such as Cora, distant shells resemble nearby ones, so without it, a probe "finds" 10-hop information that is really 1-hop information.
We make three falsifiable predictions. For GCNII and APPNP, $R(\ell, k)$ will saturate at small $k$ no matter how large $\ell$ grows, which would confirm the anchor account at the level of representations. For models with deep neighbor averaging but only two weight layers (AIR-style), reach will extend further but decay with $k$, in line with the smoothing account. For plain deep GCNs, reach will collapse before effective rank does.
Research Program
We build a probing toolkit that computes shells, residualized targets, and closed-form ridge probes, so that probe fitting has no optimizer settings to tune and costs little even on ogbn-arxiv. We apply it to a grid of models: GCN, GAT, GCNII, APPNP, AIR, and the layer-connection search model of Learn Layer-wise Connections in Graph Neural Networks. Following Model Degradation Hinders Deep Graph Neural Networks, we vary propagation depth (rounds of neighbor averaging) and transformation depth (number of learned weight layers) independently, from 2 to 64.
Every trained model is paired with an untrained copy of the same architecture. This matters because Probing Graph Representations showed that random graph networks already encode substantial structure. That paper supplies our method: linear and information-based probing of frozen graph representations, together with the finding that general information peaks in middle layers. We differ from it in three ways. It studied molecular graph-level tasks at standard depths. We study node-level tasks, depths up to 64, and a distance-specific target designed to rule out closer-hop shortcuts.
Baselines
The naive reference point is a probe on the raw propagated features $\hat A^{\ell} X$, where $\hat A$ is the normalized adjacency matrix. We also probe an untrained network of the same architecture. Together these show how much reach comes from neighbor averaging alone, before any learning.
The strongest existing diagnostic is effective rank, together with numerical rank, from Are we measuring oversmoothing in graph neural networks correctly?. That paper reports an average Pearson correlation of 0.91 between effective rank and accuracy across depths, datasets, and architectures. We compute it on exactly the same frozen layers. We also report Dirichlet energy and the mean average distance index as weaker references.
For end-to-end behavior, the reference is the Star result of about 65% for residual models, from Analyzing the effect of residual connections to oversmoothing in graph neural networks. We add a gradient-based sensitivity score: the norm of the derivative of a node's output with respect to $k$-hop inputs. No paper in the file reports it for these models, so we implement it ourselves.
The key ablation removes residualization and probes the raw $s_k$. A second ablation replaces the ridge probe with a two-layer MLP probe. All diagnostics are computed on identical checkpoints and node splits. The only tuning is a single ridge penalty chosen on a validation split, and the MLP probe gets a matched validation budget.
"Beating" the baselines has a specific meaning. Across checkpoints, the reach summary $R(\ell^*, k_{\text{task}})$ at the output layer $\ell^*$, where $k_{\text{task}}$ is the hop distance the task requires, must predict end-to-end accuracy on long-range tasks better than effective rank and sensitivity do. We test this with held-out-architecture correlation and with the rank ordering of models.
Why not just…?
Why not just measure effective rank? Its authors themselves note that high rank is necessary but not sufficient: random noise has full rank and no task content. An anchored GCNII can keep high rank simply by copying its input features. Rank cannot tell copied local information apart from transmitted distant information. The reach map can. We test this directly by looking for checkpoints with high rank and low $R(\ell, 10)$ on Star.
Why not just run end-to-end tasks like Star or the Long-Range Ising Model benchmark? These show that a model fails, but not where or why. A wrong output could reflect information that never arrived or information that arrived and was not used. LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning shows that an oracle limited to 5 hops loses accuracy. Lacuna, however, has no per-model error numbers for this benchmark, and end-to-end error alone cannot locate the bottleneck layer.
Why not just compute gradient sensitivity to distant nodes? This is the most serious alternative. Sensitivity measures whether outputs move when distant inputs change. Our probe measures whether distant information is recoverable. A tiny gradient can still carry linearly decodable signal, and a large gradient can reflect a mixing of distances that cannot be untangled. If sensitivity tracks accuracy as well as the reach map does, the instrument is redundant, and we will report that.
Why not use nonlinear probes or fine-tuning? A flexible probe can rebuild missing structure itself, and fine-tuning brings back the optimization failures that Model Degradation Hinders Deep Graph Neural Networks identified. We report the MLP probe as a bound. If the gap between the linear and MLP probes is large, distant information is present but stored nonlinearly, and that is itself a finding.
Why not skip depth and use precomputed hop features? Fixed Aggregation Features Can Rival GNNs matches or beats GNNs on 12 of 14 tasks; on Squirrel it scores 44.59% against GCN's 44.26%. It trails, however, on Roman-Empire and Minesweeper, which need 10 to 15 layers, and its feature count explodes beyond 4 hops. Those long-range tasks are exactly where the question of reach matters.
Proposed Experiments
We run four experiments.
The first tests the anchor account. On Star and on Long-Range Ising Model graphs at an easy setting ($\sigma=1.5$) and a hard setting ($\sigma=0.6$), we compute $R(\ell, k)$ for GCNII and APPNP at 64 layers. The anchor account predicts that $R(\ell, k)$ stays near zero for $k \ge 10$ at every layer, matching the roughly 65% Star accuracy. If instead distant information is decodable but unused, the readout or optimization is the culprit, not the anchor.
The second applies the propagation-versus-transformation grid on Cora, PubMed, Roman-Empire, Minesweeper, and ogbn-arxiv. It tests whether failures from deep weight stacks show up as lost reach or only as poor readout from representations that still carry the information.
The third places rank and reach on the same layers. It tests whether rank collapse comes before, at the same time as, or after reach collapse.
The fourth is the decisive check. Across all checkpoints, we test whether reach predicts long-range task accuracy on held-out architectures better than effective rank (the 0.91 reference) and gradient sensitivity. As a sanity check, the residualization ablation must show inflated spurious reach on Cora. If it does not, the residualization step is not doing the work we claim for it.
References
- Simple and Deep Graph Convolutional Networks
- Analyzing the effect of residual connections to oversmoothing in graph neural networks
- Model Degradation Hinders Deep Graph Neural Networks
- Learn Layer-wise Connections in Graph Neural Networks
- Probing Graph Representations
- Are we measuring oversmoothing in graph neural networks correctly?
- LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning
- Fixed Aggregation Features Can Rival GNNs