详解图神经网络：方法与应用（一）
本篇文章来自小编：IDPT-大脸猫前言
机器学习中大量的任务都需要处理包含元素间丰富关系信息的图数据。
建模物理系统、学习分子指纹、预测蛋白质界面和疾病分类都需要一个模型来从输入的图形中学习得到其潜在信息。在从文本和图像等非结构化数据中学习的其他领域中，基于提取的结构(如句子的依赖树和图像的场景图)进行推理是一个重要的研究课题，同样需要图推理模型。图神经网络(GNN)是一种神经模型，通过图节点之间的消息传递来捕获图的依赖性。近年来，各种类型的GNN，如图卷积网络(GCN)、图注意网络(GAT)、图循环网络(GRN)在许多深度学习任务中都表现出了突破性的性能。
图神经网络起源
设计GNN的动机源于神经网络用于图的悠久历史。在90年代，递归神经网络RNN首次被用于有向无环图(Sperduti and Starita, 1997; Frasconi et al., 1998)。之后，(Scarselli et al.， 2009)和(Micheli, 2009)分别引入了递归神经网络RNN和前馈神经网络FNN来处理周期数据。尽管这些方法很成功，但其背后的普遍思想是在图上构建状态转换系统并迭代直到收敛，这限制了可扩展性和表示能力。深度神经网络，特别是卷积神经网络(CNNs) (LeCun et al.，1998)的最新进展使得GNN的价值再次被挖掘出来。CNN能够提取多尺度的局部空间特征并构建高度表达的表征，这使得几乎所有的机器学习领域都有了突破，开启了深度学习的新时代(LeCun et al.， 2015)。CNN的关键要素是局部链接、共享权重和多层堆叠(LeCun et al.， 2015)。这些在解决图的问题上也是很重要的。然而，CNN只能操作常规的欧式数据，如图像(2D网格)和文本(1D序列)，而这些数据结构可以视为图形实例。
左图为欧式空间图(image)，右图为非欧式空间图(graph)
图神经网络发展史
图是一种对一组对象(节点)及其关系(边)进行建模的数据结构。近来，研究使用机器学习分析图形越来越受到关注。图的强大表达能力使得图可以应用于许多system，包括社会科学在内的各个领域(social networks (Wu et al., 2020)，自然科学(physical systems (Sanchez et al., 2018; Battaglia et al.,2016) 和蛋白质-蛋白质相互作用网络 (Fout et al., 2017)，知识图谱(Hamaguchi et al., 2017)和许多其他研究领域(Hamaguchi et al., 2017)。作为一种独特的用于机器学习的非欧式数据结构，图分析侧重于节点分类等任务，链接预测和聚类。图神经网络 (GNN) 是在图域上运行的基于深度学习的方法，而近几年，卷积图神经网络、循环图神经网络、图自编码器以及 空间-时间图神经网络相继被提出。
GNN应用场景
图神经网络设计思想
下面，我们分析一下图神经网络设计的普适性流程。一般而言，设计流程分为4步：
[*]分析图的结构
[*]确定图的类型和规模
[*]设计损失函数
[*]构建图模型
分析图的结构
首先，我们必须找出一个系统中的图结构。通常有两种场景: 结构化场景和非结构化场景。在结构化场景中，图形结构在应用中是显式的，如分子应用、物理系统应用、知识图等。在非结构化场景中，图是隐式的，因此我们必须首先从任务中构建图，例如为文本构建一个完全连接的“单词”图 或是 为图像构建一个场景图。在我们得到图之后，后面的设计过程试图在这个特定的图上找到一个最优的GNN模型。
确定图的类型和规模
在归纳出图结构后，我们必须找出图的类型及其规模。 具有复杂类型的图形可以提供有关节点及其连接的更多信息。 图通常分为以下几类：
[*]有向/无向图： 有向图中的边都是从一个节点指向另一个节点的，这比无向图提供了更多的信息。 无向图中的每条边也可以视为两条有向边。
[*]同构/异构图： 同构图中的节点和边具有相同的类型，而异构图中的节点和边具有不同的类型。 节点和边的类型在异构图中起着重要作用，应进一步考虑。
[*]静态/动态图：当输入特征或图的拓扑随时间变化时，该图被视为动态图。 在动态图中应该仔细考虑时间信息。
以上这些类别是正交的，这意味着我们可以组合这些类型，例如 可以处理动态有向异构图。 还有其他几种图类型专为不同的任务而设计，例如超图(hypergraphs)和有符号图(signed graphs)。 我们不会在这里列举所有类型，但最重要的想法是考虑这些图提供的附加信息。 一旦我们确定了图类型，在设计过程中应该进一步考虑这些图类型提供的附加信息。
至于图的规模，“小”和“大”图没有明确的分类标准。 随着硬件的发展（例如 GPU 的速度和内存），该标准仍在变化。 一般地，我们认为当设备无法存储和处理图的邻接矩阵或图拉普拉斯算子（空间复杂度为 https://www.zhihu.com/equation?tex=O%28n%5E2%29 ）时，我们将该图视为大规模图，随之带来的便是我们需要考虑一些采样方法。
设计损失函数
图学习任务和一般的深度学习任务一样，我们需要根据任务类型和数据以及训练过程中总结得到的经验知识来设计损失函数。对于图学习任务而言，通常有以下三种任务：
[*]节点级(Node-level)任务 侧重于节点，包括节点分类、节点回归、节点聚类等。节点分类试图将节点分为若干类，节点回归预测每个节点的连续值。 节点聚类旨在将节点划分为几个不相交的组，其中相似的节点应该在同一组中。
[*]边级任务(Edge-level) 是边分类和链接预测，这需要模型对边类型进行分类或预测两个给定节点之间是否存在边。
[*]图级(Graph-level)任务 包括图分类、图回归和图匹配，所有这些都需要模型来学习图表示。
从监督或者说training settings这个角度来看，我们还可以将图学习任务分为三种不同的训练任务：
监督学习为训练提供标记数据。
半监督学习给出少量标记节点和大量未标记节点用于训练。 在测试阶段，半监督学习需要模型预测给定的未标记节点的标签，而 inductive bias提供来自相同分布的新的未标记节点进行推断。 大多数节点和边缘分类任务都是半监督的。 Wang and Leskovec(2020) and Rossi et al(2018) 采用了混合半监督-归纳方案。
无监督学习只为模型提供未标记的数据来寻找模式。 节点聚类是典型的无监督学习任务。
通过任务类型和training settings，我们可以为任务设计一个特定的损失函数。例如，对于节点级半监督分类任务，交叉熵损失可用于训练集中已被标记的节点。
构建图模型
传播模块：前向传播模块用于在节点之间传播信息，以便聚合信息可以捕获特征和拓扑信息。 在传播模块中，卷积算子和循环算子通常用于聚合来自邻域的信息，而skip connection操作用于从节点的历史表示中收集信息并缓解过度平滑问题。
采样模块：当图很大时，通常需要采样模块对图进行传播。 采样模块通常与传播模块结合使用。
池化模块：当我们需要high-level subgraph或图的表示时，需要池化模块从节点中提取信息。
GNN模型设计流程
我们通常通过组合它们来构建典型的 GNN 模型， GNN 模型的典型架构如上图中间部分所示，其中使用卷积算子、循环算子、采样模块和skip connection在每一层传播信息，然后加入池化模块提取深层信息。这些层通常堆叠在一起以获得更好的表示。值得注意的是，此架构可以泛化大多数 GNN 模型，但也有例外，例如，NDCN（Zang 和 Wang，2020）结合了常微分方程系统 (ODE) 和 GNN，它可以看作是一个连续时间 GNN 模型，它在连续时间上集成了 GNN 层，而不需要通过离散数量的层进行传播。
计算模块实例
本节中，我们将阐述上文提到的三种模块（传播、采样、池化模块）的实例。对于传播模块，其主要包括卷积算子、循环算子和skip connection。
下图为GNN计算模块的概览图。
GNN计算模块
卷积算子(convolution operator)
我们在本节中介绍的卷积算子是GNN模型中最常用的传播算子。卷积算子的主要思想是将卷积从其他域推广到图域。这方面的进展通常分为光谱法和空间法。
谱方法
谱方法使用了图形的谱域表示。这种方法基于图信号处理(Shuman et al., 2013)并定义了谱域中的卷积算子。
在谱方法中，一个图信号 https://www.zhihu.com/equation?tex=x 首先通过傅里叶变换 https://www.zhihu.com/equation?tex=F 转换至谱域，随后进行卷积运算。在卷积运算结束后，我们使用逆傅里叶图变换 https://www.zhihu.com/equation?tex=F%5E%7B-1%7D 将结果信号变回。这个过程可表示为：
https://www.zhihu.com/equation?tex=F%28x%29+%3D+U%5ETx+%5C%5C+F%5E%7B-1%7D%28x%29+%3D+Ux
这里的 https://www.zhihu.com/equation?tex=U 是归一化的图拉普拉斯算子的特征向量矩阵 https://www.zhihu.com/equation?tex=L+%3D+I_N+-+D%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7DAD%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7D ，在这里， https://www.zhihu.com/equation?tex=D 是图论中的度数矩阵， https://www.zhihu.com/equation?tex=A 是图的邻接矩阵。归一化图拉普拉斯算子是实对称半正定的，因此可以分解为 https://www.zhihu.com/equation?tex=L%3DU%CE%9BU%5ET ( https://www.zhihu.com/equation?tex=%CE%9B 是特征值的对角矩阵)。从卷积定理的角度来看，卷积操作可以定义为：
https://www.zhihu.com/equation?tex=g+%5Cstar+x+%3D+F%5E%7B-1%7D%28F%28g%29%5Codot+F%28x%29%29+%3D+U%28U%5ETg+%5Codot+U%5ET+x%29
在这里， https://www.zhihu.com/equation?tex=U%5ET 为谱域中的卷积核或者说滤波器，我们可以简单地给它增设一个可学习的对角矩阵变量，那么我们可以得到谱方法的基本函数：
https://www.zhihu.com/equation?tex=g_w+%5Cstar+x+%3D+Ug_wU%5ETx
此外，还有几种典型的设计滤波器的谱方法。
1. Spectral Network
Spectral Network谱网络使用了可学习的对角矩阵（ https://www.zhihu.com/equation?tex=g_w+%3D+diag%28w%29%2C+w+%5Cin+R%5EN ）作为滤波器。这种操作的缺点是计算效率低且滤波器具有 non-spatially localized性质。因此，Henaff et al. (2015)通过引入平滑参数使得谱滤波器空间局部化spatially localized。
2. ChebNet
Hammond et al. (2011) 提出可以通过 https://www.zhihu.com/equation?tex=k 阶切比雪夫多项式 https://www.zhihu.com/equation?tex=T_k%28x%29 的截断扩展来估计得到。Defferrard et al. (2016) 基于此理论提出了ChebNet。我们又可以将其写为：
https://www.zhihu.com/equation?tex=g_w+%5Cstar+x+%5Capprox+%5Csum%5E%7BK%7D_%7Bk%3D0%7Dw_kT_k%28%5Ctilde%7BL%7D%29x
在这里， https://www.zhihu.com/equation?tex=%5Ctilde%7BL%7D+%3D+%5Cfrac%7B2%7D%7B%5Clambda_%7Bmax%7D%7DL-I_N ，其中 https://www.zhihu.com/equation?tex=%5Clambda_%7Bmax%7D 表示 https://www.zhihu.com/equation?tex=L 向量矩阵的最大的特征值， https://www.zhihu.com/equation?tex=%5Ctilde%7BL%7D 的特征值范围为 https://www.zhihu.com/equation?tex=%5B-1%2C1%5D ， https://www.zhihu.com/equation?tex=w+%5Cin+R%5EK 为切比雪夫系数。
3. GCN
Kipf and Welling (2017) 简化了前一个公式的卷积运算操作来缓解过拟合问题。
4. GWNN
图小波神经网络(GWNN) (Xu et al.， 2019a)使用图小波变换代替图傅里叶变换。它具有以下几个优点:(1)无需矩阵分解即可快速得到图小波;(2)图小波是稀疏的和局部的，因此结果更好，更容易解释。在半监督节点分类任务中，GWNN优于几种谱方法。
5. AGCN/DGCN
AGCN和DGCN尝试从增广图拉普拉斯的角度改进谱方法。总之，谱方法具有良好的理论基础，最近也提出了一些理论分析。
空间法
空间法基于图拓扑直接在图上定义卷积。空间方法的主要挑战是定义不同大小的邻域的卷积操作，并保持CNN的局部不变性。
目前较为热门的基于空间方法（卷积）的GNN模型有：
[*]Neural FPs (Duvenaud et al., 2015)
[*]DCNN. The diffusion convolutional neural network (DCNN)(Atwood and Towsley, 2016)
[*]PATCHY-SAN(Niepert et al., 2016)
[*]LGCN. The learnable graph convolutional network (LGCN) (Gao et al.,2018a)
[*]GraphSAGE. GraphSAGE (Hamilton et al., 2017a)
此外，attention注意机制已成功应用于许多序列任务，如机器翻译，机器阅读等。还有几个模型试图在图上推广注意力算子。与之前提到的算子相比，基于注意的算子为邻域分配不同的权重，从而可以消减噪声，取得更好的效果。
目前较为热门的基于空间方法（attention）的GNN模型有：
[*]GAT. The graph attention network (GAT) (Velickovic et al., 2018)
[*]GaAN. The gated attention network (GaAN) (Zhang et al., 2018c)
今天就讲到这里，下一节我们将继续讨论传播模块。 内容详实，读后醍醐灌顶
页:
[1]