Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective

André Ribeiro; Germano Barcelos; Amauri H. Souza; Diego Mesquita; Ana Luiza Tenório

stat.MLOct 3, 2026

Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective

Authors: André Ribeiro, Germano Barcelos, Amauri H. Souza, Diego Mesquita, Ana Luiza Tenório

Organizations: Getulio Vargas Foundation · Federal University of Viçosa · Federal Institute of Ceará, 2δ AI · Getulio Vargas Foundation, 2δ AI · Getulio Vargas Foundation, UFRRJ

Abstract

Graph Neural Networks (GNNs) often struggle to capture long-range dependencies due to over-squashing -- a phenomenon in which the repeated compression of node embeddings into finite-size messages causes representations to collapse. Over-squashing is most often diagnosed as a property of the graph topology, with effective resistance serving as a principled measure of the bottleneck. We provide a complementary view on the matter: building on cellular sheaves, we introduce sheaf effective resistance, a generalization of effective resistance that depends on the sheaf attached to the graph, and we prove that for flat vector bundles, the over-squashing sensitivity in the Jacobian sense is upper bounded by a quantity related to the sheaf effective resistance between the nodes. The bottleneck thus need not lie in the graph itself: it can be relocated, and reduced, by adjusting the sheaf. We instantiate this idea in FlatNSD, a simple message-passing variant of Neural Sheaf Diffusion, and show that it implicitly learns to modulate total sheaf effective resistance, performing well on benchmarks designed to stress over-squashing without altering the original graph topology.

Figures & tables

Figure 1: Training accuracy for the TreeNeighborsMatch task. Results for GCN, GIN, GAT, and GGNN are from Alon and Yahav (2021) . Results for BuNN are from Bamberger et al. (2025) . Only FlatNSD-SAGE achieves perfect accuracy for all $r$ .

Figure 2: Correlation between Train Accuracy and Sheaf ER on FlatNSD-SAGE with $r=8$ for $d=2$ and $d=4$ . The network struggles to find an optimal sheaf when $d=2$ , leading to higher variance for the ER throughout the layers. For $d=4$ , the effective resistance is more uniform throughout the layers, while also achieving faster convergence.

Model	diam $\,\downarrow$	ecc $\,\downarrow$	sssp $\,\downarrow$
A-DGN	$1.151_{\scriptstyle\,\pm\,0.038}$	$4.981_{\scriptstyle\,\pm\,0.037}$	$1.176_{\scriptstyle\,\pm\,0.140}$
DRew	$1.243_{\scriptstyle\,\pm\,0.047}$	$4.651_{\scriptstyle\,\pm\,0.020}$	$1.279_{\scriptstyle\,\pm\,0.011}$
GraphCON	$2.969_{\scriptstyle\,\pm\,0.189}$	$5.474_{\scriptstyle\,\pm\,0.001}$	$5.734_{\scriptstyle\,\pm\,0.011}$
GCN	$3.832_{\scriptstyle\,\pm\,0.262}$	$5.233_{\scriptstyle\,\pm\,0.034}$	$2.102_{\scriptstyle\,\pm\,0.094}$
GCNII	$2.005_{\scriptstyle\,\pm\,0.093}$	$5.241_{\scriptstyle\,\pm\,0.030}$	$2.128_{\scriptstyle\,\pm\,0.429}$
GIN	$1.630_{\scriptstyle\,\pm\,0.161}$	$4.869_{\scriptstyle\,\pm\,0.092}$	$2.234_{\scriptstyle\,\pm\,0.271}$

Table 1: Performance (MAE) of FlatNSD. Darker green indicates lower error.

Figure 3: FlatNSD delays accuracy drop for all three topologies, demonstrating its ability of alleviating over-squashing.

Model	roman-empire	amazon-ratings	minesweeper	tolokers	questions
Hom level	0.05	0.38	0.68	0.59	0.84
GCN	73.69 ± 0.74	48.70 ± 0.63	89.75 ± 0.52	83.64 ± 0.67	76.09 ± 1.27
SAGE	85.74 ± 0.67	53.63 ± 0.39	93.51 ± 0.57	82.43 ± 0.44	76.44 ± 0.62
GAT	80.87 ± 0.30	49.09 ± 0.63	92.01 ± 0.68	83.70 ± 0.47	77.43 ± 1.20
GAT-sep	88.75 ± 0.41	52.70 ± 0.62	93.91 ± 0.35	83.78 ± 0.43	76.79 ± 0.71
GT	86.51 ± 0.73	51.17 ± 0.66	91.85 ± 0.76	83.23 ± 0.64	77.95 ± 0.68

Table 2: Performance comparison on datasets from Platonov et al. (2023) . AUROC is reported for minesweeper, tolokers and questions, accuracy is reported for the remaining datasets.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: The two examples from Black et al. [2023] . For these graphs, we have $R(a,b)=6$ (left) and $R(a,b)=\frac{10}{9}$ (right)

Method	Cora	Citeseer	Texas	Cornell	Wisconsin	Chameleon	Rel Avg Improv
GCN+NONE	86.7 ± 0.3	72.3 ± 0.3	44.2 ± 1.5	41.5 ± 1.8	44.6 ± 1.4	59.2 ± 0.6	-
GIN+NONE	77.5 ± 1.2	59.3 ± 1.3	46.4 ± 4.5	40.2 ± 4.8	42.1 ± 3.6	56.6 ± 0.8	-
SAGE+NONE	87.1 ± 0.1	75.0 ± 0.1	82.4 ± 0.3	73.2 ± 0.3	77.3 ± 0.9	66.1 ± 0.9	-
GCN+SDRF	86.3 ± 0.3	72.6 ± 0.3	43.9 ± 1.6	42.2 ± 1.5	46.2 ± 1.2	59.4 ± 0.5	+0.81%
GIN+SDRF	77.2 ± 0.8	59.9 ± 1.2	44.5 ± 3.9	38.2 ± 4.1	43.1 ± 1.6	58.1 ± 1.4	-0.57%
SAGE+SDRF	87.1 ± 0.7	74.1 ± 0.7	81.9 ± 2.9	72.4 ± 2.5	76.5 ± 1.8	65.2 ± 1.2	-0.88%

Appendix

Table 3: Performance of FlatNSD and GCN, GIN, and SAGE with different rewiring methods for both node and graph classification tasks. The method with the higher accuracy is highlighted in bold . DR requires graphs to have at least 3 nodes, but some graphs from Enzymes have only 2.

Figure 7: The figure shows the Spearman Correlation between Sheaf Effective Resistance and Train Accuracy on FlatNSD-SAGE. The correlation is weaker on these node classification tasks, aligning with the common understanding they are not a suitable setting for studying over-squashing.

Figure 8: Example of graph in the GridTransfer task. Two grids are linked by an edge connecting two nodes in a diagonal. The task is to transfer information from one of the nodes in the diagonal of the node in the path to the most-distant node in the other grid.

Figure 9: Accuracy of the models on the training set for the GridTransfer task. FlatNSD-SAGE is the only model to achieve accuracy $1$ until $r=7$ .

Figure 10: Log-Dirichlet Energy on the graph classification tasks of GCN and FlatNSD ${}_{\text{GCN}}$ . The high Dirichlet Energy presented by FlatNSD-GCN against the low Dirichlet Energy presented by GCN is sign that FlatNSD alleviates over-smoothing even in datasets more strongly dominated by over-squashing.

Figure 11: FlatNSD accuracy decreases only after longer distances from source to target, in comparison with GAT, GCN, GIN, and SAGE. Moreover, $d=4$ presents better performance than $d=2$ , suggesting the importance of $d$ for tasks sensitive to over-squashing.

Figure 12: Spearman Correlation between total sheaf effective resistance and accuracy in TreeNeighborsMatch on each layer across the problem radius $2\leq r\leq 8$ (left to right).

Figure 13: Spearman Correlation between total sheaf effective resistance and Jacobian norm for the TreeNeighborsMatch task on each layer across the problem radius $2\leq r\leq 8$ (left to right).

Panel of Table 4 — Table 4: Model hyperparameter configurations used across all datasets. The Node and Graph Classification columns refer to Figure 5 , the TreeNeighborsMatch column refers to Figure 1 , and the Heterophilic Graphs column refers to Table 2 .

Method	Cora	Citeseer	Texas	Cornell	Wisconsin	Chameleon	Enzymes	IMDB	Mutag	Proteins
GCN+SDRF	926.86	815.83	640.10	676.62	676.62	2087.36	2502.20	2307.62	710.50	3598.63
GCN+FOSR	945.13	825.15	522.83	677.56	677.56	2158.64	2601.29	2319.26	760.12	5962.85
GCN+BORF	1082.56	835.79	775.45	785.78	727.22	2093.88	4213.78	6410.12	1216.25	7330.80
GCN+DR	920.43	813.23	641.02	697.87	666.79	2148.66	-	2339.10	730.28	3637.15
GCN+GTR	898.48	791.14	638.70	710.84	647.71	2117.94	2589.34	2247.56	736.23	4023.95
GCN+LASER	1150.83	820.52	609.81	746.45	786.21	2143.54	2633.41	2296.16	741.60	4370.87

Appendix

Table 5: Total runtime in seconds of FlatNSD and GCN with different rewiring methods for both node and graph classification tasks. DR requires graphs to have at least 3 nodes, but some graphs from Enzymes have only 2 nodes.

Parameter	Node Classification	Graph Classification
sheaf dimension	4	4
# layers	2	2
# hidden channels	32	64
GNN architecture	GCN	GCN
# of GNN layers	5	5
GNN dimension	32	32

Appendix

Table 6: Model parameters configurations used on runtime comparison experiment.

Explore similar work

Understanding over-squashing and bottlenecks on graphs via curvature
Nov 29, 2021Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain +2Graph Rewiring Over-Squashing
University of Oxford · Imperial College London · Twitter
Demystifying Oversmoothing in Sheaf Neural Networks: An Index-Theoretic Criterion
Aug 17, 2026Junwen Dong, Yuhan Peng, Hao Li +2Sheaf Neural Networks Graph Neural Networks
Department of Mathematics, Faculty of Science National University of Singapore Singapore · School of Physical and Mathematical Sciences Nanyang Technological University Singapore
Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing
Mar 12, 2026Bertran Miquel-Oliver, Manel Gil-Sorribes, Victor Guallar +1Graph Neural Networks Graph Rewiring
Barcelona Supercomputing Center (BSC), Barcelona, Spain · Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Barcelona, Spain · Nostrum Biodiscovery, Barcelona, 08029, Spain +1

Nov 29, 2021J/K move · Enter open · S save

Understanding over-squashing and bottlenecks on graphs via curvature

Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong+1

University of Oxford · Imperial College London · Twitter

Graph Rewiring Over-Squashing Message Passing Neural Networks

Open paper AskPDF arXiv

Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of

k

-hop neighbors grows rapidly with

k

. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.

Abstract

Explore similar work

Understanding over-squashing and bottlenecks on graphs via curvature

Demystifying Oversmoothing in Sheaf Neural Networks: An Index-Theoretic Criterion

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