CaltechAUTHORS
  A Caltech Library Service

Combinatorial optimization with physics-inspired graph neural networks

Schuetz, Martin J. A. and Brubaker, J. Kyle and Katzgraber, Helmut G. (2022) Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4 (4). pp. 367-377. ISSN 2522-5839. doi:10.1038/s42256-022-00468-6. https://resolver.caltech.edu/CaltechAUTHORS:20220505-181556200

[img] PDF - Accepted Version
See Usage Policy.

2MB
[img] PDF (Supplementary listings 1 and 2 and Table 1) - Supplemental Material
See Usage Policy.

702kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220505-181556200

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1038/s42256-022-00468-6DOIArticle
https://rdcu.be/cMPy0PublisherFree ReadCube access
https://arxiv.org/abs/2107.01188arXivDiscussion Paper
https://web.stanford.edu/~yyye/yyye/Gset/Related ItemData
https://networkx.org/Related ItemNetworkx
https://github.com/amazon-research/co-with-gnns-exampleRelated ItemCode
ORCID:
AuthorORCID
Schuetz, Martin J. A.0000-0001-5948-6859
Brubaker, J. Kyle0000-0002-6439-5270
Katzgraber, Helmut G.0000-0003-3341-9943
Additional Information:© 2022 Nature Publishing Group. Received 09 July 2021; Accepted 21 February 2022; Published 21 April 2022. We thank F. Brandao, G. Karypis, M. Kastoryano, E. Kessler, T. Mullenbach, N. Pancotti, M. Resende, S. Roy, G. Salton, S. Severini, A. Urweisse and J. Zhu for fruitful discussions. Data availability: The data necessary to reproduce our numerical benchmark results are publicly available at https://web.stanford.edu/~yyye/yyye/Gset/. Random d-regular graphs have been generated using the open-source networkx library (https://networkx.org). Code availability: An end-to-end open source demo version of the code implementing our approach has been made publicly available at https://github.com/amazon-research/co-with-gnns-example. Contributions: All authors contributed to the ideation and design of the research. M.J.A.S. and J.K.B. developed and ran the computational experiments and also wrote the initial draft of the the manuscript. H.G.K. supervised this work and revised the manuscript. Competing interests: M.J.A.S., J.K.B. and H.G.K. are listed as inventors on a US provisional patent application (no. 7924-38500) on combinatorial optimization with graph neural networks. Peer review information: Nature Machine Intelligence thanks Thomas Vandal and Estelle Inack for their contribution to the peer review of this work.
Group:AWS Center for Quantum Computing
Subject Keywords:Computer science; Operational research; Quantum information; Statistical physics
Issue or Number:4
DOI:10.1038/s42256-022-00468-6
Record Number:CaltechAUTHORS:20220505-181556200
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220505-181556200
Official Citation:Schuetz, M.J.A., Brubaker, J.K. & Katzgraber, H.G. Combinatorial optimization with physics-inspired graph neural networks. Nat Mach Intell 4, 367–377 (2022). https://doi.org/10.1038/s42256-022-00468-6
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:114595
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:05 May 2022 19:11
Last Modified:05 May 2022 19:11

Repository Staff Only: item control page