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

Yihong Wu; Jiaming Xu; Bruce Hajek

doi:10.1109/ACSSC.2015.7421303

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 proceeding › Conference 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 language	English (US)
Title of host publication	Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	1070-1074
Number of pages	5
ISBN (Electronic)	9781467385763
DOIs	https://doi.org/10.1109/ACSSC.2015.7421303
State	Published - Feb 26 2016
Event	49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States Duration: Nov 8 2015 → Nov 11 2015

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Volume	2016-February
ISSN (Print)	1058-6393

Other

Other	49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Country/Territory	United States
City	Pacific Grove
Period	11/8/15 → 11/11/15

ASJC Scopus subject areas

Signal Processing
Computer Networks and Communications

Online availability

10.1109/ACSSC.2015.7421303

Library availability

Discover UIUC Full Text

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). Article 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 proceeding › Conference 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). doi: 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",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 ; Conference date: 08-11-2015 Through 11-11-2015",

year = "2016",

month = feb,

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

T2 - 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

Y2 - 8 November 2015 through 11 November 2015

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this