2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology

Graph-cut based Iterative Constrained Clustering
Masayuki Okabe
Toyohashi University of Technology
Tenpaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

Seiji Yamada
National Institute of Infomatics
Chiyoda, Tokyo, Japanseiji@nii.ac.jp

Abstract—This paper proposes a constrained clustering
method that is based on a graph-cut problem formalized by
SDP (Semi-Deﬁnite Programming). Our SDP approach has theadvantage of convenient constraint utilization compared withconventional spectral clustering methods. The algorithm starts
from a single cluster of a complete dataset and repeatedly
selects the largest cluster, which it then divides into two clusters
by swapping rows and columns of a relational label matrix
obtained by solving the maximum graph-cut problem. Thisswapping procedure is effective because we can create clusters without any computationally heavy matrix decomposition
process to obtain a cluster label for each data. The results ofexperiments using a Web document dataset demonstrated that
our method outperformed other conventional and the state of
the art clustering methods in many cases. Hence we consider
our clustering provides a promising basic method to interactive
Web clustering.

Our approach is to solve it as a semi-deﬁnite programming(SDP) problem. The advantage of SDP is that we cannaturally incorporate constraints without any complicatedprocessing and do not need any speciﬁc objective functions(e.g., normalized cut) to avoid a trivial solution (as is thecase with many other spectral clustering methods).
In terms of formalization, our problem is the same as Li’s[4] or Hoi’s [5], although the introduction is completely different. The most critical difference is the interpretation of the
SDP solution. They interpret the solution as a kernel matrix
and use it for multi-class clustering, while we interpret it
as a label matrix (as described above) and use it for twoclass clustering. As we will show in the experiments, our
two-class clustering approach performs better than the multiclass clustering approach. Our approach is based on thedivide and conquer algorithm. It starts from a single clusterof a complete dataset and repeatedly selects the largest
cluster, which it then divides into two clusters until we get
the target numbers of clusters. In each iteration, we obtain
relational labels for all data pairs from the solution of the
SDP problem. We then use the label matrix to create clusters
by swapping rows and columns to reduce the clusters’label distribution entropies. This swapping procedure isvery effective because we can create clusters without any
computationally heavy matrix decomposition processing.
In summary, we propose a constrained clustering methodthat has the following features.

I. I NTRODUCTION
Constrained clustering is a semi-supervised learning approach that utilizes pre-given knowledge about data pairs
to improve normal clustering accuracy [1]. The knowledge
used is generally of two simple types: a constraint aboutdata pairs that must be in the same cluster, and a constraint
about data pairs that must be in a different cluster. These
are usually called must-link and cannot-link, respectively.
Recent research about distance metric learning interprets
the constraint information as the distance or kernel value ofdata pairs and tries to produce a new distance measure or
kernel matrix for a complete dataset to ensure the distanceof must-link is small and the distance of cannot-link is large[2]. In this research, we do not interpret the constraint as
a distance or kernel value but rather as a relational labelthat indicates whether data pairs should be in the samecluster or not. Our objective is to predict the correct label
for each data pair (not for each individual piece of data)
by using sample labels converted from pre-given constraint
information according to the framework of the transductive
learning.
Our method is based on the graph-cut problem. Althoughgraph-cut based clustering (e.g., spectral clustering) is a wellknown approach and many methods have been proposedso far [3], their solutions are mostly based on the graphspectrum obtained by eigen decomposition, which requires
complicated processes to add in the constraint information.
978-0-7695-4513-4/11 $26.00 © 2011 IEEE
DOI 10.1109/WI-IAT.2011.42

Clustering is performed based on the relational labelsof all data pairs that are obtained by solving a graphcut problem formalized by semi-deﬁnite programming.
Our SDP approach has the advantage convenient constraint utilization compared with conventional spectralclustering methods.
• The interpretation of the obtained matrix is different
from Li and Hoi’s approaches, although the problem
formalization is similar. They use the matrix as a kernel
matrix for one-time multi-class clustering, while we use
it as binary label matrix for divide and conquer-based
two-class clustering.
•

These advantages make constrained clustering more efﬁcient, especially in the case of small number of constraints.
Thus we are planning to apply this clustering method to126interactive web clustering like [6].
II. G RAPH PARTITIONING AND ITS S OLUTION
A. Maximum Cut Problem
The objective of the problem is to divide a graph into twoparts as its cut amount reaches the maximum. More formally,
consider a graph G = (V, E), where V is a set of vertices
and E is a set of edges. The problem is to ﬁnd partitioning(V1 , V2 ) such as V1 ∪ V2= V and V1 ∩ V2 = φ and amaximum cut amount of i∈V1 ,j∈V2 wij . Here, wij is theweight of an edge between data i ∈ V1 and data j ∈ V2 . We
decide on a “maximum” cut when wij is deﬁned by somedistance (e.g., Euclid distance). In contrast, if wij is deﬁned
by some similarity (e.g., Gauss kernel), the “minimum” cutis appropriate.
By introducing a cluster label variable ui for each vertex,
we can formalize the maximum cut problem as follows.

 



Figure 1.

u = (u1 , u2 , ..., un ),1  wij (1 − ui uj )4

Maximum Cut Problem with SDP Relaxation

u2k = 1 (k ∈ V )
+1 (k ∈ V1 )uk =−1 (k ∈ V2 )maximizesubject to(i = 1 ∼ n)(i, j) ∈ M

Eij is an n × n matrix in which only the (i, j) element
is 1, and all others are 0. M is a set of must-link.
Although available constraints are not limited to mustlink, meaning we can also use cannot-link, it is very difﬁcult
to select applicable cannot-links during multi-class clustering because the partitioning order determined in the graphcut process is usually unpredictable in advance. Figure 1
gives an idea of the difﬁculty of using cannot-link. There
are three data in the ﬁgure - a, b, c - and cannot-link isapplicable only at the second cut. It cannot be used at theﬁrst cut because b and c are in the same cluster at that time.
There are several freely available SDP solvers that we canuse to obtain an approximate solution X̃. Although we needto decompose X̃ to obtain partitioning label u, we found a
way to complete partitioning by using only X̃. We explain
this method in the next section.
III. C LUSTERING THROUGH S WAPPING ROWS AND
C OLUMNS IN A L ABEL M ATRIXAs described in the previous section, we solve the maximum cut problem with relaxed SDP, so the elements ofX̃ are assigned a real value ranging from -1 to 1. Though
we can use those values as similarity and run k-means,
we found the resulting performance was very low. We
therefore decided on a different approach in which we ﬁrst
binarize X̃ with 0-1 values, then swap rows and columns towij (1 − ui uj ) = (diag(W e) − W ) • X=

L•X
Eii • X = 1,
Eij • X = 1,
XO

B. Solution by Semi-deﬁnite Programming Relaxation
Semi-deﬁnite programming is a kind of convex optimization that is used to relax several optimization problems suchas combinatorial optimization, 0-1 integer programming, andnon-convex quadratic programming. Since the maximum cut
problem is an example of 0-1 integer programming, SDP canalso relax it.
For the standard formalization of SDP, we transform theabove objective function into a matrix representation witha weight matrix W and a matrix X whose element is the
product of ui and uj .

i∈V1 j∈V2n = |V |L is the graph Laplacian matrix and e is a vector whose
elements are all one. As a ﬁnal step, we add must-link constraints to formalize the constrained maximum cut problem
as follows.

According to the standard method of spectral clusteringor segmentation by the random walk model, we can solve
this problem with the method of Lagrange multipliers. The
ui labels are obtained as eigen vectors corresponding to thesecond largest eigen value.
Our aim is to incorporate given constraints into the above
problem and ﬁnd a method to solve constrained maximum cut problems. While there are constrained versions ofspectral clustering methods, we adopt a different approach,solution by semi-deﬁnite programming (SDP), which ispractically easier to use because it can handle constraints
intrinsically.

 

Cannot-link is not applicable in divide and conquer approach

X = uT ui∈V1 j∈V2subject to         Maximum Cut Problem
maximize



L•X

127



1: Input: D// Dataset
2:
W// Weight Matrix
3:M// Must-Link Set
4:K// Number to be Clustered
5: Output: {D1 , D2 , ..., DK }// K clusters
6:0
7: Let Dsub
=Dt
8: Select the largest cluster Dsubt
9: Select a set of must-link applicable to divide Dsubtt
10: Solve maximum graph cuts problem for Dsub
and divide Dsub        

Figure 2.
matrixtt
into Dsub1and Dsub2     

Clustering process by swapping rows and columns in a label
Table IDATASETS
No.
1
2
3
4
5
6
7
8
9
10
11
12

maximize the evaluation measure, and ﬁnally determine thepartitioning border.
The concrete procedures are as follows.
1) Each element of X̃ is binarized as follows.

1, if xij ≥ 0
xij =0, if xij < 0
The value does not matter because we treat 0 and 1
as a character in the following steps.
2) For each row, treat the column’s value as a character (0or 1) and make a string (or pattern) by concatenatingeach character in the original order. Next, make groupsof the same string (select a representative of each kindof string).
3) Determine the most frequent string s0 , and calculate
the Hamiltonian distance between s0 and the otherstrings. Next, align other strings in descending orderof the distance. String s1 is the most similar to s0 .
4) Determine the partitioning boundary according to thefollowing measure.
4   

11: Return STATE 8 and Repeat K-1 times

F (i, j) =            

Algorithm 1 Clustering Procedure

Category
Anomalies and Alternative Science
Science in Society
Environment/Water Resources
Astronomy
Technology/Structural Engineering
Agriculture
Biology/Genetics
Social Sciences/Linguistics
Physics
Earth Sciences
Math
Chemistry

#data
47
45
42
24
24
19
16
15
15
11
10
6

We describe an entire procedure of our clustering algorithm in Algorithm 1.
IV. E XPERIMENTS
We evaluated our proposed method using a Web document
dataset extracted from the Open Directory Project (ODP)1 .
The categories we used are summarized in Table I. They are
all sub-categories of the “Science” top category. In each subcategory, there are some registered sites. We used top pagesof those sites as data. We removed tags and stop words fromoriginal web pages, and then made a tf-idf vector for eachdata.
We compared the following four methods.
• GCUT: This is our proposed method. We use the SDPA
package2 for solving the semi-deﬁnite programming.
We adopted the Euclid distance for the weight wij ofa graph edge in the maximum graph-cut problem.
• CKM: This is the COP-Kmeans constrained clustering
algorithm proposed by Wagstaff [7]. We used ten seeds
for the k-means and took the average of those results.
• ITML: This is a state of the art metric learning (Information Theoretic Metric Learning) method proposed
by Jain [8]. We used improved online version of thismethod because it was too difﬁcult to tune parameters
and thereby obtain stable results with the original batch
version. We changed the learning parameter η from−pk0 log(pk0 ) − pk1 log(pk1 )

k=1(i, j) represents the partitioning boundary. If we partition the above aligned matrix in the boundary between
i’s row and j’s row (i.e., also in the boundary of i’s
column and j’s column ), there are four partitioned
areas in the matrix. pk0 and pk1 are the probabilities of
0 and 1, respectively, that appears in the area k. Thus,F (i, j) is the sum of the entropy in four areas whenpartitioned between ith and jth row (and column). The
more clearly partitioned, F (i, j) becomes lower.
5) Determine the boundary at the lowest F (i, j).
Figure 2 illustrates this procedure. The ﬁgure shows thecase of two class clustering. The clusters are made by theboundary between 0 and 1 in the matrix.
This is a heuristic method because the original problem is
a combinatorial one and practically intractable. There is no
guarantee for obtaining global optimum. However, experimentally it works well, as described in the next section.

1 http://www.dmoz.org/
2 http://sdpa.indsys.chuo-u.ac.jp/sdpa/

128

 

 








 


$

$

$

$

$

$







$





$




             







 



$

$

 

$

$




$



$
$

$ $          !"#  !"# (a) Category 1∼4(b) Category 1∼8
Figure 3.

$$ $          !"# (c) Category 1∼12

Results

0.1∼0.9 with 0.1 steps and selected the best results
for the evaluation. The clustering is done by a normal
k-means algorithm. We used ten seeds for the k-means
and took the average of those results.
• SDPKKM: We also compared the method proposed by
Li or Hoi [4], [5], which has similar SDP formalizationof the problem to ours but there is a big difference
for the use of the solution matrix. We adopted the theinnner product of the feature vector i and j for theweight wij of a graph edge used during the kernel
matrix learning because it was too difﬁcult to tune theradius parameter for the Gaussian kernel. The clustering
is done by a conventional kernel k-means algorithm. We
used ten seeds for the k-means and took the average of
those results.
We use normalized mutual information (NMI) to measure
the clustering accuracy.
Figure 3 shows the results. The horizontal axis is thenumber of constraints and the vertical axis is the valueof normalized mutual information (NMI). We increase thenumber of must-link constraints from 0 to 500, which is
randomly selected. We tested each method with ten different
sets of constraint and calculate those average for the results
at each number of constraint.
We changed the number of categories to test as shownin the ﬁgure. Though SDPKKM and CKM showed comparable performance in Figure 3 (a) and (c) respectively, ourproposed method mostly outperformed other methods in any
category set.

method like spectral clustering and more appropriate SDP’s
solution matrix utilization compared with other SDP-based
methods. Results showed that our proposed clustering
method constantly outperformed conventional methods andutilized constraints effectively.
The advantages of our proposed clustering is efﬁciency,
especially in the case of small number of constraints. Thus
we are planning to apply this clustering method to interactive(Web) clustering with GUI [6].

V. C ONCLUSIONSIn this paper, we proposed a constrained clustering methodthat is based on a graph-cut problem formalized by semideﬁnite programming and deterministic iterative two-classpartitioning approach. While graph-cut based clustering
is a particularly promising way to improve conventional
techniques like k-means method, few methods have been
proposed, which can naturally incorporate constraint likemust-link and cannot-link.
Our method has the advantages of more convenient constraint incorporation compared to other graph-cut based[6] M. Okabe and S. Yamada, “An interactive tool for humanactive learning in constrained clustering,” Journal of Emerging
Technologies in Web Intelligence, vol. 3, no. 1, pp. 20–27,
2011.

R EFERENCES[1] O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised
Learning. The MIT Press, 2006.
[2] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing semisupervised clustering: A feature projection perspective,” in Proceedings of the 13th International Conference on Knowledge
Discovery and Data Mining, 2007, pp. 707–716.
[3] S. X. Yu and J. Shi, “Segmentation given partial grouping constraints,” IEEE Transactions on Pattern Analysis and MachineIntelligence, vol. 26, no. 2, pp. 173–183, 2004.
[4] Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation
by semideﬁnite programming for semi-supervised classiﬁcation,” in Proceedings of the 25th international conference on
Machine learning, 2008, pp. 576–583.
[5] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametrickernel matrices from pairwise constraints,” in Proceedings ofthe 24th international conference on Machine learning, 2007,
pp. 361–368.

[7] K. Wagstaff and S. Roger, “Constrained k-means clusteringwith background knowledge,” in Proceedings of the 18th
International Conference on Machine Learning, 2001, pp. 577–
584.
[8] P. Jain, B. Kulis, I. S. Dhillon, and K. Grauman, “Online metriclearning and fast similarity search,” in Proceedings of Neural
Information Processing Systems, 2008, pp. 761–768.

129