ICML Poster Correlation Clustering with Asymmetric Classification Errors

Poster

Correlation Clustering with Asymmetric Classification Errors

Jafar Jafarov · Sanchit Kalhan · Konstantin Makarychev · Yury Makarychev

Keywords: [ Clustering ] [ Combinatorial Optimization ] [ Unsupervised and Semi-supervised Learning ]

[ Abstract ]

Abstract: In the Correlation Clustering problem, we are given a weighted graph

G

$G$ with its edges labelled 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

$e$ has weight

w_{e} \in [α w, w]

$w_e \in [ \alpha w, w ]$ and every "dissimilar" edge

e

$e$ has weight

w_{e} \geq α w

$w_e \geq \alpha w$ (where

α \leq 1

$\alpha \leq 1$ and

w > 0

$w > 0$ is a scaling parameter). We give a

(3 + 2 \log_{e} (1 / α))

$(3 + 2 \log_e (1/\alpha))$ 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 / α)

$\Omega(\log 1/\alpha)$ .

Chat is not available.