Graph Neural Networks for Solving Combinatorial Optimization Problems

Combinatorial optimization (CO) problems are essential in various scientific and industrial applications. This thesis explores the use of unsupervised Graph Neural Networks (GNNs) for solving CO problems reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. We propose the incorporation of novel type of recurrence in GNNs, utilizing intermediate model predictions as dynamic graph features. Our investigation leads to the development of a novel GNN architecture that minimizes a QUBO-based loss function through iterative refinement. Experimental results on benchmark datasets for maximum cut, graph coloring, and maximum independent set problems show that the proposed algorithm significantly outperforms existing learning-based approaches and rivals state-of-the-art heuristics, demonstrating perfect scalability on large instances.