Curvature of Hypergraphs via Multi-Marginal Optimal Transport
Shahab Asoodeh, Tingran Gao, James A. Evans · 2018
We introduce a novel definition of curvature for hypergraphs, a natural generalization of graphs, by introducing a multi-marginal optimal transport problem for a naturally defined random walk on the hypergraph. This curvature, termed coarse scalar curvature, extends a recent definition of Ricci curvature for Markov chains on metric spaces by Ollivier [Journal of Functional Analysis 256 (2009) 810-864], and is related to the scalar curvature when the hypergraph arises naturally from a Riemannian manifold. We investigate basic theoretical properties of the coarse scalar curvature and obtain several bounds. Empirical experiments demonstrate that coarse scalar curvatures detects “bridges” across connected components in hypergraphs, akin to the behavior of coarse Ricci curvatures on graphs.