Understanding over-squashing and bottlenecks on graphs via curvature

By Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein. International Conference on Learning Representations, 2021

679 citations recorded by the source corpus.

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 $k$-hop neighbors grows rapidly with $k$. 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/04ac11f8db83406b03d92aa4571fc3e6c176c1e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

A Survey on Oversmoothing in Graph Neural Networks (2023, neutral): “This is related to several issues impairing the performance of deep GNNs in realistic graph-learning settings: graph bottlenecks (Alon & Yahav, 2021), over-squashing (Topping et al., 2021; Deac et al., 2022), and over-smoothing (Li et al., 2018; Nt & Maehara, 2019; Oono & Suzuki, 2020).”
Large Language Models on Graphs: A Comprehensive Survey (2023, background): “Subsequent work on GNN tackles the issues of over-smoothing [139], over-squashing [140], interpretability [145], and bias [143].”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, background): “Particularly, they are expected to help alleviate the problems of over-smoothing and over-squashing [1, 51] in MPNNs, which are analogous to the vanishing gradients and lack of long-term dependencies in NLP.”