摘要
图神经网络 (GNN) 在图机器学习中得到了广泛应用,大量研究集中在它们的表现力上。当前的研究通常通过将 GNN 与 Weisfeiler-Lehman (WL) 测试或经典图算法进行比较来评估其表现力。然而,我们在现有分析中发现了三个关键问题:(1) 一些研究使用预处理来增强表现力,但忽略了其计算成本;(2) 一些研究声称匿名 WL 测试的效力有限,同时使用非匿名特征来增强表现力,造成了不匹配;(3) 一些研究用 CONGEST 模型来描述消息传递 GNN (MPGNN),但对计算资源做出了不切实际的假设,允许 $\textsf{NP-Complete}$ 问题在 $O(m)$ 深度内解决。我们认为,迫切需要一个定义明确的计算模型作为讨论 GNN 表现力的基础。为了解决这些问题,我们引入了资源受限 CONGEST (RL-CONGEST) 模型,该模型包含可选的预处理和后处理,形成一个用于分析 GNN 表现力的框架。我们的框架阐明了计算方面,包括 WL 测试中哈希函数的计算难度以及虚拟节点在减少网络容量方面的作用。此外,我们建议高阶 GNN 对应于一阶模型检验问题,为其表现力提供了新的见解。