The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Combinatorial optimization with physics-inspired graph neural networks
Open accessAbstract
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. Combinatorial optimization, the search for the minimum of an objective function within a finite but very large set of candidate solutions, finds many important and challenging applications in science and industry. A new graph neural network deep learning approach that incorporates concepts from statistical physics is used to develop a robust solver that can tackle a large class of NP-hard combinatorial optimization problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000 · cited 2×
“In the deep learning community, graph neural networks (GNNs) have seen a burst in popularity over the last few years [23–30].”
BackgroundMethodDeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582
Beitrag zur Theorie des Ferromagnetismus
Ising, E. (1925) · Zeitschrift für Physik · doi:10.1007/bf02980577 · Cited by 3,871
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3219890 · Cited by 3,733
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 1×
“For graphs with up to a few hundred nodes, we compare our GNN-based solver to the (approximate) polynomialtime Goemans-Williamson (GW) algorithm [81], which provides the current record for an approximate answer within some fixed multiplicative factor of the optimum (referred to as approximation ratio α), using semidef…”
MethodIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
A new model for learning in graph domains
Gori, M., Monfardini, G., & Scarselli, F. (2006) · Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. · doi:10.1109/ijcnn.2005.1555942 · Cited by 2,075
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
Cited by
Quantum bridge analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G., Hennig, R., & Du, Y. (2022) · Annals of Operations Research · doi:10.1007/s10479-022-04634-2 · Cited by 297
Multimodal learning with graphs
Ektefaie, Y., Dasoulas, G., Noori, A., Farhat, M., & Zitnik, M. (2023) · Nature Machine Intelligence · doi:10.1038/s42256-023-00624-6 · Cited by 166
“This message-passing strategy advances the MGL’s third component (Section 2) and has also been employed to solve combinatorial algorithms (Bellman-Ford and Prim’s algorithms) [94, 95] and chip floorplanning to design the physical layout of computer chips [96].”
MethodPhysics-Informed Graph Learning
Peng, C., Xia, F., Saikrishna, V., & Liu, H. (2022) · arXiv · doi:10.48550/arxiv.2202.10679 · Cited by 8
Metadata
- Authors
- Schuetz, M. J. A., Brubaker, J. K., & Katzgraber, H. G.
- Venue
- Nature Machine Intelligence
- Published
- 2022-04-21
- Volume
- 4
- Issue
- 4
- Pages
- 367-377
- ISSN
- 2522-5839 (ISSN-L)
- OpenAlex
- W3181036294
- Cited by
- 203
- References
- 21
- FWCI
- 13.25
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Combinatorial optimization with physics-inspired graph neural networks. https://app.cochat.ai/papers/10.1038/s42256-022-00468-6
- The paper
- Schuetz, M. J. A., Brubaker, J. K., & Katzgraber, H. G. (2022). Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence. https://doi.org/10.1038/s42256-022-00468-6
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.