On Over-Squashing in Message Passing Neural Networks: The Impact of
  Width, Depth, and Topology
Message Passing Neural Networks (MPNNs) are instances of Graph Neural
Networks that leverage the graph to send messages over the edges. This
inductive bias leads to a phenomenon known as over-squashing, where a node
feature is insensitive to information contained at distant nodes. Despite
recent methods introduced to mitigate this issue, an understanding of the
causes for over-squashing and of possible solutions are lacking. In this
theoretical work, we prove that: (i) Neural network width can mitigate
over-squashing, but at the cost of making the whole network more sensitive;
(ii) Conversely, depth cannot help mitigate over-squashing: increasing the
number of layers leads to over-squashing being dominated by vanishing
gradients; (iii) The graph topology plays the greatest role, since
over-squashing occurs between nodes at high commute (access) time. Our analysis
provides a unified framework to study different recent methods introduced to
cope with over-squashing and serves as a justification for a class of methods
that fall under graph rewiring.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', Michael Bronstein
# On Over-Squashing in Message Passing Neural Networks:

###### Abstract

Message Passing Neural Networks (MPNNs) are instances of Graph Neural Networks that leverage the graph to send messages over the edges. This inductive bias leads to a phenomenon known as over-squashing, where a node feature is insensitive to information contained at distant nodes. Despite recent methods introduced to mitigate this issue, an understanding of the causes for over-squashing and of possible solutions are lacking. In this theoretical work, we prove that: (i) Neural network width can mitigate over-squashing, but at the cost of making the whole network more sensitive; (ii) Conversely, depth cannot help mitigate over-squashing: increasing the number of layers leads to over-squashing being dominated by vanishing gradients; (iii) The graph topology plays the greatest role, since over-squashing occurs between nodes at high commute time. Our analysis provides a unified framework to study different recent methods introduced to cope with over-squashing and serves as a justification for a class of methods that fall under 'graph rewiring'.

Machine Learning, Deep Learning, Neural Networks, Graph Networks, Graph Networks, Graph Networks

## 1 Introduction

Learning on graphs with Graph Neural Networks (GNNs) (Sperduti, 1993; Goller & Kuchler, 1996; Gori et al., 2005; Scarselli et al., 2008; Bruna et al., 2014; Defferrard et al., 2016) has become an increasingly flourishing area of machine learning. Typically, GNNs operate in the _message-passing paradigm_ by exchanging information between nearby nodes (Gilmer et al., 2017), giving rise to the class of Message-Passing Neural Networks (MPNNs). While message-passing has demonstrated to be a useful inductive bias, it has also been shown that the paradigm has some fundamental flaws, from expressivity (Xu et al., 2019; Morris et al., 2019), to over-smoothing (Nt & Maehara, 2019; Cai & Wang, 2020; Bodnar et al., 2022; Rusch et al., 2022; Di Giovanni et al., 2022; Zhao et al., 2022) and over-squashing. The first two limitations have been thoroughly investigated, however _less is known about over-squashing_.

Alon & Yahav (2021) described over-squashing as an issue emerging when MPNNs propagate messages across distant nodes, with the exponential expansion of the receptive field of a node leading to many messages being'squashed' into fixed-size vectors. Topping et al. (2022) formally justified this phenomenon via a sensitivity analysis on the Jacobian of node features and, partly, linked it to the existence of edges with high-negative curvature. However, some important **questions are left open** from the analysis in Topping et al. (2022): (i) What is the impact of _width_ in mitigating over-squashing? (ii) Can over-squashing be avoided by sufficiently _deep_ models? (iii) How does over-squashing relate to the graph-spectrum and the underlying _topology_ beyond curvature bounds that only apply to 2-hop propagation? The last point is particularly relevant due to recent works trying to combat over-squashing via methods that depend on the graph spectrum (Arnaiz-Rodriguez et al., 2022; Deac et al., 2022; Karhadkar et al., 2022). However, it is yet to be clarified if and why these works alleviate over-squashing.

In this work, we aim to address all the questions that are left open in Topping et al. (2022) to provide a better theoretical understanding on the causes of over-squashing as well as on what can and cannot fix it.

Contributions and outline.An MPNN is generally constituted by two main parts: a choice of architecture, and an underlying graph over which it operates. In this work, we investigate how these factors participate in the over-squashing phenomenon. We focus on the width and depth of the MPNN, as well as on the graph-topology.

* In Section 3, we prove that the _width_ can mitigate over-squashing (Theorem 3.2), albeit at the potential cost of generalization. We also verify this with experiments.
* In Section 4, we show that depth may not be able to alleviate over-squashing. We identify two regimes. In
the first one, the number of layers is comparable to the graph diameter, and we prove that over-squashing is likely to occur among distant nodes (Theorem 4.1). In fact, the distance at which over-squashing happens is strongly dependent on the graph topology - as we validate experimentally. In the second regime, we consider an arbitrary (large) number of layers. We prove that at this stage the MPNN is, generally, dominated by vanishing gradients (Theorem 4.2). This result is of independent interest, since it characterizes analytically conditions of vanishing gradients of the loss for a large class of MPNNs that also include residual connections.
* In Section 5 we show that the _topology_ of the graph has the greatest impact on over-squashing. In fact, we show that over-squashing happens among nodes with high commute time (Theorem 5.5) and we validate this empirically. This provides a unified framework to explain why all spatial and spectral _rewiring_ approaches (discussed in Section 2.3) do mitigate over-squashing.

## 2 Background and related work

### The message-passing paradigm

Let \(\mathsf{G}\) be a graph with nodes \(\mathsf{V}\) and edges \(\mathsf{E}\). The connectivity is encoded in the adjacency matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\), with \(n\) the number of nodes. We assume that \(\mathsf{G}\) is undirected, connected, and that there are features \(\{\mathbf{h}_{v}^{(0)}\}_{v\in\mathsf{V}}\subset\mathbb{R}^{p}\). Graph Neural Networks (GNNs) are functions of the form \(\mathsf{GNN}_{\theta}:(\mathsf{G},\{\mathbf{h}_{v}^{(0)}\})\mapsto y_{ \mathsf{G}}\), with parameters \(\theta\) estimated via training and whose output \(y_{\mathsf{G}}\) is either a node-level or graph-level prediction. The most studied class of GNNs, known as the Message Passing Neural Network (MPNN) (Gilmer et al., 2017), compute node representations by stacking \(m\) layers of the form:

\[\mathbf{h}_{v}^{(t)}=\mathsf{com}^{(t)}(\mathbf{h}_{v}^{(t-1)},\mathsf{agg}^{ (t)}(\{\mathbf{h}_{u}^{(t-1)}:(v,u)\in\mathsf{E}\})),\]

for \(t=1,\ldots,m\), where \(\mathsf{agg}^{(t)}\) is some _aggregation_ function invariant to node permutation, while \(\mathsf{com}^{(t)}\)_combines_ the node's current state with messages from its neighbours. In this work, we usually assume \(\mathsf{agg}\) to be of the form

\[\mathsf{agg}^{(t)}(\{\mathbf{h}_{u}^{(t-1)}:(v,u)\in\mathsf{E}\})=\sum_{u} \mathbf{A}_{vu}\mathbf{h}_{u}^{(t-1)}, \tag{1}\]

where \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is a **Graph Shift Operator (GSO)**, meaning that \(\mathbf{A}_{vu}\neq 0\) if and only if \((v,u)\in\mathsf{E}\). Typically, \(\mathbf{A}\) is a (normalized) adjacency matrix that we also refer to as message-passing matrix. While instances of MPNN differ based on the choices of \(\mathbf{A}\) and \(\mathsf{com}\), they all aggregate messages over the neighbours, such that in a layer, only nodes connected via an edge exchange messages. This presents two advantages: MPNNs (i) can capture graph-induced'short-range' dependencies well, and (ii) are efficient, since they can leverage the sparsity of the graph. Nonetheless, MPNNs have been shown to suffer from a few drawbacks, including _limited expressive power_ and _over-squashing_. The problem of expressive power stems from the equivalence of MPNNs to the Weisfeiler-Leman graph isomorphism test (Xu et al., 2019; Morris et al., 2019). This framework has been studied extensively (Jegelka, 2022). On the other hand, the phenomenon of over-squashing, which is the main focus of this work, is more elusive and less understood. We review what is currently known about it in the next subsection.

### The problem: introducing over-squashing

Since in an MPNN the information is aggregated over the neighbours, for a node \(v\) to be affected by features at distance \(r\), an MPNN needs at least \(r\) layers (Barcelo et al., 2019). It has been observed though that due to the expansion of the receptive field of a node, MPNNs may end up sending a number of messages growing exponentially with the distance \(r\), leading to a potential loss of information known as _over-squashing_(Alon and Yahav, 2021). Topping et al. (2022) showed that for an MPNN with message-passing matrix \(\mathbf{A}\) as in Eq. (1) and _scalar_ features, given nodes \(v,u\) at distance \(r\), we have \(|\partial h_{v}^{(r)}/\partial h_{u}^{(0)}|\leq c\cdot(\mathbf{A}^{r})_{vu}\), with \(c\) a constant depending on the Lipschitz regularity of the model. If \((\mathbf{A}^{r})_{vu}\) decays exponentially with \(r\), then the feature of \(v\) is insensitive to the information contained at \(u\). Moreover, Topping et al. (2022) showed that over-squashing is related to the existence of edges with _high negative curvature_. Such characterization though only applies to propagation of information up to 2 hops.

### Related work

Multiple solutions to mitigate over-squashing have already been proposed. We classify them below; in Section 5, we provide a unified framework that encompasses all such solu

Figure 1: Effect of different rewirings \(\mathcal{R}\) on the graph connectivity. The colouring denotes Commute Time – defined in Section 5 – w.r.t. to the star node. From left to right, the graphs shown are: the base, spatially rewired and spectrally rewired. The added edges significantly reduce the Commute Time and hence mitigate over-squashing in light of Theorem 5.5.
tions. We first introduce the following notion:

**Definition 2.1**.: Consider an \(\mathsf{MPNN}\), a graph \(\mathsf{G}\) with adjacency \(\mathbf{A}\), and a map \(\mathcal{R}:\mathbb{R}^{n\times n}\to\mathbb{R}^{n\times n}\). We say that \(\mathsf{G}\) has been **rewired** by \(\mathcal{R}\), if the messages are exchanged on \(\mathcal{R}(\mathsf{G})\) instead of \(\mathsf{G}\), with \(\mathcal{R}(\mathsf{G})\) the graph with adjacency \(\mathcal{R}(\mathbf{A})\).

Recent approaches to combat over-squashing share a common idea: replace the graph \(\mathsf{G}\) with a rewired graph \(\mathcal{R}(\mathsf{G})\) enjoying better connectivity Figure 1. We then distinguish these works based on the choice of the rewiring \(\mathcal{R}\).

Spatial methods.Since \(\mathsf{MPNN}\)s fail to propagate information to distant nodes, a solution consists in replacing \(\mathsf{G}\) with \(\mathcal{R}(\mathsf{G})\) such that \(\operatorname{diam}(\mathcal{R}(\mathsf{G}))\ll\operatorname{diam}(\mathsf{G})\). Typically, this is achieved by either explicitly adding edges (possibly attributed) between distant nodes (Bruel-Gabrielsson et al., 2022; Abboud et al., 2022) or by allowing distant nodes to communicate through higher-order structures (e.g., cellular or simplicial complexes, (Bodnar et al., 2021; \(\mathsf{b}\)), which requires additional domain knowledge and incurs a computational overhead). _Graph-Transformers_ can be seen as an extreme example of rewiring, where \(\mathcal{R}(\mathsf{G})\) is a _complete graph_ with edges weighted via attention (Kreuzer et al., 2021; Mialon et al., 2021; Ying et al., 2021; Rampasek et al., 2022). While these methods do alleviate over-squashing, since they _bring all pair of nodes closer_, they come at the expense of making the graph \(\mathcal{R}(\mathsf{G})\) much denser. In turn, this has an impact on computational complexity and introduces the risk of mixing local and non-local interactions.

We include in this group Topping et al. (2022) and Banerjee et al. (2022), where the rewiring is _surgical_ - but requires specific pre-processing - in the sense that \(\mathsf{G}\) is replaced by \(\mathcal{R}(\mathsf{G})\) where edges have only been added to'mitigate' bottlenecks as identified, for example, by negative curvature (Ollivier, 2007; Di Giovanni et al., 2022).

We finally mention that spatial rewiring, intended as accessing information beyond the 1-hop when updating node features, is common to many existing frameworks (Abu-El-Haija et al., 2019; Klicpera et al., 2019; Chen et al., 2020; Ma et al., 2020; Wang et al., 2020; Nikolentzos et al., 2020). However, this is usually done via powers of the adjacency matrix, which is the main culprit for over-squashing (Topping et al., 2022). Accordingly, although the diffusion operators \(\mathbf{A}^{k}\) allow to aggregate information over non-local hops, they are not suited to mitigate over-squashing.

Spectral methods.The connectedness of a graph \(\mathsf{G}\) can be measured via a quantity known as the _Cheeger constant_, defined as follows (Chung and Graham, 1997):

**Definition 2.2**.: For a graph \(\mathsf{G}\), the Cheeger constant is

\[\mathsf{h}_{\mathsf{Cheeg}}=\min_{\mathsf{U}\in\mathsf{V}}\frac{|\{(u,v)\in \mathsf{E}:u\in\mathsf{U},v\in\mathsf{V}\setminus\mathsf{U}\}|}{\min(\mathrm{ vol}(\mathsf{U}),\mathrm{vol}(\mathsf{V}\setminus\mathsf{U}))},\]

where \(\mathrm{vol}(\mathsf{U})=\sum_{u\in\mathsf{U}}d_{u}\), with \(d_{u}\) the degree of node \(u\).

The Cheeger constant \(\mathsf{h}_{\mathsf{Cheeg}}\) represents the energy required to disconnect \(\mathsf{G}\) into two communities. A small \(\mathsf{h}_{\mathsf{Cheeg}}\) means that \(\mathsf{G}\) generally has two communities separated by only few edges - over-squashing is then expected to occur here _if_ information needs to travel from one community to the other. While \(\mathsf{h}_{\mathsf{Cheeg}}\) is generally intractable to compute, thanks to the Cheeger inequality we know that \(\mathsf{h}_{\mathsf{Cheeg}}\sim\lambda_{1}\), where \(\lambda_{1}\) is the positive, smallest eigenvalue of the graph Laplacian. Accordingly, a few new approaches have suggested to choose a rewiring that depends on the spectrum of \(\mathsf{G}\) and yields a new graph satisfying \(\mathsf{h}_{\mathsf{Cheeg}}(\mathcal{R}(\mathsf{G}))>\mathsf{h}_{\mathsf{ Cheeg}}(\mathsf{G})\). This strategy includes Arnaiz-Rodriguez et al. (2022); Deac et al. (2022); Karhadkar et al. (2022). It is claimed that sending messages over such a graph \(\mathcal{R}(\mathsf{G})\) alleviates over-squashing, however this has not been shown analytically yet.

The goal of this work.The analysis of Topping et al. (2022), which represents our current theoretical understanding of the over-squashing problem, leaves some important open questions which we address in this work: (i) We study the role of the **width** in mitigating over-squashing; (ii) We analyse what happens when the **depth** exceeds the distance among two nodes of interest; (iii) We prove how over-squashing is related to the graph structure (beyond local curvature-bounds) and its **spectrum**. As a consequence of (iii), we _provide a unified framework to explain how spatial and spectral approaches alleviate over-squashing_. We reference here the concurrent work of Black et al. (2023), who, similarly to us, drew a strong connection between over-squashing and Effective Resistance (see Section 5).

Notations and conventions to improve readability.In the following, to prioritize readability we often leave sharper bounds with more optimal and explicit terms to the Appendix. From now on, \(p\) always denotes the width (hidden dimension) while \(m\) is the depth (i.e. number of layers). The feature of node \(v\) at layer \(t\) is written as \(\mathbf{h}_{v}^{(t)}\). Finally, we write \([\ell]=\{1,\ldots,\ell\}\) for any integer \(\ell\). All proofs can be found in the Appendix.

## 3 The impact of width

In this Section we assess whether the width of the underlying \(\mathsf{MPNN}\) can mitigate over-squashing and the extent to which this is possible. In order to do that, we extend the sensitivity analysis in Topping et al. (2022) to higher-dimensional node features. We consider a class of \(\mathsf{MPNN}\)s parameterised by neural networks, of the form:

\[\mathbf{h}_{v}^{(t+1)}=\sigma\left(c_{\mathsf{r}}\mathbf{W}_{\mathsf{r}}^{(t)} \mathbf{h}_{v}^{(t)}+c_{\mathsf{a}}\mathbf{W}_{\mathsf{a}}^{(t)}\sum_{u} \boldsymbol{\mathsf{A}}_{vu}\mathbf{h}_{u}^{(t)}\right), \tag{2}\]
where \(\sigma\) is a pointwise-nonlinearity, \(\mathbf{W}_{r}^{(t)},\mathbf{W}_{a}^{(t)}\in\mathbb{R}^{p\times p}\) are learnable weight matrices and \(\mathbf{A}\) is a graph shift operator. Note that Eq. (2) includes common \(\mathsf{MPNN}\)s such as \(\mathsf{GCN}\)(Kipf and Welling, 2017), \(\mathsf{SAGE}\)(Hamilton et al., 2017), and \(\mathsf{GIN}\)(Xu et al., 2019), where \(\mathbf{A}\) is one of \(\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), \(\mathbf{D}^{-1}\mathbf{A}\) and \(\mathbf{A}\), respectively, with \(\mathbf{D}\) the diagonal degree matrix. In Appendix B, we extend the analysis to a more general class of \(\mathsf{MPNN}\)s (see Theorem B.1), which includes stacking multiple nonlinearities. We also emphasize that the positive scalars \(c_{r},c_{a}\) represent the weighted contribution of the residual term and of the aggregation term, respectively. To ease the notations, we introduce a family of message-passing matrices that depend on \(c_{r},c_{a}\).

**Definition 3.1**.: For a graph shift operator \(\mathbf{A}\) and constants \(c_{r},c_{a}>0\), we define \(\mathbf{S}_{r,a}:=c_{r}\mathbf{I}+c_{a}\mathbf{A}\in\mathbb{R}^{n\times n}\) to be the message-passing matrix adopted by the \(\mathsf{MPNN}\).

As in Xu et al. (2018) and Topping et al. (2022), we study the propagation of information in the \(\mathsf{MPNN}\) via the Jacobian of node features after \(m\) layers.

**Theorem 3.2** (**Sensitivity bounds)**.: _Consider an \(\mathsf{MPNN}\) as in Eq. (2) for \(m\) layers, with \(c_{\sigma}\) the Lipschitz constant of the nonlinearity \(\sigma\) and \(w\) the maximal entry-value over all weight matrices. For \(v,u\in\mathsf{V}\) and width \(p\), we have_

\[\left|\left|\frac{\partial\mathbf{h}_{v}^{(m)}}{\partial\mathbf{h}_{u}^{(0)}} \right|\right|_{L_{1}}\leq\underbrace{(c_{\sigma}w)}_{\mathrm{model}}{}^{m} \underbrace{(\mathbf{S}_{r,a}^{m})_{vu}}_{\mathrm{topology}}, \tag{3}\]

_with \(\mathbf{S}_{r,a}^{m}\) the \(m^{th}\)-power of \(\mathbf{S}_{r,a}\) introduced in Definition 3.1._

Over-squashing occurs if the right hand side of Eq. (3) is too small - this will be related to the distance among \(v\) and \(u\) in Section 4.1. A small derivative of \(\mathbf{h}_{v}^{(m)}\) with respect to \(\mathbf{h}_{u}^{(0)}\) means that after \(m\) layers, _the feature at \(v\) is mostly insensitive to the information initially contained at \(u\)_, and hence that messages have not been propagated effectively. Theorem 3.2 clarifies how the model can impact over-squashing through (i) its Lipschitz regularity \(c_{\sigma},w\) and (ii) its width \(p\). In fact, given a graph \(\mathsf{G}\) such that \((\mathbf{S}_{r,a}^{m})_{vu}\) decays exponentially with \(m\), the \(\mathsf{MPNN}\) can compensate by increasing the width \(p\) and the magnitude of \(w\) and \(c_{\sigma}\). This confirms analytically the discussion in Alon and Yahav (2021): **a larger hidden dimension \(p\) does mitigate over-squashing**. However, this is not an optimal solution since increasing the contribution of the model (i.e. the term \(c_{\sigma}wp\)) may lead to over-fitting and poorer generalization (Bartlett et al., 2017). Taking larger values of \(c_{\sigma},w,p\) affects the model _globally_ and does not target the sensitivity of specific node pairs induced by the topology via \(\mathbf{S}_{r,a}\).

Validating the theoretical results.We validate empirically the message from Theorem 3.2: if the task presents long-range dependencies, increasing the hidden dimension mitigates over-squashing and therefore has a positive impact on the performance. We consider the following 'graph transfer' task, building upon Bodnar et al. (2021): given a graph, consider source and target nodes, placed at distance \(r\) from each other. We assign a one-hot encoded label to the target and a constant unitary feature vector to all other nodes. The goal is to assign to the source node the feature vector of the target. Partly due to over-squashing, performance is expected to degrade as \(r\) increases.

To validate that this holds irrespective of the graph structure, we evaluate across three graph topologies, called \(\mathsf{CrossReg}\), \(\mathsf{Ring}\) and \(\mathsf{CliquePath}\) - see Appendix E for further details. While the topology is also expected to affect the performance (as confirmed in Section 4), given a fixed topology, we expect the model to benefit from an increase of hidden dimension.

To verify this behaviour, we evaluate \(\mathsf{GCN}\)(Kipf and Welling, 2017) on the three graph transfer tasks increasing the hidden dimension, but keeping the number of layers equal to the distance between source and target, as shown in Figure 2. The results verify the intuition from the theorem that a higher hidden dimension helps the \(\mathsf{GCN}\) model solve the task to larger distances across the three graph-topologies.

**Message of the Section:**_The Lipschitz regularity, weights, and width of the underlying \(\mathsf{MPNN}\) can help mitigate the effect of over-squashing. However, this is a remedy that comes at the expense of generalization and does not address the real culprit behind over-squashing: the graph-topology_.

Figure 2: Performance of \(\mathsf{GCN}\) on the \(\mathsf{CrossedRing}\), \(\mathsf{Ring}\), and \(\mathsf{CliquePath}\) tasks obtained by varying the hidden dimension. Increasing the hidden dimension helps mitigate the over-squashing effect, in accordance with Theorem 3.2.
## 4 The impact of depth

Consider a graph \(\mathsf{G}\) and a task with 'long-range' dependencies, meaning that there exists (at least) a node \(v\) whose embedding has to account for information contained at some node \(u\) at distance \(r\gg 1\). One natural attempt at resolving over-squashing amounts to increasing the number of layers \(m\) to compensate for the distance. We prove that the depth of the \(\mathsf{MPNN}\) will, generally, not help with over-squashing. We show that: (i) When the depth \(m\) is comparable to the distance, over-squashing is bound to occur among distant nodes - in fact, the distance at which over-squashing happens, is strongly dependent on the underlying topology; (ii) If we take a large number of layers to cover the long-range interactions, we rigorously prove under which _exact_ conditions, \(\mathsf{MPNNs}\) incur the vanishing gradients problem.

### The shallow-diameter regime: over-squashing occurs among distant nodes

Consider the scenario above, with two nodes \(v,u\), whose interaction is important for the task, at distance \(r\). We first focus on the regime \(m\sim r\). We refer to this as the _shallow-diameter_ regime, since the number of layers \(m\) is comparable to the diameter of the graph.

From now on, we set \(\textbf{A}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), where we recall that **A** is the adjacency matrix and **D** is the degree matrix. This is not restrictive, but allows us to derive more explicit bounds and, later, bring into the equation the spectrum of the graph. We note that results can be extended easily to \(\mathbf{D}^{-1}\mathbf{A}\), given that this matrix is similar to **A**, and, in expectation, to **A** by normalizing the Jacobian as in Xu et al. (2019) and Section A in the Appendix of Topping et al. (2022).

**Theorem 4.1** (**Over-squashing among distant nodes)**.: _Given an \(\mathsf{MPNN}\) as in Eq. (2), with \(c_{\mathsf{a}}\leq 1\), let \(v,u\in\mathsf{V}\) be at distance \(r\). Let \(c_{\sigma}\) be the Lipschitz constant of \(\sigma\), \(w\) the maximal entry-value over all weight matrices, \(d_{\min}\) the minimal degree of \(\mathsf{G}\), and \(\gamma_{\ell}(v,u)\) the number of walks from \(v\) to \(u\) of maximal length \(\ell\). For any \(0\leq k<r\), there exists \(C_{k}>0\)_**independent** _of \(r\) and of the graph, such that_

\[\left|\left|\frac{\partial\mathbf{h}_{v}^{(r+k)}}{\partial\mathbf{h}_{u}^{(0 )}}\right|\right|_{L_{1}}\leq C_{k}\gamma_{r+k}(v,u)\left(\frac{2c_{\sigma}wp} {d_{\min}}\right)^{r}. \tag{4}\]

To understand the bound above, fix \(k<r\) and assume that nodes \(v,u\) are 'badly' connected, meaning that the number of walks \(\gamma_{r+k}(v,u)\) of length at most \(r+k\), is small. If \(2\,c_{\sigma}wp<d_{\min}\), then the bound on the Jacobian in Eq. (4) _decays exponentially with the distance \(r\)_. Note that the bound above considers \(d_{\min}\) and \(\gamma_{r+k}\) as a worst case scenario. If one has a better understanding of the topology of the graph, sharper bounds can be derived by estimating \((\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu}\). Theorem 4.1 implies that, when the depth \(m\) is comparable to the diameter of \(\mathsf{G}\), _over-squashing becomes an issue if the task depends on the interaction of nodes \(v,u\) at 'large' distance \(r\)_. In fact, Theorem 4.1 shows that the distance at which the Jacobian sensitivity falls below a given threshold, depends on both the model, via \(c_{\sigma},w,p\), and on the graph, through \(d_{\min}\) and \(\gamma_{r+k}(v,u)\). We finally observe that Theorem 4.1 generalizes the analysis in Topping et al. (2022) in multiple ways: (i) it holds for any width \(p>1\); (ii) it includes cases where \(m>r\); (iii) it provides explicit estimates in terms of number of walks and degree information.

**Remark**.: What if \(2c_{\sigma}wp>d_{\min}\)? Taking larger weights and hidden dimension increases the sensitivity of node features. However, this occurs _everywhere_ in the graph the same. Accordingly, nodes at shorter distances will, on average, still have sensitivity exponentially larger than nodes at large distance. This is validated in our synthetic experiments below, where we do not have constraints on the weights.

Validating the theoretical results.From Theorem 4.1, we derive a strong indication of the difficulty of a task by calculating an upper bound on the Jacobian. We consider the same graph transfer tasks introduced above, namely \(\mathsf{CrossedRing}\), \(\mathsf{Ring}\), and \(\mathsf{CliquePath}\). For these special cases, we can derive a refined version of the r.h.s in Eq. (4): in particular, \(k=0\) (i.e. the depth coincides with the distance among source and target) and the term \(\gamma_{r}(v,u)(d_{\min})^{-r}\) can be replaced by the exact quantity \((\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu}\). Fixing a distance \(r\) between source \(u\) and target \(v\) then, if we consider for example the \(\mathsf{GCN}\)-case, we have \(\mathbf{S}_{\mathsf{r},\mathsf{a}}=\textbf{A}\) so that the term \((\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu}\) can be computed explicitly:

\[(\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu} =(3/2)^{-(r-1)} \text{for $\mathsf{CrossedRing}$}\] \[(\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu} =2^{-(r-1)} \text{for $\mathsf{Ring}$}\] \[(\mathbf{S}_{\mathsf{r},\mathsf{a}}^{r})_{vu} =2^{-(r-2)}/(r\sqrt{r-2}) \text{for $\mathsf{CliquePath}$}.\]

Given an \(\mathsf{MPNN}\), terms like \(c_{\sigma},w,p\) entering Theorem 4.1 are independent of the graph-topology and hence can be assumed to behave, roughly, the same across different graphs. As a consequence, we can expect over-squashing to be more problematic for \(\mathsf{CliquePath}\), followed by \(\mathsf{Ring}\), and less prevalent comparatively in \(\mathsf{CrossedRing}\). Figure 3 shows the behaviour of \(\mathsf{GIN}\)(Xu et al., 2019), \(\mathsf{SAGE}\)(Hamilton et al., 2017), \(\mathsf{GCN}\)(Kipf & Welling, 2017), and GAT (Velickovic et al., 2018) on the aformentioned tasks. We verify the conjectured difficulty. \(\mathsf{CliquePath}\) is the consistently hardest task, followed by \(\mathsf{Ring}\), and \(\mathsf{CrossedRing}\). Furthermore, the decay of the performance to random guessing for the _same_ architecture across different graph topologies highlights that this drop cannot be simply labelled as 'vanishing gradients' since for certain topologies the same model can, in fact, achieve perfect accuracy. This validates that the underlying topology has a strong impact on the distance at which over-squashing is expected to happen. Moreover, we confirm
that in the regime where the depth \(m\) is comparable to the distance \(r\), over-squashing will occur if \(r\) is large enough.

### The deep regime: vanishing gradients dominate

We now focus on the regime where the number of layers \(m\gg r\) is large. We show that in this case, vanishing gradients can occur and make the entire model insensitive. Given a weight \(\theta^{(k)}\) entering a layer \(k\), one can write the gradient of the loss after \(m\) layers as (Pascanu et al., 2013)

\[\frac{\partial\mathcal{L}}{\partial\theta^{(k)}}=\sum_{v,u\in V}\left(\frac{ \partial\mathcal{L}}{\partial\mathbf{h}_{v}^{(m)}}\frac{\partial\mathbf{h}_{ u}^{(k)}}{\partial\theta^{(k)}}\right)\underbrace{\frac{\partial\mathbf{h}_{v}^{(m)} }{\partial\mathbf{h}_{u}^{(k)}}}_{\text{sensitivity}} \tag{5}\]

We provide **exact conditions** for MPNNs to incur the vanishing gradient problem, intended as the gradients of the loss decaying exponentially with the number of layers \(m\).

**Theorem 4.2** (Vanishing gradients).: _Consider an_ MPNN _as in Eq. (2) for \(m\) layers with a quadratic loss \(\mathcal{L}\). Assume that (i) \(\sigma\) has Lipschitz constant \(c_{\sigma}\) and \(\sigma(0)=0\), and (ii) weight matrices have spectral norm bounded by \(\mu>0\). Given any weight \(\theta\) entering a layer \(k\), there exists a constant \(C>0\) independent of \(m\), such that_

\[\left|\frac{\partial\mathcal{L}}{\partial\theta}\right|\leq C\left(c_{\sigma} \mu(c_{\tau}+c_{\mathsf{a}})\right)^{m-k}\left(1+\left(c_{\sigma}\mu(c_{ \tau}+c_{\mathsf{a}})\right)^{m}\right). \tag{6}\]

_In particular, if \(c_{\sigma}\mu(c_{\tau}+c_{\mathsf{a}})<1\), then the gradients of the loss decay to zero exponentially fast with \(m\)._

The problem of vanishing gradients for graph convolutional networks have been studied from an empirical perspective (Li et al., 2019, 2021). Theorem 4.2 provides sufficient conditions for the vanishing of gradients to occur in a large class of MPNNs that also include (a form of) residual connections through the contribution of \(c_{\tau}\) in Eq. (2). This extends a behaviour studied for Recurrent Neural Networks (Bengio et al., 1994; Hochreiter and Schmidhuber, 1997; Pascanu et al., 2013; Rusch and Mishra, 2021; ) to the MPNN class. We also mention that some discussion on vanishing gradients for MPNNs can be found in Ruiz et al. (2020) and Rusch et al. (2022). A few final comments are in order. (i) The bound in Theorem 4.2 seems to 'hide' the contribution of the graph. This is, in fact, because the spectral norm of the graph operator \(\mathbf{S}_{r,\mathsf{a}}\) is \(c_{r}+c_{\mathsf{a}}\) - we reserve the investigation of more general graph shift operators (Dasoulas et al., 2021) to future work. (ii) Theorem 4.1 shows that if the distance \(r\) is large enough and we take the number of layers \(m\) s.t. \(m\sim r\), over-squashing arises among nodes at distance \(r\). Taking the number of layers large enough though, may incur the vanishing gradient problem Theorem 4.2. In principle, there might be an intermediate regime where \(m\) is larger than \(r\), but _not_ too large, in which the depth could help with over-squashing before it leads to vanishing gradients. Given a graph \(\mathsf{G}\), and bounds on the Lipschitz regularity and width, we conjecture though that there exists \(\tilde{r}\), depending on the topology of \(\mathsf{G}\), such that if the task has interactions at distance \(r>\tilde{r}\), no number of layers can allow the MPNN class to solve it. This is left for future work.

**Message of the Section:**_Increasing the depth \(m\) will, in general, not fix over-squashing. As we increase \(m\),_ MPNNs _transition from over-squashing (Theorem 4.1) to vanishing gradients (Theorem 4.2)._

## 5 The impact of topology

We finally discuss the impact of the graph topology, and in particular of the graph spectrum, on over-squashing. This allows us to draw a unified framework that shows why existing approaches manage to alleviate over-squashing by either spatial or spectral rewiring (Section 2.3).

### On over-squashing and access time

Throughout the section we relate over-squashing to well-known properties of random walks on graphs. To this aim, we first review basic concepts about random walks.

Access and commute time.A Random Walk (RW) on \(\mathsf{G}\) is a Markov chain which, at each step, moves from a node

Figure 3: Performance of GIN, SAGE, GCN, and GAT on the CliquePath, Ring, and CrossedRing tasks. In the case where depth and distance are comparable, over-squashing highly depends on the topology of the graph as we increase the distance.
\(v\) to one of its neighbours with probability \(1/d_{v}\). Several properties about RWs have been studied. We are particularly interested in the notion of _access time_\(\mathsf{t}(v,u)\) and of _commute time_\(\tau(v,u)\) (see Figure 1). The access time \(\mathsf{t}(v,u)\) (also known as _hitting time_) is the expected number of steps before node \(u\) is visited for a RW starting from node \(v\). The commute time instead, represents the expected number of steps in a RW starting at \(v\) to reach node \(u\) and _come back_. A high access (commute) time means that nodes \(v,u\) generally struggle to visit each other in a RW - this can happen if nodes are far-away, but it is in fact more general and strongly dependent on the topology.

Some connections between over-squashing and the topology have already been derived (Theorem 4.1), but up to this point 'topology' has entered the picture through 'distances' only. In this section, we further link over-squashing to other quantities related to the topology of the graph, such as access time, commute time and the Cheeger constant. We ultimately provide a unified framework to understand how existing approaches manage to mitigate over-squashing via graph-rewiring.

Integrating information across different layers.We consider a family of \(\mathsf{MPNN}\)s of the form

\[\mathbf{h}_{v}^{(t)}=\mathsf{ReLU}\left(\mathbf{W}^{(t)}\left(c_{\mathsf{r}} \mathbf{h}_{v}^{(t-1)}+c_{\mathsf{a}}(\boldsymbol{\mathsf{A}}\mathbf{h}^{(t- 1)})_{v}\right)\right). \tag{7}\]

Similarly to Kawaguchi (2016); Xu et al. (2018), we require the following:

**Assumption 5.1**.: All paths in the computation graph of the model are activated with the same probability of success \(\rho\).

Take two nodes \(v\neq u\) at distance \(r\gg 1\) and imagine we are interested in sending information _from_\(u\)\(to\)\(v\). Given a layer \(k<m\) of the \(\mathsf{MPNN}\), by Theorem 4.1 we expect that \(\mathbf{h}_{v}^{(m)}\) is much more sensitive to the information contained _at the same_ node \(v\) at an earlier layer \(k\), i.e. \(\mathbf{h}_{v}^{(k)}\), rather than to the information contained at a distant node \(u\), i.e. \(\mathbf{h}_{u}^{(k)}\). Accordingly, we introduce the following quantity:

\[\mathbf{J}_{k}^{(m)}(v,u):=\frac{1}{d_{v}}\frac{\partial\mathbf{h}_{v}^{(m)}} {\partial\mathbf{h}_{v}^{(k)}}-\frac{1}{\sqrt{d_{v}d_{u}}}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial\mathbf{h}_{u}^{(k)}}.\]

We note that the normalization by degree stems from our choice \(\boldsymbol{\mathsf{A}}=\mathbf{D}^{-1/2}\boldsymbol{\mathsf{A}}\mathbf{D}^{ -1/2}\). We provide an intuition for this term. Say that node \(v\) at layer \(m\) of the \(\mathsf{MPNN}\) is mostly insensitive to the information sent from \(u\) at layer \(k\). Then, on average, we expect \(||\partial\mathbf{h}_{v}^{(m)}/\partial\mathbf{h}_{u}^{(k)}||\ll||\partial \mathbf{h}_{v}^{(m)}/\partial\mathbf{h}_{v}^{(k)}||\). In the opposite case instead, we expect, on average, that \(||\partial\mathbf{h}_{v}^{(m)}/\partial\mathbf{h}_{u}^{(k)}||\sim||\partial \mathbf{h}_{v}^{(m)}/\partial\mathbf{h}_{v}^{(k)}||\). Therefore \(||\mathbf{J}_{k}^{(m)}(v,u)||\) will be _larger_ when \(v\) is (roughly) independent of the information contained at \(u\) at layer \(k\). We extend the same argument by accounting for messages sent at each layer \(k\leq m\).

**Definition 5.2**.: The Jacobian obstruction of node \(v\) with respect to node \(u\) after \(m\) layers is \(\mathsf{O}^{(m)}(v,u)=\sum_{k=0}^{m}||\mathbf{J}_{k}^{(m)}(v,u)||\).

As motivated above, a larger \(\mathsf{O}^{(m)}(v,u)\) means that, after \(m\) layers, the representation of node \(v\) is more likely to be insensitive to information contained at \(u\) and conversely, a small \(\mathsf{O}^{(m)}(v,u)\) means that nodes \(v\) is, on average, able to receive information from \(u\). Differently from the Jacobian bounds of the earlier sections, here we consider the contribution coming from all layers \(k\leq m\) (note the sum over layers \(k\) in Definition 5.2).

**Theorem 5.3** (**Over-squashing and access-time)**.: _Consider an \(\mathsf{MPNN}\) as in Eq. (7) and let Assumption 5.1 hold. If \(\nu\) is the smallest singular value across all weight matrices and \(c_{\mathsf{r}},c_{\mathsf{a}}\) are such that \(\nu(c_{\mathsf{r}}+c_{\mathsf{a}})=1\), then, in expectation, we have_

\[\mathsf{O}^{(m)}(v,u)\geq\frac{\rho}{\nu c_{\mathsf{a}}}\frac{\mathsf{t}(u,v)} {2|\mathsf{E}|}+o(m),\]

_with \(o(m)\to 0\) exponentially fast with \(m\)._

We note that an exact expansion of the term \(o(m)\) is reported in the Appendix. We also observe that more general bounds are possible if \(\nu(c_{\mathsf{r}}+c_{\mathsf{a}})<1\) - however, they will progressively become less informative in the limit \(\nu(c_{\mathsf{r}}+c_{\mathsf{a}})\to 0\). Theorem 5.3 shows that the obstruction is a function of the access time \(\mathsf{t}(u,v)\); **high access time, on average, translates into high obstruction for node \(v\) to receive information from node \(u\) inside the \(\mathsf{MPNN}\)**. This resonates with the intuition that access time is a measure of how easily a 'diffusion' process starting at \(u\) reaches \(v\). We emphasize that the obstruction provided by the access time cannot be fixed by increasing the number of layers and in fact this is independent of the number of layers, further corroborating the analysis in Section 4. Next, we relate over-squashing to commute time, and hence, to effective resistance.

### On over-squashing and commute time

We now restrict our attention to a slightly more special form of over-squashing, where we are interested in nodes \(v,u\) exchanging information both ways - differently from before where we looked at node \(v\) receiving information from node \(u\). Following the same intuition described previously, we introduce the symmetric quantity:

\[\tilde{\mathbf{J}}_{k}^{(m)}(v,u) :=\left(\frac{1}{d_{v}}\frac{\partial\mathbf{h}_{v}^{(m)}}{ \partial\mathbf{h}_{v}^{(k)}}-\frac{1}{\sqrt{d_{v}d_{u}}}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial\mathbf{h}_{u}^{(k)}}\right)\] \[+\left(\frac{1}{d_{u}}\frac{\partial\mathbf{h}_{u}^{(m)}}{ \partial\mathbf{h}_{u}^{(k)}}-\frac{1}{\sqrt{d_{v}d_{u}}}\frac{\partial \mathbf{h}_{u}^{(m)}}{\partial\mathbf{h}_{v}^{(k)}}\right).\]

Once again, we expect that \(||\tilde{\mathbf{J}}_{k}^{(m)}(v,u)||\) is larger if nodes \(v,u\) are failing to communicate in the \(\mathsf{MPNN}\), and con
versely to be smaller whenever the communication is sufficiently robust. Similarly, we integrate the information collected at each layer \(k\leq m\).

**Definition 5.4**.: The symmetric Jacobian obstruction of nodes \(v,u\) after \(m\) layers is \(\tilde{\mathsf{O}}^{(m)}(v,u)=\sum_{k=0}^{m}\lvert\lvert\tilde{\mathbf{J}}_{k}^{ (m)}(v,u)\rvert\rvert\).

The intuition of comparing the sensitivity of a node \(v\) with a different node \(u\) and to itself, and then swapping the roles of \(v\) and \(u\), resembles the concept of commute time \(\tau(v,u)\). In fact, this is not a coincidence:

**Theorem 5.5** (**Over-squashing and commute-time**).: _Consider an \(\mathsf{MPNN}\) as in Eq. (7) with \(\mu\) the maximal spectral norm of the weight matrices and \(\nu\) the minimal singular value. Let Assumption 5.1 hold. If \(\mu(c_{\mathsf{r}}+c_{\mathsf{a}})\leq 1\), then there exists \(\epsilon_{\mathsf{G}}\), independent of nodes \(v,u\), such that in expectation, we have_

\[\epsilon_{\mathsf{G}}(1-o(m))\frac{\rho}{\nu c_{\mathsf{a}}}\frac{\tau(v,u)}{ 2\lvert\mathsf{E}\rvert}\leq\tilde{\mathsf{O}}^{(m)}(v,u)\leq\frac{\rho}{\mu c _{\mathsf{a}}}\frac{\tau(v,u)}{2\lvert\mathsf{E}\rvert},\]

_with \(o(m)\to 0\) exponentially fast with \(m\) increasing._

We note that an explicit expansion of the \(o(m)\)-term is reported in the proof of the Theorem in the Appendix. By the previous discussion, a **smaller**\(\tilde{\mathsf{O}}^{(m)}(v,u)\) means \(v\) is more sensitive to \(u\) in the \(\mathsf{MPNN}\) (and viceversa when \(\tilde{\mathsf{O}}^{(m)}(v,u)\) is large). Therefore, Theorem 5.5 implies that nodes at small commute time will exchange information better in an \(\mathsf{MPNN}\) and conversely for those at high commute time. This has some **important consequences**:

1. When the task only depends on local interactions, the property of \(\mathsf{MPNN}\) of reducing the sensitivity to messages from nodes with high commute time _can_ be beneficial since it decreases harmful redundancy.
2. Over-squashing is an issue when the task depends on the interaction of nodes with high commute time.
3. The commute time represents an obstruction to the sensitivity of an \(\mathsf{MPNN}\) which is _independent of the number of layers_, since the bounds in Theorem 5.5 are independent of \(m\) (up to errors decaying exponentially fast with \(m\)).

We note that the very same comments hold in the case of access time as well if, for example, the task depends on node \(v\) receiving information from node \(u\) but not on \(u\) receiving information from \(v\).

### A unified framework

Why spectral-rewiring works.First, we justify why the spectral approaches discussed in Section 2.3 mitigate over-squashing. This comes as a consequence of Lovasz (1993) and Theorem 5.5:

**Corollary 5.6**.: _Under the assumptions of Theorem 5.5, for any \(v,u\in\mathsf{V}\), we have_

\[\tilde{\mathsf{O}}^{(m)}(v,u)\leq\frac{4}{\rho\mu c_{\mathsf{a}}}\frac{1}{ \hbar_{\mathsf{Cheng}}^{2}}.\]

Corollary 5.6 essentially tells us that the obstruction among _all_ pairs of nodes decreases (so better information flow) if the \(\mathsf{MPNN}\) operates on a graph \(\mathsf{G}\) with larger Cheeger constant. This rigorously justifies why recent works like Arnaiz-Rodriguez et al. (2022); Deac et al. (2022); Karhadkar et al. (2022) manage to alleviate over-squashing by propagating information on a rewired graph \(\mathcal{R}(\mathsf{G})\) with larger Cheeger constant \(\hbar_{\mathsf{Cheng}}\). Our result also highlights why bounded-degree expanders are particularly suited - as leveraged in Deac et al. (2022) - given that their commute time is only \(\mathcal{O}(\lvert\mathsf{E}\rvert)\)Chandra et al. (1996), making the bound in Theorem 5.5 scale as \(\mathcal{O}(1)\) w.r.t. the size of the graph. In fact, the concurrent work of Black et al. (2023) leverages directly the effective resistance of the graph \(\mathsf{Res}(v,u)=\tau(v,u)/2\lvert\mathsf{E}\rvert\) to guide a rewiring that improves the graph connectivity and hence mitigates over-squashing.

Why spatial-rewiring works.Chandra et al. (1996) proved that the commute time satisfies: \(\tau(v,u)=2\lvert\mathsf{E}\rvert\mathsf{Res}(v,u)\), with \(\mathsf{Res}(v,u)\) the **effective resistance** of nodes \(v,u\). \(\mathsf{Res}(v,u)\) measures the voltage difference between nodes \(v,u\) if a unit current flows through the graph from \(v\) to \(u\) and we take each edge to represent a unit resistance (Thomassen, 1990; Dorfler et al., 2018), and has also been used in Velingker et al. (2022) as a form of structural encoding. Therefore, we emphasize that Theorem 5.5 can be _equivalently rephrased as saying that nodes at high-effective resistance struggle to exchange information in an \(\mathsf{MPNN}\)_ and viceversa for node at low effective resistance. We recall that a result known as Rayleigh's monotonicity principle (Thomassen, 1990), asserts that the _total_ effective resistance \(\mathsf{Res}_{\mathsf{G}}=\sum_{v,u}\mathsf{Res}(v,u)\) decreases when adding new edges - which offer a new interpretation as to why spatial methods help combat over-squashing.

What about curvature?Our analysis also sheds further light on the relation between over-squashing and curvature derived in Topping et al. (2022). If the effective resistance is bounded from above, this leads to lower bounds for the resistance curvature introduced in Devriendt & Lambiotte (2022) and hence, under some assumptions, for the Ollivier curvature too (Ollivier, 2007, 2009). Our analysis then recovers why preventing the curvature from being 'too' negative has benefits in terms of reducing over-squashing.

About the Graph Transfer task.We finally note that the results in Figure 3 also validate the theoretical findings of Theorem 5.5. If \(v,u\) represent target and source nodes
on the different graph-transfer topologies, then \(\mathsf{Res}(v,u)\) is highest for \(\mathsf{CliquePath}\) and lowest for the \(\mathsf{CrossedRing}\). Once again, the distance is only a partial information. Effective resistance provides a better picture for the impact of topology to over-squashing and hence the accuracy on the task; in Appendix F we further validate that via a synthetic experiment where we study how the propagation of a signal in a \(\mathsf{MPNN}\) is affected by the effective resistance of \(\mathsf{G}\).

**Message of the Section:**\(\mathsf{MPNN}\)_s struggle to send information among nodes with high commute (access) time (equivalently, effective resistance). This connection between over-squashing and commute (access) time provides a unified framework for explaining why spatial and spectral-rewiring approaches manage to alleviate over-squashing._

## 6 Conclusion and discussion

**What did we do?** In this work, we investigated the role played by width, depth, and topology in the over-squashing phenomenon. We have proved that, while width can partly mitigate this problem, depth is, instead, generally bound to fail since over-squashing spills into vanishing gradients for a large number of layers. In fact, we have shown that the graph-topology plays the biggest role, with the commute (access) time providing a strong indicator for whether over-squashing is likely to happen independently of the number of layers. As a consequence of our analysis, we can draw a unified framework where we can rigorously justify why all recently proposed rewiring methods do alleviate over-squashing.

Limitations.Strictly speaking, the analysis in this work applies to \(\mathsf{MPNN}\)s that weigh each edge contribution the same, up to a degree normalization. In the opposite case, which, for example, includes GAT (Velickovic et al., 2018) and \(\mathsf{GatedGCN}\)(Bresson & Laurent, 2017), over-squashing can be further mitigated by pruning the graph, hence alleviating the dispersion of information. However, the attention (gating) mechanism can fail if it is not able to identify which branches to ignore and can even amplify over-squashing by further reducing 'useful' pathways. In fact, GAT still fails on the Graph Transfer task of Section 4, albeit it seems to exhibit slightly more robustness. Extending the Jacobian bounds to this case is not hard, but will lead to less transparent formulas: a thorough analysis of this class, is left for future work. We also note that determining when the sensitivity is 'too' small is generally also a function of the resolution of the readout, which we have not considered. Finally, Theorem 5.5 holds in expectation over the nonlinearity and, generally, Definition 5.2 encodes an average type of behaviour: a more refined (and exact) analysis is left for future work.

**Where to go from here.** We believe that the relation between over-squashing and vanishing gradient deserves further analysis. In particular, it seems that there is a phase transition that \(\mathsf{MPNN}\)s undergo from over-squashing of information between distant nodes, to vanishing of gradients at the level of the loss. In fact, this connection suggests that traditional methods that have been used in RNNs and GNNs to mitigate vanishing gradients, may also be beneficial for over-squashing. On a different note, this work has not touched on the important problem of over-smoothing; we believe that the theoretical connections we have derived, based on the relation between over-squashing, commute time, and Cheeger constant, suggest a much deeper interplay between these two phenomena. Finally, while this analysis confirms that both spatial and spectral-rewiring methods provably mitigate over-squashing, it does not tell us which method is preferable, when, and why. We hope that the theoretical investigation of over-squashing we have provided here, will also help tackle this important methodological question.

## Acknowledgements

We are grateful to Adrian Arnaiz, Johannes Lutzeyer, and Ismail Ceylan for providing insightful and detailed feedback and suggestions on an earlier version of the manuscript. We are also particularly thankful to Jacob Bamberger for helping us fix a technical assumption in one of our arguments. Finally, we are grateful to the anonymous reviewers for their input. This research was supported in part by ERC Consolidator grant No. 274228 (LEMAN).