一、GAT [2017]

《Graph attention networks》

1. 卷积神经网络（Convolutional Neural Network: CNN）已经成功应用于图像分类、语义分割以及机器翻译之类的问题，其底层数据结构为网格状结构（grid-like structure）。这些架构通过将它们应用于所有的 input position 从而有效地 reuse 具有可学习参数的局部滤波器（ local filter）。

   然而，许多人们感兴趣的任务涉及的数据无法以网格状结构来表达，而是位于不规则域（irregular domain）。例如，3D mesh、社交网络、电信网络、生物网络、脑连接组（brain connectome）等等。这些数据通常可以通过 graph 的形式来表达。

   有一些文献尝试扩展神经网络从而处理任意结构的图。

   • 早期的工作使用递归神经网络（recursive neural network: RNN ）来处理 graph domain 中表示为有向无环图的数据。

   • 《A new model for learning in graph domains》 和 《The graph neural network model》 提出了图神经网络（Graph Neural Network: GNN ）作为 RNN 的泛化，从而可以直接处理更通用的 graph 类型，如：循环图、有向图、无向图。

     GNN 包含一个迭代过程，该迭代过程传播节点状态直到达到平衡。然后是一个神经网络，它根据每个节点的状态为每个节点生成一个输出。

   • 这个思想被 《Gated graph sequence neural networks》 所采纳和改进，该方法提出在传播过程中使用门控循环单元（gated recurrent unit: GRU）。

   然而，人们将卷积推广到 graph domain 的兴趣越来越大。这个方向的进展通常分为谱方法（spectral approach ）和非谱方法 （non-spectral approach）。

   • 一方面，谱方法与图的谱表示（spectral representation）一起工作，并已成功应用于节点分类的 context 中。

     • 在 《Spectral networks and locallyconnected networks on graphs》 中，卷积运算是通过计算图拉普拉斯矩阵（graph Laplacian）的特征分解（eigen decomposition）从而在傅里叶域 （Fourier domain）中定义的，这导致潜在的稠密计算以及非空间局部化的滤波器（non-spatially localized filter）。 这些问题在随后的工作中得到解决。

     • 《Deep convolutional networks on graph-structured data》 引入了具有平滑系数的谱滤波器（spectral filter）的参数化（parameterization），使得滤波器在空间上局部化。

     • 后来，《Convolutional neural networks on graphs with fast localized spectral filtering》 提出通过图拉普拉斯矩阵的切比雪夫展开来近似滤波器，从而无需计算图拉普拉斯矩阵的特征向量从而生成空间局部化的滤波器。

     • 最后，《Semi-supervised classification with graph convolutional networks》 通过限制滤波器仅操作每个节点周围的 1-step 邻域内来简化之前的方法。

     然而，在所有上述谱方法中，学到的滤波器依赖于拉普拉斯矩阵的特征基（Laplacian eigenbasis），而这个特征基依赖于图结构。因此，在特定图结构上训练的模型无法直接应用于具有不同结构的其它的图。

   • 另一方面，我们有非谱方法，该方法直接在图上定义卷积从而操作空间近邻的节点集合。这些方法的挑战之一是：定义一个与不同规模的邻域一起工作，并能保持 CNN 的权重共享属性的算子。

     • 在某些情况下，这需要为每个节点 degree 学习一个特定的权重矩阵（《Convolutional networks on graphs for learning molecular fingerprints》），或者需要使用转移矩阵（transition matrix）的幂来定义邻域并同时针对每个输入通道和邻域 degree 来学习权重（《Diffusion-convolutional neural networks》），或者需要抽取和归一化邻域从而包含固定数量节点（《Learning convolutional neural networksfor graphs》）。

     • 《Geometric deep learning on graphs and manifolds using mixture model cnns》 提出了 mixture model CNN （MoNet），这是一种空间方法，可以将 CNN 架构统一泛化到图。

     • 最近，《representation learning on largegraphs》 提出了 GraphSAGE，这是一种以归纳式的方式计算 node representation 的方法。该技术通过对每个节点采样固定尺寸邻域，然后该邻域执行特定的聚合器（如，均值池化聚合器，或 LSTM 聚合器）。GraphSAGE 在多个大规模归纳式 benchmark 中取得了令人印象深刻的性能。

       GAT 无需对邻域进行采样，能够处理可变邻域。

   在许多 sequence-based 任务中，注意力机制几乎已经成为事实上的标准。注意力机制的好处之一是：注意力机制允许处理可变尺寸的输入，并聚焦于输入中最相关的部分从而作出决策。当使用注意力机制来计算单个序列的 representation 时，它通常被称作 self-attention 或 intra-attention 。与 RNN 或卷积一起，self-attention 已被证明对机器阅读、sentence representation 学习等任务很有用。而且，《Attention is all you need》 表明：self-attention 不仅可以改进基于 RNN 或卷积的方法，而且足以构建一个强大的模型并且在机器翻译任务上获得 SOTA 的性能。

   受最近这项工作的启发，论文《Graph attention networks》 引入了一种 attention-based 架构来执行图结构数据的节点分类。基本思想是：遵从 self-attention 策略，可以通过 attend 节点的邻居来计算图中每个节点的 hidden representation 。注意力架构有几个有趣的特性：

   • 操作是高效的，因为它可以跨 node-neighbor pair 进行并行化。

   • self-attention 通过给邻居赋予可学习的、任意的权重，从而可以应用于具有不同 degree 的图节点。

   • 该模型直接适用于归纳式的学习问题，包括模型必须泛化到完全 unseen 的图的任务。

   作者在四个具有挑战性的 benchmark 上验证了所提出的方法，实现或接近 SOTA 的结果。实验结果凸显了 attention-based 模型在处理任意结构的图时的潜力。

   注：inductive learning 和 transductive learning的区别：

   • inductive learning 是从具体样本中总结普适性规律，然后泛化到训练中 unseen 的样本。

   • transductive learning 是从具体样本中总结具体性规律，它用于预测训练集中已经出现过的unlabelled 样本，常用于半监督学习。

2. 相关工作：

   • 正如 《Semi-supervised classification with graph convolutional networks》 和 《Diffusion-convolutional neural networks》 一样，我们的工作也可以重新表述为 MoNet 的一个特定实例。

   • 此外，我们跨 edge 共享神经网络计算（neural network computation）的方法让人联想起关系网络（relational network ）（《A simple neural network module for relational reasoning》）和 VAIN （《Vain: Attentional multi-agent predictive modeling》）的公式，其中 object 或 agent 之间的relation 是通过采用一种共享机制来 pair-wise 聚合的。

   • 同样地，我们提出的注意力模型可以与 《One-shot imitation learning》 和 《Programmable agents》 等工作联系起来，它们使用邻域注意力操作（neighborhood attention operation）来计算环境中不同对象之间的注意力系数。

   • 其它相关方法包括局部线性嵌入（ locally linear embedding: LLE）、记忆网络 （memory network） 。

     • LLE 在每个 data point 周围选择固定数量的邻居，并为每个邻居学习一个权重系数，从而将每个 point 重构为其邻居的加权和。然后第二步优化是抽取 point 的 feature embedding 。

     • memory network也与我们的工作有一些联系。具体而言，如果我们将节点的邻域解释为 memory，那么该 memory 被用于通过 attend memory 的 values 来计算 node feature （READ 过程），然后通过将新的特征存储在 node 对应的位置从而进行更新（WRITE 过程）。

1.1 模型

1. 这里我们介绍用于构建任意 graph attention network: GAT 的 building block layer（通过堆叠该层），即 graph attentional layer: GAL 。然后我们概述与神经图处理（neural graph processing）领域的先前工作相比，这种 layer 的理论和实践上的优势和局限性。

1.1.1 Graph Attentional Layer

1. 我们将从描述单个 graph attentional layer: GAL 开始，其中GAL 作为我们实验中使用的 GAT 架构中使用的唯一一种 layer 。我们使用的特定的 attentional setup 与 《Neural machine translation by jointly learning to align and translate》 的工作密切相关，但是 GAT 框架与注意力机制的特定选择无关。

2. GAL 的输入为一组节点特征：$\mathbb{H}=\{{\overrightarrow{\mathbf{h}}}_1,\cdots ,{\overrightarrow{\mathbf{h}}}_N\},{\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^F$$\mathbb H= \left\{\mathbf{\vec h}_1,\cdots,\mathbf{\vec h}_N\right\} ,\mathbf{\vec h}_i\in \mathbb R^F$ ，其中 $N$$N$ 为图的节点数量、$F$$F$ 为节点的representation 维度。GAL 输出这些节点的新的representation：${\mathbb{H}}^{\prime }=\{{\overrightarrow{\mathbf{h}}}_1^{\prime },\cdots ,{\overrightarrow{\mathbf{h}}}_N^{\prime }\},{\overrightarrow{\mathbf{h}}}_i^{\prime }\in {\mathbb{R}}^{F^{\prime }}$$\mathbb H^\prime = \left\{\mathbf{\vec h}_1^\prime,\cdots,\mathbf{\vec h}_N^\prime\right\},\quad \mathbf{\vec h}_i^\prime\in \mathbb R^{F^\prime}$ ，其中 $F^{\prime }$$F^\prime$ 为节点新的 representation 维度（可能与 $F$$F$ 不同）。

   为了获得足够的表达能力（expressive power）从而将 input feature 转化为 higher-level feature ，至少需要一个可学习的线性变换。为此，作为初始的 step ，我们首先对所有节点应用一个共享权重的线性变换，权重为 $\mathbf{W}\in {\mathbb{R}}^{F^{\prime }\times F}$$\mathbf W \in \mathbb R^{F^\prime \times F}$ 。然后，我们在每个节点上应用 self-attention $a$$a$ （一个共享的 attentional mechanism ） ：${\mathbb{R}}^{F^{\prime }}\times {\mathbb{R}}^{F^{\prime }}\to \mathbb{R}$$\mathbb R^{F^\prime }\times \mathbb R^{F^\prime} \rightarrow \mathbb R$ ， 来计算attention 系数：

   $$e_{i,j}=a(\mathbf{W}{\overrightarrow{\mathbf{h}}}_i,\mathbf{W}{\overrightarrow{\mathbf{h}}}_j)$$

   其中 $e_{i,j}$$e_{i,j}$ 表示节点 $j$$j$ 的特征对于节点 $i$$i$ 的重要性。

   理论上讲，我们允许每个节点关注图中所有其它的节点，因此这可以完全忽略所有的图结构信息。实际上，我们采用 masked attention 机制将图的结构信息注入到 attention 机制：对于节点 $i$$i$ 我们仅仅计算其邻域内节点的 attention 系数 $e_{i,j},j\in {\mathcal{N}}_i$$e_{i,j},j\in \mathcal N_i$ ，其中 ${\mathcal{N}}_i$$\mathcal N_i$ 为节点 $i$$i$ 的邻域。目前在我们的所有实验中，邻域 $\mathcal{N}$$\mathcal N$ 仅仅包含节点的一阶邻居（包括节点 $i$$i$ 在内）。

   注意：这里 ${\mathcal{N}}_i$$\mathcal N_i$ 包含节点 $i$$i$ 在内。因为我们需要计算 $e_{i,i}$$e_{i,i}$ 。

   为使得系数可以在不同节点之间比较，我们使用 softmax 函数对所有的 $j$$j$ 进行归一化：

   $${\alpha }_{i,j}={\text{softmax}}_j(e_{i,j})=\frac{\exp (e_{i,j})}{\sum _{k\in {\mathcal{N}}_i}\exp (e_{i,k})}$$

   在我们的实验中，注意力机制 $a$$a$ 是一个单层的前向传播网络，参数为权重 $\overrightarrow{\mathbf{a}}\in {\mathbb{R}}^{2F^{\prime }}$$\mathbf{\vec a}\in \mathbb R^{2F^\prime}$，采用 LeakyReLU 激活函数，其中负轴斜率 $\beta =0.2$$\beta = 0.2$。完全展开后，注意力机制计算的系数可以表示为（如下图所示）：

   $${\alpha }_{i,j}={\text{softmax}}_j(e_{i,j})=\frac{\exp \left(\text{LeakyReLU}(\overrightarrow{\mathbf{a}}\cdot [\mathbf{W}{\overrightarrow{\mathbf{h}}}_i||\mathbf{W}{\overrightarrow{\mathbf{h}}}_j])\right)}{\sum _{k\in {\mathcal{N}}_i}\exp \left(\text{LeakyReLU}(\overrightarrow{\mathbf{a}}\cdot [\mathbf{W}{\overrightarrow{\mathbf{h}}}_i||\mathbf{W}{\overrightarrow{\mathbf{h}}}_k])\right))}$$

   其中：$||$$||$ 表示向量拼接操作。

   注意：这里的节点 $i$$i$ 作为 query，邻域 ${\mathcal{N}}_i$$\mathcal N_i$ 内节点作为 key 。query 节点 $i$$i$ 的representation 和每个 key 的 representation 进行拼接。

   

3. 一旦得到归一化的注意力得分，我们就可以用它对相应的邻居节点的特征进行加权线性组合，从而得到每个节点的final output feature：

   $${\overrightarrow{\mathbf{h}}}_i^{\prime }=\sigma \left(\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}\mathbf{W}{\overrightarrow{\mathbf{h}}}_j\right)$$

   其中 $\mathbf{W}\in {\mathbb{R}}^{F^{\prime }\times F}$$\mathbf W\in \mathbb R^{F^\prime \times F}$ ，它就是前面计算注意力得分的矩阵。

   理论上也可以使用不同的 $\mathbf{W}$$\mathbf W$，此时模型容量会得到进一步提升。

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

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{\prime (1)}=\sigma \left(\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}^{(1)}{\mathbf{W}}^{(1)}{\overrightarrow{\mathbf{h}}}_j\right)\\ ⋮\\ {\overrightarrow{\mathbf{h}}}_i^{\prime (K)}=\sigma \left(\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}^{(K)}{\mathbf{W}}^{(K)}{\overrightarrow{\mathbf{h}}}_j\right)\\ {\overrightarrow{\mathbf{h}}}_i^{\prime }=[{\overrightarrow{\mathbf{h}}}_i^{\prime (1)}||\cdots ||{\overrightarrow{\mathbf{h}}}_i^{\prime (K)}]\end{array}$$

   其中：

   • ${\alpha }_{i,j}^{(k)}$$\alpha_{i,j}^{(k)}$ 为第 $k$$k$ 个head 的归一化的注意力得分。

   • ${\mathbf{W}}^{(k)}$$\mathbf W^{(k)}$ 为第 $k$$k$ 个 head 的权重矩阵。

   最终的输出 ${\overrightarrow{\mathbf{h}}}^{\prime }$$\mathbf{\vec h}^\prime$ 的维度为 $K{F}^{\prime }$$KF^\prime$ （而不是 $F^{\prime }$$F^\prime$ ）。

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

   $${\overrightarrow{\mathbf{h}}}_i^{\prime }=\sigma \left(\frac{1}{K}\sum _{k=1}^K\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}^{(k)}{\mathbf{W}}^{(k)}{\overrightarrow{\mathbf{h}}}_j\right)$$

   理论上，最后的GAL 也可以拼接再额外接一个输出层。例如，实验部分作者就在最后一层使用 $K=8$$K=8$ 个 attention head 。

   如下图所示为 multi head = 3，当且节点 $i=1$$i=1$ 。不同颜色的箭头表示不同的 head 。

   

1.1.2 和相关工作的比较

1. GAL 解决了现有的、基于神经网络对图结构数据建模的方法的问题。

   • GAL 计算高效：

     • self-attentional layer 的操作可以跨所有 edge 并行化，输出特征的计算可以跨所有节点并行化。

       即，单个 self-attention 内部的、计算 $e_{i,j}$$e_{i,j}$ 的操作可以并行化。不同节点之间计算 self-attention 也可以并行化。

     • 不需要特征分解（eigen decomposition）或类似的昂贵矩阵计算。

     • 单个 attention head 计算 $F^{\prime }$$F^\prime$ 个特征的时间复杂度为 $O(|V|\times F\times F^{\prime }+|E|\times F^{\prime })$$O(|V|\times F\times F^\prime + |E|\times F^\prime)$ ，其中 $F$$F$ 为输入特征的个数，$|V|$$|V|$ 为图中节点的数量，$|E|$$|E|$ 为图中边的数量。这种复杂度和一些baseline 方法（如 GCN ）差不多。

       • 首先计算所有节点的 $\mathbf{W}{\overrightarrow{\mathbf{h}}}_i$$\mathbf W \mathbf{\vec h}_i$ ，计算复杂度为 $O(|V|\times F\times F^{\prime })$$O(|V|\times F\times F^\prime)$ 。

       • 再计算所有的 $\overrightarrow{\mathbf{a}}\cdot [\mathbf{W}{\overrightarrow{\mathbf{h}}}_i,\mathbf{W}{\overrightarrow{\mathbf{h}}}_j]$$\mathbf{\vec a}\cdot [\mathbf W\mathbf{\vec h}_i,\mathbf W\mathbf{\vec h}_j]$ ，计算复杂度为 $O(|E|\times F^{\prime })$$O(|E|\times F^\prime)$ 。

       • 再计算所有的 ${\alpha }_{i,j}$$\alpha_{i,j}$ ，计算复杂度为 $O(|V|\times \overline{d})$$O(|V|\times \bar d)$ ，其中 $\overline{d}=\frac{|E|}{|V|}$$\bar d = \frac{|E|}{|V|}$ 为节点的平均 degree ，则 ${\alpha }_{i,j}$$\alpha_{i,j}$ 的计算复杂度为 $O(|E|)$$O(|E|)$ 。

       最终计算复杂度为 $|V|\times F\times F^{\prime }+|E|\times F^{\prime }$$|V|\times F\times F^\prime + |E| \times F^\prime$ 。

     • 应用 multi-head attention 将存储需求和参数需求乘以 $K$$K$ 倍，而各个 head 的计算是完全独立的并且可以并行化。

   • GCN：和 GCN 相比，GAT 模型允许为同一个邻域内的节点分配不同的重要性，从而实现模型容量（model capacity）的飞跃。另外，和机器翻译领域一样，对学到的注意力权重进行分析可能会带来可解释性的好处。

   • 注意力机制以共享的方式应用于图的所有边，因此它不需要预先得到整个图结构或者所有节点（这是许多现有技术的局限性）。这有几个理想的含义：

     • 图可以是有向图，也可以是无向图。如果边 $j\to i$$j\rightarrow i$ 不存在，则我们不需要计算系数 ${\alpha }_{i,j}$$\alpha_{i,j}$ 。

     • GAT 可以直接应用到归纳式学习（ inductinve learning ）：模型可以预测那些在训练期间中 unseen 的图。

   • GraphSAGE ：最近发表的归纳式方法 GraphSAGE 对每个节点采样固定大小的邻域，从而保持计算足迹（ computational footprint）的一致性。这使得模型无法在测试期间访问整个邻域。

     注意：由于训练期间训练多个 epoch，则 GraphSAGE 可能访问到节点的整个邻域。

     此外，当使用 LSTM-based 邻域集合器时，GraphSAGE 取得了一些最强的结果。LSTM 假设在邻域之间存在一致的节点排序，并且作者通过向 LSTM 持续地提供随机排序的序列来使用 LSTM 。

     GAT 没有这两个问题：GAT 作用在完整的邻域上，并且不假设邻域内有任何节点的排序。

     注意：虽然 GAT 作用在完整的领域上，但是在大型图的训练过程中可能还需要对邻域进行采样。因为对于大型图，对于每个 mini-batch $\mathcal{B}$$\mathcal B$，我们不仅要提供 $\mathcal{B}$$\mathcal B$ ，我们还需要提供 $v\in \mathcal{B}$$v\in \mathcal B$ 的邻域、以及它的邻域的邻域，... 。如果 GAT 有 $L$$L$ 层，那么需要覆盖 $\mathcal{B}$$\mathcal B$ 的 $L$$L$ 阶邻域。

     如果使用完整的邻域，那么每个 mini-batch 所需要的节点可能就是整个大图。这对于大型图而言是无法接受的（空间复杂度太高）。

   • MoNet：如前所述，GAT 可以重写表述为 MoNet 的特定实例。更具体而言：

     • 设定伪坐标函数（pseudo-coordinate function）为 $u(x,y)=f\left(x\right)||f\left(y\right)$$u\left(x,y\right) = f\left(x\right)|| f\left(y\right)$ ，其中： $f\left(x\right)$$f\left(x\right)$ 表示节点 $x$$x$ 的特征（可能是 MLP 变换而来），$||$$||$ 表示特征拼接。

     • 设定权重函数为 $w_j(u)=\text{softmax}(\text{MLP}(u))$$w_j(u) = \text{softmax}(\text{MLP}(u))$ ，在节点的整个邻域上执行 softmax 。

     此时，这种 MoNet 的补丁算子 （patch operator）将类似于我们的方法。

     然而，应该注意的是：与这个 MoNet 实例相比，我们的模型使用节点特征来计算相似性，而不是节点的结构属性（假设预先知道图结构）。

2. 我们可以使用一种利用稀疏矩阵操作的 GAL 层，它可以将空间复杂度下降到节点和边的线性复杂度，从而使得模型能够在更大的图数据集上运行。但是我们的 tensor 计算框架仅支持二阶tensor 的稀疏矩阵乘法，这限制了当前版本的 batch 处理能力，特别是在具有很多图的数据集上。解决该问题是未来一个重要的方向。另外，根据现有图结构的规律，在稀疏矩阵的情况下，GPU 的运算速度并不会比 CPU 快多少因此无法提供主要的性能优势。

   还应该注意的是，我们模型的感受野 （receptive field）的大小是网络深度的上限（类似于 GCN 或类似的模型）。然而，诸如 skip connection 之类的技术可以解决该问题，从而允许 GAT 使用更深的网络。

   最后，跨图中所有 edge 的并行化，尤其是以分布式方式，可能会涉及大量冗余计算，因为图中邻域通常高度重叠。

1.1.3 未来工作

1. 一些有待改进的点：

   • 如何处理更大的 batch size 。

   • 如何利用注意力机制对模型的可解释性进行彻底的分析。

   • 如何执行graph-level 的分类，而不仅仅是node-level 的分类。

   • 如何利用边的特征，而不仅仅是节点的特征。因为边可能蕴含了节点之间的关系，边的特征可能有助于解决各种各样的问题。

1.2 实验

1.2.1 Transductinve Learning

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

   每个节点表示一篇文章、边（无向）表示文章引用关系。每个节点的特征为文章的 BOW representation。每个节点有一个类别标签。

   • Cora 数据集：包含2708 个节点、5429 条边、7 个类别，每个节点 1433 维特征。

   • Citeseer 数据集：包含3327 个节点、4732 条边、6 个类别，每个节点 3703 维特征。

   • Pubmed 数据集：包含19717 个节点、44338 条边、3 个类别，每个节点 500 维特征。

   对每个数据集的每个类别，我们使用20 个带标签的节点来训练，然后在 1000 个测试节点上评估模型效果。我们使用额外的 500 个带标签节点作为验证集（与 GCN 论文中使用的相同）。

   注意：训练算法可以利用所有节点的结构信息和特征信息，但是只能利用每个类别 20 个节点的标签信息。

   

2. 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 模型。

   • 我们也直接对比了 GCN模型、利用高阶切比雪夫的图卷积模型Chebyshev filter-based（《Convolutional neural networks on graphs with fast localized spectral filtering》）、以及 MoNet 模型。

   • 我们还提供了每个节点共享 MLP 分类器的性能，该模型完全没有利用图的结构信息。

3. 参数配置：

   • 我们使用一个双层的 GAT 模型，它的架构超参数已经在 Cora 数据集上进行了优化，然后被 Citeseer 复用。

     • 第一层包含 $K=8$$K=8$ 个 attention head，每个 head 得到 $F^{\prime }=8$$F^\prime = 8$ 个特征，总计 64 个特征。第一层后面接一个exponential linear unit: ELU 非线性激活层。

     • 第二层用作分类，采用一个 attention head 计算 $C$$C$ 个特征，其中 $C$$C$ 为类别数量，然后使用 softmax 激活函数。

   • 当处理小数据集时，我们在模型上施加正则化：

     • 我们采用 $L_2$$L_2$ 正则化，其中正则化系数为 $\lambda =0.0005$$\lambda = 0.0005$。

     • 两个层的输入，以及 normalized attention coefficient 都使用了 $p=0.6$$p=0.6$ （遗忘比例）的 dropout 。即每轮迭代时，每个节点需要随机采样邻居（因为有些邻居被 dropout 了）。

   • 对于60 个样本的 Pubmd 数据集，我们需要对 GAT 架构进行微调：

     • 输出为 $K=8$$K=8$ 个 attention head ，而不是一个。

     • $L_2$$L_2$ 正则化系数为 $\lambda =0.001$$\lambda = 0.001$ 。

     除此之外都和 Cora/Citeseer 的一样。

   • 所有模型都采用 Glorot 初始化方式来初始化参数，优化目标为交叉熵，使用 Adam SGD 优化器来优化。初始化学习率为：Pubmed 数据集为 0.01，其它数据集为 0.005 。

     我们在所有任务上执行早停策略，在验证集上的交叉熵和accuracy 如果连续 100 个 epoch 没有改善，则停止训练。

4. 我们报告了 GAT 随机执行 100 次实验的分类准确率的均值以及标准差，也使用了 GCN 和 Monet 报告的结果。

   对基于切比雪夫过滤器的方法，我们提供了 $K=2,K=3$$K=2,K=3$ 阶过滤器的最佳结果。

   我们进一步评估了 GCN 模型，其隐层为 64 维，同时尝试使用 ReLU 和 ELU 激活函数，并记录执行 100 次后效果最好的那个（实验表明 ReLU 在所有三个数据集上都最佳），记作 GCN-64* 。

   结论：GAT 在 Cora 和 Citeseer 上超过 GCN 分别为 1.5%, 1.6% ，这表明为邻域内节点分配不同的权重是有利的。

   

1.2.2 Inductinve learning

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

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

   从 Molecular Signatuers Database 收集到的gene ontology 有 121 种标签，这里每个节点可能同时属于多个标签。

   

2. Baseline 模型：我们对比了四个不同版本的监督 GraphSAGE 模型，它们提供了多种方法来聚合采样邻域内的节点特征：

   • GraphSAGE-GCN：将图卷积方式的操作扩展到归纳式 setting 。

   • GraphSAGE-mean：取特征向量的逐元素均值来聚合。

   • GraphSAGE-LSTM：通过将邻域特征馈入 LSTM 来聚合。

   • GraphSAGE-pool ：采用共享非线性多层感知机转换后的特征向量的逐元素最大池化来聚合。

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

   我们还提供了每个节点共享 MLP 分类器的性能，该模型完全没有利用图的结构信息。

3. 参数配置：

   • 我们使用一个三层GAT 模型：

     • 第一层包含 $K=4$$K=4$ 个 attention head，每个 head 得到 $F^{\prime }=256$$F^\prime = 256$ 个特征，总计 1024 个特征。第一层后面接一个exponential linear unit:ELU 非线性激活层。

     • 第二层和第一层配置相同。

     • 第三层为输出层，包含 $K=6$$K=6$ 个 attention head ，每个 head 得到 121 个特征。

       我们对所有 head 取平均，并后接一个 sigmoid 激活函数。

   • 由于该任务的训练集足够大，因此我们无需执行 $L_2$$L_2$ 正则化或者 dropout 。

   • 我们在 attention layer 之间应用 skip connection 。

   • 训练的 batch size = 2 ，即每批2 个 graph 。

   • 为评估 attention 机制的效果，我们提供了一个注意力得分为常数的模型进行对比（$a(x,y)=1$$a(x,y) = 1$），其它结构不变。

   • 所有模型都采用 Glorot 初始化方式来初始化参数，优化目标为交叉熵，使用 Adam SGD 优化器来优化。初始化学习率为：Pubmed 数据集为 0.01，其它数据集为 0.005 。

     我们在所有任务上执行早停策略，在验证集上的交叉熵和micro-F1 如果连续 100 个 epoch 没有改善，则停止训练。

4. 我们报告了模型在测试集（两个从未见过的 Graph ）上的 micro-F1 得分。我们随机执行10 轮 “训练--测试”，并报告这十轮的均值。对于其它基准模型，我们使用 GraphSAGE 报告的结果。具体而言，由于我们的 setting 是有监督的，我们将与有监督的 GraphSAGE 方法进行比较。

   为了评估聚合整个邻域的好处，我们进一步提供了GraphSAGE 架构的最佳结果，记作 GraphSAGE* 。这是通过一个三层GraphSAGE-LSTM 得到的，三层维度分别为 [512,512,726]，最终聚合的特征为 128 维。

   最后，我们报告常数的注意力系数为 Const-GAT 的结果。

   结论：

   • GAT 在 PPI 数据集上相对于 GraphSAGE 的最佳效果还要提升 20.5% ，这表明我们的模型在inductive 任务中通过观察整个邻域可以获得更大的预测能力。

   • 相比于 Const-GAT，我们的模型提升了 3.9%，这再次证明了为不同邻居分配不同权重的重要性。

   

注意：这里作者并未给出超参数研究的实验分析，包括：GAT 层数、multi-head 数量、是否使用 skip connection 等等。

1.2.3 可视化

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

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

   下图中：颜色表示节点类别，线条粗细代表归一化的注意力系数均值：

   $${\text{line}}_{i,j}=\frac{1}{K}\sum _{k=1}^K{\alpha }_{i,j}^k+{\alpha }_{j,i}^k$$