Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering

Pan Li, Olgica Milenkovic
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3014-3023, 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 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 this Paper

BibTeX
@InProceedings{pmlr-v80-li18e, title = {Submodular Hypergraphs: p-Laplacians, {C}heeger Inequalities and Spectral Clustering}, author = {Li, Pan and Milenkovic, Olgica}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3014--3023}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/li18e/li18e.pdf}, url = {https://proceedings.mlr.press/v80/li18e.html}, 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.} }
Endnote
%0 Conference Paper %T Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering %A Pan Li %A Olgica Milenkovic %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-li18e %I PMLR %P 3014--3023 %U https://proceedings.mlr.press/v80/li18e.html %V 80 %X 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.
APA
Li, P. & Milenkovic, O.. (2018). Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3014-3023 Available from https://proceedings.mlr.press/v80/li18e.html.

Related Material