# Correlation Clustering with Asymmetric Classification Errors

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

## Key facts

- Cited by 6 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)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [BUbiNG: Massive Crawling for the Masses](https://mlsanity.com/paper/1601.06919/) (2016)
- [Breaking the Small Cluster Barrier of Graph Clustering](https://mlsanity.com/paper/1302.4549/) (2013)

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

- [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)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (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 weighted graph G with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge e has weight we∈[α w, w] and every "dissimilar" edge e has weight we≥ α w (where α≤ 1 and w>0 is a scaling parameter). We give a (3 + 2 loge (1/α)) approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of Omega(log 1/α).