现代机器学习 课件 第15章 图卷积神经网络

第15章图卷积神经网络15.1符号的定义15.2图卷积和图池化的构建15.3图卷积神经网络的训练15.4图卷积神经网络的典型算法15.5图卷积神经网络的应用15.6图卷积神经网络的未来发展方向本章小结

传统的卷积神经网络只能处理具有平移不变性的欧氏空间数据(如图像、文本、语音等)。一种非欧氏空间数据——图数据,受到了越来越多的关注。图数据可以自然地表达现

实生活中的数据结构,如交通网络、万维网、社交网络等。如图15.1所示,与图像和文本这种欧氏空间数据不同,非欧氏空间数据的图数据中每个节点的局部结构不同,使得其不再满足平移不变性。因此,缺乏平移不变性对基于欧氏空间数据的卷积神经网络提出了挑战。图15.1欧氏空间数据与非欧氏空间数据

构建图卷积神经网络的挑战主要有如下几个:

(1)图数据中每个节点的局部结构不同,不满足平移不变性。传统卷积神经网络的基本卷积操作和池化依赖于数据的平移不变性。因此,如何在图数据上定义卷积和池化成为

一个具有挑战性的任务。

(2)图数据的特性多样。现实生活中的许多应用都可以用图数据来表示,如社交网络中用户的定向连接、引文网络中作者与引文之间的异质连接、政治网络中正负趋势符号的连接等,这使得图数据的特性多样。图的特性给图卷积神经网络的构建带来了更多的信息,但多特性的建模也要求图卷积神经网络的设计更加复杂和精确。

(3)图数据具有大规模性质。在大数据时代,实际应用中的图可能包含数百万甚至上千万个节点,如推荐系统中的用户商品网络和社交网络中的用户网络。在可接受的时间和

空间范围内,如何在大规模图上构造图卷积神经网络也是一个巨大的挑战。

15.1符号的定义

本节首先给出图卷积神经网络中常见符号的定义,如表15.1所示。

15.2图卷积和图池化的构建

15.2.1图卷积的构建现有的图卷积神经网络可分为谱方法和空间方法。谱方法利用图卷积定理在谱域定义图的卷积,而空间方法则在节点域通过定义聚合函数来聚合每个中心节点及其相邻节点。

1.谱方法构建图卷积

谱卷积神经网络(spectrumCNN)是第一种在图上构造卷积神经网络的方法。该方法利用卷积定理在每一层定义图卷积。在损失函数的指导下,通过梯度反向传播学习卷积核参

数,构成多层神经网络。谱卷积神经网络的m层结构如下:

2.空间方法构建图卷积

以上方法都是基于卷积定理定义谱域中的图卷积,而空间方法是在节点域定义聚合函数,对每个中心节点及其相邻节点进行聚合。目前,已有一些方法通过注意机制或递归神

经网络直接从节点域学习聚合函数,另有一些方法从空间角度定义了图卷积神经网络的一般框架,并解释了图卷积神经网络的内在机制。

平移不变性的缺失给图神经网络的定义带来了困难,混合卷积网络在图上定义坐标系,并将节点之间的关系表示为新坐标系下的一个低维向量,同时,混合卷积网络定义一簇权重函数,权重函数作用在以一个节点为中心的所有邻近节点上,其输入为节点间的关系表示(一个低维向量),输出为一个标量值。通过这簇权重函数,混合卷积网络对每个节点给出了相同尺寸的向量表示:

其中,N(x)是x的相邻节点集;f(y)是信号f下节点y的值;u(x,y)是坐标系u下的节点,表示关系的低维向量;wj表示第j个权重函数;J是权重函数的个数。该操作使每个节点得到一个J维的表示,该表示综合了节点的局部结构信息。混合卷积模型在这个J维表示上定义了共享卷积核:

式中,{g(j)}Jj=1表示卷积核。

与混合卷积网络不同,消息传播网络指出图卷积的核心是定义节点间的聚合函数。基于聚合函数,每个节点可以表示为周围节点和自身信息的叠加。因此,该模型通过定义一

个通用的聚合函数,提出了图卷积网络的一般框架。消息传播网络进行两个步骤。首先将聚合函数应用于每个节点及其相邻节点,得到节点的局部结构表达式;其次,将更新函数应用于自身和局部结构表达式,得到当前节点的新的表达式:

在上述空间框架下,研究人员采用一些现有的方法设计神经网络来学习聚合函数,而不再依赖拉普拉斯矩阵。这些方法学习的聚合函数使其能够适应任务和特定的图结构,具

有较大的灵活性。例如,图神经网络是第一个在图上建立神经网络的模型。在图神经网络中,聚集函数被定义为循环递归函数。每个节点以周围的节点和连接的边作为源信息,更

新自己的表达式。

图注意力网络(GAT)通过注意机制定义聚合函数。然而,与以往的关注边信息的模型不同的是,在图注意力网络中,邻接矩阵仅用于定义相关节点,而关联权重的计算依赖于

节点的特征表达式。图15.2所示为图注意力网络的结构。图15.2(a)以节点i和节点j的特征表达式为输入,计算i和j之间的注意力权重并将其归一化;图15.2(b)使用注意力权重,以加权和的形式将周围节点的表达式聚合为自身。关于图注意力网络的详细内容将在第15.4.3节中介绍。图15.2图注意力网络的结构

从图注意力网络出发,节点间的权值计算开始从依赖于网络的结构信息转向依赖于节点的特征表达。然而,上述模型在处理时需要加载整个网络的节点特性,给模型在大规模

网络中的应用带来了困难。基于此,GraphSAGE提出了图采样聚合网络。与以往模型考虑所有邻近节点不同,图采样聚合网络对相邻节点进行随机抽样,使得每个节点的相邻节点数小于给定的样本数。图15.3展示了图采样聚合网络的结构。图15.3图采样聚合网络的结构

以上基于聚集函数的空间方法主要研究了空间方法的根本问题,即聚合函数的构建。随着图卷积神经网络的发展,研究人员开始考虑更复杂的场景,提出了一类具有更丰富的建模信息的空间方法,包括如何在具有边缘信息的网络上建立图卷积神经网络以及如何对高阶信息建模。

15.2.2图池化的构建

在传统的卷积神经网络中,卷积和池化通常结合在一起。池化可以减少学习参数,反映输入数据的层次结构。然而,在图卷积神经网络中,池化算子在求解节点级任务(如节点分类和链路预测)时是不必要的。因此,在图卷积神经网络领域,池化受到的关注较少。近年来,为了更好地描述网络的层次结构,一些研究者开始投身于池化的研究。

图上的池化通常对应于图分类任务。假设A是邻接矩阵,X是节点的特征矩阵,对于图G=(A,X),给定一些标记的图数据集D={(G1,y1),(G2,y2),…}和与图相对应的标签集Y={y1,y2,…},用映射函数f:G→Y将图结构映射到相应的标签上。

切比雪夫网络(Chebynet)使用完全二叉树来实现池化运算,提出基于Graclus贪心准则计算每个节点的最匹配节点,并将此节点对池化成一个节点。同时,切比雪夫网络通过添加虚假节点来保证整个池化过程是一个完整的二叉树。图15.4显示了切比雪夫网络将八个节点的图池化为三个节点的过程。图15.4切比雪夫网络利用完全二叉树进行池化操作

在池化过程中,为了充分利用节点的特性和局部结构,谱池化(EigenPooling)采用谱聚类的方法将整个图分成若干不重叠的子图,每个子图合并后作为一个新节点,根据原子

图的边连接生成新节点之间的边。谱池化可以控制每次划分后子图的数目,进而控制每层的池比例。图15.5显示了将谱池化与一阶图卷积神经网络相结合的图分类框架。图15.5中,每种颜色表示一个子图,在池化后成为一个新的节点。图15.5将谱池化和一阶图卷积神经网络相结合的图分类框架

池化算子的目的是学习图的层次结构,从而完成图级的任务。首先,基于图的拓扑结构,启发式地定义了一些节点的舍弃方式和融合方式。随着技术的发展,池化算子不仅依

赖于节点的拓扑结构,而且依赖于节点的属性信息。同时,注意机制和数学研究也开始为该模型的参数学习做指导。

15.3图卷积神经网络的训练

15.3.1深层图卷积神经网络残差网络解决了传统神经网络在增加层数时拟合能力下降的问题,而多层图卷积层叠加后,节点之间的特性变得过于平滑,缺乏区分性,从而导致网络性能较差。简单地应用残差连接并不能解决这一问题,因为在图卷积神经网络中,每个节点只向其直接相邻节点发送特征,而不同的节点具有不同的传播速度,即中心节点可能可以通过一层或两层图卷积将特征传输到整个网络中的大多数节点,而网络中的边缘节点需要多次传播才能影响到网络中的一些节点。

跳跃知识网络利用跳跃连接和注意机制为每个节点选择合适的传播范围。跳跃知识网络的模型结构如图15.6所示。图15.64层跳跃知识网络的示意图(N.A.表示从邻居节点聚合特征的操作)

15.3.2大规模网络图卷积技术

传统的机器学习方法(如多层感知器)认为样本是独立的,因此可以采用批量处理的方法来处理大规模的训练数据。由于图卷积神经网络中,卷积运算依赖于相邻节点,因此需要引入大量相关节点来使用批训练方法。也就是说,对于中心节点,更新其表达式所需的邻居节点数随着网络层的增加呈指数级增加。同时在大规模网络中,某些度数过大的节点即使只考虑二阶邻居其计算量也过于庞大。这两个结果导致直接批量训练方法不适用于解决图卷积神经网络中难以在大规模网络中应用的问题。

GraphSAGE随机抽样相邻节点,以减少每次卷积中要计算的节点数,但是这种估计法是有偏方的,不能保证收敛。在采样邻居节点的基础上,基于方差控制的算法利用未采样节点的历史表达来控制方差。该方法认为,当参数变化不大时,节点的表达式与其历史表达式很接近。因此,未采样的节点通过其历史表示进行近似拟合。

15.3.3半监督节点分类问题的训练技术

图卷积神经网络在半监督节点分类问题中取得了有效的结果,但是由于卷积算子认为所有一阶邻居节点都同等重要,因此导致图卷积神经网络对网络数据中心节点的分类效果

较差。DGCN指出,去除这类节点中的一些边后,图卷积神经网络的效果可以得到改善,这说明仅利用一阶邻居节点的邻近性有一定的局限性,需要引入额外的信息来区分一阶邻居

节点。DGCN通过引入PPMI矩阵降低了一阶邻居关系对节点的影响,并引入了比一阶邻居节点更丰富的关系。

使用PPMI进行卷积可以纠正图卷积神经网络中的一些错分点,但也会引入新的错误。因此,DGCN采用集成学习的方法,结合两种不同卷积的优点来提高分类效果。

15.4图卷积神经网络的典型算法

15.4.1半监督图卷积网络曾经有研究人员通过带有图拉普拉斯正则化项的损失函数进行优化:

此模型使用神经网络模型f(X,A)对图结构进行编码,并对所有有标签节点用监督损失L0进行训练,从而避免了损失函数中基于图的正则化。在图的邻接矩阵上调节f(·)将使模型从有监督损失L0中分散梯度信息,并使带标签和不带标签节点的表示形式均能被模型学习。

1.加速版本的GCN

2.线性模型

可以通过堆叠多个式(158)形式的卷积层来建立基于图卷积的神经网络模型,每层之后是逐点非线性函数。现在假设将分层卷积运算限制为K=1(参见式(158)),此时模型

是线性的,因此在拉普拉斯谱图上具有线性函数。

通过使用这种形式的GCN,可以缓解模型在图的局部结构上的过拟合,且在很大程度上减小了计算开销,使得我们可以堆叠多个GCN来获得一个更深的模型并提取特征。

进一步近似地认为λmax≈2,式(158)可以简化为

3.半监督节点分类

前面介绍了优化后的图卷积结构。在现在的半监督任务中,研究人员希望通过已知的数据X和邻接矩阵A来训练图卷积网络f(X,A)。有专家认为,在邻接矩阵中包含了一些X中没有的隐含的图的结构信息,我们可以利用这些信息进行推理。

图15.7(a)所示是一个多层GCN网络示意图,输入有C维特征,输出有F维特征,中间有若干隐藏层,X是训练数据,Y是标签。图15.7(b)是使用一个两层GCN在Cora数据集(只用了5%的标签)上得到的可视化结果。图15.7多层GCN及可视化

15.4.2HA-GCN

1.k阶卷积算子

假设A是图G的邻接矩阵,则其第k个乘积Ak

的(i,j)项是从i到j的k跳路径的数量。有了这个命题,我们可以定义一个k阶卷积算子如下:

其中:

2.自适应滤波模块

自适应滤波的思想来源于注意力机制,该机制自适应地选择关注的像素。从技术上讲,我们的自适应滤波器是权重矩阵Wk上的非线性算子g,即

15.4.3GAT

15.5图卷积神经网络的应用

15.5.1网络分析引文网络是社会网络分析领域最常见的数据,论文作为节点,引用关系作为边。分类的一个典型任务是通过给出文章之间的内容信息和引用关系,将每一篇文章划分到相应的领域。

15.5.2社区发现

在社区发现问题中,以往的算法主要是对其进行明确的定义,并对图的划分最小割问题进行优化。线性图神经网络(LineGraphNeuralNetworks,LGNN)提出了一种新的用于社区发现的图神经网络模型。该方法采用纯数据驱动,无须基本的生成模型,在社区发现任务中取得了良好的效果。在其他网络分析(如信息传播、社会网络地理信息预测)中,研究人员均引入了图卷积神经网络来有效地建模网络结构信息和节点属性信息。

15.5.3推荐系统

如图15.8所示,将产品与用户之间的关系看作矩阵补全或链接预测,可以有效地对产品与用户之间的关系进行建模。MGCNN(Multi-GraphCNN)结合多图卷积神经网络与循环神经网络,分别利用多图卷积神经网络和循环神经网络来提取局部静止的特征和补全矩阵。GC-C(GraphConvolutionalMatrixCompletion)将推荐系统建模为一个基于图的链接预测问题,提出了一种基于不同消息传播的图自编码框架来对推荐系统的二部图(又称二分图,是图论中的一种特殊模型)建模,在包含社交网络的数据上取得了最佳效果。图15.8推荐系统中的矩阵补全和链接预测建模示意图

15.5.4交通预测

交通预测也是图卷积神经网络的广泛应用之一。它的目的是在给定历史交通速度和路线图的情况下预测未来的交通速度。在交通预测问题中,节点表示放置在道路上的传感器,

而边缘表示节点对的物理距离,每个节点都包含一个时序特征。

15.5.5生物化学

除了传统的图形数据建模外,图卷积神经网络在生物化学领域也引起了研究人员的广泛关注。与传统的图形数据研究相比,在生物化学领域,人们通常把一个化学结构或一个蛋白质看作一个图形。图中的节点是较小的分子,边表示键或相互作用。图15.9是布洛芬的分子图,节点是碳、氢和氧原子,边是化学键。图15.10是FAA4蛋白质交互网络,节点代表蛋白质,边缘代表相互作用。研究人员关注的是图的化学功能,即研究对象不再是图中的节点,而是整个图本身。图15.9布洛芬分子示意图图15.10FAA4蛋白交互网络

15.5.6计算机视觉

在计算机视觉中,图卷积神经网络的应用主要集中在小样本学习、点云、零样本学习、场景图等方面。

小样本学习的目的是用较少的样本来训练和识别新样本。它通常包括两个阶段:元训练和元测试。在这个任务中,数据集包括训练集、支持集和测试集。支持集和测试集共享相

同的标签空间,但是训练集有一个单独的标签空间,并且不与支持集或测试集相交。如果支持集在每个类中包含k个标签样本和C个类别,则称该问题为C-wayk-shot问题。

点云图像是由三维扫描仪在一定的坐标系中生成的一组点,它比二维图像包含更多的三维坐标信息、颜色等几何信息。3DGNN利用图神经网络实现了RGBD图像的语义分割

任务。DGCNN在点云上使用图卷积神经网络,提出用边卷积来采集边的特征,它不仅包含局部域信息,而且通过叠加或循环学习全局几何属性。该模型在形状分类和局部分割任务

中取得了良好的效果。SuperPoint_Graph使用消息传播机制对点云图像进行建模。

场景图是计算机视觉领域比较常见的另一种图形结构数据。它的节点是对象,边特征表示它们的空间关系。与传统的线性结构相比,图结构包含了更多有价值的语义信息。如

何利用图卷积神经网络对场景图进行建模,引起了人们的广泛关注。GraphVQA通过对场景图和句法依赖图的建模,有效地应用于可视问答。Iterative-Visual-Reasoning提出了知识

图谱、图像区域空间关联图和区域类别分布图三个图形模块,有效地模拟了可视化回答。

15.5.7自然语言处理

图卷积神经网络在自然语言处理中有着广泛的应用。在这一领域,常用的图形数据有知识图谱、依存句法图、抽象意义表示图、词共现图等。其抽象意义是一种将句子的意义编码为有根有向图的方法。Syntax-awared-NMT将图卷积神经网络应用于依存句法树,并将其应用于英语、捷克语、英语和德语的机器翻译任务。Graph2seq利用阈值图神经网络对抽象意义图进行基于语法的机器翻译任务。

除上述图谱外,词共现网络还应用于文本分类任务。节点是非停用词,边是给定窗口中单词的共现关系。CNN_Graph提出了一种用图谱理论定义的卷积神经网络,为快速设计图的局部卷积滤波器提供了必要的数学背景和有效的数值方案。

大量的研究表明,使用图卷积神经网络模型可以提高各种自然语言处理任务的效果。图结构的使用使得对象之间复杂的语义关系得到有效挖掘。与传统的用于自然语言处理的

串行化建模相比,图卷积神经网络可以用来挖掘复杂的非线性语义关系。

15.6图卷积神经网络的未来发展方向

15.6.1深层的网络结构传统的深度学习模型在堆叠了大量网络层后,由于其强大的表示能力,在很多问题上了取得了显著的效果。但是图卷积神经网络模型在堆叠了较少层数后,网络就达到了最好的效果,再增加图卷积层反而会使得结果变差。这是因为图卷积包含了聚合邻居节点特征的操作,当网络堆叠多层后会使得节点之间的特征过于平滑,缺乏区分性。

15.6.2大规模数据

在实际场景中,网络的规模往往非常大。比如新浪微博、Twitter等社交关系网络往往包含了数亿计的节点和边。而目前绝大部分图卷积神经网络模型不适用于这种大规模的网络。

比如,基于谱方法的图卷积神经网络需要计算图拉普拉斯矩阵的特征向量矩阵,而这个操作的计算复杂度和空间复杂度都很高,难以用于大规模网络。空间方法在更新节点表达时依赖于大量的邻居节点,使得计算代价过大,不适用于大规模网络。虽然近些年已经有一些基于采样的方法来处理大规模网络数据的问题,但是这一问题仍然没有得到有效解决。

15.6.3多尺度的图上任务

图挖掘任务根据主体对象的不同可以分成节点级任务、图以及子图级任务和信号级任务。节点级任务的关键点在于为每个节点学习有效的表达,而为图学习表达是图级任务的

关键。信号级任务的关键点在于在网络结构不变的情况下