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

2018/03/10 by Li, Pan, Milenkovic, Olgica · 3 citations
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1803.03833

Abstract

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.

Cited by

• Higher-Order Regularization Learning on Hypergraphs
• Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
• p-Laplacians for Manifold-valued Hypergraphs

Related

• Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering
• Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian
• Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
• Cheeger Inequalities for Submodular Transformations
• Dense clusters in hypergraphs