Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract)
Abstract
Graph spectral clustering is a fundamental technique in data analysis, which utilizes eigenpairs of the Laplacian matrix to partition graph vertices into clusters. However, classical spectral clustering algorithms require eigendecomposition of the Laplacian matrix, which has cubic time complexity. In this work, we describe pass-efficient spectral clustering algorithms that leverage recent advances in randomized eigendecomposition and the structure of the graph vertex-edge matrix. Furthermore, we derive formulas for their efficient implementation. The resulting algorithms have a linear time complexity with respect to the number of vertices and edges and pass over the graph constant times, making them suitable for processing large graphs stored on slow memory. Experiments validate the accuracy and efficiency of the algorithms.
Cite
Text
Yan et al. "Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract)." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I21.30528Markdown
[Yan et al. "Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract)." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/yan2024aaai-pass/) doi:10.1609/AAAI.V38I21.30528BibTeX
@inproceedings{yan2024aaai-pass,
title = {{Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract)}},
author = {Yan, Boshen and Wan, Guihong and Schweitzer, Haim and Maliga, Zoltan and Khattab, Sara and Yu, Kun-Hsing and Sorger, Peter K. and Semenov, Yevgeniy R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {23690-23692},
doi = {10.1609/AAAI.V38I21.30528},
url = {https://mlanthology.org/aaai/2024/yan2024aaai-pass/}
}