Clustering the Google Distance with
Eigenvectors and Semidefinite
Programming
Jan Poland and Thomas Zeugmann
Division of Computer Science
Hokkaido University
N-14, W-9, Sapporo 060-0814, Japan{jan,thomas}@ist.hokudai.ac.jp
Abstract
Web mining techniques are becoming increasingly popular and more accurate, as the informationbody of the World Wide Web grows and reflects a more and more comprehensive picture of thehumans’ view of the world. One simple web mining tool is called the Google distance and has
been recently suggested by Cilibrasi and Vitányi. It is an information distance between two
terms in natural language, and can be derived from the “similarity metric”, which is definedin the context of Kolmogorov complexity. The Google distance can be calculated from justcounting how often the terms occur in the web (page counts), e.g. using the Google searchengine. In this work, we compare two clustering methods for quickly and fully automaticallydecomposing a list of terms into semantically related groups: Spectral clustering and clusteringby semidefinite programming.

1. Introduction
The Google 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 partsof the world we live in as a huge collection of documents, mostly written in natural language. By just counting the relative frequency of a term or a tuple ofterms, we may obtain a probability of thisterm or tuple. From there, one may define conditional probabilities and, by taking logarithms, complexities. Li et al. [7]have proposed a distance function basedon Kolmogorov complexity, which can beused for other complexities, such as thosederived from the WWW frequencies.
Spectral clustering is an increasingly popular method for analyzing and clustering
data by using only the matrix of pairwise
similarities. It was invented more than 30
years ago for partitioning graphs (see e.g.
[11] for a brief history). Formally, spectralclustering can be related to approximating the normalized min-cut of the graphdefined by the adjacency matrix of pairwise similarities [15]. Finding the exactly
minimizing cut is an NP-hard problem.
The Google distances can be transformed
to similarities by means of a suitable kernel. However, as such a transformation
potentially introduces errors, since in particular the kernel has to be chosen appropriately and the clustering is quite sensitive to this choice, it seems natural toalphabet is ASCII or UTF-8, according towhich character set we are actually using.
(For simplicity, we shall always use theterm ASCII in the following, which is tobe replaced by UTF-8 if necessary.) Then,the (prefix) Kolmogorov complexity of acharacter string x is defined aswork directly on the distances. Then,the emerging graph-theoretical criterion
is that of a maximum cut. Optimizing
this cut is again NP-hard, but can beapproximated with semidefinite programming (SDP).
The main aim of this work is to compare spectral clustering and clustering by
SDP, both of which are much faster thanthe computationally expensive phylogenetic trees used by [2]. We will show how
state-of-the-art techniques can be combined in order to achieve quite accurate
clustering of natural language terms withsurprisingly little effort.

K(x) = length of the shortest self-delimiting program generating x.
By the requirement “self-delimiting” weensure that the programs form a prefixfree set and therefore the Kraft inequality
holds, i.e.,X
2−K(x) ≤ 1 ,There is a huge amount of related work,in computer science, in linguistics, as wellas in other fields. Text mining with spectral methods has been for instance studied
in [3]. A variety of statistical similarity
measures for natural language terms has
been listed in [13]. For literature on spectral clustering, see the References section
and the references in the cited papers.

xwhere x ranges over all ASCII strings.
The Kolmogorov complexity is a welldefined quantity regardless of the choiceof the universal Turing machine, up to an
additive constant.
If x and y are ASCII strings and x∗ and y ∗are their shortest (binary) programs, respectively, we can define K(y|x∗ ), whichis 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 [7] anddefine the universal similarity metric asmax K(y|x∗ ), K(x|y ∗ )d(x, y) =(1)
max K(x), K(y)The paper is structured as follows. In thenext section, we introduce the similarity
metric, the Google distance, and spectralclustering as well as clustering by SDP,
and we shall state our algorithms. Section 3 describes the experiments and theirresults. Finally, in Section 4 we discuss
the results obtained and give conclusions.

2. Theory

We can interprete d(x, y) as an approximation of the ratio by which the complexity of the more complex string decreases, if we already know how to generate the less complex string. The universal similarity metric is almost a metricaccording to the usual definition, as it satisfies the metric (in)equalities up to order
1/max K(x), K(y) .

2.1. Similarity Metric and Google
Distance
We start with a brief introduction to Kolmogorov complexity (see [8] for a much
deeper introduction). Let us fix a universal Turing machine (which one we fix
is not relevant, since each universal machine can interpret each other by using a“compiler” program of 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. the base 2. The output

Given a collection of documents like theWorld Wide Web, we define the probability of a term or a tuple of terms by counting relative frequencies. That is, for a tuple of terms X = (x1 , x2 , . . . , xn ), where62are interested in the similarity of “cosine”
and “triangle.” They would be relevant if
we were searching for the corresponding
Chinese terms. So we use a different way
to fix the relevant database size. We add
the search term “the” to each query, if weare dealing with English language. Thisis one of the most frequent words used in
English and therefore gives a reasonable
restriction of the database. The databasesize is then the number of occurrences of“the” in the Google index. Similarly, forour experiments with Japanese, we add
the term d (“no” in hiragana) to all
queries.

each term xi is an ASCII string, we set
pwww (X) = pwww (x1 , x2 , . . . , xn ) =(2)# web pages containing all x1 , x2 , . . . , xn.
# relevant web pages
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 theprobabilities defined in this way do notsatisfy the Kraft inequality, we may stilldefine complexities
K www (X) = − log pwww (X) and2.2. Spectral Clustering
Consider the block diagonal matrix


1 1 0
 1 1 0  .
0 0 1

K www (Y |X) = K www (Y ∪ X) − K www (X) .
Then we use (1) in order to define the web
distance of two ASCII strings x and y,following [2], as
dwww (x, y) =K www (x ∪ y) − min K www (x), K www (y)max K www (x), K www (y)Its top two eigenvectors, i.e., the eigenvectors associated with the largest two eigenvalues, are [1 1 0]T and [0 0 1]T . That is,they separate the two perfect clusters represented by this similarity matrix. In general, there are conditions under which the
top k eigenvectors of the similarity matrix
or its Laplacian result in a good clustering, even if the similarity matrix is not
perfectly block diagonal [9, 14]. In particular, it was observed in [4] that the transformed data points given by the k top
eigenvectors tend to be aligned to lines in
the k-dimensional Euclidean space, therefore the kLines algorithm is appropriate
for clustering. In order to get a complete clustering algorithm, we therefore
only need to fix a suitable kernel functionin order to proceed from a distance matrix
to a similarity matrix.
For the kernel, we use the Gaussiank(x, y) = exp − 12 d(x, y)2 /σ 2 . We may
use a globally fixed kernel width σ, since
the Google distance (3) is scale invariant.
In the experiments, we compute the meanvalue of the entries of the distance√ matrix
D and then set σ = mean(D)/ 2.

(3)

Since we use Google to query the pagecounts of the pages, we also call dwww the
Google distance. Since the Kraft inequality does not hold, the Google distance isquite far from being a metric, unlike theuniversal similarity metric above.
A remark concerning the “number of relevant web pages” in (2) is mandatory here.
This could be basically the number of all
pages indexed by Google. But this quantity is not appropriate for two reasons:First, since some months ago there seems
to be no way to directly query this number. Hence, the implementation by [2]used a heuristic to estimate this value,
which however yields inaccurate results.
Second, not all web pages are really relevant for our search. For example, billionsof Chinese web pages are irrelevant if we
63

The max-k-cut problem is the task offinding the partition that maximizes theweight of the cut. It can be stated as follows: Let a1 , . . . , ak ∈ S k−2 be the verticesof a regular simplex, where

In this way, the kernel is most sensitivearound mean(D).
The final spectral clustering algorithm fora known number of clusters k is stated below. We shall discuss in the experimental
section how to estimate k if the numberof clusters is not known in advance.

S d = {x ∈ Rd+1 | kxk2 = 1}
is the d-dimensional unit sphere. Then1
the inner product ai · aj = − k−1
wheneveri 6= j. Hence, finding the max-k-cut isequivalent to solving the following integer
program:X
IP:
maximize k−1
dij (1 − yi · yj )kAlgorithm Spectral clustering of a word
list
Input: word list X = (x1 , x2 , . . . , xn ),number of clusters k
Output: clustering c ∈ {1 . . . k}n
1. for x, y ∈ X, compute Google relative
frequencies pwww (x), pwww (x, y)i<jsubject toyj ∈ {a1 , . . . , ak }for all 1 ≤ j ≤ n.

2. for x, y ∈ X, compute complexities
K www (x), K www (x, y)Frieze and Jerrum [5] propose the following semidefinite program (SDP) in orderto relax the integer program:Xdij (1 − vi · vj )SDP :maximize k−1k

3. compute distance matrix
D = dwww (x, y) x,y∈X√
4. compute σ = mean(D)/ 2

i<j

5. compute similarity matrix

subject 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
A = exp(− dwww (x, y)2 /σ 2 )2
1

1

6. compute Laplacian
L = S − 2 AS − 2 ,P
where Sii = j Aij and Sij = 0 for
i 6= j1
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 the objective.
We shall see in the experimental part that
this indeed would result in invalid approximations. The SDP finally can be reformulated as a convex program:
X
CP : minimize
dij Yij(4a)

7. compute top k eigenvectors V ∈ Rn×k
8. cluster V using kLines [4]2.3. Semidefinite programming
Given a 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-waycut is a partition of V into k disjoint subsets S1 , . . . , Sk . Here k is assumed to begiven. We define the predicate A(i, j) = 0
if ∃`[1 ≤ ` ≤ k, 1 ≤ i, j ≤ n and i, j ∈S` ] and A(i, j) = 1, otherwise. The weightof the cut (S1 , . . . , Sk ) is defined as
n
X

i<j

subject toYjj = 1(4b)
for all 1 ≤ j ≤ n and(4c)1
Yij ≥ − k−1 for all i 6= j (4d)(necessary if k ≥ 3)
(4e)
and Y  0.
(4f)
Here, Y ∈ Rn×n is a matrix, and the lastcondition Y  0 means that Y is positive

dij A(i, j) .

i,j=1

64

3. Experiments

semidefinite. Hence, Y will be a kernel
matrix. Efficient solvers are available forthis kind of optimization problems, suchas CSDP [1] or SeDuMi [12]. In order1
to implement the constraints Yij ≥ − k−1
with these solvers, actually positive slack
variables Zij have to be introduced together with the equality constraints

In this section, we present the experiments of our clustering algorithm applied
to four lists of terms. First we show stepby step how the algorithm acts on the firstdata set, which is the following list of 60
English words:
axiom,average,coefficient,probability,
continuous,coordinate,cube,
denominator,disjoint, domain, exponent,
function,histogram, infinity, inverse,
logarithm,permutation, polyhedra,
quadratic, random, cancer, abnormal,
abscess, bacillus,delirium,
betablocker, vasomotor, hypothalamic,
cardiovascular, chemotherapy,
chromosomal, dermatitis, diagnosis,
endocrine, epilepsy, oestrogen,ophthalmic,vaccination, traumatic,transplantation, nasdaq, investor,
obligation, benefit,bond, account,clearing, currency, deposit, stock,market, option, bankruptcy,creditor,
assets, liability, transactions,insolvent, accrual, unemployment

1Yij − Zij = −.
k−1
Finally, in order obtain the partitioning
from the vectors vj or the matrix Y , [5]propose to sample k points z1 , . . . , zk randomly on S n−1 and assign each vj to thegroup by the closest zi . They show approximation guarantees generalizing thoseof Goemans and Williamson [6]. In practice however, the approximation guarantee does not necessarily yield 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[10]) which directly works on the scalar
products Yij = vi · vj , without need of recovering the vj . We thus arrive at thefollowing algorithm:

The first 20 words are commonly used inmathematics, the next 20 words have beentaken from a medical glossary, and thefinal 20 words are financial terms. The
matrix containing the complexities is depicted in Figure 1 (large complexities arewhite, small complexities black). Clearly,
the single complexities on the diagonal aresmaller than the pairwise complexities offdiagonal.

Algorithm SDP clustering of a word list
Input: word list X = (x1 , x2 , . . . , xn ),number of clusters k
Output: clustering c ∈ {1 . . . k}n
1. for x, y ∈ X, compute Google relative
frequencies pwww (x), pwww (x, y)
2. for x, y ∈ X, compute complexities
K www (x), K www (x, y)
3. compute distance matrix
D = dwww (x, y) x,y∈X
4. solve the SDP by using CP (cf. (4a)through (4f))

Fig. 1: Complexities

5. cluster the resulting matrix Y using
kernel k-means [10]Fig. 2: Distances

In the distance matrix (Figure 2), the65Fig. 3: Similarity

to the medical terms, in a hierarchicalclustering we would first split off the medical terms and then divide mathematicaland financial terms. The spectral clustering correctly groups all terms except
for “average”, which is assigned to thefinancial terms instead of the mathematical terms (this is also visible from Figure 5). As average also occurs often infinance, we cannot even count this as misclustering. We stress that the clustering
algorithm is of course invariant to permutations of the data, i.e. yields the same
results if the terms are given in a different order. It is just convenient for thepresentation to work with an order corresponding to the correct grouping.

Fig. 4: Laplacianfirst eigenvector of the Laplacian0

second eigenvector of the Laplacian
0.4
0.2
0
-0.2
third eigenvector of the Laplacian
0.4
0.2
0

The same clustering result is obtained
from the SDP clustering. The kernel matrix resulting from solving the SDP clearly
displays the block structure, again withthe exception of the term “average”.

Fig. 5: Eigenvector plot

In case that we do not know the number of clusters k in advance, there is a
way to estimate this quite reliably fromthe eigenvalues of the Laplacian, if thedata is not too noisy. Consider again
the case of a perfect block diagonal matrix, i.e. all intra-cluster similarities are 1
and all other entries 0. Then the number of non-zero eigenvalues of this matrix
is equal to the number of blocks/clusters.
If the matrix is not perfectly block diagonal, we may still expect some dominant eigenvalues which are clearly larger
than the others. Figure 7 top left shows
this for our first example data set. The
top three eigenvalues of the Laplacian are
dominant, the fourth and all subsequentones are clearly smaller. (Observe thatthe smallest eigenvalues are even negative:
This indicates that the distances we used
do not stem from a metric. Otherwise all
eigenvalues should be nonnegative, since
the Gaussian kernel is positive definite.)block structure is visible. After transformation to the Similarity matrix (Figure 3)
and Laplacian (Figure 4), the block structure of the matrix becomes very clear.
Figure 5 shows the top three eigenvectors of the Laplacian. The first eigenvector having only negative entries seems
not useful at all for the clustering (butin fact it is useful for the kLines algorithm). The second eigenvector separates
the medical terms (positive entries) fromthe union of mathematical and financial
terms (negative entries). This indicatesthat the mathematical and financial clusters are closer related than each is related

We propose a simple method for detecting the gap between the dominant eigenvalues and the rest: Tentatively split

Fig. 6: Kernel matrix after SDP

66

The next data set is the “colors-nums”
data set from [2]:eigenvalues of the Laplacian: math-med-finance
1
0.8
0.6
0.4
0.2
0

purple, three, blue, red, eight,
transparent, black, white, small, six,yellow,seven, fortytwo, five,
chartreuse, two, green, one, zero,orange, four

eigenvalues of the Laplacian: colors-nums
1
0.8
0.6
0.4
0.2
0

Although the intended clustering has
two groups, colors and numbers (where“small” is supposed to be a number and“transparent” a color), the eigenvaluesof the Laplacian in Figure 7 bottom left
indicate that there are three clusters.
Indeed, in the final spectral clustering,“fortytwo” forms a singleton group,and “white” and “transparent” aremisclustered as numbers.
Clusteringwith SDP gives a slightly different result:Here, best results are obtained with k = 2
clusters, in which case only “fortytwo”
is wrongly assigned to the colors.

eigenvalues of the Laplacian: people
1
0.8
0.6
0.4
0.2
0

eigenvalues of the Laplacian: Japanese
1
0.8
0.6
0.4
0.2
0

The next data set,
Fig. 7: Plots of the eigenvalues of the
Laplacian (bars) and the s.s.e. score fordetermining the number of clusters (lines)
for the four data sets

Takemitsu, Stockhausen, Kagel, Xenakis,
Ligeti, Kurtag, Martinu, Berg, Britten,
Crumb,Penderecki, Bartok, Beethoven,
Mozart, Debussy, Hindemith, Ravel,
Schoenberg, Sibelius,Villa-Lobos, Cage,
Boulez, Kodaly, Prokofiev, Schubert,
Rembrandt, Rubens, Beckmann, Botero, Braque,
Chagall, Duchamp, Escher, Frankenthaler,
Giacometti, Hotere, Kirchner, Kandinsky,
Kollwitz, Klimt, Malevich, Modigliani,
Munch, Picasso, Rodin, Schlemmer, Tinguely,
Villafuerte, Vasarely, Warhol, Rowling,
Brown, Frey, Hosseini, McCullough, Friedman,
Warren, Paolini, Oz, Grisham, Osteen,
Gladwell, Trudeau, Levitt, Kidd, Haddon,
Brashares, Guiliano, Maguire, Sparks,
Roberts, Snicket, Lewis, Patterson, Kostova,
Pythagoras, Archimedes, Euclid, Thales,
Descartes, Pascal, Newton, Lagrange, Laplace,
Leibniz, Euler, Gauss, Hilbert, Galois,
Cauchy, Dedekind, Kantor, Poincare, Godel,
Ramanujan, Wiles, Riemann, Erdos, Thomas
Zeugmann, Jan Poland, Rolling, Stones,
Madonna,Elvis, Depeche, Mode, Pink, Floyd,
Elton, John, Beatles, Phil, Collins,

after the second eigenvalue, compute themeans of the eigenvalues in the two groups“dominant” and “non-dominant” (ignore
the top eigenvalue, which is always muchlarger), and calculate the sum square error (s.s.e.) of all eigenvalues w.r.t. theirmeans. Compute this s.s.e. score also forthe split after the third eigenvalue, thefourth eigenvalue and so forth. Choose
the split with the lowest score. We have
depicted the s.s.e. scores in Figure 7 bysolid lines. For the math-med-financedata set, the minimum score is at the correct number of k = 3 clusters.
Note that this method works only for the
spectral clustering, there is no obvious
corresponding algorithm for the SDP clustering.
67

clearly indicate the correct number ofk = 2 clusters. However, when using
k = 2, only the term “d d” (whichmeans “environment”) is non-intendedlygrouped with the computer science words
by the spectral clustering. SDP clustering
gives the same result here.

Toten, Hosen, McLachan, Prinzen, Aguilera,
Queen, Britney, Spears, Scorpions,
Metallica, Blackmore, Mercy

consists of five groups of each 25 (moreor less) famous people:
composers,
artists, last year’s bestseller authors,mathematicians (including the authors of
the present paper), and pop music performers. We deliberately did not specify
the terms very well (except for our own
much less popular names), in this way
the algorithm could “decide” itself if“Oz” meant one of the authors Amos andMehmet Oz or one of the pop music songs
with Oz in the title. The eigenvalue plot
in Figure 7 top right shows clearly fiveclusters. From the 125 names, 9 were notclustered into the intended groups using
the spectral method. The highest numberof incorrectly clustered names (4 misclusterings) occurred in the least populargroup of the mathematicians (but our
two names were correctly assigned). We
also observed that the spectral clusteringgets disproportionately harder when thenumber of clusters increases: Clustering
only the first 50, 75, and 100 names gives
0, 2, and 5 clustering errors, respectively.
We also tried clustering the same data
set w.r.t. the Japanese web sites in the
Google index, this gave 0, 1, 4, and 16
clustering errors for the first 50, 75, 100,
and 125 names, respectively.

The computational resources requiredby our clustering algorithms are much
lower than those needed by Cilibrasi andVitányi’s algorithm [2]. Their clustering
tries to optimize a quality function, a task
which is NP hard. The approximation
costs hours even for small lists of n = 20
words. On the other hand, our spectralclustering’s naive time complexity is cubicO(n3 ) in the number of words. This canbe improved to O(n2 k) by using Lanczos
method for computing the top k eigenvectors.
On our largest “people” data set withn = 125, our spectral clustering needs
about 0.11sec on a 3GHz Pentium4 processor with the ATLAS library.
Solving the SDP in order to approximate
max-cut is more expensive. The respective complexity is O(n3 + m3 ) (cf. [1]),where m is the 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 ofO(n6 ). On our largest “people” data set
with n = 125, our SDP clustering needs
about 2544sec.

Clustering with SDP gives better results
here: 0, 0, 1, and 4 clustering errors forthe first 50, 75, 100, and 125 names, respectively.

4. Discussion and Conclusions
We have shown that it needs surprisingly
little effort, just a few queries to a popularsearch engine together with some state-ofthe-art methods in machine learning, toautomatically separate lists of terms into
clusters which make sense. We have focused on unsupervised learning in this paper, but for other tasks such as supervised
learning, appropriate tools are available
as well (e.g. SVM). Our methods are theoretically quite well founded, basing on the

The last data set consists of 20 Japaneseterms from finance and 10 Japanese terms
from computer science (taken from glossaries):
dd, dd, dd, dd, dd, dd, dd, dd,
dd, dd, dd, dd, dd, dd, dd, dd
d, dd, ddd, dddd, dd, dd, ddd
d, dddd, dd, dd, dd, dd, dd, dd, dd.

The eigenvalue plot in Figure 7 does not68[8] M. Li and P. M. B. Vitányi. An introduction to Kolmogorov complexity
and its applications. Springer, 2ndedition, 1997.

theories of Kolmogorov complexity on the
one hand and graph cut criteria and spectral clustering or semidefinite programming on the other hand. The SDP clustering is the more direct approach, as itneeds less steps. Also, it yields slightly
better results. However, it is computationally more expensive than spectralclustering.

[9] A. Ng, M. Jordan, and Y. Weiss. On
spectral clustering: Analysis and analgorithm. In Advances in Neural
Information Processing Systems 14,
2001.

References[10] 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.

[1] B. Borchers and J. G. Young. Implementation of a primal-dual method
for sdp on a shared memory parallelarchitecture. March 27, 2006.
[2] R. Cilibrasi and P. M. B. Vitányi.
Automatic meaning discovery using
Google. Manuscript, CWI, Amsterdam, 2006.

[11] D. A. Spielman and S. Teng. Spectral
partitioning works: Planar graphs
and finite element meshes. In IEEE
Symposium on Foundations of Computer Science, pages 96–105, 1996.

[3] I. Dhillon. Co-clustering documents
and words using bipartite spectral
graph partitioning. In Proceedingsof the 7th ACM SIGKDD Int. Conference on Knowledge Discovery andData Mining(KDD), pages 269–274,
2001.

[12] J. Sturm. Using SeDuMi 1.02, a
MATLAB toolbox for optimization
over symmetric cones. Optimization
Methods and Software, 11(12):625–
653, 1999.

[4] I. Fischer and J. Poland. New methods for spectral clustering. Technical
Report IDSIA-12-04, IDSIA / USISUPSI, Manno, Switzerland, 2004.

[13] E. L. Terra and C. L. A. Clarke. Frequency estimates for statistical word
similarity measures. In HLT-NAACL
2003: Main Proceedings, pages 244–
251, Edmonton, Alberta, Canada,
2003.

[5] A. Frieze and M. Jerrum.
Improved algorithms for MAX k-CUT
and MAX BISECTION. Algorithmica, 18(1):67–81, 1997.

[14] U. von Luxburg, O. Bousquet, and
M. Belkin. Limits of spectral clustering. In Advances in Neural Information Processing Systems (NIPS) 17.
MIT Press, 2005.

[6] 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.

[15] 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.

[7] M. Li, X. Chen, X. Li, B. Ma, andP. M. B. Vitányi. The similarity metric. IEEE Transactions on Information Theory, 50(12):3250–3264, 2004.
69