Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block
  Models, and Multi-layer Networks
Zhongyuan Lyu Ting Li Dong Xia
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.