  We consider the problem of estimating common community structures in
multi-layer stochastic block models, where each single layer may not have
sufficient signal strength to recover the full community structure. In order to
efficiently aggregate signal across different layers, we argue that the
sum-of-squared adjacency matrices contain sufficient signal even when
individual layers are very sparse. Our method uses a bias-removal step that is
necessary when the squared noise matrices may overwhelm the signal in the very
sparse regime. The analysis of our method relies on several novel tail
probability bounds for matrix linear combinations with matrix-valued
coefficients and matrix-valued quadratic forms, which may be of independent
interest. The performance of our method and the necessity of bias removal is
demonstrated in synthetic data and in microarray analysis about gene
co-expression networks.
