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

Aug 5, 2026

Upload by Liam

Message Passing Neural Networks (MPNNs) operate on graphs by exchanging information along edges, but this inductive bias can produce over-squashing: node representations become insensitive to information originating from distant nodes. Building on recent mitigation proposals, this theoretical work establishes when and why oversquashing can be reduced or not. It proves that increased width can mitigate oversquashing with a sensitivity trade-off, whereas increased depth is ineffective due to vanishing gradients, and shows graph topology dominates via high commute time.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

AccessFree to download

Abstract

Introduction

Contributions and outline

Background and related work

The message-passing paradigm

On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology Francesco Di Giovanni 1 Lorenzo Giusti 2 Federico Barbero 3 Giulia Luise 4 Pietro Li 1 Michael Bronstein 3 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 oversquashing 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. 1. Introduction Learning on graphs with Graph Neural Networks (GNNs)(Sperduti, 1993 ; Goller & Kuchler, 1996 ; Gori et al., 2005 ; Scarselli et al., 2008 ; Bruna et al., 2014 ; Defferrard et al., 2016) has become an increasingly flourishing area of machine learning. Typically, GNNs operate in the messagepassing paradigm by exchanging information between nearby nodes (Gilmer et al., 2017), giving rise to the class of Message-Passing Neural Networks (MPNNs) . While message-passing has demonstrated to be a useful inductive bias, it has also been shown that the paradigm has some fun- 1University of Cambridge 2 Sapienza University 3University of Oxford 4Microsoft Research. Correspondence to: Francesco Di Giovanni <[fd405@cam.ac.uk](fd405@cam.ac.uk)> . Proceedings of the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023 . Copyright 2023 by the author(s) . damental flaws, from expressivity (Xu et al., 2019 ; Morris et al., 2019), to over-smoothing (Nt & Maehara, 2019 ; Cai & Wang, 2020 ; Bodnar et al., 2022 ; Rusch et al., 2022 ; Di Giovanni et al., 2022b ; Zhao et al., 2022) and over-squashing. The first two limitations have been thoroughly investigated, however less is known about over-squashing. Alon & Yahav (2021) described over-squashing as an issue emerging when MPNNs propagate messages across distant nodes, with the exponential expansion of the receptive field of a node leading to many messages being ‘squashed’ into fixed-size vectors. Topping et al. (2022) formally justified this phenomenon via a sensitivity analysis on the Jacobian of node features and, partly, linked it to the existence of edges with high-negative curvature. However, some important questions are left open from the analysis in Topping et al. (2022): (i) What is the impact of width in mitigating over-squashing? (ii) Can over-squashing be avoided by sufficiently deep models? (iii) How does over-squashing relate to the graph-spectrum and the underlying topology beyond curvature bounds that only apply to 2-hop propagation? The last point is particularly relevant due to recent works trying to combat over-squashing via methods that depend on the graph spectrum (Arnaiz-Rodr´ıguez et al., 2022 ; Deacet al., 2022 ; Karhadkar et al., 2022) . However, it is yet to be clarified if and why these works alleviate over-squashing. In this work, we aim to address all the questions that are left open in Topping et al. (2022) to provide a better theoretical understanding on the causes of over-squashing as well as on what can and cannot fix it. Contributions and outline. An MPNN is generally constituted by two main parts: a choice of architecture, and an underlying graph o

FAQs

What problem does over-squashing describe in MPNNs?

Over-squashing occurs when MPNNs propagate information across distant nodes, causing many incoming messages to be “squashed” into fixed-size vectors and making node features insensitive to far-away information.

How does neural network width affect over-squashing?

The work shows that increasing width can mitigate over-squashing, but may come at the cost of making the network more sensitive and potentially affecting generalization.

Why does increasing depth fail to mitigate over-squashing?

Depth does not help in general: when layer count matches the graph diameter, oversquashing emerges among distant nodes; for larger depths, the model becomes dominated by vanishing gradients.

Aug 5, 2026

Upload by Liam