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也是一种用于解决图同构问题的算法。 3.1 GNN表达能力的必要性 机器学习模型的表现取决于其表达能力,神经网络的表达能力通常强于GNN。然而,在某些节点分类问题中,图增强多层感知器(MLP)的表现优于GNN。这表明仅使用每个节点的信息计算节点特征嵌入的MLP可以超越使用全局信息聚合邻居节点特征嵌入的GNN。GNN的卓越性能关键在于其拓扑表示能力,为了评估和设计更有效的GNN模型,需要深入研究它们如何利用图的拓扑结构进行信息传播和节点更新,并开发一套新的理论工具来描述GNN的拓扑表示能力。 图3说明了不同模型的表达能力: a) GNN 的特征嵌入能力与神经网络相同,都是通过 f 将特征空间 X 中的观察到的示例映射到目标空间 Y。 特征嵌入能力的强弱是通过f的值域空间F的大小来衡量的。 b)GNN的拓扑表示能力是通过f将特征空间中观察到的实例映射到目标空间并保留实例之间的原始拓扑来实现的。 能力的强弱是通过值域空间F′(X = 1)的大小来衡量的。 c) GNN 的表达能力由特征嵌入能力和拓扑表示能力的组合组成,通过 F 和 F′ 的交集大小(其中 X = 随机)来衡量。 图 4:GNN表达能力的示意图 目前GNN表达能力研究中的几种主流观点分别将表达能力描述为近似能力、分离能力和子图计数能力。图 5为不同表达能力表示下 GNN 模型的输入和输出。当使用近似能力来描述GNN的表达能力时,模型的输入是一组图形,输出是图形嵌入。当使用分离能力时,输入是一对图形,输出是图形嵌入。当使用子图计数能力时,输入是单个图形,输出是节点(集合)嵌入。 GNN的表达能力强于表达图特征和图拓扑结构,因此图特征嵌入和图拓扑表示的效果将影响GNN的表达。节点特征和全局图特征都具有判别能力,GNN可以区分不同节点特征或全局图特征的图。然而,GNN的表达能力受到排列不变聚合函数的限制,这种函数忽略了相邻节点之间的关系,导致GNN在拓扑表示中丢失上下文的拓扑结构,从而无法学习图的基本拓扑属性。 提高图神经网络表达能力的三种方法:图特征增强、图拓扑增强和GNN架构增强。图特征增强是通过增强特征嵌入效果来提高表达能力,图拓扑增强则是寻求更有效地表示图拓扑以捕获更复杂的图拓扑信息。GNN架构增强包括改进限制GNN表达能力的排列不变聚合函数和其他评估指标。这些方法可以提高特征嵌入效果和改善拓扑表示效果,从而增强GNN模型的表达能力。 表1对近年来更强大的表达性GNN进行了检查和系统分类,根据其采用的设计方法进行分类。 图7:图特征增强的方法 我们还提供了使用这些方法的GNN模型的示例,例如自适应多通道图卷积网络(AM-GCN)、CL-GNN和ACR-GNN。图8展示了AM-GCN架构中信息通过三图卷积的传播过程。左边部分显示了通过为原始图中的每个节点选择 k 个最相似的邻居来获得 k-NN 图的过程。右半部分展示了k-NN图、原始图和常见卷积过程上的卷积。 图 9:图拓扑增强的方法 图10:P-GNN 的更新策略 图11:GNN 架构增强的方法 |
|