On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology

Francesco Di GiovanniLorenzo GiustiFederico BarberoGiulia LuisePietro LioMichael M. Bronstein

article2023ICML187 citations

Proves theoretically that over-squashing in message passing neural networks is fundamentally driven by graph topology and high commute time rather than network depth, providing a unified framework that justifies both spatial and spectral graph rewiring solutions.

Listen

Message Passing Neural Networks (MPNNs) are widely used for machine learning on graph-structured data, operating by passing information between adjacent nodes. However, they suffer from "over-squashing," an information bottleneck where node representations become insensitive to data located at distant nodes due to the exponential expansion of neighborhood paths. While practitioners have proposed various graph-rewiring techniques to alleviate this issue, the theoretical foundation explaining why over-squashing occurs and how model architectural choices interact with graph structure has remained incomplete.

The article establishes a rigorous mathematical framework to evaluate the precise impacts of network width (hidden layer dimension), network depth (number of layers), and graph topology on over-squashing. Through theoretical sensitivity bounds and empirical benchmarks, the authors demonstrate why existing rewiring heuristics work and identify the fundamental limitations of architectural adjustments.

To conduct this evaluation, the authors performed sensitivity analyses on the Jacobian matrices of node features across network layers. They examined two distinct depth regimes: one where depth matches the graph diameter and another where depth is arbitrarily large. Furthermore, they connected message propagation bounds to random walk metrics on graphs, including access time, commute time, and effective resistance. These theoretical findings were validated through controlled "graph transfer" tasks on synthetic graph topologies (CrossedRing, Ring, and CliquePath) using standard architectures (such as GCN, GIN, SAGE, and GAT) and signal propagation experiments on benchmark datasets including PROTEINS, NCI1, PTC, and ENZYMES.

The findings establish that graph topology is the primary driver of over-squashing, which occurs predominantly between node pairs characterized by high commute time or high effective resistance. Increasing network width can mathematically mitigate over-squashing, but doing so increases sensitivity globally, which risks severe overfitting and degraded generalization. In contrast, increasing network depth cannot resolve the issue: when depth is comparable to the distance between nodes, over-squashing still occurs across distant paths, and when depth is increased further to capture long-range interactions, the model transitions directly into the vanishing gradient problem. Crucially, the authors prove that graph rewiring—both spatial additions of shortcut edges and spectral modifications that expand the Cheeger constant—provably reduces commute time and effective resistance, offering a unified explanation for why rewiring succeeds where purely architectural changes fail.

These results show that organizations and practitioners deploying MPNNs cannot solve long-range information bottlenecks simply by scaling model depth or excessively widening layers. Relying on depth introduces severe training instability through vanishing gradients, while uncontrolled width expansion increases compute costs and risks poor generalization. Instead, the findings justify graph rewiring as the theoretically sound method to resolve information bottlenecks without compromising training dynamics.

For engineering and research teams facing over-squashing in graph learning tasks, the article supports adopting targeted graph rewiring strategies, such as spectral rewiring or effective resistance-based edge insertion, rather than increasing model depth. When spatial rewiring is chosen, teams must manage the trade-off between improved connectivity and increased graph density, which can introduce computational overhead and dilute local features. Further empirical research is recommended to establish concrete selection criteria determining exactly when spectral rewiring is preferable to spatial rewiring across specific real-world domain applications.

The analysis relies on theoretical bounds derived primarily for standard linear aggregation MPNNs with identical edge weightings and assumes uniform activation probabilities across computation paths. While the conclusions provide high confidence regarding fundamental message-passing limits, readers should exercise caution when applying these exact formulas directly to complex attention-based architectures (such as GATs), where dynamic edge pruning and gating mechanisms can introduce additional behavioral nuances.

Microsoft Sapienza University of Rome University of Cambridge University of Oxford network architecture network topology recurrent neural networks over-squashing message passing neural networks spectral rewiring

arXiv: 2302.02941

Paper: Neural Message Passing for Quantum Chemistry, Justin Gilmer et al. (2017). Introduces the standard Message Passing Neural Network (MPNN) framework whose theoretical depth, width, and topological limits are analyzed in the source.
Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). Establishes the foundational theoretical limits of standard MPNN expressiveness and neighbor aggregation that motivate deeper analyses of information flow bottlenecks.
Paper: Representation Learning on Graphs with Jumping Knowledge Networks, Keyulu Xu et al. (2018). Connects graph neighborhood propagation directly to random walk dynamics and layer-wise aggregation limits in GNNs.
Paper: Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, Deli Chen et al. (2019). Analyzes how graph topology and increasing layer depth cause representation degradation in GNNs.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). Defines the core localized graph convolutional architecture that serves as a primary baseline analyzed for over-squashing.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). Presents Graph Attention Networks, one of the central attention-based architectures benchmarked and evaluated for sensitivity bounds in the source.

Paper: A Generalization of ViT/MLP-Mixer to Graphs, Xiaoxin He et al. (2023). Proposes a patch-based Graph ViT/MLP-Mixer architecture specifically designed to capture long-range dependencies and overcome over-squashing with linear computational complexity.
Paper: Cooperative Graph Neural Networks, Ben Finkelshtein et al. (2024). Extends message-passing paradigms by introducing game-theoretic cooperative mechanisms to regulate and optimize inter-node information exchange.
Paper: Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing, Yunchong Song et al. (2023). Develops an ordered neuron-allocation framework to prevent the degradation of multi-hop neighborhood information across deep layers.
Paper: Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?, Haitao Mao et al. (2023). Investigates localized performance disparities and generalization bounds across diverse topological subgraphs in GNNs.

Cover for On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology

Abstract

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

Topics

network architecture network topology recurrent neural networks topology

Keywords

over-squashing message passing neural networks spectral rewiring signal propagation CliquePath tasks graph topologies receptive field propagation distance

1. Introduction
2. Background and related work
2.1. The message-passing paradigm
2.2. The problem: introducing over-squashing
2.3. Related work
3. The impact of width
4. The impact of depth
4.1. The shallow-diameter regime: over-squashing occurs among distant nodes
4.2. The deep regime: vanishing gradients dominate
5. The impact of topology
5.1. On over-squashing and access time
5.2. On over-squashing and commute time
5.3. A unified framework
6. Conclusion and discussion
Acknowledgements
References
A. General preliminaries
B. Proofs of Section 3
C. Proofs of Section 4
C.1. Vanishing gradients result
D. Proofs of Section 5
E. Graph Transfer
F. Signal Propagation

Knowls

Knowl 1 — Symmetric Jacobian Obstruction and Graph Commute Time Bound
theoretical result
Consider a Message Passing Neural Network (MPNN) of depth $m$ operating on an undirected, connected, non-bipartite graph $G = (V, E)$ with normalized adjacency matrix $A = D^{-1/2} A_{\text{adj}} D^{-1/2}$ , degree matrix $D = \text{diag}(d_1, \dots, d_n)$ , and layers defined by:

$h_v^{(t)} = \text{ReLU}\left(W^{(t)}\left(c_r h_v^{(t-1)} + c_a (A h^{(t-1)})_v\right)\right)$

where $c_r, c_a > 0$ with $c_r \ge c_a$ , and weight matrices $W^{(t)} \in \mathbb{R}^{p \times p}$ having maximum spectral norm $\mu$ and minimum singular value $\nu$ . Assume all paths in the computation graph activate independently with probability $\rho \in (0, 1]$ . If $\mu(c_r + c_a) \le 1$ , then there exists a constant $\epsilon_G = \frac{\lambda_1}{\lambda_1 + \frac{1 - \nu(c_r + c_a)}{\nu c_a}} > 0$ (with $\lambda_1$ the smallest positive eigenvalue of the normalized Laplacian $\Delta = I - A$ ) such that for any two nodes $v, u \in V$ , the expectation over the network activations of the symmetric Jacobian obstruction $\tilde{O}^{(m)}(v, u)$ satisfies:

$\epsilon_G (1 - o(m)) \frac{\rho}{\nu c_a} \frac{\tau(v, u)}{2|E|} \le \mathbb{E}\left[\tilde{O}^{(m)}(v, u)\right] \le \frac{\rho}{\mu c_a} \frac{\tau(v, u)}{2|E|}$

where $\tau(v, u)$ is the random walk commute time between $v$ and $u$ , $\frac{\tau(v, u)}{2|E|} = \text{Res}(v, u)$ is the effective electrical resistance between $v$ and $u$ , and $o(m) \to 0$ exponentially fast as $m \to \infty$ .

This demonstrates that over-squashing is fundamentally governed by the commute time (effective resistance) between node pairs rather than purely their geodesic distance, and this obstruction persists independently of network depth.
Knowl 2 — Jacobian Obstruction Bound via Graph Cheeger Constant
theoretical result
For an MPNN with layer updates $h_v^{(t)} = \text{ReLU}\left(W^{(t)}\left(c_r h_v^{(t-1)} + c_a (A h^{(t-1)})_v\right)\right)$ , maximal weight spectral norm $\mu$ , path activation probability $\rho$ , and $\mu(c_r + c_a) \le 1$ , the expected symmetric Jacobian obstruction $\tilde{O}^{(m)}(v, u)$ between any pair of nodes $v, u \in V$ on a graph $G$ is upper-bounded in terms of the Cheeger constant $h_{\text{Cheeg}}$ of $G$ as:

$\mathbb{E}\left[\tilde{O}^{(m)}(v, u)\right] \le \frac{4}{\rho \mu c_a} \frac{1}{h_{\text{Cheeg}}^2}$

where the Cheeger constant is defined as:

$h_{\text{Cheeg}} = \min_{U \subset V} \frac{|\{(u, v) \in E : u \in U, v \in V \setminus U\}|}{\min(\text{vol}(U), \text{vol}(V \setminus U))}$

with $\text{vol}(U) = \sum_{u \in U} d_u$ .

This result provides a theoretical justification for spectral graph rewiring methods: modifying the graph topology to increase $h_{\text{Cheeg}}$ (or using expander graphs where commute time scales as $O(|E|)$ ) provably decreases the information obstruction bound across all node pairs.
Knowl 3 — Directional Jacobian Obstruction and Random Walk Access Time
theoretical result
Consider an MPNN $h_v^{(t)} = \text{ReLU}\left(W^{(t)}\left(c_r h_v^{(t-1)} + c_a (A h^{(t-1)})_v\right)\right)$ with normalized shift operator $A = D^{-1/2} A_{\text{adj}} D^{-1/2}$ , path activation probability $\rho$ , and minimal singular value $\nu$ across all weight matrices. If the hyperparameters satisfy $\nu(c_r + c_a) = 1$ , the expected directional Jacobian obstruction $O^{(m)}(v, u)$ of node $v$ with respect to node $u$ after $m$ layers satisfies:

$\mathbb{E}\left[O^{(m)}(v, u)\right] \ge \frac{\rho}{\nu c_a} \frac{t(u, v)}{2|E|} + o(m)$

where $t(u, v)$ is the random walk access (hitting) time from node $u$ to node $v$ , $|E|$ is the number of edges, and $o(m) \to 0$ exponentially fast with $m$ .

A high access time $t(u, v)$ mathematically implies a high obstruction for node $v$ to receive signals originating at node $u$ , showing that directional over-squashing is governed by random walk hitting times and cannot be eliminated merely by adding more message passing layers.
Knowl 4 — Sensitivity Upper Bound on MPNN Features via Network Width and Shift Matrix
theoretical result
Let an MPNN of depth $m$ have node update rule:

$h_v^{(t+1)} = \sigma\left(c_r W_r^{(t)} h_v^{(t)} + c_a W_a^{(t)} \sum_{u \in V} A_{vu} h_u^{(t)}\right)$

where $\sigma$ is a pointwise non-linearity with Lipschitz constant $c_\sigma$ , $W_r^{(t)}, W_a^{(t)} \in \mathbb{R}^{p \times p}$ are weight matrices with maximal absolute entry value bounded by $w$ , $p$ is the hidden layer width, $A \in \mathbb{R}^{n \times n}$ is a graph shift operator, and $S_{r,a} := c_r I + c_a A$ . Then for any pair of nodes $v, u \in V$ , the $L_1$ -norm of the feature Jacobian satisfies:

$\left\| \frac{\partial h_v^{(m)}}{\partial h_u^{(0)}} \right\|_{L_1} \le (c_\sigma w p)^m (S_{r,a}^m)_{vu}$

More generally, for a $(c_{\text{up}}, c_{\text{rs}}, c_{\text{mp}})$ -regular MPNN where the update, residual, and message-passing functions have $L_1$ gradient bounds $c_{\text{up}}$ , $c_{\text{rs}}$ , and $c_{\text{mp}}$ respectively, the bound becomes:

$\left\| \frac{\partial h_v^{(m)}}{\partial h_u^{(0)}} \right\|_{L_1} \le p \cdot c_{\text{up}}^m \left( (c_{\text{rs}} I + c_{\text{mp}} A)^m \right)_{vu}$

Increasing the width $p$ can counteract topological attenuation factors $(S_{r,a}^m)_{vu}$ , but scales the model globally rather than addressing pair-specific bottlenecks.
Knowl 5 — Over-Squashing in the Shallow-Diameter Regime
theoretical result
Let $G = (V, E)$ be a graph with minimum degree $d_{\text{min}}$ , normalized adjacency matrix $A = D^{-1/2} A_{\text{adj}} D^{-1/2}$ , and geodesic distance $r = d_G(v, u)$ between nodes $v, u \in V$ . For an MPNN with $c_a \le 1$ , activation Lipschitz constant $c_\sigma$ , maximal weight entry $w$ , and width $p$ , let $\gamma_\ell(v, u)$ denote the number of walks of length at most $\ell$ between $v$ and $u$ . For any $0 \le k < r$ (where layer depth $m = r + k$ is comparable to distance $r$ ):

$\left\| \frac{\partial h_v^{(r+k)}}{\partial h_u^{(0)}} \right\|_{L_1} \le \gamma_{r+k}(v, u) \left( c_\sigma (c_r + c_a) w p (k + 1) \right)^k \left( \frac{2 c_\sigma w p c_a}{d_{\text{min}}} \right)^r$

Consequently, when $2 c_\sigma w p c_a < d_{\text{min}}$ and the number of walks $\gamma_{r+k}(v, u)$ is small, the sensitivity of $h_v^{(r+k)}$ to $h_u^{(0)}$ decays exponentially with distance $r$ .
Knowl 6 — Vanishing Gradients in Deep MPNNs
theoretical result
Consider an $m$ -layer MPNN $h_v^{(t+1)} = \sigma\left(c_r W_r^{(t)} h_v^{(t)} + c_a W_a^{(t)} \sum_{u} A_{vu} h_u^{(t)}\right)$ trained with a quadratic loss $\mathcal{L}(H^{(m)}) = \frac{1}{2} \sum_{v \in V} \|h_v^{(m)} - y_v\|^2$ . Assume $\sigma(0) = 0$ with Lipschitz constant $c_\sigma$ , and all weight matrices have spectral norm bounded by $\mu > 0$ . For any learnable parameter $\theta$ at layer $k < m$ , there exists a constant $C > 0$ independent of $m$ such that:

$\left| \frac{\partial \mathcal{L}}{\partial \theta} \right| \le C \left( c_\sigma \mu (c_r + c_a) \right)^{m-k} \left( 1 + \left( c_\sigma \mu (c_r + c_a) \right)^m \right)$

If $c_\sigma \mu (c_r + c_a) < 1$ , the gradient of the loss decays to zero exponentially fast with total depth $m$ . Therefore, deep MPNNs transition from over-squashing at $m \sim r$ to vanishing gradients at $m \gg r$ .
Knowl 7 — Directional and Symmetric Jacobian Obstructions
definition
For an MPNN operating on a graph $G = (V, E)$ with node degree $d_v$ and node representations $h_v^{(t)}$ at layer $t$ , the layer- $k$ directional Jacobian operator is defined as:

$J_k^{(m)}(v, u) := \frac{1}{d_v} \frac{\partial h_v^{(m)}}{\partial h_v^{(k)}} - \frac{1}{\sqrt{d_v d_u}} \frac{\partial h_v^{(m)}}{\partial h_u^{(k)}}$

The total directional Jacobian obstruction after $m$ layers is:

$O^{(m)}(v, u) := \sum_{k=0}^m \left\| J_k^{(m)}(v, u) \right\|$

The symmetric layer- $k$ Jacobian operator is defined as:

$\tilde{J}_k^{(m)}(v, u) := \left( \frac{1}{d_v} \frac{\partial h_v^{(m)}}{\partial h_v^{(k)}} - \frac{1}{\sqrt{d_v d_u}} \frac{\partial h_v^{(m)}}{\partial h_u^{(k)}} \right) + \left( \frac{1}{d_u} \frac{\partial h_u^{(m)}}{\partial h_u^{(k)}} - \frac{1}{\sqrt{d_v d_u}} \frac{\partial h_u^{(m)}}{\partial h_v^{(k)}} \right)$

and the total symmetric Jacobian obstruction is $\tilde{O}^{(m)}(v, u) := \sum_{k=0}^m \|\tilde{J}_k^{(m)}(v, u)\|$ . These measures quantify the insensitivity of node representations to signals from distant nodes relative to local self-signals across all intermediate layers.
Knowl 8 — Uniform Path Activation Assumption for MPNN Computation Graphs
assumption
In the sensitivity analysis of ReLU-activated MPNNs, all computational paths in the execution graph of the network are assumed to be active independently with an identical probability of success $\rho \in (0, 1]$ . Under this assumption, the expected Jacobian of node representations between layer $m$ and layer $k$ satisfies:

$\mathbb{E}\left[ \frac{\partial h_v^{(m)}}{\partial h_u^{(k)}} \right] = \rho \prod_{s=k+1}^m W^{(s)} (S_{r,a}^{m-k})_{vu}$

where $S_{r,a} = c_r I + c_a A$ is the weighted message-passing matrix.
Knowl 9 — Graph Transfer Benchmark: Topology and Width Dependence
empirical result
On the synthetic Graph Transfer task (where a source node must predict a 5-dimensional one-hot target label located at distance $r$ ), MPNN performance was evaluated across three distinct topologies:
1. Ring: Cycle of size $n$ , with source and target at distance $\lfloor n/2 \rfloor$ .
2. CrossedRing: Cycle of size $n$ with diagonal auxiliary cross edges that maintain source-target distance $\lfloor n/2 \rfloor$ but add alternative pathways.
3. CliquePath: A $\lfloor n/2 \rfloor$ -clique connected to a path of length $\lfloor n/2 \rfloor$ , with source in the clique and target at the path end (distance $\lfloor n/2 \rfloor + 1$ ).
Results across GCN, GIN, GraphSAGE, and GAT showed:
- Difficulty directly mirrored the analytical term $(S_{r,a}^r)_{vu}$ : CliquePath ( $(S_{r,a}^r)_{vu} = 2^{-(r-2)}/(r\sqrt{r}-2)$ ) failed first as $r$ increased, followed by Ring ( $(S_{r,a}^r)_{vu} = 2^{-(r-1)}$ ), while CrossedRing ( $(S_{r,a}^r)_{vu} = (3/2)^{-(r-1)}$ ) remained solvable at larger distances.
- For a fixed topology, increasing GCN hidden dimension $p$ from 1 to 64 systematically extended the solvable distance $r$ , verifying that width mitigates over-squashing.
Knowl 10 — Signal Propagation Distance Inversely Correlates with Total Effective Resistance
empirical result
To evaluate information propagation independently of training dynamics, signal propagation was measured across molecules from PROTEINS, NCI1, PTC, and ENZYMES using randomly initialized, untrained MPNNs (GIN, GraphSAGE, GCN, GAT). With a unit-mass feature placed at a source node $v$ , the normalized signal propagation distance after $m$ layers (with $m$ set close to the average graph diameter) was computed as:

$h_\odot^{(m)} = \frac{1}{p \max_{u \ne v} d_G(v, u)} \sum_{f=1}^p \sum_{u \ne v} \frac{h_u^{(m),f}}{\|h_u^{(m),f}\|} d_G(v, u)$

Across all four architectures and datasets, $h_\odot^{(m)}$ monotonically decayed as the normalized total effective resistance $\text{Res}_G = \sum_{v, u} \text{Res}(v, u)$ of the graph increased, confirming experimentally that graphs with lower effective resistance facilitate superior long-range information propagation.

Coverage note — No substantial contributed material was omitted; all primary theorems relating over-squashing to width, shallow/deep depth regimes, access time, commute time, Cheeger constant bounds, and empirical benchmarks were fully represented.

References

1.Abboud, R., Dimitrov, R., and Ceylan, I. I. Shortest path networks for graph property prediction. In The First Learning on Graphs Conference, 2022. URL https://openreview.net/forum?id=mWzWvMxuFg1.
2.Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Galstyan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21–29. PMLR, 2019.
3.Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
4.Arnaiz-Rodr%C3%ADguez, A., Begga, A., Escolano, F., and Oliver, N. DiffWire: Inductive Graph Rewiring via the Lov%C3%A1sz Bound. In The First Learning on Graphs Conference, 2022. URL https://openreview.net/pdf?id=IXvfIex0mX6f.
5.Banerjee, P. K., Karhadkar, K., Wang, Y. G., Alon, U., and Montufar, G. Oversquashing in gnns through the lens of information contraction and graph expansion. In Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1–8. IEEE, 2022.
6.Barcel%C3%B3, P., Kostylev, E. V., Monet, M., P%C3%A9rez, J., Reutter, J., and Silva, J. P. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019.
7.Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
8.Bengio, Y., Simard, P., and Frasconi, P. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157–166, 1994.
9.Black, M., Nayyeri, A., Wan, Z., and Wang, Y. Understanding oversquashing in gnns through the lens of effective resistance. arXiv preprint arXiv:2302.06835, 2023.
10.Bodnar, C., Frasca, F., Otter, N., Wang, Y., Lio, P., Montufar, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. In Advances in Neural Information Processing Systems, volume 34, pp. 2625–2640, 2021a.
11.Bodnar, C., Frasca, F., Wang, Y., Otter, N., Mont%C3%BAfar, G. F., Lio, P., and Bronstein, M. M. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026–1037, 2021b.
12.Bodnar, C., Giovanni, F. D., Chamberlain, B. P., Lio, P., and Bronstein, M. M. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Advances in Neural Information Processing Systems, 2022.
13.Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017.
14.Br%C3%BCel-Gabrielsson, R., Yurochkin, M., and Solomon, J. Rewiring with positional encodings for graph neural networks. arXiv preprint arXiv:2201.12674, 2022.
15.Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014.
16.Cai, C. and Wang, Y. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318, 2020.
17.Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., and Tiwari, P. The electrical resistance of a graph captures its commute and cover times. computational complexity, 6(4):312–340, 1996.
18.Chen, Z., Li, L., and Bruna, J. Supervised community detection with line graph neural networks. In International conference on learning representations, 2020.
19.Chung, F. R. and Graham, F. C. Spectral graph theory. American Mathematical Soc., 1997.
20.Dasoulas, G., Lutzeyer, J. F., and Vazirgiannis, M. Learning parametrised graph shift operators. In International Conference on Learning Representations, 2021.
21.Deac, A., Lackenby, M., and Veli%C4%8Dkovi%C4%87, P. Expander graph propagation. In The First Learning on Graphs Conference, 2022.
22.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, volume 29, 2016.
23.Devriendt, K. and Lambiotte, R. Discrete curvature on graphs from the effective resistance. Journal of Physics: Complexity, 2022.
24.Di Giovanni, F., Luise, G., and Bronstein, M. Heterogeneous manifolds for curvature-aware graph embedding. In International Conference on Learning Representations Workshop on Geometrical and Topological Representation Learning, 2022a.
25.Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., and Bronstein, M. M. Graph neural networks as gradient flows. arXiv preprint arXiv:2206.10991, 2022b.
26.D%C3%B6rfler, F., Simpson-Porco, J. W., and Bullo, F. Electrical networks and algebraic graph theory: Models, properties, and applications. Proceedings of the IEEE, 106(5):977–1005, 2018.
27.Ellens, W., Spieksma, F. M., Van Mieghem, P., Jamakovic, A., and Kooij, R. E. Effective graph resistance. Linear algebra and its applications, 435(10):2491–2506, 2011.
28.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263–1272. PMLR, 2017.
29.Goller, C. and Kuchler, A. Learning task-dependent distributed representations by backpropagation through structure. In Proceedings of International Conference on Neural Networks (ICNN’96), volume 1, pp. 347–352. IEEE, 1996.
30.Gori, M., Monfardini, G., and Scarselli, F. 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.
31.Gutteridge, B., Dong, X., Bronstein, M., and Di Giovanni, F. Drew: Dynamically rewired message passing with delay. arXiv preprint arXiv:2305.08018, 2023.
32.Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025–1035, 2017.
33.Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.
34.Jegelka, S. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
35.Karhadkar, K., Banerjee, P. K., and Mont%C3%BAfar, G. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint arXiv:2210.11790, 2022.
36.Kawaguchi, K. Deep learning without poor local minima. In Advances in neural information processing systems, volume 29, 2016.
37.Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, 2017.
38.Klicpera, J., Wei%C3%9Fenberger, S., and G%C3%BCnnemann, S. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, 2019.
39.Kreuzer, D., Beaini, D., Hamilton, W., L%C3%A9tourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, volume 34, pp. 21618–21629, 2021.
40.Li, G., M%C3%BCller, M., Thabet, A., and Ghanem, B. Deepgcns: Can gcns go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267–9276, 2019.
41.Li, G., M%C3%BCller, M., Ghanem, B., and Koltun, V. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437–6449. PMLR, 2021.
42.Lov%C3%A1sz, L. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
43.Ma, Z., Xuan, J., Wang, Y. G., Li, M., and Li%C3%B2, P. Path integral based convolution and pooling for graph neural networks. In Advances in Neural Information Processing Systems, volume 33, pp. 16421–16433, 2020.
44.Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667, 2021.
45.Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, pp. 4602–4609. AAAI Press, 2019.
46.Nikolentzos, G., Dasoulas, G., and Vazirgiannis, M. k-hop graph neural networks. Neural Networks, 130:195–205, 2020.
47.Nt, H. and Maehara, T. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550, 2019.
48.Ollivier, Y. Ricci curvature of metric spaces. Comptes Rendus Mathematique, 345(11):643–646, 2007.
49.Ollivier, Y. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, 256(3):810–864, 2009.
50.Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310–1318. PMLR, 2013.
51.Rampasek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, 2022.
52.Ruiz, L., Gama, F., and Ribeiro, A. Gated graph recurrent neural networks. IEEE Transactions on Signal Processing, 68:6303–6318, 2020.
53.Rusch, T. K. and Mishra, S. Coupled oscillatory recurrent neural network (co{rnn}): An accurate and (gradient) stable architecture for learning long time dependencies. In International Conference on Learning Representations, 2021a. URL https://openreview.net/forum?id=F3s69XzWOia.
54.Rusch, T. K. and Mishra, S. Unicornn: A recurrent model for learning very long time dependencies. In International Conference on Machine Learning, pp. 9168–9178. PMLR, 2021b.
55.Rusch, T. K., Chamberlain, B. P., Rowbottom, J., Mishra, S., and Bronstein, M. M. Graph-coupled oscillator networks. In International Conference on Machine Learning, 2022.
56.Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008.
57.Sperduti, A. Encoding labeled graphs by labeling raam. In Advances in Neural Information Processing Systems, volume 6, 1993.
58.Thomassen, C. Resistances and currents in infinite electrical networks. Journal of Combinatorial Theory, Series B, 49(1):87–102, 1990.
59.Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
60.Velingker, A., Sinop, A. K., Ktena, I., Veli%C4%8Dkovi%C4%87, P., and Gollapudi, S. Affinity-aware graph networks. arXiv preprint arXiv:2206.11941, 2022.
61.Veli%C4%8Dkovi%C4%87, P., Cucurull, G., Casanova, A., Romero, A., Li%C3%B2, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
62.Wang, G., Ying, R., Huang, J., and Leskovec, J. Multi-hop attention graph neural network. arXiv preprint arXiv:2009.14332, 2020.
63.Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453–5462. PMLR, 2018.
64.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
65.Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, volume 34, pp. 28877–28888, 2021.
66.Zhao, W., Wang, C., Han, C., and Guo, T. Analysis of graph neural networks with theory of markov chains. 2022.

Citation

MLA

Giovanni, F. D., et al. “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology”. International Conference on Machine Learning, vol. 202, 2023, pp. 7865–85, https://proceedings.mlr.press/v202/di-giovanni23a.html.

APA

Giovanni, F. D., Giusti, L., Barbero, F., Luise, G., Lio, P., & Bronstein, M. M. (2023). On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. International Conference on Machine Learning, 202, 7865–7885. https://proceedings.mlr.press/v202/di-giovanni23a.html

Chicago

Giovanni, F. D., L. Giusti, F. Barbero, G. Luise, P. Lio, and M. M. Bronstein. 2023. “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology”. International Conference on Machine Learning 202: 7865–85. https://proceedings.mlr.press/v202/di-giovanni23a.html.

Harvard

Giovanni, F.D. et al. (2023) “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology”, International Conference on Machine Learning. PMLR, pp. 7865–7885. Available at: https://proceedings.mlr.press/v202/di-giovanni23a.html.

Vancouver

1. Giovanni FD, Giusti L, Barbero F, Luise G, Lio P, Bronstein MM (2023) On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. In: International Conference on Machine Learning. PMLR, pp 7865–7885

BibTeX

@InProceedings{pmlr-v202-di-giovanni23a,
  title = 	 {On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology},
  author =       {Di Giovanni, Francesco and Giusti, Lorenzo and Barbero, Federico and Luise, Giulia and Lio, Pietro and Bronstein, Michael M.},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {7865--7885},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/di-giovanni23a/di-giovanni23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/di-giovanni23a.html},
  abstract = 	 {Message Passing Neural Networks (MPNNs) are instances of Graph Neural Networks that leverage the graph to send messages over the edges. This inductive bias leads to a phenomenon known as over-squashing, where a node feature is insensitive to information contained at distant nodes. Despite recent methods introduced to mitigate this issue, an understanding of the causes for over-squashing and of possible solutions are lacking. In this theoretical work, we prove that: (i) Neural network width can mitigate over-squashing, but at the cost of making the whole network more sensitive; (ii) Conversely, depth cannot help mitigate over-squashing: increasing the number of layers leads to over-squashing being dominated by vanishing gradients; (iii) The graph topology plays the greatest role, since over-squashing occurs between nodes at high commute time. Our analysis provides a unified framework to study different recent methods introduced to cope with over-squashing and serves as a justification for a class of methods that fall under graph rewiring.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Symmetric Jacobian Obstruction and Graph Commute Time Bound

Knowl 2 — Jacobian Obstruction Bound via Graph Cheeger Constant

Knowl 3 — Directional Jacobian Obstruction and Random Walk Access Time

Knowl 4 — Sensitivity Upper Bound on MPNN Features via Network Width and Shift Matrix

Knowl 5 — Over-Squashing in the Shallow-Diameter Regime

Knowl 6 — Vanishing Gradients in Deep MPNNs

Knowl 7 — Directional and Symmetric Jacobian Obstructions

Knowl 8 — Uniform Path Activation Assumption for MPNN Computation Graphs

Knowl 9 — Graph Transfer Benchmark: Topology and Width Dependence

Knowl 10 — Signal Propagation Distance Inversely Correlates with Total Effective Resistance

References

Citation

BibTeX

Access the Paper