I'm trying to get a better feel for graph drawing algorithms and I'm having a hard time conceptualizing the minimization of the following energy function that is from this paper (Section 3.1): Graph Drawing by Eigenvectors
The paper describes how the problem can be reduced down to a linear algebra minimization:
$$\min_{x^1, \ldots x^p} E(x^1, \ldots, x^p) \stackrel{\textrm{def}}{=}\frac{\sum\limits_{k=1}^{p} (x^k)^TLx^k}{\sum\limits_{k=1}^{p} (x^k)^Tx^k}$$
Subject to:
$$(x^k)^Tx^l = \delta_{kl}, \quad k,l = 1,p$$ $$(x^k)^T \cdot 1_n = 0, \quad k = 1,p$$
Where $1_n \stackrel{\textrm{def}}{=} (1,\ldots,1)^T \in \mathbb{R}^n$ is an eigenvector of $L$ (the graph laplacian), with the associated eigenvalue of $0$.
And a $p-$dimensional layout of the graph is defined by $p$ vectors:
$$x^1,\ldots, x^p \in \mathbb{R}^n$$ where $x^1(i), x^2(i)$ denote the coordinates of the node $i$.
It is then stated: "Using the fact that the lowest eigenvector of $L$ is $1_n$, we obtain that the optimal layout is given by the lowest positive Laplacian eigenvectors $v^2,\ldots,v^{p+1}$
I'm having a hard time grasping how these eigenvectors provide the optimal layout of the graph. Do they act as coordinates for the nodes positions? If someone could explain how this minimization function works, it would be greatly appreciated.
The Courant-Fischer theorem describes the relationship between the eigenvectors and eigenvalues of a symmetric matrix and optimizing the Raleigh quotient, $$\frac{x^T A x}{x^Tx} $$. Essentially, an eigenvector corresponding to the largest eigenvalue maximizes the Raleigh quotient. Likewise, an eigenvector corresponding to the second largest eigenvalue maximizes the Raleigh quotient subject to being orthogonal to the first eigenvector. The Courant-Fischer theorem states a more general version of this, but it's the same basic idea. Your energy function looks very similar to a Raleigh quotient. The other fact that is used here is that for every Laplacian matrix, the all ones vector $\mathbb{1}$ is an eigenvector corresponding to an eigenvalue of $0$. There's a few more details to work out but those two facts should get you started.
Dan Spielman has some great course notes on this that include both the spectral graph drawing and the Courant-Fischer theorem. Let me know if you want any further explanation and I'd be happy to help.