Appendix C
Signed unnormalized
clustering
Let us start with the case of k = 2. Our goal is to solve the optimization problem:
min
A⊂V
SRcut(A, A).
For a subset A ⊂ V , let u be the vector (u 1 , . . . , u n ) ∈ R n with entries:
u i =





|A|/|A| if v i ∈ A
−
|A|/|A| if v i ∈ A
Using the defined vector u, the SRcut objective function can be seen to be equivalent
to the unnormalized signed Laplacian L sign :
u
L sign u =
1
2
n
∑
i, j=1
w i j (u i − u j )
2
=
1
2 ∑
i∈A, j∈A
w i j


|A|
|A|
+
|A|
|A|


2
+
1
2 ∑
i∈A, j∈A
w i j

 −
|A|
|A|
−
|A|
|A|


2
=
cut
+ (A, A) − cut
− (A, A)


|A|
|A|
+
|A|
|A|


2
=
cut
+ (A, A) − cut
− (A, A)
|A|
|A|
+
|A|
|A|
+ 2
=
cut
+ (A, A) − cut
− (A, A)
|A| + |A|
|A|
+
|A| + |A|
|A|
=|V | ∗ SRcut(A, A)
175