Source-linked AI summary
Understanding over-squashing and bottlenecks on graphs via curvature
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein
TL;DR
Message-passing GNNs can over-squash distant information when graph topology creates bottlenecks, but the phenomenon lacks a precise geometric account. The paper formalizes over-squashing with Jacobians, introduces Balanced Forman curvature, and proposes curvature-based rewiring; its experiments find that SDRF improves baseline node-classification performance across nine datasets while largely preserving topology. Theoretical results do not currently extend to multigraphs and the method ignores node features.
Problem
Over-squashing distorts distant messages in message-passing GNNs, while the graph bottlenecks causing it and the best remedy remain insufficiently understood.
Method
The paper uses node-representation Jacobians, introduces Balanced Forman curvature, proves its connection to negatively curved bottleneck edges, and develops SDRF rewiring.
Results
SDRF improves on the baseline in all nine node-classification datasets and matches or outperforms DIGL and +FA on most datasets.
Takeaways & Limitations
Curvature-based rewiring is supported as a viable way to improve GNN performance while more selectively modifying graph topology than DIGL.
Takeaways & Limitations
The theoretical results do not currently extend to multigraphs, and the methodology is agnostic to node features.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
GNNs use message passing to propagate information, but distant-node interactions can be distorted by graph bottlenecks. The paper develops a geometric account of over-squashing and proposes curvature-based rewiring to address it.
- GNNs and related geometric deep learning models commonly use message passing to diffuse information across graph structures.
- Over-squashing distorts messages from distant nodes, while the graph properties creating this effect are understood less precisely than other message-passing limitations.
- The paper formalizes over-squashing with node-representation Jacobians and identifies graph topology as a source of bottlenecks in message propagation.
- Balanced Forman curvature is introduced as an edge-based combinatorial curvature, with negatively curved edges linked theoretically to bottlenecks and over-squashing.
- Stochastic Discrete Ricci Flow is proposed as a curvature-based rewiring method that targets edges responsible for the bottleneck.
2 ANALYSIS OF THE OVER-SQUASHING PHENOMENON
The paper characterizes over-squashing through the sensitivity of node representations to distant input features. Bounded message and update derivatives connect this sensitivity to powers of the normalized adjacency matrix and graph topology.
- An r-layer message passing network at node i has receptive field B_r(i), the nodes within graph distance r.
- Over-squashing occurs when exponentially many receptive-field features must be compressed into fixed-size representations during long-range propagation.
- The Jacobian ∂h^(r)_i/∂x_s provides an explicit measure of how strongly a distant input feature affects a node representation.
- Bounded derivatives of message and update functions make message propagation controllable through powers of the augmented normalized adjacency matrix.
- On a binary-tree neighborhood, (Â^(r+1))_is = 2^-1 3^-r, demonstrating exponential decay of dependence on features at distance r.
- The sensitivity analysis motivates studying local graph properties and edge-based curvature as sources of the bottleneck.
3 GRAPH CURVATURE AND BOTTLENECK
The paper introduces Balanced Forman curvature to connect local graph geometry with bottlenecks and over-squashing. It proves that sufficiently negative-curvature edges create bottlenecks and motivates curvature-based rewiring and spectral control.
- Graph edge curvature is interpreted through discrete analogues of spherical, Euclidean, and hyperbolic geometries, corresponding to converging, parallel, and diverging structures.
- Balanced Forman curvature uses triangles, diagonal-free 4-cycles, and a degeneracy factor to describe an edge’s local neighborhood.
- The curvature of an edge is negative when it behaves as a bridge between neighboring shells and positive when those shells remain connected without the edge.
- For every edge, Ollivier curvature κ(i,j) is at least as large as Balanced Forman curvature Ric(i,j).
- Positive curvature everywhere bounds graph diameter and prevents sufficiently large-radius neighborhoods from expanding too rapidly.
- Edges with sufficiently high negative curvature create bottlenecks, causing many distance-two nodes to receive poorly propagated messages in two layers.
- A positive curvature lower bound gives λ_1/2 ≥ h_G ≥ k, linking curvature to the Cheeger constant and spectral gap.
4 CURVATURE-BASED REWIRING METHODS
The paper proposes curvature-guided graph rewiring that targets bottleneck-causing edges while preserving graph structure. It contrasts this surgical strategy with diffusion-based rewiring, which may fail to improve bottlenecks sufficiently.
- Curvature-based graph rewiring: SDRF rewires graphs by modifying strongly negatively curved edges to reduce bottlenecks and potentially alleviate over-squashing.The method is designed to change the edge structure without significantly compromising the input graph’s statistical properties.
- Curvature-based graph rewiring: At each iteration, SDRF adds a locally chosen edge supporting the most negatively curved edge, then removes the most positively curved edge when it exceeds an optional threshold.The added edge creates an extra 3- or 4-cycle around the negative edge, keeping the modification local.
- Curvature-based graph rewiring: The graph edit distance between the original and preprocessed graphs is bounded by twice the maximum number of iterations.
- Comparison with diffusion-based rewiring: Diffusion-based rewiring may not improve the Cheeger constant, and therefore the bottleneck, arbitrarily well.The limitation arises because random-walk methods prioritize short diffusion-distance connections and act more on intra-community than inter-community edges.
- Graph structure preservation: SDRF is intended to preserve topology better than random-walk rewiring by making targeted changes around negatively curved edges, often involving high-degree nodes.The paper links this surgical behavior to better preservation of statistical properties such as degree distribution.
- Homophily and bottleneck: DIGL is more naturally suited to high-homophily graphs, whereas SDRF is argued to be more suitable for low-homophily settings with important long-range dependencies.In low-homophily graphs, SDRF reduces bottlenecks without substantially increasing connections between different-label nodes.
5 EXPERIMENTAL RESULTS
Experiments compare SDRF with DIGL, +FA, and unprocessed or undirected graphs across nine node-classification datasets. SDRF improves over the baseline in all cases, performs competitively with the alternatives, and preserves degree distributions more closely than DIGL.
- Experiment setup: SDRF was evaluated against no preprocessing, undirected graphs, DIGL, and +FA on nine semi-supervised node-classification datasets.The evaluation used a GCN, 100 random data splits, separately optimized preprocessing-specific hyperparameters, and test accuracy with 95% bootstrap confidence intervals.
- Node classification results: SDRF improves upon the baseline in all cases, with the largest improvements on low-homophily datasets.
- Node classification results: SDRF matches or outperforms DIGL and +FA on most datasets, supporting curvature-based rewiring as a viable candidate for improving GNN performance.
- Graph topology change: DIGL makes graphs much denser for optimal performance, altering node degrees and potentially increasing downstream GNN time and space complexity.The reported complexity dependence is O(E).
- Graph topology change: SDRF preserves the original degree distribution more closely than DIGL, whose preprocessing has a more noticeable effect.The comparison uses kernel density estimates and the Wasserstein distance W1 between original and preprocessed degree distributions.
- Graph topology change: In the Cornell graph, SDRF largely preserves topology while curvature becomes more homogeneous and Jacobian entries to 2-hop neighbors increase.The paper attributes the Jacobian increase to the ability of both DIGL and SDRF to alleviate over-squashing.
6 CONCLUSION
The paper develops a geometric account of graph bottlenecks and over-squashing, linking negatively curved edges to over-squashing and proposing curvature-based rewiring. It reports theoretical and experimental advantages over diffusion-based rewiring, while noting limitations concerning multigraphs and node features.
- The paper uses a Jacobian-based analysis to connect graph topology, bottlenecks, and over-squashing in message passing GNNs.
- Balanced Forman curvature is introduced as an edge-based Ricci curvature and related to classical Ollivier curvature.
- Negatively curved edges are identified as responsible for over-squashing, motivating curvature-based graph rewiring.
- The proposed rewiring method is theoretically and experimentally advantageous compared with a diffusion-based rewiring approach.
- The theoretical results do not currently extend to multigraphs, and the methodology does not use information beyond graph topology, such as node features.
A PROOFS OF RESULTS IN SECTION 2
The proofs formalize how message-passing Jacobians depend on graph walks and show that distance and branching can attenuate information from distant nodes. They also clarify how self-loops and aggregation choices alter this dependence.
- For nodes at distance r+1, the Jacobian expansion retains only minimal walks joining the source and target nodes.
- Bounding the gradients of aggregation and update maps yields an upper bound on distant-node influence through products of layerwise derivatives.
- Without self-loops, a coefficient product is nonzero only when a walk has exactly the specified length; self-loops allow walks of at most that length.
- Without self-loops, a 2-layer simplified GNN output at node i is independent of neighbors k that do not form a triangle with i.
- On a tree, the derived influence bound decays exponentially as 2^−(r+1).
B PRELIMINARY ANALYSIS OF AN EDGE-NEIGHBORHOOD
This appendix constructs local edge-neighborhood quantities for curvature, focusing on triangles, diagonal-free 4-cycles, and tractable approximations to pairing counts. It also reviews existing curvatures and their limitations for representing graph neighborhoods.
- For an edge i ∼j, the analysis counts common neighbors forming triangles and neighbors participating in diagonal-free 4-cycles.
- The pairing-based quantity requires distinguishing all possible 4-cycles and selecting a maximal pairing map, making it computationally inconvenient.
- The quantity γmax measures the maximal degeneracy of edges forming 4-cycles and is designed as a computationally easier substitute for maximal pairing counts.
- Ollivier Ricci curvature is defined through probability measures on one-hop neighborhoods and a transportation distance based on graph geodesic distance.
- Augmented Forman curvature does not distinguish 4-cycle contributions; on an orthogonal grid of degree d ≥4 it equals 2(2−d)<0 despite polynomial r-hop neighborhood growth.
D PROOFS OF RESULTS IN SECTION 3
The proofs establish curvature bounds and connect graph bottlenecks to message-passing over-squashing through local topology, betweenness, and spectral properties.
- Theorem 2 proves that, for every edge in an unweighted graph, the new curvature κ(i, j) is at least the Balanced Forman curvature Ric(i, j).
- When an endpoint has degree one, the optimal transport plan gives zero Ollivier curvature, matching the Balanced Forman curvature.
- Curvature provides a more local and robust way to control bottlenecks than global betweenness, while positive Ricci curvature also lower-bounds the Cheeger constant and spectral gap.
- The bottleneck value bG averages node betweenness centrality; it is zero exactly for the complete graph Kn and decreases when edges are added.
E PROOFS OF RESULTS IN SECTION 4
These proofs relate personalized PageRank and graph conductance to bottlenecks, showing that sparsification can leave communities connected by few edges.
- The proof bounds the new Cheeger constant using the average and minimum degrees of S and the volume transferred by the personalized PageRank operator.
- For a set S with volume at most half the graph, Proposition 17 guarantees a subset S_k,α retaining at least vol(S)(1 − (2k)^−1) volume.
- After thresholding personalized PageRank entries, only few edges still connect different communities, highlighting the limitations of random-walk methods for graph bottlenecks.
F EXPERIMENTS
The experiments evaluate semi-supervised node classification across nine common graph-learning datasets using repeated random splits and held-out test evaluation.
- The experimental study uses semi-supervised node classification on nine graph-learning datasets, including small and medium heterophilic networks.
- Each of 100 random splits separates development and test data before random-search hyperparameter fitting on train and validation sets.
- Reported accuracy is the mean test accuracy, with a 95% confidence interval obtained by bootstrapping test accuracies with 1000 samples.
F.1 DATASETS
The experiments use nine semi-supervised node-classification datasets and compare multiple GCN preprocessing and architectural conditions, including SDRF, DIGL, and fully connected final layers.
- F.1 DATASETS: Nine datasets span WebKB, heterophily-focused, and citation/social-network benchmarks: Cornell, Texas, Wisconsin, Chameleon, Squirrel, Actor, Cora, Citeseer, and Pubmed.For disconnected graphs, reported statistics use the largest connected component.
- F.1 DATASETS: Figure 5 compares original and preprocessed degree distributions using log2 node degree, kernel density estimates, and Wasserstein distance W1.The figure assesses how preprocessing changes graph degree statistics.
- F.1 DATASETS: Figure 6 visualizes Cornell rewiring from the original graph to DIGL and SDRF, coloring edges by curvature and nodes by distant-feature Jacobian magnitude.The caption states that SDRF homogenizes curvature and lifts the Theorem 4 Jacobian upper bound, while DIGL does so partly at a topology-preservation cost.
- F.1 DATASETS: The evaluation compares no preprocessing, undirected inputs, SDRF preprocessing, DIGL preprocessing, and a fully connected final GCN layer.The supplied hyperparameter tables cover these experimental configurations and SDRF/DIGL variants.
- F.1 DATASETS: SDRF hyperparameters include maximum iterations, temperature τ, and C+, while SDRF plus undirected preprocessing is listed separately.These parameters are identified as the SDRF settings described in Algorithm 1.
G HARDWARE SPECIFICATIONS
The experiments ran on a 40-core Intel Xeon server with four GeForce RTX 3090 GPUs, 126GB RAM, and Ubuntu 20.04.2 LTS.
- G HARDWARE SPECIFICATIONS: The server used an x86_64 architecture with 40 Intel Xeon Silver 4210R CPU cores at 2.40GHz.
- G HARDWARE SPECIFICATIONS: The system included four GeForce RTX 3090 GPUs with 24268MiB per GPU, 126GB RAM, and Ubuntu 20.04.2 LTS.