Correlation Clustering and Biclustering with Locally Bounded
Errors

arXiv:1506.08189v3 [] 24 May 2016

Gregory J. Puleo

Olgica Milenkovic

May 25, 2016
Abstract
We consider a generalized version of the correlation clustering problem, defined as follows. Given a
complete graph G whose edges are labeled with + or −, we wish to partition the graph into clusters
while trying to avoid errors: + edges between clusters or − edges within clusters. Classically, one seeks
to minimize the total number of such errors. We introduce a new framework that allows the objective to
be a more general function of the number of errors at each vertex (for example, we may wish to minimize
the number of errors at the worst vertex) and provide a rounding algorithm which converts “fractional
clusterings” into discrete clusterings while causing only a constant-factor blowup in the number of errors
at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete
problem under a wide variety of objective functions.

1

Introduction

Correlation clustering is a clustering model first introduced by Bansal, Blum, and Chawla [5, 6]. The basic
form of the model is as follows. We are given a collection of objects and, for some pairs of objects, we
are given a judgment of whether the objects are similar or dissimilar. This information is represented as a
labeled graph, with edges labeled + or − according to whether the endpoints are similar or dissimilar. Our
goal is to cluster the graph so that + edges tend to be within clusters and − edges tend to go across clusters.
The number of clusters is not specified in advance; determining the optimal number of clusters is instead
part of the optimization problem.
Given a solution clustering, an error is a + edge whose endpoints lie in different clusters or a − edge
whose endpoints lie in the same cluster. In the original formulation of the correlation clustering, the goal is
to minimize the total number of errors; this formulation of the optimization problem is called MinDisagree.
Finding an exact optimal solution is NP-hard even when the input graph is complete [5, 6]. Furthermore,
if the input graph is allowed to be arbitrary, the best known approximation ratio is O(log n), obtained
by [9, 10, 14]. Assuming the Unique Games Conjecture of Khot [16], no constant-factor approximation for
MinDisagree on arbitrary graphs is possible; this follows from the results of [11, 21] concerning the minimum
multicut problem and the connection between correlation clustering and minimum multicut described in
[9, 10, 14].
Since theoretical barriers appear to preclude constant-factor approximations on arbitrary graphs, much
research has focused on special graph classes such as complete graphs and complete bipartite graphs, which
are the graph classes we consider here. Ailon, Charikar, and Newman [2, 3] gave a very simple randomized
3-approximation algorithm for MinDisagree on complete graphs. This algorithm was derandomized by
van Zuylen and Williamson [24], and a parallel version of the algorithm was studied by Pan, Papailiopoulos,
Recht, Ramchandran, and Jordan [20]. More recently, a 2.06-approximation algorithm was announced by
Chawla, Makarychev, Schramm and Yaroslavtsev [12]. Similar results have been obtained for complete bipartite graphs. The first constant approximation algorithm for correlation clustering on complete bipartite
graphs was described by Amit [4], who gave an 11-approximation algorithm. This ratio was improved by
Ailon, Avigdor-Elgrabli, Liberty and van Zuylen [1], who obtained a 4-approximation algorithm. Chawla,
Makarychev, Schramm and Yaroslavtsev [12] announced a 3-approximation algorithm for correlation clustering on complete k-partite graphs, for arbitrary k, which includes the complete bipartite case. Bipartite
clustering has also been studied, outside the correlation-clustering context, by Lim, Chen, and Xu [19].
1

We depart from the classical correlation-clustering literature by considering a broader class of objective
functions which also cater to the need of many community-detection applications in machine learning, social
sciences, recommender systems and bioinformatics [13, 22, 18]. The technical details of this class of functions
can be found in Section 2. As a representative example of this class, we introduce minimax correlation
clustering.
In minimax clustering, rather than seeking to minimize the total number of errors, we instead seek to
minimize the number of errors at the worst-off vertex in the clustering. Put more formally, if for a given
clustering each vertex v has yv incident edges that are errors, then we wish to find a clustering that minimizes
maxv yv .
Minimax clustering, like classical correlation clustering, is NP-hard on complete graphs, as we prove
in Appendix C. To design approximation algorithms for minimax clustering, it is necessary to bound the
growth of errors locally at each vertex when we round from a fractional clustering to a discrete clustering;
this introduces new difficulties in the design and analysis of our rounding algorithm. These new technical
difficulties cause the algorithm of [2, 3] to fail in the minimax context, and there is no obvious way to adapt
that algorithm to this new context; this phenomenon is explored further in Appendix A.
Minimax correlation clustering on graphs is relevant in detecting communities, such as gene, social
network, or voter communities, in which no antagonists are allowed. Here, an antagonist refers to an entity
that has properties inconsistent with a large number of members of the community. Alternatively, one
may view the minimax constraint as enabling individual vertex quality control within the clusters, which is
relevant in biclustering applications such as collaborative filtering for recommender systems, where minimum
quality recommendations have to be ensured for each user in a given category. As an illustrative example, one
may view a complete bipartite graph as a preference model in which nodes on the left represent viewers and
nodes on the right represent movies. A positive edge between a user and a movie indicates that the viewer
likes the movie, while a negative edge indicates that they do not like or have not seen the movie. We may be
interested in finding communities of viewers for the purpose of providing them with joint recommendations.
Using a minimax objective function here allows us to provide a uniform quality of recommendations, as we
seek to minimize the number of errors for the user who suffers the most errors.
A minimax objective function for a graph partitioning problem different from correlation clustering was
previously studied by [7]. In that paper, the problem under consideration was to split a graph into k roughlyequal-sized parts, minimizing the total number of edges leaving any part. Thus, the minimum in [7] is being
taken over the parts of the solution, rather than minimizing over vertices as we do here.
Another idea slightly similar to minimax clustering has previously appeared in the literature on fixedparameter tractability of the Cluster Editing problem, which is an equivalent formulation of Correlation Clustering. In particular, Komusiewicz and Uhlmann [17] proved that the following problem is fixedparameter tractable for the combined parameter (d, t):
(d, t)-Constrained-Cluster Editing
Input: A labeled complete graph G, a function τ : V (G) → {0, . . . , t}, and nonnegative integers
d and k.
Question: Does G admit a clustering into at most d clusters with at most k errors such that
every vertex v is incident to at most τ (v) errors?
(Here, we have translated their original formulation into the language of correlation clustering.) Komusiewicz
and Uhlmann also obtained several NP-hardness results related to this formulation of the problem. While
their work involves a notion of local errors for correlation clustering, their results are primarily focused on
fixed-parameter tractability, rather than approximation algorithms, and are therefore largely orthogonal to
the results of this paper.
The contributions of this paper are organized as follows. In Section 2, we introduce and formally express
our framework for the generalized version of correlation clustering, which includes both classical clustering
and minimax clustering as special cases. In Section 3, we give a rounding algorithm which allows the development of constant-factor approximation algorithms for the generalized clustering problem. In Section 4,
we give a version of this rounding algorithm for complete bipartite graphs.
In Appendix A, we discuss minimax clustering in more detail, and show that algorithms similar to the
Ailon–Charikar–Newman algorithm fail in the minimax context. In Appendix B we discuss the approximation
properties of the MaxAgree formulation of minimax clustering, where the objective is to maximize the
2

number of correct edges, rather than minimize the number of incorrect edges, at the worst vertex. In
Appendix C and Appendix D we prove that the minimax correlation clustering problem is NP-hard on
complete graphs and complete bipartite graphs, respectively. Appendix E contains technical details for
various proofs.

2

Framework and Formal Definitions

In this section, we formally set up the framework we will use for our broad class of correlation-clustering
objective functions.
Definition 1. Let G be an edge-labeled graph. A discrete clustering (or just a clustering) of G is a partition


of V (G). A fractional clustering of G is a vector x indexed by V (G)
such that xuv ∈ [0, 1] for all uv ∈ V (G)
2
2
and such that xvz ≤ xvw + xwz for all distinct v, w, z ∈ V (G).
If x is a fractional clustering, we can view xuv as a “distance” from u to v; the constraints xvz ≤ xvw +xwz
are therefore referred to as triangle inequality constraints. We also adopt the convention that xuu = 0 for
all u.
In the special case where all coordinates of x are 0 or 1, the triangle inequality constraints guarantee that
the relation defined by u ∼ v iff xuv = 0 is an equivalence relation. Such a vector x can therefore naturally
be viewed as a discrete clustering, where the clusters are the equivalence classes under ∼. By viewing a
discrete clustering as a fractional clustering with integer coordinates, we see that fractional clusterings are
a continuous relaxation of discrete clusterings, which justifies the name. This gives a natural notion of the
total weight of errors at a given vertex.
Definition 2. Let G be an edge-labeled complete graph, and let x be a fractional clustering of G. The
error vector of x with respect to G, written err(x), is a real vector indexed by V (G) whose coordinates are
defined by
X
X
err(x)v =
xvw +
(1 − xvw ).
w∈N + (v)

w∈N − (v)

If C is a clustering of G and xC is the natural associated fractional clustering, we define err(C) as err(xC ).
We are now prepared to formally state the optimization problem we wish to solve. Let Rn≥0 denote the set
of vectors in Rn with all coordinates nonnegative. Our problem is parameterized by a function f : Rn≥0 → R.
f -Correlation Clustering
Input: A labeled graph G.
Output: A clustering C of G.
Objective: Minimize f (err(C)).
In order to approximate f -Correlation Clustering, we introduce a relaxed version of the problem.
Fractional f -Correlation Clustering
Input: A labeled graph G.
Output: A fractional clustering x of G.
Objective: Minimize f (err(x)).
If f is convex on Rn≥0 , then using standard techniques from convex optimization [8], the Fractional f Correlation Clustering problem can be approximately solved in polynomial time, as the composite function
f ◦ err is convex and the constraints defining a fractional clustering are linear inequalities in the variables
xe . When G is a complete graph, we then employ a rounding algorithm based on the algorithm of Charikar,
Guruswami, and Wirth [9, 10] to transform the fractional clustering into a discrete clustering. Under rather
modest conditions on f , we are able to obtain a constant-factor bound on the error growth, that is, we can
produce a clustering C such that f (err(C)) ≤ cf (err(x)), where c is a constant not depending on f or x. In
particular, we require the following assumptions on f .
Assumption A. We assume that f : Rn≥0 → R has the following properties.
3

(1) f (cy) ≤ cf (y) for all c ≥ 0 and all y ∈ Rn , and
(2) If y, z ∈ Rn≥0 are vectors with yi ≤ zi for all i, then f (y) ≤ f (z).
Under Assumption A, the claim that f (err(C)) ≤ cf (err(x)) follows if we can show that err(C)v ≤ c err(x)v
for every vertex v ∈ V (G). This is the property we prove for our rounding algorithms.
We will slightly abuse terminology by referring to the constant c as an approximation ratio for the
rounding algorithm; this notation is motivated by the fact that when f is linear, the Fractional f -Correlation
Clustering problem can be solved exactly in polynomial time, and applying a rounding algorithm with
constant c to the fractional solution yields a c-approximation algorithm to the (discrete) f -Correlation
Clustering problem. In contrast, when f is nonlinear, we may only be able to obtain a (1 + ǫ)-approximation
for the Fractional f -Correlation Clustering problem, in which case applying the rounding algorithm yields a
c(1 + ǫ)-approximation algorithm for the discrete problem.
A natural class of convex objective functions obeying Assumption A is the class of ℓp norms. For all
p ≥ 1, the ℓp -norm on Rn is defined by
p

ℓ (x) =

n
X
i=1

|xi |

p

!1/p

.

As p grows larger, the ℓp -norm puts more emphasis on the coordinates with larger absolute value. This
justifies that definition of the ℓ∞ -norm as
ℓ∞ (x) = max{x1 , . . . , xn }.
Classical correlation clustering is the case of f -Correlation Clustering where f (x) = n1 ℓ1 (x), while minimax
correlation clustering is the case of f -Correlation Clustering where f (x) = ℓ∞ (x).
Our emphasis on convex f is due to the fact that convex programming techniques allow the Fractional
f -Correlation Clustering problem to be approximately solved in polynomial time when f is convex. However,
the correctness of our rounding algorithm does not depend on the convexity of f , only on the properties listed
in Assumption A. If f is nonconvex and obeys Assumption A, and we produce a “good” fractional clustering
x by some means, then our algorithm still produces a discrete clustering C with f (err(C)) ≤ cf (err(x)).

3

A Rounding Algorithm for Complete Graphs

We now describe a rounding algorithm to transform an arbitrary fractional clustering x of a labeled complete
graph G into a clustering C such that err(C)v ≤ c err(x)v for all v ∈ V (G).
Our rounding algorithm is based on the algorithm of Charikar, Guruswami, and Wirth [9, 10] and is
shown in Algorithm 1. The main difference between Algorithm 1 and the algorithm of [9, 10] is the new
strategy of choosing a pivot vertex that maximizes |Tu∗ |; in [9, 10], the pivot vertex is chosen arbitrarily.
Furthermore, the algorithm of [9, 10] always uses α = 1/2 as a cutoff for forming “candidate clusters”, while
we express α as a parameter which we later choose in order to optimize the approximation ratio.
Under the classical objective function, an optimal fractional clustering is the solution to a linear program,
which motivates the following notation for the more general case.
Definition 3. If uv is an edge of a labeled graph G, we define the LP-cost of uv relative to a fractional
clustering x to be xuv if uv ∈ E + , and 1 − xuv if uv ∈ E − . Likewise, the cluster-cost of an edge uv is 1 if
uv is an error in the clustering produced by Algorithm 1, and 0 otherwise.
Our general strategy for obtaining the constant-factor error bound for Algorithm 1 is similar to that of
[9, 10]. Each time a cluster is output, we pay for the cluster-cost of the errors incurred by “charging” the
cost of these errors to the LP-costs of the fractional clustering. The main difference between our proof and
the proof of [9, 10] is that we must pay for errors locally: for each vertex v, we must pay for all clustering
errors incident to v by charging to the LP cost incident to v. In particular, every clustering error must now
be paid for at each of its endpoints, while in [9, 10], it was enough to pay for each clustering error at one of
its endpoints. For edges which cross between a cluster and its complement, this requires a different analysis
4

Algorithm 1 Round fractional clustering x to obtain a discrete clustering, using threshold parameters α, γ
with 0 < γ < α < 1/2.
Let S = V (G).
while S 6= ∅ do
For each u ∈ S, let Tu = {w ∈ S − {u} : xuw ≤ α} and let Tu∗ = {w ∈ S − {u} : xuw ≤ γ}.
Choose a pivot vertex u ∈ S that maximizes |Tu∗ |.
LetPT = Tu .
if w∈T xuw ≥ α |T | /2 then
Output the cluster {u}. {Type 1 cluster}
Let S = S − {u}.
else
Output the cluster {u} ∪ T . {Type 2 cluster}
Let S = S − ({u} ∪ T ).
end if
end while
at each endpoint, a difficulty which was not present in [9, 10]. Our proof emphasizes the solutions to these
new technical problems; the parts of the proof that are technically nontrivial but follow earlier work are
omitted due to space constraints but can be found in Appendix E.
Observation 4. Let x be a fractional clustering of a graph G, and let w, z ∈ V (G). For any vertex u, we
have xwz ≥ xuz − xuw and 1 − xwz ≥ 1 − xuz − xuw .
Theorem 5. Let G be a labeled complete graph, let α and γ be parameters with 0 < γ < α < 1/2, and let
x be any fractional clustering of G. If C is the clustering produced by Algorithm 1 with the given input, then
for all v ∈ V (G) we have err(C)v ≤ c err(x)v , where c is a constant depending only on α and γ.
Proof. Let k1 , k2 , k3 be constants to be determined, with 1/2 < k1 < 1 and 0 < 2k2 ≤ k3 < 1/2. Also assume
that k1 α > γ and that k2 α ≤ 1 − 2α.
To prove the approximation ratio, we consider the cluster-costs incurred as each cluster is output, splitting
into cases according to the type of cluster. In our analysis, as the algorithm runs, we will mark certain
vertices as “safe”, representing the fact that some possible future clustering costs have been paid for in
advance. Initially, no vertex is marked as safe.
Case 1: A Type 1 cluster is output. Let X = S ∩ N + (u), with S as in Algorithm 1. The new cluster-cost
incurred at u is |X|, and for each v ∈ X, a new cluster-cost of 1 is incurred at v.
First we pay for the new cluster cost incurred at u. For each edge uv with v ∈ T , wePhave xuv ≤ α and
so 1 − xuv ≥ 1 − α ≥ xuv . Thus, the total LP cost of edges uv with v ∈ T is at least v∈T xuv , which is
at least α |T | /2 since {u} is output as a Type 1 cluster. Thus, charging each edge uv with v ∈ T a total of
2/α times its LP-cost pays for the cluster-cost of any positive edges from u to T . On the other hand, if uv
is a positive edge with v ∈ S − T , then since v ∈
/ T , we have xuv ≥ α. Hence, the LP-cost of uv is at least
α, and charging 1/α times the LP-cost of uv pays for the cluster-cost of this edge.
Now let v ∈ X; we must pay for the new cluster cost at v. If xuv ≥ k2 α, then the edge uv already incurs
LP cost at least k2 α, so the new cost at v is only 1/(k2 α) times the LP-cost of the edge uv. So assume
xuv < k2 α. In this case, we say that u is a bad pivot for v.
First suppose that v is not safe (as is initially the case). We will make a single charge to the edges
incident to v that is large enough to pay for both the edge uv and for all possible future bad pivots, and
then we will mark v as safe to indicate that we have done this. The basic idea is that if v has many possible
bad pivots,Pthen since xuv is “small”, all of these possible bad pivots are also close to u, thus included in
Tu . Since w∈Tu xuw ≥ α |Tu | /2, there is a large set B ⊆ Tu of vertices that are “moderately far” from u,
and therefore moderately far from v. The number of these vertices grows with the number of bad pivots, so
charging all the edges vz for z ∈ B is sufficient to pay for all bad pivots.
We now make this argument rigorous. Let Pv be the set of potential bad pivots for v, defined by
Pv = {p ∈ S : xvp < k2 α}.

5

Note that u ∈ Pv . Since k2 < 1/4, we have xup ≤ xuv + xvp < α/2 for all p ∈ Pv ; hence Pv ⊆ T . Define the
vertex set B by
B = {z ∈ T : xuz > k3 α}.
Since xuz ≤ α for all z ∈ T , we see that
X

xuz ≤ k3 α |T − B| + α |B| .

z∈T

On the other hand, since {u} is output as a Type 1 cluster, we have
X
xuz ≥ α |T | /2.
z∈T

Combining these inequalities and rearranging, we obtain |B| ≥ (1 − 2k3 ) |T − B|. For each vertex z ∈ B, we
have xvz ≥ xuz − xuv ≥ (k3 − k2 )α; in particular, since k3 ≥ 2k2 , we have xvz ≥ k2 α, so that z ∈
/ Pv . Hence
|T − B| ≥ |Pv |, and we have |B| ≥ (1 − 2k3 ) |Pv |.
On the other hand, for z ∈ B we also have 1 − xvz ≥ 1 − xuv − xuz ≥ 1 − (1 + k2 )α. It follows that
each edge vz for z ∈ B has LP-cost at least min((k3 − k2 )α, 1 − (1 + k2 )α), independent of whether vz is
positive or negative. It is easy to check that since α < 1/2 and k3 < 1, this minimum is always achieved
by (k3 − k2 )α. Therefore, we can pay for the (possible) Type-1-cluster cost of all edges vp for p ∈ Pv by
charging each edge vz with z ∈ B a total of
1
(1 − 2k3 )(k3 − k2 )α
times its LP-cost. We make all these charges when the cluster {u} is created and put them in a “bank
account” to pay for later Type-1-cluster costs for v. Then we mark v as safe. The total charge in the bank
account is at least |Pv |, which is enough to pay for all bad pivots for v.
We have just described the case where u is a bad pivot and v is not safe. On the other hand, if u is a
bad pivot and v is safe, then v already has a bank account large enough to pay for all its bad pivots, and we
simply charge 1 to the account to pay for the edge uv.
Case 2: A Type 2 cluster {u} ∪ T is output. The negative edges within {u} ∪ T are easy to pay for: if
vw if a negative edge inside {u} ∪ T , then we have 1 − xvw ≥ 1 − xuv − xuw ≥ 1 − 2α, so we can pay for each
1
times its LP-cost.
of these edges by charging a factor of 1−2α
Thus, we consider edges joining {u} ∪ T with S − ({u} ∪ T ). We call these edges cross-edges for their
endpoints. A standard argument (see Appendix E) shows that for z ∈ S − ({u} ∪ T ), the total cluster-cost
of the cross-edges for z is at most max{1/(1 − 2α), 2/α} times the LP-cost of those edges, so the vertices
outside {u} ∪ T can be dealt with easily.
However, we also must bound the cluster-cost at vertices inside {u} ∪ T . This is where we use the
maximality of |Tu∗ |.
Let w ∈ {u} ∪ T . First consider the positive cross-edges wz such that xwz ≥ γ. Any such edge has
cluster-cost 1 and already has LP-cost at least γ, so charging 1/γ times the LP-cost to such an edge pays for
its cluster cost. Now let X = {z ∈ S − ({u} ∪ T ) : xwz < γ}; we still must pay for the edges wz with z ∈ X.
If xuw ≤ k1 α, which includes the case u = w, then for all z ∈ X, we have xwz ≥ xuz − xuw ≥ α − k1 α =
(1 − k1 )α. Hence, for any positive edge wz with z ∈ X, the LP-cost of wz is at least (1 − k1 )α, and so
the cluster cost of the edge wz is at most 1/((1 − k1 )α) times the LP cost. Charging this factor to each
cross-edge pays for the cluster-cost of each cross-edge.
Now suppose xuw > k1 α. Since k1 α > γ, this implies w ∈
/ Tu∗ . In this case, it is possible that w may have
many positive neighbors z ∈ X for which xwz is quite small, so we cannot necessarily pay for the cluster-cost
of the edges joining w and X by using their LP-cost. Instead, we charge their cluster-cost to the LP-cost of
edges within T .
Observe that X ⊆ Tw∗ , and hence |Tw∗ | ≥ |X|. By the maximality of |Tu∗ |, this implies that |Tu∗ | ≥ |X|.
Now for any v ∈ Tu∗ , we have the following bounds:
xwv ≥ xuw − xuv ≥ k1 α − γ,
1 − xwv ≥ 1 − xuw − xuv ≥ 1 − α − γ.
6

Since α < 1/2 and k1 ≤ 1, we have k1 α ≤ α < 1 − α, so these lower bounds imply that each edge wv with
v ∈ Tu∗ has LP-cost at least k1 α − γ, independent of whether wv is a positive or negative edge. Thus, the
total LP cost of edges joining w to Tu∗ is at least (k1 α − γ) |Tu∗ |.
Since the total cluster-cost of edges joining w and X is at most |X| and since |Tu∗ | ≥ |X|, we can pay for
1
these edges by charging each edge wv with v ∈ Tu∗ a factor of k1 α−γ
times its LP-cost.
Having paid for all cluster-costs, we now look at the total charge accrued at each vertex. Fix any vertex
v and an edge vw incident to v. We bound the total amount charged to vw by v in terms of the LP-cost of
vw. There are three distinct possibilities for the edge vw: either vw ended inside a cluster, or v was clustered
before w, or w was clustered before v.
Case 1: vw ended within a cluster. In this case, v may have made the following charges:
• A charge of

1
(1−2k3 )(k3 −k2 )α

• A charge of

1
1−2α

• A charge of

1
k1 α−γ

times the LP-cost, to pay for a “bank account” for v,

times the LP-cost, to pay for vw itself if vw is a negative edge,
times the LP-cost, to pay for positive edges leaving the v-cluster.

Thus, in this case the total cost charged to vw by v is at most c1 times the LP-cost of vw, where
c1 =

1
1
1
+
+
.
(1 − 2k3 )(k3 − k2 )α 1 − 2α k1 α − γ

Case 2: v was clustered before w. In this case, v may have made the following charges:
• A charge of

1
(1−2k3 )(k3 −k2 )α

• A charge of at most

times the LP-cost, to pay for a “bank account” for v,

2
α

times the LP-cost, to pay for all cross-edges if v was output as a Type 1 cluster,
n
o
• A charge of at most max (1−k1 1 )α , γ1 times the LP-cost, to pay for vw if v was output in a Type 2
cluster.

Note that k1 > 1/2 implies that (1−k1 1 )α ≥ α2 , so we may disregard the case where v is output as a Type 1
cluster. Thus, in this case the total cost charged to vw by v is at most c2 times the LP-cost of vw, where


1
1
1
.
+ max
,
c2 =
(1 − 2k3 )(k3 − k2 )α
(1 − k1 )α γ
Case 3: w was clustered before v. In this case, v may have made the following charges:
• A charge of at most

1
(1−2k3 )(k3 −k2 )α

times the LP-cost, to pay for a “bank account” for v,

• A charge of at most k21α times the LP-cost, to pay for the cluster-cost of vw if vw is a positive edge
and w was output as a Type 1 cluster,
• A charge of at most
max



1
2
,
1 − 2α α



times the LP-cost, to pay for vw if w was output in a Type 2 cluster.
Clearly vw cannot receive both the second and third types of charge. Furthermore, since k2 ≤ 1/4, we have
1
2
1
k2 α ≥ α . Since k2 α ≤ 1 − 2α, we see that k2 α is the largest charge that vw could receive from either the
second or third type of charge. Thus, in this case the total cost charged to vw by v is at most c3 times the
LP-cost, where
1
1
+
c3 =
(1 − 2k3 )(k3 − k2 )α k2 α.
Thus, the approximation ratio of the algorithm is at most max{c1 , c2 , c3 }. We wish to choose the various
parameters to make this ratio as small as possible, subject to the various assumptions on the parameters
7

required for the correctness of the proof. It seems difficult to obtain an exact solution to this optimization
problem. Solving the problem numerically, we obtained the following values for the parameters:
α = 0.465744
k1 = 0.767566

γ = 0.0887449
k2 = 0.117219

k3 = 0.308433.

These parameters yield an approximation ratio of roughly 48.

4

A Rounding Algorithm for One-Sided Biclustering

In this section, we consider a version of the f -Correlation Clustering problem on complete bipartite graphs.
Let G be a complete bipartite graph with edges labeled + and −, and let V1 and V2 be its partite sets. We
will obtain a rounding algorithm that transforms any fractional clustering x into a discrete clustering C such
that err(C)v ≤ c err(x)v for all v ∈ V1 . Our algorithm is shown in Algorithm 2.
Our algorithm does not guarantee any upper bound on err(C)v for v ∈ V2 : as the algorithm treats the
sides V1 and V2 asymmetrically, it is difficult to control the per-vertex error at V2 . Nevertheless, an error
guarantee for the vertices in V1 suffices for some applications. Our approach is motivated by applications in
recommender systems, where vertices in V1 correspond to users, while vertices in V2 correspond to objects
to be ranked. In this context, quality of service conditions only need to be imposed for users, and not for
objects.
Algorithm 2 Round fractional clustering to obtain a discrete clustering, using threshold parameters α, γ
with α < 1/2 and γ < α.
Let S = V (G).
while V1 ∩ S 6= ∅ do
For each u ∈ V1 ∩ S, let Tu = {w ∈ S − {u} : xuw ≤ α} and let Tu∗ = {w ∈ V2 ∩ S : xuw ≤ γ}.
Choose a pivot vertex u ∈ V1 ∩ S that maximizes |Tu∗ |.
LetPT = Tu .
if w∈V2 ∩T xuw ≥ α |V2 ∩ T | /2 then
Output the singleton cluster {u}. {Type 1 cluster}
Let S = S − {u}.
else
Output the cluster {u} ∪ T . {Type 2 cluster}
Let S = S − ({u} ∪ T ).
end if
end while
Output each remaining vertex of V2 ∩ S as a singleton cluster.
Theorem 6. Let G be a labeled complete bipartite graph with partite sets V1 and V2 , let α, γ be parameters
as described in Algorithm 2, and let x be any fractional clustering of G. If C is the clustering produced by
Algorithm 2 with the given input, then for all v ∈ V1 we have err(C)v ≤ c err(x)v , where c is a constant
depending only on α and γ.
We note that the proof of Theorem 6 is actually simpler than the proof of Theorem 5, because the focus
on errors only at V1 eliminates the need for the “bad pivots” argument used in Theorem 6. This also leads
to a smaller value of c in Theorem 6 than we were able to obtain in Theorem 5.
Proof. As before, we make charges to pay for the new cluster costs at each vertex of V1 as each cluster is
output, splitting into cases according to the type of cluster. Let k1 be a constant to be determined, with
k1 α > γ.
Case 1: A Type 1 cluster {u} is output. In this case, the only cluster costs incurred are the positive
edges incident to u, all of which have their other endpoint in V2 . The averaging argument used in Case 1 of
Section 3 shows that charging every edge incident to u a factor of 2/α times its LP cost pays for the cluster
cost of all such edges.
8

Case 2: A Type 2 cluster {u} ∪ T is output. Negative edges within the cluster are easy to pay for: if
w1 w2 is a negative edge within the cluster, with wi ∈ Vi , then we have
1 − xw1 w2 ≥ 1 − xuw1 − xuw2 ≥ 1 − 2α,
so we can pay for the cluster-cost of such an edge by charging it a factor of 1/(1 − 2α) times its LP-cost.
We still must pay for positive edges joining the cluster with the rest of S; we call such edges cross-edges.
Each such edge must be paid for at its endpoint in V1 .
If z ∈ V1 is a vertex outside the cluster, then a standard argument (see Appendix E) shows that the
cross-edges for z can be paid for by charging each such edge a factor of max{1/(1 − 2α), 2/α)} times its LP
cost.
Now let w ∈ V1 be a vertex inside the cluster. We must pay for the cross-edges incident to w using the
LP-cost of the edges incident to w. First consider the positive edges from w to vertices z outside the cluster
such that xwz ≥ γ. Any such edge has cluster-cost 1 and LP-cost at least γ, so charging each such edge a
factor of 1/γ times its LP-cost pays for its cluster cost. Let X = {z ∈ (S ∩ V2 ) − T : xwz < γ}; we must pay
for the edges wz with z ∈ X. Note that xuz > α for all z ∈ X, since z ∈ X implies z ∈
/ T.
If xuw ≤ k1 α, then for all z ∈ X, we have
xwz ≥ xuz − xuw ≥ (1 − k1 )α.
Hence, for any positive cross-edge wz with z ∈ X, the LP-cost of wz is at least (1 − k1 )α, and so we can pay
for the cluster-cost of wz by charging wz a factor of (1−k1 1 )α times its LP-cost.
Now suppose xuw > k1 α. As before, we pay for the cross-edges by charging the edges inside the cluster.
Observe that |Tw∗ | ≥ |X|. Since u was chosen to maximize |Tu∗ |, this implies that |Tu∗ | ≥ |X|. For any v ∈ Tu∗ ,
we have
xwv ≥ xuw − xuv ≥ k1 α − γ.
On the other hand, for any v ∈ Tu∗ we also have
1 − xwv ≥ 1 − xuw − xuv ≥ 1 − α − γ ≥ α − γ.
Since k1 ≤ 1, it follows that the edge wv has LP-cost at least k1 α − γ independent of whether wv is positive
or negative. Thus, the total LP cost of edges joining w to Tu∗ is at least (k1 α − γ) |Tu∗ |.
Since the total cluster-cost of the cross- edges joining w and X is at most |X| and since |Tu∗ | ≥ |X|, we
1
times its LP-cost.
can pay for the cross-edges by charging each edge wv with v ∈ Tu∗ a factor of k1 α−γ
Having paid for all cluster-costs, we now look at the total charge accrued at each vertex. Fix a vertex
v ∈ V1 and an edge vw incident to v. We bound the total amount charged to vw by v in terms of the
LP-cost of vw. There are three distinct possibilities for the edge vw: either vw ended inside a cluster, or v
was clustered before w, or w was clustered before v.
Case 1: vw ended within a cluster. In this case, v may have made the following charges:
• A charge of at most
• A charge of

1
k1 α−γ

1
1−2α

times the LP cost, to pay for vw itself if vw is a negative edge,

times the LP-cost, to pay for positive edges leaving the v-cluster.

Thus, in this case the total cost charged to vw by v is at most c1 times the LP-cost of vw, where
c1 =

1
1
+
.
1 − 2α k1 α − γ

Case 2: v was clustered before w. In this case, v may have made the following charges:
• A charge of 2/α times the LP cost, to pay for vw if v was output as a singleton,
• A charge of max{ (1−k1 1 )α , γ1 } times the LP cost, to pay for vw if v was output in a nonsingleton cluster,

9

Since v makes at most one of the charges above, the total cost charged to vw by v is at most c2 times the
LP-cost of vw, where


1
1 2
c2 = max
.
, ,
(1 − k1 )α γ α
Case 3: w was clustered before v. In this case, v may have made the following charges:
1
• A charge of at most max{ 1−2α
, α2 } times the LP cost, to pay for cross-edges at v if w is output in a
nonsingleton cluster.

Thus, in this case the total cost charged to vw by v is at most c3 times the LP-cost of vw, where


2
1
.
,
c3 = max
1 − 2α α
The approximation ratio is max{c1 , c2 , c3 }. Numerically, we obtain an approximation ratio of at most 10 by
taking the following parameter values:
α = 0.377

5

γ = 0.102

k1 = 0.730

Acknowledgments

The authors thank Dimitris Papailiopoulos for helpful discussions that led to the example in Appendix A. The
authors also acknowledge funding from the NSF grants IOS 1339388 and CCF 1527636, 1526875, 1117980.
Research of the first author was supported by the IC Postdoctoral Program.

References
[1] Nir Ailon, Noa Avigdor-Elgrabli, Edo Liberty, and Anke Van Zuylen, Improved approximation algorithms
for bipartite correlation clustering, SIAM Journal on Computing 41 (2012), no. 5, 1110–1121.
[2] Nir Ailon, Moses Charikar, and Alantha Newman, Aggregating inconsistent information: ranking and
clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, ACM,
2005, pp. 684–693.
[3]

, Aggregating inconsistent information: ranking and clustering, Journal of the ACM (JACM) 55
(2008), no. 5, 23.

[4] Noga Amit, The bicluster graph editing problem, Master’s thesis, Tel Aviv University, 2004.
[5] Nikhil Bansal, Avrim Blum, and Shuchi Chawla, Correlation clustering, Proceedings of the 43rd Symposium on Foundations of Computer Science (Washington, DC, USA), FOCS ’02, IEEE Computer Society,
2002, pp. 238–.
[6]

, Correlation clustering, Mach. Learn. 56 (2004), no. 1-3, 89–113.

[7] Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph
Naor, and Roy Schwartz, Min-max graph partitioning and small set expansion, 2011 IEEE 52nd Annual
Symposium on Foundations of Computer Science—FOCS 2011, IEEE Computer Soc., Los Alamitos,
CA, 2011, pp. 17–26. MR 2932676
[8] Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004.
[9] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth, Clustering with qualitative information,
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (Washington,
DC, USA), FOCS ’03, IEEE Computer Society, 2003, pp. 524–.
[10]

, Clustering with qualitative information, J. Comput. Syst. Sci. 71 (2005), no. 3, 360–383.
10

[11] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar, On the hardness
of approximating multicut and sparsest-cut, Computational Complexity 15 (2006), no. 2, 94–114.
[12] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev, Near optimal lp
rounding algorithm for correlation clustering on complete and complete k-partite graphs, 2014.
[13] Yizong Cheng and George M Church, Biclustering of expression data., ISMB, vol. 8, 2000, pp. 93–103.
[14] Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica, Correlation clustering in general
weighted graphs, Theoretical Computer Science 361 (2006), no. 2, 172–187.
[15] Michael R Garey and David S Johnson, Computers and intractability: a guide to NP-completeness,
1979.
[16] Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual
ACM symposium on Theory of computing, ACM, 2002, pp. 767–775.
[17] Christian Komusiewicz and Johannes Uhlmann, Cluster editing with locally bounded modifications, Discrete Appl. Math. 160 (2012), no. 15, 2259–2270. MR 2954767
[18] Hans-Peter Kriegel, Peer Kröger, and Arthur Zimek, Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering, ACM Transactions on Knowledge
Discovery from Data (TKDD) 3 (2009), no. 1, 1.
[19] Shiau Hong Lim, Yudong Chen, and Huan Xu, A convex optimization framework for bi-clustering,
Proceedings of The 32nd International Conference on Machine Learning, 2015, pp. 1679–1688.
[20] Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and
Michael I Jordan, Parallel correlation clustering on big graphs, arXiv preprint arXiv:1507.05086 (2015).
[21] D. Steurer and N. Vishnoi, Connections between unique games and multcut, Tech. Report TR09-125, Electronic Colloquium on Computational Complexity, 2009, Available at
http://eccc.hpi-web.de/report/2009/125.
[22] Panagiotis Symeonidis, Alexandros Nanopoulos, Apostolos Papadopoulos, and Yannis Manolopoulos,
Nearest-biclusters collaborative filtering with constant values, Advances in web mining and web usage
analysis, Springer, 2007, pp. 36–55.
[23] Johan M. M. van Rooij, Marcel E. van Kooten Niekerk, and Hans L. Bodlaender, Partition into triangles
on bounded degree graphs, Theory Comput. Syst. 52 (2013), no. 4, 687–718. MR 3038518
[24] Anke van Zuylen and David P. Williamson, Deterministic pivoting algorithms for constrained ranking
and clustering problems, Math. Oper. Res. 34 (2009), no. 3, 594–620. MR 2555338 (2010j:68136)

11

A

Minimax Clustering and the Failure of Pivoting Algorithms

In this appendix, we consider minimax clustering, which is the special case of f -Correlation Clustering where
f (y) = maxv∈V (G) yv . Thus, in minimax clustering, we seek to minimize the number of errors at the worst
vertex in the clustering. Equivalently, we are trying to minimize the ℓ∞ -norm of the error vector, in contrast
to classical correlation clustering, where we are trying to minimize the ℓ1 -norm.
Minimax clustering is a representative example of the difficulties which arise in moving from classical correlation clustering to the more general f -Correlation Clustering problem. We will show that some techniques
which work well for the classical correlation clustering problem break down in the minimax context.
Ailon, Charikar, and Newman [2, 3] gave a beautifully simple randomized 3-approximation algorithm
for classical correlation clustering on complete graphs. Their algorithm is shown in Algorithm 3. Since
our rounding clustering in Section 3 is based on the Charikar–Guruswami–Wirth algorithm with a modified
pivoting rule, it is natural to ask whether a similar modification to the Ailon–Charikar–Newman algorithm
also yields a constant-factor approximation algorithm for minimax clustering.
Algorithm 3 Ailon–Charikar–Newman algorithm [2, 3].
Let S = V (G).
while S 6= ∅ do
Pick v ∈ S uniformly at random.
Let T = ({v} ∪ N + (v)) ∩ S.
Output the cluster T .
Let S = S − T .
end while
Unfortunately, it seems that there are severe obstacles to modifying the ACN algorithm in this manner.
For any positive integer t, let Mt be a graph on 2t vertices consisting of t pairwise disjoint edges, and let Gt
be the labeling of K2t in which the edges of Mt are labeled − and all other edges are labeled +.
Clearly, if all vertices of Gt are placed in the same cluster (the “giant clustering”), then there is only 1
error at each vertex of Gt . We show that all other clusterings of Gt have many more errors at some vertex.
Lemma 7. If C is a clustering of Gt with more than 1 cluster, then some vertex of Gt has at least t − 1
errors in C.
Proof. Let X be the smallest cluster in C. Since C has at least 2 clusters, we have |X| ≤ t. For any v ∈ X,
there is at most one w ∈
/ X such that vw is a negative edge. Hence, each v ∈ X has at least t − 1 incident
errors.
By Lemma 7, any constant-factor randomized algorithm for minimax clustering must return the giant
clustering for Gt with probability 1 − O(1/t). On the other hand, if we modify Algorithm 3 by changing
the rule for choosing the pivot vertex v, the resulting algorithm still cannot produce the giant clustering. It
is difficult to see how Algorithm 3 could sensibly be modified in order to return the giant clustering for Gt
with high enough probability.
We now consider the behavior of Algorithm 1 on the graph Gt . While the minimax objective function is
not linear in the variables xuv , we can still model the f -Fractional Correlation Clustering problem using the
linear program L shown in Figure 1.
Since the algorithm presented in Section 3 yields a constant-factor approximation algorithm for minimax
clustering, and since every clustering of Gt other than the giant clustering has t − 1 errors at some vertex,
it is necessary that our rounding algorithm, applied to an optimal solution of L, returns the giant clustering
for all sufficiently large t. This follows immediately from the following result.
Proposition 8. Let L be the linear program shown in Figure 1, as formulated for Gt . If t ≥ 3, then the
unique optimal solution to L has xuv = 0 for all uv ∈ E(G).
Proof. The dual program to L is shown in Figure 2, with the following variables:
P
P
• For each v ∈ V (Gt ), a variable πv corresponding to the constraint w∈N + (v) xvw + w∈N − (v) (1 −
xvw ) ≤ M ,
12

minimize M , subject to:
xuv ≤ xuz + xzv
X

xvw +

w∈N + (v)

X

(for all distinct u, v, z)

(1 − xvw ) ≤ M

(for all v ∈ V (G))

w∈N − (v)

0 ≤ xe ≤ 1

(for all e ∈ E(G))

M ∈R
Figure 1: LP formulation L of f -Fractional Correlation Clustering, where f (y) = maxv∈V (G) yv .
maximize

X

d− (v)πv , subject to:

v∈V (G)

−πu − πv + σ̂u,v ≤ 0

(for all uv ∈ E + (G))

πu + πv + σ̂u,v ≤ 0
X
πv ≤ 1

(for all uv ∈ E − (G))

v

πz , σu,v ≥ 0

(for all z ∈ V (G) and all u, v ∈ E(G)).

Figure 2: Dual of L.
• For each ordered triple (u, v, z) where u, v, z are distinct vertices of V (Gt ), a variable σ(u,v,z) corresponding to the constraint xuv ≤ xuz + xzv .
P
For convenience of notation, we also introduce the abbreviation σ̂u,v to stand for z∈V (G)−{u,v} (−σu,v,z −
σv,u,z + σz,u,v + σz,v,u + σu,z,v + σv,z,u ). Observe that there are exactly 2t − 2 choices of z to sum over.
Now we define a dual solution. Let u′ u′′ be an edge of the negative matching. Consider the dual solution
defined below:
σu′ ,u′′ ,z = 1/(2t − 2) for all z ∈
/ {u′ , u′′ },

πu′ = πu′′ = 1/2,
′

′′

σu,v,z = 0 if (u, v) 6= (u′ , u′′ ).

πv = 0 for all v ∈
/ {u , u },

Clearly this solution has an objective value of 1; we check that it is feasible for t ≥ 2. If uv is an edge
containing neither of {u′ , u′′ }, then πu = πv = 0 and σ̂u,v = 0, since every term of σ̂u,v is 0. The edge u′ u′′
is a negative edge with πu′ = πu′′ = 1/2, and after eliminating all the zero terms, we have
σ̂u′ u′′ =

X

(−σu′ ,u′′ ,z ) = −

X

z∈V (G)−{u,v}

z∈V (G)−{u,v}

1
= −1.
2t − 2

Thus, πu′ + πu′′ + σ̂u′ ,u′′ ≤ 0, as required. Finally, if uv is a positive edge with u ∈ {u′ , u′′ }, say if u = u′ ,
then the only nonzero term of σ̂uv is σu,u′′ ,v , and we have −πu − πv + σ̂u,v = −1/2 + 1/(2t − 2) ≤ 0 as
required. The same argument holds if u = u′′ .
Since this solution has an objective value of 1, matching the primal objective when xuv = 0 everywhere, it
is clearly optimal. Furthermore, if t ≥ 3, then for each positive edge incident to u′ or u′′ , there is slack in the
corresponding constraint of the dual problem. By complementary slackness, this implies that in any optimal
solution to L, we have xu′ v = xu′′ v = 0 for all v ∈ V (G) − {u′ , u′′ }. The triangle inequality constraints in L
then imply that in an optimal primal solution, xuv = 0 for all uv ∈ E(G).

B

MaxAgree for Classical and Minimax Clustering

In this paper, we have mainly focused on studying the MinDisagree formulation of f -Correlation Clustering,
where we seek to minimize an objective function related to the clustering errors in a candidate solution, and
13

where a c-approximation algorithm is an algorithm whose total error weight is at most c times the optimal
weight.
An alternative formulation to MinDisagree is MaxAgree, where we instead seek to maximize some
function related to the edges that are not errors. In classical correlation clustering, this means that we
want to maximize the number of edges which are correct. In minimax clustering, we wish to maximize the
number of correct edges at the vertex with the fewest correct edges. In both cases, an optimal solution to
MinDisagree is also an optimal solution to MaxAgree, but their approximation properties differ.
In the classical case, there is a trivial 2-approximation algorithm for MaxAgree on arbitrary graphs:
we can simply choose the better of clustering with all vertices in separate clusters and the clustering with all
vertices in the same cluster. All negative edges are correct in the first clustering and all positive edges are
correct in the second clustering, so taking the better of the two yields a clustering with at least half the edges
correct, which is clearly at least half the value of an optimal clustering. Less trivially, Bansal, Blum, and
Chawla [5, 6] gave a PTAS for MaxAgree, so that any approximation ratio greater than 1 is achievable.
In contrast, the best approximation ratio known for MinDisagree on arbitrary graphs has a ratio of log n.
It is natural to ask whether some algorithm can also be found to approximate MaxAgree in the minimax
context. The trivial 2-approximation algorithm no longer works, since if G both has vertices of high positive
degree and high negative degree, then each of the “extreme” clusterings will cause a large number of errors at
some vertex. We have not been able to find any constant-factor approximation algorithm for the MaxAgree
formulation of minimax clustering, even with the additional assumption that G is a labeled complete graph.
We now construct a graph which seems to be a good example of the difficulties in designing an algorithm
for this problem. For any n, let Gn be the complete graph on n + 1 vertices, and fix some vertex u∗ ∈ V (Gn ).
All edges incident to u∗ are labeled +, while all other edges are labeled −. Thus, u∗ has positive degree n,
while all other vertices have positive degree 1.
It is clear that only one type of integer clustering could be optimal: cluster u∗ with some number t of
the remaining vertices, and cluster all other vertices as singletons. This yields t correct edges at u∗ , n − t + 1
correct edges at each vertex clustered with u∗ , and n − 1 correct edges at each singleton vertex. Thus, the
optimal clustering has ⌊(n + 1)/2⌋ correct edges at its worst vertex.
The following result demonstrates why algorithms based on LP rounding are likely to have trouble finding
a good clustering of Gn under the MaxAgree objective. We reuse the LP formulation of MinDisagree
shown in Figure 1; this is valid because when we seek an exact solution, minimizing M in Figure 1 is
equivalent to maximizing |V (G)| − 1 − M , the weight of the correct edges at the worst vertex.
Proposition 9. Let L be the linear program shown in Figure 1, as formulated for Gn . If n ≥ 2, then the
unique optimal solution to L has xu∗ v = 1/3 for all v 6= u∗ and xvw = 2/3 for all vw ∈ E(Gn − u∗ ).
Proof. In the proposed solution, we have M = n/3. To show that this solution is optimal and unique, we
construct a solution to the dual program shown in Figure 2, as in the proof of Proposition 8. Consider the
dual solution defined by
n
,
3(n − 1)
1
πv =
for all v =
6 u∗ ,
3(n − 1)

πu∗ = 1 −

σv,w,u∗ =

1
for all vw ∈ E(Gn − u∗ )
3(n − 1)

σv,w,z = 0 if z 6= u∗ .

Since d− (u∗ ) = 0 and d− (v) = n − 1 for all v 6= u∗ , the objective value of this solution is n/3. Thus, if this
solution is feasible, then it is optimal.
To see that this solution is feasible, we observe that for v, w 6= u∗ , we have σ̂v,w = −σv,w,u∗ − σw,v,u∗ =
−(πv + πw ), so that πv + πw + σ̂v,w ≤ 0 for all negative edges vw, as needed. On the other hand, for v 6= u∗
we have
X
(σv,z,u∗ + σz,v,u∗ ) = 2(n − 1)πv .
σ̂u∗ ,v =
z ∈{u
/ ∗ ,v}

Since πu∗ = 1 − nπv , this implies that
−piu∗ − πv + σ̂u∗ ,v = −(1 − nπv ) − πv + 2(n − 1)πv = (n − 1)πv − 1 + 2(n − 1)πv = 0,

14

P
so that −πu∗ − πv + σ̂u∗ ,v ≤ 0 for all positive edges u∗ v, as needed. Since also v πv = 1, we see that the
proposed dual solution is feasible, so the given primal solution is optimal.
Now we argue that the given primal solution is the unique optimal solution. Let x be any optimal primal
solution. For each edge vw ∈ E(Gn − u∗ ), the dual variable σv,w,u∗ is nonzero in the dual solution above, so
by complementary slackness we have xvw = xu∗ v + xu∗ w . Furthermore, since each πv > 0, each v 6= u∗ must
have total error weight equal to M , again by complementary slackness. Therefore, for each v 6= u∗ , we have
X
X
X
(1 − (xu∗ v + xu∗ w ))
M=
xvw +
(1 − xvw ) = xu∗ v +
w∈N + (v)

∗}
w ∈{v,u
/

w∈N − (v)

= (n − 1) − (n − 3)xu∗ v −

X

xu∗ w .

w6=u∗

This implies that xu∗ v = xu∗ w for all v 6= w. Letting p denote this common value, we have M = (n − 1) −
(n − 3)p − np = (n − 1) − (2n − 3)p. On the other hand, since πu∗ > 0, we also have
X
xu∗ w = np.
M=
w∈N + (u∗ )

Thus, (n − 1) − (2n − 3)p = np, which implies that p = 1/3. Hence, in any optimal solution we have
xu∗ v = 1/3 for all v 6= u∗ and xvw = 2/3 for all vw ∈ E(Gn − u∗ ), as desired.
Thus, the only optimal solution to the natural LP rounding is highly symmetric, but the natural symmetric clusterings of Gn – into either all singletons or into one giant cluster – both have at most 1 correct
edge at the worst vertex, which is far short of the optimum value of ⌊n/2⌋ correct edges. We note that this
does not pose a problem for the MinDisagree formulation: in a c-approximation for MinDisagree, we
only promise that the generated clustering has at most c⌈n/2⌉ errors at its worst vertex, and if c > 2, then
any clustering at all meets this guarantee.

C

NP-Completeness of Minimax Clustering on Complete Graphs

To show that minimax clustering is NP-hard on complete graphs, we use a reduction from the Partitioninto-Triangles problem, originally stated in [15] and attributed to Schaefer.
Partition into Triangles
Input: A graph G with |V (G)| = 3q for some integer q.
Question: Is there a partition of V (G) into q sets V1 , . . . , Vq such that each set Vi induces a
triangle in G?
Specifically, we reduce from the 4-regular case:
Theorem 10 (van Rooij, van Kooten Niekerk, Bodlaender [23]). Partition into Triangles on 4-regular graphs
is NP-complete.
(Although this is not explicitly stated in [23], it follows immediately from two of their results: that
the problem is NP-hard on graphs of maximum degree at most 4, and that every partition-into-triangles
instance with maximum degree at most 4 can be transformed in polynomial time into an equivalent 4-regular
instance.)
To prove that minimax clustering is NP-hard, we use the following reformulation, which is more convenient
for our purposes.
t-Perfect Clustering
Input: A labeled complete graph G together with a tolerance tv ∈ Z+ for each v ∈ V (G).
Question: Does G admit a t-perfect clustering, that is, a clustering such that each vertex v has
at most tv incident mistakes?

15

Taking λv = 1/tv , we see that G has a t-perfect clustering if and only if the minimax-clustering value of the
resulting weighted graph is at most 1.
Our NP-completeness proof mimics the proof given by Bansal, Blum, and Chawla for the classical correlation clustering problem. Let G be a 4-regular graph on n vertices, where n ≥ 7, and let G′ be the labeled
complete graph on the same vertex set whose positive edges are exactly the edges of G. Observe that G has
a partition into triangles if and only if G′ has a clustering with all clusters of size at most 3 and exactly 2
mistakes at each vertex. The idea is to expand G′ into a larger labeled complete graph H such that in an
optimal clustering of H, every cluster has at most three G′ -vertices.
We use essentially the same construction as Bansal–Blum–Chawla. Let H consist of G′ , augmented as
follows. For every 3-set {u, v, w} ⊆ V (G′ ), add to H a clique Cuvw with 7 vertices. All edges within Cuvw
are positive, all edges from Cuvw to the vertices {u, v, w} are positive, and all other edges incident to Cuvw
are negative.

We assign the following tolerances: each original vertex u ∈ G′ has tu = 7( n−1
− 1) + 2, and each added
2
vertex v ∈ H − G′ has tv = 3.
Lemma 11. If H has a t-perfect clustering C, then every cluster of C contains at most three vertices of G′ ,
and every cluster of C contains vertices from at most exactly one clique of H − G′ .
Proof. First suppose that C has a cluster X containing vertices from two different cliques of H − G′ . Let
v1 , v2 belong to the cliques C1 , C2 respectively. If |X ∩ C1 | > 3, then v2 has more than 3 incident mistakes,
which exceeds its tolerance. On the other hand, if |X ∩ C1 | ≤ 3, then since |C1 | = 7, we have |C1 − X| ≥ 4,
so v1 has at least 4 incident mistakes, which again exceeds its tolerance. Thus, if C is t-perfect, then every
cluster contains vertices from at most one clique.
′
Now suppose that C has a cluster X that does not contain vertices from
 any clique of H − G . ′ Since
n−1
′
clusters are nonempty, X contains a vertex v ∈ V (G ). Since v has 7 2 neighbors in V (H − G ) and

is not clustered with any of them, v has at least 7 n−1
incident mistakes, which exceeds its tolerance of
2

7 n−1
−
5.
2
Finally, suppose that C has some cluster X with at least four G′ -vertices. Since X contains vertices from
at most one clique of H − G′ , there is some vertex
v ∈ V (G′ ) ∩ X does not have any positive neighbors in

n−1
′
X ∩ V (H − G ). Since v has a total of 7 2 positive neighbors in H − G′ , it again follows that v has at

least 7 n−1
incident mistakes, exceeding its tolerance.
2
Corollary 12. H has a t-perfect clustering if and only if G has a partition into triangles.

Proof. First suppose that V1 , . . . , Vk is a partition of G into triangles. Cluster H as follows: for i ∈ [k], let
Xi = Vi ∪ CVi , where CVi is the clque of H with vertex set Vi . For every clique C that is not equal to some
Vi , cluster C on its own.


Each v ∈ V (G′ ) has exactly 7( n−1
− 1) + 2 mistakes: among the 7 n−1
postive edges to vertices of
2
2
H − G′ , it is clustered with exactly 7 of them, and among its 4 positive neighbors in G, it is clustered
with exactly 2 of them (and with no negative neighbors), since V1 , . . . , Vk is a partition of G into triangles.
Furthermore, each v ∈ V (H − G′ ) has at most 3 mistakes, since this clustering has no mistakes within H − G′
and does not cluster any w ∈ V (Cxyz ) with a vertex outside of {x, y, z}. Thus, the clustering is t-perfect.
Now suppose that H has a t-perfect clustering C. By Lemma 11, every cluster of C contains at most three
vertices of G and contains vertices from exactly one cluster Cuvw of V (H − G′ ). We claim that the restriction
of C to V (G′ ) is a partition of G into triangles. If not, some vertex v ∈ V (G′ ) is clustered with fewer than
2 of its positive neighbors, and therefore has at least 3 incident mistakes in G′ . Since the cluster containing

v contains vertices from only one of the cliques containing v, we see that v also has at least 7( n−1
− 1)
2

incident mistakes to vertices of V (H ′ − G), for at total of at least 7( n−1
−
1)
+
3
incident
mistakes.
This
2
exceeds its tolerance, contradicting the hypothesis that C is t-perfect.

D

NP-Completeness on Complete Bipartite Graphs

In this section, we show that “one-sided” minimax clustering on complete bipartite graphs is NP-hard. This
complements the approximation algorithm given in Section 4 for the same problem. Our proof is similar

16

to the proof of Amit [4] which shows that biclustering with the classical objective function is NP-hard, but
requires significant modifications to accomodate the new objective function. The proof uses a reduction from
the 3-cover problem, which is well-known to be NP-complete [15].
3-Cover
Input: A ground set U = {u1 , . . . , u3n } and a family of subsets S = {S1 , . . . , Sp } with each
|Si | = 3.
Question: Is there a subfamily S ′ ⊆ S such that each ui lies in exactly one element of S ′ ?
Given an instance of 3-cover, we construct an instance of the following problem:
One-Sided t-perfect Biclustering
Input: A labeled complete bipartite graph G with partite sets V1 , V2 and a tolerance tv ∈ Z+
for each v ∈ V1 .
Question: Does G have a clustering such that each vertex v ∈ V1 has at most tv incident edges
that are errors?
By the same argument used in Appendix C, any algorithm which exactly determines the optimal one-sided
minimax clustering for complete bipartite graphs would also solve the t-perfect biclustering problem. Hence,
it suffices to show that t-perfect biclustering is NP-hard. Note also that one-sided minimax clustering can
be viewed as the special case of (two-sided) minimax clustering for which tv = |V1 | for all v ∈ V2 ; thus, the
reduction in this section also shows that the two-sided version of the problem is NP-hard.
Given a nontrivial instance of 3-cover (that is, an instance with n, p ≥ 1), we construct an instance of
t-perfect biclustering as follows. For each ui ∈ U , construct a pair of vertices xi ∈ V1 , yi ∈ V2 . Call these
vertices ground vertices. Each edge xi yj is positive if ui = uj or if ui and uj lie in some common triplet of
S, and negative otherwise.
For each Si ∈ S, we create a vertex x(Si ) ∈ V1 and m vertices y1 (Si ), . . . , ym (Si ) ∈ V2 , where each
xj (Si ) ∈ V1 and yj (Si ) ∈ V2 , where m ≥ 6n + 3p is some fixed constant. Call these vertices triplet vertices,
and let Bi = {x(Si )} ∪ {yj (Si ) : j ∈ {1, . . . , m}}. All edges x(Si )yk (Si ) for a fixed i are positive, and all
edges x(Si )yk (Sℓ ) for i 6= ℓ are negative. For ui ∈ U , if ui ∈ Sj , then the edges xi yk (Sj ) and yi x(Sj ) are
positive, and otherwise these edges are negative.
Finally, let Z = {z1 , . . . , z3n } be new V2 -vertices, and for each zi ∈ Z, add positive edges to all groundvertices in V1 and negative edges to all triplet-vertices in V1 . Call these vertices dummy vertices.
Next we determine the tolerances tv . For Si ∈ S, let tx(Si ) = 3. For ui ∈ U , the corresponding tolerances
are computed more intricately. Let d(ui ) be the number of triplets Sj ∈ S containing ui and let c(ui ) be the
number of uj ∈ U − {ui } such that uj and ui lie in some common triplet Sj . We define
txi = m(d(ui ) − 1) + (c(ui ) − 2) + (|Z| − 3).
It is clear that G and t can be constructed in polynomial time.
Lemma 13. Suppose that G has a t-perfect clustering C. For any Si , Sj ∈ S with i 6= j, the vertices x(Si )
and x(Sj ) lie in different clusters.
Proof. Suppose that x(Si ) and x(Sj ) lie in the same cluster X. Since tx(Si ) = 3, we see that X contains at
least m − 3 vertices from y1 (Si ), . . . , ym (Si ). Since x(Sj ) has negative edges to all these vertices, it follows
that x(Sj ) has at least m − 3 incident errors. Since m − 3 > 3 = tx(Sj ) , this contradicts the fact that C is
t-perfect.
Lemma 14. Suppose that G has a t-perfect clustering C. For any uj ∈ U , there is a unique Si ∈ S such
that xj is clustered with x(Si ). Furthermore, this Si has the following properties:
1. uj ∈ Si , and
2. xj is clustered with each vertex yℓ such that uℓ ∈ Si .

17

Proof. First we prove the existence of a unique Si such that xj is clustered with x(Si ), then we show that
Si has the desired properties.
If yk (Si ) is a triplet V2 -vertex not clustered with x(Si ), call yk (Si ) a rogue vertex. It is immediate from
the definition of t that in a t-perfect clustering, each Bi contains at most 3 rogue vertices.
To prove that xj is clustered with some x(Si ), it suffices to show that xj is clustered with some triplet
V2 -vertex that is not a rogue vertex. Since each Bi contains at most 3 rogue vertices, there are at most 3p
rogue vertices in total, where p = |S|. If all triplet vertices clustered with xj are rogue vertices, then since
xj has md(uj ) positive edges to triplet vertices, it follows that xj has at least md(uj ) − 3p incident errors.
Now we have
txj = m(d(uj ) − 1) + (c(uj ) − 2) + (|Z| − 3) < md(uj ) − m + 6n ≤ md(uj ) − 3p,
where the last inequality follows from m ≥ 6n + 3p. Thus, there are more than txj errors at xj , contradicting the assumption that C is t-perfect. Thus, xj is clustered with some x(Si ). Uniqueness of Si follows
immediately from Lemma 13.
To see that uj ∈ Si , suppose that uj ∈
/ Si . Then xj is clustered with at most 3 triplet-vertices that are
its positive neighbors, and therefore has at least md(uj ) − 3 incident errors. Since md(uj ) − 3 > txj , this
contradicts the assumption that C is t-perfect.
Next we prove (2). Let B = N + (xj ) − N + (x(Si )). Since tx(Si ) = 3, the cluster containing xj contains at
most 3 vertices from B. Thus, there are at least |B| − 3 errors from x to the vertices of B, where
|B| − 3 = |Z| + m(d(uj ) − 1) + (c(uj ) − 2) − 3 = txj .
Thus, for C to be t-perfect, it is necessary that all errors incident to xj are edges from x to B. In particular, xj
is clustered with all vertices in N + (xj ) ∩ N + (x(Si )), so that xj is clustered with all yℓ such that yℓ ∈ Si .
Corollary 15. G has a t-perfect clustering if and only if S ′ has a 3-cover.
Proof. Given any t-perfect clustering, let S ′ be the family of triplets Si such that some vertex of Bi is
clustered with some V1 -ground-vertex xj . Lemma 14 immediately implies that these triplets cover all of u.
Furthemore, Lemma 14 implies that these triplets are pairwise disjoint: if S1′ and S2′ are triplets of S ′ that
both contain uj , then Lemma 14 would force each x(S1′ ) and x(S2′ ) to both be clustered with yj and hence
to be clustered together, which contradicts Lemma 13. Hence, S ′ is a 3-cover.
Conversely, let S ′ be a 3-cover in S. We define a clustering of G. Since S ′ is a 3-cover, we have |S ′ | = n.
Let ZS1′ , . . . , ZSn′ be a partition of Z into n disjoint sets of size 3, indexed by the sets of S ′ . Now for each
Si ∈ S, define a cluster Xi by
(
Bi ∪ {xj , yj : uj ∈ Si } ∪ ZSi , if Si ∈ S ′ ,
Xi =
Bi ,
otherwise.
Since S ′ is a 3-cover, the clusters Xi are pairwise disjoint and cover the vertices of G. We claim that this
clustering is t-perfect. If x(Si ) is a triplet vertex corresponding to some Si ∈
/ S ′ , then x(Si ) has exactly 3
incident errors, namely its edges to the ground-vertices yj with uj ∈ Si . On the other hand, if x(Si ) is a
triplet vertex corresponding to some Si ∈ S ′ , then x(Si ) again has exactly 3 incident errors, namely its edges
to the dummy-vertices in ZSi .
If xj (or yj ) is a ground vertex, then xj has m(d(uj ) − 1) incident errors which are positive edges to
triplet-vertices, c(uj ) − 2 incident errors which are positive edges to ground-vertices, and |Z| − 3 incident
errors which are positive edges to dummy-vertices. This is a total of exactly txj incident errors. Hence the
clustering is t-perfect.

E

Technical Details

Lemma 16. Suppose a Type 2 cluster {u}∪T has just been output in Algorithm 1. For any z ∈ S −({u}∪T ),
the total cluster-cost of the cross-edges for z is at most max{1/(1 − 2α), 2/α} times the total LP-cost of the
cross-edges for z.
18

Proof. This is essentially the same proof given by Charikar, Guruswami, and Wirth [9, 10]; we repeat it here
to keep the paper self-contained. If xuz ≥ 1 − α, then for each w ∈ {u} ∪ T , we have
xwz ≥ xuz − xuw ≥ 1 − 2α.
If there are p positive cross-edges, this implies that the total LP-cost of the cross-edges for z is at least
(1 − 2α)p. Since the total cluster-cost of the cross-edges for z is p, the claim holds.
Now consider xuz ∈ (α, 1 − α). Let P = N + (z) ∩ ({u} ∪ T ) and let Q = N − (z) ∩ ({u} ∪ T ); the total
cluster-cost of the cross-edges for z is just |P |. We have the following lower bound on the total LP-cost of
the cross-edges for z:
X
X
X
X
xwz +
(1 − xwz ) ≥
(xuz − xuw ) +
(1 − xuz − xuw )
w∈P

w∈N

w∈P

w∈Q

= |P | xuz + |Q| (1 − xuz ) −

X

xuw

w∈{u}∪T

≥ |P | xuz + |Q| (1 − xuz ) −

α(|P | + |Q|)
,
2

P
|
. This lower bound is linear in xuz , so
where in the last line we used the inequality w∈{u}∪T xuw ≤ α|{u}∪T
2
we study its behavior at the endpoints of (α, 1 − α). When xuz = α, the lower bound rearranges as follows:
α |P | + (1 − α) |Q| −

α(|P | + |Q|)
α
3α
α
= |P | + (1 −
) |Q| ≥ |P | .
2
2
2
2

When xuz = 1 − α, the lower bound rearranges as follows:
(1 − α) |P | + α |Q| −

3α
α
α
α(|P | + |Q|)
= (1 −
) |P | + |Q| ≥ |P | .
2
2
2
2

α
In both cases, we used the assumption α < 1/2, which implies 1 − 3α
2 ≥ 2 . It follows that charging
the LP-cost of each cross-edge yields enough charge to pay for the cluster-cost of all cross-edges.

2
α

times

Lemma 17. Suppose that a Type 2 cluster C has just been output in Algorithm 2. For any vertex z ∈ V1 −C,
the total cluster-cost of the cross-edges for z is at most max{1/(1 − 2α), 2/α} times the total LP-cost of the
cross-edges for z.
Proof. We essentially repeat the proof of Lemma 16. If xuz ≥ 1 − α, then for each w ∈ {u} ∪ T , we have
xwz ≥ xuz − xuw ≥ 1 − 2α.
If there are p positive cross-edges, this implies that the total LP-cost of the cross-edges for z is at least
(1 − 2α)p. Since the total cluster-cost of the cross-edges for z is p, the claim holds.
Now consider xuz ∈ (α, 1 − α). Let P = N + (z) ∩ ({u} ∪ T ) and let Q = N − (z) ∩ ({u} ∪ T ); the total
cluster-cost of the cross-edges for z is just |P |. Note that P ∪ Q = V2 ∩ T . We have the following lower
bound on the total LP-cost of the cross-edges for z:
X
X
X
X
xwz +
(1 − xwz ) ≥
(xuz − xuw ) +
(1 − xuz − xuw )
w∈P

w∈N

w∈P

w∈Q

= |P | xuz + |Q| (1 − xuz ) −

X

xuw

w∈V2 ∩T

≥ |P | xuz + |Q| (1 − xuz ) −

α
(|P | + |Q|),
2

P
where in the last line we used the inequality w∈V2 ∩T xuw ≤ α2 |{u} ∪ T |. This lower bound is linear in
xuz , so we study its behavior at the endpoints of (α, 1 − α). When xuz = α, the lower bound rearranges as
follows:
α
3α
α
α
) |Q| ≥ |P | .
α |P | + (1 − α) |Q| − (|P | + |Q|) = |P | + (1 −
2
2
2
2
19

When xuz = 1 − α, the lower bound rearranges as follows:
(1 − α) |P | + α |Q| −

α
α
α
α
(|P | + |Q|) ≥ (1 − α − ) |P | + |Q| ≥ |P | .
2
2
2
2

In both cases, we used the assumption α < 1/2. It follows that when xuz ∈ (α, 1 − α), charging 1/(α − β)
times the LP-cost of each cross-edge yields enough charge to pay for the cluster-cost of all cross-edges.

20

