104
Chapter 8. Modelling positive and negative relationships
A small issue remains. There is an asymmetry in the two terms in the numerator of R L sns ( f ). As two positively connected nodes are moved closer, the change in
the magnitude of the contribution to the numerator becomes smaller as desired (but
it tends to be in the “flat” part of the quadratic). When two negatively connected
nodes are moved farther apart, the change in the magnitude of the contribution to the
numerator becomes larger, again as desired (but it also tends to be in the “steep” part
of the quadratic). The numerator therefore has a bias towards separating negatively
connected pairs rather than placing positively connected pairs closer together — the
same relative movement has an asymmetric effect on the numerator. Globally this
means that positively connected pairs are embedded farther apart than they “should
be”.
A better Laplacian, therefore, should slightly reduce the effect of strongly negatively weighted edges. The Rayleigh quotient corresponding to the balanced normalized signed graph Laplacian is:
R L bns ( f ) =
f (D + −W ) f
f D f
=
∑
n
i, j=1
1
2 w i j ( f i − f j ) 2 + w
−
i j f 2
i
∑
n
i=1 d i f 2
i
=
∑
n
i, j=1
1
2 w
+
i j ( f i − f j ) 2 −
1
2 w
−
i j ( f i − f j ) 2 + w
−
i j f 2
i
∑
n
i=1 d i f 2
i
,
The w
−
i j f 2
i term acts to pull nodes with incident negatively weighted edges slightly
towards the origin. The effect is shown in Figure 8.3(c), where nodes 1, 3, and 5 are
closer to nodes 2, 4, and 6, respectively, than in Figure 8.3(b).
However, the constant one vector 1 is no longer guaranteed to be an eigenvector of L bns . In other words, the origin will no longer be the “center” of the embedded
graph. L bns has n real-valued eigenvalues which lie between −1 and 2.
8.3.2 Graph cuts of signed random-walk Laplacians
Kunegis et al. also derive a signed normalized minimum cut from their Laplacian
[48]:
SignedNcut(A, A) = scut(A, A)
1
vol(A)
+
1
vol(A)
.
As before, SignedNcut does not consider the balance of negative edges in each group,
which may lead to the same problem as in the positive cut. Their definitions are based
on clustering into 2 clusters and it is problematic to extend to general k clusters [17].
Chapter 8. Modelling positive and negative relationships
A small issue remains. There is an asymmetry in the two terms in the numerator of R L sns ( f ). As two positively connected nodes are moved closer, the change in
the magnitude of the contribution to the numerator becomes smaller as desired (but
it tends to be in the “flat” part of the quadratic). When two negatively connected
nodes are moved farther apart, the change in the magnitude of the contribution to the
numerator becomes larger, again as desired (but it also tends to be in the “steep” part
of the quadratic). The numerator therefore has a bias towards separating negatively
connected pairs rather than placing positively connected pairs closer together — the
same relative movement has an asymmetric effect on the numerator. Globally this
means that positively connected pairs are embedded farther apart than they “should
be”.
A better Laplacian, therefore, should slightly reduce the effect of strongly negatively weighted edges. The Rayleigh quotient corresponding to the balanced normalized signed graph Laplacian is:
R L bns ( f ) =
f (D + −W ) f
f D f
=
∑
n
i, j=1
1
2 w i j ( f i − f j ) 2 + w
−
i j f 2
i
∑
n
i=1 d i f 2
i
=
∑
n
i, j=1
1
2 w
+
i j ( f i − f j ) 2 −
1
2 w
−
i j ( f i − f j ) 2 + w
−
i j f 2
i
∑
n
i=1 d i f 2
i
,
The w
−
i j f 2
i term acts to pull nodes with incident negatively weighted edges slightly
towards the origin. The effect is shown in Figure 8.3(c), where nodes 1, 3, and 5 are
closer to nodes 2, 4, and 6, respectively, than in Figure 8.3(b).
However, the constant one vector 1 is no longer guaranteed to be an eigenvector of L bns . In other words, the origin will no longer be the “center” of the embedded
graph. L bns has n real-valued eigenvalues which lie between −1 and 2.
8.3.2 Graph cuts of signed random-walk Laplacians
Kunegis et al. also derive a signed normalized minimum cut from their Laplacian
[48]:
SignedNcut(A, A) = scut(A, A)
1
vol(A)
+
1
vol(A)
.
As before, SignedNcut does not consider the balance of negative edges in each group,
which may lead to the same problem as in the positive cut. Their definitions are based
on clustering into 2 clusters and it is problematic to extend to general k clusters [17].