Balanced Graph Partition Refinement using the Graph p-Laplacian
Informazioni aggiuntive
Autori
Simpson T.,
Dimosthenis P.,
Kourounis D.,
Fujita K.,
Yamaguchi T.,
Tsuyoshi I.,
Schenk O.
Tipo
Contributo in atti di convegno
Anno
2018
Lingua
Inglese
Sommario
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.
Parole chiave
Combinatorial mathematics, Graph Theory, Laplace Equations, Parallel processing
Titolo atti di convegno
Proceedings of the ACM Platform for Advanced Scientific Computing Conference
Number ( Month )
June
Editore
ACM New York, NY, USA, 2018
Nome convegno
PASC18
Luogo convegno
Basel, Switzerland
Data convegno
July 02 to 04, 2018
