Fast Spectral Clustering with efficient large graph construction

Spectral clustering has been regarded as a powerful tool for unsupervised tasks despite its excellent performance, the high computational cost has become a bottleneck which limits its application for large scale problems. Recent studies on anchor-based graph can partly alleviate the problem, however, it is still a great challenge to deal with such data with both high performance and high efficiency. In this paper, we propose Fast Spectral Clustering (FSC) to efficiently deal with large scale data. The proposed method first constructs anchor-based similarity graph with Balanced K-means based Hierarchical K-means (BKHK) algorithm, and then performs spectral analysis on the graph. The overall computational complexity is O(ndm), where n is the number of samples, d is the number of features, and m is the number of anchors. Comprehensive experiments on several large scale data sets demonstrate the effectiveness and efficiency of the proposed method.