aiqbench analysis
This research addresses a fundamental limitation in Graph Neural Networks (GNNs) known as over-squashing, where information from distant nodes becomes distorted during message passing. The authors introduce a new combinatorial curvature metric to precisely identify negatively curved edges that cause this bottleneck and propose a graph rewiring technique to mitigate the issue. By linking structural geometry directly to GNN performance, this work offers a rigorous theoretical foundation for improving long-range interaction capabilities in machine learning models.
Understanding over-squashing and bottlenecks on graphs via curvature
arXiv:2111.14522v4 Announce Type: replace-cross 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 $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.
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 $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.
Published 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
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2111.14522 [stat.ML]
(or arXiv:2111.14522v4 [stat.ML] for this version)
Full text under the publisher's open licence · 168 words
Related coverage
Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing
arXiv · Oct 5, 2026
Detecting Hallucination in LLMs: Tracing the Topological Signatures of Impaired Context Sharing
arXiv · Sep 22, 2026
Graph Trace Formula Links Quantum Probability to Curvature
Quantum Zeitgeist · Aug 1, 2026
Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective
arXiv · Oct 6, 2026