mlsanityData to 7 Oct 2026

Exact Community Recovery in Correlated Stochastic Block Models

arXiv 2203.15736 ↗First posted 29 Mar 2022math.ST cs.IT cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 39 of its 63 references that are in the map. First posted on arXiv 29 Mar 2022.

Builds on

39 of 63 references.

References · 39

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2018Contextual Stochastic Block Modelscited by 134
  3. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  4. 2018Efficient random graph matching via degree profilescited by 48
  5. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  6. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  7. 2019Inference for multiple heterogeneous networks with a common invariant subspacecited by 39
  8. 2013A Proof Of The Block Model Threshold Conjecturecited by 35
  9. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 35
  10. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  11. 2014Covariate-assisted spectral clusteringcited by 29
  12. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
27 more
  1. 2017Spectral and matrix factorization methods for consistent community detection in multi-layer networkscited by 27
  2. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  3. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  4. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
  5. 2020From tree matching to sparse graph alignmentcited by 26
  6. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  7. 2014Consistency Thresholds for the Planted Bisection Modelcited by 24
  8. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  9. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  10. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  11. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  12. 2015Clustering attributed graphs: models, measures and methodscited by 20
  13. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  14. 2013An efficient reconciliation algorithm for social networkscited by 12
  15. 2016Covariate Regularized Community Detection in Sparse Graphscited by 12
  16. 2020Correlated randomly growing graphscited by 12
  17. 2016Optimal De-Anonymization in Random Graphs with Community Structurecited by 11
  18. 2020Global and Individualized Community Detection in Inhomogeneous Multilayer Networkscited by 11
  19. 2015Community Detection in Networks with Node Featurescited by 10
  20. 2016Information Recovery in Shuffled Graphs via Graph Matchingcited by 8
  21. 2015Local Algorithms for Block Models with Side Informationcited by 7
  22. 2019Mutual Information in Community Detection with Covariate Information and Correlated Networkscited by 7
  23. 2021The Power of D-hops in Matching Power-Law Graphscited by 7
  24. 2014Global and Local Information in Clustering Labeled Block Modelscited by 5
  25. 2018Latent heterogeneous multilayer community detectioncited by 5
  26. 2018Recovering a Single Community with Side Informationcited by 5
  27. 2016On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networkscited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  2. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  3. 2024Harnessing Multiple Correlated Networks for Exact Community Recoverycited by 3
  4. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 2
  5. 2024Community Detection in the Multi-View Stochastic Block Modelcited by 1
  6. 2025Exact Matching in Correlated Networks with Node Attributes for Improved Community Recoverycited by 1
  7. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  8. 2026Query-Limited Community Recovery in Stochastic Block Modelscited by 0