Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks
This work addresses the fundamental limit of clustering in multi-layer networks and discrete mixtures, providing optimal error rates and a practical algorithm, which is significant for network analysis and statistical learning but appears incremental as it builds on existing mixture models and clustering methods.
The paper tackles the problem of clustering networks under a mixture multi-layer stochastic block model, showing that the minimax optimal clustering error rate takes an exponential form characterized by Renyi divergence and proposing a two-stage algorithm that achieves this rate, with validation from simulations and real data. It extends this to discrete mixtures like Binomial and Poisson, where the same exponential error rate holds and is achievable by their algorithm.
In this paper, we first study the fundamental limit of clustering networks when a multi-layer network is present. Under the mixture multi-layer stochastic block model (MMSBM), we show that the minimax optimal network clustering error rate, which takes an exponential form and is characterized by the Renyi divergence between the edge probability distributions of the component networks. We propose a novel two-stage network clustering method including a tensor-based initialization algorithm involving both node and sample splitting and a refinement procedure by likelihood-based Lloyd algorithm. Network clustering must be accompanied by node community detection. Our proposed algorithm achieves the minimax optimal network clustering error rate and allows extreme network sparsity under MMSBM. Numerical simulations and real data experiments both validate that our method outperforms existing methods. Oftentimes, the edges of networks carry count-type weights. We then extend our methodology and analysis framework to study the minimax optimal clustering error rate for mixture of discrete distributions including Binomial, Poisson, and multi-layer Poisson networks. The minimax optimal clustering error rates in these discrete mixtures all take the same exponential form characterized by the Renyi divergences. These optimal clustering error rates in discrete mixtures can also be achieved by our proposed two-stage clustering algorithm.