Spectral Graph Partitioning Using Geodesic Distance-based Projection

The graph partitioning problem is one of the most fundamental combinatorial problems with a wide variety of applications. In this paper, we propose an efficient approach for implementing spectral graph partitioning that has a solid theoretical foundation but is practically less efficient than standard multilevel partitioners. The proposed method is based on the approximation of the eigenvectors of a graph-Laplacian matrix derived using the basis vectors by geodesic distance-based approach, instead of a standard linear algebraic approach. This geodesic distance-based approach is the key to making our method competitive in comparison to the multilevel partitioners. The primary building blocks of our method are the breadth-first search and the sparse matrix-vector product, which are the main kernels intensively studied in the high-performance computing field. Based on a performance evaluation in the shared-memory parallel setting, we demonstrate that our method is comparable to standard partitioners in terms of both quality and speed. We also show that our method has the potential to facilitate reproducibility-aware parallel partitioning.