pith. sign in

arxiv: 2604.12211 · v1 · submitted 2026-04-14 · 💻 cs.LG · cs.DS

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

Xiang Gu , Huichun Zhang , Jian Sun This is my paper

Pith reviewed 2026-05-10 15:41 UTC · model grok-4.3

classification 💻 cs.LG cs.DS
keywords Ollivier-Ricci curvaturelower boundWasserstein distancegraph curvaturerandom walkcomputational graph theoryapproximation algorithms
0
0 comments X

The pith

A residual-shell lower bound tightens estimates of Ollivier-Ricci curvature while remaining fast to compute.

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

This paper introduces a tighter lower bound for Ollivier-Ricci curvature on graphs by using a residual-shell correction to the Wasserstein distance. Previous lower bounds based on 1-hop random walks left large gaps to the exact value, limiting their use as proxies. The new approach reduces those gaps substantially and extends the bound to k-hop random walks. It achieves this with computation costs far below exact optimal transport calculations, offering speedups of tens of times on tested graphs.

Core claim

We establish a residual-shell-based lower bound for the Ollivier-Ricci curvature that is substantially tighter than the existing bound from 1-hop random walks, applies also to k-hop random walks, and can be computed much faster than the exact curvature while providing good approximation accuracy on fundamental graph structures.

What carries the argument

The residual-shell correction, which accounts for the probability mass not transported in the initial step to refine the lower bound on the Wasserstein distance between node neighborhoods.

Load-bearing premise

The residual-shell correction term preserves the lower-bound property for the Wasserstein distance without introducing looseness that cancels out the tightness improvement.

What would settle it

Run exact ORC computation and the new bound on a small cycle graph, then verify if the new bound exceeds the old lower bound but stays below the exact value for all edges.

Figures

Figures reproduced from arXiv: 2604.12211 by Huichun Zhang, Jian Sun, Xiang Gu.

Figure 1
Figure 1. Figure 1: Illustration of Erdős–Rényi (ER) graph, Barabási–Albert (BA) graph, Watts–Strogatz (WS) graph, and two￾dimensional grid graph (Grid). BA ER WS Grid 10 2 10 1 10 0 Time per edge (ms) Computational time BA ER WS Grid 0.0 0.2 0.4 Curvature gap Approximation error Exact KP-LB RS-LB [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: computational time cost of exact ORC computed using linear programming, the lower bounds including KP-LB [3] and our RS-LB, measured via runtime per edge. Right: approximation error of KP-LB and RS-LB, measured by mean absolute gap between bound and exact ORC. bounds. We can observe that our bound RS-LB takes more time than KP-LB, but still yields speedups of tens of times over the exact computation … view at source ↗
Figure 3
Figure 3. Figure 3: Histograms of the exact curvature and its lower bounds including KP-LB [3] and our derived RS-LB, on four graphs. The curves are the corresponding estimated density functions. 1 2 3 4 5 k 0 10 20 30 Time per edge (ms) Computation time Exact RS-LB 1 2 3 4 5 k 0.0 0.1 0.2 0.3 Curvature gap Approximation error [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Computational time and approximation error of RS-LB for ORC defined on 𝑘-hop random walks for varying 𝑘. We also evaluate our RS-LB on ORC defined on 𝑘-hop random walks. Note that KP-LB is not applicable to this 𝑘-hop setting [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
read the original abstract

Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, our bound is not restricted to 1-hop random walks, but also applies to k-hop random walks (k > 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of both approximation accuracy and computational efficiency.

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

3 major / 3 minor

Summary. The manuscript proposes a residual-shell-based correction to obtain a tighter lower bound on Ollivier-Ricci curvature (ORC) than the existing 1-hop random-walk bound. The construction is asserted to remain a valid lower bound on the 1-Wasserstein distance while extending directly to k-hop walks (k>1), delivering practical speedups of tens of times over exact ORC computation at far lower cost than the exact value. Empirical results on several fundamental graph structures are reported to demonstrate improved approximation accuracy and efficiency.

Significance. If the lower-bound property is rigorously established, the result would supply a useful practical proxy for ORC that improves tightness without sacrificing the computational advantage of prior bounds. The k-hop extension would further increase applicability in geometric graph analysis. The significance is currently limited by the absence of a complete derivation confirming that the correction term preserves the inequality for arbitrary graphs and k>1.

major comments (3)
  1. [§3] §3 (Residual-Shell Construction) and the subsequent proof sketch: the manuscript states the residual-shell term but supplies no explicit derivation showing that the added correction is guaranteed never to exceed the true W_1(μ,ν) for all measures arising from 1-hop or k-hop walks; the argument rests on the empirical observation that the term is non-negative on the tested graphs.
  2. [§4] k-hop extension (likely §4): no separate argument or induction is given establishing that the residual-shell correction continues to yield a valid lower bound when the random walks are taken over k>1 hops; the claim that the same construction applies without additional looseness is asserted rather than derived.
  3. [Experiments] Experimental evaluation (results section): the reported tightness gains and 'tens of times' speedups lack error bars, number of independent runs, or statistical tests, so it is impossible to assess whether the observed improvements are reliable across graph instances or merely artifacts of the chosen examples.
minor comments (3)
  1. [Abstract] The abstract and introduction should explicitly state the precise baseline (exact ORC or prior lower bound) against which the 'tens of times' speedup is measured and on which graph sizes the timing was performed.
  2. [§2] Notation for the residual-shell term and the modified probability measures should be introduced with a short self-contained definition before the main theorem to improve readability.
  3. [Experiments] A brief comparison table listing the new bound, the prior 1-hop bound, and exact ORC on the same small graphs would make the tightness claim immediately verifiable.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and will revise the manuscript to strengthen the theoretical arguments and experimental reporting.

read point-by-point responses

  1. Referee: [§3] §3 (Residual-Shell Construction) and the subsequent proof sketch: the manuscript states the residual-shell term but supplies no explicit derivation showing that the added correction is guaranteed never to exceed the true W_1(μ,ν) for all measures arising from 1-hop or k-hop walks; the argument rests on the empirical observation that the term is non-negative on the tested graphs.

    Authors: We acknowledge that the proof sketch in §3 is insufficient for a rigorous guarantee. In the revised manuscript we will replace the sketch with a complete, self-contained derivation proving that the residual-shell correction preserves the lower-bound property for arbitrary graphs and all 1-hop measures, without relying on empirical non-negativity. revision: yes

  2. Referee: [§4] k-hop extension (likely §4): no separate argument or induction is given establishing that the residual-shell correction continues to yield a valid lower bound when the random walks are taken over k>1 hops; the claim that the same construction applies without additional looseness is asserted rather than derived.

    Authors: We agree that a dedicated argument is required. The revised manuscript will include an explicit derivation (or inductive step) in §4 showing that the same residual-shell construction yields a valid lower bound for k-hop walks (k>1) on arbitrary graphs. revision: yes

  3. Referee: [Experiments] Experimental evaluation (results section): the reported tightness gains and 'tens of times' speedups lack error bars, number of independent runs, or statistical tests, so it is impossible to assess whether the observed improvements are reliable across graph instances or merely artifacts of the chosen examples.

    Authors: We accept this criticism. The revised results section will report error bars from multiple independent runs, state the number of runs performed, and include statistical tests to confirm that the observed gains in tightness and speed are reliable. revision: yes

Circularity Check

0 steps flagged

No circularity: residual-shell lower bound derived directly from Wasserstein definition without self-referential reduction

full rationale

The paper constructs a tighter lower bound on Ollivier-Ricci curvature by augmenting the prior 1-hop random-walk bound with a residual-shell correction term, then extends the same construction to k-hop walks. This is presented as a direct inequality manipulation starting from the definition of the 1-Wasserstein distance on the graph; the correction is asserted to be non-negative and to preserve the lower-bound property. No equation reduces by construction to a fitted parameter, a renamed input, or a load-bearing self-citation whose validity is presupposed. The central claim therefore remains an independent mathematical statement whose validity can be checked against the Wasserstein definition and graph geometry without circular reference to the paper's own outputs or prior results by the same authors. Experiments on fundamental graphs serve only as validation, not as the derivation itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract supplies no explicit free parameters, axioms, or invented entities; the bound is described as derived from the Wasserstein definition plus a residual-shell correction whose validity is asserted without further breakdown.

pith-pipeline@v0.9.0 · 5459 in / 1152 out tokens · 21603 ms · 2026-05-10T15:41:17.069923+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

  1. [1]

    Unfolding the multiscale structure of networks with dynamical ollivier-ricci curvature

    Gosztolai, A., Arnaudon, A., 2021. Unfolding the multiscale structure of networks with dynamical ollivier-ricci curvature. Nature Communications 12, 4561

    work page 2021

  2. [2]

    Ollivier’s ricci curvature, local clustering and curvature-dimension inequalities on graphs

    Jost, J., Liu, S., 2014. Ollivier’s ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete & Computational Geometry 51, 300–322

    work page 2014

  3. [3]

    Accelerated evaluation of ollivier-ricci curvature lower bounds: Bridging theory and computation

    Kang, W., Park, H., 2024. Accelerated evaluation of ollivier-ricci curvature lower bounds: Bridging theory and computation. arXiv preprint arXiv:2405.13302

    work page arXiv 2024

  4. [4]

    Ricci curvature of metric spaces

    Ollivier, Y., 2007. Ricci curvature of metric spaces. Comptes Rendus. Mathématique 345, 643–646

    work page 2007

  5. [5]

    Ricci curvature of markov chains on metric spaces

    Ollivier, Y., 2009. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis 256, 810–864

    work page 2009

  6. [6]

    Comparative analysis of two discretizations of ricci curvature for complex networks

    Samal, A., Sreejith, R., Gu, J., Liu, S., Saucan, E., Jost, J., 2018. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific reports 8, 8650. X. Gu, et al.:Preprint submitted to ElsevierPage 6 of 6

    work page 2018