100
Chapter 8. Modelling positive and negative relationships
(a) L
(b) L sign
Figure 8.1: A toy signed graph embedding of unnormalized Laplacians in two dimensions, where edges are weighted ±1, shown as solid lines (+1) and dashed lines
(−1).
A minimum of the Rayleigh quotient R L sign ( f ) corresponds to an embedding that
minimizes the total squared distance between positively connected pairs and maximizes the total squared distance between negatively connected pairs. Thus, embedding using the Laplacian L sign avoids the problem of L.
Figure 8.1(b) shows that the embedding based on L sign places the nodes in
more reasonable positions. For example, node 1 is closer to node 4 than node 2 is.
The matrix L sign has the following properties. First, 0 is an eigenvalue of L sign ,
and the corresponding eigenvector is the constant one vector 1. Exactly as for the
conventional Laplacian L, this is a trivial embedding. Second, if f i and f j are two
different eigenvectors of matrix L sign , then f i ⊥ f j . The proofs are similar to those
for the conventional Laplacian L.
8.2.2 Graph cuts of signed unnormalized Laplacians
For signed graphs, there is also a direct relationship between spectral embeddings
and the cuts used for clustering. In other words, for each Rayleigh quotient of the
signed unnormalized Laplacians, there is a corresponding plausible cut function.
When there are negative edges in a graph, balanced minimum cut approaches
need to be redefined. For convenience, we represent the basic cut in its positive and
negative parts, respectively:
cut
+ (A 1 , ..., A k ) =
1
2
k
∑
i=1
W
+ (A i , A i ),
cut
− (A 1 , ..., A k ) =
1
2
k
∑
i=1
W
− (A i , A i ).
The sum of the positive and negative volumes is the total volume of the nodes in a
Chapter 8. Modelling positive and negative relationships
(a) L
(b) L sign
Figure 8.1: A toy signed graph embedding of unnormalized Laplacians in two dimensions, where edges are weighted ±1, shown as solid lines (+1) and dashed lines
(−1).
A minimum of the Rayleigh quotient R L sign ( f ) corresponds to an embedding that
minimizes the total squared distance between positively connected pairs and maximizes the total squared distance between negatively connected pairs. Thus, embedding using the Laplacian L sign avoids the problem of L.
Figure 8.1(b) shows that the embedding based on L sign places the nodes in
more reasonable positions. For example, node 1 is closer to node 4 than node 2 is.
The matrix L sign has the following properties. First, 0 is an eigenvalue of L sign ,
and the corresponding eigenvector is the constant one vector 1. Exactly as for the
conventional Laplacian L, this is a trivial embedding. Second, if f i and f j are two
different eigenvectors of matrix L sign , then f i ⊥ f j . The proofs are similar to those
for the conventional Laplacian L.
8.2.2 Graph cuts of signed unnormalized Laplacians
For signed graphs, there is also a direct relationship between spectral embeddings
and the cuts used for clustering. In other words, for each Rayleigh quotient of the
signed unnormalized Laplacians, there is a corresponding plausible cut function.
When there are negative edges in a graph, balanced minimum cut approaches
need to be redefined. For convenience, we represent the basic cut in its positive and
negative parts, respectively:
cut
+ (A 1 , ..., A k ) =
1
2
k
∑
i=1
W
+ (A i , A i ),
cut
− (A 1 , ..., A k ) =
1
2
k
∑
i=1
W
− (A i , A i ).
The sum of the positive and negative volumes is the total volume of the nodes in a