Graph Neural Networks (GNNs) rely on message passing to aggregate information from a node's neighborhood. However, this architecture suffers from a fundamental structural limitation known as over-squashing. As the number of layers increases to capture long-range dependencies, the volume of information from an exponentially growing neighborhood must be compressed into fixed-size node vectors. When this information encounters a structural bottleneck—a narrow path or a bridge between dense communities—the signal becomes severely distorted or lost. Conversely, in highly dense regions, features can quickly homogenize, leading to over-smoothing.
To solve these topological bottlenecks, researchers have turned to differential geometry, using the concept of discrete graph curvature to surgically rewire graphs and optimize information flow.
The Geometric Intuition of Graph Curvature
In smooth geometry, curvature describes how a space behaves locally. Negative curvature characterizes hyperbolic spaces that branch out exponentially (like a saddle), while positive curvature characterizes spherical spaces that close in on themselves.
On a discrete graph, this intuition translates directly to local connectivity patterns:
- Negative Curvature: An edge has highly negative curvature if its endpoints share few or no common neighbors. These edges act as bridges or structural bottlenecks between distinct communities.
- Positive Curvature: An edge has positive curvature if its endpoints are tightly clustered and share many mutual neighbors, typically forming triangular motifs.
Negative Curvature (Bridge/Bottleneck) Positive Curvature (Cluster/Triangles)
O O O-------O
\ / / \ / \
O-----------O / \ / \
/ \ O-----O-----O
O O
Several formulations of discrete curvature have been adapted to graphs, including Ollivier-Ricci curvature, Forman-Ricci curvature, and Angle-Based Sectional (ABS) curvature (Pei et al.). As Topping and Di Giovanni formally demonstrated, negative combinatorial curvature (specifically Balanced Forman curvature) provides a precise mathematical bound on the sensitivity of message passing. It identifies the exact edges responsible for over-squashing, where the volume of incoming information exceeds the topological path capacity.
Surgical Rewiring via Ricci Flow
Once these bottlenecks are identified, how do we alleviate them? The most prominent strategy is graph rewiring—altering the graph's underlying topology to optimize information flow before or during GNN training.
Instead of global modifications that alter the entire graph indiscriminately, curvature allows for a "surgical" approach. Topping and Di Giovanni introduced Stochastic Discrete Ricci Flow (SDRF), an algorithmic framework that iteratively adds shortcut edges to form cycles around negatively curved bottlenecks. This process mimics the continuous "Ricci flow" used in physics to smooth out geometric deformations. By adding these shortcuts, the local curvature increases, providing alternative pathways for message passing and reducing the compression of long-range dependencies.
Similarly, Nguyen et al. demonstrated that adding shortcuts specifically at high negative curvature locations allows models to scale to greater depths without performance degradation, effectively mitigating both over-squashing and over-smoothing simultaneously. Li Sun et al. showed that applying backward Ricci flow widens narrow paths by increasing the graph's Cheeger constant (a measure of global connectivity), which enhances global conductance and long-range information propagation.
Balancing the Topology: Dual-Action Rewiring
Alleviating over-squashing by adding edges risks accelerating over-smoothing if the graph becomes too dense. To maintain this delicate balance, several frameworks employ dual-action rewiring that both adds and removes edges based on geometric profiles.
Fesser and Weber developed AFR-k, a scalable method using Augmented Forman-Ricci Curvature. AFR-k adds edges to negative-curvature regions to relieve bottlenecks and prunes edges in high-curvature regions to prevent feature homogenization. A similar stochastic approach balancing edge addition and removal based on discrete curvature and embedding distances was proposed by Skianis et al..
To bypass expensive global spectral computations, Banerjee et al. introduced the Greedy Random Local Edge Flip (G-RLEF) algorithm. They leveraged the insight that targeting edges with low triangle counts serves as an effective local proxy for smoothing negative curvature and increasing the graph's spectral gap without requiring global spectral analysis.
Triangulation and Motif-Driven Geometry
Rather than just modifying individual edges, some researchers propose restructuring the graph using geometric motifs, particularly triangles. Triangles naturally increase local connectivity and discrete curvature, which lowers the effective resistance between nodes.
Attali et al. developed TRIGON, a framework that dynamically selects relevant triangles across multiple graph views. By relaxing planarity constraints, TRIGON introduces long-range shortcuts that drastically reduce the graph diameter and clear information congestion. Taking this to the extreme, Attali proposed Delaunay Rewiring (DR), which completely reconstructs the graph topology using Delaunay Triangulation on node features. This geometric constraint ensures that no point lies within the circumcircle of any triangle, resulting in a perfectly balanced Ricci curvature that eliminates structural bottlenecks.
Broad Applications of Geometric Rewiring
Curvature-based graph optimization has proven vital across diverse domains where preserving structural fidelity is critical:
- Fluid Dynamics: In mesh-based simulations, standard GNNs often blur fine-grained physical features due to over-squashing across dense meshes. Seo et al. utilized Ollivier-Ricci curvature to dynamically rewire dense meshes, preserving distinct physical boundaries like turbulent flows.
- Biomedical and Molecular Graphs: Zhou applied discrete Ricci flow to causal graphs derived from fMRI data to optimize brain network topologies for disease classification. In molecular dynamics, Guo et al. fused static protein structures with dynamic motion data to increase the positive curvature of the network, preventing signal loss in deep architectures.
- Topology Imbalance: When labels are unevenly distributed, supervision signals can fail to propagate across sparse regions. Jianxin Li et al. used negative Ricci curvature to identify the precise "bridge edges" causing this topology-imbalance, adjusting connectivity to ensure uniform information flow.
Key Foundational Work
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus (2011) — contributed 1 concept elements to this direction.
Curvature Regularization to Prevent Distortion in Graph Embedding (2020) — contributed 1 concept elements to this direction.