°éÕ«ÃÈkúeO¯é¹¿êó°Clustering based on Graph Cuts∗ÝéóÉ äó Ä©¤¯Þó AÊ
Jan Poland and Thomas ZeugmannwS'f'fbÅ1ÑfvÑGraduate School of Information Science and Technology, Hokkaido University
Abstract: Clustering algorithms based on a matrix of pairwise similarities (kernel matrix)
for the data are widely known and used, a particularly popular class being spectral clustering
algorithms. Here we propose a clustering algorithm based on the SDP relaxation of the maxk-cut of the graph of pairwise distances. We compare the algorithm with a spectral relaxationof a norm-k-cut. Moreover, we propose a simple heuristic for dealing with missing data.

1

Introduction

Consider a set of n objects or data points,
x1 , . . . , xn . We might not know anything about theobjects, but assume that their pairwise distances
dij = d(xi , xj ) are known. Here, d : M × M → R isa distance measure over a set M , i.e., d(x, y) ≥ 0,d(x, y) = d(y, x) for all x, y ∈ M , and d(x, y) = 0
iff x = y. Then we can cluster the data, i.e., assign the xi to k distinct groups such that the distances within groups are small and the distances
between the groups are large. This is done as follows. Construct a graph from the pairwise distancesand choose an algorithm from the large class of recently published methods based on graph-theoretic
cut criteria. As the cuts are usually N P-hard to
optimize, appropriate relaxations have been subject to intensive research. Two types of relaxations
are particularly important:(1) Spectral methods, where the top eigenvectorsof the graph’s adjacency matrix are used to project
the data into a lower dimensional space. This gives
rise to new theoretical investigations of the popular
spectral clustering algorithms.
(2) Semi-definite programming (SDP), where thediscrete constraints of the cut criterion are replacedby continuous counterparts. Then convex solvers
can be used for the optimization.
Surprisingly, all of the clustering approaches sug∗ Support by JSPS 21st century COE program C01 andthe MEXT Grand-in-Aid for Scientific Research on Priority
Areas under Grant No. 18049001 is gratefully acknowledged.
: 060-0814
14
9
E-mail: {jan,thomas}@ist.hokudai.ac.jp#aH -L: a îgested so far work on a graph of similarities rather
than distances. This means that, given the distances, we need one additional step to obtain similarities from distances, e.g., by applying a Gaussian
kernel. This also involves tuning the kernel width,a quantity which the clustering algorithm is quitesensitive to. Hence, it is natural to avoid this stepby using a cut criterion that directly works withthe distance graph, e.g., max-cut. We follow Frieze
and Jerrum [4] and solve the max-cut problem via
an SDP relaxation. We compare this method witha representative of spectral clustering algorithms,
namely the spectral relaxation of the normalized
cut criterion [12].
As a second contribution of this paper, we propose a simple heuristic for dealing with missing
data, i.e., the case where some of the pairwise distances dij are unknown. Then, our aim is to substitute the missing dij by a value which is most likely
to leave the values of the cuts intact. This turns
out to be the mean of the observed dij .
One motivation for considering missing data isgiven by the application we shall use to test thealgorithms: Clustering of natural language terms
using the Google distance. The Google distance[2] is a means of computing the pairwise distanceof any searchable terms by just using the relative frequency count resulting from a web search.
The Google API provides a convenient way for automating this process, however with a single key(which is obtained by prior registration) the maximum amount of daily queries is currently limited to1000. Hence, by querying an incomplete sparse dis-tance matrix rather than a full one, one can speed
up considerably the overall process, as we will see.
The paper is structured as follows. In Section 2,
we introduce the algorithm based on the max-k-cut
relaxation, and recall some theory. We then briefly
review the algorithm based on norm-k-cut in Section 3. In Section 4 we address the missing data
problem. Section 5 confronts the two algorithms,
looking on the exact cut criteria rather than therelaxations, and compares the computational resources required. In Section 6 we present experimental results with the Google distance. Relation
to other work is discussed and conclusions are given
in Section 7.

2

Max-k-cut

Given a fully connected, weighted graph G= (V, D)
with vertices V = {x1 , . . . , xn } and edge weights
D = {dij ≥ 0 | 1 ≤ i, j ≤ n} which express pairwise
distances, a k-way-cut is a partition of V into kdisjoint subsets S1 , . . . , Sk . Here k is assumed to begiven. We define the predicate A(i, j) = 0 if xi andxj happen to be in the same subset, i.e., if ∃`[1 ≤` ≤ k, 1 ≤ i, j ≤ n and i, j ∈ S` ], and A(i, j) = 1,otherwise. The weight of the cut (S1 , . . . , Sk ) isdefined asnX
dij A(i, j) .
i,j=1

The max-k-cut problem is the task of finding thepartition that maximizes the weight of the cut. It
can be stated as follows: Let a1 , . . . , ak ∈ S k−2 bethe vertices of a regular simplex, where
S d = {x ∈ Rd+1 | kxk2 = 1}
is the d-dimensional unit sphere. Then the inner1
product ai · aj = − k−1
whenever i 6= j. Hence,finding the max-k-cut is equivalent to solving thefollowing integer program:
X
IP : maximize k−1
dij (1 − yi · yj )ki<jsubject to yj ∈ {a1 , . . . , ak } for all 1 ≤ j ≤ n.
Frieze and Jerrum [4] propose the following semidefinite program (SDP) in order to relax the integer
program:Xdij (1 − vi · vj )SDP : maximize k−1
ki<jsubject to vj ∈ S n−1 for all 1 ≤ j ≤ n and1
for all i 6= jvi · vj ≥ − k−1(necessary if k ≥ 3).

1
The constraints vi · vj ≥ − k−1
are necessary fork ≥ 3 because otherwise the SDP would prefer solutions where vi ·vj = −1, resulting in a larger valueof the objective. We shall see in the experimental
part that this indeed would result in invalid approximations. The SDP finally can be reformulated asa convex program:
X
CP : minimize
dij Yij(1a)i<jsubject to Yjj = 1 for all 1 ≤ j ≤ n,(1b)

1
for all i 6= j (if k ≥ 3) andYij ≥ − k−1(1c)

Y = (Yij )1≤i,j≤n satisfies Y º 0.

(1d)Here, for the matrix Y ∈ Rn×n the last condition
Y º 0 means that Y is positive semidefinite. Efficient solvers are available for this kind of optimization problems, such as CSDP [1] or SeDuMi [10].
1
In order to implement the constraints Yij ≥ − k−1
with these solvers, positive slack variables Zij haveto be introduced together with the equality con1
straints Yij − Zij = − k−1.
Finally, for obtaining the partitioning from thevectors vj or the matrix Y , Frieze and Jerrum [4]propose to sample k points z1 , . . . , zk randomly on
S n−1 , representing the groups, and assign each vj to
the closest group, i.e., the closest zj . They show approximation guarantees generalizing those of Goemans and Williamson [5]. In practice however, theapproximation guarantee does not necessarily imply a good clustering, and applying the k-means
algorithm for clustering the vj gives better results
here. We use the kernel k-means (probably introduced for the first time by [9]) which directly works
on the scalar products Yij = vi · vj , without needof recovering the vj . We recapitulate the complete
algorithm:
Algorithm. Clustering as an SDP relaxation ofmax-k-cut
Input: Distance matrix D = (dij ) .
1. Solve the SDP via the CP (1a) through (1d).
2. Cluster the resulting matrix Y using kernel kmeans.

3

Normalized k-cut

The normalized cut criterion has emerged as one of
the most widely accepted cut criteria for clustering.
It is defined on a graph G = (V, W ) of pairwise similarities rather than distances: W = {wij | wij ∈[0, 1], 1 ≤ i, j ≤ n}. Here, we identify the edgesof G with their weights given by the similarities.
For a k-way-cut, i.e., a partition of V into k disjoint subsets S1 , . . . , Sk , the norm-k-cut criterion isdefined as (cf. Yu and Shi [12])k P
k P
1 X i∈S` ,j ∈S
1 X i∈S` ,j∈S` wij/ ` wijP
P=1−kki∈S` ,j∈V wiji∈S` ,j∈V wij
`=1

`=1

=: 1 − knassoc(S1 , . . . , Sk ), (2)where knassoc(S1 , . . . , Sk ) is called the k-way normalized associations criterion. Therefore, minimizing the norm-k-cut value is equivalent to maximizing the norm-knassoc value.
Optimizing (2) can be restated as solving an integer problem, which is shown to be N P-hard. Yu
and Shi [12] therefore derive a spectral relaxation,
which we shall use in the following (see also [8]).
We briefly point to the fact that the EM procedure used in this spectral relaxation algorithm isdifferent from, but nevertheless closely related to
the k-means algorithm used in the algorithm basedon max-k-cut and many other spectral clustering
algorithms. For details, please see [12].

4Missing data

Assume that either the distance matrix D or thesimilarity matrix W is not fully specified, but a
portion of the off-diagonal entries is missing. One
motivation for considering this case could be thedesire to save resources by computing only partof the entries (e.g., for the Google distance discussed below, normal user registration permits only
a limited amount of queries a day). Suppose thatM = (Mij )1≤i,j≤n ∈ {0, 1}n×n is a matrix suchthat Mii = 0 for all i = 1, . . . , n and Mij = 1 if andonly if dij (or wij , respectively) is not missing. Assume that the diagonal of D is zero and that of W
is one, and denote the ith column of a matrix X
by X[i]. Define the mean of the observed values,nX
1
D[i]T M [i]i,j Mij i=1

D̄ = PornX
1
W [i]T M [i].
M
ij
i,j
i=1

W̄ = P

Then, replacing the missing entries in D with thevalue D̄, the resulting distance matrix D is an unbiased estimate for the original full matrix, if thepositions of the missing values are sampled from a
uniform distribution. Hence, the resulting max-kcut criterion for each partition is an unbiased estimate for the criterion respective to the original
matrix, and this is the best we can do to achieve
our goal that the optimal k-way-cuts of the original
and the completed matrix are the same.

Also in the case of a similarity matrix W , themissing values should be replaced by the mean of
the observed values. Asymptotically for n → ∞,this also yields an unbiased estimate for the normk-cut criterion. However, the reasoning is moredifficult here, since the norm-k-cut criterion is asum of quotients, and for two random variables X
and Y , we have E[X/Y ] 6= E[X]/E[Y ]. Still, theactual values of numerator and denominator areclose to their expectations, as one can verify using concentration inequalities, e.g., Hoeffding’s inequality. Then, for large n, with high probability
the quotient is close to the corresponding quantity
for the original (full) similarity matrix.

5

Max-k-cut versus norm-k-cut

In this section, we compare the max-cut and normcut criteria on distance and similarity matrices thatare small enough to allow for a brute-force computation of the exact criteria. We start from 10 × 10
matrices D0 and W0 consisting of two blocks of eachsize 5,0B
B
B
B
D 0 =B
B
B
B
B
@
0
B
B
B
B
W0 =B
B
B
B
B
@

0
.
.
.
0
1
.
.
.
1

···
..
.
···
···
..
.
···

0
.
.
.
0
1
.
.
.
1

1
.
.
.
1
0
.
.
.
0

···
..
.
···
···
..
.
···

1
.
.
.
1
0
.
.
.
0

1
.
.
.
1
0
.
.
.
0

···
..
.
···
···
..
.
···

1
.
.
.
1
0
.
.
.
0

0
.
.
.
0
1
.
.
.
1

···
..
.
···
···
..
.
···

0
.
.
.
0
1
.
.
.
1

1
C
C
C
C
C
C
C
C
C
A

and

1
C
C
C
C
C
C.
C
C
C
A

From these matrices, distance matrices D andsimilarity matrices W are obtained by (1) perturbing the value by Gaussian noise of varying amplitude, (2) making the matrices symmetric andrescaling them to the interval [0, 1], (3) removing
a fraction of the off-diagonal values and replacing
them by the mean of the remaining values. Anothermatrix we use for the norm-cut criterion is a kernel
matrix obtained from the distance matrix using a
Gaussian kernel, W D = exp(− 2σ1 2 D2 ) (all operations are meant in the pointwise sense here). Since
the values of the distance matrix are normalized to[0, 1], we use a fixed σ = 13 . The missing valuesof W D are replaced by the mean of the observed
values in W D .
All values displayed in Figures 1 through 3 below
are means of 1500 independent samples. Figure 1
shows that, when using the max-cut criterion, the

0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
missingvalues fraction

1
0.5

0.2
0 0

noise
amplitudedifference fract. of incorr. clust.

1
0.8
0.6
0.4
0.2
0
0.8

1
0.5

0.2
0 0

0.5

0

−0.5
0.8
0.6
0.4
missingvalues fraction

1
0.5
0.2
0 0

Figure 1: Average fraction of incorrect clusterings by max-k-cut on a noisy distance matrix
with missing data.

0.6
0.4
missingvalues fraction

difference fract. of incorr. clust.

fractions of incorrect clusterings

1

noise
amplitude

Figure 2: Difference of the average fraction ofincorrect clusterings by norm-k-cut relative tomax-k-cut, where the similarity matrix W D
was obtained from the distance matrix D as
W D = exp(− 2σ1 2 D2 ).

relative number of experiments that result in a different clustering than the originally intended one,
grows if either the noise amplitude or the fractionof missing values increases. Of course this was expected. The max-cut criterion even yields always
the correct clustering if both noise amplitude andmissing data fraction are sufficiently low.
The same holds in principle for the norm-cut criterion, both for the directly generated similarity
matrices W and for those matrices W D derived
from the distance matrix by means of the Gaussian kernel. However, in Figure 2, where the average difference of the error rates of the norm-cut
clustering of W D to the max-cut clustering of D
is displayed, we can see: The norm-cut clustering

noise
amplitude

Figure 3: Average fraction of incorrect clusterings by norm-k-cut: Difference of a W D =exp(− 2σ1 2 D2 ) matrix to a directly generated
similarity matrix W .

always produces a higher error rate. The error rateis even more significantly higher for large fractionsof missing values.
Did we introduce this increased error artificiallyby the additional transformation with the Gaussian
kernel? Figure 3 indicates that this is not the case,as it shows nowhere a significantly positive value.
Precisely, Figure 3 displays the difference of the error rates of the norm-cut clusterings of W D relative
to the directly generated matrices W .
Next, we turn to the computational resources required by the algorithms. Both max-cut and normcut are N P-hard to optimize, so let us look at therelaxations. The spectral decomposition of a n × nmatrix can be done in time O(n3 ), and if only the
top k eigenvectors are desired, the effort can beeven reduced to O(kn2 ) by an appropriate Lanczos method. Therefore the norm-cut/spectral algorithm has quadratic or (depending on the implementation) at most cubic complexity.
On the other hand, solving the SDP in order toapproximate max-cut is more expensive. The respective complexity is O(n3 +m3 ) (see [1]), where mis the number of constraints. If k = 2, then m = n
and the overall complexity is cubic. However, fork ≥ 3, we need m = O(n2 ) constraints, resulting inan overall computational complexity of O(n6 ).
Finally, note that the analysis of the eigenvaluesof the similarity matrix can yield a quite useful criterion to automatically determine the number k ofclusters, in case that k is not known. We do notknow of a corresponding method based on the distance matrix. We shall not further discuss this issue
here and assume in the following that k is known.

Experimental results with theGoogle distance

We evaluate both clustering algorithms from Sections 2 and 3 on a set of natural language terms
clustering tasks [2, 8]. We used the following
datasets, which are all available at
http://www-alg.ist.hokudai.ac.jp/datasets.html .
The dataset people2 contains the names of 25
famous classical composers and 25 artists (i.e., twointended clusters), people3 contains all names frompeople2 plus 25 bestseller authors, people4 is extended by 25 mathematicians, and people5 additionally contains 25 classical composers. The
dataset alt-ds contains not terms in natural language, but rather titles and authors’ last names
from (almost all of) the papers from the ALT
2004 and DS 2004 conferences. Furthermore weuse the datasets math-med-fin containing 20 terms
each from the mathematical, medical, and financial terminology, finance-cs-j contains 20 financial and 10 computer science terms in Japanese,
phil-avi-d has 98 terms from philately and 100
terms from aviation in German, and math-cuisine
has 254 mathematical and 346 cuisine-related terms(in English). The distance matrices of the last two
data sets are not fully given: in phil-avi only
50% of the entries are known, in math-cuisine itis only 30%.
For the norm-cut based algorithm, we need toconvert the distance matrix to a similarity matrix. We do this by using a Gaussian kernel
W D = exp(− 2σ1 2 D2 ) and set the width parame√
ter σ = D̄/ 2, which gives good results in practice. Another almost equally good choice is σ = 13 ,which can be justified by the fact that the Google
distance is scale invariant and mostly in [0, 1].
Table 1 shows the number of clustering errors,i.e., the number of data points that are sorted to adifferent group than the intended one, respectively,on the data sets just described. One can see thatboth algorithms perform well in principle, in factmany of the “errors” displayed are in reality ambiguities of the data, e.g., the only misclusteringin the math-med-fin data set concerns the term
“average” which was intended to belong to themathematical terms but ended up in the financialgroup.
We remark that the constraints (1c) and the resulting huge SDP size were really necessary in order to get reasonable results: Without these constraints, e.g., clustering the people5 data set with
the SDP algorithm, the resulting average numberof errors is 36.

average clustering errors

6

20
15
10
5
0
2

0.75
3
#clusters

0.5

4
5

0.25
missing data

Figure 4: Comparison of the max-cut/SDP(dark bars) and the norm-cut/spectral algorithm (light bars) with variable fraction of
missing data and variable number of clusters and data set size, on the data sets
people2-people5.

Looking on the computation times in Table 1(measured on a 3 Ghz Pentium IV), the spectral
method is clearly much faster than the SDP, inparticular for k = 3 or more clusters. Here thequadratic number of constraints in the SDP and
the resulting 6th order computation time are really expensive. Actually, the available SDP software (CSDP, SeDuMi) do not even work at all withmuch larger problems if k ≥ 3.
Next we consider a situation with varying fraction of missing data, shown in Figure 4 forthe data sets people2-people5. Here the maxcut/SDP algorithm consistently outperforms thenorm-cut/spectral algorithm, in particular if thenumber of clusters or the fraction of missing data
grows. The same can be observed for other data
sets. Both algorithms work quite well until about
70% missing data, after that the error increases
sharply. The figure is based on 20 independent samples of missing data each, where the missing data
locations were sampled in a balanced way such thateach row and column of the distance matrix has thesame fraction of missing values.

7

Relations to other work andConclusions

There are many papers on clustering based on similarity matrices, in particular spectral clustering. It
seems that norm-(k-)cut is quite established as an
ideal criterion here, but there are different, such

namepeople2people3
people4
people5alt-dsmath-med-fin
finance-cs-j
phil-avi-d
math-cuisine

data set information
size#clusters
50
2
75
3
100
4
125
5
64
2
60
3
30
2
198
2
600
2

missing data
0%
0%
0%
0%
0%
0%
0%
50%
70%

clustering errors and comp. time
max-cut/SDP
norm-cut/spectral0(4 sec) 0(0.07 sec)
0(∼ 90 sec) 2(0.13 sec)
1(∼ 876 sec) 5(0.2 sec)
4 (∼ 2544 sec) 8(0.35 sec)
1
(3 sec) 1(0.1 sec)
1(∼ 36 sec) 1(0.1 sec)
4(1.8 sec) 1(0.05 sec)
5
(12 sec) 6(2 sec)23(137 sec) 22(16.6 sec)

Table 1: Empirical comparison of the algorithms on the basic data sets (without removing additional data).

as min-max cut [3]. But also SDP has been usedin connection with spectral clustering and kernels:[11] propose a SDP relaxation for norm-k-cut clustering based on a similarity matrix, while [6] and[7] use SDP for completion and learning of kernel
matrices, respectively.
To our knowledge, this is the first time that a distance matrix and a max-(k-)cut criterion for similar clustering tasks have been used, which is natural in many applications where distances are given
instead of similarities. We have seen that a SDP
relaxation works quite well and yields results which
tend to be superior to the spectral clustering results, in particular if the fraction of missing values
grows. However, the SDP relaxation is expensive
for k = 3 or more clusters. Thus we conclude withthe open question of how to obtain a more efficientrelaxation of max-k-cut, for instance a spectral one.

References[1] B. Borchers and J. G. Young. Implementation ofa primal-dual method for sdp on a shared memory
parallel architecture. March 27, 2006.
[2] R. Cilibrasi and P. M. B. Vitányi. Automatic
meaning discovery using Google. Manuscript,
CWI, Amsterdam, 2006.
[3] C. H. Q. Ding, X. He, H. Zha, M. Gu, and H. D.
Simon. A min-max cut algorithm for graph partitioning and data clustering. In ICDM ’01: Proceedings of the 2001 IEEE International Conference on
Data Mining, pages 107–114. IEEE Computer Society, 2001.
[4] A. Frieze and M. Jerrum. Improved algorithms for
MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 1997.
[5] M. X. Goemans and D. P. Williamson. .879approximation algorithms for MAX CUT and
MAX 2SAT. In STOC ’94: Proceedings of theTwenty-Sixth Annual ACM Symposium on Theoryof Computing, pages 422–431. ACM Press, 1994.
[6] T. Graepel. Kernel matrix completion by semidefinite programming. In ICANN ’02: Proceedings ofthe International Conference on Artificial Neural
Networks, pages 694–699. Springer-Verlag, 2002.
[7] G. R. G. Lanckriet, N. Cristianini, P. Bartlett,
L. El Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. JMLR,
5:27–72, 2004.
[8] J. Poland and T. Zeugmann. Clustering pairwise
distances with missing data: Maximum cuts versus
normalized cuts. Accepted to the 9th International
Conference on Discovery Science (DS), 2006.
[9] B. Schölkopf, A. Smola, and K.-R. Müller. Nonlinear component analysis as a kernel eigenvalue
problem. Neural Computation, 10(5):1299–1319,
1998.
[10] J.F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11(12):625–653,
1999.
[11] E. P. Xing and M. I. Jordan. On semidefinite relaxation for normalized k-cut and connections tospectral clustering. Technical Report UCB/CSD03-1265, EECS Department, University of California, Berkeley, 2003.
[12] S. X. Yu and J. Shi. Multiclass spectral clustering.
In ICCV ’03: Proceedings of the Ninth IEEE International Conference on Computer Vision, pages
313–319. IEEE Computer Society, 2003.