Accession Number : ADA292214

Title :   On the Performance of Spectral Graph Partitioning Methods.

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Guattery, Stephen ; Miller, Gary L.

PDF Url : ADA292214

Report Date : DEC 1994

Pagination or Media Count : 33

Abstract : Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there is not much theoretical analysis of the quality of the separators produced by this technique; instead it is usually claimed that spectral 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 definition of spectral methods that allows the use of some specified number of the eigenvectors corresponding to the smallest eigenvalues of the Laplacian matrix of a graph, and show that if such algorithms use a constant number of eigenvectors, then there are graphs for which they do no better than using only the second smallest eigenvector. Further, when applied to these graphs the algorithm based on the second smallest eigenvector performs poorly with respect to theoretical bounds. Even if an algorithm meeting the generalized definition uses up to n% for 0 < E < % eigenvectors, there exist graphs for which the algorithm fails to find a separator with a cut quotient within %-4-e - 1 of the isoperimetric number. We also introduce some facts about the structure of eigenvectors of certain types of Laplacian and symmetric matrices; these facts provide the basis for the analysis of the counterexamples.

Descriptors :   *GRAPHS, *EIGENVECTORS, *EIGENVALUES, *SEPARATORS, ALGORITHMS, METHODOLOGY, COMPUTATIONS, THEORY, SPECTRA, CUTTING, LINEAR ALGEBRA.

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE