stat.COMar 13, 2026

From Proxy to Certificate: Two-Sided Ollivier-Ricci Bounds from Balanced Forman Curvature

Authors: Giorgio Micaletto, Tebe Nigrelli

Organizations: Department of Statistics University of Chicago Chicago, IL 60637-1514, USA · Department of Computing Sciences Bocconi University Via Roberto Sarfatti 25, 20136 Milan, Italy

Abstract

Balanced Forman (BF) curvature is used in graph learning as a cheap stand-in for Ollivier-Ricci (OR) curvature, yet it does not lower-bound OR curvature. We show that the BF value of an edge certifies a two-sided interval for its lazy OR curvature without solving any optimal transport problem, that BF coincides with a quadrangle-augmented Jost-Liu (JL) bound with its positive parts removed, and that when the 2-hop neighborhood is available, the interval can be sharpened at a cost of O(dmax⁡2.5)\mathcal O(d_{\max}^{2.5}) per edge. On 23 benchmark graphs, our quadrangle-augmented bound is tighter than the bounds of JL and Tian-Lubberts-Weber (TLW) on 13.8-100% of the edges and reduces their mean gap to the exact curvature by a median of 31.2%; intersected with the bounds of TLW, the intervals settle the curvature sign of more than half of the edges on 21 of the 23 graphs. On 15 real networks with up to 1,049,866 edges, a certify-then-solve procedure answers sign queries exactly while solving a median of 5.9 times fewer transport problems, for median speedups of 2×\times over exact evaluation, measured against a min-cut solver that is itself about two orders of magnitude faster than the widely used GraphRicciCurvature\mathtt{GraphRicciCurvature}. The main results are machine-checked in Lean 4.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Transport-Free Lower Bounds for Ollivier--Ricci Curvature in Higher-Order Networks: Scope, Tightness, and Computational Applications

    May 22, 2024Wonwoo Kang, Heehyun ParkOllivier-Ricci Curvature

  2. Ollivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural Networks

    Apr 6, 2026Eleanor P WieslerOllivier-Ricci CurvatureRiemannian Geometry

  3. A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

    Apr 14, 2026Xiang Gu, Huichun Zhang, Jian SunOllivier-Ricci CurvatureApproximation Algorithms