On the performance of spectral graph partitioning methods

Computing graph separators is an important step in many graph algorithms. A popular technique for computing graph separators involves spectral methods. However, there is not much theoretical analysis of the quality of the separators produced by spectral methods; instead it is usually claimed that such methods "work well in practice." We present an initial attempt at such analysis. In particular, we consider two popular spectral separator algorithms, and provide counterexamples that show these algorithms perform poorly on certain graphs. We also consider a generalized version of the spectral method that allows the use of some specified number of the eigenvectors corresponding to the smallest eigenvalues of the Laplacian matrix of a graph; for such algorithms, we show that if they use a constant number of eigenvectors, then there are graphs for which they do no better than using only the second smallest eigenvector. We also show that in this case the algorithm based on the second smalles...