Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DescriptiveSimilar Papers 제목 키워드 기반
Discrete scalar curvature as a weighted sum of Ollivier-Ricci curvatures
We study the relationship between discrete analogues of Ricci and scalar curvature that are defined for point clouds and graphs. In the discrete setting, Ricci curvature is replaced by Ollivier-Ricci curvature. Scalar cu…
Point CloudsOllivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural Networks
This thesis is an exposition of Ollivier-Ricci Curvature of metric spaces as introduced by Yann Ollivier, which is based upon the 1-Wasserstein Distance and optimal transport theory. We present some of the major results …
Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds
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 …
A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
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 Wasse…
Computational EfficiencyEfficient Curvature-aware Graph Network
Graph curvature provides geometric priors for Graph Neural Networks (GNNs), enhancing their ability to model complex graph structures, particularly in terms of structural awareness, robustness, and theoretical interpreta…
Computational Efficiency