Faster Dynamic Graph Clustering with Hierarchical Graph Contraction

We study clustering algorithm for dynamic evolving graphs $\{G_t\}$, in which new edges (and potentially new vertices) are added into a graph, and the underlying cluster structure of the graph gradually changes over time. By designing a hierarchical data structure for dynamically maintaining the cluster structure of $\{G_t\}$, we prove that the cluster structure of $G_T$ can be maintained with $O(d)$ amortised update time and $\tilde{O}\left(n_T^{1/d}\right)$ amortised query time, for an arbitrary large constant $d$. This significantly improves the previous state-of-the-art (Laenen and Sun, ICML '24), which requires $O(1)$ update time and $O(n_T/\log n_T)$ amortised query time. We further demonstrate this improvement with experiments on both synthetic and real-world datasets.