Technical Program

Paper Detail

Paper Title Community Detection with Side Information via Semidefinite Programming
Paper IdentifierMO3.R5.5
Authors Mohammad Esmaeili, Hussein Saad, Aria Nosratinia, University of Texas at Dallas, United States
Session Community Detection and Graphical Models
Location Saint Victor, Level 3
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 15:50 - 16:10
Manuscript  Click here to download the manuscript
Abstract Semidefinite programming is known to be both efficient and asymptotically optimal in solving community detection problems, but it has been studied in this context only when observations are purely graphical in nature. In this paper, we extend the use of semidefinite programming in community detection to observations that have both a graphical and a non-graphical component. We consider the binary censored block model with $n$ nodes and study the effect of partially revealed labels on the performance of semidefinite programming. We address the question: do partially revealed labels help the semidefinite programming solution as much as they help the maximum likelihood solution? Our results are twofold. First, we show that partially revealed labels change the phase transition of exact recovery if and only if the information they provide grows no slower than $\Omega(\log(n))$. Second, we show that the semidefinite programming relaxation of maximum likelihood can achieve exact recovery down to the optimal threshold under partially revealed labels.