Local Correlation Clustering with Asymmetric Classification Errors

Abstract

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 dis_v 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 O((1)^12-12p 1) approximation algorithm for this problem. Furthermore, we show an almost matching convex programming integrality gap.

Tasks

Reproductions