Research map / Learning theory and algorithms / Clustering
Learning-Augmented Streaming Algorithms for Correlation Clustering
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 learning-augmented single-pass streaming algorithms for Correlation Clustering on complete and general graphs that use pairwise-distance predictions, achieving better-than-3 approximation on complete graphs and O(β log|E-|) on general graphs in Õ(n) space.
Problem
Correlation Clustering in graph streams (dynamic and insertion-only) with limited space, where the goal is minimizing disagreements on complete and general graphs.
Approach
Uses an oracle predictor of pairwise distances (satisfying a β-level quality condition tied to an LP-feasible solution) to combine truncated Pivot with LP-style probabilistic pivot clustering on an ℓ0-sampled subgraph, and to drive ball-growing on a spectral sparsifier for general graphs.
Key results
- For complete graphs, the learning-augmented dynamic-stream algorithm achieves (min{2.06β,3}+ε)-approximation in Õ(ε^-2 n) total space, improving the best (3+ε) semi-streaming bound.
- For general graphs, the algorithm achieves O(β log|E-|)-approximation in Õ(ε^-2 n) total space, avoiding storing all negative edges.
- On Facebook subgraph FB 0 with β≈1.2, the cost is 15% lower than CLMNPT21 and 22% lower than CKLPU24; with binary classifier predictions on SBM n=2400, cost is reduced by 72% vs CKLPU24.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a binary classifier as the pairwise-distance predictor instead of no predictions | Complete-graph streaming correlation clustering · SBM (n=1200) | clustering cost: 105.3 -> 35.9 | Helped |
| Use a binary classifier as the pairwise-distance predictor instead of no predictions | Complete-graph streaming correlation clustering · SBM (n=2400) | clustering cost: 524.8 -> 145.6 | Helped |
| Use a binary classifier as the pairwise-distance predictor instead of no predictions | Complete-graph streaming correlation clustering · SBM (n=3600) | clustering cost: 1114.3 -> 324.9 | Helped |
| Use a binary classifier as the pairwise-distance predictor instead of no predictions | Complete-graph streaming correlation clustering · DBLP (sampled subgraph, 10000 vertices) | clustering cost: 537.5 -> 247.1 | Helped |
| Use a good-quality pairwise-distance predictor | Complete-graph streaming correlation clustering · Facebook subgraph FB 0 | average clustering cost: 15% lower than CLMNPT21; 22% lower than CKLPU24 | Helped |
| Use spectral-embedding pairwise-distance predictions | Complete-graph streaming correlation clustering · EmailCore | clustering cost: up to 14% | Helped |
| Use the learning-augmented algorithm rather than CKLPU24 | Complete-graph streaming correlation clustering · Synthetic SBM (p=0.7) | clustering cost: up to 26% | Helped |
| Use the learning-augmented algorithm rather than CKLPU24 | Complete-graph streaming correlation clustering · Synthetic SBM (p=0.95, n=2400) | clustering cost: 72% | Helped |
| Use poor-quality predictions | Complete-graph streaming correlation clustering · Real-world datasets | clustering cost | No clear effect |
| Increase graph size | Complete-graph streaming correlation clustering · Synthetic SBM (p=0.95) | cost-to-optimum ratio | No clear effect |
| Use the learning-augmented algorithm rather than CKLPU24 | Complete-graph streaming correlation clustering · Synthetic SBM datasets | clustering cost | Helped |
Surprising findings
- The CLMNPT21 multi-pass algorithm yields near-optimal solutions on SBM graphs, outperforming the learning-augmented streaming method there.
Limitations
- Guarantees depend on predictor quality parameter β; the approximation degrades to the non-learning bound only as predictions worsen.
- General-graph guarantee uses an adapted β-level predictor requiring weighted sparsifier-based conditions.
- Experiments run only on the complete-graph setting; the general-graph algorithm is not empirically evaluated.
Experimental setup
Datasets: SBM synthetic graphs EmailCore Facebook LastFM DBLP
Benchmarks: SBM synthetic graphs EmailCore Facebook LastFM DBLP
Metrics: correlation clustering cost ratio to optimal cost
Baselines: CKLPU24 CLMNPT21 Chakrabarty-Makarychev (3+eps) streaming
Builds on: Cambus et al. truncated pivot streaming Ahn et al. dynamic streaming correlation clustering Chawla et al. LP rounding Charikar et al. ball-growing
Closest papers by meaning
- Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost (NeurIPS 2023 · similarity 0.94)
- Estimating Correlation Clustering Cost in Node-Arrival Stream (ICML 2026 · similarity 0.92)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.90)
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.87)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.87)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.86)
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.