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

• URL: http://arxiv.org/abs/2604.12211v1
• Date: Tue, 14 Apr 2026 02:40:15 GMT
• Title: A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
• Abstract summary: Ollivier-Ricci curvature (ORC) is defined via the Wasserstein distance that captures rich geometric information.<n>Previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks.<n>We establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost.
• Score: 43.85263006081191
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Quantization-based Bounds on the Wasserstein Metric [0.7550566004119158]
  The Wasserstein metric has become increasingly important in many machine learning applications.<n>Despite its appeal, it is often too costly to compute.<n>We consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds.
  arXiv  Detail & Related papers  (2025-06-01T12:06:31Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation [0.0]
  Curvature serves as a potent and descriptive invariant, with its efficacy validated both theoretically and practically within graph theory. We employ a definition of generalized Ricci curvature proposed by Ollivier, which Lin and Yau later adapted to graph theory, known as Ollivier-Ricci curvature (ORC) ORC measures curvature using the Wasserstein distance, thereby integrating geometric concepts with probability theory and optimal transport.
  arXiv  Detail & Related papers  (2024-05-22T02:44:46Z)
• A Bound on the Maximal Marginal Degrees of Freedom [0.0]
  This paper addresses low rank approximations and surrogates for kernel ridge regression.<n>We demonstrate that the computational cost of the most popular low rank approach, which is the Nystr"om method, is almost linear in the sample size.<n>The result builds on a thorough theoretical analysis of the approximation of elementary kernel functions by elements in the range of the associated integral operator.
  arXiv  Detail & Related papers  (2024-02-20T10:25:44Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances [18.9717974398864]
  Sliced Wasserstein distances preserve properties of classic Wasserstein distances while being more scalable for computation and estimation in high dimensions. We quantify this scalability from three key aspects: (i) empirical convergence rates; (ii) robustness to data contamination; and (iii) efficient computational methods.
  arXiv  Detail & Related papers  (2022-10-17T15:04:51Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
  A problem of 1-bit compressed sensing is to estimate a sparse signal from a few binary measurements. We present a novel and concise analysis that moves away from the widely used non-constrained notion of width.
  arXiv  Detail & Related papers  (2020-07-07T17:28:03Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.