# An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 40 references that are in the map.
- First posted on arXiv 20 Dec 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (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)
- [SPONGE: A generalized eigenproblem for clustering signed networks](https://mlsanity.com/paper/1904.08575/) (2019)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences](https://mlsanity.com/paper/1609.05820/) (2016)
- [Community detection with node attributes in multilayer networks](https://mlsanity.com/paper/2004.09160/) (2020)
- [Covariate Regularized Community Detection in Sparse Graphs](https://mlsanity.com/paper/1607.02675/) (2016)
- [Stochastic Block Models with Multiple Continuous Attributes](https://mlsanity.com/paper/1803.02726/) (2018)
- [Community Detection in Networks with Node Features](https://mlsanity.com/paper/1509.01173/) (2015)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [Network structure, metadata and the prediction of missing nodes and annotations](https://mlsanity.com/paper/1604.00255/) (2016)
- [Optimal Adaptivity of Signed-Polygon Statistics for Network Testing](https://mlsanity.com/paper/1904.09532/) (2019)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Spectral inference for large Stochastic Blockmodels with nodal covariates](https://mlsanity.com/paper/1908.06438/) (2019)
- [Community detection with nodal information](https://mlsanity.com/paper/1610.09735/) (2016)
- [Projected Power Iteration for Network Alignment](https://mlsanity.com/paper/1707.04929/) (2017)
- [A Map Equation with Metadata: Varying the Role of Attributes in Community Detection](https://mlsanity.com/paper/1810.10433/) (2018)

## Built on by (most cited first, 10 of 10)

- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [HEIST: A Graph Foundation Model for Spatial Transcriptomics and Proteomics Data](https://mlsanity.com/paper/2506.11152/) (2025)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [High-dimensional Clustering onto Hamiltonian Cycle](https://mlsanity.com/paper/2304.14531/) (2023)
- [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [Directed Link Prediction using GNN with Local and Global Feature Fusion](https://mlsanity.com/paper/2506.20235/) (2025)
- [Exact Recovery in the Data Block Model](https://mlsanity.com/paper/2602.05852/) (2026)

## Abstract (arXiv)

Real-world networks often come with side information that can help to improve the performance of network analysis tasks such as clustering. Despite a large number of empirical and theoretical studies conducted on network clustering methods during the past decade, the added value of side information and the methods used to incorporate it optimally in clustering algorithms are relatively less understood. We propose a new iterative algorithm to cluster networks with side information for nodes (in the form of covariates) and show that our algorithm is optimal under the Contextual Symmetric Stochastic Block Model. Our algorithm can be applied to general Contextual Stochastic Block Models and avoids hyperparameter tuning in contrast to previously proposed methods. We confirm our theoretical results on synthetic data experiments where our algorithm significantly outperforms other methods, and show that it can also be applied to signed graphs. Finally we demonstrate the practical interest of our method on real data.