03 图神经网络

图神经网络对于非欧几里德数据在深度学习中的应用有着非常重要的地位，尤其是利用图结构在传统贝叶斯因果网络上可解释的特点，在定义深度神经网络关系可推理、因果可解释的问题上有很大的研究意义。如何利用深度学习方法对图结构的数据进行分析和推理吸引了非常多的研究和关注。

这里我们将现有的图神经网络的算法进行了总结与归纳，给出一个通用的图神经网络结构如图2所示，将图神经网络推理过程通过图节点预表示、图节点采样、子图提取、子图特征融合、图神经网络的生成和训练子过程来表示，具体步骤如下:

STEP1图节点预表示:通过图嵌入(Graph Embedding)的方法对图中每一个节点进行嵌入表示;

STEP2图节点采样:对图中每个节点或存在的节点对的正负样本进行采样;

STEP3子图提取:提取图中每一个节点的邻节点构建n阶子图，其中n表示第n层的邻节点，从而形成通用的子图结构;

STEP4子图特征融合:对每一个输入神经网络的子图进行局部或全局的特征提取;

STEPS生成图神经网络和训练:定义网络的层数和输入输出的参数，并对图数据进行网络训练。

本章将从分别频域和空间域的GCN研究的角度，对比多种图卷积神经网络[23]的差异效果和发展历程;介绍门控图神经网络[24]、利用注意力结构替代卷积的图注意力网络[25]、针对无监督模型的图自动编码器[26]以及时域空间的图时空网络[27];讨论图嵌入[28]作为图神经网络的模型结构和多种实现方式。最后对上述网络模型从聚合方式、网络基础和应用优势的角度对比分析图神经网络模型之间的差异。

3.1 图卷积神经网络

深度学习的流行与卷积神经网络的广泛适用性密不可分，图神经网络的研究中时间最长、研究成果最多的就是图卷积神经网络，从特征空间来看图卷积神经网络主要可以分为频域和空间域两个类型。

图卷积神经网络将原始图结构的数据G=(V, E)映射到一个新的特征空间：

以单层向前传播图卷积神经网络为例，第i层神经网络的特征用wi表示，对于图结构中的每一个节点vi在计算时，每一层神经网络的输出H(l+1)都可以以非线性函数f(·,·)表示为

其中A为特征邻接矩阵。

通过非线性激活函数ReLU=σ(·)实现一个图卷积神经网络结构，其分层传播规则如下：

表示为图结构G= (V, E)的邻接矩阵，I为单位矩阵：

表示矩阵A的对角矩阵，w(l)为第l层卷积神经网络的权重矩阵。通过分层传播规则，图卷积神经网络将卷积神经网络局部参数共享的特性带入了图结构中，使得每一个节点的感受域的光对随着传播层数的增加而得更大的提升，从而获取到更多邻节点的信息。

接下来两小节将分别从频域和空间图卷积的方向具体列举分析不同类型图卷积神经网络方法。

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

频域的图卷积神经网络基于图信号处理[29]问题，将图神经网络的卷积层定义为一个滤波器，即通过滤波器去除噪声信号从而得到输入信号的分类结果实际问题中只能用于处理无向且边上无信息的图结构，将输入信号的图定义为可特征分解的拉普拉斯矩阵，归一化后的特征分解可以表示为通用结构其对角矩阵A就是特征值的λi按序排列组成的特征矩阵。

最早在频域实现的图卷积神经网络是由Bruna[10]等人提出定义频域图卷积神经网络的卷积层函数。将频域图卷积神经网络假设在图信号处理中的滤波器，特征分解需要至少o(n3)的计算复杂度和0 (n2)的存储空间，对于输入图数据为稀疏矩阵的场景时，可以通过随机特征分解等方法在保证精度的情况下将时间复杂度降低到0 (n2r + r3), r为近似矩阵的秩远小于n。

Henafff[30]等人提出基于插值内核(Interpolation Kernel)的图卷积神经网络方法。在频域卷积神经网络的基础上提出了无监督和有监督两种新的通过图卷积神经网络来进行推理预测的方案，从图1图神经网络通用结构中可以看出，第一步图节点的预表示可以根据数据预测相似性矩阵，这种方法也将应用场景扩充到了大规模图像和文本分类等问题中。

Dei}errad[11]等人提出了基于切比雪夫多项式的频域卷积滤波器ChebNet，其中切比雪夫多项式的组成是由特征值对角矩阵的项组成的，通过切比雪夫展开式Ti(x)替换了原始GCN中通用频域卷积滤波器g的特征分解部分，从而有效地避免了特征分解的计算部分，将计算复杂度从o(n3)降低到了o (LE)，其中E为输入图G中边的数量。一阶切比雪夫图卷积神经网络[27]则是利用了一阶切比雪夫展开更好的提升网络的计算效率。针对包含复杂属性的节点异构图，可以通过图卷积神经网络来实现节点的聚类。为了提升属性图的信息提取的性能和模型的效果，Zhang等人提出了AGC[31]自适应图卷积方法，利用高阶图卷积来获取全局聚类的结构来定义k阶图卷积，从而实现了对于复杂异质图的处理。

3.1.2 基于空间的图卷积神经网络

与深度学习中卷积神经网络对图像的像素点进行卷积运算类似，基于空间的图卷积神经网络通过计算中心单一节点与邻节点之间的卷积，来表示邻节点间信息的传递和聚合，作为特征域的新节点表示。

Scarselli等人[32]提出了一种利用基于相同图卷积结构的循环函数递归地实现了空间图卷积神经网络的收敛方法，该方法可以支持节点和边上分别包含特定属性契合传统卷积神经网络基本思想的方法。Dai等人[33]提出的随机稳态图神经网络迭代算法SSE通过异步随机的方式，对于每个拥有不同数量邻节点的节点而言利用双向权重矩阵w1，wz在每次卷积迭代中更新节点的特征表示。

随机稳态图神经网络不支持边上包含的信息，这里通过两个权重函数分别对全部的节点v∈VN和包含信息的节点集合v∈VN进行卷积处理，这样从而使得图卷积神经网络的迭代效率得到了提升。图结构数据中节点存在极多的关系导致参数数量过多的情况下，引入基础分解和块对角分解两种方式可以有效解决过拟合的问题。关系图卷积神经网络可以有效地应用在以节点为中心的实体分类问题和以边为中心的链接预测问题上。

AtWOOCl[34]提出的基于图结构的传播卷积神经网络DCNN通过传播卷积的方式，扩散性地扫描图结构中的每一个顶点，替代了一般图卷积神经网络基于矩阵特征的卷积形式，DCNN的参数是根据搜索深度而不是节点在图结构中的位置决定的，可以用于节点、边以及图结构等多种分类任务，但由于计算转移概率的时间复杂度较高，并不适用于大规模的图结构数据。Zhuang和Ma[35]在传播和邻接矩阵两种卷积结构的基础上提出了一种双路图卷积神经网络的方法，通过半监督图卷积[29]的和转移概率的正逐点互信息((PPMI)矩阵作为卷积运算邻接矩阵来更好提升模型的信息抽取的效果。

图卷积神经网络频域和空间两个方向分析对比如表2所示。频域图卷积神经网络主要依赖于频域矩阵的特征分解，而空间图卷积神经网络主要是借助邻节点特征信息的聚合来定义在图数据上的卷积运算。此外在最新的研究中，GCN的实现方式还包括利用子图训练组合的GraphSage[36]，基于信息传递的MPNN[37]，以及AGCN[38] MGCN[39]，pinSage[40]，Fast-GCN[41]等方法。同时关于图卷积神经网络优化方式也有很多研究，针对解决高阶图卷积在空间图卷积中性能较差问题，引入稀疏邻域来替代频域图卷积的MixHop[42]。

3.2 门控图神经网络

目前基于门控机制的递归神经网络机制下的图神经网络结构的研究也有不少，例如基于门控循环单元(GRU)的门控图神经网络(GGNN)[43]，通过门控循环单元控制网络传播过程中固定步数T的迭代循环来实现门控图神经网络的结构，通过节点二来建立邻节点之间的聚合信息，然后通过循环门控单元z和r实现递归过程更新每个节点的隐藏状态。

Tai等人[44]提出了基于子节点和的树状长短期记忆网络Tree-LSTM用于处理图神经网络中的语义表示问题。门控图神经网络除了基于门控循环单元和LSTM的基础模型外还有很多变种，You等人[45]利用分层循环递归网络分别生成新的节点和节点对应的边，从而将图递归神经网络应用于图生成的问题；Peng等人[46]提出了利用不同的权重矩阵，来表示不同标签的图长短神经网络结构；Ma等人[47]将时间感知LSTM与图神经网络结合，利用LSTM来更新两个关联节点和对应的邻居节点的表示，提出了动态图神经网络，更好地处理传播效应。

3.3 图注意力网络

对于图神经网络中的注意力机制，可以简单理解为借助于注意力(attention )模块取代了一般图卷积神经网络中的卷积激活器，在不同的方法中，可以结合门控信息来提升注意力机制感受域的权重参数，达到更好的推理和应用性能。

图卷积神经网络实现了对图结构数据的节点分类，而注意力机制目前在自然语言处理领域有着非常好的效果和表现。对于图注意力机制(Graph Attention Network)而言，邻居节点的特征做累加求和的过程与图卷积神经网络则完全不同，通过全局注意力机制替代了卷积分层传递的固化操作，可以有效地选择在图结构中更为重要的节点或子图、模型、路径分配更大的注意力权重。

图注意力网络中的注意力权重被表示为：

对于第l层网络而言，定义节点为：

是注意力模型中的节点向量

表示为一个可变化的线性变换参数

那么节点间的注意力分数就会根据注意力权重的不同进行迭代。通过和图卷积神经网络的分层传播规则的对比，图注意力网络将原本的常数参数替换为表示邻节点权重的注意力参数。

Zhang等人[49]提出了一种通过卷积子网络来控制分配权重的自我注意力机制，基于循环门控单元用于解决流量速度预测的问题。Lee等人[50]提出了结合LSTM的利用注意力机制进行图节点分类的方法，Abu-El-Haija等人[42]提出了一种注意力游走的方法，将图注意力机制应用到节点嵌入中。

现实中信息在被表示成节点和边构成的拓扑结构时往往是异构的，广义上被定义为异构信息网络(HIN)[51]，而现阶段的图神经网络方法大多是聚焦于同构图的处理分析上，对于在本文1.2节中提到的节点异构和边异构的图结构而言，更大的信息量和更复杂的网络结构带来了更大的挑战和研究价值。Xiao等人[52]提出了一种基于注意机制的异构图注意力网络，将节点和边的异构性表达为不同类型的语义信息，通过节点层的注意力来判断相同属性邻节点的重要性，同时利用语义层的注意力选择有意义的元路径，节点层利用注意力来表示不同节点i，j的重要性。

图注意力网络的研究还集中在图像语义推理、上下文推理等方面。具体的，Yang等人[53]在处理通过自然语言来表示图像中的描述对象的问题时，通过抽取图像中对象之间的语义关系建立关联图结构，借助动态图注意力网络D GA来实现更好的语义推理能力。

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。