Harnessing Multiple Correlated Networks for Exact Community Recovery
Not on the map. Why?
Abstract (arXiv)
We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, R'acz, and Sridhar (COLT 2022) determined the precise information-theoretic threshold for exact community recovery using two correlated graphs; in particular, this showcased the subtle interplay between community recovery and graph matching. Here we study the natural setting of more than two graphs. The main challenge lies in understanding how to aggregate information across several graphs when none of the pairwise latent vertex correspondences can be exactly recovered. Our main result derives the precise information-theoretic threshold for exact community recovery using any constant number of correlated graphs, answering a question of Gaudio, R'acz, and Sridhar (COLT 2022). In particular, for every K ≥ 3 we uncover and characterize a region of the parameter space where exact community recovery is possible using K correlated graphs, even though (1) this is information-theoretically impossible using any K-1 of them and (2) none of the latent matchings can be exactly recovered.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 15 of its 50 references that are in the map. First posted on arXiv 3 Dec 2024.
Builds on
15 of 50 references.
References · 15
- 2014Testing for high-dimensional geometry in random graphscited by 25
- 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
- 2020Correlated randomly growing graphscited by 12
- 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
- 2019Finding a planted clique by adaptive probingcited by 6
- 2021Phase transition in noisy high-dimensional random geometric graphscited by 6
- 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
- 2021A probabilistic view of latent space graphs and phase transitionscited by 5
- 2022Towards Consensus: Reducing Polarization by Perturbing Social Networkscited by 4
- 2014From trees to seeds: on the inference of the seed from large trees in the uniform attachment modelcited by 3
- 2014On the influence of the seed graph in the preferential attachment modelcited by 2
- 2020Rumor source detection with multiple observations under adaptive diffusionscited by 2
3 more
- 2016Basic models and questions in statistical network analysiscited by 1
- 2017Optimal control for diffusions on graphscited by 1
- 2020Batch Optimization for DNA Synthesiscited by 1
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.