Correlation Clustering.
We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, v) is labeled either + or  depending on whether u and v have been deemed to be similar or different. The goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we want a clustering that maximizes the number of + edges within clusters, plus the number of  edges between clusters (equivalently, minimizes the number of disagreements: the number of  edges inside clusters plus the number of + edges between clusters). This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible&semi; it can also be viewed as a kind of agnostic learning problem.An interesting feature of this clustering formulation is that one does not need to specify the number of clusters k as a separate parameter, as in measures such as k-median or min-sum or min-max clustering. Instead, in our formulation, the optimal number of clusters could be any value between 1 and n, depending on the edge labels. We look at approximation algorithms for both minimizing disagreements and for maximizing agreements. For minimizing disagreements, we give a constant factor approximation. For maximizing agreements we give a PTAS, building on ideas of Goldreich, Goldwasser, and Ron (1998) and de la Veg (1996). We also show how to extend some of these results to graphs with edge labels in [1, +1], and give some results for the case of random noise.
Introduction
Suppose that you are given a set of n documents to cluster
into topics. Unfortunately, you have no idea of what
a "topic" is. However, you have at your disposal a classifier
f(A; B) that given two documents A and B, outputs
Department of Computer Science, Carnegie Mellon University.
fnikhil,avrim,shuchig@cs.cmu.edu. This research was supported
in part by NSF grants CCR-0085982, CCR-0122581, CCR-
0105488, and an IBM Graduate Fellowship.
whether or not it believes A and B are similar to each other.
For example, perhaps f was learned from some past training
data. In this case, a natural approach to clustering is to
apply f to every pair of documents in your set, and then to
find the clustering that agrees as much as possible with the
results.
Specifically, we consider the following problem. Given
a fully-connected graph G with edges labeled "+" (similar)
find a partition of the vertices into clusters
that agrees as much as possible with the edge labels.
In particular, we can look at this in terms of maximizing
agreements (the number of + edges inside clusters plus the
number of edges between clusters) or in terms of minimizing
disagreements (the number of edges inside clusters
plus the number of + edges between clusters). These
two are equivalent at optimality but, as usual, differ from
the point of view of approximation. In this paper we give
a constant factor approximation to the problem of minimizing
disagreements, and a PTAS for maximizing agreements.
We also extend some of our results to the case of real-valued
edge weights. This problem formulation is motivated in part
by some clustering problems at Whizbang Labs in which
learning algorithms have been trained to help with various
clustering tasks [8, 9, 10]. 1
What is interesting about the clustering problem defined
here is that unlike most clustering formulations, we do not
need to specify the number of clusters k as a separate pa-
rameter. For example, in k-median [7, 15] or min-sum clustering
[20] or min-max clustering [14], one can always get
a perfect score by putting each node into its own cluster -
the question is how well one can do with only k clusters. In
our clustering formulation, there is just a single objective,
An example of one such problem is clustering entity names. In this
problem, items are entries taken from multiple databases (e.g., think of
names/affiliations of researchers), and the goal is to do a "robust uniq"
collecting together the entries that correspond to the same entity (per-
son). E.g., in the case of researchers, the same person might appear
multiple times with different affiliations, or might appear once with a
middle name and once without, etc. In practice, the classifier f typically
would output a probability, in which case the natural edge label is
log(Pr(same)/Pr(different)). This is 0 if the classifier is unsure, positive if
the classifier believes the items are more likely in the same cluster, and
negative if the classifier believes they are more likely in different clusters.
The case of f+; g labels corresponds to the setting in which the classifier
has equal confidence about each of its decisions.
and the optimal clustering might have few or many clusters:
it all depends on the edge labels.
To get a feel for this problem, notice that if there exists
a perfect clustering, i.e., one that gets all the edges correct,
then the optimal clustering is easy to find: just delete
edges and output the connected components of the graph
remaining. (This is called the "naive algorithm" in [10].)
Thus, the interesting case is when no clustering is perfect.
Also, notice that for any graph G, it is trivial to produce a
clustering that agrees with at least half of the edge labels:
if there are more + edges than edges, then simply put all
vertices into one big cluster; otherwise, put each vertex into
its own cluster. This observation means that for maximizing
agreements, getting a 2-approximation is easy (note: we
will show a PTAS). In general, finding the optimal clustering
is NP-hard, which can be seen via a tedious reduction
from X3C (details can be found in [5]).
Another simple fact to notice is that if the graph contains
a triangle in which two edges are labeled + and one is labeled
, then no clustering can be perfect. More generally,
the number of edge-disjoint triangles of this form gives a
lower bound on the number of disagreements of the optimal
clustering. This fact is used in our constant-factor approximation
algorithm.
For maximizing agreements, our PTAS is quite similar
to the PTAS developed by [12] for MAX-CUT on dense
graphs, and related to PTASs of [4, 3]. Notice that since
there must exist a clustering with at least n(n 1)=4
agreements, this means it suffices to approximate agreements
to within an additive factor of n 2 . This problem
is also closely related to work on testing graph properties
of [13, 19, 1]. In fact, we show how we can use the General
Partition Property Tester of [13] as a subroutine to get a
PTAS with running time O(ne O(( 1
Unfortunately, this
is doubly exponential in 1
, so we also present an alternative
direct algorithm (based more closely on the approach
of [12]) that takes only O(n 2 e O( 1
Relation to agnostic learning: One way to view this
clustering problem is that edges are "examples" (labeled as
positive or negative) and we are trying to represent the target
function f using a hypothesis class of vertex clusters. This
hypothesis class has limited representational power: if we
want to say (u; v) and (v; w) are positive in this language,
then we have to say (u; w) is positive too. So, we might
not be able to represent f perfectly. This sort of problem -
trying to find the (nearly) best representation of some arbitrary
target f in a given limited hypothesis language - is
sometimes called agnostic learning [17, 6]. The observation
that one can trivially agree with at least half the edge labels
is equivalent to the standard machine learning fact that one
can always achieve error at most 1=2 using either the all
positive or all negative hypothesis.
Our PTAS for approximating the number of agreements
means that if the optimal clustering has error rate , then we
can find one of error rate at most  + . Our running time is
exponential in 1=, but this means that we can achieve any
constant error gap in polynomial time. What makes this interesting
from the point of view of agnostic learning is that
there are very few nontrivial problems where agnostic learning
can be done in polynomial time. Even for simple classes
such as conjunctions and disjunctions, no polynomial-time
algorithms are known that give even an error gap of 1=2 .
Notation and Definitions
E) be a complete graph on n vertices, and
let e(u; v) denote the label (+ or ) of the edge (u; v). Let
denote the positive and negative neighbors of
respectively.
We let OPT denote the optimal clustering on this graph.
In general, for a clustering C, let C(v) be the set of vertices
in the same cluster as v. We will use A to denote the clustering
produced by our algorithms.
In a clustering C, we call an edge (u; v) a mistake if either
we call the mistake a positive
mistake, otherwise it is called a negative mistake. We
denote the total number of mistakes made by a clustering
use mOPT to denote the number of mistakes
made by OPT.
For positive real numbers x, y and z, we use x 2 yz to
Finally, let X for X  V denote
the complement (V n X).
3 A Constant Factor Approximation for Minimizing
Disagreements
We now describe our main algorithm: a constant-factor
approximation for minimizing the number of disagreements

The high-level idea of the algorithm is as follows. First,
we show (Lemma 1) that if we can cluster a portion of
the graph using clusters that each look sufficiently "clean"
(Definition 1), then we can charge off the mistakes made
within that portion to "erroneous triangles": triangles with
two edges and one edge. Furthermore, we can do
this in such a way that the triangles we charge are nearly
edge-disjoint, allowing us to bound the number of these
mistakes by a constant factor of OPT. Second, we show
(Lemma 2) that there must exist a nearly optimal clustering
OPT 0 in which all non-singleton clusters are "clean".
Finally, we show (Theorem 3 and Lemma 7) that we can algorithmically
produce a clustering of the entire graph containing
only clean clusters and singleton clusters, such that
mistakes that have an endpoint in singleton clusters are
bounded by OPT 0 , and mistakes with both endpoints in
clean clusters are bounded using Lemma 1.
We begin with a definition of a "clean" cluster and a
"good" vertex.
vertex v is called -good with respect to C,
where C  V , if it satisfies the following:
If a vertex v is not -good with respect to (wrt) C, then it is
called -bad wrt C. Finally, a set C is -clean if all v 2 C
are -good wrt C.
We now present two key lemmas.
Given a clustering of V in which all clusters are
-clean for some -  1=4, then the number of mistakes
made by this clustering is at most 8mOPT .
Proof: Let the clustering on V be
bound the number of mistakes made by this clustering by 8
times the number of edge-disjoint "erroneous triangles" in
the graph, where an erroneous triangle is a triangle having
two edges and one edge. We then use the fact that OPT
must make at least one mistake for each such triangle.
First consider the negative mistakes. Pick a negative
edge that has not been considered so far.
We will pick a w 2 C i such that both (u; w) and (v; w)
are positive and associate (u; v) with the erroneous triangle
(u; v; w). We now show that for all (u; v), such a w can
always be picked such that no other negative edges
or (u; v 0 ) (i.e. the ones sharing u or v) also pick w.
Since C i is -clean, neither u nor v has more than -jC
negative neighbors inside C i . Thus (u; v) has at least
vertices w such that both (u; w) and (v; w)
are positive. Moreover, at most 2-jC i j 2 of these could
have already been chosen by other negative edges
v) has at least (1 4-)s choices of
w that satisfy the required condition. Since -  1=4, (u; v)
will always be able to pick such a w.
Note that any positive edge (v; w) can be chosen at most
times by the above scheme, once for negative mistakes
on v and possibly again for negative mistakes on w. Thus
we can account for at least a fourth (because only positive
edges are double counted) of the negative mistakes using
edge disjoint erroneous triangles.
Now, we consider the positive mistakes. Just as above,
we will associate mistakes with erroneous triangles. We
will start afresh, without taking into account the labelings
from the previous part.
Consider a positive edge between
j. Pick a w 2 C i such that (u; w) is positive and
(v; w) is negative. There will be at least jC
such vertices as before and at most -(jC i j+jC j j) of them will
be already taken. Moreover only the positive edge (u; w)
can be chosen twice (once as (u; w) and once as (w; u)).
Repeating the above argument, we again see that we account
for at least half (hence at least a quarter) of the positive
mistakes using edge disjoint triangles.
Now depending on whether there are more negative mistakes
or more positive mistakes, we can choose the triangles
appropriately, and hence account for at least 1/8 of the total
mistakes in the clustering.
There exists a clustering OPT 0 in which each
non-singleton cluster is -clean, and mOPT 0  ( 9
1)mOPT .
Proof: Consider the following procedure applied to the
clustering of OPT and call the resulting clustering OPT 0 .
Procedure -Clean-Up: Let C OPT
k be
the clusters in OPT.
1. Let
2. For
(a) If the number of --bad vertices in C OPT
i is more
than -jC OPT
call this "dissolving" the cluster.
(b) Else, let B i denote the --bad vertices in C OPT
3. Output the clustering OPT
We will prove that mOPT and mOPT 0 are closely related.
We first show that each C 0
clean. Clearly, this holds
i is non-empty, we know that jC OPT
-=3). For each point
Similarly, counting positive neighbors of v in C OPT
outside C OPT
Thus each C 0
i is -clean.
We now account for the number of mistakes. If we
dissolve some C OPT
clearly the mistakes associated
with vertices in original C OPT
i is at least (-=3) 2 jC OPT
The mistakes added due to dissolving clusters is at most
If C OPT
i was not dissolved, then, the original mistakes in
i were at least -=3jC OPT
The mistakes added
by the procedure is at most jB i jjC OPT
j. Noting that 6=- <
the lemma follows.
For the clustering OPT 0 given by the above lemma, we
use C 0
i to denote the non-singleton clusters and S to denote
the set of singleton clusters. We will now describe Algorithm
Cautious that tries to find clusters similar to OPT 0 .
Throughout the rest of this section, we assume that
1. Pick an arbitrary vertex v and do the following:
(a) Let
(b) (Vertex Removal Step): While 9x 2 A(v) such
that x is 3-bad wrt A(v), fxg.
(c) (Vertex Addition Step): Let
7-good wrt A(v)g. Let
2. Delete A(v) from the set of vertices and repeat until no
vertices are left or until all the produced sets A(v) are
empty. In the latter case, output the remaining vertices
as singleton nodes.
Call the clusters output by algorithm Cautious
Z be the set of singleton vertices
created in the final step. Our main goal will be to show that
the clusters output by our algorithm satisfy the property
stated below.
Theorem 3 8j, 9i such that C 0
Moreover, each A i
is 11-clean.
In order to prove this theorem, we need the following
two lemmas.
i is a -clean cluster in OPT 0 ,
any vertex w 2 C 0
Proof: As v; w
j.
Also, (1 -)jC 0
j. Thus, we
get the following two conditions.
Thus, w is 3-good wrt N (v).
2 Observe that in the vertex addition step, all vertices are added in one
step as opposed to in the vertex removal step
Lemma 5 Given an arbitrary set X , if
cannot both be 3-good wrt X .
Proof: Firstly if v is 3-good wrt some arbitrary set X , then
Suppose that v 1 and v 2 are both 3-good with respect to
which implies that jN
Also, since v 1 lies in a -clean cluster C 0
i in OPT 0 ,
;. It follows that jN
Now notice that jC 0
j.
j. The same holds for C 0
However, since - < 1=9,
and we have a contradiction. Thus the result follows.
This gives us the following important corollary.
Corollary 6 After the remove phase of the algorithm, no
two vertices from distinct C 0
j can be present in A(v).
Now we go on to prove Theorem 3.
Proof of Theorem 3: We will first show that each A i is either
a subset of S or contains exactly one of the clusters C 0
. The
first part of the theorem will follow.
For a cluster A i , let A 0
i be the set produced after the vertex
removal phase such the cluster A i is obtained by applying
the vertex addition phase to A 0
i . We have two cases.
First, we consider the case when A 0
Now during the
vertex addition step, no vertex
can enter A 0
i for any
j. This follows because, since C 0
j is -clean and disjoint
from A 0
for u to enter we need that -jC 0
and (1 -)jC 0
these two conditions cannot
be satisfied simultaneously. Thus A i  S.
In the second case, some u 2 C 0
j is present in A 0
ever, in this case observe that from Corollary 6, no vertices
from C 0
k can be present in A 0
i for any k 6= j. Also, by the
same reasoning as for the case A 0
no vertex from C 0
will enter A 0
i in the vertex addition phase. Now it only remains
to show that C 0
Since u was not removed from A 0
it follows that many
vertices from C 0
are present in A 0
i . In particular, jN
j. Now
implies that jC 0
j. Also, jA 0
j. So we have jA 0
j.
We now show that all remaining vertices from C 0
enter A i during the vertex addition phase. For
j such
that
together imply that jA 0
j. The same holds for jA 0
i and will be added in the Vertex Addition step. Thus
we have shown that A(v) can contain C 0
j for at most one j
and in fact will contain this set entirely.
Next, we will show that for every j, 9i s.t. C 0
Let v chosen in Step 1 of the algorithm be such that v 2
. We show that during the vertex removal step, no vertex
j is removed. The proof follows by an easy
induction on the number of vertices removed so far (r) in
the vertex removal step. The base case
Lemma 4 since every vertex in C 0
j is 3-good with respect to
(v). For the induction step observe that since no vertex
j is removed thus far, every vertex in C 0
is still 3-good wrt to the intermediate A(v) (by mimicking
the proof of lemma 4 with N replaced by A(v)). Thus
i contains at least (1 -)jC 0
vertices of C 0
j at the end
of the vertex removal phase, and hence by the second case
after the vertex addition phase.
Finally we show that every non-singleton cluster A i is
11-clean. We know that at the end of vertex removal phase,
j. So the total number of positive edges leaving A 0
is at most 3-jA 0
. Since, in the vertex addition step, we
add vertices that are 7-good wrt A 0
these can be at most
j.
Since all vertices v in A i are at least 7-good wrt A 0
Similarly,
This gives us
the result.
Now we are ready to bound the mistakes of A in terms of
OPT and OPT 0 . Call mistakes that have both end points
in some clusters A i and A j as internal mistakes and those
that have an end point in Z as external mistakes. Similarly
in OPT 0 , we call mistakes among the sets C 0
i as internal
mistakes and mistakes having one end point in S as external
mistakes. We bound mistakes of Cautious in two steps: the
following lemma bounds external mistakes.
Lemma 7 The total number of external mistakes made by
Cautious are less than the external mistakes made by OPT 0 .
Proof: From theorem 3, it follows that Z cannot contain
any vertex v in some C 0
. Thus, Z  S. Now, any external
mistakes made by Cautious are positive edges adjacent
to vertices in Z. These edges are also mistakes in OPT 0
since they are incident on singleton vertices in S. Hence
the lemma follows.
Now consider the internal mistakes of A. Notice that
these could be many more than the internal mistakes of
OPT 0 . However, we can at this point apply Lemma 1
on the graph induced by V In particular, the
bound on internal mistakes follows easily by observing that
11-  1=4, and that the mistakes of the optimal clustering
on the graph induced by V 0 is no more than mOPT . Thus,
Lemma 8 The total number of internal mistakes of Cautious
is  8mOPT .
Summing up results from the lemmas 7 and 8, and using
lemma 2, we get the following theorem:
Theorem 9 m Cautious  9( 1
4 A PTAS for maximizing agreements
In this section, we give a PTAS for maximizing agree-
ments: the total number of positive edges inside clusters
and negative edges between clusters.
Let OPT denote the optimal clustering and A denote our
clustering. We will abuse notation and also use OPT to denote
the number of agreements in the optimal solution. As
noticed in the introduction, OPT  n(n 1)=4. So it suffices
to produce a clustering that has at least OPT n 2
agreements, which will be the goal of our algorithm. Let
the number of positive edges between
sets Similarly, let - the number
of negative edges between the two. Let OPT() denote
the optimal clustering that has all non-singleton clusters of
size greater than n.
Proof: Consider the clusters of OPT of size less than or
equal to n and break them apart into clusters of size 1.
Breaking up a cluster of size s reduces our objective function
by at most s , which can be viewed as s=2 per node in
the cluster. Since there are at most n nodes in these clusters,
and these clusters have size at most n, the total loss is at
most  n 2The above lemma means that it suffices to produce a
good approximation to OPT(). Note that the number
of non-singleton clusters in OPT() is less than 1
.
Let C OPT
k denote the non-singleton clusters of
OPT() and let C OPT
k+1 denote the set of points which correspond
to singleton clusters.
4.1 A PTAS doubly-exponential in 1=
If we are willing to have a run time that is doubly-
exponential in 1=, we can do this by reducing our problem
to the General Partitioning problem of [13]. The idea is as
follows.
denote the graph of only the + edges in G. Then,
notice that we can express the quality of OPT() in terms
of just the sizes of the clusters, and the number of edges in
between and inside each of C OPT
k+1 . In par-
ticular, if s
the number of agreements in OPT() is:
e i;i
e k+1;k+1
The General Partitioning property tester of [13] allows us
to specify values for the s i and e ij , and if a partition of G
exists satisfying these constraints, will produce a partition
that satisfies these approximately. We obtain a partition that
has at least OPT() n 2 agreements. The property tester
runs in time exponential in ( 1
polynomial in n.
Thus if we can guess the values of these sizes and number
of edges accurately, we would be done. It suffices, in
fact, to only guess the values up to an additive  2 n for the
and up to an additive  3 n 2 for the e i;j , because this
introduces an additional error of at most O(). So, at most
calls to the property tester need to be made.
Our algorithm proceeds by finding a partition for each possible
value of s i and e i;j and returns the partition with the
maximum number of agreements. We get the following result

Theorem 11 The General Partitioning algorithm returns a
clustering of graph G which has more than OPT
agreements with probability at least 1 -. It runs in time
exponential in ( 1
polynomial in n and 1
- .
4.2 A singly-exponential PTAS
We will now describe an algorithm that is based on the
same basic idea of random sampling used by the General
Partitioning algorithm. The idea behind our algorithm is
as follows: Notice that if we knew the density of positive
edges between a vertex and all the clusters, we could put v
in the cluster that has the most positive edges to it. How-
ever, trying all possible values of the densities requires too
much time. Instead we adopt the following
select a small random subset W of vertices and cluster them
correctly into fW i g with W i  O i 8i, by enumerating all
possible clusterings of W . Since this subset is picked ran-
domly, with a high probability, for all vertices v, the density
of positive edges between v and W i will be approximately
equal to the density of positive edges between v and O i .
So we can decide which cluster to put v into, based on this
information. However this is not sufficient to account for
edges between two vertices both of which do not
belong to W . So, we consider subsets U i of size m at a time
and try out all possible clusterings fU ij g of them, picking
the one that maximizes agreements with respect to fW i g.
This gives us the PTAS.
Firstly note that if jC OPT
we only consider
the agreements in the graph GnC OPT
affects the solution
by at most n 2 . For now, we will assume that jC OPT
and will present the algorithm and analysis based on this
assumption. Later we will discuss the changes required to
deal with the other case.
In the following algorithm  is a performance parameter
to be specified later. Let
and  the density of
positive edges inside the cluster C OPT
ij the density
of negative edges between clusters C OPT
.
That is,
We begin by defining a measure of goodness of a clustering
of some set U i with respect to fW i g, that will
enable us to pick the right clustering of the set U i .
satisfies the following for all
and, for at least (1  0 )n of the vertices x and 8 j,
Our algorithm is as follows:
Algorithm Divide&Choose:
1. Pick a random subset W  V of size m.
2. For all partitions W of W do
(b) Let
m 1. Consider a random partition of
, such that 8i, jU
(c) For all i do:
1)-partitions of U i and
let U be the partition that is
above). If there is no such partition, choose
arbitrarily.
(d) Let A be the
number of agreements of this clustering.
3. Let fW i g be the partition of W that maximizes
Return the clusters fA i corresponding
to this partition of W .
We will concentrate on the "right" partition of of W given
by
We will show that the number of
agreements of the clustering A corresponding
to this partition fW i g is at least OPT() 2n 2 . Since we
pick the best clustering, this gives us a PTAS.
We will begin by showing that with a high probability,
for most values of i, the partition of U i s corresponding to
the optimal partition is good with respect to fW i g. Thus
the algorithm will find at least one such partition. Next we
will show that if the algorithm finds good partitions for most
it achieves at least OPT O()n 2 agreements.
We will need the following results from probability the-
ory. Please refer to [2] for a proof.
Fact 1: Let H(n; m; l) be the hypergeometric distribution
with parameters n; m and l (choosing l samples from n
points without replacement with the random variable taking
a value of 1 on exactly m out of the n points). Let
lm
Fact 2: Let mutually independent r.v.s
such that jX i E[X i ]j < m for all i. Let
then
a 2
We will also need the following lemma:
Lemma 12 Let Y and S be arbitrary disjoint sets and Z be
a set picked from S at random. Then we have the following:
.
is a sum of jZj random variables -
(v 2 Z), each bounded above by jY j and having expected
Thus applying Fact 2, we get
2e  02 jZj=2
Now notice that since we picked W uniformly at random
from V , with a high probability the sizes of W i s are
in proportion to jC OPT
j. The following lemma formalizes
this.
With probability at least 1 2ke  02 m=2 , 8i,
Proof: For a given i, using Fact 1 and since
2e  02 mjC OPT
Taking union bound over
the k values of i we get the result.
Using Lemma 13, we show that the computed values of ^
are close to the true values p i and n ij respectively.
This gives us the following two lemmas 3 .
Lemma 14 If W i  C OPT
i and W j  C OPT
with probability at least 1 4e
Proof We can apply lemma 12 in two steps -
first to bound - + (W
in terms of -
by considering the process of picking W i from C OPT
second to bound - in terms of -
fixing W i and considering the process of picking W j from
. Then using lemma 13, we combine the two and get
the lemma.
Lemma 15 With probability at least 1 8
Proof Note that we cannot use an argument similar
to the previous lemma directly here since we are dealing
with edges inside the same set. We use the following trick:
consider the partition of C OPT
subsets of size  0 n 0
j. The idea is to bound the number
of positive edges between every pair of subsets of C OPT
using
argument in the previous lemma and adding these up to
get the result.
Now
. The following lemma shows
that for all i, with a high probability all U ij s are  0 -good wrt
g. So we will be able to find  0 -good partitions for most
Lemma For a given i, let U
probability at least 1
are
g.
Proof Sketch: The first and second conditions of Definition
2 can be obtained by applying an argument similar to
lemmas 15 and 14 respectively.
In order to obtain the third condition, we consider
as a sum of m f0; 1g random variables (corre-
sponding to picking U i from V ), each of which is 1 iff the
picked vertex lies in C OPT
j and is adjacent to x. Then an application
of Chernoff bound followed by union bound gives
us the condition.
Now we can bound the total number of agreements of
in terms of OPT:
3 Please refer to [5] for full proofs of the lemmas.
Theorem 17 If jC OPT
probability at least 1 .
Proof: From lemma 16, the probability that we were not
able to find a  0 -good partition of U i wrt k is at
most
m=4 . By our choice of m, this is at most
with probability at least 1 =2, at most =2 of
the U i s do not have an  0 -good partition.
In the following calculation of the number of agree-
ments, we assume that we are able to find good partitions
of all U i s. We will only need to subtract at most n 2 =2
from this value to obtain the actual number of agreements,
since each U i can effect the number of agreements by at
most mn.
We start by calculating the number of positive
edges inside a cluster A j . These are given by
a
x). Using the fact that U aj is good wrt
(condition (3)),
The last follows from the fact that U bj is good wrt fW i g
(condition (1)). From Lemma 13,
Thus we bound
Now using Lemma 15, the total number of agreements is at
least
Hence, A
Similarly, consider the negative edges in A. Using lemma
14 to estimate - (U ai ; U bj ), we get,
ab
Summing over all i < j, we get the total number of negative
agreements is at least OPT 12
So we have, A  OPT 44
However, since we lose n 2 =2 for not finding  0 -good partitions
of every U i (as argued before), n 2 due to C OPT
using
we obtain A  OPT 3n 2 .
The algorithm can fail in four situations: more than =2
do not have an  0 -good partition with probability at
most =2, lemma 13 does not hold for some W i with probability
at most 2ke  02 m=2 , lemma 15 does not hold for
some i with probability at most 8k
m=4 or lemma 14
does not hold for some pair with probability at most
. The latter three quantities are at most =2 by
our choice of m. So, the algorithm succeeds with probability
greater than 1 .
Now we need to argue for the case when jC OPT
Notice that in this case, using an argument similar to lemma
13, we can show that jW k+1 j  mwith a very high prob-
ability. This is good because, now with a high probability,
U i(k+1) will also be  0 -good wrt W k+1 for most values of
i. We can now count the number of negative edges from
these vertices and incorporate them in the proof of Theorem
17 just as we did for the other k clusters. So in this
case, we can modify algorithm Divide&Choose to consider
-goodness of the (k+1)th partitions as well. This gives us
the same guarantee as in Theorem 17. Thus our strategy will
be to run Algorithm Divide&Choose once assuming that
again assuming that jC OPT
and picking the better of the two outputs. One of the two
cases will correspond to reality and will give us the desired
approximation to OPT.
Now each U i has O(k m ) different partitions. Each iteration
takes O(nm) time. There are n=m U i s, so for each
partition of W , the algorithm takes time O(n
there are k m different partitions of W , the total running time
of the algorithm is O(n 2 k 2m
gives us the following theorem:
Theorem using
Divide&Choose runs in time O(n 2 e O( 1
probability at least 1 -produces a clustering with number
of agreements at least OPT -n 2 .
Minimizing disagreements in [
weighted graphs
In section 3, we developed an algorithm for minimizing
disagreements in a graph with +1 and 1 weighted edges.
Now we consider the situation in which edge weights lie in
the interval [
To address this setting, we need to define a cost model -
the penalty for placing an edge inside or between clusters.
One natural model is a linear cost function. Specifically,
given a clustering, we assign a cost of 1 xif an edge of
weight x is within a cluster and a cost of 1+xif it is placed
between two clusters. For example, an edge weighing 0:5
incurs a cost of 0:25 if it lies inside a cluster and 0:75 oth-
erwise. A 0 weight edge, on the other hand, incurs a cost
of 1=2 no matter what.
It turns out that any algorithm that finds a good clustering
in a f1; 1ggraph also works well in the [ case
under a linear cost function.
Theorem 19 Let A be an algorithm that produces a clustering
on a f1; 1ggraph with approximation ratio .
Then, we can construct an algorithm A 0 that achieves an
approximation ratio of
the linear cost function.
Proof: Let G be a [ be the
1ggraph obtained when we assign a weight of 1 to
all positive edges in G and 1 to all the negative edges (0
cost edges are weighted arbitrarily). Let OPT be the optimal
clustering on G and OPT 0 the optimal clustering on G 0 .
Also, let m 0 be the measure of cost (on G 0 ) in the f1; 1g
penalty model and m in the new [
OPT  2mOPT . The latter is because
OPT incurs a greater penalty of 1 in m 0 as compared to m
only when a positive edge is between clusters or a negative
edge inside a cluster. In both these situations, OPT incurs
a cost of at least 1=2 in m and at most 1 in m 0 . This gives
us the above equation.
Our algorithm A 0 simply runs A on the graph G 0 and
outputs the resulting clustering A. So, we have, m 0
A
Now we need to bound mA in terms of m 0
A . Notice that,
if a positive edge lies between two clusters in A, or a negative
edge lies inside a cluster, then the cost incurred by A
for these edges in m 0 is 1 while it is at most 1 in m. So, the
total cost due to such mistakes is at most m 0
A . On the other
hand, if we consider cost due to positive edges inside clus-
ters, and negative edges between clusters, then OPT also
incurs at least this cost on those edges (because cost due to
these edges can only increase if they are clustered differ-
ently). So cost due to these mistakes is at most mOPT .
So we have,
A +mOPT  2mOPT +mOPT
Another natural cost model is one in which an edge of
weight x incurs a cost of jxj when it is clustered improperly
(inside a cluster if x < 0 or between clusters of x > 0) and
a cost of 0 when it is correct. We do not know of any good
approximation in this case (see Section 7).
6 Random noise
Going back to our original motivation, if we imagine
there is some true correct clustering OPT of our n items,
and that the only reason this clustering does not appear perfect
is that our function f(A; B) used to label the edges has
some error, then it is natural to consider the case that the the
errors are random. That is, there is some constant noise rate
< 1=2 and each edge, independently, is mislabeled with
respect to OPT with probability . In the machine learning
context, this is called the problem of learning with random
noise. As can be expected, this is much easier to handle
than the worst-case problem. In fact, with very simple algorithms
one can (whp) produce a clustering that is quite
close to OPT, much closer than the number of disagreements
between OPT and f . The analysis is fairly standard
(much like the generic transformation of Kearns [16] in the
machine learning context, and even closer to the analysis
of Condon and Karp for graph partitioning [11]). In fact,
this problem nearly matches a special case of the planted-
partition problem of McSherry [18]. We present our analysis
anyway since the algorithms are so simple.
One-sided noise: As an easier special case, let us consider
only one-sided noise in which each true "+" edge is
flipped to " " with probability . In that case, if u and v are
in different clusters of OPT, then jN
for certain. But, if u and v are in the same cluster, then
every other node in the cluster independently has probability
of being a neighbor to both. So, if the
cluster is large, then N have a non-empty
intersection with high probability. So, consider clustering
greedily: pick an arbitrary node v, produce a cluster
then repeat on
probability we will correctly cluster all
nodes whose clusters in OPT are of size !(log n). The remaining
nodes might be placed in clusters that are too small,
but overall the number of edge-mistakes is only ~
O(n).
Two-sided noise: For the two-sided case, it is technically
easier to consider the symmetric difference of N + (u) and
(v). If u and v are in the same cluster of OPT, then
every node w 62 fu; vg has probability exactly 2(1 ) of
belonging to this symmetric difference. But, if u and v are
in different clusters, then all nodes w in OPT(u)[OPT(v)
have probability (1 belonging
to the symmetric difference. (For w 62 OPT(u) [OPT(v),
the probability remains 2(1 ).) Since 2(1 ) is a
constant less than 1=2, this means we can confidently detect
that u and v belong to different clusters so long as
log n). Furthermore, using
just (v)j, we can approximately sort the vertices
by cluster sizes. Combining these two facts, we can whp
correctly cluster all vertices in large clusters, and then just
place each of the others into a cluster by itself, making a
total of ~
O(n 3=2 ) edge mistakes.
7 Open Problems and Concluding Remarks
In this paper, we have presented a constant-factor approximation
for minimizing disagreements, and a PTAS for
maximizing agreements, for the problem of clustering vertices
in a fully-connected graph G with f+; g edge labels.
In Section 5 we extended some of our results to the case of
real-valued labels, under a linear cost metric.
One interesting open question is to find good approximations
for the case when edge weights are in f1; 0; +1g
(equivalently, edges are labeled + or but G is not necessarily
fully-connected) without considering the 0-edges
as "half a mistake". In that context it is still easy to cluster
if a perfect clustering exists: the same simple strategy
works of removing the edges and producing each connected
component of the resulting graph as a cluster. The
random case is also easy if defined appropriately. However,
our approximation techniques do not appear to go through.
We do not know how to achieve a constant-factor, or even
logarithmic factor, approximation for minimizing disagree-
ments. Note that we can still use our Divide & Choose
algorithm to achieve an additive approximation of n 2 to
the number of agreements. However, this does not imply a
PTAS for maximizing agreements because OPT might be
A further generalization of the problem is to consider unbounded
edge weights (lying in [1;+1]). For example,
the edge weights might correspond to the log odds of two
documents belonging to the same cluster. Here the number
of disagreements could be defined as the total weight of
positive edges between clusters and negative edges inside
clusters, and agreements defined analogously. Again, we
do not know of any good algorithm for approximating the
number of disagreements in this case. We believe the problem
of maximizing agreements should be APX-hard for this
generalization, but have not been able to prove it. We can
show, however, that a PTAS would give an n  approximation
algorithm for k-coloring, for any constant k. 4 The incomplete
model seems to be as hard as
this problem.
For the original problem on a fully connected f+; g
graph, another question is whether one can approximate the
correlation: the number of agreements minus the number
of disagreements. It is easy to show that OPT must be
n)
for this measure, but we do not know of any good approx-
imation. It would also be good to improve our (currently
fairly large) constant for approximating disagreements.



--R

Efficient testing of large graphs.
The Probabilistic Method.
A new rounding procedure for the assignment problem with applications to dense graph arrangements.
Polynomial time approximation schemes for dense instances of np-hard prob- lems
Correlation clustering (http://www.
Agnostic boost- ing
Improved combinatorial algorithms for the facility location and k-median problems
Personal communication
Learning to match and cluster entity names.
Learning to match and cluster large high-dimensional data sets for data integration
Algorithms for graph partitioning on the planted partition model.

Property testing and its connection to learning and approximation.
A unified approach to approximation algorithms for bottleneck problems.

Efficient noise-tolerant learning from statistical queries
Toward efficient agnostic learning.
Spectral partitioning of random graphs.
Testing the diameter of graphs.
Clustering for edge-cost minimization
--TR
A unified approach to approximation algorithms for bottleneck problems
Toward Efficient Agnostic Learning
MAX-CUT has a randomized approximation scheme in dense graphs
An MYAMPERSANDOtilde;(<italic>n</italic><supscrpt>3/14</supscrpt>)-coloring algorithm for 3-colorable graphs
Property testing and its connection to learning and approximation
Efficient noise-tolerant learning from statistical queries
Polynomial time approximation schemes for dense instances of <inline-equation> <f> <sc>NP</sc></f> </inline-equation>-hard problems
Clustering for edge-cost minimization (extended abstract)
Algorithms for graph partitioning on the planted partition model
Approximation algorithms for metric facility location and <italic>k</italic>-Median problems using the primal-dual schema and Lagrangian relaxation
Computers and Intractability; A Guide to the Theory of NP-Completeness
Testing the diameter of graphs
Improved Algorithms for the Random Cluster Graph Model
Agnostic Boosting
Learning to match and cluster large high-dimensional data sets for data integration
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems
Spectral Partitioning of Random Graphs
Clustering with Qualitative Information
Correlation Clustering

--CTR
Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with qualitative information, Journal of Computer and System Sciences, v.71 n.3, p.360-383, October 2005
Anders Dessmark , Jesper Jansson , Andrzej Lingas , Eva-Marta Lundell , Mia Persson, On the approximability of maximum and minimum edge clique partition problems, Proceedings of the 12th Computing: The Australasian Theroy Symposium, p.101-105, January 16-19, 2006, Hobart, Australia
Thorsten Joachims , John Hopcroft, Error bounds for correlation clustering, Proceedings of the 22nd international conference on Machine learning, p.385-392, August 07-11, 2005, Bonn, Germany
Thomas Finley , Thorsten Joachims, Supervised clustering with support vector machines, Proceedings of the 22nd international conference on Machine learning, p.217-224, August 07-11, 2005, Bonn, Germany
Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering aggregation, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.4-es, March 2007
Shai Avidan , Yael Moses , Yoram Moses, Centralized and Distributed Multi-view Correspondence, International Journal of Computer Vision, v.71 n.1, p.49-69, January   2007
Surajit Chaudhuri , Anish Das Sarma , Venkatesh Ganti , Raghav Kaushik, Leveraging aggregate constraints for deduplication, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Ioannis Giotis , Venkatesan Guruswami, Correlation clustering with a fixed number of clusters, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1167-1176, January 22-26, 2006, Miami, Florida
Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Yigal Bejerano , Mark A. Smith , Joseph Naor , Nicole Immorlica, Efficient location area planning for personal communication systems, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.438-450, April 2006
document classification;clustering;approximation algorithm