Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model

Abstract

We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma \in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati (2017) for non-uniform HSBMs. Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularized adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularization of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.

54 pages

References in corpus (21)

• Networks beyond pairwise interactions: structure and dynamics
• Higher-order organization of complex networks
• Consistency of spectral clustering in stochastic block models
• Spectral Methods for Data Science: A Statistical Perspective
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Belief propagation, robust reconstruction and optimal recovery of block models
• Size biased couplings and the spectral gap for random regular graphs
• Spectral Detection on Sparse Hypergraphs
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Consistency Thresholds for the Planted Bisection Model
• 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
• Spectra of random regular hypergraphs
• Sparse random tensors: Concentration, regularization and applications
• Deterministic tensor completion with hypergraph expanders
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Sparse SYK and traversable wormholes

Cited by in corpus (1)

• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model