1 概述
图神经网络（GNN）是深度学习领域的一个重要模型，已广泛应用于推荐系统、计算机视觉、自然语言处理、分子分析、数据挖掘和异常检测等现实场景。GNN在从图形数据中学习方面表现出优越的能力，其变体已被广泛应用。
GNN的表达能力包括特征嵌入能力和拓扑表示能力两个方面。影响GNN表达能力的因素包括特征和拓扑，其中GNN在学习和保持图拓扑方面的缺陷是限制表达的主要因素。提高GNN表达能力的现有工作可分为图特征增强、图拓扑增强和GNN架构增强三类。
2 初步认识
2.1 图神经网络的基础知识
图(Graph)一般定义为节点（v）、边（e）的集合，可用于表示实体之间的复杂关系，并使用邻接矩阵和节点特征来表示。节点是图中的基本单元，边表示节点之间的关系。邻居节点是指与某个节点相邻接的节点。邻接矩阵是一个n×n的矩阵，其中n是节点的数量，矩阵中的元素表示节点之间是否存在边。节点特征是指每个节点的属性或特征向量。节点特征可以是任何类型的数据，如数字、文本或图像。
GNN是一种深度学习模型，用于学习图的表示。GNN的基本思想是通过迭代地聚合节点的邻居节点来更新每个节点的表示。本文介绍了一些基本的GNN模型，如Graph Convolutional Networks（GCNs）和Graph Attention Networks（GATs），以及一些增强GNN表达能力的模型，如Graph Isomorphism Networks（GINs）和Message Passing Neural Networks（MPNNs）。
2.2 图同构性的基础知识
图同构性是指两个图在节点和边的结构上完全相同，但节点和边的标签可以不同。在图神经网络中，图同构性是一个重要的概念，因为它可以帮助我们判断两个图是否相同，从而避免重复计算。GNNs可以通过学习图的特征来解决图同构问题。
Weisfeiler-Lehman测试（WL测试）是一种解决图同构问题的有效算法，也称为颜色细化算法。图1展示了WL测试的聚合和更新过程。(a)给定两个没有特征的图，并为所有节点添加颜色标签。(b)在第一次迭代中，节点聚合的不同信息被映射到新的颜色标签中，然后这些新标签被重新分配给节点，并在分配后计算标签数量。在第一次迭代后，G1和G2具有相同的颜色分布，以确定它们是否同构，并进行下一次迭代。(c)再次执行节点邻居聚合和颜色标签重新分配步骤，并获得G1和G2的不同颜色分布，此时可以确定它们不同构。图2展示了WL测试无法区分的非同构图。k-WL也是一种用于解决图同构问题的算法。
图1 WL测试的聚合和更新过程
图2：一些WL测试无法区分的非同构图
3 GNN的表达能力
3.1 GNN表达能力的必要性
机器学习模型的表现取决于其表达能力，神经网络的表达能力通常强于GNN。然而，在某些节点分类问题中，图增强多层感知器（MLP）的表现优于GNN。这表明仅使用每个节点的信息计算节点特征嵌入的MLP可以超越使用全局信息聚合邻居节点特征嵌入的GNN。GNN的卓越性能关键在于其拓扑表示能力，为了评估和设计更有效的GNN模型，需要深入研究它们如何利用图的拓扑结构进行信息传播和节点更新，并开发一套新的理论工具来描述GNN的拓扑表示能力。
图3说明了不同模型的表达能力：
a)部分说明机器学习问题的目标是基于多个观察到的例子来学习从特征空间到目标空间的映射。
b)部分说明神经网络的表达能力指的是空间F和F'之间的差距。虽然神经网络具有表达能力（F'在F中密集），但基于神经网络的学习模型f'可能与f*存在显著差异，因为它们过度拟合了有限的观察数据。
图 3：神经网络的表达能力及其对学习模型性能的影响。
3.2 GNN表达能力的定义和表示
GNN的表达能力与其特征嵌入能力和拓扑表示能力密切相关。作为神经网络的一种，GNN具有强大的特征嵌入能力，可以学习图中节点和边的表示，反映了具有不同特征的节点可以得到不同的节点嵌入。拓扑表示能力是GNN的独特能力，使其不同于其他机器学习模型，它使GNN能够捕捉图的结构信息并学习节点之间的连接模式，反映了具有不同拓扑位置的节点可以得到不同的节点嵌入。
特征嵌入能力和拓扑表示能力共同构成了GNN的表达能力，如图4所示：
a) GNN 的特征嵌入能力与神经网络相同，都是通过 f 将特征空间 X 中的观察到的示例映射到目标空间 Y。 特征嵌入能力的强弱是通过f的值域空间F的大小来衡量的。
b）GNN的拓扑表示能力是通过f将特征空间中观察到的实例映射到目标空间并保留实例之间的原始拓扑来实现的。 能力的强弱是通过值域空间F′（X = 1）的大小来衡量的。
c) GNN 的表达能力由特征嵌入能力和拓扑表示能力的组合组成，通过 F 和 F′ 的交集大小（其中 X = 随机）来衡量。
图 4：GNN表达能力的示意图
目前GNN表达能力研究中的几种主流观点分别将表达能力描述为近似能力、分离能力和子图计数能力。图 5为不同表达能力表示下 GNN 模型的输入和输出。当使用近似能力来描述GNN的表达能力时，模型的输入是一组图形，输出是图形嵌入。当使用分离能力时，输入是一对图形，输出是图形嵌入。当使用子图计数能力时，输入是单个图形，输出是节点（集合）嵌入。
图 5：不同表达能力表示下 GNN 模型的输入和输出
3.3 GNN表达能力的强度
GNN 具有执行特征嵌入和拓扑表示的能力，这使得它们能够捕获图的局部和全局结构信息。 这种能力使 GNN 能够在图的拓扑上传播和聚合信息，这对于节点分类、链接预测和图分类等任务至关重要。 GNN 在这些任务中表现出了显着的成功，这表明了其卓越的表达能力。
4 提高 GNNS 表达能力的现有工作
4.1 影响GNN表达能力的因素
GNN的表达能力强于表达图特征和图拓扑结构，因此图特征嵌入和图拓扑表示的效果将影响GNN的表达。节点特征和全局图特征都具有判别能力，GNN可以区分不同节点特征或全局图特征的图。然而，GNN的表达能力受到排列不变聚合函数的限制，这种函数忽略了相邻节点之间的关系，导致GNN在拓扑表示中丢失上下文的拓扑结构，从而无法学习图的基本拓扑属性。
4.2 提高GNN表达能力的方法
提高图神经网络表达能力的三种方法：图特征增强、图拓扑增强和GNN架构增强。图特征增强是通过增强特征嵌入效果来提高表达能力，图拓扑增强则是寻求更有效地表示图拓扑以捕获更复杂的图拓扑信息。GNN架构增强包括改进限制GNN表达能力的排列不变聚合函数和其他评估指标。这些方法可以提高特征嵌入效果和改善拓扑表示效果，从而增强GNN模型的表达能力。
表1对近年来更强大的表达性GNN进行了检查和系统分类，根据其采用的设计方法进行分类。
表 1：强大模型的总结
图特征增强，旨在提高图特征的嵌入效率。其中一种方法是提取特征之间的依赖关系，以增加特征的信息量，另一种方法是提高特征的利用率。图7详细描述了这种提升特征嵌入效果的方法。
图7：图特征增强的方法
我们还提供了使用这些方法的GNN模型的示例，例如自适应多通道图卷积网络（AM-GCN）、CL-GNN和ACR-GNN。图8展示了AM-GCN架构中信息通过三图卷积的传播过程。左边部分显示了通过为原始图中的每个节点选择 k 个最相似的邻居来获得 k-NN 图的过程。右半部分展示了k-NN图、原始图和常见卷积过程上的卷积。
图8：AM-GCN架构中信息通过三图卷积的传播过程
图拓扑增强，旨在直接编码学习到的拓扑信息。其中一种方法是手动添加额外的拓扑相关节点特征，另一种方法是直接编码图中固有的拓扑信息。根据编码的不同拓扑信息，后一种方法可以进一步分为：编码微观拓扑（如距离、位置和其他拓扑信息）、编码局部拓扑（主要基于子图拓扑的局部拓扑信息）和编码全局拓扑。图9展示了图拓扑增强方法的详细描述。图10示例了P-GNN 的更新策略，a)是不同大小的锚节点集，b)是v1嵌入到第l层的过程。
图 9：图拓扑增强的方法
图10：P-GNN 的更新策略
GNN 架构增强。GNN架构增强是提高GNN表达能力的另一种方法，例如使用注意力机制、增加层数、使用多头注意力机制等方法可以提高GNNs的表达能力和性能。图11展示了GNN 架构增强的方法。
图11：GNN 架构增强的方法
5 挑战和未来的发展方向
GNN 研究的主要挑战之一是缺乏可靠的真实数据集、明确的基准和合理的评估指标，这使得比较不同模型的性能并评估其有效性变得困难。另一个挑战是 GNN 模型的可扩展性较差。为了应对这些挑战，我们需要更全面和多样化的现实世界数据集，以提供更可信的模型评估。 此外，我们需要为 GNN 的表达能力建立明确的基准和评估指标，并利用新的模型和技术来提高 GNN 的可扩展性和表达能力。
参考文献：《A Survey on The Expressive Power of Graph Neural Networks》https://arxiv.org/abs/2003.04078
