Clustering Pairwise Distances with Missing
Data: Maximum Cuts versus Normalized Cuts?
Jan Poland and Thomas Zeugmann
Division of Computer Science
Hokkaido University, Sapporo 060-0814, Japan{jan,thomas}@ist.hokudai.ac.jp
http://www-alg.ist.hokudai.ac.jp/∼{jan,thomas}

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. In contrast,
algorithms working with the pairwise distance matrix have been studied
rarely for clustering. This is surprising, as in many applications, distances
are directly given, and computing similarities involves another step thatis error-prone, since the kernel has to be chosen appropriately, albeit computationally cheap. This paper proposes a clustering algorithm based on
the SDP relaxation of the max-k-cut of the graph of pairwise distances,
based on the work of Frieze and Jerrum. We compare the algorithm with
Yu and Shi’s algorithm based on spectral relaxation of a norm-k-cut.
Moreover, we propose a simple heuristic for dealing with missing data,i.e., the case where some of the pairwise distances or similarities are
not known. We evaluate the algorithms on the task of clustering natural
language terms with the Google distance, a semantic distance recently
introduced by Cilibrasi and Vitányi, using relative frequency counts from
WWW queries and based on the theory of Kolmogorov complexity.

1

Introduction

Let a set of n objects or data points, x1 , . . . , xn , be given. We might not know
anything about the objects, but assume that their pairwise distances dij =d(xi , xj ) are known. Here, d : M × M → R is a 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 thatthe distances within groups are small and the distances between the groups arelarge. This is done as follows. Construct a graph from the pairwise distances andchoose an algorithm from the large class of recently published methods basedon graph-theoretic cut criteria. As the cuts are usually N P-hard to optimize,appropriate relaxations have been subject to intensive research. Two types ofrelaxations are particularly important:?

This work was supported by JSPS 21st century COE program C01. Additional support has been provided by the MEXT Grand-in-Aid for Scientific Research on Priority Areas under Grant No. 18049001

2

Jan Poland and Thomas Zeugmann(1) Spectral methods, where the top eigenvectors of the graph’s adjacency
matrix are used to project the data into a lower dimensional space. This gives riseto new theoretical investigations of the popular spectral clustering algorithms.
(2) Semi-definite programming (SDP), where the discrete constraints of thecut criterion are replaced by continuous counterparts. Then convex solvers canbe used for the optimization.
Surprisingly, all of the clustering approaches suggested so far work on a graphof similarities rather than distances. This means that, given the distances, weneed 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 theclustering algorithm is quite sensitive to. Hence, it is natural to avoid this stepby using a cut criterion that directly works with the distance graph, e.g., maxcut. We follow Frieze and Jerrum [4] and solve the max-cut problem via an SDP
relaxation. We compare this method with a 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 ismost likely to leave the values of the cuts intact. This turns out to be the meanof the observed dij .
One motivation for considering missing data is given by the application weshall use to test the algorithms: Clustering of natural language terms using theGoogle distance. The Google distance [2] is a means of computing the pairwise distance of any searchable terms by just using the relative frequency countresulting from a web search. The Google API provides a convenient way for
automating this process, however with a single key (which is obtained by priorregistration) the maximum amount of daily queries is currently limited to 1000.
Hence, by querying an incomplete sparse distance matrix rather than a full one,
one can speed up considerably the overall process, as we shall demonstrate.
The paper is structured as follows. In the next two sections, we introduce
the two algorithms based on max-k-cut and norm-k-cut relaxations, respectively,
and recall some theory. In Section 4 we address the missing data problem. Section 5 confronts the two algorithms, looking on the exact cut criteria rather than
the relaxations, and compares the computational resources required. Section 6
describes the Google distance. In Section 7 we present experimental results with
the Google distance. Relation to other work is discussed and conclusions are
given in Section 8.

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 k disjoint subsets S1 , . . . , Sk . Here k is assumed to be given. We define the predicate A(i, j) = 0 if xi and xj happen to
be in the same subset, i.e., if ∃`[1 ≤ ` ≤ k, 1 ≤ i, j ≤ n and i, j ∈ S` ], andClustering Pairwise Distances with Missing Data

3

A(i, j) = 1, otherwise. The weight of the cut (S1 , . . . , Sk ) is defined asnXdi,j A(i, j) .

i,j=1

The max-k-cut problem is the task of finding the partition that maximizes theweight of the cut. It can be stated as follows: Let a1 , . . . , ak ∈ S k−2 be thevertices of a regular simplex, where
S d = {x ∈ Rd+1 | kxk2 = 1}
1
wheneveris the d-dimensional unit sphere. Then the inner product ai ·aj = − k−1
i 6= j. Hence, finding the max-k-cut is equivalent to solving the following integer
program:Xdij (1 − yi · yj )IP : maximize k−1
ki<jsubject to yj ∈ {a1 , . . . , ak } for all 1 ≤ j ≤ n.
Frieze and Jerrum [4] propose the following semidefinite program (SDP) in orderto relax the integer program:Xdij (1 − vi · vj )SDP : maximize k−1
ki<jsubject to vj ∈ S n−1 for all 1 ≤ j ≤ n and
1vi · vj ≥ − k−1
for all i 6= j (necessary if k ≥ 3).
1
The constraints vi · vj ≥ − k−1
are necessary for k ≥ 3 because otherwise the
SDP would prefer solutions where vi · vj = −1, resulting in a larger value of theobjective. We shall see in the experimental part that this indeed would resultin invalid approximations. The SDP finally can be reformulated as a convex
program:X
CP : minimize
dij Yij(1a)i<jsubject to Yjj = 1 for all 1 ≤ j ≤ n and1
Yij ≥ − k−1
for all i 6= j (necessary if k ≥ 3) andY = (Yij )1≤i,j≤n satisfies Y  0.

(1b)
(1c)
(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]. In order to implement the con1
straints Yij ≥ − k−1
with these solvers, positive slack variables Zij have to be1
introduced together with the equality constraints Yij − Zij = − k−1.
Finally, for obtaining the partitioning from the vectors vj or the matrix Y ,Frieze and Jerrum [4] propose to sample k points z1 , . . . , zk randomly on S n−1 ,4Jan Poland and Thomas Zeugmann

representing the groups, and assign each vj to the closest group, i.e., the closest zj . They show approximation guarantees generalizing those of Goemans andWilliamson [5]. In practice however, the approximation 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 need of recovering the vj . We recapitulate the complete algorithm:
Algorithm. Clustering as an SDP relaxation of max-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 k-means.

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 edges of 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 isdefined as (cf. Yu and Shi [12])k P
k P
1 X i∈S` ,j∈S` wij
1 X i∈S` ,j ∈S/ ` wijPP= 1−=: 1−knassoc(S1 , . . . , Sk ), (2)kki∈S` ,j∈V wiji∈S` ,j∈V wij
`=1

`=1

where knassoc(S1 , . . . , Sk ) is called the k-way normalized associations criterion.
Therefore, minimizing the norm-k-cut value is equivalent to maximizing thenorm-knassoc value. Following [12], this is the task we consider. For a vectorv = (v1 , . . . , vn ) we write Diag(v) to denote the matrix M = (mij )1≤i,j≤n withmii = vi and mij = 0 for all i 6= j. Furthermore, for a matrix M = (mij )1≤i,j≤n
we write diag(M ) to denote the vector (m11 , . . . , mnn ).
Optimizing (2) can be restated as solving the following integer program
IP : maximize k1 tr(Z T W Z)
1subject to Z = X(X T ΣX)− 2 , XnΣ = Diag
wij 1≤j≤n , and

(3)

i=1

X ∈ {0, 1}n×k such thatkX

X(j, `) = 1 for all 1 ≤ j ≤ n.

`=1

Relaxing the constraints on Z and passing to continuous domain, we need tosolve the following continuous program
ContP : maximize k1 tr(Z T W Z)
T

subject to Z ΣZ = Ik ,(4)

Clustering Pairwise Distances with Missing Data

5

where Ik is the k-dimensional identity matrix and Σ is defined as above. The
space of all optima of (4) can be described with the help of a spectral decompo1
1
sition of the Laplacian L = Σ − 2 W Σ − 2
1

1

L = Σ − 2 W Σ − 2 = U ΛU T ,(5)where U is orthogonal and Λ is diagonal. Let Λ∗ ∈ Rn×k denote the part of Λ
containing the largest k eigenvalues (such that Λ∗ (i, j) = 0 unless i = j), andU ∗ ∈ Rn×k be the corresponding eigenvectors, then1

Z = {Σ − 2 U ∗ R | RT R = Ik }(6)

describes the space of solutions of (4).
For some relaxed solution Z ∈ Z, the corresponding X ∈ Rn×k can beobtained by inverting (3):X̃ = Diag diag(ZZ t ) Z.
Then one can reconstruct an integer solution X by applying an EM procedure
and alternatingly optimizing the rotation matrix R and the discretization X:
1. For given R and resulting Z and X̃, let X(i, `) = 1, if X̃(i, `) ≥ X̃(i, m) for
all 1 ≤ m ≤ k, and let X(i, `) = 0, otherwise.
2. For given X and X̃, compute a singular value decomposition X T X̃ = Ũ Λ̃Ū T
and let R = Ũ Ū t .
We recapitulate the algorithm:
Algorithm. Clustering as a spectral relaxation of norm-k-cut [12]Input: Similarity matrix W = (wij ) .
1. Solve the eigenvalue problem (5).
2. Use the described EM procedure to optimize the discretization.
Note that the EM procedure used in this algorithm is different from, butnevertheless closely related to the k-means algorithm used in the algorithm basedon max-k-cut and many other spectral clustering algorithms.

4

Missing data

Assume that either the distance matrix D or the similarity matrix W is not fully
specified, but a portion of the off-diagonal entries is missing. One motivation
for considering this case could be the desire to save resources by computing
only part of the entries (e.g., for the Google distance discussed below, normaluser registration permits only a limited amount of queries a day). Suppose thatM ∈ {0, 1}n×n is a matrix such that diag(M ) = 0 and M (i, j) = 1 if and only if
D(i, j) (or W (i, j), 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]
M
(i,
j)
i,j
i=1

D̄ = PnX
1
W [i]T M [i].
M
(i,
j)
i,j
i=1

or W̄ = P

6Jan Poland and Thomas Zeugmann

Then, replacing the missing entries in D with the value D̄, the resulting distancematrix D is an unbiased estimate for the original full matrix, if the positions of
the missing values are sampled from a uniform distribution. Hence, the resulting
max-k-cut 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 ourgoal 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 , the missing values should be
replaced by the mean of the observed values. Asymptotically for n → ∞, this also
yields an unbiased estimate for the norm-k-cut criterion. However, the reasoning
is more difficult here, since the norm-k-cut criterion is a sum of quotients, and for
two random variables X and Y , we have E[X/Y ] 6= E[X]/E[Y ]. Still, the actual
values of numerator and denominator are close to their expectations, as one canverify using concentration inequalities, e.g., Hoeffding’s inequality. Then, forlarge 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 norm-cut criteria on distance andsimilarity matrices that are small enough to allow for a brute-force computationof the exact criteria. We start from 10 × 10 matrices D0 and W0 consisting of
two blocks of each size 5,
10 ··· 0 1 ··· 1
B. .
. . .
.C
B . .. . . .. . C
B.
. .
.C
B
C
0 ··· 0 1 ··· 1C
D0 =B
B
C
B1 ··· 1 0 ··· 0C
B
C
B. .
. . .
.C
@ . .. . . .. . A.
.
. .
1 ··· 1 0 ··· 0011 ··· 1 0 ··· 0
B. .
. . .
.C
B . .. . . .. . C
B.
. .
.C
B
C
1 ··· 1 0 ··· 0C
W0 =B
B
C.
B0 ··· 0 1 ··· 1C
B
C
B. .
. . .
.C
@ . .. . . .. . A. .
.
.
0 ··· 0 1 ··· 10and

From these matrices, distance matrices D and similarity matrices W are obtained by (1) perturbing the value by Gaussian noise of varying amplitude, (2)making the matrices symmetric and rescaling them to the interval [0, 1], (3) removing a fraction of the off-diagonal values and replacing them by the meanof the remaining values. Another matrix we use for the norm-cut criterion isa 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 values of 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 relative
number of experiments that result in a different clustering than the originallyintended one, grows if either the noise amplitude or the fraction of missing values increases. Of course this was expected. The max-cut criterion even yields
always the correct clustering if both noise amplitude and missing data fraction
are sufficiently low.

1
0.8
0.6
0.4
0.2
0
0.8

0.6
0.4
missingvalues fraction

1
0.2

0 0

noise
amplitude

0.5

7

1
0.8
0.6
0.4
0.2
0
0.8

0.6
0.4
missingvalues fraction

1
0.2

0 0

noise
amplitude

0.5

Fig. 2. Difference of the average fractionof incorrect clusterings by norm-k-cut relative to max-k-cut, where the similarity matrix W D was obtained from the distancematrix D as W D = exp(− 2σ1 2 D2 ).

Fig. 1. Average fraction of incorrect clusterings by max-kcut on a noisy distance matrix
with missing data.
difference fract. of incorr. clust.

difference fract. of incorr. clust.

fractions of incorrect clusterings

Clustering Pairwise Distances with Missing Data

0.5

0

−0.5
0.8

0.6
0.4
missingvalues fraction

1
0.2

0 0

noise
amplitude

0.5

Fig. 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 .

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 always
produces a higher error rate. The error rate is even more significantly higher forlarge fractions of missing values.
Did we introduce this increased error artificially by 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 thedifference of the error rates of the norm-cut clusterings of W D relative to thedirectly generated matrices W .

8

Jan Poland and Thomas Zeugmann

Next, we turn to the computational resources required by the algorithms.
Both max-cut and norm-cut are N P-hard to optimize, so let us look at therelaxations. The spectral decomposition of a n × n matrix can be done in timeO(n3 ), and if only the top k eigenvectors are desired, the effort can be evenreduced to O(kn2 ) by an appropriate Lanczos method. Therefore the normcut/spectral algorithm has quadratic or (depending on the implementation) at
most cubic complexity.
On the other hand, solving the SDP in order to approximate max-cut ismore expensive. The respective complexity is O(n3 + m3 ) (see [1]), where m isthe number of constraints. If k = 2, then m = n and the overall complexity
is cubic. However, for k ≥ 3, we need m = O(n2 ) constraints, resulting in an
overall computational complexity of O(n6 ).
Finally, we remark that the analysis of the eigenvalues of 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 not know of a corresponding method
based on the distance matrix. We shall not further discuss this issue here andassume in the following that k is known.

6

The Google distanceOur sample application for the subsequent simulations will be clustering of natural language terms using the Google distance. This distance has been suggested
by Cilibrasi and Vitányi [2] as a semantical distance function on pairs of words orterms. For instance, for most of today’s people, the terms “Claude Debussy” and“Béla Bartók” are much tighter related than “Béla Bartók” and “Michael Schumacher”. The World Wide Web represents parts of the world we live in as a hugecollection of documents, mostly written in natural language. We briefly describe
the derivation of the Google distance, starting with concepts from Kolmogorov
complexity (Algorithmic Information Theory).
Let us fix a universal Turing machine (which one we fix is not relevant, sinceeach universal machine can interpret each other by using a “compiler” programof constant length). For concreteness, we assume that its program tape is binary,such that all subsequent logarithms referring to program lengths are w.r.t. base 2(which is also not relevant for our algorithms). The output alphabet is ASCII.
Then, the (prefix) Kolmogorov complexity of a character string x is defined as
K(x) = length of the shortest self-delimiting program generating x,
where by the requirement “self-delimiting” we make sure that the programs forma prefix-free set and therefore the Kraft inequality holds:
X
2−K(x) ≤ 1 , where x ranges over all ASCII stringsx

The Kolmogorov complexity is a well-defined quantity regardless of the choiceof the universal Turing machine, up to an additive constant.

Clustering Pairwise Distances with Missing Data9

If x and y are ASCII strings and x∗ and y ∗ are their shortest (binary) programs, respectively, we can define K(y|x∗ ), which is the length of the shortest self-delimiting program generating y where x∗ , the program for x, is given.
K(x|y ∗ ) is computed analogously. Thus, we may follow [8] and define the universal similarity metric asmax K(y|x∗ ), K(x|y ∗ )(7)d(x, y) =max K(x), K(y)This can be interpreted as (approximately) the ratio by which the complexity of the more complex string decreases, if we already know how to generate the less complex string. The similarity metric is almost a metric according to 
the usual definition, as it satisfies the metric (in)equalities up to order
1/max K(x), K(y) .
Given a collection of documents like the World Wide Web, we can define theprobability of a term or a tuple of terms just by counting relative frequencies.
That is, for a tuple of terms X = (x1 , x2 , . . . , xn ), where each term xi is an
ASCII string, we set
pwww (X) = pwww (x1 , x2 , . . . , xn ) =# web pages cont. all x1 , x2 , . . . , xn.
# relevant web pages(8)

Conditional probabilities can be defined likewise as
pwww (Y |X) = pwww (Y  X)/pwww (X) ,where X and Y are tuples of terms and  denotes the concatenation. Although
the probabilities defined in this way do not satisfy the Kraft inequality, we may
still define complexities
K www (X) = − log pwww (X) and K www (Y |X) = K www (Y X)−K www (X). (9)Then we use (7) in order to define the web distance of two ASCII strings x and y,following Cilibrasi and Vitányi [2], asK www (x  y) − min K www (x), K www (y)wwwd(x, y) =(10)
max K www (x), K www (y)We query the page counts of the pages by using the Google API, so we call
dwww the Google distance. Since the Kraft inequality does not hold, the Google
distance is quite far from being a metric, unlike the universal similarity metricabove.
The “number of relevant web pages” arising in (8) will be estimated by handfor all of the subsequent simulations. Actually, the clustering is not very sensitive
to this value. On the other hand, Google no longer publishes its database size,
and the full database size would not be the most appropriate value anyway formany applications. E.g., if we cluster words in a not so common language, thenthe index size relative to this language might be more appropriate.

10

7

Jan Poland and Thomas Zeugmann

Experimental results with the Google distance

We evaluate both clustering algorithms from Sections 2 and 3 on a set of natural
language terms clustering tasks. We used the following datasets, which are allavailable at http://www-alg.ist.hokudai.ac.jp/datasets.html .
data set information
clustering errors and comp. time
namesize #clusters missing data max-cut/SDP norm-cut/spectral
people250
20%0(4 sec) 0(0.07 sec)
people375
30%0(∼ 90 sec) 2(0.13 sec)
people4100
40%1 (∼ 876 sec) 5(0.2 sec)
people5125
50%
4 (∼ 2544 sec) 8(0.35 sec)
alt-ds64
20%
1(3 sec) 1(0.1 sec)
math-med-fin 60
30%
1(∼ 36 sec) 1(0.1 sec)
finance-cs-j 30
2
0%4(1.8 sec) 1(0.05 sec)phil-avi-d
198
2
50%
5
(12 sec) 6(2 sec)math-cuisine 600
270%
23(137 sec) 22(16.6 sec)
Table 1. Empirical comparison of the algorithms on the basic data sets (without
removing additional data).

The dataset people2 contains the names of 25 famous classical composers
and 25 artists (i.e., two intended 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 we use the datasets math-med-fin containing 20 terms each fromthe 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 distancematrices of the last two data sets are not fully given: in phil-avi only 50% of
the entries are known, in math-cuisine it is only 30%.
For the norm-cut based algorithm, we need to convert the distance matrix toa similarity matrix. We do this by using a Gaussian kernel W D = exp(− 2σ1 2 D2 )√and set the width parameter σ = D̄/ 2, which gives good results in practice.
Another almost equally good choice is σ = 31 , which can be justified by the factthat 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 a different group than the intended one, respectively, on thedata sets just described. One can see that both algorithms perform well in principle, in fact many of the “errors” displayed are in reality ambiguities of thedata, e.g., the only misclustering in the math-med-fin data set concerns theClustering Pairwise Distances with Missing Data

15
10
5
0
2

0.75
3
#clusters

0.5

4
5

0.25
missing data

Fig. 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.

average number of clustering errors

average clustering errors

35

20

30

11

max−k−cut/SDP
norm−k−cut/spectral

25
20
15
10
5
0
0

0.2

0.4
0.6
missing data fraction

0.8

1Fig. 5. Comparison withvariable fraction of missing
data on the math-med-fin
set.

term “average” which was intended to belong to the mathematical terms but
ended up in the financial group.
We remark that the constraints (1c) and the resulting huge SDP size werereally necessary in order to get reasonable results: Without these constraints,
e.g., clustering the people5 data set with the SDP algorithm, the resulting
average number of errors is 36.
Looking on the computation times in Table 1 (measured on a 3 Ghz PentiumIV), the spectral method is clearly much faster than the SDP, in particular fork = 3 or more clusters. Here the quadratic number of constraints in the SDP
and the resulting 6th order computation time are really expensive. Actually, theavailable SDP software (CSDP, SeDuMi) do not even work at all with muchlarger problems if k ≥ 3.
Next we consider a situation with varying fraction of missing data, shown in
Figure 4 for the data sets people2-people5. Here the max-cut/SDP algorithm
consistently outperforms the norm-cut/spectral algorithm, in particular if thenumber of clusters or the fraction of missing data grows. The same can beobserved on the math-med-fin as shown in Figure 5. Note that both algorithms
work quite well until about 70% missing data, after that the error increases
sharply. Both figures are 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 the same fraction of missing
values. Figure 5 also displays 95%-confidence bars based on the standard normal
assumption.

12

8

Jan Poland and Thomas Zeugmann

Relations to other work and Conclusions

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 as min-max cut [3]. But also SDP
has been used in 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, the present work is the first one to use a distance matrix
and a max-(k-)cut criterion for similar clustering tasks, which is natural in many
applications where distances are given instead of similarities. We have seen thata 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 with the open question of how to obtain a more efficient relaxationof max-k-cut, for instance a spectral one.

References[1] B. Borchers and J. G. Young. Implementation of a 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. .879-approximation algorithms for MAX
CUT and MAX 2SAT. In STOC ’94: Proceedings of the twenty-sixth annual ACM
symposium on Theory of computing, pages 422–431. ACM Press, 1994.
[6] T. Graepel. Kernel matrix completion by semidefinite programming. In ICANN’02: Proceedings of the International Conference on Artificial Neural Networks,
pages 694–699. Springer-Verlag, 2002.
[7] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan.
Learning the kernel matrix with semidefinite programming. JMLR, 5:27–72, 2004.
[8] M. Li, X. Chen, X. Li, B. Ma, and P. M. B. Vitányi. The similarity metric. IEEE
Transactions on Information Theory, 50(12):3250–3264, 2004.
[9] B. Schölkopf, A. Smola, and K.-R. Müller. Nonlinear component analysis as akernel eigenvalue problem. Neural Computation, 10(5):1299–1319, 1998.
[10] J. 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 andconnections to spectral clustering. Technical Report UCB/CSD-03-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.