# Ultra-Scalable Spectral Clustering and Ensemble Clustering

arXiv: https://arxiv.org/abs/1903.01057 · HTML: https://mlsanity.com/paper/1903.01057/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

## Built on by (most cited first, 30 of 50)

- [Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity](https://mlsanity.com/paper/2203.11572/) (2022)
- [Unpaired Multi-View Graph Clustering with Cross-View Structure Matching](https://mlsanity.com/paper/2307.03476/) (2023)
- [DivClust: Controlling Diversity in Deep Clustering](https://mlsanity.com/paper/2304.01042/) (2023)
- [Strongly Augmented Contrastive Clustering](https://mlsanity.com/paper/2206.00380/) (2022)
- [Seeking Commonness and Inconsistencies: A Jointly Smoothed Approach to Multi-view Subspace Clustering](https://mlsanity.com/paper/2203.08060/) (2022)
- [Joint Multi-view Unsupervised Feature Selection and Graph Learning](https://mlsanity.com/paper/2204.08247/) (2022)
- [Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph Learning](https://mlsanity.com/paper/2209.04187/) (2022)
- [Divide-and-conquer based Large-Scale Spectral Clustering](https://mlsanity.com/paper/2104.15042/) (2021)
- [Deep Temporal Contrastive Clustering](https://mlsanity.com/paper/2212.14366/) (2022)
- [Efficient Multi-View Graph Clustering with Local and Global Structure Preservation](https://mlsanity.com/paper/2309.00024/) (2023)
- [Adaptively Topological Tensor Network for Multi-view Subspace Clustering](https://mlsanity.com/paper/2305.00716/) (2023)
- [Generation of Granular-Balls for Clustering Based on the Principle of Justifiable Granularity](https://mlsanity.com/paper/2405.06904/) (2024)
- [Continual Learning in 3D Point Clouds: Employing Spectral Techniques for Exemplar Selection](https://mlsanity.com/paper/2409.08388/) (2024)
- [DeepCluE: Enhanced Image Clustering via Multi-layer Ensembles in Deep Neural Networks](https://mlsanity.com/paper/2206.00359/) (2022)
- [GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and Object Tracking](https://mlsanity.com/paper/2206.02200/) (2022)
- [Heterogeneous Tri-stream Clustering Network](https://mlsanity.com/paper/2301.04451/) (2023)
- [k-HyperEdge Medoids for Clustering Ensemble](https://mlsanity.com/paper/2412.08289/) (2024)
- [Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image](https://mlsanity.com/paper/2104.11904/) (2021)
- [VDPC: Variational Density Peak Clustering Algorithm](https://mlsanity.com/paper/2201.00641/) (2021)
- [A Restarted Large-Scale Spectral Clustering with Self-Guiding and Block Diagonal Representation](https://mlsanity.com/paper/2306.15138/) (2023)
- [MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion](https://mlsanity.com/paper/2312.04067/) (2023)
- [Clustering by Mining Density Distributions and Splitting Manifold Structure](https://mlsanity.com/paper/2408.10493/) (2024)
- [Similarity and Dissimilarity Guided Co-association Matrix Construction for Ensemble Clustering](https://mlsanity.com/paper/2411.00904/) (2024)
- [Neural Normalized Cut: A Differential and Generalizable Approach for Spectral Clustering](https://mlsanity.com/paper/2503.09260/) (2025)
- [LSEC: Large-scale spectral ensemble clustering](https://mlsanity.com/paper/2106.09852/) (2021)
- [Clustering and classification of low-dimensional data in explicit feature map domain: intraoperative pixel-wise diagnosis of adenocarcinoma of a colon in a liver](https://mlsanity.com/paper/2203.03636/) (2022)
- [Vision Transformer for Contrastive Clustering](https://mlsanity.com/paper/2206.12925/) (2022)
- [SE-shapelets: Semi-supervised Clustering of Time Series Using Representative Shapelets](https://mlsanity.com/paper/2304.03292/) (2023)
- [Large-scale Fully-Unsupervised Re-Identification](https://mlsanity.com/paper/2307.14278/) (2023)
- [TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization](https://mlsanity.com/paper/2408.10084/) (2024)

## Abstract (arXiv)

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 K-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 ten-million-level nonlinearly-separable datasets on a PC with 64GB 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 https://www.researchgate.net/publication/330760669.