Parallel Spectral Graph Partitioning

In this paper we develop a novel parallel spectral partitioning method that takes advantage of an efficient implementation of a preconditioned eigenvalue solver and a k-means algorithm on the GPU. We showcase the performance of our novel scheme against standard spectral techniques. Also, we use it to compare the ratio and normalized cut cost functions often used to measure the quality of graph partitioning. Finally, we show that the behavior of our spectral scheme and popular multi-level schemes is starkly different for two classes of problems: (i) social network graphs that often have power law-like distribution of edges per node and (ii) meshes arising from discretization of partial differential equations. Although in our numerical experiments the multi-level schemes are almost always faster, we show that our spectral scheme can achieve a significantly higher quality of partitioning for the former class of problems.