Rethinking the Gold Standard: Why Discrete Curvature Fails to Fully Capture Over-squashing in GNNs?
Authors: Jialong Chen
Bowen Deng
Zibin Zheng
Chuan Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Discrete Curvature
Over-squashing
GNNs
Primary area: learning on graphs and other geometries & topologies
TL;DR: high negative curvature is not a necessary condition for over-squashing

Abstract: As a topological invariant for discrete structures, discrete curvature has been widely adopted in the study of complex networks and graph neural networks. A prevailing viewpoint posits that edges with highly negative curvature will induce graph bottlenecks and the over-squashing phenomenon. In this paper, we critically re-examine this view and put forward our central claim: **high negative curvature is a sufficient but not a necessary condition for over-squashing**. We first construct a family of counterexamples demonstrating the failure of discrete curvature, where some edges are severely squashed, but the curvature still appears positive. Furthermore, extensive experiments demonstrate that the most commonly used discrete curvature measure --- Ollivier–Ricci curvature --- fails to detect as many as 30%~40% of over-squashed edges. To alleviate this limitation, we propose Weighted Augmented Forman-3 Curvature ($\mathsf{WAF3}$), which significantly improves the detection of over-squashed edges. Additionally, we develop a highly efficient approximation algorithm for $\mathsf{WAF3}$, enabling curvature computation on graphs with five million edges in only 23.6 seconds, which is 133.7 times faster than the existing algorithm with the lowest complexity for curvatures.

Published as a conference paper at ICLR 2026
RETHINKING THE GOLD STANDARD: WHY DISCRETE CURVATURE FAILS TO FULLY IN GNNs?
CAPTURE
Jialong Chen', Bowen Deng, Zibin Zheng, Chuan Chen
Sun Yat-sen University
1 cchenjlong7 @mail2..... sysu. edu. cn, Pchenchuan3mail. wys.eaaiillisslaa..........u sysu. edu. cn
ABSTRACT
As topological invariant for discrete structures, discrete curvature has been widely adopted in the study of complex networks and graph neural networks. A prevail- ing viewpoint posits that edges with highly negative curvature will induce graph bottlenecks and the over-squashing phenomenon. In this paper, we critically re- examine this view and put forward our central claim: high negative curvature is sufficient but not necessary condition for over-squashing. We first con- struct a family of counterexamples demonstrating the failure of discrete curvature, where some edges are severely squashed, but the curvature still appears positive. Furthermore, extensive experiments demonstrate that the most commonly used discrete curvature measure Ollivier-Ried curvature fails to detect many as 30% ~ 40% of over-squashed edges. To alleviate this limitation, we propose Weighted Augmented Forman-3 Curvature (WAF3), which significantly improves the detection of over-squashed edges. Additionally, we develop a highly efficient approximation algorithm for WAF3, enabling curvature computation with five million edges in only 23.6 seconds, which is 133.7 times faster than the existing algorithm with the lowest complexity for curvatures.
graphs
INTRODUCTION
In differential geometry, curvature is used to describe how volume grows within a local region and how geodesics diverge or converge. Discrete curvature naturally extends this concept to discrete structures, such graphs. In complex network analysis and graph deep learning, discrete curvature plays critical role. It is widely applied numerous downstream tasks, including key node identification (Farooq al., 2019), community detection (Park & Li, 2024; Sia al., 2019), clustering (Tian et al., 2025; Sun et al., 2023), sparsification (Zhang et al., 2023), and anomaly detection (Grover et al., 2025), among others. Among these, the idea of tackling the graph werrsquashing (Akansha, 2025) based on discrete curvature has been widely studied, with one of the most notable findings being that:
"Edges with high negative curvature are those causing the graph bottleneck and thus leading to the over-squashin phenomenon." " - Topping al. (2021)
This perspective has garnered significant attention within the community. It has spawned a consider- able body of follow-up research, including theoretical investigations into the relationship between over-squashing and curvature (Di Giovanni et al., 2023a; Nguyen et al., 2023), curvature- based graph rewiring techniques (Nguyen et al., 2023; Giraldo et al., 2023; Fesser & Weber, 2024), and curvature-inspired graph neural networks (Li et al., 2022; Sun et al., 2022; Fu et al., 2025).
Although the work of Topping al. (2021) has achieved remarkable success, subtle but important point is that they only established the sufficiency of highly negative curvature for over-squa while leaving its necessity unaddressed. To the best of our knowledge, this fundamental yet crucial issue has long been overlooked. In this paper, we investigate it for the first time and uncover a striking fact: the necessity does actually hold. In other words, there exist edges in graph datasets that suffer from severe over-squa but cannot be detected by curvature.
"Corresoonding author.

---

Published as a conference paper at ICLR 2026
In detail, our contributions organized into four interlocking parts:
New theoretical results (Section 3). We construct a family of counterexample graphs and prove that within them, there exist edges that, despite exhibiting severe werr-squshhnng still possess highly positive discrete curvature. Here, discrete curvature can be defined in eight popular ways, including Ollivier Ricci curvature (Ollivier, 2009) and Balanced Forman curvature (Topping et al., 2021), 1,, among others. Theorem implies that curvature may ignore some over-squashed edges, so highly negative curvature is not necessary condition for over-squashing.
New metric and extensive empirical evidence (Section 4). To answer the question of how many over-squashed edges in practical graph learning tasks are overlooked by curvature, we propose new metric: Missed Over-Squashing Ratio (MOSR). MOSR quantifies the proportion of over-squashed edges that are ignored by curvature. Extensive experimental results show that the MOSR of Ollivier Ricci curvature can exceed 30%, revealing a significant deficiency in one of the most widely used discrete curvature measures. Further experimental analysis provides insights into the underlying reasons why curvature fails to capture these edges.
New discrete curvature (Section 5). Based on the aforementioned analysis and experimental observations, we propose new discrete curvature definition called WAF3. Not only does WAF3 achieve a significantly lower MOSR value compared to other existing curvature definitions, but also maintains computational complexity on par with the most efficient one currently available.
New approximation algorithm (Section 6). Although WAF3 already boasts state-of-the computational complexity, it still faces scalability limitations when processing large-scale graphs. To address this, we propose an efficient approximation algorithm for WAF3 that further reduces the time complexity to linear level. This algorithm requires only 23.8 seconds to complete computations a graph containing five million edges, achieving a 133.7x speedup compared to exact computation.
In summary, our work is not only critical, demonstrating through both theory and experiments that curvature cannot fully capture the over-squashing in GNNs, but also constructive: we propose new metrics, curvature definitions, and approximation algorithms, significantly enhancing the applicability of curvature-based tools in graph learning.
2 PRELIMINARY
Message passing neural network (MPNN, (Gilmer et al., 2017; Kipf, 2016)) Consider a simple, connected, undirected graph G E) with node set of V and edge set E. We denote the adjacency matrix of G by A. Each node equipped with an initial feature vector (0) Rd, (W() E Rdixdr1) / is set of learnable parameters. The 1-th layer of MPNN is formalized as:
H ReLU (AH
where À = (D (D+1) + (D + 1 denotes the symmetrically normalized adjacency matrix and D denotes the degree matrix. H := " :.... ( " E xl denotes the collections of l-layer embedding of all nodes. In line with many previous works, we also introduce the following assumptions facilitate the analysis of the ReLU.
Assumption 1. (Di Giovanni al., 2023a; Kawaguchi, 2016; Xu al., 2018) All paths in the computation graph of the model are activated with the same probability of success
Discrete curvatures For any edge u ~ v in graph 9, the edge curvature Curv(u, v) measures the tightness of the connection between the first-order ego-graph of node u and the first-order ego-graph of node v. As shown in Table 1, there are multiple definitions for Curv. Regardless the specific definition, discrete curvature typically depends only tiny local neighborhood of the edge (except for the resistance curvature (Devriendt & Lambiotte, 2022)).
Over- ever-squashing In graph deep learning, message passing often compresses information from large neighborhoods into single topological structures (e.g.. nodes or edges). resulting in information loss and gradient issues known ovur-squa (Alon & Yahav, 2020), which has emerged challenge in modern graph models. The Jacobian norm between the feature of the input node and the embedding of the output node offers the most accurate measure of information flow, and thus the
key
2

---

Published as a conference paper at ICLR 2026
Table 1: We summarize all discrete curvatures defined on edges here. Curvatures defined on nodes (such Bakry-Emery-Riect (Mondal et al., 2024), combination (Kamtue, 2018), and node resistance (Devriendt & Lambiotte, 2022)) are not included. 1e is the uniform distribution of the first-order neighbors of u with restart probability a. W1 is the I-Wasserstein distance. {War} the pseudo- inverse of the weighted Laplacian matrix. du is the degree of node and d, V de == max (du, de). du A dg == min(dy, d.). Au, v) and (u, 2) denote the number of triangles and quadrangles containing the edge (u, v).. #8 v) denote the numbers of neighbors of u. forming 4-cycle based at the edge (u, v) without diagonals inside. r(u, v) is the maximal number of 4-cycles based at (u, v)
traversing common node. is the degree-weighting function.
Curvature
Delinition
Complexity
Ollivier ricci
1 Wi He)
0(1E)d max)
(Ollivier, 2009)
Lin-Lu-Yau
lim (1
Wi (g))(1
(Lin ct al., 2011)
Link resistance
(2 Lin M/u
Ejne Moz)/Wur
O((V)*)
(Devriendt & Lambiotte, 2022)
Balance forman
(Topping et al., 2021)
2 du
+ de
2
Mux) vd
Muau d,
O(18 (((E)dP..) (dPmax)
Balance Forman w/o 4-cycle
1 d.
+ t..
Aluei d.vd.
Alu.e) a_
O(1E) (maax)
(Tori ct al., 2024a)
Jost-I.uu Liu Forman
A(ur) du Val
+ - (1
1 du
Alua) Ma.o) dundd
O(1E (dmax)
(Jost & Liu, 2014)
du
du
a.va.
Augmented Forman-3
4 du - d + 32(u,)) v)
O(1E (dmax)
(Forman, 2003) Augmented Forman-4 (Forman, 2003)
4 du dy 3D(u, v) + (0,,))
O(1E ((1))d
Weighted AF-3 (Ours)
Exeray B(o) f(4) (EveNcwy/BO)) f(d.) Eieooy/(a)) f(a.)
1 d
0 (HE
severity of over-squashing. In Lemma 2, we establish a lower bound for the Jacobian norm when the degrees of the ends fixed and b. All proofs are provided in Appendix A.
Lemma 2 (Infimum of the over-squahhing). Let N,a, be positive integers. The set
G GN((s, a), (t, b)) denotes the collection of all simple undirected graphs G = (V, E) with [V] N such that there exist adjacent vertices 5,t e where deg(s) and deg(t) b. Assume an
L-layer MPNN in equation (1). Then:
Oh (L)
inf NEZt (tGx(
= (a,
Oh.
where = I1 wa/l wool
(1
b+T
(a+ (0+4))
DISCRETE CURVATURES FAIL TO FULLY CAPTURES OVER-SQUASHING
Since the Jacobian matrix norm is tightly coupled with the model and entails prohibitive computational costs, Topping et al. (2021) first proposed using discrete curvature as surrogate criterion for detecting over-squashing. However, through the following counterexamples and theorems, we demonstrate that discrete curvature is in fact not necessary condition for identifying ever-squashing.
Definition 3 (counterexample graph). Let the soruce node, the target node, N₂ (ulhsign the I-hop neighbor and N₂ (vshisisn.1sjgm the 2-hop neighbor set. The counterexample graph Im. is such a simple, connected and undirected graph that y = {s.t) U,, Nr and 3 == {(s.t) U & which E == {(s, u,) u,)sisn U ((t, 4shsss and E = ((us, sinnsisns
made
source
made
NLI
NU2
Figure 1: Example diagram of G5
3

---

Published as a conference paper at ICLR 2026
Theorem 4 (Discrete curvatures fail to fully to capture over-squashing). Consider an L-layer GCN as in equation (1). For the family of graphs & {9 m m.me with source-targel pairs (s, t), we have:
(
For any fixed n²,
- ÓL(N" + +1, + 1) at speed (mm when m - +o0.
ah.
If Curv is given by any of: a-Ollivier-Ricet curvature, Lin-La- Yau curvature, balanced Forman curvature (with/without 4-cycle), Jost-Liu curvature or augmented Forman-3/4 curvature, then there exist a > such that VG E 39 Curv(s, t) >c.
If Curv is defined as resistance curvature under symmetric normalized Laplacian, then for any fixed n", there exist m² and e 0, such that VG E {9 |n n", >> m²) Curv(s, t)
In simple terms, the above theorem states that in G m. as long m is large enough, there will be very severe over-squashing between source node and target node t. However, all discrete curvatures fail to identify this their values are all positive.
To understand this phenomenon, we need to keep in mind that the discrete curvature between (s, t) is essentially measure of how tightly connected the first-order neighbors of s are to the first-order neighbors of t (Chen et al., 2025). Furthermore, this "tightness" can usually be reflected in the number of triangles that (s participates in (Topping al., 2021; Jost & Liu, 2014; Forman, 2003). Since any edge (u, v) can form at most min(d, (d,, 1, - }} triangles, and in 9 (s, t) just reaches this upper limit (dg = d = n + and there are n triangles: any definition is almost always highly positive.
u, t, vi E [1, m)) Curv(s, t) under
On the other hand, in I when the information in node s propagates to node t, a considerable part of the propagation path needs pass through the nodes in An. However, each node in Mi is connected to m other nodes. Every time the propagation path passes through a node in Mi, the information in s "diluted" by m nodes. As m increases, the degree over-squashing between s and approaches its theoretical lower bound. Since almost all GNNs require at least two rounds of pressage-passingg discrete curvature that only considers first-order neighbors almost always insufficient to capture all potential over-squashing fully.
4 THE MISSED OVER- SQUASHING EDGES: HOW MANY AND WHERE
Since discrete curvature cannot fully identify over-squashing in theory, two other important questions arise: how many over-squashing edges ignored by curvature in practice? Moreover, where these ignored edges?
To answer the first question, first establish corresponding metrics. For any graph g E). we define the multiset := (e)u }}} as the collection of discrete curvature values for all edges in E. Let C_ {(cle < e C}} be the subset of negative curvature values. The function Percentile(C_, .q) returns the value below which % of the observations in C_ lie, for E [0, 100).
We then define:
E fc E C/Curv(e) < Percentile(C-..q)
Note that E, corresponds precisely the set of "edges with high negative curvature" mentioned by Topping et al. (2021). That is, the edges in Eg are those correctly identified as over-squashing by curvature. Here, q represents the threshold for classifying an edge as over-squashing; smaller g implies stricter criterion.
For an L-layer message passing neural network, let JacoNorm(u,e) == |0h h || denote the ground-truth measure of information squashing. Define J, == (u,)EE) JacoNorm v). We then introduce the Missed Over- Squrshqqashing Ratio (MOSR):
MOSR, := DiumEE Icur((u,))20 LnceNNor(u.v)s
E(W.y)EE 1 LacsNormuu"
In MOSR,, the numerator counts edges with non-negative curvature that are nevertheless over- squashed (i.e., JacoNorm v) Jq). which are thus ignored by curvature. The denominator counts all truly over-squashing edges (with Jg as the threshold). Therefore, MOSR, represents the proportion of over-squashing edges that are not identified by curvature.
4

---

Published as a conference paper at ICLR 2026
Table 2:
The values of MOSRjo and MSSR2s across different GNNs, curvatures, and datasets. Among these, the entry * -000/0110" in the first row and first column indicates that for Ollivier Ricci curvature, GCN, and Cora dataset, MOSR 0.030 and MOSR25 0.103. OOR denotes "Out of Resources", meaning the GPU memory consumption exceeds 24 GB or the running time surpasses 12 hours. NNE (No Negative-curvature Edge) indicates that | = 0 in this scenario.
Ollivier Ricci
Augmented Forman-3
Balauced Forman
GCN
GAT
SAGE
GCN
GAT
SAGE
GCN
GAT
SAGE
Cora
0300.103
185//224
.233/258
.01//027
.163.1700
.187/187
002/010
.155/217
.210/.245
Citeseer
.119/151
.172/277
.286/331
008/034
.39//239
289/3307
000/0014
.88/.120
.219/3224
Pubmed
026/.073
.087/.090
.0971.977
.000000
.091.009
.1 010/111
00000000
.074/108
.144/142
Computers
.52/.352
.353/353
.353/3353
.003/0066
.011/011
.011/011
00000005
.010/012
.011/0122
Photo
503/.503
.503/503
,503/.503
.042/.033
.455.045
.045/045
.041/004
.045/046
.045/.066
CS
057/.086
.113/.128
.1231.126
.017/0330
074/0755
0755/075
00110012
.411/073
.080/.991
Physies
0OR
OOR
OOR
006//027
.52//056
OOR
.01//012
.055/065
OOR
WikiCS
472/.473
4734473
.773/473
250//249
.2491.249
.249/249
.245/224
.246/2245
.250/.246
CoraMM
204/.204
217//235
2210/225
025//039
096/.098
0090 101
.066/109
.126/.139
.126/1177
Cull
OOR
OOR
OOR
OOR
OOR
OOR
0OR
OOR
OOR
DBLP
072/080
084/.089
086/.096
003/:004
030V.033
0366/038
007/001
.338/052
048/0065
Cornell
00000000
33313395
.396/4110
.00/0000
.136/1188
.167/.158
.000.364
.335/.370
.373/.390
Texas
093/.174
.388/308
.308/.08
00000000
.112/.116
.126/.130
.000.254
.385/3300
.342/.366
Wisconsin
000//24
.334/334
.332/.342
.00V0000
.113/.118
.128/.135
.175/.191
.2571.556
.2211
Chameleon
6431.643
.643/643
.431.643
.115/.116
.125/.125
.129/.129
.010/.200
.131/.155
.136/.18
Squirrel
7231.723
.723/.23
.723/723
1377.137
.133/133
.133/.133
.130/.129
.130/.130
.132/132
Roman-empire
014/.097
276/ 446
,4971,547
001/.080
.300,520
5241.524
00000000
.247/.532
695/.753
Tolokers
6571.657
OOR
.657.657
0022/002
OOR
.003/
,003/0003
OOR
003/.003
Questions
0OR
OOR
OOR
000/0002
008/.008
010//010
0048/074
.083/085
1003/1100
Amazon-ratings
639/.655
524//638
6381/653
2228/285
.292/2997
.09/.310
.335/378
.117/.275
.357/337
Minesweeper
NNE
NNE
NNE
502/.502
.502/.502
5022,502
.502/.502
.502/5002
.502/5502
Average
.271/3077
.336/.366
.36//399
.0671.099
.148/115
.160/.161
.078/.124
.161/196
.210V.227
As shown Table 2, we comprehensively report the results of MOSR and MOSR25 along with their average values across three of the most commonly used curvatures, three of the most widely adopted graph neural networks, and 21 datasets, amounting to a total of 350 numerical results.
Observation 1: At q 10, discrete curvature systematically ignored 6.7% 38.6% of over-squashing edges. When q increased to 25, this range increased to 7.9% ~ 39.8%. This indicates that discrete curvature fails to identify over-squashing phenomena perfectly.
Observation 2: Across different datasets, discrete curvature generally demonstrates supe- rior performance on GAT compared to GraphSAGE, while GCN consistently achieves the optimal results. This indicates that model architecture significantly influences the accurate identification of over-squashing edges.
The Ollivier Ricci curvature, with its computational complexity as high O(EE|dm missed the most significant number of over-squashing edges, whereas the Augmented Forman-3 curvature - the one with the lowest complexity - achieved the best average performance. Therefore, recommend prioritizing the latter in GNNs.
Observation 3:
To answer the second question, we introduce edge betweenness (Freeman, 1977; Girvan Newman, 2002). According to Girvan & Newman (2002), the edge betweenness of an edge is defined as:
Ouv(e)
Between
Tuv
V
Where Tue denotes the total number shortest paths between nodes u and v; (e) denotes the number of those shortest paths that pass through edge Simply put, high Between(e) usually means that edge e forms a bridge between two clusters, and a low Between(e) indicates that e is inside cluster. We further introduce the following three statistics characterize the average edge
5

---

Published as a conference paper at ICLR 2026
Table The model is fixed GCN, @ set to 25, and we report Betwlden, BetwAll, and Betwigno on three curvature definitions and 21 datasets, respectively. NIE (No Ignored Edge) means no edges ignored by curvature, so Betwigno cannot be calculated.
Ollivier Ricel
Augmented Forman-3
Balanced Forman
Betwiden
BetwAll
Betwigna
Betwiden
BetwAAl
Betwigno
Betwiden
BetwAll
Betwigna
x 10"
3.69
10*
7.58
10"
10
2.36 10"
Citeseer
109
4.80
10
1.2
109
10
108
10a
1.16x
10
10
1.09 10
Pubmed
6.76 x 10"
2.78 10'
1.36
10
4.74
10*
2.78 10"
2.02 10
5.93
10"
2.78 10*
NTE
Computers
4.32 x 10
1.23 10
2.98
102
244
10
10a
1.79
102
2.19
102
1.23
10
2.70 10"
Photo
4.02 10a
9.53 10
2.81
10a
1,50
10
9.53 10"
2.36 10#
1.91
10a
9.53 10"
3.31 10"
CS
2 x 10"
1.11 x 10
2.19 10
2.22
10*
1.11
10
1.39
10
2.35 x 10#
1.11 104
1.51 10
Physies
0OR
OOR
OOR
1,86
101
1.24 10"
1.43
10*
2.30 x 10
1.24 x 10'
1.03 x 10"
WIkiCS
3.36 x 10
8.94 x 10"
1.77 10"
3.01 10"
8.91 10"
7.91 10'
1.82 x 10"
8.94 x 10
1.81 x 10"
Cora_MI.
7.10 x 10"
2.55 10
7.96 x 10
5.24 102
2.55 10"
2.54 10"
5.64 x 10a
2.55 x 10
1.24 10"
Cora Full
DOR
OOR
OOR
OOR
OOR
OOR
OOR
OOR
OOR
DBLP
3.79 x 10"
1.64 x 10'
4.53 10a
2.56 10"
L.64 10"
1.02 x 10*
2.89 10"
1.64 x 10*
9.19 10
Cornell
5.37 x 10
1.92 x 102
NIE
3,30 10"
1.92 10"
NIE
4.71 x 10
1.92 x 10
1.82 10"
Texas
4.08 x 10a
1.81 10
8.45 10a
3.10
10a
1.81 10"
NIE
3.44 x 10
1.81 x 10a
1.82 x 10P
Wisconsia
5,93 x 10P
2:27 x 10a
1.32
102
4.63
2.27
NIE
4.21 x 102
2.27 x 10
1.17 x 10P
Chameleon
1.66 x 10a
2.94
9.02
7.25
2.94
4.72 x 102
2.94 x 10P
6.64 10
Squirrel
1.63 x 10a
2.31
10
6.54 10
3.40
2.31
x
5.44 x 102
x 10
6.95 x 10'
Roman-empire
x 107
1.82
7.48
10
x 107
Tolokers
161x 10
3.71 10
1,39 10?
7.76 10
108
10
10
Questions
OOR
OOR
5.37 10
10*
109
x 10
10
Amazon-ratings
3.23 10
5:23 10"
1.13 10
1.12 10
5.23 10"
10'
1.90 10
5.23 10
1.7 x 10
Minesweeper
NNE
NNT
NNE
NNE
NNE
NNE
NNE
NNE
NNE
betweenness of different types of edges:
Betwiden, ==
Mean MeennBetween(ee)) Ve E Eg),
BetwAll := (eeneBeeween(()) Ve E E),
(5)
Betwigno, == Mean(Between(e)) Ve E E, Curv(e) > 0, JacoNor(e)) < Jy).
BetwAll indicates the average betweenness of all edges, while Betwlden and Betwlgno represent the average betweenness of identified or ignored edges by curvature, respectively. See Table 3 for results.
In most cases, there is BetwAll > within cluster, there may be over-squashing edges, and discrete curvature ignores them systematically.
Observation 4:
Betwlgno. This means that even
Observation In most cases, there Betwiden >> BetwAll, which indicates that discrete curvature can only identify over-squashing edges that appear as "bridges" between clusters.
Previous studies have often, perhaps unconsciously, conflated terms such as "over-squashing" and "bottleneck" with "bridge edges connecting clusters" (a classical example can be found in Figure I of Topping al. (2021)). However, our experimental results demonstrate that bottlenecks and over- squashing can also arise within clusters. The neglect of such edges by discrete curvature is precisely the key reason why curvature cannot serve as a necessary condition for detecting over-squashing In this sense, curvature is not the gold standard for identifying over-squashing, but rather the gold standard for identifying bridge edges between clusters.
5 WEIGHTED AUGMENTED FORMAN-3 CURVATURE
In this section, we discuss how to leverage previous results to enhance existing discrete curvatures. According to the re- sults in Table 2, we consider improving augmented Forman-3 curvature, which has the lowest time complexity and the best actual performance. We first provide equivalent form for AF3 (Equation 6), where and o are any pair of adjacent nodes in graph, (()) {ijé v, V} represents all first-order
AF3(u.)) #Blue #Green Figure 2: Calculation of AF3.

---

Published as a conference paper at ICLR 2026
Table 4: The values of MOSR10 and MOSRgs across different GNNs and datasets when the discrete curvature si set to WAF3 and (() = 11 + 2).
GCN
GAT
SAGE
GCN
GAT
SAGE
Cora
.000/001
.157/.166
.183/1833
Citeseer
020/.041
210//211
.279/2880
Pubmed
.001/0022
.013/0014
.015/0155
Computers
.002/0005
.011/011
.011/011
Photo
021//024
.027/0077
.027/027
CS
.009/004
.075/0755
.076/.076
Physics
020/.040
.055/0588
OOR
WikiCS
.140/141
.144/1144
.144/.144
Cora ML
025/.056
.098/103
.103/1103
DBLP
.20//022
.052/.055
.057/.599
Cornell
0000/000
.116/.122
.138/.143
Texas
.000/.000
.134/.139
.143/.149
Wisconsin
00000000
.108/.177
.122/.134
Chameleon
.065/.066
.075/.076
.079/.79
Squirrel
039//039
.041/001
.041/0041
Roman-empire
.000/.001
.351/.431
.433/453
Tolokers
0022/002
OOR
003//003
Questions
.003/.011
.023/.024
.025/.025
Amazon-ratings
.159//218
.223/2211
245/.246
Minesweeper
.191/.192
.192/.192
.192/.192
Average
.036/.045
.111/.18
.123/.144
neighbors of and B(v) = (w)) U {v} represents all nodes within distance of from The detailed derivation is provided Appendix A.
AF3 r) dg d. ()) [B(u) n (BO))
(IW())/B(O) + W(t)/B())
(6)
Nomber nodes triangles
Number of modes triangles
According to Equation 6, AF3 actually calculates the difference between the number of nodes that make up the triangle and the number of remaining first-order neighbors (Figure 2). However, as discussed in Chapter 3, triangle counting ignores the degree of nodes; however, high-degree nodes actually do little to enhance the information flow from the source node to the target node, Therefore, we propose weighted augmented Forman-3 curvature (WAF3). WAF3 weights each node's contribution to the curvature based on its degree by a function f R + IR, which corrects for the influence of high-degree nodes. Obviously, AF3 is special case of WAF3 when f =
WAF3,
f(d:) (EB()))((()
Σ
Σ
f(d)) +
Σ s(d.)
(BN(U))B(O))
(EN(U))B(u)
Theorem 5 (WAF3 gets rid of counterexamples) Consider an L-layer MPNN as equation (1). Suppose [(+00) 0+. For the family of graphs & = (s, t). There dose not exist > 0 such that for every G E I, WAF3(s, t) >
with source-target pairs
The above theorem clearly shows the difference between WAF3 and all other discrete curvatures, namely correcting the inappropriate contribution of high-degree nodes - only requiring the weight function to satisfy f(-2o) 0 Furthermore, AF3 in Table 4, where we set to be a GCN-style weighting function, i.e., f = 1/(1 + x), which satisfies the condition required in Theorem 5.
report the MOSR1o and MOSR values of
Observation 6: The MOSR values of WAF3 range from 3.6% to 12.3%, while the MOSRgs values range from 4.5% to 13.4%. This is further reduction of more than 3% compared to the best-performing AF3 in Table 2.
ACCELERATING WAF3 VIA MINHASH
In terms of complexity, WAF3 has a time complexity of O(EE)mmma while WAF3 has O d
Complex(f)) f), in which the factor dmax comes from the intersection of sets (B(u) n B(v)). When Complex(f) = O(1) (such as the function f = 1/(1 + x) we use), the complexity of WAF3 is equivalent to that of AF3, which is the curvature with the lowest complexity present (Table 1).
7

---

Published as a conference paper at ICLR 2026
Algorithm I Approximating WAF3
1: Input: Graph (V,E), weighting function f, number of hashing H.
2: for E do
3: u' = f(du):
O(V Complex(
4: end for
5: for
do
6: Sy = fe'le E N(u)::
7: u" (Sm(Su):
((2E))
8: end for
9: for (u, E do
10: Jaccard (V()),N(w)) z Minhash(S....) S.) (loffe, 2010);
(H > ((E))
11: Compute WAF3y(u, 8) via Theorem 6;
12:
end for
However, this is still unacceptable in large graphs, since dmax usually also grows with the number of nodes in graphs. This dilemma has largely hindered the promotion of curvature tools to graph learning. To solve this problem, we first prove that an equivalent form of WAF3 is as follows:
Theorem 6 (Equivalent form of WAF3 based on Jaccard similarity). Let weighted Jaccard Exextonooo) f(d) then the following equation holds: Eiex(ajuNto) [(d.))
similarity (N
WAF3, -2) + 2f(r)
Σ s(d.+ (EN(U)
Σ ((.)) KEN(()
1 (
Theorem 6 converts the time-consuming intersection operation into a weighted Jaccard similarity operation. Fortunately, the acceleration algorithm of the latter has been widely studied (Wu et al., 2020). In particular, class of algorithms called weighted Minhash (Manasse, 2010; loffe, 2010; Wu al., 2016; 2017; 2018) can reduce the complexity of computing Jaccard similarity to constant (O(H)) by sampling H hash functions, where the larger H is, the smaller the approximation error is. At this point, the overall complexity of WAF3 will be further advanced to O( &l), reaching its theoretical lower bound (because it has constant complexity for each edge).
Two experiments are conducted to evaluate the practicality of Algorithm First, in order verify the compu- tational efficiency, we randomly gen- erated Rédōs-Rényi random graphs (ERDdS & R&wi, 1959) with the number of nodes being (10*,2 2 x 10 x 104, 4 10 5 10a, 109),
O
WA
hashs)
3142x
WA hashs)
2500
WA bashs)
1 paads L'EET
WAF3
2000
Time (s)
ORC
1500
where the connection probability between any 0,0005, which is comparable to the sparsity level of most commonly used graph datasets. Under the constraint of maximum GPU memory of 24GB, the running times of different curva- ture computations are reported Fig- ure 3.
nodes was set to
500
23.5s
10
3wieer 4.5% 2x:00"
10"
4x 10" to
S.. to
2x 2x10"
Graph size (Num node & Num edge)
Figure 3: Computation time of different discrete curvatures with p 0.0005. 10a-10s nodes, and 24 GB GPU limit. Here, WAF3 denotes the WAF3 approximation with different number of hashing (Algorithm 1).
Secondly, we evaluate whether the ap- proximation error is within accept- able range. is worth noting that, for most curvature- based graph learning methods, the relative ordering of curvature values is often more critical than their absolute magnitudes (for example, in rewiring-bai based approaches (Nguyen et al., 2023; Giraldo et al., 2023; Fesser &
8

---

Published as a conference paper at ICLR 2026
1.00
Kendall Tau-b
0.97
0.94
0.91
100
hashs
100 hashs (Avg.)
0.88
1000
hashs
1000 hushs (Avg.)
10000
bashs
10000 hashs (Avg.)
0.85
Cora
Citeaeer
Pabmed
Computers
Photo
CS
Physies
Wikics
Cora. ML
Cora, Full
DBLF
Cornell
Toxas
Wisconsin
Chameleon
Squirrel
Roman-ompie
Tolokers
Questions
Amazon-ratings
Average
Figure 4: The Kendall Tau-b similarity between WAF3 and WAF3 values calculated for different datasets when H is 100, 1000, and 10000. The average value is also reported.
Weber, 2024), typically only the edges with the smallest curvature are considered). Based on this observation, we report in Figure 4 the Kendall Tau-b similarity (Kendall, 1938) between WAF3 and its approximated values. This rank-based metric measures the consistency between two sequences, with higher values indicating greater agreement in their orderings.
Observation 7: When the random graph scales to 10 nodes and 5 x 10th edges, ORC (O(E)) and BFC (O((E) can no longer complete the computation within tolerable time. WAF3 ((()) [maxx) also requires over 3,000 seconds. However, the Minhash- based approximation algorithm has significant acceleration effect, especially when H 100, with speedup of 133.7 times.
Observation 8: Even when = 100, the average Kendall tau-b similarity across all datasets is approximately 95%. This means that only (100% 95%) /2 2.5% of edge pairs are misordered. When H = 1000, the similarity rises to over 98%. On this basis, the
similarity improvement for 10, 000 less than 1%, a significant marginal benefit.
According to Figure 3, for large-scale graphs, even the exact computation of the least complex curva- ture becomes prohibitively expensive. However, our proposed algorithm facilitates the emergence of a new paradigm for curvature-based learning: first, a small subset of candidate edges is identified through an approximation algorithm, and then the final set of highly negatively curved edges is determined via exact computation.
We provide more experiments and observations in Appendix, including the impact of model training and the value of g on MOSR (Appendix D. I); insights into designing the weighting function f (Appendix D.2); and the effect of WAF3 in actual curvature garph learning (Appendix D.3).
7 CONCLUSION
This work revisits the belief that discrete curvature reliably captures over-squashing in graph neural networks. We prove through constructive counterexamples that even highly positive-curvature edges can suffer from severe squashing, showing that curvature is not necessary condition. To quantify this gap, we introduce MOSR, a metric that measures the proportion of over-squashed edges missed by curvature-based criteria, and we find that common curvatures such as Ollivier-Ricel may overlook more than 30%. We further present WAF3, a weighted refinement of Forman-3 curvature, which addresses the theoretical limitations of existing definitions. By reformulating as a weighted Jaceard similarity and applying weighted MinHash, we achieve practical scalability with over two orders of magnitude speedup.
Overall, this work both challenges an implicit assumption in the community and provides a feasible alternative. encourages more principled ways to characterize over-squashing and supports the design of graph learning methods that move beyond curvature as a universal surrogate.

---

Published as a conference paper at ICLR 2026
8 REPRODUCIBILITY STATEMENT
We provide detailed proof's and derivations of theoretical results presented in the main text in the appendix. We also provide anonymous link to the code of this project and state all necessary implementation details in the appendix. We provide a statement of use for the LLMs at the end the appendix.
REFERENCES
Singh Akansha. Over-squashing in graph neural networks: A comprehensive survey, Neurocomputing, pp. 130389, 2025.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A cext-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 2623-2631, 2019.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications.
arXiv preprint arXiv:2006.05205, 2020.
Kushal Bose and Swagatam Das. Asynchronous message passing for addressing oversquashing in graph neural networks. arXiv preprint arXiv:2509.06777, 2025.
Jialong Chen, Tianchi Liao, Chuan Chen, and Zibin Zheng. Improving message-passingg gnns by asynchronous aggregation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 228-238, 2024.
Jialong Chen, Bowen Deng, Chuan Chen, Zibin Zheng, al. Graph neural ricci flow: Evolving feature from a curvature perspective. In The Thirteenth International Conference on Learning Representations, 2025.
Karel Devriendt and Renaud Lambiotte. Discrete curvature graphs from the effective resistance*
Journal of Physics: Complexity, 3(2):025008, June 2022. ISSN 2632-072X. doi: 10. 1088/ 2632-072x/ac730d. URL http:ttt/// //xx doi ooriioorg1000 10. 00000//2262-002/2773000000
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact width, depth, and topology. In International conference on machine learning, pp. 7865-7885. PMLR, 2023a.
Francesco Di Giovanni, T Konstantin Rusch, Michael M Bronstein, Andreea Deac, Mare Lackenby, Siddhartha Mishra, and Petar Veličković. How does over-squashing affect the power of gnns? arXiv preprint arXiv:2306.033: 033589, 2023b.
P ERDdS and A R&wi. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Hamza Farooq, Yongxin Chen, Tryphon T Georgiou, Allen Tannenbaum, and Christophe Lenglet. Network curvature as a hallmark of brain structural connectivity. Nature communications, 10(1): 4937, 2019.
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmentations of forman-ricci curvature. Learning on Graphs Conference, pp. 19-1. PMLR, 2024.
Forman. Bochner's method for cell complexes and combinatorial ricci curvature. Discrete & Computational Geometry, 29(3):323-374, 2003.
Linton C Freeman. A set of measures of centrality based on betweenness. Sociometry, pp. 35-41, 1977.
Xingcheng Fu, Jian Wang, Yisen Gao, Qingyun Sun, Haonan Yuan, Jianxin Li, and Xianxian Li. Discrete curvature graph information bottleneck. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 16666-16673, 2025.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. Pmlr, 2017.
10

---

Published as a conference paper at ICLR 2026
Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. On the trade- off between over-smoothing and squr-squa in deep graph neural networks. In Proceedings of the 32nd ACM international conference information and knowledge management, pp. 566-576, 2023.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks.
Proceedings of the national academy sciences, 99(12)7721--7226 2002.
Karish Grover, Geoffrey Gordon, and Christos Faloutsos. Curvgad: Leveraging curvature for enhanced graph anomaly detection. arXiv preprint arXiv:2502.08605. 2025.
Benjamin Gutteridge, Xiaowen Dong. Michael M Bronstein, and Francesco Di Giovanni, Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 22222-12267 PMLR, 2023.
Sergey loffe. Improved consistent sampling, weighted minhash and 11 sketching. In 2010 IEEE international conference on data mining, pp. 245-255. IEEE, 2010.
Jürgen Jost and Shiping Liu. Ollivier's ricci curvature, local clustering and curvature ceivaturr-dimension inequalities on graphs. Discrete & Computational Geometry, 512)):000-32, 2014.
Supanat Kamtue. Combinatorial, bakry-) 'emery, ollivier's ricci curvature notions and their motivation from riemannian geometry. arXiv preprint arXiv:1803 08898, 2018
Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information processing systems, 29, 2016.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1-2):81-93, 1938.
TN Kipf. Semi-supervised classification with graph convolutional networks. arXiv preprint 10X1v:160. 2016.
Haifeng Li, Jun Cao, Jiawei Zhu, Yu Liu, Qing Zhu, and Guohua Wu. Curvature graph neural network. Information Sciences, 592:50-66 66, 2022.
Yong Lin, Linyuan Lu, and Shing-Tune Tung Yau. Ricci curvature of graphs. Tohoku Mathematical doi:
Journal, 63(4):605 627, 2011. 274 7748/tm3/1325888
URL
Mark S Manasse. Consistent weighted sampling. 2010.
Madhumita Mondal, Areejit Samal, Florentin Münch, and Jürgen Jost. Bakry-émery-ricch curvature: an alternative network geometry measure in the expanding toolbox of graph ricci curvatures. Journal of Complex Networks, 12(3):cnae019, 2024.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen. Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting smer-smog and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pp. 25956-25979. PMLR, 2023.
Yann Ollivier. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256 (3):810-864) 2009. ISSN 0022-1236. doi: //www. sci enced rect. com/ sci
10....10000.000.1111111111110000 URL https:
Yun Jin Park and Didong Li. Lower ricci curvature for efficient community detection. arXiv preprint 10110224 2024.
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-rieci curvature-based method to commu- nity detection in complex networks. Scientific reports, 9(1):9800, 2019.
Li Sun, Zhongbao Zhang, Junda Ye, Hao Peng. Jiawei Zhang, Sen Su, and Philip Yu. A self- supervised mixed-curvature graph neural network. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 4156-4155, 2022.
Li Sun, Feiyang Wang. Junda Ye, Hao Peng. and Philip S Yu. Contrastive graph clustering in curvature spaces. arXiv preprint arXiv:2305.03555 2023.

---

Published as a conference paper at ICLR 2026
Yu Tian, Zachary Lubberts. and Melanie Weber. Curvature-based clustering graphs. Journal of Machine Learning Research, 26(52):1-67, 2025.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature, arXiv preprint vrXiv:2111.14522, 2021.
Floriano Tori, Vincent Holst, and Vincent Ginis. The effectiveness of curvature curvature-based rewiring and the role of hyperparameters in gnns revisited. arXiv preprint arXiv:2407.09) 09381, 2024a.
Floriano Tori, Vincent Holst, and Vincent Ginis. The effectiveness curvature- based rewiring and the role of hyperparameters in gnns revisited. arXiv preprint arXiv:2407.0938/, 2024b.
Wei Wu, Bin Li, Ling Chen, and Chengqi Zhang. Canonical consistent weighted sampling for real-value weighted min-hash. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1287-1292. IEEE, 2016.
Wei Wu, Bin Li, Ling Chen, and Chengqi Zhang. Consistent weighted sampling made more practical. In Proceedings of the 26th international conference world wide web, pp. 1035-1043, 2017.
Wei Wu, Bin Li, Ling Chen, Chenggi Zhang, and Philip S Yu. Improved consistent weighted sampling revisited. IEEE Transactions on Knowledge and Data Engineering, 31((2):2332- 2018.
Wei Wu, Bin Li, Ling Chen, Junbin Gao, and Chengqi Zhang. A review for weighted minhash algorithms. IEEE Transactions on Knowledge and Data Engineering, 34(6)225332253,, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. pmlr, 2018
Xikun Zhang, Dongjin Song, and Dacheng Tao. Ricci curvature- based graph sparsification for continual graph representation learning. IEEE Transactions Neural Networks and Learning Systems, 2023.
12

---

Published as a conference paper at ICLR 2026
A PROOFS & DERIVATIONS
A.1 PROOF OF LEMMA 2
Lemma 7. Let A be the adjacency matrix of an undirected, unweighted, simple graph, and D the degree matirx. For any two adjacent points and j in the graph, for any L. E Zt we have:
dd+1
dj +1+1
V 1)(d +1)
The equal sign is obtained iff d4 dj =
Proof.
Define M = =D++I)
(D+1)-1/3(A + I)(D + 1)-1// The element of M is given by:
1
for the diagonal,
d, +1
My
if j
((d + () +1)
otherwise.
The (i, entry of M denoted M/j, represents the sum of the weights of all walks of length L from node i to node j. The weight of a walk is the product of the M-weights of the edges traversed at each step. To bound M adjacent, this subgraph includes the edge (i, along with self-loops at both nodes. The matrix M restricted to these two nodes is:
consider the subgraph restricted nodes and j. Since i and
M M
M
P
Mj
+1](4,+1
Zy+I
We now compute the (1, 2) entry P which corresponds to walks from i (index 1) to (index 2) within this subgraph. Note that P can be expressed as the outer product P =v"", where:
VO,+I
vd
Thus for any integer T, 2.21 1:
4-1
p = (vv7' (V)) vvvv) =
P.
di +
dg +1
Specifically, we have:
L-1
P/ = d;
+1
d, +1
Vid: + l)(d, +1)
In the full graph, M includes all walks of length L from i to j. not only those confined to {i, The walks restricted to {i,j} form subset of these walks, and their total weight is exactly Pfz- Since all entries M are non-ncgative (M,v 2 0 for all u, v), the weight of every walk is non-negatio Therefore, the sum over all walks is least the over the subset of walks confined to (i.j]:
M
P
This establishes the desired inequality. The equal sign holds iff = M, which means d, = d 1.
Before we prove Lemma 2, we first further explain Assumption 1. When we compute the Oh (L) /ah we obtain of different terms all possible paths from of length L. In this case, the derivative of ReLU acts as a Bernoulli variable evaluated along all these possible paths. So follow the very same argument in Di Giovanni al. (2023a); Kawaguchi (2016); Xu al. (2018), can get:
Oh (L)
L-1
w 11/2 + I + +I) 1-- -11))) b
II
0h (0)
=
1=0
13

---

Published as a conference paper at ICLR 2026
Which the expectation means that are taking the average over such Bernoulli variables. Then can take the norm (in expectation) and leverage Lemma 5:
Oh (L)
L-1 II w())
(at1+ (
L-1
1
0h (0)
P
V(a + 1)
Which = dg and b = de Note that the right side of the inequality has nothing to do with the graph structure, And by Lemma 5, this bound is tight. So the proof complete.
A.2 PROOF OF THBOREM 4
Lemma 8. Consider family of x matrices (a)
{alj') (a)] parameterized by 0,
satisfying:
Diagonal invariance: For all S S n, the diagonal elements di are constant
(independent ot). o.)
Upper-left block invariance: There exists a fixed integer m (15 m S such that the submatrix Asub = (aig Sissssm is constant (independent of a.)
Uniform decay outside block: All other elements are bounded by a, i.e.,
Ss for all (i> or j >> m) and i + j-
Let A.,a) denote the k-th power of A A(a), and A sub the k-th power of the fixed submatrix A
Then for any fixed integer k Z 1 and all 1 S i, m:
lim a
(A A(a)))) (A =0
with convergence rate (a²2).
Proof. Fix 1 2 1 and j.j E (1,... .m) We interpret A (0) as the adjacency matrix of a weighted nodes, where a is the edge weight from node j. The (i,j)-entry of (o).k equals the sum of weights of all paths of length from i to j. with path weight defined as the product of edge weights. Similarly, (A (bu)) sums weights of paths confined to the subgraph of nodes {1, .m].
directed graph
(a)
Let Paub be the of paths from to j of length & within (1,"..,,) and Petse the set that visits
least one node in {m + 1, ... ,n... Then:
(A (laa)))
Σ w(p)
Σ w(p),
(A
Σ w(p),
PEP
Pete
PEP
S0:
(A (Aii)))
Σ w(p)
Σ |w(p)).
pePat
pEPat
Where w(p) denotes the weight the path p. which is always nonnegative. for each path p E Pelse contains at least edge that move from node set {1, ..,) to node set {m + 1..... ,n. and also contains at least one edge that move from node set(m + 1.....
......,7. ,n} to node set {1, (1,...,70 m]. Thus:
w(p) < a² maxx a. maxxaxa (a) max (a (a) 1 (a 1stjšm }
When a S max; (a (n)) and a S max (a (a)) the above formula is simplified to:
w(p) < a maxx max(a (a) }, max
(c(2)1)
k-2
-2ch-2
"ssifsm
Because [P pPtttl| |Potaal n and iPpathl ** k-1 (A
(Att)is s - m x1) a²Cz
which implies lim (A (A)))))) (Att) 0 with convergence rate O(a2).
14

---

Published as a conference paper at ICLR 2026
We first prove the second property in Theorem 3, namely the convergence of | /Ohg | Let A the adjcent matrix of 9 and Dc the degree matrix. Similar to the proof of Lemma 2, we have:
(Z)
(0)
Th (T)
L-1
w(
(ID++ +1) ( I)(D +1) +1) 1/2)
=
0h.
t=0
Let M = (D + 1)
(A + De + +1)-1/2 we have:
if E {s,t) and E {s, t),
12 + 2
if = E1,
17 +
if =
M
2
1
( (s,t) and j E or (i EM and j E (s,
v (n 2)(m +3)
if (i E N1 and N2) or (i E N2 and j E Ni1,
v (m + 33
otherwise.
Since
max 0, (n +3
22(m + 3)
2 + +3)
According to Lemma 6, we have:
(M )s, + (1/0+ 1/(n+ 2)
21-11
6n + 1,n+1).
1/(n+ + 2)
(n + 2)
1,2
with convergence rate ((1/(2(m + 3))) = 00 when + +o0.
Then we prove separately that for all n.m m R+ the seven discrete curvatures (except link resistance curvature) between nodes and are always positive in graph 9
Augmented Forman-3 curvature & Augmented Forman-4 curvature Note that edge (s, t) is not contained in any 4-cycle in &s thus (s,,) t) Thus for all n, m E R+ we have:
AF3(s,t) AF4 t) 4
+ 3n 4 2 5.
Jost-Liu forman curvature Note that A(s, t) and de Ad = d.V.V. Vd d, = 1. Thus for all g
1
A
t)
1
Ass,t)
(s,,t)
JLF(s, = - (1
- (1
d
dj
dg
V
d
d dj
d, A
d, V
=- (1
1
n
)+ (1
n
) +
n + 1
+
1
+ 1
n+1
1
n
n
1
n + 1
n
+
2'
Balance forman curvature with/without 4-cycle For all n, m E R+:
2
2
(s,
Ass,t)
BFw/o4(s, t)
-
2
d₂
dj
d, d.
d, de
2
2
2 2
n1 +1+1
n+1 1
n
n +
1.
n n
Note that (stt+ (s.t) (.v1)
2 0, Thus:
BF(s BFw/o4(s,
15

---

Published as a conference paper at ICLR 2026
Ollivier Ricci curvature Note that:
a
1= s,
1-a
(v)
vENuUt
n+1
clse.
and
a
= {s},
1-
(v)
U VEM
n n+1
else.
To calculate W p(), when >
1-c
we need to move 1- probability mass directly
m+1
*+1
from when < x+I need to move WiGg /44) = |a we take a = 1-1 and oOR(s, = la n+1
I-a a probability mass directly from So a+1
1-a and thus OR(s, t) = n 2 2 when
Lin-Lu-Yat curvature By using the definition:
(LY t) lim aOR(s, lim
a 1-a
a->1- 1
a-1-
C
Define g(0) a I-a For a sufficiently close to 1, specifically when a n+2 (which holds for in left neighborhood of 1 since n+2 lg(a)) g(a) in this region. The numerator simplifies as follows:
#411
_ < 1 for all positive integers n),, have g(a) 0. Thus,
1-a
n n+2
1- (-(a(a) = 11)((a) =1
= -1
(1--a
m+17
n+1
Therefore:
1 |g(a))
a)
n+2
lim n+2
n n+2
lim a-1- 1
lim
> 1.
12 n n n+1
Which means (s, 1.
Link resistance curvature Finally, we prove that link resistance curvature, for any fixed n², there exists an m such that for all m > m", and node-pair (s, in G .m LR(s, > 0.
To calculate the link resistance curvature, we first need calculate the equivalent resistance each edge in g Looking back at the definition of G there are three equivalent types of edges. Let's assume that the edges in (s, t)}. {(s, u)), (t, uu)hsign and {w,,, heggnn have resistance values of rı, r2, and r3 respectively. And their equivalent resistances are recorded as wh, W2, and Wy respectively.
Calculate Wi: Note that there are n + resistors in parallel between and t, n of which have resistance of 2r2 and one has resistance of rı, S0:
+ n
W1 =
r1
2r²
Calculate W2: Since the equivalent resistance of all edges in {(s, uz), (t, uJ)ists is equal, let's take the calculation of the equivalent resistance between and in example. According to the topology of the graph, the calculation is divided into three steps. First, we connect n resistors in parallel: s
U2 t, U3 ... un where the resistance of s is rı and the resistance the remaining n - resistors is 2r2. Then, we connect the resulting resistor in series with ūn (with a resistance of r2). Finally, we connect the resulting resistor in parallel with u (with a resistance of r2). Therefore, wa is calculated as:
W222
r2 +
n
2r
16

---

Published as a conference paper at ICLR 2026
Calculate wy: Since any May is only connected to ue, the equivalent resistance between Biy and u5 is not affected by any other resistance, so:
W3 73.
From the definition,
2(1 nnw2)
LR(s,t) t)
W1
since wi > O, making LR(s, t) > O is equivalent to making 1 - 7002 > true, which is further
equivalent to ensure:
1 n --
r2 +
+ > n.
2r²
r2
Simplify the left side of the above inequality:
2r + (n 1)ri
2r172
-1
1
left
r2 +
r2 +
+
2rir2
02
2r2 + (n - 1)r
12
[22 + (n + 1)r172
1
2r (n 1)r1
1
2r2 -nn1
+
2r2 + (n 1)rl
T2
2r
+ (n+ 1)r172
T2 2r + (n + 1)ri72
Considering that in the symmetric normalized Laplacian, the value of any edge (u, v) is Thus (n + 1)r1 = 1. We can further n+1 and 12 (mm=))(m+2)
so r1
+dd,+)
deduce the equivalent conditions as follows:
2r2 + 2nr1
2r2 + 2nrr
(2 n)r2 2nr 2nr 0.
2r + (n+ 1)r1
2r +2
We further narrow the left side of the above inequality to make its validity condition more stringent:
(2 - n2)r + 2nr
2nr2 > -nr2 + +2n1 - 2nr = n2(21 - -22 -2r2)
2
=11
(n + 1)(m + = f(n,
11 11
((n 1)(m + 2)
Obviously, (n, m)/0m O, and f(n, +o0) = न > 0. so for any fixed n², there must exist mn such that for any m > m", f'mn", approaches proved.
2 n+I arbitrarily, thus the original proposition is
A.3 DERIVATION OF EQUATION 6
4 di d--de d, 3Ai
=4 - -4-IW(n) - ((W())))
-())))))))))))) =4 (IV(w)) - (
=4 -
-
-(2 + --KKk//-Xo00--000/XXXX00000--0-0
=IB(u) n (
A.4 PROOF OF THEOREM 5
By definition, we know that for any G we have:
WAF3(s, t) 2f(n + 1) + nz nf(mm + 2)
The original proposition is equivalent to proving that for any
0, there exists set of positive integers n² and m such that ( + +nf(m + + < e. Since f(+x) = 0+, for any e >>> 0. there exists Ni > 0 such that when x > N1. we have f(z) < 5. Choose positive integer n² such that
n + > Ni. Then, f(n + 1) < {. and thus
2f(n" + 1) < 2
17

---

Published as a conference paper at ICLR 2026
For fixed n², since f(x)) - 0 as oc, there exists N2 > 0 such that when N2,, have
f(z) < 2n- Choose a positive integer m² such that m + > N2. Then, f(mm + 2) < 2n and thus
n' f(m" + 2) 2
c
Therefore,
2f(n" + n2' f(m" + <
+ 2
A.5 PROOF OF THEOREM 6
Notice that:
EiEN(OINN f(d:)
(
EiEN(O)UN f(d,)
EiEN(WINNiO) f(d:)
Jacccard
ΣiEN(O) f(d,) + EiEN(H) f(d:) - EiEA( f(d,)
EiEN(u) f(d,) + EiEN(O) f(d,)
Jaccard (N(u).N(v))
EiEN(WrNN(O) f(d:)
f(d+) EiEN(w) f(d,) + EvEN(O) f(d))
Σ
Jaccard (N(u),N(w))
(EM(U)nWi))
So:
WAF3
Σ f(d.)
Σ
f(d.)
Σ
f(d.)
(EB(w)NB(U)
(EN(w)/B(O)
iEA(O)/B(w)
+((W)+((d)
((dw) + +f(c)) +
Σ
f(ah)
Σ
f(d:) f(do)
(((o))
E
f(d,) f(dw)
(EN(W))N(()
(EN(W)/N(O)
(EA(e)//V(W)
-2f(d)) + +2f(d)) +
Σ f(d))
E f(d))
E
f(di)
iEN(U)
iEN(u)/N(())
iEN(O)/N())
-2f(de) +ff(d))+
Σ 3f(d.)
Σ f(d:)
Σ f(d)
(EN(s))W(t)
(EN(w)
(EN(e)
3 -25(dw) + +2((d)) + Jaccardd, N(V)) +1 +1
Σ s(d)) + Σ S(d+)
(EN(w)
iEN(v)
-2f(dw) + 2f(dd)) + 3Jaccard, (Baccard,(N(u),,))))) (N(n),
-1)
Σ f(d+) + Σ f(d))
+ Jaccard (N(u), /
iEN(u)
(EN(w)
=2f(dw) =2f(dd)+2f(d) 2f((d)) + (2 1 Jaccardd,
3
Σ (EN(u)
f(d+) + Σ f(d))
(EN(0)
B RELATED WORK
Alon & Yahav (2020) first proposed that information flowing through graph can be over-squashed due to bottleneck structures. This idea was quickly recognized by the graph learning community, and over-squashing has become one of the core challenges faced by subsequent researchers designing new deep graph models. The next notable breakthrough in weurshiush research came from Topping al. (2021), who demonstrated the of the discrete decrement matrix norm, thus transforming the ambiguous problem of determining over-squashed edges into a precisely defined curvature caleulation.
upper bound on the Jacobian
18

---

Published as a conference paper at ICLR 2026
Since then, discrete curvature has garnered significant interest within the graph learning community. One of the most typical approaches is curvature- basee graph rewiring, whose core idea involves performing curvature- survature-based preprocessing eliminate edges with extremely high or low curvature. Representative methods include those by SDRF (Topping al., 2021), BORF (Nguyen et al., 2023), SJLR (Giraldo et al., 2023), AFR-3 (Fesser & Weber, 2024), among others. Another approach involves directly integrating curvature into end-to- end GNN models. For instance, Li et al. (2022) utilized discrete curvature to improve aggregation weights in message passing: Sun et al. (2022) employed a hierarchical attention mechanism based on mnxed-ccuvattur spaces to capture complex graph structures and enhance performance; Fu et al. (2025) et al. proposed a curvature -ortanuee-ppiiiize variational information bottleneck principle to optimize information transmission on graphs; while Chen et al. (2025) designed a continuous-depti GNN with effects similar to rewiring methods via curvature Ricci flow. In addition, there is another type of method that proposes the asynchronous message passing mechanism (Gutteridge et al., 2023; Chen et al., 2024; Bose & Das, 2025). Their core innovation lies in combining the above two categories: graph reconnection and end-to-end graph network.
graph data before executing graph deep learning to
In terms of theoretical progress, Di Giovanni et al. (2023a) discussed how factors such network width, depth, and graph topology affect over-squeezing with the help of arrival time; Di Giovanni al. (2023b) studied the relationship between over-squeezing and expressiveness; Nguyen al. (2023) et al. established a unified understanding of over-smoothing and over-squeezing through ORC; Chen et al. (2024) gave the conditions for GNN to exhibit local priority through curvature. Tori et al. (2024b) proposed that the efffectivnness of curvature-base based graph rewiring methods may be due to the correction of outliers.
C COMPUTE MOSR
In this paper, we introduce the metric MOSR,, which measures the proportion of over-squashed edges that are ignored by the discrete curvature. MOSR is calculated using the Jacobian matrix norm, making it a tightly coupled metric with the model. This section details the calculation of MOSR.
To ensure faimess, we want the network model to be optimal when calculating the Jacobian matrix norm. To achieve this, we used Optuna Akiba al. (2019) perform 200 times hyperparameter search for each model on each dataset, with the hyperparameter search range fixed uniformly (as shown in Table 5. The hyperparameter search results are shown in Table 6, Table 7 and Table 8.
We then randomly initialize the GNN with the optimal hyperparameter combination and calculate
ab (1)
the Jacobian matrix norm
for each edge (i.j) in the dataset via the autograd module in
oh (0)
pytorch. We directly use randomly initialized GNNs without any training (See Appendix D. for
more discussion on this).
Following the definition of discrete curvature, we compute a curvature value for each edge and then compute MOSR as defined in Section 4. We repeat each experiment 10 times with different initialization and report the average value. Our experimental platform is Intel(R) Xeon(R) Gold 6240C CPU @ 2.60GHz and NVIDIA GeForce RTX 4090 x 4. We set the resource consumption limit for single experiment 12 hours of runtime and 24GB of GPU memory. Experiments exceeding this limit will be marked as Out of Resources (OOR).
Table 5: Scope of hyperparameter search
Hyperparameter
Range
laaer
[2,3.4.5]
hidden
[64, 128, 256]
dropout
[0. 0.1, 0.2. 0.3, 0.4, 0.5, 0.6, 0.7] [0.01, 0.005, 0.002, 0.001, 0.0005]
weight_decay
[0.005, 0.001, 0.0005, 0.0001, 0]
norm
["batch_nmee nrom", "layer_norm" none]
19

---

Published as a conference paper at ICLR 2026
Table 6: The optimal hyperparameter combination of GCN on different datasets
n llaaeer
hidden
dropout
Ir
weight
norm
Cora
2
64
0.7
0.001
0.005
none
Citeseer
2
256
0.5
0.001
0.005
none
Pubmed
2
64
0.6
0.005
0.0001
none
Computers
2
256
0.3
0.002
0.0001
none
Photo
2
256
0.5
0.0005
CS
2
128
0.7
0.0005
0.001
none
Physics
2
64
0.1
0.005
0.001
WikiCS
2
256
0.5
0.0005
In
Cora.ML
5
64
0.6
0.001
0.0001
none
Cora Full
2
128
0.5
0.01
0.001
none
DBLP
3
256
0.3
0.005
0.005
Cornell
2
64
0.4
0.0005
0.005
none
Texas
2
256
0.2
0.002
0.0005
none
Wisconsin
3
128
0.2
0.01
0.001
bn
Chameleon
2
64
0.6
0.001
0.0005
none
Squirrel
4
128
0.2
0.01
0.0001
bn none In In
Roman-empire
2
256
0.1
0.002
0.0001
Tolokers
2
256
0.7
0.01
Questions
2
256
0.6
0.01
0.001
Amazon-ratings
2
256
0.2
0.01
In
Minesweeper
3
256
0.5
0.005
Table 7: The optimal hyperparameter combination of GAT on different datasets
n layer
hidden
dropout
Ir
weight decay
norm
Cora
3
128
0.0005
0.005
none
Citeseer
2
64
0.4
0.005
0.005
none
Pubmed
2
64
0.5
0.0005
0
bn
Computers
4
128
0.5
0.001
0.001
In none
Photo
3
128
0.5
0.005
0.0001
CS
2
256
0.6
0.01
0.0001
none
Physics
2
256
0.7
0.002
0.001
In
WikiCS
2
256
0.6
0.0005
0.0001
bn
Co
5
64
0.7
0.0005
Cora Full
2
256
0.7
0.01
0.005
bn
DBLP
3
64
0.5
0.01
0.005
none
Cornell
4
64
0.4
0.005
0.005
bn
Texas
5
256
0.7
0.002
Wisconsin
4
128
0.7
0.01
0.005
none
Chameleon
5
128
0.3
0.0005
0.005
In
Squirrel
2
256
0.6
0.002
0.001
bn
Roman-empire
2
128
0.3
0.005
none
Tolokers
3
256
0.6
0.005
0.0001
none
Questions
4
256
0.3
0.001
0.0001
none
Amazon-ratings
2
128
0.1
0.0005
0.0001
bn
Minesweeper
3
128
0.4
0.01
0.0001
none
20

---

Published as a conference paper at ICLR 2026
Table 8: The optimal hyperparameter combination of GraphSAGE on different datasets
n layer
hidden
dropout
Ir
weight decay
norm
Cora
2
64
0.5
0.0005
0.005
none
Citeseer
2
128
0.2
0.005
0.005
none
Pubmed
2
256
0.5
0.005
0.001
Computers
4
256
0.7
0.0005
0.0001
none
Photo
2
64
0.6
0.002
none
CS
2
256
0.6
0.001
0.0001
none
Physics
3
256
0.7
0.005
0.0001
In
WikiCS
3
256
0.7
0.005
In none In bn
Co
3
256
0.1
0.001
0.0005
Cora Full
2
256
0.2
0.0005
0.005
DBLP
5
64
0.7
0.01
0.0005
Cornell
3
0.1
0.0005
0.001
none
Texas
2
0.2
0.001
0.005
none
Wisconsin
3
64
0.3
0.01
0.001
none
Chameleon
2
128
0.7
0.01
none
Squirrel
3
256
0.7
0.005
In
Roman-empire
4
256
0.5
0.01
bn
Tolokers
4
64
0.5
0.005
0
bn
Questions
5
128
0.7
0.0005
0.0005
none
Amazon-ratings
3
256
0.5
0.002
bn
Minesweeper
5
256
0.4
0.001
0.0005
none
D SUPPLEMENTARY EXPERIMENTS
D.1 EFFECTS OF TRAINING AND ON MOSR.
We explore the impact of the number of training rounds of the GNN model and the choice of p value on the value of MOSR. Our experimental settings cover different models, datasets, and curvature definitions.
As the number of training epochs increases, the value of MOSR will slowly increase and gradually stabilize as the training converges (because the difference in MOSR between epoch=200 and epoch=500 is significantly smaller than the difference in MOSR between epoch=0 and epoch=50).
Observation 9:
When is smaller, the criteria for being considered an over-squashing edge will be stricter, and the value of MOSR, will also become smaller.
Observation 10:
Observation 11: Observation 9 and observation 10 hold for all discrete curvatures (com- pare Figure with Figures and 7), all models (compare Figure with Figures and 9), and all dataset (compare Figure 5 with Figures 10 and 11).
The MOSR values reported in the main paper are all based untrained model (epoch=0) and small p-values (10 and 25). Based on the above observations, this means that we are reporting lower bound the probability that the discrete curvature ignores over-squashing edges. Under any other settings (c.g., more epochs and higher p), the discrete curvature will ignore even more over squashing edges than report.
21

---

Published as a conference paper at ICLR 2026
epoch
50 spoch
200 epochs
0.30
500 epoch
0.25
0.20
Dataset Citeseer Model GCN
0.15
Curvature OR
10
20
30
40
50
60
70
90
Figure 5: When the dataset is Citeseer, the model is GCN, and the discrete curvature is Ollivier Ricci Curvature, the impact of different training epochs and y-values on MOSR
0.25
egoch
50 epoch
200 epochs
0.20
500 epoch
MOSR,
0.15
0.10
0.05
Dataset = Citeseer Model GCN Curvalare
0.00
10
30
40
60
70
90
Figure 6: When the dataset Citeseer, the model is GCN, and the discrete curvature is balanced Forman Curvature, the impact of different training epochs and p-values on MOSR.
epoch
0.175
epoch
200 epochs
0.150
500 epoch
0.125
MOSS,
0.100
0.075
0.050
Datasel Citeseer
0.025
Model GCN
0.000
10
20
30
40
50
60
70
80
90
Figure 7: When the dataset is Citeseer, the model is GCN, and the discrete curvature is augmented Forman-3 Curvature, the impact of different training epochs and p-values on MOSR.
22

---

Published as a conference paper at ICLR 2026
0.40
epoch
50 spoch
0.35
200 epochs
500 epoch
0.30
MOSR,
0.25
0.20
Dataset Citeseer Model GAT Curvature OR
0.15
10
20
30
40
20
60
70
80
90
Figure 8: When the dataset is Citeseer, the model is GAT, and the discrete curvature is Ollivier Ricci Curvature, the impact different training epochs and p-values on MOSR
egoch
0.35
epoch
200 epochs
0.30
epoch
Dataset Citeseer
0.15
Model SAGE Curvature OR
10
Figure When the dataset is Citeseer, model is GraphSAGE, and the discrete curvature is Ollivier Ricci Curvature, the impact of different training epochs and p-values on MOSR.
0.25
epoch
50 spoch
200 epochs
0.20
500 epoch
MOSR,
0.15
0.10
Datasel = Cora Model GCN Curvature OR
0.05
10
20
30
40
60
70
90
Figure 10: When the dataset is Cora, the model is GCN, and the discrete curvature is Ollivier Ricci Curvature, the impact different training epochs and y-values on MOSR.
23

---

Published as a conference paper at ICLR 2026
0.14
0.12
0.10
Dataset = Pubmned
MOSR.
Model GCN
0.08
Curvature OR
0.06
0 epoch
50 epoch
0.04
200 epochs
500 epoch
0.02
Figure 11:
When the dataset is Pubmed, the model GCN, and the discrete curvature is Ollivier Ricci Curvature, the impact of different training epochs and p-values on MOSR..
D.2 WEIGHTING FUNCTION
Assuming that node and node have a common node for an MPNN as shown in Equation (1), the norm of the Jacobian matrix of u's information flowing through to e is:
ah Th
Oh
(h!+))
(+1)
The
F
w()
(D+ 1/2 + +)(DD -ID
( (D+
I)(D 1)-1/2
w
The inffuence of intermediate node
Therefore, we set f(d) to 1/(1 d,) to balance the contribution of any first-order neighbor node in computing the discrete curvature. We also explore the effects of weight functions that decay faster or slower than 1/(1 + d,) (i.e., (1 + d4) and + d4) -1/2) in Table 9.
Observation 12: On average, when f(d) = (1 + d) -1 the value of MOSR is generally slightly smaller (better) than when f(d) = (1 + d) or f(d) = (1+ d1 1/2
D.3 CURVATURE BASED GRAPH LEARNING
We explore the impact different discrete curvature definitions on graph learning. We select Stochastic Discrete Rieci Flow (SDRF, (Topping et al., 2021)) as representative graph rewiring method and Graph Neural Ricci Flow (GNRF, (Chen et al., 2025)) as representative end-to-end method. The results shown in Tables 10 and 11, respectively.
the graph rewiring method SDRF, WAF3 (and approximations) outperform other curvatures on two datasets; and in the end-to-end GNRF, they outperform other curvatures on all three datasets.
Observation 13:
Observation 14: When hash=100, approximately WAF3 performs as well or better than balanced Forman curvature and Ollivier Ricci curvature on both SDRF and GNRF
The above observations show that WAF3 can achieve better performance in curvature- based graph learning than previous curvature methods, and can do well enough even with rough approximations.
24

---

Published as a conference paper at ICLR 2026
Table 9: The impact of different attenuation functions on the calculation of WAF3. The values in the table represent 10 and 25SR
(dd = d)
((d) (1
d/-1/2
f(d) = +1++1100 d)-
GCN
GAT
SAGE
GCN
GAT
SAGE
GCN
GAT
SAGE
Cora
009//056
.169/118
.96//1996
000/0016
.147/.144
.172/172
0000:014
.157/.166
.183/1183
Citeseer
044/092
223/.335
.866/286
007/:026
.205/2205
2551.273
02000040
.210/2166
.279/2880
Pubmed
008/0013
.233/023
.255/025
0000000
00900010
011/0111
.01//002
.013/014
.015/015
Computers
014/017
.018/018
.018/018
001/0004
.009.009
.010/010
002/0005
.011/011
.011/011
Photo
020/.02
026//026
026//026
0129/000
033/.033
033//033
.211.024
0227/027
.027/.027
CS
070.079
092//093
094//094
.011/0011
068/.068
,699/069
00900034
07550075
.076/0076
Physies
06010699
0771/072
OOR
.01//023
049/.053
OOR
.2000040
.055/058
OOR
WikiCS
0651.069
.011/071
.203/203
.205/2205
.05//205
.140.141
.14//144
.144/114
Cora_MI.
074/.085
.115/119
1119/119
0200/048
088/.090
.01//093
0257.056
.098 103
.033/103
Cola_Full
OOR
OOR
OOR
OOR
OOR
OOR
OOR
OOR
OOR
DBLP
056/.069
084/.086
088//092
002/000
.344/037
.039/043
020M
.052/055
.057/.599
Cornell
00000000
.127/.188
.141/1166
.00/0000
.1201.124
.143/143
00000000
.116/.122
.138/.133
Texas
00000000
.132/132
.140/,143
00000000
.118/_123
.128/137
00000000
.134/.199
.143/.149
Wisconsin
0000.000
.122/132
.130/.100
00000000
.02// 109
.116/.126
00000000
.188.117
.122/134
Chamelcon
0371.043
040V 044
044//044
1000
.104/104
0657/066
07550076
.079/.079
Squirrel
015/.11
.155/.115
0151/.11
103/.03
1000
.100 101
.039/.039
.041/.01
.411/041
Roman-empire
000/0002
293//432
A52/.454
0000 004
.352/431
452/
0000.001
.351/431
A53/453
Tolokers
0077.007
OOR
.007/007
.0010001
OOR
.002/002
.002/002
OOR
003/.003
Questions
.011/.018
.031/0011
.322/032
.00//0066
.116/016
.188/018
,038/011
.023/.024
.055/.055
Amazon-ratings
.194/211
201/.209
.221/2244
.178/2235
.400/244
2611/263
.159//218
.223/2231
.245/,246
Minesweeper
.270/.270
.271/.211
.271/.271
.233/233
.23//2344
.233/2333
.191/.192
.192/.192
.192/1192
Average
.048/0057
.118/.122
.1251.126
.045/053
.117/.124
.128/.199
.036/.055
.111/118
.123/.124
Table 10: Accuracy downstream classification tasks after graph rewiring using SDRF (Topping et al., 2021) with different curvature definitions. The experimental setup for this experiment remains identical the original paper. *Indicates data referenced from Topping al. (2021).
Cornell
Texas
Wisconsin
Balanced Forman
57.54 0.34*
70.35
0.60*
61.55 0.84*
Ollivier Ricci
55.56 + 1.05
64.51 + 0.26
58.51 + 0.60
Augmented Forman 3
58.29 + 0.92
73.29 + 0.64
63.19 + 0.96
Weighted AF3
57.91 0.54
73.62 0.62
65.64 +: 0.24
Approximately Weighted AF3 (100 hash)
58.21 0.64
71.96 + 0.68
63.74 + 0.34
Approximately Weighted AF3 (1000 hash)
57.88 + 0.78
70.55 + 0.61
65.10 + 0.63
Approximately Weighted AF3 (10000 hash)
57.67 + 0.62
72.11 0.51
65.99 0.67
Table 11: The accuracy of end-to-end model GNRF (Chen et al., 2025) on downstream classification tasks using different curvature definitions. The experimental setup for this experiment remains exactly the same as the original GNRF paper.
Cornell
Texas
Wisconsin
Balanced Forman
84.37 3.11
83.15 + 6.25
83.15 + 3.25
Ollivier Ricci
81.26 5.45
79.95 = 5.14
81.26 + 2.36
Augmented Forman 3
84.21 + 5.26
85.66 + 3.25
79.26 + 1.59
Weighted AF3
84.62 - 3.26
87.11 + 1.03
84.66 + 0.34
Approximately Weighted AF3 (100 hash)
84.16 + 4.10
84.26 2.34
82.56 + 1.26
Approximately Weighted AF3 (1000 hash)
83.12 2.16
85.79 1.26
85.11 = 1.26
Approximately Weighted AF3 (10000 hash)
84.99 + 2.13
86.35 2.11
84.25 + 0.67
25

---

Published as a conference paper at ICLR 2026
E USE OF LLMS
In this project, we only used LLMs to find and correct grammatical errors and polish the text.
26


Reviews:
[{"review_id": "tq3KOGr6HJ", "reviewer": "Reviewer_fzn1", "summary": "This paper considers the connection between the oversquashing problem and negatively curved edges (quantified using a variety of different notions of discrete curvature). They show, contrary to popular belief, that negative curvature is merely a sufficient, rather than a necessary, condition for oversquashing to occur and show empirically that many oversquashed edges (quantified via jacobian norms) are \"missed\" by checking the curvature. To remedy this, the authors introduce a novel version of discrete curvature, as well as a fast approximation algorithm.", "questions": "Are there any viable ways to understand oversquashing which are not curvature derived?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Oversquashing is a well-known, highly studied problem in the training of GNNs. This paper lends a new perspective showing that the prevailing wisdom, oversquashing <==> negative curvature, is inadequate. They also show experimentally which of the common GNN architecture are prone to oversquashing.\n\nEmpiricial results are supported by theoretical analysis and novel definition which provide a new framework for thinking about oversquashing", "weaknesses": "Assumption 1 comes out of no where and is hard to understand. More discussion and motivation should be given.\n\nThe definition of $\\mu_u^\\alpha$, is unclear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GK8LfjxvPn", "reviewer": "Reviewer_hwjY", "summary": "In this paper, the authors question the connection of edge curvature to over-squashing. These edges are identified by a discrete notion of curvature (which is specifically adapted for graphs) that assigns a curvature value to each edge. They specifically claim that high negative curvature is a sufficient but not a necessary condition for over-squashing. To show that, they create counterexamples where some of the edges are squashed while the curvature remains positive. Since the Ollivier–Ricci curvature, one of the most commonly used discrete curvature measure, fails to detect a considerable percentage of over-squashed edges, the authors propose the Weighted Augmented Forman-3 Curvature (WAF3) to improve the detection of over-squashed edges. Finally, a new approximated WAF is presented that is able to handle very large graphs.", "questions": "- How robust is MOSR under different operational definitions of over-squashing?\n- Do analogous failure cases appear in real-world graphs (social, citation, molecular)?\n- Does WAF3-based rewiring or edge weighting actually alleviate over-squashing and improve downstream accuracy?\n\nTypos\n- line 155: Let s the soruce node, -> source", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- studies the over-squashing phenomenon in GNNs\n- shows that over-squashed edges may not always be detected by curvature\n- newly introduced metric for measuring over-squashed edges ratio by curvature-based criteria", "weaknesses": "- Counterexamples may not be representative of real-world graphs (e.g., citation, molecule, social). The authors should provide synthetic constructions with empirical evidence that similar topology/feature interactions occur in practical datasets.\n- Weighted Jaccard and MinHash are algorithmic conveniences; the transformation may sacrifice geometric interpretability\n- Proposed WAF3 correlates with or mitigates real over-squashing beyond proxy metrics", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xKO9Vu9OND", "reviewer": "Reviewer_5cz2", "summary": "The authors address the problem of over-squashing in GNNs. In this context, they investigate the following point: high negative curvature is a sufficient but not a necessary condition for over-squashing. In addition, they develop an approximation algorithm for the method Weighted Augmented Forman-3 Curvature.", "questions": "None", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is well organized and written\n- The authors address a key issue about GNNs: over-squashing.\n- The proposed method Weighted Augmented Forman-3 Curvature is detailed and reproducible.\n- Experiments are well conducted.", "weaknesses": "The authors should indicate more information between over-squashing and over-smoothing.\nMissing references:\nA. Arnaiz-Rodríguez, F. Errica, “Oversmoothing, Oversquashing, Heterophily, Long-Range, and More: Demystifying Common Beliefs in Graph Machine Learning”, Preprint, May 2025.\nY. Liu, et al., \"CurvDrop: A Ricci curvature based approach to prevent graph neural networks from over-smoothing and over-squashing\",  ACM Web Conference 2023, pages 221-230, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eu4Xv0Em0U", "reviewer": "Reviewer_jUf2", "summary": "The paper argues that having a negative discrete curvature (e.g., Ollivier–Ricci, Forman variants) is not a necessary condition for over-squashing in GNNs. It provides a counterexample family Gnm, showing edges can be heavily over-squashed while having positive curvature; introduces MOSR (Missed Over-Squashing Ratio) to quantify how many over-squashed edges are missed by curvature; proposes a new curvature WAF3 (Weighted Augmented Forman-3) with a degree-weighting; and develops a MinHash-based approximation to scale WAF3. Experiments report MOSR across 21 datasets and three architectures (GCN/GAT/GraphSAGE), plus efficiency and rank-correlation results for the approximation.", "questions": "- What is \\rho in Lemma 2? This also appears in Appendix A.1, but I’m not sure what this is.\n- Assumption 1 is not clear. What does the paper mean by all paths in the computation graph? What’s the computation graph in this case?\n- The notation in Definition 3 is not clear. N_1 and N_2 are the 1-hop and 2-hop neighborhoods of whom?\n- s_q is the proportion of over-squashing edges that are not identified by curvature, but I don’t see this in the equation. Do the authors mean MOSR_q?\n- What’s the number of layers L for the experiments in Table 2?\n- Could the authors provide the same results as in Table 2 for the balance Forman w/o 4-cycle and the Jost-Liu Forman? These two curvature metrics are also computationally efficient.\n- In Appendix A.1, Lemma 5 is used to get the bound, but I didn’t find this Lemma. Is it Lemma 7? Even if this is the case, I’m not quite sure how to get the bound in the first Equation on page 14 (please label the equations). Why is greater than or equal to? I’m confused at that point.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper shows that negative curvature does not imply necessity, with a concrete counterexample and theorem.\n- MOSR is a reasonable way to quantify “missed” oversquashed edges.\n- WAF3 is intuitive, keeps low complexity, and is shown to remove the counterexample under mild conditions.\n- Equivalent form via weighted Jaccard + MinHash is clever and gives large speedups with good rank fidelity.", "weaknesses": "- Eqn (1) is not the MPNN model; that’s the GCN model. MPNN is a generalization of GCN. This is problematic since most of the results in over-squashing in the previous literature are for MPNNs, while in this paper, they’re only true for GCNs. This reduces the scope and impact of the proposed work and diminishes the results in Table 4, since the theoretical understanding is only available for GCN.\n- Similarly, multiple formal statements (Lemma 2, Theorem 5) say “Assume an L-layer MPNN as in (1).” But Eq. (1) is the symmetric-normalized GCN layer with ReLU; it is not a general MPNN. The proofs that rely on the exact matrix M therefore apply to GCN-style propagation; generalizations would require additional conditions on the aggregation kernels.\n- The last part of Section 4 lacks clear intuition on how over-squashing relates to bottlenecks and how this differs from “bridges”. Prior theory (e.g., Topping et al.) does not imply that removing bottlenecks eliminates over-squashing, yet the paper does not provide a concrete narrative or example to reconcile this. In particular, the manuscript does not illustrate what an intra-cluster over-squashed edge looks like (low betweenness, still over-squashed) or explain the mechanisms that make it over-squashed despite no obvious bottleneck. This gap makes the conceptual contribution harder to follow and weakens the takeaways of Section 4.\n- The choice of the Forman-3 curvature for the extension seems arbitrary. Indeed, the balance Forman w/o 4-cycle and the Jost-Liu Forman have the same complexity as the Augmented Forman-3 according to Table 1. However, those are not compared in Table 2, and we don’t know if these other two computationally efficient metrics are better or worse than the Forman-3 curvature.\n- I understood the reasoning behind Figure 4, but I feel it’s also important to compare the efficient version of the proposed curvature in terms of MOSR, as in Table 4. This new version might be more efficient, but the main point of this paper is to avoid missing the over-squashed edges where the curvature is positive, and if this is not the case for the efficient formulation, why should one go with this alternative? If the important point is the ordering (I agree with the authors on this), why should one choose this approach over something that achieves the correct rank, while being perhaps more efficient?\n\n\n**General comment**: This is a timely paper, but two pieces are missing to make the contribution fully convincing. (1) The manuscript does not clearly connect the proposed most efficient curvature variant to the central claim of the paper (reducing missed over-squashed edges). Please make the causal chain explicit: why this efficient metric preserves the ordering or detection properties that matter for oversquashing, and how that supports the paper’s main thesis. (2) The paper lacks a large-scale, real-world evaluation demonstrating impact. A straightforward way to address this is to plug the efficient curvature into an existing rewiring pipeline and report results on a sparse OGB node property benchmark—e.g., ogbn-products or ogbn-papers100M—including both accuracy and compute (runtime/memory). This would substantiate scalability claims and show that the efficiency gains translate into practical benefits without undermining effectiveness.\n\n\n**Minor comments:**\n\n- Line 58: “This theorem…”, which theorem? At this point in the paper, it’s not clear this is supported by a theorem.\n- Please define acronyms the first time they’re used, e.g., MOSR.\n- It seems like Table 3 has not been referenced in the paper.\n- Figure 2 is violating the margins.\n- Typo in Theorem 5? There dose not.\n- Could you include the statistics of the datasets? I think this is important to put things in context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kqNBwWjkpa", "reviewer": "Reviewer_QN1W", "summary": "The paper challenges the common assumption that discrete curvature is a reliable proxy for detecting over-squashing in GNNs, showing via a family of counterexample graphs and formal results that many severely squashed edges can still have positive curvature—so high negative curvature is sufficient but not necessary for over-squashing. To quantify this gap, the authors introduce MOSR, a metric that counts the fraction of truly over-squashed edges missed by a curvature rule; across models and 21 datasets, Ollivier–Ricci misses roughly 30–40% of such edges, and a betweenness analysis indicates that curvature mostly finds “bridge” edges while often ignoring in-cluster bottlenecks. They then propose Weighted Augmented Forman-3 (WAF3), a degree-weighted refinement that theoretically avoids the counterexamples and empirically reduces MOSR relative to prior curvatures while retaining low complexity. Finally, they derive an equivalent weighted-Jaccard form and a MinHash-based approximation that lowers runtime to linear in the number of edges, enabling curvature computation on graphs with about 5 million edges", "questions": "Could you provide intervention-based validation showing that using WAF3 to guide rewiring, edge weighting, or attention bias leads to consistent gains in downstream GNN performance versus Ollivier–Ricci and prior Forman variants, with compute-matched baselines, multiple seeds, and analyses of where improvements concentrate (e.g., non-bridge bottlenecks)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is original in challenging a widely assumed link between discrete curvature and over-squashing and in formalizing how and why common curvatures can fail, complemented by a clear diagnostic (MOSR) that quantifies misses rather than relying on anecdotal examples. It shows solid technical quality through explicit counterexamples, theoretical guarantees for the proposed WAF3 variant, and careful complexity considerations, including an equivalent weighted-Jaccard view and a MinHash-based approximation that makes large-scale computation practical. The presentation is clear: definitions, constructions, and algorithms are spelled out with enough detail to reproduce both the counterexamples and the fast estimator. Significance is high for both researchers and practitioners who use curvature to guide model design or interventions for over-squashing, since the work both tempers over-reliance on existing curvatures and supplies a drop-in alternative that is faster and empirically more aligned with actual over-squashing.", "weaknesses": "Despite strong theoretical framing, the empirical story rests heavily on MOSR—a model- and label-dependent proxy for “true” over-squashing—so it remains unclear how much the proposed curvature actually improves downstream GNN behavior (e.g., training stability, accuracy, or robustness) beyond ranking edges; adding intervention studies (rewiring, weighting, or attention bias guided by WAF3 vs prior curvatures) and showing consistent end-task gains would strengthen the claim. The novelty of WAF3 also needs sharper positioning: prior work on curvature-based structural encodings (e.g., “Effective structural encodings via local curvature profiles”) should be cited in the introduction and connections to other works that use (weighted) augmented Forman–Ricci variants (e.g., “Augmentations of Forman’s Ricci curvature and their applications in community detection”) should be cited and discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)