24
Chapter 3. Background
3.3 Spectral pipeline
The overall approach to spectral embedding follows these steps:
• Construct an adjacency matrix based on the node–node relationship intensities.
• Choose a Rayleigh quotient objective function that captures the desired properties of a “good” embedding.
• Find the Laplacian matrix corresponding to this Rayleigh quotient (the choice
of objective function is constrained by the necessity to find such a matrix).
Once this step has been done, adjacency matrices can be directly converted to
Laplacians without explicit attention to the Rayleigh quotient.
• Compute an eigendecomposition of the Laplacian matrix.
• Perform a projective embedding of the nodes and edges into the space spanned
by some number of the eigenvectors of the eigendecomposition, ignoring the
last eigenvector (with corresponding 0 eigenvalue).
• In this geometric representation of the graph, positioning of the point corresponding to each node corresponds to its global importance (more central =
more important), distances reflect similarity as it was expressed by the structure of the Rayleigh quotient, and standard operations on geometric spaces,
such as clustering, can be applied. If the dimensionality is low enough, the
graph can be visualized.
We will almost always be interested in networks that are connected. However, the
number of zero-valued eigenvalues equals the number of connected components of
the graph, so it is easy to tell when the network is not fully connected.
3.4 Spectral approaches to clustering
So far, we have concentrated on embedding a graph using spectral techniques. However, a substantial amount of work has focused on the role of spectral embedding in
graph clustering. This is both an application of spectral embedding, and a means of
justifying certain choices of spectral embedding techniques.
Large social networks tend not to have well-defined clusters because of the
number of different kinds of connections among individuals. But there are other settings where the number of nodes is smaller, or only particular kinds of relationships
are being considered, where it makes sense to ask whether a social network contains
clusters. The concept of a cluster is hard to make rigorous, but the intuition is that
clusters are subgroups of nodes that belong together and are therefore, somehow,
well connected internally but sparsely connected to other parts of the graph. Laplacian clustering techniques can be divided into graph cut, random-walk, or commute
distance approaches.
Chapter 3. Background
3.3 Spectral pipeline
The overall approach to spectral embedding follows these steps:
• Construct an adjacency matrix based on the node–node relationship intensities.
• Choose a Rayleigh quotient objective function that captures the desired properties of a “good” embedding.
• Find the Laplacian matrix corresponding to this Rayleigh quotient (the choice
of objective function is constrained by the necessity to find such a matrix).
Once this step has been done, adjacency matrices can be directly converted to
Laplacians without explicit attention to the Rayleigh quotient.
• Compute an eigendecomposition of the Laplacian matrix.
• Perform a projective embedding of the nodes and edges into the space spanned
by some number of the eigenvectors of the eigendecomposition, ignoring the
last eigenvector (with corresponding 0 eigenvalue).
• In this geometric representation of the graph, positioning of the point corresponding to each node corresponds to its global importance (more central =
more important), distances reflect similarity as it was expressed by the structure of the Rayleigh quotient, and standard operations on geometric spaces,
such as clustering, can be applied. If the dimensionality is low enough, the
graph can be visualized.
We will almost always be interested in networks that are connected. However, the
number of zero-valued eigenvalues equals the number of connected components of
the graph, so it is easy to tell when the network is not fully connected.
3.4 Spectral approaches to clustering
So far, we have concentrated on embedding a graph using spectral techniques. However, a substantial amount of work has focused on the role of spectral embedding in
graph clustering. This is both an application of spectral embedding, and a means of
justifying certain choices of spectral embedding techniques.
Large social networks tend not to have well-defined clusters because of the
number of different kinds of connections among individuals. But there are other settings where the number of nodes is smaller, or only particular kinds of relationships
are being considered, where it makes sense to ask whether a social network contains
clusters. The concept of a cluster is hard to make rigorous, but the intuition is that
clusters are subgroups of nodes that belong together and are therefore, somehow,
well connected internally but sparsely connected to other parts of the graph. Laplacian clustering techniques can be divided into graph cut, random-walk, or commute
distance approaches.