Semidefinite Programming for Community Detection with Side Information
  This paper produces an efficient Semidefinite Programming (SDP) solution for
community detection that incorporates non-graph data, which in this context is
known as side information. SDP is an efficient solution for standard community
detection on graphs. We formulate a semi-definite relaxation for the maximum
likelihood estimation of node labels, subject to observing both graph and
non-graph data. This formulation is distinct from the SDP solution of standard
community detection, but maintains its desirable properties. We calculate the
exact recovery threshold for three types of non-graph information, which in
this paper are called side information: partially revealed labels, noisy
labels, as well as multiple observations (features) per node with arbitrary but
finite cardinality. We find that SDP has the same exact recovery threshold in
the presence of side information as maximum likelihood with side information.
Thus, the methods developed herein are computationally efficient as well as
asymptotically accurate for the solution of community detection in the presence
of side information. Simulations show that the asymptotic results of this paper
can also shed light on the performance of SDP for graphs of modest size.
