Exact Recovery in the Balanced Stochastic Block Model with Side Information
- Creators
- Sima, Jin
- Zhao, Feng
- Huang, Shao-Lun
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.
Additional Information
© 2021 IEEE.Additional details
- Eprint ID
- 112714
- DOI
- 10.1109/itw48936.2021.9611438
- Resolver ID
- CaltechAUTHORS:20220105-582974400
- Created
-
2022-01-09Created from EPrint's datestamp field
- Updated
-
2022-07-25Created from EPrint's last_modified field