A Local Search for a Graph Correlation Clustering

Abstract

In the clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. We consider a version of the clustering problem when the number of clusters does not exceed a positive integer k and the goal is to minimize the number of edges between clusters and the number of missing edges within clusters. This problem is NP-hard for any k 2. We propose a polynomial time k-approximation algorithm for this problem.

Keywords

• Graph clustering
• local search
• approximation algorithm

Introduction

d(G1; G2) = jE1 n E2j + jE2 n E1j; i.e., d(G1; G2) is the number of noncoinciding edges in G1 and G2.

Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes.

The variants of CC in which the number of clusters is bounded were also studied [ 3, 6 ].

One of the most visual formalizations of the clustering problem is the graph clustering [ 10 ], that is grouping the vertices of a graph into clusters taking into consideration the edge structure of the graph whose vertices are objects and edges represent similarities between the objects. In this setting, the clustering can be understood as cluster graph M whose connected components correspond to the clusters.

Obviously, the following setting is equivalent to CC.

GRAPH CORRELATION CLUSTERING (GCC). Given a graph G = (V; E), nd a graph M 2 M(V ) such that d(G; M ) =

min M2M(V ) d(G; M ):

We focus on the following bounded variants of GRAPH CORRELATION CLUSTERING.

GCCk. Given a graph G = (V; E) and an integer k, 2 M 2 Mk(V ) such that

GCC1;k. Given a graph G = (V; E) and an integer k, 2 M 2 M1;k(V ) such that d(G; M ) =

min M2Mk(V )

d(G; M ): d(G; M ) =

min M2M1;k(V ) d(G; M ): k k jV j, nd a graph jV j, nd a graph

In Section 2 of this paper we present a short survey of the known results involving results on computation complexity and approximability of different versions of the graph clustering problem. In section 3 we propose a new k-approximation algirithm for GCC1;k. 2

Known results

Apparently, NP-hardness of problem GCC was rst proved by Krivanek and Moravek [ 9 ] in 1986.

At the beginning and in the middle of the 2000s, several groups of authors were independently dealing with the different versions of the graph clustering problems. Chen, Jiang, and Lin [ 5 ] considered the closest phylogenetic root problems and also proved NP-hardness of GCC. Bansal, Blum, and Chawla [ 3 ], using a reduction from PARTITION INTO TRIANGLES, show that GCC is NP-hard even if all clusters are of size 3 as a maximum.

Shamir, Sharan, and Tsur [ 11 ] independently showed NP-hardness of problem GCC by a reduction from the 3-exact 3-Cover problem. They also reduced the known NPcomplete problem of 2-coloring of 3-Uniform Hypergraph to problem GCC2 and as a result they showed that problem GCCk is NP-hard for any xed k 2. In both cases Shamir, Sharan, and Tsur use rather complicated reduction. Later, Giotis and Guruswami [ 7 ] published a more simple proof of the same result using a polynomial reduction from the graph bisection problem.

At the same time, Ageev, Il'ev, Kononov, and Talevnin [ 1 ] independently proved that problems GCC2 and GCC1;2 are NP-hard on cubic (i.e., 3-regular) graphs and deduced from this that all the above-mentioned variants of the graph clustering problems (including GCC1;k) are NP-hard.

In 2004, Bansal, Blum, and Chawla [ 3 ] presented a simple polynomial time 3approximation algorithm for GCC1;2. For each v 2 V their algorithm considers the following pair of clusters. The rst cluster contains v and all neighbors of v in G = (V; E). The second cluster contains all other vertices. The algorithm outputs the pair that minimizes the number of mismatched edges. More formally this algorithm may be described as follows.

Algorithm N1;2(G).

Step 1. For each vertex v 2 V construct the cluster graph Mv 2 M1;2(V ) with V1 = fvg [ N (G) and V2 = V n V1 as the vertex sets of connected components of Mv.

Step 2. Pick the graph Mv with minimal distance from G, i.e.,

In 2006, Ageev, Il'ev, Kononov, and Talevnin [ 1 ] proved the existence of a randomized PTAS for problem GCC1;2 by reducing this problem to the graph bisection problem, and Giotis and Guruswami [ 7 ] presented a randomized PTAS for problem GCCk (for any xed k 2). In 2007, Il'ev, Navrotskaya, and Talevnin [ 8 ] considered a local search algorithm for problem GCC1;2. They showed that if the number of edges in a graph is subquadratic of the number of vertices, the local search algorithm is asymptotically exact.

In 2008, Coleman, Saunderson, and Wirth [ 6 ] pointed out that complexity of PTAS from [ 7 ] make this scheme practically useless. They presented a 2-approximation algorithm for problem GCC1;2 applying local search to the feasible solution obtained by the 3-approximation algorithm from [ 3 ].

In 2005, Charicar, Guruswami, and Wirth [ 4 ] proved that problem GCC is APXhard. They also constructed a 4-approximation algorithm for problem GCC by rounding a natural LP relaxation using the region growing technique. In 2008, Ailon, Charicar, and Newman [ 2 ] proposed a randomized 2.5-approximation algorithm for GCC.

An approximation algorithm for GCC1;k

As it was already said, Coleman, Saunderson, and Wirth [ 6 ] presented a 2-approximation algorithm for problem GCC1;2 applying local search to the feasible solution obtained by the 3-approximation algorithm N1;2 from [ 3 ]. Extending this strategy we propose a polynomial time approximation algorithm NLS1;k for problem GCC1;k when k > 2 and use algorithm from [ 6 ] for k = 2.

First we describe the algorithm formally. Denote by N (v) the set of all neighbors of a vertex v.

Algorithm NLS1;k

Input: Given graph G = (V; E) and k > 2.

Step 1. For each vertex v 2 V construct the cluster graph Mv 2 M1;k(V ) as follows: if fvg [ N (v) = V , then Mv = KjV j, else Mv = N1;k(G; fvg [ N (v); k).

Step 2. Use procedure LS1;k to modify each graph Mv.

Step 3. Pick the graph Mv with minimal distance from G, i.e.,

For any vertex u 2 V de ne the value impu(Vi; Vj) = Vi+(u) + Vj (u)

Vi (u)

Vj+(u); where Vi+(u) is the number of vertices in the set Vi adjacent to u and Vi (u) is the number of vertices in Vi not adjacent to u.

Procedure LS1;k

Input: A graph G = (V; E) and a cluster graph M 2 M1;k(V ). The sets V1; : : : ; Vk are the vertex sets of the connected components of M .

Step s (s = 1; 2; :::). Pick the vertex v 2 V such that impv(Vp; Vq) = max ( max impu(Vi; Vj)): i=1;:::k; j=1;:::k;

u2Vi j̸=i If impv(Vp; Vq) > 0, then move v from Vp to Vq and go to step s + 1, else stop.

Comments. Algorithm NLS1;k uses the function N1;k for constructing a cluster graph and the local search procedure LS1;k for improving the found cluster graph. In the end the algorithm picks a cluster graph 'nearest' to G.

Function N1;k makes a partition of the vertex set of a given graph G = (V; E). Consider the subgraph of G without the subsets of the vertex set V constructed at the previous step. Function N1;2 solves problem GCC1;2 approximately and returns a vertex set of the rst connected component of the found cluster graph. This subset is added to already constructed ones. At the next step the algorithm considers the subgraph without all found subsets involving the last constructed subset. At step 4 we have k subsets (some of which may be empty) which are a partition of the vertex set of given graph G. This partition induces a cluster graph M and the algorithm returns M .

Function N1;2 takes as an input a graph G and for each vertex v of G constructs a cluster graph whose rst connected component has vertex set consisting of v and all adjacent to v vertices. The second connected component consists of all other vertices of G. Later, cluster graph 'nearest' to G among all the constructed cluster graphs is selected. Function N1;2 returns the vertex set of the rst connected component of the cluster graph, i.e., vertex v and all its neighbors.

Procedure LS1;k takes as an input a given graph G = (V; E) and a cluster graph M 2 M1;k(V ) constructed by algorithm N1;k. On each iteration the algorithm nds a vertex whose moving to one of the rest connected components leads to steepest decreasing the distance bitween graphs G and M . If such vertex is found, it is moved to the respective corresponding connected component, else the algorithm nishes.

The followimg theorem shows that algorithm NLS1;k is k-approximation algorithm for problem GCC1;k.

Theorem 1. For any graph G = (V; E) and an integer k, 2 bound occurs: k

jV j, the following d(G; M ) kd(G; M ); where M is the cluster graph constucted by algorithm NLS1;k and M solution to GCC1;k. is an optimal

Acknowledgement

This research was supported by the RSF grant 15-11-10009.

References

1. Ageev , A. A. , Il'ev, V. P. , Kononov , A. V. , Talevnin , A. S.: Computational complexity of the graph approximation problem . Diskretnyi Analiz i Issledovanie Operatsii. Ser . 1 . 13 ( 1 ), 3 { 11 ( 2006 ) (in Russian) . English transl . in J. of Applied and Industrial Math . 1 ( 1 ), 1{ 8 ( 2007 )

2. Ailon , N. , Charikar , M. , Newman , A. : Aggregating inconsistent information: Ranking and clustering . J. ACM . 55 ( 5 ), 1 { 27 ( 2008 )

3. Bansal , N. , Blum , A. , Chawla , S. : Correlation clustering . Machine Learning . 56 , 89 { 113 ( 2004 )

4. Charikar , M. , Guruswami , V. , Wirth , A. : Clustering with qualitative information . J. Comput. Syst. Sci . 71 ( 3 ), 360 { 383 ( 2005 )

5. Chen , Z.-Z. , Jiang , T. , Lin , G. : Computing phylogenetic roots with bounded degrees and errors . SIAM J. Comput . 32 ( 4 ), 864 { 879 ( 2003 )

6. Coleman , T. , Saunderson , J. , Wirth , A. : A local-search 2-approximation for 2-correlationclustering . In: Algorithms { ESA 2008 . LNCS , vol. 5193 , pp. 308 { 319 . Springer, Heidelberg ( 2008 )

7. Giotis , I. , Guruswami , V. : Correlation clustering with a xed number of clusters . Theory of Computing . 2 ( 1 ), 249 { 266 ( 2006 )

8. Il'ev, V. P. , Navrotskaya , A. A. , Talevnin , A. S.: Polynomial time approximation scheme for the graph approximation problem . Vestnik Omskogo Universiteta . 4 , 24 { 27 ( 2007 ) (in Russian)

9. Krivanek , M. , Moravek , J.: NP-hard problems in hierarchical-tree clustering . Acta informatica . 23 , 311 { 323 ( 1986 )

10. Schaeffer , S. E. : Graph clustering . Computer Science Review . 1 ( 1 ), 27 { 64 ( 2007 )

11. Shamir , R. , Sharan , R. , Tsur , D. : Cluster graph modi cation problems . Discrete Appl . Math. 144 ( 1 {2), 173 { 182 ( 2004 )