.png){kind=icon}
Return
GON: End-to-end optimization framework for constraint graph optimization problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2022.109697.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Real-world computational applications often require solving combinatorial optimization problems on graphs, i.e., graph optimization problems (GOPs). An emerging trend is using graph neural networks (GNNs) to tackle GOPs. However, for GOPs with constraints, a great challenge faced by GNNs-based methods is to produce optimal solutions that satisfy the constraints. Existing methods relying on supervised learning require a large amount of labeled data, while unsupervised learning methods often require designing elaborate network architectures. To address these limitations, we propose an end-to-end optimization framework for constraint GOPs, coined Graph Optimization Network (GON). GON is a simple and effective method aiming to address general GOPs without designing specific network architectures for different problems. The proposed framework is evaluated on two typical constraint GOPs, one with only soft constraints (the balanced graph partitioning problem) and the other with hard constraints (the maximum independent set problem). We model the two problems as node assignment problems and design the corresponding constraint-aware loss function for each so that the model can be directly optimized to generate optimal solutions that satisfy the constraints. Experiments on various benchmarks show that the proposed GON equipped with a vanilla GNN can achieve excellent performance on both GOPs, superior to state-of-the-art methods. The results suggest that GON is a promising solver to address NP-hard GOPs.(c) 2022 Elsevier B.V. All rights reserved.
Keywords:
Graph optimization
Graph neural networks
Balanced graph partitioning
Maximum independent set
Journal
K
IF:
7.6
Papers:
1.3W
Citations:
4.5W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSave
View more