ON THE QUALITY OF SPECTRAL SEPARATORS

Citation
S. Guattery et Gl. Miller, ON THE QUALITY OF SPECTRAL SEPARATORS, SIAM journal on matrix analysis and applications (Print), 19(3), 1998, pp. 701-719
Citations number
27
Categorie Soggetti
Mathematics,Mathematics
ISSN journal
08954798
Volume
19
Issue
3
Year of publication
1998
Pages
701 - 719
Database
ISI
SICI code
0895-4798(1998)19:3<701:OTQOSS>2.0.ZU;2-2
Abstract
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.