A Spectral Clustering Approach to Optimally Combining
Numerical Vectors with a Modular Network
Motoki Shiga

Bioinformatics Center
Kyoto University
Gokasho Uji 611-0011, Japanshiga@kuicr.kyotou.ac.jp

Ichigaku Takigawa

Bioinformatics Center
Kyoto University
Gokasho Uji 611-0011, Japan

takigawa@kuicr.kyotou.ac.jp

Hiroshi Mamitsuka

Bioinformatics Center
Kyoto University
Gokasho Uji 611-0011, Japanmami@kuicr.kyotou.ac.jp

ABSTRACT

General Terms

We address the issue of clustering numerical vectors with a
network. The problem setting is basically equivalent to constrained clustering by Wagstaﬀ and Cardie [20] and semisupervised clustering by Basu et al. [2], but our focus is
more on the optimal combination of two heterogeneous data
sources. An application of this setting is web pages which
can be numerically vectorized by their contents, e.g. term
frequencies, and which are hyperlinked to each other, showing a network. Another typical application is genes whose
behavior can be numerically measured and a gene network
can be given from another data source. We ﬁrst deﬁne a
new graph clustering measure which we call normalized network modularity, by balancing the cluster size of the original modularity. We then propose a new clustering method
which integrates the cost of clustering numerical vectors
with the cost of maximizing the normalized network modularity into a spectral relaxation problem. Our learning algorithm is based on spectral clustering which makes our issue
an eigenvalue problem and uses k-means for ﬁnal cluster assignments. A signiﬁcant advantage of our method is that
we can optimize the weight parameter for balancing the twocosts from the given data by choosing the minimum total
cost. We evaluated the performance of our proposed method
using a variety of datasets including synthetic data as well
as real-world data from molecular biology. Experimental results showed that our method is eﬀective enough to havegood results for clustering by numerical vectors and a network.

Algorithms and Experimentation

Categories and Subject Descriptors
H.2.8 [Database Management]: Database Applications—
Data mining; I.5.3 [Pattern Recognition]: Clustering—
Algorithms

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
KDD’07, August 12–15, 2007, San Jose, California, USA.
Copyright 2007 ACM 978-1-59593-609-7/07/0008 ...$5.00.

Keywords
Network modularity, spectral clustering, heterogeneous data
sources, k-means, eigenvalue problem

1. INTRODUCTION
Clustering, a major research subject in data mining, hasbeen successfully applied to a wide variety of areas in thereal world. In this paper, we address the issue of clustering numerical vectors with a network. This is a general
setting which can be found in a lot of applications and basically equivalent to constrained clustering by Wagstaﬀ andCardie [20] and semi-supervised clustering by Basu et al. [2],but our focus is more on the optimal combination of two heterogeneous data sources, numerical vectors and a network.
A typical application is web pages. This case, web pages
will be clustered by their contents, say term frequencies,
based on the assumption that if the contents of a page arevery similar to those of another, these pages can be in thesame cluster. In contrast, web pages are linked together,
forming a network in which nodes and edges correspond to
web pages and hyperlinks between them, respectively, andcan be clustered based on the hyperlink connectivity. Clustering web pages based on hyperlinks is exactly graph partitioning. Standard criteria for graph partitioning are ratio
cut [8] and normalized cut [15]. Simply speaking, these criteria are to minimize the number of inter-cluster edges relevant to the size of a cluster. The number of inter-cluster
edges which is called graph min-cut is to check the partitioning performance while the size of a cluster is to avoid asmall cluster which might be generated by outliers. In otherwords, these criteria are obtained by normalizing the graphmin-cut by the cluster size. Given a network, minimizing
normalized cut (or ratio cut) is a trace optimization problem
which is NP-hard. Thus usually this problem is converted
by spectral relaxation into an optimization problem witha constraint which can be solved by Lagrange multipliers,
and the solution is given by an eigenvalue problem. This iscalled spectral graph clustering which is diﬃcult to assign acluster label to each node deﬁnitely. Thus usually k-means
is ﬁnally applied to cluster assignments using the resultant
eigenvectors.
In the problem setting of graph partitioning, a numericalweight can be attached to each edge of a given graph, andyou may think that the similarity between two web pages
can be a weight for the hyperlink between them. However,
we assume that a given graph and a given set of numerical vectors are independently observed. This assumption isnatural. For example, the contents of web pages and theirlinks are independently generated. More concretely, there
is a case that two web pages are very similar to each other,even if there are no links between them. Thus we note thatour problem cannot be solved directly by using an existinggraph partitioning method only.
Another application is genes. Genes are expressed andfunction in a cell. Currently the quantitative expressionof thousands of genes can be measured simultaneously byusing the latest technology in genetic engineering, called
cDNA microarray. We can have a numerical vector (generally called a proﬁle) for each gene by repeating the experiment of cDNA microarray. However cDNA microarray data
is very noisy and unreliable. Thus naturally we often need
another data source in clustering genes, since precise geneclustering is important in predicting gene function [16]. We
can have more reliable information on genes as a gene network, although they are conﬁned to relatively well-studied
genes. For example, literature information provides us withthe co-occurrence frequencies of genes in medical documents
which can be turned into a network of genes by setting a
cut-oﬀ value against the frequencies. Similarly, metabolicor gene regulatory networks which are generated from literature are much more reliable than microarray data.
A potential approach for our problem setting would be
to integrate the two data sources, numerical vectors anda network. A typical example of this direction is semisupervised clustering based on a hidden Markov random
ﬁeld (HMRF) [2]. Semi-supervised clustering by HMRF
is clustering numerical vectors by minimizing the objectivefunction containing squared Euclidean distance as well as
weighted network constraints. This method was extended
to a more general framework in which the objective function can be expressed as a trace optimization problem forwhich an eﬃcient weighted kernel k-means algorithm was
proposed [11]. This work is based on the idea that minimizing the cost (or the objective function) of semi-supervised
clustering by HMRF can be a trace optimization problem,
which is true of minimizing the objective function of theweighted kernel k-means and more generally, minimizing agraph cut criterion such as normalized cut or ratio cut [3].
This work inspired us to combine numerical vectors witha network, but we note that our criterion for graph partitioning is clearly diﬀerent from that in [11] and our focus is
more on optimally combining the two data sources in termsof clustering.
Recent analysis on networks in the real-world data haverevealed that they have some common global characteristics
such as small-world phenomena [21], scale-free property [1],self-similarity [17] and hierarchical modularity [14]. We can
expect that the performance of clustering in our problem setting might be improved by using some global network property than the vicinity information like the Markov property.
In light of the above, we propose a new method for clustering numerical vectors with a network. We focus on network
modularity, a global feature found in a lot of real-world networks such as gene networks [14] and must be a powerful
criterion for clustering by the graph connectivity. The orig-

inal network modularity [13, 7, 6] is, intuitively, the numberof intra-cluster edges minus the square of the number ofinter-cluster edges. That is, this measure is given by using
only the edges of a graph and is not balanced by the cluster size. Thus we ﬁrst deﬁne normalized network modularity
which is obtained by dividing the original network modularity by the cluster size. We then integrate the normalized
network modularity with the cost of clustering numerical
vectors into the framework of a trace optimization problem.
Our clustering algorithm is based on spectral clustering bywhich our issue is relaxed into an eigenvalue problem andthe ﬁnal clusters are assigned by k-means clustering algorithm from the resultant eigenvectors. We stress that ourwork is an approach for clustering with not only numerical
vectors but the network modularity. A signiﬁcant merit ofour method is that we can optimize the weight parameterfor balancing the two data sources by choosing that which
minimizes the total cost.
We evaluated the performance of our method using three
types of datasets including both synthetic and real-world
data. Our ﬁrst dataset was synthetic both in numerical
vectors and a network. Numerical vectors were generated
randomly according to a mixture of von Mises-Fisher distributions, and a network was generated by selecting node pairs
randomly. We conﬁrmed the eﬀectiveness of our method bychecking normalized mutual information (NMI), a measure
to check the performance of clustering methods, and the total cost of clustering, with varying the value of the weightparameter for balancing the two data sources. In particular,
we found that NMI was mostly maximized at the weightparameter value which minimized the total cost, meaningthat our strategy of choosing the weight parameter valueof the minimum total cost worked successfully. The second
dataset was synthetic numerical vectors and a real metabolic
network having the scale-free property and unbalanced cluster sizes. From the experimental results on this dataset, we
showed that our method of optimally combining numerical
vectors with a given network worked favorably against evena real scale-free network with unbalanced cluster sizes. The
third dataset was real microarray expression proﬁles corresponding to numerical vectors and the real gene network
used in the second dataset. We note that gene expression
measured by microarray is heavily noisy and unreliable while
the network we used is from a database which is manuallycurated and trustworthy. Interestingly the resultant weightparameter value was extremely biased to the network information, being consistent with the above reliability fact of
the two input data sources.

2. METHOD
2.1 Preliminaries and Notations
We describe the notations that will be used throughout
this paper.
Let N be the number of given numerical vectors (datapoints). Let E be the N × N matrix whose entries are allone. Let X := (x1 , · · · , xN ) be given numerical vectors.
Each xn has p entries, and let xn (i) be the i-th
entry of xn .
pP
p2
Let X̄ := (x̄1 , x̄2 , . . . , x̄N ) where x̄n := xn /i=1 xn (i) .
T
Y = X̄ X̄. Let G be a given network with N nodes
and edges. Let W ∈ N×N be a non-negative, symmetric matrix whose (i, j) entry, wij is a non-negative weightbetween nodes i and j. If there is no edge between nodes
i and j, wij is zero. We note that in our problem setting,
W is an input having all information on a given graph G
and is often called a weight matrix or an aﬃnity matrix.
Let W̄ be a matrix whose (i, j) entry w̄ij satisﬁes thatPw̄ij = wij / N
j=1 wij . Let D d be a N × N diagonal maPtrix whose (i, i) entry di satisﬁes that di = N
j=1 wij . Let
D := dT d where d := (d1 , · · · , dN ). Let M be a matrix
which satisﬁes M := D−1
d W.
Let K be the number of clusters which is an input. Let I K
be the identity matrix of size K. Let Z := (z 1 , · · · , z K ) bean unsigned cluster assignment in which z Tk = (zk,1 , · · · , zk,N )where zk,n (∈ {0, 1}) is 1 if xn is in cluster k, otherwise zero.
Z̃ := √ ZT . Let — := (—1 , · · · , —K ) where —k be the repZ Z
resentative (or the cluster center) of cluster k. Let Zk be
a set of nodes in a given graph (or numerical vectors) incluster k, and let |Zk | be the number of all nodes in clusdiagonal
ter k. Z := ∪K
k=1 Zk . Let V be a P
P matrix whose(k, k) entry is |Zk |. L(Zk , Zk ) := i∈Zk j∈Z  wij , andk
L := L(Z, Z).
Let J be a cost of clustering numerical vectors X (or/and
nodes in network G). Let ω be a numerical parameter whichtakes a value between zero and one, and balances the twodata sources, i.e. numerical vectors X and network G.

2.2 k-means
We ﬁrst brieﬂy review the k-means clustering algorithm
which is widely used in a lot of applications. The cost (orthe objective function) of the k-means algorithm is given as
follows:
Jnum (X, Z; —) =

K
1 XX

N

Dist(xi , —k ),——————————————————————–
Input : X, K, Z (0) , —(0)Output : Z, —, J
k-means (X, K, Z (0) , —(0) )1: Z ← Z (0)√, — ← —(0)2: X̄ ← X/ X T X
3: while J(X̄, Z; —) is not converged do
P
(t+1)
4:
—k
← 1(t)(t) x̄j (k = 1, · · · , K)
j∈Z
|Zk |

k

5:
Z (t+1) ← arg minZ J(X̄, Z; —(t+1) )6:
Z ← Z (t+1) , — ← —(t+1) , J ← J(X̄, Z; —)7: end while——————————————————————–
Figure 1: Pseudocode of k-means.
The numerator which is common to the above two cuts is theso-called graph min-cut. If we use the graph min-cut only,
the clustering result is very sensitive to outliers. That is,a small cluster might be formed, if this cluster is relatively
isolated from other nodes. So we need to normalize thegraph min-cut by the number of nodes (ratio cut) or the
total weight (normalized cut) in each cluster.
We can see that the above criteria can be rewritten as
follows:
X z T (Dd − W )z kk.
Ratio Cut:z Tk z kk
Normalized Cut:

where Dist(xi , —k ) is a distance between numerical vector
xi and cluster representative —k of cluster k. We can use
any distance such as Euclidean distance, cosine similarity
and 1−Pearson correlation coeﬃcient. In our experiments,
we used cosine similarity which is used for clustering highdimensional data such as text documents [25]:!
1
xTn —kDist(xi , —k ) =.
1− p
2xTn xnkk(1)

k=1 i∈Zk

X z T (Dd − W )z k
z Tk Dc z k.

Finding a set of clusters which minimizes this criterion
is an NP-hard problem, and we then solve this problem byrelaxing the discrete cluster indicator matrix to a real valued
one. We can then have the following optimization problem:Tminimizetr(Z̃ (Dd − W )Z̃)subject toZ̃ Z̃ = I K . (Ratio Cut)T

T(Z̃ D d Z̃ = I K . (Normalized Cut))

2.3 Maximizing Normalized Network Modularity

By using Lagrange multipliers, we can easily ﬁnd that thesolution of this optimization can be an eigenvalue problem.
In a standard manner of spectral clustering, after solving
the eigenvalue problem, we ﬁrst select the resultant K − 1eigenvectors with the minimum eigenvalues. Then, since wecannot directly assign a cluster label to each numerical vector (or each node in a given graph) by the resultant eigenvectors, we apply the k-means clustering algorithm to theselected K − 1 eigenvectors after their normalization.

2.3.1 Spectral Graph Partitioning

2.3.2 Maximizing Normalized Network Modularity
with Spectral Graph Partitioning

The k-means algorithm minimizes the cost of Eq. (1) byrepeating the following two steps alternately until convergence: 1) updating the cluster representative and 2) updating cluster labels. Figure 1 shows the pseudocode of the
k-means clustering algorithm.

We brieﬂy review k-way graph partitioning which divides
nodes of a given graph (network) into k clusters. The standard criteria to be minimized in k-way graph partitioning
are ratio cut and normalized cut which are given as follows:
X L(Zk , Z \ Zk )Ratio cut:
.
|Zk |
k
X L(Zk , Z \ Zk )Normalized cut:.
L(Zk , Z)k

Network modularity is originally deﬁned as follows [6]:
(
„
«2 )
K
X
gk (G)
2ek (G)
Q(G) =
,
(2)
−
L
L
k=1
where ek (G) is the number of edges in cluster k and gk (G)is the total sum of degrees over all nodes in cluster k. As
shown in the above, the weight attached to each edge was notconsidered in the original deﬁnition of network modularity.

Hereafter, we incorporate the edge weight into the network
modularity, meaning that the binary deﬁnition on each edge
is turned into a numerical one. We note that the propertyof the network modularity is totally kept in this extension.
Eq. (2) can then be rewritten by using only L as follows:
(
„
«2 )
K
X
L(Zk , Z)
L(Zk , Zk ).
−Q(W ) =
L
L
k=1

This measure is deﬁned by the (weighted) number of edges
only, meaning that the original modularity considers thenumber of edges only. More importantly, the original network modularity is not balanced by the cluster size, meaningthat a cluster might become small when aﬀected by outliers.
Thus we deﬁne the new measure which we call normalized
network modularity whose cost (or the objective function) is
given as follows:
(„
)
«2
K
X
L(Zk , Zk )N
L(Zk , Z)−.
Jnet (W , Z) =
|Zk |
L
L
k=1
This equation indicates that the larger negative value of thiscost a clustered network has, the higher normalized network
modularity this network has. The problem of ﬁnding theset of clusters which minimizes this cost is NP-hard. Wethen apply the spectral clustering approach to minimize thecost of normalized network modularity, J(W , Z). In the following derivation, we partly borrow the idea of the spectral
graph clustering by White and Smith which was developed
for the original network modularity [22].
We can ﬁrst modify the problem of minimizing J(W , Z)
into the problem of minimizing the following trace:`´ !
Z T N L12 D − L1 W Z
Jnet (W , Z) = tr
. (3)
ZT Z
As shown in the spectral graph clustering using ratio (or normalized) cut, matrix Z must satisfy the following constraint
since each node falls into one cluster only:
ZT Z = V .

T

Z̃ Z̃ = I K .

Figure 2: Pseudocode of spectral clustering for normalized network modularity.

This modiﬁcation allows M to be a very sparse matrix,
meaning that we can reduce the computational cost of solving the eigenvalue problem in Eq. (5).
After solving Eq. (5), we have the resultant K − 1 eigenvectors with the minimum eigenvalues. That is, we can haveN × (K − 1) matrix, H = (h1 , · · · , hK−1 ) where hi be thei-th eigenvector of the selected K − 1 eigenvectors. We thennormalize this matrix into N × (K −q1) matrix, H̄ in which
PK−1 2(n, k) entry h̄nk satisﬁes h̄nk = hnk /k=1 hnk where hnk
is (n, k) entry of H. This eigenmatrix H̄ can be an inputof k-means. Figure 2 shows the pseudocode of this process.

2.4 Proposed Algorithm for Optimally Combining Numerical Vectors with Normalized
Network Modularity
2.4.1 Spectral Clustering with Numerical Values anda Network
We describe our proposed algorithm for combining two
data sources: numerical vectors and a given weighted network.
We ﬁrst set the cost (the objective function) of clustering
numerical vectors as follows:
1 XX 1(1 − x̄Ti —k ),N
2i∈Z

Jnum (X̄, Z; —) =k=1

kwhere the cluster representative —k of cluster k is given as
follows:
1 X
x̄j
—k =
|Zk | j∈Zk

The solution can be found via Lagrange multipliers in thefollowing typical eigenvalue problem:
«
„
1
1
W
Z̃ = Z̃Λ,
D−
L2
L
where Λ is a diagonal matrix of Lagrange multipliers. Thiscan be further modiﬁed using W̄ , the normalized W , into:
«
„
1
1
(4)
W̄ − 2 E Z̃ = Z̃Λ.
L
L
When n → ∞, the second term of Eq. (4) approaches zero
faster than the ﬁrst term. In addition, we can approximateW̄ by D−1
d W . We then approximate Eq. (4) by the following simple eigenvalue problem:
M Z̃ = Z̃Λ.

1: Compute D d from W .
2: M ← D−1
d W
3: Compute H of M .
4: Normalize H into H̄.
5: [Z, —, J] ← k-means(H̄, K, Z (0) , —(0) )——————————————————————–

K

We can then replace Z with Z̃ and rewrite the trace optimization problem in the following by relaxing the discrete
cluster indicators into real-valued indicators:
« «
„
„
1
T
1
W
Z̃
D
−
minimizetr Z̃
L2
Lsubject to——————————————————————–
Input : W , K, Z (0) , —(0)Output : Z(5)

The cost of k-means can be rewritten as follows:”
1 XX“
1 − x̄Ti —k
2N k=1 i∈Z
k
0
1
K X
X
X
1
1
T
@1 − x̄ix̄j A
2N k=1 i∈Z|Zk | j∈Z
K

Jnum (X̄, Z)

=

=

k

=

1
1
−
2
2N

K
X
k=1

k

1 X X Tx̄ x̄j|Zk | i∈Z j∈Z ikk

and it can then be a trace optimization problem:„ T«
Z (2N )−1 Y Z
1Jnum (X̄, Z) = − tr
T
2
Z Z

(6)

We then combine the cost of clustering numerical vectors
which is shown in Eq. (6) with the cost of the normalized
network modularity which is given in Eq. (3), using ω forbalancing the two costs:
Jtotal (X̄, W , Z)
= ωJnet (W , Z) + (1 − ω)Jnum (X̄, Z)(`´ )Z T ωND − ωNW − 1−ω
Y Z
L
2N
L2
= tr
ZT Z
„
« ﬀ
j
ωN
T
ωN
1−ω
D
−
W
−
Y
Z̃
= tr Z̃
L2
L
2N
Finding a set of clusters minimizing the integrated cost isalso an NP-hard problem, and so we solve this problem byrelaxing discrete cluster indicators into real-valued ones. By
doing so, we can have the following optimization problem:
« ﬀ
j
„
ωN
T
1−ω
ωN
D
−
W
−
Y
Z̃
minimize
tr
Z̃
L2
L
2N
subject toTZ̃ Z̃ = I K(7)This optimization problem can be also turned by Lagrange
multipliers into the following eigenvalue problem for the total cost:
M ω Z̃ = Z̃Λ,

(8)

where
ωN
ωN
1−ω
D−
W −
Y.
L2
L
2N
Once we have the above eigenvalue problem, we can use
the same manner of clustering as done in spectral graph clustering. That is, given N × N matrix M , we can obtain the
resultant K − 1 eigenvectors with the minimum eigenvalues,
to generate N × (K − 1) matrix S = (s1 , · · · , sK−1 ) where
si is the i-th eigenvector of the selected K − 1 eigenvectors.
We then use the k-means clustering algorithm, after normalizing S into S̄ which is the N × (Kq− 1) matrix in which
PK−1 2(n, k) entry s̄nk satisﬁes s̄nk = snk /k=1 snk where snk
is (n, k) entry of S.
As we saw in spectral graph clustering, the constraint
given in Eq. (7) can be modiﬁed into another form. For
T
example, we can use Z̃ Dd Z̃ = I K which was used for normalized cut in graph partitioning. This case, M ω is given
as follows:ωN1−ω− 1 ωN−1
M ω = Dd 2 ( 2 D −W −Y )D d 2 .
LL
2N
We used this constraint in our experiments, since normalized cut is more often used in graph partitioning than ratio
cut. In addition, White and Smith [22] also used this modiﬁcation when they practically applied their spectral graphclustering with the original network modularity to the realworld datasets.
Mω =2.4.2 Estimating ω
The parameter ω depends on the spectral space which is
generated by combining the two data sources, meaning thatthe choice of ω will heavily aﬀect the clustering result. So
we propose a method to estimate the optimal ω value fromgiven two data sources. In this method, varying ω fromzero to one, we choose the ω which gives the minimum total
cost, Jtotal . Figure 3 shows the pseudocode of the wholeprocedure of our proposed algorithm.

——————————————————————–
Input : X, W , K, Z (0) , —(0)Output : Z√
1: X̄ ← X/ X T X
T
2: Y ← X̄ X̄
3: Compute D d and D from W
4: for ω = 0 to 11 do−−1
5:
M ω ← Dd 2 ( ωND − ωNW − 1−ωY )Dd 2 .
L
2N
L2
6:
Compute S of M ω .
7:
Normalize S into S̄.
8:[Zω , —ω , Jω ] ← k-means(S̄, K, Z (0) , —(0) )9: end for10: ωmin ← arg minω Jω
11: Z ← Zωmin——————————————————————–
Figure 3: Pseudocode of the proposed algorithm.

3. EXPERIMENTS
3.1 Dataset 1: Synthetic Numerical Vectors andSynthetic Random Network
3.1.1 Data
1. Synthetic Numerical Vectors: We ﬁrst assume
that numerical vectors are randomly generated according toa mixture of von Mises-Fisher distributions [12] in which
each component corresponds to a cluster:p(x) =KX

T

αk cp (κ)eκ—k x ,k=1

where αk (k = 1, · · · , K) are mixture proportions satisfying
Pthat K
k=1 αk = 1 and 0 ≤ αk ≤ 1, and cp (κ) is given as
follows:
cp (κ) =κp/2−1(2π)p/2 I

p/2−1 (κ),

where Ip/2−1 (κ) is the type 1 Bessel function of order pwhich is given as follows:Z
1 π κ cos t
Ip (κ) =ecos(pt)dt.
π 0Interested readers should refer [4] on the method for randomly generating numerical values according to this distribution. We used the following settings: K = 4, p = 3,T
αk = 0.25 (k =√ 1, . . . , 4), —1 = (0, 0, 1)T , —√2 = (0, 0, −0.5) ,TT33—3 = (−0.5, 2 , −0.5) , —4 = (−0.5, − 2 , −0.5) . Another parameter, κ which is called concentration parameter,
behaves like the inverse of the variance of numerical vectors
in a cluster. Thus numerical vectors which are generated
with a larger κ will be more concentrated on cluster representatives and be more easily clustered. Thus we changed
κ in our experiments to check the eﬀect of κ on clusteringresults.
2. Synthetic Random Network: To generate a network, we ﬁrst assigned a cluster label to each node. We
generated a network in which the number of nodes and thenumber of edges in each cluster are kept the same for all
clusters. Thus the generated network was deﬁned by threeparameters: Nv (the number of nodes in a cluster), Ne (the

1

0

0

0

-1
1

s3

1

s3

s3

1

-1
1
s2

1

0
0
-1

-1

s

-1
1
1

s 0

0

2

1

-1

(a)

-1

(b)

s

1

1

s2 0

0
-1

-1

s

1

(c)

Figure 4: Dataset 1: The distribution of eigenvectors sn (n = 1, . . . , 400) which are shown by four diﬀerent
symbols (◦, ∗, +, ) corresponding to four diﬀerent clusters at Nin = 250, κ = 5, (a) ω = 0 and J = 0.0932, (b)ω = 0.3 and J = 0.0538 and (c) ω = 1 and J = 0.0809.

total number of edges) and Nin (the number of edges in acluster) which is equal to 12 L(Zk , Zk ) (k = 1, · · · , K). We
then chose a value of Nv to generate a set of nodes andrandomly chose node pairs which are connected by edges tosatisfy the values of Ne and Nin . In Dataset 1, we used
Nv = 100 (meaning that the total number of nodes is 400)
and Ne = 1, 600, while Nin was changed to check how theclustering performance is aﬀected by Nin .

3.1.2 Performance Results
To evaluate our clustering results using true cluster labels,
we used normalized mutual information (NMI) [18] which
has been used in a lot of applications to measure the performance of clustering methods [24]. A larger NMI value indicates a better clustering result. Interested readers shouldsee [18] for the detail of NMI.
We ﬁrst checked the distribution of sn (n = 1, · · · , 400),
i.e. the resultant eigenvectors of the eigenvalue problem in
Eq. (8), when we ﬁxed κ = 5 and Nin = 250. Figure 4 shows
the three distributions of eigenvectors which are shown infour diﬀerent symbols (◦, ∗, +, ) corresponding to four different clusters, when ω was at 0, 0.3 and 1. This ﬁgure showsthat the distribution of eigenvectors changes with varying ω.
In particular, we can see that when ω = 0.3, the eigenvectors were separated most clearly among the three cases. In
fact, when ω=0, 0.3 and 1, J was 0.0932, 0.0538 and 0.0809,
respectively, indicating that eigenvectors at ω = 0.3 werethe most concentrated on the cluster representatives among
the three cases of ω.
We then checked the eﬀectiveness of our method of optimally combining two diﬀerent data sources by using the cost
J and NMI, when ω is changed. We used each data set of all
combinations of κ = 1, 5 and 50 and Nin = 250, 280 and 300.
Figure 5 shows J of all these cases, and Figure 6 shows NMI
of all these cases. From these ﬁgures, ﬁrst of all, we can seethat with increasing Nin ((a) → (b) → (c)), the modularity
became higher, resulting with decreasing the cost (J) andincreasing NMI. This might be clearer if we focus on the ωof one. On the other hand, we can see that with increasingκ (1 → 5 → 50), numerical vectors were more concentrated
on their cluster representatives, resulting with decreasing

the cost (J) and increasing NMI. This might be also clearer
if we focus on the ω of zero.
In all 18 curves in Figures 5 and 6, the best value is obtained when 0 < ω < 1, indicating that combining two data
sources improved the cost J and NMI of ω = 0 and ω = 1. In
particular, we emphasize that the ω value of the minimum
J was mostly consistent with that of the maximum NMI.
For example, when Nin = 250 and κ = 1, J was minimizedat ω = 0.5 and the maximum NMI was at ω = 0.4. Similarly, at κ = 5, the minimum J was at ω = 0.4 where themaximum NMI was obtained. This was true of Nin = 280
and κ = 1 where ω = 0.5 provided the best in both NMI
and J. These results imply that our method of selecting
ω worked eﬀectively for optimally combining numerical vectors with a given network. An interesting ﬁnding is that ina balanced case in which the cost (and NMI) of ω = 0 is
almost the same as that of ω = 1, the curve became concave(and convex for NMI), indicating that the minimum cost(and the maximum NMI) can be easily found. On the other
hand, in an unbalanced case such as κ = 1 and Nin = 310
in (c), the curve was not necessarily concave (and convex
for NMI), meaning that only one data source (i.e. network
information), is much more informative for clustering thanthe other (i.e. numerical vectors). This is natural, because
numerical vectors at κ = 1 were widely distributed, notconcentrating on the cluster representatives, and it would
be diﬃcult to do clustering by them, comparing to the caseof Nin = 310 where clustering could be relatively easy byusing network information only. Thus in such a case, ourmethod might choose ω = 1 (or ω = 0), but this would be
the right selection, since the NMI at ω = 1 (or ω = 0) must
be the maximum or very close to the maximum in this case.
Using the same parameter setting as that in Figure 6,
we ﬁnally checked NMI by repeating randomly generating
datasets 400 times and averaging the performance over them.
Figure 7 shows the averaged NMI obtained by this experiment. The curves in this ﬁgure were almost similar to thosein Figure 6, implying that our results were very stable. Totally we can say that our method optimally combined thetwo synthetic data sources.

Cost (J)

0.12

0.12

0.1

0.1

0.08

0.08

0.06

0.06

0.06

0.04

0.04

0.02

0.02

κ=1
κ=5
κ = 50

0.04
0.02
0
0

0.5

1

ω

0
0

(a)

0.12
κ=1
κ=5
κ = 50

0.5

0.08

1

ω

κ=1
κ=5
κ = 50

0.1

0
0

(b)

0.5

1

ω

(c)

NMI

Figure 5: Dataset 1: J at Nin = (a) 250, (b) 280 and (c) 310.

1

1

1

0.8

0.8

0.8

0.6

0.6
0.4

0.4

κ=1
κ=5
κ = 50

0.2
0
0

0.6

0.5

ω

κ=1
κ=5
κ = 50

0.2

1

0
0

(a)

0.5

ω

κ=1
κ=5
κ = 50

0.4
0.2
1

0

(b)

0.5

ω

1

(c)

Figure 6: Dataset 1: NMI at Nin = (a) 250, (b) 280 and (c) 310.

3.2 Dataset 2: Synthetic Numerical Vectors andReal Scale-free Network
3.2.1 Data
1. Synthetic Numerical Vectors: Numerical values ofa gene, such as gene expression, are usually measured experimentally, meaning that these values are noisy, comparing to
the network which we can derive from a curated database inmolecular biology1 . Thus in this experiment, we generated
synthetic numerical vectors to check the performance of our
method of combining two data sources.
As we used a real metabolic network of 636 Saccharomyces
cerevisiae genes (See below the way to generate this network.), we ﬁrst assigned a cluster label to each node of the
network in the following way: 1) We ﬁxed the number ofclusters and repeated running spectral graph clustering by
White and Smith [22] 1,000 times on the real metabolic network, measuring the original network modularity on the resultant clusters at each time. 2) Out of the 1,000 runs, wethen chose the clusters with the highest network modularity2 , and these clusters were used to assign a cluster label
1
We show this fact more clearly in the experiment using
Dataset 3.
2
We note that the clusters with the highest modularity can-to each node. That is, these clusters were used as standard
data for evaluation.
We then generated numerical vectors (corresponding tonodes in the metabolic network) in each cluster, assumingthat they can be generated according to a component of the
von Mises-Fisher distribution mixture as in Section 3.1.1.
We used the following settings: K = 10, p = 5, αk =0.1 (k = 1, · · · , 10), —1 = (1, 0, 0, 0, 0)T , —2 = (−1, 0, 0, 0, 0)T ,—3 = (0, 1, 0, 0, 0)T , —4 = (0, −1, 0, 0, 0)T , —5 = (0, 0, 1, 0, 0)T ,—6 = (0, 0, −1, 0, 0)T , —7 = (0, 0, 0, 1, 0)T , —8 = (0, 0, 0, −1, 0)T ,—9 = (0, 0, 0, 0, 1)T , —10 = (0, 0, 0, 0, −1)T . We changed κ
to check how clustering results are aﬀected by κ.
2. Real Metabolic Network: Metabolism is represented by a directed graph, called a metabolic pathway whichshows biochemical processes of synthesizing small molecules
in a cell. Each node is labeled by a chemical compound. A
directed edge from a node, say node A, to another, say nodeB, is a chemical reaction, meaning that the compound corresponding to node B is synthesized from that for node A, andeach edge is labeled by a (enzyme) gene which catalyzes thecorresponding chemical reaction. From a metabolic pathnot be obtained so easily by our method of ω = 1, since inspectral graph clustering, the ﬁnal solution is obtained byk-means and is always an approximation.

Average NMI

1

1

1

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

κ=1
κ=5
κ = 50

0.2
0
0

0.5

0.2
0
0

1

ω

0.5

ω

(a)

κ=1
κ=5
κ = 50

0.4

κ=1
κ=5
κ = 50

0.2

1

0
0

(b)

0.5

ω

1

(c)

Figure 7: Dataset 1: Average NMI over 400 replicates at Nin = (a) 250, (b) 280 and (c) 310.

1
0.15

0.1

0.9

κ = 102

κ = 103

NMI

Cost (J)κ = 100.8
κ = 100.7

0.05

κ = 10 2
κ = 10 3

0.6
0
0

0.5

ω

1

(a)

0

0.5

ω

(b)

Figure 8: Dataset 2: Cost (J) and NMI.

way which is stored in the KEGG (Kyoto Encyclopedia of
Genes and Genomes) database [10], we generated a networkby connecting two genes by an undirected edge, if they catalyze two neighboring chemical reactions in the metabolic
pathway. The generated network which we call metabolic
network had 636 nodes and 3,104 edges. Most importantly,
this network has two important network features: the scalefree property [1] as well as hierarchical network modularity [14].

3.2.2 Performance Results
We used NMI again to validate the clustering results obtained by our method, with the standard data for evaluation. Figure 8 (a) shows the total cost J with changing
ω, and Figure 8 (b) shows NMI with changing ω. The results we can derive from these ﬁgures were mostly consistent with those obtained by Dataset 1. For example, atκ = 102 and 103 where the distribution of numerical vectors
was relatively concentrated on their cluster representatives,the curves could be concave for J (and convex for NMI),
and the ω value of the minimum cost and the ω value of the
maximum NMI were easily found. Furthermore they were
mostly consistent with each other. In addition, at κ = 1
where numerical vectors were distributed broadly, the curve
was not necessarily a strong concave for the cost J (and con-1

vex for NMI), implying that this case, the network information would be more useful for clustering than the numerical
vectors. In fact, NMI at ω = 1 reached around 0.9, a very
high value, whereas that at ω = 0 stays at less than 0.6.
Figure 9 shows the clustering results obtained by our method
at three diﬀerent ω values when κ = 10. Ten diﬀerent colors
correspond to ten diﬀerent clusters. Figure 10 shows thetrue cluster labels we used for both evaluation and generating numerical vectors. From these ﬁgures, we can easily
see that the clustering result at ω = 0.5 was the most similar to the true cluster labels among the three networks in
Figure 9. For example, the center part of the true clusters
were colored orange and dark blue, and this was consistent
with the network at ω = 0.5 in Figure 9 (b). On the other
hand, this center part has a lot of diﬀerent colors at ω = 0
in Figure 9 (a) and is colored dark blue only at ω = 1 inFigure 9 (c).
From these results, we can say that our method worked
eﬀectively for Dataset 2 which contains a real metabolic network with the scale-free property as well as unbalanced cluster sizes.

3.3 Dataset 3: Real Numerical Vectors and Real
Scale-free Network
3.3.1 Data
1. Real Numerical Vectors: Microarray Gene Expression We used a microarray gene expression dataset [9]which has 300 expression proﬁles (numerical vectors) whilearound 200 missing values only. This dataset has been often
used in the literature of microarray expression analysis [26,23]. All missing values were interpolated by using the 10nearest least square method by [19].
2. Real Metabolic Network: We used the real metabolic
network in Dataset 2.

3.3.2 Performance Results
In order to evaluate the clustering result by our method,
we used ten categories in metabolism which were stored in
the KEGG database. At least one of the ten categories could
be assigned to each metabolic gene. We note that theseten categories are not deﬁned directly from the metabolic
pathways in the KEGG database, and so these ten clusters
cannot be identiﬁed by using the metabolic network in our

(a)

(b)

(c)

0.16

0.4

0.14

0.35

0.12

0.3

0.1

0.25

NMI

Cost (J)

Figure 9: Dataset 2: Clustered metabolic networks at κ = 10 and ω= (a) 0, (b) 0.5 and (c) 1.

0.08

0.2

0.06

0.15

0.04

0.1

0.02
0

0.2

0.4

ω

0.6

(a)

0.8

1

0.05
0

Proposed method
Normalized cut
Ratio cut

0.2

0.4

ω

0.6

0.8

(b)

Figure 11: Dataset 3: Cost (J) and NMI.

Figure 10: Dataset 2: True cluster labels.

experiment only. We then used NMI again to validate theperformance of our clustering result.
Figure 11 (a) shows the cost J of our method with changing ω. Figure 11 (b) shows NMI of our method with changing ω. The curves in these ﬁgures were not strong concave
for J (and convex for NMI), meaning that the two data
sources are heavily unbalanced as pointed out in the experimental results of Dataset 1 and Dataset 2. In fact, bylooking carefully, we can see that the minimum cost was ataround ω = 0.8 to 0.9 where the best NMI was obtained, andthe diﬀerence between the best NMI and NMI at ω = 1 wasinsigniﬁcant. Also Figure 11 (b) shows the averaged result
over 200 runs of each of the two spectral graph partitioning
methods using normalized cut and ratio cut. We note thatthese methods used graph information only, and the resultsof them are shown as dotted straight lines in the ﬁgure. Our
method signiﬁcantly outperformed these two methods evenat ω = 1, implying that normalized network modularity ismore eﬀective for clustering than normalized cut and ratiocut.
We repeated the same experiment replacing the above microarray dataset with datasets derived from a large microarray database [5], and found that the results were almost
similar to the above case. From this result, we can say thatthe metabolic network derived from a curated database ismore reliable in clustering metabolic genes than microarray
expression. This result is consistent with existing understanding on data reliability in molecular biology.
For Dataset-3, the ω for the minimum cost took a value
which was very close to one, around where NMI was maximum or very close to the maximum. Thus we think that
our method succeeded for this dataset. As well in Dataset-2,
our method worked favorably for optimally combining thereal metabolic network with more reliable numerical vectors.
Thus if we have more reliable numerical vectors on genes,

1the clustering result would be improved much more. Overall we can say that our method itself is very promising.

4.

CONCLUDING REMARKS

We have presented a new spectral approach to clustering
numerical vectors with a network. The focus of our method
was on network modularity, a key network property in clustering, and we deﬁned a new criterion, normalized network
modularity, for combining the two diﬀerent data sources in
the framework of spectral clustering. A signiﬁcant advantage of our method is that we can optimize the weight parameter for balancing the two data sources, i.e. numerical
vectors and a network. Also our algorithm is time-eﬃcient,and practical computation time was less than one minutefor any dataset in our experiment. Experimental results
obtained by using three diﬀerent types of datasets showedthat our method worked favorably for optimally combining
numerical vectors and a network.
In this paper, we have focused on two data sources, i.e.
numerical vectors and a network, both in methodology andexperiments. Our method can be easily extended to a moregeneral framework for combining multiple heterogeneous data
sources for clustering, and by doing so, the resultant clustering performance might be improved by adding anotherdiﬀerent data source. Thus interesting future work is to apply the proposed method to a variety of real-world datasets
to characterize more systematically under which the proposed method works well. And this would be performed by
not only two diﬀerent data sources but also more than twoheterogeneous data sources, say numerical vectors, a network and another diﬀerent type of dataset. It would also beinteresting to develop, in the context of clustering, a generalcriterion which can cover a lot of distances for numerical values as well as graph partitioning criteria such as normalized
cut, ratio cut and network modularity.

5.

ACKNOWLEDGMENTS

This work is supported in part by Bioinformatics Education Program ”Education and Research Organization for
Genome Information Science” and Kyoto University 21stCentury COE Program ”Knowledge Information Infrastructure for Genome Science” with support from MEXT, Japan.

6.

REFERENCES[1] A.-L. Barabási and A. Reka. Emergence of scaling in
random networks. Science, 286:509–512, 1999.
[2] S. Basu, M. Bilenko, and R. J. Mooney. A
probabilistic framework for semi-supervised clustering.
In KDD, pages 59–68, August 2004.
[3] I. S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means,
spectral clustering and normalized cuts. In KDD,
pages 551–556, 2004.
[4] I. S. Dhillon and S. Sra. Modeling data using
directional distributions. Technical Report TR-06-03,
University of Texas, Dept. of Computer Sciences, 2003.
[5] R. Edgar, M. Domrachev, and A. E. Lash. Gene
expression omnibus: NCBI gene expression andhybridization array data repository. NAR,
30(1):207–210, 2002.

[6] R. Guimera and L. A. Nunes Amaral. Functional
cartography of complex metabolic networks. Nature,433(7028):895–900, 2005.
[7] R. Guimera, M. Sales-Pardo, and L. A. N. Amaral.
Modularity from ﬂuctuations in random graphs andcomplex networks. Phys. Rev. E, 70:025101, 2004.
[8] L. Hagen and A. B. Kahng. New spectral methods forratio cut partitioning and clustering. IEEE TCAD,
11:1074–1085, 1992.
[9] T. R. Hughes et al. Functional discovery via acompendium of expression proﬁles. Cell,
102(1):109–126, 2000.
[10] M. Kanehisa et al. From genomics to chemical
genomics: new developments in KEGG. NAR,
34:D354–357, 2006.
[11] B. Kulis, S. Basu, I. Dhillon, and R. J. Mooney.
Semi-supervised graph clustering: A kernel approach.
In ICML, pages 457–464, 2005.
[12] K. V. Mardia and P. E. Jupp. Directional Statistics.
John Wiley & Sons, second edition, 2000.
[13] M. E. J. Newman and M. Girvan. Finding andevaluating community structure in networks. Phys.
Rev. E, 69:026113, 2004.
[14] E. Ravasz et al. Hierarchical organization ofmodularity in metabolic networks. Science,
297(5589):1551–1555, 2002.
[15] J. Shi and J. Malik. Normalized cuts and image
segmentation. IEEE PAMI, 22(8):888–905, 2000.
[16] M. Shiga, I. Takigawa and H. Mamitsuka. Annotating
gene function by combining expression data with amodular gene network. To appear in ISMB, 2007.
[17] C. Song, S. Havlin, and H. A. Makse. Self-similarity ofcomplex networks. Nature, 433:392–395, 2005.
[18] A. Strehl and J. Ghosh. Relationship-based clusteringand visualization for high-dimensional data mining.
INFORMS Journal on Computing, 15(2):208–230,
2003.
[19] O. Troyanskaya et al. Missing value estimation
methods for DNA microarrays. Bioinformatics,
17(6):520–525, 2001.
[20] K. Wagstaﬀ and C. Cardie. Clustering withinstance-level constraints. In ICML, pages 1103–1110,
2000.
[21] D. J. Watts and S. H. Strogatz. Collective dynamics of’small-world’ networks. Nature, 393:440–442, 1998.
[22] S. White and P. Smyth. A spectral clustering
approach to ﬁnding communities in graphs. In SDM,
pages 76–84, 2005.
[23] L. F. Wu et al. Large-scale prediction ofsaccharomyces cerevisiae gene function using
overlapping transcriptional clusters. Nat. Genet.,
31(3):255–265, 2002.
[24] S. Zhong and J. Ghosh. A uniﬁed framework formodel-based clustering. JMLR, 4:1001–1037, 2003.
[25] S. Zhong and J. Ghosh. Generative model-based
document clustering: A comparative study. KAIS,
8(3):374–384, 2005.
[26] X. Zhou, M. C. Kao, and W. H. Wong. Transitive
functional annotation by shortest-path analysis of gene
expression data. PNAS, 99(20):12783–12788, 2002.