【《图神经网络概述》5100字】

图神经网络概述Gori等人[36]首先提出图神经网络的概念，Scarselli等人[37]又在在此基础上进一步研究阐明，早期学习目标节点的表示都是以迭代的方式通过循环神经架构传播邻近信息学习得到，迭代直到达到稳定的状态，该过程计算量比较大，这个问题也成了该领域的一项研究难点。2018年，DeepMind、谷歌大脑、MIT和爱丁堡大学的27名作者，对图神经网络及其推理能力进行了全面阐述[38]。随后，关系网络（RelationNetwork）、图卷积网络（GraphConvolutionalNetwork）、几何深度学习技术（GeometricDeepLearning）、图神经网络（GraphNeuralNetwork）等关键词频频出现在各大顶级机器学习、数据挖掘会议上。图神经网络（GNN）有两大优势。第一，在现实世界中图是比较常见的一种数据结构，在图神经网络还没有发展起来的时候没有与之相对应神经网络模型，而GNN可以看作在图上的扩展，将卷积的思想从欧几里得域迁移到非欧几里得域[39]。第二，由于基于传统神经网络的人工智能系统的智能推理能力有限，无法展现出人工智能系统的“智能”之处，但是图神经网络却恰哈具备这种“推理能力”。换言之，图神经网络是符号主义和非符号主义相结合的产物，将规则、知识引入神经网络，使得神经网络具备了可解释性和推理能力。事实上，图神经网络并不是近几年诞生的新概念和技术，早在2005年这一概念就被提出。在后来的发展中，研究者们在针对图的空间域（SpatialDomain）和频谱域（SpecturalDomain）上分别提出了不同形式的图神经网络，并通过深入研究在2017年将空间域模型和频谱域模型进行了良好的结合，自此，图神经网络的研究进入了高速发展阶段。近几年研究者们把图神经网络分为了五类：图卷积网络[40]（GraphConvolutionalNetworks）、图注意力网络[41]（GraphAttentionNetworks）、图自编码机（GraphAuto-encoder）、图生成网络（GraphGenerativeNetworks）、图时空网络（GraphSpatial-TemporalNetworks）。1.1图卷积神经网络图卷积网络(GCN)，由传统的卷积神经网络引申出的图卷积网络，图卷积方法可分为两种，基于频谱的方法和基于空间的方法。基于频谱的方法，从图信号处理的角度，引入滤波器来定义图卷积，因此基于频谱的图卷积可理解为从图信号中去除噪声。基于空间的图卷积方法，通过汇集邻居节点的信息来构建图卷积，当图卷积在节点级运作时，可以将图池化模块和图卷积进行交错叠加，从而将图粗化为高级的子图。一般应用于社交网络以及电商场景等。针对图像识别任务，由于图片中的像素点都是二维结构，为了提取图片的特征信息，CNN应运而生。CNN的核心在于它的内核，内核其实是一个个小窗口，在图片上不断平移，通过卷积的方式来提取特征。由于图片结构上的平移不变性：

一个小窗口无论移动到图片的哪一个位置，其内部的结构都是不会变的，所以CNN可以很好的对具有平移不变性的数据进行特征提取任务。RNN是为一维结构的自然语言序列而设计的，通过各种“门”操作，对序列前后的信息进行互相影响，从而用来捕捉序列的特征。无论图片还是语言，都属于欧式空间的数据，欧式空间的数据特点就是结构比较规则。然而在现实世界中，大部分的数据结构都是不规则的，典型的就是图结构，如社交网络、交通网络、蛋白质网络、知识图谱等等。因为图的结构一般来说是十分不规则的，所以它不具备平移不变性。不同节点的周围结构可能都是不同的，针对这种数据结构，传统的CNN、RNN的处理能力就显得力不从心。为了处理这类数据，涌现出了许多方法，GCN只是其中的一种。图卷积神经网络与CNN的作用一样，用来进行特征提取，但是所针对的对象是图数据。GCN可以从这种不规则的图数据中提取特征信息，利用这种特征信息可以进行节点分类、图分类、边预测、图的嵌入表示等任务。表2-1GCN概念概念定义G一个拓扑图定义为G=(V,E)其中V是节点集合，E是边集合。NN是图中节点个数，即|V|F节点的特征数，不同学习任务F不同X网络初始化矩阵,X是N行F列的矩阵D图的度矩阵,Dij表示点i和点j是否存在连接A图结构表征矩阵,A是N行N列的矩阵，A通常是G的邻接矩阵HiGCN中每层输出矩阵Hi是一个N行F列矩阵WiGCN中每层权值矩阵Wi是一个F行F列矩阵在图数据中，假如有N个节点（node），每个节点都有自己的特征，设这些节点的特征组成一个N×D维的矩阵X，然后各个节点之间的关系也会形成一个N×N维的矩阵A，也称为邻接矩阵，大小为N×N，N为节点数量，它表示任意两个顶点之间的邻接关系，邻接则为1，不邻接则为0。X和A便是模型的输入，GCN中的层与层之间的传播方式如下公式所示： (1)其中是无向图G的邻接矩阵加上每个顶点和自身加一条边，I是单位矩阵。只用邻接矩阵A的话，由于A的对角线上都是0，所以在和特征矩阵H相乘的时候，只会计算这个node的所有邻居的特征的加权和，而该node自己的特征却被忽略了。因此，研究者们做一个小小的改动，给A加上一个单位矩阵I，这样就让对角线元素变成1了，希望在进行信息传播的时候顶点自身的特征信息也得到保留。公式(1)中是度矩阵（degreematrix），其公式为：，度矩阵为对角矩阵，对角线上的元素值即为该节点的度再加1，其中公式是可以事先算好的，因为这两个矩阵均已知是没有经过归一化的矩阵，这样与特征矩阵相乘会改变特征原本的分布，产生一些不可预测的问题。所以研究者们对A做一个标准化处理。归一化后的矩阵中每个元素取值都在(0，1)之间。H是每一层的特征，对于输入层的话，H就是X，这个运算可以理解为实现了空间信息的聚合。其中第0层的输入，是原始的特征，以后每增加一层，就会多聚合一阶邻居节点上的信息。是第i层的权重矩阵，权重矩阵的维度为，所以决定下一层的特征数由权重矩阵的第二维度大小。最终训练出来的参数矩阵W的个数都是核心公式中的层数所决定的，最后采用非线性激活函数，一般比较常用的非线性激活函数有Sigmoid、ReLu等。1.2图注意力神经网络与图卷积神经网络最大的不同之处在于，图注意力网络在图卷积网络的基础上引入了注意力机制，在真实网络中，节点与节点之间或者单个节点对于全局的影响程度不同，在研究过程中应当根据不同节点的影响比重大小对其分配不同的权重，继而在端到端的框架中，可以同时学习到注意力权重和神经网络参数，图注意网络一般被应用于异质网络社区发现等场景[42]。1、GraphAttentionNetwork(GAT)GAT模型思想主要是使用用注意力机制对邻近节点特征进行加权求和，

邻近节点特征的权重与图结构并无关系，主要取决去节点本身特征的影响因子。引入注意力机制之后，只与相邻节点有关，即共享边的节点有关，无需得到整张图的信息：(1)该图不需要是无向的(如果边缘j→i不存在，可以简单地省略计算；(2)它使这项技术直接适用于归纳学习，包括在训练期间完全看不见的图形上的评估模型的任务。2、图注意力层GraphAttentionlayer图注意力层的输入与输出GAT与GCN同样也是一个特征提取器，针对的是N个节点，按照其输入的节点特征预测输出新的节点的特征，图注意力层的输入是节点特征向量集，如公式（2）：（2）其中N为节点个数，F为节点特征的个数，矩阵h的大小是N×F，代表了所有节点的特征，而R只代表了某一个节点的特征，所以它的大小为F×1，每一层的输出是一个新的节点特征向量集：（3）其中F′表示新的节点特征向量维度，可以不等于F。特征提取与注意力机制为了得到相应的输入与输出的转换，研究需要根据输入的特征至少进行一次线性变换得到输出的特征，所以就需要对所有节点训练一个权重矩阵：，这个权重矩阵就是输入的F个特征与输出的F′个特征之间的关系。self−attention注意力机制其作用是能够更好地学习到全局特征之间的依赖关系，self−attention通过直接计算图结构中任意两个节点之间的关系，一步到位地获取图结构的全局几何特征。self−attention利用了attention机制，分三个阶段进行计算：(1)引入不同的函数和计算机制，根据Query和某个，计算两者的余弦相似性或者相关性，最常见的方法包括：求两者的向量点积、求两者的向量余弦相似性或者通过再引入额外的神经网络来求值；(2)引入类似softmax的计算方式对第一阶段的得分进行数值转换，一方面可以进行归一化，将原始计算分值整理成所有元素权重之和为1的概率分布；另一方面也可以通过softmax的内在机制更加突出重要元素的权重；(3)第二阶段的计算结果即为对应的权重系数，然后进行加权求和即可得到attention数值。针对每个节点实行self-attention的注意力机制，注意力系数为： (4)下标i，j表示第i个节点和第j个节点，公式表示了节点j对节点i的重要性，而不去考虑图结构的信息，向量h就是节点的特征向量，不是一个常数或是矩阵，是一个函数，类似于f(x)那种自己定义好的函数。之前的研究者们将注意力分配到节点i的邻居节点集上，即，节点i也是的一部分，为了使得注意力系数更容易计算和便于比较，引入了softmax函数对所有的i的相邻节点j进行正则化: (5)注意力机制是一个单层的前馈神经网络，是神经网络中连接层与层之间的权重矩阵，在该前馈神将网络的输出层上还加入了LeakyReLu函数，其中ReLu是将所有的负值都设为零，相反，LeakyReLu是给所有负值赋予一个非零斜率。综合上述公式（2）和（3），整理可得到完整的注意力机制如下： (6)其中，和都叫做注意力系数，只不过是在基础上进行归一化后的。上述过程可用下图来表示：图2-6计算注意力系数3、输出特征通过上面内容得到了正则化后的不同节点之间的注意力系数，可以用来预测每个节点的输出特征： (7)为与特征相乘的权重矩阵，为前面计算得到的注意力互相关系数，为非线性激活函数，中遍历的j表示所有与i相邻的节点，公式(5)表示该节点的输出特征与和它相邻的所有节点有关，是它们的线性和的非线性激活后得到的。4、multi-headattentionmulti-headattention:其实就是多个self−attention结构的结合，每个head学习到在不同表示空间中的特征，多个head学习到的attention侧重点可能略有不同，这样给了模型更大的容量。为了稳定self−attention的学习过程，研究者发现扩展注意力机制以采用multi−headattention是有益的。用k个独立注意力机制执行公式（5），然后将它们的特征连接起来。但是，如果对最终的网络层执行multi−headattention，则连接操作不再合理，相反，采用k平均来替代连接操作，并延迟应用最终的非线性函数（通常为分类问题的softmax或logisticsigmoid），得到最终的公式： （8）共K个注意力机制需要考虑，k表示K中的第k个，第k个注意力机制为，第k个注意力机制下性变换权重矩阵表示为，图2-7multi-headattention图例:图2-7多头计算由节点在其邻域上的multi-headattention（具有K=3个头）的图2-7所示。不同的箭头样式和颜色表示独立的注意力计算，来自每个头的聚合特征被连接或平均以获得。1.3其他图神经网络1、图自编码机图自编码机。是一种非监督学习框架，目标是通过编码机学习到低维的节点向量，然后通过解码机重构出图数据。图自编码机是一种常见的图嵌入方法，可以被应用到有属性信息的图中和无属性信息的图中。2、图生成网络图生成网络。目标是从数据中生成合理的结构，因为图是一种较为复杂的数据结构，其中包含不同类型的节点信息以及节点之间会存在直接关系或者间接关系，所以要想从数据中生成指定经验分布的图是非常具有挑战性的，目的是在图的节点和边经验分布的基础上，生成新的图，进行对抗式训练。3、图时空网络图时空网络。时空网络图有区别于其他种类的图数据，在该图数据中，图不仅由V、E、A组成，增加了一个X属性，表示的是图在时间维度上的属性变化。目标是从时空图中学习到不可见的一些模式，这在交通预测、人类的活动预测中变得越来越重要。比如，在道路交通网络就是一种时空图，图的数据在时间维度上是连续的，用图时空网络构建道路交通预测模型，就可以更加准确地预测出交通网络中的交通状态。图时空网络的关键在于考虑同一时间下的空间与事物的关联关系。许多现在的方法使用GCN结合CNN或者RNN对这种依赖关系进行建模。参考文献[1]ForbesA.Thegeographyoftransportsystems[J].Australianjournalofmaritime&oceanaffairs:AJMOA,2014.[2]郜金荣.分子生物学实验指导[M].化学工业出版社,2015.[3]BronsteinMM,BrunaJ,LeCunY,etal.Geometricdeeplearning:goingbeyondeuclideandata[J].IEEESignalProcessingMagazine,2017,34(4):18-42.[4]ZhangJ,YuP.IntegratedAnchorandSocialLinkPredictionsacrossSocialNetworks.AAAIPress,2015:2125–2131[5]ShiC,LiY,ZhangJ,etal.Asurveyofheterogeneousinformationnetworkanalysis[J].IEEETransactionsonKnowledgeandDataEngineering,2016,29(1):17-37.[6]WangF,QuY,ZhengL,etal.Deepandbroadlearningoncontent-awarePOIrecommendation[C]//InProc.ofCIC,2017:369-378.[7]SunY,HanJ,YanX,etal.Pathsim:Metapath-basedtop-ksimilaritysearchinheterogeneousinformationnetworks[C].InProc.ofVLDB,2011,4(11):992-1003.[8]HuangZ,ZhengY,ChengR,etal.Metastructure:Computingrelevanceinlargeheterogeneousinformationnetworks[C]//InProc.ofKDD,2016:1595-1604.[9]ZhaoH,YaoQ,LiJ,etal.Meta-graphbasedrecommendationfusionoverheterogeneousinformationnetworks[C]//InProc.ofKDD,2017:635-644.[10]ShiC,YuPS.HeterogeneousInformationNetworkAnalysisandApplications[J].SpringerInternationalPublishing,2017.[11]PengC,WangX,PeiJ,etal.ASurveyonNetworkEmbedding[J].IEEETransactionsonKnowledgeandDataEngineering,2017,99:1-1.[12]ClausetA，NewmanMEJ，MooreC.Findingcommunitystructureinverylargenetwork，Phys.Rev.E，2004(70).066111.

[13]刘大有，金弟，何东晓.复杂网络社区挖掘综述[J].计算机研究与发展，2012（09）.

[14]NewmanM,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].2004,69(2):026113.[15]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].清华大学出版社,2006.[16]阳广元，曹霞.国内社区发现研究进展[J].情报资料工作，2014（02）.[17]WuZ,ZhanB,JieC,etal.DiscoveringCommunitiesinMulti-relationalNetworks[J].SpringerInternationalPublishing,2015.[18]TangL,LiuH,ZhangJ,etal.Communityevolutionindynamicmulti-modenetworks.Proceedingsofthe14thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,ACM,2008:677-685.[19]SunY,TangJ,HanJ,etal.Communityevolutiondetectionindynamic