3.2. Spectral graph theory
23
3.2.2 The normalized graph Laplacians
The next Rayleigh quotient we shall consider is:
R L sym ( f ) =
f L sym f
f f
=
1
2 ∑
n
i, j=1 w i j (
f i
√
d i
−
f j
√
d j
) 2
∑
n
i=1 f 2
i
which adjusts the distances between embedded positions based on the degrees of the
corresponding nodes. As before, there is a corresponding Laplacian matrix, L sym ,
which is called the symmetric (normalized) Laplacian, and can be expressed as:
L sym = D
−1/2 LD
−1/2 = I − D
−1/2 W D
−1/2
where D, as before is the diagonal degree matrix of the adjacency matrix, W . The
diagonal entries of L sym are all 1s, and the value of the i jth entry is
−
w i j
d(v i )d(v j )
when the i jth entry of W is non-zero.
The minimum value of the Rayleigh quotient of the symmetric normalized
Laplacian is still 0, but the corresponding vector is the square roots of the degrees,
rather than the constant one vector 1. The symmetric normalized Laplacian L sym is
still positive semi-definite, and its smallest eigenvalue is 0.
The second variant of the Rayleigh quotient is defined as:
R L rw ( f ) =
f L 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
with the corresponding random-walk Laplacian given by:
L rw = D
−1 L = I − D
−1 W
The minimum value of the Rayleigh quotient of the random-walk normalized
Laplacian is 0, and the corresponding eigenvector is the constant one vector 1. Thus,
the random-walk normalized Laplacian L rw is positive semi-definite, and its smallest
eigenvalue is 0, but its eigenvectors are no longer orthogonal. It is easy to see why
from Figure 3.1. The points corresponding to each row of the random-walk matrix
are all in the positive hyperquadrant in the obvious direct embedding. Eigenvectors
that capture the variation in the cloud of such points cannot be guaranteed to be
orthogonal. They are, however, orthogonal to D 1/2 and f i D f j = 0.
The two normalized Laplacians are closely related:
L rw = D
−1/2 (I − L sym )D
1/2
Both normalized matrices have the same eigenvalues. The vector f is an eigenvector
of L rw if and only if g = D 1/2 f is an eigenvector of L sym ; λ and f are an eigenvalue
and eigenvector of L rw if and only if λ and f solve the generalized eigenproblem
L f = λ D f .
23
3.2.2 The normalized graph Laplacians
The next Rayleigh quotient we shall consider is:
R L sym ( f ) =
f L sym f
f f
=
1
2 ∑
n
i, j=1 w i j (
f i
√
d i
−
f j
√
d j
) 2
∑
n
i=1 f 2
i
which adjusts the distances between embedded positions based on the degrees of the
corresponding nodes. As before, there is a corresponding Laplacian matrix, L sym ,
which is called the symmetric (normalized) Laplacian, and can be expressed as:
L sym = D
−1/2 LD
−1/2 = I − D
−1/2 W D
−1/2
where D, as before is the diagonal degree matrix of the adjacency matrix, W . The
diagonal entries of L sym are all 1s, and the value of the i jth entry is
−
w i j
d(v i )d(v j )
when the i jth entry of W is non-zero.
The minimum value of the Rayleigh quotient of the symmetric normalized
Laplacian is still 0, but the corresponding vector is the square roots of the degrees,
rather than the constant one vector 1. The symmetric normalized Laplacian L sym is
still positive semi-definite, and its smallest eigenvalue is 0.
The second variant of the Rayleigh quotient is defined as:
R L rw ( f ) =
f L 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
with the corresponding random-walk Laplacian given by:
L rw = D
−1 L = I − D
−1 W
The minimum value of the Rayleigh quotient of the random-walk normalized
Laplacian is 0, and the corresponding eigenvector is the constant one vector 1. Thus,
the random-walk normalized Laplacian L rw is positive semi-definite, and its smallest
eigenvalue is 0, but its eigenvectors are no longer orthogonal. It is easy to see why
from Figure 3.1. The points corresponding to each row of the random-walk matrix
are all in the positive hyperquadrant in the obvious direct embedding. Eigenvectors
that capture the variation in the cloud of such points cannot be guaranteed to be
orthogonal. They are, however, orthogonal to D 1/2 and f i D f j = 0.
The two normalized Laplacians are closely related:
L rw = D
−1/2 (I − L sym )D
1/2
Both normalized matrices have the same eigenvalues. The vector f is an eigenvector
of L rw if and only if g = D 1/2 f is an eigenvector of L sym ; λ and f are an eigenvalue
and eigenvector of L rw if and only if λ and f solve the generalized eigenproblem
L f = λ D f .