On the Bottleneck of Graph Neural Networks and its Practical Implications

2020/06/09 by Uri Alon, Eran Yahav, Alon, Uri +1 · 1 voice · 117 citations
Computer Science · Engineering · Materials Science · Mathematics · #Advanced Graph Neural Networks #Advanced Memory and Neural Computing #Algorithm #Artificial intelligence #Bottleneck #Cluster analysis #Code (set theory) #Computer network #Computer science #Data mining #Engineering #Ferroelectric and Negative Capacitance Devices #Graph #Hyperparameter #Information bottleneck method #Machine Learning in Materials Science #Mutual information #Node (physics) #Path (computing) #Range (aeronautics) #Theoretical computer science #Topic Modeling #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2006.05205

published in arXiv (Cornell University) (Cornell University) · Accepted to ICLR'2021

openalex publication_date 2020/06/09 · arxiv created 2021/03/09 · arxiv updated 2021/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

Since the proposal of the graph neural network (GNN) by Gori et al. (2005) and Scarselli et al. (2008), one of the major problems in training GNNs was their struggle to propagate information between distant nodes in the graph. We propose a new explanation for this problem: GNNs are susceptible to a bottleneck when aggregating messages across a long path. This bottleneck causes the over-squashing of exponentially growing information into fixed-size vectors. As a result, GNNs fail to propagate messages originating from distant nodes and perform poorly when the prediction task depends on long-range interaction. In this paper, we highlight the inherent problem of over-squashing in GNNs: we demonstrate that the bottleneck hinders popular GNNs from fitting long-range signals in the training data; we further show that GNNs that absorb incoming edges equally, such as GCN and GIN, are more susceptible to over-squashing than GAT and GGNN; finally, we show that prior work, which extensively tuned GNN models of long-range problems, suffers from over-squashing, and that breaking the bottleneck improves their state-of-the-art results without any tuning or additional weights. Our code is available at https://github.com/tech-srl/bottleneck/ .

Cited by

• ReVEAL: GNN-Guided Reverse Engineering for Formal Verification of Optimized Multipliers
• Plain Transformers are Surprisingly Powerful Link Predictors
• Long-range electrostatics for machine learning interatomic potentials is easier than we thought
• Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation
• How Smoothing is N-simplicial Attention?
• Photonics-Enhanced Graph Convolutional Networks
• A Roadmap for Applying Graph Neural Networks to Numerical Data: Insights from Cementitious Materials
• Enhancing Node-Level Graph Domain Adaptation by Alleviating Local Dependency
• View Space: Learning Representation across Arbitrary Graphs
• Understanding the Failure Modes of Transformers through the Lens of Graph Neural Networks
• Multi-Scale Protein Structure Modelling with Geometric Graph U-Nets
• Layered Division and Global Allocation for Community Detection in Multilayer Network
• Cross-View Topology-Aware Graph Representation Learning
• Reasoning About the Unsaid: Misinformation Detection with Omission-Aware Graph Inference
• The Final-Stage Bottleneck: A Systematic Dissection of the R-Learner for Network Causal Inference
• Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
• Short-Range Oversquashing
• Resolving Node Identifiability in Graph Neural Processes via Laplacian Spectral Encodings
• Foundations of Artificial Intelligence Frameworks: Notion and Limits of AGI
• Gauge-Equivariant Graph Networks via Self-Interference Cancellation
• Transformer-Based Multi-Agent Reinforcement Learning for Networked Systems with Long-Range Interactions
• GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance
• AdaptViG: Adaptive Vision GNN with Exponential Decay Gating
• Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamics
• Efficient Curvature-aware Graph Network
• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
• Learning the Word Problem: Geodesic Lengths and Cryptographic Applications
• Enhanced spatial clustering of single-molecule localizations with graph neural networks
• A roadmap for curvature-based geometric data analysis and learning
• Hierarchical Graph Networks for Accurate Weather Forecasting via Lightweight Training
• Relieving the Over-Aggregating Effect in Graph Transformers
• Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models
• On The Expressive Power of GNN Derivatives
• T3former: Temporal Graph Classification with Topological Machine Learning
• Reciprocal Space Attention for Learning Long-Range Interactions
• Multi-Scale High-Resolution Logarithmic Grapher Module for Efficient Vision GNNs
• GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus
• Bridging Semantics & Structure for Software Vulnerability Detection using Hybrid Network Models
• gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity
• When Does Global Attention Help? A Unified Empirical Study on Atomistic Graph Learning
• ATOM: A Pretrained Neural Operator for Multitask Molecular Dynamics
• Neural Message-Passing on Attention Graphs for Hallucination Detection
• TRACE: Learning to Compute on Graphs
• SlideMamba: Entropy-Based Adaptive Fusion of GNN and Mamba for Enhanced Representation Learning in Digital Pathology
• Ricci Flow on Weighted Digraphs with Balancing Factor
• Frame-based Equivariant Diffusion Models for 3D Molecular Generation
• Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks
• Schreier-Coset Graph Rewiring
• LLM-based Vulnerability Discovery through the Lens of Code Metrics
• Quantum Graph Attention Network: A Novel Quantum Multi-Head Attention Mechanism for Graph Learning
• MAST: Multi-Agent Spatial Transformer for Learning to Collaborate
• Exploring the Global-to-Local Attention Scheme in Graph Transformers: An Empirical Study
• A Multi-Scale Graph Neural Process with Cross-Drug Co-Attention for Drug-Drug Interactions Prediction
• GRATE: a Graph transformer-based deep Reinforcement learning Approach for Time-efficient autonomous robot Exploration
• Scaling Graph Transformers: A Comparative Study of Sparse and Dense Attention
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
• Why does your graph neural network fail on some graphs? Insights from exact generalisation error
• Long-Range Graph Wavelet Networks
• Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks
• Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies
• Bridging Thoughts and Words: Graph-Based Intent-Semantic Joint Learning for Fake News Detection
• What Expressivity Theory Misses: Message Passing Complexity for GNNs
• A Geometric Perspective on the Difficulties of Learning GNN-based SAT Solvers
• Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks
• Memorization in Graph Neural Networks
• Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
• Predicting the Performance of Graph Convolutional Networks with Spectral Properties of the Graph Laplacian
• Non-Dissipative Graph Propagation for Non-Local Community Detection
• Chi-Geometry: A Library for Benchmarking Chirality Prediction of GNNs
• TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
• Understanding the Embedding Models on Hyper-relational Knowledge Graph
• WOCD: A Semi-Supervised Method for Overlapping Community Detection Using Weak Cliques
• Learning Long-Range Representations with Equivariant Messages
• Causal Process Models: Reframing Dynamic Causal Graph Discovery as a Reinforcement Learning Problem
• DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomolecules
• GATE: Graph Attention Neural Networks with Real-Time Edge Construction for Robust Indoor Localization using Mobile Embedded Devices
• DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local Fusion
• Geometric Generative Modeling with Noise-Conditioned Graph Networks
• SILVA Networks as Structured Implicit Layers and Vector Attractors via Dynamic Interaction Fields
• Cooperative Sheaf Neural Networks
• Transaction Categorization with Relational Deep Learning in QuickBooks
• Convergent Privacy Framework for Multi-layer GNNs through Contractive Message Passing
• Generative Modeling of Full-Atom Protein Conformations using Latent Diffusion on Graph Embeddings
• Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks
• CLOUD: A Scalable and Physics-Informed Foundation Model for Crystal Representation Learning
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
• Long-Context Generalization with Sparse Attention
• Over-squashing in Spatiotemporal Graph Neural Networks
• GITO: Graph-Informed Transformer Operator for Learning Complex Partial Differential Equations
• How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?
• Caterpillar GNN: Replacing Message Passing with Efficient Aggregation
• FuncGNN: Learning Functional Semantics of Logic Circuits with Graph Neural Networks
• Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing
• On Measuring Long-Range Interactions in Graph Neural Networks
• Influence Functions for Edge Edits in Non-Convex Graph Neural Networks
• Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
• Multi-Granular Attention based Heterogeneous Hypergraph Neural Network
• Towards Efficient Few-shot Graph Neural Architecture Search via Partitioning Gradient Contribution
• Improving the Effective Receptive Field of Message-Passing Neural Networks
• Thickness-aware E(3)-Equivariant 3D Mesh Neural Networks
• Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling
• Early-Exit Graph Neural Networks
• DAM-GT: Dual Positional Encoding-Based Attention Masking Graph Transformer for Node Classification
• Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning
• Table Foundation Models: on knowledge pre-training for tabular learning
• Electrostatics from Laplacian Eigenbasis for Neural Network Interatomic Potentials
• Graph-Guided Passage Retrieval for Author-Centric Structured Feedback
• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
• Relational Graph Transformer
• Schreier-Coset Graph Propagation
• SAR-GTR: Attributed Scattering Information Guided SAR Graph Transformer Recognition Algorithm
• Graph Neural Network Predictions of Carbon 1s Binding Energies with Near-Experimental Accuracy
• Understanding Truncated Positional Encodings for Graph Neural Networks
• Designing a Good Virtual Node: Addressable and Cardinality-Preserving Global Memory for Message Passing Architectures
• SFi-Former: Sparse Flow Induced Attention for Graph Transformer
• Graph Neural Network Reveals the Cortical Morphology of Local Brain Aging in Normal Cognition and Alzheimer's Disease
• PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networks

Discussions

• The original 'oversquashing' paper is very accessibly written: - In GNNs, when data needs to pass many nodes, the data gets exponentially 'diluted' - Adding a simply fully-connected edge layer, impro [bsky, 1 points, 0 comments]

Related

• How does over-squashing affect the power of GNNs?
• Over-Squashing in Graph Neural Networks: A Comprehensive survey
• Understanding over-squashing and bottlenecks on graphs via curvature
• Short-Range Oversquashing
• On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning