Graph neural networks enhanced with heuristics improve spin model optimization
Graph neural networks and the energetic cavity method for combinatorial optimization
Machine Learning
Summary
Finding the best arrangement of spins in certain physics problems helps solve many puzzles in computing called combinatorial optimization. The authors studied how graph neural networks (GNNs), a kind of AI, can approximate these best spin arrangements but found GNNs alone didn't do as well as classic heuristic methods. By adding ideas from these heuristics into the GNN design, performance improved a lot. Still, a traditional method called simulated annealing was just as good or better for similar computing effort.
What this means in practice
- •For operations research analysts: Use enhanced graph neural networks to find approximate solutions in large combinatorial optimization problems faster than some existing AI methods.
- •For software engineers in logistics: Incorporate improved GNN-based heuristics into routing and scheduling software to handle complex decision problems formulated as spin models.
Authors
Joe Bacchus George, George T. Cantwell
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.