Correlation Clustering with Asymmetric Classification Errors
This addresses a specific scenario in clustering with noisy data, offering theoretical guarantees for asymmetric errors, but it is incremental as it builds on existing correlation clustering frameworks.
The paper tackles the Correlation Clustering problem under an assumption of asymmetric classification errors in edge weights, providing a (3 + 2 log_e(1/α)) approximation algorithm and showing a matching Ω(log 1/α) integrality gap.
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 $\mathbf{w}_e\in[α\mathbf{w}, \mathbf{w}]$ and every "dissimilar" edge $e$ has weight $\mathbf{w}_e\geq α\mathbf{w}$ (where $α\leq 1$ and $\mathbf{w}>0$ is a scaling parameter). We give a $(3 + 2 \log_e (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 $Ω(\log 1/α)$.