Research map / Learning theory and algorithms / Clustering
Sparse-pivot: Dynamic correlation clustering for node insertions
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.
Gives a dynamic node-insertion correlation clustering algorithm (Sparse-Pivot) with polylogarithmic amortized database-query update time and a 20+ε approximation, improving on the constant but huge approximation of Cohen-Addad et al. 2024.
Problem
Correlation clustering on a complete-information similarity graph where nodes arrive one at a time and the algorithm must update the clustering using database queries (degree, random neighbor, adjacency) with small update time and good approximation.
Approach
Adapts a 5-approximate semi-streaming Pivot variant to node insertions with random ranks in [0,1]; non-pivot nodes find pivots by sampling O(log n) neighbors, and each pivot's cluster is pruned via a dense-subset selection by degree threshold, estimated with sampling, to control non-edges.
Key results
- Theoretical guarantee: expected cost at most 4(1+O(ε)) times the Reference Clustering cost, with the overall approximation stated as 20+ε.
- On a density table, Sparse-Pivot objective is 0.6, 0.49, 0.41, 0.32, 0.29 versus dynamic-agreement 0.69, 0.59, 0.5, 0.39, 0.35 (normalized by singletons) across five density levels.
- Amortized update time is poly(log T, 1/ε) with high probability, per the paper's theorem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Sparse-Pivot instead of Dynamic Agreement | Dynamic correlation clustering · Drift dataset, densities 235.36, 114.87, 69.74, 52.17, and 42.25 | clustering objective: 0.69 -> 0.6; 0.59 -> 0.49; 0.5 -> 0.41; 0.39 -> 0.32; 0.35 -> 0.29 | Helped |
| Use Sparse-Pivot instead of Reference Clustering | Dynamic correlation clustering · Drift dataset, density 235.36 | clustering objective: 0.59 -> 0.6 | Hurt |
| Use Sparse-Pivot instead of Reference Clustering | Dynamic correlation clustering · Drift dataset, densities 114.87, 69.74, 52.17, and 42.25 | clustering objective: 0.64 -> 0.49; 0.5 -> 0.41; 0.42 -> 0.32; 0.35 -> 0.29 | Helped |
Surprising findings
- Sparse-Pivot's objective beats the Reference Clustering it approximates in some density settings (e.g., 0.6 vs 0.59 is not, but 0.49 vs 0.64 and 0.41 vs 0.5 are), attributed to the cluster-pruning step.
Limitations
- The approximation factor is 20+ε, with the factor-20 loss coming from the break-cluster subroutine; the heuristic used in experiments differs from the analyzed version.
- Only handles node insertions with soft deletions; full random deletions require periodic recomputation.
- Assumes a non-adaptive arrival order and a fixed graph in advance.
Experimental setup
Datasets: musae-facebook email-Enron ca-AstroPh cit-HepTh drift dataset (UCI ML Repository)
Benchmarks: SNAP graphs (musae-facebook, email-Enron, ca-AstroPh, cit-HepTh) drift dataset graphs at multiple densities
Metrics: correlation clustering objective normalized by singletons co running time
Baselines: Singletons Dynamic agreement Reference Clustering
Builds on: Pivot algorithm Cohen-Addad et al. dynamic correlation clustering (ICML 2024) 5-approximation Pivot for semi-streaming
Closest papers by meaning
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.89)
- Correlation Clustering Beyond the Pivot Algorithm (ICML 2025 · similarity 0.89)
- Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.88)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.86)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.