# Correlation Clustering with Random Partial Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 17 Aug 2026.

## Builds on (most cited first, 9 of 9)

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Understanding the Cluster LP for Correlation Clustering](https://mlsanity.com/paper/2404.17509/) (2024)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (2023)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [Min-Max Correlation Clustering via Neighborhood Similarity](https://mlsanity.com/paper/2502.12519/) (2025)

## Abstract (arXiv)

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to O(log n) and O(√n). This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph G, where each edge is independently deleted with probability q. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on q) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.