论文解读（GATv2）《How Attentive are Graph Attention Networks?》

论文信息

论文标题：How Attentive are Graph Attention Networks?
论文作者：Shaked Brody, Uri Alon, Eran Yahav
论文来源：2022,ICLR
论文地址：download 
论文代码：download

1 Abstract

　　在 GAT中，每个节点都为它的邻居给出自己的查询表示。然而，在本文中证明了 GAT 计算的是一种非常有限的注意类型：注意力分数在查询节点上是无条件的。本文将其定义为静态注意力，并提出了相应的动态注意力 GATv2。

2 Introduction

　　静态注意力：对于任何 query nodes，注意函数相对于邻域（key）分数是单调的。即：注意系数的排序在图中的所有节点上共享，并且在查询节点上不受条件的影响。如 Figure1 所示：

　　对于一组固定的 keys，如果不同的 query 对这组 keys 进行 attention，得到的注意力系数相对不变，那么这个注意力系数计算函数就是静态的。如下面的左图所示，GATv1 就是静态的，也就是无论 q 怎么变（q0-q9），一直是 k8 对应的 attention 最大，改进版本 GATv2 解决了这个问题。

　　

3 Preliminaries

3.1 Graph neural networks

　　　　hi′=fθ(hi, AGGREGATE ({hj∣j∈Ni}))(1)" role="presentation">h′i=fθ(hi, AGGREGATE ({hj∣j∈Ni}))(1)${\mathit{h}}_i^{\mathrm{\prime }}=f_{\theta }({\mathit{h}}_i,\text{ AGGREGATE }\left(\{{\mathit{h}}_j\mid j\in {\mathcal{N}}_i\}\right))(1)$

3.2 Graph attention networks

　　表示邻居 j" role="presentation">j$j$ 的特征对节点 i" role="presentation">i$i$ 的重要性：

　　　　e(hi,hj)= LeakyReLU (a⊤⋅[Whi‖Whj])(2)" role="presentation">e(hi,hj)= LeakyReLU (a⊤⋅[Whi∥Whj])(2)$e({\mathit{h}}_i,{\mathit{h}}_j)=\text{ LeakyReLU }({\mathit{a}}^{\mathrm{\top }}\cdot [\mathit{W}{\mathit{h}}_i\Vert \mathit{W}{\mathit{h}}_j])(2)$

　　注意函数的定义为：

　　　　αij=softmaxj⁡(e(hi,hj))=exp⁡(e(hi,hj))∑j′∈Niexp⁡(e(hi,hj′))(3)" role="presentation">αij=softmaxj(e(hi,hj))=exp(e(hi,hj))∑j′∈Niexp(e(hi,hj′))(3)${\alpha }_{ij}={\mathrm{softmax}}_j\left(e({\mathit{h}}_i,{\mathit{h}}_j)\right)=\frac{\exp \left(e({\mathit{h}}_i,{\mathit{h}}_j)\right)}{\sum _{j^{\mathrm{\prime }}\in {\mathcal{N}}_i}\exp \left(e({\mathit{h}}_i,{\mathit{h}}_{j^{\mathrm{\prime }}})\right)}(3)$

　　然后，GAT计算相邻节点的变换特征的加权平均值（然后是一个非线性 σ" role="presentation">σ$\sigma$）作为 i" role="presentation">i$i$ 的新表示，使用归一化注意系数：

　　　　hi′=σ(∑j∈Niαij⋅Whj)(4)" role="presentation">h′i=σ(∑j∈Niαij⋅Whj)(4)${\mathit{h}}_i^{\mathrm{\prime }}=\sigma (\sum _{j\in {\mathcal{N}}_i}{\alpha }_{ij}\cdot \mathit{W}{\mathit{h}}_j)(4)$

4 The expressive power of graph attention mechanisms

4.1 The importance of dynamic weighting

　　给定一个查询向量，如果注意力函数总是对一个键的权重至少和任何其他键一样大，而无需进行查询，就说这个注意函数是静态的：

　　Definition 3.1 (Static attention). A (possibly infinite) family of scoring functions F⊆(Rd×Rd→R)" role="presentation">F⊆(Rd×Rd→R)$\mathcal{F}\subseteq ({\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R})$ computes static scoring for a given set of key vectors K={k1,…,kn}⊂Rd" role="presentation">K={k1,…,kn}⊂Rd$\mathbb{K}=\{{\mathit{k}}_1,\dots ,{\mathit{k}}_n\}\subset {\mathbb{R}}^d$ and query vectors Q={q1,…,qm}⊂Rd" role="presentation">Q={q1,…,qm}⊂Rd$\mathbb{Q}=\{{\mathit{q}}_1,\dots ,{\mathit{q}}_m\}\subset {\mathbb{R}}^d$ , if for every f∈F" role="presentation">f∈F$f\in \mathcal{F}$ there exists a "highest scoring" key jf∈[n]" role="presentation">jf∈[n]$j_f\in [n]$ such that for every query i∈[m]" role="presentation">i∈[m]$i\in [m]$ and key j∈[n]" role="presentation">j∈[n]$j\in [n]$ it holds that f(qi,kjf)≥f(qi,kj)" role="presentation">f(qi,kjf)≥f(qi,kj)$f({\mathit{q}}_i,{\mathit{k}}_{j_f})\ge f({\mathit{q}}_i,{\mathit{k}}_j)$ . We say that a family of attention functions computes static attention given K" role="presentation">K$\mathbb{K}$ and Q" role="presentation">Q$\mathbb{Q}$ , if its scoring function computes static scoring, possibly followed by monotonic normalization such as softmax.

　　对动态注意力机制的定义：

　　Definition  3.2  (Dynamic attention). A (possibly infinite) family of scoring functions  F⊆(Rd×Rd→R)" role="presentation">F⊆(Rd×Rd→R)$\mathcal{F}\subseteq ({\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R})$  computes dynamic scoring for a given set of key vectors  K={k1,…,kn}⊂Rd" role="presentation">K={k1,…,kn}⊂Rd$\mathbb{K}=\{{\mathit{k}}_1,\dots ,{\mathit{k}}_n\}\subset {\mathbb{R}}^d$  and query vectors  Q={q1,…,qm}⊂Rd" role="presentation">Q={q1,…,qm}⊂Rd$\mathbb{Q}=\{{\mathit{q}}_1,\dots ,{\mathit{q}}_m\}\subset {\mathbb{R}}^d$ , if for any mapping  φ:[m]→[n]" role="presentation">φ:[m]→[n]$\phi :[m]\to [n]$  there exists  f∈F" role="presentation">f∈F$f\in \mathcal{F}$  such that for any query  i∈[m]" role="presentation">i∈[m]$i\in [m]$  and any key  j≠φ(i)∈[n]:f(qi,kφ(i))>f(qi,kj)" role="presentation">j≠φ(i)∈[n]:f(qi,kφ(i))>f(qi,kj)$j_{\ne \phi (i)}\in [n]:f({\mathit{q}}_i,{\mathit{k}}_{\phi (i)})>f({\mathit{q}}_i,{\mathit{k}}_j)$ . We say that a family of attention functions computes dynamic attention for  K" role="presentation">K$\mathbb{K}$  and  Q" role="presentation">Q$\mathbb{Q}$ , if its scoring function computes dynamic scoring, possibly followed by monotonic normalization such as softmax.

Attending by decaying

　　提高注意力系数的方法可以考虑衰减其他 key 的注意力权重，不一定得增加自身所关心的 key 注意力权重。

4.2 The limited expressivity of GAT

　　Theorem 1. A GAT layer computes only static attention, for any set of node representations  K=Q={h1,…,hn}" role="presentation">K=Q={h1,…,hn}$\mathbb{K}=\mathbb{Q}=\{{\mathit{h}}_1,\dots ,{\mathit{h}}_n\}$ . In particular, for  n>1" role="presentation">n>1$n>1$ , a GAT layer does not compute dynamic attention.

　　证明：

　　

　　Theorem 1 的结果是，节点集 V" role="presentation">V$\mathcal{V}$ 中存在一个 sj=a2⊤Whj" role="presentation">sj=a⊤2Whj$s_j={\mathit{a}}_2^{\mathrm{\top }}\mathit{W}{\mathit{h}}_j$ 使得 节点 j" role="presentation">j$j$ 的全局排名最高，那么造成的结果就是 节点 j" role="presentation">j$j$ 的局部领域 Ni" role="presentation">Ni${\mathcal{N}}_i$ 排名也最高。hi" role="presentation">hi${\mathit{h}}_i$ 的唯一影响是在所产生的注意力分布的 “sharpness” 上。这在 Figure 1a（bottom）中得到了演示，其中不同的曲线表示不同的 query (hi)" role="presentation">(hi)$\left({\mathit{h}}_i\right)$。

Generalization to multi-head attention

　　对于多头注意力机制，Theorem 1 同样适用于每个头。

4.3 Building dynamic graph attention networks

GATv2

　　standard GAT 评分函数（Eq.2" role="presentation">Eq.2$\text{Eq.2}$）的主要问题是学习到的 W" role="presentation">W$\mathit{W}$ 和 a" role="presentation">a$\mathit{a}$ 是连续应用的，因此可以分解成一个单一的线性层。为了解决这个限制，我们简单地在非线性之后应用一层(LeakyReLU)，在连接之后应用 W" role="presentation">W$\mathit{W}$，有效地应用一个MLP来计算每个查询键对的分数：

　　GAT ：  e(hi,hj)=LeakyReLU(a⊤⋅[Whi‖Whj])" role="presentation">e(hi,hj)=LeakyReLU(a⊤⋅[Whi∥Whj])$e({\mathit{h}}_i,{\mathit{h}}_j)=\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{a}}^{\mathrm{\top }}\cdot [\mathit{W}{\mathit{h}}_i\Vert \mathit{W}{\mathit{h}}_j])$

　　GATv2：e(hi,hj)=a⊤LeakyReLU⁡(W⋅[hi‖hj])" role="presentation">e(hi,hj)=a⊤LeakyReLU(W⋅[hi∥hj])$e({\mathit{h}}_i,{\mathit{h}}_j)={\mathit{a}}^{\mathrm{\top }}\mathrm{LeakyReLU}(\mathit{W}\cdot [{\mathit{h}}_i\Vert {\mathit{h}}_j])$

Complexity

时间复杂度

　　GAT：O(|V|dd′+|E|d′)" role="presentation">O(|V|dd′+|E|d′)$\mathcal{O}(|\mathcal{V}|d{d}^{\mathrm{\prime }}+|\mathcal{E}|d^{\mathrm{\prime }})$　　

　　GATv2：O(|V|dd′+|E|d′)" role="presentation">O(|V|dd′+|E|d′)$\mathcal{O}(|\mathcal{V}|d{d}^{\mathrm{\prime }}+|\mathcal{E}|d^{\mathrm{\prime }})$

参数复杂度

　　

5 Evaluation

5.1 Synthetic benchmark:DICTIONARYLOOKUP

　　本节在条形码预测问题上验证 GAT v2 的有效性。

　　

　　对比一下 GIN：

　　

Visualization

　　同样对于 条形码预测问题 ，其可视化结果如下：

　　

The role of multi-head attention

　　提了一嘴，说多头注意力是稳定学习过程的一种方法，但是呢，你可以想想每对节点对有多个注意力系数是不是很难解释？反正有人吐槽过这一点。

　　下图也有说明了 多头注意力并不是在所有数据集上都有效。

5.2 Robustness to noise

　　我们研究了动态注意和静态对噪声的注意的鲁棒性。特别地，我们关注结构噪声：给定一个输入图 G=(V,E)" role="presentation">G=(V,E)$\mathcal{G}=(\mathcal{V},\mathcal{E})$ 和一个噪声比为 0≤p≤1" role="presentation">0≤p≤1$0\le p\le 1$，我们从 V×V∖E" role="presentation">V×V∖E$\mathcal{V}\times \mathcal{V}\mathrm{\setminus }\mathcal{E}$ 中随机抽取 |E|×p" role="presentation">|E|×p$|\mathcal{E}|\times p$ 不存在的边 E′" role="presentation">E′${\mathcal{E}}^{\mathrm{\prime }}$。然后，我们在有噪声的图 G′=(V,E∪E′)" role="presentation">G′=(V,E∪E′)${\mathcal{G}}^{\mathrm{\prime }}=(\mathcal{V},\mathcal{E}\cup {\mathcal{E}}^{\mathrm{\prime }})$ 上训练GNN。

　　

5.3 Programs:Varmisuse

　　验证在 Varmisuse 的结果：

　　

5.4 Node-prediction

　　

5.5 Graph-prediction:QM9

　　

5.6 link-prediction

　　

5.7 Discussion

　　在所有被检查的基准测试中，我们发现 GATv2 比 GAT 更准确。此外，我们发现 GATv2 对噪声的鲁棒性明显高于 GAT。在条形码预测基准测试中，GAT 不能表达数据，因此甚至能达到较差的训练精度。

Which graph attention mechanism should I use?

　　通常不可能预先确定哪种体系结构的性能最好。一个理论上较弱的模型在实践中可能表现得更好，因为如果任务 “easy-to-overfit” 且不需要这样的表达能力，那么一个更强的模型可能会过度拟合训练数据。直观地说，我们认为节点之间的相互作用越复杂，GNN从理论上更强的图注意机制中获得的好处就越大。主要的问题是问题是否有“有影响力 ”节点的全局排名(GAT就足够了)，或者不同的节点有不同的邻居排名(使用GATv2)。

　　GAT的作者在 Twitter 上证实，GAT 被设计用于当时的 “容易过拟合” 的数据集，如 Cora，Citeseer 和 Pubmed，在那里，数据可能有一个 “globally important” 节点的潜在静态排名。更新和更具挑战性的基准测试可能需要更强的注意机制，如GATv2。在本文中，我们回顾了传统的假设，并表明许多现代图基准和数据集包含更复杂的交互，因此需要动态的关注。

6 Conclusion

 　　在本文中，我们发现流行和广泛使用的图注意网络不计算动态注意。相反，GAT的标准定义和实现中的注意机制只是静态的：对于任何查询，它的邻居评分对于每个节点的分数都是单调的。因此，GAT甚至不能表达简单的对齐问题。为了解决这一限制，我们引入了一个简单的修复并提出了GATv2：通过修改GAT中的操作顺序，GATv2实现了一个通用的近似注意函数，因此严格比GAT更强大。

　　我们在一个需要动态选择节点的综合问题中，展示了GATv2相对于GAT的经验优势，以及来自OGB和其他公共数据集的11个基准测试。我们的实验表明，在具有相同参数成本的情况下，GATv2在所有基准测试中都优于GAT。

 

• 论文信息
• 1 Abstract
• 2 Introduction
• 3 Preliminaries
•     3.1 Graph neural networks
•     3.2 Graph attention networks
• 4 The expressive power of graph attention mechanisms
•     4.1 The importance of dynamic weighting
•     4.2 The limited expressivity of GAT
•     4.3 Building dynamic graph attention networks
• 5 Evaluation
•     5.1 Synthetic benchmark:DICTIONARYLOOKUP
•     5.2 Robustness to noise
•     5.3 Programs:Varmisuse
•     5.4 Node-prediction
•     5.5 Graph-prediction:QM9
•     5.6 link-prediction
•     5.7 Discussion
• 6 Conclusion

__EOF__