Computing graph separators is an important step in many graph algorith
ms. A popular technique for finding separators involves spectral metho
ds. However, there has not been much prior analysis of the quality of
the separators produced by this technique; instead it is usually claim
ed that spectral methods ''work well in practice.'' We present an init
ial attempt at such an analysis. In particular, we consider two popula
r spectral separator algorithms and provide counterexamples showing th
at these algorithms perform poorly on certain graphs. We also consider
a generalized definition of spectral methods that allows the use of s
ome specified number of the eigenvectors corresponding to the smallest
eigenvalues of the Laplacian matrix of a graph, and we show that if s
uch algorithms use a constant number of eigenvectors, then there are g
raphs for which they do no better than using only the second smallest
eigenvector. Furthermore, using the second smallest eigenvector of the
se graphs produces partitions that are poor with respect to bounds on
the gap between the isoperimetric number and the cut quotient of the s
pectral separator. Even if a generalized spectral algorithm uses n(is
an element of) for 0 < is an element of < 1/4 eigenvectors, there exis
t graphs for which the algorithm fails to find a separator with a cut
quotient within n(1/4-is an element of) - 1 of the isoperimetric numbe
r. We also introduce some facts about the structure of eigenvectors of
certain types of Laplacian and symmetric matrices; these facts provid
e the basis for the analysis of the counterexamples. Finally, we discu
ss some developments in spectral partitioning that have occurred since
these results first appeared.