Research map / Learning theory and algorithms / Clustering

Faster Dynamic Graph Clustering with Hierarchical Graph Contraction

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Spectral clustering algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a hierarchical data structure that dynamically maintains the cluster structure of evolving graphs with O(d) amortised update time.

Problem

Clustering dynamic evolving graphs where edges and vertices are added over time and the underlying cluster structure gradually changes.

Approach

A hierarchical graph contraction data structure that maintains the cluster structure of the evolving graph with amortised O(d) update cost per step, avoiding recomputation from scratch.

Key results

• Cluster structure of G_T can be maintained with O(d) amortised update time per edge update, per the abstract (d is abstract's graph parameter, truncated in the provided text).

Closest papers by meaning

• Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.93)
• Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.91)
• Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.88)
• Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.87)
• Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.86)
• Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.86)