ABSTRACT
The general strategy for spectral embedding of a graph requires a transformation of the adjacency matrix into a Laplacian matrix. This can be thought of as a kind of normalization, turning the graph inside out so that high-degree nodes are no longer naturally on the outside of the embedding; or as a result of choosing an objective function — the Rayleigh quotient — that defines what a "good" embedding should be. The eigendecomposition of this Laplacian matrix is then computed. This eigendecomposition corresponds to a change of basis in which new axes — the eigenvectors — are arranged in mutually orthogonal directions in which the cloud of points corresponding to the nodes has large variation. The final stage is to project the nodes into a subspace of appropriate dimensionality, where geometric calculations can be used to assess similarity, centrality, clustering, outliers, and so on.
