Fiedler vector, what else?

In the spectral analysis of a graph with 1 connected component, the first non-trivial eigenvector (corresponding to the non-zero smallest eigenvalue) is also called the Fiedler vector. This vector is useful in graph partitioning because it minimizes the distance between the connected vertices in the original graph. In other ways, it can creates partitions in which nodes within the same partitions have minimal distance/high similarity and nodes between partitions have minimum edges connecting them. Now, my question is, as soon as we go to higher eigenvalues, what do eigenvectors mean? Do they represent other partitions of the same graph? Should they be taken into consideration?

• Try to look up "nodal domains" in the context of graphs. The rough idea (but wrong in this exact form) is that the subgraph induced on the non-negative (or non-positive) entries of an eigenvector to the $k$-th largest eigenvalue has $k-1$ connected components. There exist some estimates on how wrong this number can be. – M. Winter Jun 23 at 14:43

Yes. See e.g. the paper Multi-way spectral partitioning and higher-order Cheeger inequalities by Lee, Oveis-Gharan and Trevisan. They show how the first $$k$$ eigenvectors can be used to find a useful $$k$$-way partitioning.