Understanding over-squashing and bottlenecks on graphs via curvature
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 int...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
OpenReview
2022
|
| _version_ | 1797110448876683264 |
|---|---|
| author | Topping, J Di Giovanni, F Chamberlain, BP Dong, X Bronstein, M |
| author_facet | Topping, J Di Giovanni, F Chamberlain, BP Dong, X Bronstein, M |
| author_sort | Topping, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:55:01Z |
| format | Conference item |
| id | oxford-uuid:c1f6c5bb-428f-471a-a6d3-e5ca24efbd90 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:55:01Z |
| publishDate | 2022 |
| publisher | OpenReview |
| record_format | dspace |
| spelling | oxford-uuid:c1f6c5bb-428f-471a-a6d3-e5ca24efbd902023-08-08T16:28:08ZUnderstanding over-squashing and bottlenecks on graphs via curvatureConference itemhttp://purl.org/coar/resource_type/c_5794uuid:c1f6c5bb-428f-471a-a6d3-e5ca24efbd90EnglishSymplectic ElementsOpenReview2022Topping, JDi Giovanni, FChamberlain, BPDong, XBronstein, MMost 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. |
| spellingShingle | Topping, J Di Giovanni, F Chamberlain, BP Dong, X Bronstein, M Understanding over-squashing and bottlenecks on graphs via curvature |
| title | Understanding over-squashing and bottlenecks on graphs via curvature |
| title_full | Understanding over-squashing and bottlenecks on graphs via curvature |
| title_fullStr | Understanding over-squashing and bottlenecks on graphs via curvature |
| title_full_unstemmed | Understanding over-squashing and bottlenecks on graphs via curvature |
| title_short | Understanding over-squashing and bottlenecks on graphs via curvature |
| title_sort | understanding over squashing and bottlenecks on graphs via curvature |
| work_keys_str_mv | AT toppingj understandingoversquashingandbottlenecksongraphsviacurvature AT digiovannif understandingoversquashingandbottlenecksongraphsviacurvature AT chamberlainbp understandingoversquashingandbottlenecksongraphsviacurvature AT dongx understandingoversquashingandbottlenecksongraphsviacurvature AT bronsteinm understandingoversquashingandbottlenecksongraphsviacurvature |