Combinatorial Optimization with Physics-Inspired Graph Neural Networks

Abstract

Combinatorial optimization problems are pervasive across science and industry. Modern deep learning tools are poised to solve these problems at unprecedented scales, but a unifying framework that incorporates insights from statistical physics is still outstanding. Here we demonstrate how graph neural networks can be used to solve combinatorial optimization problems. Our approach is broadly applicable to canonical NP-hard problems in the form of quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems. We apply a relaxation strategy to the problem Hamiltonian to generate a differentiable loss function with which we train the graph neural network and apply a simple projection to integer variables once the unsupervised training process has completed. We showcase our approach with numerical results for the canonical maximum cut and maximum independent set problems. We find that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables.

Manuscript: 13 pages, 5 figures, 1 table. Supplemental Material: 1 page, 1 table

References in corpus (9)

• A Quantum Approximate Optimization Algorithm
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Empirical performance bounds for quantum approximate optimization
• Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
• Efficient Combinatorial Optimization Using Quantum Annealing
• Utilising Graph Machine Learning within Drug Discovery and Development

Cited by in corpus (37)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Attention-based graph neural networks: a survey
• Graph neural network initialisation of quantum approximate optimisation
• Quantum approximate optimization via learning-based adaptive optimization
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Roadmap on machine learning glassy dynamics
• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Real-time Trading System based on Selections of Potentially Profitable, Uncorrelated, and Balanced Stocks by NP-hard Combinatorial Optimization
• Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Discovering dynamic laws from observations: the case of self-propelled, interacting colloids
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Correlation-diversified portfolio construction by finding maximum independent set in large-scale market graph
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
• Transit facility allocation: Hybrid quantum-classical optimization
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Deep-learning-aided dismantling of interdependent networks
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• A Survey of Methods for Converting Unstructured Data to CSG Models
• Qudit-inspired optimization for graph coloring
• Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
• A QUBO Framework for Team Formation
• Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Optimization via Quantum Preconditioning
• Higher-Order Portfolio Optimization with Quantum Approximate Optimization Algorithm
• Nearest-Neighbours Neural Network architecture for efficient sampling of statistical physics models
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems
• In-Depth Investigation of Phase Transition Phenomena in Network Models Derived from Lattice Models
• Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians
• A Transfer Framework for Enhancing Temporal Graph Learning in Data-Scarce Settings