RESKM: A General Framework to Accelerate Large-Scale Spectral Clustering

• Published in: Pattern recognition 2023-05, Vol.137, p.109275, Article 109275
• Main Authors: Yang, Geping, Deng, Sucheng, Chen, Xiang, Chen, Can, Yang, Yiyang, Gong, Zhiguo, Hao, Zhifeng
• Format: Article
• Language: English
• Subjects: Large-scale; Machine learning; Spectral clustering; Unsupervised learning
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2022.109275

•A general and unified framework Robust and Efficient Spectral k-Means (RESKM) is proposed in this work to accelerate the large-scale Spectral Clustering.•Each phase in RESKM is conducted with high interpretability, its bottleneck is analyzed theoretically, and the corresponding accelerating solution is given.•The evaluation of commonly used datasets demonstrates that the proposed RESKM is robust and outstanding. More significantly, compared with SOTA methods, the efficiency gain of our RESKM is prominent. Spectral Clustering is an effective preprocessing method in communities for its excellent performance, but its scalability still is a challenge. Many efforts have been made to face this problem, and several solutions are proposed, including Nyström Approximation, Sparse Representation Approximation, etc. However, according to our survey, there is still a large room for improvement. This work thoroughly investigates the factors relevant to large-scale Spectral Clustering and proposes a general framework to accelerate Spectral Clustering by utilizing the Robust and Efficient Spectral k-Means (RESKM). The contributions of RESKM are three folds: (1) a unified framework is proposed for large-scale Spectral Clustering; (2) it consists of four phases, each phase is theoretically analyzed, and the corresponding acceleration is suggested; (3) the majority of the existing large-scale Spectral Clustering methods can be integrated into RESKM and therefore be accelerated. Experiments on datasets with different scalability demonstrate that the robustness and efficiency of RESKM.