Graph Attention Networks[ICLR'18]

ICLR18一篇解决GCN聚合信息时无法区分信息重要性的论文

解决的问题

如何将attention机制应用于图类型的数据上。

做法及创新

图卷积

1 2

给定一个含$n$个顶点的图,其中顶点的特征构成的集合为$(\overrightarrow{h_1},\overrightarrow{h_2},\dots,\overrightarrow{h_n})$,$\overrightarrow{h_i}\in \mathbb{R}^F$且邻接矩阵为$A$。一个图卷积层根据已有的顶点特征和图的结构来计算一个新的特征集合$(\overrightarrow{h_1’},\overrightarrow{h_2’},\dots,\overrightarrow{h_n’})$,$\overrightarrow{h_i’}\in \mathbb{R}^{F’}$

每个图卷积层首先会进行特征转换,以特征矩阵$W$表示,$W\in \mathbb{R}^{F’\times F}$它将特征向量线性转换为$\overrightarrow{g_i}=W\overrightarrow{h_i}$,再将新得到的特征向量以某种方式进行结合。为了利用邻域的信息,一种典型的做法如下:

其中$N_i$表示顶点$i$的邻域(典型的构造方式是选取直接相连的顶点,包括自身),$\alpha_{ij}$表示顶点$j$的特征对于顶点$i$的重要程度,也可以看成一种权重。

现有的做法都是显式地定义$\alpha_{ij}$,本文的创新之处在于使用attention机制隐式地定义$\alpha_{ij}$。所使用的attention机制定义为$a:R^{F’}\times \mathbb{R}^{F’} \rightarrow \mathbb{R}$,以一个权重向量$\overrightarrow{a}\in \mathbb{R}^{2F’}$表示,对应于论文中的self-attention。

Self-attention

  1. 基于顶点的特征计算系数$e_{ij}$
  1. 以顶点的邻域将上一步计算得到的系数正则化,这么做能引入图的结构信息:

0H5cX6.png

次序不变性:给定$(i,j),(i,k),(i’,j),(i’,k)$表示两个顶点间的关系,可以为边或自环。$a$为对应的attention系数,如果$a_{ij}>a_{ik}$,则有$a_{i’j}>a_{i’k}$

DeepInf中给出了证明:

​ 将权重向量$\overrightarrow{a}\in \mathbb{R}^{2F’}$重写为$\overrightarrow{a}=[p^T,q^T]$,则有

​ 由softmax与LeakyReLU的单调性可知,因为$a_{ij}>a_{ik}$,有$q^TWh_j>q^TWh_k$,类似地就可以得到$a_{i’j}>a_{i’k}$。

​ 这意味着,即使每个顶点都只关注于自己的邻域,但得到的attention系数却具有全局性。

  1. 以上一步得到的系数$\alpha_{ij}$作为顶点$j$的特征对顶点$i$的重要程度,将领域中各顶点的特征做一个线性组合以作为顶点$i$最终输出的特征表示:

Multi-head attention

为了稳定self-attention的学习过程,论文引入了multi-head attention,即由$K$个相互独立的self-attention得到各自的特征,再进行拼接:

0HbZlj.png

其中$\alpha_{ij}^k$是第$k$个attention机制$(a^k)$计算出来的正则化系数,$W^k$是对应的将输入进行线性转化的权重矩阵。论文选取的拼接操作为求平均:

数据集

Cora、Citeseer、Pubmed、PPI