From Proxy to Certificate: Two-Sided Ollivier-Ricci Bounds from Balanced Forman Curvature
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 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 over exact evaluation, measured against a min-cut solver that is itself about two orders of magnitude faster than the widely used . The main results are machine-checked in Lean 4.
Figures & tables
| Concept / Symbol | Definition / Formula |
|---|---|
| Neighborhood Sets | Common: ; Unique: (respectively ). |
| Degrees and Triangles | , ; . |
| Cross-Edge Graph ( ) | The bipartite graph with sides , and the edges of between them (the cross edges ); is its matching number (the size of a maximum matching), and is its maximum degree. |
| Cross-Edge Vertices ( ) | , the number of non-isolated vertices of , where (respectively ). |
| 4-Cycle Term | , and if . |
| Matching Statistic | . |
| Interval | Inputs | Cost | Used in |
|---|---|---|---|
| BF interval (Corollary 5.8 ) | , , | given , which costs | Sections 6.2 and 6.3 |
| 2-hop interval (Proposition 5.9 ) | , , , and | , dominated by one maximum matching of | First stage of certify-then-solve (Section 6.3 ) |
| Sharpened interval: the 2-hop interval intersected with (Section 6.1 ) | The above and the distances between and | , as above | Section 6.1 ; second stage of certify-then-solve |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Result | Lean | Module |
|---|---|---|
| Lemma 3.6 | C4_le_two_matchStat | Cover |
| Proposition 4.1 | mixing_transfer_paper , cLLY_le_q_paper | Paper |
| Corollary 4.2 | mixing_tf_paper , lamTF_closed | Paper |
| Theorem 4.3 | jl_aug , jl_aug_exact_of_perfect , cOR0_le_tri_div | Bounds , Exactness |
| Remark 4.4 , Appendix A | LBM_le_Lsq , LBM_eq_Lsq_iff | Appendix |
| Remark 4.5 | pos_part_sub_pos_part | Algebra |