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

Jovanovic R., Palk M., Bayhan S., Voss S.

IEEE Access, cilt.11, ss.38534-38547, 2023 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 11
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1109/access.2023.3268212
  • Dergi Adı: IEEE Access
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, INSPEC, Directory of Open Access Journals
  • Sayfa Sayıları: ss.38534-38547
  • Anahtar Kelimeler: Combinatorial optimization, deep learning, graph neural networks, loss function, NP-hard problem
  • Gazi Üniversitesi Adresli: Hayır

Özet

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.