Metraipolis › archive › dc_420ccd88429e
Graph neural networks and the energetic cavity method for combinatorial optimization — arXiv:2609.07456
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07456
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:59:13.531Z
- SHA-256 of the archived text
289feeebe71acade4686e32ede417d2ccae3a774334ffa017d8dfcefa8373888- Stable URL of this page
https://metraipolis.com/documento/dc_420ccd88429e
How to cite
Graph neural networks and the energetic cavity method for combinatorial optimization — arXiv:2609.07456 — arXiv (en), https://arxiv.org/abs/2609.07456 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_420ccd88429e (Metraipolis archive dc_420ccd88429e, sha256 289feeebe71acade4686e32ede417d2ccae3a774334ffa017d8dfcefa8373888)
BibTeX
@misc{dc420ccd88429e,
title = {Graph neural networks and the energetic cavity method for combinatorial optimization — arXiv:2609.07456},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07456},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_420ccd88429e; sha256 289feeebe71acade4686e32ede417d2ccae3a774334ffa017d8dfcefa8373888},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07456. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG). Categorie arXiv: Disordered Systems and Neural Networks (cond-mat.dis-nn) ; Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.07456 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T13:39:43.222Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).