Faster Spectral Clustering with Approximation Guarantee

Spectral clustering is a basic algorithm in machine learning with widespread applications. However, classical spectral clustering requires computing the bottom eigenvectors of the Laplacian of the input graph, which leads to high time complexity. To address this limitation, we propose a faster clustering algorithm based on coresets and the Nyström method, and prove that it achieves the same approximation guarantee as classical spectral clustering. We empirically evaluate our algorithm on both synthetic and real-world datasets, and the results confirm that our algorithm runs substantially faster while producing results comparable to those of classical spectral clustering.