Faster Dynamic Graph Clustering with Hierarchical Graph Contraction

Abstract

We study clustering in dynamic graphs, where edges (and possibly vertices) arrive over time and the underlying cluster structure evolves gradually. We design a hierarchical data structure that maintains this cluster structure with $O(d)$ amortised update time and $\widetilde{O}(n_T^{1/d})$ amortised query time, for any large constant $d$, where $n_T$ is the number of vertices at time $T$. This improves on the previous state of the art (Laenen and Sun, ICML 2024), which has $O(1)$ update time but $O(n_T/\log n_T)$ amortised query time. Experiments on synthetic and real-world datasets confirm the improvement.

Publication
In Neural Information Processing Systems 2026
Steinar Laenen
Steinar Laenen
Senior Software Engineer

I work on AI for visual search and agentic systems at Google. My research background is in spectral graph theory and graph clustering.