From Proxy to Certificate: Two-Sided Ollivier-Ricci Bounds from Balanced Forman Curvature
Giorgio Micaletto, Tebe Nigrelli
stat.CO
Mar 13, 2026 · v6
cs.DM cs.LG math.CO math.DG
TL;DR
The main curvature bounds and the correctness of the certify-then-solve algorithm are formalized in Lean 4 with Mathlib, sorry-free, in a public repository.
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 $\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 $\mathtt{GraphRicciCurvature}$. The main results are machine-checked in Lean 4.
Problem
Balanced Forman (BF) curvature is used in graph learning as a cheap proxy for Ollivier-Ricci (OR) curvature, but it does not lower-bound OR curvature. It is unclear what a BF value actually certifies about the OR curvature of an edge.
Approach
Explicit optimal-transport couplings and Lipschitz test functions give two-sided transfer moduli from the BF value to the lazy OR curvature. A quadrangle-augmented Jost-Liu lower bound uses the matching number of the cross-edge graph, and BF is shown to equal this bound with its positive parts removed. A certify-then-solve algorithm resolves sign queries exactly, solving transport problems only on undecided edges. The main bounds and the algorithm's correctness are machine-checked in Lean 4 with Mathlib.
Results
On 23 benchmark graphs, the augmented bound is tighter than the Jost-Liu and Tian-Lubberts-Weber bounds on 13.8-100% of edges and reduces their mean gap to the exact curvature by a median of 31.2%. On 21 of the 23 graphs, intersecting it with the Tian-Lubberts-Weber bounds settles the curvature sign of more than half the edges. On 15 real networks with up to about 1M edges, certify-then-solve solves a median of 5.9 times fewer transport problems, for a median 2x speedup over exact evaluation with a fast min-cut solver.