acceptodds
Under review as a conference paper at ICLR 2027

Provable Global Reach via Effective-Resistance-Weighted Propagation

Abstract

Message-passing graph neural networks (GNNs) have a finite receptive field and can struggle to transmit information across long graph distances and structural bottlenecks. Although existing remedies such as graph rewiring or virtual nodes can bypass these issues, they may alter the original communication geometry or mediate global interactions through a shared latent state. To overcome this with theoretical support, we propose ER-GCN, an architecture that augments local graph convolution with a global propagation channel derived from effective resistance. ER-GCN assigns positive weights to every pair of distinct nodes with weights decreasing as effective resistance increases. Afterwards, ER-GCN row-normalizes the resulting similarity matrix to obtain a global propagation operator. Theoretically, our node-wise Jacobian support analysis shows that augmenting local propagation with this effective-resistance-based global propagation operator in at least one layer can remove topology-induced structural zeros between distinct node pairs. Empirical evaluations on synthetic bottleneck benchmarks and real-world long-range graph datasets are consistent with our theoretical analyses that ER-GCN improves performance most consistently when long-range information is important, while ER-GCN remaining competitive on tasks dominated by local structure. Ablation studies further support the importance of dense global support and suggest a benefit from resistance-aware weighting.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, message passing, effective resistance, over-squashing, long-range dependencies, global propagation

Reviews

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

The manuscript presents ER-GCN, a novel message-passing layer for Graph Neural Networks that mixes a standard GCN-like propagation operator PP with a dense operator QQ derived from effective resistance theory. The paper claims that this hybrid layer removes structural zeros in the Jacobian that affect long-range propagation. Moreover, the authors propose a variational characterization of their methodology. Experiments explore Barbell topologies, TreeNeighborsMatch, and several real-world datasets (LRGB Peptides, TU, and ZINC).

Critical strengths
  1. I checked the theory and it is correct, proving that dense mixing layers are a sufficient condition to annihilate structural zeros in the Jacobian. Limitations are stated and acknowledged. I think the application of effective resistance in GNNs is an interesting topic, and the authors' implementation really is simple, neat, efficient and lightweight: it is as easy as modifying a GCN layer (excluding the pre-processing overhead), which I appreciate a lot.
  2. Experimental setup is broad and reveals, in full clarity, also the limitations of the method. I also found the ablation useful and detailed, and I think it is important to report relevant results in a complete and transparent way.
Critical weaknesses
  1. Limited novelty and evidence of long-range propagation. The main contribution of the manuscript is the construction of a dense node-mixing operator QQ on top of standard GCN message passing. While the proposed theoretical results are sufficient to establish that such an operator will remove topologically introduced zeros (and produce positive Jacobians), they do not guarantee that information from distant nodes can still have a significant influence on a given node. In my opinion, the manuscript lacks a methodological and theoretical analysis that relates the elimination of structural zeros to meaningful message passing, that is, a proof of effective long-range propagation. Moreover, the main theoretical guarantees follow directly from the strictly positive off-diagonal entries of QQ rather than from any specific property of ER; the assumptions in Section 3.2 only require Qji>0Q_{ji} > 0. Uniform mixing would, indeed, satisfy the same properties. In fact, the authors include this comparison in an ablation study (see Table 8), where uniform stays competitive with the resistance-based kernel (uniform: 0.1286±0.0210.1286 \pm 0.021 vs. resistance: 0.1213±0.0170.1213 \pm 0.017), undermining the claimed benefits of resistance weighting. Finally, the chosen kernel assigns exponentially smaller weights to pairs of nodes with higher resistance than to lower-resistance pairs in the same row, suppressing signals from distant nodes. In conclusion, given the existing literature on long-range propagation and on effective resistance in GNNs, this contribution appears limited unless the manuscript is adequately revised and its long-range claims are addressed.
  2. Experimental evidence is limited. In addition to the aforementioned methodological limitations, I think that the experimental section presents problems that further weaken the manuscript's conclusions. After carefully reading Appendix C, I must point out that the reported score for each seed on the Barbell task is the lowest test MAE observed during training (manuscript lines 1401-1402, Table 5). In other words, the authors are selecting the best checkpoint on the test set, undermining the validity of the results. Secondly, the hyperparameter selection protocol is not documented. Appendix D thoroughly reports the selected hyperparameters, but neither the search space nor the selection criterion is described. This is particularly important given that the importance of hyperparameter selection and tuning in GNNs has already been analyzed in previous literature [5]. Besides the serious concerns about the tuning, another major experimental issue arises. The only long-range dataset experiment provided is Peptides from the LRGB suite. However, recent literature has extensively questioned the actual long-range nature of the task. In particular, in [2] the authors show substantial improvements from tuning MPNN baselines on LRGB; in [3] the authors formally question the actual need for long-range interactions to solve the Peptides task. Finally, results on ZINC and conventional graph datasets do not establish, nor prove, improved long-range propagation arising from the method.

I must also point out major clarity issues. The manuscript formulation and writing style is convoluted and not ready for publication: core math concepts are introduced after their definition (just for example, the matrix QQ is introduced in sec. 3, but its structure only defined in sec. 4; notation is hard to follow; terms like "structural zeros" or dGd_G are never defined in the text).

References:

  • [1] Velingker et al. Affinity-Aware Graph Networks. NeurIPS, 2023.

  • [2] Tönshoff, J., et al. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. arXiv preprint arXiv:2309.00367, 2023.

  • [3] Bamberger, J. et al. On Measuring Long-Range Interactions in Graph Neural Networks. ICML, 2025.

  • [4] Mathys, J. et al. LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning. ICLR, 2026.

  • [5] Luo, Y. et al. Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification. arXiv preprint arXiv:2406.08993, 2024.

  • [6] Gravina et al. Anti-Symmetric DGN: a stable architecture for Deep Graph Networks. arXiv preprint arXiv:2210.09789, 2023.

Questions for authors
  1. Can the authors clarify the positioning of their methodology with respect to existing ER literature in GNNs (e.g., [1])?
  2. Can the authors provide a quantitative and methodological analysis of the actual long-range capabilities of the ER-GCN layer, with particular regard to the weaknesses pointed out in W1?
  3. Can the authors address the experimental limitations listed in W2? In particular, can the authors provide empirical long-range evidence beyond the discussed LRGB results, and test their method on long-range datasets (see LRIM [4] as a solid dataset) and against long-range MPNNs (see A-DGN [6] as an example of a solid long-range baseline)? Can they provide a real long-range sensitivity analysis according to [3]?
  4. Again on the experimental setup, can the authors provide the hyperparameter search space used to train ER-GCN?
8 comments

We sincerely thank the reviewer for their feedback and their thoughtful evaluation. Below we address all points.

1. Positioning w.r.t. Existing Effective-Resistance Literature in GNNs (Q1, W1)

Prior work incorporates effective resistance (ER) into GNNs in roles fundamentally distinct from ER-GCN:

  • ER as Node/Edge Features: Affinity-Aware GNNs [1] inject random-walk affinities as static node or edge features inside standard 1-hop MPNNs to boost structural expressivity beyond 1-WL while avoiding O(N2)\mathcal{O}(N^2) message passing. Crucially, because message passing remains strictly local along original graph edges, an LL-layer Affinity-Aware GNN still obeys the hard LL-hop feature receptive-field barrier. Dynamic input features xu\boldsymbol{x}_u at distance dG(u,v)>Ld_G(u,v) > L have identically zero Jacobian (∂hv(L)/∂xu=0\partial \boldsymbol{h}_v^{(L)}/\partial \boldsymbol{x}_u = \mathbf{0}). On tasks where topology is fixed and targets depend on distant dynamic node features, static ER edge/node features cannot transmit feature signals beyond LL hops.
  • ER for Sparse Rewiring: GTR [2] greedily adds a sparse edge budget to minimize total resistance, altering the graph geometry while leaving distant pairs disconnected or bottlenecked when the budget is small.
  • ER-GCN: Rather than using ER as static features or sparse graph edits, ER-GCN transforms all-pairs ER into a dense, row-stochastic feature-propagation operator Q\boldsymbol{Q} derived from an entropy-regularized variational principle, preserving the exact local operator P\boldsymbol{P} while enabling direct nonlocal feature transport at any finite depth LL with only one learnable scalar θl\theta_l per layer. We will expand Section 2 to make this distinction explicit.

2. Quantitative & Methodological Analysis of Long-Range Propagation(Q2, Q3, W1)

To provide evidence of ER-GCN's task-meaningful message passing, we conducted a four-level quantitative, range [3], and causal analysis on trained Barbell 10-layer ER-GCN models:

(A) Layer-Level Operator Attenuation & Jacobian Factorization

In the hybrid layer Ml=(1−βl)P+βlQ\boldsymbol{M}_{l} = (1-\beta_{l})\boldsymbol{P} + \beta_{l}\boldsymbol{Q}, the row-wise weight ratio is QuvQuw=exp⁡(−Reff(u,v)−Reff(u,w)σ)\frac{Q_{uv}}{Q_{uw}} = \exp\left(-\frac{R_{\mathrm{eff}}(u,v)-R_{\mathrm{eff}}(u,w)}{\sigma}\right).

  • For target nodes u∈C2u \in C_2 to distant source nodes v∈C1v \in C_1, entries are Q22,11=0.01603Q_{22,11} = 0.01603 (hop 11, Reff=11.0R_{\mathrm{eff}}=11.0), Q23,11=0.01589Q_{23,11} = 0.01589 (hop 12, Reff=11.17R_{\mathrm{eff}}=11.17), and Q23,0=0.01563Q_{23,0} = 0.01563 (hop 13, Reff=11.33R_{\mathrm{eff}}=11.33).
  • Summing over the 12 source-clique nodes, C1C_1 receives 18.78%18.78\% of a resistance-Q\boldsymbol{Q} row. With learned βl≈0.104\beta_l \approx 0.104 (β0=0.1042\beta_0=0.1042 to β9=0.1041\beta_9=0.1041), direct per-layer mixed mass beyond 10 hops is 2.13%2.13\% per layer.
  • Factoring the exact 1-layer Jacobian as \left\\|\frac{\partial H_u^{l+1}}{\partial H_v^l}\right\\|_{1,\mathrm{entry}} = (M_l)_{uv} C_{u,l}(X) where Cu,l(X)=∑a,b∣ϕl′(Zual)Wbal∣C_{u,l}(X) = \sum_{a,b} |\phi_l'(Z_{ua}^l) W_{ba}^l|, the trained network actively amplifies early-layer signals (Cu,0=123.40C_{u,0} = 123.40, yielding direct 1-layer Jacobian magnitudes of 0.224,0.373,2.0270.224, 0.373, 2.027 at hops 11, 12, 13) before projecting down at the readout layer (Cu,9=7.752C_{u,9} = 7.752).

(B) Long-Range Sensitivity Analysis Following Bamberger et al. [3]

Using the normalized hop sensitivity distribution qX(u,h)=TX(u,h)∑kTX(u,k)q_X(u,h) = \frac{T_X(u,h)}{\sum_k T_X(u,k)} where T_X(u,h) = \sum_{v: d_G(u,v)=h} \left\\|\frac{\partial \hat{y}_u}{\partial X_v}\right\\|_1, we compute the influence-weighted range RX(u)=∑hh,qX(u,h)R_X(u) = \sum_h h\\, q_X(u,h) [3], the 9090\\%-mass radius r90r_{90}, and the sensitivity fraction beyond the 10-hop barrier (F>10=∑h>10qX(u,h)F_{>10} = \sum_{h>10} q_X(u,h)):

For ER-GCN with L=10L=10 and σ=10\sigma=10, it has full-input range R=3.404R = 3.404 hops (9595\\% CI [3.382,3.426][3.382, 3.426]), with F>10=14.35F_{>10} = 14.35\\% ([14.20[14.20\\%, 14.50\\%]) of total sensitivity strictly beyond 10 hops and 9090\\%-mass radius r90=12.862r_{90} = 12.862 hops (matching the oracle target distance of 12.83312.833 hops; source-restricted range =12.816= 12.816 hops). Individual source–target pair influences remain strong across all distant shells: 1.1171.117 (hop 11), 1.0111.011 (hop 12), and 0.9060.906 (hop 13).

(C) End-to-End Task Alignment & Causal Interventions

To verify that this 14.35%14.35\% distant Jacobian mass reflects faithful message passing rather than noise, we test against the ground-truth generator y=1c∑v∈C1Xv⊤wd/cy = \frac{\frac{1}{c}\sum_{v\in C_1} X_v^\top w}{\sqrt{d/c}} (oracle gradient ∇Xvy=w/cd\nabla_{X_v} y = w/\sqrt{cd} at hops 11–13):

  • Directional Gradient Alignment: Cosine similarity between ER-GCN's input gradient ∇XC1y^u\nabla_{X_{C_1}} \hat{y}_u and the oracle gradient is 0.98770.9877 ([0.9857,0.9897][0.9857, 0.9897]), specifically 0.98980.9898, 0.98970.9897, and 0.98950.9895 at hops 11, 12, and 13. ER-GCN recovers the exact projection vector ww across the 11–13 hop bottleneck.
  • Causal Source-Resampling Interventions: Independently resampling C1C_1 features (11–13 hops away) on held-out graphs while freezing all other inputs/weights yields prediction shifts Δy^u\Delta \hat{y}_u tracking Δyu\Delta y_u with correlation 0.98650.9865 ([0.9838,0.9893][0.9838, 0.9893]), regression slope is 0.96330.9633 (ideal =1.0=1.0). Single-node interventions at hops 11, 12, and 13 individually achieve correlations of 0.980,0.976,0.9800.980, 0.976, 0.980.

(D) Bandwidth (σ\sigma) Sweep

We directly quantifies the reviewer's concern about exponential decay. When σ=1\sigma=1 is much smaller than ReffR_{\mathrm{eff}}, exponential decay indeed suppresses C1C_1 (0.0015%0.0015\% row mass, F>10=0.015%,R=1.033,EΔ=0.3856F_{>10} = 0.015\%, R = 1.033, E_\Delta = 0.3856, MAE 0.30150.3015). However, once σ\sigma matches the resistance scale (σ≥10\sigma \ge 10), attenuation is mild: F>10F_{>10} reaches 14.35%14.35\% (σ=10\sigma=10), 18.60%18.60\% (σ=20\sigma=20, MAE 0.12880.1288), and 21.98%21.98\% (σ=100\sigma=100), preserving causal transfer (EΔ≈0.160–0.163E_\Delta \approx 0.160\text{--}0.163).

3. Why Exponential Resistance Kernel? (W1)

We choose gσ(R)=exp⁡(−R/σ)g_\sigma(R) = \exp(-R/\sigma) because it uniquely solves the entropy-regularized distortion minimization (Section 4, Eq. 13 & Lemma A.2): \boldsymbol{q}_u^\star = \arg\min_{\boldsymbol{q}_u \in \Delta_u} \left\\{ \sum_{v \neq u} q_{uv} R_{\mathrm{eff}}(u,v) + \sigma\\, \mathrm{KL}(\boldsymbol{q}_u \\| \boldsymbol{\pi}_u) \right\\}, \quad \text{where } \left\\|\overline{\boldsymbol{h}}_u(\boldsymbol{q}_u) - \boldsymbol{h}_u\right\\|_2^2 \le \operatorname{tr}(\boldsymbol{H}^\top \boldsymbol{L} \boldsymbol{H}) \sum_{v \neq u} q_{uv} R_{\mathrm{eff}}(u,v). Uniform mixing (πu\boldsymbol{\pi}_u, corresponding to σ→∞\sigma \to \infty) minimizes only entropy while ignoring the topological distortion bound ∑v≠uquvReff(u,v)\sum_{v\neq u} q_{uv} R_{\mathrm{eff}}(u,v), indiscriminately mixing unrelated graph regions when all nodes carry active features. Conversely, σ→0\sigma \to 0 collapses support. For finite σ>0\sigma > 0, the exponential kernel uniquely balances full global support (Quv>0Q_{uv} > 0) with bounded geometric distortion.

4. Protocol Fix, New Baselines, and LRIM Evaluation (Q3, W2)

(a) Barbell Checkpoint Selection Fix: We thank the reviewer for pointing out this issue. We added an independent validation split for checkpoint selection and updated all Barbell results in Table 1.

(b) Following the reviewer's suggestion, we have tested A-DGN [4] on Barbell (MAE ↓\downarrow) and TreeMatch (Acc % ↑\uparrow). Experiments on other datasets are in progress and will be included in the revision

Modelpl=10pl{=}10pl=12pl{=}12pl=14pl{=}14d=3d{=}3d=6d{=}6d=8d{=}8
A-DGN [4]N/AN/AN/A99.70±0.5115.30±2.1016.00±0.00
ER-GCN0.1334±0.02750.1396±0.02690.1970±0.0214100.00±0.0099.70±0.6799.65±1.11

A-DGN is 1-hop local and therefore N/A on Barbell pl≥10p_l\ge 10. On TreeMatch, A-DGN suffers over-squashing (16.0% at d=8d=8) while ER-GCN keeps >99.6%>99.6\% Acc and lowest MAE.

(c) We agree with [3, 5] regarding Peptides. We thank the reviewer for recommending LRIM [6], an exemplary, physics-grounded benchmark where Ising-system targets provably depend on long-range interactions across graphs with dense node features, paired with explicit complexity reporting.

To directly test overcoming the hard receptive-field barrier, we evaluated ER-GCN and the LRIM baselines following LRIM's official hyperparameter selection protocol but at fixed depth L=4L=4 (well below lattice diameter).

ModelLRIM-16-hard ↓\downarrowLRIM-32-hard ↓\downarrowLRIM-16-easy ↓\downarrowLRIM-32-easy ↓\downarrow
GIN [7]-1.6795±0.0112-1.2213±0.0089-2.5964±0.0177-2.2461±0.0161
GatedGCN [8]-1.6006±0.0078-1.2049±0.0314-2.6478±0.0139-2.1303±0.0249
GatedGCN-VN$_G$ [9]-1.7315±0.0149-1.2185±0.0037-2.6887±0.0071-2.2200±0.0055
ER-GCN-1.7012±0.0657-1.2245±0.0702-2.8528±0.0430-2.3412±0.0578

ER-GCN beats GIN/GatedGCN on all splits and ranks 1st on 3/4 splits, validating ER decay on dense active features. GPS [10] and its variants on other LRIM datasets under the same protocol are currently in progress and will be included and cited upon acceptance.

5. Hyperparameter Search Space & Protocol (Q4, W2)

We have add the hyperparameter search space to Appendix D.

6. Manuscript Organization and Presentation of Q\boldsymbol{Q} (W3)

We agree with this critique. We have reorganized it and moved the definition of Q\boldsymbol{Q} and its explanation to their proper place for better readability and logical progression.

Reviewer_xQd8OpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes, ER-GCN, a new message passing scheme for long-range modelling, which introduces a global message passing layer inspired by the effective resistance between nodes.

Critical strengths
  • The idea of using effective resistance as a graph message passing method is very interesting, and the intuition of using this technique for long-range propagation is reasonable and straightforward.
Critical weaknesses
  • The motivation of this paper is not clear. In the introduction, the authors only discussed what they did in the new message-passing framework for long-range propagation on graphs but failed to explain the necessity of this new architecture compared to existing literature. In particular, how does the proposed method distinguish from methods based on virtual nodes? What are the limitations in the previous work and how does ER-GCN address those problems?
  • As mentioned in the paper, the computation of Q requires O(n^3) (but only once before training), which is fine for inductive tasks on small graphs used in the paper’s experiments. But what about transductive tasks on relatively large graphs of more than 100k nodes?
  • Many datasets used in experiments are not long ranged. ZINC, DD, ENZYMES are not long-range datasets by design, while Peptides-Func and Peptides-Struct are also found not as long ranged as what was claimed [1].
  • The paper is also missing common long-range baselines in the literature like Drew [2]; and methods based on graph transformers like Exphormer [3] and GraphGPS [4].

Reference

[1] Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. TMLR-2024

[2] DRew: Dynamically Rewired Message Passing with Delay. ICML-2023

[3] Exphormer: Sparse Transformers for Graphs. ICML-2023

[4] Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS-2022

Questions for authors
  • The presentation of the paper is a bit messy. The key contribution is the Q matrix in section 4, but the authors first conducted a theoretical analysis in section 3, and keep referring to Q even before it is defined and explained.
  • Can you test your models on long-range datasets like City-Networks [5] (transductive tasks on large graphs), ECHO [6] and LRIM [7] (inductive tasks on small & medium size graphs)?
  • I am curious how the Jacobian-based range measurement [5, 8] behave on your trained ER-GCN model, which measures the average sensitivity of the model to each hop, and how far (i.e., #hops) does the model reach on average.

Reference

[5] Towards quantifying long-range interactions in graph machine learning: a large graph dataset and a measurement. ICLR-2026

[6] Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation. ICLR-2026

[7] LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning. ICLR-2026

[8] On measuring long-range interactions in graph neural networks. ICML-2025

5 comments

We sincerely thank the reviewer for their feedback and their thoughtful evaluation. Below we address all points including LRIM [1] and Jacobian-based range measurement [2, 3] results.

1. Manuscript Organization and Presentation of Q\boldsymbol{Q} (Q1). We agree with this critique. We have reorganized it and moved the definition of Q\boldsymbol{Q} and its explanation to their proper place for better readability and logical progression.

2. Clarifying Motivation and Distinction from Virtual Nodes & Prior Work (W1). We agree with you. Virtual-node methods (GCN+VN [4, 5], VN-G [6]) route global context through a single shared state (a rank-1 bottleneck) that erases pairwise geometry, preventing node uu from distinguishing low-Reff(u,v)R_{\text{eff}}(u,v) regions from bottlenecks. Consequently, both substantially underperform ER-GCN on Barbell (Table 1). Rewiring methods remain structurally constrained. GTR's [7] fixed edge budget leaves structural zeros when it cannot cover all distant pairs (14.85%14.85\% on TreeMatch d=8d=8), whereas DRew [8] connects kk-hop neighborhoods at layer kk, leaving zero reach beyond LL hops (L<dG(u,v)L<d_G(u,v)). Meanwhile, Graph Transformers (GraphGPS [9], Exphormer [10]) rely on learned attention and PEs, incurring heavy parameter and optimization overhead.

By contrast, our ER-GCN keeps P\mathbf{P} intact and adds a closed-form pairwise resistance operator Q\mathbf{Q} (requires only one learnable scalar θl\theta_l per layer), provably removing off-diagonal structural zeros in 1 hybrid layer at any depth LL. We have foreground this in Section 1.

3. New Experiments on LRIM [1] (Q2, W3, W4). We agree that ZINC, DD, and ENZYMES are not long-range, and Peptides shows smaller gaps for tuned MPNNs [11]. In our study, ZINC, DD, ENZYMES (and the TU datasets in Appendix E) were included specifically as control benchmarks (Section 6, Q2) to verify that dense resistance-weighted propagation does not degrade performance when predictive signals are predominantly local (enabled by learned shallow-layer βl\beta_l values remaining small).

We thank the reviewer for recommending LRIM [1], which we view as an exemplary and rigorous contribution to the field. LRIM grounds node regression in a physical system with provable long-range interactions. To directly test ER-GCN's core advantage, i.e., breaking the hard receptive-field barrier, we evaluate ER-GCN and LRIM baselines at fixed L=4L=4 on LRIM-16/32 (diameters ≫4\gg 4) under LRIM's protocol:

ModelLRIM-16-hard ↓\downarrowLRIM-32-hard ↓\downarrowLRIM-16-easy ↓\downarrowLRIM-32-easy ↓\downarrow
GIN [12]-1.6795±0.0112-1.2213±0.0089-2.5964±0.0177-2.2461±0.0161
GatedGCN [13]-1.6006±0.0078-1.2049±0.0314-2.6478±0.0139-2.1303±0.0249
GatedGCN-VN$_G$ [6]-1.7315±0.0149-1.2185±0.0037-2.6887±0.0071-2.2200±0.0055
ER-GCN-1.7012±0.0657-1.2245±0.0702-2.8528±0.0430-2.3412±0.0578

At L=4L=4, ER-GCN is comparable to local GIN and GatedGCN on all 4 tasks, ranking 1st on 3/4. GraphGPS [9] runs on other LRIM datasets under the same protocol are currently in progress and will be included and cited upon acceptance.

4. Jacobian-Based Range Measurement [2, 3] and Per-Hop Sensitivity (Q3). On Barbell (L=10,pl=10,c=12,σ=10L=10, p_l=10, c=12, \sigma=10; 34 nodes, diam. 13; 10 seeds, 64 draws/seed), for u∈C2u\in C_2 we compute

  • T(u,h)=∑dG(u,v)=h∥∂y^u/∂Xv∥1T(u,h)=\sum_{d_G(u,v)=h}\|\partial\hat{y}_u/\partial X_v\|_1 [2] and q(u,h)=T(u,h)/∑kT(u,k)q(u,h)=T(u,h)/\sum_k T(u,k)

  • range R(u)=∑hh q(u,h)R(u)=\sum_h h\,q(u,h) [3]

  • 90%90\%-radius r90r_{90}

  • F>10=∑h>10q(u,h)F_{>10}=\sum_{h>10}q(u,h) (95%95\% CIs)

Model (L=10,pl=10L=10, p_l=10)Mean RRMed. RRr90r_{90}F>10F_{>10}Sens. >10>10∑hT(h)\sum_h T(h)
Local GCN [4]0.980 [0.980,0.980]0.9802.000.00%0.0042.15
ER-GCN (σ=10\sigma=10)3.404 [3.382,3.426]3.44312.862 [12.839,12.885]14.35% [14.20%,14.50%]11.77 [11.56,11.98]81.51 [80.42,82.59]

Moreover, in the pl=10p_l=10 Barbell graph, all 144144 task-relevant source–target pairs lie beyond L=10L=10 hops:

Hop (kk)# PairsTotal Shell Sensitivity (TkT_k)Per-Node SensitivityIndividual Pair Influence
1110.7840.7841.117
12221.8531.0951.011
131219.1340.9060.906

We will include detailed Jacobian range and per-hop influence analysis in the revised manuscript.

5. Transductive tasks on relatively large graphs of more than 100k nodes (W2). Exact ER-GCN needs O(n3)O(n^3) preprocessing, which may exceed the memory. We have clarified this scope in revised manuscript and detail scaling via Spielman–Srivastava [14] O(log⁡n)O(\log n)-dim random-projection resistance embeddings in O~(mlog⁡n)\tilde{O}(m\log n) time with random-feature or landmark operators.

References

[1] Mathys et al. LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning. ICLR, 2026.

[2] Liang et al. Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement. ICLR, 2026.

[3] Bamberger et al. On Measuring Long-Range Interactions in Graph Neural Networks. ICML, 2025.

[4] Kipf & Welling. Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.

[5] Gilmer et al. Neural Message Passing for Quantum Chemistry. ICML, 2017.

[6] Southern et al. Understanding Virtual Nodes: Oversquashing and Node Heterogeneity. ICLR, 2025.

[7] Black et al. Understanding Oversquashing in GNNs through the Lens of Effective Resistance. ICML, 2023.

[8] Gutteridge et al. DRew: Dynamically Rewired Message Passing with Delay. ICML, 2023.

[9] Rampášek et al. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS, 2022.

[10] Shirzad et al. Exphormer: Sparse Transformers for Graphs. ICML, 2023.

[11] Tönshoff et al. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. TMLR, 2024.

[12] Xu et al. How Powerful are Graph Neural Networks? ICLR, 2019.

[13] Bresson & Laurent. Residual Gated Graph ConvNets. arXiv:1711.07553, 2017.

[14] Spielman & Srivastava. Graph Sparsification by Effective Resistances. SIAM J. Comput., 2011.

I thank the authors for their effort in addressing my previous points. The improved presentation as well as additional experimental results on LRIM and the range measure definitely make the paper stronger. In the meantime, I do still have the following concerns of the paper:

  • important baselines such as DRew and GTs are still missing
  • empirical results in the original paper (Tables 2, 7-8) are not fully convincing, and there isn’t much analysis why the method underperforms on a dataset (whether it is due to lack of bottlenecks/long-range dependencies or something else?)
  • claims that other methods use more parameters need to be supported by a formal analysis on this, e.g. looking at the trade-off between performance and parameter count
  • computational complexity of O^3 is too high in practice, this may not be an issue for small-scale graph-level tasks but those also do not always experience over-squashing

I remain open to any further discussion with the authors regarding the above.

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

This paper addresses the long-range limitations in message-passing graph neural networks by proposing ER-GCN, an architecture that augments local graph convolution with a dense global propagation operator derived from pairwise effective resistance. Through a node-wise Jacobian support analysis, the authors prove that inserting even a single hybrid layer at any depth removes all topology-induced structural zeros between distinct node pairs, and characterize the resulting Jacobian support for ER-GCN with tanh activations. Experiments on synthetic bottleneck benchmarks and real-world long-range graph datasets show that ER-GCN achieves performance improvements on tasks requiring long-range information, while remaining competitive on tasks dominated by local structure.

Critical strengths
  1. This paper provides rigorous and verifiable theoretical guarantees. The key theoretical results (Theorem 3.2 and Corollary 3.3) establish that a single hybrid layer at any depth eliminates all topology-induced structural zeros between distinct node pairs, with an explicit positive lower bound on the effective propagation weight. These results provide a mathematical guarantee for the paper's core claim of "provable global reach." Theorem 3.4 further bridges the gap between structural support and realized Jacobians for tanh networks.
  2. ER-GCN achieves competitive performance with a parameter count comparable to that of a standard GCN, while several competitive baselines require two to three times as many parameters.
  3. This paper ensures close alignment between theory and experiments and clearly acknowledges its limitations. The authors carefully describe the scope of their theoretical guarantees, acknowledging that positive structural propagation support may still yield a zero Jacobian. Moreover, they transparently report neutral and negative results, supported by statistical testing.
Critical weaknesses

This paper is primarily theoretical. As I do not have sufficient expertise to assess its theoretical contributions reliably, I have informed the AC of this problem. I can only point out some potential weaknesses in the experimental evaluation, which falls within my area of expertise:

The experimental evaluation lacks comparisons with graph Transformer baselines. Graph Transformers equipped with positional or structural encodings are standard baselines on LRGB and are discussed in Section 2, yet they are not included in the experimental comparisons. Given that ER-GCN claims to "give every pair of distinct nodes positive structural propagation support without ... learning an all-pairs attention matrix," comparisons with these alternatives are essential to substantiate this claim.

Questions for authors

This paper is primarily theoretical. As I do not have sufficient expertise to assess its theoretical contributions reliably, I have informed the AC of this problem. I can only raise one question regarding the experimental evaluation, which falls within my area of expertise:

How does ER-GCN compare with Transformer-based graph models on the evaluation benchmarks?

2 comments

We sincerely thank the reviewer for the thoughtful evaluation of our work and for highlighting our rigorous theoretical guarantees.

We agree that empirically comparing ER-GCN against Graph Transformer models such as GraphGPS [1] (cited and discussed in Section 2) is essential to substantiate our claim that a fixed, effective-resistance-weighted propagation channel achieves global reach without needing to learn an all-pairs attention matrix.

Following the evaluation protocol of Table 1, we evaluated GraphGPS on our controlled long-range benchmarks: Barbell (pl∈10,12,14pl \in {10, 12, 14}, evaluated by test MAE ↓\downarrow) and TreeNeighborsMatch (d∈3,6,8d \in {3, 6, 8}, evaluated by classification accuracy ↑\uparrow). (Note that in response to Reviewer tnQN, we introduced an independent validation split for checkpoint selection on Barbell and re-evaluated accordingly.)

Modelpl=10pl{=}10pl=12pl{=}12pl=14pl{=}14d=3d{=}3d=6d{=}6d=8d{=}8
GraphGPS0.4591±0.13700.5207±0.11460.4070±0.089697.20±5.6216.55±20.9910.65±2.78
ER-GCN0.1334±0.02750.1396±0.02690.1970±0.0214100.00±0.0099.70±0.6799.65±1.11

Unlike purely local message-passing models whose receptive fields cannot span the bridge, GraphGPS is able to transmit global information via all-pairs attention. However, ER-GCN achieves reductions in test MAE across all bridge lengths with substantially lower variance. Unfortunately, while GraphGPS performs well on shallow trees (d=3d{=}3), its accuracy drops sharply as depth and graph size grow. Under a matched parameter budget, learning precise pairwise interactions from scratch via global self-attention becomes increasingly difficult as the number of candidate nodes expands. In contrast, ER-GCN maintains near-perfect accuracy (99.6599.65% at d=8d{=}8) by directly using graph topology through our effective-resistance operator Q\boldsymbol{Q}, requiring only one learnable scalar mixing coefficient βl\beta_l per layer. Limited by the conference schedule, additional experiments evaluating GraphGPS under other benchmarks are currently running and will be included in the revised manuscript.

References

[1] Rampášek et al. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS, 2022.

Reviewer_CuiHOpenReview ↗

Response to Authors from Reviewer CuiH

Thanks for the authors' detailed response and additional experiments. My concerns regarding the experimental evaluation have been well addressed. I maintain my original rating and confidence.

Comments on the paper

1 comment

Dear Reviewers,

The authors have submitted their responses to the questions and concerns raised in the reviews. Please review their responses and provide any further comments or clarifications, if applicable.

Thank you for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.