Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation

• URL: http://arxiv.org/abs/2405.13302v1
• Date: Wed, 22 May 2024 02:44:46 GMT
• Title: Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation
• Authors: Wonwoo Kang, Heehyun Park,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. Jost and Liu previously discussed the lower bound of ORC by showing the upper bound of the Wasserstein distance. We extend the applicability of these bounds to discrete spaces with metrics on integers, specifically hypergraphs. Compared to prior work on ORC in hypergraphs by Coupette, Dalleiger, and Rieck, which faced computational challenges, our method introduces a simplified approach with linear computational complexity, making it particularly suitable for analyzing large-scale networks. Through extensive simulations and application to synthetic and real-world datasets, we demonstrate the significant improvements our method offers in evaluating ORC.

Related papers

• Kernel Approximation of Fisher-Rao Gradient Flows [52.154685604660465]
  We present a rigorous investigation of Fisher-Rao and Wasserstein type gradient flows concerning their gradient structures, flow equations, and their kernel approximations. Specifically, we focus on the Fisher-Rao geometry and its various kernel-based approximations, developing a principled theoretical framework.
  arXiv  Detail & Related papers  (2024-10-27T22:52:08Z)
• Finite-dimensional approximations of push-forwards on locally analytic functionals [5.787117733071417]
  Our approach is to consider the push-forward on the space of locally analytic functionals, instead of directly handling the analytic map itself. We establish a methodology enabling appropriate finite-dimensional approximation of the push-forward from finite discrete data.
  arXiv  Detail & Related papers  (2024-04-16T17:53:59Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• 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 Framework for Analyzing Cross-correlators using Price's Theorem and Piecewise-Linear Decomposition [5.094549132183797]
  We present a general mathematical framework that allows us to analyze cross-correlators constructed using a mixture of piece-wise linear functions. We show that some of the most promising cross-correlators are based on Huber's loss functions, margin-propagation (MP) functions, and the log-sum-exp (LSE) functions.
  arXiv  Detail & Related papers  (2023-04-18T19:03:27Z)
• Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework [15.447966950703952]
  We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs. We show that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.
  arXiv  Detail & Related papers  (2022-10-21T15:40:49Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Projected Statistical Methods for Distributional Data on the Real Line with the Wasserstein Metric [0.0]
  We present a novel class of projected methods, to perform statistical analysis on a data set of probability distributions on the real line. We focus in particular on Principal Component Analysis (PCA) and regression. Several theoretical properties of the models are investigated and consistency is proven.
  arXiv  Detail & Related papers  (2021-01-22T10:24:49Z)
• Efficient Semi-Implicit Variational Inference [65.07058307271329]
  We propose an efficient and scalable semi-implicit extrapolational (SIVI) Our method maps SIVI's evidence to a rigorous inference of lower gradient values.
  arXiv  Detail & Related papers  (2021-01-15T11:39:09Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.