8.3. Normalized spectral Laplacians of signed graphs
103
(a) L rw
(b) L sns
(c) L bns
Figure 8.3: A toy signed graph embedding of normalized Laplacians in two dimensions, where edges are weighted ±1, shown as solid lines (+1) and as dashed lines
(−1).
Our simple normalized signed graph Laplacian L sns is motivated by the Rayleigh
quotient:
R L sns ( f ) =
f (D + − D − −W ) f
f D f
=
1
2 ∑
n
i, j=1 w i j ( f i − f j ) 2
∑
n
i=1 d i f 2
i
=
1
2 ∑
n
i, j=1
w
+
i j ( f i − f j ) 2 − w
−
i j ( f i − f j ) 2
∑
n
i=1 d i f 2
i
.
which penalizes long positive edges and short negative edges in the same way as our
unnormalized construction.
A minimum of the Rayleigh quotient R L sns ( 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, normalized by the total degree D. Thus, embedding using the Laplacian L sns avoids the
problem of L.
Figure 8.3 shows the embeddings of the three normalized signed Laplacians;
the relationships are qualitatively the same as for the unnormalized signed Laplacians.
The matrix L sns has the following properties. First, 0 is an eigenvalue of L sns ,
and the corresponding eigenvector is the constant one vector 1. Exactly as for the
conventional Laplacian L rw , this is a trivial embedding. Second, if f i and f j are two
different eigenvectors of matrix L sns , then f
i D f j = 0. The proof is similar to that
for the conventional Laplacian L rw . Third, L sns has n real-valued eigenvalues within
range [−2, 2]. The proof is based on the Rayleigh quotient. If f is an eigenvector
of matrix L sns , the corresponding eigenvalue is equal to the corresponding Rayleigh
quotient value.