mlsanityData to 14 Oct 2026

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

arXiv 2107.06767 ↗First posted 14 Jul 2021math.ST cs.IT cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models, focusing on the regime where the average degree is logarithmic in the number of vertices. We derive the precise information-theoretic threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to 1, while below it no estimator can recover the true correspondence with probability bounded away from 0. As an application of our results, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 36 of its 75 references that are in the map. First posted on arXiv 14 Jul 2021.

Builds on

36 of 75 references.

References · 36

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2018Contextual Stochastic Block Modelscited by 134
  3. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  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. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  9. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  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
24 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. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  9. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  10. 2015Clustering attributed graphs: models, measures and methodscited by 20
  11. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  12. 2013An efficient reconciliation algorithm for social networkscited by 12
  13. 2020Correlated randomly growing graphscited by 12
  14. 2016Optimal De-Anonymization in Random Graphs with Community Structurecited by 11
  15. 2015Community Detection in Networks with Node Featurescited by 10
  16. 2015Local Algorithms for Block Models with Side Informationcited by 7
  17. 2019Mutual Information in Community Detection with Covariate Information and Correlated Networkscited by 7
  18. 2021The Power of D-hops in Matching Power-Law Graphscited by 7
  19. 2014Global and Local Information in Clustering Labeled Block Modelscited by 5
  20. 2018Latent heterogeneous multilayer community detectioncited by 5
  21. 2018Recovering a Single Community with Side Informationcited by 5
  22. 2015Clustering and Inference From Pairwise Comparisonscited by 4
  23. 2016On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networkscited by 4
  24. 2018MPGM: Scalable and Accurate Multiple Network Alignmentcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 5; 2024: 7; 2025: 3; 2026: 1.

22 papers.

Sort:

  1. 2022Matching recovery threshold for correlated random graphscited by 16
  2. 2023T-GAE: Transferable Graph Autoencoder for Network Alignmentcited by 14
  3. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  4. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 9
  5. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  6. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
  7. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  8. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 6
  9. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  10. 2022Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodcited by 4
  11. 2024Harnessing Multiple Correlated Networks for Exact Community Recoverycited by 3
  12. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 3
10 more
  1. 2022Clustered Graph Matching for Label Recovery and Graph Classificationcited by 2
  2. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  3. 2023Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlationcited by 1
  4. 2024Community Detection in the Multi-View Stochastic Block Modelcited by 1
  5. 2025Exact Matching in Correlated Networks with Node Attributes for Improved Community Recoverycited by 1
  6. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  7. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  8. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  9. 2025Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)cited by 0
  10. 2026Query-Limited Community Recovery in Stochastic Block Modelscited by 0