Contextual Stochastic Block Models

Abstract

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.

arXiv comment28 pages, 1 figure, conference submission

Cited by in corpus (18)

• Adaptive Universal Generalized PageRank Graph Neural Network
• Is Homophily a Necessity for Graph Neural Networks?
• Subgroup Generalization and Fairness of Graph Neural Networks
• New Benchmarks for Learning on Non-Homophilous Graphs
• On Provable Benefits of Depth in Training Graph Convolutional Networks
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• Community Detection with Contextual Multilayer Networks
• $p$-Laplacian Based Graph Neural Networks
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• A Time-Varying Network for Cryptocurrencies
• An ${\ell }_p$ theory of PCA and spectral clustering
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• SCG: Spotting Coordinated Groups in Social Media