Graph Neural Networks and its applications

摘要

以图形形式构建的数据存在于生物化学、图像处理、推荐系统和社会网络分析等多个领域。利用预处理技术在图结构数据上训练机器学习模型有几种方法，但它们缺乏完全适应数据集和手头任务的灵活性。图神经网络允许创建一个端到端的机器学习模型，该模型同时被训练来学习图结构数据的表示并在其上拟合预测模型。图神经网络可以应用于从聚类或可视化到对图数据进行分类或回归的任务，它们还可以在节点或图级别学习表示。他们在半监督学习和有监督图分类方面取得了最新的成果。半监督学习是指当一个图包含一些带标签的节点，并将它们的标签扩展到图的其余节点，例如对Reddit帖子进行分类。有监督图分类或回归用于预测整个图或子图的某些属性的类或值。这项工作将探索一些最突出的图神经网络变体，并将其应用于两项任务：近似社区检测Girvan-Newman算法和编译代码段分类。

引言

数据结构如图存在于许多领域，如生物学、化学、图像处理、推荐系统和社会网络分析等等。由于图数据的高维性和非欧几里德特性，在机器学习模型中使用这些数据是困难的。多年来，通过对图结构数据进行总结或以简化的方式表示信息来训练机器学习模型的方法已经被使用。然而，这些方法被用作预处理步骤，而不是训练过程的一部分。图神经网络是一种最新的技术，它可以创建一个端到端的机器学习模型，同时训练它来学习图结构数据的表示并在其上拟合预测模型。

图神经网络[1]通过在低维空间中嵌入图节点来学习图的表示。端到端的训练允许学习这种表示法，以反映当前问题感兴趣的图的结构属性。将节点表示为嵌入，通过从每个节点的邻居处聚合信息以迭代方式创建。这个过程的计算成本很高，因此现代实现通过限制迭代次数或使用采样技术来提高速度。这种节点嵌入表示可以用于下游机器学习，也可以在嵌入的同时进行训练。当任务需要在节点级进行分类或进行回归时，直接使用嵌入中每个节点的表示。当任务需要在图或子图级别对值进行分类或预测时，可以使用池技术来获得图或子图级别的表示。
图神经网络最显著的改进版本将卷积神经网络的思想应用于图，因此被称为图卷积网络[2]。它们可以分为两大类，基于谱的方法和基于空间的方法。基于谱的方法依赖于图的邻接矩阵的特征分解，这使得它们不太适合处理大数据或泛化为不可见的数据。另一方面，基于空间的方法依赖于每个节点邻域的信息聚合，使得算法能够成批地处理图，从而能够处理大的图。

在大图的半监督学习中，只有一小部分节点具有标签或目标值，其余的节点没有标记，已经获得了最新的性能。该任务包括为其余未标记的节点分配标签（[2]，[3]）。蛋白质分析中的图分类和回归任务也有了突破[4]。这也是科学界对这一领域越来越感兴趣的原因之一，自2016年以来，出版物大幅增加。

近年来，关于图神经网络在生物化学、计算机视觉、推荐系统、组合优化、流量优化、归纳逻辑和程序验证等领域的应用已经出现。图神经网络解决的主要任务可概括为节点（图）分类、节点（图）回归、链路预测、节点聚类、图划分和图形可视化。

本硕士论文的目标是将图神经网络模型应用于不同的问题，以创造一个新的解决方案。其目的是了解图神经网络在每种情况下是如何使用的。研究了两个问题：Girvan-Newmann算法逼近和编译码函数分类。它们对应于图神经网络成功完成的两个主要任务：图上节点的半监督学习和有监督图的分类。

图神经网络是解决图相关问题的一种很有前途的方法，在许多领域有着广泛的应用。现在似乎是时候开始学习最新的模型了，因为它们在一些已经解决的任务上取得了最先进的性能。

论文的组织结构如下：下一节将介绍图神经网络模型的主要模型、内部结构以及它们所解决的问题。然后，在第三部分，介绍了实验所遵循的方法。之后，第四节将对实验的实施进行概述，而在第五节中总结实验结果。最后，在第六部分给出了本文的结论。

内容

目前技术水平
这一部分是几个来源的汇编，这些来源调查了最新的图形神经网络的进展，并给出了关于其内部的详细信息。部分文本摘自以下研究论文和调查：

• Hamilton等人，图的表示学习：方法和应用[5]

• Xu等人，图神经网络有多强大？[6]

• Wu等，图神经网络综合研究[7]

• Kipf等人，用图卷积网络进行半监督分类[2]

• Li等人，门控图序列神经网络[8]

许多数据可以用图形表示，这是一种数据结构，常用于生物化学、社交网络、推荐系统甚至计算机程序分析等领域。许多机器学习应用程序都是使用图结构数据来进行预测的。将图结构数据中的信息合并为机器学习模型的输入并不简单。图结构数据是高维和非欧几里德的，这是创建一个统一和通用的方法来使用它作为模型输入的主要障碍。图数据是不规则的，具有可变大小和可变邻域数。有许多方法可以通过使用摘要图统计、内核函数或手工工程特性将图形数据转换为机器学习模型的可用特征。这些方法在学习过程中缺乏适应性。

图神经网络的思想是学习一个映射，将节点或整个子图嵌入到低维向量空间$R^d$中，目标是优化映射，使嵌入空间中的几何关系反映原始图的结构。以前的图形学习方法使用这种方法作为预处理步骤，使用固定和/或手工设计的参数。图神经网络将这种表示学习任务视为机器学习任务，使用数据驱动方法学习编码所需图结构的嵌入。
本节将介绍图神经网络的主要进展，展示节点和整个子图的表示技术。

1.概念

图的定义：图定义为G=（V，E，A），其中V是节点集，E是边集，A是邻接矩阵。
图可以与节点属性X相关联，其中$X\in R^{N\times D}$是一个特征矩阵，$X_i\in R^D$代表节点的特征向量。

图结构数据被认为是非欧式的。在由图本身定义的空间中，表示节点的向量的范数没有一个明确的定义。因此，两个节点之间的距离必须根据其他一些标准来定义。通常，两个节点之间的距离计算为源节点和目标节点之间沿边的最短路径中存在的节点数。此外，基于节点属性计算的节点间相似度不需要符合节点距离（如前一句所定义）。

2.原始模型

图神经网络的概念首先由Gori等人（2005）[9]提出，然后由Scarselli等人发展。（2009年）[1]。在[5]和[6]中解释了图神经网络训练过程的良好和一般性定义。以下段落对它们进行了总结。

图神经网络：GNNs利用图结构和节点特征Xv为v∈V学习一个节点hv或整个图hG的表示向量。现代GNN遵循邻域聚合策略，通过聚合相邻节点的表示来迭代更新节点的表示。经过k次聚合迭代后，节点的表示将捕获其k跳网络邻域内的结构信息。形式上，GNN的第k层是：

其中$h_v^{(k)}$是第k次迭代/层节点v的特征向量。初始化包含$h_v^{(0)}=X_v$和N（v），其是与v相邻的一组节点。迭代聚合过程是计算密集型的。现代实现试图加速这种收敛过程，例如通过限制迭代次数或使用随机游动来处理邻域。为了保证收敛性，递归函数（组合和聚合的组合）必须是收缩映射。收缩映射缩小映射后两点之间的距离。GNN使用Almeida-Pineda算法[10]训练模型。其核心思想是运行传播过程以达到收敛点，然后在给定收敛解的情况下执行反向过程。

有两种类型的任务使用GNNs：节点分类/回归和图分类/回归。节点分类或回归是指当每个节点v∈V有一个相关的标签或目标值$y_v$，目标是学习v的一个表示向量$hv$，使得v的标签或目标值可以预测为$y_v=f（h_v）$。图分类或回归是当给定一组图{G1，…，GN}及其标签或目标值{y1，…，yN}时，目标是学习一个表示向量$h_G$，它有助于预测整个图的标号或目标值$y_G=f（h_G）$。

对于节点分类/回归，使用最终迭代的节点表示进行预测。对于图分类/回归，读出函数从最终迭代中聚合节点特征，以获得整个图的表示hG：

READOUT函数可以是简单的置换不变函数，例如求和，也可以是更复杂的图形级合并函数。

AGGREGATE（k）（·）和COMBINE（k）（·）的选择至关重要。 在下一部分中，将说明该模型的主要演变。 主要思想是对这些最新模型使用了AGGREGATE（k）（·）和COMBINE（k）（·）的哪些选择。

3.高级模型

早期的模型试图通过迭代传播邻居信息来学习节点的表示，直到所有节点都达到收敛。这个过程是计算密集型的，所以最近有一些出版物试图降低这个过程的成本。大量的方法将计算机视觉领域中卷积网络的特性应用于图形数据。它们被称为图卷积网络（GCN）。

图形卷积网络：
Bruna等人（2013）[11]提出了第一个GCN模型，该模型基于谱图论开发了一种图形卷积的变体。关于基于谱的图卷积网络，还有其他一些出版物[12]。谱方法从图形信号处理的角度引入滤波器来定义图形卷积，其中图形卷积运算被解释为从图形信号中去除噪声。他们依靠拉普拉斯矩阵的特征分解。这样做的缺点是，图的任何改动都会导致特征根的变化，并且所学习的滤波器是与域相关的，因此它们不能应用于具有不同结构的图。

另一种卷积方法是基于空间的卷积网络，请参见[3]和[13]。他们根据节点的空间关系定义图卷积。这些方法通过聚集邻居节点信息直接在图域中执行卷积。基于空间的图卷积采用节点及其邻居的聚合来为其获取新的表示形式。一种常见的做法是将多个图卷积层堆叠在一起。

在可扩展性和并行化方面，频谱方法的成本随图形的大小呈指数增长，但它需要整个图形存储在内存中。因此，这些方法不适用于大规模数据或并行化体系结构。但是，空间方法通过聚集邻居属性在图域中执行卷积，因此它们可以处理大型图。可以对一批节点而不是整个图执行计算。当邻居的数量变得过多时，也可以使用采样技术。

在模型的泛化方面，基于频谱的模型假定固定的图，并且不善于泛化为未知的图。空间方法没有此约束，因为它们的卷积是在本地执行的，并且卷积中使用的权重可以在不同位置之间共享。

最后，谱方法仅限于在无向图上使用，而空间方法可以通过修改聚合函数来处理多源输入和有向图。与基于谱的模型相比，基于空间的模型在科学界引起了更多的关注。

让我们看看基于空间的图卷积网络如何实现将迭代生成节点表示形式的算法。该算法取决于权重（也称为系数），稍后将使用随机梯度下降或等效算法进行更新。这些更新机制允许训练一个端到端模型，该模型包含图形生成（嵌入）的表示形式以及将使用嵌入作为其分类或回归任务输入的后续层。

上一小节显示，可以将节点状态（其属性值）的更新形式化为节点状态和邻居节点状态聚合的函数：

其中W（k）是第l个神经网络层的权重矩阵，而σ（∆）是类似于ReLU的非线性激活函数。 必须对邻接矩阵A施加一些其他约束。首先，必须将其添加到标识I中，以便创建自循环并允许在更新中对节点属性进行计数。 其次，必须将A标准化。

此功能正在图上实现Weisfeiler-Lehman算法，该算法用于检测同构。 它为每个节点分配一组唯一的功能，以唯一地描述其在图中的角色。 其工作方式如下：
对于所有节点$v_i\in G$：

•获取相邻节点{$v_j$}的特征{$h_{v_j}$}

•更新节点特征$h_{v_i}$= hash（$P_j{h}_{v_j}$），其中hash（·）是注入式哈希函数。

•重复k步直到收敛。

这种想法的变体符合本小节中所介绍的更高级的Graph神经网络模型的基础，即Graph卷积网络及其变体，例如GraphSage或称为GIN的Graph同构网络。
图卷积网络模型使用在图的所有位置上共享的过滤器参数W（k）：

其中j索引vi的相邻节点，而cij是边（vi，vj）的归一化常数。 此版本是原始Weisfeiler-Legman算法中使用的哈希函数的可微化和参数化变体。 通过适当的初始化（Glorot），此更新规则是稳定的。

当训练模型对整个图或子图执行分类时，必须使用图池化模块。 使用池化模块的GCN在区分图形结构方面与Weisfeiler-Legman测试一样强大。 与CNN的池化层相似，图池化模块可以通过在卷积层之间进行下采样来轻松减少方差和计算复杂度。 平均，最大和总和池是实现它们的最常见方法。

本小节的其余部分将介绍最众所周知的GCN模型的演变过程。

消息传递神经网络（MPNN）：MPNN模型将几个现有的图形卷积网络概括为一个称为消息传递神经网络的统一框架。 它包括两个阶段，消息传递阶段和读取阶段。 消息传递阶段实际上运行T步基于空间的图卷积。 图卷积运算通过消息函数Mt（·）和更新函数Ut（·）根据

读出阶段实际上是一个池操作，该池操作基于每个单独节点的隐藏表示来生成整个图的表示。 定义为

通过输出函数R（·），最终表示y’用于执行图级预测任务。作者[14]指出，通过假设Ut（·）和Mt（∆）的不同形式，其他一些图卷积网络也属于它们的框架。

GraphSage：在[3]中引入了聚合函数的概念来定义图卷积。 聚合功能本质上是集合节点的邻居信息。 它必须是不变的节点顺序的排列，例如均值，总和和最大值。 图卷积运算定义为

GraphSave没有更新所有节点的状态，而是提出了一种批量训练算法，提高了大型图的可伸缩性。图形的学习过程包括三个步骤。首先，以固定大小的节点局部k-hop邻域作为样本。第二个节点通过聚合其中心节点的信息来获取其最终状态。最后，它使用中心节点的最终状态来进行预测和反向传播错误。假设第t跳处要采样的邻居数为st，则一批中GraphSage的时间复杂度为A。因此，计算成本随着t的增加呈指数级增加，这使得GraphSage无法拥有深层架构。然而，在实践中，作者发现t=2的GraphSage已经获得了很高的性能。

门控图神经网络（GGNN）：也称为GGNN，这种GNN采用门控递归单元（GRU）[15]作为递归函数，将递归减少到固定的步骤数。 GGNN的空间图卷积定义为

为了更新权重，GGNN使用时间反向传播（BPTT）来学习参数。 优点是它不再需要约束参数以确保收敛。 但是，BPTT训练的缺点是牺牲了时间和记忆效率。 对于大型图而言，这尤其成问题，因为GGNN需要在所有节点上多次运行递归函数，从而需要将所有节点的中间状态存储在内存中。

GGN的其他类型是图注意网络，图自动编码器，图生成网络和图时空网络。

图注意力网络类似于GCN，并寻求一种聚合函数来融合图中的相邻节点，随机游走和候选模型，以学习新的表示形式。 关键区别在于图注意力网络采用注意力机制，该机制将更大的权重分配给更重要的节点，walks或模型。 注意力权重与端到端框架内的神经网络参数一起学习。

图自动编码器是一种无监督的学习框架，其目的是通过编码器学习低维的节点向量，然后通过解码器重建图形数据。图自动编码是学习图嵌入的一种常用方法，对于没有属性信息的平面图和属性图都是如此。对于平面图，许多算法直接对邻接矩阵进行预处理，要么构造一个具有丰富信息的新矩阵（即逐点互信息矩阵），要么将邻接矩阵输入到自动编码器模型中，同时捕获一阶和二阶信息。对于属性图，图自动编码器模型倾向于使用GCN作为编码器的构建块，并通过链路预测解码器重建结构信息。

图生成网络旨在从数据中生成合理的结构。从根本上讲，生成给定图经验分布的图是一个挑战，主要是因为图是复杂的数据结构。为了解决这一问题，研究者们探索将生成过程分解为节点和边的交替形成，采用生成性对抗训练。图生成网络的一个很有前途的应用领域是化合物合成。在化学图中，原子被视为节点，化学键被视为边。其任务是发现具有一定化学和物理性质的新的可合成分子。

图时空网络的目的是从时空图中学习不可见的模式，在交通预测、人类活动预测等许多应用中发挥着越来越重要的作用。例如，底层道路交通网络是一个自然图，其中每个关键位置都是一个节点，其交通数据被连续监控。通过建立有效的图时空网络模型，可以准确地预测整个交通系统的交通状况。图时空网络的核心思想是同时考虑空间依赖和时间依赖。目前的许多方法都是用gcn来捕获依赖关系，同时使用一些RNN或CNN来对时间依赖进行建模。

4.图神经网络的替代方案

图神经网络的替代品早在出现之前就存在了：摘要图统计、核函数和网络嵌入（矩阵分解和随机游走）。

摘要统计旨在捕捉整个图的非常具体的特征，希望它们能使模型能够区分或预测值。最常见的是平均节点度、聚类系数和分类度。它们通常缺乏很多表示灵活性，并且无法正确捕获那些摘要统计信息没有反映的图结构的各个方面

核函数允许从图结构中捕获更多的信号，然后可以用来构建强大的分类或回归算法。它们也被用于无监督的学习方法中。内核的缺点是，它们不适合于大规模的图，因为它们需要在内存中保存整个图。

网络嵌入的目的是通过保留网络拓扑结构和节点内容信息，在低维向量空间中表示网络顶点。这种嵌入可以用于任何下游的浅层机器学习算法，例如分类、回归或聚类，就像GGN的输出一样。许多网络嵌入算法都是典型的无监督算法，它们可以大致分为三类：矩阵分解[16]、随机游动[17]和深度学习方法。

5.图神经网络的应用

最后，本节介绍了图神经网络及其变体的最重要应用。几个特定领域的应用程序都属于以下机器学习任务列表，GNN对这些任务显示出良好的效果：

•节点分类/回归

•图形分类/回归

•图形生成

•图形可视化

•节点群集

•链路预测

计算机视觉：在这一领域，研究了场景图的生成、点云的分类和分割以及动作识别。在场景图生成中，对象之间的语义关系有助于理解视觉场景背后的语义。给定一幅图像，场景图生成模型检测和识别对象，并预测对象对之间的语义关系[18]。在点云分类与分割中，[19]的任务是通过图卷积网络来确定点云所描绘的对象的拓扑结构。在动作识别中，在图像（或视频）中识别出的人的关节被检测出来，他们之间的连接形成一个图，可以用时空神经网络对人的行为进行分类。

推荐系统：基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系，基于图形的推荐系统能够产生高质量的推荐。推荐系统的关键是给用户打分。因此，它可以归结为一个链路预测问题。目标是预测用户和项目之间缺少的链接（[20]，[21]，[22]）。
生物化学：用图神经网络对分子结构进行分类。节点代表原子，边代表化学键。节点分类、图形分类和图形生成是三个主要任务。例如学习分子指纹[23]、预测分子性质[14]和合成化合物[24]

通信网络建模：通信网络依靠路由和路径优化来保证良好的服务水平。目前，网络运营商缺乏有效的网络模型，能够以有限的成本准确预测相关的端到端关键性能指标（KPI），如延迟或抖动。分析模型和数据包级模拟已用于生成KPI，但成本较高。图神经网络模型RouteNet[25]被提出作为一个有效的解决方案，产生延迟和抖动的估计精度与包级网络模拟器类似。

程序验证：是图神经网络显示其潜力的另一个富有成果的领域（[8]，[26]和[27]）。指令遵循一系列的执行顺序，包括循环、分支和对其他指令的调用。这种代码建模允许验证变量的正确使用（在释放内存缓冲区后避免使用）、变量名猜测和函数重命名，以正确理解代码功能。门控图序列神经网络[8]被称为GGNN，是利用门控递归单元和现代优化技术输出序列的图神经网络。当问题是图结构时，它们相对于纯粹基于序列的模型（如LSTMs）具有良好的归纳偏差。它们在应用于内存安全的程序验证方面实现了最先进的性能，将存储器的状态映射为一组输入图，并将其映射为数据结构的逻辑描述。例如，这可以用来验证程序中没有空指针取消引用。在[26]中，作者使用图来表示代码的语法和语义结构，并使用基于图的深度学习方法来学习对程序结构进行推理。他们将GGNN的修改版本应用于VarNaming（根据变量的用法预测变量的名称）和varususage（在给定的程序位置选择正确变量的原因）。最后，在[27]中给出了一种预测整个函数或子例程名称的方法，其中没有使用图神经网络方法，而是从抽象语法树生成嵌入。它用于代码片段预测语义属性。我们相信，图神经网络有很大的潜力来实现最先进的性能。

社交网络分析：随着网络的迅速扩张，社交网络作为人们与人交往的主要方式之一，在过去的几年里被大量采用。图神经网络在社会网络分析中有许多直接的应用，如朋友或链接预测[28]、社区检测[2]等，如[5]和[29]所示。社会网络分析的主要任务之一是发现社区的过程，称为社区检测。Girvan-Newman算法[30]是一种基于聚类的社区检测方法，被认为是最强大的算法之一。提出了一种基于边介度的无向边图和未加权图的划分算法。该算法以最“介于”社区和社区之间的边缘为中心，通过将这些边缘从原始边缘中移除，逐步构建出社区和社区之间的边缘图表。那个边介度算法时间复杂度的最坏情况是O（m2n），稀疏图的时间复杂度是O（n3），m是边的个数，n是顶点的个数，它的缺点是非常耗时，不适合应用于现代社交网络。如[31]所述，许多作者致力于改进它，降低计算复杂性或从中提取有用的概念（见[32]和[33]，[34]，[35]）。