论文标题：Graph Attention Networks
论文方向：图像领域
论文来源：ICLR 2018
论文链接：https://arxiv.org/abs/1710.10903
论文代码：https://github.com/PetarV-/GAT
1 介绍
针对图结构数据，本文提出了一种GAT（ Graph Attention Networks ）网络。该网络使用 masked self-attention层解决了之前基于图卷积的模型所存在的问题。在 GAT 中，图中的每个节点可以根据邻节点的特征，为其分配不同的权值。GAT的另一个优点在于，无需使用预先构建好的图。因此，GAT可以解决一些基于谱的图神经网络中所具有的问题。实验证明，GAT模型可以有效地适用于（基于图的）归纳学习问题与转导学习问题。
- 计算速度快，可以在不同的节点上进行并行计算；
- 可以通过指定邻居指定任意权值应用于具有不同程度的图节点；
- 该模型直接适用于归纳学习问题，包括模型必须推广到完全看不见的图的任务。
2 GAT 网络架构
通过堆叠单个的图注意力层（building block layer）来构建任意的图注意力网络。
2.1 Graph Attentional Layer
首先来介绍单个的 Graph attentional layer.
单个的 Graph attentional layer 的输入是一个节点特征向量集：
$mathbf{h}=left{vec{h}_{1}, vec{h}_{2}, ldots, vec{h}_{N} ight}, vec{h}_{i} in mathbb{R}^{F}$
其中， $N$ 表示节点集中节点的个数， $F$ 表示相应的特征向量维度。
每一层的输出是一个新的节点特征向量集：
$mathbf{h}^{prime}=left{vec{h}_{1}^{prime}, vec{h}_{2}^{prime}, ldots, vec{h}_{N}^{prime} ight}, vec{h}_{i}^{prime} in mathbb{R}^{F^{prime}}$
其中，$F^{prime}$ 表示新的节点特征向量维度 (可以不等于 $F$ )。
一个 Graph attentional layer 的结构如下图所示：
为了获得足够的表达能力将输入特征转换为更高层次的特征，Graph attentional layer 首先根据输入的节点特征向量集，进行 self-attention处理：
$e_{i j}=aleft(mathbf{W} vec{h}_{i}, mathbf{W} vec{h}_{j} ight)$
其中， $a$ 是一个 $mathbb{R}^{F^{prime}} imes mathbb{R}^{F^{prime}} ightarrow mathbb{R}$ 的映射，$W in mathbb{R}^{F^{prime} imes F}$ 是一个权重矩阵（被所有 $vec{h}_{i}$ 的共享）。$e_{ij}$ 表明节点 $j$ 的特征对节点 $i$ 的重要性。
一般来说，self-attention 会将注意力分配到图中所有的节点上，这种做法显然会丢失结构信息。为了解决这一问题，本文使用了一种 masked attention 的方式——仅将注意力分配到节点 $i$ 的邻节点集上，即 $j in mathcal{N}_{i}$，（在本文中，节点 $i$ 也是 $mathcal{N}_{i}$ 的一部分）：
为了使注意力权重在不同节点之间容易比较，我们使用 Softmax 函数对所有的选择进行标准化：
$alpha_{i j}=operatorname{softmax}_{j}left(e_{i j} ight)=frac{exp left(e_{i j} ight)}{sum limits _{k in mathcal{N}_{i}} exp left(e_{i k} ight)}$
其中，$overrightarrow{mathbf{a}} in mathbb{R}^{2 F^{prime}} $ 是单层前馈神经网络 $a$ 的一个权重向量参数。$a$ 使用 LeakyReLU 非线性激活函数（在负区间，斜率 $alpha=0.2$）。
注意力机制的完全形式为：
$alpha_{i j}=frac{exp left(operatorname{LeakyReLU}left(overrightarrow{mathbf{a}}^{T}left[mathbf{W} vec{h}_{i} | mathbf{W} vec{h}_{j} ight] ight) ight)}{sum limits _{k in mathcal{N}_{i}} exp left(operatorname{LeakyReLU}left(overrightarrow{mathbf{a}}^{T}left[mathbf{W} vec{h}_{i} | mathbf{W} vec{h}_{k} ight] ight) ight)}$
其中， $vec{a}^{T} in mathbb{R}^{2 F^{prime}}$ 为前馈神经网络 $a$ 的参数，${.}^{T} $ 代表着是转置操作，$||$ 是串联操作（ t.cat ）。这里最终 $alpha_{ij} epsilon {mathbb{R}}$ 。
$vec{h}_{i}^{prime}=sigmaleft(sum limits _{j in mathcal{N}_{mathbf{1}}} alpha_{i j} mathbf{W} vec{h}_{j} ight)$
为提高模型的拟合能力，本文引入了 multi-head attention ，即同时使用多个 $W^{k}$ 计算 self-attention，然后将各个 $W^{k}$ 计算得到的结果合并（连接或求和）：
其中， $||$ 表示拼接，$a_{i j}^{k}$ 表示 $W^{k}$ 与 第 $k$ 个抽头得到的计算结果。由于 $W^{k} in mathbb{R}^{F^{prime} imes F}$ , 因此这里的 $vec{h}_{i}^{prime} in mathbb{R}^{K F^{prime}}$ 。
如果我们对网络的最终（预测）层执行 multi-head attention ，那么连接就不再是明智的，可以采取求和的方式来得到 $vec{h}_{i}^{prime}$：
$vec{h}_{i}^{prime}=sigmaleft(frac{1}{K} sum limits _{k=1}^{K} sum limits_{j in mathcal{N}_{i}} alpha_{i j}^{k} mathbf{W}^{k} vec{h}_{j} ight)$
由于 $W^{k} in mathbb{R}^{F^{prime} imes F}$ ，因此这里的 $vec{h}_{i}^{prime} in mathbb{R}^{ F^{prime}}$ 。
2.2 与相关工作的比较
本文使用了很大的篇幅将GAT与其他的图模型进行了比较：
- GAT是高效的。相比于其他图模型，GAT 无需使用特征值分解等复杂的矩阵运算。单层 GAT 的 时间复杂度为 $Oleft(|V| F F^{prime}+|E| F^{prime} ight) $ (与 GCN 相同) 。其中，$ |V| $ 与 $|E|$ 分别表示图中节点的数量与边的数量。
- 相比于GCN，每个节点的重要性可以是不同的，因此，GAT具有更强的表示能力。
- 对于图中的所有边，attention 机制是共享的。因此GAT也是一种局部模型。也就是说，在使用GAT时，我们无需访问整个图，而只需要访问所关注节点的邻节点即可。这一特点的作用主要有：最新的归纳学习方法（GraphSAGE）通过从每个节点的邻居中抽取固定数量的节点，从而保证其计算的一致性。这意味着，在执行推断时，我们无法访问所有的邻居。然而，本文所提出的模型是建立在所有邻节点上的，而且无需假设任何节点顺序。
- 可以处理有向图（若 $jlongrightarrow i$ 不存在，仅需忽略 $alpha _{ij}$ 即可）；
- 可以被直接用于进行归纳学习——包括在训练过程中完全看不到的图上评估模型的任务。
- GAT可以被看作是 MoNet 的一个特例。具体来说，可以通过将伪坐标函数（pseudo-coordinate function）设为 $u(x, y)=f(x) | f(y)$ 。其中，$f(x)$ 表示节点 $x$ 的特征，$||$ 表示连接符号；相应的权值函数则变成了 $w_{j}(u)=operatorname{softmax}(operatorname{MLP}(u))$ 。然而，需要注意的是，与之前考虑的 MoNet 实例相比，我们的模型使用节点特征进行相似性计算，而不是节点的结构属性(假设知道图的结构）。
3 实验
本文的实验建立在四个基于图的任务上，这些任务包括三个转导学习（transductive learning）任务以及一个归纳学习（inductive learning）任务。具体如下：
这两个模型都使用 Glorot 初始化进行初始化，并使用 AdamSGD 优化器 进行训练，以减少训练节点上的交叉熵，Pubmed 的初始学习率为0.01，其他数据集的初始学习率为 0.005。在这两种情况下，我们都使用交叉熵损失的早期停止策略和验证节点的准确性（转导学习），使用$micro-F_{1} $f1（归纳学习）得分的停止策略，训练 100 个epoch。
3.1 转导学习（Transductive learning）
三个标准的引文网络基准数据集——Cora, Citeseer and Pubmed 。这三个数据库每个类20 个节点用于训练，然而，根据 transductive setup ，训练算法可以访问所有节点的特征向量（这就是转导学习的特点），使用500 个节点做验证，使用1000个节点做测试。
对于转导学习任务，我们应用了一个两层 GAT 模型。它的架构超参数已经在 Cora 数据集上进行了优化，然后被重新用于 Citeseer。第一层由 $K = 8$ 个 attention head 组成，每个 attention head 计算 $F^{prime} = 8$ 个特征（总共 64 个特征），然后使用指数线性单元（ELU）非线性。第二层用于分类：计算 $C$ 个特征的 single attention head（其中 $C$ 是类的数量），然后是 softmax 激活。为了应对较小的训练集大小，模型中大量应用了正则化。在训练期间，我们应用 $L_2$ 正则化，$lambda = 0.0005$。此外，$p = 0.6$ 的 dropout 应用于两个层的输入以及归一化的注意力系数。我们发现 Pubmed 的训练集大小（60 个示例）需要对 GAT 架构稍作更改：我们应用了 $K = 8$ 个输出注意力头（而不是一个），并将 $L_2$ 正则化增强为 $lambda = 0.001$。否则，该架构与用于 Cora 和 Citeseer 的架构相匹配。
转导学习的实验结果如下表所示，可以看到，GAT模型的效果要基本优于其他模型。
3.2 归纳学习（Inductive learning ）
归纳学习的实验结果如下表所示，可以看到，GAT模型的效果要远远优于其他模型。
4 结论
本文提出了一种基于 self-attention 的图模型。总的来说，GAT的特点主要有以下两点：
- 与GCN类似，GAT同样是一种局部网络。因此，（相比于GNN或GGNN等网络）训练GAT模型无需了解整个图结构，只需知道每个节点的邻节点即可。
$A=left[egin{array}{lll} 1 & 1 & 0 \ 0 & 1 & 1 \ 0 & 0 & 1 end{array} ight] quad X=left[egin{array}{ll}x_{11} & x_{12} \x_{21} & x_{22} \ x_{31} & x_{32} end{array} ight] quad W=left[egin{array}{ll} w_{11} & w_{12} \ w_{21} & w_{22} end{array} ight]$
单层GCN（忽略激活函数）
$X^{n e w}=A^{n e w} X W=left[egin{array}{cc}a_{11}left(w_{11} x_{11}+w_{12} x_{12} ight)+a_{12}left(w_{11} x_{21}+w_{21} x_{22} ight) & ldots \ldots & ldots \ldots & w_{12} x_{31}+w_{22} x_{32}end{array} ight]$
- GAT与GCN有着不同的节点更新方式。GCN使用的是GAT使用 self-attention为每个邻节点分配权重，也就是说，GAT的节点更新方式与以下是一个具体的示例。假设有三个节点，每个节点使用二维向量进行表示，则两种网络对应于以上运算。通过对比可以发现，GAT在计算新的节点表示时，相比于GCN，多引入了一个权值矩阵（可以看成将原先的 $A$ 修改成了 $A^{new}$。