mlsanityData to 7 Oct 2026

Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold

arXiv 2205.11677 ↗First posted 24 May 2022stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with an arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to the stochastic model of networks and semidefinite program research.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 25 of its 78 references that are in the map. First posted on arXiv 24 May 2022.

Builds on

25 of 78 references.

References · 25

  1. 2019Self-training with Noisy Student improves ImageNet classificationcited by 1,304
  2. 2017Community Detection and Stochastic Block Modelscited by 317
  3. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  4. 2013Spectral redemption: clustering sparse networkscited by 54
  5. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  6. 2013A Proof Of The Block Model Threshold Conjecturecited by 35
  7. 2015Achieving Optimal Misclassification Proportion in Stochastic Block Modelcited by 35
  8. 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 32
  9. 2014Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatricescited by 29
  10. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
  11. 2014On semidefinite relaxations for the block modelcited by 22
  12. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
13 more
  1. 2014Community detection in sparse networks via Grothendieck's inequalitycited by 21
  2. 2015How Robust are Reconstruction Thresholds for Community Detection?cited by 20
  3. 2020Strong Consistency, Graph Laplacians, and the Stochastic Block Modelcited by 20
  4. 2015Optimal Cluster Recovery in the Labeled Stochastic Block Modelcited by 18
  5. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  6. 2015Random Laplacian matrices and convex relaxationscited by 13
  7. 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
  8. 2018Graph powering and spectral robustnesscited by 10
  9. 2015A semidefinite program for unbalanced multisection in the stochastic block modelcited by 7
  10. 2015Local Algorithms for Block Models with Side Informationcited by 7
  11. 2014Global and Local Information in Clustering Labeled Block Modelscited by 5
  12. 2014Phase transitions in semisupervised clustering of sparse networkscited by 4
  13. 2015Multisection in the Stochastic Block Model using Semidefinite Programmingcited by 4

Built on by

Not cited yet.