  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.

Disordered Systems and Neural Networks;Artificial Intelligence;Machine Learning;Optimization and Control;Quantum Physics