2026/03/13 by Giorgio Micaletto, Tebe Nigrelli · 1 voice
Mathematics · #stat.CO #math.CO #math.DG
arxiv published 2026/03/13 · arxiv updated 2026/04/13
Evaluating Ollivier-Ricci (OR) curvature on large-scale graphs is computationally prohibitive due to the necessity of solving an optimal transport problem for every edge. We bypass this computational bottleneck by deriving explicit, two-sided, piecewise-affine transfer moduli between the transport-based OR curvature and the combinatorial Balanced Forman (BF) curvature introduced by Topping et al. By constructing a lazy transport envelope and augmenting the Jost and Liu bound with a cross-edge matching statistic, we establish deterministic bounds for \mathfrakcOR(i,j) parameterized by 2-hop local graph combinatorics. This formulation reduces the edgewise evaluation complexity from an optimal transport linear program to a worst-case O(maxv ∈ V deg(v)1.5) time, entirely eliminating the reliance on global solvers. We validate these bounds via distributional analyses on canonical random graphs and empirical networks; the derived analytical bands enclose the empirical distributions independent of degree heterogeneity, geometry, or clustering, providing a scalable, computationally efficient framework for statistical network analysis.