3.2. Spectral graph theory
19
of an initial space, where the matrix entries are coordinates with respect to the standard basis, to a new space, spanned by the eigenvectors, and coordinates in this space
that are better behaved. For example, if the space is not of full rank, such a transformation can reveal that the data lie on a lower-dimensional manifold.
From yet another perspective, an eigenvector–eigenvalue pair represent the amplitude and frequency of vibration if the structure associated with the matrix were to
be struck parallel to one of the original axes.
All three of these perspectives on eigendecompositions arise from regarding
the original matrix as defining a cloud of points, each one at a position described
by a row of the matrix. The eigendecomposition finds a view of this cloud that
emphasizes the aspects of its structure with the greatest variation.
An eigendecomposition of an adjacency matrix can reveal the importance of
each node in the graph, an idea exploited by Google in their PageRank algorithm.
The rows of the adjacency matrix can be regarded as points in n-dimensional space,
in fact in the positive hyperquadrant of n-dimensional space since edge weights are
positive. The principal eigenvector of this matrix points through the center of this
cloud of points, and the projection of each of the n nodes onto it determines a ranking
from most- to least-important node. For an undirected graph this corresponds to the
edge weight sum of each node, but for a directed graph, such as the random-walk
version of the adjacency matrix, this is no longer the case.
Unfortunately, further eigenvectors of the adjacency matrix do not provide similar insights since the second, and subsequent, eigenvectors are constrained to be orthogonal to the first — but the direction of the principal eigenvector is determined by
the overall weights of the graph edges. In other words, the vector connecting the origin to the cloud of points in the positive hyperquadrant depends on the total structure
of the graph, but not its internal structure, and so the requirement for orthogonality
to this eigenvector is not revealing.
This can be seen in Figure 3.1. The graph edge weights are all non-negative,
so that the representation of each node as a point in n-dimensional space is a cloud in
the positive hyperquadrant. Since the eigendecomposition is a purely numerical algorithm, it finds the principal eigenvector, v 1 , pointing along the direction of greatest
numerical variation, so from the origin to the center of the cloud. The second eigenvector, v 2 , is constrained to be orthogonal to it, but this direction is not meaningful
as a property of the cloud of points.
As we described earlier, the adjacency matrix needs to be converted to a Laplacian matrix before eigendecomposition to create a structure in which all of the eigenvectors reflect the structure of the graph. Because of this normalization, the eigenvectors that are most useful for embedding are those associated with the smaller
eigenvalues, rather than those associated with the largest eigenvalues used for conventional eigendecompositions. These eigenvectors are the columns at the right-hand
end of the decomposed matrix when the eigenvalues are sorted into descending order.
In such an eigendecomposition, the eigenvalue associated with the last column
is 0, and the corresponding eigenvector is conventionally ignored. (It plays no role in
the corresponding matrix product, although several of the algorithms that compute
eigendecompositions do actually place meaningful values in this last column.)
19
of an initial space, where the matrix entries are coordinates with respect to the standard basis, to a new space, spanned by the eigenvectors, and coordinates in this space
that are better behaved. For example, if the space is not of full rank, such a transformation can reveal that the data lie on a lower-dimensional manifold.
From yet another perspective, an eigenvector–eigenvalue pair represent the amplitude and frequency of vibration if the structure associated with the matrix were to
be struck parallel to one of the original axes.
All three of these perspectives on eigendecompositions arise from regarding
the original matrix as defining a cloud of points, each one at a position described
by a row of the matrix. The eigendecomposition finds a view of this cloud that
emphasizes the aspects of its structure with the greatest variation.
An eigendecomposition of an adjacency matrix can reveal the importance of
each node in the graph, an idea exploited by Google in their PageRank algorithm.
The rows of the adjacency matrix can be regarded as points in n-dimensional space,
in fact in the positive hyperquadrant of n-dimensional space since edge weights are
positive. The principal eigenvector of this matrix points through the center of this
cloud of points, and the projection of each of the n nodes onto it determines a ranking
from most- to least-important node. For an undirected graph this corresponds to the
edge weight sum of each node, but for a directed graph, such as the random-walk
version of the adjacency matrix, this is no longer the case.
Unfortunately, further eigenvectors of the adjacency matrix do not provide similar insights since the second, and subsequent, eigenvectors are constrained to be orthogonal to the first — but the direction of the principal eigenvector is determined by
the overall weights of the graph edges. In other words, the vector connecting the origin to the cloud of points in the positive hyperquadrant depends on the total structure
of the graph, but not its internal structure, and so the requirement for orthogonality
to this eigenvector is not revealing.
This can be seen in Figure 3.1. The graph edge weights are all non-negative,
so that the representation of each node as a point in n-dimensional space is a cloud in
the positive hyperquadrant. Since the eigendecomposition is a purely numerical algorithm, it finds the principal eigenvector, v 1 , pointing along the direction of greatest
numerical variation, so from the origin to the center of the cloud. The second eigenvector, v 2 , is constrained to be orthogonal to it, but this direction is not meaningful
as a property of the cloud of points.
As we described earlier, the adjacency matrix needs to be converted to a Laplacian matrix before eigendecomposition to create a structure in which all of the eigenvectors reflect the structure of the graph. Because of this normalization, the eigenvectors that are most useful for embedding are those associated with the smaller
eigenvalues, rather than those associated with the largest eigenvalues used for conventional eigendecompositions. These eigenvectors are the columns at the right-hand
end of the decomposed matrix when the eigenvalues are sorted into descending order.
In such an eigendecomposition, the eigenvalue associated with the last column
is 0, and the corresponding eigenvector is conventionally ignored. (It plays no role in
the corresponding matrix product, although several of the algorithms that compute
eigendecompositions do actually place meaningful values in this last column.)