Fast Compressive Spectral Clustering for Large-Scale Sparse Graph

Spectral clustering (SC) is an unsupervised learning method that has been widely used in industrial product analysis. Compressive spectral clustering (CSC) effectively accelerates clustering by leveraging graph filter and random sampling techniques. However, CSC suffers from two major problems. First, the direct use of the dichotomy and eigencount techniques for estimating Laplacian matrix's kth eigenvalue is expensive. Second, the computation of interpolation is time-consuming because it requires to repeat matrix-vector product for every cluster in each iteration. To address these problems, we propose a new method called fast compressive spectral clustering (FCSC). Our method addresses the first problem by assuming that the eigenvalues approximately satisfy local uniform distribution, and addresses the second problem by recalculating the pairwise similarity between nodes with low-dimensional representation to reconstruct denoised laplacian matrix. The time complexity of reconstruction is linear with the number of non-zeros in Laplacian matrix. As experimentally demonstrated on both artificial and real-world datasets, our method significantly reduces the computation time while preserving high clustering accuracy comparable to previous designs, demonstrating the effectiveness of FCSC.

Automated summary

Spectral clustering (SC) is widely used in industrial product analysis as an unsupervised learning method. Compressive spectral clustering (CSC) accelerates clustering effectively but suffers from expensive computation and time-consuming interpolation. The proposed fast compressive spectral clustering (FCSC) method addresses these issues by assuming eigenvalues satisfy local uniform distribution and reconstructing denoised Laplacian matrix with low-dimensional representation. The experimental results show that FCSC significantly reduces computation time while maintaining high clustering accuracy.