Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
arXiv:2011.09841
Abstract
We study community detection in the contextual stochastic block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596 [cs.SI], the second author studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous cavity method from statistical physics, they conjectured the sharp limits for community detection in this setting. Further, the information theoretic threshold was verified, assuming that the average degree of the observed graph is large. It is expected that the conjecture holds as soon as the average degree exceeds one, so that the graph has a giant component. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery.
24 pages, 1 figure
References in corpus (8)
- Spectral redemption: clustering sparse networks
- Structure and inference in annotated networks
- Hierarchical relational models for document networks
- Fundamental limits of detection in the spiked Wigner model
- Latent Multi-group Membership Graph Model
- Contextual Stochastic Block Models
- Detection limits in the high-dimensional spiked rectangular model
- Asymptotic normality and analysis of variance of log-likelihood ratios in spiked random matrix models
Cited by in corpus (4)
- Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
- Community Detection with Contextual Multilayer Networks
- Neural-prior stochastic block model
- LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNN