Understanding over-squashing and bottlenecks on graphs via curvature
arXiv:2111.14522
Abstract
Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of -hop neighbors grows rapidly with . We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.
arXiv commentPublished at ICLR 2022 (Outstanding Paper Honourable Mention); 30 pages. v2: corrected Corollary 3 and rephrased in terms of graph diameter. Any other result is unaffected
References in corpus (13)
- Neural Message Passing for Quantum Chemistry
- Representation Learning on Graphs with Jumping Knowledge Networks
- Pitfalls of Graph Neural Network Evaluation
- Finite extinction time for the solutions to the Ricci flow on certain three-manifolds
- Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
- Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
- Network Geometry
- SIGN: Scalable Inception Graph Neural Networks
- Forman curvature for complex networks
- Differentiable Graph Module (DGM) for Graph Convolutional Networks
- Geom-GCN: Geometric Graph Convolutional Networks
- Hyperbolic Graph Neural Networks
- Interpretable Stability Bounds for Spectral Graph Filters