Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model

Yihong Wu, Jiaming Xu, Bruce Hajek

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

Abstract

Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold under the stochastic block model with a fixed number of equal-sized clusters.

Original languageEnglish (US)
Title of host publicationConference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages1070-1074
Number of pages5
ISBN (Electronic)9781467385763
DOIs
StatePublished - Feb 26 2016
Event49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States
Duration: Nov 8 2015Nov 11 2015

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2016-February
ISSN (Print)1058-6393

Other

Other49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
CountryUnited States
CityPacific Grove
Period11/8/1511/11/15

Fingerprint

Recovery
Maximum likelihood

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Cite this

Wu, Y., Xu, J., & Hajek, B. (2016). Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. In M. B. Matthews (Ed.), Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 (pp. 1070-1074). [7421303] (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2016-February). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2015.7421303

Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. / Wu, Yihong; Xu, Jiaming; Hajek, Bruce.

Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. ed. / Michael B. Matthews. IEEE Computer Society, 2016. p. 1070-1074 7421303 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2016-February).

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

Wu, Y, Xu, J & Hajek, B 2016, Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. in MB Matthews (ed.), Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015., 7421303, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2016-February, IEEE Computer Society, pp. 1070-1074, 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015, Pacific Grove, United States, 11/8/15. https://doi.org/10.1109/ACSSC.2015.7421303
Wu Y, Xu J, Hajek B. Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. In Matthews MB, editor, Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. IEEE Computer Society. 2016. p. 1070-1074. 7421303. (Conference Record - Asilomar Conference on Signals, Systems and Computers). https://doi.org/10.1109/ACSSC.2015.7421303
Wu, Yihong ; Xu, Jiaming ; Hajek, Bruce. / Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. editor / Michael B. Matthews. IEEE Computer Society, 2016. pp. 1070-1074 (Conference Record - Asilomar Conference on Signals, Systems and Computers).
@inproceedings{9b4eeebe67c64148aa9ed5632ef9f7dc,
title = "Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model",
abstract = "Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold under the stochastic block model with a fixed number of equal-sized clusters.",
author = "Yihong Wu and Jiaming Xu and Bruce Hajek",
year = "2016",
month = "2",
day = "26",
doi = "10.1109/ACSSC.2015.7421303",
language = "English (US)",
series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",
publisher = "IEEE Computer Society",
pages = "1070--1074",
editor = "Matthews, {Michael B.}",
booktitle = "Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015",

}

TY - GEN

T1 - Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model

AU - Wu, Yihong

AU - Xu, Jiaming

AU - Hajek, Bruce

PY - 2016/2/26

Y1 - 2016/2/26

N2 - Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold under the stochastic block model with a fixed number of equal-sized clusters.

AB - Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold under the stochastic block model with a fixed number of equal-sized clusters.

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

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

U2 - 10.1109/ACSSC.2015.7421303

DO - 10.1109/ACSSC.2015.7421303

M3 - Conference contribution

AN - SCOPUS:84969888729

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1070

EP - 1074

BT - Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

A2 - Matthews, Michael B.

PB - IEEE Computer Society

ER -