3.2. Spectral graph theory
21
3.2.1 The unnormalized graph Laplacian
We now outline more carefully the process for embedding a graph using a spectral
approach.
Given an adjacency matrix, what would be considered a good embedding?
We shall see that there are multiple answers to that question, but we will start with
the simplest case. Suppose we want to embed the nodes of the graph in a single
dimension (that is, along a line) in a way that best reflects their mutually connected
structure. A plausible objective function is:
1
2
n
∑
i, j=1
w i j ( f i − f j )
2
where f is a non-zero vector of the positions on the line of the graph’s nodes, and w i j
is the i jth entry of the adjacency matrix, W . This function preferentially places nodes
that are strongly connected close together, and penalizes separation by an amount
proportional to Euclidean distance. The division by 2 is required because every term
appear twice in the sum.
There is no special scale for the vector f describing positions on the line. To
remove the effect of the magnitude of f , we can refine the objective function to:
1
2 ∑
n
i, j=1 w i j ( f i − f j ) 2
∑
n
i=1 f 2
i
This function is called the Rayleigh quotient.
If f corresponds to the position of each node of the graph in a 1-dimensional
embedding, then a small value for the Rayleigh quotient corresponds to a “good”
embedding. One particular good, but rather uninteresting, embedding would be to
place every node at the same location.
Note also that a vector of locations could be altered by adding or subtracting a
constant from all of its values, but this does not change the embedding in any useful
way. Thus there is still a normalization issue to consider.
A choice for the trivial embedding would be 1, placing every node at location
1, for which the Rayleigh quotient is, of course, equal to zero. This is a very uninteresting embedding, but it is useful to impose the property that every other embedding
must have the property that f ⊥ 1, that is they must be centered at the origin, and so
have mean 0. This orthogonality constraint acts to normalize all of the other potential
solutions for the vector f .
A little algebra reveals the matrix equation:
R L ( f ) =
f L f
f f
=
1
2 ∑
n
i, j=1 w i j ( f i − f j ) 2
∑
n
i=1 f 2
i
for a matrix, L, which is
L = D −W
where D is the diagonal degree matrix of W . We have seen this matrix before. This
matrix, L, is called the unnormalized, or combinatorial, Laplacian of the graph, and
21
3.2.1 The unnormalized graph Laplacian
We now outline more carefully the process for embedding a graph using a spectral
approach.
Given an adjacency matrix, what would be considered a good embedding?
We shall see that there are multiple answers to that question, but we will start with
the simplest case. Suppose we want to embed the nodes of the graph in a single
dimension (that is, along a line) in a way that best reflects their mutually connected
structure. A plausible objective function is:
1
2
n
∑
i, j=1
w i j ( f i − f j )
2
where f is a non-zero vector of the positions on the line of the graph’s nodes, and w i j
is the i jth entry of the adjacency matrix, W . This function preferentially places nodes
that are strongly connected close together, and penalizes separation by an amount
proportional to Euclidean distance. The division by 2 is required because every term
appear twice in the sum.
There is no special scale for the vector f describing positions on the line. To
remove the effect of the magnitude of f , we can refine the objective function to:
1
2 ∑
n
i, j=1 w i j ( f i − f j ) 2
∑
n
i=1 f 2
i
This function is called the Rayleigh quotient.
If f corresponds to the position of each node of the graph in a 1-dimensional
embedding, then a small value for the Rayleigh quotient corresponds to a “good”
embedding. One particular good, but rather uninteresting, embedding would be to
place every node at the same location.
Note also that a vector of locations could be altered by adding or subtracting a
constant from all of its values, but this does not change the embedding in any useful
way. Thus there is still a normalization issue to consider.
A choice for the trivial embedding would be 1, placing every node at location
1, for which the Rayleigh quotient is, of course, equal to zero. This is a very uninteresting embedding, but it is useful to impose the property that every other embedding
must have the property that f ⊥ 1, that is they must be centered at the origin, and so
have mean 0. This orthogonality constraint acts to normalize all of the other potential
solutions for the vector f .
A little algebra reveals the matrix equation:
R L ( f ) =
f L f
f f
=
1
2 ∑
n
i, j=1 w i j ( f i − f j ) 2
∑
n
i=1 f 2
i
for a matrix, L, which is
L = D −W
where D is the diagonal degree matrix of W . We have seen this matrix before. This
matrix, L, is called the unnormalized, or combinatorial, Laplacian of the graph, and