  We provide the first information theoretic tight analysis for inference of
latent community structure given a sparse graph along with high dimensional
node covariates, correlated with the same latent communities. Our work bridges
recent theoretical breakthroughs in the detection of latent community structure
without nodes covariates and a large body of empirical work using diverse
heuristics for combining node covariates with graphs for inference. The
tightness of our analysis implies in particular, the information theoretical
necessity of combining the different sources of information. Our analysis holds
for networks of large degrees as well as for a Gaussian version of the model.
