178
Appendix D. Signed normalized Laplacian L sns clustering
Furthermore, it is provable that Du ⊥ 1.
Thus, R L sns (u) = SNScut(A, A). In other words, the problem of minimizing
SNScut(A, A) can be equivalently rewritten as: min
A⊂V
R L sns (u).
We can relax the problem by taking an arbitrary real-valued vector f :
min
f ∈R n
R L sns ( f ).
The solution of this problem is the eigenvector corresponding to the smallest eigenvalue of L sns , or equivalently the generalized eigenvector of (D + − D − − W ) f =
λ D f .
As before, the smallest eigenvector is a real-valued solution rather than a discrete indicator vector, but standard approaches can be used to turn this into a clustering.
The relaxation of the minimization SNScut in a general case of k > 2 follows
in a similar way. 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/
vol(A) if v i ∈ A
0
otherwise
(i = 1, . . . , n; j = 1, . . . , k).
As before, we see that
h
i (D
+ − D
− −W )h i =
cut + (A i , A i ) − cut − (A i , A i )
vol(A i )
,
h
i (D
+ − D
− −W )h i =
H
(D
+ − D
− −W )H
ii
,
and h
i Dh i = 1, H DH = I.
Combining those facts, we get
SNScut(A 1 , ..., A k ) =
k
∑
i=1
h
i (D
+ − D
− −W )h i
= Tr
H
i (D
+ − D
− −W )H
,
where Tr denotes the trace of a matrix. As before, we relax the problem of minimizing SNScut(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
R L sns (F)
s.t. F
DF = I.
Substituting F = D
−1/2 T , we obtain:
min
T ∈R n∗k
Tr
T
D
−1/2 (D
+ − D
− −W )D
−1/2 T
s.t. T
T = I.