Year: 2021

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.

text: 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.
1 INTRODUCTION
In the past few years, deep learning on graphs and in particular graph neural networks (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; ?; Kipf & Welling, 2017; Gilmer et al., 2017) have become very popular in the machine learning community 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., 2021).
The vast majority of GNNs follow the message passing paradigm (Gilmer et al., 2017), using learnable non-linear func-
tions to diffuse information on the graph. Multiple popular GNN architectures such as GCN (Kipf & Welling, 2017) and GAT (Veličković et al., 2018) can be posed as particular flavors of this scheme and considered instances of a 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 & Yahav (2021) proposed rewiring the graph as a way of reducing the bottleneck, defined as those topological properties in the graph leading to over-squashing. This approach is in line with multiple other results e.g. using connectivity diffusion (Klicpera et al., 2019) as a preprocessing step to facilitate graph learning. Yet, the exact understanding of the over-squashing and how it originates from the bottlenecks in the topology of the underlying graph are still elusive. Consequently, there is currently no consensus on 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 et al., 2021). One notion of curvature that has received attention for graph learning is Ricci curvature (Hamilton, 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 Ricci flow to construct a metric between graphs. Graph Ricci flow was also used in Ni et al. (2019) for community detection. Both of these methods use the edge weights as a substitute for the metric of a manifold, and do not change the topological structure of the graph.
Contributions and Outline. This paper, to our knowledge, is the first theoretical study of the bottleneck and over-squashing phenomena in message passing neural networks from a geometric perspective. In Section 2, we propose the Jacobian of node representations as a formal way of measuring the over-squashing and we show that the graph topology may compromise message propagation in graph neural networks by creating a bottleneck. In Section 3, 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 a new curvature-based method for graph rewiring called Stochastic Discrete Ricci Flow. According to the theoretical results in 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-based 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.

heading: 2 ANALYSIS OF THE OVER-SQUASHING PHENOMENON

heading: 2.1 PRELIMINARIES
text: Let G = (V,E) be a simple, undirected, and connected graph, where (i, j) ∈ E iff i ∼ 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̃ = A+ I be the adjacency matrix augmented with self-loops. Similarly we let D̃ = D + I , with D the diagonal degree matrix, and let Â = D̃− 1 2 ÃD̃− 1 2 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 self-loops are taken into account). Given i ∈ V , we denote its degree by di and let
Sr(i) := {j ∈ V : dG(i, j) = r}, Br(i) := {j ∈ V : dG(i, j) ≤ r},
where dG is the standard shortest-path distance on the graph and r ∈ N. The set Br(i) 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 ∈ Rn×p0 where xi ∈ Rp0 is the feature vector at node i = 1, . . . , n = |V |. We denote by h
(`) i ∈ Rp` the representation of node i at layer ` ≥ 0, with h (0) i = xi. Given a family of message
functions ψ` : Rp` × Rp` → Rp ′ ` and update functions φ` : Rp` × Rp ′ ` → Rp`+1 , we can write the (`+ 1)-st layer output of a generic MPNN as follows (Gilmer et al., 2017):
h (`+1) i = φ` h(`)i , n∑ j=1 Âijψ`(h (`) i , h (`) j )  . (1) Here we have used the augmented normalized adjacency matrix to propagate messages from each node to its neighbors, which simply leads to a degree normalization of the message functions ψ`. To avoid heavy notations the node features and representations are assumed to be scalar from now on; these assumptions simplify the discussion and the vector case leads to analogous results.

heading: 2.2 THE OVER-SQUASHING PROBLEM
text: 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 a graph learning problem has long-range 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 nonadjacent 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 Br(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 over-squashing of information (Alon & Yahav, 2021). In line with Alon & Yahav (2021), we refer to those structural properties of the graph that lead to over-squashing as a bottleneck1.
Sensitivity analysis. The hidden feature h(`)i = h (`) i (x1, . . . , xn) computed by an MPNN with ` layers as in equation 1 is a differentiable function of the input node features {x1, . . . , xn} as long as the update and message functions φ` and ψ` are differentiable. The over-squashing of information can then be understood in terms of one node representation h(`)i failing to be affected by some input feature xs of node s at distance r from node i. Hence, we propose the Jacobian ∂h (r) i /∂xs as an explicit and formal way of assessing the over-squashing effect2.
Lemma 1. Assume an MPNN as in equation 1. Let i, s ∈ V with s ∈ Sr+1(i). If |∇φ`| ≤ α and |∇ψ`| ≤ β for 0 ≤ ` ≤ r, then ∣∣∣∣∣∂h(r+1)i∂xs ∣∣∣∣∣ ≤ (αβ)r+1(Âr+1)is. (2) Lemma 1 states that if φ` and ψ` have bounded derivatives, then the propagation of messages is controlled by a suitable power of Â. For example, if dG(i, s) = r + 1 and the sub-graph induced on Br+1(i) is a binary tree, then (Âr+1)is = 2−13−r, which gives an exponential decay of the node dependence on input features at distance r, as also heuristically argued by Alon & Yahav (2021).
The sensitivity analysis in Lemma 1 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 2, 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.

heading: 3 GRAPH CURVATURE AND BOTTLENECK
text: A natural object in Riemannian geometry is the Ricci curvature, a bilinear form determining the geodesic dispersion, i.e. whether geodesics starting at nearby points with ‘same’ velocity remain parallel (Euclidean 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 a discrete spherical geometry (Figure 2a), the edges would meet at k to form a triangle (complete graph). In a discrete Euclidean geometry (Figure 2b), the edges would stay parallel and form a 4-cycle based at i ∼ j (orthogonal grid). Finally, in a discrete hyperbolic geometry (Figure 2c), the mutual distance of the edge endpoints would have grown compared to that of i and j (tree). Therefore, a Ricci curvature for graphs should provide us with more sophisticated tools than the degree to analyze the neighborhood of an edge.
1We note that the over-squashing issue is different from the problem of under-reaching; the latter simply amounts to a MPNN failing to fully explore a graph when the depth is smaller than the diameter (Barceló et al., 2019). The over-squashing phenomenon instead may occur even in deep GNNs with the number of layers larger than the graph diameter, as tested experimentally in Alon & Yahav (2021).
2The Jacobian of a GNN-output was also used by Xu et al. (2018) to set a similarity score among nodes.
(a) Clique (> 0) (b) Grid (= 0) (c) Tree (< 0)
Figure 2: Different regimes of curvatures on graphs analogous to spherical (a), planar (b), and hyperbolic (c) geometries in the continuous setting.
Curvatures on graphs. The main examples of edge-based curvature are the Forman curvature F (i, j) (Forman, 2003) and the Ollivier curvature κ(i, j) in Ollivier (2007; 2009) (see Appendix). While F (i, j) is given in terms of combinatorial quantities (Sreejith et al., 2016), results are scarce and the definition is biased towards negative curvature. The theory on κ(i, j) instead is richer (Lin et al., 2011; Münch, 2019) but its formulation makes it hard to control local quantities.
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 an edge i ∼ j and we refer to the Appendix for a more complete discussion:
(i) ]∆(i, j) := S1(i) ∩ S1(j) are the triangles based at i ∼ j.
(ii) ]i (i, j) := {k ∈ S1(i) \ S1(j), k 6= j : ∃w ∈ (S1(k) ∩ S1(j)) \ S1(i)} are the neighbors of i forming a 4-cycle based at the edge i ∼ j without diagonals inside.
(iii) γmax(i, j) is the maximal number of 4−cycles based at i ∼ j traversing a common node (see Definition 4).
0 1
2
3
4
5
6
Figure 3: 4-cycle contribution.
In line with the discussion about geodesic dispersion, one expects ]∆ to be related to positive curvature (complete graph), ]i to zero curvature (grid), and the remaining outgoing edges to negative curvature (tree). Our new curvature formulation reflects such an intuition and recovers the expected results in the classical cases. In the example in Figure 3 we have ]0 (0, 1) = {2, 3} while ]1 (0, 1) = {5}, both without 4,6 because of the triangle 1-6-0. The degeneracy factor γmax(0, 1) = 2, as there exist two 4-cycles passing through node 5.
Definition 1 (Balanced Forman curvature). For any edge i ∼ j in a simple, unweighted graph G, we let Ric(i, j) be zero if min{di, dj} = 1 and otherwise
Ric(i, j) := 2
di +
2 dj − 2 + 2 |]∆(i, j)| max{di, dj} + |]∆(i, j)| min{di, dj} + (γmax) −1 max{di, dj} (|]i |+ |] j |), (3)
where the last term is set to be zero if |]i | (and hence |] j |) is zero. In particular Ric(i, j) > −2.
The curvature is negative when i ∼ j behaves as a bridge between S1(i) and S1(j), while it is positive when S1(i) and S1(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 κ(i, j) thanks to our next theorem.
Theorem 2. Given an unweighted graph G, for any edge i ∼ j we have κ(i, j) ≥ Ric(i, j).
Theorem 2 generalizes Jost & Liu (2014, Theorem 3) (see Appendix).We also note that the computational complexity for κ scales as O(|E|d3max), while for our Ric we have O(|E|d2max), with dmax the maximal degree. From Theorem 2 and Paeng (2012), we find:
Corollary 3. If Ric(i, j) ≥ k > 0 for any edge i ∼ j, then there exists a polynomial P such that
|Br(i)| ≤ P (r), ∀i ∈ V.
Therefore, when the curvature is positive everywhere, the bottleneck effect should not play a 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 a learning task on a graph would suffer from over-squashing.
Curvature and over-squashing. Thanks to our new combinatorial curvature and the sensitivity analysis in Lemma 1, 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 1. Let i ∼ j with di ≤ dj and assume that:
(i) |∇φ`| ≤ α and |∇ψ`| ≤ β for each 0 ≤ ` ≤ L− 1, with L ≥ 2 the depth of the MPNN.
(ii) There exists δ s.t. 0 < δ < (max{di, dj})− 1 2 , δ < γ−1max, and Ric(i, j) ≤ −2 + δ.
Then there exists Qj ⊂ S2(i) satisfying |Qj | > δ−1 and for 0 ≤ `0 ≤ L− 2 we have
1 |Qj | ∑ k∈Qj ∣∣∣∣∣∂h(`0+2)k∂h(`0)i ∣∣∣∣∣ < (αβ)2δ 14 . (4)
Condition (i) is always satisfied and allows us to control the message passing functions. The requirement (ii) instead means that the curvature of (i, j) is negative enough when compared to the degrees of i and j (recall that Ric(i, j) > 2). The further condition on γmax 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 `0 = 0. The equation 4 shows that negatively curved edges are the ones causing bottlenecks, interpreted as how the graph topology prevents a representation h(2)k to be affected by non-adjacent features h (0) i = xi. Theorem 4 implies that if we have a negatively curved edge as in (ii), then there exist a large number of nodes k such that GNNs - on average - struggle to propagate messages from i to k in two layers despite these nodes k being at distance 2 from i. In this case the over-squashing occurs as measured by the Jacobian in equation 4 and hence the propagation of information suffers. If the task at hand has long-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 see that the graph can be easily disconnected. This property is encoded in the classical notion of the Cheeger constant (Chung & Graham, 1997)
hG := min S⊂V hS , hS := min S⊂V |∂S| min{vol(S), vol(V \ S)}
(5)
where ∂S = {(i, j) : i ∈ S, j ∈ V \ S} and vol(S) = ∑ i∈S di. The main result about the Cheeger constant is the Cheeger inequality (Cheeger, 2015; Chung & Graham, 1997):
2hG ≥ λ1 ≥ h2G 2
(6)
where λ1 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 \ S := S̄) and few inter-community edges has a small Cheeger constant hG. For nodes in different communities to interact with each other, all messages need to go through the same few bridges hence leading to the over-squashing of information (a similar intuition was explored in Alon & Yahav (2021)). Therefore, hG can be interpreted as a 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 a relationship between hG and the curvature of the graph. The next proposition follows from Theorem 2 and Lin et al. (2011):
Proposition 5. If Ric(i, j) ≥ k > 0 for all i ∼ j, then λ1/2 ≥ hG ≥ k2 .
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-based graph-rewiring methods might fail to significantly alter hG and hence correct the graph bottleneck potentially induced by inter-community edges. This will lead us to propose an alternative curvature-based graph rewiring.

heading: 4 CURVATURE-BASED REWIRING METHODS
text: 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 a trend to decouple the input graph from the graph used for information propagation. This can take the form of graph subsampling or resampling to deal with scalability (Hamilton et al., 2017) or topological noise (Zhang et al., 2019), using larger motif-based (Monti et al., 2018) or multi-hop filters (Rossi et al., 2020), or changing the graph either as a preprocessing step (Klicpera et al., 2019; Alon & Yahav, 2021) 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 in a surgical way by modifying the negatively-curved edges, so to decrease the bottleneck without significantly compromising the statistical properties of the input graph. We also rigorously show that a random-walk based rewiring method might generally fail to obtain an edge set E′ with a significant improvement in its bottleneckedness as measured by the Cheeger constant.
Curvature-based graph rewiring. Since according to Theorem 4 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 strongly-negatively curved edges. To this end we implement a simple rewiring method called Stochastic Discrete Ricci Flow (SDRF), described in Algorithm 1.
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 i ∼ j with minimal Ricci curvature Ric(i, j): Calculate vector x where xkl = Rickl(i, j)− Ric(i, j), the improvement to Ric(i, j) from adding edge k ∼ l where k ∈ B1(i), l ∈ B1(j);
Sample index k, l with probability softmax(τx)kl and add edge k ∼ l to G. 2) Remove edge i ∼ j with maximal Ricci curvature Ric(i, j) if Ric(i, j) > C+.
Until convergence, or max iterations reached;
At each iteration this preprocessing step adds an edge to ‘support’ the graph’s most negatively curved edge, and then removes the most positively curved edge. The requirement on the added edge k ∼ l that k ∈ B1(i) and l ∈ B1(j) ensures that we’re adding either an extra 3- or 4-cycle around the negative edge i ∼ j so that this is a local modification. The temperature τ determines how stochastic the edge addition is, with τ = ∞ being fully deterministic (the best edge is always added). The graph edit distance between the original and preprocessed graph is bounded above by 2 × the max number of iterations. At each step we remove the edge with most positive curvature to balance the distributions of curvature and node degrees. This generally improves performance. We use Balanced Forman curvature as in equation 3 for Ric(i, j). C+ can be chosen to stop the method skewing the curvature distribution negative, including C+ = ∞ to not remove any edges. The method is inspired by the continuous (backwards) Ricci flow with the aim of homogenizing edge curvatures. This is 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 1.
Can random-walk based rewiring address bottlenecks? A good way of understanding the effectiveness of SDRF in reducing the graph bottleneck is through comparison with random-walk based rewiring strategies. Recall that, as argued in Section 3, the Cheeger constant hG of a graph constitutes a rough measure of its bottleneckedness as induced by the inter-community edges (a small hG is indicative of a bottleneck). Suppose we are given a graph G with a small hG and wish to rewire it into a graph G′ with a significantly improved Cheeger constant in order to reduce the inter-community bottleneck. A random-walk based rewiring method such as DIGL (Klicpera et al., 2019) acts by smoothing out the graph adjacency and hence tends to promote connections among nodes at short
diffusion distance (Coifman & Lafon, 2006). Accordingly, such a rewiring method might fail to correct structural features like the bottleneck, which is instead more prominent for nodes that are at long diffusion distance.3 To emphasize this point, we consider a classic example: given α ∈ (0, 1), the Personalized Page Rank (PPR) matrix is defined by (Brin & Page, 1998) as
Rα := ∞∑ k=0 θPPRk (D −1A)k = α ∞∑ k=0 ( (1− α)(D−1A) )k .
Assume that we rewire the graph using Rα, meaning that we replace the given adjacency A with Rα. Since Rα is stochastic, the new Cheeger constant of the rewired graph can be computed as
hS,α = |∂S|α volα(S) ≡ 1 |S| ∑ i∈S ∑ j∈S̄ (Rα)ij .
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. (2019) where we also take into account the effect of the sparsification.
Theorem 6. Let S ⊂ V with vol(S) ≤ vol(G)/2. Then hS,α ≤ ( 1−α α ) davg(S) dmin(S)
hS , where davg(S) and dmin(S) are the average and minimum degree on S, respectively.
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 intra-community edges rather than inter-community edges because it prioritizes short diffusion distance nodes. This is also why this method performs well on high-homophily datasets, as discussed below. In particular, for a fixed α ∈ (0, 1), the bound in Theorem 6 can be very small. As a specific example, consider two complete graphs Kn joined by one bridge. Then hG = (n(n − 1) + 1)−1, which means that the bound on the right hand side is O(n−2).
Theorem 6 implies that a diffusion approach such as DIGL might fail to yield a new edge set E′ with a sufficiently improved bottleneck. By contrast, from Theorem 4 and Proposition 5, we deduce that a curvature-based rewiring method such as SDRF properly addresses the edges that cause the bottleneck.
Graph structure preservation. Although a graph-rewiring approach aims at 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-based rewiring is surgical in nature and hence more likely to preserve the structure of the input graph better than a random-walk based approach. Consider, for example, that we are given ρ > 0 and wish to rewire the graph such that the new edge set E′ is within graph-edit distance ρ from the original E. Theorem 4 tells 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 ρ/2.
Secondly, we also point out that Ric(i, j) < −2 + δ implies that min{di, dj} > 2/δ. Therefore, if we mostly modify the edge set at those nodes i, j joined by an edge with large negative curvature, then we are perturbing nodes with high degree where such a 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), making curvature-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 a few broad conclusions about their suitability in each of these settings. A random-walk approach such as DIGL tends to improve the connectivity among nodes that are at short diffusion
3We refer to the right hand side of equation 2 where the power of the normalized augmented adjacency is measuring the number of walks of distance r from i to s.
distance; since for a high-homophily dataset these nodes often share the same label, a 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 as also noted in Klicpera et al. (2019). Conversely, on a low-homophily dataset, a 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.

heading: 5 EXPERIMENTAL RESULTS
text: Experiment setup. To demonstrate the theoretical results in this paper we ran a suite of semisupervised node classification tasks comparing our curvature-based rewiring method SDRF to DIGL from Klicpera et al. (2019) (GDC with the PPR kernel) and the +FA method from Alon & Yahav (2021), 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 dataset4; Chameleon and Squirrel (Rozemberczki et al., 2021) along with Actor (Tang et al., 2009); and Cora (McCallum et al., 2000), Citeseer (Sen et al., 2008) and Pubmed (Namata et al., 2012). Statistics for these datasets can be found in Appendix F.1. Our base model is a GCN (Kipf & Welling, 2017). Following Shchur et al. (2018) and Klicpera et al. (2019) we optimized hyperparameters for all dataset-preprocessing combinations separately by random search over 100 data splits. Results are reported as average accuracies on a 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, SDRF, and the given combinations. For DIGL + undirected we symmetrized the diffusion matrix as in Klicpera et 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 F.3.
Node classification results. Table 2 shows the results of the experiments. As well as reporting results we give a measure of homophilyH(G) 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 on most datasets, supporting our argument that curvature-based rewiring is 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 a 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,
4http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/
which typically are O(E). In comparison, SDRF adds and removes a similar number of edges and approximately preserves the degree distribution. The effect on the full degree distribution for three
datasets is shown in Figure 4. We see that the degree distribution following SDRF is close to, or in some cases indistinguishable from, the original distribution, whereas DIGL has a more noticeable effect. We also compute the Wasserstein distance between the degree distributions, denoted by W1 in the figure captions, to numerically confirm this observation. For this analysis extended to all nine datasets see Appendix F.2.
This difference is also visually evident from Figure 5 in Appendix F, 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 a 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 to alleviate the upper bound presented in Theorem 4 and thus reduce over-squashing.

heading: 6 CONCLUSION
text: In this paper, we studied the graph bottleneck and the over-squashing phenomena limiting the performance of message passing graph neural networks from a geometric perspective. We started with a Jacobian approach to determine how the over-squashing phenomenon is dictated by the graph topology as in equation 2. We then investigated further how the topology induces the bottleneck and hence causes over-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 negatively-curved edges are responsible for over-squashing, calling for a possibility of curvature-based rewiring of the graph in order to improve its bottleneckedness. We show one such possibility (Algorithm 1), inspired by the classical Ricci flow and comment on the advantages of surgical method such as this. We show both theoretically and experimentally that the proposed method can be advantageous compared to a diffusion-based rewiring approach, opening the door for curvature-based rewiring methods for improving GNN performance going forward.
Limitations and future directions. Our paper establishes a geometric perspective on the graph bottleneck and over-squashing, 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 multigraphs. In addition, the current methodology is agnostic to information beyond the graph topology, such as node features. In future works, we will develop a notion of the curvature and the corresponding rewiring method that can take into account such information.

heading: A PROOFS OF RESULTS IN SECTION 2
text: Lemma 1. Assume an MPNN as in equation 1. Let i, s ∈ V with s ∈ Sr+1(i). If |∇φ`| ≤ α and |∇ψ`| ≤ β for 0 ≤ ` ≤ r, then ∣∣∣∣∣∂h(r+1)i∂xs ∣∣∣∣∣ ≤ (αβ)r+1(Âr+1)is. (2) Proof. Let i ∈ V and s ∈ Sr+1(i). We recall that to ease the notations we assume that node features and hidden representations are scalar. The proof in the more general higher-dimensional case follows without any modification. We compute
∂h (r+1) i
∂xs = ∂1φr(. . .)∂xsh
(r) i
+ ∂2φr(. . .) n∑ jr=1 âijr ( ∂1ψr(h (r) i , h (r) jr )∂xsh (r) i + ∂2ψr(h (r) i , h (r) jr )∂xsh (r) jr ) .
We can iterate the computation above and see that the right hand side can be expanded as
∂h (r+1) i
∂xs = ∑ jr,...,j0 ∑ kr∈{i,jr} · · · ∑ k1∈{i,jr,...,j1} âijr âkrjr−1 . . . âk1j0Zijrkrjr−1...k1j0(X)∂xsh (0) j0 ,
for some functions Zijr...k1j0 of the input features obtained as products of r + 1 partial derivatives of the maps φ` and r + 1 partial derivatives of the maps ψ`. Since H(0) = X , we have
∂xsh (0) j0 = δj0s
meaning that the previous sum becomes
∂h (r+1) i
∂xs = ∑ jr,...,j1 ∑ kr∈{i,jr} · · · ∑ k1∈{i,jr,...,j1} âijr âkrjr−1 . . . âk1sZijrkrjr−1...k1s(X).
Since dG(i, s) = r + 1, the only non-vanishing terms in the sum above are the minimal walks from i to s. In fact, if there existed a different choice of coefficients yielding a non-zero term then we would find a walk joining i to s of length lesser than r + 1, which is in contradiction with the definition of geodesic distance. Since Zi...s(X) is a product of r + 1-partial derivatives of the aggregation and update maps and by assumption their gradients are bounded by α and β respectively, we conclude that ∣∣∣∣∣∂h(r+1)i∂xs ∣∣∣∣∣ ≤ (αβ)r+1 ∑ jr,...,j1 âijr âjrjr−1 . . . âj1s = α r+1(Âr+1)is
which completes the proof of the Lemma.
As a byproduct of this analysis, we can also provide a rigorous motivation for the role of self-loops in GNNs (see Appendix for details):
Corollary 7. If h(`+1)i = ∑ j∼i ψ`(h (`) j ), then h (`+1) i 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 r ≤ `+ 1. Proof. If h(`+1)i = ∑ j∼i ψ`(h (`) j ) for each ` ∈ [0, L − 1], then we can argue as in the proof of Lemma 1 and find ∂h
(`+1) i
∂xs = ∑ j`,...,j1 aij` . . . aj1sψ ′ `(h (`) j` ) · · ·ψ′0(xs).
The combinatorial coefficient aij` . . . aj1s is non-zero iff there exists a walk from i to s of length exactly `+1, since we are not taking into account the contribution coming from self-loops. Conversely, if each term aij` was replaced by âij` then we would find that âij` . . . âj1s is non-zero iff there exists a walk from i to s of length at most r + 1, since the diagonal entries are now positive.
Remark 8. As a specific instance of Corollary 7, we note that if we do not include self-loops in the adjacency matrix, then the output of a 2-layer simplified graph neural network at node i is independent of the features of neighbours k that do not form a triangle with i. Once again here the dependence is precisely measured via the Jacobian 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 to lazy random-walks.
GNNs with different aggregations We note that similar conclusions extend to 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. (2018) we consider a GNN-model of the form
h (`+1) i = ReLU ∑ j∈Ñi h (`) j w`  . Note that the augmented neighbourhood Ñi is defined as Ni ∪ {i}. Differently from the setting of Theorem 1 in Xu et al. (2018), the aggregation here is not an average but a simple sum. Let us now take nodes i and s such that s ∈ Sr+1(i) as in the statement of Lemma 1. In this case, instead of simply considering the quantity |∂h(r+1)i /∂xs|, we normalize the Jacobian entries - obtaining what
is referred to as influence score in Xu et al. (2018):
Jr+1(i, s) := ∣∣∣∣∂h(r+1)i∂xs ∣∣∣∣∑
k ∣∣∣∣∂h(r+1)i∂xk ∣∣∣∣
This of course represents now a relative importance of feature xs on the representation of node i at layer r + 1. If - similarly to Theorem 1 in Xu et 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
Jr+1(i, s) = Ãr+1is∑ k Ã r+1 ik ≤ Ã r+1 is Vol(Br+1(i)) ,
where Ã = A+ I and vol(S) = ∑ j∈S dj . In particular, we again find that if we have a tree structure, then the right hand side decays exponentially as 2−(r+1).

heading: B PRELIMINARY ANALYSIS OF AN EDGE-NEIGHBOURHOOD
text: Given an edge i ∼ j, we introduce the sets below:
(i) ]∆(i, j) := S1(i) ∩ S1(j), the number of triangles based at the edge i ∼ j.
(ii) ]i (i, j) := {k ∈ S1(i) \ S1(j), k 6= j : ∃w ∈ (S1(k) ∩ S1(j)) \ S1(i)}, the number of nodes k ∈ S1(i) forming a 4-cycle based at i ∼ j without diagonals inside.
(iii) Qi(j) := S1(i) \ ({j} ∪ ]∆(i, j) ∪ ]i (i, j)), simply the complement of the neighbours of i with respect to the sets introduced in (i) and (ii) once we also exclude j.
In the following we simply write ]∆, ]i and Qi when the edge i ∼ j is clear from the context.
4-cycle contributions. In general the sets ]i and ] j may differ. This may occur when there exists
a node k belonging to ]i that admits multiple solutions w as in the definition of ] i . This feature needs to be taken into account when comparing Ollivier’s Ricci curvature to the new notion we present below. We first introduce the following class to ease the notations.
Definition 2. For any simple, undirected graph G = (V,E), if U ⊂ V , then we set
D(U) := {ϕ : U → V, |U | = |ϕ(U)|, (z, ϕ(z)) ∈ E, ∀z ∈ U} .
We note that any ϕ ∈ D(U) is injective. We may now define a quantity which measures the maximal number of 1-1 pairings that can be performed from ]i to ] j .
Definition 3. For any edge i ∼ j we let ]m (i, j) := max { |U | : U ⊂ ]i , ∃ϕ : U → ] j , ϕ ∈ D(U) } .
We often simply write ]m . While the quantity ] m plays a role in the derivation of the Ollivier curvature of i ∼ j it is not computationally-friendly, as to determine ]m we need to identify and distinguish all possible 4-cycles based at i ∼ j and then choose a maximal pairing map. Accordingly, we consider a looser term which is easier to compute:
Definition 4. For any pair of adjacent nodes i ∼ j we define
γmax(i, j) := max { max k∈]i {(Ak · (Aj −Ai Aj))− 1}, max w∈]j {(Aw · (Ai −Aj Ai))− 1} } ,
where As denotes the s-th row of the adjacency matrix. We usually simply write γmax.
Remark 10. We note that given k ∈ S1(i) \ S1(j) the term (Ak · (Aj − Ai Aj))− 1 yields the number of nodes w forming a 4-cycle of the form i ∼ k ∼ w ∼ j ∼ i with no diagonals inside. The value γmax measures the maximal degeneracy of edges forming 4-cycles, meaning that it is equal to 1 iff for each k ∈ ]i there exists a unique node w ∈ ] j such that i ∼ k ∼ w ∼ j ∼ i is a 4-cycle.
We now end the discussion about 4-cycle contributions by proving the following inequality, which allows us to avoid to compute directly the term ]m up to giving up some accuracy.
Lemma 11. For any edge i ∼ j we have
|]m | ≥ max{|]i |, |] j |}
γmax .
Proof. The proof is based on a combinatorial argument. Let ]i = {k1, . . . , kr} and let ]m = {k1, . . . , k`}, with ` < r. By definition there exists ϕ : {k1, . . . , k`} → {w1, . . . , w`}, with ki ∼ wi and wi ∈ ]j , for 1 ≤ i ≤ `. Given k ∈ ] i \ {k1, . . . , k`}, then there are no w ∈ ] j \ {w1, . . . , w`} such that k ∼ w, otherwise we could extend ϕ by setting k 7→ ϕ(k) := w and we would then get |]m | = `+ 1. Accordingly, we have∑̀
s=1
(Aws · (Ai −Aj Ai))− 1) ≥ |]i |,
which implies
γmax |]m | ≡ γmax ` ≥ ∑̀ s=1 (Aws · (Ai −Aj Ai))− 1) ≥ |]i |.

heading: C EXISTING CURVATURE CANDIDATES
text: Ollivier Ricci curvature For i ∈ V and α ∈ [0, 1) we define a probability measure on B1(i) by:
µαi : j 7→  α, j = i 1−α di , j ∈ S1(i),
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 as
W1(µ α i , µ α j ) := inf
M ∑ k∈S1(i) ∑ w∈S1(j) MkwdG(k,w),
where dG(·, ·) is the geodesic distance on the graph and the infimum is taken over all matrices M satisfying the marginal constraints:∑
k∈S1(i)
Mkw = µ α j (w), ∑ w∈S1(j) Mkw = µ α i (k).
We are now ready to define the Ollivier Ricci curvature: the formulation below is due to Lin et al. (2011).
Definition 5. Given i ∼ j we define the α-Ollivier curvature by
κα(i, j) := 1−W1(µαi , µαj ). (7)
Since κα(1− α)−1 is increasing and bounded the quantity below is well-defined:
κ(i, j) := lim α→1 1−W1(µαi , µαj ) 1− α . (8)
Forman Ricci curvature In the following we report a 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, j) := 4− di − dj + 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 ≥ 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 κα, with α ∈ [0, 1) was defined in equation 7. Theorem 12 (Jost & Liu (2014)). For any edge i ∼ j, with di ≤ dj , the following bound is satisfied:
κ0(i, j) ≥ Φ(i, j) := − (
1− 1 di − 1 dj − |]∆| dj ) + − ( 1− 1 di − 1 dj − |]∆| di ) + + |]∆| dj .

heading: D PROOFS OF RESULTS IN SECTION 3
text: We first recall our definition of Balanced Forman: Definition 7. For any edge i ∼ j we let Ric(i, j) be zero if min{di, dj} = 1, otherwise
Ric(i, j) := 2
di +
2 dj − 2 + 2 |]∆| max{di, dj} + |]∆| min{di, dj} + (γmax)
−1
max{di, dj} (|]i |+ |] j |) (9)
where the last term is set to be zero if |]i | (and hence |] j |) is zero.
We also extend the previous definition to the weighted case. In this setting we let G = (V,E, ω) 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):
F (i, j) = ω(i) + ω(j) + ∑
k∈S1(i)∩S1(j)
ω2ij ω∆
− ∑
k∈S1(i)\S1(j)
ω(i) √ ωij ωik − ∑ k∈S1(j)\S1(i) ω(j) √ ωij ωjk ,
where ω∆ is taken to be the Heron formula for the area of a triangle while ω(·) denotes some weighting scheme for the nodes as well. We propose a 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 A is the combinatorial one. Moreover, we write Aij = (Aj − Ai)+ and similarly for W ij .
Definition 8. For any pair of adjacent nodes i, j ∈ V we define Ric(i, j) to be 0 if min{|di|, |dj |} = 1, otherwise we set
Ric(i, j) := 1
di 1− ∑ k∈Qi √ ωij ωik + 1 dj 1− ∑ k∈Qj √ ωij ωjk  + 1
max{di, dj} ∑
k∈S1(i)∩S1(j)
ω2ij ω∆
+ ∑ k∈]i ωij ω ( ωij(γmax) −1 max{di, dj} − √ ωijν di )
+ ∑ k∈]j ωij ω ( ωij(γmax) −1 max{di, dj} − √ ωijν dj ) ,
with
ω∆ := 1
3 (ω2ij + ω 2 ik + ω 2 jk), z ∈ S1(i) ∩ S1(j),
and, for a given k ∈ ]i ,
ν := Wz ·Aij Ak ·Aij , ω = 1 4
( ω2ij + ω 2 ik + ν 2 +
Ak ·W ij Ak ·Aij
) .
Important convention. Without losing generality, in the following we always assume that 1 ≤ di ≤ dj . In particular, we write di . = d and dj = d+ s, for some s ≥ 0, omitting to specify that both d and s are of course depending on i and j. Moreover, from now on we only focus on the unweighted case.
We can now prove our main comparison theorem.
Theorem 2. Given an unweighted graph G, for any edge i ∼ j we have κ(i, j) ≥ Ric(i, j).
Proof. We stick to the aforementioned convention: di := d ≤ dj = d+ s, s ≥ 0. The strategy of the proof amounts to finding a transportation plan providing an upper bound for W1(µαi , µ α j ) and hence a lower bound for the curvature κ(i, j). In particular, we consider plans moving the mass µαi from B1(i) to B1(j).
If d = 1, then the optimal transport plan consists of moving the mass α from i to j and the remaining mass 1−α on j to S1(j). This yields a unit Wasserstein distance between µαi and µαj and hence zero Ollivier curvature κ(i, j), which coincides with the value of balanced Forman Ric(i, j).
Assume now that d ≥ 2. A (possibly non-optimal) transport plan from µαi to µαj is given by:
(i) Move mass (1−α)/(d+ s) from each node k ∈ ]m ⊂ ]i to its unique image in ] j under a
bijection ϕ as per definition of ]m .
(ii) The remaining mass on each node k ∈ ]m will need to travel by at most distance 3 to S1(j).
(iii) The extra-mass (1− α)(1/d− 1/(d+ s)) on each common neighbour k ∈ ]∆ will need to travel by at most distance 2 to S1(j).
(iv) Move the mass (1− α)/d from j to S1(j).
(v) Move the mass α from i to j. This leaves left-over mass (1 − α)/(d + s) at i from the distribution µαj . This mass can be compensated from mass in S1(i) which is at distance one.
(vi) Finally, we move the mass (1 − α)/d of any untouched node in S1(i) to S1(j) along a path of length lesser or equal than three. Note that the remaining mass is equal to ((1− α)/d)(d− 1− |]∆| − |]m |)− (1− α)(d+ s), where the last terms comes from (v).
If we sum all the contributions we find
W1(µ α i , µ α j ) ≤ (1− α) ( |]m | d+ s + 3|]m | ( 1 d − 1 d+ s ) + 2|]∆| ( 1 d − 1 d+ s ) + 1 d ) + α+ 1− α d+ s
+ 3(1− α) ( 1
d (d− 1− |]∆| − |]m |)−
1
d+ s ) = (1− α) ( 1
d+ s (−2|]∆| − 2|]m | − 2) +
1 d (−|]∆| − 2) + 2
) + 1
= (1− α) ( 1
d+ s
( −3|]∆| − s
d |]∆| − 2|]m | − 4− 2
s d + 2(d+ s)
)) + 1.
Therefore we have
κ(i, j) = lim α→1 1−W (µαi , µαj ) 1− α
≥ ( 1
d+ s
( 3|]∆|+ s
d |]∆|+ 2|]m |+ 4 + 2
s d − 2(d+ s)
)) .
By using Lemma 11, we can bound the right hand side as κ(i, j) ≥ ( 1
d+ s
( 3|]∆|+ s
d |]∆|+ (γmax)−1(|]i |+ |] j |) + 4 + 2
s d − 2(d+ s)
)) = Ric(i, j)
which completes the proof.
Remark 13. By inspection Ric(i, j) ≥ Φ(i, j), with Φ(i, j) as in Theorem 12. We have three cases:
(i) Φ(i, j) = 2/d + 2/(d + s) − 2 + 2|]∆|/(d + s) + |]∆|/d ≤ Ric(i, j), because Ric(i, j) takes into account the positive contribution of 4-cycles as well.
(ii) Φ(i, j) = −1 + 1/d+ 1/(d+ s) + 2|]∆|/(d+ s), which happens iff
d+ s− 2− s d − |]∆| > 0
and d+ s− 2− s
d − |]∆| −
s d |]∆| ≤ 0.
From the previous inequalities we derive
Ric(i, j) ≥ Φ(i, j) + 1 d+ s
( 2− d− s+ |]∆|+ s
d |]∆|+
s
d
) ≥ Φ(i, j).
(iii) Φ(i, j) = |]∆|/(d+ s) which is equivalent to
d+ s− 2− s d − |]∆| ≤ 0.
In this case we have
Ric(i, j) ≥ Φ(i, j) + s d |]∆| d+ s
Corollary 3. If Ric(i, j) ≥ k > 0 for any edge i ∼ j, then there exists a polynomial P such that
|Br(i)| ≤ P (r), ∀i ∈ V.
Proof. This follows immediately from Theorem 2 and a Bishop-Gromov type of result for discrete Ollivier curvature on graphs Paeng (2012).
To address the proof of Theorem 4, we first need the Lemma below. Lemma 14. Given i ∼ j, with di ≤ dj , if Ric(i, j) ≤ −2 + δ, for some 0 < δ < (1 + γmax)−1, then
|Qj | |]∆|+ 1 > δ−1.
Proof. According to our convention we let di = d and dj = d + s, for s ≥ 0. We also recall that Qj = S1(j)\(]∆∪]j ∪{i}). If we multiply equation 3 by dj = d+s, we see that Ric(i, j) ≤ −2+δ iff
4 + 2 s
d + 3|]∆|+
s d |]∆|+ γ−1max(|]i |+ |] j |) ≤ δ(1 + |]∆|+ |] j |+ |Qj |).
By assumption |]j |(γ −1 max − δ) ≥ 0, meaning that
δ(1 + |]∆|+ |Qj |) ≥ 4 + 2 s
d + 3|]∆|+
s d |]∆| ≥ 4 + 3|]∆|.
Therefore, we conclude |Qj | |]∆|+ 1 ≥ 3 δ − 1.
Theorem 4. Consider a MPNN as in equation 1. Let i ∼ j with di ≤ dj and assume that:
(i) |∇φ`| ≤ α and |∇ψ`| ≤ β for each 0 ≤ ` ≤ L− 1, with L ≥ 2 the depth of the MPNN.
(ii) There exists δ s.t. 0 < δ < (max{di, dj})− 1 2 , δ < γ−1max, and Ric(i, j) ≤ −2 + δ.
Then there exists Qj ⊂ S2(i) satisfying |Qj | > δ−1 and for 0 ≤ `0 ≤ L− 2 we have
1 |Qj | ∑ k∈Qj ∣∣∣∣∣∂h(`0+2)k∂h(`0)i ∣∣∣∣∣ < (αβ)2δ 14 . (4)
Proof. As usual we let di := d and dj := d + s, for some s ≥ 0. We first observe that from the requirement δ2(d+ s) ≤ 1 in (ii), we derive Ric(i, j) ≤ −2 + δ iff
4 + 2 s
d + 3|]∆|+
s d |]∆|+ γ−1max(|]i |+ |] j |) ≤ δ(d+ s).
Therefore we have δ|]∆| ( 3 + s
d
) ≤ δ2(d+ s),
meaning that δ|]∆| ≤ 1. (10)
From now on we let Qj denote again the complement S1(j) \ (S1(i) ∪ ]j ∪ {i}). Without loss of generality we set `0 = 0 and hence h (0) i = xi; the very same proof applies to any other choice of `0. Given k ∈ Qj , since k ∈ S2(i), we can apply Lemma 1 and derive∣∣∣∣∣∂h(2)k∂xi ∣∣∣∣∣ ≤ (αβ)2(Â)2ik. (11)
We may expand the power of the augmented normalized adjacency matrix as
(Â)2ik = 1√
(dk + 1)(di + 1) ∑ w∈S1(k)∩S1(i) 1 dw + 1 .
If we introduce the set Q̂j = {k ∈ Qj : σik > 1}, we can then write∑ k∈Qj (Â)2ik = ∑ k∈Qj 1√ (dk + 1)(di + 1) ∑ w∈S1(k)∩S1(i) 1 dw + 1 =
= 1√ di + 1 ∑ k∈Qj 1√ dk + 1 1 dj + 1 + ∑ k∈Q̂j 1√ dk + 1 ∑ w∈S1(k)∩S1(i)∩S1(j) 1 dw + 1  (12) where in the last equality we have again used the fact that k ∈ Q̂j iff there isw ∈ S1(k)∩S1(i)∩S1(j). To avoid heavy notations, we introduce Vk := S1(k) ∩ S1(i) ∩ S1(j). Let us first focus on the first sum in equation 12. We have
1√ di + 1 ∑ k∈Qj 1√ dk + 1 1 dj + 1 ≤ 1√ di + 1 |Qj | 1 dj + 1 ≤ 1√ di + 1 ≤ 1. (13)
We now consider the second sum in equation 12. We assume |]∆| ≥ 1, otherwise Q̂j = ∅. We let
Ω := { w ∈ ]∆ : dw < 1
C |Q̂j | |]∆| + 2 C } for some C > 0 to be chosen below. Then, the second sum in equation 12 can be split as
∑ k∈Q̂j 1√ dk + 1  ∑ w∈Vk∩Ω 1 dw + 1 + ∑ w∈Vk\Ω 1 dw + 1  . (14)
Since any w ∈ Vk has degree at least three, we can bound the first term in equation 14 as∑ k∈Q̂j 1√ dk + 1 ( ∑ w∈Vk∩Ω 1 dw + 1 ) ≤ ∑ k∈Q̂j 1√ dk + 1 |Vk ∩ Ω| 4 .
We now observe that∑ k∈Q̂j |Vk ∩ Ω|√ dk + 1 ≤ ∑ k∈Q̂j |Vk ∩ Ω| = ∣∣∣{(k,w) ∈ E : k ∈ Q̂j , w ∈ Vk ∩ Ω}∣∣∣ ≤ (max w∈Ω dw ) |Ω|.
Since dw ≤ (1/C)|Q̂j |/|]∆|+ 2/C for any w ∈ Ω we see that the first term in equation 14 can be bounded by∑
k∈Q̂j
1√ dk + 1 ∑ w∈Vk∩Ω 1 dw + 1 ≤ ∑ k∈Q̂j 1√ dk + 1 |Vk ∩ Ω| 4
≤
( 1
C |Q̂j | |]∆| + 2 C ) |Ω| 4 ≤ ( 1 C |Q̂j | |]∆| + 2 C ) |]∆| 4 . (15)
by definition of Ω. We now bound the second term in equation 14 as∑ k∈Q̂j 1√ dk + 1 ∑ w∈Vk\Ω 1 dw + 1 ≤ ∑ k∈Q̂j 1√ dk + 1 C|]∆| |Q̂j | |Vk \ Ω|
where we have used that d−1w ≤ C|]∆|/|Q̂j | if w ∈ Vk \ Ω. Since
|Vk \ Ω|√ dk + 1 ≤ |Vk|√ |S1(k)| ≤ |Vk|√ |Vk|
≤ √ |Vk| ≤ √ |]∆|
we see that ∑ k∈Q̂j 1√ dk + 1 C|]∆| |Q̂j | |Vk \ Ω| ≤ C|]∆| |Q̂j | √ |]∆||Q̂j | = C|]∆| 3 2 . (16)
We are now ready to complete the proof of the theorem. According to equation 11 it suffices to show that
1 |Qj | ∑ k∈Qj (Â2)ik ≤ δ1/4.
From equation 12 and equation 13 we derive that the left hand side of the equation above is bounded by
1 |Qj | ∑ k∈Qj (Â2)ik ≤ 1 |Qj | + 1 |Qj | ∑ k∈Q̂j 1√ dk + 1 ∑ w∈Vk
1
dw + 1  ≤ δ + 1
|Qj | ∑ k∈Q̂j 1√ dk + 1 ∑ w∈Vk
1
dw + 1  where in the last inequality we have used Lemma 14 to bound |Qj |−1 by δ. In particular we note that if ]∆ = ∅ then Q̂j = ∅, and the bound would be simply controlled by δ as claimed. When |]∆| > 0, we can use equation 15 and equation 16 to estimate the second term from above by
1
|Qj | ∑ k∈Q̂j 1√ dk + 1 ∑ w∈Vk
1
dw + 1  ≤ 1
|Qj |
(( 1
C |Q̂j | |]∆| + 2 C
) |]∆|
4
) + 1
|Qj |
( C|]∆| 3 2 ) ≤ 1
4
( 1
C + 2|]∆| C|Qj | ) + C|]∆| |Qj | √ |]∆|.
By applying Lemma 14 we get
1
4
( 1
C + 2|]∆| C|Qj | ) + C|]∆| |Qj | √ |]∆| ≤ 1 4 ( 1 C + 2 δ C ) + Cδ √ |]∆|.
We now choose C = δ−1/4, so that the previous quantity can be bounded by
1
4
( 1
C + 2
δ
C
) + Cδ √ |]∆| ≤ 1
4
( δ 1 4 + 2δ 5 4 ) + δ 1 4 √ δ|]∆| ≤ 1
4
( δ 1 4 + 2δ 5 4 ) + δ 1 4
where in the last inequality we have used equation 10. Therefore, we have shown that
1 |Qj | ∑ k∈Qj (Â2)ik ≤ δ + 1 4 ( δ 1 4 + 2δ 5 4 ) + δ 1 4 ≤ 3δ 14
where we have used that δ < 1. This completes the proof (once we absorb the extra factor 3 in the constant αβ in equation 11).
Remark 15. The requirement δ √
max{di, dj} < 1 can be replaced by a more general bound δ √
max{di, dj} < r. The argument above extends to this case up to renaming the constant αβ in the statement so to include an extra factor r. We note that the condition δmax{di, dj} < r would be stronger than the one appearing in (ii) of Theorem 4. In this regard, we recall that for a d-tree the curvature satisfies Ric(i, j) = −2 + 4d .
We can also prove Proposition 5: Proposition 5. If Ric(i, j) ≥ k > 0 for all i ∼ j, then λ1/2 ≥ hG ≥ k2 .
Proof. This follows as an immediate Corollary of Theorem 2 and (Lin et 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 h(r+1)i on the input feature xs, for nodes i, s at distance r + 1. We note that in this case Âr+1is is exactly measuring the number of minimal paths from i to s. If the receptive field Br+1(i) is a 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 is in the minimal paths between different branches. Since the frequency in which a node appears in the minimal path of distinct pairs of nodes is measured by the betweenness centrality Freeman (1977), we propose a topological characterization of the ‘bottleneckedness’ of a graph as follows: Definition 9 (bottleneck). The bottleneck-value of G is bG := 1n ∑n i=1 b(i), where b(i) denotes the betweenness centrality on node i.
From a standard combinatorial argument it follows that if G is connected, then
bG = 1
n ∑ i,j (dG(i, j)− 1) . (17)
We note that bG = 0 iff G is the complete graph Kn. Therefore, bG determines how far the given topology is from Kn, with the latter representing the limit case of a fully connected layer Alon & Yahav (2021) where no bottleneck may occur as any pair of nodes would be neighbours. This further supports our intuition that the betweenness centrality is a good topological candidate for providing a global measurement of bottleneckedness in the graph.
It also follows from equation 17 that any update to the graph topology consisting of edge additions would decrease bG and thus reduce the bottleneck. The quantity bG 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 on the edge i ∼ j in the middle of such path. Nodes i 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) = b(j) = (m+ r)2 + (m+ r). If now we add a
single edge joining the two cliques Km, the values b(i) and b(j) decrease dramatically by Ω(m2 + r). Since the operation is non-local, we see that the representation h(`)i of any MPNN is unaffected by the edge addition for any ` ∈ (0, r), and similarly for j. Eventually, if we keep adding edges, the receptive fields Bs(i) will be affected for small values of s as well: the drawback of such approach is that the resulting adjacency may be significantly different. Conversely, the curvature provides a more precise, local and hence robust way of controlling the bottleneck and hence the over-squashing problem. Nonetheless, we relate the betweenness centrality to the Jacobian of the hidden features. Theorem 16. Given i ∼ j, let Ωj := S1(i) ∩ S1(j) ∪ {j}. If Ric(i, j) ≤ −2 + δ, for 0 < δ < (1 + γmax)
−1, then 1 |Ωj | ∑ k∈Ωj b(k) ≥ δ−1.
Proof. We rewrite the quantity in the statement as
1
|]∆|+ 1 ∑ k∈]∆ b(k) + b(j)  . By definition, given a node k ∈ V , the betweenness centrality of k is given by
b(k) := ∑
s,t∈V :s6=k,t 6=k
σst(k)
σst
where σst is the number of minimal paths between s and t while σst(k) is the number of minimal paths from s to t passing through k. For convenience, we introduce the set Q̂j ⊂ Qj defined by
Q̂j := {w ∈ Qj : σiw > 1}.
Equivalently, Q̂j consists of those nodes in S1(j) \ S1(i) which form a 4-cycle based at i ∼ j with a diagonal inside. Indeed, if w ∈ Qj and σiw > 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 ∈ S1(i) ∩ S1(w). Since w ∈ Qj and Qj ∩ ]j = ∅, we derive that k ∈ S1(j) as well. We then get∑
k∈]∆ b(k) = ∑ k∈]∆ ∑ s,t∈V :s 6=k,t 6=k σst(k) σst ≥ ∑ k∈]∆ ∑ w∈Q̂j σiw(k) σiw = ∑ w∈Q̂j 1 σiw ∑ k∈]∆ σiw(k).
By summing σiw(k) for all k ∈ ]∆ we obtain all the 2-long minimal paths between i and w with the exception of the one passing through j:∑
k∈]∆ b(k) ≥ ∑ w∈Q̂j 1 σiw (σiw − 1). (18)
On the other hand we also have b(j) = ∑
s,t∈V :s6=j,t 6=j
σst(j) σst ≥ ∑ z∈Qj σiz(j) σiz = ∑ z∈Qj 1 σiz . (19)
By combining equation 18 and equation 19 we finally get
1
|]∆|+ 1 ∑ k∈]∆ b(k) + b(j)  ≥ 1 |]∆|+ 1 ∑ w∈Q̂j 1 σiw (σiw − 1) + ∑ z∈Qj 1 σiz  = 1
|]∆|+ 1 |Q̂j |+ ∑ z∈Qj\Q̂j 1 σiz  = |Qj | |]∆|+ 1 ,
where in the last equality we have used that by definition σiz = 1 for all z ∈ Qj \ Q̂j . By Lemma 14 the last quantity is larger than δ−1.

heading: E PROOFS OF RESULTS IN SECTION 4
text: Theorem 6. Let S ⊂ V with vol(S) ≤ vol(G)/2. Then hS,α ≤ ( 1−α α ) davg(S) dmin(S)
hS , where davg(S) and dmin(S) are the average and minimum degree on S, respectively.
Proof. Given a signal f : V → R on the vertex set and U ⊂ V , analogously to Chung (2007), we introduce the notation f(U) := ∑ i∈U f(i).
Let us rewrite the new Cheeger constant hS,α as follows:
hS,α = 1 |S| ∑
i∈S,j∈S̄
(Rα)ij = 1
|S| χSRα(S̄)
with χS the characteristic function of the subset S, i.e. χS(i) = 1 iff i ∈ S. Since the graph G is connected, we can bound hS,α from above as
1
|S| χSRα(S̄) =
1 |S| ∑
i∈S,j∈S̄
(Rα)ij ≤ 1 |S| ∑
i∈S,j∈S̄
(Rα)ij di
dmin(S) =
1
|S| χSDRα(S̄)
1
dmin(S) .
It was proven in (Chung, 2007, Lemma 5) that
χSDRα(S̄) ≤ 1− α α |∂S|. (20)
By applying equation equation 20 to the bound for the Cheeger constant hS,α we finally see that
hS,α = 1
|S| χSRα(S̄) ≤
1
|S| χSDRα(S̄)
1 dmin(S) ≤ 1 |S| 1− α α |∂S| 1 dmin(S)
= 1 |S| 1− α α hSvol(S) 1 dmin(S) = 1− α α hS davg (S) dmin(S) .
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 k ∈ N, there exists Sk,α ⊂ S with vol(Sk,α) ≥ vol(S)(1− (2k)−1) such that∑
j∈S̄
(Rα)ij ≤ k 1− α α hS ,
for all i ∈ Sk,α.
Proof. Let k ∈ N. By modifying slightly the argument in (Chung, 2007, Lemma 5), we derive that
S′k,α := {i ∈ S : χiRα(S̄) ≥ k 1− α α hS}
satisfies 1− α
2α |∂S| ≥ vol(S′k,α)k 1− α α hS .
Therefore, we obtain
vol(S′k,α) ≤ 1
k vol(S) 2 .
We then conclude that the complement of S′k,α has volume greater or equal than vol(S)(1− (2k)−1), which completes the proof.
Remark 18. The previous proposition shows that after sparsifying the personalized page rank operator Rα as 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 are generally not suited to tackle the graph bottleneck.

heading: F EXPERIMENTS
text: Our experiments in this paper are semi-supervised node classification (semi-supervised in that the graph structure provides some unlabelled information) on 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 et al., 2021) are medium heterophilic datasets based on Wikipedia networks, along with Actor, the actor-only induced subgraph of the filmdirector-actor-writer 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 a development set and the test set. This is done once to ensure the test set is not used for any training or hyperparameter fitting before the final evaluation. For each of the 100 random splits the development set is divided randomly into a train set and a validation set, where we train models on the train set and evaluate 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 is the mean accuracy on the test set from models trained on the train sets with the chosen hyperparameters, along with a 95% confidence interval calculated by bootstrapping the test set accuracies with 1000 samples. For Cora, Citeseer and Pubmed the development set contains 1500 nodes with the rest kept for the test set, and for each random split the train set is chosen to contain 20 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 to have comparable results. For the remaining datasets we perform a 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.
The homophily indexH(G) proposed by Pei et al. (2019) is defined as
H(G) = 1 |V | ∑ v∈V Number of v’s neighbors who have the same label as v Number of v’s neighbors . (21)
F.1 DATASETS
For datasets with disconnected graphs, the statistics shown here are for the largest connected component.
Cornell Texas Wisconsin Chameleon Squirrel Actor Cora Citeseer Pubmed
H(G) 0.11 0.06 0.16 0.25 0.22 0.24 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 5 5 5 5 5 7 6 3 Directed? Yes Yes Yes Yes Yes Yes No No No
F.2 DEGREE DISTRIBUTIONS
F.3 HYPERPARAMETERS

heading: G HARDWARE SPECIFICATIONS
text: Our experiments were performed on a server with the following specifications:
Component Specification
Architecture x86_64 CPU 40x Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz GPU 4x GeForce RTX 3090 (24268MiB/GPU) RAM 126GB OS Ubuntu 20.04.2 LTS

Review summaries:
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.

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. 

 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.  Further, 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. 

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.  One 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.  In particular, the contributions are: - 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  - 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.  - 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  - 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