TY - JOUR
T1 - Correlation clustering with local objectives
AU - Kalhan, Sanchit
AU - Makarychev, Konstantin
AU - Zhou, Timothy
N1 - Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2019
Y1 - 2019
N2 - Correlation Clustering is a powerful graph partitioning model that aims to cluster items based on the notion of similarity between items. An instance of the Correlation Clustering problem consists of a graph G (not necessarily complete) whose edges are labeled by a binary classifier as “similar” and “dissimilar”. An objective which has received a lot of attention in literature is that of minimizing the number of disagreements: an edge is in disagreement if it is a “similar” edge and is present across clusters or if it is a “dissimilar” edge and is present within a cluster. Define the disagreements vector to be an n dimensional vector indexed by the vertices, where the v-th index is the number of disagreements at vertex v. Recently, Puleo and Milenkovic (ICML'16) initiated the study of the Correlation Clustering framework in which the objectives were more general functions of the disagreements vector. In this paper, we study algorithms for minimizing lq norms (q = 1) of the disagreements vector for both arbitrary and complete graphs. We present the first known algorithm for minimizing the lq norm of the disagreements vector on arbitrary graphs and also provide an improved algorithm for minimizing the lq norm (q = 1) of the disagreements vector on complete graphs. We also study an alternate cluster-wise local objective introduced by Ahmadi, Khuller and Saha (IPCO'19), which aims to minimize the maximum number of disagreements associated with a cluster. We also present an improved (2 + e)-approximation algorithm for this objective. Finally, we compliment our algorithmic results for minimizing the lq norm of the disagreements vector with some hardness results.
AB - Correlation Clustering is a powerful graph partitioning model that aims to cluster items based on the notion of similarity between items. An instance of the Correlation Clustering problem consists of a graph G (not necessarily complete) whose edges are labeled by a binary classifier as “similar” and “dissimilar”. An objective which has received a lot of attention in literature is that of minimizing the number of disagreements: an edge is in disagreement if it is a “similar” edge and is present across clusters or if it is a “dissimilar” edge and is present within a cluster. Define the disagreements vector to be an n dimensional vector indexed by the vertices, where the v-th index is the number of disagreements at vertex v. Recently, Puleo and Milenkovic (ICML'16) initiated the study of the Correlation Clustering framework in which the objectives were more general functions of the disagreements vector. In this paper, we study algorithms for minimizing lq norms (q = 1) of the disagreements vector for both arbitrary and complete graphs. We present the first known algorithm for minimizing the lq norm of the disagreements vector on arbitrary graphs and also provide an improved algorithm for minimizing the lq norm (q = 1) of the disagreements vector on complete graphs. We also study an alternate cluster-wise local objective introduced by Ahmadi, Khuller and Saha (IPCO'19), which aims to minimize the maximum number of disagreements associated with a cluster. We also present an improved (2 + e)-approximation algorithm for this objective. Finally, we compliment our algorithmic results for minimizing the lq norm of the disagreements vector with some hardness results.
UR - http://www.scopus.com/inward/record.url?scp=85090174802&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090174802&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85090174802
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
SN - 1049-5258
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -