# Combinatorial Optimization with Physics-Inspired Graph Neural Networks

**Authors:** Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber  
**arXiv:** [2107.01188](https://arxiv.org/abs/2107.01188)  
**Date:** 2021-07-02  
**Summary page:** https://www.summarizepaper.com/en/paper/2107.01188v1/

## Key points

- Authors explore the use of graph neural networks (GNNs) for combinatorial optimization problems
- GNN approach applicable to a wide range of NP-hard problems
- Relaxation strategy proposed for Hamiltonian problem to generate differentiable loss function
- GNN trained using this loss function to optimize solution for combinatorial problem
- Projection technique applied to convert continuous variables into integer values after training
- Numerical results provided for maximum cut and maximum independent set problems, showing GNN outperforms existing solvers in solution quality
- Method can scale beyond current state-of-the-art approaches and handle problems with millions of variables

## Summary

In their paper titled "Combinatorial Optimization with Physics-Inspired Graph Neural Networks," authors Martin J. A. Schuetz, J. Kyle Brubaker, and Helmut G. Katzgraber explore the use of graph neural networks (GNNs) to solve combinatorial optimization problems. They demonstrate that their approach is applicable to a wide range of canonical NP-hard problems, including quadratic unconstrained binary optimization problems such as maximum cut, minimum vertex cover, and maximum independent set. The authors propose a relaxation strategy for the problem Hamiltonian which allows them to generate a differentiable loss function. This loss function is then used to train the GNN enabling it to optimize the solution for the given combinatorial problem. Once the unsupervised training process is completed a simple projection technique is applied to convert the continuous variables into integer values. To showcase the effectiveness of their approach, the authors provide numerical results for two canonical combinatorial optimization problems: maximum cut and maximum independent set. They compare their GNN optimizer with existing solvers and find that it performs on par or even outperforms them in terms of solution quality. Additionally they highlight that their method can scale beyond current state-of-the-art approaches and handle problems with millions of variables. Overall this research demonstrates how graph neural networks can be leveraged to tackle challenging combinatorial optimization problems effectively. The proposed relaxation strategy and training process enable efficient optimization while maintaining competitive performance compared to existing solvers.