Why use the Fiedler vector?

Question

The Fiedler vector is defined as $$\vec{x_2}=\arg\min_{||\vec{x}||=1,\ \vec{x}^t\vec{x_1}=0}\ \sum_{(ij)\in E}(x_i-x_j)^2,$$ where $\vec{x_1}$ is the smallest eigenvalue's eigenvector. It can be used to find an embedding or partition of a graph. My question is, what is the advantage of having the additional constraint that $\vec{x}^t\vec{x_1}=0$ (and thus obtaining the Fiedler vector) versus just minimizing the expression without that constraint, for the same goal of finding a good partition or embedding?

Answer 1

In general, when minimizing a positive semidefinite quadratic form subject to $\|\vec x\|=1$, you'll get the first eigenvector $\vec{x_1}$. If you add the additional constraint that $\vec x$ should be orthogonal to $\vec{x_1}$, you'll get the second eigenvector $\vec{x_2}$. If you ask for $\vec x$ to be orthogonal to the first two eigenvectors, you'll get the third, and so on.

Here, if we drop the constraint $\vec x^{\mathsf T} \vec{x_1} = 0$, we'll get back $\vec{ x_1}$ as the solution, and $\vec{x_1}$ is just $(1,1,1,\dots,1,1)$ in this case. It's not very useful for finding an embedding (it just gives every vertex the same coordinate) or a partition (it treats every vertex equally).

For connected graphs, the Fiedler eigenvector $\vec{x_2}$ gives the first nontrivial eigenvector - the first one that gives us any interesting information about the graph. (If the graph is not connected, the second eigenvector will give some information about connected components. This is sometimes helpful, but not very good for finding an embedding - you'd do better to embed each component separately.)