How does over-squashing affect the power of GNNs?
Authors: Francesco Di Giovanni
T. Konstantin Rusch
Michael Bronstein
Andreea Deac
Marc Lackenby
Siddhartha Mishra
Petar Veličković
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). While understanding the expressive power of MPNNs is a key question, existing results typically consider settings with uninformative node features. In this paper, we provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We do so by measuring  the level of *pairwise interactions* between nodes that MPNNs allow for. This measure provides a novel quantitative characterization of the so-called over-squashing effect, which is observed to occur when a large volume of messages is aggregated into fixed-size vectors. Using our measure, we prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending on properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that *over-squashing hinders the expressive power of MPNNs*. Our theory also holds for geometric graphs and hence extends to equivariant MPNNs on point clouds. We validate our analysis through extensive controlled experiments and ablation studies.

Published in Transactions on Machine Learning Research (02/2024)
How does over-squashing affect the power of GNNs?
Francesco Di Giovanni' University of Oxford
francesco.di.giovvnnnn.t dw..giovanmmsss.oo.......
T. Konstantin Rusch' Massachusetts Institute of Technology
tkrusch@mit edu
Michael M. Bronstein
University of Oxford
Andreea Deac Université de Montréal
Marc Lackenby University of Oxford
Siddhartha Mishra ETH Zürich
Petar Veličković
Google Dind
Reviewed on OpenReview: https: openreview. net/ pormm id= QJRONs
Abstract
Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). While understanding the expressive power of MPNNs is key question, existing results typically consider settings with uninformative node features. In this paper, we provide rigorous analysis to delermine which function classes of node features can be learned by an MPNN given capacity. We do so by measuring the level of pairwise interactions between nodes that MPNNs allow for. This mcasure provides a novel quantitative charactcrization of the so-called over-squashing effect, which is observed to occur when large volume of messages is aggregated into fixed-size vectors. Using measure, prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that over-squac squrssqug hinders the expressive power of MPNNs. Our theory also holds for geometric graphs and hence extends to equivariant MPNNs on point clouds. We validate our analysis through extensive controlled experiments and ablation studies.
1 Introduction
Graphs describe the relational structure for large variety of natural and artificial systems, making learning on graphs imperative in many contexts (Veličković, 2023; DeZoort et al., 2023; Williamson, 2023). To this end, Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli et al., 2008) have emorged as a widely popular framework for graph machine learning, with plentiful success stories in science (Bapst et al., 2020;
Eqqual contribution.

---

Published in Transactions on Machine Learning Research (02/2024)
U
Figure I: We study the power of MPNNs in terms of the mixing they induce amoug features and show that this is affected by the model (via norm of the weights and depth) and the graph topology (via commute times). For the given graph, the MPNN learns stronger mixing (tight springs) for nodes v, u and u, w since their commute time is small, while nodes u, q and u, 2, with high commute-time, have weak mixing (loose springs). We characterize over-squashing as the inverse of the mixing induced by an MPNN and hence relate it to its power, In fact, the MPNN might require an impractical depth to solve tasks on the given graph that depend on high-mixing of features assigned to u, 2.
Davies et al., 2021; Blundell et al., 2021; Stokes et al., 2020; Liu et al., 2023) and technology (Monti et al., 2019; Mirhoseini et al., 2021; Perrow-Pinion et al., 2021).
Given an underlying graph and features, defined on its nodes (and edges), as inputs, a GNN learns paramctric functions from data. Due to the ubiquity of GNNs, characterizing their expressive power, i.e., which class of functions a GNN able to learn, a problem of great interest. In this context, most available results in literature on the universality of GNNs pertain impractical higher-order tensors (Maron al., 2019; Keriven & Peyré, 2019) unique node identifiers that may break the symmetries of the problem (Loukas, 2020). In particular, these results do not necessarily apply to Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017), which have emerged as the most popular class of GNN models in recent years. Concerning expressivily results for MPNNs, the most general available characterization is due to Xu et al. (2019) and Morris et al. (2019), who proved that MPNNs are, at most, as powerful as the Weisfeiler- graph isomorphism test (Weisfeiler & Leman, 1968) in distinguishing graphs without any features. This brings an important question:
Which classes of functions can MPNNs of a given capacity learn, if node features are specified??
Razin et al. (2022) address this question by characterizing the separation rank of MPNNs; however, their analysis only covers unconventional architectures that do not correspond to MPNN models used in practice. In contrast, Alon& & Yahav (2021) investigate this question empèrically, by observing that MPNNs fail to solve tasks which involve long-range interactions among nodes. This limitation was ascribed to a phenomenon termed as over-squashing, which loosely entails messages being 'squashed' into fixed-size vectors when the receptive field of node grows too fast. This effect was formalized in Topping et al. (2022); Di Giovanni et al. (2023); Black et al. (2023), who showed that the Jacobian of the nodes features is affected by topological properties the graph, such as curvature and effective resistance. However, all the aforementioned papers ignore the specifics of the task at hand, i.e. the underlying function that the MPNN seeks to learn, leading us the following question:
How does over-squahhin affect the expressive power of MPNNs? Can we measure it?
What about geometric graphs? In many scientific applications, data come as graphs embedded in Euclidean space. Since popular architectures resort to the message-passing paradigm (Gasteiger et al., 2021; Dauparas el al., 2022; Batzner et al., 2022), the expressive power of such models has been rephrased in the language of the WL test, once extended to account for the extra geometric information (Joshi et al., 2023). Nonetheless, the questions raised above are even more pressing for these tasks, where the graph is typically derived from point cloud using cutoff radius, while the features also contain information about the positions in 3D space. In fact, for such problems where the features may carry more valuable information
2

---

Published in Transactions on Machine Learning Research (02/2024)
than the 2D graph structure, argue that proposing new ways to assess the power of message- passsingg other than (variants of) the WT. test, is crucial. To this aim, in our paper we study generic message- passing equations with no assumptions on the nature of the features, meaning that they may also include additional positional information if the dataset is a point cloud embedded in Euclidaan space.
Contributions. Our main goal to show how over-squashing can be understood as the misalignment between the task and the graph-topology, thereby limiting the classes of functions that MPNNs of practical size can learn (see Figure 1). We start by measuring the extent to which an MPNN allows any pair of nodes in the graph to interact (via mixing their features). With this measure a tool, characterize which functions of node features can be learned by an MPNN and how the model architecture and parameters, as well as the topology of the graph, affect the expressive power. More concretely,
We introduce novel metric of expressive power that is based on the Hessian of the function learned by an MPNN and measures the ability of model to mix features associated with different nodes. This approach complements the current repertoire of tools at disposal to assess the power of GNNs, and is of interest independent of the over-squashing phenomenon.
We then prove upper bounds the Hessian of functions learned by MPNNs, hence dcriving limitations on the power of MPNNs to mix features (i.e., model interactions) according to the novel metric mentioned above. As far as we know, this is the first theoretical result stating limitations of MPNNs to learn functions and their derivatives.
We characterize over-squashing as the reciprocal of the maximal mixing that MPNNs can induce among nodes: the higher this measure, the smaller the class of functions MPNNs can learn. Differently from the WL-test, which depends on the separation of node representations based on the computational trees, our metric quantifies the ability of an MPNN to mix information associated with different. nodes and the cost required to do so in terms of size of the weights and depth.
We prove that the weights and depth must be sufficiently large - depending on the topology - to ensure mixing. For some tasks, the depth must exceed the highest commate time on the graph, resulting in impossibility statements. Our results show that MPNNs of practical size, fail to learn functions with strong mixing among nodes at high commute time.
We illustrate our theoretical results with controlled experiments that verify our analysis, by highlight- ing the impact of the architecture (depth), of the topology (commute time), and of the underlying task (the level of mixing required).
Thus, present a novel paradigm for deriving rigorous results in relating two key notions in graph machine learning, that of GNN expressive power and over-squashing.
2 The Message-Passingg paradigm
Definitions on graphs. We denote graph by G (V, E), E), where V is the set of n nodes while E are the edges. We assume that G is undirected, connected and non-bipartite and define the n x n adjacency matrix A as Ayu = if (v, u) E E and zero otherwise. We let D be the diagonal degree matrix with D.v := d, and use dmax and dmin to denote the maximal and minimal degrees. Since we are interested in the over-squashing phenomenon, which affects the propagation of information, we need to quantify distances on G. We let de(v, u) be the length of the shortest path connecting nodes v and (geodesic distance). While de describes how far two nodes u, v are in G, it does not account for how many different routes they can use to communicate. In fact, we will see below that the over-squashing of nodes v, and, more generally, the mixing induced by MPNNs among the features associated with v, can be better quantified by their commute time T(v, u), equal to the expected number of steps for a random walk to start at v, reach u, and then come back to v.
The MPNN-class. For most problems, graphs are equipped with features (x, heev C Rd, whose matrix representation is X E Raxd To study the interactions induced by a GNN among pairs of features, we focus graph-level tasks in Section F. of the Appendix, we extend the discussion and our main theoretical results
3

---

Published in Transactions on Machine Learning Research (02/2024)
to node-level tasks. The goal then is to predict function X + yG (X), where we assume that the graph G is fixed and thus yG Raad - IR is a function of the node features. MPNNs define family of parametric functions through iterative local updates of the node features: the feature of node v at layer t is derived as
h (()) (n6- (h""","")) (UD!
(v, u) (.))))E))) EE)) h/0 X
(1)
where f(), are learnable functions, g( is invariant to permutations and (1:3) denotes multiset meaning terms can be repeated. Specifically, we study class of MPNNs of the following form,
h = 00222 ((-1) + w(
Σ (h (t) b (n(-",, 1))
(0) = X
(2)
where acts pointwise, (2(1), w(O E Igd are weight matrices, A E R is any matrix satisfying Ava. > 0 if (e, u) E E and zero otherwise A is typically some (normalized) version of the adjacency matrix A - and sb((t)
is a learnable message function. The layer-update in (2) includes common MPNN-models such as GCN (Kipf & Welling, 2017), SAGE (Hamilton et al., 2017), GIN (Xu et al., 2019), and GatedGCN (Bresson & Laurent, 2017). As commented extensively in Section 6, this is the most general class of MPNN equations studied thus far in theoretical works on over-squashing: unless otherwise stated, all our considerations and analysis apply to MPNNs as in (2). For graph-level tasks, permutaaiion-nnvaiaan readout READ is required - usually MAX, MEAN, or SUM. We define the graph-level function computed by the MPNN after m layers to be
VG
(m) (X) 0 @TREAD( (h("))) }),
(3)
for some learnable 0 E Rd. While a more complex non-linear readout can be considered, we restrict to a single linear-layer since we are interested in the mixing among variables induced by the MPNN itself through the topology (and not in readout, independently of the graph-structure).
MPNNs geometric graphs. We note that (2) also describes a class of generic, equivariant MPNNs over a point cloud embedded in Fuclidean space, once the matrix A is intended to encode the pairs of points that exchange information across each typricllllllyy creating a graph G by drawing a weighted edge between any pair of points whose distance is smaller than a cutoff radius. In fact, throughout our analysis we have no restriction on the type of features h, that can also contain the position of node 3D space. Accordingly, our theoretical results below hold for MPNNs on both 2D and 3D data, since they pertain to how the message passing paradigm models pairwise interactions among different points (nodes). To streamline the presentation, we often omit to specify that the features can also encode 3D information (when available).
3 On the mixing induced by Message Passing Neural Networks
As one of the main contributions of this paper, we propose a new framework for characterizing the expressive power of MPNNs by estimating the amount of mizing they induce among pairs of features x, and x corresponding to the nodes v and u E V. To motivate our definition, fix the underlying graph G, lot yG be the ground-truth function to be learned, and suppose, for simplieity, that the node features (2:) are all scalar. If yG is smooth function, then we can take the Taylor expansion of yc at any point x (Z1,..., In) and obtain polynomial in the variables (zI,..., In), up to higher-order corrections. The miring induced by yo on the features Te,Ta Tu can then be expressed in terms of mized product monomials of the form T,Ta, and the powers thereof. The lowest-degree mixed monomials of this form are multiplied by the Hessian (i.e. the second-order derivatives) of yg. Accordingly, we can take the entries v, u of the Hessian of yc as the simplest mcasure of pairwise mixing induced by Ve over the nodes v, u. In fact, to make things more concrete, note that if (x(x)= @o(xx) + Φ1 (I.), then the mixing (Hessian) would always be zero since the variables are fully separable; conversely, if yc(x)= 6(x] x,), then the amplitude of the mixing (Hessian) depends on how nonlinear o is. The same reasoning applies to digneo-dimensionall node features too: Definition 3.1. For a twice differentiable induced by yo among the features x, and x,, associated with nodes v, u.
yG of node features (xi), the maximal mixing
82 yG X)
mix (v, u) = max max 15a
(4)
Oxgdnu
4

---

Published in Transactions on Machine Learning Research (02/2024)
We note that the first maximum is taken over all imput features considering that the Hessian of yG is itself function of the node features over the graph while the second maximum is taken over all entries a, 8 of the d-dimensional node features X, and x,; it is straightforward to adapt the results below to alternative definitions based on different norms of the Hessian.
Problem statement. Our goal to study the expressive power of MPNNs in terms of the (maximal) mixing they can generate among nodes v, u. A low value of miring implies that the MPNN cannot learn functions Us that require high miring of the features associated with v. and hence they cannot model 'product -type interactions per explanation based the Taylor expansion. We investigate how weights and depth on the one side, and the graph topology on the other, affect the mixing of an MPNN.
The requirement of smoothness. In many applications, especially when deploying neural network models to solve partial differential equations, the predictions need to be sufficiently regular (smooth), which motivates the adoption of smooth non-lincar activations (Hornik ct al., 1990; Brandstetter et al., 2021; Equer al., 2023). Our analysis below follows this paradigm and holds for all activations a that are (at least) twice differentiable, including smoother versions of ReLU such as the GELU function.
3.1 Pairwise mixing induced by MPNNs
In this Section, our goal is to derive an upper bound on the maximal mixing induced by MPNNs, defined above, over the features associated with pairs of nodes v, u. To motivate the structure of this bound, we consider the simple yet. illustrative setting of an MPNN as in (2) with scalar features, weights w, w > 0 and a linear message function of the form cb(2,)) y) = c + czy, for some learnable constants C1, In this case, the layer-update (2) takes the very simple form,
h.th (W((Sh((
S :
w " I cidiag AA1 c2A E ER*x.
(5)
where 1 E IR" is the vector of ones. Hence, the operator wS governs the flow of information from layer t - to layer t- once we factor out the dcrivatives of and the k-power of this matrix (wS)* determines the propagation of information on the graph over k layers, i.e. over walks of length k.
Suppose that nodes v, at distance r the graph. If this MPNN has depth m, to have any mixing among the features of and u, there has to be a node that receives information from both and u, which only occurs when m 2 r/2. If m = r/2, then we can roughly estimate the mixing at node i as ((w)))" When m > r/2, information from e and u can arrive at after being processed at an intermediate node j: in fact, this node j first collects information from both v and u over a walk of length m - k, and then shares it with node over walk of length We then obtain terms of the form Σ. ((WS) "* ((WS((()**))) (((() since we are summing over all possible ways of aggregating information from v and u across intermediate nodes j, before måring it at i.
A similar argument also works in the general case of (2), once we account for bounds on the non-linear activation function a by co = max(lo'), [o"",, and we choose w, C2, satisfying
|| S as, ||w(|| s w, || S Ci.
for i = 1,2, where Vath is the Jacobian of sb with respect to the i-th variable, and ||| is the operator norm of a matrix. We note that for trained MPNNs the weights would be finite and bounded, so our assumption is mild. For models with linear eb such as GCN, SAGE or GIN, these constants will suffice in deriving the upper bound on the mixing. However, the more general case of non-linear message functions v which for example includes GatedGCN, we also need to account for the term Qu,, defined below, which arises due the Hessian of sp when laking second-order derivatives of the MPNN (2): given S in (5), we set.
P = (S 1mm-k-1p --1 diag (1T (
Q P + P -=1- Tdiag(1 S* (diag(A1) + A))
We assume that the Hessian of sb is bounded as (3) and that mix sm) (v, u) is its maximal mixing of nodes v, u as per Definition 3.1.
(m) is the MPNN-prediction ||000 < c(2), Recall that ye
5

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 3.2. Consider an MPNN of depth in (2), where and wit)) are C² functions and we denote the bounds on their derivalives and on the norm of the weights as above. Let S and Qi. be defined as in (5) and (6), respectively, If the readout is MAX, MEAN or SUM and 0 in (3) has unit norm, then the mixing mix smo (v, u) induced by the MPNN over the features of nodes v, u satisfies
m--1
mix 9
amm (1, u) S
Σ k=0
(cow)am-k-1 (w(S">>)) T diag(1 sm Qx())ss)....
(7)
Theorem 3.2 shows how the mixing induced by an MPNN depends on the model (via regularity of a, norm of the weights w, and depth m) and on the graph-topology (via the powers of A, which enters the definition of S in (5)). Despite its generality, from (7) it is as yet unclear which specifie properties of the underlying graph affect the mixing the most, and how weights and depth of the MPNN can compensate for it. Therefore, our goal now is to expand (7) and relate it to known quantities on the graph and show how this can be used to characterize the phenomenon of over-squashing. First, we introduce a notion of capacity of an MPNN in the spirit of Loukas (2020).
The capacity of an MPNN. For simplicity, we assume that C, 1, since this is satisficd by most commonly used non-linear activations - it is straightforward to extend the analysis to arbitrary Co. Definition 3.3. Given an MPNN with m layers and w the mazimal operator norm of the weights, we soy that the pair (m,w) w) represents the capacity of the MPNN.
A larger capacity, by increasing either expressive power and can hence induce larger mixing among the nodes u,u. Accordingly, given v, u,u, we formulate the problem of expressivity as: what is the capacity required to induce enough mizing mixyc (v, u)
w, both, heuristically implics that the MPNN has more
Studying exprcssivity through derivatives. In applications to physics and PDEs, we may often need the neural-nelwork to also match derivatives of a larget function (Hornik el al., 1990). Theorem 3.2 shows that the second-order derivatives of MPNN predictions as in (2), cannot approximate second-order derivatives of graph-functions yG whose associated mixing is larger than the right hand side of (7).To the best of our knowledge, this is the first theoretical analysis on the limitations of MPNNs to approximate classes of functions and the derivatives thereof.
Message of the Section: We can estimate the nonlinear, joint dependence of a smooth graph function on puirs of node features in terms of ils second-order derivatives. We refer to this quantily as mixing, since it relates mized product monomials of the Taylor polynomial exponsion. Since méring is property of the task, assessing the miring ability of MPNN becomes an additional metric of erpressive power. Graph functions whose miring violales (7), cannot be learned by MPNNs salisfying Theorem 3.2.
4 Over-squashing limits the expressive power of MPNNs
Ever-squashing was originally described in Alon & Yahav (2021) as the failure of MPNNs to propagate information across distant nodes. In fact, Topping et al. (2022); Black et al. (2023); Di Giovanni et al. (2023) showed that over-squashing quantified by the sensilivity of node v to the input feature al node via their Jacobian is affected by topological properties such as curvature and effective resistance; however, no connection to how over-suuashing affects the expressive power of MPNNs, nor proposal of measures for over-squashing have been derived. In light of these works, it is evident that over-squashing is related to the inability of MPNNs to model interactions among certain nodes, depending on the underlying graph topology. Since one can rely on the Taylor expansion of graph function to measure such interactions through the sccond-order derivatives, i.c. the maximal mixing, we leverage Definition 3.1 to propose novel, broader, but more accurate, characterization of over- sverssqushhnn:
Definition 4.1. Given the prediction vic") (m) of an MPNN with capacity (m, we define the pairwise over-squashing of u, a as
OSQ (m, w) = mix (mo (v.u)
6

---

Published in Transactions on Machine Learning Research (02/2024)
Our notion of over-squashing is patrwise measure over the graph that naturally depends the graph- topology, as well the capacity of the model. In particular, it captures how over-squashing pertains to the ability of the model to mix (induce interactions) between features associated with different nodes. If such maximal mixing is large, then there is no obstruction to exchanging information between the given nodes and hence the over-squashing measure would be small; conversely, the over-squashing is large precisely when the model struggles to mix features associated with nodes e and u.
In general though, computing the actual mixing induced by MPNN may be difficult. Accordingly, can rely on Theorem 3.2 to derive proxy for the over-squa measure that will be used to obtain necessary conditions on the capacity of an MPNN to induce a required level of mixing:
Definition 4.2. Given an MPNN with capacity (m, w), we apprezimale O5Qu,u w) by
==
172
(W(S"(()))) diag(1 "S + +x() an ) W
2m 2 k-1
-1
S <SSQu,u (SQueu(mm (m, w).
k=0
The upper bound is a simple application of Theorem 3.2. To justify our characterization, we begin by consid- ering simple settings. If the network has no bandwidth through the weights (w = 0), then OSQ.,, 0) oc. Besides, the proposed measure captures the special case of under-reaching (Barceló et al., 2019), since OSQu,u is infinite (i.e.; zero mixing) whenever 2m < dc(u, u), where de is the shortest-walk distance on G. We also recall that for simplicity we have taken Go but the measure extends to arbitrary non-linear activations a. Finally, generalize the characterization of OSQ to node-level tasks in Section E of the Appendix.
We can rephrase our novel approach for studying expressivity through pairwise mixing, in terms of the over-squashing measure and its proxy. By Theorem 3.2 we derive that a necessary condition for a smooth MPNN to learn a function yo with mixing mix (v, u) is
DSQu.u(m, w) < (mix (v, u))-
(8)
An MPNN of given capacity might suffer or not from over-squashing, depending on the level of mixing required by the underlying task. Over-squashing can then be understood as the misalignment between the task and the underlying topology, as measured by the gap between the maximal mixing induced by an MPNN over nodes v, u and the mixing required by the task.
For a given graph G, to reduce the value of OSQ and hence satisfy (8), the capacity (m, (m,w) must satisfy constraints posed by G and the choice v, u. Since we can increase the capacity by taking either larger weights or more layers, we consider these two regimes separately. Below, we expand (8) in order derive minimal requirements on the quantities and m to induce certain level of mixing, thereby deriving lower bounds on the capacity of MPNN to learn functions with given second-order derivatives (mixing).
Strategy.
Choice of A. For simplicity, we restrict our analysis to the case A = Asym := D 111/A -1/2 and extend the results to D and A in Section D of the Appendix. For the unnormalized adjacency, the bounds look more favourable, simply because we are no longer normalizing the messages, which makes the model more sensitive for all nodes. In Section D.4 we comment on how one could account for the lack of normalization by taking relative measurement for OSQ in the spirit of Xu et al. (2019).
4.1
The case of fixed depth m and variable weights norm w
To assess the ability of the norm of the weights w to increase the capacity of an MPNN and hence reduce OSQ, we consider the boundary case where the depth is the minimal required for an MPNN to have a non-zero mixing among v, u (half the shortest-wall walk distance de between the nodes).
Theorem 4.3. Let A = Asym, r r= de(v, u), m = [r/2], and q be the number of paths of length r between v and For an MPNN salisfying Theorem 3.2 with copacity (m [r//]], w); we find OSQ (m, w) (c2w)"(A") 2
7

---

Published in Transactions on Machine Learning Research (02/2024)
1. In particular, if the MPNN generates miring mixyc (v, u), then
dmin
mixua (v, w) 7
W 2
Theorem 4.3 highlights that if the depth is set as the minimum required for any non-zero mixing, then the norm of the weights w has to be large enough depending on the connectivity of G - recall that for models as GCN, we have c = 1. However, increasing w is not optimal and may lead to poorer generalization capabilities (Bartlett et al., 2017; Garg et al., 2020). Besides, controlling the maximal operator norm from below is, in general, tricky. A more reasonable stralegy might be then to increase the number of layers; we explore such approach next, after reviewing a few explicit examples.
Some examples. We illustrate the bounds in Theorem 4.3 and for simplicity, set O2 1. Consider tree Ta of arity d, with v the root and u a leaf at distance r and depth m = r/2; then OSQ (m, w) 2 w (d+1))=- and the operator norm required to generate mixing y(u, u) is
( u) d d+1
w ž (d+1)
We note that by taking d = we recover the case of the path-graph (1D grid). Since the operator norm of the weights grows with the branching factor, we see that, in general, the capacity required by MPNNs to solve long-range tasks could be higher graphs than on sequences (Alon & Yahav, 2021). We also consider the case of a 1-layer MPNN on a complete graph K, with v * u. We find that OSQ (m, w) 2 (n 1)/w and hence the operator norm required to generate mixing y(v, u) w 2 (n - 1)y(", u). We note how the measure of over-squashing also captures the problem of redundancy of messages (Chen al., 2022). In fact, even if U, u are at distance 1, the more nodes are there in the complete graph and hence the more messages are exchanged, the more difficult for shallow MPNN to induce enough mixing among those specific nodes.
4.2 The case of fixed weights norm and variable depth
We now study the (desirable) setting where is bounded, and derive the depth necessary to induce mixing of nodes u. Below, we let 0 = Ao < λ S ... S An-1 be the eigenvalues of the normalized graph Laplacian A -I Asym: we note that X is the spectral gap and An-1 < 2 if G is not bipartite (Chung & Graham, 1997). We also recall that de is the shortest-walk distance and T is the commute time (defined in Section 2). Finally, dimax and dmin denote the maximal and minimal degrees, respectively, we set 7 := v /dmaxx/ dmmnn
Theorem 4.4. Consider an MPNN satisfying Theorem 3.2, with max w/w / + S 1, and A Asym- If Os w) (mixyc (v, u)) 1, i.e. the MPNN generates måring mix,c (v, u) among the features associated with nodes v, u, then the number of layers m. satisfies
m 2 T(V,u)
EE|
mix (v. u)
1(7++) -122--1111---1
-2
+ =2))))
+
(9)
40²
di
d
where r = da(u, u), μ == 1 + (0 (1 + +7) and - =1=02""==axxocss-1 |1
max0cesn-
c2ddl <1
Theorem 4.4 provides a necessary condition on the depth of an MPNN induce enough mixing among nodes U, u. We see that the MPNN must be sufficiently deep if the task depends interactions between nodes at high commute time and in fact, if the required mixing is large enough, then m 2 T(V, u). Note that the lower bound on the depth can translate into a practical impossibility statement, since the commute time can be as large as Onn2) (Chandra et al., 1996). We also recall that for MPNN models such as GCN, the bounds above simplify since c(2) = O and hence = 1. If we let diam (G) be the diameter of G. Theorem 4.4 implics: Corollary 4.5. Given a graph with features, nodes v, u, and an MPNN satisfying Theorem 4.4, if the depth mn fails to satisfy (9), then the MPNN cannot learn functions with miaing mixyc (f,
Therefore, if (i) the graph is such that the commute time between v. large, and (ii) the task depends high-mixing of features associated with u, u, then ouer-squashing limits the expressive power of
8

---

Published in Transactions on Machine Learning Research (02/2024)
MPNNs with bounded depth. In fact, increasing the depth based on the number of nodes may also cause issues connected to vanishing gradients (Di Giovanni et al., 2023) and over-smoothing (Rusch et al., 2023a; Cai & Wang, 2020; Rusch et al., 2023b; Di Giovanni et al., 2022). In contrast to existing analysis on the limitations of MPNNs via graph-isomorphism test, our results characterize the expressivity of MPNNs even when meaningful (geometric) features are provided. Corollary 4.5 implies that for any given maximal number of layers m and for any graph G with commute time T, we can identify classes of functions that are outside the hypothesis space of the MPNNs: these are the ones whose mixing violates (9).
Since the commute time of two adjacent nodes v, u equals 2 if u) is cut-edge (Aleliunas et al., 1979), our result shows that MPNNs may require m = S2(EE) to generate enough mixing along a cut-edge, drawing connection with Zhang et al. (2023), where it was shown that most GNNs fail to identify cut-edges on unattributed graphs. Moreover, since the commute time is proportional to the effective resistance R by 2R(v, E)|E| = 7(, u), Theorem 4.4 connects recent. works Di Giovanni et al. (2023); Black et al. (2023) relating the Jacobian of node features and R, and the expressive power of MPNNs in terms of their mixing.
We emphasize how our theoretical results are far more general than assessing the inability of an MPNN to solve tasks with long-range interactions. Our analysis shows, precisely, how over-squashing can be understood as fundamental problem associated with how hard as measured by the number of layers required - is for an MPNN to exchange informalion between nodes that are 'badly connected'' as per their commute time metric distance, whatever this information might be.
Message of the Section: If the miring generated by an MPNN is small, then the model struggles to exchange information between nodes. Accordingly, we propose to measure over-squahhing as the inverse of the mining induced by an MPNN. Nezt, we asked: given a target level of miring, what is the capacity of the MPNN required to match such quantity? We have addressed this question for the cases of bounded depth (Theorem 4-3) and bounded weights (Theorem 4-4)- In the latter, we have shown that the minimal number of layers required by an MPNN to match a given level of mixing, grows with the commute time distance. Therefore, our analysis explicitly identifies classes of functions that are impossible to be learned on cerlain graphs for MPNNs of bounded depth.
5 Experimental validation of the theoretical results
Next, we aim to empirically verify the theoretical findings of this paper, i.e., the characterization of the impact of the graph topology (via commute time r), the GNN architecture (depth, norm of weights), and the underlying lask (node mixing) on over-squashing. This, however, requires detailed information about the underlying function to be learned, which is not readily available in practice. Hence, we perform our empirical test in a controlled environment, but at the same time, we base our experiments on the real world ZINC chemical dataset (Irwin et al., 2012) and follow the experimenta setup in Dwivedi et al. (2020), constraining the number of molecular graphs to 12K. Moreover, we exclude the edge features from this experiment and fix the MPNN size to ~100K parameters. However, instead of regressing the constrained solubility based on the molecular input graphs, we define our own synthetic node features as well as our own target values as follows.
Let } be the set of the 12K ZINC molecular graphs. We set all node features to zero, except for two, which are set to uniform random numbers a between O and 1 (i.e., -/,,=/. ~ ((,,, 1)) for all i. The target output is set to y² = tanh(x + ) for all i. Hence, the task entails a non-lincar mixing with non vanissii second derivatives. The two non-zero node features oiee at are positioned on G, according to the commute time T, ie.,, for a given a E [0, 1], we choose the nodes u², v² as the a-quantile of the r-distribution over G. This enables us to have the desired control on the level of commute time of the underlying mixing (iee. 01 02, if aj results in a lower than a2). See Fig. 2 for an illustration of ZINC graph together with the histogram of the corresponding between all pairs of different nodes. We call this graph dataset the synthetic ZINC dataset.
We consider four different MPNN models namely GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), GraphSAGE (Hamilton et al., 2017), and GatodGCN (Bresson & Laurent, 2017). Morcover, we choose the MAX-pooling as the GNN readout, which is supported by Theorem 3.2 and forces the GNNs to make use of the message-passing in order to learn the mixing.
9

---

Published in Transactions on Machine Learning Research (02/2024)
2 30
2 36
Ri 252
Frequencis 15
20
100 200
Figure 2: (Left) Exemplary molecular graph of the ZINC (12K) dataset with colored nodes corresponding to different values of commute time т. We note that T is a more refined measure than the distance, and fact. beyond long-range nodes (red case), also captures other topological properties (yellow nodes are adjacent but belong to cut-edge, their commute-time is 2|E (Right) Histogram of commute time between all pairs of the graph nodes.
5.1 The role of commute time
In this lask, empirically analyse the effect of the commute time of the underlying mixing the performance of the MPNNs. To this end, we fix the architecture for all considered MPNNs. In particular, we set the depth to m max; (eax//ciimmG')//a. such that the MPNNs are guarantced not to underreach. We further vary the value of the a-quantile of the r-distributions over the graphs G between and 1, thus controlling the level of commute times. According to our theoretical findings in Section 4, the measure OSQu,u (Definition 4.2) heavily depends on the commute time of the underlying mixing as derived Theorem 4.4. In fact, this can be empirically verified in Appendix Fig. 7, where OSQu,u increases for increasing values of a. Thus, perform significantly worse for increasing levels of the commute time. This is indeed confirmed in Fig, 3 depicting the resulting test. mean absolute error (MAF) (average and standard deviation over several random weight initializations), and showing that the test MAE increases for larger values of a for all considored MPNNs. The same qualitative behavior can be observed for the training MAE (Appendix F.2). We further note that the models exhibit low standard deviation, as can be seen in Fig. as well.
which happens to be m = 11 for the considered ZINC 12K graphs,
would expect the MPNNs to
10
0.060
10-2
Test MAE
MAE
0.010
GCN
GCN
10-9
GIN
GIN
GraphSAGE
GraphSAGE
GatedGCN
GatedGCN
0.8
0.001
Commute time o-quantile
Number of layers m
Figure 3: Test MAF (average and standard deviation over several random weight initializations) of GCN, GIN, GraphSAGE, and GaledGCN on synthetic ZINC, where the commute time of the underlying mixing is variod, while the MPNN architecture fixed (e.g., depth, number of parameters), i.c., mix- ing according to increasing values of the a-quantile of the r-distribution over the ZINC graphs.
Figure 4: Test MAE (average and standard deviation over several random weight initializations) of GCN, GIN, GraphSAGE, and GatedGCN on synthetic ZINC, where the commute time fixed to be high (i.c., at the level of the 0.8-quantilc), while only the depth of the underlying MPNN is varied between 4 and 32 (all other architectural components fixed).
10

---

Published in Transactions on Machine Learning Research (02/2024)
5.2 The role of depth
In this task, we study the effect of the depth on the performance of the MPNNs. To this end, we consider high commute time-regine by setting a 0.8. Note that in this case the maximum (over all graphs G') shortest path between two nodes u', of is 14. Therefore, depth of = 7 is sufficient to avoid under-reaching all graphs. However, according to the over-squashing measure we provide and the conclusions of Theorem 4.4, we expect the MPNNs to be able to induce more mixing among nodes v, and hence reduce the error, as we increase the number of layers. This expectation is further evidenced in Appendix Fig. 8, where the computed OSQ decreases for increasing number of layers. In Fig. 4, plot the test MAE (average and standard deviation over several random weight initializations) of all considered MPNNs for increasing number of layers. We can indeed see that all considered GNNs benefit from depth, and thus higher capacity (Definition 3.3), as GatedGCN obtains the lowest test MAE with 16 layers, as well as GraphSAGE, GIN, and GCN with 32 layers. The same qualitative behavior can be observed for the training MAE (Appendix F.2). Our theoretical results provide a strong explanation as to why a task only depending on the mixing of nodes within 14 hops
that 7 layers would suffice actually benefits from many more layers. Naturally, we cannot increase the depth arbitrarily, impact the trainability of the MPNNs (Rusch et al., 2022). Moreover, as can be additionally scen in Fig. 4, all models exhibit low standard deviation (over several trained MPNNs). We finally point out that, while over-squashing occurs - as can be seen when the number of layers 'only' equals the minimal one to avoid underreaching can be mitigated by taking much deeper architectures.
at some point other issues emerge, such vanishing gradients, which
5.3 The role of mixing
We further test the considered MPNN architectures on their performance with respect to different mixings. To this end, we consider again the ranh-based mixing as in our previous tasks (i.e., regressing targets y = tanh(x + xx,,) for each graph G in the dataset), as well another mixing based on the exponential function (i.e., with targets yi exp(xt; + x ))- We note that these two tasks differ significantly in terms of their maximal mixing values (4) (shown in Table 1). Thus, according to (8) and Theorem 4.4, would expect that MPNNs perform significantly worse in the case of higher maximal mixing, i... for the exponential-based mixing compared to the tanh-mixing. To confirm this empirically, we train the MPNNs on both types of mixing and provide the resulting relative MAEs (i.c., MAE divided by the L of the targets) in Table 1. We can see that all four MPNNs perform significantly better on the tanl-mixing than on the exponential based mixing. Moreover, increasing the range for the exponential- based mixing from 1 to 1.5 further impairs the performance of all considered MPNNs. In order to check if this difference in performance can simply be explained by higher capacity required by neural network to accurately approximate the mapping exp(x +y) compared to tanh(x for some inputs 2/ R, we train a simple two-layer feed-forward neural network (with 2 inputs, i.e., x and y) on both mappings. The trained networks reach a similarly low relative MAE of 4.6 x 10-4 for the tanh(x + y) mapping as well as 4.1 x 10-4 for the exp(x + y) mapping using an input range of (0, 1) and 4.0 10 for an input range of (0, 1.5). Thus, we can conclude that the significant differences in the obtained results in Table 1 are not caused by a higher capacity required by a neural network to learn the underlying mappings of the different mixings.
Table 1: Relative MAE of GCN, GIN, GraphSAGE and GatedGCN on different choices of mixing on synthetic ZINC for fixed 0.8-quantile of the commute time distributions over graphs G₁.
Mixing
imput interval
marimal mixing
GCN
GIN
GraphSAGE
GatedGCN
tanli(r + x..)
(0,1) 1)
R 0.77
0.024
0.014
0.006
0.004
exp(x),. + )
(0,
2 7.4
0.043
0.021
0.033
0.008
exp(x) + )
(0,
2 20.1
0.054
0.035
0.075
0.014
11

---

Published in Transactions on Machine Learning Research (02/2024)
6 Discussion
expressive power of MPNNs. The MPNN class in (2) is as powerful as the 1-WL, test. (Weisfeiler& & Leman, 1968) in distinguishing unattributed graphs (Xu et al., 2019; Morris et al., 2019). In fact, MPNNs typically struggle to compute graph properties on feature-less graphs (Dchmamy et al., 2019; Chen et al., 2020; Sato et al., 2019; Loukas, 2020). The expressivity of GNNs has also been studied from the point of view of logical and tensor languages (Barceló et al., 2019; Azizian & Telarge, 2021; Geerts & Reutter, 2022). Nonetheless, far less is known about which functions of node features MPNNs can learn and the capacity required to do so. Razin et al. (2022) recently studied the separation rank of a specific MPNN class. While this approach is a strong inspiration for our work, the results in Razin et al. (2022) only apply to a single unconventional family of MPNNs which does not include MPNN models used in practice. Our results instead hold in the full generality of (2) and provide a novel approach for invesligating the expressivity of MPNNs through the mixing they are able to generate among features.
Related Work:
Mixing and the WL test. We emphasize that throughout our analysis we had no assumption the nature of the features, that can in fact be structural or positional - meaning that the MPNNs we have considered above, may also be more powerful than the 1-WL test. Our derivations do not rely on the ability to distinguish different node representations, but rather on the ability of the MPNN to mix information associated with different nodes. This novel alternative paradigm may help design GNNs that are more powerful at mixing than MPNNs, and may further shed light on how and when frameworks such as Graph Transformers can solve the underlying task better than conventional MPNNs. Similarly, our analysis holds for all equivariant MPNNs of the form (2) acting on geometric graphs embedded in Euclidean space, independent of the geometric information included in the features.
Differences between our results and existing works on over-squashing. The problem of over- squashing was introduced in Alon & Yahav (2021) and studied through sensitivity analysis in Topping el al. (2022). This approach was generalized in Black et al. (2023); Di Giovanni et al. (2023) who proved that the Jacobian of node features is likely to be small if the nodes have high commute time (offective resistance). We discuss more in detail the novelty of this work when compared to Topping et al. (2022); Di Giovanni et al. (2023). (i) In Topping et al. (2022); Di Giovanni et al. (2023) there is no analysis which functions MPNNs cannot learn
consequence of over-squashing, nor a formal measure of over-squashing is provided. In fact, they only derive some conditions under which the Jacobian of node features can be small, but do not connect it to the ability of MPNNs to learn desired function classes. Besides, the Jacobian of node features may not be suited for studying over-squashin for graph-level tasks. Note that our theory holds for node-level tasks and generalize existing approaches (see Appendix E). (ii) The analysis in Topping et al. (2022) does not study over-squashing among nodes at distance larger than 2 and does not provide insights on the capacity required to learn certain tasks. (iii) Finally, the analysis in Di Giovanni et al. (2023) does not account for MPNNs such GatedGCN, and is only carried out in a simplified setting where the activation function is chosen to be a ReLU and its derivatives are taken to be the same, in expectation, for every path in the computational graph. We have extended these ideas to connect over-squashing and expressive power by studying higher-order derivatives of the MPNN and relating them to the capacity of the model and the underlying graph-topology.
6.1 Limitations and ways forward
The measures OSQ and OSQ. Definition 4.1 considers pairs of nodes and second-order derivalives; this could be generalized to build a hierarchy of measures with increasingly higher-order interactions of nodes. The proxy (lower bound) OSQ in Delinition 4.2 allows to derive necessary conditions for the MPNN to learn classes of functions based on their mixing. If, depending the problem, one has access to better estimates the mixing induced by an MPNN than (7), then one can extend our approach and get a finer approximation of OSQ. In the paper we focused our analysis on the case of graph-level tasks; we provide an extension to node-level functions in Section E.
Beyond sum-aggregations. Our results apply to MPNNs as (2), where A is constant, and do not include attention- based MPNNs (Veličković al., 2018; Brody et al., 2022) or Graph-Transformen Transformers (Kreuzer et al., 2021; Mialon et al., 2021; Ying et al., 2021; Rampasek et al., 2022) which further depend features via
12

---

Published in Transactions on Machine Learning Research (02/2024)
normalization. Extending the analysis to these models is only more technically involved. More generally, could replace the aggregation Σ. Avu in (2) with smooth, permutation invariant operator Q (Bronstein et al., 2021; Ong & Veličković, 2022). Our formalism will then prove useful to assess if different aggregations are more expressive in terms of the mizing (interactions) they are able to generate.
Graph rewiring. Another way of going beyond (2) to find MPNNs with lower OSQ is to replace A with a different matrix A', (partly) independent of the connectivity of the input graph. In other words, one could rewire the graph, by replacing G with G'. Indeed, Theorem 4.4 further validates why recent graph-rewiring methods such as (Arriiz-Rodriguez al., 2022; Karhadkar et al., 2023; Deac et al., 2022; Black et al., 2023) manage to alleviate over-squashin: by adding edges that decrease the overall effective resistance (commute time) of the graph, these methods reduce the measure OSQ. More generally, Definition 4.2 allows one to measure whether given rewiring is beneficial in terms of over-squashing (and hence of the mixing generated) and what extent. In fact, follows from Thcorem 4.4 that methods like (Deac al., 2022; Shirzad al., 2023) are optimal from the point of view of friendliness of the computational graph to messsago-passing since they both propose propagale information over exponder graphs, which are sparse and have commute time scaling linearly with the nunber of edges. Finally, theoretical results suggest that for data given by point clouds in 3D space, the choice of a computational graph over which message passing can operate, should also account for the its commute time, given that the latter is closely aligned with over-squashing.
Acknowledgemmnts. The authors would like to thank Dr. Martín Arjovsky, Dr. Charles Blundell and Dr. Karl Tuyls for their insightful feedback and constructive suggestions on an earlier version of the manuscript.
13

---

Published in Transactions on Machine Learning Research (02/2024)
References
Romas Aleliunas, Richard M Karp, Richard J Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Poundations of Computer Science (sJes 1979), pp. 218 223. IEEE Computer Sociely, 1979.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Adrián Armaiz-Rodrigues Ahmed Begga, Francisco Escolano, and Nuria Oliver. DiffWire: Inductive Graph Rewiring via the Lovász Bound. In The First Learning on Graphs Conference, 2022. URL https://openreviier wwt.eee.neee/pdddddddddeeeeeeee
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https://openreviit wwt.:/eeeeeoteee..m
IxHgXYN44bv..
Victor Bapst, Thomas Keck, Ctabska-Barwiite Craig Donner, Ekin Dogus Cubuk, Samuel Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448 454, 2020.
Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019.
Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Speedrally-normmaizee margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Kornbluth, Nicola Molinari, Tess E Smidt, and Boris Kozinsky. E (3)-qquivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 13(1):2453, 2022.
Mitchell Black, Amir Nayyeri, Zhengchao Wan, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. arXiv preprial WVi:22922008355, 2023.
Charles Blundell, Lars Buesing, Alex Davies, Petar Veličković, and Geordie Williamson. Towards combinatorial invariance for kazhdan-lusatig polynomials. arXiv preprint arXio:2111.1116 2021.
Johannes Brandstetter, Daniel Worrall, and Max Welling. Message passing neural pde solvers. Tn International Conference on Learning Representations, 2021.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv: 2017.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. Xrxiv preprint arXiv:2104 13478, 2021.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprinl arXiv:2006.133) 13318, 2020.
Ashok K Chandra, Prabhakar Raghavan, Walter Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. computational complexity, 6(4): 312-340, 1996.
Rongqin Chen, Shenghui Zhang, Ye Li, et al. Redundancy-free message passing for graph neural networks. Advances in Neural Information Processing Systems, 35:4316 4327, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? A duances in neural information processing systems, 33:10383 10395, 2020.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical Soc., 1997.
Justas Dauparas, Ivan Anishchenko, Nathaniel Bennett, Hua Bai, Robert Ragotte, Lukas F Milles, Basile IM Wicky, Alexis Courbet, Rob de Haas, Neville Bethel, et al. Robust deep learning- based protein sequence design using proteinmpnn. Science, 378(6615):49 56, 2022.
A. Davies, P. Veličković, I.. Buesing, S. Blackwell, D. Zheng, N. Tomašev, R. Tanburn, Battaglia, C. Blundell, A. Juhász, et al. Advancing mathematics by guiding human intuition with ai. Nature, 600(7887):70 74, 2021.
Andreca Deac, Mare Lackenby, and Petar Veličković. Expander graph propagation. In The First Learning Graphs Conference, 2022.
Nima Dchmamy, Albert-Lászih Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. Advances in Nearal Information Processing Systems, 32, 2019.
Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, et al. Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3767-3776, 2021.
Gage DeZoort, Peter W Battaglia, Catherine Biscarat, and Jean-Roch Vlimant. Graph neural networks the large hadron collider. Noture Reviews Physics, pp. 1-23, 2023.
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. arXiv preprint orXiv:2206. 100e.11099 10991, 2022.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, 2023.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua. Bengio, and Xavier Bresson. Bench- marking graph neural networks. ::Xt::2003.0098, 2020.
Léonard Equer, Konstantin Rusch, and Siddhartha Mishra. Multi-scale message passing neural pdc solvers. arXiv preprinl (XXi:2302.03588 2023.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430. PMLR, 2020.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemmet: Universal directional graph neural networks for molecules. Advances in Neurol Information Processing Systems, 34:6790 6802, 2021.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks, International Conference on Learning Representations, 2022. URL /ttps://oppnreviee: net/forum?id= wIZUeM3TAU.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, pp. 2017.
PMLR,
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural networks, 3(5):551-5m) 560, 1990.
15

---

Published in Transactions on Machine Learning Research (02/2024)
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical informalion and modeling, 52(7))1757-1768, 2012.
Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. arXiv preprint arXiv:3301009306 2023.
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023. URL. https:://pperreiieeeeeeee net.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neurol Information Processing Systems, volume 34, pp. 21618 21629, 2021.
Gary Liu, Denise B. Catacutan, Khushi Rathod, Kyle Swanson, Wengong Jin, Jody C. Mohammed, Anush Chiappino- Saad A. Syed, Meghan Fragis, Kenneth Rachwalski, Jakob Magolan, Michael G. Surette, Brian K. Coombes, Tommi Jaakkola, Regina Barzilay, James J. Collins, and Jonathan M. Stokes. Deep learning-guided discovery of an antibiotic targeting acinetobacter baumannii. Na- lure Chemical Biology, May 2023. ISSN 1552-4469. doi: (00008//11589003--001 //doi. ..c....0 wttg//..10////111.1.. 1000////119--0----0-000011 01349-8.
URL https:
Andreas Loukas. What graph neural networks cannot learn: depth width. In International Conference Learning Representations, 2020. URL https://openrevioor http://wwweeeoooo////////a//pp/
Lászóó Lovász. Random walks on graphs. Combinalorics, Paul erdos is eighly, 2(1-46):4, 1993.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. International conference on machine learning, pp. 3363-4371 PMLR, 2019.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.0560 266.66666,, 2021.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young- Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 20447862)2207-21,, 2021.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein. Fake news detection on social media using geometric deep learning. arXiv preprint wxXi::1902.060% 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence, pp. 4602-4609. AAAI Press, 2019.
Euan Ong and Petar Veličković. Learnable commutative monoids for graph neural networks. arXie preprint ar arXiv:2212.0888 2022.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, 2022.
Noam Razin, Tom Verbin, and Nadav Cohen. On the ability of graph neural networks to model interactions between vertices. ar Xio preprint (rXim:2211.16433 2022.
16

---

Published in Transactions on Machine Learning Research (02/2024)
T. Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. Tn Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 18888 18909, PMLR, 2022.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXic preprint 0rXa::2303.1090 109933 2023a.
T Konstantin Rusch, Benjamin Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradicnt gating for deep multi-rate learning on graphs. In International Conference on Learning Representations, 2023b.
Ryoma Salo, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 80, 2008.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. arXiv preprint arXiv:2303.061 061477,, 2023.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Craig MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, al. deep learning approach antibiotic discovery. Cell, (80(4))688-))) 702, 2020.
Nina M Donghia,
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squa and bottlenecks on graphs via curvature. In International Conference on Leurning Representations, 2022.
Petar Veličković. Everything is connected: Graph neural networks. Current Opinion in Structural Biology- 79:102538, 2023.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Geordie Williamson. Is deep learning useful tool for the pure mathematician? arXiv preprint arXiv:2304. 120022602, 2023.
K. Xu, W. Hu, J. Leskovee, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Advunces in Neurul Information Processing Systems, volume 34, pp. 28877 28888, 2021.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
17

---

Published in Transactions on Machine Learning Research (02/2024)
A Outline of the appendix
We provide an overview of the appendix. Since in the appendix we report additional thcoretical results and considerations, we first point out to the most relevant content: the proofs of the main results, the extension of our discussion and analysis to node-level tasks, and the additional ablation studies.
Where to find proofs of the main results. We prove Theorem 3.2 Section C.1, we prove Theorem 4.3 in Section D.1, and finally we prove Theorem 4.4 in Section D.3.
Where to find the extension to node-level Gasks.Concerue thorough discussion the matter in Section E, where extend the definition of the over-squashing measure and generalize Theorem 3.2 and Theorem 4.4 to node-level predictions of the MPNN class in (2).
the case of node-level tasks, present
Where to find additional ablation studics. Section we have conducted further experiments on the profile of the over-squashing measure OSQ across different MPNN models as well as the training mean average error, to further validate our claims on over-squahhing hindering the expressive power of MPNNs.
Next, we summarize the contents of the Appendix more in detail below.
In order to be sell-consistent, in Section B we review important notions pertaining to the spectrum of the graph-Laplacian and known properties of random walks graphs, that will be then be used in our proofs.
In Scction C we prove the main theorem on the maximal mixing induced by MPNNs (Thoorem 3.2). In particular, we also derive additional results on the mixing generated at specific node, which will turn out useful when extending the characterization of the over-squashing measure OSQ for node-level tasks.
In Section D we prove the main results of Section 4, mainly Theorem 4.3 and Theorem 4.4. Further, we also derive an explicit (sharper) characterization of the depth required to induce enough mixing among nodes, in terms the pseudo-inverse of the graph-Laplacian. Finally, in Section D.4 we extend the results to the case of the unnormalized adjacency matrix and discuss relative over-squashing measures.
In Scction we generalize the over-squashing mcasure for node-level tasks, commenting on the differences between our approach and existing works (mainly (Topping et al., 2022; Black et al., 2023; Di Giovanni al., 2023)). In particular, we show that the same conclusions Theorem 4.4 hold for node-level predictions too.
Finally, in Section F we report additional details on our experimental setup and further ablation studies concerning the over-squashing measure OSQ.
B Summary of spectral properties on graphs
Basic notions of spectral theory graphs.
Throughout the appendix, we let A be the normalized graph Laplacian defined by - 1/2, It is known Chung & Graham (1997) that the graph Laplacian is symmetrically, positive semi-definite matrix whose spectral decomposition takes the form
A
AcoroT
(10)
where { is an orthonormal basis in R" and 0 = Ao < A1 < <... < An-1 recall that since we assume G to be connected, the zero cigenvalue has multiplicity one, i.c. Xj > We also note that we typically write Φe(u) for the value of de at E V, and that the kernel of is spanned by de with @b(v) = / //E the results would extend to the bipartite cas As usual when doing spectral analysis one too if graphs, we exclude
18

---

Published in Transactions on Machine Learning Research (02/2024)
the edge case of the bipartite graph to make sure that the largest eigenvalue of the graph Laplacian satisfies An-1 < 2 yet all results hold for the bipartite case too provided we take ||V < 1. Finally, we let A denote the pseudo-inverse of the graph Laplacian, which can be written as
(11)
and we emphasize that the sum starts from & = 1 since we need to ignore the kernel of A spanned by the orthonormal vector Φn-
Basic properties of Random Walks on graphs. A simple Random Walk (RW) on is a Markov chain supported on the nodes V with transition matrix defined by P(c,u) dz' While RW can be studied through different properties, the one we are interested in is the commute time т, which represents the expected number of steps for RW starting at v, to visit u and then come back to The commute time is dislance on the graph and caplures the diffusion properLies associated with the underlying topology. In fact, while nodes that are distant often have larger commute time, the latter is more expressive than the shortest- walk graph-distance, since it also accounts (for example) for the number of paths connecting two given nodes. Thanks to Lovász (1993), we can write down the commute time among two nodes using the spectral representation of the graph Laplacian in (10):
ΦE(V))
(x(4)) V
5(. u) E
(12)
de
C Proofs and additional details of Section 3
The goal of this section amounts to proving Theorem 3.2. To work towards this result, we first derive bounds on the Jacobian and Hessian of single node feature after m layers before the readout READ operation. We emphasize that our analysis below is novel, when compared to previous works of Black et al. (2023); Di Giovanni ct al. (2023), on many accounts. First, Black et al. (2023); Di Giovanni et al. (2023) do not consider higher (second) order derivatives, limiting their discussion to the case of first order derivatives, which are not suited to capture notions of mixing among features we will expand on this topic in Section E. Second, even for the case of first-order derivatives, our result below is more general since it holds for all MPNNs as in (2), which includes (i) message- finettionnnnniinssssooe &o that also depend on the input features (as for GatedGCN), and (ii) choices of message-passing matrices A that could be weighted and (or) asymmetrie. Third, the analysis in Black ct al. (2023); Di Giovanni et al. (2023) docs not account for the role of the readout map and hence fails to study the expressive power of graph-level prediction of MPNNs as measured by the mixing they generate among nodes.
Conventions and notations for the proofs. First, we recall that h! x, E Rd is the input feature at node v. Below, we write h (t)aa for the a-th entry of the feature (t) To simplify the notations, we rewrite the layer-update in (2) using coordinates as
h(),aa = =
(h(! (h(,))),a) 1sasd.
(13)
where 7: 1((--))a is the entry a of the pre-activated feature of node v at layer t. We also let (b(0r and 02, be the p-th derivative of (1,0)) (,,)),, and of (1,(0 respectively. To avoid cumbersome notations, we usually omit write the arguments of the dorivatives of the messago-functions s.. Similarly, we let. Viú (V24) be the d d Jacobian matrix of sb with respect to the first. (second) variable. Finally, given nodes i, V. 2 V introduce the following terms:
ah(m) (m)
8h,mm) (m)
V (m))
E Rddd
E (dx(dd)))
Ox,
0x,0x,
First, we derive an upper bound on the first-order derivatives of the node-features. This will provide useful to derive the more general second-order estimate of the MPNN-prediction. We highlight that the result.
19

---

Published in Transactions on Machine Learning Research (02/2024)
below extends the analysis in (Di Giovanni al., 2023) to MPNNs with arbitrary (i.e. non-linear) message functions v, such GatedGCN (Bresson & Laurent, 2017).
Theorem C.1. Given MPNNs in (2), let and wi(() be C³ functions and assume |o'| ca, ||52(0|| S w, || & w, | I c1, and V2 22 I c2. Let S E R be
S = " It didig A1) + +2A
Given nodes v, u E and m the number of layers, the following holds:
1 S (S"))
(14)
Proof. Recall that the dimension of the features is taken be d for any layer stt m. We procoed by
induction. If m and fix entries 1 S a, S d, then using the shorthand in (13), obtain
(V (V.h()) )ap o' a
D + Σ Wil En Aus (0, don 8g (1
= (diag((o' (hiag(o'(h!))) (h(")) 5 + wa) Aujoeu V + Avu V2
Therefore, we can bound the (spectral) norm of the Jacobian the left hand side by
|V < |ddiag(o' (h, (1020) + //W0I(( Ans + c2A
S (o w(e Aupoon + c2An))) C.
which proves the estimate on the Jacobian for the case of We now take the induction step, and follow the same argument above to write the node Jacobian after m layers as
(V (mb)))))) = o' o'(hlmm-20 1),a)
(
(V (V.h..-- 1))
o' (h 1),a Wr/m) Σ Auj Σ
br @rppbblmirr (V.h(m-))) (m)(mm)))) + 22 ( (mm- (m--1)) )p3)
diagg(o' (h (m 12 (m)) V Vichi (m
diagg( (h.m (m--1))) W(m)
Ans
Auy V Vicbim) m V.n.m-
Any Veglini V.n () as
Therefore, we can use the induction step bound the Jacobian as
IV S (m (S )o + (cow)" Σ (Sm-)) )ou (m 1ju
= (c # (A1) + c² ()m))))))) (S"")
which completes the proof for the first-order bounds.
Before we move the second-order estimates, we introduce some additional preliminary notations. Given nodes i, v, u, a matrix Ruxa which will always be chosen per (5) and integer e, we write
(f)
= (S*) )to (AS') )a. + (S² )au (AS'), Ne + E(s') (diag (A1) + A).g (S))
(15)
In particular, denote by P(()
(vw) E 2 the vector with entries (P(2) (( (()) i(vu)'
for 1 < i S n.
20

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem C.2. Given MPNNs in (2), let and eb(t) be C² functions and assume |o 1o"| S co || S w, || S w, |1 S e,, /2 S c2,
| (b S c! Let S E Ruxn be
I + c diag A1) + czA. S =
Given nodes u, E V, P (va) E E is as in (15) and m is the number of layers, then we derive
V h mm
k=0 JEV
(2)
Σ t=
(5
(mu) )
(16)
(m) Proof. First, note that V hu, h for indexing the columns which is consistent with typical way of labelling columns of the Kronecker product of matrices, as detailed below (note that indices here start from 1):
is matrix of dimension (dxdd))) We then the following ordering
phim)a == (Viunn (m))
(17)
0x.
(1((3-1)+>
As above, proceed by induction and start from the case 1:
(nago +
Σ wil
A + +ojud2, ,
a,((3-1)+7
(2 +
Σ W(Y) Σ As + 02
+ + (0),a) Σ wil Σ Aijdia((n,nn or. (hrr dir + 02, 02 (r,
+ +
Σ Wil (Ai (ir 82, )wv)
= (Q1)a.8. (Q2)a + (Qa)a,837
where Q1 is the term containing second derivatives of sb while Q2, Qa are the remaining expressions including second-order derivatives of the message functions vb. Using the same strategy as for the first-order estimates, can rewrite the first term Qı
(Qi)a.8.7 = (diag(o ((h (2 Do + w
Asydi (i(((1) + Arv v2((1))) ory
(2 w()) AryOeu VI(((1)
Aru (egs())))
a.
We now observe that given two matrices B, C E Rdxd and 1 s a,, a' ,, $ d, the entries of the Kronecker product B 8 C can be indexed as
B & () = BasCarn-
We now introduce the (d x d) sub-matrix of @ defined by
(B 2 C) = BasCor
(18)
Therefore, we can rewrite (Q1)a,8, as the entry (a, d(3 1) + 7) of the x (d x d) sub-matrix
(Qu) (B C),
(19)
21

---

Published in Transactions on Machine Learning Research (02/2024)
where
B = diag(o"(h,") (2 + -way Σ Aigrio Vi((() + Ai (erb(t)))
C = (0 + w Σ Acydiu Viel( + Aia V2rb(1).
Next, proceed to write (Q2),, in matricial form. Before we do that, we observe that the Hessian of the message functions (x,, + (6(1) (x,, xy) takes the form
V2 (6((()
V2 12 12251e)
ViSl00
(6(()
22 (01
21
where (br E Rdd((dxd) and is indexed as follows
V ( (dd((-1)+>> oa,
where a, b E (1,2}. Using these notations, we note that
Σ 01, (W a.d(B-1)4 1)+7
Therefore, we derive
(Q2)a,pn = (Q2)a
Σ Acy ( (12111)) d0
+ A ) (
(20)
A similar argument works for Q3:
(Qs)a.8, = (Qs) = Aru (diag(o ((i (()) V2 (1)(1))) (0.0(3-1)49
Asa (diagg of (L.
W()) V2 (a.(()))))))))
(21)
Therefore, we combine (19), (20), and (21) to write
V h 11 < QQil Q22l + Q3ll
I co (wos) + w(crdiag( (aaidii)gg).d,, + c2Asv)) (wosu + ((crdiag(AA)) c2Asu)
+ co (2) (diag A,, + Aso
(o (Aindiv + Aind..).
Finally, we can rely on (15) to re-arrange the equation above as
I ( ( < (wG)) + (2) (8:cAin + AinAio Σ 8jo (diag(AA) + A),;
(c..) + (2)
c, ((() i(ow))
which proves the bound for the second-order derivatives in the 1.
22

---

Published in Transactions on Machine Learning Research (02/2024)
We now assume that the claim holds for all layers t I 1, and compute the second order derivative after m layers:
V h (m))
o" (7,(m-1)))) a((h
a,4(3-144
x
(m)
(V. h
(uhh (m-1))
+ (m)
Σ Aid
a Pi " + 22 (mm.). (mm-1)) )ps)
x
(Vh
(mm ymm
(m
+ W(()
_Ap Σ Br (p (V.nnrr.Vnhh V..h(---)) )0 + 02 (m)))) (V.h)) ( (pm))
+ 0 (A(m-1)e (mm-))aa Σ
+
w/mm
Aij
Σ p1pe1 21 (m)) (Vuh. (1m )0ol V.,4a ()
3
P.g
+ t
(m (((((m-1).a) 1),a)
Σ
W(mm)
Ag
θ O2. (m), (V
(V.h. 1m 1- pol V..b, fm- 1/ )00
P.q
+ to((1(
(m 1),0 Σ
W(m)
Agg
θ p1 22 (m)) (V.hy (m aam-11 1) o0sl V c1! 1
+ +o'(h
1),0
Σ W(m)
Σ
Aig Σ
22. O2 (m)) (V.hy W..h//ml (m-
n (V (. 1
+ - 1),8)
Σ (2m))
(V2 h
(m-11) 1)
)11(0-1)+7
(m 1),0
Σ Welm
ΣAU
Aig Σ
Ô (i Wo mmm (m-1)) p.0(--1)
+ +o'(h(m-l) 1).0
Σ W(m)
ΣAn(
E2ppbbim) (V ( (m-1)) ) )
P
:= Ra,3 +
(Qab)a, + La.B.r
(1.2)
where is the term containing second derivatives of the non-linear map a, Qab is indexed according to the second derivatives of the message-functions vs, and finally Z is the term containing second-order derivatives of the features. For the term Ra,3,7 can argue in the m case and use the sub-matrix notation in (18) to rewrite it as the entry (a, d(3 - 1) + 77) of the d x (d d) sub-matrix
Ra (B 4(3-
(22)
where
B = diag(o"(i (m ())
(m) V,h 1m-1) 1)
+ (())
Air V Vi V.h. 1m- +
(2 (m (m-1)))).
C == ② V. 1m-1) + W(m)
Aig V
1m- V (..nfm-1)
Next we considor the terms (Qa Without loss of generality, we focus on (Qui), and use again the same argument in the m = case, to rewrite it as (Qu)a, = (Qu)a where
Qn = diag(o (h. (m (((m--1))) 1) Σ A (w(m)) vi v (m-1) 0 V.b. (m-1) (m-
(23)
where again we are indexing the matrix Virgi() by
(V )r.(d)))+ppp) 3 01
23

---

Published in Transactions on Machine Learning Research (02/2024)
The other Q-terms can be estimated similarly. Finally, rewrite Za,0,7 (2) d( where
Z diag(o'( (oog(oo(((mm))))) )) (2( V Pioh! mm/mmm)______
W(m) Σ Aty (V
v h mmm-1)
Veeblm) V by fm 1m) (24)
Therefore, we have rewritten the second-derivativee of the features in matricial form
V [m)
R +
Σ Qab Z.
0.bE(1.2)
To complete the proof, we now simply need to estimate the three terms and show they fit the recursion claimed for m. For the case of R. (22), we find
| & co (o(w]] V.h
(m-1) (MlcddiagAA)).llvc..o. (m-
+ 11
E Aijl
Vohy fm- ID)
(w|] V (m
w(e (1 V.
1)
|| 02
V. mm 1)
If we write (m R the matrix with entries (Dh (Dh(m-1)))
[V
(1 ||, then obtain
| S (WWWSDDD(m-)))) (SDh (SDD (SDh(m-)))
We can then plug the first-order estimates derived in Theorem C.1 and obtain
|||| I c. ww
((c,.))" smm = (cow) (mow))m((w((S)) (w(S"")) (S"))())))
(25)
Next, we move onto the Q-terms, and use again the first-order estimates in Theorem C.1 and the fact that we can bound the norm of V2 (5(m) by c(2) derive
Σ Qatil S ( (cow) 2m (diag(A1), (A1), 1m- "s 1Sm- /u +
Aig (Sm ) (Sm
(1.2
+ (2) 2m
((S :.. (AS (
)A (Sm-)) )iu (AS (AS )iv)
c (cow) 2m lplm-1/
(26)
Finally, if we let D E R be the vector with entries (DPhouss V2 h (m- then
Z I co w
[ 2 uu
11 + w ( (m- c Σ Ass V "
(27)
c. Cc.w(S77 D hru)..
Therefore, we can use the induction to derive
m
|z|| I cow Σ S it
(cow) 2m 2-m (-m (5m-1-k),
km
JEV
m
+ CoW
S (c(
(co)))
1
Σ
(cow) 2m
w(S 1 (S (Sm
k= JEV
m
(Gn (m )s)
m-1
m-
(mow)mm-ko w(s - (Sm + c22) Σ
(on) (mn))))
JEV
24

---

Published in Transactions on Machine Learning Research (02/2024)
By (25), we derive that the R-term corresponds to the & = 0 entry of the first sum, while (26) corresponds to the case L = m of the second sum, which completes the induction and hence our proof.
7
C.1 Proof of Theorem 3.2
We use the previous characterization to derive estimates on the Hessian of the graph-level function computed by MPNNs. We restate Thcorem 3.2 here for convenience.
Theorem 3.2. Consider an MPNN of depth
in (2), where and w0th) are C² functions and we denote the bounds on their derivatives and on the norm of the weights as above. Let S and Q₁ be defined as in (5) and (6), respectively. If the readoul is MAX, MEAN or SUM and A in (3) has unit norm, then the mixing mix (m) (v, u) induced by the MPNN over the features of nodes v, u satisfies
9 mix (mm (u, u) S Σ
(cow)2m-A-1 (w(S ddag(( stis"" * cc()
(7)
k=0
Proof. First, we recall that according to Definition 3.1, we are interested in bounding the quantity
0% (m) (X)
mix (m) u) max max X ISPRYS
Let us first consider the choice READ SUM, so that by (3) we get
8h (m))a
mix (m) (v, u) Ve
Σ 0a
dxudx
NEV
As before, we index the columns of the Hessian of h, as
8P pmpme
(V2
uu h (m))
) and hence obtain
Ou
mix amo (v, & Σ De
(m))
01 S
h (m))
(28)
iEV
sEV
since has unit norm. Note that the very same bound in (28) also holds if we replaced the SUM readout with either the MAX or the MEAN readoul. We can then rely on Theorem C.2 and find
m
mix (m)) (0, $
(cow)2 2m w(s (S
iEV
k=
JEV
( (mn))s
EV
0=
m
(cow)2n)
2m-1
diagg1 st)s
(on)
E=
(cow)am-k-)
(w(S diag(1 s sm)
me
m-1
(2)
S (m--
(va)
k=
For the second term we can the simply use the formula in (15) to rewrite in matricial form as claimed recall that Qs is defined in (6).
25

---

Published in Transactions on Machine Learning Research (02/2024)
D Proofs and additional details of Section 4
Throughout this Section, for simplicity, we assume (nxx/cl/l:c4 to be smaller equal than one this is satisfied by the vast majority of commonly used non-linear activations, and extending the results below to arbitrary C is straightforward.
D.1 Proof of Theorem 4.3
We begin by proving lower bounds on the operator norm of the weights, when the depth is the minimal one required to induce any non-zero mixing among nodes v, u. For convenience, we restate Theorem 4.3 here as well.
Theorem 4.3. Let A = Asym: r r= dc(v, u), m = [r/2], and q be the number of paths of length r between v and For MPNN satisfying Theorem 3.2 with capacity (m [r/2], w), we find OSQu, (m, w) (cow)"
1. In particular, if the MPNN generules mixing mixyc (v, u), then
dyni C2
mixxa (u, u
Proof. Without loss of generality, we assume that r is even, so that by our assumptions, we can simply take m = r/22. According to Theorem 3.2, we know that the maximal mixing induced by an MPNN of depth m over the features associated with nodes v, u is bounded from above as
m
mix (m) (v, u)
2m 2m-
(wS" - diag( "iaa(("")) (*11) 1 -c(2) Q12
where we have replaced e, with one, as per our assumption. Since m r/2, where is the distance among nodes U, u, then the only non-zero contribution for the first term is obtained for k 0 otherwise would find path of length 2(m k) connecting v and hence violating the assumptions and is equal to w2m (S 2my Jou, and note that 2m = Concerning the terms Q instead, the longest-walk contribution for S
nodes v, u is 2m - (when k = 0), meaning that Q = 0 for all 0 < k mm 1 if m = 2r. Accordingly, we
can reduce the bound above to:
mix (m) (v, u) S w ( = 2m (c22A22m 96
vu
where the last equality we have again usod that 2m = r, so when expanding the power of S only the highest-order term in the variiable gives non-zero contributions. characterization of over-squashing in Definition 4.2, then
replace now 2m and use the
OSQ (m 5. w) 2 (cow) -r (A")eu
Therefore, if the MPNN generates mixing mix (m) (v, u) among the features of and u, then (8) is satisfied, meaning that the operator norm of the weights must be larger than
1 mix (m) (v, u)
W 2
C2
The term A" general can be estimated sharply depending on the knowledge we have of the underlying graph. To get universal albeit potentially looser bound it suffices note that along each path connecting v and u, the product of the entries of A can be bounded from above by (dmin)" which completes the proof. J
We highlight that if A.. = D i.e. the aggregation over the neighbours consists of mean-operation apply the very same proof above and derive
for the GraphSAGE architecture then
Corollary D.I. The same lower bound for in Theorem 4.3, holds when A A-
26

---

Published in Transactions on Machine Learning Research (02/2024)
D.2 Spectral bounds
Next, we study the case of fixed, bounded operator norm of the weights, but variable depth, since we are interested in showing that over-squashing hinders the expressive power of MPNNs for tasks requiring high-miizing of fealures associaled with nodes at high commauee lime. We first. provide characterization of the maximal mixing (and hence of the over-squashing measure) in terms of the graph-Laplacian and its pscudo-inverse.
Convention. In the proofs below we usually deal with matrices with nonnegative entries. Accordingly, we introduce the following convention: we write that A $ B Acj S By for all entries < i, S n.
Theorem D.2. Let = V
dmnax and set A = Auym or Arw- Consider an MPNN as in Thm. 3.2 with Then the marimal mixing of nodes v, a generated
dain
depth m, max (w, w/w + 017 +22 1. Define Z: I C2 by such MPNN after m layers
mix Lon (U, u)
$ nM m
Vd.du
+
Z22 ( Z 2mh
1
(I 2) - A )
Ve
2/E|
C2
(2) +
[[[+)")I-=)(0 Z 2mm (I Z) -)-
C2
where = =====: if A Asm or 4,5 = 2 if A.w.
Proof. We first focus on the symmetrically normalized case A Asym = -D-1/22D-1/ which we recall that we can rewrite as Asym = I- A, where the (normalized) graph Laplacian (10). Since w S 1 and the pesssae-ppassing matrix is symmetric, by Theorem 3.2, we can bound the maximal mixing of an MPNN as in the statement by
m- 1
m k 1) Q))
mix (m)) (u, u) 26
We focus on the first sum. Since A = (D 1/2 where D- is row-stochastic matrix, we see that
Sij S deg + c1 + c2
meaning that write $ < al + c2A, where w/w + ein using the convention introduced above. Accordingly, we can estimate the row-sum of the powers of S by using (A*1), S
4 (5*1), S Σ OF) p=
(K
(( =(a + 02)* s 7
Σ a
p=0
where the last inequality simply follows from the assumptions. Therefore, find
Σ S "idggS
1$*1)
S
2 3(m k))
you
Σ
2h S
yun-
(29)
n
k=1
By the assumptions on the regularity of the message-fimctions, we can estimate S from above by S <
al + A (a c Z, and derive
m-1
Σ
S m
diag (
1=
S
Σ k=
k=
27

---

Published in Transactions on Machine Learning Research (02/2024)
From the spectral decomposition of the graph-Laplacian in (10) and the properties that do and @o(x) v d we find
Z
2k
Σ
( (e(w))=(u)
k=
6=
Vd
(1 c2dr)2(m+t))
- c220)² 1)
m
2
v d.
c21e)3(1 - -(1 -1-
-11-22))) )
)or())o(uu)
m 2/E
(2- (2- 02de)o2de
Since C2 & 1 and G is not bipartite, we derive that (I+ Z) = =II Co A is invertible and hence that the
following decompasition holds:
(I+ -+= Σ 2 c2
0100.
E20
Therefore, can rely the spectral-dcoompositonn of the pscudo-inverse of the graph-Laplacian in (11) to get
Σ S mm- diag (S) S m
do
+
1 (z-2(I 02
2m (I (1
Z) -)- AAi vn))
(30)
2
It now remains to bound the term (( 2k=o (Qx) estimate ($*1), S 7, that we derived above, we obtain
First, we note that by the symmetry of A and the
c(2) m-
m-1
Quker S 26
Σ k=0
(AZ2 2(m (mm- x-1)) + 7Z22mm ---))
K=
Then we can use the identity A -- A, to find
(22) m-
Qu om S (2)
((1 (m=
(31)
k=
By relying on the spectral decomposition as above, we finally get
m2
Vd.du
(2)
Qk)ou 5 $2c(3) m
(1 + +7)
2
0
Σ (1+7- 2x) 1- 2m 2m
20(gg
(2 - c22 )elu)6l(u)
ESO
As done previously, we can rewrite the last terms via (I + Z)
Qu) 3 220(0)
m
(1 7)
2
0
(2)
(1+ + A) Z 2m (I + Z) -)-''))
(32)
C2
We can then combine (30) and (32) and derive the bound we claimed, when A Asym- For the case A A. A it suffices to notice that S < a'I + czA, where a' w/w + Ci and that
(1 ); ΣΣ
(a' ) DD-AA))
S
dmax (a' + 02)* 5 dmin
28

---

Published in Transactions on Machine Learning Research (02/2024)
where have used that by assumption a' +2 S 1. Similarly, get (S"-AATT(( the Qe-term can be bounded by
(mm-)) S 2 Finally,
c(2)
Qs)eu (c
4 Asym Z 2 k-1))-1)---
K=
k=
and we can follow the previous steps in the symmetric case to complete the proof.
Corollary D.3. Under the assumptions of Theorem D.2, if the message functions in (2) are lineor as for GCN, SAGE, or GIN then the mazimal miring induced by such an MPNN of m layers is
dmax dman
d,du 2
1 (
mix (m)) (v. w) S MG
-2 z (I - +
Proof. This follows from Theorem D.2 simply by noticing that if the message-funncton vf in (2) is linear, then the upper bound for the norm of the Hessian can be taken to be zero, i.c. c( =
D.3 Proof of Theorem 4.4
We now expand the previous results to derive the minimal number of layers required induce mixing in the of bounded weights, showing that the depth may need to grow with the commute time of nodes. We recall that y is v dmax/ /min while 0= λo < A1 .... S Ax-1 the eigenvalues of the symmetrically normalized graph Laplacian (10). We restate Theorem 4.4 below.
Theorem 4.4. Consider MPNN satisfying Theorem 3.2, with
S 1, and A Asym- If OfQu,aam w) (mixyo (v, u)) & 1, iee. the MPNN generates miring mix (u, u) among the features associated with nodes v, u, then the number of layers mn satisfies
T(0,u)
E
mix (V, u)
1 117 12--11-1
+ cd2) ))
m 2
+
(9)
402
7/
02
where de(u, u), == 20 (1 + ? and -222 maxo<tsn-1
=axo |1
c2del <1
Proof. From now on we let be the shortest-walk distance between v and If m < r/2, then we incur the under-reaching issue and hence we get zero mixing among the features associated with nodes u u. Accordingly, we can choose m 2 r/2. We need to provide an estimate on the maximal mixing induced by an MPNN as the statement. We focus on the bound in Theorem 3.2, and recall that the first sum can be bounded as in (29) by
m-1
m
m
Σ 5mh diag(S*1)ss**
S
Σ S
2k
where I- A. We can then bound the geometric sum by accounting for the odd powers too. Therefore, get
2m
2k
ZZ
vu
ou
k=
k=D
k=0 E20
As for the proof of Theorem D.2, separate the contribution of the zero-eigenvalue and that of the positive ones, we find that.
Vd.da
(1 2m
Σ IZ Dou 522m
Se (v()b((())
2
Vd
(1 c2de) 2m+1
= -m2m + 1)
+
de (e())(((u) - -
(e(v))e(u).
(33)
2
C2de
Ozde
E>0
E>0
29

---

Published in Transactions on Machine Learning Research (02/2024)
Thanks to the characterization of commute-tine time provided in (12), we derive
Σ 1 ES0 o2fe
T(U, u)
1 Σ
du (B(0))
dr oW
dodu +
+
Ec2/E|
202 E20
dr
r(U, u)
1
dp
du
S 4c2
dodux + 202 (dd
du
+
V
du
[E]
(34)
where in the last inequality we have used that Eiso 23 = 1 ---((()) since {Ør) constitute an orthonormal
basis, with do(x) = /d./2/E1 and that de 2 A1, for all l <> 0. Next, we estimate the second sum in (33), and we note that \ in the statement is either A1 or An-1:
2m
- c22-12m
)e(v))b(u) -
Σ
(de(w))e(u))
C2de
0>
8>3
1-o2
022*|emm
Σ (0)(v) + (z))
20221
E>1
c22011"
de
du
(2
(35)
20221
2
2
where in the last inequality we have used that [1 - c2 < 1 and that m 2 r/2 (otherwise we would have zero-mixing due to under-reaching). Therefore, by combining (34) and (35), we derive that the first sum on the right hand side of (7) can be bounded from above by
Σ S k diag(S 1))m==+))))))) s <>((2m 1)
1
T(U, u)
V do
2/El
4cg E
k=
(11
7 (1:
/dd
du
202i1
(V
dh
+ V
dp
|E]
11 c2
do
du
+ 7
(2
(36)
202d1
2
2/E
Next, we continue by estimating the second sum entering the right hand side of (7). We recall that by (31), we have
Qu: )ou s 20
A)) = 26
((1+))I
A)
0=
k=
mu
K=
2(m 1)
Σ 2c
((1+7)I -))*)
0=
2(m-1) 1)
= 2c
Σ
220
We then proceed as above, and separate the contributions associated with the kernel of the Laplacian, to find
m-1
Σ (x)xs 527 52:(11 (11+ vd
2/E
+ + 7)
(1 - (1 (1--ee2)))
(37)
C2)
27
(1 (1 - c2 1100-)))-000000660)66
(38)
C2 10
30

---

Published in Transactions on Machine Learning Research (02/2024)
For the term in (37), can apply the same estimate as for the case of (33). Similarly, we can bound (38) by
2y Σ (1- (1 02)e)) 2m (oo)))))))))
27
(i(()) +o(())
- 7
2(2
du
du
C2 200
2
C2
2
2
E>0
Therefore, we can finally bound the Qx-terms in (7) by
vdndu
-(1+7) 7) T(U,u) u)
Qu) S 220 (1 + 72 1)
V Voodu
2/E1
402 EE|
+ 7
+
dg
du
dn
dy
[E]
1 1+7 ?
de
du
2)
[1 02201"
2
2
(2)
dg
du
2
(39)
22
2
2
We can the combine (36) and (39), to find that the maximal mixing induced by an MPNN of m layers as in the statement of Theorem 4.4, is
r(C,
u)
mix (m) (1, u) S TV dodu V/G
/ddd
1
E
E
4c2
[E|
1
dy
du
dd
+ 7 202
+
V
dy
dp
E
+ 7
1
11 -
022"11
(2
d.
du
202
2/E|
2
7c(2)
du
2
(40)
C2
2/E|
2
where ;== 1 (1 + +7) and have removed the term -2 /dddd//22 S 0. Moreover, since A1 <I 1 unless G is the complete graph (and if that was the case, then we could take the distance r below to
simply be equal to 1) and < 1, we find
dodu 2/El
(1-
1 (1+ |1 c21-1-11 (V
(/ du
dr
+ +Vn))
s O.
02d1
d
Accordingly, we can simplify (40) as
mix (m) (v, S TV d,dg
[E
m
11
T( u)
4c² E 11
+
20
7/14
(V
du
de
V d
du
1 + (2)
7/4
11
C²
C2
We can now rearrange the terms and obtain
T(u u)
E
mix
(v,
1
dr
1
_ 2 c(2)
m3 2
402
+
7/4
202d1
V
dy
+
V
d,
c2A1
11
12
C2 1
(v, u)
E
mixyc (v,
1
1
(22) 1
+
(27)
C2l
12
402
v dj
7/14
202d1
c2d1
C2 p
uu,
E
mixyo (v, (v,
7
+
||
x
+
2
402
Vd
7/14
A1
which completes the proof.
31

---

Published in Transactions on Machine Learning Research (02/2024)
We note that the case of A Arw follows easily since adapt the previous argument exactly in the proof of Theorem D.2, which lead to the same bounds once we replace 7 with 7 dmax/Omin
First, we note that the bounds again simplify further and become sharper if the message-functins &b in (2)
are linear.
Corollary D.4. If the assumptions of Theorem 4.4 are salisfied, and the message-fuunclions th are linear as for GCN, GIN, GraphSAGE then
u(U,u)
E
mixya (U,
(1+11-0227111
2
402
7
c211
In fact, the graph is regular with degree d, then
T(U, u)
[
c2A1 (1-0111111))
m
mixya (v, u)
402
D.4 The case of the unnormalized adjacency matrix
In this Section extend the analysis on the depth required induce mixing, the case of the unnormalized adjacency matrix A. When A A, the aggregation in (2) is simply sum over the neighbours, case that covers the classical GIN-architecturee In this way, the messages are no longer scaled down by the degree of (either) the endpoints of the edge, which means that, in principle, the whole GNN architecture is more sensitive but independent of where we are in the graph. First, we generalize Theorem 4.4 to this setting, We note that the same conclusions hold, provided that the maximal operator norm of the weights is smaller than the maximal degree dmaxi this not surprising, since it accounts for the lack of the normalization of the messages.
Corollary D.5. Consider an MPNN as in (2) with A = A. If (wdmax) + c1 + C2 I 1 and wdmax S 1, then the minimal depth m satisfies the same lower bound Theorem 4-4 with y = 1.
Proof. First, we note that in this case
Sig S by + cidmaxdiy A2 dmax (adij c2 (esyym))s)
where a = wu/(wdmax) + er. In particular, we find that
1$*1) S Σ
k p PCg(AP)); S (dmax) (a
p=0
Accordingly, we can bound the first sum in (7) as
2(m-k)
Σ w 2m (dmax) - c2) (dlnax) 2(m- (al (22+cAA Asym k=
2 k))
k=0
where we have used the assumptions a a + 02 < 1, and wdmax 1, and the definition Z A in Theorem D.2. Since this term is the same entering the argument in the proof of Thcorem 4.4 (once set y 1) can proceed in the same way to estimate it. A similar argument works for the sum of the Q₁ terms, which, thanks to our assumptions, can still be bounded as in (31) with 1 so that we can finally simply copy the proof of Theorem 4.4.
A relative measurement for OSQ. To account for the fact that different message- pasgggg matrices A may lead to inherently quite distinct scales (think of the case where the aggregation is mean vs when it is a sum), one could modify the over-squashing characterization in Definition 4.2 as follows:
32

---

Published in Transactions on Machine Learning Research (02/2024)
Definition D.6. Given an MPNN with capacity (m,w), w), define the relative over-squashing of nodes U, U.
-1
Σ m-- k=U w2m-k-1 ((S Tdiig diag T mm cc(2) jEX Ex w2m-k-1 k-1
smm
rll OSQ (m,
vu
(0002((((') ((s" Tdiag (1 (1 mm + cl Qh
The normalization proposed here is similar to the idea of relative score introduced in (Xu et al., 2018). This way, larger scale induced by certain choice of the message- message-passing passing matrix A, is naturally accounted for by the relative measurement. In particular, the relative over-squashing is now quantifying the maximal mixing among a certain pair of nodes v, u compared to the maximal mixing that the same MPNN over the same graph can generate among any pair of nodes. In our theoretical development in Section 4 we have decided to rely on the absolute measurement since our analysis depends on the derivation of the maximal mixing induced by an MPNN (i.e. upper bounds) which translate into necessary criteria for an MPNN to generate a given level of mixing. In principle, to deal with relative measurements, one would also need some form of lower bound on the maximal mixing and hence address also whether the conditions provided are indeed sufficient. We rescrve thorough investigation of this angle to future work.
E The case of node-level tasks
In this Section we discuss how one can extend our analysis to node-level tasks and further comment on the novelty of approach compared to existing results in (Black et al., 2023; Di Giovanni et al., 2023). First, we emphasize that the analysis on the Jacobian of node features carried over in Black et al. (2023); Di Giovanni et al. (2023) cannot be extended to graph-level functions and that in fact, our notion of mixing is needed to assess how two different node-features are communicating when the target is a graph-level function.
From now on, let us consider the case where the function we need to learn Y Raxd + Raxd and as usual we assume to be equivariant. with respect to permutations of the nodes. natural attempt to connect the results in Black et al. (2023); Di Giovanni et al. (2023) and the expressivity of the MPNNs in the spirit of our Section - could be to characterize the first-order interactions (or mixing of order of the features associaled with nodes v, with respect to the underlying node-level task Y as
((Y()))
mix y (v, = max max X 15a,3dd dr
where (Y())) Rd is the value of the node-level map at v. Accordingly, one can then use Theorem C.1 to derive upper bounds on the maximal first-order interactions that MPNNs (2) can induce among nodes. As consequence of this approach, we would still find that MPNNs struggle to learn functions with large mix?" (1) (v, u) if nodes v, u have large commute time. In particular, light Theorem C.1, we can extend the measure of over-squashing tacitly assume that the non-linear activation satisfies |o'| 1, although it is straightforward to extend the formulation to the general case.
the case of first-order interactions for node-level tasks. Once again, below we
Definition E.I. Given MPNN in (2) with capacity (m, w), we define the first-order over-squashing of t,a as
OSQ (m, w) == (mixy' (v. u) )
As for the case of graph-level lasks, we can then study proxy (lower bound) for the node-level over-squashing of order 1 by:
Definition E.2. Given on MPNN as in (2) with capacity (m, w) and S defined in (5), we approzimate the first-order over-squashing of as
OSQua(m, (m, w) = ("
33

---

Published in Transactions on Machine Learning Research (02/2024)
It follows then from Theorem C.1, that necessary condition for an MPNN to learn node-level function Y with first-order mixing mixy (v, u)
1 OSQ n.a (m,.)) < (mixy' (u, (v. u)) )
It is straightforward to argue as in Theorem 4.4 and (Black et al., 2023) for example, to derive that nodes at higher effective resistance will incur higher first-order overssquashing. Accordingly:
An MPNN as in (2) with bounded cupacily, cannol learn node-level functions with high, first-order inteructions among nodes v, u with high effective resistance.
Building a hicrarchy of measures. Although first-order derivatives might be enough capture form of over-squashing for node-level lasks, even in this scenario can study the pairwise mixing induced al specific node, and hence consider the curvature (or Hessian) of the node-level function Y which is more expressive than the first-order Jacobian. Accordingly, for a node-level function Y Raxd + Rnxd we say that it has second-order interactions (or mixing of order 2) mixy (i, v, of the features associated with nodes e, u at given node when
02 ((()))
mixy (i, = max X
(2)
We can then restate Theorem C.2 as follows we let (mm) be the node-level function computed by an MPNN after m layers.
Corollary E.3. Given MPNNs as in (2), let and v((t) be C² functions and assume lo |o"| S ca. |(200 S w, [| & w, [[ I ci, (Vzb(() S c2, || I cl Let S E Rxxa be defined as in (5). Given nodes u, U. V, if pP(()
(en) E R" is as in (15) and m is the number of layers, then the marimal mixing of order of the MPNN at node satisfies
mix (2) yim) u)) S
(cow)2m-k- w(S ) (Sm
k=0 jEV
+ (2)
( (ou)) (vu)
(41)
t=0
Similarly to Definition 4.2, we can use the maximal mixing (at the node-level) to characterize the over-squashing of order two at a specific node as follows: as usual, for simplicity we assume that Ca 1.
Definition E.4. Given an MPNN as in (2) with capacity (m, w) and defined in (5), we approzimate the sccond-order over-squashing of v, u at node as
(2) OSQ, (m, (m,w) w) =
2m ((
k= JEV
+ (2)
wm+ wm
8=0
It then straightforward to extend our theoretical analysis to derive how OSQ prevents MPNNs from learning node-level functions with high-mixing at some specific node of features associated with nodes v, u large commute time. To support our claim, consider the setting in Theorem 4.4 and hence let A Asym D 1-2 1/1121//// Under the same assumptions of Theorem 4.4, find
S )) S 1.
We then simply copy the proof of Theorem 4.4 once we set 7 and extend its conclusions follows:
34

---

Published in Transactions on Machine Learning Research (02/2024)
Corollary E.5. Consider an MPNN in (2) and let the assumptions of Theorem 4.4 hold. If the MPNN (2) (i, v, u) node i, with respect to the features associated with nodes v, u,
generates second-order miring mixy then the number of layers m satisfy:
m 2 T(U u)
E
mo (v,u)
1 -222-11 +
c(22) 20)
+
402
1
A1
where 1 + 4c(2)
Accordingly, in this Section we have adapted results from graph-level tasks to node-level tasks and proved that:
The message of Section E. An MPNN of bounded capacity (m,, connot learn node-level functions that, at some node i, induce high (first order or second order) mixing of features associated with nodes v, u whose commute time is large.
F
Additional details of experiments and further ablations
F.1 Computing the commute time
The commute time r between two nodes u, v E on a graph can be efficiently computed via the effective resistance R, with 7(u, v) 2/E[R(u, v). In order to compute the effective resistance R, we introduce the (non-normalized) Laplacian matrix L D A, where D the degree matrix. The effective resistance then be computed by
R(u, v) D un + Tew 2T mE:
where I the the Moore-Penrose inverse of
L+
1 Vixi V
with 1 Mixiii E RIVIXIVI being matrix with all entries set to one.
F.2 On the training error
In this section, report the training error of the MPNNs trained in section 5. Fig. 5 shows the training MAE corresponding to the experiment in section 5.1, while Fig. 6 shows the training MAE corresponding to section 5.2. We can see that in both cases, the training MAE exhibits the same qualitative behavior as the reported test MAE in the main paper, i..., the training MAE increases for increasing levels of commute time t, while it decreases for increasing number of MPNN layers, which further validates our claim that over-squashing hinders the expressive power of MPNNs.
F.3 On the over-squashing measure
In this section, we examine how the over-squashing measure OSQ (as of Definition 4.2) depends the commute time t well as on the depth of the underlying MPNN. To this end, we follow the experimental setup of section 5.1 and 5.2, but instead of training the models and presenting their performance in terms of the test MAE, we compute OSQ of the underlying models. We can in Fig. 7 that OSQ increases for increasing values of the a-quantile of the r-distribution for all MPNNs considered here. Morcover, we can see in Fig. 8 that ÖSQ decreases for increasing number of layers for all considered models.
35

---

Published in Transactions on Machine Learning Research (02/2024)
0.050
10-9
Train MAE
Train MAE
0.010
10-3
GCN GIN
GCN
GIN
GraphSAGE GatedGGNN
GraphSAGE
GatedGCN
10
0.001
0.8
1.0
Commute time o-quantile
Number of layers on
Figure 5: Train MAE of GCN, GIN, GraphSAGE, and GatedGCN on synthetic ZINC, where the com- mute time of the underlying mixing is varied, while the MPNN architecture fixed (e.g., depth, number of parameters), i.c., mixing according to increasing values of the a-quantile of the r-distribution over the ZINC graphs
Figure 6: Train MAE GCN, GIN, GraphSAGE, and GatedGCN on synthetic ZINC, where the com-- mute time fixed be high (i.c., at the level of the q.S-tuantlle), while only the depth of the under- lying MPNN is varied between 5 and 32 (all other architectural components are fixed).
GCN
1
10
GIN
GraphSAGE
10
10
GatedGCN
05Q
Q5Q
10
GCN
10
GIN
10-7
10
GraphSAGE
GatedGGN
0.0
0.2
10.4
0.6
0.5
1.0
32
Commute time quantile
Number of layers
Figure 7: OSQ (Definition 4.2) of GCN, GIN, Graph- SAGE, and GatedGCN on synthetic ZINC, where the commute time of the underlying mixing is varied, while the MPNN architecture fixed (c.g., depth, number of parameters), ie., mixing according to in- creasing values of the a-quantile of the 7-distribution over the ZINC graphs.
Figure 8: OSQ (Definition 4.2) of GCN, GIN, Graph- SAGE, and GatedGCN on synthetic ZINC, where the commute time is fixed to be high (i.e., at the level of the 0.8-quantilc), while only the depth of the underlying MPNN varied between and (all other architectural components are fixed).
36


Reviews:
[{"review_id": "Wyi6eHOxZQ", "reviewer": "Reviewer_7rF7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- novelty \n- scientific rigour\n- theoretical results\nWeaknesses\n- experimental results are quite limited\n- paper is very hard to read and understand", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Authors provide a rigorous analysis to determine which function classes of node features can be learned by an Message Passing Neural Networks of a given capacity using a the level of pairwise interactions between nodes that Message Passing Neural Networks allow for.\nTheoretical and practical results supports the proposed approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think that the paper should be improved by\n- increase the experimental results\n- simplify the paper by moving the more technical parts in the appendix, better explain in plain english the results\n- add some toy examples to provide more insights into the theoretical results", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "F0ti0GhNAF", "reviewer": "Reviewer_gw29", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- an interesting topic for which getting theoretical results is not easy.\n- the paper is well-written and easy to follow\n\nWeakness:\n- it is not clear that the bounds derived are indeed tight. In this case, the theoretical results will not explain the expressive power of MPNN.\n- the experimental results are weak (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies over-squashing for message-passing GNNs (MPNN). The authors introduce a notion of mixing for a function of node features, which is an upper bound of the Hessian. In Section 3, they derive an upper bound for the mixing of MPNN as a function of the bounds on the weights, gradients of the aggregating functions, and activation functions. Then, Section 4 defines a quantitative notion of over-squashing (OSQ) as the inverse of the mixing defined above. A direct consequence of their first result is that in order to be able to approximate a function with a given mixing, the OSQ of the MPNN needs to be low enough. The authors derive bounds on the weight norm (Theorem 4.3) and the minimal number of layers (Theorem 4.4) for this condition to be valid. These theoretical results are validated through experiments on synthetic signals on real graphs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It looks like the bounds can be very loose. For example, in Theorem 4.4, deriving a lower bound on the number of layers, it is not clear that this bound is indeed positive. For a GCN, we have a term like $\\frac{A}{\\gamma} -(\\gamma+B)$, so if $\\gamma$ is large, this will be negative.\nThe experiments do not help and, indeed, are in favor of claiming that these bounds are very loose. The mixing is of order one, and the OSQ given in Appendix F.3. varies between $10^{-19}$ and $10^{-3}$, so very far from the targeted mixing. Clearly, it would be much more convincing to have experiments showing the tightness of the bounds. This is not the case here.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fHGl2JI1ak", "reviewer": "Reviewer_AJhv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\na) They have a reasonable justification for the way they define mixing and as a result over-squashing, as required by the underlying task, which is absent from prior works.\n\nb) Their measure seemingly captures different phenomena of under-reaching, redundancy of messages that were observed in prior works such as Barceló et al. 2019 and Chen et al.2022.\n\nWeaknesses:\n\nA lot of the main message of the paper is not entirely new/unknown in relation to the prior works such as Di Giovanni et al.2023, Black et al.2023 etc, especially in relation with the commute times of the graph.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: \n\na) The authors re-define the over-squashing phenomena previous defined in Topping et al. 2022, Di Giovanni et al. 2023, in terms of the \"mixing\" induced by the MPNN. The ``mixing\" here is defined, assuming the output/labeling function is a smooth function of the input, node features. Precisely it defined as the (maximum) magnitude of the mixed derivatives (w.r.t two different nodes) of this labeling function. Once this definition is made then over-squashing between two nodes is defined as the inverse of the mixing between the nodes. More importantly, the provide an estimate of this that depends on the norms of the (learnable) weight matrices and crucially also the graph topology and parameters such as the commute time between two nodes, max/min degrees, the eigenvalues of the Laplacian etc.\n\nb)Based on the above estimates, they provide some necessary conditions on the the depth (with fixed weight) and the norm (with fixed depth) in order to achieve a certain mixing value.\n\nc)They also are able to explain certain phenomena observed in other prior-works such as under-reaching, in terms of mixing.\n\nd) They have controlled experiments explaining the effects and show that these experiments reflect the theoretically predicted patterns.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor:\n\na)Can the formulae for over-squashing, mixing etc be left intact with their respective norms instead of the bounds. I think it might help to see the general dependence on norms easily.\n\nb) Some notations such as double-brackets and the MAX operator should be explained for better readability and why is the function.\n\nc) Corollary 4.5 seems quite informal as stated here. How high is \"high\" and how large is \"large\"?\n\nMajor:\n\na) Di Giovanni et al. 2023 show that increasing depth may not prevent over-squashing (according to their definition) and leads to vanishing gradients. I think this is important to address here in this paper, which uses a different definition of over-squashing. But then can one increase depth indefinitely without any issues? \n\nb) Does mixing/over-squashing dependence on the initial node-features, any dependence on $X$, or the dimension of the node features? I think this has to be clarified slightly better.\n\nc)The requirement of twice-differentiable output function (w.r.t to the node features) maybe quite strong in general. It would be great if the authors could have some discussion of how to overcome and estimate the mixing outside this setting?", "broader_impact_concerns": "It is predominantly a theoretical paper. There are no ethical implications as far as I can see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The final feeling of reviewers was mixed, although suggestion to accept the paper were in majority. The main perplexities were concerning the practical application of the theory, as well as  the strength of the experimental assessment proposed by the paper. The decision to accept it is mainly based on the recognition of the theoretical nature of the paper. Although direct practical applications of the theory are far from been clear, the proposed theory constitutes a step towards a better understanding of learning in this type of networks. As such, the work proposed in the paper deserves to be presented to the scientific community as a potential new starting point from where to develop more advanced theories, as well as guidelines for designing more effective architectural features of graph neural network models.
Decision: Accept (poster)