An end-to-end bi-objective approach to deep graph partitioning

Area of Science:

• Computer Science
• Graph Theory
• Machine Learning

Background:

• Graph partitioning is crucial for large-scale networks like social networks and computation graphs.
• The bi-objective problem seeks to minimize edge cuts and balance partition sizes.
• Existing methods struggle with scalability or partition balance, and deep learning approaches lack end-to-end optimization.

Purpose of the Study:

• To introduce a novel, end-to-end graph partitioning method using graph neural networks (GNNs).
• To address the bi-objective graph partitioning problem by minimizing cuts and ensuring partition balance.
• To leverage multilevel graph features for improved partitioning performance.

Main Methods:

• Utilized graph neural networks (GNNs) with multilevel graph features (node, local, global).
• Formulated a bounded bi-objective function to minimize graph cuts and balance partition sizes.
• Developed a GNN-based deep model with a Hardmax operator for end-to-end optimization.

Main Results:

• The proposed GNN method significantly improved partitioning quality and scalability.
• Demonstrated superior performance compared to existing bi-objective and deep graph partitioning baselines.
• Validated on 12 diverse datasets across various applications and scales.

Conclusions:

• The novel GNN approach offers an effective end-to-end solution for bi-objective graph partitioning.
• This method enhances both the quality of partitions and the scalability for large graphs.
• The multilevel feature exploration and Hardmax operator contribute to improved performance.