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?

  • 3
    $\begingroup$ For this type of question I suggest you contact support directly. But when they reply, it'd be good if you could post the answer here for everyone's benefit. $\endgroup$
    – Szabolcs
    Commented Feb 8, 2013 at 17:55
  • $\begingroup$ @Szabolcs No response yet, but I'll post here what I learn. $\endgroup$ Commented Feb 10, 2013 at 13:21

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.