论文解读（ChebyGIN）《Understanding Attention and Generalization in Graph Neural Networks》

论文信息

论文标题：Understanding Attention and Generalization in Graph Neural Networks
论文作者：Boris Knyazev, Graham W. Taylor, Mohamed R. Amer
论文来源：2019,NeurIPS
论文地址：download
论文代码：download

1 Introduction

　　本文关注将注意力 GNNs 推广到更大、更复杂或有噪声的图。作者发现在某些情况下，注意力机制的影响可以忽略不计，甚至有害，但在某些条件下，它给一些分类任务带来了超过 60% 的额外收益。

2 Attention meets pooling in graph neural networks

　　注意力机制可以用在边上，也可以用在节点上，传统的 GAT 是用在边上，本文更关注于节点上的注意力机制。

　　注意力机制在CNN里一般用以下公式表达：

　　　　Z=α⊙X(1)" role="presentation">Z=α⊙X(1)$Z=\alpha \odot X(1)$

　　其中:

• • X∈RN×C" role="presentation">X∈RN×C$X\in {\mathbb{R}}^{N\times C}$ 代表输入；
  • Zi=αiXi" role="presentation">Zi=αiXi$Z_i={\alpha }_i{X}_i$ 是使用注意力机制后的输出；
  • α" role="presentation">α$\alpha$ 是注意力系数，并有 ∑iNαi=1" role="presentation">∑Niαi=1$\sum _i^N{\alpha }_i=1$；

　　在 Graph U-Nets​ 的 Eq.2" role="presentation">Eq.2$\text{Eq.2}$ 中，同样使用到了注意力机制：

　　　　Zi={αiXi,∀i∈P∅, otherwise (2)" role="presentation">Zi={αiXi,∅,∀i∈P otherwise (2)$Z_i=\{\begin{array}{ll}{\alpha }_i{X}_i,& \mathrm{\forall }i\in P\\ \mathrm{\varnothing },& \text{ otherwise }\end{array}(2)$

　　其中：

• • P" role="presentation">P$P$ 是一组集合节点的索引，且有 |P|≤N" role="presentation">|P|≤N$|P|\le N$；
  • ∅" role="presentation">∅$\mathrm{\varnothing }$ 表示输出中不存在该单元；

　　本文的 Eq.2" role="presentation">Eq.2$\text{Eq.2}$ 和 Eq.1" role="presentation">Eq.1$\text{Eq.1}$ 的不同之处在于，在 Graph U-Nets 中 Z∈R|P|×C" role="presentation">Z∈R|P|×C$Z\in {\mathbb{R}}^{|P|\times C}$ 表明只使用了部分节点，即保存了 r=|P|/N≤1" role="presentation">r=|P|/N≤1$r=|P|/N\le 1$ 部分的节点。

　　本文设计了两个简单的图形推理任务，让我们在一个受控环境中研究注意力，了解地面真实注意力。第一个任务是计算图中的颜色，其中颜色是一个唯一的离散特征。第二个任务是计算图形中的三角形的数量。​我们在一个标准基准，MNIST[13]（Figure1）上证实了我们的观察结果，并确定了影响注意力有效性的因素。​

　　

3 Model

　　本文研究了两种GNNs：GCN 和 GIN，其中 GIN 将原有的 MEAN aggregator 替换为 SUM aggregator，然后使用一个 FC 层。

3.1 Thresholding by attention coefficients

　　使用 Graph U-Nets 中的方法，需要使用预定义的比率 r=|P|/N" role="presentation">r=|P|/N$r=|P|/N$  为整个数据集选择节点。比如对每个 pooling 设置 r = 0.8 即 80% 的节点被保存下来。直观地说，对于大小不同的图，这个比率应该是不同的。因此，建议选择阈值 α~" role="presentation">α~$\tilde{\alpha }$，这样就只传播具有注意值 αi>α~" role="presentation">αi>α~${\alpha }_i>\tilde{\alpha }$ 的节点：

　　　　Zi={αiXi,∀i:αi>α~∅, otherwise (3)" role="presentation">Zi={αiXi,∅,∀i:αi>α~ otherwise (3)$Z_i=\{\begin{array}{ll}{\alpha }_i{X}_i,& \mathrm{\forall }i:{\alpha }_i>\tilde{\alpha }\\ \mathrm{\varnothing },& \text{ otherwise }\end{array}(3)$

　　Note：图中删除的节点不同于保存的节点，其特征的值是非常小的，甚至为 0" role="presentation">0$0$。在本实验中，相近邻域的节点通常有相似 α" role="presentation">α$\alpha$ ，因此整个局部邻域被合并或者丢弃，而不是基于聚类的方法将每个邻域压缩为单个节点。

3.2 Attention subnetwork

　　为了训练一个预测节点系数的注意模型，我们考虑了两种方法：

• • Linear Projection[11]：只有单层投影 p∈RC" role="presentation">p∈RC$\mathbf{p}\in {\mathbb{R}}^C$ 需要被训练：αpre =Xp​" role="presentation">αpre =Xp​${\alpha }_{\text{pre }}=X\mathbf{p}$；
  • DiffPool[10]，其中训练了一个单独的 GNN：αpre =Xp​" role="presentation">αpre =Xp​${\alpha }_{\text{pre }}=X\mathbf{p}$；

　　在所有情况下，我们在[11]中使用 softmax 激活函数而不是 tanh，因为它提供了更可解释的结果和稀疏输出：α=softmax⁡(αpre)" role="presentation">α=softmax(αpre)$\alpha =\mathrm{softmax}\left({\alpha }_{pre}\right)$ 。为了以监督或弱监督的方式训练注意力，我们使用 KL 散度损失。

3.3 ChebyGIN

　　有些结果下，GCNs 和 GINs 表现的较差，本文将 GIN 和 ChebyNet 进行融合，研究了 K=2" role="presentation">K=2$K=2$ 的 ChebyGIN。

4 Experiments

4.1 Datasets

COLORS

　　本文引入了颜色计数任务，即统计图中绿色的节点有多少个，对于绿色节点设置 注意力系数为 αiGT=1/Ngreen " role="presentation">αGTi=1/Ngreen ${\alpha }_i^{GT}=1/N_{\text{green }}$。

TRIANGLES

　　统计图中有多少个三角形？显然一个简单 的方法是计算：trace⁡(A3)/6" role="presentation">trace(A3)/6$\mathrm{trace}\left(A^3\right)/6$ 。

　　接着对每个节点设置注意力系数：αiGT=Ti/∑iTi" role="presentation">αGTi=Ti/∑iTi${\alpha }_i^{GT}=T_i/\sum _i{T}_i$，其中 Ti" role="presentation">Ti$T_i$ 是多少个三角形包含节点 i" role="presentation">i$i$。

MNIST-75SP

 

　　该任务的目的是识别出图片代表的数字是多少，其中图片为 0−9" role="presentation">0−9$0-9$ 的数字。具体方法是先用 SLIC 算法生成超像素快，然后构建图。每个节点对应一个超像素块。然后 α" role="presentation">α$\alpha$ 系数的初始值的计算公式为：αiGT=1/Nnonzero " role="presentation">αGTi=1/Nnonzero ${\alpha }_i^{GT}=1/N_{\text{nonzero }}$ ，Nnonzero " role="presentation">Nnonzero $N_{\text{nonzero }}$ 是这些超像素的总数。

4.2 Generalization to larger and noisy graphs

　　为了验证注意力机制的健壮性，作者将颜色实验和三角形实验引入到更大的网络之中。如图：

　　

　　在颜色实验中添加了另外一个通道，变成 4" role="presentation">4$4$ 个通道 [ c_1,c_2,c_3,c_3 ]，然后其中 [0,1,0,0] 的时候代表绿色，其他的时候 [c1,0,c3,c4]" role="presentation">[c1,0,c3,c4]$[c_1,0,c_3,c_4]$ 其中 c1" role="presentation">c1$c_1$，c3" role="presentation">c3$c_3$，c4" role="presentation">c4$c_4$，可以是 0−1" role="presentation">0−1$0-1$ 之间的数值，代表红色，蓝色，透明色的三种颜色的混合。

　　在三角形计数实验中，也引入了更多的节点数。

　　在MNIST数据集的实验中，加入了高斯噪音，是的模型的识别度更高。

4.3 Network architectures and training

　　对于 COLORS 和 TRIANGLES，我们最小化了其他任务的回归损失(MSE)和交叉熵(CE)，对于有监督和弱监督实验，本文还最小化了 ground truth attention αGT" role="presentation">αGT${\alpha }^{GT}$ 和 predicted coefficients α" role="presentation">α$\alpha$ 之间的 KL 散度。

　　　　L=LMSE/CE+βN∑iαiGTlog⁡(αiGTαi)(5)" role="presentation">L=LMSE/CE+βN∑iαGTilog(αGTiαi)(5)$\mathcal{L}={\mathcal{L}}_{MSE/CE}+\frac{\beta }{N}\sum _i{\alpha }_i^{GT}\log \left(\frac{{\alpha }_i^{GT}}{{\alpha }_i}\right)(5)$

　　为了评估注意力系数的正确性，遵循CNN的方式，我们在训练完一个模型之后呢，移除这个节点，再计算预测一个标签，计算与原始标签的差异，这样来计算出一个评估的 α" role="presentation">α$\alpha$ 系数：

　　　　αiWS=|yi−y|∑j=1N|yj−y|" role="presentation">αWSi=|yi−y|∑j=1N∣∣yj−y∣∣${\alpha }_i^{WS}=\frac{|y_i-y|}{\sum _{j=1}^N|y_j-y|}$

5 Experiments

　　

 

6 Conclusion

　　证明了注意力对于图神经网络是非常强大的，但是由于初始注意力系数的敏感性，要达到最优是很困难的。特别是在无监督的环境中，由于不能确定初始注意力系数的值，使得这样的训练更加困难。我们还表明，注意力可以使GNN对更大，更嘈杂的图形有更强的能力。同时本文提出的弱监督模型和有监督模型具有相似的优势性。

 

• 论文信息
• 1 Introduction
• 2 Attention meets pooling in graph neural networks
• 3 Model
•     3.1 Thresholding by attention coefficients
•     3.2 Attention subnetwork
•     3.3 ChebyGIN
• 4 Experiments
•     4.1 Datasets
•     4.2 Generalization to larger and noisy graphs
•     4.3 Network architectures and training
• 5 Experiments
• 6 Conclusion

__EOF__