Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification

Yongyu Wang, Zhuo Feng

The eigendeomposition of nearest-neighbor (NN) graph Laplacian matrices is the main computational bottleneck in spectral clustering. In this work, we introduce a highly-scalable, s…