Consistency of Spectral Hypergraph Partitioning under Planted Partition Model

Abstract

Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random non-uniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning non-uniform hypergraphs.

35 pages, 2 figures, 1 table

References in corpus (6)

• Random hypergraphs and their applications
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Structure of large random hypergraphs
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Sparse random graphs: regularization and concentration of the Laplacian

Cited by in corpus (33)

• What are higher-order networks?
• Inhomogeneous Hypergraph Clustering with Applications
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Searching for Representative Modes on Hypergraphs for Robust Geometric Model Fitting
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Randomizing hypergraphs preserving degree correlation and local clustering
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Community detection in the sparse hypergraph stochastic block model
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Opinion disparity in hypergraphs with community structure
• Sparse random tensors: Concentration, regularization and applications
• Testing Community Structures for Hypergraphs
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Marchenko-Pastur law with relaxed independence conditions
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• On the Minimax Misclassification Ratio of Hypergraph Community Detection
• Community Detection in General Hypergraph via Graph Embedding
• Attributed Hypergraph Generation with Realistic Interplay Between Structure and Attributes
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Equipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
• Phase transition in a power-law uniform hypergraph
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• A Family of Pairwise Multi-Marginal Optimal Transports that Define a Generalized Metric
• Spectral bounds for non-uniform hypergraphs using weighted clique expansion