Optimal Clustering of Multi-layer Networks under Mixture Block Models
Abstract
We study clustering for multi-layer networks, where each observation is an undirected network measured on the same set of vertices. Under the mixture multi-layer stochastic block model (MMSBM), each network is generated from one of two stochastic block models, and the goal is to recover the latent network labels. We establish the minimax optimal network clustering error rate, which takes an exponential form and is characterized by the Chernoff information between the edge probability distributions of the component networks. We propose a novel two-stage estimator that combines tensor-based initialization, node and sample splitting, and a likelihood-based refinement. The refinement step exploits estimated node communities and achieves the minimax rate with high probability under extreme network sparsity. We further extend the likelihood-refinement framework to count-weighted networks through a mixture multi-layer Poisson block model. Numerical studies and two real-data analyses illustrate the finite-sample behavior of the proposed method and its use for both external-label benchmarking and unlabeled exploratory network clustering.
