← 研踪 PaperTrailarXiv:2609.07456 · v2
Graph neural networks and the energetic cavity method for combinatorial optimization
首次提交 2026-09-07 21:07
版本更新 2026-11-17 22:23
雷达观测 2026-11-18 16:38
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-17 22:23 · 最新观测版本
Graph neural networks and the energetic cavity method for combinatorial optimization
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.
查看此版本解读 →查看此版本原文 ↗