pith. sign in

arxiv: 2603.13535 · v2 · submitted 2026-03-13 · 📊 stat.CO · math.CO· math.DG

Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature

Giorgio Micaletto , Tebe Nigrelli This is my paper

Pith reviewed 2026-05-15 12:14 UTC · model grok-4.3

classification 📊 stat.CO math.COmath.DG
keywords Ollivier-Ricci curvatureBalanced Forman curvaturegraph curvature boundsoptimal transportnetwork analysiscomputational efficiencylocal graph combinatorics
0
0 comments X

The pith

Deterministic bounds connect Ollivier-Ricci curvature to Balanced Forman curvature via local 2-hop graph features.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to bound the Ollivier-Ricci curvature of each graph edge using only the Balanced Forman curvature and simple counts from the two-hop neighborhood. It does this by building a lazy transport envelope and extending an existing bound with a cross-edge matching count, turning an expensive optimal transport calculation into a fast combinatorial one. This matters because many network analyses rely on curvature but become impractical on large graphs when every edge requires solving a linear program. The resulting bounds are validated to contain the true values across random and real-world networks without depending on global properties like degree distribution.

Core claim

By constructing a lazy transport envelope and augmenting the Jost and Liu bound with a cross-edge matching statistic, deterministic two-sided bounds are established for the Ollivier-Ricci curvature c_OR(i,j) that depend only on 2-hop local graph combinatorics. These bounds are piecewise-affine transfer moduli between the transport-based OR curvature and the combinatorial Balanced Forman curvature. The formulation reduces edgewise evaluation from an optimal transport linear program to O(max deg(v)^{1.5}) time.

What carries the argument

The lazy transport envelope augmented with a cross-edge matching statistic, which provides explicit two-sided bounds for Ollivier-Ricci curvature parameterized by local degrees and edge matchings.

If this is right

  • The per-edge curvature computation becomes feasible for large graphs by avoiding optimal transport solvers.
  • Bounds hold independently of degree heterogeneity, geometry, or clustering in the network.
  • Statistical network analysis using curvature can now scale to much larger datasets.
  • Validation confirms the analytical bands enclose empirical curvature distributions on tested graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar envelope techniques could be developed for other pairs of graph curvatures to further reduce computation.
  • The local nature of the bounds suggests potential for distributed or parallel curvature computation on massive networks.
  • Testing the bounds on dynamic graphs where edges change over time could reveal how curvature evolves locally.

Load-bearing premise

The lazy transport envelope and the cross-edge matching augmentation produce valid two-sided bounds that hold for arbitrary graphs.

What would settle it

Finding a specific graph and edge where the true Ollivier-Ricci curvature lies outside the derived lower and upper bounds.

Figures

Figures reproduced from arXiv: 2603.13535 by Giorgio Micaletto, Tebe Nigrelli.

Figure 1
Figure 1. Figure 1: Local, small-multiple illustrations around a fixed base edge [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Toy two-block stochastic block model (SBM) graphs illustrating assortative and [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Representative edgewise scatter plots. Blue points: sampled edges; black: median[cOR | cBF]; green (red) dash-dot: median of the lower (upper ) transfer cBF 7→ cOR. Panels: RGG, ER, WS, BA (left-to-right, top-to-bottom). 6.2 Open Problems and Future Directions A natural next step is to formalize the asymptotic behavior of the envelopes under geometric random graphs. For cOR, the limiting behavior is alread… view at source ↗
Figure 4
Figure 4. Figure 4: Representative edgewise scatter plots. Same styling as [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Distributional views. Top row (RGG): observed histograms (filled blue) against distributions induced by transfers (green/orange/red outlines) and by the coverage envelope (Proposition 3.11). Middle row (ER): sparse case where the lower distributions track the observed modes. Bottom row (WS): quantile profiles for observed series and their transferred counterparts, showing near-parallel separation and a vis… view at source ↗
read the original abstract

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 $\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 $\mathcal{O}(\max_{v \in V} \operatorname{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper derives explicit two-sided piecewise-affine bounds relating Ollivier-Ricci curvature c_OR(i,j) to Balanced Forman curvature. The construction augments the Jost-Liu inequality with a lazy transport envelope and a cross-edge matching statistic, yielding deterministic bounds parameterized solely by 2-hop local combinatorics. This reduces per-edge evaluation from an optimal-transport linear program to O(max_v deg(v)^{1.5}) time. The bounds are reported to enclose empirical curvature distributions on random graphs and real networks independently of degree heterogeneity, geometry, or clustering.

Significance. If the bounds are rigorously valid, the work supplies a scalable, solver-free surrogate for OR curvature that preserves deterministic guarantees. This would be a practical advance for statistical network analysis on large graphs where repeated OT solves are prohibitive, while also clarifying the relationship between combinatorial and transport-based curvatures.

major comments (2)
  1. The central claim that the lazy transport envelope plus cross-edge matching statistic produces valid two-sided bounds for arbitrary graphs rests on an unproven domination of the Wasserstein distance by the constructed affine envelope. No proof sketch, counter-example search, or explicit verification for 2-hop neighborhoods containing odd cycles or dense bipartite subgraphs is supplied; this is load-bearing for the deterministic guarantee asserted in the abstract.
  2. The validation consists of distributional enclosure checks on canonical random graphs and empirical networks, yet the manuscript provides neither the explicit closed-form expressions for the lower and upper moduli nor an error analysis quantifying how the cross-edge matching statistic affects tightness. Without these, it is impossible to confirm that the reported enclosure is not an artifact of post-hoc parameter choices or limited test graphs.
minor comments (2)
  1. Notation for Ollivier-Ricci curvature alternates between c_OR(i,j) and mathfrak{c}_OR(i,j); a single consistent symbol should be adopted.
  2. The complexity claim O(max_v deg(v)^{1.5}) should be accompanied by a precise breakdown of the matching step (e.g., which algorithm realizes the 1.5 exponent) and a statement of the hidden constants.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful and insightful comments on our manuscript. We provide point-by-point responses to the major comments below. We have revised the manuscript to address the concerns raised regarding the proof and the explicit expressions.

read point-by-point responses

  1. Referee: The central claim that the lazy transport envelope plus cross-edge matching statistic produces valid two-sided bounds for arbitrary graphs rests on an unproven domination of the Wasserstein distance by the constructed affine envelope. No proof sketch, counter-example search, or explicit verification for 2-hop neighborhoods containing odd cycles or dense bipartite subgraphs is supplied; this is load-bearing for the deterministic guarantee asserted in the abstract.

    Authors: We acknowledge that a more explicit proof sketch would strengthen the presentation. The derivation of the bounds is given in Section 3, but we have added a detailed proof in the revised version (new Appendix A) that includes the domination argument for the Wasserstein distance. We also include explicit verification for cases with odd cycles and dense bipartite subgraphs by constructing matching statistics and checking small instances, confirming the bounds hold. revision: yes

  2. Referee: The validation consists of distributional enclosure checks on canonical random graphs and empirical networks, yet the manuscript provides neither the explicit closed-form expressions for the lower and upper moduli nor an error analysis quantifying how the cross-edge matching statistic affects tightness. Without these, it is impossible to confirm that the reported enclosure is not an artifact of post-hoc parameter choices or limited test graphs.

    Authors: We agree that the explicit closed-form expressions and error analysis are necessary for full transparency. In the original manuscript, the expressions are derived but not presented in closed form separately from the construction. We have revised to include the explicit lower and upper bound formulas in Theorem 3.1 and added an error analysis subsection in Section 4 that quantifies the impact of the cross-edge matching statistic on bound tightness, with numerical results on the test set. Additional graphs have been included to mitigate concerns about limited test cases. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from external Jost-Liu inequality plus new combinatorial augmentation

full rationale

The derivation constructs a lazy transport envelope by augmenting the Jost-Liu bound (external citation) with a cross-edge matching statistic, then uses 2-hop combinatorics to produce explicit two-sided piecewise-affine bounds on Ollivier-Ricci curvature. No equation reduces by construction to a fitted parameter, self-definition, or self-citation chain; the central claim remains an independent combinatorial envelope rather than a renaming or ansatz imported from the authors' prior work. Validation on random graphs and empirical networks is distributional and does not involve predicting held-out data from a fit on the same quantities. This is self-contained against external benchmarks and receives score 0.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard properties of optimal transport on graphs and the existing Jost-Liu bound; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Optimal transport distance between node neighborhoods defines Ollivier-Ricci curvature
    Invoked in the definition of c_OR
  • domain assumption Jost and Liu bound provides a combinatorial lower bound on curvature
    Explicitly augmented in the paper

pith-pipeline@v0.9.0 · 5487 in / 1326 out tokens · 42203 ms · 2026-05-15T12:14:23.888083+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    By constructing a lazy transport envelope and augmenting the Jost and Liu bound with a cross-edge matching statistic, we establish deterministic bounds for c_OR(i,j) parameterized by 2-hop local graph combinatorics... reduces the edgewise evaluation complexity from an optimal transport linear program to a worst-case O(max_v deg(v)^{1.5}) time.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    URLhttps://doi.org/10.1007/s00454-013-9558-1

    doi: 10.1007/s00454-013-9558-1. URLhttps://doi.org/10.1007/s00454-013-9558-1. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks.Physical Review E, 82(3), September 2010. ISSN 1550-2376. doi: 10.1103/physreve.82.036106. URLhttp://dx.doi.org/10.1103/PhysRevE.82. 036106. Yong Lin,...

    work page doi:10.1007/s00454-013-9558-1 2010

  2. [2]

    ISBN 978-0130144003. Wayne W. Zachary. An information flow model for conflict and fission in small groups.Journal of Anthropological Research, 33(4):452–473, 1977. 26 Edgewise Envelopes Between Discrete Ricci Cur v atures Appendix A. Synthetic Graph Generators Erdős–RényiG(n, p) Rule:For every unordered pair{i, j}withi < j, include edge(i, j)independently...

    work page 1977

  3. [3]

    InitializeG m as the cliqueKm onV m ={1, . . . , m}

    work page

  4. [4]

    , n: (a) Add new vertext

    Fort=m+ 1, . . . , n: (a) Add new vertext. (b) Choosemdistinctendpointsu 1, . . . , um fromV t−1 without replacement, with sampling weights proportional to current degrees:P(u=u ⋆)∝deg Gt−1(u⋆). (c) Add edges(t, us)fors= 1, . . . , m(skip duplicates/self-loops by re-drawing)

    work page

  5. [5]

    Params:ntotal nodes;m∈ {1,

    ReturnG n. Params:ntotal nodes;m∈ {1, . . . , n−1}attachments per arriving node (controls mean degree and tail heaviness of degree distribution). The initial seed can be any connectedm-vertex graph; usingK m is standard. Watts–Strogatz small-worldWS(n, k,β) Pseudo-algorithm:

    work page

  6. [6]

    Start from a ring lattice: connect eachi∈[n]to itsk/2nearest neighbors on each side modulon(assumekis even and2≤k≤n−1)

    work page

  7. [7]

    clockwise

    Foreachdirected“clockwise” edge(i, i+d)withd∈ {1, . . . , k/2}: withprobability β,rewireits endpoint to a new nodejdrawn as j∼Unif [n]\ {i} ∪N(i) , otherwise keep the edge. Maintain simplicity (no multi-edges, no self-loops)

    work page

  8. [8]

    Params:nnodes;kinitial lattice degree (even);β∈[0,1]rewiring rate (β= 0gives a regular ring,β= 1approaches a random graph with short path lengths)

    Return the undirected version of the rewired graph. Params:nnodes;kinitial lattice degree (even);β∈[0,1]rewiring rate (β= 0gives a regular ring,β= 1approaches a random graph with short path lengths). Random geometric graphRGG(n, r) Rule:Samplex 1, . . . , xn i.i.d.∼Unif([0,1] 2). Connect(i, j)iff∥x i −x j∥2 ≤r 6. Params:npoints;r >0connection radius (cont...

    work page

  9. [9]

    27 Micaletto and Nigrelli Randomd-regularReg(n, d) Pseudo-algorithm:

    Euclidean metric in the unit square. 27 Micaletto and Nigrelli Randomd-regularReg(n, d) Pseudo-algorithm:

    work page

  10. [10]

    Require0≤d < nandndeven

    work page

  11. [11]

    Form a multiset ofstubs: a listScontainingdcopies of eachv∈[n]; uniformly shuffleS

    work page

  12. [12]

    WhileS̸=∅: (a) Pop one stubufromS

    InitializeE←∅. WhileS̸=∅: (a) Pop one stubufromS. (b) ScanSfor a partnerv̸=uwith{u, v}/∈E. (c) If no suchvexists,restart: discardE, rebuild and reshuffleS. (d) Otherwise remove thatvfromSand setE←E∪ {{u, v}}

    work page

  13. [13]

    Params:nnodes;dtarget degree

    Return the simple graphG= ([n], E). Params:nnodes;dtarget degree. Hyperbolic random graphHRG(n, R,α, T) Sampling:Draw anglesθ i ∼Unif[0,2π)and radiir i on[0, R]with density f(r) = αsinh(αr) cosh(αR)−1 . This yields a target power-law degree exponentγ= 2α+ 1. Distance:In curvature−1, the hyperbolic distance between nodesi, jis coshd ij = coshr i coshr j −s...

    work page

  14. [14]

    , nk)be block sizes and index vertices contiguously by blocks (offsetso c =P a<c na)

    Letn= (n 1, . . . , nk)be block sizes and index vertices contiguously by blocks (offsetso c =P a<c na)

    work page

  15. [15]

    28 Edgewise Envelopes Between Discrete Ricci Cur v atures (b) Setp←p in ifc(i) =c(j), elsep←p out

    For every unordered pair{i, j}withi < j: (a) Letc(i)andc(j)be the blocks ofiandj. 28 Edgewise Envelopes Between Discrete Ricci Cur v atures (b) Setp←p in ifc(i) =c(j), elsep←p out. (c) Include edge(i, j)independently with probabilityp(setA ij =A ji;A ii = 0)

    work page

  16. [16]

    Params:n;p in, pout ∈[0,1](assortative ifp in > p out, disassortative otherwise)

    Return the undirected simple graphG. Params:n;p in, pout ∈[0,1](assortative ifp in > p out, disassortative otherwise). CycleC n Rule:Vertices1, . . . , nwith edges(i, i+ 1)fori= 1, . . . , ninterpretingn+ 1≡1. Param:n≥3nodes (2-regular). GridGrid(L x, Ly) Rule:Vertex set{1, . . . , L x} × {1, . . . , Ly}with edges between lattice neighbors atℓ1 distance1(...

    work page

  17. [17]

    , L x} × {1,

    Vertex setV={1, . . . , L x} × {1, . . . , Ly}

    work page

  18. [18]

    For each(i, j)∈V, add undirected edges to (imodL x) + 1, j and i,(jmodL y) + 1

    work page

  19. [19]

    Params:L x, Ly ∈N(4-neighbor connectivity with periodic boundary conditions)

    ReturnG= (V, E). Params:L x, Ly ∈N(4-neighbor connectivity with periodic boundary conditions). d-ary treeTree(d, h) Pseudo-algorithm:

    work page

  20. [20]

    Create rootρat level0

    work page

  21. [21]

    , h−1, give every node at levelℓexactlydchildren at levelℓ+1and connect parent to children

    Forℓ= 0, . . . , h−1, give every node at levelℓexactlydchildren at levelℓ+1and connect parent to children. Params:d≥2branching factor; heighth≥1(levels0, . . . , h). Total nodes= dh+1−1 d−1 (full tree). CompleteK n Rule:Include every edge between distinct vertices; i.e.,E= [n] 2 . Param:nnodes (maximally dense). 29 Micaletto and Nigrelli Appendix B. Defer...

    work page

  22. [22]

    Otherwisex∈N(i)andy∈N(j), so(x, y)must belong to exactly one of the three mutually exclusive types:Ui−Uj (inE UU),U−C(inE △), orC−C(inE CC)

    If{x, y} ∩ {i, j} ̸=∅we are inE end. Otherwisex∈N(i)andy∈N(j), so(x, y)must belong to exactly one of the three mutually exclusive types:Ui−Uj (inE UU),U−C(inE △), orC−C(inE CC). Disjointness is immediate from the disjointness of{i},{j},Ui,U j, and C; exhaustivity follows from the above case split. 38 Edgewise Envelopes Between Discrete Ricci Cur v atures ...

    work page 2001

  23. [23]

    finite maximizer

    At most all neighbors except the opposite endpoint can be common. 46 Edgewise Envelopes Between Discrete Ricci Cur v atures withA min, Cα defined in (4.6),(4.9). Applying the two sources in (4.5) and dividing byΣ(α) i,j gives Ξij Σ(α) i,j ≤min n Bα(△(i, j)), D α(△(i, j)) o , withB α, Dα as in (4.7),(4.8). Therefore m(α) UU ≤min{A min(△), B α(△), D α(△)}, ...

    work page