On the Bottleneck of Graph Neural Networks and its Practical Implications

By Uri Alon, Eran Yahav. International Conference on Learning Representations, 2020

1,002 citations recorded by the source corpus.

Graph neural networks (GNNs) were shown to effectively learn from highly structured data containing elements (nodes) with relationships (edges) between them. GNN variants differ in how each node in the graph absorbs the information flowing from its neighbor nodes. In this paper, we highlight an inherent problem in GNNs: the mechanism of propagating information between neighbors creates a bottleneck when every node aggregates messages from its neighbors. This bottleneck causes the over-squashing of exponentially-growing information into fixed-size vectors. As a result, the graph fails to propagate messages flowing from distant nodes and performs poorly when the prediction task depends on long-range information. We demonstrate that the bottleneck hinders popular GNNs from fitting the training data. We show that GNNs that absorb incoming edges equally, like GCN and GIN, are more susceptible to over-squashing than other GNN types. We further show that existing, extensively-tuned, GNN-based models suffer from over-squashing and that breaking the bottleneck improves state-of-the-art results without any hyperparameter tuning or additional weights.

Subfields: Artificial Intelligence, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/3bfa808ce20b2736708c3fc0b9443635e3f133a7

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 Materials Chemistry

Citations in the corpus

How Attentive are Graph Attention Networks? (2021, background): “, 2020), over-squashing (Alon and Yahav, 2021), or vanishing gradients (Li et al.”
Understanding over-squashing and bottlenecks on graphs via curvature (2021, methodology): “For example, if d G ( i, s ) = r + 1 and the sub-graph induced on B r +1 ( i ) is a binary tree, then ( ˆ A r +1 ) is = 2 − 1 3 − r , which gives an exponential decay of the node dependence on input features at distance r , as also heuristically argued by Alon & Yahav (2021).”
A Survey on Oversmoothing in Graph Neural Networks (2023, background): “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).”
Structural Language Models of Code (2019, background): “Ablation acc@1 acc@5 tree@1 tree@5 Paths → Seq The superiority of our model over GNN →NAG may also be related to the GNN bottleneck (Alon & Yahav, 2020), which hinders GNNs from propagating long-range messages.”
Parameter Prediction for Unseen Deep Architectures (2021, background): “This structure might hinder long-range propagation of information between nodes [60].”
Representing Long-Range Context for Graph Neural Networks with Global Attention (2022, methodology): “More recently, state-of-the-art approaches to several computer vision tasks use an attention-style submodule on top of a traditional CNN backbone [2, 33, etc.].”
Rethinking Graph Transformers with Spectral Attention (2021, background): “Over-squashing represents the difficulty of a graph neural network to pass information to distant neighbours due to the exponential blow-up in computational paths [1].”
SIGN: Scalable Inception Graph Neural Networks (2020, methodology): “This phenomenon, as well as its connection to the DropEdge method [50] and the bottleneck problem [2], would be object of further investigation.”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, background): “However, this solution can be deficient for long-distance nodes because of the over-squashing phenomenon (Alon & Yahav, 2020).”
Long Range Graph Benchmark (2022, positive): “…of message passing based GNNs [22] with respect to the 1-Weisfeiler Leman (WL) isomorphism test [60, 62, 46] and the information oversquashing [2], there has been several developments of GNN and Graph Transformer architectures which have strictly greater representation power than 1-WL [7, 3,…”
Structure-Aware Transformer for Graph Representation Learning (2022, background): “These include the limited expressiveness of GNNs (Xu et al., 2019; Morris et al., 2019), as well as known problems such as over-smoothing (Li et al., 2018; 2019; Chen et al., 2020; Oono & Suzuki, 2020) and oversquashing (Alon & Yahav, 2021).”
Everything is Connected: Graph Neural Networks (2023, background): “Further, even if a ground-truth A is given without noise , it may not be the optimal computation graph : that is, passing messages over it may be problematic— for example, due to bottlenecks (Alon and Yahav, 2021).”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, background): “Further, the Transformer allows to resolve the expressivity bottlenecks caused by over-smoothing [34] and over-squashing [1] by allowing information to spread across the graph via full-connectivity.”
Artificial intelligence in drug development (2025, neutral): “Further, AI drug development faces talent shortages and investment risks due to long cycles, low success rates and uncertain returns, affecting investor confidence.”
Type4Py: Practical Deep Similarity Learning-Based Type Inference for Python (2021, background): “We attribute this to the inherent bottleneck of GNNs which is over-squashing information into a fixed-size vector [13] and thus they fail to capture long-range interaction.”
GRAND: Graph Neural Diffusion (2021, methodology): “Multiple GNN architecture de facto use a different computational graph from the input one, whether for reasons of scalability (e.g. sampling used in GraphSAGE (Hamilton et al., 2017)), denoising the input graph (Klicpera et al., 2019), or avoiding bottlenecks (Alon & Yahav, 2021).”
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, background): “heterophily [53], over-squashing [2], long-range dependencies [8], and graph incompleteness [11], etc.”
MolGenSurvey: A Systematic Survey in Machine Learning Models for Molecule Design (2022, background): “N-Gram Graph [35], on the other hand, proposes the walk-based GNN that can alleviate the over-squashing issue [36] in the MPNN-based GNN.”