Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing

Bertran Miquel-Oliver; Manel Gil-Sorribes; Victor Guallar; Alexis Molina

cs.LGMar 12, 2026

Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing

Authors: Bertran Miquel-Oliver, Manel Gil-Sorribes, Victor Guallar, Alexis Molina

Organizations: Barcelona Supercomputing Center (BSC), Barcelona, Spain · Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Barcelona, Spain · Nostrum Biodiscovery, Barcelona, 08029, Spain · ICREA, Barcelona, Spain

Abstract

Graph Neural Networks struggle to capture long-range dependencies due to over-squashing, where information from exponentially growing neighborhoods must pass through a small number of structural bottlenecks. While recent rewiring methods attempt to alleviate this limitation, many rely on local criteria such as curvature, which can overlook global connectivity constraints that restrict information flow. We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks. ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways while controlling graph densification under a fixed edge budget. The procedure is parameter-free beyond the rewiring budget and relies on a single global measure aggregating all paths between node pairs. Beyond predictive performance with GCN models, we analyze how rewiring affects message propagation. By tracking cosine similarity between node embeddings across layers, we examine how the relationship between initial node features and learned representations evolves during message passing, comparing graphs with and without rewiring. This analysis helps determine whether improvements arise from better long-range communication rather than changes in embedding geometry. Experiments on homophilic and heterophilic graphs, including directed settings with DirGCN, reveal a trade-off between over-squashing and oversmoothing, where oversmoothing corresponds to the loss of representation diversity across layers. Resistance-guided rewiring improves connectivity and signal propagation but can accelerate representation mixing in deep models. Combining ERR with normalization techniques such as PairNorm stabilizes this trade-off and improves performance.

Figures & tables

Panel of Figure 1 — Figure 1: GCN test accuracy versus depth (number of layers) under different rewiring strategies.

Panel of Figure 2 — Figure 2: Linear-probe accuracy on penultimate-layer embeddings of a GCN as depth increases, comparing rewiring strategies at budget $0.1$ . Results are shown for Cora (top) and Cornell (bottom), without PairNorm in the left columns and with PairNorm in the right ones; each colored curve corresponds to a different readout (output) layer. PairNorm consistently stabilizes the depth trend of probe accuracy, while resistance-driven rewiring alters the depth at which informative embeddings form and reduces the degradation observed in the unnormalized setting, highlighting the interaction between normalization (oversmoothing control) and topology edits (bottleneck alleviation).

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Hidden dim $d$	Dropout	lr	Weight decay
Cora	16	0.5	0.01	$5\times 10^{-3}$
CiteSeer	16	0.5	0.01	$5\times 10^{-3}$
Cornell	64	0.5	0.01	$5\times 10^{-4}$
Texas	64	0.5	0.01	$5\times 10^{-4}$

Appendix

Table 1: Hyperparameters adopted from prior work (no tuning): Kipf and Welling (2017) for Cora/CiteSeer and Pei et al. (2020) for Cornell/Texas.

Dataset	$N$	$E_{0}$	Budget	Curvature	Resistance (Add & Remove)	Resistance per Hop (Add & Remove)	Resistance	Resistance per Hop
cora	2708	10556	1%	105 / 105 (1.0% / 1.0%)	105 / 105 (1.0% / 1.0%)	105 / 105 (1.0% / 1.0%)	105 / – (1.0% / –)	105 / – (1.0% / –)
			5%	517 / 517 (4.9% / 4.9%)	527 / 527 (5.0% / 5.0%)	526 / 526 (5.0% / 5.0%)	527 / – (5.0% / –)	526 / – (5.0% / –)
			10%	1007 / 1007 (9.5% / 9.5%)	1055 / 1055 (10.0% / 10.0%)	1007 / 1007 (9.5% / 9.5%)	1055 / – (10.0% / –)	1007 / – (9.5% / –)
			15%	1489 / 1489 (14.1% / 14.1%)	1583 / 1583 (15.0% / 15.0%)	1440 / 1440 (13.6% / 13.6%)	1583 / – (15.0% / –)	1440 / – (13.6% / –)
citeseer	3327	9104	1%	91 / 91 (1.0% / 1.0%)	91 / 91 (1.0% / 1.0%)	91 / 91 (1.0% / 1.0%)	91 / – (1.0% / –)	91 / – (1.0% / –)
			5%	451 / 451 (5.0% / 5.0%)	455 / 455 (5.0% / 5.0%)	455 / 455 (5.0% / 5.0%)	455 / – (5.0% / –)	455 / – (5.0% / –)

Appendix

Table 2: Directed graphs: edge modifications by budget. Each cell reports added / removed edges, and on the next line the corresponding percentages relative to the initial number of edges

E_{0}

. For res and res_hop , we report added / – .

Dataset	$N$	$E_{0}$	Budget	Curvature	Resistance (Add & Remove)	Resistance per Hop (Add & Remove)	Resistance	Resistance per Hop
cora	2708	5278	1%	52 / 52 (1.0% / 1.0%)	52 / 52 (1.0% / 1.0%)	52 / 52 (1.0% / 1.0%)	52 / – (1.0% / –)	52 / – (1.0% / –)
			5%	263 / 263 (5.0% / 5.0%)	263 / 263 (5.0% / 5.0%)	263 / 263 (5.0% / 5.0%)	263 / – (5.0% / –)	263 / – (5.0% / –)
			10%	527 / 527 (10.0% / 10.0%)	519 / 519 (9.8% / 9.8%)	522 / 522 (9.9% / 9.9%)	527 / – (10.0% / –)	527 / – (10.0% / –)
			15%	789 / 789 (14.9% / 14.9%)	745 / 745 (14.1% / 14.1%)	730 / 730 (13.8% / 13.8%)	791 / – (15.0% / –)	791 / – (15.0% / –)
citeseer	3327	4552	1%	45 / 45 (1.0% / 1.0%)	45 / 45 (1.0% / 1.0%)	45 / 45 (1.0% / 1.0%)	45 / – (1.0% / –)	45 / – (1.0% / –)
			5%	227 / 227 (5.0% / 5.0%)	227 / 227 (5.0% / 5.0%)	227 / 227 (5.0% / 5.0%)	227 / – (5.0% / –)	227 / – (5.0% / –)

Appendix

Table 3: Undirected graphs: edge modifications by budget. Each cell reports added / removed edges, and on the next line the corresponding percentages relative to the initial number of (undirected) edges

E_{0}

. For res and res_hop , removals are not performed and are shown as “–”.

Panel of Figure 3 — Figure 3: GCN accuracy versus depth (number of layers) under different rewiring strategies.

Panel of Figure 4 — Figure 4: CKA similarity between last-layer GCN representations with curvature rewiring (curvature) and proposed rewiring strategies with $0.1$ as budget.

Panel of Figure 5 — Figure 5: CKA similarity between last-layer GCN representations with curvature rewiring (curvature) and proposed rewiring strategies with $0.1$ as budget.

Panel of Figure 6 — Figure 6: UpSet plots of edges added by different rewiring strategies at budget $r=0.1$ . Bars report intersection sizes of the added-edge sets, bar color indicates Jaccard overlap (intersection over union) for each combination.

Panel of Figure 7 — Figure 7: Mean cosine similarity between node embeddings as a function of the inner layer index (outer layer fixed to 7), comparing node pairs from the same class versus different classes, under different rewiring strategies at budget $r=0.1$ . Each grouped panel corresponds to one graph construction: Baseline, Curvature, Resistance, and Resistance per hop. Within each group, results are shown for Cora and Cornell, with and without PairNorm.

Explore similar work

Ramanujan Graph Rewiring with Non Negative Resistance Curvature
Jun 19, 2026Hugo Attali, Rachid El JouhriGraph Structure Learning Graph Rewiring
Université Sorbonne Paris Nord, CNRS, LIPN, France
Schreier-Coset Graph Rewiring
Jul 29, 2026Aryan Mishra, Randy Martinez, Lizhen LinGraph Neural Networks Graph Rewiring
Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey
May 1, 2026Hugo Attali, Nathalie Pernelle, Davide Buscaldi +1Graph Neural Networks Graph Rewiring
Universit´e Sorbonne Paris Nord, CNRS, LIPN · Universit´e Paris-Saclay, CentraleSup´elec, Inria

Jun 19, 2026J/K move · Enter open · S save

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

Hugo Attali, Rachid El Jouhri

Université Sorbonne Paris Nord, CNRS, LIPN, France

Graph Structure Learning Graph Rewiring Over-Squashing

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.

Abstract

Explore similar work

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

Schreier-Coset Graph Rewiring

Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey