Manara - Qatar Research Repository
Browse

Applying Graph Neural Networks to the Decision Version of Graph Combinatorial Optimization Problems

Download (1.19 MB)
journal contribution
submitted on 2024-02-12, 10:26 and posted on 2024-02-12, 10:27 authored by Raka Jovanovic, Michael Palk, Sertac Bayhan, Stefan Voss

In recent years, there has been a significant increase in the application of graph neural networks on a wide range of different problems. A specially promising direction of research is on graph convolutional neural networks (GCN). This work focuses on the application of GCNs to graph combinatorial optimization problems (GCOPs), specifically on their decision versions. GCNs are applied on the family of GCOPs in which the objective function is directly related to the number of vertices in a graph. The selected problems are the minimum vertex cover, maximum clique, minimum dominating set and graph coloring. In this work, a framework is proposed for solving problems of this type. The performance of this approach is explored for standard multi-layer GCNs using different types of convolutional layers. On top of this, we propose a new structure that is based on graph isomorphism networks. Computational experiments show that this new structure is significantly more efficient than basic structures. To further improve the performance of this method, the use of GCN ensembles is also explored. When using GCNs to generate solution values for GCOPs, they often correspond to non-feasible solutions because they violate the problem boundaries. This issue is addressed by defining an asymmetric loss function that is used during the GCN training. The proposed method is evaluated on a large set of training data consisting of graph solution pairs that can also be accessed online.

Other Information

Published in: IEEE Access
License: http://creativecommons.org/licenses/by/4.0
See article on publisher's website: https://dx.doi.org/10.1109/access.2023.3268212

Funding

Open Access funding provided by the Qatar National Library.

History

Language

  • English

Publisher

IEEE

Publication Year

  • 2023

License statement

This Item is licensed under the Creative Commons Attribution 4.0 International License

Institution affiliated with

  • Hamad Bin Khalifa University
  • Qatar Environment and Energy Research Institute - HBKU