Local Correlation Clustering with Asymmetric Classification Errors

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.