8.2. Unnormalized spectral Laplacians of signed graphs
101
group A i :
vol(A i ) = vol
− (A i ) + vol
+ (A i ).
Kunegis et al. define a signed ratio minimum cut corresponding to their Laplacian definition [48]:
RatioCut(A, A) = scut(A, A)
1
|A|
+
1
|A|
,
where scut(A, A) = 2cut + (A, A) +W − (A, A) +W − (A, A).
The minimum of the Rayleigh quotient R L can be viewed as a relaxation of
the minimization of RatioCut [48]. This objective function penalizes negative edges
within clusters, but it does so without any regard for the size of each cluster. It
seems natural that a large cluster ought to be “allowed” to contain relatively more
negative edges than a small one, so that a function like this might be more plausible
if the weights in scut were fractions of negative edges per cluster rather than simply
counts. Furthermore, this definition assumes only 2 clusters and it is problematic to
extend it to k clusters [17].
Instead, we define an unnormalized signed cut objective function by:
SRcut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) −W − (A i , A i )
|A i |
=
k
∑
i=1
cut + (A i , A i ) − cut − (A i , A i )
|A i |
The minimum of the SRcut function finds a solution with the fewest positive edges
and the most negative edges between groups. The value of SRcut could be negative.
Figure 8.2: Graph cuts of a sample graph
Both unnormalized cuts of signed graphs treat the positive edges in the same
way, but treat the negative edges differently. The RatioCut emphasizes minimizing
the total within-group negative edges. The SRcut maximizes the outgoing negative
edges from each group; this tends to create large groups when the sum of the positive
edge weights is greater than the sum of the negative edge weights between groups,
but small groups otherwise. For example, in Figure 8.2 the minimum cut of the
RatioCut is “Cut 1”, with no negative edge within groups. “Cut 2” is the result of
SRcut, with the node on the right side alone in a group. The question is which one is
the better cut? We argue that it is the second one, because the node on the right side
does not have any positive relationship to the nodes on the left.
101
group A i :
vol(A i ) = vol
− (A i ) + vol
+ (A i ).
Kunegis et al. define a signed ratio minimum cut corresponding to their Laplacian definition [48]:
RatioCut(A, A) = scut(A, A)
1
|A|
+
1
|A|
,
where scut(A, A) = 2cut + (A, A) +W − (A, A) +W − (A, A).
The minimum of the Rayleigh quotient R L can be viewed as a relaxation of
the minimization of RatioCut [48]. This objective function penalizes negative edges
within clusters, but it does so without any regard for the size of each cluster. It
seems natural that a large cluster ought to be “allowed” to contain relatively more
negative edges than a small one, so that a function like this might be more plausible
if the weights in scut were fractions of negative edges per cluster rather than simply
counts. Furthermore, this definition assumes only 2 clusters and it is problematic to
extend it to k clusters [17].
Instead, we define an unnormalized signed cut objective function by:
SRcut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) −W − (A i , A i )
|A i |
=
k
∑
i=1
cut + (A i , A i ) − cut − (A i , A i )
|A i |
The minimum of the SRcut function finds a solution with the fewest positive edges
and the most negative edges between groups. The value of SRcut could be negative.
Figure 8.2: Graph cuts of a sample graph
Both unnormalized cuts of signed graphs treat the positive edges in the same
way, but treat the negative edges differently. The RatioCut emphasizes minimizing
the total within-group negative edges. The SRcut maximizes the outgoing negative
edges from each group; this tends to create large groups when the sum of the positive
edge weights is greater than the sum of the negative edge weights between groups,
but small groups otherwise. For example, in Figure 8.2 the minimum cut of the
RatioCut is “Cut 1”, with no negative edge within groups. “Cut 2” is the result of
SRcut, with the node on the right side alone in a group. The question is which one is
the better cut? We argue that it is the second one, because the node on the right side
does not have any positive relationship to the nodes on the left.