We study the effect of side information on the information theoretic limits of recovering a single sub-graph (community) hidden in a large graph, where the community size is much smaller than the graph size. Two asymptotic recovery metrics are considered: weak recovery and exact recovery. We consider side information in the form of a vector of random variables that have a prescribed distribution conditioned on the node labels.  We show when and by how much side information can improve the information theoretic limits of weak and exact recovery. Furthermore, we show that, under certain conditions, any algorithm achieving weak recovery can also achieve exact recovery if followed by a local voting procedure.