This paper considers the problem of community detection on multiple
potentially correlated graphs from an information-theoretical perspective. We
first put forth a random graph model, called the multi-view stochastic block
model (MVSBM), designed to generate correlated graphs on the same set of nodes
(with cardinality $n$). The $n$ nodes are partitioned into two disjoint
communities of equal size. The presence or absence of edges in the graphs for
each pair of nodes depends on whether the two nodes belong to the same
community or not. The objective for the learner is to recover the hidden
communities with observed graphs. Our technical contributions are two-fold: (i)
We establish an information-theoretic upper bound (Theorem~1) showing that
exact recovery of community is achievable when the model parameters of MVSBM
exceed a certain threshold. (ii) Conversely, we derive an information-theoretic
lower bound (Theorem~2) showing that when the model parameters of MVSBM fall
below the aforementioned threshold, then for any estimator, the expected number
of misclassified nodes will always be greater than one. Our results for the
MVSBM recover several prior results for community detection in the standard SBM
as well as in multiple independent SBMs as special cases.

该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM)，我们得出了一个信息论的上界和下界，当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复，否则期望的错误分类节点数将大于一。