Scalable Algorithms Using Sparse Storage for Parallel Spectral Clustering on GPU

Overview & Synopsis

Spectral clustering has many fundamental advantages over k-means, but has high computational complexity (O(n**3)) and memory requirement (O(n**2)), making it prohibitively expensive for large datasets. In this paper we present our solution on GPU to address the scalability challenge of spectral clustering. First, we propose optimized algorithms for constructing similarity matrix directly in CSR sparse format on the GPU. Next, we leverage the spectral graph partitioning API of the GPU-accelerated nvGRAPH library for remaining computations especially for eigenvector extraction. Finally, experiments on synthetic and real-world large datasets demonstrate the high performance and scalability of our GPU implementation for spectral clustering.