paper
arXiv cs.LG
November 18th, 2026 at 5:00 AM

Graph neural networks and the energetic cavity method for combinatorial optimization

arXiv:2609.07456v2 Announce Type: replace-cross 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 much stronger than other deep learning approaches, we still find that simulated annealing is generally as good for the same computational cost.

#research

Get stories like this every Monday

The week's most important AI news in one email. Free, unsubscribe anytime.

Score: 3.12

Engagement proxy: 0

Canonical link: https://arxiv.org/abs/2609.07456