A Caltech Library Service

Exact Recovery in the Balanced Stochastic Block Model with Side Information

Sima, Jin and Zhao, Feng and Huang, Shao-Lun (2021) Exact Recovery in the Balanced Stochastic Block Model with Side Information. In: 2021 IEEE Information Theory Workshop (ITW). IEEE , Piscataway, NJ, pp. 1-6. ISBN 978-1-6654-0312-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Sima, Jin0000-0003-4588-9790
Additional Information:© 2021 IEEE.
Record Number:CaltechAUTHORS:20220105-582974400
Persistent URL:
Official Citation:J. Sima, F. Zhao and S. -L. Huang, "Exact Recovery in the Balanced Stochastic Block Model with Side Information," 2021 IEEE Information Theory Workshop (ITW), 2021, pp. 1-6, doi: 10.1109/ITW48936.2021.9611438
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112714
Deposited By: Tony Diaz
Deposited On:09 Jan 2022 21:36
Last Modified:25 Jul 2022 23:14

Repository Staff Only: item control page