Spectral clustering has many fundamental advantages over k-means clustering, but comes at much higher time complexity and memory requirements mainly due to similarity matrix construction and eigenvectors computation. Thus, spectral clustering is prohibitively expensive for processing large datasets. In this paper we address the scalability challenge of spectral clustering on single-GPU architectures. An \(n \times n\) similarity matrix generally contains many elements close to zero, and can become very sparse by applying a threshold on matrix elements. Then it can take advantage of sparse storage format like CSR if the matrix is generated directly in sparse format, which allows processing large datasets on just one GPU device. We obtain a sparse similarity matrix by constructing the \(\epsilon\) -neighborhood similarity graph and generating the associated sparse matrix in the CSR format on the GPU. Then we leverage the spectral graph partitioning API of the GPU-accelerated nvGRAPH library for remaining computations especially the eigen-decomposition. Finally, we provide experiments on synthetic and real-world large datasets which demonstrate the performance and scalability of our GPU implementation for spectral clustering.
