When I specify that a graph should be realized using the "SpectralEmbedding" procedure, what paper / algorithm for spectral embedding is this based on? I was unable to find any documentation for this.
Also, are we guaranteed that the contours of a $N \times M$ rectangular lattice will be straight lines after this embedding procedure?
I e-mailed support at Wolfram Research and received the following response:
Spectral graph drawing methods construct the layout using eigenvectors of certain matrices associated with the graph (Laplacian matrix). Reference: Hall, K.M. "An $r$-dimensional Quadratic Placement Algorithm.", Management Science 17, pp. 219-229 (1970).
Abstract: In this paper the solution to the problem of placing $n$ connected points (or nodes) in $r$-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form $\mathbf X^\prime\mathbf X = 1$, for each of the $r$ unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum of $r$ positive semi-definite quadratic forms which, under the quadratic constraints, reduces to the problem of finding $r$ eigenvectors of a special "disconnection" matrix. It is shown, by example, how this can serve as a basis for cluster identification.
From (Section 2.3) of Daniel A. Spielman's lecture notes on applications of the Laplacian in spectral graph theory:
This approach to using eigenvectors to draw graphs was suggested by Hall [Hal70] in 1970. Hall first considered the problem of assigning a real number $x(u)$ to each vertex $u$ so that $(x(u)-x(v))^2$ is small for most edges $(u; v)$. This led him to consider the problem of minimizing (2.1). So as to avoid the degenerate solutions in which every vertex is mapped to one value, he introduced the restriction that $x$ be orthogonal to $1$. As the utility of the embedding does not really depend upon its scale, he suggested the normalization $\|x\| = 1$. As we saw last class, the solution to the resulting optimization problem is precisely an eigenvector of the second-smallest eigenvalue of the Laplacian.
