GAT

GAT（Graph Attention Network）

1 基础概念

1.1 Graph数据结构的两种“特征”

当我们说起graph或者network的数据结构，通常是包含着顶点和边的关系。研究目标聚焦在顶点之上，边诉说着顶点之间的关系。

对于任意一个顶点 $i$ ，它在图上邻居 $N_{i}$ ,构成第一种特征，即图的结构关系。

图1

**当然，除了图的结构之外，每个顶点还有自己的特征 $h_{i}$ （通常是一个高维向量)。**它可以是社交网络中每个用户的个体属性；可以是生物网络中，每个蛋白质的性质；还可以使交通路网中，每个交叉口的车流量。

1.2 GCN的局限性

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

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

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

1.3 Mask graph attention or global graph attention

还有一件事件需要提前说清楚**：GAT本质上可以有两种运算方式的**，这也是原文中作者提到的

Global graph attention

**顾名思义，就是每一个顶点 $i$ 对于图上任意顶点都进行attention运算。**可以理解为图1的蓝色顶点对于其余全部顶点进行一遍运算。

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

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

Mask graph attention

注意力机制的运算只在邻居顶点上进行，也就是说图1的蓝色顶点只计算和橙色顶点的注意力系数。

2 原理

和所有的attention mechanism一样，GAT的计算也分为两步走：

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

对于顶点 $i$ ，逐个计算它的邻居们 $(j \in N_{i})$ 和它自己之间的相似系数

\begin{matrix} (1) & e_{i j} = a ([W h_{i} | | W h_{j}]), j \in N_{i} h_{i} \in R^{F} W \in R^{F^{^{'}} \times F} a \in R^{F^{^{'}}} \times R^{F^{^{'}}} \end{matrix}

解读一下这个公式**：首先一个共享参数 $W$ 的线性映射对于顶点的特征进行了增维，当然这是一种常见的特征增强（feature augment)方法**； $[\cdot | | \cdot]$ 对于顶点 $i, j$ 的变换后的特征进行了拼接（concatenate）；**最后 $a (\cdot)$ 把拼接后的高维特征映射到一个实数上，**作者是通过 single-layer feedforward neural network实现的。

显然学习顶点 $i, j$ 间的相关性，就是通过可学习的参数 $W$ 和映射 $a (\cdot)$ 完成的。

有了相关系数，离注意力系数就差归一化了！其实就是用个 $s o f t m a x$

\begin{matrix} (2) & a_{i j} = \frac{e x p (L e a k y R e L U (e_{i j}))}{\sum_{k \in N_{i}} e x p (L e a k y R e L U (e_{i k}))} \end{matrix}

要注意这里作者用了个 $L e a k y R e L U (\cdot)$ ，至于原因嘛，估计是试出来的，毕竟深度玄学。

上面的步骤可以参考图2进行理解

2.2 加权求和（aggregate）

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

\begin{matrix} (3) & h_{i}^{^{'}} = σ (\sum_{j \in N_{i}} a_{i j} W h_{j}) \end{matrix}

$h_{i}^{^{'}}$ 是GAT输出的对于每个顶点 $i$ 的新特征（融合了邻域信息）， $σ (\cdot)$ 是激活函数。

式（3）看着还有点单薄，**俗话说一个篱笆三个桩，attention得靠multi-head帮！**作者们建议对中间层使用拼接对最后一层使用求平均。来进化增强一下

\begin{matrix} (4) & h_{i}^{^{'}} (K) = ∥_{k = 1}^{K} σ (\sum_{j \in N_{i}} a_{i j}^{k} W^{k} h_{j}) \end{matrix}

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

上面的步骤可以参考图3进行理解

3 谈几点深入的理解

3.1 与GCN的联系与区别

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

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

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

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

GAT中重要的学习参数是 $W$ 与 $a (\cdot)$ ，因为上述的逐顶点运算方式，这两个参数仅与1.1节阐述的顶点特征相关，与图的结构毫无关系。所以测试任务中改变图的结构，对于GAT影响并不大，只需要改变 $N_{i}$ ，重新计算即可。**