Multilevel spectral hypergraph partitioning with arbitrary vertex sizes

This paper presents a new spectral partitioning formulation which directly incorporates vertex size information by modifying the Laplacian of the grap h. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the s caled ratio-cut costs of results on benchmarks with arbitrary vertex sizes improve by 22% when the eigenvectors of the Laplacian in the spectral parti tioner KP are replaced by the eigenvectors of our modified Laplacian. The i nability to handle vertex sizes in the spectral partitioning formulation ha s been a limitation in applying spectral partitioning in a multilevel setti ng. We investigate whether our new formulation effectively removes this lim itation by combining it with a simple multilevel bottom-up clustering algor ithm and an iterative improvement algorithm for partition refinement. Exper iments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the mod ified Laplacian in place of the standard Laplacian is more efficient and mo re effective in the partitioning of graphs with arbitrary-size and unit-siz e vertices; average improvements of 17% and 18% are observed for graphs wit h arbitrary-size and unit size vertices, respectively. Comparisons with oth er ratio-cut based partitioners on hypergraphs with unit-size as well as ar bitrary-size vertices, show that the multilevel spectral partitioner produc es either better results or almost identical results more efficiently.