Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model

Abstract

We prove strong consistency of spectral clustering under the degree-corrected hypergraph stochastic block model in the sparse regime where the maximum expected hyperdegree is as small as $\Omega (\log n)$ with $n$ denoting the number of nodes. We show that the basic spectral clustering without preprocessing or postprocessing is strongly consistent in an even wider range of the model parameters, in contrast to previous studies that either trim high-degree nodes or perform local refinement. At the heart of our analysis is the entry-wise eigenvector perturbation bound derived by the leave-one-out technique. To the best of our knowledge, this is the first entry-wise error bound for degree-corrected hypergraph models, resulting in the strong consistency for clustering non-uniform hypergraphs with heterogeneous hyperdegrees.

arXiv comment16 pages, 1 figures

References in corpus (15)

• Stochastic blockmodels and community structure in networks
• Spectral redemption: clustering sparse networks
• Recovering low-rank matrices from few coefficients in any basis
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Consistency of community detection in networks under degree-corrected stochastic block models
• Spectral Methods for Data Science: A Statistical Perspective
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models

Cited by in corpus (2)

• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model