图神经网络基本模型概述

赵佳英

（浙大宁波理工学院图书与信息技术中心，浙江 宁波 315199）

过去几年，应对图像、语音、视频、自然语言等各种形式的数据，深度学习获得了十分好的成效。越来越多的相关应用进入了实用阶段，如目标检测、机器翻译、语音和人脸识别等。但这些任务的数据通常为节点具有固定排列规则和顺序的欧式数据。近年来，越来越多的实际应用问题必须要考虑不规则的图数据，诸如电子商务、生物制药和交通网络等[1]。不同于文本和图像数据，图数据中的节点没有固定的排列规则和顺序，每个图具有可变大小的无序节点，且每个节点的邻居数量也不尽相同。研究人员借鉴卷积网络和深度自动编码器的思想，将专门处理非欧空间数据的图模型扩展到深度学习模型中，形成了图神经网络。

2005年，GORI在其论文《A new model for learning in graph domains》中，首次提出了图神经网络的概念，将图预处理转换为一组向量表示，并将学习过程直接架构于图数据之上[2]。至此，图神经网络经历了引入监督学习方法、引入卷积神经网络、基于频域卷积图神经网络到基于空域卷积图神经网络等过程，计算效率逐步提高，实现了图数据端到端的学习。本文重在阐述文献[3]分类方法的4种图神经网络的基本模型，并总结分析了它们的异同，主体结构如图1所示。

图1 主体结构

1 基本概念和符号定义

图作为一种常见的数据结构，由节点和连接节点的边组成。节点用来表示研究的对象，边表示2个对象直接的特定关系，通常使用邻接矩阵A来表示它们之间的关系。设图G=（V，E），邻接矩阵A为：

度矩阵是对角元素为各节点度个数的对角阵，Dij=∑jAij用来表示单个对象节点与之相连接的节点数量。根据图的邻接矩阵和图的度矩阵，图的拉普拉斯矩阵可表示为L=D-A，它是整合了节点自身信息和邻居节点结构信息的矩阵。借助于图的拉普拉斯矩阵，可以求得特征值和特征向量，以便进行后续图的研究。

傅里叶变换是利用图拉普拉斯求得的特征值和特征向量，在图特征提取中将时域信号转化为不同频率正弦函数和余弦函数的累加和的函数变换，其实质是对图数据进行降维，简化复杂图数据的计算工作量。本文常见符号定义如表1所示。

表1 （续）

表1 符号定义

2 循环递归图神经网络

循环递归图神经网络作为图神经网络的先驱，它假定图中的每个节点通过循环递归的方式，不断与其邻居节点交换信息，同时更新节点受其邻居节点影响的特征表示，直到达到稳定[3]。其本质是模拟人的记忆能力，在图学习过程中记录节点周边已出现的信息，并利用这些信息影响后续节点的输出。

节点i的隐藏特征表示为时刻节点i的隐藏特征受i节点特征xi、i与其邻居节j的边权重wi，j、邻居节点j特征xj以及上一时刻节点i的隐藏特征的共同影响，其中，递归函数f（·）必须满足收敛准则。循环递归神经网络不是一次性将图的所有节点信息输入，而是通过每个时刻，节点数据输入与前一时刻所得的输出结果进行结合获得新的输出，以此遍历整个图网络。循环递归图神经网络多与长短时记忆算法结合，使得信息可以在层与层之间传递，在此基础上，研究者结合卷积核运算提出了卷积图神经网络。

3 卷积图神经网络

卷积图神经网络是将卷积运算应用到图数据学习中，主要是通过聚合自身节点和其邻居节点特征，并经过多个图卷积层运算，实现节点特征的提取。卷积图神经网络具有卷积神经网络的相似性质，卷积层数越多，感受域越广，参与运算的信息也越多。卷积图神经网络主要分为2类：①以图信号表示为基础的基于频域的卷积图神经网络；②以信息传播定义为基础的基于空域的卷积图神经网络。

3.1 基于空域的卷积图神经网络

基于空域的卷积图神经网络以单个节点的空间来定义图卷积算子，将当前节点的特征与其邻居节点的特征进行卷积运算，计算得出当前节点的隐藏特征。也就是说，空域卷积是通过聚合邻居节点来收集信息的，它将当前节点所有邻居节点的隐藏特征进行加和，来更新当前节点的隐藏特征[4]。因此，第k层的卷积公式为

随着技术的发展，基于空域的图卷积神经网络进行了很多变型，在此基础上，关于邻居节点进行采样和聚合等的方式改进方面有大量论文可供参考。

3.2 基于频域的卷积图神经网络

基于频域的卷积图神经网络利用图傅里叶变换来实现卷积。首先将图的拉普拉斯矩阵分解为特征值和特征向量，导出频域上的拉普拉斯算子，类似欧式空间卷积过程进行计算。图的卷积公式为：

依据傅里叶变换的乘积定理，式（1）表示节点特征x和可学习权重参数w卷积的傅里叶变换等于节点特征的傅里叶变换UTx和可学习参数的傅里叶变换UTw的乘积。其中UT为傅里叶变换的基，U为傅里叶逆变换的基，它们可由图的拉普拉斯矩阵进行特征分解得到。其中UTw整体可以看成一个可学习的卷积核。因此，实现堆叠多个图卷积层，引入非线性激活函数σ（·）后，第k层的卷积公式为：

4 图自编码器

图自编码器是一种无监督的学习，它分为编码和重构2部分。首先它通过学习节点分布，将图编码到一个低维隐藏向量空间中，再利用得到的学习结果重构原始图。最简单的图自编码器是一个前馈非循环的图神经网络，用一层或多层隐藏层连接输入和输出，重构结果也只包含原图中最相关的部分。一个好的重构器应该能使重构图的邻接矩阵与原始图的邻接矩阵尽可能相似。

4.1 自编码器

编码器启发于传统的主成分分析，是一种非线性降维算法，通常由2个图卷积层Gconv（·）组成，从图的邻接矩阵A和特征向量x学习得到图的低维向量表示为：

式（3）中：W1、W2为待学习的参数。

解码器旨在通过解码图的低维向量表示来重建图的邻接矩阵，实现图生成，形式为

4.2 变分自编码器

简单的图自编码器可能出现图重构的过拟合现象，因此，在自编码器的基础上结合图数据分布，利用KL散度，引入了变分自编码器，避免过拟合风险。其本质也是利用2个图卷积层Gconv，μ（·），Gconv，σ（·），但它们用来分别计算均值μ和方差σ2，并使其图模型符合正态分布，再利用均值向量和协方差矩阵的解码器采样来重构原始图，其编码器为：

5 时空图神经网络

时空图神经网络用于捕捉图的动态性，结合考虑空间依赖性和时间依赖性[5]，假定节点的未来信息取决于该节点和其邻居节点的历史信息。

递归图神经网络结合空间依赖性，t时刻的节点特征表示形式为但基于递归图神经网络算法，可能存在耗时迭代和梯度爆炸或者梯度消失的问题。

卷积图神经网络在考虑空间依赖性的基础上，采用扩展的因果卷积作为时间卷积层，来学习节点的时间特征，其表示形式为h（t）=σ｛Gconv（x（t-1），A；w）+Gconv（h（t），A；U）+b｝，通过非递归的方式处理时空图，具有并行计算和梯度问题的优点，对内存需求也较低。

6 总结

图神经网络是用来高效处理非欧式图数据的重要模型之一，在学习图数据方面展现了强大的能力，本文总结概述了循环递归图神经网络、卷积图神经网络、图自编码器和时空图神经网络的基本模型。循环递归图神经网络是图神经网络的先驱，通过循环递归的方式聚合邻居节点的信息，受计算能力限制较大，适用于时序性的特征学习任务；受启发于递归循环图神经网络的卷积图神经网络使用神经元之间的连通性，旨在减少预处理，降低空间复杂度和时间复杂度，是一种半监督学习算法，适用于节点分类和边处理；图自编码器作为一种无监督学习方式，利用编码器和解码器完成网络嵌入和图生成，可用来做链路预测和推荐任务；时空图神经网络结合空间依赖性和时间依赖性，使得图结构学习更加完整，多用于预测任务。在4种模型基础之上，众多变种的图神经网络模型不断涌现，但模型在动态网络、异构图等方面仍存在一些局限性。随着科研人员的不断学习研究，这些问题终能得到解决。