LLM2D
在机器学习社区重新审视GNN的表达能力研究:局限性、问题及修正
Rethinking GNN Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections
作者: Guanyu Cui, Zhewei Wei, Hsin-Hao Su
发布日期: 2/18/2025
arXiv ID: oai:arXiv.org:2410.01308v2

摘要

arXiv:2410.01308v2 宣告类型: replace-cross 摘要:图神经网络(GNNs)的成功激发了对其表达能力的理论探索。在图机器学习领域,研究人员通常将GNNs与Weisfeiler-Lehman(WL)测试视为理论分析的基础。然而,我们识别出这种方法存在两大主要局限:(1)WL测试的语义涉及通过一组逻辑语句验证纯粹的结构等价性。因此,它们在定义表达能力时不太匹配,通常定义为GNNs能表达的函数类别,并不适合处理具有特性的图;(2)通过利用通信复杂性,我们展示了GNN的容量下限(深度与宽度的乘积)模拟一次WL测试迭代所需的容量几乎线性增长于图的大小。这一发现表明WL测试不是局部可计算的,并且与消息传递GNNs不符。此外,我们展示允许不限量的预计算或将由外部模型计算的特征直接集成,尽管声称这些预计算增强了GNNs的表达能力,有时也会导致问题。这些问题甚至可以在顶级机器学习会议上发表的一篇重要论文中观察到。我们主张使用明确定义的计算模型,如分布式计算中的CONGEST模型,是合理的方法来描述和探索GNNs的表达能力。遵循这种方法,我们呈现了一些关于虚拟节点和边的影响的结果。最后,我们突出了关于GNN表达能力的几个开放问题,以供进一步研究。