On the Power of SVD in the Stochastic Block Model
This provides theoretical justification for a common heuristic in clustering, addressing an open question in the symmetric stochastic block model.
The paper tackles the problem of understanding why spectral dimensionality reduction improves clustering by analyzing the vanilla-SVD algorithm in the stochastic block model, showing that it correctly recovers all clusters in symmetric settings.
A popular heuristic method for improving clustering results is to apply dimensionality reduction before running clustering algorithms. It has been observed that spectral-based dimensionality reduction tools, such as PCA or SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves as a dimensionality reduction tool, but also contributes to the clustering procedure in some sense. It is an interesting question to understand the behavior of spectral steps in clustering problems. As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers an open question posed by Van Vu (Combinatorics Probability and Computing, 2018) in the symmetric setting.