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.

In International Conference on Machine Learning 2024
Steinar Laenen
Steinar Laenen
PhD Candidate Computer Science

My research interests are spectral graph theory, graph clustering, and unsupervised learning