GNN是近年来非常热门的领域。最近，Nature子期刊的一篇论文提出了一种用GNN解决组合优化问题的方法，并声称GNN优化器的性能可以媲美甚至超过现有的求解器。不过这篇论文也引来了一些质疑：有人指出这个GNN的性能其实还不如经典的贪心算法，速度比贪心算法慢很多（对于一百万个变量的问题，贪心算法算法比GNN快104倍）。所以怀疑论者说，“我们没有看到任何充分的理由使用这些GNN来解决这个问题。这就像用大锤敲打螺母一样。”他们希望这些论文的作者在声称该方法的优越性之前能够先解决困难的问题。比较基准。近年来，神经网络解决了应用科学和基础科学中的许多难题，包括离散组合优化问题，这些问题是我们理解计算极限的基础。MartinJASchuetz等人在2022年进行的一项研究。《Combinatorial optimization with physics-inspired graph neural networks》[4]提出使用受物理学启发的无监督图神经网络(GNN)来解决图上的组合优化问题似乎很有希望，并发表在高影响力期刊上(《自然 · 机器智能》)。该研究测试了GNN在两个标准优化问题上的性能：最大割和最大独立集(MIS)。这个新提出的GNN优化器有一个非常好的特性：它可以扩展到许多更大的实例问题。论文地址：https://arxiv.org/pdf/2107.01188.pdf然而，最近一篇新论文《Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms》对MartinJASchuetz等人的研究提出了质疑，认为MartinJASchuetz等人提出的GNN优化器是“用大锤敲坚果，类似于用迫击炮打蚊子”，既浪费资源，又效果不佳。论文地址：https://arxiv.org/abs/2206.13211MIS问题的定义如下：给定一个n个节点，固定度d的无向随机正则图（d-RRG），其独立集（IS）为指不包含任何最近邻对的顶点子集；MIS问题需要找到最大的IS，其大小称为α。MIS是一个NP-hard问题，但人们希望找到一种算法来找到大小尽可能接近多项式时间最大值的IS。此外，好的算法不应因较大的n值而出现性能下降。MartinJASchuetz等人提出的新GNN。可以对非常大的图（n≤10^6）求IS：算法运行时间与问题大小成正比：t～n^1.7，算法性能随着n的增加保持稳定，如下图1所示。然而，当将所提出的GNN的性能与其他可用算法进行比较时，本研究仅与Boppana-Halldorsson(BH)近似算法[8]进行比较，该算法在时间t～n^中运行，n≤5002.9。实际上还有许多其他算法计算IS的速度比BH快得多，本研究应该将所提出的GNN优化器与这些算法进行比较。其中，最简单的算法是贪心算法（GA）[9]。基于度的贪婪算法（DGA）经过优化后，运行时间与节点数n几乎呈线性关系。本研究比较了MartinJASchuetz等人提出的GNN优化器的性能。（空心）和DGA（实心）用于在d=3和d=5的d-RRG上寻找MIS。如图1（右）所示，在运行时间和问题大小（节点数）之间的关系方面，DGA比GNN好得多。前渐近效应），而GNN的运行时间与节点数n几乎呈二次关系。该研究认为MartinJASchuetz等人声称“基于图神经网络的优化器的性能与现有求解器一样好或更好，有能力超越当前的SOTA模型，并且是数万个变量的问题”经不起推敲并且与实际实验结果不一致。MartinJASchuetz等人应该修改论文。该研究详细阐述了DGA的性能，并认为这种简单的贪心算法应被视为最小基线，任何新算法都必须至少执行比DGA更好的被采用。当然，DGA只是一个极其简单的算法，还有许多其他标准算法优于DGA。MariaChiara等人在2019年的论文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》提供了对性能的深入研究用于解决MIS问题的几种算法。基于此，该研究提出了一个问题：“在评估一种新的优化算法时，应该将哪些真正困难的问题作为测试算法性能的基准？”例如，研究认为寻找MIS可能只是一个容易的问题；对于较大的d，优化要求可能会更高，因为较大IS的聚类可能会给算法搜索MIS带来障碍。因此，如果要选择一个难题作为基准测试，一个可能的答案是在d>16的d-RRG上研究MIS。这里d=20和d=100的结果可以与2019年论文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》中给出的结果进行比较。很明显，一个好的优化算法应该在n的多项式时间内完成，如果是线性的就更好了，找到的解的质量应该比现有的简单算法好，并且质量不应该随着n的增加而下降slipped.该研究得出结论：目前，基于神经网络的优化器，例如MartinJASchuetz等人提出的优化器。不满足上述要求，无法与解决困难优化问题的简单标准算法竞争。探索神经网络是否可以满足这一要求，或者是否有更深层次的原因导致其失败至关重要。
