# Divide-and-conquer based Large-Scale Spectral Clustering

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 37 references that are in the map.
- First posted on arXiv 30 Apr 2021.

## Builds on (most cited first, 1 of 1)

- [Ultra-Scalable Spectral Clustering and Ensemble Clustering](https://mlsanity.com/paper/1903.01057/) (2019)

## Built on by (most cited first, 5 of 5)

- [Generation of Granular-Balls for Clustering Based on the Principle of Justifiable Granularity](https://mlsanity.com/paper/2405.06904/) (2024)
- [A Restarted Large-Scale Spectral Clustering with Self-Guiding and Block Diagonal Representation](https://mlsanity.com/paper/2306.15138/) (2023)
- [LSEC: Large-scale spectral ensemble clustering](https://mlsanity.com/paper/2106.09852/) (2021)
- [FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling](https://mlsanity.com/paper/2605.11428/) (2026)
- [Eigenvalue-based Incremental Spectral Clustering](https://mlsanity.com/paper/2308.10999/) (2023)

## Abstract (arXiv)

Spectral clustering is one of the most popular clustering methods. However, how to balance the efficiency and effectiveness of the large-scale spectral clustering with limited computing resources has not been properly solved for a long time. In this paper, we propose a divide-and-conquer based large-scale spectral clustering method to strike a good balance between efficiency and effectiveness. In the proposed method, a divide-and-conquer based landmark selection algorithm and a novel approximate similarity matrix approach are designed to construct a sparse similarity matrix within low computational complexities. Then clustering results can be computed quickly through a bipartite graph partition process. The proposed method achieves a lower computational complexity than most existing large-scale spectral clustering methods. Experimental results on ten large-scale datasets have demonstrated the efficiency and effectiveness of the proposed method. The MATLAB code of the proposed method and experimental datasets are available at https://github.com/Li-Hongmin/MyPaperWithCode.