# Learning-Augmented Streaming Algorithms for Correlation Clustering

arXiv: https://arxiv.org/abs/2510.10705 · HTML: https://mlsanity.com/paper/2510.10705/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 94 references that are in the map.
- First posted on arXiv 12 Oct 2025.

## Builds on (most cited first, 30 of 58)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Improved Price of Anarchy via Predictions](https://mlsanity.com/paper/2205.04252/) (2022)
- [On Dynamic Graph Algorithms with Predictions](https://mlsanity.com/paper/2307.09961/) (2023)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first learning-augmented streaming algorithms for the problem on both complete and general graphs, improving the best-known space-approximation tradeoffs. Based on the works of Cambus et al. (SODA'24) and Ahn et al. (ICML'15), our algorithms use the predictions of pairwise distances between vertices provided by a predictor. For complete graphs, our algorithm achieves a better-than-3 approximation under good prediction quality, while using tildeO(n) total space. For general graphs, our algorithm achieves an O(log |E^-|) approximation under good prediction quality using tildeO(n) total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.