Analysis of Various GNNs in Solving MaxCut Problem

Extraction of information from graph data is essential since most data in the real world are dynamic, large, and without fixed structure, unlike images. Graph neural networks (GNNs) harness the power of graphs, efficiently examining graph data and help make inferences from complex data structures, making them an invaluable tool in domains like social network analysis. GNNs have shown promise in solving combinatorial optimization problems which involve extracting a good candidate solution by scanning over the search space. The vastness of the search space often renders the optimal solution search a difficult task. Many previous works demonstrate the use of GNNs in solving problems like graph coloring and MaxCut problem. In this paper, we analyze the ability of different GNN architectures to tackle the MaxCut problem, posed as a Quadratic Unconstrained Binary Optimization (QUBO) problem, minimizing the loss function based on the QUBO objective.