2018-07-18 《Graph Attention Netw

作者：Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Yoshua Bengio

来源： ICLR 2018

链接： link

研究机构：Department of Computer Science and Technology；Centre de Visi´o per Computador, UAB；Montreal Institute for Learning Algorithms

源码链接： source code

Introduction

针对图结构数据，本文提出了一种GAT（graph attention networks）网络。该网络使用masked self-attention层解决了之前基于图卷积（或其近似）的模型所存在的问题。在GAT中，图中的每个节点可以根据邻节点的特征，为其分配不同的权值。GAT的另一个优点在于，无需使用预先构建好的图。因此，GAT可以解决一些基于谱的图神经网络中所具有的问题。实验证明，GAT模型可以有效地适用于（基于图的）归纳学习问题与转导学习问题。

Definition

• 归纳学习（Inductive Learning）：先从训练样本中学习到一定的模式，然后利用其对测试样本进行预测（即首先从特殊到一般，然后再从一般到特殊），这类模型如常见的贝叶斯模型。
• 转导学习（Transductive Learning）：先观察特定的训练样本，然后对特定的测试样本做出预测（从特殊到特殊），这类模型如k近邻、SVM等。

Related Work

在之前的模型中，已经有很多基于神经网络的工作被用于处理图结构的数据。例如，最早的GNN网络（详情见GNN）可以被用于处理有环图、有向图或无向图。然而，GNN网络本身必须使整个网络达到不动点之后才可以进行计算。针对这一问题，[2]中通过将GRU引入到网络结构中，进一步提出了GGNN网络（详情见GGNN）。后来，人们开始关注将卷积操作引入到图领域中，这一类算法可以被分为谱方法（spectral approaches）与非谱方法（non-spectral approaches）两大类。

谱方法是基于对图进行谱表示的一类方法。其上的卷积操作与图拉普拉斯矩阵的特征值分解有关，因此，往往需要进行密集的矩阵运算，而且整个计算并不是局部的。为了解决这一问题，[3]提出了GCN网络，该网络可以有效地对节点的一阶邻居进行处理，而且可以避免复杂的矩阵运算。然而，这些模型都依赖于图的结构，因此，在特定图结构上训练得到的模型往往不可以直接被使用到其他图结构上。

不同于谱方法，非谱方法是直接在图上（而不是在图的谱上）定义卷积。这类方法的一个挑战在于，如何定义一个可以处理可变大小邻居且共享参数的操作。针对这一问题，在[4]中，作者提出了MoNet（mixture model CNN），该方法可以有效地将CNN结构引入到图上。类似地，[5]提出了一种GraphSAGE模型，该模型使用一种归纳的方法来计算节点表示。具体来说，该模型首先从每个节点的邻节点中抽取出固定数量的节点，然后再使用特定的方式来融合这些邻节点的信息（如直接对这些节点的特征向量求平均，或者将其输入到一个RNN中），这一方法已经在很多大型归纳学习问题中取得了很好的效果。

在本文中，作者提出了一种基于attention的节点分类网络——GAT。其基本思想是，根据每个节点在其邻节点上的attention，来对节点表示进行更新。GAT具有以下几个特点：（1）计算速度快，可以在不同的节点上进行并行计算；（2）可以同时对拥有不同度的节点进行处理；（3）可以被直接用于解决归纳学习问题，即可以对从未见过的图结构进行处理。

Model

Graph Attentional Layer

首先来介绍单个的graph attentional layer.

单个的 graph attentional layer 的输入是一个节点特征向量集：

<figure style="margin: 1em 0px;"> image

</figure>

其中， [图片上传失败...(image-55538a-1531927054004)]

表示节点集中节点的个数， [图片上传失败...(image-1e03b-1531927054004)]

表示相应的特征向量维度。

每一层的输出是一个新的节点特征向量集：

<figure style="margin: 1em 0px;"> image

</figure>

其中， [图片上传失败...(image-c0d7e5-1531927054004)]

表示新的节点特征向量维度（可以不等于 [图片上传失败...(image-302754-1531927054004)]

）。

一个graph attention layer的结构如下图所示：

<figure style="margin: 1em 0px;"> image

<figcaption style="margin-top: 0.66667em; padding: 0px 1em; font-size: 0.9em; line-height: 1.5; text-align: center; color: rgb(153, 153, 153);">图1 模型结构</figcaption>

</figure>

具体来说，graph attentional layer首先根据输入的节点特征向量集，进行self-attention处理：

<figure style="margin: 1em 0px;"> image

</figure>

其中， [图片上传失败...(image-cbf41b-1531927054004)]

是一个 [图片上传失败...(image-b2e6aa-1531927054004)]

的映射， [图片上传失败...(image-79afb3-1531927054004)]

是一个权值矩阵（被所有 [图片上传失败...(image-270481-1531927054004)]

所共享）。一般来说，self-attention会将注意力分配到图中所有的节点上，这种做法显然会丢失结构信息。为了解决这一问题，本文使用了一种masked attention的方式——仅将注意力分配到节点 [图片上传失败...(image-7f1ac5-1531927054004)]

的邻节点集上，即 [图片上传失败...(image-99d843-1531927054004)]

（在本文中，节点 [图片上传失败...(image-3fa89b-1531927054004)]

也是 [图片上传失败...(image-b77317-1531927054004)]

的一部分）：

<figure style="margin: 1em 0px;"> image

</figure>

在本文中， [图片上传失败...(image-915cb2-1531927054004)]

使用单层的前馈神经网络实现。总的计算过程为：

<figure style="margin: 1em 0px;"> image

</figure>

其中， [图片上传失败...(image-1d7841-1531927054004)]

为前馈神经网络 [图片上传失败...(image-53d3aa-1531927054004)]

的参数， [图片上传失败...(image-ee6a23-1531927054004)]

为前馈神经网络的激活函数。此时就可以得到 [图片上传失败...(image-1bb23a-1531927054004)]

了：

<figure style="margin: 1em 0px;"> image

</figure>

为了提高模型的拟合能力，在本文中还引入了多抽头的self-attention（如图1右侧部分。与《Attention is All You Need》一致），即同时使用多个 [图片上传失败...(image-25d88a-1531927054004)]

计算 self-attention, 然后将各个 [图片上传失败...(image-d0b7d7-1531927054004)]

计算得到的结果合并（连接或求和）：

<figure style="margin: 1em 0px;"> image

<figcaption style="margin-top: 0.66667em; padding: 0px 1em; font-size: 0.9em; line-height: 1.5; text-align: center; color: rgb(153, 153, 153);">连接</figcaption>

</figure>

其中， [图片上传失败...(image-d0f563-1531927054004)]

表示连接， [图片上传失败...(image-7db5e7-1531927054004)]

与 [图片上传失败...(image-e74ab6-1531927054004)]

表示第 [图片上传失败...(image-a70f8e-1531927054004)]

个抽头得到的计算结果。由于 [图片上传失败...(image-2fdfe2-1531927054004)]

，因此这里的 [图片上传失败...(image-b9de96-1531927054004)]

。同样，可以采取求和的方式来得到 [图片上传失败...(image-c05045-1531927054004)]

：

<figure style="margin: 1em 0px;"> image

<figcaption style="margin-top: 0.66667em; padding: 0px 1em; font-size: 0.9em; line-height: 1.5; text-align: center; color: rgb(153, 153, 153);">求和</figcaption>

</figure>

模型比较

本文使用了很大的篇幅将GAT与其他的图模型进行了比较：

• GAT是高效的。相比于其他图模型，GAT无需使用特征值分解等复杂的矩阵运算。单层GAT的时间复杂度为 [图片上传失败...(image-6ca944-1531927054004)]

  （与GCN相同）。其中， [图片上传失败...(image-123cad-1531927054004)]

  与 [图片上传失败...(image-bbb5fb-1531927054004)]

  分别表示图中节点的数量与边的数量。

• 相比于GCN，每个节点的重要性可以是不同的，因此，GAT具有更强的表示能力。

• 对于图中的所有边，attention机制是共享的。因此GAT也是一种局部模型。也就是说，在使用GAT时，我们无需访问整个图，而只需要访问所关注节点的邻节点即可。这一特点的作用主要有：（1）可以处理有向图（若 [图片上传失败...(image-47959-1531927054004)]

  不存在，仅需忽略 [图片上传失败...(image-6da1ed-1531927054004)]

  即可）；（2）可以被直接用于进行归纳学习。

• 最新的归纳学习方法（GraphSAGE）通过从每个节点的邻居中抽取固定数量的节点，从而保证其计算的一致性。这意味着，在执行推断时，我们无法访问所有的邻居。然而，本文所提出的模型是建立在所有邻节点上的，而且无需假设任何节点顺序。

• GAT可以被看作是MoNet的一个特例。具体来说，可以通过将伪坐标函数（pseudo-coordinate function）设为 [图片上传失败...(image-dc4914-1531927054004)]

  ，其中， [图片上传失败...(image-5e09b8-1531927054004)]

  表示节点 [图片上传失败...(image-412648-1531927054004)]

  的特征， [图片上传失败...(image-bed31-1531927054004)]

  表示连接符号；相应的权值函数则变成了 [图片上传失败...(image-81458b-1531927054004)]

  。

Experiments

本文的实验建立在四个基于图的任务上，这些任务包括三个转导学习（transductive learning）任务以及一个归纳学习（inductive learning）任务。具体如下：

Transductive Learning

在转导学习任务中，使用了三个标准的引证网络数据集——Cora、Citeseer与Pubmed。在这些数据集中，节点对应于文档，边（无向的）对应于引用关系。节点特征对应于文档的BoW表示。每个节点拥有一个类别标签（在分类时使用softmax激活函数）。每个数据集的详细信息如下表所示：

<figure style="margin: 1em 0px;"> image

</figure>

转导学习的实验结果如下表所示，可以看到，GAT模型的效果要基本优于其他模型。

<figure style="margin: 1em 0px;"> image

</figure>

Inductive Learning

对于归纳学习，本文使用了一个蛋白质关联数据集（protein-protein interaction, PPI），在其中，每张图对应于人类的不同组织。此时，使用20张图进行训练，2张图进行验证，2张图用于测试。每个节点可能的标签数为121个，而且，每个节点可以同时拥有多个标签（在分类时使用sigmoid激活函数）。

归纳学习的实验结果如下表所示，可以看到，GAT模型的效果要远远优于其他模型。

<figure style="margin: 1em 0px;"> image

</figure>

Conclusion

本文提出了一种基于self-attention的图模型。总的来说，GAT的特点主要有以下两点：

• 与GCN类似，GAT同样是一种局部网络。因此，（相比于GNN或GGNN等网络）训练GAT模型无需了解整个图结构，只需知道每个节点的邻节点即可。

<figure style="margin: 1em 0px;"> image

</figure>

• GAT与GCN有着不同的节点更新方式。GCN使用的是GAT使用self-attention为每个邻节点分配权重，也就是说，GAT的节点更新方式与以下是一个具体的示例。假设有三个节点，每个节点使用二维向量进行表示，则两种网络对应于以上运算。通过对比可以发现，GAT在计算新的节点表示时，相比于GCN，多引入了一个权值矩阵（可以看成将原先的 [图片上传失败...(image-9aedd0-1531927054004)]

  修改成了 [图片上传失败...(image-d466f2-1531927054004)]

  ）。

Reference

[1]Veličković P, Cucurull G, Casanova A, et al. Graph Attention Networks. International Conference on Learning Representations (ICLR), 2018.

[2] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations (ICLR), 2016.

[3] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.

[4] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodol`a, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. arXiv preprint arXiv:1611.08402, 2016.

[5] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neural Information Processing Systems (NIPS), 2017.

发布于 2018-03-19

《Graph Attention Networks》阅读笔记
https://zhuanlan.zhihu.com/p/34232818