Fast Spectral Clustering with Landmark-Based Subspace Iteration

Spectral clustering has received a great deal of attention due to its flexibility on various type of geometry and its high-quality clustering results. However, with the rapid increase of data size, spectral clustering quickly becomes unfeasible because of its cubical complexity. Various sampling methods with at best quadratic complexity in time and space have been purposed. However, they are not able to jump out of the box for their dependency on eigen-decomposition. In this paper, we propose a novel framework called Landmark-based Subspace Iteration Spectral Clustering (LSISC), which scales linearly on both time and space with data size. Specifically, we use the similarity between points and landmarks as the new feature of points, and exploit subspace iteration to perform spectral clustering in near-linear time, while no pair-wise information is dropped. We show that the running time of LSISC is not sensitive to the number of landmarks, which allows more landmarks to be chosen for better accuracy. Experimental results show that our approach gives better clustering results in much less time than other state-of-the-art spectral methods.