Understanding over-squashing and bottlenecks on graphs via curvature

Jake Topping; Francesco Di Giovanni; Benjamin Paul Chamberlain; Xiaowen Dong; Michael M. Bronstein

stat.MLNov 29, 2021

Understanding over-squashing and bottlenecks on graphs via curvature

Authors: Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein

Organizations: University of Oxford · Imperial College London · Twitter

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Top: evolution of curvature on a surface may reduce the bottleneck. Bottom: this paper shows how the same may be done on graphs to improve GNN performance. Blue/red shows negative/positive curvature.

Panel of Figure 2 — Figure 2: Different regimes of curvatures on graphs analogous to spherical (a), planar (b), and hyperbolic (c) geometries in the continuous setting.

Figure 3: 4-cycle contribution.

Graph $G$		$\text{Ric}_{G}$
Cycles	$C_{3}$	$\frac{3}{2}$
	$C_{4}$	1
	$C_{n\geq 5}$	0
Complete $K_{n}$		$\frac{n}{n-1}$
Grid $G_{n}$		0
Tree $T_{r}$		$\frac{4}{r+1}-2$

Table 1: Examples of the Balanced Forman curvature.

	Cornell	Texas	Wisconsin	Chameleon	Squirrel	Actor	Cora	Citeseer	Pubmed
$\mathcal{H}(G)$	0.11	0.06	0.16	0.25	0.22	0.24	0.83	0.71	0.79
None	$52.69\pm 0.21$	$61.19\pm 0.49$	$54.60\pm 0.86$	$41.33\pm 0.18$	$30.32\pm 0.99$	$23.84\pm 0.43$	$81.89\pm 0.79$	$72.31\pm 0.17$	$78.16\pm 0.23$
Undirected	$53.20\pm 0.53$	$63.38\pm 0.87$	$51.37\pm 1.15$	$42.02\pm 0.30$	$35.53\pm 0.78$	$21.45\pm 0.47$	-	-	-
+FA	$\bm{58.29\pm 0.49}$	$\bm{64.82\pm 0.29}$	$55.48\pm 0.62$	$42.67\pm 0.17$	$36.86\pm 0.44$	$24.14\pm 0.43$	$81.65\pm 0.18$	$70.47\pm 0.18$	$\bm{79.48\pm 0.12}$
DIGL (PPR)	$58.26\pm 0.50$	$62.03\pm 0.43$	$49.53\pm 0.27$	$42.02\pm 0.13$	$33.22\pm 0.14$	$24.77\pm 0.32$	$\bm{83.21\pm 0.27}$	$\bm{73.29\pm 0.17}$	$78.84\pm 0.08$
DIGL + Undirected	$\bm{59.54\pm 0.64}$	$63.54\pm 0.38$	$52.23\pm 0.54$	$42.68\pm 0.12$	$32.48\pm 0.23$	$25.45\pm 0.30$	-	-	-

Table 2: Experimental results on common node classification benchmarks. Top two in bold.

	DIGL	SDRF
Cornell	$351.1\%$ / $0.0\%$	$7.8\%$ / $33.3\%$
Texas	$483.3\%$ / $0.0\%$	$2.4\%$ / $10.4\%$
Wisconsin	$300.6\%$ / $0.0\%$	$1.4\%$ / $7.5\%$
Chameleon	$336.1\%$ / $11.8\%$	$5.6\%$ / $5.6\%$
Squirrel	$73.2\%$ / $66.4\%$	$4.2\%$ / $4.2\%$
Actor	$8331.3\%$ / $0.0\%$	$1.9\%$ / $3.0\%$

Table 3: % edges added / removed by method.

Panel of Figure 4 — Figure 4: Comparing the degree distribution of the original graphs to the preprocessed version. The x-axis is node degree in $\text{log}_{2}$ scale, and the plots are a kernel density estimate of the degree distribution. In the captions we see the Wasserstein distance $W_{1}$ between the original and preprocessed graphs.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Comparing the degree distribution of the original graphs to the preprocessed version. The x-axis is node degree in $\text{log}_{2}$ scale, and the plots are a kernel density estimate of the degree distribution. In the captions we see the Wasserstein distance $W_{1}$ between the original and preprocessed graphs.

Figure 6: Rewiring of the Cornell graph. Left-to-right: original graph, DIGL, and SDRF rewiring. Edges are colored by curvature; nodes are colored by the maximum absolute entry of a trained 2-layer GCN’s Jacobian between the GCN’s prediction for that node and the features of the nodes 2 hops away in the original graph. SDRF homogenizes curvature and so lifts the upper bound on the Jacobian from Theorem 4 . DIGL also does to an extent, though at the expense of preserving graph topology.

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay
Cornell	0.3060	1	128	0.0082	0.1570
Texas	0.2346	1	128	0.0072	0.0037
Wisconsin	0.2869	1	64	0.0281	0.0113
Chameleon	0.3300	2	128	0.0230	0.0001
Squirrel	0.7236	3	32	0.0293	0.0129
Actor	0.2294	2	128	0.0102	0.0763

Appendix

Table 4: Hyperparameters for GCN with no preprocessing (None).

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay
Cornell	0.6910	1	64	0.0185	0.0285
Texas	0.2665	1	128	0.0069	0.0035
Wisconsin	0.2893	2	128	0.0142	0.0001
Chameleon	0.7546	3	16	0.0219	0.0004
Squirrel	0.6120	2	128	0.0266	0.3935
Actor	0.5249	3	128	0.0179	0.4875

Appendix

Table 5: Hyperparameters for GCN with the input graph made undirected (Undirected).

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay
Cornell	0.2643	1	128	0.0216	0.0760
Texas	0.2207	1	128	0.0102	0.4450
Wisconsin	0.2613	3	64	0.0057	0.0131
Chameleon	0.4524	1	64	0.0097	0.0197
Squirrel	0.3697	3	64	0.0171	0.0670
Actor	0.7800	2	128	0.0078	0.0134

Appendix

Table 6: Hyperparameters for GCN with the last layer made fully connected (+FA from Alon and Yahav (2021) ).

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay	$\alpha$	$k$	$\epsilon$
Cornell	0.6294	1	64	0.0134	0.0258	0.1795	64	-
Texas	0.2382	2	128	0.0063	0.0153	0.0206	32	-
Wisconsin	0.2941	1	128	0.0083	0.0226	0.1246	-	0.0001
Chameleon	0.4191	1	128	0.0052	0.0001	0.0244	64	-
Squirrel	0.6844	1	128	0.0056	0.4537	0.0395	32	-
Actor	0.3008	1	128	0.0163	0.1545	0.0656	-	0.0003

Appendix

Table 7: Hyperparameters for GCN with DIGL preprocessing, or Graph Diffusion Convolution with PPR kernel (DIGL). Descriptions for

\alpha

k

and

\epsilon

can be found in Klicpera et al. (2019) .

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay	$\alpha$	$k$	$\epsilon$
Cornell	0.6294	1	64	0.0134	0.0258	0.1795	64	-
Texas	0.2382	2	128	0.0063	0.0153	0.0206	32	-
Wisconsin	0.2941	1	128	0.0083	0.0226	0.1246	-	0.0001
Chameleon	0.4191	1	128	0.0052	0.0001	0.0244	64	-
Squirrel	0.6844	1	128	0.0056	0.4537	0.0395	16	-
Actor	0.3008	1	128	0.0163	0.1545	0.0656	16	-

Appendix

Table 8: Hyperparameters for GCN with DIGL preprocessing followed by symmetrizing the graph diffusion matrix (DIGL + Undirected).

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay	Max iterations	$\tau$	$C^{+}$
Cornell	0.2411	1	128	0.0172	0.0125	135	130	0.25
Texas	0.5954	1	128	0.0278	0.0623	47	172	2.25
Wisconsin	0.6033	1	128	0.0295	0.1920	27	32	0.5
Chameleon	0.5354	1	128	0.0170	0.3422	699	34	39.25
Squirrel	0.6503	1	32	0.0287	0.0163	2742	61	0.5
Actor	0.6963	1	64	0.0110	0.0174	3823	223	7.37

Appendix

Table 9: Hyperparameters for GCN with SDRF preprocessing (SDRF). Max iterations,

\tau

and

C^{+}

are the SDRF parameters described in Algorithm 1 .

Dataset	Dropout	Hidden depth	Hidden dimension	Learning rate	Weight decay	Max iterations	$\tau$	$C^{+}$
Cornell	0.2911	1	128	0.0056	0.0336	126	145	0.88
Texas	0.2160	1	64	0.0229	0.0137	89	22	1.64
Wisconsin	0.2452	1	64	0.0113	0.1559	136	12	7.95
Chameleon	0.4886	1	32	0.0268	0.4056	2441	252	2.84
Squirrel	0.3079	1	32	0.0299	0.0158	1396	436	5.88
Actor	0.3424	1	64	0.0129	0.0126	3249	106	7.91

Appendix

Table 10: Hyperparameters for GCN with the input graph made undirected followed by SDRF preprocessing (SDRF + Undirected).

Component	Specification
Architecture	x86_64
CPU	40x Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz
GPU	4x GeForce RTX 3090 (24268MiB/GPU)
RAM	126GB
OS	Ubuntu 20.04.2 LTS

Appendix

Table 17

Explore similar work

Jul 24, 2026cs.LG

Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature

Curvature notions on graphs, particularly Ollivier-Ricci and Forman, have emerged as powerful tools for addressing fundamental issues in Graph Neural Networks (GNNs) such as oversmoothing and oversquashing, but rely almost exclusively on local edge-level comparisons and therefore fail to certify how information actually propagates over long distances. We introduce Entropic Curvature, a global, transport-based curvature obtained by extending the Lott-Sturm-Villani framework to graphs through the displacement convexity of entropy along Wasserstein geodesics. We define a tractable Weak Entropic Curvature proxy that lower-bounds the global entropic curvature, and from it derive (i) a Poincare-type inequality controlling oversmoothing, (ii) a transport-entropy generalization bound, and (iii) an expansion paradox proving that sparsity, strong spectral expansion, and positive entropic curvature cannot coexist in large graphs, unifying oversmoothing and oversquashing as opposite ends of a single curvature spectrum. We translate the theory into three practical mechanisms, the E-Gate aggregator, the ENT structural encoding, and Midpoint-Completion Rewiring (MCR), and benchmark them against SDRF, FoSR, BORF, LCP, and Graph Ricci Flow on six node-classification benchmarks, and graph-classification.

Rachid Caich, Yassine Abbahaddou

LIX, École Polytechnique IP Paris Palaiseau, France

Graph Neural Networks Local Curvature

Ask PDF

Jun 19, 2026cs.LG

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

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.

Hugo Attali, Rachid El Jouhri

Université Sorbonne Paris Nord, CNRS, LIPN, France

Inhomogeneous Random Graphs Graph Neural Networks Local Curvature Raman

Ask PDF

May 1, 2026cs.LG

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

Graph Neural Networks are powerful models for learning from graph-structured data, yet their effectiveness is often limited by two critical challenges: over-squashing, where information from distant nodes is excessively compressed, and over-smoothing, where repeated propagation makes node representations indistinguishable. Both phenomena stem from the interaction between message passing and the input topology, ultimately degrading information flow and limiting the performance of GNNs. In this survey, we examine graph rewiring techniques, a class of methods designed to modify the graph topology to enhance information propagation in GNNs. We provide a comprehensive review of state-of-the-art rewiring approaches, delving into their theoretical underpinnings, practical implementations, and performance trade-offs.

Hugo Attali, Nathalie Pernelle, Davide Buscaldi +1

Universit´e Sorbonne Paris Nord, CNRS, LIPN · Universit´e Paris-Saclay, CentraleSup´elec, Inria

Graph Neural Networks Inhomogeneous Random Graphs Communication Topologies Smoothing

Ask PDF