Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics

The gvuph partitioning problem is to divide the vertices of a graph into disjoint clusters to minimize the total cost of the edges cut by the clusters. A spectral partitioning heuristic uses the graph’s eigenvectors to construct a geometric representation of the graph (e.g., linear orderings) which are subsequently partitioned. Our main result shows that when all the eigen-vectors are used, graph partitioning reduces to a new vector partitioning problem. This result implies that as many eigenvectors as are practically possible should be used to construct a so-lution. This philosophy is in contrast to that of the widely used spectral hipartitioning (SB) heuristic (which uses only a single eigenvector) and several previous multi-way partitioning heuristics [S, 11, 17, 27, 381 (which use k eigenvectors to construct k-way partitionings). Our result motivates a simple ordering heuristic that is a multiple-eigenvector extension of SB. This heuristic not only significantly outperforms recursive SB, but can also yield excellent multi-way VLSI circuit partitionings as compared to [l, 111. Our experiments suggest that the vector parti-tioning perspective opens the door to new and effective partitioning heuristics. The present paper updates and improves a preliminary version of this work [5]. 0 1999 Published by Elsevier Science B.V. All rights reserved. 1