Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature

Giorgio Micaletto [email protected], Tebe Nigrelli [email protected] · 2026

Read Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature by Giorgio Micaletto [email protected], Tebe Nigrelli [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13535.txt.

Introduction

Giorgio Micaletto and Tebe Nigrelli link Balanced Forman curvature to Ollivier-Ricci curvature on graphs. Computing Ollivier-Ricci curvature is costly, since each edge needs an optimal transport solve. They derive explicit two-sided, piecewise-affine transfer moduli between the transport-based and combinatorial curvatures. The bounds use only 2-hop local graph combinatorics, cutting edgewise cost a lot and removing global solvers. Benchmarks confirm large speedups over exact evaluation. Tests on random graphs and real networks show the bands hold widely.

Catalog record

CREATORGiorgio Micaletto [email protected], Tebe Nigrelli [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123372
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13535

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature Giorgio Micaletto [email protected], Tebe Nigrelli [email protected] Abstract Evaluating 15 (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 23 ’s combinatorial Balanced Forman (BF) curvature. By constructing a lazy transport envelope and augmenting the 10 bound with a cross-edge matching statistic, we establish deterministic bounds for 𝔠 O ​ R ​ ( i , j ) \mathfrak{c}_{OR}(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 𝒪 ⁡ ( max v ∈ V ⁡ deg ⁡ ( v ) 1.5 ) \mathcal{O}(\max_{v\in 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. Giorgio Micaletto, Tebe Nigrelli † † heading: XX 2026 1- XX/XX; Revised XX/XX XX/XX XX-XXXX † † shortheadings: Edgewise Envelopes Between Discrete Ricci Curvatures / Micaletto, Nigrelli † † firstpage: 1 keywords Ollivier–Ricci curvature; Balanced Forman curvature; scalable network analysis; computational graph theory; optimal transport on graphs; empirical curvature distributions. 1 Introduction Discrete analogues of Ricci curvature on graphs have become popular tools in both network science and geometry processing. Two main families account for the majority of approaches in this area: (i) transport-based coarse Ricci curvatures, introduced by 15 (OR) and extended by 12 (LLY), which notably converge to smooth Ricci curvature in the setting of random geometric graphs ( 14 ; 24 ) ; and (ii) combinatorial curvatures in the sense of 6 (FR), together with their network adaptations and extensions incorporating n -cycles ( 19 ; 27 ; 17 ) (AFR). The literature includes several empirical studies on comparing these notions across graph models and real networks, often reporting substantial, but not universal, agreement while also highlighting regimes where they differ ( 20 ; 17 ; 18 ) . From a transport perspective, OR curvature increases when local motifs, such as triangles and quadrangles, reduce the Wasserstein cost between one-step measures ( 10 ; 4 ) , while by contrast, FR and its variants are designed in a purely combinatorial fashion to reward the presence of recurring motifs ( 19 ; 27 ) . Recent work has attempted to reconcile these two perspectives: 23 introduced Balanced Forman curvature (BF), a combinatorial edge-based notion that provides a sharp lower bound for LLY curvature on graphs, while other studies have proposed extensions of Forman curvature aimed at bringing it into closer alignment with OR in applications ( 22 ; 17 ) . Positioning of This Work. To the best of the authors’ knowledge, despite many empirical comparisons, there is no analytic, two-sided relation between transport-based and combinatorial curvatures at the edge level on general graphs. Our contribution is to develop a lazy transport envelope that upper-bounds the edgewise Wasserstein–1 cost by isolating (i) zero-cost matches, (ii) endpoint residuals, and (iii) cross-edge unit-cost flow. This yields an explicit, coupling-free, piecewise-affine envelope for OR curvature as a function of degrees, laziness, triangle count, and a 4-cycle coverage (Proposition 3.6 ). Building on the BF identity and a sharper version of 10 ’s lower bound (Theorem 3.7 ), we obtain two-sided, edgewise transfer moduli between BF and OR. Upper transfer from BF to OR is obtained directly from the envelope (Theorem 4.2 ), while lower transfer from BF follows from the sharpened bound (Theorem 4.1 ). In the reverse direction, the envelope implies a necessary triangle threshold that turns OR lower bounds into BF lower bounds (Theorem 4.3 ), and inverting the inequality of Theorem 3.7 yields an OR to BF upper transfer (Theorem 4.4 ). What We Mean by “Transfer Moduli”. We define edgewise transfer moduli as pairs of nondecreasing functions, \varphi^{(i,j)} and \psiit^{(i,j)} , that convert a bound on one curvature into a bound on the other. For \mathfrak{c}_{\rm BF}\to\mathfrak{c}_{\rm OR} , and symmetrically for \mathfrak{c}_{\rm OR}\to\mathfrak{c}_{\rm BF} , we require: \displaystyle\mathfrak{c}_{\rm BF}(i,j)\geq\zetait\ \implies\mathfrak{c}_{\rm OR}(i,j)\geq\varphi^{(i,j)}_{\rm BF\to OR}(\zetait), \displaystyle\mathfrak{c}_{\rm BF}(i,j)\leq\vartheta\ \implies\mathfrak{c}_{\rm OR}(i,j)\leq\psiit^{(i,j)}_{\rm BF\to OR}(\vartheta). The strength of our theoretical result lies in the tightness of the derived moduli: they are piecewise-affine functions parameterized by the local combinatorics of G (degrees, triangles, and 4 -cycles). By encoding the specific geometric bottlenecks that constrain mass transport, these moduli offer a significant improvement over naive bounds, “transferring” the input curvature value into a sharp estimate for the target curvature. Furthermore, because the parameters of these functions depend solely on 2-hop neighborhoods, they are explicit and computable in worst-case \mathcal{O}(\max_{v\in V}\deg(v)^{1.5}) amortized time without solving the optimal transport problem, allowing us to generate “bounding bands” that enclose the empirical curvature distributions observed in Section 5 . Distributional Predictions and Experimental Scope. Our goal is to understand how edgewise curvatures are distributed within a graph and which mechanisms shape those distributions. We therefore examine full empirical histograms of OR and BF curvature and compare them to the transfer bounds described above. The bounds are plotted as envelopes that act as “bounding bands” for the observed distributions, complementing prior comparative work that emphasized edgewise scatter plots and rank correlations ( 20 ; 17 ) . We group our testbeds into three families that isolate distinct drivers of curvature: (i) Random graph models that control degree heterogeneity, clustering, and geometry: (a) Erdős–Rényi G(n,p) , which provides a neutral baseline with low clustering and light-tailed degrees (for the studied case of p\approx c/n ); OR mass concentrates near nonpositive values, and BF tracks degrees tightly ( 5 ) . (b) Watts–Strogatz small–world graphs, which interpolates between lattice-like clustering and random rewiring, letting us sweep from positive-OR, triangle-rich regimes to sparse-overlap regimes ( 26 ) . (c) Barabási–Albert preferential attachment, which introduces heavy-tailed degrees; hubs broaden BF and create many low-overlap, hub–periphery edges that create a heavier negative OR tail. ( 1 ) . (d) Random geometric graphs in \mathbb{R}^{d} , which add an explicit Euclidean geometry: spatial proximity induces clustering and short-range transport, linking OR to geometric overlap and providing a pathway to smooth-limit interpretations ( 16 ; 24 ) . (e) Random d -regular simple graphs, which fix degrees and are locally tree-like, with BF collapsing to a narrow band, and the scarcity of triangles pushes OR toward negative values, isolating degree effects from clustering ( 21 ) . (f) Homogeneous Stochastic Block Models (SBM), which inject controlled community structure: within-block edges have many shared neighbors (OR higher), while cross-block edges do not (OR lower). The disassortative regime stresses the lower envelope and approaches bipartite structure ( 9 ) . (g) Hyperbolic random graphs (HRG), which combine heavy-tailed degrees with latent negative curvature in the embedding space, providing a geometric foil where OR skews negative away from dense cores and BF spreads with degree ( 11 ) . (ii) Canonical combinatorial families that provide clean baselines and extremes: (a) Cycles , that realize a one-dimensional “flat” baseline with uniform local structure. (b) Rectangular grids that expose boundary

Read the complete text