精华内容
下载资源
问答
  • 在本综述中,我们对现有的图神经网络模型进行了详细的回顾,对应用进行了系统的分类,并提出了四个有待进一步研究的问题。 1. Introduction  图是一种数据结构,它为一组对象(节点)及其关系(边)建模。...

                                        Graph Neural Networks: A Review of Methods and Applications


    摘要:大量的学习任务要求处理元素间含有丰富关系信息的图形数据。物理系统的建模、分子指纹的学习、蛋白质界面的预测和疾病的分类都需要模型从图形输入中学习。在其他领域,如文本、图像等非结构数据的学习中,提取结构的推理,如句子的依赖树和图像的场景图,是一个需要图推理模型的重要研究课题。图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。虽然发现原始的 GNN 很难为一个固定点进行训练,但是网络结构、优化技术和并行计算的最新进展使它们能够成功地学习。近年来,基于图卷积网络 (GCN) 和门控图神经网络 (GGNN) 的系统在上述众多任务中表现出突破性的性能。在本综述中,我们对现有的图神经网络模型进行了详细的回顾,对应用进行了系统的分类,并提出了四个有待进一步研究的问题。


    1. Introduction

           图是一种数据结构,它为一组对象(节点)及其关系(边)建模。近年来,机器学习图分析的研究越来越受到人们的重视,因为图有很强的表达能力,可以作为许多系统的外延,包括社会科学 (social networks) , 自然科学 (物理系统和蛋白质相互作用网络) , 知识图谱等许多研究领域。图分析作为一种用于机器学习的独特的非欧几里得数据结构,主要集中在节点分类、链接预测和聚类等方面。图神经网络(GNN)是在图域上运行的基于深度学习的方法。GNN 以其令人信服的性能和较高的可解释性,近年来已成为一种广泛应用的图论分析方法。在下面几段中,我们将说明图神经网络的基本动机。

           GNNs 的第一个动机源于卷积神经网络 (CNN)。CNN能够提取多尺度的局部空间特征并将其组合起来,构建出高度表达的表示形式,在几乎所有的机器学习领域都取得了突破,开启了深度学习的新时代。然而,CNN只能处理常规的欧几里德数据,如图像(2D 网格)和文本(1D 序列),而这些数据结构可以看作是图的实例。随着我们对CNN和图表的深入,我们发现了CNN的关键:局部连接、共享权重和多层使用。这些对解决图域问题也具有重要意义,因为:①图是最典型的局部连通结构;②与传统的谱图理论相比,共享权值降低了计算量;③多层结构是处理层次化模式的关键,它能捕获各种尺寸的特征。因此,很容易就能发现 CNN 对图形的推广。但是,如1所示,局部化的卷积滤波器和集合算子很难定义,这阻碍了CNN从欧几里得域向非欧几里得域的转化。

            另一个动机来自图嵌入,它学习在低维向量中表示图节点、边或子图。在图分析领域,传统的机器学习方法通常依赖于手工设计的特征,且受其灵活性和高成本的限制。 DeepWalk 是第一个基于表示学习的图嵌入方法,它遵循表示学习的思想和词嵌入的成功,在生成的随机游动上应用了 SkipGram 模型。类似的方法如node2vec、LINE和 TADW 也取得了突破。然而,这些方法遭受两个严重的缺点。首先,编码器中的节点之间没有共享参数,这导致计算效率低下,因为这意味着参数数量随节点数量线性增长。直接嵌入法由于缺乏推广能力,不能处理动态图,也不能推广到新图。

           基于CNN和图形嵌入,图形神经网络(GNN)被提出用于对图形结构中的信息进行集合。因此,它们可以对由元素组成的输入和/或输出及其依赖性进行建模,并且图神经网络可以用RNN核同时对图上的扩散过程进行建模。

           在接下来的部分,我们解释了图神经网络为什么值得研究的根本原因第一,像 CNN 和 RNN 这样的标准神经网络不能正确处理图形输入,因为它们按特定的顺序堆叠节点的特征。然而,图中并没有一个自然的节点顺序。为了完整地表示一个图,我们应该像 CNN 和 RNN 一样遍历所有可能的顺序作为模型的输入,这在计算时是非常多余的。为了解决这个问题,GNN 分别在每个节点上传播,忽略节点的输入顺序。换句话说,GNNs 的输出对于节点的输入顺序是不变的。第二,图中的边表示两个节点之间的依赖信息。在标准神经网络中,依赖信息仅仅作为节点的特征。然而,GNN 可以在图形结构的引导下进行传播,而不是将其作为特性的一部分。GNN 通常通过邻域状态的加权和来更新节点的隐藏状态。第三,推理是高级人工智能的一个重要研究课题,人脑中的推理过程几乎都是基于从日常经验中提取的图。标准的神经网络已经显示出通过学习数据的分布来生成合成图像和文档的能力,而他们仍然不能从大量的实验数据中学习推理图。然而,GNN 探索从像场景图片和故事文档这样的非结构性数据生成图形,这可以成为进一步高级 AI 的强大神经模型。最近已经证明,一个未经训练的 GNN 与一个简单的体系结构也表现良好。

          关于图神经网络有几个全面的综述。[18] 给出了早期图神经网络方法的正式定义。[19] 证明了图神经网络的逼近性质和计算能力。[20] 提出了一个统一的框架Monet,将CNN架构推广到非欧几里得域(图和流形),该框架可以推广图[2]、[21]上的几种光谱方法以及流形[22]、[23]上的一些模型。[24] 提供了几何深度学习的全面回顾,其中介绍了它的问题、困难、解决方案、应用和未来的方向。[20] 和 [24] 的研究重点是将卷积推广到图或流形上,但本文只关注图上定义的问题,并研究了图神经网络中的其它机制,如门机制、注意机制和跳过连接。[25] 提出了消息传递神经网络 (MPNN),它可以推广几种图神经网络和图卷积网络的方法。给出了消息传递神经网络的定义,并演示了其在量子化学中的应用。[26]提出了非局部神经网络(NLNN),它统一了几种“自我关注”方式。然而,模型并没有在原始文件的图表上明确定义。以具体的应用领域为重点,[25] 和 [26] 只举例说明如何使用框架推广其他模型,而不提供对其他图神经网络模型的评审。[27] 提出了图网络 (GN) 框架。该框架具有很强的泛化其他模型的能力,其关系归纳偏差促进了组合泛化,被认为是 AI 的重中之重。然而,[27] 是部分立场文件,部分评审和部分统一,它只是一个粗略的分类申请。在本文中,我们提供了一个全面评审不同图形神经网络的模型以及一个系统的分类方法的应用。

           总之,本文对具有以下贡献的图神经网络进行了广泛的综述。一、我们提供了一个详细的评审现有图形神经网络的模型。我们介绍了原始模型、它的变体和几个通用框架。我们研究了这方面的各种模型,并提供了一个统一的表示,以在不同的模型中呈现不同的传播步骤。通过识别相应的聚合器和更新器,可以很容易地使用我们的表示区分不同的模型。二、我们对应用程序进行了系统分类,并将应用程序分为结构场景、非结构场景和其他场景。我们介绍了几种主要的应用程序及其相应的方法在不同的情况。三、我们提出了四个有待进一步研究的问题。图神经网络存在过度光滑和尺度问题。目前还没有有效的方法来处理动态图以及建模非结构感知数据。我们对每一个问题都进行了透彻的分析,并提出了今后的研究方向。

           本次调查的其余部分整理如下。第2节,我们介绍了图神经网络家族中的各种模型。我们首先介绍原始框架及其局限性。然后我们展示它的变体,试图释放这些限制。最后,我们介绍了最近提出的几个通用框架。在第3节中,我们将介绍图神经网络在结构场景、非结构场景和其他场景中的几个主要应用。在第4节中,我们提出了图神经网络的四个开放问题以及未来的研究方向。最后,我们在第5节结束了调查。


    2. Models

           在第 2.1 节中,我们描述了[18] 提出的原始图神经网络。我们还列出了原始 GNN 在表达能力和训练效率上的局限性。在 2.2 节中,我们介绍了图神经网络的几种变体,旨在释放其局限性。这些变量对不同类型的图进行操作,使用不同的传播函数和高级训练方法。在第 2.3 节中,我们提出了三个通用框架,可以推广和扩展几条工作线。具体而言,消息传递神经网络 (MPNN) [25] 将各种图神经网络和图卷积网络方法统一起来;非局部神经网络 (NLNN) [26] 将几种自我关注式方法统一起来。图网络 (GN) [27] 可以推广本文提到的几乎每个图神经网络变量。

           在进一步进入不同的部分之前,我们给出了将在整个论文中使用的符号。符号的详细描述见表 1。

    2.1 Graph Neural Networks

            图神经网络 (GNN) 的概念是在 [18] 首次提出的,它扩展了现有的用于处理图域中的数据的神经网络。在一个图中,每个节点由它的特征和相关的节点自然地定义。GNN 的目标是学习一个状态嵌入 h_{v}\in R^{s} ,其中包含每个节点的邻域信息。状态嵌入 h_{v} 是节点 v 的 s 维向量,可用于产生节点标签等输出 o_{v}设 f 为参数函数,称为局部转移函数,在所有节点间共享,并根据输入邻域更新节点状态。g 是局部输出函数,它描述了输出是如何产生的。然后,h_{v} 和 o_{v} 定义如下:

    其中 \bg_black \bg_black x_{v},x_{co[v]},h_{ne[v]},x_{ne[v]} 分别是 v 的特征、其边的特征、状态以及 v 附近节点的特征。

            让 H, O, X 和 X_{N} 分别是通过堆叠所有状态、所有输出、所有特征和所有节点特征构建的向量。然后我们有一个紧凑的形式:

    其中 F 是全局转换函数,G是全局输出函数,是图中所有节点 f, g 函数的叠加形式。H的值是等式3的固定点,并以f为收缩图的假设进行了独特的定义。H  的值是由等式(3)确定的,并且假设 F 是收缩图,H 的值被唯一定义。

            在 Banach 不动点定理 [28] 的建议下,GNN 使用以下经典迭代方案计算状态:

    式中,H^{t} 表示H 的 t 次迭代。对于任何初始值H(0),动态方程(5)以指数形式快速收敛到方程(3)的解。注意,F 和 G 中描述的计算可以解释为前馈神经网络。

            当我们有GNN的框架时,下一个问题是如何学习 f 和 g 的参数。利用目标信息(特定节点 t_{v})进行指导,损失可以写如下:

    其中 p 是受指导节点的数量。学习算法基于梯度下降策略,由以下步骤组成:①状态 h_{v}^{t} 由式(1)迭代更新到时间 t,它们接近式(3)的定点解:H\left ( T \right )\approx H;②权重w的梯度由损失计算得出;③根据上一步计算的梯度更新权重w

            Limitations  虽然实验结果表明,GNN是一种强大的结构数据建模体系结构,但原始GNN仍然存在一些局限性。首先,对于固定点迭代更新节点的隐藏状态是低效的。如果放宽固定点的假设,我们可以设计一个多层GNN,以得到节点及其邻域的稳定表示。其次,GNN在迭代中使用相同的参数,而大多数流行的神经网络在不同的层中使用不同的参数,这是一种分层特征提取方法。此外,节点隐藏状态的更新是一个顺序过程,可以从RNN内核(如GRU和LSTM)中获益。第三,边上也存在一些信息性特征,这些特征在原始GNN中无法有效建模。例如,知识图中的边具有关系类型,通过不同边的消息传播应根据它们的类型而有所不同。此外,如何了解边的隐藏状态也是一个重要的问题。最后,如果我们把重点放在节点的表示上而不是图上,就不适合使用固定点,因为固定点上的表示分布在数值上是平滑的,区分每个节点的信息量也比较少。

     

    2.2 Variants of Graph Neural Networks

    在本节中,我们介绍了图神经网络的几种变体。第2.2.1节重点介绍在不同图类型上操作的变体。这些变体扩展了原始模型的表示能力。第2.2.2节列出了传播步骤的几种模式(卷积、门机制、注意机制和跳跃连接),这些模型可以学习更高质量的表示。第2.2.3节介绍了使用高级培训方法的变体,这些方法可提高培训效率。图2概述了图神经网络的不同变体。

    2.2.1  Graph Types

    在原GNN[18]中,输入图由带标签信息的节点和无向边组成,这是最简单的图格式。然而,世界上有许多图形变体。在本小节中,我们将介绍一些设计用于对不同类型的图进行建模的方法。

           Directed Graphs  图的第一个变量是有向图。无向边可以看作是两个有向边,这表明两个节点之间存在一种关系。然而,有向边比无向边能带来更多的信息。例如,在一个知识图中,边从头部实体开始到尾部实体结束,头部实体是尾部实体的父类,这意味着我们应该区别对待父类和子类的信息传播过程。ADGPM[29]使用了两种权重矩阵,W_{p} 和W_{c},以合并更精确的结构信息。传播规则如下:

    其中,D_{p}^{-1}A_{p}, D_{c}^{-1}A_{c} 分别是父代和子代的标准化邻接矩阵。

            Heterogeneous Graphs 图的第二个变种是异构图,其中有几种节点。处理异构图的最简单方法是将每个节点的类型转换为一个与原始特征连接的热特征向量。此外,GraphInception[30] 将 metapath 的概念引入到异构图的传播中。使用metapath,我们可以根据相邻节点的类型和距离对其进行组。对于每个相邻组,GraphInception 将其视为同构图中的一个子图进行传播,并将来自不同同构图的传播结果连接起来以进行集体的节点表示。

           Graph with Edge Information 在图形的最终变体中,每个边还具有诸如边的权重或类型等信息。处理这种图有两种方法:首先,我们可以将图转换为二分图,其中原始边也成为节点,并且将一个原始边拆分为两个新边,这意味着边节点和开始/结束节点之间有两个新边。G2S[31]的编码器对邻域使用以下聚合函数:

    其中,W_{r} 和 b_{r} 是不同类型边(关系)的传播参数。其次,我们可以调整不同的权重矩阵,使其在不同的边上传播。当关系数(不同类型边数量)很大时,r-GCN[32] 引入两种正则化方法来减少关系建模的参数:基对角分解和块对角分解,通过基分解,每个 W_{r} 定义如下:

    也就是说,作为基变换 V_{b}\in R^{d_{in}\times d_{out}}与系数 a_{rb} 的线性组合,只有系数依赖于r。在块对角分解中,r-GCN 通过对一组低维矩阵的直接求和来定义每个W_{r},这比第一个矩阵需要更多的参数。

    2.2.2  Propagation Types

    传播步骤和输出步骤在模型中对于获得节点(或边)的隐藏状态至关重要。如下所列,在原始图神经网络模型的传播步骤中有几个主要修改,而研究人员通常在输出步骤中遵循简单的前馈神经网络设置。可以在表2中找到GNN不同变体的比较。变体使用不同的聚集器从每个节点的邻域收集信息,并指定更新器来更新节点的隐藏状态。

     

     

    Convolution. 

           人们对将卷积推广到图域越来越感兴趣。这方面的进展通常分为Spectral Methods 和Non-Spectral Methods。谱方法使用图的谱表示。[35]提出了谱网络。通过计算拉普拉斯图的特征分解,在傅立叶域中对卷积运算进行了定义。该运算可以定义为信号x\in R^{n}(每个节点的标量)与参数化的滤波器g_{\theta} = diag(\theta) (\theta \in R^{N})的乘积:

    其中,U 为归一化的拉普拉斯图 L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=UA U^{T}的特征向量矩阵 (D是Degree Matrix,A是图的邻接矩阵),其特征值的对角矩阵为\Lambda

            该运算会导致潜在的密集计算和非空间局部化滤波器。[36]试图通过引入具有平滑系数的参数化来使谱滤波器进行空间局部化。[37]提出,g_{\theta}(\Lambda ) 可以用切比雪夫多项式T_{k}(x)的截断展开近似,直到K^{th}。因此,运算是:

    其中,\widetilde{L}=\frac{2}{\lambda _{max}}L-I_{N}\lambda_{max} 表示 L 的最大特征值。\theta \in R^{K}现在是切比雪夫系数的向量。切比雪夫多项式被定义为T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x),其中T_{0}(x)=1, T_{1}(x)=x。可以看到该运算是K-局部化的,因为它是拉普拉斯算子中的K阶多项式。[38] 使用这种K-局域卷积来定义卷积神经网络,它可以消除计算拉普拉斯特征向量的需要。

           [2]将逐层卷积运算限制在K=1,以缓解节点度分布非常宽的图的局部邻域结构过度设置的问题。它进一步近似\lambda _{max}\approx 2,公式简化为:

    其中有两个自由参数\theta_{0}^{'} 和 \theta_{1}^{'} 。用\theta = \theta_{0}^{'}=-\theta_{1}{'}约束参数数量后,我们可以获得以下表达式:

           注意,叠加此运算可能会导致数值不稳定和梯度爆炸/消失,[2]引入重正化技巧:I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\rightarrow\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}},其中 \tilde{A}= A+I_{N} 和∙\tilde{D}_{ii}=\sum _{j}\tilde{A}_{ij}。最后,[2]将特征映射的定义推广到具有输入通道 C 和滤波器F 的信号X\in R^{N\times C},如下所示:

    其中\Theta \in R^{C\times F}是滤波器参数矩阵,Z\in R^{N\times F}是卷积信号矩阵。

           [39]提出了一种基于高斯过程的贝叶斯方法来解决图的半监督学习问题。它展示了模型和光谱滤波方法之间的相似之处,这可以从另一个角度给我们一些启示。

           然而,在上述所有谱方法中,所学习的滤波器依赖于拉普拉斯特征基,拉普拉斯特征基依赖于图结构,也就是说,在特定结构上训练的模型不能直接应用于具有不同结构的图。

           非谱方法直接在图上定义卷积,在空间上邻域上操作。非谱方法的主要挑战是定义具有不同大小邻域的卷积运算,并保持CNNs的局部不变性。

           [33]对不同度的节点使用不同的权重矩阵,其中W_{L}^{N_{\nu }}是 L 层上具有N_{\nu } 度的节点的权重矩阵。该方法的主要缺点是它不能应用于具有更多节点度的大规模图。

           [21]提出了扩散卷积神经网络。转移矩阵用于定义DCNN中节点的邻域。对于节点分类,它有

    其中X 是输入特征的N\times F张量(N是节点数,F是特征数)。P^{*}是一个N\times K\times N 的张量,它包含矩阵P 的幂级数\left \{ P, P^{2}, ..., P^{K} \right \},P 是图邻接矩阵A 的度归一化转换矩阵。每个实体都转换为扩散卷积表示,它是由图在F 特征上扩散的K 跳定义的K\times F矩阵。然后用一个K\times F权矩阵和一个非线性激活函数f 来定义,最后H\left ( N\times K\times F \right )表示图中每个节点的扩散表示。

           至于图的分类,DCNN只是取节点表示的平均值,这里1_{N} 是N \times 1 维向量。DCNN还可以应用于边分类任务,这需要将边转换为节点并增加邻接矩阵。

           [40]为每个节点提取并规一化恰好K个节点的邻域。然后,归一化邻域作为卷积运算的接收域。[20]提出了一个非欧几里得域上的空间域模型(MoNet),它可以概括前面的几种技术。流形上的GCNN[22] 和 ACNN[23] 或图上的GCN[2] 和DCNN[21] 可以作为 MoNet 的特殊实例。

           [1]提出了 GraphSAGE,一个通用归纳框架。该框架通过从节点的本地邻域采样和聚集特征来生成嵌入。然而,[1]没有利用等式18中的全部邻域集,而是通过均匀采样来利用固定大小的邻域集。

    [1]提出了三个聚合函数:

    Mean aggregator。它可以被视为来自转换GCN框架[2] 的卷积运算的近似值,因此GCN变体的归纳版本可以通过等式(19)导出。Mean aggregator不同于其他聚合器,因为它不执行等式(18)中连接 h_{v}^{t-1} 和 h_{N_{\nu }}^{t} 的连接操作。它可以被视为“skip connection”[41] 的一种形式,并且可以实现更好的性能。

    LSTM聚合器。[1]还使用了一个基于LSTM的聚合器,它具有更大的表达能力。然而,LSTMs以顺序方式处理输入,因此它们不是排列不变的。[1]通过置换节点的邻域来调整LSTMs以在无序集上操作。

    Pooling aggregator。在池化聚合器中,每个邻居的隐藏状态通过完全连接层提供,然后对节点的邻域集进行最大池化运算。注意,在这里可以使用任何对称函数来代替max pooling运算。

    最近,结构感知卷积和结构感知卷积神经网络被提出[42]。单变量函数用作滤波器,它们可以处理欧几里德和非欧几里德结构化数据。

     

    Gate

            有几项工作试图在传播步骤中使用GRU[43] 或LSTM[44] 这样的门机制,以减少以前GNN模型中的限制,并改善信息在图结构中的长期传播。[45]提出了门控图神经网络(GGNN),它在传播步骤中使用门控循环单元(GRU),在固定数量的步骤T 中展开循环,并使用随时间的反向传播来计算梯度。具体来说,传播模型的基本循环为

    节点\nu 首先聚集来自其邻域的消息,其中A_{v} 是图邻接矩阵A 的子矩阵,并且表示节点\nu与其邻域的连接。类似GRU的更新函数包含来自其他节点和上一个时间步骤的信息,以更新每个节点的隐藏状态。a 收集节点\nu 的邻域信息,z 和r 是更新门和重置门。LSTMs在基于树或图的传播过程中也使用类似于GRU的方式。

             [46]提出了对基本LSTM体系结构的两个扩展:Child-Sum Tree-LSTM 和 N-ary LSTM。和标准LSTM单元一样,每个Tree-LSTM单元(用\nu索引)包含输入和输出门i_{v}o_{v}、存储单元c_{v}和隐藏状态h_{v}。Tree-LSTM单元不是一个遗忘门,而是为每个孩子k包含一个遗忘门f_{vk},允许该单元有选择地合并来自每个子级的信息。Child-Sum Tree-LSTM 转换方程如下:

    x_{v}^{t} 是标准 LSTM 设置中时间 t 的输入向量。

            如果一棵树的分支因子最多为K,并且一个节点的所有子节点都是有序的,也就是说,它们可以从1索引到K,那么就可以使用N-ary Tree-LSTM。对于节点vh_{vk}^{t} 和c_{vk}^{t} 分别表示其第K个孩子在时刻t的隐藏状态和存储单元。转换方程如下:

    为每个孩子k 引入独立的参数矩阵,使得模型比 Child-Sum Tree-LSTM 能够学习更多有关单元子级状态的细粒度表示。

            这两种类型的Tree-LSTMs 可以很容易地适应图。[47] 中的结构化 LSTM 是 N-ary Tree-LSTM 在图中应用的一个例子。但是,它是一个简化版本,因为图中的每个节点最多具有 2 个传入边(来自其父节点和同级节点的前一个)。[34] 在关系抽取任务的基础上提出了图 LSTM 的另一种变体。图和树的主要区别在于图的边有它们的标签。[34] 利用不同的权重矩阵表示不同的标签:

    其中m_{vk } 代表节点v 和 k 之间的边标签。

           [48]提出了改进文本编码的Sentence LSTM。它将文本转换为图形,并利用图LSTM学习表示。S-LSTM 在许多 NLP 问题中表现出强大的表示能力。[49] 提出了一种基于图 LSTM 网络来解决语义对象解析任务。该方法采用置信区间自适应地选择初始节点,确定节点更新顺序。它遵循将现有的 LSTM 推广到图结构数据的相同思想,但是具有特定的更新序列,而我们上面提到的方法对节点顺序不可知。

     

    Attention

           注意机制已成功地应用于许多基于序列的任务中,如机器翻译 [50]-[52]、机器阅读 [53] 等。[54] 提出了一种图注意网络 (GAT),它将注意机制融入到传播步骤中。它通过关注相邻节点,遵循自我关注策略计算每个节点的隐藏状态。[54] 提出了单图注意层,并通过堆叠该层构建任意图注意网络。该层计算注意机制中节点对\left ( i,j \right ) 的系数:

    其中\alpha_{ij}是节点 j 对 i 的注意力系数,N_{i} 表示图中节点 i 的邻域。对于一层的节点输入集是h =\left \{ h_{1},h_{2},...,h_{N} \right \}, h_{i}\in \mathbb{R} ^{F},其中N 是节点数,F 是每个节点的特征数,该层产生一组新的节点特征(可能具有不同的基数{F}'),{h}' =\left \{ {h}'_{1},{h}'_{2},...,{h}'_{N} \right \}, {h}'_{i}\in \mathbb{R} ^{​{F}'} 作为其输入。W \in \mathbb{R}^{​{F}'\times F} 是应用于每个节点的共享线性变换的权重矩阵,a \in \mathbb{R}^{2{F}'} 是单层前馈神经网络的权向量。它由一个 SoftMax 函数进行归一化,并应用非线性LeakyReLU(负输入斜率\alpha =0.2),

    此外,该层利用与[52]类似的multi-head attention 来稳定学习过程。它应用 K 独立注意机制来计算隐藏状态,然后连接它们的特征(或计算平均值),从而产生以下两种输出表示:

    其中 \alpha ^{k}_{ij}  是由第 k 个注意机制计算的标准化注意系数。

    [54]中的注意力结构具有以下几个特点:(1)节点邻域对的计算是可并行的,因此操作是有效的;(2)通过对邻域指定任意权重,可以应用于不同程度的图节点;(3)很容易应用于归纳学习问题。

     

    Skip connection

    许多应用展开或堆叠图形神经网络层,目的是随着更多的层(即k层)使每个节点聚集来自k-hops 之外的邻域的更多信息而获得更好的结果。然而,在许多实验中已经观察到,更深的模型不能提高性能,更深的模型甚至可以表现得更差[2]。这主要是因为更多的层也可以传播来自指数级增加的扩展邻域成员的噪声信息。

    解决这个问题的一个简单方法,即残差网络[55],可以从计算机视觉社区中找到。但是,即使有残差连接,具有更多层的GCN在许多数据集上的性能也不如2层 GCN[2]。[56]提出了一条 Higehway GCN,该,该模型使用类似于公路网络的分层门[57]。一个层的输出与它的输入和 gate weight 相加:

    通过增加 Highway gate,性能在4层达到峰值,具体问题在[56]中讨论。[58]研究邻域聚合方案的性质和由此产生的限制。提出了一种学习自适应、结构感知表示的跳跃知识网络。跳跃知识网络从最后一层的每个节点的所有中间表示(即“跳跃”到最后一层)中进行选择,使模型根据需要适应每个节点的有效邻域大小。[58]在实验中使用了三种方法,即concatenationmax-poolingLSTM-attention来聚合信息。跳跃知识网络在社会、生物信息学和引文网络的实验中表现良好。它还可以与图形卷积网络、图形存储和图形注意网络等模型相结合,以提高它们的性能。

    2.2.3 Training Methods

    原有的图卷积神经网络在训练和优化方法上存在一些缺陷。具体来说,GCN需要完整的拉普拉斯图,这对于大型图来说是计算消耗。此外,一个节点在L层的嵌入是通过在L-1层的所有相邻节点的嵌入来递归计算的。因此,单个节点的接受域相对于层数呈指数增长,因此计算单个节点的梯度花费很大。最后,GCN被单独训练为固定图,缺乏归纳学习的能力。

           GraphSAGE[1]是对原始GCN的综合改进。为了解决上面提到的问题,GraphSAGE用可学习的聚合函数代替了全图拉普拉斯函数,这是执行消息传递和推广到未知节点的关键。如等式18所示,它们首先聚合邻域嵌入,与目标节点的嵌入连接,然后传播到下一层。通过学习聚合和传播函数,GraphSAGE可以为看不见的节点生成嵌入。此外,GraphSAGE使用邻域采样来缓解接受域扩展。

           FastGCN[59]进一步改进了采样算法。FastGCN不是对每个节点的相邻节点进行采样,而是直接对每个层的接收字段进行采样。FastGCN采用重要性抽样,重要性系数计算如下:

    与上述固定采样方法相比,[60]引入了一个参数化和可训练的采样器,以在前一层进行分层采样。此外,这种自适应采样器可以同时确定最佳采样重要性和减少方差。[61]利用节点的历史激活作为控制变量,提出了一种基于控制变量的GCN随机逼近算法。[61] 这种方法限制了1-hop 邻域外的接收域,但使用历史隐藏状态作为一个可承受的近似值。[62]重点关注GCN的局限性,其中包括GCN需要许多额外的标记数据来进行验证,并且还受到卷积过滤器的本地化性质的影响。为了解决这些局限性,作者提出了 Co-Training GCN和 Self-Training  GCN两种方法来扩大训练数据集。前一种方法确定训练数据的最近邻域,而后一种方法则采用类似于增强的方法。

     

    2.3 General Frameworks

    除了图神经网络的不同变体之外,还提出了几个通用框架,旨在将不同的模型集成到一个框架中。[25]提出了消息传递神经网络(MPNN),它结合了各种图形神经网络和图形卷积网络方法。[26]提出了非局部神经网络(NLNN)。它包括几种“self-attention”式的方法,[52],[54],[63]。[27]提出了图网络,该网络结合了MPNN和NLNN方法以及许多其他变体,如交互网络[4]、[64],Neural Physics Engine[65],CommNet[66],structure2vec[7]、[67],GGNN[45],Relation Network[68]、[69],Deep Sets[70]和 Point Net[71]。

    2.3.1 Message Passing Neural Networks

           [25]提出了一个监督图学习的通用框架,称为消息传递神经网络(MPNNS)。MPNN框架抽象了几种最流行的图结构数据模型之间的共性,例如谱方法[35][2],图卷积[38]和非谱方法[33]、门控图神经网络[45]、交互网络[4]、分子图卷积[72]、深张量神经网络[73]等。该模型分为两个阶段:消息传递阶段和读出阶段。消息传递阶段(即传播步骤)运行 T 个时间步骤,并根据消息函数 m ^{t}_{v} 和顶点更新函数U^{t} 进行定义。利用消息函数 m ^{t}_{v},隐藏状态 h^{t}_{v} 的更新函数如下:

    其中,e_{vw} 表示从节点v 到w 的边的特征。消息读出阶段使用读出函数 R 计算全图的特征向量,

    其中T 表示总时间步数。消息函数M_{t}、顶点更新函数U_{t}和读取函数R 可以有不同的设置。因此,MPNN框架可以通过不同的功能设置归纳出几个不同的模型。这里我们给出了一个推广GGNN的例子,其他模型的功能设置可以在[25]中找到。GGNN的函数设置为:

    其中,A_{e_{vw}} 是邻接矩阵,每个边标签e 对应一个。GRU是在[43]中引入的门循环单元。i 和j 是函数R 中的神经网络。

    2.3.2 Non-local Netural Networks

    [26]提出了非局部神经网络(NLNN)来捕捉深度神经网络的长期依赖性。非局部运算是计算机视觉中经典非局部平均运算[74]的推广。非局部运算将某一位置的响应计算为所有位置特征的加权和。这组位置可以在空间、时间或时空中。因此,神经网络可以被视为不同“self-attention”风格方法的统一,[52],[54],[63]。我们将首先介绍非局部运算的一般定义,然后介绍一些具体的实例。

            在非局部平均运算[74]之后,一般的非局部运算定义为:

    其中i 是输出位置的索引,j 是枚举所有可能位置的索引。f(h_{i}, h_{j}) 计算代表i 和j 之间关系的标量。g(h_{i}) 表示输入h_{j } 的转换,系数\frac{1}{c(h)}用于归一化结果。

           有几个实例具有不同的f 和g 设置。为了简单起见,[26]使用线性变换作为函数 g。这意味着 g(h_{j})=W_{g}h_{j},其中W_{g} 是一个可学习的权重矩阵。接下来,我们在下面列出函数f 的选择。

    Gaussian    高斯函数是根据非局部平均值[74]和同侧滤波器[75]的自然选择,h^{T}_{i}h_{j} 是点积相似度,C(h)=\sum_{\forall j} f(h_{i},h_{j})

    Embedded Gaussian     通过计算嵌入空间中的相似性,可以直接扩展高斯函数,这意味着:

    可以发现,在[52]中提出的 self-attention 是嵌入高斯版本的一种特殊情况。对于给定的i\frac{1}{c(h)}f(h_{i},h_{j})成为沿尺寸j 的Softmax计算,因此{h}'=softmax(h^{T}W^{T}_{\theta }W_{\phi }h)g(h),这与[52]中的self-attention形式相匹配。

    Dot product     函数f 也可以实现为点积相似度:

    Concatenation    

    [26]将上述非局部运算包装成非局部块,如下所示:

    式(34)中给出了{h}'_{i},“+h_{i} ”表示剩余连接[55]。因此,非局部块可以插入到任何预先训练的模型中,这使得块更加适用。

    2.3.3 Graph Networks

    [27]提出了图网络(GN)框架,该框架概括和扩展了各种图神经网络、MPNN和NLNN方法[18]、[25]、[26]。我们首先介绍[27]中的图定义,然后描述GN块、核心GN计算单元及其计算步骤,最后介绍其基本设计原则。

    Graph definition

    在[27]中,图被定义为3元组G=(u,H,E)(这里我们用H 代替V表示符号的一致性)。u是全局属性,H =\left \{ h_{i} \right \}_{i=1:N^{v}} 是节点集(基数N^{v}),其中每个h_{i} 都是节点的属性。E=\left \{ \left ( e_{k},r_{k},s_{k} \right ) \right \}_{k=1:N^{e}} 为边集(基数N^{e}),其中每个e_{k}为边的属性,r_{k}为接收节点的索引,s_{k}为发送节点的索引。

    GN block 

    一个GN块包括三个更新函数 \phi,以及三个聚合函数 \rho\rho 函数必须对其输入的排列保持不变,并且应采用可变参数。

    Computation steps

    (1)\phi ^{e} 用参数\left ( e_{k},h_{rk},h_{sk},u \right )应用于每条边,并返回{e}'_{k}。每个节点i 的每条边输出结果集为{E}'_{i}=\left \{ \left ( {e}'_{k},r_{k},s_{k} \right ) \right \}_{r_{k}=i,k=1:N^{e}}{E}'_{i}=\bigcup _{i}{E}'_{i}=\left \{ \left ( {e}'_{k},r_{k},s_{k} \right ) \right \}_{k=1:N^{e}}是所有边沿输出的集合.

    (2)\rho ^{e\rightarrow h} 应用于{E}'_{i},并将投影到顶点i 的边的边更新聚合到{\bar{e}_{i}}' 中,这将在下一步的节点更新中使用。

    (3)\phi ^{h} 被应用于每个节点i ,以计算更新的节点属性{h}'_{i} 。得到的每节点输出的集合是,{H}'=\left \{ {h}'_{i} \right \}_{i=1:N^{v}}

    (4)\rho ^{e\rightarrow u} 应用于{E}',并将所有边更新聚合到{\bar{e}}' 中,然后在下一步的全局更新中使用。

    (5)\rho ^{h\rightarrow u}应用于{H}',并将所有节点更新聚合到{\bar{h}}'中,然后在下一步的全局更新中使用。

    (6)\phi ^{u} 在每个图中应用一次,并计算全局属性{u }' 的更新。

    请注意,该命令并未严格执行。例如,可以从全局更新到每个节点,再到每个边。\varphi 和\rho 函数不一定是神经网络,尽管在本文中我们只关注神经网络的实现。

    Design Principles

    图网络的设计基于三个基本原则:灵活的表示、可配置的块内结构和可组合的多块架构

    · Flexible representations    GN框架支持属性的灵活表示以及不同的图结构。全局、节点和边属性可以使用任意表示形式,但实值向量和张量最常见。可以根据任务的具体要求简单地定制GN块的输出。例如,[27]列出了几个聚焦于边缘的[76]、[77]、聚焦于节点的[3]、[4]、[65]、[78]和聚焦于图的[4]、[25]、[69] 的图网络。就图结构而言,在图结构方面,框架可以应用于图结构是显式的结构场景,关系结构应该被推断或假定的非结构场景。

    · Configurable within-block structure    GN模块内的功能及其输入可以有不同的设置,因此GN框架可以在模块内结构配置中提供灵活性。例如,[77]和[3]使用完整的GN块。它们的\varphi 实现使用神经网络,\rho 函数使用元素求和。基于不同的结构和功能设置,各种模型(如MPNN、NLNN和其他变量)可以通过GN框架来表达。更多细节可以在[27]中找到。

    · Composable multi-block architectures     GN块可以被组合以构建复杂的体系结构。任意数量的GN块可以用共享或非共享参数按顺序组成。[27]利用GN块来构建 encode-peocess-decode 体系结构和循环的基于GN的体系结构。这些架构如图3所示。构建基于GN的体系结构的其他技术也是有用的,例如跳过连接、LSTM或GRU风格的门控方案等。

     

    3 APPLICATIONS

    图神经网络已经在许多问题领域中得到了探索,包括有监督的、半监督的、无监督的和强化的学习环境。在本节中,我们简单地将应用程序分为三个场景:(1)数据具有显式关系结构的结构场景,如物理系统、分子结构和知识图;(2)关系结构不显式的非结构场景,包括图像、文本等;(3)其他应用场景,如生成模型和组合优化问题。请注意,我们只列出几个具有代表性的应用程序,而不提供详尽的列表。应用程序摘要见表3。

    3.1 Structural Scenarios

    在接下来的小节中,我们将介绍GNN在结构场景中的应用,其中数据自然地在图结构中表示。例如,GNN被广泛用于社交网络预测[1],[2],交通预测[56],[118],推荐系统[119],[120]和图表表示[121]。具体来说,我们将讨论如何用对象关系图模拟现实世界的物理系统,如何预测分子的化学性质和蛋白质的生物相互作用性质,以及在知识图中推理知识库外实体的方法。

    3.1.1  Physics

    模拟现实世界的物理系统是理解人类智能的最基本的方面之一。通过将对象表示为节点,将关系表示为边,我们可以以简单有效的方式对对象、关系和物理进行基于GNN的推理。

    [4] 提出了 Interaction Networks 来对各种物理系统进行预测和推断。该模型以对象和关系作为输入,说明它们相互作用的原因,并应用效果和物理动力学来预测新的状态。它们分别对关系中心模型和对象中心模型进行建模,使得跨不同系统进行概括变得更加容易。

    Visual Interaction Networks [64]可以从像素做出预测。它从每个对象的两个连续输入帧中学习状态代码。然后,在通过交互网络块添加它们的交互效果之后,状态解码器将状态代码转换成下一步的状态。

    [3]提出了一个基于图网络的模型,它可以进行状态预测或归纳推理。推理模型将部分观察到的信息作为输入,并为隐式系统分类构造一个隐藏图。

    3.1.2 Chemistry and Biology

    Molecular Fingerprints 计算分子指纹,即代表分子的特征向量,是计算机辅助药物设计的核心步骤。传统的分子指纹是手工制作和固定的。通过将GNN应用于分子图,我们可以获得更好的指纹。[33]提出了通过GCN和求和计算子结构特征向量以获得整体表示的神经图定义。聚合函数及节点更新表示为

    Protein Interface Prediction   [5]专注于蛋白质界面预测的任务,这是一个具有挑战性的问题,在药物发现和设计中有着重要的应用。所提出的基于GCN的方法分别学习配体和受体蛋白残基的表示,并将其合并用于成对分类。GNN也可以用于生物医学工程。通过蛋白质-蛋白质相互作用网络,[109]利用图形卷积和关系网络进行乳腺癌亚型分类。[108]还提出了一个基于GCN的多药副作用预测模型。他们的工作模拟了药物和蛋白质的相互作用网络,并分别处理不同类型的边。

    3.1.3 Knowledge graph

    [6]利用GNN解决知识库完成过程中的知识库外实体问题。[6]中的OOKB实体直接连接到现有实体,因此可以从现有实体聚合OOKB实体的嵌入。该方法在标准KBC设置和OOKB设置中均达到了令人满意的性能。[110]利用GCN解决跨语言知识图校正问题。该模型将不同语言的实体嵌入到统一的嵌入空间中,并根据嵌入相似性对其进行校正。

     

    3.2 Non-structural Scenarios

    在本节中,我们将讨论非结构场景中的应用,例如图像、文本、编程源代码[45]、[122]和多代理系统[63]、[66]、[76]。由于长度限制,我们将只详细介绍前两种情况。大致上,有两种方法可以将图神经网络应用于非结构场景:(1)结合来自其他领域的结构信息来提高性能,例如使用来自知识图的信息来减轻图像任务中的零样本问题;(2)推断或假设场景中的关系结构,然后应用该模型来解决图中定义的问题,例如[48]中将文本建模为图的方法。

    3.2.1 Image

    Image Classification     

    图像分类是计算机视觉领域中一项非常基本和重要的任务,备受关注,并拥有许多像 ImageNet [123] 这样著名的数据集。图像分类的最新进展得益于大数据和 GPU 计算的强大能力,这使得我们可以在不从图像中提取结构信息的情况下训练分类器。然而,在图像分类领域中,零样本和少样本学习越来越受欢迎,因为大多数模型在获得足够数据的情况下也能获得相似的性能。有一些利用图神经网络将结构信息纳入图像分类的工作。首先,知识图可以作为额外的信息来指导零样本识别分类 [29],[94]。[94] 构建一个知识图,其中每个节点对应一个对象类别,并以节点的词嵌入作为输入来预测不同类别的分类器。由于卷积结构的深度会产生过平滑效应,[94] 中使用的六层 GCN 在表示时将冲刷掉许多有用的信息。为了解决 GCN 在传播过程中的平滑问题,[29] 在图中采用了较大邻域的单层 GCN,该邻域中同时包含了单跳和多跳节点。并证明了用现有的分类器构建零样本分类器的有效性。除了知识图外,数据集中图像之间的相似性对于少样本的学习也是有益的[93]。[93] 对于少样本分类提出建立一个基于相似性的加权全连通图像网络,并在图中做消息传递。由于大多数知识图对于推理来说是偏大的,[96] 根据目标检测的结果选择相关实体构建子图,并将 GGNN 应用于提取的图进行预测。此外,[95] 建议构造一个新的知识图,其中实体是所有类别。并且,它们定义了三种类型的标签关系:super subordinate 超从属关系、正相关关系和负相关关系,并直接在图中传播标签的置信度。

    Visual Reasoning   

    计算机视觉系统通常需要通过结合空间和语义信息来进行推理,所以为推理任务生成图表是很自然的。一个典型的视觉推理任务是视觉问答,[97]分别构造图像场景图和问题句法图。然后应用 GGNN 对嵌入进行训练,以预测最终答案。尽管对象之间存在空间连接,但 [124] 构建了以问题为条件的关系图。有了知识图,[92]、[98] 能进行更精细的关系探索和更可解释的推理过程。视觉推理的其他应用包括对象检测、交互检测和区域分类。在对象检测中 [99]、[100] ,GNN 用于计算 RoI 特征;在交互检测中 [101]、[102],GNN 是人与对象之间的消息传递工具;在区域分类中 [103] ,GNN 在连接区域和类的图上执行推理。

    Semantic Segmentation

    语义分割是实现图像理解的关键步骤。这里的任务是为图像中的每个像素分配一个唯一的标签(或类别),这可以被认为是一个密集的分类问题。然而,图像中的区域往往不是网格状的,需要非局部信息,这导致了传统 CNN 的失败。一些工作利用了图形结构化数据来处理它。[49] 提出了 Graph-LSTM,通过建立基于距离的超像素映射形式的图,并应用 LSTM 在全球范围内传播邻域信息,建立长期依赖关系和空间连接模型。后续工作从编码层次信息的角度对其进行了改进 [104]。此外,3D 语义分割(RGBD 语义分割)和点云分类利用了更多的几何信息,因此很难通过 2D CNN 建模。[107]构造了一个 K 近邻 (KNN) 图,并使用一个三维 GNN 作为传播模型。预测模型经过几步展开后,以每个节点的隐藏状态作为输入,预测其语义标签。因为总是有太多的点,[105]通过构建超级点图并为它们生成嵌入来解决大规模3D点云分割。为了分类超节点,[105]利用GGNN和图形卷积。[106]提出通过边来模拟点的相互作用,通过输入其终端节点的坐标来计算边表示向量,然后通过边聚合更新节点嵌入。

    3.2.2 Text

    图形神经网络可以应用于基于文本的多种任务。它既可以应用于句子级任务(如文本分类),也可以应用于单词级任务(如序列标记)。我们将在下面介绍几个主要的文本应用程序。

    Text classification

    文本分类是自然语言处理中一个重要的经典问题。经典的GCN模型[1]、[2]、[20]、[21]、[36]、[38]和GAT模型[54]被应用于解决该问题,但是它们仅使用文档之间的结构信息,并且不使用太多文本信息。[79] 提出了一种基于 graph-CNN 的深度学习模型,首先将文本转换为单词的图形,然后使用 [40] 中的图卷积运算将单词图卷积。[48] 提出了句子 LSTM 来编码文本。它将整个句子看作一个单一的状态,它由单个单词的子状态和一个整体句子级别的状态组成。它对分类任务使用全局语句级表示。这些方法可以将文档或句子看作一个单词节点图,也可以依赖文档引用关系来构造这个图。[80] 以文档和文字为节点构建语料库图(异构图),利用Text GCN 学习文档和文字的嵌入。情绪分类也可以看作是一个文本分类问题,[46] 提出了Tres-LSTM 方法。

    Sequence labeling

    由于 GNNs 中的每个节点都有自己的隐藏状态,如果将句子中的每个单词都看作一个节点,就可以利用隐藏状态来解决序列标注问题。[48] 使用Sentence LSTM 标记序列。它已经进行了 POS-tagging 和 NER 任务的实验,并获得了最先进的性能。语义角色标注是序列标注的另一项任务。[81] 提出了一个Syntactic GCN 来解决这个问题。Syntactic GCN 是 GCN [2]的一个特殊变体,它作用在有标记边的图上。它集成了edge-wise gates,让模型调节单个依赖边的贡献。利用句法依存树的Syntactic GCNs 作为句子编码器,学习句子中单词的潜在特征表示。[81] 还揭示了 GCNs 和 LSTMs 在任务中功能互补。

    Neural machine translation

    神经机器翻译任务通常被认为是一个序列到序列的任务。[52]引入了注意机制,取代了最常用的递归或卷积层。事实上,转换器假设语言实体之间有一个完全连通的图形结构。GNN的一个流行应用是将句法或语义信息整合到NMT任务中。[82]在句法感知的NMT任务中使用Syntactic GCN。[83]使用句法GCN整合了关于源句子predicate-argumen 结构的信息(即语义-角色表示),并比较了仅整合句法或语义信息,或者两种信息都整合到任务中的结果。[31]在语法感知的NMT中使用了GGNN。它通过将边转换成额外的节点,将句法依赖图转换成Levi 图的新结构,因此边标签可以表示为嵌入。

    Relation extration

    提取文本中实体之间的语义关系是一项重要且研究广泛的任务。一些系统将该任务视为两个独立任务的pipeline,命名为实体识别和关系提取。[84]提出了一个使用双向序列和树形结构的LSTM-RNNs的端到端关系提取模型。[86]提出了一种图卷积网络的扩展,它适合于关系提取,并对输入树应用剪枝策略。跨句子的N-ary关系抽取检测跨多个句子的N个实体之间的关系。[34]探索了一个基于图LSTMs的跨句N-ary关系抽取的通用框架。它将输入图分割成两个DAGs,而重要信息可能在分割过程中丢失。[85]提出了一个graph-state LSTM模型。它保持了原始的图形结构,并通过允许更多的并行化来加速计算。

    Event extraction

    事件抽取是一种重要的信息提取任务,用于识别文本中特定类型事件的实例。[87] 研究了一种基于依赖树的卷积神经网络(即Syntantic  GCN)来进行事件检测。[88] 提出了一种Jointly Multiple Events Extraction (JMEE) 框架,通过引入句法快捷键弧来增强信息流,从而联合提取多个事件触发点和参数,并将其应用于基于注意的图卷积网络,建立图信息模型。

    Others applications

    GNN也可以应用于许多其他应用。有几个工作集中在AMR到文本生成任务上。在这一领域已经提出了基于Sentence-LSTM的方法[89]和基于GGNN的方法[31]。[46]使用Tree LSTM来模拟两个句子的语义相关性。[90]利用Sentence LSTM来解决multi-hop阅读理解问题。另一个重要方向是关系推理,关系网络[69],交互网络[4]和递归关系网络[91],被提出来解决基于文本的关系推理任务。上面引用的作品并不是详尽的列表,我们鼓励我们的读者找到更多他们感兴趣的图神经网络的研究和应用领域。

     

    3.3 Other Scenarios

    除了结构性和非结构性场景之外,还有一些其他场景,图神经网络在其中发挥了重要作用。在本小节中,我们将介绍生成图模型和GNNs的组合优化。

    3.3.1 Generative Models

    现实世界图形的生成模型因其重要的应用而引起了极大的关注,包括对社会交互作用建模、发现新的化学结构和构建知识图形。由于深度学习方法具有强大的学习图形隐式分布的能力,近年来神经图生成模型出现了激增。

    NetGAN [114] 是最早建立神经元网络图生成模型的研究之一。它将图的生成问题转化为以特定图中的随机游动为输入的游动生成问题,并利用 GAN 体系结构训练出一个游动生成模型。虽然生成的图保留了原始图的重要拓扑属性,但节点数在生成过程中不能改变,这与原始图相同。GraphRNN[125]通过逐步生成每个节点的邻接向量生成图的邻接矩阵,这可以输出具有不同节点数量的所需网络。

    MolGAN[117]不是顺序生成邻接矩阵,而是一次预测离散图结构(邻接矩阵),并利用置换不变鉴别器来解决邻接矩阵中的节点变化问题,它还为基于RL的优化应用了一个奖励网络,以获得所需的化学性质。此外,[115]提出了约束变分自动编码器,以确保生成图的语义有效性。此外,GCPN[116]通过强化学习纳入了特定领域的规则。[126]提出了一种顺序生成边和节点的模型,并利用图神经网络提取当前图的隐藏状态,该隐藏状态用于在序列生成过程中决定下一步的动作。

    3.3.2 Combinatorial Optimization

    图的组合优化问题是一组 NP 难题,引起了各领域科学家的广泛关注。一些具体的问题,如旅行商问题 (TSP) 和最小生成树 (MST) 已经得到了各种启发式解。近年来,利用深度神经网络解决这类问题已成为一个研究热点,其中一些解决方法因图的结构而进一步利用了图神经网络。

    [127]首先提出了一种深度学习的方法来解决TSP问题。他们的方法由两部分组成:用于参数化奖励的Pointer Network [128]和用于培训的政策梯度模块[129]。这项工作已被证明可与传统方法相媲美。然而,Pointer Network 是为像文本这样的顺序数据设计的,而顺序不变编码器更适合这种工作。[130]通过包含图神经网络改进了该方法。他们首先从structure2vec [67]中获得节点嵌入,这是GCN的变体,然后将它们输入到用于决策的Q-learning 模块中。这项工作取得了比以往算法更好的性能,证明了图神经网络的表示能力。[113]提出了一种基于注意力的编解码算法。这种方法可以看作是图注意网络,其readout阶段是基于注意力的解码器,而不是理论上对训练有效的强化学习模块。[111]专注于二次分配问题,即测量两个图的相似性。基于GNN的模型独立地学习每个图的节点嵌入,并使用注意机制匹配它们。这种方法提供了有趣的良好性能,即使在标准relaxation-based技术似乎受到影响的情况下。[112]直接使用GNNs作为分类器,可以对具有成对边的图进行密集预测。模型的其余部分帮助GNNs做不同的选择并有效地训练。

     

    4 OPEN PROBLEMS

    尽管GNNs在不同领域取得了巨大成功,但值得注意的是,GNN模型不足以为任何情况下的任何图形提供令人满意的解决方案。在这一部分,我们将陈述一些有待进一步研究的未决问题。

    Shallow Structure

    由于深层结构具有更多的参数,传统的深层神经网络可以堆叠数百层以获得更好的性能,从而大大提高了表达能力。然而,图神经网络总是浅层的,大多数不超过三层。[62] 中的实验表明,叠加多个 GCN 层将导致过度平滑,也就是说,所有顶点将收敛到相同的值。尽管一些研究人员已经设法解决了这个问题 [45],[62],但它仍然是 GNN 的最大限制。

    Dynamic Graphs

    另一个具有挑战性的问题是如何处理具有动态结构的图。静态图是稳定的,因此它们可以建模的可行性,而动态图引入变化的结构。当边缘和节点出现或消失时,GNN 不能自适应地变化。动态 GNN 正在被积极研究,我们认为它是一般 GNN 稳定性和适应性的一个里程碑。

    Non-Structural Scenarios

    尽管我们已经讨论了 GNN 在非结构场景中的应用,但是我们发现没有最佳的方法从原始数据生成图。在图像领域,一些工作利用 CNN 获取特征映射,然后将它们上采样形成超像素作为节点 [49],而另一些工作直接利用一些对象检测算法获取对象节点。在文本领域[103]中,一些工作使用语法树作为语法图,而另一些工作使用全连通图。因此,寻找最佳的图形生成方法将为 GNN 的贡献提供更广泛的领域。

    Scalability

    如何在像社交网络或推荐系统这样的网络规模条件下应用嵌入方法一直是几乎所有图形嵌入算法面临的致命问题,GNN 也不例外。由于许多核心步骤在大数据环境中都是计算消耗的,因此难以扩展 GNN。关于这种现象有几个例子:第一,图数据不是正则欧几里德,每个节点都有自己的邻域结构,所以批处理不能应用。那么,当节点数和边数达数百万时,计算图的拉普拉斯也是不可行的。此外,我们需要指出的是,缩放决定了算法是否能够应用到实际应用中。几项工作已经提出了解决这个问题的办法[120]。

     

    5 CONCLUSION

    近年来,图神经网络已经成为图域机器学习的有力工具。这一进步归功于表达能力、模型灵活性和训练算法的进步。在这个调查中,我们进行了图神经网络的全面审查。对于 GNN模型,我们介绍了它的变体,按照图类型、传播类型和训练类型进行分类。此外,我们还总结了几个通用框架,以统一表示不同的变体。在应用程序分类方面,我们将 GNN 应用程序分为结构化场景、非结构化场景和其他场景,然后对每个场景中的应用程序进行详细的回顾。最后,我们提出了四个有待解决的问题,指出了图神经网络的主要挑战和未来的研究方向,包括模型深度、可扩展性、处理动态图形和非结构性场景的能力。

     

     

     

    论文地址

     

     

     

    展开全文
  • 摘要 近年来,由于神经网络在模式识别和数据挖掘领域的应用和其易用性,神经网络已获得了巨大的普及。...在本文中,我们将研究图和GNN的定义和基础,并了解图神经网络的一些最新应用。 一、什么是

    摘要

    在过去的几年中,神经网络的兴起与应用成功推动了模式识别和数据挖掘的研究。许多曾经严重依赖于手工提取特征的机器学习任务(如目标检测、机器翻译和语音识别),如今都已被各种端到端的深度学习范式(例如卷积神经网络(CNN)、长短期记忆(LSTM)和自动编码器)彻底改变了。尽管传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功,但许多实际应用场景中的数据是从非欧式空间生成的,传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。例如,在电子商务中,一个基于图(Graph)的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐,但图的复杂性使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的,每个图都有一个大小可变的无序节点,图中的每个节点都有不同数量的相邻节点,导致一些重要的操作(例如卷积)在图像(Image)上很容易计算,但不再适合直接用于图。此外,现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而,对于图来说,情况并非如此,图中的每个数据样本(节点)都会有边与图中其他实数据样本(节点)相关,这些信息可用于捕获实例之间的相互依赖关系。近年来,人们对深度学习方法在图上的扩展越来越感兴趣。在多方因素的成功推动下,研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想,定义和设计了用于处理图数据的神经网络结构,由此一个新的研究热点——“图神经网络(Graph Neural Networks,GNN)”应运而生。在本文中,我们将研究图和GNN的定义、应用场景、嵌入特征及简单代码实现,并概述图神经网络的一些最新应用。

    一、什么是图神经网络?

    1.1 什么是图?

    从名词"图神经网络"我们可以看到GNN的最基本部分是图结构的形式。在计算机领域中,图被定义为具有两个部分组成的数据结构,顶点和边缘。我们可以将图G 1定义为G = VE。其中V是一组顶点,E是它们之间的边,其中术语中顶点和节点通常可以互换使用的。如果在链接图的边上有任何箭头标记,则称该图由方向依赖性,则它是有向图。如果不是,则它们是无向图。其图结构如图所示:

    该图形描述了:

    • V作为顶点集
    • 以E为边

    然后,图G =(V,E),其中V称为节点,E为边。

    1.2 什么是图神经网络(GNN)?

    由于图具有极强的表达能力,因此它们在机器学习领域得到了广泛的关注。每个节点都有与其相互关联的嵌入特征与嵌入方式,该嵌入定义了数据空间中的节点。图神经网络是指在图上运行的神经网络体系结构。GNN架构的主要目的是学习包含有关其邻域信息的嵌入,使用此嵌入,我们可以解决一些问题,例如标记节点,预测节点和关联边等。换句话说,图神经网络是另一类深度学习方法,旨在对图形给出的数据进行推理。

     

    使用GNN神经网络结构点会添加从相邻节点收集的信息,然后最后一层结合所有这些添加的信息,并给出整体模型的预测或分类。

    GNN输出执行:

    1. 节点分类
    2. 链接预测
    3. 图分类

    1.3 图神经网络的嵌入特征及方法

    网络嵌入旨在将网络节点表示为低维向量表示,同时保留网络拓扑结构和节点内容信息,以便可以使用简单的现成方法轻松执行任何后续的图形分析任务,例如分类、聚类和推荐架式机器学习算法。GNN和传统神经网络嵌入之间的主要区别在于:GNN是为各种任务而设计的一组神经网络模型,因此其网络嵌入涵盖了针对同一任务的各种方法。因此,GNN可以通过GAE框架解决网络嵌入问题,同时网络嵌入包含其他非深度学习方法例如矩阵分解和随机游走。

    嵌入特征之随机游走

    DeepWalk是第一个以无监督学习的节点嵌入算法。它在训练过程中类似于词嵌入。它的目的是让图中的节点分布和语料库中的单词分布都遵循幂律,如下图所示:

    算法包括两个步骤:

    1. 在图中的节点上执行随机游走生成节点序列;

    2. 运行skip-gram,根据步骤1中生成的节点序列学习每个节点的嵌入;

    在随机游走过程中,下一个节点是从前一节点的邻居统一采样。然后将每个序列截短为长度为2 | w |+1的子序列,其中w表示skip-gram中的窗口大小。如果您不熟悉skip-gram,我之前的博客文章已经向您介绍它的工作原理。

    在论文中,分层softmax用于解决由于节点数量庞大而导致的softmax计算成本过高的问题。为了计算每个单独输出元素的softmax值,我们必须为所有元素k计算ek。

    softmax的定义

    因此,原始softmax的计算时间是 O(|V|) ,其中其中V表示图中的顶点集。

    多层的softmax利用二叉树来解决softmax计算成本问题。 在二叉树中,所有叶子节点(上面所说的图中的v1,v2,... v8)都是图中的顶点。 在每个内部节点中(除了叶子节点以外的节点,也就是分枝结点),都通过一个二元分类器来决定路径的选取。 为了计算某个顶点v_k的概率,可以简单地计算沿着从根节点到叶子节点v_k的路径中的每个子路径的概率。 由于每个节点的孩子节点的概率和为1,因此在多层softmax中,所有顶点的概率之和等于1的特性仍然能够保持。如果n是叶子的数量,二叉树的最长路径由O(log(n))限定,因此,元素的计算时间复杂度将减少到O(log | V |)。

    多层softmax

    在训练DeepWalk GNN之后,模型已经学习到了每个节点的表示,如下图所示。不同的颜色在输入图中(图a)表示不同标签。 我们可以看到,在输出图中,具有相同标签的节点聚集在一起,而具有不同标签的大多数节点被正确分开。

    然而,DeepWalk的主要问题是它缺乏泛化能力。每当有新节点加入到图中时,它必须重新训练模型以正确表示该节点。因此,这种GNN不适用于图中节点不断变化的动态图。

    二. 图神经网络模型

     GNN模型包括四种类型:
    递归图神经网络(RGNN)
    卷积图神经网络(CGNN)
    图形自动编码器(GAE)
    时空图神经网络(STGNN)

    2.1 递归图神经网络

    这些神经网络旨在使用递归神经网络(RNN)学习节点表示。RGNN通过假设图中的节点不断交换消息(消息传递)来工作。这种交换一直持续到达到稳定的平衡为止.RecGNN主要是GNN的先锋作品。他们在图上的节点上反复应用相同的参数集,以提取高级节点表示形式。受计算能力的限制,较早的研究主要集中在有向无环图上。

    2.2.卷积图神经网络

    CGNN通过概括从网格格式到图形格式的卷积运算来工作。与RGNN相比,CGNN使用了许多层的图卷积。这有助于提取高级节点表示。

    CGNN为构建其他GNN模型奠定了基础。CGNN应用程序的一个示例是 Pinterest的PinSage推荐系统。PinSage算法通过学习分别在3和180亿个节点和边上运行的图节点嵌入来工作。

    2.3 图形自动编码器

     GAE是深度神经网络,可以学习生成新图。他们将节点映射到潜在向量空间。然后,他们从潜在表示中重建图信息。它们用于学习网络中的嵌入和图形的生成分布。GAE已被用来在引用网络中执行链接预测任务。这些网络包含通过引文链接在一起的文章。GAE可以将这些文章分为不同的组。

    2.4 时空图神经网络

     

     

    这些网络背后的思想是同时考虑空间和时间依赖性。在当前的研究中,图卷积捕获了空间依赖性。CNN或RNN捕获时间依赖性。STGNN适用于:人体动作识别、交通速度预测、驾驶员机动预期

     

    (a)具有多个图卷积层的ConvGNN。图卷积层通过聚集来自其邻居的特征信息来封装每个节点的隐藏表示。特征聚合后,将非线性变换应用于结果输出。通过堆叠多层,每个节点的最终隐藏表示形式将接收来自其他邻居的消息。

    (b)具有池和输出层的ConvGNN用于图分类。图卷积层之后是池化层,以将图粗化转化为子图,以使粗化图上的节点表示表示更高的图级表示。读出层通过获取子图的隐藏表示的总和/平均值来总结最终的图形表示。

    (c)用于网络嵌入的GAE 。编码器使用图卷积层获得每个节点的网络嵌入。解码器计算给定网络嵌入的成对距离。在应用非线性激活函数之后,解码器重建图邻接矩阵。通过最小化实际邻接矩阵和重构的邻接矩阵之间的差异来训练网络。

    (d)STGNN用于时空图预测。图卷积层后面是1-D-CNN层。图卷积层利用X 捕获空间依赖性,而1-D-CNN层滑过 X 沿时间轴捕获时间依赖性。输出层是线性变换,为每个节点生成预测,例如在下一时间步的未来值。

    三、图神经网络的应用

    3.1、计算机视觉

    图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。

    在场景图生成中,对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像,场景图生成模型检测和识别对象,并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图,其中每个词代表一个对象,这是一个有希望的解决方案,以合成给定的文本描述图像。

    在点云分类和分割中,点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境,这通常有利于无人驾驶车辆。为了识别点云所描绘的物体,将点云转换为k-最近邻图或叠加图,并利用图论进化网络来探索拓扑结构。

    在动作识别中,识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一组解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图表。给定人类关节位置的时间序列,应用时空神经网络来学习人类行为模式。

    此外,图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。

    3.2、推荐系统

    基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息,基于图的推荐系统能够生成高质量的推荐。推荐系统的关键是评价一个项目对用户的重要性。因此,可以将其转换为一个链路预测问题。目标是预测用户和项目之间丢失的链接。为了解决这个问题,有学者提出了一种基于GCN的图形自动编码器。还有学者结合GCN和RNN,来学习用户对项目评分的隐藏步骤。

    3.3、交通系统

    交通拥堵已成为现代城市的一个热点社会问题。准确预测交通网络中的交通速度、交通量或道路密度,在路线规划和流量控制中至关重要。有学者采用基于图的时空神经网络方法来解决这些问题。他们模型的输入是一个时空图。在这个时空图中,节点由放置在道路上的传感器表示,边由阈值以上成对节点的距离表示,每个节点都包含一个时间序列作为特征。目标是预测一条道路在时间间隔内的平均速度。另一个有趣的应用是出租车需求预测。这有助于智能交通系统有效利用资源,节约能源。

    GNN也已与长期短期记忆(LSTM)和CNN一起使用,以预测一个时间间隔内特定位置的出租车需求数量。它考虑了过去的出租车需求,天气数据和位置信息。

    3.4、化学

    在化学中,研究人员应用图神经网络研究分子的图结构。在分子图中,原子为图中的节点,化学键为图中的边。节点分类、图形分类和图形生成是分子图的三个主要任务,它们可以用来学习分子指纹、预测分子性质、推断蛋白质结构、合成化合物。

    将分子描述为图形的图像

    3.5、自然语言处理

    除了以上四个领域外,图神经网络还已被探索可以应用于其他问题,如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。在NLP中,GNN用于文本数据的分类。他们使用文档中单词之间的相互关系来计算文档中的标签。

    NLP中的图

     

    四、图神经网络的具体应用及代码实现

    通过图神经进行相似度计算

    图相似度搜索是最重要的基于图的应用程序之一,例如,查找与查询化合物最相似的化合物。受神经网络方法最近在几种图形应用(例如节点或图形分类)中取得成功的启发,我们提出了一种新颖的基于神经网络的方法来解决这一经典而具有挑战性的图形问题,旨在减轻计算负担,同时保持良好的性能。这种方法称为SimGNN,它结合了两种策略。首先,我们设计一个可学习的嵌入函数,将每个图形映射到一个嵌入向量中,提供图形的全局摘要。提出了一种新颖的注意力机制来强调关于特定相似性度量的重要节点。其次,我们设计了一种成对节点比较方法,以用细粒度的节点级信息来补充图级嵌入。在三个真实图形数据集上的实验结果证明了该方法的有效性。

    4.1 SIMGNN模型的构建

    4.2 核心代码实现

    from tensorflow import keras
    # from tensorflow.keras import layers
    from keras_gcn import GraphConv
    from keras.models import Model
    from keras.layers import Input
    from custom_layers import Attention, NeuralTensorLayer
    """ 
    Main model : Node-to-Node interaction not implemented.
    Functional API :
    Shared layers are shared_gcn1, shared_gcn2, shard_gcn3, shared_attention
    """
    def simgnn(parser):
        inputA = Input(shape=(None,16))
        GinputA = Input(shape=(None,None))
        inputB = Input(shape=(None,16))
        GinputB = Input(shape=(None,None))
        
        shared_gcn1 =  GraphConv(units=parser.filters_1,step_num=3, activation="relu")
        shared_gcn2 =  GraphConv(units=parser.filters_2,step_num=3, activation="relu")
        shared_gcn3 =  GraphConv(units=parser.filters_3,step_num=3, activation="relu")
        shared_attention =  Attention(parser)
    
        x = shared_gcn1([inputA, GinputA])
        x = shared_gcn2([x, GinputA])
        x = shared_gcn3([x, GinputA])
        x = shared_attention(x[0])
    
        y = shared_gcn1([inputB, GinputB])
        y = shared_gcn2([y, GinputB])
        y = shared_gcn3([y, GinputB])
        y = shared_attention(y[0])
    
        z = NeuralTensorLayer(output_dim=16, input_dim=16)([x, y])
        z = keras.layers.Dense(16, activation="relu")(z)
        z = keras.layers.Dense(8, activation="relu")(z)
        z = keras.layers.Dense(4, activation="relu")(z)
        z = keras.layers.Dense(1)(z)
        z = keras.activations.sigmoid(z)
    
        return Model(inputs=[inputA, GinputA, inputB, GinputB], outputs=z)

    5.总结

    自从引入GNN以来,在过去的几年中,它们已成为解决可以通过图形建模的问题的强大而可靠的工具。这是由于其灵活性,表达能力和易于查看的效果。因此,GNN是具有大量实际应用程序的非结构化数据的直观解决方案。

    6.参考文献

    1. Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., & Sun, M. (2018). Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434.
    2. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Philip, S. Y. (2020). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems.
    3.Bai Y , Ding H , Bian S , et al. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation[J]. 2018.

     

    展开全文
  • 15种图神经网络应用场景总结

    千次阅读 多人点赞 2021-04-13 09:10:43
    在本文中,我们主要关注模型的应用,而具体的网络设计并不是我们这里特别感兴趣的。 社会影响的预测 社会影响预测侧重于朋友之间行为的影响,尤其是在社交网络中。例如,如果一些社交网络上的朋友买了一件衣服,他/...

    在本文中,我们主要关注模型的应用,而具体的网络设计并不是我们这里特别感兴趣的。

    社会影响的预测

    社会影响预测侧重于朋友之间行为的影响,尤其是在社交网络中。例如,如果一些社交网络上的朋友买了一件衣服,他/她会不会也买呢?以社交图作为输入,DeepInf为用户学习网络嵌入(一种潜在的社会表征)。结合下面(d)中手工制作的特征,对社会影响进行预测,比如v是否也会观看广告片段(步骤f)。在训练过程中,将预测结果与真值进行对比,学习这个网络嵌入。

    电子健康记录建模

    我们可以用图来建立医学本体的模型。下面是一个使用DAG(有向无环图)表示本体的例子。

    为了利用本体论,我们通过将嵌入的eᵢ与其父节点结合使用,学习出一个为节点cᵢ嵌入的网络gᵢ。为了进行预测,我们将本体知识G与当前访问的xt相乘,并通过神经网络进行传递。例如,它们可以是诊断预测任务或心力衰竭预测任务。利用RNN网络,该模型可以通过以往的访问信息进一步增强。

    以下是使用t-SNE对不同疾病的最终代表gᵢ的散点图。

    药物发现和合成化合物

    DNN可以训练成千上万的化学结构来编码和解码分子,还可以构建预测因子,根据潜在的表征来估计化学性质。例如,我们可以学习一个自编码器来编码一个分子的图形表示,然后用解码器重建分子。目的是学习一个潜在的表示,最大限度地减少重建损失。我们可以使用这个潜在表示来预测合成可及性和药物与另一个DNN(下面的绿色网络)的相似性。

    这些潜在的表达方式允许研究人员在潜在空间中通过扰乱已知的化学结构或插入分子之间的简单操作自动生成新的化学结构。

    这是麻省理工学院的另一个项目,将深度学习应用于图形对象,从而发现新的抗生素。

    Open Catalyst项目是利用人工智能发现用于可再生能源存储的新催化剂的另一个例子。

    推荐系统

    物体可以在视觉上相似,但实际上是完全不同的物体。例如,下面的第一行包含的对象与左侧的预期图像查询截然不同,尽管它们在视觉上是相似的。

    在Pinterest中,将pins连接在一起形成图。pinage是一个随机行走的GCN,它学习了Pinterest图形中的节点(图像)嵌入。由于图中包含数十亿个对象,在如此巨大的图中进行卷积是没有效率的。相反,Pinterest动态地构建这些图形。它根据访问次数使用加权抽样来模拟随机行走。这个过程构建动态的和更小的图和卷积之后被用于计算节点的嵌入。

    在Uber Eats上,它使用GraphSage来进行推荐。

    交通预测

    DCRNN融合了交通流的空间依赖性和时间依赖性,用于交通预测。道路上的传感器被建模为图中的节点。DCRNN利用图上的双向随机游动来捕获空间依赖关系,利用编解码器来捕获时间依赖关系。

    生成场景关系图

    给定一幅图像,我们可以生成描述图像中物体及其关系的场景图。

    下面的模型使用GRUs生成场景图,并通过消息传递学习迭代改进其预测。

    F-net使用自底向上的聚类方法将整个图分解成子图,每个子图包含几个对象及其关系的子集。采用分治方法,大大减少了中间阶段的计算量。

    反过来,我们可以根据场景图生成图像。

    引用这篇论文的内容:https://arxiv.org/pdf/1804.01622.pdf

    我们的模型使用图形卷积处理输入图形,通过预测包围框和分割掩码计算场景布局,并通过级联的细化网络将布局转换为图像。网络对抗的形式进行训练,以确保真实的输出。

    链接预测

    链路预测网络中的两个节点是否可能存在链路。在推荐系统中,我们推荐的是高度“连接”的产品。

    SEAL提取了一个围绕下面a和B的局部包围子图,省略了链接AB。然后,用GNN训练模型来预测这种链路是否存在。

    点云分类与分割

    像激光雷达这样的3D扫描仪会产生3D点云,一种带有坐标的3D空间中物体的表示,以及可能的颜色信息。

    下面是一个对点云进行分类和分割的模型。

    这是另一个使用RGB点云的3D对象分割的例子。

    这是生成3D分割的模型。

    人物交互

    GPNN用图形结构来解释一个给定的场景。例如,它用“舔”来标记人与刀之间的联系。

    文本分类

    我们可以应用GNN进行主题文本分类,包括新闻分类、Q&A、搜索结果组织等。

    在下面的模型中,它在原始文本上滑动一个三个单词的窗口,以创建单词图。这张图表示三个词范围内的词共现。然后,它根据每个节点的秩(节点的连接数)从图中选择节点。对于每个节点,它使用广度优先搜索查找包含该节点和另外四个节点的4个节点的子图。子图将是有序的,这样卷积可以一致地应用到所有子图。

    下面的图是从这些子图中进行标签预测的架构。

    序列标签

    句子中的单词可以被建模为图中的节点,我们可以计算每个节点的隐藏表示,并使用它来标记序列(序列中的单词的标签)。

    潜在的应用包括POS-tagging、NER(命名实体识别)和语义角色标签(SRL)。SRL给句子中的单词或短语贴上标签,表明它们的语义角色,如下图所示。

    因此,给定一个谓词(“disputed”这个词),下面的模型会识别并标记它的所有参数。

    NLP中的关系提取

    下面的图表表示了各种依赖关系,如线性上下文(相邻词)、句法依赖关系和语篇关系。

    这句话表明EGFR基因L858E突变的肿瘤对药物吉非替尼有反应。如果我们将三者定义为(药物、基因、突变),这些句子将表明三者(gefitinib、EGFR、L858E)具有“应答”关系。

    在下面的架构中,句子中的单词是用单词嵌入来编码的。然后,它使用一个图形LSTM来学习每个单词的上下文表示。接下来,我们将单词(gefitinib, EGFR, L858E)的上下文表示连接在一起。最后,我们使用一个关系分类器对这三个词的关系进行评分(分类)。因此关系式“Respond”(说成“R₄”)得分最高。

    姿态估计

    ST-GCN对其空间和时间邻居进行卷积,以估计输入视频的姿态。

    芯片设计

    在晶片设计中,标准晶片单元的放置和路线会影响晶片的功率、晶片模具尺寸和性能。谷歌证明了使用GNN和强化学习来优化单元的放置。

    芯片网表图(节点类型和图邻接信息)和当前放置的节点通过GNN进行输入状态编码。

    这些嵌入与嵌入的元数据(如电线的总数)相连接,并提供给一个神经网络。输出是一个学习的潜在表示,并作为输入的策略和损失进行强化学习。策略网络在当前节点所有可能的单元布局上产生一个概率分布。

    粒子物理

    在费米实验室,研究人员使用GNN来分析大型强子对撞机CMS探测器产生的图像,以识别粒子物理实验需要的有趣粒子。

    络。输出是一个学习的潜在表示,并作为输入的策略和损失进行强化学习。策略网络在当前节点所有可能的单元布局上产生一个概率分布。

    展开全文
  • 三、图神经网络应用 1、Structural Scenarios 主要应用于其数据结构为图结构的场景 ,如蛋白质分子结构图、KnowledgeGraph 等。以 KnowledgeGraph 中应用 GNN 为例:   相关论文:<IJCAI-17> Hamaguchi T, et al. ...

    640?wx_fmt=jpeg


    整理 | 耿玉霞,浙江大学直博生。研究方向:知识图谱,零样本学习,自然语言处理等。

    来源 | 开放知识图谱(公众号id:OpenKG-CN)

    责编 | Jane


    近日,清华刘知远老师组在 arXiv 上发表了一篇关于图神经网络的综述,本次论文浅尝在分享这篇论文的基础上,对图神经网络的相关方法及应用作一次梳理。


    640?wx_fmt=png


    一、前言


    图神经网络(GraphNeural Networks, GNNs),主要针对非欧几里得空间结构(图结构)的数据进行处理。具有以下特点:


    • 忽略节点的输入顺序;

    • 在计算过程中,节点的表示受其周围邻居节点的影响,而图本身连接不变;

    • 图结构的表示,使得可以进行基于图的推理。


    640?wx_fmt=png


    二、图神经网络模型


    通常,图神经网络由两个模块组成:传播模块(PropagationModule)和输出模块(Output Module),具体地:


    (1)Propagation Module:图中节点之间传递信息并更新状态;


    • aggregator: 对于一个节点v, 通过聚合其周围节点的信息,学习其潜在表示h_v (state embedding)。



    640?wx_fmt=png


    其中,x_v为节点v的features,x_co[v]为其周围边的features,h_ne[v]表示节点v周围邻居节点的state embedding,x_ne[v]表示周围节点的features。


    • updater: 更新节点的stateembedding。


    640?wx_fmt=png


    (2)Output Module:基于节点和边的向量表示根据不同的任务定义目标函数


    640?wx_fmt=png


    在监督学习场景中,对于一个特定的节点,其监督信号表示为:t_v,lossfunction定义为:


    640?wx_fmt=png 


    常见的图神经网络有:图卷积神经网络(GraphConvolutional Networks, GCNs),门控图神经网络(Gated Graph Neural Networks,GGNNs)以及基于Attention机制的GraphAttention Networks(GAT),下面详细介绍这三种网络:

    640?wx_fmt=png

     

    1、图卷积神经网络(GCN)


    (1)基于谱方法(Spectral Methods):

    相关论文:<ICLR-17> Kipf T N, Welling M.Semi-supervised classification with graph convolutional networks.


    640?wx_fmt=png


    通过计算图拉普拉斯算子(Graph Laplacian)的特征分解,在Fourier域定义卷积计算。对于输入信号x和卷积核?_?=????(?):


    640?wx_fmt=png


    其中,表示图结构的Graph Laplacian矩阵可分解为:


    640?wx_fmt=png


    上式的计算将卷积核近似为切比雪夫多项式,并进行化简:


    640?wx_fmt=png

    640?wx_fmt=png


    最终得到GCN网络中的表示:


    • aggregator:

    640?wx_fmt=png

    • updater:

    640?wx_fmt=png


    但是以上方法有几点不足,卷积核的学习依赖图拉普拉斯矩阵的特征分解,对于图结构有一定的要求,在固定结构上学习的模型,无法迁移到其他结构的模型上。

     

    (2)基于非谱方法(Non-spectral Methods):


    在图上直接定义卷积计算,将不同size的邻居节点考虑在内,同时保持像CNN一样的局部卷积不变性。


    • DCNNs:基于扩散卷积的思想的网络;

    • GraphSAGE:采样固定size的邻居节点,同时通过mean,LSTM, pooling等方式聚合周围节点的信息。


    640?wx_fmt=png


    2、门控图神经网络(GGNN)


    相关论文:<ICLR-16> Li Y, Tarlow D, Brockschmidt M,et al. Gated graph sequence neural networks.


    • 提高图结构信息的long-term传播能力

    • 将图中的edge信息考虑在内


    将图矩阵作如下表示,不同类型的边采用不同类型的传播矩阵,同时,用 A^(out)和 A^(in) 分别表示节点的入度信息和出度信息。


    640?wx_fmt=png     

    计算图传播信息:


    (1)Propagation module

    • initialization step

      640?wx_fmt=png


    • pass information:矩阵A中包含了当前节点与其他节点的交互信息




      640?wx_fmt=png


    节点的state embedding h_{v^(t-1)},与其他节点的交互信息a_{v^(t)}通过GRU单元进行融合:


    • update gate

      640?wx_fmt=png


    • reset gate

      640?wx_fmt=png


    • activate


    640?wx_fmt=png

    640?wx_fmt=png


    (2)Output module


    • node-level

      640?wx_fmt=png


    • graph-level

      640?wx_fmt=png


                其中,i,j表示两个全连接神经网络。

     

    3、注意力图神经网络(GAT)


    相关论文:<ICLR-18> Velickovic, Petar, et al. Graphattention networks.


    • 为节点的不同的邻居节点指定不同权重

    • 节点-邻居节点对的计算可并行化,相比于GCN等网络,速度较快


      640?wx_fmt=png


    节点权重的计算:


    640?wx_fmt=png

           

    节点信息的更新:

    640?wx_fmt=png


    由“Attentionis all you need”一文中提出的 head attention,GAT 网络中也使用了 headattention:


    640?wx_fmt=png

    640?wx_fmt=png

     

    三、图神经网络应用


    640?wx_fmt=png


    1、Structural Scenarios


    主要应用于其数据结构为图结构的场景,如蛋白质分子结构图、KnowledgeGraph 等。以 KnowledgeGraph 中应用 GNN 为例:

     

    相关论文:<IJCAI-17> Hamaguchi T, et al. Knowledgetransfer for out-of-knowledge-base entities: a graph neural network approach.


    论文主要针对 KG 中的 out-of-knowledge-base(OOKB) 实体,进行知识库补全等任务。


    a、OOKB实体定义:


    在训练过程中未被训练到的实体,无法得到其 embedding 表示,从而无法预测其与知识库中其他实体之间的关系。如下图中在测试期间新出现的实体“Blade-Runner”,或者说新出现的三元组“(Blade-Runner,based-on, Do-Androids-Dream-of-Electric-Sheep?)”(图中红线所示部分)。


    640?wx_fmt=png


    我们的任务则定义为:基于知识库中已存在的三元组(2)和当前新出现的三元组(1),预测当前新实体与知识库中其他实体之间的关系(即三元组3)。


    同时,OOKB 实体即哪些与知识库中已存在的实体直接相连的实体,基于此,可以通过知识库中现有的实体表示得到 OOKB 实体表示。

     

    b、这篇文章利用 GNN 中节点表示的方式,对 OOKB 实体进行表示:


    640?wx_fmt=png


    其中,T_head 表示以 OOKB 实体为尾实体的三元组集合,T_tail 表示以 OOKB 实体为头实体的三元组集合,通过其周围邻居的头尾实体对当前实体进行表示。


    T_head, T_tail 分别表示聚合三元组信息的函数,论文中为 batchnormalization function。


    经 GNN 传播的节点状态表示为:


    640?wx_fmt=png


    c、模型的输出模块利用 TransE 等经典模型,进行知识库补全任务。


    640?wx_fmt=png


    2、Non-structural Scenarios


    主要应用于其数据结构为非图结构的场景,如图片、文本等。在此类场景中,应用GNN通常有两种方式:


    • 利用具有图结构信息的外部资源,如 KnowledgeGraph 等;

    • 探索此类数据中隐含的图结构,如文本的句法数结构。

     

    (1)图片相关任务:

    • Image Classification, i.e., zero-shot, few-shot

    • Visual Reasoning, i.e., VQA

    • Semantic Segmentation


    其中,图片分类任务零样本学习和少样本学习的相关论文有:


    • Zero-shot recognition via semantic embeddings and knowledge graphs

    • Rethinking knowledge graph propagation for zero-shot learning

    • Multi-label zero-shot learning with structured knowledge graphs

    • The more you know: Using knowledge graphs forimage classification

    • Few-shot learning with graph neural networks


    (2)NLP相关任务:


    • Text Classification

    • Sequence Labeling

    • Neural machine translation

    • Relation Extraction

    • Event Extraction

     

    以机器翻译的一篇论文为例,通过将 sourcelanguage 的句法结构图输 GNN 进行 encode,继而附加 Attention layer 和 decoder 层,输出 target language 序列。

     

    相关论文:<ACL-18> Beck D, Haffari G, Cohn T.Graph-to-sequence learning using gated graph neural networks.

               

    这篇文章以“Graph tosequence”为要点,实验部分包括两个任务,其中一个是 AMR 图输出序列,另一个做 syntax-aware 的机器翻译任务。


    其中,AMR Graph 为从句子的句法表示中抽象出来的语义表示语言,具体相似语义的句子有相同的 AMR Graph。如下图左所示。


    640?wx_fmt=png


    模型在 Seq2seq 模型的基础上,以 AMR graph 为输入,通过 GGNN 网络进行 encode,经过 Attention 层和 RNNdecoder 输出序列。GGNN encoder 部分表示为:

    640?wx_fmt=png


    其中,640?wx_fmt=png 表示当前节点与周围节点相连边的参数,l_e 表示不同边的类型。


    但随着 Graph 中边类型的增多,很容易引起参数爆炸的问题,因此,本文提出了一种融合 Graph 中 edge 信息的方式,即将 edge 转化为附加的节点(no labelled edges)。具体地,通过将 Graph 转化为对应的二分图。上图中的句法结构图对应的二分图如下所示:


    640?wx_fmt=png


    由此,graph 中的边的类型只有一种。

     

    四、Open problems


    图神经网络目前虽被广泛利用,但存在不少问题亟待解决:


    (1)Shallowstructure:多层的图神经网络,可能会导致 over-smoothing的问题,如 GCN 等网络,一些论文中也尝试用 Skip connection 的方式加以解决;

    (2)Dynamicgraphs:GNN 目前仅能处理一些静态图,对于实时增加/减少的节点和边则无法很好地处理;

    (3)Non-structuralscenarios:在处理非图结构的数据时,希望利用其中内在的结构,而目前从 raw data 中生成 graph 的方法仍需改善;

    (4)Scalability

     

    五、总结


    本文中总结了近年来常用的几种图神经网络模型,并就其应用场景进行了进一步的探讨。总的来说,图神经网络强大的计算能力,对图结构数据的友好处理,深受研究者们的喜爱,但其仍存在很多需要解决的问题,也是我们可以进一步研究的方向。


    最后,送上这份值得大家收藏的论文地址

    论文链接:

    https://arxiv.org/pdf/1812.08434.pdf

    GNN相关论文列表链接:

    https://github.com/thunlp/GNNPapers

    原文链接:

    https://mp.weixin.qq.com/s/043sK8IDmdTYDpbCfPLIxw 


    (本文为AI科技大本营转载文章,转载请联系作者,禁止二次转载)



    推荐荐阅读:

                             640?wx_fmt=png

    ❤点击“阅读原文”,查看历史精彩文章。

    展开全文
  • 图神经网络综述

    万次阅读 2019-06-14 17:09:03
    图神经网络(GNN)热度持续上升,之前我们曾介绍了清华两篇综述论文,参见:深度学习时代的图模型,清华发文综述图网络,和清华大学图神经网络综述:模型与应用。最近,IEEE Fellow、Senior Memb...
  • 图神经网络GNN综述

    千次阅读 2019-06-11 16:29:34
    清华大学图神经网络综述:模型与应用题 引言:近年来,图神经网络的研究成为深度学习领域的热点,机器之心曾介绍过清华大学朱文武等人综述的图网络。近日,清华大学孙茂松组在 arXiv 上发布预印版综述文章 Graph ...
  • 异质图神经网络:模型与应用

    千次阅读 2020-02-17 12:41:32
    下面是作者0116在蚂蚁金服人工智能部的分享PPT,异质图神经网络:模型与应用,方便大家入门理解.作者目前在阿里搜索事业部做Research Intern,最近在做一些关于异质图神经网络...
  • 三、图神经网络应用 1 、 Structural Scenarios 主要应用于其数据结构为图结构的场景,如蛋白质分子结构图、 KnowledgeGraph 等。 以 KnowledgeGraph 中应用 GNN 为例:   相关论文: <IJCAI-17> Hamaguchi T, et ...
  • 本文将介绍基于图神经网络的知识图谱学习与计算以及基于图神经网络融合知识图谱信息的应用的研究进展。 1 知识图谱与图神经网络 近几年来,人工智能技术得到了飞速发展,其进展突出体现在以知识图谱(Knowledge ...
  • 知识图谱提供了现实世界的事实知识,利用图神经网络模型尤其是概率图神经网络应用在知识图谱中实现逻辑推理,从而显式地生成基于知识图谱的推理路径,或许可以期待打开深度学习的黑盒。 部分参考文献 [1] Lin B Y, ...
  • 摘要:本文我们将主要介绍各种典型的图神经网络的网络架构和训练方法。 本文我们将主要介绍各种典型的图神经网络的网络架构和训练方法。...在图神经网的实际应用中,卷积图神经网络的使用最为广泛,因此,本
  • 从图嵌入算法到图神经网络

    千次阅读 多人点赞 2019-08-13 15:12:25
    图神经网络,广泛应用于社交关系、知识图谱、推荐系统、蛋白质分子建模,同样源自于对传统领域的创新,它的前身是图嵌入算法;而图嵌入算法又以图数据作为载体。这一关系,将贯穿本文始末,成为我们
  • 31页PPT概述:图神经网络表达能力有多强?

    千次阅读 热门讨论 2019-02-18 15:04:33
    整理 | 一一出品 | AI科技大本营近年来,图神经网络的研究成为深度学习领域的热点。图是一种数据结构,它对一组对象(节点)及其关系(边)进行建模,由于图结构的强大表现力...
  • 卷积神经网络5:卷积的应用

    千次阅读 2020-12-06 12:56:04
    备注:本篇博客摘自某培训机构上的图神经网络讲解的视频内容,该视频关于图神经网络入门讲解、经典算法的引入和优缺点的介绍比较详细,逻辑主线也比较清晰。因此记录分享下。 前几篇介绍了谱域图卷积及空域图卷积:...
  • 在本次talk中,我们将探索图神经网络(Graph Neural Networks)在分子图(Molecular Graph)建模中的应用。具体来说,我们将介绍我们开源的一个全新的分子数据库(alchemy.tencent.com)用以评估图神经网络的性能,...
  • 算法在反欺诈中的应用

    千次阅读 2020-12-14 10:43:38
    是表示事物之间关联关系的有效方式,包括节点和边。节点是一种实体,可以是账号,也可以是设备、手机号等,而边表示这些节点之间的关联关系,比如某个账号使用过某台设备,就可以在对应的账号和设备节点之间建立一...
  • 【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks 文章转载于好我的朋友:大家可以关注他的博客: Memory逆光 博客地址:...
  • 图神经网络,这到底是个什么?

    千次阅读 2021-03-01 14:27:54
    摘要:图神经网络是一种基于图结构的深度学习方法。 1、什么是图神经网络 图神经网络(Graph Neu做ral Networks, GNNs)是一种基于图结构的深度学习方法,从其定义中可以看出图神经网络主要由两部分组成,即“图”...
  • 卷积神经网络架构

    万次阅读 多人点赞 2018-11-20 17:14:48
    卷积神经网络(conv)架构 卷积神经网络在图像分类数据集上有非常突出的表现,...卷积神经网络图: 共同点: 中每一个节点都代表一个神经元,没相邻两层之间的节点都有边相;输入输出的流程基本一致。 不同...
  • 图神经网络笔记(一)

    千次阅读 多人点赞 2019-03-07 20:00:10
    图神经网络(GNN)是一类基于深度学习的处理图域信息的方法。由于其较好的性能和可解释性,GNN 最近已成为一种广泛应用的图分析方法。 为什么有图卷积神经网络 本质上说,世界上所有的数据都是拓扑结构,也就是...
  • 图神经网络 | (1) 一文读懂图卷积GCN

    千次阅读 2020-02-01 12:22:51
    1. 图网络的分类 2. 卷积 3. 卷积 4. 卷积的通式 5. 参考文献 1. 图网络的分类 在最开始,我们先梳理一下经常被提到的几个术语的区别和联系,也就是Graph Embedding,Graph Neural Network和Graph ...
  • 一、什么是图神经网络? 在过去的几年中,神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务,如目标检测、机器翻译和语音识别,曾经严重依赖手工的特征工程来提取信息特征集,最近被各种端到端的...
  • 图神经网络综述】一文道尽GNN原理、框架和应用

    千次阅读 多人点赞 2020-08-05 00:06:03
    【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks1. 摘要:2. 简介:2.1 为什么要用图表示数据:2.2 GNN与network embedding:2.3 GNN与Graph Kernel:2.4 一些符号表示: 论文地址:...
  • 从数据结构到算法:图网络方法初探 论文《Graph Neural Networks: A Review of Methods and Applications》 木牛马论文阅读笔记... 文章目录图神经网络(Graph Neural Networks,GNN)1. GNN起源1.1 动..
  • 什么是图神经网络

    万次阅读 2020-08-05 10:25:32
    2019年可以说是图神经网络元年。01 什么是图神经网络?1. 图和属性图要了解图神经网络,首先要了解图。图是由节点和边组成的,如下图所示。一般图中的节点表示实体对象(比如一个用户、一件商品、一辆车、一张银行卡...
  • 点击蓝字关注我们AI TIME欢迎每一位AI爱好者的加入!药物间相互作用(DDI)预测是药理学和临床应用中一个具有挑战性的问题,在临床试验期间,有效识别潜在的DDI对患者和社会至关重要。现...
  • 可解释图神经网络:5个GNN解释方法

    千次阅读 2021-06-17 08:58:17
    由于图结构的不规则性,现有的解释方法难以适用于图神经网络。 Explainability增加可靠性 最近,人工智能中的可解释性引起了人们的广泛关注,其主要动机在于通过深度神经网络等“黑盒子”模型产生更可靠和可信的预测...
  • 今天介绍两篇在计算机视觉领域应用图神经网络的论文,这两篇论文选自CVPR2020,都可以在arxiv上找到对应的原文。第一篇论文题目为Object Re...
  • 一些研究已经发展出将ML/DL应用于社交网络、社区分类、脑网络分析等网络任务的方法。在这些任务中,数据由G(V,E)表示,其中V是节点的集合,E是边的集合:节点表示数据点,边表示节点之间的连接。数据集上的ML/DL...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 171,819
精华内容 68,727
关键字:

图神经网络的应用