Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms

Community detection in the stochastic block model is one of the central problems of graph clustering. Since its introduction by Holland, Laskey and Leinhardt (Social Networks, 1983), many subsequent papers have made great strides in solving and understanding this model. In this setup, spectral algorithms have been one of the most widely used frameworks for the design of clustering algorithms. However, despite the long history of study, there are still unsolved challenges. One of the main open problems is the design and analysis of "simple"(vanilla) spectral algorithms, especially when the number of communities is large.

In this paper, we provide two algorithms. The first one is based on the power-iteration method. This is a simple algorithm which only compares the rows of the powered adjacency matrix. Our algorithm performs optimally (up to logarithmic factors) compared to the best known bounds in the dense graph regime by Van Vu (Combinatorics Probability and Computing, 2018). Furthermore, our algorithm is also robust to the "small cluster barrier", recovering large clusters in the presence of an arbitrary number of small clusters. Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a "vanilla" spectral algorithm for large number of communities in the balanced case. This answers an open question by Van Vu (Combinatorics Probability and Computing, 2018) in the balanced case. Our methods also partially solve technical barriers discussed by Abbe, Fan, Wang and Zhong (Annals of Statistics, 2020).

In the technical side, we introduce a random partition method to analyze each entry of a powered random matrix. This method can be viewed as an eigenvector version of Wigner's trace method. Recall that Wigner's trace method links the trace of powered matrix to eigenvalues.

Our method links the whole powered matrix to the span of eigenvectors. We expect our method to have more applications in random matrix theory.