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

2023/02/06 by Francesco Di Giovanni, Di Giovanni, Francesco, Lorenzo Giusti +9 · 27 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Artificial Intelligence (cs.AI) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2302.02941

openalex publication_date 2023/02/06 · openalex created_date 2023/02/09 · openalex updated_date 2026/07/28

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 (access) time. Our analysis provides a unified framework to study different recent methods introduced to cope with over-squashing and serves as a justification for a class of methods that fall under graph rewiring.

Cited by

• Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation
• How Smoothing is N-simplicial Attention?
• Understanding the Failure Modes of Transformers through the Lens of Graph Neural Networks
• Multi-Scale Protein Structure Modelling with Geometric Graph U-Nets
• Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
• Short-Range Oversquashing
• Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulations
• Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamics
• How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimation
• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
• Attention Sinks in Diffusion Language Models
• Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models
• On The Expressive Power of GNN Derivatives
• Structured Spectral Graph Representation Learning for Multi-label Abnormality Analysis from 3D CT Scans
• gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity
• Transformers Discover Molecular Structure Without Graph Priors
• LEAP: Local ECT-Based Learnable Positional Encodings for Graphs
• State Space Models over Directed Graphs
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
• What Expressivity Theory Misses: Message Passing Complexity for GNNs
• Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks
• Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
• Training Transformers for Mesh-Based Simulations
• Over-Squashing in GNNs and Causal Inference of Rewiring Strategies
• TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
• Understanding Learning Dynamics Through Structured Representations
• GraphTorque: Torque-Driven Rewiring Graph Neural Network

Related

• Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges
• How does over-squashing affect the power of GNNs?
• Understanding over-squashing and bottlenecks on graphs via curvature
• Over-Squashing in Graph Neural Networks: A Comprehensive survey
• Leave Graphs Alone: Addressing Over-Squashing without Rewiring