Improved algorithms for Correlation Clustering with local objectives
share
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". Classically, we are tasked with producing a clustering that minimizes 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 ℓ_q norms (q ≥ 1) of the disagreements vector for both arbitrary and complete graphs. We present the first known algorithm for minimizing the ℓ_q norm of the disagreements vector on arbitrary graphs and also provide an improved algorithm for minimizing the ℓ_q norm (q ≥ 1) of the disagreements vector on complete graphs. Finally, we compliment these two algorithmic results with some hardness results.
READ FULL TEXT