Exact Community Recovery in Correlated Stochastic Block Models

Julia Gaudio, Miklos Z. Racz, Anirudh Sridhar
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:2183-2241, 2022.

Abstract

We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-gaudio22a, title = {Exact Community Recovery in Correlated Stochastic Block Models}, author = {Gaudio, Julia and Racz, Miklos Z. and Sridhar, Anirudh}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {2183--2241}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/gaudio22a/gaudio22a.pdf}, url = {https://proceedings.mlr.press/v178/gaudio22a.html}, abstract = {We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.} }
Endnote
%0 Conference Paper %T Exact Community Recovery in Correlated Stochastic Block Models %A Julia Gaudio %A Miklos Z. Racz %A Anirudh Sridhar %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-gaudio22a %I PMLR %P 2183--2241 %U https://proceedings.mlr.press/v178/gaudio22a.html %V 178 %X We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.
APA
Gaudio, J., Racz, M.Z. & Sridhar, A.. (2022). Exact Community Recovery in Correlated Stochastic Block Models. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:2183-2241 Available from https://proceedings.mlr.press/v178/gaudio22a.html.

Related Material