13.图神经网络 - 九、GAT - 《AI算法工程师手册》

九、GAT
- 9.1 模型
- 9.2 实验

九、GAT

卷积神经网络CNN 已经成功应用于图像分类、语义分割以及机器翻译之类的问题，其底层数据结构为网格状结构grid-like structure 。但很多任务涉及到无法以网状结构表示的数据，如：社交网络、电信网络等，而这些数据通常可以用图的方式来组织。
- 早期图领域任务通常作为有向无环图，采用循环神经网络RNN 来处理。后来发展出图神经网络GNN 作为 RNN 的泛化来直接处理更通用的图，如循环图、有向图、无环图。
  
  GNN 包含一个迭代过程来传播顶点状态直至达到状态平衡，即不动点；然后再根据顶点状态为每个顶点生成输出。GG-NN 通过在顶点状态传播过程中使用门控循环单元来改进这一方法。
- 另一个方向是将卷积推广到图领域，有两种推广思路：谱方法spectral approach 、非谱方法non-spectral approach 。
  - 谱方法通常和图的谱表达spectral representation 配合使用，并已成功应用于顶点分类。
    
    但是这些谱方法中，学习的filter 都依赖于拉普拉斯矩阵分解后的特征向量。这种分解依赖于具体的图结构，因此在一种图结构上训练的模型无法直接应用到具有不同结构的图上。
    
    另外，该方法无法应用于 graph-level 任务，因为不同图的结构通常不同，因此拉普拉斯矩阵也不同。
  - 非谱方法可以直接在图上定义卷积，从而对空间相邻的邻域顶点进行运算。
    
    但是如何定义一种可以处理不同数量邻居顶点、且能保持 CNN 权重共享的卷积操作是一个挑战。PATCHY-SAN 通过归一化邻域得到固定大小的邻域。
- attention 机制在很多基于序列的任务中已经称为标配。注意力机制的一个好处是可以处理变长输入，并聚焦于输入中最相关的部分来做决策。当注意力机制作用于单个序列的representation 时，通常称作self-attention 或者 intra-attention 。
  
  受此启发，论文 《GRAPH ATTENTION NETWORKS》 提出了一种基于注意力的架构 Graph attention network:GAT 来对图结构数据进行顶点分类。其基本思想是：通过self-attention 策略来“注意”邻居顶点，从而计算每个顶点的 representation 。
  
  GAT 堆叠了一些 masked self-attention layer ，这些层中的顶点能够注意到邻居顶点的特征，并给邻域中不同的顶点赋予不同权重。在这个过程中不需要进行任何复杂的矩阵操作（如矩阵求逆或者矩阵分解），也不需要任何依赖于图结构的先验知识。
  
  GAT 模型具有以下优势：
  - 计算高效，因为GAT 可以在顶点邻居pair 对之间并行执行。
  - 通过对邻居顶点赋予任意权重，它可以应用到任意degree 的顶点，对网络结构的普适性更强。
  - 该模型可以直接应用于归纳学习inductive learning 问题，包括将模型推广到从未见过的图。
inductive learning 和 transductive learning的区别：
- inductive learning 是从具体样本中总结普适性规律，然后泛化到训练中从未见过的样本。
- transductive learning 是从具体样本中总结具体性规律，它用于预测训练集中已经出现过的unlabelled 样本，常用于半监督学习。
  
  半监督学习不一定是 transductive，它也可能是 inductive 。如：训练时仅考虑 labelled 样本，不使用任何 unlabelled 样本的信息。

9.1 模型

graph attentional laye:GAL 是 GAT 模型中最重要的层，模型通过大量堆叠这种层来实现。
attention 的实现方式有很多种，GAT 不依赖于具体的 attention 实现方式。我们以最常见的实现方式为例，来说明 GAL 。

GAL 的输入为一组顶点特征：，其中为图的顶点数量、为顶点的representation 维度。GAL 输出这些顶点的新的representation：，其中为顶点新的 representation 维度。
- 为了在将输入特征映射到高维特征时获得足够的表达能力，我们至少需要一个可学习的线性变换，即这个线性变换的权重不是固定的。
  
  为实现该目的，我们首先对所有顶点应用一个共享权重的线性变换，权重为。
- 然后，我们在每个顶点上应用 self-attention ，来计算attention 系数：
  
  的物理意义为：站在顶点的角度看顶点对它的重要性。
- 理论上讲，我们允许每个顶点关注图中所有其它的顶点，因此这可以完全忽略所有的图结构信息。实际上，我们采用 masked attention 机制来结合图的结构信息：对于顶点我们仅仅计算其邻域内顶点的 attention 系数，其中为顶点的邻域。注意：这里包含顶点在内。
  
  目前在我们的所有实验中，邻域仅仅包含顶点的一阶邻居（包括顶点在内）。
- 为使得系数可以在不同顶点之间比较，我们使用 softmax 函数对所有的进行归一化：
  
  在我们的实验中，注意力机制是一个单层的前向传播网络，参数为权重，采用 LeakyReLU 激活函数，其中负轴斜率。因此注意力得分为：
  
  其中表示两个向量的拼接。
一旦得到注意力得分，我们就可以用它对相应的邻居顶点进行加权，从而得到每个顶点的最终输出：

其中，它就是前面计算注意力得分的矩阵。

我们使用 multi-head attention 来稳定 self-attention 的学习过程。我们采用个 head，然后将它们的输出拼接在一起：

其中为第个head 的注意力得分，为第个 head 的权重矩阵。最终的输出的维度为（而不是）。

但是，如果 GAL 是网络最后一层（即输出层），我们对 multi-head 的输出不再进行拼接，而是直接取平均，因为拼接没有意义。同时我们延迟使用最后的非线性层，对分类问题通常是 softmax 或者 sigmoid ：

理论上，最后的GAL 也可以拼接再额外接一个输出层。

如下图所示为 multi head = 3，当且顶点。不同颜色的箭头表示不同的 head 。
GAL 解决了基于神经网络对图结构的数据建模的现有方法的问题：
- GAL 计算高效。GAL 层的操作可以在所有的边上并行计算，输出特征的计算可以在所有顶点上并行计算。这里没有耗时的特征值分解，也没有类似的矩阵的耗时操作（如求逆）。
  - 单个 attention head 计算个特征的时间复杂度为，其复杂度和一些baseline 方法（如 Graph Convolutional Networks:GCN ）差不多。
    
    首先计算所有顶点的，计算复杂度为；再计算所有的，计算复杂度为；再计算所有的，计算复杂度为，其中为顶点的平均 degree ，则的计算复杂度为。
    
    最终计算复杂度为。
  - 尽管 multi-head attention 使得参数数量和空间复杂度变成倍，但是每个 head 可以并行计算。
- 和 Semi-Supervised GCN 相比，GAT 模型允许为同一个邻域内的顶点分配不同的重要性，从而实现模型容量的飞跃。另外，和机器翻译领域一样，对学得的注意力权重进行分析可以得到更好的解释性。
- 注意力机制以共享的方式应用于图的所有边，因此它不需要预先得到整个图结构或者所有顶点。这带来几个影响：
  - 图可以是有向图，也可以是无向图。如果边不存在，则我们不需要计算系数。
  - GAT 可以直接应用到归纳学习 inductinve learning ：模型可以预测那些在训练集中从未出现的图。
- GraphSage 归纳学习模型对每个顶点采样固定大小的邻域，从而保持计算过程的一致性。这使得模型无法在测试期间访问整个邻域。注意：由于训练期间训练多个 epoch，则可能访问到顶点的整个邻域。
  
  也可以使用LSTM 技术来聚合邻域顶点，但是这需要假设邻域中存在一个一致的顶点顺序。
  
  GAT 没有这两个问题：GAT 在作用在完整的邻域上，并且不关心邻域内顶点的顺序。
我们可以使用一种利用稀疏矩阵操作的 GAL 层，它可以将空间复杂度下降到顶点和边的线性复杂度，从而使得模型能够在更大的图数据集上运行。但是我们的 tensor 计算框架仅支持二阶tensor 的稀疏矩阵乘法，这限制了当且版本的 batch 处理能力，特别是在具有很多图的数据集上。解决该问题是未来一个重要的方向。

另外，在稀疏矩阵的情况下，GPU 的运算速度并不会比 CPU 快多少。
和Semi-Supervised GCN以及其它模型类似，GAT 模型的感受野取决于网络深度。但是网络太深容易引起优化困难，此时采用跳跃连接 skip connection 可以解决该问题，从而允许 GAT 使用更深的网络。
如果在所有边上并行计算（尤其是分布式并行计算）可能包含大量重复计算，因为图中的邻居往往高度重叠。

9.2 实验

9.2.1 Transductinve Learning

数据集：三个标准的引文网络数据集Cora, Citeseer,Pubmed。

每个顶点表示一篇文章、边（无向）表示文章引用关系。每个顶点的特征为文章的 BOW representation。每个顶点有一个类别标签。
- Cora 数据集：包含2708 个顶点、5429 条边、7 个类别，每个顶点 1433 维特征。
- Citeseer 数据集：包含3327 个顶点、4732 条边、6 个类别，每个顶点 3703 维特征。
- Pubmed 数据集：包含19717 个顶点、44338 条边、3 个类别，每个顶点 500 维特征。
对每个数据集的每个类别我们使用20 个带标签的顶点来训练，然后在 1000 个测试顶点上评估模型效果。我们使用额外的 500 个带标签顶点作为验证集。注意：训练算法可以利用所有顶点的结构信息和特征信息，但是只能利用每个类别 20 个顶点的标签信息。
Baseline 模型：我们对比了论文 《Semi-supervised classification with graph convolutional networks》 的工作，以及其它的 baseline 模型，包括：标签传播模型label propagation: LP，半监督嵌入模型 semi-supervised embedding: SemiEmb，流型正则化模型 manifold regularization: ManiReg，基于SkipGram 的graph embeding 模型（如 DeepWalk），迭代式分类算法模型 iterative classification algorithm: ICA ，Planetoid 模型。

我们也直接对比了 Semi-Supervised GCN模型、利用高阶切比雪夫的图卷积模型、以及 MoNet 模型。

我们还提供了每个顶点共享 MLP 分类器的性能，该模型完全没有利用图的结构信息。
参数配置：
- 我们使用一个双层的 GAT 模型：
  - 第一层包含个 attention head，每个 head 得到个特征，总计 64 个特征。第一层后面接一个exponential linear unit:ELU 非线性激活层。
  - 第二层用作分类，采用一个 attention head 计算个特征，其中为类别数量，然后使用 softmax 激活函数。
- 模型的所有超参数在 Cora 上优化之后，复用到Citeseer 数据集。
- 当处理小数据集时，我们在模型上施加正则化：
  - 我们采用正则化，其中正则化系数为
  - 两个层的输入，以及 normalized attention coefficient 都使用了（遗忘比例）的 dropout 。即每轮迭代时，每个顶点需要随机采样邻居。
- 对于60 个样本的 Pubmd 数据集，这些参数都需要微调：
  - 输出为个 attention head ，而不是一个。
  - 正则化系数为。
  除此之外都和 Cora/Citeseer 的一样。
- 所有模型都采用 Glorot 初始化方式来初始化参数，优化目标为交叉熵，使用 Adam SGD 优化器来优化。初始化学习率为：Pubmed 数据集为 0.01，其它数据集为 0.005 。
  
  我们在所有任务上执行早停策略，在验证集上的交叉熵、accuracy 如果连续 100 个 epoch 没有改善，则停止训练。
我们报告了 GAT 随机执行 100 次实验的分类准确率的均值以及标准差，也使用了 Semi-Supervised GCN （即表中的 GCN ）和 Monet 报告的结果。
- 对基于切比雪夫过滤器的方法，我们提供了阶过滤器的最佳结果。
- 我们进一步评估了 Semi-Supervised GCN 模型，其隐层为 64 维，同时尝试使用 ReLU 和 ELU 激活函数，并记录执行 100 次后效果最好的那个（实验表明 ReLU 在所有三个数据集上都最佳），记作 GCN-64* 。
- 结论：GAT 在 Cora 和 Citeseer 上超过 Semi-Supervised GCN 分别为 1.5%, 1.6% ，这表明为邻域内顶点分配不同的权重是有利的。

9.2.2 Inductinve learning

数据集：protein-protein interaction: PPI 数据集，该数据集包含了人体不同组织的蛋白质的24 个图。其中20 个图为训练集、2 个图为验证集、2 个图为测试集。注意：这里测试的Graph 在训练期间完全未被观测到。

我们使用 GraphSage 提供的预处理数据来构建图，每个图的平均顶点数量为 2372 个，每个顶点50 维特征，这些特征由 positional gene sets, motif gene sets, immunological signatures 组成。

从 Molecular Signatuers Database 收集到的gene ontology 有 121 种标签，这里每个顶点可能同时属于多个标签。
Baseline 模型：我们对比了四个不同版本的监督 GraphSAGE 模型，它们提供了多种方法来聚合采样邻域内的顶点特征：GraphSAGE-GCN、GraphSAGE-mean、GraphSAGE-LSTM、GraphSAGE-pool 。

剩下的 transductinve 方法要么完全不适用于inductive 的情形，要么无法应用于在训练期间完全看不到测试Graph的情形，如 PPI数据集。

我们还提供了每个顶点共享 MLP 分类器的性能，该模型完全没有利用图的结构信息。
参数配置：
- 我们使用一个三层GAT 模型：
  - 第一层包含个 attention head，每个 head 得到个特征，总计 1024 个特征。第一层后面接一个exponential linear unit:ELU 非线性激活层。
  - 第二层和第一层配置相同。
  - 第三层为输出层，包含个 attention head ，每个 head 得到 121 个特征。
    
    我们对所有 head 取平均，并后接一个 sigmoid 激活函数。
- 由于该任务的训练集足够大，因此我们无需执行正则化或者 dropout 。
- 我们在 attention layer 之间应用 skip connection 。
- 训练的 batch size = 2 ，即每批2 个 graph 。
- 为评估 attention 机制的效果，我们提供了一个注意力得分为常数的模型进行对比（），其它结构不变。
- 所有模型都采用 Glorot 初始化方式来初始化参数，优化目标为交叉熵，使用 Adam SGD 优化器来优化。初始化学习率为：Pubmed 数据集为 0.01，其它数据集为 0.005 。
  
  我们在所有任务上执行早停策略，在验证集上的交叉熵、micro-F1 如果连续 100 个 epoch 没有改善，则停止训练。
我们报告了模型在测试集（两个从未见过的 Graph ）上的 micro-F1 得分。我们随机执行10 轮 “训练—测试”，并报告这十轮的均值。
- 对于其它基准模型，我们使用 GraphSage 报告的结果。
- 为了评估聚合邻域的好处，我们进一步提供了GraphSAGE 架构的最佳结果，记作 GraphSAGE* 。这是通过一个三层GraphSAGE-LSTM 得到的，三层维度分别为 [512,512,726]，最终聚合的特征为 128 维。
- 我们报告常数的注意力系数为 Const-GAT 。
- 结论：
  - GAT 在 PPI 数据集上相对于 GraphSAGE 的最佳效果还要提升 20.5% ，这表明我们的模型在inductive 任务中通过观察整个邻域可以获得更大的预测能力。
  - 相比于 Const-GAT，我们的模型提升了 3.9%，这再次证明了为不同邻居分配不同权重的重要性。

9.2.3 其它

我们采用 t-SNE 对学到的特征进行可视化。我们对 Cora 数据集训练的 GAT 模型的第一层的输出进行可视化，该 representation 在投影到的二维空间中表现出明显的聚类。这些簇对应于数据集的七种类别，从而验证了模型的分类能力。

此外我们还可视化了归一化注意力系数的相对强度（在所有8 个 attention head 上的均值）。如果正确的解读这些系数需要有关该数据集的进一步的领域知识。

下图中：颜色表示顶点类别，线条粗细代表归一化的注意力系数均值：
一些有待改进的点：
- 如果处理更大的 batch size 。
- 如果利用注意力机制对模型的可解释性进行彻底的分析。
- 如何执行graph-level 的分类，而不仅仅是node-level 的分类。
- 如果利用边的特征，而不仅仅是顶点的特征。因为边可能蕴含了顶点之间的关系，边的特征可能有助于解决各种各样的问题。