A Cheeger Cut for Uniform Hypergraphs
arXiv:2011.06816 · doi:10.1007/s00373-021-02348-z
Abstract
The graph Cheeger constant and Cheeger inequalities are generalized to the case of hypergraphs whose edges have the same cardinality. In particular, it is shown that the second largest eigenvalue of the generalized normalized Laplacian is bounded both above and below by the generalized Cheeger constant, and the corresponding eigenfunctions can be used to approximate the Cheeger cut.
References in corpus (11)
- Consistency of spectral clustering
- Hypergraph model of social tagging networks
- Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
- An Oriented Hypergraphic Approach to Algebraic Graph Theory
- Stochastic dynamics on hypergraphs and the spatial majority rule model
- Spectral Theory of Laplace Operators on Oriented Hypergraphs
- The Normalized Graph Cut and Cheeger Constant: from Discrete to Continuous
- Signless Normalized Laplacian for Hypergraphs
- Sharp bounds for the largest eigenvalue
- Finding Cheeger Cuts in Hypergraphs via Heat Equation
- Minimal Embedding Dimensions of Connected Neural Codes