GitHub - amazon-science/co-with-gnns-example

Abstraction: Physics-inspired GNNs solving NP-hard combinatorial optimization via QUBO relaxation

Key points:

• Demonstrates GNNs solving NP-hard problems cast as Quadratic Unconstrained Binary Optimization (QUBO): MaxCut, Minimum Vertex Cover, Maximum Independent Set, Ising spin glasses, and polynomial generalizations (PUBO).
• Approach: relax the QUBO Hamiltonian into a differentiable loss; train GNN unsupervised; project soft node assignments to binary integers post-training.
• GNN layers aggregate one-hop neighborhood information; stacking layers extends the receptive field for long-range propagation.
• Results show the GNN optimizer performs on par with or better than existing solvers and scales to problems with millions of variables.
• Based on Schuetz, Brubaker, Katzgraber (arXiv 2107.01188); implemented with the open-source DGL library; runs in ~30-60 seconds on a standard laptop.

Connections: Amazon · Graph Neural Networks · Combinatorial Optimization · Quadratic Unconstrained Binary Optimization

Source: https://github.com/amazon-research/co-with-gnns-example