Timezone: »

Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
Pan Li · Olgica Milenkovic

Fri Jul 13 07:40 AM -- 07:50 AM (PDT) @ K11

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.

Author Information

Pan Li (University of Illinois Urbana-Champaign)
Olgica Milenkovic (University of Illinois UC)

Related Events (a corresponding poster, oral, or spotlight)