@conference{Toby Simpson2018,
author = "Toby Simpson and Pasadakis Dimosthenis and Drosos Kourounis and Kohei Fujita and Takuma Yamaguchi and Ichimura Tsuyoshi and Olaf Schenk",
abstract = "A continuous formulation of the optimal 2-way graph partitioning based on the p-norm minimization of the graph Laplacian Rayleigh quotient is presented, which provides a sharp approximation to the balanced graph partitioning problem, the optimality of which is known to be NP-hard. The minimization is initialized from a cut provided by a state-of-the-art multilevel recursive bisection algorithm, and then a continuation approach reduces the p-norm from a 2-norm towards a 1-norm, employing for each value of p a feasibility-preserving steepest-descent method that converges on the p-Laplacian eigenvector. A filter favors iterates advancing towards minimum edgecut and partition load imbalance. The complexity of the suggested approach is linear in graph edges. The simplicity of the steepest-descent algorithm renders the overall approach highly scalable and efficient in parallel distributed architectures. Parallel implementation of recursive bisection on multi-core CPUs and GPUs are presented for large-scale graphs with up to 1.9 billion tetrahedra. The suggested approach exhibits improvements of up to 52.8% over METIS for graphs originating from triangular Delaunay meshes, 34.7% over METIS and 21.9% over KaHIP for power network graphs, 40.8% over METIS and 20.6% over KaHIP for sparse matrix graphs, and finally 93.2% over METIS for graphs emerging from social networks.",
booktitle = "Proceedings of the ACM Platform for Advanced Scientific Computing Conference",
month = "June",
publisher = "ACM New York, NY, USA, 2018",
title = "{B}alanced {G}raph {P}artition {R}efinement using the {G}raph p-{L}aplacian",
year = "2018",
}