标题： 图神经网络启发式方法在求解最大割（Max-Cut）等组合优化问题时无法超越贪心算法的能力 显示英文标题

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

摘要： 在《自然·机器智能》4卷，367页（2022年），Schuetz等人提供了一种方案，利用图神经网络（GNN）作为启发式方法来解决各种经典的NP难组合优化问题。 它描述了网络如何在样本实例上进行训练，以及由此产生的GNN启发式方法如何通过广泛使用的技术进行评估，以确定其成功的能力。 显然，这种无需人工干预的方法利用这些网络的强大能力来“学习”复杂多峰能量景观的精妙之处似乎很有吸引力。 并且根据观察到的性能，该启发式方法有望具有高度可扩展性，计算成本与输入规模线性相关$n$，尽管由于GNN本身的存在，前因子可能有显著的额外开销。 然而，仔细检查显示，这种GNN报告的结果仅比梯度下降稍好一点，并且在Max-Cut问题上被贪心算法超越。 讨论还突出了我认为在启发式方法评估中存在的一些常见误解。 显示英文摘要

摘要： 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.