Exact Recovery by Semidefinite Programming in the Binary Stochastic Block Model with Partially Revealed Side Information

摘要

We propose a semidefinite programming (SDP) approach to community detection in graphs in the presence of additional non-graphical side information, and analyze the corresponding exact recovery threshold. The community detection problem is considered in the context of the binary symmetric Stochastic Block Model (SBM), and the side information is in the form of partially revealed labels with erasure probability ε. Our results show that the semidefinite programming relaxation of the maximum likelihood estimator can achieve exact recovery down to the optimal threshold. The theoretical findings of this paper are validated via simulations on finite synthetic data-sets, showing that the asymptotic results of this paper can also shed light on the performance at finite n.