TY - GEN
T1 - Achieving exact cluster recovery threshold via semidefinite programming
AU - Hajek, Bruce
AU - Wu, Yihong
AU - Xu, Jiaming
N1 - Funding Information:
This research was supported by the National Science Foundation under Grant ECCS 10-28464, IIS-1447879, and CCF-1423088, and Strategic Research Initiative on Big-Data Analytics of the College of Engineering at the University of Illinois.
Publisher Copyright:
© 2015 IEEE.
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.
T2 - IEEE International Symposium on Information Theory, ISIT 2015
Y2 - 14 June 2015 through 19 June 2015
ER -