Provable Global Reach via Effective-Resistance-Weighted Propagation

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.