Publication Type

Journal Article

Version

acceptedVersion

Publication Date

10-2024

Abstract

Graphs are ubiquitous in real-world applications, such as computation graphs and social networks. Partitioning large graphs into smaller, balanced partitions is often essential, with the biobjective graph partitioning problem aiming to minimize both the“cut” across partitions and the imbalance in partition sizes. However, existing heuristic methods face scalability challenges or overlook partition balance, leading to suboptimal results. Recent deep learning approaches, while promising, typically focus only on node-level features and lack a truly end-to-end framework, resulting in limited performance. In this paper, we introduce a novel method based on graph neural networks (GNNs) that leverages multilevel graph features and addresses the problem end-to-end through a bi-objective formulation. Our approach explores node-, local-, and globallevel features, and introduces a well-bounded bi-objective function that minimizes the cut while ensuring partition-wise balance across all partitions. Additionally, we propose a GNN-based deep model incorporating a Hardmax operator, allowing the model to optimize partitions in a fully end-to-end manner. Experimental results on 12 datasets across various applications and scales demonstrate that our method significantly improves both partitioning quality and scalability compared to existing bi-objective and deep graph partitioning baselines.

Keywords

Graph Partition, End-to-end, Bi-objective, Graph Neural Networks

Discipline

Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Neural Networks

Volume

181

First Page

1

Last Page

21

ISSN

0893-6080

Identifier

10.1016/j.neunet.2024.106823

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.neunet.2024.106823

Download

Share

COinS