Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models

Abstract

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. Supplementary materials for this article are available online.

KEYWORDS:

• Community detection
• Gene co-expression network
• Matrix concentration inequalities
• Network data
• Spectral clustering
• Stochastic block models

Supplementary Materials

The online supplementary file contains technical proofs of main theorems, and further details about data access, simulation study, real data analysis.

Acknowledgments

We thank Kathryn Roeder, Fuchen Liu, and Xuran Wang for providing the data and code used in Liu et al. (2018) to preprocess the data. We also thank the editor, the associate editor, and two anonymous reviewers for their helpful suggestions to improve the manuscript.

Additional information

Funding

Jing Lei’s research is partially funded by NSF grant DMS-2015492 and NIH grant R01 MH123184.