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

Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature
Jul 24, 2026Rachid Caich, Yassine AbbahaddouGraph Neural Networks Local Curvature
LIX, École Polytechnique IP Paris Palaiseau, France
Ramanujan Graph Rewiring with Non Negative Resistance Curvature
Jun 19, 2026Hugo Attali, Rachid El JouhriInhomogeneous Random Graphs Graph Neural Networks
Université Sorbonne Paris Nord, CNRS, LIPN, France
Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey
May 1, 2026Hugo Attali, Nathalie Pernelle, Davide Buscaldi +1Graph Neural Networks Inhomogeneous Random Graphs
Universit´e Sorbonne Paris Nord, CNRS, LIPN · Universit´e Paris-Saclay, CentraleSup´elec, Inria

Jul 24, 2026, cs.LGJ/K move · Enter open · S save

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

Rachid Caich, Yassine Abbahaddou

LIX, École Polytechnique IP Paris Palaiseau, France

Graph Neural Networks Local Curvature

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

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