[论文笔记]GRAPH ATTENTION NETWORKS(GAT) 图注意力网络原理

GAT Note

参考：

Paper：GRAPH ATTENTION NETWORKS ICLR 2018

向往的GAT（图注意力模型） - 知乎 (zhihu.com)

专栏 | 深入理解图注意力机制 (qq.com)

图卷积神经网络系列：8. | 空域图卷积模型GAT及PyTorch实现 - 知乎 (zhihu.com)

Paper

• GAT中，卷积被定义为利用注意力机制来对邻域结点进行有区别的聚合，核心思想：将Attention应用于图卷积网络

Motivation

• 作者认为，邻域中所有的节点共享相同的卷积核参数会限制模型的能力。因为邻域内的每一个节点和中心节点的关联度都是不同的，在卷积聚合邻域节点的信息时需要对邻域中的不同的节点区别对待。

• 具体地，就是利用Attention机制来建模邻域节点与中心节点的关联度，来实现“区别对待”。

Method

关键点1：使用注意力机制计算节点之间的关联度

关键点2：利用注意力系数对邻域节点进行有区别的信息聚合，完成图卷积操作

注意力机制的理解

• GAT也可以认为是对局部图结构的一种学习。现有的图卷积方法常常更关注节点特征，而忽视了图上的结构。

• Attention机制可以认为是一个带有可学习参数的可学习函数。利用Attention机制，就可以构建一个可学习的函数来得到相邻节点之间的关系，也就是局部的图结构。

Basic of GAT

• 两种特征

  • 对于任意一个顶点，它在图上的邻居特征，即图的结构关系
  • 每个顶点还有自己的特征（通常是高维向量）
• GCN的局限性

  GCN是处理transductive任务的一把利器（transductive任务是指：训练阶段与测试阶段都基于同样的图结构），但是存在局限性

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

• 处理有向图的瓶颈，不容易实现分配不同的学习权重给不同的neighbor。

  • Mask graph attention or global graph attention

• Global graph attention：每个顶点对图上任意顶点都进行attention运算

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

  • 缺点：

    1. 丢掉了图结构这个特征
    2. 运算成本很大

• Mask graph attention：注意力机制的运算只在邻居顶点上进行

  • 论文中作者即采用的这种方式

GAT

• 和所有的attention mechanism一样，GAT的计算也分为两步走： %7D%3DW%5E%7B(l)%7Dhi%5E%7B(l)%7D%5C%5C%0Ae%7Bij%7D%5E%7B(l)%7D%3D%5Cvec%20a%5E%7B(l)T%7D(%5Bzi%5E%7B(l)%7D%7C%7Cz_j%5E%7B(l)%7D%5D)%5C%5C%0A%5Calpha%7Bij%7D%5E%7B(l)%7D%3D%5Cfrac%7Bexp(LeakyReLU(e%7Bij%7D%5E%7B(l)%7D))%7D%7B%5Csum%7Bk%5Cin%20N(i)%7Dexp(LeakyReLU(e%7Bik%7D%5E%7B(l)%7D))%7D%20%5Ctag%7B1%7D%0A#card=math&code=z_i%5E%7B%28l%29%7D%3DW%5E%7B%28l%29%7Dh_i%5E%7B%28l%29%7D%5C%5C%0Ae%7Bij%7D%5E%7B%28l%29%7D%3D%5Cvec%20a%5E%7B%28l%29T%7D%28%5Bzi%5E%7B%28l%29%7D%7C%7Cz_j%5E%7B%28l%29%7D%5D%29%5C%5C%0A%5Calpha%7Bij%7D%5E%7B%28l%29%7D%3D%5Cfrac%7Bexp%28LeakyReLU%28e%7Bij%7D%5E%7B%28l%29%7D%29%29%7D%7B%5Csum%7Bk%5Cin%20N%28i%29%7Dexp%28LeakyReLU%28e%7Bik%7D%5E%7B%28l%29%7D%29%29%7D%20%5Ctag%7B1%7D%0A)
  %7D%3D%5Csigma(%5Csum%7Bj%5Cin%20N(i)%7D%5Calpha%7Bij%7D%5E%7B(l)%7Dz_j%5E%7B(l)%7D)%20%5Ctag%7B2%7D%0A#card=math&code=h_i%5E%7B%28l%2B1%29%7D%3D%5Csigma%28%5Csum%7Bj%5Cin%20N%28i%29%7D%5Calpha_%7Bij%7D%5E%7B%28l%29%7Dz_j%5E%7B%28l%29%7D%29%20%5Ctag%7B2%7D%0A)

对比GCN：

%7D%3D%5Csigma(%5Ctilde%7BD%7D%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7D%5Ctilde%7BA%7D%5Ctilde%7BD%7D%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7DH%5E%7B(l)%7D%5Ctheta)%0A#card=math&code=H%5E%7B%28l%2B1%29%7D%3D%5Csigma%28%5Ctilde%7BD%7D%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7D%5Ctilde%7BA%7D%5Ctilde%7BD%7D%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7DH%5E%7B%28l%29%7D%5Ctheta%29%0A)

(1)计算注意力系数（attention coefficient）

• 对于顶点 ，逐个计算它的邻居们（）和它自己之间的相似系数： T%7D(%5BW%5E%7B(l)%7Dhi%5E%7B(l)%7D%7C%7CW%5E%7B(l)%7Dh_j%5E%7B(l)%7D%5D)%2C%20j%5Cin%20N_i%0A#card=math&code=e%7Bij%7D%3D%5Cvec%20a%5E%7B%28l%29T%7D%28%5BW%5E%7B%28l%29%7Dh_i%5E%7B%28l%29%7D%7C%7CW%5E%7B%28l%29%7Dh_j%5E%7B%28l%29%7D%5D%29%2C%20j%5Cin%20N_i%0A)

1. 首先一个共享参数的线性映射对顶点的特征和进行增维（这是一个常见的特征增强feature augment方法）
2. 对顶点，的变换后的特征进行拼接（concatenate）
3. 最后#card=math&code=a%28%C2%B7%29)把拼接后的高维特征映射到一个实数上（作者通过single-layer feedforward neural network实现）

显然学习顶点，之间的相关性，就是通过可学习的参数和映射#card=math&code=a%28%C2%B7%29)完成的。

• 有了相关系数，归一化（论文采用softmax）后可以得到注意力系数 %7D%3D%5Cfrac%7Bexp(LeakyReLU(e%7Bij%7D%5E%7B(l)%7D))%7D%7B%5Csum%7Bk%5Cin%20N(i)%7Dexp(LeakyReLU(e%7Bik%7D%5E%7B(l)%7D))%7D%0A#card=math&code=%5Calpha%7Bij%7D%5E%7B%28l%29%7D%3D%5Cfrac%7Bexp%28LeakyReLU%28e%7Bij%7D%5E%7B%28l%29%7D%29%29%7D%7B%5Csum%7Bk%5Cin%20N%28i%29%7Dexp%28LeakyReLU%28e_%7Bik%7D%5E%7B%28l%29%7D%29%29%7D%0A)

(2)加权求和（aggregate）

• 根据计算好的注意力系数，把特征加权求和（aggregate） %0A#card=math&code=%5Cvec%20hi%5E%7B%27%7D%3D%5Csigma%28%5Csum%20%7Bj%5Cin%20Ni%7D%5Calpha%7Bij%7DW%5Cvec%20h_j%29%0A)

就是GAT输出的对于每个顶点的新特征（融合了邻域信息），#card=math&code=%5Csigma%28%C2%B7%29)是激活函数

• multi-head attention
  神似卷积神经网络里的多通道，GAT 引入了多头注意力来丰富模型的能力和稳定训练的过程。每一个注意力的头都有它自己的参数。如何整合多个注意力机制的输出结果一般有两种方式：

  1. 拼接

%3D%5Cparallel%7Bk%3D1%7D%5EK%5Csigma(%5Csum%7Bj%5Cin%20Ni%7D%5Calpha%7Bij%7D%5Ek%20W%5Ek%5Cvec%20hj)%20%5Ctag%7B3%7D%0A#card=math&code=%5Cvec%20h_i%5E%7B%27%7D%28K%29%3D%5Cparallel%7Bk%3D1%7D%5EK%5Csigma%28%5Csum%7Bj%5Cin%20N_i%7D%5Calpha%7Bij%7D%5Ek%20W%5Ek%5Cvec%20h_j%29%20%5Ctag%7B3%7D%0A)

1. 平均

%3D%5Csigma(%5Cfrac%7B1%7D%7BK%7D%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Csum%7Bj%5Cin%20Ni%7D%5Calpha%7Bij%7D%5Ek%20W%5Ek%5Cvec%20hj)%20%5Ctag%7B3%7D%0A#card=math&code=%5Cvec%20h_i%5E%7B%27%7D%28K%29%3D%5Csigma%28%5Cfrac%7B1%7D%7BK%7D%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Csum%7Bj%5Cin%20N_i%7D%5Calpha%7Bij%7D%5Ek%20W%5Ek%5Cvec%20h_j%29%20%5Ctag%7B3%7D%0A)

与其他图卷积模型的对比

1. 在邻域节点构建上，不同于GNN（随机游走）、GraphSAGE（采样）， GAT直接选用一阶相邻节点作为邻域节点（和GCN类似）。

   随机游走(random walk)

• 所谓随机游走(random walk)，就是在网络上不断重复地随机选择游走路径，最终形成一条贯穿网络的路径。
  从一个顶点出发，然后按照一定的概率随机移动到一个邻居节点，并将该节点作为新的当前节点，如此循环执行若干步，得到一条游走路径。

• 优点：

  • 并行性
  • 局部适应性

(7条消息) GNN笔记： random walk_UQI-LIUWJ的博客-CSDN博客

1. 在节点排序上，GAT中的邻域的所有节点无需排序并且共享卷积核参数（和 GraphSAGE类似）。

2. 由于GAT引入了Attention机制，可以构建相邻节点的关系，是对邻域节点的有区别的聚合。若将 和 结合起来看做一个系数，实际上GAT对邻域的每个节点隐式地（implicitly）分配了不同的卷积核参数。

深入理解

与GCN的联系与区别

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

为什么GAT适用于有向图？

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

为什么GAT适用于inductive任务？

GAT中重要的学习参数是 与#card=math&code=a%28%C2%B7%29)，因为上述的逐顶点运算方式，这两个参数仅与顶点特征相关，与图的结构毫无关系。所以测试任务中改变图的结构，对于GAT影响并不大，只需要改变，重新计算即可。
与此相反的是，GCN是一种全图的计算方式，一次计算就更新全图的节点特征。学习的参数很大程度与图结构相关，这使得GCN在inductive任务上遇到困境。