Harnessing Multiple Correlated Networks for Exact Community Recovery
This addresses a fundamental challenge in network analysis for researchers, providing theoretical limits and enabling recovery in previously impossible scenarios, though it is incremental on prior work.
The paper tackles the problem of exact community recovery from multiple correlated networks, deriving the precise information-theoretic threshold for any constant number of graphs and showing recovery is possible with K graphs even when impossible with K-1 and no latent matchings are recoverable.
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ácz, 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ácz, and Sridhar (COLT 2022). In particular, for every $K \geq 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.