182
Appendix E. Signed normalized Laplacian L bns clustering
Again we can relax the problem by taking an arbitrary real-valued vector f :
min
f ∈R n
R L bns ( f ).
The solution of the minimization problem is the eigenvector corresponding to the
smallest eigenvalue of L bns , or equivalently the generalized eigenvector of (D + −
W ) f = λ D f .
For the case of finding k > 2 clusters, we use the same indicator matrix H
defined in Appendix D. We get:
h
i (D
+ −W )h =
cut + (A i , A i ) − cut − (A i , A i ) + vol − (A i )
vol(A i )
,
h
i (D
+ −W )h =
H
i (D
+ −W )H
ii
,
and h
i Dh i = 1, H DH = I.
Combining those facts, we get
BNScut(A 1 , ..., A k ) = Tr
H
i (D
+ −W )H
.
Again we use an arbitrary real-valued matrix F ∈ R n∗k . Then the relaxed problem
becomes:
min
F∈R n∗k
R L bns (F)
s.t. HD
H = I.
The minimization problem is solved by choosing F as the first k smallest eigenvectors of the Laplacian matrix L bns as columns.
Appendix E. Signed normalized Laplacian L bns clustering
Again we can relax the problem by taking an arbitrary real-valued vector f :
min
f ∈R n
R L bns ( f ).
The solution of the minimization problem is the eigenvector corresponding to the
smallest eigenvalue of L bns , or equivalently the generalized eigenvector of (D + −
W ) f = λ D f .
For the case of finding k > 2 clusters, we use the same indicator matrix H
defined in Appendix D. We get:
h
i (D
+ −W )h =
cut + (A i , A i ) − cut − (A i , A i ) + vol − (A i )
vol(A i )
,
h
i (D
+ −W )h =
H
i (D
+ −W )H
ii
,
and h
i Dh i = 1, H DH = I.
Combining those facts, we get
BNScut(A 1 , ..., A k ) = Tr
H
i (D
+ −W )H
.
Again we use an arbitrary real-valued matrix F ∈ R n∗k . Then the relaxed problem
becomes:
min
F∈R n∗k
R L bns (F)
s.t. HD
H = I.
The minimization problem is solved by choosing F as the first k smallest eigenvectors of the Laplacian matrix L bns as columns.