Source-linked AI summary
Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs
Jürgen Jost, Shiping Liu
TL;DR
The paper investigates how triangle frequency and local clustering relate to Ollivier’s combinatorial Ricci curvature, and connects this curvature with curvature dimension inequalities. It formulates curvature through transportation between local neighborhood measures and derives graph curvature bounds and relations to clustering.
Problem
The paper asks how triangle presence and local clustering relate to neighborhood-overlap-based Ollivier Ricci curvature, and how this curvature relates to curvature dimension inequalities.
Method
The paper uses Ollivier’s transportation-distance formulation on graph neighborhood measures to study curvature bounds and its relations with Bakry–Émery curvature dimension inequalities.
Results
The paper establishes relations between Ollivier curvature and the Watts–Strogatz clustering coefficient, with sharp bounds exemplified by complete graphs where both sides equal n−2.
Takeaways & Limitations
Triangle overlap provides a graph-theoretic route to curvature estimates, while local clustering also yields more precise curvature dimension inequalities.
Takeaways & Limitations
The analysis assumes locally finite connected simple graphs, works mainly with unweighted graphs, and requires a 1-Lipschitz extension in one argument.
Abstract
from arXiv · showhide
In this paper, we explore the relationship between one of the most elementary and important properties of graphs, the presence and relative frequency of triangles, and a combinatorial notion of Ricci curvature. We employ a definition of generalized Ricci curvature proposed by Ollivier in a general framework of Markov processes and metric spaces and applied in graph theory by Lin-Yau. In analogy with curvature notions in Riemannian geometry, we interpret this Ricci curvature as a control on the amount of overlap between neighborhoods of two neighboring vertices. It is therefore naturally related to the presence of triangles containing those vertices, or more precisely, the local clustering coefficient, that is, the relative proportion of connected neighbors among all the neighbors of a vertex. This suggests to derive lower Ricci curvature bounds on graphs in terms of such local clustering coefficients. We also study curvature dimension inequalities on graphs, building upon previous work of several authors.
1. Introduction
The paper studies how Ollivier’s graph Ricci curvature relates quantitatively to triangles and local clustering, and connects this curvature with Bakry–Émery curvature dimension inequalities and eigenvalue estimates.
- Motivation: Triangles increase overlap between neighboring vertices’ radius-1 neighborhoods, motivating a relationship between triangle abundance and graph Ricci curvature.The paper interprets curvature through neighborhood overlap and transport between local measures.
- Method: Ollivier’s curvature is defined using the transportation distance W1 between uniform neighbor measures mx and my.For neighboring vertices, mx assigns equal weight to each neighbor of x; smaller transport distance corresponds to larger curvature.
- Main curvature result: Theorem 1 introduces the number of triangles ♯(x, y) containing neighboring vertices and gives a curvature bound incorporating this triangle term.The notation includes positive-part and maximum/minimum operations in the stated bound.
- Clustering coefficient: For d-regular graphs, the example explicitly illustrates the relation between Ollivier’s curvature and the Watts–Strogatz local clustering coefficient.The local clustering coefficient averages triangle counts ♯(x, y) over neighbors of x.
- Curvature dimension and spectra: The paper also relates Ollivier curvature and Bakry–Émery curvature dimension inequalities, both of which yield lower bounds for the first Laplace eigenvalue λ1.This connects geometric and analytic aspects of graphs and relates λ1 to local clustering or the number of 3-cycles.
- Scope: The analysis concerns connected, locally finite simple graphs, primarily unweighted, with analogous results also derived for weighted graphs.The vertex set may be infinite, but every vertex must have finite degree.
2. Ollivier’s Ricci curvature and Bakry-´Emery’s calculus
This section defines Ollivier’s graph Ricci curvature through optimal transportation between neighborhood measures and develops the associated Laplace and Bakry-Émery Γ2 calculus. It connects curvature bounds with neighborhood overlap and curvature-dimension inequalities.
- 2.1. Ollivier’s Ricci curvature: Ollivier’s Ricci curvature is defined using the transportation distance between probability measures attached to points in a metric space.The graph setting uses neighborhood measures, with equal mass assigned to neighbors.
- 2.1. Ollivier’s Ricci curvature: A transfer plan gives an upper bound on transportation distance and therefore a lower bound on Ollivier’s curvature.Kantorovich duality provides the complementary route: a suitable 1-Lipschitz function lower-bounds transportation distance and upper-bounds curvature.
- 2.2.1. Laplace operator: The graph Laplace operator is introduced as the analogue of the Laplace-Beltrami operator and agrees with a graph Laplacian studied previously.The section then develops Γ2 calculus as the analytic counterpart of curvature.
- 2.2.2. Bochner formula and curvature-dimension inequality: Bakry-Émery curvature-dimension inequalities are formulated directly from iterated operators, with m as the dimension parameter and K(x) as the curvature function.This operator-based approach parallels the role of the Bochner formula in relating Ricci curvature to analytic inequalities.
3. Ollivier’s Ricci curvature and triangles
The paper derives lower bounds for Ollivier’s Ricci curvature on locally finite graphs using neighborhood transport and triangle counts, linking curvature to local clustering. It also identifies sharp cases and extensions to weighted graphs.
- Curvature bounds: Ollivier’s curvature is bounded below for neighboring vertices, and the bound extends to arbitrary vertex pairs through the triangle inequality for W1.The paper focuses on neighboring vertices because this suffices to control curvature at any distance.
- Curvature and triangles: Triangle-containing edges reduce transportation costs between neighboring measures, thereby increasing the corresponding Ollivier curvature.Common neighbors permit shorter mass transfers in the transport plan.
- Curvature and triangles: Theorem 3 expresses the curvature lower bound through symmetric degree terms and the number of triangles containing the edge, with sharpness for certain graphs.The formulation uses quantities symmetric in the endpoint degrees and triangle count.
- Boundary cases: If an edge has no triangles, the lower bound reduces to the earlier degree-based bound; degree-one endpoints instead have curvature exactly 0.These cases provide boundary behavior for sparse local neighborhoods.
- Short cycles: Triangles, quadrangles, and pentagons affect Ollivier curvature through short paths, whereas polygons with more than five edges do not impact it.The result follows from the path-length constraints in the 1-Lipschitz extension used with Kantorovich duality.
- Clustering consequences: Positive Ollivier curvature requires at least one triangle on each neighboring edge, while scalar curvature admits lower bounds controlled by the local clustering coefficient.Trees attain the scalar-curvature lower bound, consistent with their rapid volume growth.
4. Curvature dimension inequalities
The section establishes curvature dimension inequalities for locally finite graphs, including weighted variants, and examines how positive Ollivier-Ricci curvature and triangles affect the curvature term. Complete graphs and regular trees provide examples where the resulting curvature terms are optimal.
- Curvature dimension inequalities: Curvature dimension inequalities are established for locally finite graphs through estimates involving the graph Laplace operator.The section also states weighted-graph analogues.
- Unweighted graphs: Triangles cause cancellations in calculating Hf(x), adding terms that enter the curvature-dimension estimates.The proof compares contributions from neighboring vertices and uses the symmetry created by triangles.
- Unweighted graphs: Positive Ollivier-Ricci curvature yields curvature dimension inequalities, and increasing curvature raises the curvature term in the associated inequality.The section separately treats strictly positive curvature and curvature bounded below by k > 0.
- Unweighted graphs: κ(x, y) ≥ k > 0 bounds the graph diameter by 2/k, so the graph is finite in this case.This consequence is attributed to a proposition of Ollivier.
- Examples: The examples motivate choosing dimension parameters appropriately to obtain stronger relations between lower curvature bounds and curvature terms.The complete-graph dimension choice is connected to its interpretation as the boundary of an (n − 1)-dimensional simplex.