Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut

Abstract

In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme to employ graph neural networks (GNN) as a heuristic to solve a variety of classical, NP-hard combinatorial optimization problems. It describes how the network is trained on sample instances and the resulting GNN heuristic is evaluated applying widely used techniques to determine its ability to succeed. Clearly, the idea of harnessing the powerful abilities of such networks to ``learn'' the intricacies of complex, multimodal energy landscapes in such a hands-off approach seems enticing. And based on the observed performance, the heuristic promises to be highly scalable, with a computational cost linear in the input size $n$, although there is likely a significant overhead in the pre-factor due to the GNN itself. However, closer inspection shows that the reported results for this GNN are only minutely better than those for gradient descent and get outperformed by a greedy algorithm, for example, for Max-Cut. The discussion also highlights what I believe are some common misconceptions in the evaluations of heuristics.

arXiv commentRevTex4, 2 pages, 1 figure; comment on arXiv:2107.01188. Related information at http://www.physics.emory.edu/faculty/boettcher/

References in corpus (7)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Extremal Cuts of Sparse Random Graphs
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices
• Conjecture on the maximum cut and bisection width in random regular graphs
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass

Cited by in corpus (9)

• Quantum approximate optimization via learning-based adaptive optimization
• Roadmap on machine learning glassy dynamics
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• Optimization via Quantum Preconditioning
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Nearest-Neighbours Neural Network architecture for efficient sampling of statistical physics models
• Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems