Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

Miklós Z. Rácz; Anirudh Sridhar

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

Miklós Z. Rácz, Anirudh Sridhar

Statistics and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
Editors	Marc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
Publisher	Neural information processing systems foundation
ISBN (Electronic)	9781713845393
State	Published - 2021
Event	35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online Duration: Dec 6 2021 → Dec 14 2021

Publication series

Name	Advances in Neural Information Processing Systems
Volume	34
ISSN (Print)	1049-5258

Conference

Conference	35th Conference on Neural Information Processing Systems, NeurIPS 2021
City	Virtual, Online
Period	12/6/21 → 12/14/21

Funding

We thank Jasmine Nirody for help with figures. We gratefully acknowledge funding support from NSF under Grant DMS 1811724 (to M.Z.R. and A.S.) and RAPID Grant IIS-2026982 (to A.S.).

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

Rácz, M. Z., & Sridhar, A. (2021). Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021 (Advances in Neural Information Processing Systems; Vol. 34). Neural information processing systems foundation.

Rácz, Miklós Z. ; Sridhar, Anirudh. / Correlated Stochastic Block Models : Exact Graph Matching with Applications to Recovering Communities. Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. editor / Marc'Aurelio Ranzato ; Alina Beygelzimer ; Yann Dauphin ; Percy S. Liang ; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. (Advances in Neural Information Processing Systems).

@inproceedings{2f3e4768cc4d4806945fa2a2eb8cf12e,

title = "Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities",

abstract = "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.",

author = "R{\'a}cz, {Mikl{\'o}s Z.} and Anirudh Sridhar",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE Computer Society. All rights reserved.; 35th Conference on Neural Information Processing Systems, NeurIPS 2021 ; Conference date: 06-12-2021 Through 14-12-2021",

year = "2021",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

editor = "Marc'Aurelio Ranzato and Alina Beygelzimer and Yann Dauphin and Liang, {Percy S.} and {Wortman Vaughan}, Jenn",

booktitle = "Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021",

}

Rácz, MZ & Sridhar, A 2021, Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities. in MA Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Advances in Neural Information Processing Systems, vol. 34, Neural information processing systems foundation, 35th Conference on Neural Information Processing Systems, NeurIPS 2021, Virtual, Online, 12/6/21.

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities. / Rácz, Miklós Z.; Sridhar, Anirudh.
Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. ed. / Marc'Aurelio Ranzato; Alina Beygelzimer; Yann Dauphin; Percy S. Liang; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. (Advances in Neural Information Processing Systems; Vol. 34).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Correlated Stochastic Block Models

T2 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

AU - Rácz, Miklós Z.

AU - Sridhar, Anirudh

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85128013582&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85128013582&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85128013582

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

A2 - Ranzato, Marc'Aurelio

A2 - Beygelzimer, Alina

A2 - Dauphin, Yann

A2 - Liang, Percy S.

A2 - Wortman Vaughan, Jenn

PB - Neural information processing systems foundation

Y2 - 6 December 2021 through 14 December 2021

ER -

Rácz MZ, Sridhar A. Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities. In Ranzato MA, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, editors, Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Neural information processing systems foundation. 2021. (Advances in Neural Information Processing Systems).

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this