Nature上的GNN，比贪心慢104倍！灌水新高度？

Nature 最新发表论文提出了一种用 GNN解决组合优化问题的方法，并声称该 GNN 优化器的性能与现有的求解器相当，甚至超过了现有的求解器。不过，这篇论文引来了一些质疑：有人指出，这个 GNN 的性能其实还不如经典的贪心算法，而且速度还比贪心算法慢得多（对于有一百万个变量的问题，贪心算法比 GNN 快 104 倍）。所以质疑者表示，「我们看不出有什么好的理由用这些 GNN 来解决该问题，就像用大锤砸坚果一样。」他们希望这些论文作者能够在宣称方法优越性之前，先和困难问题的基准比较一下。

近年来，神经网络解决了应用和基础科学方面的诸多难题，其中就包括离散组合优化问题，这也是我们理解计算极限的基础。

Martin JA Schuetz 等人 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》对 Martin JA Schuetz 等人的研究提出了质疑，认为 Martin JA Schuetz 等人提出的 GNN 优化器是「用大锤敲坚果（ Cracking nuts with a sledgehammer ），类似于迫击炮打蚊子」，既浪费资源，效果也不好。

论文地址：https://arxiv.org/abs/2206.13211

MIS 问题的定义如下：给定一个具有 n 个节点、度固定为 d 的无向随机正则图（d-RRG），独立集（IS）是指不包含任何最近邻对的顶点子集；MIS 问题需要找到最大的 IS，其大小称为α。MIS 是一个 NP-hard 问题，但人们希望找到一种算法，以在多项式时间内找到一个大小尽可能接近最大值的 IS。此外，一个好算法不应因为 n 值较大而性能降低。

Martin JA Schuetz 等人提出的新型 GNN 可以为非常大的图（n≤ 10^6）找到 IS：算法运行时间与问题大小成比例：t∼ n^1.7，并且算法性能随着 n 的增加保持稳定，如下图 1 所示。

然而，当将所提 GNN 与其他可用算法进行性能比较时，该研究仅与 Boppana-Halldorsson（BH）近似算法 [8] 做了比较，该算法在 n≤ 500 时，运行时间 t∼n^2.9。

实际上还有许多其他计算 IS 的算法比 BH 快得多，该研究应该将所提 GNN 优化器与这些算法进行比较。其中，最简单的算法就是贪心算法（GA）[9]。基于度的贪心算法（DGA）经过优化后，运行时间几乎与节点数目 n 呈线性关系。

该研究比较了 Martin JA Schuetz 等人提出的 GNN 优化器（空心）和 DGA（实心）在 d=3 和 d=5 的 d-RRG 上查找 MIS 的性能。 如图 1（右）所示，从运行时间与问题大小（节点数）的关系上看，DGA 比 GNN 好得多，前者的运行时间几乎与节点数 n 呈线性关系（指数是 1.15 可能是由于预渐近效应），而 GNN 的运行时间与节点数 n 几乎呈二次关系。

该研究认为 Martin JA Schuetz 等人的主张「基于图神经网络的优化器的性能与现有的求解器相当或优于现有的求解器，具有超越当前 SOTA 模型的能力，能够扩展到具有数百万个变量的问题」，经不起推敲，与实际实验结果不一致，Martin JA Schuetz 等人应对论文予以修改。

该研究详细阐明了 DGA 的性能，并认为这种简单的贪心算法应该被视为一个最低基准，任何新算法的性能必须至少比 DGA 好才能被采用。

当然，DGA 只是一种极为简单的算法，还有许多其他标准算法优于 DGA。Maria Chiara 等人 2019 年的论文《Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs》对多个解决 MIS 问题的算法性能进行了深入的研究。

基于此，该研究提出一个问题：「评估一个新的优化算法时，应该用什么真正困难的问题作为测试算法性能的基准？」

例如，该研究认为，在 d<16 的 d-RRG 中找出 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 的增加而质量有所下滑。

该研究总结道：目前，基于神经网络的优化器（如 Martin JA Schuetz 等人提出的优化器）不满足上述要求，并且无法与简单的标准算法竞争以解决困难的优化问题。探究神经网络是否可以满足这一要求，或者它们的失败是否有更深层次的原因，这一点至关重要。