10
Chapter 2. The core model
should this relaxation be done? A perfectly accurate representation of an n-node
graph requires n − 1 dimensions, but a reasonable drawing can use at most 2, or
perhaps 3, dimensions. If the relaxation is done in a high-dimensional space, then
some kind of projection is still required to reduce it to 2 or 3 dimensions. If it is done
in 2 or 3 dimensions from the start, the pulls from the other nodes are not quite in the
right directions, so the stable configuration may not be what it “should” be.
The second main way to understand a graph is spectral embedding. First, the
graph is created in its full n − 1-dimensional spatial complexity, with each node
represented as a point in space with the distances between each connected pair
of nodes exactly representing their similarity. (Euclidean distance corresponds to
dissimilarity, so well-connected nodes are close.) Second, this cloud of points is
rotated in such a way that its maximal variation is aligned along an initial axis, its
orthogonal next largest variation along a second axis, and so on — this corresponds
to an eigendecomposition. Third, the cloud is projected into the space spanned by
the most useful of these axes — those that reveal the maximal variation — and the
values of the eigenvectors for each node are interpreted as coordinates in a lowerdimensional space.
The advantage of spectral approaches over graph drawing is that the construction comes with strong guarantees about the quality of the embedding. A projection
to k dimensions is guaranteed to be the most faithful possible in that number of dimensions. Of course, this accuracy may come at the expense of direct intelligibility,
since the visualization may not be as easy for a human viewer to understand as one
produced by graph drawing. However, its inherent accuracy means that downstream
analysis can be used to make sense of its properties, even if these properties cannot
be captured in a nice picture. We will render spectral embeddings directly, but it is
possible to tweak such embeddings to increase their human comprehensibility without sacrificing much of the geometric accuracy. For example, the Multinet package
(http://www.sfu.ca/personal/archives/richards/Multinet/Pages/multinet.htm)
[80] can render social networks in many different ways, based on underlying spectral
embeddings.
It might seem natural to begin this eigendecomposition with the network’s
adjacency matrix, but this does not work. A well-connected graph node has a row
in the adjacency matrix with many non-zero entries; when it is embedded in n − 1dimensional space, it will be placed far from the origin. Conversely, a node with few
connections will have many zeros in the corresponding row of the adjacency matrix,
and so will be placed close to the origin. Hence the cloud will be “inside out”.
Worse still, the well-connected nodes will tend to be connected to one another in
the network (assortativity) but, by being far from the origin, they are also embedded
far from one another. So using the adjacency matrix as a starting point dooms the
process to failure (which has not prevented the alarmingly large number of research
papers that do it anyway).
Rather than starting from the adjacency matrix, a transformation is applied
that is a kind of normalization. As we shall see, there are a number of ways of doing
this, but the simplest one is to convert the adjacency matrix into a combinatorial
Laplacian by summing the entries in each row (which corresponds to the weighted
Chapter 2. The core model
should this relaxation be done? A perfectly accurate representation of an n-node
graph requires n − 1 dimensions, but a reasonable drawing can use at most 2, or
perhaps 3, dimensions. If the relaxation is done in a high-dimensional space, then
some kind of projection is still required to reduce it to 2 or 3 dimensions. If it is done
in 2 or 3 dimensions from the start, the pulls from the other nodes are not quite in the
right directions, so the stable configuration may not be what it “should” be.
The second main way to understand a graph is spectral embedding. First, the
graph is created in its full n − 1-dimensional spatial complexity, with each node
represented as a point in space with the distances between each connected pair
of nodes exactly representing their similarity. (Euclidean distance corresponds to
dissimilarity, so well-connected nodes are close.) Second, this cloud of points is
rotated in such a way that its maximal variation is aligned along an initial axis, its
orthogonal next largest variation along a second axis, and so on — this corresponds
to an eigendecomposition. Third, the cloud is projected into the space spanned by
the most useful of these axes — those that reveal the maximal variation — and the
values of the eigenvectors for each node are interpreted as coordinates in a lowerdimensional space.
The advantage of spectral approaches over graph drawing is that the construction comes with strong guarantees about the quality of the embedding. A projection
to k dimensions is guaranteed to be the most faithful possible in that number of dimensions. Of course, this accuracy may come at the expense of direct intelligibility,
since the visualization may not be as easy for a human viewer to understand as one
produced by graph drawing. However, its inherent accuracy means that downstream
analysis can be used to make sense of its properties, even if these properties cannot
be captured in a nice picture. We will render spectral embeddings directly, but it is
possible to tweak such embeddings to increase their human comprehensibility without sacrificing much of the geometric accuracy. For example, the Multinet package
(http://www.sfu.ca/personal/archives/richards/Multinet/Pages/multinet.htm)
[80] can render social networks in many different ways, based on underlying spectral
embeddings.
It might seem natural to begin this eigendecomposition with the network’s
adjacency matrix, but this does not work. A well-connected graph node has a row
in the adjacency matrix with many non-zero entries; when it is embedded in n − 1dimensional space, it will be placed far from the origin. Conversely, a node with few
connections will have many zeros in the corresponding row of the adjacency matrix,
and so will be placed close to the origin. Hence the cloud will be “inside out”.
Worse still, the well-connected nodes will tend to be connected to one another in
the network (assortativity) but, by being far from the origin, they are also embedded
far from one another. So using the adjacency matrix as a starting point dooms the
process to failure (which has not prevented the alarmingly large number of research
papers that do it anyway).
Rather than starting from the adjacency matrix, a transformation is applied
that is a kind of normalization. As we shall see, there are a number of ways of doing
this, but the simplest one is to convert the adjacency matrix into a combinatorial
Laplacian by summing the entries in each row (which corresponds to the weighted