Ultra-Scalable Spectral Clustering and Ensemble Clustering

By Dong Huang, Changdong Wang, Jian-Sheng Wu, J. Lai, Chee Keong Kwoh. IEEE Transactions on Knowledge and Data Engineering, 2019

448 citations recorded by the source corpus.

This paper focuses on scalability and robustness of spectral clustering for extremely large-scale datasets with limited resources. Two novel algorithms are proposed, namely, ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for <inline-formula><tex-math notation="LaTeX">$K$</tex-math><alternatives><mml:math><mml:mi>K</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq1-2903410.gif"/></alternatives></inline-formula>-nearest representatives are proposed for the construction of a sparse affinity sub-matrix. By interpreting the sparse sub-matrix as a bipartite graph, the transfer cut is then utilized to efficiently partition the graph and obtain the clustering result. In U-SENC, multiple U-SPEC clusterers are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC while maintaining high efficiency. Based on the ensemble generation via multiple U-SEPC's, a new bipartite graph is constructed between objects and base clusters and then efficiently partitioned to achieve the consensus clustering result. It is noteworthy that both U-SPEC and U-SENC have nearly linear time and space complexity, and are capable of robustly and efficiently partitioning 10-million-level nonlinearly-separable datasets on a PC with 64 GB memory. Experiments on various large-scale datasets have demonstrated the scalability and robustness of our algorithms. The MATLAB code and experimental data are available at <uri>https://www.researchgate.net/publication/330760669</uri>.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/d21a6b0d4d14afc5f6403c6743aba27671a0f7da

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Xiangwen Wang
2. Zhenyu Lu
3. Yue Xi
4. Yonggang Lu
5. Xingcheng Ran

In Computer Vision and Pattern Recognition

1. Xiangwen Wang
2. Zhenyu Lu
3. Yue Xi
4. Yonggang Lu
5. Xingcheng Ran

Citations in the corpus

• Comprehensive survey on hierarchical clustering algorithms and the recent developments (2022, methodology): “…c l u s t e r i ng m e t hod s (Zahn 1971; Guan and Du 1998), CLICK (Sharan and Shamir 2000), Spectral clustering (von Luxburg 2007), improvements of Spectral clustering (Chen et al. 2011; Cai and Chen 2015; He et al. 2019; Huang et al. 2020), and Kemighan–Lin (KL) method (Kernighan and Lin 1970).”