Spectral Graph Theory without a Spectrum: Diffusions on Hypergraphs and Their Convergence

Abstract

Hypergraphs are straightforward generalizations of graphs for which the Laplacian operator is non-linear and non-differentiable. We show that, even in this general setting, we can efficiently simulate hypergraph heat diffusions and that a Poincare constant analogous to the spectral gap controls their convergence to the stationary heat distribution.