Graph neural networks and the energetic cavity method for combinatorial optimization
Abstract
We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.
Related
- Regional accuracy of physics-informed neural networks (PINNs) for recirculation in a deep lid-driven cavity
- Feature tracking in physics-informed neural networks via joint optimization of nonlinear deformation manifolds: application to shocks
- Measurement-Efficient Differentiable Quantum Architecture Search for Combinatorial Optimization
- Quantum-echo Markov process for combinatorial optimization
- Frequency-inference method for reduced modeling of energetic particle modes (EPM) utilizing resonant auto-optimization remnants of imperfect time-scale separation
BibTeX
@misc{george2026graph,
title = {{Graph neural networks and the energetic cavity method for combinatorial optimization}},
author = {Joe Bacchus George and George T. Cantwell},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07456},
eprint = {2609.07456},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07456},
}
RIS
TY - UNPB
TI - Graph neural networks and the energetic cavity method for combinatorial optimization
AU - Joe Bacchus George
AU - George T. Cantwell
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07456
UR - https://arxiv.org/abs/2609.07456
AB - We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.
ER -