Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
This work addresses the challenge of community detection in networks for researchers in statistics and machine learning, providing a theoretical foundation for exact recovery in correlated settings, though it is incremental as it builds on existing stochastic block model frameworks.
The paper tackles the problem of learning latent community structure from multiple correlated networks by deriving the information-theoretic threshold for exact recovery of vertex correspondence in edge-correlated stochastic block models, showing that exact recovery is possible above this threshold and impossible below it. As a result, it demonstrates that using multiple correlated graphs can enable exact community recovery in regimes where a single graph fails, with the threshold depending on logarithmic average degrees.
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.