# Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation

arXiv: https://arxiv.org/abs/2405.13302 · HTML: https://mlsanity.com/paper/2405.13302/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 22 references that are in the map.
- First posted on arXiv 22 May 2024.

## Builds on (most cited first, 7 of 7)

- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Ricci Curvature of the Internet Topology](https://mlsanity.com/paper/1501.04138/) (2015)
- [HypeBoy: Generative Self-Supervised Representation Learning on Hypergraphs](https://mlsanity.com/paper/2404.00638/) (2024)
- [Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework](https://mlsanity.com/paper/2210.12048/) (2022)
- [Curvature of Hypergraphs via Multi-Marginal Optimal Transport](https://mlsanity.com/paper/1803.08584/) (2018)
- [Evolution of Cooperation in the Presence of Higher-Order Interactions: from Networks to Hypergraphs](https://mlsanity.com/paper/2006.03893/) (2020)
- [All the World's a (Hyper)Graph: A Data Drama](https://mlsanity.com/paper/2206.08225/) (2022)

## Built on by (most cited first, 2 of 2)

- [Sobolev--Ricci Curvature](https://mlsanity.com/paper/2603.12652/) (2026)
- [A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature](https://mlsanity.com/paper/2604.12211/) (2026)

## Abstract (arXiv)

Curvature serves as a potent and descriptive invariant, with its efficacy validated both theoretically and practically within graph theory. We employ a definition of generalized Ricci curvature proposed by Ollivier, which Lin and Yau later adapted to graph theory, known as Ollivier-Ricci curvature (ORC). ORC measures curvature using the Wasserstein distance, thereby integrating geometric concepts with probability theory and optimal transport. Jost and Liu previously discussed the lower bound of ORC by showing the upper bound of the Wasserstein distance. We extend the applicability of these bounds to discrete spaces with metrics on integers, specifically hypergraphs. Compared to prior work on ORC in hypergraphs by Coupette, Dalleiger, and Rieck, which faced computational challenges, our method introduces a simplified approach with linear computational complexity, making it particularly suitable for analyzing large-scale networks. Through extensive simulations and application to synthetic and real-world datasets, we demonstrate the significant improvements our method offers in evaluating ORC.