Understanding over-squashing and bottlenecks on graphs via curvature
Authors: Jake Topping
Francesco Di Giovanni
Benjamin Paul Chamberlain
Xiaowen Dong
Michael M. Bronstein
Venue: ICLR 2022 Oral (2022)
Keywords: Graph neural networks
Geometric deep learning
Differential geometry
Ricci curvature

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.

Published as a conference paper at ICLR 2022
UNDERSTANDING BOTTLENECKS ON GRAPHS VIA CURVATURE
AND
Jake Topping 21, Francesco Di Giovanni BBejjamin P. Chamberlain'
Xiaowen Dong', and Michael M. Bronstein
University of Oxford IImpeial 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 factor limiting the effi- ciency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as "over-squashing' has been heuristically attributed 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, introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the weer-squs issue. We also propose and experimentally test a curvature- based graph rewiring method to alleviate the over wer-squashing.
INTRODUCTION
In the past few years, deep learning
graphs and in particular graph neural net-
works (GNNs) (Sperduti 1994 Goller &
Kuchler
1996
Sperduti & Starita
1997
Frasconi et al.
1998 Gori et al.
2005
Scarselli et al.
2008 Bruna et al.
2014
Defferrard al. 2016 Kipf & Welling
2017; et al., (2017) have become very popular in the machine learning com- munity due to their ability to deal with broad classes of systems of relations and interactions, ranging from social networks to particle physics (Shlomi et al. 202T).
Figure I: 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 per- formance. Blue/red shows negative/positive curvature.
The vast majority of GNNs follow the message passing paradigm (Gilmer et al.) 2017), using learnable non-linear functions to diffuse information the graph. Multiple popular GNN architectures such as GCN (Kipf & Welling 2017) and GAT (Veličković et al. 2018) can be posed as particular flavors of this scheme and considered instances of more general framework of geometric deep learning (Bronstein et al., (2021).
Some of the drawbacks of the message passing paradigm have now been identified and formalized, including the limits of expressive power (Xu et al. 2019 Morris et al. 2019 Maron et al.) 2019) and the problem of over-smoothing (NT & Maehara 2019 Oono & Suzuki] 2020). On the other hand, much less is known about the phenomenon of over-squashing, consisting in the distortion of
messages being propagated from distant nodes. Alon & Yahay (202T) proposed rewiring the graph as way of reducing the botrleneck, defined as those topological properties in the graph leading to wer-ssuashing. This approach is in line with multiple other results e.g. using connectivity diffusion (Klicpera et al. 2019) as preprocessing step to facilitate graph learning. Yet, the exact understanding of the squashing and how it originates from the bottlenecks the topology of the underlying
1 Equal contribution

---

Published as a conference paper at ICLR 2022
graph are still elusive. Consequently, there is currently no consensus the right method (either based on graph rewiring or not) to address the bottleneck and hence alleviate the over-squashing.
In this paper, we address these questions using tools from differential geometry, which traditionally is concerned with the study of manifolds. It offers an appealing framework to study the properties of graphs, in particular arguing that graphs, like manifolds, exhibit curvature that makes them more suitable to be realized in spaces with hyperbolic geometry (Liu et al. 2019 Chami et al., 2019 Boguna al.) [2021). One notion of curvature that has received attention for graph learning is Ricci curvalure (on 1988), also known in geometry for its use in Ricci flow and the subsequent
proof of the Poincaré conjecture (Perelman 2003). Certain graph analogues of the Ricci curvature (Forman 2003] Ollivier 2009; Sreejith et al. 2016) were used in Ni et al. (2018) for a discrete version of Ricei flow to construct a metrie hetween graphs. Graph Ricci flow was also used in Ni et al. (2019) for community detection. Both of these methods use the edge weights as substitute for the metric of a manifold, and do not change the topological structure of the graph.
Contributions and Outline. This paper, to knowledge, is the first theoretical study of the bottleneck and over-squahhing phenomena in message passing neural networks from a geometric perspective. In Section 2 propose the Jacobian of node representations measuring the over-squashing and we show that the graph topology may compromise message propagation in graph neural networks by creating bottleneck. In Section we investigate how such a bottleneck is induced which leads to the over-squashing of information. To this aim, we introduce a new combinatorial edge-based curvature called Balanced Forman curvature that constitutes a sharp lower bound to the standard Ollivier curvature on graphs, and prove that negatively curved edges are responsible for the formation of bottlenecks (and hence for over-squashing). In Section 4 we present new survature-based method for graph rewiring called Stochastic Discrete Ricci Flow. According to the theoretical results Section 3 this rewiring method is suited to address the graph bottleneck and hence alleviate the over-squashing by surgically targeting the edges responsible for the issue. By contrast, we rigorously show that a recently introduced diffusion-
formal way of
rewiring scheme might generally fail to reduce the bottleneck. Finally, in Section 5 we compare different rewiring strategies experimentally on several standard graph learning datasets.
2 ANALYSIS OF THE OVER-SQUASHING PHENOMENON
2.1 PRELIMINARIES
Let G = (V, E) be simple, undirected, and connected graph, where (i,j) E Eiff j. We focus on the unweighted case, although the theory extends to the weighted setting as well. We denote the adjacency matrix by A and let Ā = A + T be the adjacency matrix augmented with self-loops. Similarly we let D D + I, with D the diagonal degree matrix, and let A = D- AD- be the normalized augmented adjacency matrix (self-loops are commonly included in GNN architecture, and in Section 2 we formally explain why GNNs are expected to propagate information more reliably when solf- are taken into account). Given i V. we denote its degree by d, and let
Sr(1) = (j e V: da(i,)) = r), B,( := (j E V (i $ r))
where de the standard shortest-pale path distance on the graph and r N. The set B,) represents the receptive field of an r-layer message passing neural network at node i.
Message passing neural networks (MPNNs). Assume that the graph G is equipped with node features X E xo where E 1 is the feature vector at node i = 1, ,, [V. We denote by h E Rd the representation of node i at layer é 2 O, with h,"' = It. Given a family of message functions u/. : RR x IRP + IR''s and update functions dy : IRPt x R2 + RP we can write the (E 1)-st layer output of a generic MPNN as follows (Gilmer et al. 2017):
n ((+1)) 6e
h Σ
Anyee (0) n00)
Here we have used the augmented normalized adjacency matrix to propagate messages from each node to its neighbors, which simply leads to degree normalization of the message functions dhz. To
2

---

Published as a conference paper at ICLR 2022
avoid heavy notations the node features and representations assumed to be scalar from now on; these assumptions simplify the discussion and the vector case leads to analogous results.
2.2 THE RVEROVEERROOOOE -VER-SQUASHING PROBLEM
Multiple recent papers observed that MPNNs tend to perform poorly in situations when the learned task requires long-range dependencies and at the same time the structure of the graph results in exponentially many long-range neighboring nodes. We say that graph learning problem has long-rang, dependencies when the output of a MPNN depends on representations of distant nodes interacting with each other. If long-range dependencies are present, messages coming from non- adjacent nodes need to be propagated across the network without being too distorted. In many cases however (e.g. in 'small-world' graphs such as social networks). the size of the receptive field (i) grows exponentially with r. If this occurs, representations of exponentially many neighboring nodes need to be compressed into fixed- size vectors to propagate messages to node i, causing a phenomenon referred to as ser-sqqushin of information (Alon & Yahav) (021). In line with |Alon & Yahay (2021), we refer to those structural properties of the graph that lead to over-squashing as bottleneck
Sensitivity analysis. The hidden feature h = h (z1,..., In) computed by an MPNN with & layers as in equation is differentiable function of the input node features {æi,.... Fnn J as long as the update and message functions Φb and thp are differentiable. The over-squashing of information
can then be understood in terms of one node representation h,²) failing to be affected by some input
feature T, of node 8 at distance r from node i. Hence, we propose the Jacobian oh /0x. as an explicit and formal way of assessing the over-squashin effect]
(r)
Lemma 1. Assume an MPNN as in equation
| Let i, E V with s E S,+1 If Voll S and
|Vibel S B for 0 < 8 S r, then
Oh (r+1)
< (a:3))+((*++))
dr,
Lemma [ states that if the and the have bounded derivatives, then the propagation of messages is controlled by a suitable power of Å. For example, if do(i, - + 1 and the sub-graph induced on (1) is a binary tree, then (Ár+1);s = 2-13-r, which gives an exponential decay of the node dependence on input features at distance as also heuristically argued by Alon & Yahav (2021).
The sensitivity analysis in Lemma relates the over-squashing - as measured by the Jacobian of the node representations- - to the graph topology via powers of the augmented normalized adjacency matrix. In the next section we explore this connection further by analyzing which local properties of the graph structure affect the right hand side in equation [ hence causing the bottleneck. We will address this problem by introducing a new combinatorial notion of edge-based curvature and showing that negatively curved edges are those responsible for the over-squashing phenomenon.
3 GRAPH CURVATURE AND BOTTLENECK
A natural object in Riemannian geometry is the Ricci curvature, a bilinear form determining the geodesic dispersion, i.e. whether geodesies starting nearby points with 'same' velocity remain parallel (Fuclidean space), converge (spherical space), or diverge (hyperbolic space). To motivate the introduction of a Ricci curvature for graphs, we focus on these three cases. Consider two nodes i ~ j and two edges starting at i and j respectively. In discrete spherical geometry (Figure 2 the edges would meet A form triangle (complete graph). In discrete Euclidean geometry (Figure (2)), the edges would stay parallel and form a 4-cycle based at i ~ (orthogonal grid). Finally, discrete hyperbolic geometry (Figure (2), the mutual distance of the edge endpoints would have grown compared to that of i and (tree). Therefore, a Ricci curvature for graphs should provide us with more sophisticated tools than the degree to analyze the neighborhood of an edge.
We note that the sver-squashing issue is different from the problem of under-reaching: the latter simply amounts to MPNN failing to fully explore graph when the depth is smaller than the diameter (Barceló al.) 2019). The over-squashing phenomenon instead may occur even in deep GNNs with the number layers larger than the graph diameter, as tested experimentally in Alon & Yahav (202T).
The Jacobian of GNN-output was also used by Xu et 2018 set similarity score among nodes.
3

---

Published as a conference paper at ICLR 2022
Curvatures graphs. The main amples of edge-based curvature are the Forman curvature F(i.j) (Forman 2003) and the Ollivier curvature k((,j) inlliiiier (2077: 2009) (see Appendix). While F(i.) j] is given in terms of combi- natorial quantities (Sreejith al. 2016).
results are scarce and the definition is bi- ased towards negative curvature. The the- ory on k(i.j) j) instead is richer (Lin et al.
(a) Clique (> 0) (h) Grid (= 0)
(c) Tree (<. 0)
Figure 2: Different regimes of curvatures on graphs anal-
2011 I, Münch| 2019) but its formulation makes it hard to control local quantities.
ogous to spherical (a), planar (b), and hyperbolic (c) ge-
ometries in the continuous setting.
Balanced Forman curvature. We propose a new curvature to address the shortcomings of the existing candidates. We use the following definitions to describe the neighborhood of edge i and we refer to the Appendix for a more complete discussion:
(i) (a( (d) n Si() are the triangles based at j.j. j.
(ii F (i,j) := {k (i) Si),, j: Ew E (K) S(() (i)) are the neighbors of i forming a 4-cycle based at the edge ~ j without diagonals inside.
(iii) Tmaa () is the maximal number of 4 4-cycles based at ~ j traversing common node (see Definition 4
In line with the discussion about geodesic dispersion, one expects ia to related to positive curvature (complete graph). =b to zero curvature (grid), and the remaining outgoing edges to negative curvature (tree). Our new curvature formulation reflects such intuition and recovers the expected results in the classical cases. In the example in Figure we have (0, 1) = (2,3} while (0, 1) = {5), both without 4,6 because of the triangle 1-6-0. The degeneracy factor Ymmx (0,1) 2, there exist two 4-cycles passing through node 5.
Figure 3: 4-cycle contribution.
Definition (Balanced Forman curvature). For any edge i ~ j in a simple, unweighted graph G, we let Ric(i,j) be zero if m'minndd d,} and otherwise
2
2 [+ + min(de, dg} maxid, dz}
[+a(1,))
(Tmar))
Ric(i.
(IEE + l=a)), (3)
di dj
max(di,d,]
where the last term is set to be zero if [t/gl (and hence [#A|) is zero. In particular Ric(i, > 2.
The curvature is negative when i ~ j behaves as a bridge between (i) and (j), while it is positive when Si (1) and (j) stay connected after removing i j. We refer to Ric as Balanced Forman curvature. We can relate the Balanced Forman curvature to the Jacobian of hidden features, while also extending many results valid for the Ollivier curvature x(i,j) thanks to our next theorem.
Theorem 2. Given an unweighted graph G. for any edge i ~ j we have x(i. 2 Ric
Theorem ggeneralizesoost & Liu (2014) Theorem 3) (see Appendix). We also note that the computational complexity for k scales as O( E dd ( ). while for our Ric we have O E d2 ). with dmax the )
Graph G
Ricg
Ca
maximal degree. From Theorem 2 and Paeng 2012), we find:
Cycles
Ca
Cas5
0
Corollary 3. If (iciii, j) 2 for any edge i ~ j. then there exists a polynomial such that
Complete Kn
n-1
Grid G.. 0
(i) < P(r), ViEV.
Tree T,
4
2
r+
Therefore, when the curvature is positive everywhere, the bottleneck effect should not play crucial role as the receptive field of each node will be polynomial in the hop-distance. This limit case shows how the curvature determines whether learning task graph would suffer from over-squashing.
Table I: Examples of the Balanced Forman eurvature.
4

---

Published as a conference paper at ICLR 2022
Curvature and over-squashing. Thanks to our new combinatorial curvature and the sensitivity analysis in Lemma[] []] we are able to relate local curvature properties to the Jacobian of the node representations. This leads to one of the main results of this paper: negatively curved edges are those causing the graph bottleneck and thus leading to the over-squashing phenomenon:
Theorem 4. Consider a MPNN as in equation 7 Let ~ j with d$ S dj and assume that:
(i) Vod S a and ( dpl < B for each 0 S L < with L 2 2 the depth of the MPNN.
(ii) There exists 8 s.t. 0 < 8 < (max ( (d, d;3)) t, < +mma and Ric(t, S -2
Then there exists Q2 C (i) satisfying [Qy1 > 8-1 and for S to S we have
ah k
(2)+
(a
(4)
Q2
oh (fo)
Condition (i) is always satisfied and allows us to control the message passing functions. The requirement (ii) instead means that the curvature of (i, is negative enough when compared to the degrees of i and j (recall that Ric(i. 2)). The further condition on Tmax is to avoid pathological cases where we have a large number of degenerate 4-cycles passing through the same three nodes.
To understand the conclusions in Theorem 4 let us fix to O. The equation shows that negatively curved edges are the ones causing bottlenecks, interpreted as how the graph topology prevents representation h,(²) to be affected by non-adjacent features n:(0) z;z- Theorem 4 implies that if have a negatively curved edge as in (ii), then there exist a large number of nodes & such that GNNs on average- struggle to propagate messages from to k in two layers despite these nodes being at distance 2 from i. In this case the over werrssqashing occurs as measured by the Jacobian in equation 4 and hence the propagation of information suffers. If the task at hand has long-rang oong-range dependencies, then the over-squashing caused by the negatively curved edges may compromise the performance.
Bottleneck via Cheeger constant. We now relate the previous discussion about bottlenecks and curvature to spectral properties of the graph. In particular, since the spectral gap of a graph can be interpreted as a topological obstruction to the graph being partitioned into two communities, we argue below that this quantity is related to the graph bottleneck and should hence be controllable by the curvature. We start with an intuitive explanation: suppose we are given a graph G with two communities separated by few edges. In this case, we that the graph can be easily disconnected. This property is encoded in the classical notion of the Cheeger constant (Chung & Graham 1997)
[as|
he min hs: hg min SCV min(vol( S), (V {S)
SCV
where as = {(i.g) : :i S, j E V S} and vol(S) = Eies d.. The main result about the Cheeger constant is the Cheeger inequality (Cheeger 2015 Chung & Graham 1997):
h2
2hg 2 A1
(6)
2
where A is the first non-zero eigenvalue of the normalized graph Laplacian, often referred to as the spectral gap. A graph with two tightly connected communities (S and V V := 8) and few inter-community edges has a small Cheeger constant hg. For nodes in different communities to interact with each other, all messages need go through the same few bridges hence leading the over-squashing of information (a similar intuition was explored in Alon & Yahav (202T). Therefore, he can be interpreted as rough measure of graph 'bottleneckedness' in the sense that the smaller its value, the more likely the over-squashing is to occur across inter-community edges. Since Theorem 4 implies that negatively curved edges induce the bottleneck, we expect relationship between hGg and the curvature of the graph. The next proposition follows from Theorem 2 and Lin et al. (2011):
Proposition 5. If () 2 k > 0 for all i ~ j, then /1/2 2 he
Therefore, a positive lower bound on the curvature gives us a control on hG and hence on the spectral gap of the graph. In the next section] we show that diffusion-basee graph-rewiring methods might fail to significantly alter he and hence correct the graph bottleneck potentially induced by inter-community edges. This will lead us propose an alternative curvature- -hased graph rewiring.
5

---

Published as a conference paper at ICLR 2022
4 CURVATURE-BASED REWIRING METHODS
The traditional paradigm of message passing graph neural networks assumes that messages are propagated on the input graph (Gilmer et al. 2017). More recently. there is trend to decouple the input graph from the graph used for information propagation. This can take the form of graph subsampling resampling to deal with scalability (Hamilton et al., (017)) or topological noise (Zhang
et al. 2019). using larger motif-base or changing the graph either as a preprocessing step KKlicpera et al.
(Monti et al. (018) or multi-hop filters (Rossi et al.] 2020).
2019 Alon & Yahav] (222]) or
adaptively for the downstream task (Wang et al. 2019 Kazi et al.
2020). Such methods are often
generically referred to as graph rewiring.
In the context of this paper, we assume that graph rewiring attempts to produce a new graph G" = (V, E") with a different edge structure that reduces the bottleneck and hence potentially alleviates the over-squashing of information. We propose a method that leverages the graph curvature to guide the rewiring steps a surgical way by modifying the negatively-curr curveed edges, so to decrease the bottleneck without significantly compromising the statistical properties of the input graph. We also rigorously show that random-wal walk based rewiring method might generally fail to obtain an edge set E' with significant improvement in its bottleneckedness as measured by the Cheeger constant.
Curvature-basse graph rewiring. Since according to Theorem negatively curved edges induce a bottleneck and are hence responsible for over-squashing, a curvature-based rewiring method should attempt to alleviate a graph's 's strongly-negativel curved edges. To this end we implement a simple rewiring method called Stochastic Discrete Ricci Flow (SDRF), described in Algorithm I
Algorithm 1: Stochastic Discrete Ricci Flow (SDRF)
Input: graph G, temperature > 0, max number of iterations, optional Ric upper-bound C+ Repeat
1) For edge ~j j with minimal Ricci curvature Ric(i,.):
Calculate vector æ where TAi Ricaa (i,a(t,)) (i, j) Ric(i, j). the improvement to Ric(i,j) from adding edge
I where & E (1), Bi);
Sample index k, I with probability softmax(ræxxu and add edge k ~ l to G.
2) Remove edge i ~ j with maximal Ricci curvature Ric(i, if ji > C+.
Until convergence, or max iterations reached;
At each iteration this preprocessing step adds an edge to 'support' the graph's 's most negatively curved edge, and then removes the most positively curved edge. The requirement on the added edge le ~ I that k E (i) and E (i( (j) ensures that we're adding either an extra 3- 4-cycle around the negative edge ~ j so that this is a local modification. The graph edit distance between the original and preprocessed graph is bounded above by 2 x the max number of iterations. The temperature r determines how stochastic the edge addition is, with r = oo being fully deterministic (the best edge is always added). At each step we remove the edge with most positive curvature to balance the distributions of curvature and node degrees. We use Balanced Forman curvature as in equation [3 for Ric C++ can be chosen to stop the method skewing the curvature distribution negative, including C+ = oo to not remove any edges. The method is inspired by the continuous (backwards) Ricci flow with the aim of homogenizing edge curvatures. This different from more direct extensions of Ricci flow on graphs where it becomes increasingly expensive to propagate messages across negatively curved edges (as in other applications such as Ni et al. (2019)) An example alongside its continuous analogue can be seen in Figure] I
Can random-walk based rewiring address bottlenecks? A good way of understanding the effec- tiveness of SDRF in reducing the graph bottleneck is through comparison with random-wald based rewiring strategies. Recall that, as argued in Section 3 the Cheeger constant lGg of graph constitutes rough measure of its bottleneckedness as induced by the inter-community edges (a small lG is indicative of a bottleneck). Suppose we are given a graph G with a small hy and wish to rewire it into graph G' with significantly improved Cheeger constant in order to reduce the inter-communig bottleneck. A random-wall based rewiring method such as DIGL (Kliepera et al.) 2019) acts by smoothing out the graph adjacency and hence tends to promote connections among nodes at short

---

Published as a conference paper at ICLR 2022
diffusion distance (Coifman & Lafon 2006).
Accordingly, such rewiring method might fail to correct structural features like the bottleneck, which is instead more prominent for nodes that are at long diffusion distance To emphasize this point, we consider a classic example: given E (0, 1), the Personalized Page Rank (PPR) matrix is defined by (Brin & Page 1998) as
Ra: : Σ OPPPRDDAAA
Σ (1--a)DD 0
Assume that we rewire the graph using R. as in Klicpera et al. (2019) with the PPR kernl,, meaning that we replace the given adjacency A with Ra. Since Ra is stochastic, the new Cheeger constant of the rewired graph can be computed as
|as
1
ΣΣ (Ra)u. iES JE8
hs.a = vol.
|ST
By applying (Chung 2007 Lemma 5), we show that we cannot improve the Cheeger constant (and hence the bottleneck) arbitrarily well (in contrast to a curvature-based approach), We refer to Proposition 17 and Remark 18 in Appendix E for results that are more tailored to the actual strategy adopted in Klicpera et al. (219)) where we also take into account the effect of the sparsification.
Theorem 6. Let S V with vol(S) S vol(G) Then hs,a S (1 and dmin (S) are the average and minimum degree on S, respectively.
(S) duai (S) hs, where davg(S)
The property that the new Cheeger constant is directly controlled by the old one stems from the fact that a random-walk approach like in Klicpera et al.] (2019) is meant to act more relevantly on commumitm edges rather than inter-community edges because prioritizes short diffusion distance nodes. This is also why this method performs well on high-homophily datasets, as discussed below. In particular, for fixed a E (0. 1). the bound in Theorem caan be very small. As a specific example, consider two complete graphs Kn joined by one bridge. Then he = (n(n - 1) + +)-1 which means that the bound on the right hand side is O(n O2)
Theorem 6 implies that a diffusion approach such DIGL might fail to yield new edge set E' with sufficiently improved bottleneck. By contrast, from Theorem aand Proposition [ we deduce that a curvature-biic -ased rewiring method such as SDRF properly addresses the edges that cause the bottleneck.
Graph structure preservation. Although graph-rewiring approach aims providing a new edge set E' potentially more beneficial for the given learning task, it is still desirable to control how far E' is from E. In this regard, we note that a curvature-basee rewiring surgical in nature and hence more likely to preserve the structure of the input graph better than a random-walk walk based approach. Consider, for example, that we are given p >> 0 and wish to rewire the graph such that the new edge set E" is within graph-edit distance P from the original E. Theorem tellss us how to do the rewiring under such constraints in order to best address the over-squashing the topological modifications need to be localized around the most negatively-curved edges. We can do this with SDRF, with the maximum number of iterations set to p/2.
Secondly, we also point out that Ric(i.)) < - + å implies that min(de, (d,,dd)))) d,) > 2/8. Therefore, if we mostly modify the edge set at those nodes i joined by an edge with large negative curvature, then we perturbing nodes with high degree where such change is relatively insignificant, and thus overall statistical properties of the rewired graph such as degree distribution are likely to be better preserved. Moreover, graph convolutional networks tend to be more stable to perturbations of high degree nodes (Zügner et al. 2020 Kenlay et al. 2021). 1). making curvature-bast based rewiring more suitable for the downstream learning tasks with popular GNN architectures.
Homophily and bottleneck. As a final remark, note that the graph rewiring techniques considered in this paper (both DIGL and SDRF) are based purely on the topological structure of the graph and completely agnostic to the node features and to whether the dataset is homophilic (adjacent nodes have same labels) or heterophilic. Nonetheless, the different nature of these rewiring methods allows us to draw few broad conclusions about their suitability in each of these settings. A random-walk
We refer to the right hand side of equation where the power of the normalized augmented adjacency is measuring the number of walks of distance from i
7

---

Published as a conference paper at ICLR 2022
Connell
Toxas
Wisconsin
Chameloon 0.25
Squirel 0.22
Actor
Cor
Citeseer
Pabased
H(G)
0,11
0.06
0.16
0.24
0.83
0.7L
0.79
None
52.69
0.21
61.19 1 0.49
54.60
+ 0.68
41.80 1 0.41
39.83
0.14
28.70 + 0.09
81.89
0.79
72.31
0.17
78.16
0.23
Undirectad
53.20 = 0.53
63.38 + 0.87
51.37
= 1.15
42.63
0.30
40.77
0.16
2
IBA
68.29 + 0.49
64.82
+: 0.29
55.48
42.33
0.17
40.74
28.68
0.16
81.00
0.18
70.47
0.18
79.48
0.12
DIGL (PFR)
58.26 0.50
62.03
1 0.43
49.53
1 0.27
42.02
0.13
34.38
0.11
30.79
0.10
83.21
0.27
73.29
+ 0.17
78.84
0.08
DIGL Undirected
59.54 + 0.64
63.34 + 0.38
52.23
+ 0.54
42.68
+ 0.12
33.36
+ 0.21
29.71
0.111
SDRF
54.60 60 1: 0.39
64.46
1: 0.38
55.51
+ 0.27
43.75
= 0.31
40.97
+ 0.14
29.70
0:13
82.76 0.23 72.58 + 0.20 79.10
0.11
SDRF Undinected
0.34
70.35
+ 0.60
+ 0.86 44.46
+: 0.17
0.21
29.85 #.007
Table 2: Experimental results on common node classification benchmarks. Top two in bold.
approach such as DIGL tends to improve the connectivity among nodes that are at short diffusion distance; since for high-homophily dataset these nodes often share the same label, rewiring method like DIGL is likely to act as graph denoising and yield improved performance. On the other hand, for datasets with low homophily, nodes at short diffusion distance are more likely to belong to different label classes, meaning that a diffusion-based rewiring might inject noise and hence compromise performance also noted in Klicpera et al. (2019). Conversely, curvature-based approach as SDRF modifies the edge set mainly around the most negatively curved edges, meaning that it decreases the bottleneck without significantly increasing the connectivity among nodes with different labels. In fact, long-range dependencies are often more relevant in low-homophily settings, where nodes sharing the same labels are in general not neighbors. This observation is largely confirmed by experimental results reported in the next section
a low-homen now-homophily dataset,
5 EXPERIMENTAL RESULTS
Experiment setup. To demonstrate the theoretical results in this paper we ran a suite of semi- supervised node classification tasks comparing our curvature-based rewiring method [SDRF method[SDRFio DIGL from Klicpera et al. (2019) (GDC with the PPR kernel) and the +FA method from Alon & Yahav 22021) where the last layer of the GNN is made fully connected. We evaluate the methods on nine datasets: Cornell, Texas and Wisconsin from the WebKB datase Chameleon and Squirrel (Rozemberczki et al. 2021) along with Actor (Tang et al. 2009): and Cora (McCallum et al. 2000).
Citeseer (Sen ct al. 2008) and Pubmed (Namata et al. 2012). J. Statistics for these datasets can be found
in Appendix F.1 Our base model is a GCN (Kipf& & Welling 2017). Following (Shchur et al. (0018)
and Kllicprra et al. 2019) we optimized hyperparameters for all preprssspprproosssiingg combinations
separately by random search over 100 data splits. Results are reported as average accuracies test set used once with 95% confidence intervals calculated by bootstrapping. We compared the performance on graphs with no preprocessing, making the graph undirected, +FA, DIGL, SDRE, and the given combinations. For DIGL + Undirected we symmetrized the diffusion matrix as in Klicpera al. (2019), and for SDRF Undirected we made the graph undirected before applying SDRF. For more details on the experiments and datasets see Appendix F and for the hyperparameters used for each model and preprocessing see Appendix
Node classification results. Table 2 shows the results of the experiments. As well as reporting results we give a measure of homophily H()) proposed by Pei et al. (2019) (restated in Appendix F equation 21.. by which we can see our experiment set is diverse with respect to homophily. We see that SDRF improves upon the baseline in all cases, and that the largest improvements are seen on the low-homophily datasets. We also see that SDRF matches or outperforms DIGL and +FA most datasets, supporting our argument that curvature-bane rewiring a viable candidate for improving GNN performance.
Graph topology change. Furthermore, SDRF preserves the graph topology to a far greater extent than DIGL due to its surgical nature. Table 3 shows the number of edges added / removed by the two preprocessings on each dataset as percentage of the original number of edges. We see that for optimal performance DIGL makes the graph much denser, which significantly affects the node degrees and may negatively impact the time and space complexity of the downstream GNN, which typically are (EE). In comparison, SDRF adds and removes similar number of edges and approximately preserves the degree distribution. The effect on the full degree distribution for three
l/www/wwkh/
8

---

Published as a conference paper at ICLR 2022
origial Ied. SA
Orgral
D.G.
15
22
64
150
15
32
ze
stz
3004
64 100 255 512 1004
(a) Wisconsin:
(b) Actor:
(c) Pubmed:
Wi (Origiiaa, DIGL) 11.83
Wi (Original, DIGL) 243.81
Wi (OrOiiginal, DIGL) 247.01
Wi(Original, SDRF) 0.28
Wi Wi (Original, SDRF) 1.03 Wi (OOOriginal SDRF) 0.03
Figure 4: Comparing the degree distribution of the original graphs to the preprocessed version. The x- axis node degree log, scale, and the plots are a kernel density estimate of the degree distribution. In the captions we see the Wasserstein distance W1 between the original and preprocessed graphs.
datasets is shown in Figure 4 We see that the de- gree distribution following SDRF is close to, or in some cases indistinguishable from, the orig- inal distribution, whereas DIGL has more no- ticeable effect. We also compute the Wasser- stein distance between the degree distributions, denoted by W1 in the figure captions, numer- ically confirm this observation. For this analysis extended to all nine datasets see Appendix F22
DIGL
SDRF
Cornell
351.1% / 0000%
7.8% / 33.3%
Texas
483.3% 0.0%
2.4% / 10.4%
Wisconsin
300.6% 0.0%
1.4% / 7.5%
Chamelcon
336.1% / 11.8%
6.4% 6.4%
Squirrel
228.8% 1.9%
0.7% 0.7%
Actor
2444.0% / 2.3%
5.4% / 9.9%
This difference is also visually evident from Fig- urelolin Appendix [F3 where we again observe that SDRF largely preserves the topology of the Cornell graph and that the curvature (encoded by the edge color) is homogenized across the graph. We also see that the entries of the trained network's Jacobian between node's prediction and the features of its 2-hop neighbors (encoded as node colors) are increased over the graph, which we may attribute to both DIGL and SDRF's ability alleviate the upper bound presented in Theorem and thus reduce over-squashing
Cora
3038.0% 0.5%
1.0% / 1.0%
Citeseer
2568.3% 0.0%
1.1% 1.1%
Pubmed
2747.1% 0.1%
0.2% 0.2%
Table 3: % edges added removed by method.
CONCLUSION
In this paper, we studied the graph bottleneck and the over-squashing phenomena limiting the performance of message passing graph neural networks from geometric perspective. We started with Jacobian approach to determine how the over-squashing phenomenon is dictated by the graph topology in equation 2 We then investigated further how the topology induces the bottleneck and hence causes over- wver-squashing. We introduced a new notion of edge-based Ricci curvature called Balanced Forman curvature, relating it to the classical Ollivier curvature (Theorem (2). We then proved in Theorem 4 that grrattveel-curved edges are responsible for over-squashing, calling for a possibility of curvature-base based rewiring of the graph in order to improve its bottleneckedness. We show one such possibility (Al (Algorithm T). inspired by the classical Ricci flow and comment on the advantages of surgical method such this. We show both theoretically and experimentally that the proposed method can be ad advatageouus compared to a diffusion- based rewiring approach, opening the door for basse rewiring methods for improving GNN performance going forward.
Limitations and future directions. Our paper establishes geometric perspective the graph bottleneck and over squashin,,, providing new tools to study and cope with these phenomena. One limitation of our work is that the theoretical results presented here do not currently extend to multi- graphs. In addition, the current methodology is agnostic to information beyond the graph topology, such as node features. In future works, we will develop notion of the curvature and the corresponding rewiring method that can take into account such information.
This research was supported in part by the EPSRC CDT in Modern Statistics and Statistical Machine Learning (EP/S023151/1 and the ERC Consolidator Grant No. 724228 (LEMAN). X.D. gratefully acknowledges support from the Oxford-Mee Institute of Quantitative Finance and the EPSRC (FP/T003333/1).
Acknowledgements.

---

Published as a conference paper at ICLR 2022
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference Learning Representations, 2021. URL httptt::/pppeeeeeeeeee net/foruu 1o= 10l==800PPOOR 80CPhOCVH2
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2019.
Marian Boguna, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M Angeles Serrano. Network geometry. Nature Reviews Physics, pp. 1-22, 2021.
Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-)):007-117, 1998.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv:2104. 13478, 2021.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In NeurIPS, 2019.
Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Problems in analysis, pp. 195-200. Princeton University Press, 2015.
Fan Chung. Four proofs for the cheeger inequality and graph partition algorithms. In Proceedings of ICCM, volume 2, pp. 378. Citeseer, 2007.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92, American Mathematical Soc., 1997.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In D. Lee, M. Sugiyama, Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran As- sociates, Inc., 2016. URL
/ http:////ppooceeennneeerr.....o.
neeeiinnurrig pdf
44dffd434de 2aad3344441cbbbb222bbbbeeeeeeeee
Robin Forman. Discrete and computational geometry, 2003.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing
of data structures. IEEE Trans. Neural Networks, 95):768-786, 1998.
Linton C Freeman. A set of measures of centrality based betweenness. Sociometry, pp. 35-41, 1977.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1263-1272. PMLR, 2017.
Christoph Goller and Andreas Kuchler. Learning task-dependent distributed representations by backpropagation through structure. In ICNN, 1996.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEFE International Joint Conference Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Richard Hamilton. The ricci flow on surfaces. In Mathematics and general relativity, Proceedings of the AMS-IMS-SIAN Joint Summer Research Conference in the Mathematical Sciences Mathematics in General Relativity, Univ. of California, Santa Cruz, California, 1986, pp. 237-262. Amer. Math. Soc., 1988.
10

---

Published as a conference paper at ICLR 2022
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In NeurlPS, 2017.
Jürgen Jost and Shiping Liu. Ollivier's s ricci curvature, local clustering and seevaatureddimensin inequalities on graphs. Discrete & Compulational Geometry, 51 51(2)300-322, 2014.
Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Differentiable graph module
(dgm) graph convolutional networks. arXiv preprint arXiv:2002.04999 2020. URL https
//arxiv.
04999. pdf
Henry Kenlay, Dorina Thanou, and Xiaowen Dong. Interpretable stability bounds for spectral graph filters. arXiv preprint arXiv:2/02.09587, 2021.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks, In Proceedings of the Sth International Conference on Learning Representations, ICLR '17, 2017. URL
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
Yong Lin, Linyuan Lu, and Shing-Tung Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, 63(4))605-627, 2011.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL htttps:://pocceediinot www.ees.eeiii..ccm http://eeeeee......ooooc.oo///// wweeurips.ccpppppeeeeeeee
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, pp. 2153-2164, 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Monti, K. Otness, and M. M. Bronstein. Motifnet: motif-based graph convolutional network for directed graphs. In JEEE Data Science Workshop, 2018
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, pp. 4602-4609, AAAI Press, 2019.
Florentin Münch. Non- negaaivte ollivier curvature on graphs, reverse poincar', 'e inequality, buser inequality, liouville property, harnack inequality and eigenvalue estimates. arXiv preprint arXiv:1907.133 2019.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp. 2012.
Chien-Chun Ni, Yu-Yao Lin, Jie Gao, and Xianfeng Gu. Network alignment by discrete ollivier-ricci flow. In International Symposium Graph Drawing and Network Visualization, pp. 447-462. Springer, 2018. htRlsttps:/// httpaaiiivvvoo.a org absp://bb/////// 00320
Chien-Chun Ni, Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific reports, 91):1-12, 2019.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. 2019.
Yann Ollivier. Ricci curvature metric spaces. Comptes Rendus Mathematique, 345(11):644-66) 646, 2007.
11

---

Published as a conference paper at ICLR 2022
Yann Ollivier. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256(3):80-886) 2009.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Seong-Hun Paeng. Volume and diameter of a graph and ollivier's ricci curvature. European Journal of Combinatorics, 1888) 1819, 2012.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. 2019.
Grisha Perelman. Finite extinction time for the solutions to the ricci flow on certain three-manifolds arXiv preprint math/0307245, 2003.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. CoRR, abs/2004. 11904, 2020. URL
11198
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, Journal of Complex Networks, 9(2)ccnab014, 2021.
Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific reports, 8(1):1-16, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.
Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In NIPS workshop, 2018.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, jan 2021. doi: 10. 10.1088/2632-21532 abbf9a. URL
abbff/
Alessandro Sperduti. Encoding labeled graphs by labeling RAAM. In NIPS, 1994.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Trans. Neural Networks, 633):714-735, 1997.
R P Sreejith, Karthikeyan Mohanraj. Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curvature for complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2016(6): doi: 10.
063206, Jun 2016. ISSN 1742-5468.
6//6//66////0//006666 URL URLhttp!
7/dx. orgg
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '09, pp. 807-816, New York, NY, USA, 2009, Association for Computing Machinery. ISBN 9781 605584499, doi: 10. 10.1145/1557019.155 15501999.5551111 108. URL U.R.https::/ddo org/
10 0e.1145/1557111
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liô, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. UtL/itttss:/ggpeeeeee
net. wtt.///rmmmmmmdrmppppop
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning on point clouds. ACM Trans. Graphics, 38(5):1-12. 2019.
Melanie Weber, Emil Saucan, and Jürgen Jost. Coarse geometry of evolving networks. Journal of complex networks, 6(3)7706732, 2018.
12

---

Published as a conference paper at ICLR 2022
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 Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR. OpenReview.net, 2019.
Y. Zhang, S. Pal, M. Coates, and D. Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. AAAI Conference on Artificial Intelligence, 2019.
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
13

---

Published as a conference paper at ICLR 2022
APPENDIX
The Appendix is structured as follows:
(i) In Appendix A we prove Lemma 1 and a side-result about the role of self-loops. We also summarize how to extend the analysis in Lemma to message passing models with sum aggregations (not average), meaning those architectures where we do not normalize the adjacency matrix.
(ii) In Appendix B
introduce and deseribe different quantities use to characterize the neighbourhood of a given edge ~ These objects are all essential to studying the new notion of balanced Forman curvature. The focus is on how computationally tractable way without losing too much accuracy.
distinguish 4-cycles in
(iii) In Appendix C we provide a brief literature review about existing curvature candidates. In particular, we report the definitions of (modified) Ollivier curvature and Forman curvature.
(iv) In Appendix D we prove the statements in Section 3 i.e. Theorem 2 Corollary 3 Theorem and Proposition 5 We also comment on the role of the assumptions and compare the bound in Theorem 2 with the existing literature. Finally, we relate the classical notion of betweenness centrality to the over-squashing effect and the negatively curved edges in graph.
(v) In Appendix B prove the results in Section 4 namely Theorem Canorem@annd analogous result.
(vi) In Appendix F we describe more fully the experiments from Section including a full anal- ysis degree distribution (Appendix F2 and the hyperparameters used in our experiments (Appendix F.4
(vii) In Appendix G we comment on hardware specifications.
A PROOFS OF RESULTS IN SECTION 2
Lemma 1. Assume an MPNN as in equation
Let i, E V with s E Sr+1(1). If Vod S and
/ & B for S SES r, then
ah (r+1)
$ (a,3))+((A"")
Or,
Proof. Let i E V and (1). We recall that to ease the notations we assume that node features and hidden representations are scalar. The proof the more general higher-dimensional case follows without any modification. We compute
oh (r+1)
0. (0,,,h..)),
dr.
n
+ (2..(...)
Σ 1==1
aijn (Dr0, ( + O20 (o.)).,,1))))
We iterate the computation above and see that the right hand side can be expanded
Oh (r+1)
Σ
Σ
ākj. ... Gi
(X)O,, h (0)
dr.
Je....to
for some functions Zij of the input features obtained products of + partial derivatives of the maps de and r partial derivatives of the maps the. Since ( X, have
Oz, 1 (0)
1/ 800n
14

---

Published as a conference paper at ICLR 2022
meaning that the previous sum becomes
an!-t1)
Σ
Σ
Σ
Öijy Ck 1- ... 0kg Ni to (X).
0z.
Seundh (.E())))
AiE((de
the only non-vanishing terms the sum above are the minimal walks from to In fact, if there existed a different choice of coefficients yielding non-zero term then we would find a walk joining i to of length lesser than r + which is contradiction with the definition of geodesic distance. Since Z (X) ) is product of + 1-partial derivatives of the aggregation and update maps and by assumption their gradients are bounded by a and / respectively, we conclude that
Since di(i, (
Ol:
(11))
2 (a
Σ Jrswn
āeg asrs. ....ajs = a a*+1(A"" (Art)))
dx,
which completes the proof of the Lemma.
As a byproduct of this analysis, we can also provide rigorous motivation for the role of self-loops in GNNs (see Appendix for details):
Corollary 7. If h (1+1) = =Enn+b((hh)) then h (P+1) only depends on nodes that can be reached via walks of length exactly { + 1. By adding self-loops, the GNN also takes into account nodes that can be reached via walks of length se+1.
Proof. If ((( Eyns ve(hg9) for each & [0, L 1], then argue in the proof of Lemma Mand find
an(et1)
Σ ag a an (..
(2.))
Oz,
Jeund
The combinatorial coefficient asj. ajs non-zero iff there exists walk from to s of length exactly 2+1, since we are not taking into account the contribution coming from self-loops. Conversely, if each term Oij. was replaced by a.j, then we would find that â.z, ... jjis non-zero iff there exists a walk from to 8 of length at most 1, since the diagonal entries are now positive.
Remark 8. As specific instance of Corollary 7 we note that if we do not include self-loops in the adjacency matrix, then the output of 2-layer simplified graph neural network at node is independent of the features of neighbours k that do not form triangle with i. Once again here the dependence is precisely measured via the Jucobian of the hidden features with respect to the input features.
Remark 9. We note that the role of self-loops has also implicitly been noted in Xu et al. (2018) where the analysis of the Jacobian of node representations on the graph augmented with self-loops has been related lazy random-wald
GNNs with different aggregations We note that similar conclusions extend message passing architectures where the aggregations are sums and not averages meaning that we take the augmented adjacency without normalizing by the degree matrices. Consistently with Lemma 1, we restrict to the setting where features and node representations at each layer are scalars to make the discussion simpler. In line with the Xu et al. (0118) we consider GNN-model of the form
h ((+ ReLU
Σ JEAG
100l h We
Note that the augmented neighbourhood Ni defined as NG U (i). Differently from the setting of Theorem in Xu al. (218)) the aggregation here is not average but simple sum. Let now take nodes i and s such that s E 51+1(1) as in the statement of Lemma [ In this case, instead of simply considering the quantity (0((++1) /0r,)
normalize the Jacobian entries obtaining what
15

---

Published as a conference paper at ICLR 2022
is referred to as inffuence score in Xu al. (2018):
anfr+1)
In-1(1,8)
(1+1)
Σn
dzz
This of course represents now relative importance of feature I, on the representation of node i layer r + If similarly to Theorem 1 in Xu al.] (2018) we assume that all paths in the computational graph of the model are activated with the same probability, then we obtain that on average
Art1
A+1
Tr+1 Jr+1(1,8)
A
Vol( (ol(B.+1(3)
where Ā A+ and vol(S) = Ejes dz. In partieular, we again find that if we have a tree structure, then the right hand side decays exponentially 2 2-(+1))
B PRELIMINARY ANALYSIS OF AN EDGE-NEICHBORHOOD
Given an edge ~ j. we introduce the sets below:
(i) (a (i) n Si(),, the number of triangles based at the edge ~.j.
(ii) (i, {k E (1) S1 S1(1), + j: Ew (S) n Si()) (i)), the number of nodes k E S1 (i) forming a 4-cycle based at i ~ j without diagonals inside.
(ii) Q,U) = (1) (t U f (i, j)), simply the complement of the neighbours of with respect the sets introduced in (i) and (ii) once also exclude j.
In the following we simply write da, fu and Q; when the edge i j is clear from the context.
4-cycle contributions. In general the sets thb and Fu may differ. This may occur when there exists a node k belonging to di that admits multiple solutions w as in the definition of Hb This feature needs be taken into account when comparing Ollivier's Ricci curvature the new notion present below. We first introduce the following class to ease the notations.
Definition 2. For any simple, undirected graph G = (V, E), ifU C V, then we set
D(U) = (:: U |0| = |p(U),, (z,p(z)) E E, U}.
We note that any E D(U) is injective. We may now define quantity which measures the maximal number of 1-1 pairings that can be performed from & to K
Definition 3. For any edge we let
(i.j) = max {ull: U UC Up: o e D(U)).
We often simply write tm. While the quantity 4 plays a role the derivation Ollivier curvature is not computationally -fienddl, to determine 4m need to identify and distinguish all
of j j possible 4-cycles based at ~ j and then choose a maximal pairing map. Accordingly, we consider a looser term which easier to compute:
Definition 4. For any pair of adjacent nodes i we define
"imac (inaci max
max
-A,-A; A, A,)) 1), max
max (AA,. (A A, A.)) A,)) -11
kE
weth
where As denotes the s-th of the adjacency matrix. We usually simply write Tmar-
16

---

Published as a conference paper at ICLR 2022
We note that given k E S1)1) S1(5) the term (Ak (A3- A, A2)) yields yields the number of nodes w forming a 4-cycle of the form i k ~ w ~ ~ i with no diagonals inside. The value "max measures the maximal degeneracy of edges forming 4-cycles, meaning that it is equal to I iff for each & E i there exists unique node E th such that i ~ k
Remark 10.
i is 4-cycle.
We now end the discussion about 4-cycle contributions by proving the following inequality, which allows us avoid to compute directly the term + up to giving up some accuracy.
Lemma 11. For any edge j we have
max 1 1ol
Tmax
Proof. The proof is based on combinatorial argument. Let 2 [ ky and let = (ki...., )2). with & < By definition there exists &0 (kI.... ke) + [wr.... we). with k; ~ and E the for < i S l. Given # {A1,...., kee. then there are E # {wi...., we} such that k ~ w, otherwise we could extend ip by setting h + (ok) == w and we would then get |m l + 1. Accordingly, we have
Σ (Aw, (Ai Aú (.A.A.) A.)) - 1) 2 |+bb
which implies
(Aur, (A; - O A.)) - 11
7max
Timax
C
EXISTING CURVATURE CANDIDATES
Ollivier Ricci curvature
For i E V and E [0, 1) we define probability measure Bj by:
a, j =
1 :f:je
ب. S 0, otherwise.
Before we introduce the Ollivier curvature, we recall that the transportation distance between two finitely supported probability measures as above can be computed
Wi (1
inf Σ
Σ
Me (k, w).
KES)()) wE81()
where . is the geodesic distance on the graph and the infimum is taken over all matrices M satisfying the marginal constraints:
Σ
Mew = (w),
Σ
Mew = p. (k).
kESi())
WES
We now ready to define the Ollivier Ricci curvature: the formulation below is due to Lin et al. (011). Definition 5. Given i j we define the a-Ollivier curvature by
Ka (i.j) := W1 Wi
Since K. (1 - a1 is increasing and bounded the quantity below is well-defind::
1 W1 (n (np .p))
x(i.j)
lim a-+1
a
17

---

Published as a conference paper at ICLR 2022
Forman Ricci curvature In the following report formula for the augmented Forman Ricci curvature on unweighted graphs Samal et al. (2018). We also note that Forman curvature on graphs has also been studied in Sreejith et al. (2016); Weber et al. (2018).
Definition 6. For any edge i ~ j the augmented Forman curvature is given by
F(i.)) 4 3
We note that such formulation of curvature does not distinguish contributions coming from 4-cycles. In fact, for the orthogonal grid with degree d 2 4, Forman Ricci curvature is equal to 2(2 d) < 0. This does not reflect that the r-hop neighbourhood for such a graph grows polynomially in r.
We conclude this appendix by reporting a lower bound for the Ollivier Ricci curvature derived in Jost Liu (2014). We recall that Ra. with a E [o, 1) was defined in equation 7
Theorem 12 (Jost& & Liu (014)). For any edge j. with d: S dj. the following bound is satisfied:
(1
(1
Hal
ko((,)) 2 ((1,)) ==
+
d, dj
dj
di dj
di
dj
D PROOFS OF RESULTS IN SECTION
We first recall our definition of Balanced Forman:
Definition 7. For any edge i we let Ric(i, be zero if mrmmin dg} = L, otherwise
2 2 |tal
max d + IFAL
+ (Amaa))
Ric(i, j) = d, dj
(1#b/+ 1:-
(9)
min dd max,di, di, dg}
where the last term is set be zero if [1bb1 (and hence |# is zero.
We also extend the previous definition to the weighted case. In this setting we let G = (V, F,,, be a simple, locally finite, undirected graph with normalized weights. We first report the formula for the augmented Forman in the weighted case Samal et al. (2018):
why
F(i,)) = w() + w(J)+ +
WA
kES: (1ns: (1)
wi))
Wij
Σ
w(i)
Waj
Witk
Wik
where Wa is taken to be the Heron formula for the area of a triangle while w(.) denotes some weighting scheme for the nodes as well. We propose similar definition for the weighted case, which reduces to the one discussed above in the combinatorial setting. We recall that W is the weighted adjacency matrix while is the combinatorial one. Moreover, we write A = (A, A,)+ and similarly for Wj.
Definition 8. For any pair of adjacent nodes i, E V we define Ric to be 0 if min [d,), |d,|} = otherwise we set
Ric(i. = di
Way Wite
+
1
Way Wij
d
V
kE
kEQs
1
max d
WA
KEST (1)
Wij
Wiy (Tmar)
WiyU
Wm
max d4, d,}
di
kEll
Wiy (Tmax)) -1 max dr. d,}
Wij
Wn
d,
ketS
18

---

Published as a conference paper at ICLR 2022
with
1
Wa = (wif + w + wFk)), zE((()))()))
3
and, for a given +D
W3 AA vD Aş A3"
A Wj A& A3
w w +
4
Important convention. Without losing generality, in the following we always assume that 1 < d, S dy. particular, we write d; = d and dj d s, for some s 2 0. omitting specify that both d and are of course depending on and j. Moreover, from now on we only focus on the unweighted case.
We can now prove our main comparison theorem.
Theorem 2. Given unweighted graph G. for any edge i j we have k(i,)) 2 Ric(i,
Proof. We stick to the aforementioned convention: d; := S dj =dd==++ d. proof amounts to finding a transportation plan providing an upper bound for Wi (Hf" (4)) and hence a lower bound for the curvature k(i,j) j). In particular, we consider plans moving the mass μuf from (1) to (j).
The strategy the
If d = 1, then the optimal transport plan consists of moving the mass from i to j and the remaining mass a on j to ()). This yields a unit Wasserstein distance between μa² and 1& and hence zero Ollivier curvature K x(i, j). which coincides with the value of balanced Forman Ric(i,j).
Assume now that d 2 2. A (possibly non-optimal) transport plan from μ to j is given by:
(i) Move mass (1 (1-a)/(d+s) from each node k E tD C #b to its unique image in to under bijection & as per definition of P.:
(ii) The remaining mass on each node ls E = will need to travel by at most distance to Si)..
(iii) The extra-mass (1 - (1dd))/1////////aaa + s)) on each common neighbour i E F4 will need to travel by most distance 2 to S (j).
(iv) Move the mass (1 - ad from j to S1().
(v) Move the mass a from i to j. This leaves left-over mass (1-a)/(d (dd((++++))))))))))))))))))))() at from the distribution pd.. This mass be compensated from mass in (1) which is distance one.
(vi) Finally, we move the mass (1 - (1-a)/d of any untouched node in S1(1) to S1() along path of length lesser or equal than three. Note that the remaining mass is equal to ((1 - a)/dddd
Htll l=m) - (1 a)(d + s), where the last terms comes from (v).
we sum all the contributions we find
1
1
1 112
1 1-a 1 a d+s s
Wi (4f m3) (1 a:)
d + 3|
+ 2|FA
dds)
+
d+s)
d
d+s)
1
+3(1 a)
(d 1 HA H
d +
(1 a)
d+ (-2/1al 2 - 2) (- 2) +2 +
(1 a)
|3/t
= |t
2|
4 2 + +(d +2((+ +
d+
Therefore we have
1 W(4 11)
+ 2 + 4 4 4 - 2(d + $s) 8)))
k(i,j) = lim
(3|t
+
a=1
a
d d+s
19

---

Published as a conference paper at ICLR 2022
By using Lemma 11 can bound the right hand side as
1 d (3Hal العاا + (Timax) "1"( + + + - 2(d +))) 3))) Ric(i,
x(i,j)
which completes the proof.
Remark 13. By inspection Ric(i, 2 5), with ((i,j) as in Theorem 12 We have three cases:
(i) (i.j) = 2/d+ 2/(d + 5) - /// + 8) + Hial/d s Ric because Ric(i, j)
takes into account the positive contribution of 4-cycles well.
(i) ((i,)) - 1/d 1/(d 1/ s), which happens iff
d+ d
Hta 0
and
d+ - -
| / S O.
d
From the previous inequalities derive
Ric(i, 2 ((i,)) + d (2 (2-d-st Hal + ادداي + 2) 2 (ii,))
1
(mi) ((i.5) = |#al/(d + 8) which is equivalent to
d+ - 2- -Ha < O.
In this case we have
Hial
Ric(i, 2 ( + dd
Corollary 3. (i,,)() 2 0 for any edge j. then there exists a polynomial P such that [B,(1) < P(r), ViEV.
Proof. This follows immediately from Theorem 2 and Bishop-Gromov type of result for discrete Ollivier curvature on graphs Paeng (2012).
To address the proof of Theorem 4 first need the Lemma below.
Lemma 14. Given j. with d, dj. if Ric(i,, s -2 + d, for some < 8 < (1 + 7mmax) -1, then
|0₂1
> 8-1
H +
Proof. According to convention let d, d and dj d + for 2 0. We also recall that Q (EA) If multiply equation by d, d 8, we see that Ric(i, S 8 iff
4 4+2 $ + 3/1a| + | + ymd (Ithl + I& 8(1 + | + 1 1Qyl)-
d
By assumption
10 8) 2 0, meaning that
8(1 + |A + 10,1) 2 4
2
+
+3/aa|
+
اددد 2 3//al
$ 2
Therefore, we conclude
Q
3
2
|
8
Theorem 4. Consider MPNN as in equation]
Let i ~ j with dg S d3 and assume that:
20

---

Published as a conference paper at ICLR 2022
(i) Vodl I and V for each e L 1, with L 2 2 the depth of the MPNN.
(i) There exists 8 s.I. 0 < 8 < (max ( di dj}) -
*, 0 < Vmma and Ric(i, S - d.
Then there exists Q2 (i) satisfying [2,1 > 8-1
and for 0 to S L - 2 we have
ah (c0+2)
1
< <aa3))54.
[
(6))
kEQ
Proof. As usual we let d; := d and dj == + 8, for some 2 0. We first observe that from the requirement dd + s) & 1 in (ii, we derive Ric(i, - -2 +
4 4+ 8 + 3 + اماا + Ymix (1=b1 + I= & 8(d + s).
d
Therefore we have
8|FA| (3 ") s (d(+
meaning that
8|tA| 1 1.
(10)
From now we let Q, denote again the complement Si( (1) U (a)). Without loss of
generality we set tu = 0 and hence h; = z;; the very same proof applies to any other choice of lg- Given & Qj, since (2()), we apply Lemma I and derive
ah (2)
S (a)))
(11)
0x;
We may expand the power of the augmented normalized adjacency matrix as
(A)
Σ
1
Vida + 1)(d, +1)
du
WEST (
If we introduce the set Q, = tk E Qj oz > 11. we can then write
Σ (A) = Σ
Σ
V(d. 1) +1)
d +1
KEQ;
kEQ,
(K))())
Σ KEQ,
Σ kEQ,
Σ Vdl + wES: (
(12)
Vd. +1
Vd, + 1 dg +1
du +
where in the last equality we have again used the fact that & E Qj iff there w E S To avoid heavy notations, introduce Va = (i)k (i) Si). Let first focus on the first sum in equation 12
We have
Σ KEQ,
S
10,
S
S
(13)
Vd. +1
dd
+1 +1
dd, +
dj +
dd
-
We now consider the second sum in equation
12
We assume F 2 1, otherwise Q
0. We let
1
1 2 C |
Ω w Ed: dn
+
C
for some C O to be chosen below. Then, the second sum in equation 12 can be split as
Σ
Σ
(14)
Vds
+I
du +
du +
kEQ,
wEVen
wEVi
21

---

Published as a conference paper at ICLR 2022
Since any w V& has degree at least three, bound the first term in equation
14
Σ
Σ
Ve
n
vdx
dw +1
v dd
kEQ;
weVnn
kE
We now observe that
Σ kEQ,
VE n
Σ
Eivi V1 n 1 (k: w)
E k w
max duy weD
|s2]-
dd
kEQ,
Since du 11/C + 2/C for any Ω see that the first term in equation 14 can be bounded by
IV
Σ
Σ
Σ
dd +1 kEQ,
du +
vdz
+1
wEVena
kEQ,
2
|0
2 C
+
+
(15)
C
C
4
C
HA
by definition of F2 We now bound the second term in equation 14as as
ClFa
Σ
Σ
[V/ \ 22
dd
du +1
dd +1 1Q
REQ,
WEV
kEQ;
where we have used that d 2 ClHa
[Q if E V2 \ 122 Since
Vi 22
[Vel
<
VlVal S Vital
dx +1
[A)
V
we see that
CliAl
Cla
Σ
\ S
(16)
V dd +1
|4,
Q1
K
We are now ready to complete the proof the theorem. According to equation Ti suffices to show that
Σ (AP)
8//4
KEQ,
From equation 12 and equation 13 we derive that the left hand side of the equation above is bounded by
Σ(A9)
Σ
Σ
+ [Qjl
Q2
12
dd
+
dn
+1
KEQ;
kE
WEVe
$ 8 +
Q11
dd
du
+
KEQ;
WE Vv
where in the last inequality we have used Lemma 14 bound |Qyl-1 by 8. In partieular we note that d. = 0 then Q, = 0. and the bound would be simply controlled by as claimed. When [ia] > we can use equation 15 and equation 16 to estimate the second term from above by
S
Q2
ddh
d +1
KEEq
we Vo
1
12,1
2
|ta]
)
10,1 (CHAl
(
1
+ 2|Ha| )
Claal
1Q,1 Viial.
[02]
C
C
4
22

---

Published as a conference paper at ICLR 2022
By applying Lemma 14 we get
4 ((c cIQ,)
2|1
Cltal 14
- 1 4
((c+2()
+
v HA
+ cōv lEal
We now choose
=
1/4, 1-4, so that the previous quantity can be bounded by
JHA I 1 ( 2 ( C5 Covisals 1 (5t + +2622)2)) + +
1 08 25a 8
4
where in the last inequality we have used equation 10 Therefore, we have shown that
(A 5
82 262 + 5 s <35
Q2
kEQ;
where we have used that 5 < 1. This completes the proof (once we absorb the extra factor 3 in the constant a:3 in equation 11
Remark 15. The requirement ó. m//mxxds, dj} < can be replaced by a more general bound by 1//max/d, ] < r. The argument above extends to this case up to renaming the constant aB in the statement so to include an extra factor r. We note that the condition ö max/d;, dj} would be stronger than the one appearing in (ii) of Theorem 4
In this regard, recall that for d-tree the curvature satisfies Ric(i. - 3.
We can also prove Proposition
Proposition 5. If Ric(ci, j) 2 k > for all i ~ then 21/2 2 hg 2 A
Proof. This follows as an immediate Corollary of Theorem 2 and (Lin al. 2011 Theorem 4.2).
Betweenness centrality to measure bottleneck. In equation 2 we have derived how the topology of the graph affects the dependence of the hidden node representation nn(++)) on the input feature re- for nodes i, 8 at distance r + 1. We note that in this case A is exactly measuring the number of minimal paths from to s. the receptive field B,+1 is binary tree, then we have seen that the entry of the power matrix decays exponentially. The reason for such decay stems from the existence of exponentially many nodes in the receptive field combined with the lack of multiple minimal paths (shortcuts). When such conditions hold, most of the minimal paths go through the same nodes, which is exactly what happens for the tree where each node in the minimal paths between different branches. Since the frequency in which a node appears in the minimal path of distinct pairs of nodes measured by the betweenness centrality Freeman (1977), we propose a topological characterization of the 'bottleneckedness' of graph as follows:
Definition 9 (bottleneck). The bottleneck- of G is by = Em b(i), where b(i) denotes the betweenness centrality on node
From standard combinatorial argument it follows that if G is connected, then
bg = Σ (da(i.j) -).
(17)
We note that by 0 iff G is the complete graph K,, Therefore, by determines how far the given topology is from Kn,, with the latter representing the limit case of fully connected layer Alon & Yahav 2222) where no bottleneck may occur as any pair of nodes would be neighbours. This further supports our intuition that the betweenness centrality is good topological candidate for providing a global measurement of bottleneckedness in the graph.
also follows from equation [7 that any update to the graph topology consisting of edge additions would decrease be and thus reduce the bottleneck. The quantity be is global in nature though and hence lacks robustness. As a pedagogical example, consider a barbell G(m, 2r + 1), with m the size of the two cliques joined by a path of length 2r + 1 and focus the edge i in the middle of
such path. Nodes and j are central to the graph. in the sense that most minimal paths go through them and indeed their betweenness centrality is b(i) i) b(j) (m + r)2 + (m r). If now we add
23

---

Published as a conference paper at ICLR 2022
single edge joining the two cliques Km, the values b(1) and b(j) decrease dramatically by Q0m2 + +r). Since the operation non-local, we see that the representation 1, of any MPNN is unaffected by the edge addition for any & E r), and similarly for j. Eventually, if we keep adding edges, the receptive fields B, (t) will be affected for small values of as well: the drawback of such approach is that the resulting adjacency may be significantly different. Conversely, the curvature provides more precise, local and hence robust way of controlling the bottleneck and hence the over-squashing problem. Nonetheless,
relate the betweenness centrality to the Jacobian of the hidden features.
Theorem 16. Given i ~ j. let 22 = Si(i) n (I() U (b). If Ric(i, S - + 6, for 0 < 8
(1 + Tbmax) -1 then
1 S2
b(k) 2 8-
kEn
Proof. We rewrite the quantity in the statement
Σ b(k) + 8(1) 16))
HA +
REE
By definition, given node & E V, the betweenness centrality of k is given by
(kc(k)
b(k) ==
Σ
s, L.EVispk Oat
where aat is the number of minimal paths between and while (k)) is the number of minimal paths from s to passing through k. For convenience, we introduce the set Q2 c Qj defined by
2 = fw E Qi Oie > 1}.
Equivalently, Q consists those nodes in Si \ (1) which form a 4-cycle based at ~ j with diagonal inside. Indeed, if w E Q2 and dir > 1, then there exists more than one minimal path between i and w, in addition to the one passing through node j. For any such path there exists k E (1) n (w)) Since w E Q2 and Q2 n #h = we derive that E Si( as well. We then get
(k)
Σ b(k) kEta
Σ
Σ
Σ
Σ (k).
Ost
RELA &.EV:spk.t7k
kE
wEQ,
WEQ,
kEdA
By summing (inn() for all & E ia we obtain all the 2-long minimal paths between i and w with the exception of the one passing through j:
1
Σb(k)
b(k) N
Σ
(otw 1).
(18)
Oiw
RE
WEQ,
On the other hand we also have
Tee (i)
Oie
b(j)
Σ
(19)
Tat
Osc
diz
8. s.EVV j.
=EQ;
=EQ,
By combining equation 18 and equation 19 we finally get
Σ kEta
b(k) + B(J)
Σ
(oi - 1)+ Σ
+1
+1
Fww
diz
IWEQ,
=EQ,
12y1+
Σ
1
HA
+1
14) Oiz
=EQ,
I0,1
F
+
where in the last equality we have used that by definition di for all 2 E Q, \ Q,. By Lemma 14 the last quantity is larger than 8-1
24

---

Published as a conference paper at ICLR 2022
E PROOFS OF RESULTS IN SECTION 4
Theorem 6. Let S C with vol(S) S vol(G) Then bs,a I ( 11a)) der(S) dan(S)
hg, where (wvg(S)
and (S) are the average and minimum degree on S, respectively.
Proof. Given signal V + R on the vertex set and U C V, analogously to Chung (007), we introduce the notation
V
f(U) = EE((). f(i).
IEU
Let us rewrite the new Cheeger constant h5,0 as follows:
hg.0
1
Σ
(Ra)is
[.]] Xs (s)
S
iESJES
with Xs the characteristic function of the subset S, i.e xs(i) = l E S. Since the graph G is connected, we can bound hs,a from above as
(5)
1
Raa)y S
Σ
(Ra)
d3 1
|8| | DR
S
(S)
dinia (S)
iES
iES.JE
was proven in (Chung 2007
Lemma 5) that
1 las).
XsDRR, (5)
(20)
a
By applying equation equation 20 to the bound for the Cheeger constant hs,a finally that
1
1
1 jas)
1
hssa
[ Xs R,
|S| Xs Xa
(S)
S
a
dmin
(S)
1 hgvol(S)
a
hs davg (5)
S a
dmin(S)
a dmin ())
We also report an equivalent result, again relying on (Chung 2007 Lemma 5).
Proposition 17. Let S V with vol(S) vol(G)/2. For any l N, there exists Sn S with vol(Sk,o) 2 vol(S)(1 (2k)-1) such that
(Ra)i S k 1
hs:
a
jES
for all i E Sk.c-
Proof. Let ki E By modifying slightly the argument in (Chung 2007
Lemma 5), we derive that
Ska = {i ( S X; (5() 2 k
hs}
satisfies
a jas| 2 vol( Sal(Sk,ol )k a hs.
2a
Therefore, we obtain
vol(S% (a()))a) vol(S)
We then conclude that the complement Sh has volume greater or equal than vol(S) (22kk) -2k)-1) - which completes the proof.
The previous proposition shows that after sparsifying the personalized page rank operator Ra suggested in Klicpera et al. (2019) by setting entries below some threshold equal to zero, there will still be only few edges connecting different communities, once again highlighting that random- walk based methods generally not suited to tackle the graph bottleneck.
Remark 18.
25

---

Published as a conference paper at ICLR 2022
F EXPERIMENTS
Our experiments in this paper are semi-supervised node classification (semi-supervised that the graph structure provides some unlabelled information) nine common graph learning datasets. Cornell, Texas and Wisconsin are small heterophilic datasets based on webpage networks from the WebKB dataset. Chameleon and Squirrel (Rozemberczki al. 202T are medium heterophilic datasets based on Wikipedia networks, along with Actor, the actor-oni. only induced subgraph of the film- director-actor-wrice network (Tang et al. 2009). Cora (McCallum et al. 2000), Citeseer (Sen et al.. 2008) and Pubmed (Namata et al. 2012) are medium homophilic datasets based on citation networks. As in Klicpera et al. (2019), for all experiments we consider the largest connected component of the graph.
When splitting the data into train/validation/test sets, we first separate the data into development set and the test set. This is done once to ensure the test set is not used for any training hyperparameter fitting before the final evaluation. For each of the 100 random splits the development set is divided randomly into train set and validation set, where on the validation set. We fit hyperparameters by random search, maximising the mean accuracy across the validation sets. The accuracy then reported in Table 2 the from models trained on the train sets with the chosen hyperparameters, along with 95% confidence interval calculated by bootstrapping the test accuracies with 1000 samples. For Cora, Citescer and Pubmed the development set contains 1500 nodes with the rest kept for the test set, and for each random split the train set chosen to contain nodes of each class while the rest form the validation set. As this is the same method as Klicpera et al.] (2019) and we use the same random seeds, we are using the same test set and expect have comparable results. For the remaining datasets we perform 60/20/20 split, with 20% of nodes set aside as the test set and then for each random split the remaining 80% is split into 60% training, 20% validation.
train models the train set and evaluate
accuracy the test set
The homophily index HG)) proposed by Pei et al. (2019) is defined as
Number of v's neighbors who have the same label as v Number of v's neighbors
H(G)
(21)
V
VEV
F.1 DATASETS
For datasets with disconnected graphs, the statistics shown here are for the largest connected compo-
Cornell
Texas
Wisconsin
Chameleon
Squirrel
Actor
Cora
Citeseer
Pubmed
H(G)
0.11
0.06
0.16
0.25
0.22
0.83
0.72
0.79
Nodes
140
135
184
832
2186
4388
2485
2120
19717
Edges
219
251
362
12355
65224
21907
5069
3679
44324
Features
1703
1703
1703
2323
2089
931
1433
3703
500
Classes
5
Directed?
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
26

---

Published as a conference paper at ICLR 2022
F.2 DEGREE DISTRIBUTIONS
SKG SORT
6045
15
129
35
32
12
35
30
128
(a) Cornell:
(b) Texas:
(c) Wisconsin:
W1 (Original, DIGL) = 10.99
Wi (Original, DIGL) 17.98
Wi Wi (Original, DIGL) 11.83
W1 (Original, SDRF) = 1.01
W1 (Original, SDRF) 0.39
Wi (Original, SDRF) = 0.28
orginal
Otgral
Orgiul 50.3
2007
512
(d) Chameleon: W1 (Originn,,, DIGI.) = 96.30
(e) Squirrel:
(f) Actor:
W1 (Original, DIGI.) 135.41
W (Original, DIGI.) = 243.81
Wi (Original, SDRF) = 1.93
Wi Wi (Original, SDRF) 0.50
Wi (Original, SDRF) = 1.03
Digg
DELL
Cora:
(h) Citeseer:
Pubmed: Wi (Original, DIGL) = 217.01
Wi (Originaa, DIGL) = 247.84
Wi (Original, DIGL) = 178.28
W, (Original, SDRF) = 0.14
Wi (Original, SDRF) 0.15 Wi (Original, SDRF) = 0.03
Figure 5: Comparing the degree distribution of the original graphs to the preprocessed version. The axis is node degree in log, scale, and the plots are a kernel density estimate of the degree distribution. In the captions we see the Wasserstein distance W1 between the original and preprocessed graphs
27

---

Published as a conference paper at ICLR 2022
F.3 VISUALIZING CURVATURE AND SENSITIVITY FEATURES
Joottben
Figure 6: Rewiring of the Cornell graph. Lest-to-right: original graph, DIGL, and SDRF rewiring. Edges are colored by curvature; nodes are colored by the maximum absolute entry of trained 2-layer GCN's Jacobian between the GCN's prediction for that node and the features of the nodes hops away in the original graph. SDRF homogenizes curvature and so lifts the upper bound the Jacobian from Theorem DIGL also does to an extent, though at the expense of preserving graph topology.
F.4 HYPERPARAMETERS
Table 4: Hyperparameters for GCN with preprocessing (None).
Hidden depth
Hidden dimension
Learning rate
Weight
Dataset
Dropout
decay
Cornell
0.3060
128
0,0082
0.1570
Texas
0.2346
128
0,0072
0,0037
Wisconsin
0.2869
64
0,0281
0.0113
Chamelcon
0.7304
128
0.0248
0.0936
Squirrel
0.5974
0.0136
0.1346
Actor
0.7605
64
0.0290
0.0619
Cora
0.4144
64
0,0097
0,0639
Citeseer
0.7477
128
0.0251
0.4577
Pubmed
0.4013
0.0095
0.0448
Table 5: Hyperparameters for GCN with the input graph made undirected (Undirected).
Hidden depth
Hidden dimension
Learning rate
Weight decay
Dataset
Dropout
Cornell
0.6910
64
0.0185
0.0285
Texas
0.2665
128
0.0069
0.0035
Wisconsin
0.2893
128
0.0142
0.0001
Chameleon
0.4657
0.0189
0.0423
Squirrel
0.5944
64
0,0081
0.0309
Actor
0.6626
64
0.0195
0.0219
28

---

Published as a conference paper at ICLR 2022
Table 6: Hyperparameters for GCN with the last layer made fully connected (+FA from Alon &
Yahav (202T).
Hidden depth
Hidden dimension
Learning rate
Weight decay
Dataset
Dropout
Cornell
0.2643
128
0,0216
0.0760
Texas
0.2207
128
0.0102
0.4450
Wisconsin
0.2613
0.0057
0.0131
Chamelcon
0.7783
0.0156
0.0108
Squirrel
0.3654
64
0.0077
0.1922
Actor
0.3824
64
0.0165
0.1168
Cora
0.7840
128
0.0149
0.1429
Citeseer
0.5460
0.0066
0.0758
Pubmed
0.3376
128
0.0204
0.0215
Table 7: Hyperparameters for GCN with DIGL preprocessing, or Graph Diffusion Convolution with PPR kernel (DIGL). Descriptions for a, and can be found in Klicpera al. (2019).
Hidden depth
Hidden dimension
Learning rate
Weight decay
Dataset
Dropout
k
Coreell
0.6294
64
0.0134
0.0258
0.1795
64
Texas
0,2382
128
0,0063
0.0153
0.0206
32
Wisconsin
0.2941
128
0.0083
0.0226
0.1246
0.0001
Chameleon
0.4191
128
0.0052
0.0001
0.0244
64
Squirrel
0.6844
128
0.0056
0.4537
0.0395
32
Actor
0,7820
64
0,0170
0.0102
0.1584
128
Cora
0.3315
64
0.0284
0.0572
0.0773
128
Citeseer
0.5561
64
0.0094
0.5013
0.1076
0.0008
Pubmed
0.4915
128
0.0057
0.0597
0.1155
128
Table Hyperparameters for GCN with DIGL preprocessing followed by symmetrizing the graph diffusion matrix (DIGL Undirected).
Hidden depth
Hidden dimension
Learning rate
Weight decay
Dataset
Dropout
CE
k
Cornell
0.6294
64
0.0134
0.0258
0.1795
64
Texas
0,2382
128
0.0063
0.01533
0.0206
32
Wisconsin
0.2941
128
0.0083
0.0226
0.1246
0.0001
Chameleon
0.4191
128
0.0052
0.0001
0.0244
64
Squirrel
0.7094
0.0172
0.0192
0.1610
64
Actor
0.4012
64
0.0161
0.0141
0.0706
0.0016
Cora
0.3315
64
0,0284
0.0572
0.0773
128
Citeseer
0.5561
64
0.0094
0.5013
0.1076
0.0008
Pubmed
0.4915
128
0.0057
0.0597
0.1155
128
29

---

Published as a conference paper at ICLR 2022
Table Hyperparameters for GCN with SDRF preprocessing (SDRF). Max iterations, T and C+ are the SDRF parameters described in Algorithm
Dataset
Dropout
Hidden depth
Hidden dimension
Learning rate
Weight decay
Max
C
iterations
Comell
0.2411
128
0.0172
0.0125
135
0.25
Texas
0,5954
128
0.0278
0.0623
47
172
2.25
Wisconsin
0.6033
1
128
0.0295
0.1920
27
32
0.5
Chamelcon
0.7265
I
128
0.0180
0.2101
832
77
3.35
Squirrel
0.7401
2
16
0.0189
0.2255
6157
178
0.5
Actor
0.6886
128
0.0095
0.0727
1010
69
Cora 0.3396
128
0.0244
0.1076
100
163
0.95
Citeseer 0,4103
1
64
0.0199
0.4551
84
180
0.22
Pubmed
0.3749
3
128
0.0112
0.0138
166
115
14.43
Table 10: Hyperparameters for GCN with the input graph made undirected followed by SDRF preprocessing (SDRF + Undirected).
Dataset
Dropout
Hidden depth
Hidden dimension
Learning rate
Weight decay
Max iterations
C+
Comell
0.2911
128
0.0056
0.0336
126
145
0.88
Texas
0.2160
64
0.0229
0,0137
22
1.64
Wisconsin
0,2452
64
0.0113
0.1559
136
12
7.95
Chameleon
0,4886
32
0.0268
0.4056
2441
252
2.84
Squirrel
0.4249
64
0.0295
0.1397
787
43
17.19
Actor
0.6705
128
0.0115
0.0447
1141
44
11.17
G HARDWARE SPECIFICATIONS
Our experiments were performed on server with the following specifications:
Component
Specification
Architecture
x86_64
CPU
40x Intel(R) Xcon(R) Silver 4210R CPU @ 2.40GHz 4x GeForce RTX 3090 (2426MMiB/GPU)
GPU
RAM
126GB
OS
Ubuntu 20.04.2 LTS
30


Reviews:
[{"review_id": "l19T-EuvxvG", "reviewer": "Reviewer_idLR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Detailed comments:\n- A critical aspect of rewiring is its effect on the structure and topological properties of the underlying graph. This is not captured by just analyzing the number of added/ removed edges across the graph. I think that it would be more useful to analyze graph characteristics (such as the node degree distribution) or to measure the distance of the original and the rewired graph globally, e.g., with a transportation distance. \n- Can you comment on the cost of curvature-based rewiring vs. random walk-based rewiring? If curvature-based rewiring is less efficient than random walk-based rewiring, is this (in your experiments) mitigated by a reduced cost in the downstream task (due to the smaller number of edges).\n- In section 4 you briefly remark that curvature-based rewiring may reduce over-smoothing. I think it could be interesting to expand on that.\n", "summary_of_the_paper": "The authors propose a new graph rewiring approach that utilizes a discrete notion of Ricci curvature to mitigate over-squashing. This is motivated by a link between negatively curved edges and graph bottlenecks. The paper has a theoretical focus, but also provides a set of validation experiments to demonstrate the proposed approach.", "summary_of_the_review": "I found the paper very interesting in that it analyzes the over-squashing problems through a new, geometric lens. The theoretical motivation for using curvature-based tools as opposed to random-walk-based rewiring is well-done. My main concern is that the authors’ notion of graph structure preservation is not convincing to me. The experiments could be more comprehensive. Please see detailed comments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K9waDPEsE7B", "reviewer": "Reviewer_LDyA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is well-written and well-organized. Formalizing the concept of over-squashing is interesting and timely, and is of interest to the field. This paper, as is often the case when one delves into novel grounds, makes somewhat arbitrary choices in order to move forward: the definition of over-squashing is somewhat arbitrary, the choice of working with that particular definition of Ricci curvature could be more motivated. Efforts are however made in an interesting direction, and the several discussions around the Cheeger constant gives depth to the paper, and its main messages.\n\n- minor: Appendices F and G are announced at the beginnning of the Appendix section but I did not have them in my pdf document\n", "summary_of_the_paper": "In this paper, the authors work on the over-squashing effect that has been recently observed in the GCN literature, namely the effect that, in a message-passing paradigm and for a learning problem that necessitates long-range interaction between distant nodes, the existence of bottlenecks in the graph (for instance an edge e with very large betweenness centrality) will intuitively distort the information that needs to travel from distant nodes and thus hinder the GCN's performance.\n\nOne natural direction of research is to add edges (and sometimes remove others in order to keep the complexity under control) to alleviate the bottlenecks. This rewiring process may be done in different ways and the authors suggest one particular algorithm that they compare with state-of-the-art.\n\nIn particular, the contributions are:\n- a precise (even if somewhat arbitrary) definition of an over-squashing measure between two nodes $i$ and $s$ that is simply the Jacobian of the node representation at $i$ with respect to the entry $x_s$. The smaller this measure, the less $i$ \"feels\" $s$, the larger the over-squashing effect. The goal of the paper is to find a way to understand how to alleviate the bottlenecks responsible for this effect\n\n- to this end, the authors suggest a new definition of Ricci-like curvature defined over the edges of the graphs. This new definition has one main property which is theorem 3: it lower bounds the Ollivier curvature. This then enables to obtain Cor. 4, and finally the main result Thm 5, that states, in a nutshell, that negatively curved edges are the ones causing bottlenecks.\n\n- a concrete rewiring algorithm is suggested, in which two steps are repeated until convergence or max iteration is reached: a first stochastic step is performed where an edge is added to alleviate the edge that has minimal curvature, before a deterministic step where the edge with maximal curvature (typically those in cliques) is removed if it is larger than a threshold\n\n- a tentative analysis, in the form of Thm 8, as well as experiments show the authors' method performs as well or outperforms other rewiring methods (they mainly compare with DIGL) while keeping the number of total edges after rewiring under control", "summary_of_the_review": "This is novel work on a seemingly important effect hindering GCN performance in general. Giving a formal definition of over-squashing and providing an analysis based on curvature is novel work, and potentially very useful to the field. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "583iS7M5keP", "reviewer": "Reviewer_Za5a", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall the paper is well written, however, the paper improve further to have better readability. It would be helpful to have more intuitive clarity on the use of hyperbolic spaces since many readers may not be familiar with the topic. Throughout the paper, homophilic and hetherophilic nature of graphs are mentioned, however, the exact definitions of them are not clearly defined. Further, in experiments “low-homophily” is mentioned, but there is not measure for low or high homophily. I suggest that the authors provide a proper definition for homophilic/heherophilic as [1,2] and provide numerical measures for datasets used in experiments as in [1]  \n\nThe main weak point of the paper is experiments. First of all, is it fully-supervised node classification of semi-supervised node classification? The experiments are not substantial in terms of dataset selections, comparisons with baseline methods and obtained accuracy. \n\na) The selected baseline methods are limited, can the authors use further baselines methods? Can the proposed graph rewiring method be compared with the +FA method in  [1]?\n\nb) To my knowledge Cora is not a homophilic dataset [1]. It would be helpful if more datasets from hetherophilic graphs (Citeseer, Pubmed) are also considered in experiments, which would allow us to  have a better understanding of the over-squashing phenomenon.\n\nc) Cornell, Texas and Wisconsin are small scale datasets. I suggest to experiments with Chameleon or/and Squirrel dataset, which have large number of nodes and dense graphs. \n\nd) Why are accuracies of Cornell, Texas, and Wisconsin low? There are methods that have shown greater accuracy for these datasets [1]. I wonder whether the low accuracy is due to the use of GCN and if a different GNN method is used in with the proposed rewiring method the accuracy would increase. Do authors have any experience with other models?  \n\n\n\nReferences\n[1] Eli Chien and Jianhao Peng and Pan Li and Olgica Milenkovic, Adaptive Universal Generalized PageRank Graph Neural Network,\nInternational Conference on Learning Representations (2021)\n\n[2] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks.  International Conference on Learning Representations (2019)", "summary_of_the_paper": "This paper analyzes oversquashing in GNN using geometric methods. The paper proposes a novel rewiring method based on negative curvature to construct graphs that are less susceptible to oversquashing. Though the theoretical contribution is strong the empirical evidence is not strong. Overall a good paper. ", "summary_of_the_review": "A good paper with a novel ideas on oversquashing in GNN. The main limitation of the paper is the limited of empirical support.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1ognaWiUJk", "reviewer": "Reviewer_kUJT", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "## Strengths\n* The paper provides good intuitions to over-squashing. This intuition is visualized in Figure 1 that gives a good intuition of over-squashing and of the proposed SDRF solution.\n* Further, the paper provides a good connection to graph curvatures that allows to measure and analyze over-squashing.\n* The paper provides a thorough analysis using the proposed notations and connects it to further geometric theoretical and classical ideas.\n* The paper provides a good conceptual comparison to random-walk-based rewiring and whether this can address the GNN bottleneck, and also an interesting discussion about the likelihood of GNN bottlenecks in homophilic and heterophilic datasets.\n* The evaluation shows that the proposed SDRF method outperforms the DIGL baseline without a significant increase in the amount of computation compared to the original graph structure, while the DIGL baseline adds an order of magnitude more edges, which increases the computation cost.\n\n## Weaknesses\n\n* Generality - I am not sure how do these results generalize beyond Graph Convolutional Networks (GCN). The use of GCN's augmented normalized adjacency matrix is assumed at the beginning of the paper, and this assumption is never questioned.\nAre Lemma 1 and Corollary 2 correct only for GCN, where it is common to use the augmented normalized adjacency matrix? Specifically, this matrix has $D^{-1}$ which decays messages over paths. What happens if nodes are summed (as in GIN)? How does the signal then decay with the number of layers? Intuitively, I can understand that summing an exponentially growing number of nodes in a single vector cannot compress all the information after some compression steps (that is, GNN layers). But how is this expressed in the curvature theory? If the analysis in the paper refers only to GCN and GNNs which perform averaging, please mention this explicitly.\n\n* Writing - as is, the paper can be perfectly understood only by audiences that are very familiar with all related work. The paper can be significantly improved by giving more background, explaining equations more intuitively, and avoiding unneeded citations which confuse the reader. For example, the paper uses the names such as \"Ricci\", \"Poincare\", \"Ollivier\", and \"Forman\" frequently. These references can confuse audiences who are not familiar with all terms and papers. Specifically, calling the main method \"Balanced Forman\", gives the reader the feeling that they would not really understand the proposed method without understanding the original Forman first. I believe that this is not the case, and that the paper *could* be standalone.\nWhile the authors show an impressive understanding and familiarity with the related and classical work, I advise the authors to avoid this \"name-dropping\", in favor of better readability and accessibility to a broader audience.\nI even think that some parts of the paper can be moved to the appendix, in favor of the readability of the remaining parts. For example, I am not sure that Corollary 2 is new (see below), and I'm not sure whether this is directly related to the point the paper tries to make, or whether is it a side-result.\nSee more specific details below.\n\n* The Evaluation could also be strengthened by addressing more datasets and more GNN types.\nSee more details below.\n\n* Reproducibility - please provide more training details, hyperparameters tuned and ranges, and the final selected hyperparameter values for the experiments in Section 5. A table of dataset statistics (in the appendix) can also help, before and after applying every type of preprocessing method (similarly to Table 3, possibly with absolute numbers as well).\n\n\n## Writing\n\n* Section 2.1: what is \"$(i,j) \\in E$ if $i \\sim j$\"? What does $i\\sim j$ mean? Does it simply mean that there is an edge between them? If it only means that there is an edge between them, why is this a different notation than $(i,j) \\in E$?\n\n* What is $\\hat{a}$ in Equation (1)? I cannot find its definition. Is it $\\hat{A}$? It is unclear from the text.\n\n* Section 2.1:\n>\"$d_{G}$ is the standard minimum-walk (geodesic) distance on the graph\"\n\nIs it simply the **shortest-path**? If so, I suggest using this term which is much more common to the broader audience. If not, the term \"minimum-walk (geodesic) distance\" should be better explained. \n\n* Section 2.1: \n> \"the node features and representations are assumed to be scalar from now on\"\n\nthat is, $p_0 = 1$ and all $p_l$ equal to 1?\n\n* Corollary 2 - I think that the \"Jumping Knowledge\" paper (Xu et al., 2018) had already recognized this role of self-loops. What is the difference between this corollary and Theorem 1 in Xu et al. (2018)? Also, as the role of self-loops is not directly connected to the main contributions of this paper, I suggest considering moving it to the appendix, or removing it if it was already recognized by Xu et al, in favor of more space for explanations of other parts.\n\n* Section 3, definition of $\\lambda_{max}$ - what does \"traversing the same node\" mean? the same $k$ node from the previous definition of 4-cycles? A formal definition of $\\lambda_{max}$ will be helpful.\n\n* Section 3, the example describing Figure 3: I cannot understand the examples because in (ii), $\\sharp_{\\square}^{i}$ is defined for a specific edge $\\sharp_{\\square}^{i}(i,j)$, and here it appears as $\\sharp_{\\square}^{0}$ and $\\sharp_{\\square}^{1}$\n\nAlso, why is $\\sharp_{\\square}^{1}={5}$, and not also the node 0 is included, as it also creates a 4-cycle (1-0-3-5)?\n\n* Corollary 4: what is \"the volume of the geodesic balls\", and what does growing \"polynomially\" exactly mean? How is the volume measured, and what does it grow over? (what is the \"x axis\"?)\n\n* Theorem 5 - it would help if the authors could clarify this theorem, explain its meaning in words and intuitively. I am not sure I understand why every detail there is necessary, and what are its implications. \n\n* Cheeger constant (Equations (5)+(6)) - I did not really understand the notations in Eq. (5), what is the meaning of Equation (6), what is its significance?\n\n##  Evaluation:\n1. It would really improve the evaluation if the authors could experiment with more GNN types and more benchmarks. Specifically, if the authors could take the datasets and exact settings used in Alon & Yahav (2020) and show how the proposed SDRF method improves the results there. The reason that this would be helpful is that Alon & Yahav showed that these datasets already suffer from over-squashing, by taking existing source code of other papers and improving their results. It would be interesting to compare SDRF and the (computationally expensive) solution of Alon & Yahav in terms of the tradeoff between accuracy and computation cost (the overall number of added edges).\n\n2. DIGL is compared to SDRF as the main baseline. However, I couldn't find what exactly does DIGL do. The paragraph about random-walk-based rewiring on page 7 does explain the general idea, but it is unclear whether this is explaining directly about DIGL, or in general about PageRank-style approaches?\n\n## Additional questions to authors\n* According to this analysis, in the authors' opinion, are over-squashing and over-smoothing the same thing or not? What is the difference between them? (The answer to this question will **not** affect the rating negatively, as it is obviously out of the scope of this paper)\nIf the authors have an insightful explanation, I recommend including it in the body of the paper.\n\n\n\n### Other minor comments:\n* The paragraph about Discrete curvatures on graphs on page 4 is completely unclear for the audience who are unfamiliar with the described curvatures. I suggest delaying this to later or even moving to an appendix in favor of more text that will help clarify the rest of the paper.\n\n* Theorem 5(i) writes $\\ell \\in [0, L-1]$. For clarity, I suggest being consistent which previous notations, for example as Lemma 1 which denotes $0 \\leq \\ell \\leq ...$.\n", "summary_of_the_paper": " The paper provides an analytical explanation for the over-squashing and GNN bottleneck phenomena. While Alon & Yahav (2020) demonstrated the over-squashing phenomenon empirically and provided mainly intuitions as to why it happens, this paper performs a deeper analysis and connects over-squashing to combinatorial curvatures. The paper shows that negatively curved edges are responsible for over-squashing. This is important because it allows to measure over-squashing, and pinpoint specific edges that are responsible for it in a given graph. \nFurther, the paper proposes a method (called SDRF) to re-wire the graph based on these insights and shows empirically how this method alleviates over-squashing.\n", "summary_of_the_review": "Despite my many comments, I think that this is an important paper, which deepens our understanding of the over-squashing phenomenon from a geometric perspective.\nWhile many recent GNN papers introduce new application domains, new features, and new GNN architectures, this paper improves our understanding of the foundations of existing GNNs and their limitations, which is even more important.\n\nI will increase my rating if the authors would answer all questions in the \"Writing\" section above, in the \"Additional Questions\" section above, and provide more evaluation datasets (as detailed in the \"Evaluation\" section above).\n\n===== Update =====\n\nI have increased my rating to 10, good work.\n\nNote that Table 2 is now too wide and goes beyond the page's borders.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new technique to handle oversquashing in GNNs by introducing a novel rewiring technique. The reviewers are quite positive about the paper and the rebuttal phase greatly helped clarify the method and it's impact.
Decision: Accept (Oral)