# Harnessing Multiple Correlated Networks for Exact Community Recovery

arXiv: https://arxiv.org/abs/2412.02796 · HTML: https://mlsanity.com/paper/2412.02796/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 50 references that are in the map.
- First posted on arXiv 3 Dec 2024.

## Builds on (most cited first, 15 of 15)

- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Correlated randomly growing graphs](https://mlsanity.com/paper/2004.13537/) (2020)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [Finding a planted clique by adaptive probing](https://mlsanity.com/paper/1903.12050/) (2019)
- [Phase transition in noisy high-dimensional random geometric graphs](https://mlsanity.com/paper/2103.15249/) (2021)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)
- [A probabilistic view of latent space graphs and phase transitions](https://mlsanity.com/paper/2110.15886/) (2021)
- [Towards Consensus: Reducing Polarization by Perturbing Social Networks](https://mlsanity.com/paper/2206.08996/) (2022)
- [From trees to seeds: on the inference of the seed from large trees in the uniform attachment model](https://mlsanity.com/paper/1409.7685/) (2014)
- [On the influence of the seed graph in the preferential attachment model](https://mlsanity.com/paper/1401.4849/) (2014)
- [Rumor source detection with multiple observations under adaptive diffusions](https://mlsanity.com/paper/2006.11211/) (2020)
- [Basic models and questions in statistical network analysis](https://mlsanity.com/paper/1609.03511/) (2016)
- [Optimal control for diffusions on graphs](https://mlsanity.com/paper/1703.09892/) (2017)
- [Batch Optimization for DNA Synthesis](https://mlsanity.com/paper/2011.14532/) (2020)

## Built on by (most cited first, 3 of 3)

- [PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment](https://mlsanity.com/paper/2505.21366/) (2025)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## 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.