# Local Correlation Clustering with Asymmetric Classification Errors

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 20 references that are in the map.
- First posted on arXiv 11 Aug 2021.

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

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Multi-Person Tracking by Multicut and Deep Matching](https://mlsanity.com/paper/1608.05404/) (2016)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Min-Max Correlation Clustering via MultiCut](https://mlsanity.com/paper/1907.00117/) (2019)

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

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Robust Correlation Clustering with Asymmetric Noise](https://mlsanity.com/paper/2110.08385/) (2021)
- [Four Algorithms for Correlation Clustering: A Survey](https://mlsanity.com/paper/2208.12636/) (2022)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)

## Abstract (arXiv)

In the Correlation Clustering problem, we are given a complete weighted graph G with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier. For a clustering C of graph G, a similar edge is in disagreement with C, if its endpoints belong to distinct clusters; and a dissimilar edge is in disagreement with C if its endpoints belong to the same cluster. The disagreements vector, dis, is a vector indexed by the vertices of G such that the v-th coordinate disv equals the weight of all disagreeing edges incident on v. The goal is to produce a clustering that minimizes the ℓp norm of the disagreements vector for p≥ 1. We study the ℓp objective in Correlation Clustering under the following assumption: Every similar edge has weight in the range of [αw,w] and every dissimilar edge has weight at least αw (where α ≤ 1 and w>0 is a scaling parameter). We give an Oleft((frac1α)^frac12-frac12p· logfrac1αright) approximation algorithm for this problem. Furthermore, we show an almost matching convex programming integrality gap.