GAT算法及其DGL实现

1. GCN的局限性

GCN是处理transductive任务的一把利器（transductive任务是指：训练阶段与测试阶段都基于同样的图结构），然而GCN有两大局限性是经常被诟病的：

（a）无法完成inductive任务，即处理动态图问题。inductive任务是指：训练阶段与测试阶段需要处理的graph不同。通常是训练阶段只是在子图（subgraph）上进行，测试阶段需要处理未知的顶点。（unseen node）

（b）处理有向图的瓶颈(可以从频域GCN公式理解)，不容易实现分配不同的学习权重给不同的neighbor。

2. Attention 引入的目的

  • 为每个邻居节点分配不同权重，让模型有更强的表达能力
  • 关注那些作用比较大的节点，而忽视一些作用较小的节点(注意力机制)
  • 在处理局部信息的时候同时能够关注整体的信息，不是用来给参与计算的各个节点进行加权的，而是表示一个全局的信息并参与计算

3. GAT及其Attention原理

3.1 GAT概述

GAT(Graph Attention Networks)，即图注意力网络。

GAT由Yoshua Bengio团队出品，发表在ICLR2018，

按理来说，其缩写应该是GAN，可惜这个名字被【生成式对抗网络】先用了。

无奈只能叫GAT，有点像山寨版的网络。但这丝毫不影响其作为一种强势GNN的存在。

3.2 GAT原理

3.2.1 GAT中的Attention

GAT中注意力的提取，本质上可以有两种运算方式的，这也是原文中作者提到的。

  • Global graph attention

顾名思义，就是每一个顶点 i对于图上任意顶点都进行attention运算。

优点：完全不依赖于图的结构，对于inductive任务无压力

缺点：

  1. （1）丢掉了图结构的这个特征，无异于自废武功，效果可能会很差
  3. （2）运算面临着高昂的成本
  • Mask graph attention

注意力机制的运算只在邻居顶点上进行

作者在原文中GAT ARCHITECTURE这一节中写道“We inject the graph structure into the mechanism by performing masked attention—we only compute eij for nodes j ∈Ni, whereNi is some neighborhood of node i in the graph. “

和所有的attention mechanism一样，GAT的计算也分为两步走：计算注意力系数和加权求和

3.2.2 计算注意力系数（attention coefficient）

对于顶点 GAT算法及其DGL实现 - 图1 ，逐个计算它的邻居们（ GAT算法及其DGL实现 - 图2 ）和它自己之间的相似系数

GAT算法及其DGL实现 - 图3

解读一下这个公式：首先一个共享参数 GAT算法及其DGL实现 - 图4 的线性映射对于顶点的特征进行了增维，当然这是一种常见的特征增强（feature augment）方法；GAT算法及其DGL实现 - 图5 对于顶点 GAT算法及其DGL实现 - 图6 的变换后的特征进行了拼接（concatenate）；最后 GAT算法及其DGL实现 - 图7 把拼接后的高维特征映射到一个实数上，作者是通过 single-layer feedforward neural network实现的。

显然学习顶点 GAT算法及其DGL实现 - 图8 之间的相关性，就是通过可学习的参数 GAT算法及其DGL实现 - 图9 和映射 GAT算法及其DGL实现 - 图10 完成的。

有了相关系数，离注意力系数就差归一化了！其实就是用个softmax

GAT算法及其DGL实现 - 图11

要注意这里作者用了个 GAT算法及其DGL实现 - 图12 ，至于原因嘛，估计是试出来的，毕竟深度玄学。

可以结合下图理解：

GAT算法及其DGL实现 - 图13

3.2.3 加权求和（aggregate）

完成第一步，已经成功一大半了。第二步很简单，根据计算好的注意力系数，把特征加权求和（aggregate）一下。

GAT算法及其DGL实现 - 图14

GAT算法及其DGL实现 - 图15 就是GAT输出的对于每个顶点 GAT算法及其DGL实现 - 图16 的新特征（融合了邻域信息）， GAT算法及其DGL实现 - 图17 是激活函数。

式（3）看着还有点单薄，俗话说一个篱笆三个桩，attention得靠multi-head帮！来进化增强一下

GAT算法及其DGL实现 - 图18

嗯，这次看起来就很健壮了，multi-head attention也可以理解成用了ensemble的方法，毕竟convolution也得靠大量的卷积核才能大显神威！

GAT中的多头注意力机制如图所示：

GAT算法及其DGL实现 - 图19

4. 深入理解GAT

4.1 与GCN的联系与区别

无独有偶，我们可以发现本质上而言：

  • GCN与GAT都是将邻居顶点的特征聚合到中心顶点上（一种aggregate运算），利用graph上的local stationary学习新的顶点特征表达。
  • 不同的是GCN利用了拉普拉斯矩阵，GAT利用attention系数。
  • 一定程度上而言，GAT会更强，因为顶点特征之间的相关性被更好地融入到模型中。

4.2 为什么GAT适用于有向图？

  • 个人 认为，根本的原因是GAT的运算方式是逐顶点的运算（node-wise），这一点可从公式（1）—公式（3）中很明显地看出。
  • 每一次运算都需要循环遍历图上的所有顶点来完成。
  • 逐顶点运算意味着，摆脱了拉普拉丝矩阵的束缚，使得有向图问题迎刃而解。

4.3 为什么GAT适用于inductive任务？

GAT中重要的学习参数是 GAT算法及其DGL实现 - 图20 与 GAT算法及其DGL实现 - 图21 ，因为上述的逐顶点运算方式，这两个参数仅与1.1节阐述的顶点特征相关，与图的结构毫无关系。所以测试任务中改变图的结构，对于GAT影响并不大，只需要改变 GAT算法及其DGL实现 - 图22 ，重新计算即可。

与此相反的是，GCN是一种全图的计算方式，一次计算就更新全图的节点特征。学习的参数很大程度与图结构相关，这使得GCN在inductive任务上遇到困境。

4.4 与其他工作对比

  • GAT是高效的。相比于其他图模型，GAT无需使用特征值分解等复杂的矩阵运算。单层GAT的时间复杂度为 GAT算法及其DGL实现 - 图23 (没懂)，与频域GCN相同。其中， GAT算法及其DGL实现 - 图24 与 GAT算法及其DGL实现 - 图25 分别表示图中节点的数量与边的数量。
  • 相比于GCN，每个节点的重要性可以是不同的，因此，GAT具有更强的表示能力。
  • 对于图中的所有边，attention机制是共享的。因此GAT也是一种局部模型。也就是说，在使用GAT时，我们无需访问整个图，而只需要访问所关注节点的邻节点即可。这一特点的作用主要有：（1）可以处理有向图（若 GAT算法及其DGL实现 - 图26 不存在，仅需忽略 GAT算法及其DGL实现 - 图27 即可）；（2）可以被直接用于进行归纳学习。
  • 最新的归纳学习方法（GraphSAGE）通过从每个节点的邻居中抽取固定数量的节点，从而保证其计算的一致性。这意味着，在执行推断时，我们无法访问所有的邻居。然而，本文所提出的模型是建立在所有邻节点上的，而且无需假设任何节点顺序。

5 DGL中的GAT

GAT算法及其DGL实现 - 图28%7D%26%3DW%5E%7B(l)%7Dh_i%5E%7B(l)%7D%2C%26(1)%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Az_i%5E%7B%28l%29%7D%26%3DW%5E%7B%28l%29%7Dh_i%5E%7B%28l%29%7D%2C%26%281%29%0A%5Cend%7Balign%7D%0A)

GAT算法及其DGL实现 - 图29%7D%26%3D%5Ctext%7BLeakyReLU%7D(%5Cvec%20a%5E%7B(l)%5ET%7D(zi%5E%7B(l)%7D%7C%7Cz_j%5E%7B(l)%7D))%2C%26(2)%5C%5C%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Ae%7Bij%7D%5E%7B%28l%29%7D%26%3D%5Ctext%7BLeakyReLU%7D%28%5Cvec%20a%5E%7B%28l%29%5ET%7D%28z_i%5E%7B%28l%29%7D%7C%7Cz_j%5E%7B%28l%29%7D%29%29%2C%26%282%29%5C%5C%0A%5Cend%7Balign%7D%0A&height=26&width=274)

GAT算法及其DGL实现 - 图30%7D%26%3D%5Cfrac%7B%5Cexp(e%7Bij%7D%5E%7B(l)%7D)%7D%7B%5Csum%7Bk%5Cin%20%5Cmathcal%7BN%7D(i)%7D%5E%7B%7D%5Cexp(e%7Bik%7D%5E%7B(l)%7D)%7D%2C%26(3)%5C%5C%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%5Calpha%7Bij%7D%5E%7B%28l%29%7D%26%3D%5Cfrac%7B%5Cexp%28e%7Bij%7D%5E%7B%28l%29%7D%29%7D%7B%5Csum%7Bk%5Cin%20%5Cmathcal%7BN%7D%28i%29%7D%5E%7B%7D%5Cexp%28e_%7Bik%7D%5E%7B%28l%29%7D%29%7D%2C%26%283%29%5C%5C%0A%5Cend%7Balign%7D%0A)

GAT算法及其DGL实现 - 图31%7D%26%3D%5Csigma%5Cleft(%5Csum%7Bj%5Cin%20%5Cmathcal%7BN%7D(i)%7D%20%7B%5Calpha%5E%7B(l)%7D%7Bij%7D%20z%5E%7B(l)%7Dj%20%7D%5Cright)%2C%26(4)%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Ah_i%5E%7B%28l%2B1%29%7D%26%3D%5Csigma%5Cleft%28%5Csum%7Bj%5Cin%20%5Cmathcal%7BN%7D%28i%29%7D%20%7B%5Calpha%5E%7B%28l%29%7D_%7Bij%7D%20z%5E%7B%28l%29%7D_j%20%7D%5Cright%29%2C%26%284%29%0A%5Cend%7Balign%7D%0A)

其核心公式与论文中的一致。