On the Bottleneck of Graph Neural Networks and its Practical Implications

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/ .

arXiv commentAccepted to ICLR'2021

References in corpus (12)

• Sequence to Sequence Learning with Neural Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Pitfalls of Graph Neural Network Evaluation
• Simple and Deep Graph Convolutional Networks
• PairNorm: Tackling Oversmoothing in GNNs
• A Fair Comparison of Graph Neural Networks for Graph Classification
• Generalization and Representational Limits of Graph Neural Networks

Cited by in corpus (28)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• SIGN: Scalable Inception Graph Neural Networks
• Graph Neural Networks: Taxonomy, Advances and Trends
• Rethinking Graph Transformers with Spectral Attention
• Learning physical properties of anomalous random walks using graph neural networks
• Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
• Graph-based Modeling of Online Communities for Fake News Detection
• On the design space between molecular mechanics and machine learning force fields
• Graph Neural Networks with Learnable Structural and Positional Representations
• Building powerful and equivariant graph neural networks with structural message-passing
• Deep Graph Neural Networks with Shallow Subgraph Samplers
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• Directional Graph Networks
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• On Graph Neural Networks versus Graph-Augmented MLPs
• The Impact of Global Structural Information in Graph Neural Networks Applications
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
• Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormer
• Parameter Prediction for Unseen Deep Architectures
• Data-Driven Learning of Geometric Scattering Networks
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism
• Learning Parametrised Graph Shift Operators
• Improving the Long-Range Performance of Gated Graph Neural Networks
• An FEA surrogate model with Boundary Oriented Graph Embedding approach
• FDGATII : Fast Dynamic Graph Attention with Initial Residual and Identity Mapping
• Convolutions for Spatial Interaction Modeling
• LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
• Image-Like Graph Representations for Improved Molecular Property Prediction