GON: End-to-end optimization framework for constraint graph optimization problems

摘要

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.