图神经网络发Nature子刊,却被爆比普通算法慢104倍,质疑者:灌水新高度?
近年来,神经网络解决了应用和基础科学方面的诸多难题,其中就包括离散组合优化问题,这也是我们理解计算极限的基础。
Martin JA Schuetz 等人 2022 年的研究《Combinatorial optimization with physics-inspired graph neural networks》[4]提出使用受物理启发的无监督图神经网络(GNN)来解决图上的组合优化问题,这种方法似乎很有前途,并发表在具有高影响力的期刊(《自然 · 机器智能》)上。该研究测试了 GNN 在两个标准优化问题上的性能:最大切割和最大独立集(MIS)。这种新提出的 GNN优化器有一个非常好的特性:它可以扩展到许多更大的实例问题上。
论文地址:http://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 ),类似于迫击炮打蚊子」,既浪费资源,效果也不好。
论文地址:http://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 等人提出的优化器)不满足上述要求,并且无法与简单的标准算法竞争以解决困难的优化问题。探究神经网络是否可以满足这一要求,或者它们的失败是否有更深层次的原因,这一点至关重要。
- 从AI为宠物投保这个「小事」讲起,保险变革开始了
- 华为MindSpore架构师王紫东:当生物计算领域「遇灾」,MindSpore做了何解?
- 从产线到星空,这些AI工程师带着算法上天入地
- 数实融合驱动数字未来 影谱科技携沉浸式数字技术亮相2022服贸会
- 驱动虚实融合,影谱科技在WAIC推出多款智能视觉及元宇宙新品
- 英伟达和Ampere共同推出云游戏Arm服务器:每台最多支持160个用户
- 扩散模型背后数学太难了,啃不动?谷歌用统一视角讲明白了
- 悟空搜索“降世”,能否大闹搜索引擎“天宫”?
- 蘑菇车联与北京通州达成合作,打造车路云一体化智慧交通系统
- LeCun没看好的AGI,传奇程序员John Carmack:已创业,融资两千万美元
- 蘑菇车联与无锡梁溪区签约,将打造数字孪生城市交通底座
- 这场比赛,让上百个AI智能体「卷起来了」
- 大模型时代,那些一起训练AI模型的企业是怎么应对数据顾虑的?
- 数字人赛道热度正高,AI技术如何创造不一样的“灵魂”?
- Unity否决175亿美元并购提议:准备自己收购广告公司
- 消费级GPU可用,文本转图像开源新模型Stable Diffusion生成宇宙变迁大片
- 全球游戏引擎商业化进入新阶段,国内头号玩家Cocos“三分天下”
- 墨芯获评大湾区高成长性企业TOP50
- 图神经网络发Nature子刊,却被爆比普通算法慢104倍,质疑者:灌水新高度?
- 亚马逊欲17亿美元收购iRobot,扫地机器人“含金量”几何?