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

Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', Michael M. Bronstein

Abstract

Message Passing Neural Networks (MPNNs) are the standard architecture for graph-based machine learning, yet they suffer from a fundamental limitation known as "over-squashing." This phenomenon occurs when information from a node's distant neighborhood is compressed into a fixed-size vector, leading to signal loss. This paper provides a rigorous theoretical framework to analyze over-squashing through the lens of sensitivity analysis. We demonstrate that while increasing network width can mitigate the issue, it risks overfitting, and increasing depth eventually leads to vanishing gradients. Ultimately, we show that the primary driver of over-squashing is the graph's topology, specifically related to commute times and effective resistance between nodes.

Introduction

In MPNNs, nodes update their representations by aggregating features from their immediate neighbors. As the number of layers ($m$) increases, the "receptive field" of a node—the set of nodes from which it can receive information—grows exponentially. However, the hidden dimension ($p$) of the node features remains fixed. This creates a bottleneck where a vast amount of structural and feature information must be "squashed" into a single vector. When a task depends on long-range dependencies, the signal from a distant source node often becomes indistinguishable from noise, a problem termed over-squashing.

While the existence of this bottleneck has been recognized, this research seeks to formalize the interaction between model hyperparameters (width and depth) and the underlying graph structure (topology) to understand how they collectively contribute to or alleviate this bottleneck.

Theoretical Framework: Sensitivity Analysis

To quantify over-squashing, the authors employ sensitivity analysis. Specifically, they examine the Jacobian of the hidden features of a node $v$ at layer $m$ with respect to the input features of a node $u$ at layer 0:

$$\left| \frac{\partial \mathbf{h}_v^{(m)}}{\partial \mathbf{x}_u} \right|$$

If this derivative is near zero, the network is effectively "blind" to the features of node $u$ when computing the representation for node $v$. The paper generalizes previous sensitivity bounds to account for multi-dimensional hidden features and arbitrary network depths, providing a unified metric for information flow.

The Impact of Model Architecture

Width: A Global Band-Aid

Theorem 3.2 in the paper proves that increasing the hidden dimension ($p$)—the width of the GNN—mitigates over-squashing. By providing more "space" in the vector representations, the network can preserve more information from the neighborhood. However, the authors caution that this is a brute-force solution. Increasing width globally increases the network's sensitivity to all nodes in the receptive field, which can lead to overfitting and poor generalization as the model struggles to distinguish relevant signals from irrelevant noise.

Depth: The Vanishing Gradient Trap

One might assume that increasing the number of layers ($m$) would naturally solve long-range dependency issues by allowing the message-passing process to reach further. However, Theorem 4.2 demonstrates a transition point: as depth increases, the network moves from an over-squashing regime to a vanishing gradient regime. There is no optimal depth that solves long-range dependencies for all graph types; instead, excessive depth eventually renders the training process unstable and the signal propagation ineffective.

The Role of Topology

The most significant contribution of this work is linking over-squashing to classical graph theory. The authors prove that the severity of over-squashing between two nodes $u$ and $v$ is directly related to their commute time and effective resistance.

  • Commute Time: The expected number of steps a random walk takes to travel from $u$ to $v$ and back.
  • Effective Resistance: A measure of how well-connected two nodes are, viewing the graph as an electrical circuit.

Nodes separated by high effective resistance (i.e., few paths or long distances) are the most susceptible to over-squashing. This explains why "graph rewiring" strategies—adding edges to bridge bottlenecks or improving the graph's spectral gap—are effective at improving GNN performance. These strategies are essentially reducing the effective resistance between distant nodes.

Experimental Validation

Synthetic "Graph Transfer" Tasks

The authors tested their framework on three synthetic topologies designed to isolate the impact of distance and connectivity:

  1. Ring: A simple cycle where information must travel along a single path.
  2. CrossedRing: A ring with additional "shortcut" edges.
  3. CliquePath: A series of fully connected cliques joined by single edges.

Results showed that CliquePath exhibited the highest over-squashing due to its extreme bottlenecks, while CrossedRing was the easiest to solve because the shortcuts reduced the effective resistance between nodes.

Real-World Benchmarks

On standard datasets such as PROTEINS, NCI1, and ENZYMES, the authors found a clear inverse correlation between the total effective resistance of a graph and the ability of an MPNN to propagate signals. Graphs that are naturally well-connected allow for significantly better information flow, confirming that topology is a primary determinant of model success.

Conclusion

Over-squashing is not merely a symptom of shallow networks but a complex interplay between architecture and graph structure. While increasing width offers a partial reprieve, it is not a scalable solution. This research suggests that the most effective way to combat over-squashing is to address the graph's topology directly. By understanding the resistance and commute times within a graph, researchers can better design rewiring strategies that facilitate efficient information flow without falling into the traps of overfitting or vanishing gradients.

Summary updated

BibTeX
@inproceedings{giovanni2023over,
  author = {Francesco Di Giovanni and Lorenzo Giusti and Federico Barbero and Giulia Luise and Pietro Lio' and Michael M. Bronstein},
  title = {{On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=t2tTfWwAEl},
}
Figure