Contextual Stochastic Block Models
Yash Deshpande, Subhabrata Sen, Andrea Montanari, Elchanan Mossel
Abstract
We provide the first information theoretical 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 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 theoretic 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.
BibTeX
@inproceedings{NEURIPS2018_08fc80de,
author = {Deshpande, Yash and Sen, Subhabrata and Montanari, Andrea and Mossel, Elchanan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Contextual Stochastic Block Models},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/08fc80de8121419136e443a70489c123-Paper.pdf},
volume = {31},
year = {2018}
}