Curvature Based Graph Rewiring for Information Flow

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 255 papers76 conceptsfrozen 2026-10-04

Graph Neural Networks (GNNs) suffer from a fundamental "traffic jam" problem. As a model attempts to aggregate information from distant nodes, the signals must pass through structural bottlenecks—edges or nodes that connect large, otherwise isolated clusters. When too much information is forced through these narrow channels, it is compressed into a fixed-size vector and lost, a phenomenon known as over-squashing. Conversely, in very dense regions, repeated message passing causes node features to become indistinguishable, leading to over-smoothing.

Recent research has shown that these issues are not just accidental artifacts of architecture but are deeply rooted in the discrete geometry of the graph. By treating the graph as a curved manifold rather than a flat set of connections, researchers have developed "surgical" rewiring techniques that modify the graph's topology to optimize the flow of information.

The Geometry of Bottlenecks

In differential geometry, curvature describes how a space deviates from being "flat." On a graph, we use discrete analogues like Ollivier-Ricci Curvature or Forman-Ricci Curvature to characterize local connectivity.

  • Negative Curvature (The Bottleneck): An edge has negative curvature if it acts as a "bridge" between two regions that are not otherwise well-connected. These are the primary sites of over-squashing. Jake Topping, Francesco Di Giovanni, and Michael M. Bronstein demonstrated in Understanding over-squashing and bottlenecks on graphs via curvature that these negatively curved edges are mathematically responsible for the decay of information as it travels across the network.
  • Positive Curvature (The Cluster): An edge has positive curvature if it belongs to many triangles or dense cliques. While these regions are robust, they are prone to over-smoothing, where the "community" signal overwhelms the individual node features.

By identifying these geometric signatures, we can diagnose exactly where a GNN will fail before training even begins.

Surgical Rewiring: SDRF and BORF

The core idea of curvature-based rewiring is to "flatten" the graph's computational landscape. If a bottleneck is identified (negative curvature), we add a "shortcut" edge to provide an alternative path for information. If a region is too dense (positive curvature), we may remove edges to prevent feature homogenization.

The SDRF (Stochastic Discrete Ricci Flow) algorithm, proposed by Topping et al., iteratively adds edges to regions of high negative curvature. This process increases the "Balanced Forman Curvature," effectively widening the pipes through which messages flow.

Building on this, Nhat Ho and Khang Nguyen introduced BORF in Revisiting Over-smoothing and Over-squashing using Ollivier's Ricci Curvature. BORF employs a dual-action mechanism: it adds edges to alleviate over-squashing and removes edges in positively curved areas to combat over-smoothing. This balanced approach ensures that the graph remains expressive without becoming a "hairball" of redundant connections.

Why Triangles Matter

Many of these methods, such as TRIGON by Hugo Attali and Nathalie Pernelle, focus on triangulation. In Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks, the authors argue that adding edges to form triangles increases the local Forman curvature and lowers the "effective resistance" between nodes.

Intuitively, a triangle is the simplest stable geometric structure that provides redundancy. If one edge in a triangle is a bottleneck, the other two edges provide a bypass. This geometric intuition is even being extended to higher-order structures like simplicial complexes, where Diaaeldin Taha and James Chapman show that over-squashing can be mitigated by optimizing the relational structures beyond simple pairwise edges Demystifying Topological Message-Passing with Relational Structures.

Efficiency and Scalability

A major hurdle for curvature-based methods is computational cost; calculating Ricci curvature for every edge can be expensive. To address this, Anthea Monod and Kevin N. Webster demonstrated that "classical" discrete geometry metrics can achieve similar results with significantly lower overhead Rewiring Networks for Graph Neural Network Training Using Discrete Geometry. Similarly, the AFR-k method uses an augmented version of Forman-Ricci curvature that can be computed in linear time, making curvature-aware rewiring feasible for massive datasets Mitigating Over-smoothing and Over-squashing using Augmentations of Forman-Ricci Curvature.

Beyond Static Graphs

The principles of curvature-based rewiring are now expanding into dynamic domains:

  • Temporal Graphs: Katarina Petrovic and Petar Veličković introduced Temporal Graph Rewiring (TGR), using expander graphs to create "message-passing highways" across time steps Temporal Graph Rewiring with Expander Graphs.
  • Physics-Informed Models: Frameworks like UYGNN treat graph propagation as a physical system where "virtual nodes" act as gravitational sources to pull relevant information across bottlenecks Design Your Own Universe.

By shifting the focus from the architecture of the neural network to the geometry of the data, this research direction provides a principled, mathematically grounded way to build GNNs that can finally "see" the big picture without losing the details in the traffic.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 42 papers
  2. Version 1 · 2026-10-04 · 55 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curvature_based_graph_rewiring_8a71ff1f,
  title = {curvature-based graph rewiring},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curvature-based-graph-rewiring/rdr_8a71ff1f9c4b4089bf257f261e6d1082},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_curvature_based_graph_rewiring_for_infor_8a71ff1f_v1,
  title = {Curvature Based Graph Rewiring for Information Flow},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curvature-based-graph-rewiring-for-information-flow/rdr_8a71ff1f9c4b4089bf257f261e6d1082/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}