Solving Maximum Weighted Matching problem using Graph Neural Networks

Abstract

In this work we train a graph neural network model to solve the Maximum Weighted Matching problem on graphs using supervised learning. Unfortunately, the final results were below the set expectations. The model seemed to be slightly worse than a standard greedy algorithm, mainly because the greedy algorithm on average performed very well compared to the optimal solution. However, the neural network did show potential at solving the problem for more narrow graph datasets and graphs that were particularly difficult for the greedy algorithm. The results do not imply that graph neural networks in general cannot beat greedy algorithms, but rather suggest that different approaches or further improvement are needed.