Submodular Hypergraphs: P-Laplacians, Cheeger Inequalities and Spectral Clustering
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 higher-order structures carry relevant information. For such hypergraphs, we define the notion of p-Laplacians and derive corresponding nodal domain theorems and k-way Cheeger inequalities. We conclude with the description of algorithms for computing the spectra of 1- and 2-Laplacians that constitute the basis of new spectral hypergraph clustering methods.
Cite
Text
Li and Milenkovic. "Submodular Hypergraphs: P-Laplacians, Cheeger Inequalities and Spectral Clustering." International Conference on Machine Learning, 2018.Markdown
[Li and Milenkovic. "Submodular Hypergraphs: P-Laplacians, Cheeger Inequalities and Spectral Clustering." International Conference on Machine Learning, 2018.](https://mlanthology.org/icml/2018/li2018icml-submodular/)BibTeX
@inproceedings{li2018icml-submodular,
title = {{Submodular Hypergraphs: P-Laplacians, Cheeger Inequalities and Spectral Clustering}},
author = {Li, Pan and Milenkovic, Olgica},
booktitle = {International Conference on Machine Learning},
year = {2018},
pages = {3014-3023},
volume = {80},
url = {https://mlanthology.org/icml/2018/li2018icml-submodular/}
}