Exact Recovery in the Balanced Stochastic Block Model with Side Information

Authors

Image provided by Jin Sima
Jin
Sima
California Institute of Technology
Profile
Feng
Zhao
Graduate School at Shenzhen, Tsinghua University
Profile
Shao-Lun
Huang
Tsinghua-Berkeley Shenzhen Institute

Abstract

The role that side information plays in improving the exact recovery threshold in the stochastic block model (SBM) has been studied in many aspects. This paper studies exact recovery in n node balanced binary symmetric SBM with side information, given in the form of O(log n) i.i.d. samples at each node. A sharp exact recovery threshold is obtained and turns out to coincide with an existing threshold result, where no balanced constraint is imposed. Our main contribution is an efficient semi-definite programming (SDP) algorithm that achieves the optimal exact recovery threshold. Compared to the existing works on SDP algorithm for SBM with constant number of samples as side information, the challenge in this paper is to deal with the number of samples increasing in n.

Paper Manuscript