Community detection in the multi-view stochastic block model

This paper studies community detection in correlated multi-view graphs from an information-theoretic perspective. We consider multi-view graphs observed from D views on a common node set, where edge variables across views may be statistically dependent. To capture inter-graph correlations, we propose a random graph model called the multi-view stochastic block model (MVSBM), which generates D graphs over n nodes partitioned into two equal-sized communities. For each pair of nodes (i,j), the presence or absence of edges across the D graphs depends on whether i and j belong to the same community. Our goal is to exactly recover the hidden communities from the observed graphs. Our contributions are three-fold. First, we establish an information-theoretic achievability result (Theorem 1), showing that exact recovery is possible when the MVSBM parameters exceed a critical threshold. Second, we derive a matching converse (Theorem 2), proving that below this threshold any estimator has an expected number of misclassified nodes greater than one. Together, these results yield a sharp threshold for exact recovery. Third, we develop a computationally efficient spectral clustering algorithm with a local refinement step. Experiments on MVSBM-generated graphs demonstrate a phase transition that closely matches the theoretical threshold and show that the proposed method outperforms several baselines. Overall, our results delineate the fundamental limits of community detection in correlated multi-view graphs.