Graph Attention Networks

GNN

发布日期: 2020-12-17

Background

图数据是生活中常见的一种数据，它具有非欧几里得的性质。随着深度学习的发展，基于图数据的深度学习方法日趋流行，主要包括RecGNN、ConvGNN、GAEs、STGNN。

ConvGNN可以分为Spectral ConvGNN和Spatial ConvGNN两种：

Spectral ConvGNN基于图信号处理理论，需要使用图的Laplacian Matrix，，以及对其进行特征值分解。这就使得：

一个图上的Spectral ConvGNN不能直接迁移到另一个图上（not inductive）；
特征值分解也涉及了大量的矩阵操作，增大了时间复杂度；

而Spatial ConvGNN则不依赖于Laplacian Matrix，它的思想是邻居聚合，主要的研究方向包括聚合函数、采样等等。

同时，在许多sequence-based任务中，注意力机制被广泛使用。因此，Spatial ConvGNN+Attention Mechanism就成了GAT的inspiration！

Contributions

计算高效性：
- self-attentional layer操作可以按edge实现并行；
- message aggregation操作可以按node实现并行；
- 多头之间可以实现并行；
- 不需要复杂的矩阵运算；
- a single GAT attention head的时间复杂度为：$O(|V|FF^‘+|E|F’)$
通过注意力机制，可以学习到每个邻居的importance weight
注意力机制不依赖于图的结构，是一种inductive的模型，具有很好的泛化性

Model：Graph Attentional Layer

Graph Attentional Layer

Graph Attentionnode feature的输入为：
$$
{\bf {h}} = \lbrace \vec h_1,\vec h_2,…,\vec h_N \rbrace$，$\vec h_i \in \mathbb R^F
$$
首先，用一个共享的线性变换模块，对每个点进行处理。线性变换模块的参数为： ${\bf W} \in \mathbb R^{F’ \times F}$，则所有点的feature变成：

$\left\{\mathbf{W}\vec{h}_{1}, \mathbf{W}\vec{h}_{2}, \ldots, \mathbf{W}\vec{h}_{N}\right\}, \mathbf{W}\vec{h}_{i} \in \mathbb{R}^{F^\prime} \\$

接下来就是常见的注意力机制操作，对节点$i$的邻居节点$j$计算注意力系数（节点$i$自己也算作自己的邻居节点）：

$e_{i j}=a\left(\mathbf{W} \vec{h}_{i}, \mathbf{W} \vec{h}_{j}\right), e_{ij} \in \mathbb{R}\\$

用$softmax$函数对$i$的所有邻居节点的注意力系数进行归一化操作有：

$\alpha_{i j}=\operatorname{softmax}_{j}\left(e_{i j}\right)=\frac{\exp \left(e_{i j}\right)}{\sum_{k \in \mathcal{N}_{i}} \exp \left(e_{i k}\right)} \\$

具体实现时，函数$a$为：

$a\left(\mathbf{W} \vec{h}_{i}, \mathbf{W} \vec{h}_{j}\right) = \mathbf{LeakyReLU}\left(\overrightarrow{\mathbf{a}}^{T}\left[\mathbf{W} \vec{h}_{i} \| \mathbf{W} \vec{h}_{j}\right]\right), \overrightarrow{\mathbf{a}} \in \mathbb{R}^{2 F^{\prime}} \\$

相当于将两个点的feature拼接起来后，用一个全连接层+leakyReLU进行处理。所以：

$\alpha_{i j}=\frac{\exp \left(\text { LeakyReLU }\left(\overrightarrow{\mathbf{a}}^{T}\left[\mathbf{W} \vec{h}_{i} | \mathbf{W} \vec{h}_{j}\right]\right)\right)}{\sum_{k \in \mathcal{N}_{i}} \exp \left(\text { LeakyReLU }\left(\overrightarrow{\mathbf{a}}^{T}\left[\mathbf{W} \vec{h}_{i} \| \mathbf{W} \vec{h}_{k}\right]\right)\right)} \\$

最后，对点 $i$的所有邻居点的feature（包含点 $i$本身），用 $\alpha$ 加权求和，并有激活函数$\sigma$处理，得到点$i$经过Graph Attention处理后的feature：

$\vec{h}_{i}^{\prime}=\sigma\left(\sum_{j \in \mathcal{N}_{i}} \alpha_{i j} \mathbf{W} \vec{h}_{j}\right) \\$

为增加训练过程的稳定性，可以使用 $\bf K$个Attention分支并行计算，最后将所有分支的结果拼接起来，或者求$\bf K$个分支的均值。

拼接 $\bf K$ 个分支：

$\vec{h}_{i}^{\prime}=\|_{k=1}^{K} \sigma\left(\sum_{j \in \mathcal{N}_{i}} \alpha_{i j}^{k} \mathbf{W}^{k} \vec{h}_{j}\right)$
求 $\bf K$ 个分支的均值：

$\vec{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} \vec{h}_{j}\right)$

Experiments

本篇论文的实验部分是值得深思的，它比较了许多知名的GNN模型。它将这些模型分为两大类：transductive和insductive。相应的数据集也分为transductive和insductive两种

Datasets

Transductive learning：

Cora
Citeseer
Pubmed

Inductive learning：

State-of-the-art methods

Transductive learning：

transductive

Inductive learning：

inductive

我的思考

下面三篇论文递进关系：
- Semi-Supervised Classification with Graph Convolutional Networks，ICLR 2017，图卷积网络 https://arxiv.org/abs/1609.02907
- Graph Attention Networks，ICLR 2018. 图注意力网络，就是此篇文章所解析的论文 https://arxiv.org/abs/1710.10903
- Relational Graph Attention Networks ，ICLR2019 关联性图注意力网络，整合了GCN+Attention+Relational
原论文在介绍的时候讲得非常清楚，连Dropout的probability都介绍了，所以原论文的实验部分还是值得仔细推敲，对自己以后做实验也有用！
我之前学习的GeniePath、SemiGNN、GraphConsis在聚合邻居的时候无不例外地都使用到了GAT（GEM并没有用GAT），说明GAT基本上是聚合邻居的基础操作了，那么基于GNN的金融反欺诈应该朝着哪里研究呢？

我觉得主要从数据出发，观察数据的特性（比如数据的异质性，数据的种类）。