176
Appendix C. Signed unnormalized clustering
Additionally, we have
n
∑
i=1
u
2
i = |A|
|A|
|A|
+ |A|
|A|
|A|
= n.
Furthermore, it is provable that u ⊥ 1.
Thus, R L sign (u) = SRcut(A, A). In other words, the problem of minimizing
SRcut(A, A) can be equivalently rewritten as: min
A⊂V
R L sign (u).
We can relax the problem by taking an arbitrary real value vector f :
min
f ∈R n
R L sign ( f ),
s.t. f ⊥ 1; || f || =
√
n.
The solution of this problem is the eigenvector corresponding to the smallest eigenvalue of L sign .
The smallest eigenvector is a real-valued solution rather than a discrete indicator vector. The simplest way to partition a graph using such an eigenvector is to use
the sign of each entry value. A more sophisticated partition can be obtained by using
any standard clustering algorithm — k-means has often been used.
The relaxation of the minimization SRcut in a general case of k > 2 follows
a similar principle. We define the indicator matrix H = (h 1 , . . . , h k ) ∈ R n∗k , where
each column vector h j with entries
h i, j =
1/
|A| if v i ∈ A
0
otherwise
(i = 1, . . . , n; j = 1, . . . , k).
As before, we see that
h
i L sign h i =
cut + (A i , A i ) − cut − (A i , A i )
|A i |
,
h
i L sign h i =
H
L sign H
ii
,
and h
i h i = 1, H H = I.
Combining those facts, we get
SRcut(A 1 , ..., A k ) =
k
∑
i=1
h
i L sign h = Tr(H
i L sign H),
where Tr denotes the trace of a matrix. As before, we relax the problem of minimizing SRcut(A 1 , ..., A k ) by allowing matrix F to take arbitrary real values F ∈ R n∗k .
The relaxed problem becomes:
min
F∈R n∗k
T R(F
L sign F),
s.t. F
F = I.
This is the standard form of a trace minimization problem, and it can be solved
by choosing F as the k smallest eigenvectors of the Laplacian matrix L sign as columns
[100]. Clustering methods can then be applied to (some of) the columns to get a
discrete partition as before.
Appendix C. Signed unnormalized clustering
Additionally, we have
n
∑
i=1
u
2
i = |A|
|A|
|A|
+ |A|
|A|
|A|
= n.
Furthermore, it is provable that u ⊥ 1.
Thus, R L sign (u) = SRcut(A, A). In other words, the problem of minimizing
SRcut(A, A) can be equivalently rewritten as: min
A⊂V
R L sign (u).
We can relax the problem by taking an arbitrary real value vector f :
min
f ∈R n
R L sign ( f ),
s.t. f ⊥ 1; || f || =
√
n.
The solution of this problem is the eigenvector corresponding to the smallest eigenvalue of L sign .
The smallest eigenvector is a real-valued solution rather than a discrete indicator vector. The simplest way to partition a graph using such an eigenvector is to use
the sign of each entry value. A more sophisticated partition can be obtained by using
any standard clustering algorithm — k-means has often been used.
The relaxation of the minimization SRcut in a general case of k > 2 follows
a similar principle. We define the indicator matrix H = (h 1 , . . . , h k ) ∈ R n∗k , where
each column vector h j with entries
h i, j =
1/
|A| if v i ∈ A
0
otherwise
(i = 1, . . . , n; j = 1, . . . , k).
As before, we see that
h
i L sign h i =
cut + (A i , A i ) − cut − (A i , A i )
|A i |
,
h
i L sign h i =
H
L sign H
ii
,
and h
i h i = 1, H H = I.
Combining those facts, we get
SRcut(A 1 , ..., A k ) =
k
∑
i=1
h
i L sign h = Tr(H
i L sign H),
where Tr denotes the trace of a matrix. As before, we relax the problem of minimizing SRcut(A 1 , ..., A k ) by allowing matrix F to take arbitrary real values F ∈ R n∗k .
The relaxed problem becomes:
min
F∈R n∗k
T R(F
L sign F),
s.t. F
F = I.
This is the standard form of a trace minimization problem, and it can be solved
by choosing F as the k smallest eigenvectors of the Laplacian matrix L sign as columns
[100]. Clustering methods can then be applied to (some of) the columns to get a
discrete partition as before.