Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
This work addresses clustering in complex data with multi-way interactions, such as social or biological networks, by extending spectral methods to hypergraphs, though it is incremental relative to existing graph-based approaches.
The paper tackles the problem of clustering data with higher-order relationships by introducing submodular hypergraphs, which assign submodular weights to hyperedge cuts, and develops p-Laplacians and Cheeger inequalities for them, resulting in new spectral clustering algorithms for hypergraphs.
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in clustering 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.