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

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 Ω(log n) with n denoting the number of nodes. We show that the basic spectral clustering without preprocessing or...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2024-03, Vol.70 (3), p.1-1
Main Authors: Deng, Chong, Xu, Xin-Jian, Ying, Shihui
Format: Article
Language:English
Subjects:
Approximation algorithms
Clustering
Clustering algorithms
Consistency
Eigenvectors
Error correction
Graph theory
Hypergraph
Image edge detection
Linear matrix inequalities
Nodes
Numerical models
Perturbation methods
spectral clustering
stochastic block model
Stochastic processes
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Ω(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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2023.3302283