Understanding over-squashing and bottlenecks on graphs via curvature

Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein
11/29/2021
stat.MLcs.LG

Official code: jctops/understanding-oversquashing (43 stars, MIT, last commit 2022-07-03).

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.

View on arXivView PDF

Code Implementations(1)

jctops/understanding-oversquashingOfficial100%
MIT
438Shell, PythonMay 10, 20224 years agoMIT

Similar Papers

Rewiring Networks for Graph Neural Network Training Using Discrete Geometry

90% match2022

Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature

89% match2023

On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology

89% match1 repo162023

Over-Squashing in Riemannian Graph Neural Networks

88% match2023

Curvature-based Pooling within Graph Neural Networks

88% match2023

Probing Graph Neural Network Activation Patterns Through Graph Topology

88% match2026

Cite this paper

@article{topping2021understanding,
  title  = {Understanding over-squashing and bottlenecks on graphs via curvature},
  author = {Jake Topping and Francesco Di Giovanni and Benjamin Paul Chamberlain and Xiaowen Dong and Michael M. Bronstein},
  year   = {2021},
  eprint = {2111.14522},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2111.14522}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2111.14522.svg)](https://codeofpaper.com/paper/2111.14522)

Discussion