mlsanityData to 7 Oct 2026

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

arXiv 2112.10467 ↗First posted 20 Dec 2021stat.ML cs.LG math.STcited by 10

Not on the map. Why?

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.

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

Builds on

27 of 40 references.

References · 27

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  3. 2018Contextual Stochastic Block Modelscited by 134
  4. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 52
  5. 2014Community Detection in Networks with Node Attributescited by 44
  6. 2016Community Detection in Degree-Corrected Block Modelscited by 36
  7. 2015Structure and inference in annotated networkscited by 30
  8. 2016Nonconvex phase synchronizationcited by 30
  9. 2014Covariate-assisted spectral clusteringcited by 29
  10. 2015Minimax Rates of Community Detection in Stochastic Block Modelscited by 25
  11. 2019SPONGE: A generalized eigenproblem for clustering signed networkscited by 24
  12. 2020Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limitcited by 23
15 more
  1. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  2. 2019Iterative Algorithm for Discrete Structure Recoverycited by 21
  3. 2016The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differencescited by 15
  4. 2020Community detection with node attributes in multilayer networkscited by 14
  5. 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
  6. 2018Stochastic Block Models with Multiple Continuous Attributescited by 11
  7. 2015Community Detection in Networks with Node Featurescited by 10
  8. 2021Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Methodcited by 10
  9. 2016Network structure, metadata and the prediction of missing nodes and annotationscited by 8
  10. 2019Optimal Adaptivity of Signed-Polygon Statistics for Network Testingcited by 8
  11. 2021Optimal Clustering in Anisotropic Gaussian Mixture Modelscited by 7
  12. 2019Spectral inference for large Stochastic Blockmodels with nodal covariatescited by 6
  13. 2016Community detection with nodal informationcited by 4
  14. 2017Projected Power Iteration for Network Alignmentcited by 3
  15. 2018A Map Equation with Metadata: Varying the Role of Attributes in Community Detectioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 3; 2026: 2.

10 papers.

  1. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 11
  2. 2023Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Modelcited by 7
  3. 2025HEIST: A Graph Foundation Model for Spatial Transcriptomics and Proteomics Datacited by 7
  4. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  5. 2023High-dimensional Clustering onto Hamiltonian Cyclecited by 2
  6. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  7. 2024VEC-SBM: Optimal Community Detection with Vectorial Edges Covariatescited by 0
  8. 2025Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithmscited by 0
  9. 2025Directed Link Prediction using GNN with Local and Global Feature Fusioncited by 0
  10. 2026Exact Recovery in the Data Block Modelcited by 0