Dynamic Spectral Clustering with Provable Approximation Guarantee
Abstract
This paper studies clustering algorithms for dynamically evolving graphs $\{G_t\}$, in which new edges (and potential new vertices) are added into a graph, and the underlying cluster structure of the graph can gradually change. The paper proves that, under some mild condition on the cluster-structure, the clusters of the final graph $G_T$ of $n_T$ vertices at time $T$ can be well approximated by a dynamic variant of the spectral clustering algorithm. The algorithm runs in amortised update time $O(1)$ and query time $o(n_T)$. Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm.
Cite
Text
Laenen and Sun. "Dynamic Spectral Clustering with Provable Approximation Guarantee." International Conference on Machine Learning, 2024.Markdown
[Laenen and Sun. "Dynamic Spectral Clustering with Provable Approximation Guarantee." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/laenen2024icml-dynamic/)BibTeX
@inproceedings{laenen2024icml-dynamic,
title = {{Dynamic Spectral Clustering with Provable Approximation Guarantee}},
author = {Laenen, Steinar and Sun, He},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {25844-25870},
volume = {235},
url = {https://mlanthology.org/icml/2024/laenen2024icml-dynamic/}
}