论文标题
在求解组合优化问题（例如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-HARD组合优化问题。它描述了如何在示例实例上训练网络，并评估了最终的GNN启发式方法，并应用了广泛使用的技术来确定其成功的能力。显然，利用此类网络的强大能力``学习''的想法是在这种失调的方法中复杂的多模式能量景观的复杂性似乎很诱人。并且根据观察到的性能，启发式的承诺将具有高度可扩展性，并且在输入尺寸$ n $中的计算成本线性，尽管由于GNN本身，因此在事前可能存在明显的开销。但是，仔细检查表明，该GNN的报告结果仅比梯度下降的结果要好得多，例如，对于最大切割而言，贪婪的算法的表现棒极了。讨论还突出了我认为在启发式方法评估中的一些常见误解。
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.
