Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds

• URL: http://arxiv.org/abs/2307.02378v2
• Date: Mon, 26 Aug 2024 12:36:51 GMT
• Title: Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds
• Abstract summary: We study the relationship between the curvature of a random geometric graph built from $X$ and the curvature of the manifold $M$ via continuum limits of Ollivier's discrete Ricci curvature. We discuss applications of the global discrete curvature bounds to contraction properties of heat kernels on graphs, as well as implications for manifold learning from data clouds.
• Score: 1.1126342180866644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $M$ denote a low-dimensional manifold embedded in Euclidean space and let ${X}= \{ x_1, \dots, x_n \}$ be a collection of points uniformly sampled from it. We study the relationship between the curvature of a random geometric graph built from ${X}$ and the curvature of the manifold $M$ via continuum limits of Ollivier's discrete Ricci curvature. We prove pointwise, non-asymptotic consistency results and also show that if $M$ has Ricci curvature bounded from below by a positive constant, then the random geometric graph will inherit this global structural property with high probability. We discuss applications of the global discrete curvature bounds to contraction properties of heat kernels on graphs, as well as implications for manifold learning from data clouds. In particular, we show that our consistency results allow for estimating the intrinsic curvature of a manifold by first estimating concrete extrinsic quantities.

Related papers

• $\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition [47.80325814873361]
  Mixed-curvature representation learning seeks to capture rich geometric structures that cannot be adequately modeled by a single curvature regime.<n>We introduce the $mathbbSL(n)$ space, a representation geometry defined by the simple $det(A)variant=1$ constraint and a left in Schatten-$p$ structure.<n>Despite this minimal construction, $mathbbSL(n)$ exhibits pointwise negative, zero, and flag curvature around a common flagpole.
  arXiv  Detail & Related papers  (2026-09-14T05:52:14Z)
• Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds [9.035866986287205]
  This work addresses decentralized online convexian optimization on Hadamard.<n>To our knowledge these are the first curvature-independent regret guarantees on embeddings for predicted rates, with no degradation due to curvature.
  arXiv  Detail & Related papers  (2026-09-12T01:53:49Z)
• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• The Geometric Cost of Normalization: Affine Bounds on the Bayesian Complexity of Neural Networks [0.0]
  We prove that LayerNorm's mean-centering step, by confining data to a linear hyperplane (through the origin), reduces the Local Learning Coefficient (LLC) of the subsequent weight matrix by exactly $m/2$.<n>We further show that Softmax simplex data introduces a "smuggled bias" that activates the same $m/2$ LLC drop when paired with an explicit downstream bias.
  arXiv  Detail & Related papers  (2026-03-28T22:15:45Z)
• Pivotal CLTs for Pseudolikelihood via Conditional Centering in Dependent Random Fields [1.3875545441867139]
  We study fluctuations of conditionally centered statistics of the form $$N-1/2sum_i=1N c_i(g(sigma_i)-mathbbE_N[g(sigma_i)|sigma_j,jneq i])$$ where $(sigma_j,ldots,sigma_N) are sampled from a dependent random field.<n>We develop a general framework for maximum pseudolikelihood inference in dependent random fields.
  arXiv  Detail & Related papers  (2025-10-06T16:06:45Z)
• Discrete scalar curvature as a weighted sum of Ollivier-Ricci curvatures [4.891498111882615]
  In the discrete setting, Ricci curvature is replaced by Ollivier-Ricci curvature.<n>We show that our definition converges to scalar curvature for nearest neighbor graphs obtained by sampling from a manifold.
  arXiv  Detail & Related papers  (2025-10-06T15:43:07Z)
• Central limit theorems for the eigenvalues of graph Laplacians on data clouds [6.993491018326815]
  We consider the Laplacian operator $Delta_n$ associated to an $varepsilon$-sqrt graph over $X_n$.<n>A formal argument allows us to interpret this variance as the dissipation of a suitable energy with respect to the Fisher-Rao geometry.<n>A statistical interpretation of the geometric variance in terms of a Cramer-Rao lower bound for the estimation of the eigenvalues of certain weighted Laplace-Beltrami operator.
  arXiv  Detail & Related papers  (2025-07-24T21:03:20Z)
• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs) We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN. The most important observation is that the generalization capability can be realized with one large graph instead of being limited to the size of the graph as in previous results.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Ironing the Graphs: Toward a Correct Geometric Analysis of Large-Scale Graphs [2.2557806157585834]
  We argue that the classical embedding techniques cannot lead to correct geometric interpretation as they miss the curvature at each point, of manifold. We present an embedding approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete Ricci flow. A major contribution of this paper is that for the first time, we prove the convergence of discrete Ricci flow to a constant curvature and stable distance metrics over the edges.
  arXiv  Detail & Related papers  (2024-07-31T13:47:53Z)
• Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
  We study the task efficiently sampling from a Gibbs distribution $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC. Our results apply to general settings where $pi*$ can be non exponential and $Mh$ can have negative Ricci curvature.
  arXiv  Detail & Related papers  (2024-02-15T22:59:14Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  Graph Structure Learning (GSL) plays an important role in boosting Graph Neural Networks (GNNs) with a refined graph. GSL solutions usually focus on structure refinement with task-specific supervision (i.e., node classification) or overlook the inherent weakness of GNNs themselves. We propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs.
  arXiv  Detail & Related papers  (2024-01-23T14:06:08Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  We show that wetailed high-prob convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. We demonstrate analytically and that $ta$ can be used to the preferred choice of setting for a given problem.
  arXiv  Detail & Related papers  (2023-10-28T18:53:41Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
  Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis. We prove the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates. When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency.
  arXiv  Detail & Related papers  (2022-06-22T21:08:24Z)
• Heterogeneous manifolds for curvature-aware graph embedding [6.3351090376024155]
  Graph embeddings are used in a broad range of Graph ML applications. The quality of such embeddings crucially depends on whether the geometry of the space matches that of the graph.
  arXiv  Detail & Related papers  (2022-02-02T18:18:35Z)
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
  We study the problem of recovering the hidden correspondence between two edge-correlated random graphs. For dense graphs with $p=n-o(1)$, we prove that there exists a sharp threshold. For sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$, we show that the all-or-nothing phenomenon no longer holds.
  arXiv  Detail & Related papers  (2021-01-29T21:49:50Z)
• Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
  We prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues.
  arXiv  Detail & Related papers  (2020-07-13T20:43:19Z)

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.