图神经网络发Nature子刊，却被爆比普通算法慢104倍，质疑者：灌水新高度？

机器之心报道

机器之心编辑部

GNN 是近年来非常火的一个领域。最近，一篇 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 等人提出的优化器）不满足上述要求，并且无法与简单的标准算法竞争以解决困难的优化问题。探究神经网络是否可以满足这一要求，或者它们的失败是否有更深层次的原因，这一点至关重要。

WAIC黑客马拉松——蚂蚁财富双赛道

行情波动下的金融问答挑战赛

该赛道在财富社区的问答数据基础上，针对每个用户的问题，利用检索、深度学习、自然语言处理等技术，生成出流畅、准确、合理的针对该问题的回答。

AntSQL大规模金融语义解析中文Text-to-SQL挑战赛

该赛道采用金融领域的表格作为数据源，涵盖了基金的产品和属性，提供在此基础上的标注的Query-SQL对，希望选手们能在此基础上训练深度学习模型，将自然语言准确的转换为可查询的SQL语句。

赛事福利：

1. 最高可获奖金10万元，总奖金20万；
2. 获奖选手均可获得大赛荣誉证书；
3. 获奖选手受邀参加2022世界人工智能大会WAIC · AI开发者日举行的颁奖典礼 ；
4. 优秀选手有机会获得Offer绿色通道，入职蚂蚁财富认知智能团队；
5. 邀请好友参赛即可获得 扫地机器人、空气炸锅，欢迎加入钉钉群了解详情。
   

© THE END 

转载请联系本公众号获得授权

投稿或寻求报道：content@jiqizhixin.com