Submodular Hypergraphs: pLaplacians, Cheeger Inequalities and Spectral Clustering
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:30143023, 2018.
Abstract
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in cluster ing applications in which higherorder structures carry relevant information. For such hypergraphs, we define the notion of pLaplacians and derive corresponding nodal domain theorems and kway Cheeger inequalities. We conclude with the description of algorithms for computing the spectra of 1 and 2Laplacians that constitute the basis of new spectral hypergraph clustering methods.
Related Material


