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 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.

arXiv commentA short version of this paper is presented in ICML 2018. This version includes the definition of a sequence of eigenvalues for 1-Laplacian

References in corpus (12)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Higher-order organization of complex networks
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Reflection methods for user-friendly submodular optimization
• Nodal Domains of Eigenvectors for $1$-Laplacian on Graphs
• Nonparametric Detection of Geometric Structures over Networks
• The Lusternik-Schnirelmann theorem for graphs
• On the Convergence Rate of Decomposable Submodular Function Minimization
• Revisiting Decomposable Submodular Function Minimization with Incidence Relations
• Submodularity on Hypergraphs: From Sets to Sequences
• Structured learning of sum-of-submodular higher order energy functions

Cited by in corpus (18)

• HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Line Hypergraph Convolution Network: Applying Graph Convolution for Hypergraphs
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• A Cheeger Cut for Uniform Hypergraphs
• Hypergraph $p$-Laplacians and Scale Spaces
• Revisiting Decomposable Submodular Function Minimization with Incidence Relations
• Hodge Decompositions for Weighted Hypergraphs
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
• Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel $k$-means, and Heat Kernel
• Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering
• How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators
• Local Hyper-Flow Diffusion
• Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• $H{S}^2$: Active Learning over Hypergraphs
• Nonlinear Evolution Equation Associated with Hypergraph Laplacian
• Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization