Dynamic Spectral Clustering with Provable Approximation Guarantee
<|reference_start|>Dynamic Spectral Clustering with Provable Approximation Guarantee: 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.<|reference_end|>
@article{laenen2024dynamic,
    title={Dynamic Spectral Clustering with Provable Approximation Guarantee},
    author={Steinar Laenen, He Sun},
    journal={arXiv preprint arXiv:2406.03152},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03152},
    primaryClass={cs.DS cs.LG}
}