Achieving exact cluster recovery threshold via semidefinite programming

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. [1]. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1442-1446
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - Sep 28 2015
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: Jun 14 2015Jun 19 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2015-June
ISSN (Print)2157-8095

Other

OtherIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period6/14/156/19/15

Fingerprint

Semidefinite Programming
Recovery
Semidefinite Programming Relaxation
Maximum likelihood
Optimal Recovery
Random Graphs
Maximum Likelihood Estimator
Subgraph
Directly proportional
Partition
Binary
Graph in graph theory
Model

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

Hajek, B., Wu, Y., & Xu, J. (2015). Achieving exact cluster recovery threshold via semidefinite programming. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 1442-1446). [7282694] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282694

Achieving exact cluster recovery threshold via semidefinite programming. / Hajek, Bruce; Wu, Yihong; Xu, Jiaming.

Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 1442-1446 7282694 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Hajek, B, Wu, Y & Xu, J 2015, Achieving exact cluster recovery threshold via semidefinite programming. in Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015., 7282694, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 1442-1446, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7282694
Hajek B, Wu Y, Xu J. Achieving exact cluster recovery threshold via semidefinite programming. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 1442-1446. 7282694. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2015.7282694
Hajek, Bruce ; Wu, Yihong ; Xu, Jiaming. / Achieving exact cluster recovery threshold via semidefinite programming. Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 1442-1446 (IEEE International Symposium on Information Theory - Proceedings).
@inproceedings{33c5f1a326a04df9a9109af32d7283b4,
title = "Achieving exact cluster recovery threshold via semidefinite programming",
abstract = "The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. [1]. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.",
author = "Bruce Hajek and Yihong Wu and Jiaming Xu",
year = "2015",
month = "9",
day = "28",
doi = "10.1109/ISIT.2015.7282694",
language = "English (US)",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1442--1446",
booktitle = "Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015",
address = "United States",

}

TY - GEN

T1 - Achieving exact cluster recovery threshold via semidefinite programming

AU - Hajek, Bruce

AU - Wu, Yihong

AU - Xu, Jiaming

PY - 2015/9/28

Y1 - 2015/9/28

N2 - The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. [1]. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

AB - The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. [1]. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

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

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

U2 - 10.1109/ISIT.2015.7282694

DO - 10.1109/ISIT.2015.7282694

M3 - Conference contribution

AN - SCOPUS:84969820675

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1442

EP - 1446

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -