什么是好的GNN表达？国防科大最新《图神经网络的表达能力》综述

图神经网络(GNNs)是许多与图相关的应用的有效机器学习模型。尽管它们在实际应用中取得了成功，但仍有许多研究努力专注于GNNs的理论局限性，即GNNs的表达能力。

这个领域的早期工作主要集中在研究GNNs的图同构识别能力，而近期的工作试图利用诸如子图计数和连接学习等属性来描述GNNs的表达能力，这些都更加实用并且更接近实际应用。

然而，还没有综述论文和开源代码库能够全面地总结和讨论这个重要方向的模型。为了填补这个空白，我们进行了第一次关于增强不同定义形式下表达能力的模型的调查。

具体来说，这些模型基于三个类别进行了综述，即，图特征增强、图拓扑结构增强以及GNNs架构增强。

图神经网络表达能力

图神经网络(GNNs)已经成为深度学习领域的一个突出模型，吸引了大量的研究兴趣[1]–[3]。GNNs已经显示出了在学习图数据方面的卓越能力，它们的各种变体已经被广泛地应用于众多真实世界的场景，包括推荐系统[4]、计算机视觉[5]、自然语言处理[6]、分子分析[7]、数据挖掘[8]和异常检测[9]。关于GNNs的基础和应用的更多介绍，请参考文献[10]–[12]以获取更多详细信息。

与结构良好的文本和图像相比，图是不规则的。在图上进行机器学习的一个基本假设是，预测的目标应该与图上节点的顺序无关。为了满足这个假设，GNNs引入了一个称为排列不变性的归纳偏见[13]。具体地说，GNNs的输出与图的节点索引如何分配以及它们的处理顺序无关，即，模型参数与节点顺序无关，并在整个图中共享。由于这种新的参数共享机制，我们需要新的理论工具来研究它们的表达能力。然而，研究GNNs的表达性面临许多挑战。首先，大多数GNNs通常被用作图的黑盒特征提取器，我们不清楚它们能够多好地捕获不同的图特征和拓扑。其次，由于引入了排列不变性，神经网络(NNs)的经典通用逼近定理的结果[14]、[15]不能直接推广到GNNs[16]–[18]。此外，在实践中，表达能力的研究与图论中一些长期存在的困难问题有关[19]、[20]。例如，在预测化学分子的性质时，需要判断分子结构是否与已知性质的分子相同或相似，这涉及到图/子图同构判断的问题[19]、[21]和图匹配[22]、[23]等问题[24]。

已有一些关于GNNs表达能力的开创性研究。Morris等人[25]、[26]以及Xu等人[27]提出使用图同构识别来解释GNNs的表达能力，从而引领了分析GNNs的分离能力的趋势。Maron等人[16]和Chen等人[28]提出使用GNNs来近似图函数的能力来解释它们的表达能力，并进一步给出了可以由GNNs近似的不变图函数的集合表示，从而引领了分析GNNs的近似能力的趋势。尽管近年来已经出现了多项描述和增强GNNs表达能力的研究，但在这个方向上仍然缺乏全面的评论。Sato[29]探讨了图同构测试与表达能力之间的关系，并总结了克服GNNs表达能力局限性的策略。然而，他们只描述了GNNs的分离能力和近似能力来描述GNNs的表达能力，而还存在其他能力，包括子图计数能力、谱分解能力[30]–[32]、逻辑能力[33]–[39]等，这些也被认为是GNNs表达能力的主要类别。因此，澄清GNNs表达能力的定义和范围是至关重要的，这也是促使这项工作的动机。 在这项工作中，我们认为GNNs的表达能力包括两个方面，即特征嵌入能力和拓扑表示能力。作为神经网络的一员，GNNs具有强大的特征嵌入能力。拓扑表示能力是GNNs的独特能力，这使GNNs与其他机器学习模型有所不同。基于这两个组件，我们进一步分析了GNNs表达能力的边界及其影响因素。研究发现，影响GNNs表达能力的因素也包括特征和拓扑，其中GNNs在学习和保持图拓扑方面的缺陷是限制其表达能力的主要因素。 基于对影响GNNs表达能力因素的分析，本文将改进GNNs表达能力的现有工作总结为三个类别，即图特性增强、图拓扑增强和GNNs架构增强。图特性增强旨在通过增强特征嵌入效果来提高表达能力。图拓扑增强旨在更有效地表示图拓扑，以帮助GNNs捕获更复杂的图拓扑信息。GNNs架构增强涉及改进限制GNNs表达能力的排列不变的聚合函数。我们还指出了这一方向现有基准和评估指标中的一些不足，并强调确定GNNs表达能力的挑战。此外，我们提出了几个有前景的未来研究方向，包括一个为设计更强大的GNNs而提出的受物理启发的方法论，以及利用图神经架构搜索。本文的结构组织如下：第2节介绍初步知识，包括图神经网络的基础和图同构。第3节给出了GNNs表达能力的统一定义。第4节分析了影响因素以及旨在提高GNNs表达能力的现有工作。第5节指出了这一研究方向中的几个挑战和机会。最后，我们在第6节结束。

GNNs的表达能力

表达能力。所有的机器学习问题都可以被抽象为从特征空间X到目标空间Y的映射f∗。f∗通常使用模型fθ来近似，通过优化一些参数θ。在实践中，f∗通常是事先未知的，所以人们希望fθ能尽可能地近似一大范围的f∗。估计这个范围有多宽被称为模型的表达能力，它为模型的潜力提供了一个重要的度量[69]，如图3(a)所示。

神经网络（NNs）强大的表达能力体现在它们可以近似所有连续函数[70]的能力上，特别是将特征空间X中的数据嵌入到由任何连续函数生成的目标空间Y的能力，这实际上是特征嵌入能力，如图3(b)所示。由于NNs的强大表达能力，很少有工作怀疑在各种应用任务中展现出明显优越性能的GNNs的表达能力，因为它们天然地将GNNs的优越性能归因于它们出色的特征嵌入能力。然而，一些增强的多层感知器(MLP)模型[71]、[72]在多个节点分类问题[73]中的性能超过了GNNs，尽管前者的表达能力比后者少，其中MLPs[74]仅使用每个节点的信息来计算节点的特征嵌入，而GNNs在每一层迭代地聚合邻近节点的特征，从而允许使用全局信息来计算节点的特征嵌入。这一事实导致了我们对表达能力的直观理解之间的矛盾，但同时也说明特征嵌入能力并不能很好地描述GNNs的表达能力。与NNs相比，GNNs增加了排列不变性的归纳偏见，使得它们可以在图的拓扑结构上传播和聚合信息。[48]、[75]证明，如果GNNs只有特征嵌入能力，但缺乏保持图拓扑的能力，那么它们的性能可能不如MLP。此外，我们知道前馈神经网络的表达能力通常受到它们宽度的限制，而GNNs的表达能力不仅受到它们的宽度的限制，还受到它们如何使用图拓扑进行消息传播和节点更新的限制。由此可见，GNNs的拓扑表示能力，即保持图拓扑的能力，成为了它们优越性能的关键。为了使用它们的拓扑表示能力来描述GNNs的表达能力，则需要一套新的理论工具。

提高GNNs表达能力的现有研究

为了提高GNNs的表达能力，我们可以从两个方面来考虑：一是提高特征嵌入效果，二是提高拓扑表示效果。特征嵌入效果的增强依赖于特征本身的增强，包括提取特征之间的依赖性和添加相关特征。增强拓扑表示效果有两种有效的方法。一种方法是为GNNs学习直接编码相关的拓扑信息，另一种方法是优化GNNs模型架构，以消除由排列不变聚合函数引起的保持拓扑的障碍。在本文中，我们总结了这三种方法为：图特征增强（增强特征嵌入效果）、图拓扑增强（直接编码拓扑信息）和GNNs架构增强（减轻排列不变聚合函数的缺陷）。符合我们的预期，目前已知的用于提高表达能力的更强大的GNNs模型设计都可以归入我们总结的这三种方法。表2根据它们采用的设计方法检查并系统地分类了近年来更具表达能力的GNNs的设计。

结论

关于GNNs表达能力的研究已经相当成熟，越来越多的改进模型不断出现。然而，这些研究并没有为深入了解GNNs的表达能力作出显著的贡献。因此，我们提出了一个统一的理论框架，用于描述GNNs的表达能力，包括定义、局限性和分析影响表达的因素。此外，我们利用这个框架来总结和分类目前用于增强GNNs表达能力的方法。总的来说，作为图形学习模型的一个范例，GNNs的表达能力既涉及到图的特征，也涉及到拓扑。因此，设计方法应该同时考虑这两个方面。我们的统一框架为在这个背景下研究GNNs的表达能力提供了一个新颖的、标准化的路径。