Title: Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds

Abstract

Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier–Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.

Benson, Brian; Ralli, Peter; Tetali, Prasad(
, International Mathematics Research Notices)

Abstract

We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature.

Following recent work in the continuous setting of Riemannian manifolds (by the 1st author), we then bound the eigenvalues of the Laplacian of a graph under bounds on the volume growth. In particular, $\lambda _2$ of the graph can be bounded using a weighted discrete Hardy inequality and the higher eigenvalues of the graph can be bounded by the eigenvalues of a tridiagonal matrix times a multiplicative factor, both of which only depend on the volume growth of the graph. As a direct application, we relate the eigenvalues to the Cheeger isoperimetric constant. Using these methods, we describe classes of graphs for which the Cheeger inequality is tight on the 2nd eigenvalue (i.e. the 1st nonzero eigenvalue). We also describe a method for proving Buser’s Inequality in graphs, particularly under a lower bound assumption on curvature.

Anari, Nima; Jain, Vishesh; Koehler, Frederic; Pham, Huy Tuan; Vuong, Thuy-Duong(
, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution $\mu$ on $k$-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set $S$, the relative entropy of a single element of $S$ drawn uniformly at random carries at most $O(1/k)$ fraction of the relative entropy of $S$. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces.
In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified log-Sobolev inequalities, for down-up random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. We furthermore extend our theory to the case where spectral independence does not hold under arbitrary external fields. To do this, we introduce a framework for obtaining tight mixing time bounds for Markov chains based on what we call restricted modified log-Sobolev inequalities, which guarantee entropy contraction not for all distributions, but for those in a sufficiently large neighborhood of the stationary distribution. To derive our results, we relate entropic independence to properties of polynomials: $\mu$ is entropically independent exactly when a transformed version of the generating polynomial of $\mu$ is upper bounded by its linear tangent; this property is implied by concavity of the said transformation, which was shown by prior work to be locally equivalent to spectral independence.
We apply our results to obtain (1) tight modified log-Sobolev inequalities and mixing times for multi-step down-up walks on fractionally log-concave distributions, (2) the tight mixing time of $O(n\log n)$ for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than $1$, improving upon the prior quadratic dependence on $n$, and (3) nearly-linear time $\widetilde O_{\delta}(n)$ samplers for the hardcore and Ising models on $n$-node graphs that have $\delta$-relative gap to the tree-uniqueness threshold. In the last application, our bound on the running time does not depend on the maximum degree $\Delta$ of the graph, and is therefore optimal even for high-degree graphs, and in fact, is sublinear in the size of the graph for high-degree graphs.

Lu, Linyuan; Wang, Zhiyu(
, Pure and applied mathematics quarterly)

In this paper, we prove an Azuma-Hoeffding-type inequality
in several classical models of random configurations by a
Ricci curvature approach. Adapting Ollivier’s work on the Ricci
curvature of Markov chains on metric spaces, we prove a cleaner
form of the corresponding concentration inequality in graphs.
Namely, we show that for any Lipschitz function f on any graph
(equipped with an ergodic random walk and thus an invariant distribution
ν) with Ricci curvature at least κ > 0, we have
ν (|f − Eνf| ≥ t) ≤ 2 exp(−t^2κ/7).

We analyze networks of functional correlations between brain regions to identify changes in their structure caused by Attention Deficit Hyperactivity Disorder (adhd). We express the task for finding changes as a network anomaly detection problem on temporal networks. We propose the use of a curvature measure based on the Forman–Ricci curvature, which expresses higher-order correlations among two connected nodes. Our theoretical result on comparing this Forman–Ricci curvature with another well-known notion of network curvature, namely the Ollivier–Ricci curvature, lends further justification to the assertions that these two notions of network curvatures are not well correlated and therefore one of these curvature measures cannot be used as an universal substitute for the other measure. Our experimental results indicate nine critical edges whose curvature differs dramatically in brains ofadhdpatients compared to healthy brains. The importance of these edges is supported by existing neuroscience evidence. We demonstrate that comparative analysis of curvature identifies changes that more traditional approaches, for example analysis of edge weights, would not be able to identify.

Many complex networks in the real world have community structures – groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical/combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By considering networks as geometric objects and communities in a network as a geometric decomposition, we apply curvature and discrete Ricci flow, which have been used to decompose smooth manifolds with astonishing successes in mathematics, to break down communities in networks. We tested our method on networks with ground-truth community structures, and experimentally confirmed the effectiveness of this geometric approach.

Hoorn, Pim van der, Lippner, Gabor, Trugenberger, Carlo, and Krioukov, Dmitri. Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds. Discrete & Computational Geometry 70.3 Web. doi:10.1007/s00454-023-00507-y.

Hoorn, Pim van der, Lippner, Gabor, Trugenberger, Carlo, and Krioukov, Dmitri.
"Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds". Discrete & Computational Geometry 70 (3). Country unknown/Code not available: Springer Science + Business Media. https://doi.org/10.1007/s00454-023-00507-y.https://par.nsf.gov/biblio/10426373.

@article{osti_10426373,
place = {Country unknown/Code not available},
title = {Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds},
url = {https://par.nsf.gov/biblio/10426373},
DOI = {10.1007/s00454-023-00507-y},
abstractNote = {Abstract Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier–Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.},
journal = {Discrete & Computational Geometry},
volume = {70},
number = {3},
publisher = {Springer Science + Business Media},
author = {Hoorn, Pim van der and Lippner, Gabor and Trugenberger, Carlo and Krioukov, Dmitri},
}

Warning: Leaving National Science Foundation Website

You are now leaving the National Science Foundation website to go to a non-government website.

Website:

NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.