# Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms

arXiv: https://arxiv.org/abs/2501.11139 · HTML: https://mlsanity.com/paper/2501.11139/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 46 references that are in the map.
- First posted on arXiv 19 Jan 2025.

## Builds on (most cited first, 24 of 24)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Learning Latent Block Structure in Weighted Networks](https://mlsanity.com/paper/1404.0431/) (2014)
- [Adaptive Estimation in Structured Factor Models with Applications to Overlapping Clustering](https://mlsanity.com/paper/1704.06977/) (2017)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Vintage Factor Analysis with Varimax Performs Statistical Inference](https://mlsanity.com/paper/2004.05387/) (2020)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Covariate Regularized Community Detection in Sparse Graphs](https://mlsanity.com/paper/1607.02675/) (2016)
- [Community Detection in Networks with Node Features](https://mlsanity.com/paper/1509.01173/) (2015)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence](https://mlsanity.com/paper/1509.06418/) (2015)
- [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Model Selection in Overlapping Stochastic Block Models](https://mlsanity.com/paper/1405.2722/) (2014)
- [Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph boldsymbolβ-Model](https://mlsanity.com/paper/2307.02818/) (2023)
- [Optimal vintage factor analysis with deflation varimax](https://mlsanity.com/paper/2310.10545/) (2023)

## Abstract (arXiv)

The integration of network information and node attribute information has recently gained significant attention in the community detection literature. In this work, we consider community detection in the Contextual Labeled Stochastic Block Model (CLSBM), where the network follows an LSBM and node attributes follow a Gaussian Mixture Model (GMM). Our primary focus is the misclassification rate, which measures the expected number of nodes misclassified by community detection algorithms. We first establish a lower bound on the optimal misclassification rate that holds for any algorithm. When we specialize our setting to the LSBM (which preserves only network information) or the GMM (which preserves only node attribute information), our lower bound recovers prior results. Moreover, we present an efficient spectral-based algorithm tailored for the CLSBM and derive an upper bound on its misclassification rate. Although the algorithm does not attain the lower bound, it serves as a reliable starting point for designing more accurate community detection algorithms (as many algorithms use spectral method as an initial step, followed by refinement procedures to enhance accuracy).