Appendix D
Signed normalized
Laplacian L sns clustering
Let us start with the case of SNScut and k = 2. Our goal is to solve the optimization
problem:
min
A⊂V
SNScut(A, A).
For a subset A ⊂ V , let u be the vector (u 1 , . . . , u n ) ∈ R n with entries:
u i =





vol(A)/vol(A) if v i ∈ A
−
vol(A)/vol(A) if v i ∈ A
Using the defined vector u, the SNScut objective function can be seen to be
equivalent to the normalized signed Laplacian L sns :
u
(D
+ − D
− −W )u =
1
2
n
∑
i, j=1
w i j (u i − u j )
2
=
1
2 ∑
i∈A, j∈A
w i j


vol(A)
vol(A)
+
vol(A)
vol(A)


2
+
1
2 ∑
i∈A, j∈A
w i j

 −
vol(A)
vol(A)
−
vol(A)
vol(A)


2
=
cut
+ (A, A) − cut
− (A, A)
vol(A)
vol(A)
+
vol(A)
vol(A)
+ 2
=
cut
+ (A, A) − cut
− (A, A)
vol(A) + vol(A)
vol(A)
+
vol(A) + vol(A)
vol(A)
=vol(V ) ∗ SNScut(A, A)
Additionally, we have
n
∑
i=1
d i u
2
i = vol(A)
vol(A)
vol(A)
+ vol(A)
vol(A)
vol(A)
= vol(V ).
177