# A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 69 references that are in the map.
- First posted on arXiv 8 Dec 2022.

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

- [Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication](https://mlsanity.com/paper/1510.00844/) (2015)
- [MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization](https://mlsanity.com/paper/1609.09154/) (2016)
- [Design, Generation, and Validation of Extreme Scale Power-Law Graphs](https://mlsanity.com/paper/1803.01281/) (2018)

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

- [Spectral Clustering via Orthogonalization-Free Methods](https://mlsanity.com/paper/2305.10356/) (2023)
- [Wormhole: Concept-Aware Deep Representation Learning for Co-Evolving Sequences](https://mlsanity.com/paper/2409.13857/) (2024)

## Abstract (arXiv)

We develop a distributed Block Chebyshev-Davidson algorithm to solve large-scale leading eigenvalue problems for spectral analysis in spectral clustering. First, the efficiency of the Chebyshev-Davidson algorithm relies on the prior knowledge of the eigenvalue spectrum, which could be expensive to estimate. This issue can be lessened by the analytic spectrum estimation of the Laplacian or normalized Laplacian matrices in spectral clustering, making the proposed algorithm very efficient for spectral clustering. Second, to make the proposed algorithm capable of analyzing big data, a distributed and parallel version has been developed with attractive scalability. The speedup by parallel computing is approximately equivalent to √p, where p denotes the number of processes. Numerical results will be provided to demonstrate its efficiency in spectral clustering and scalability advantage over existing eigensolvers used for spectral clustering in parallel computing environments.