Research map / Learning theory and algorithms / Clustering

Dynamic Correlation Clustering in Sublinear Update Time

ICML 2024 · Learning theory and algorithms › Clustering · approach: Correlation clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

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

Let me correct the previous call.

Problem

Maintaining a constant-factor approximate correlation clustering under dynamic node streams (adversarial insertions, random deletions) with sublinear update time in the database query model.

Approach

Dynamizes the Agreement algorithm by sampling neighborhoods with logarithmic-size samples, maintaining a random anchor set of heavy nodes, and propagating arrival/deletion events via a Notify procedure that sends notifications to O(polylog n) nodes, so that cluster structure is tracked through anchor connections without reading full neighborhoods.

Key results

• On the Drift dataset, Dynamic-Agreement's running time stays roughly constant (12.5 to 15.8 s) across densities from average degree 42 to 253, while Pivot-Dynamic's grows from 0.07 to 0.28 s.
• Dynamic-Agreement achieves relative objective 0.320 to 0.696 vs singletons on Drift, beating Pivot-Dynamic at the sparsest and densest... (mixed: DA better at lower densities, PD better at densest)
• Theory: O(1)-approximation with probability at least 1-5/n and O(polylog n) amortized update time under random deletions.

Measured effects reported in the paper

Surprising findings

• Pivot-Dynamic has lower relative objective than Dynamic-Agreement on the densest Drift graphs (0.610 vs 0.696), contrary to the claim that DA consistently outperforms it.
• Singletons is competitive on sparse graphs, so the clustering objective is often not far from trivial.

Limitations

• Analysis assumes random node deletions; adversarial deletions can blow up the update time.
• Practical implementation uses different constants (sample size 2, anchor probability 20/d_u) than the theory.
• Dynamic-Agreement is slower than Pivot-Dynamic on sparse graphs.

Experimental setup

Datasets: musae-facebook email-Enron ca-AstroPh cit-HepTh Drift (UCI)

Benchmarks: musae-facebook email-Enron ca-AstroPh cit-HepTh Drift

Metrics: correlation clustering objective relative to singletons running time

Baselines: Singletons Pivot-Dynamic

Builds on: Agreement algorithm (Assadi and Wang) Pivot-Dynamic (Cohen-Addad et al.) Pivot algorithm

Closest papers by meaning

• Faster Dynamic Graph Clustering with Hierarchical Graph Contraction (NeurIPS 2026 · similarity 0.91)
• Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.90)
• Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.90)
• Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.89)
• Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.88)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)