Dynamic Spectral Clustering with Provable Approximation Guarantee

Steinar Laenen, He Sun
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:25844-25870, 2024.

Abstract

This paper studies clustering algorithms for dynamically evolving graphs {Gt}, 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 GT of nT 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(nT). Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-laenen24a, title = {Dynamic Spectral Clustering with Provable Approximation Guarantee}, author = {Laenen, Steinar and Sun, He}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {25844--25870}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/laenen24a/laenen24a.pdf}, url = {https://proceedings.mlr.press/v235/laenen24a.html}, 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.} }
Endnote
%0 Conference Paper %T Dynamic Spectral Clustering with Provable Approximation Guarantee %A Steinar Laenen %A He Sun %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-laenen24a %I PMLR %P 25844--25870 %U https://proceedings.mlr.press/v235/laenen24a.html %V 235 %X 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.
APA
Laenen, S. & Sun, H.. (2024). Dynamic Spectral Clustering with Provable Approximation Guarantee. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:25844-25870 Available from https://proceedings.mlr.press/v235/laenen24a.html.

Related Material