  The community detection problem involves making inferences about node labels
in a graph, based on observing the graph edges. This paper studies the effect
of additional, non-graphical side information on the phase transition of exact
recovery in the binary stochastic block model (SBM) with $n$ nodes. When side
information consists of noisy labels with error probability $\alpha$, it is
shown that phase transition is improved if and only if
$\log(\frac{1-\alpha}{\alpha})=\Omega(\log(n))$. When side information consists
of revealing a fraction $1-\epsilon$ of the labels, it is shown that phase
transition is improved if and only if $\log(1/\epsilon)=\Omega(\log(n))$. For a
more general side information consisting of $K$ features, two scenarios are
studied: (1)~$K$ is fixed while the likelihood of each feature with respect to
corresponding node label evolves with $n$, and (2)~The number of features $K$
varies with $n$ but the likelihood of each feature is fixed. In each case, we
find when side information improves the exact recovery phase transition and by
how much. The calculated necessary and sufficient conditions for exact recovery
are tight except for one special case. In the process of deriving inner bounds,
a variation of an efficient algorithm is proposed for community detection with
side information that uses a partial recovery algorithm combined with a local
improvement procedure.
