Contextual Stochastic Block Models
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.
UPDATE after authors' rebuttal I am quite happy about the scientific answers provided by the authors. Hence I upgrade my score from 6 to 7. Hoping it will be enough for an acceptance to NIPS (competition is harsh!), and if not, still hoping to read your work somewhere!  This paper is about the clustering of statistical entities for which network data and individual measurements are available. The article reads well and is technically sound. he numerical experiments are disappointing, I don't really understand how they illustrate the performance of the method. I would have expected some accuracy measure for the methods on its ability to identify meaningful clusters. Moreover, I challenge the novelty of the approach presented here. It was easy to find references like https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5890472/ (very similar problem with the same kind of data) or less recently https://ieeexplore.ieee.org/document/4359897/ (with the implementation the authors published in https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3051335/, you could well compare to your approach). I truly feel you should compare the method you present to the state-of-the-art literature. To me, your model resembles a Hidden Conditional Random Fields (or a Markov Random Fields) via Equations (1) and (2). Details:  - l17, the A data is not necessarily a 'similarity' measure, it could just be a graph measure directly defined, e.g. regulatory relationships. A similarity measure is more a representation of similar measures on nodes, hence more a proxy for a B data in your settings.  - l65: you focus on bi-partitioning, which in graph is clearly an easier (yet challenging) special case of the general framework. Why is that? How can your method be applied with K classes and K>2?  - I quite like the 'in Other words...' explanation of our theorems.  - What is a 'Claim' for you? A Proposition? A conjecture?  - Again, your algorithm (Section 4) could be compared to traditional approaches like Variational Inference and MCMC strategies.  - In the reference, make the style uniform: with or without first names?