ICML2019 Self-Attention Graph Pooling

本文转载自知乎专栏: NLP入门论文解析 作者: Taki https://zhuanlan.zhihu.com/p/104837556

小编语: 经典的CNN架构通常包含卷积层和池化层. GNN将CNN泛化到了图数据上,在很多领域得到了广泛的应用.但是,目前的GNN主要关注如何定义节点的邻居并聚合邻居信息(也就是卷积层的设计),对于池化并没有较多的关注. 那么,图上的池化层该怎么来做呢?有什么独特的挑战呢?

Links：arxiv.org/abs/1904.0808

Github：github.com/inyeoplee77/

Conference：ICML2019

0 Abstrcat

将深度学习的框架迁移到结构化的数据近期也是个热点，近期的一些学习都在将卷积+pool迁移到非结构化的数据中【模仿CNN，目前LSTM，GRU还没有人模仿】，将卷积操作迁移到Graph中已经被证明是有效的，但是在Graph中downsampling依旧是一个挑战性的问题，上篇论文也研究了Graph Pool【link】。在这篇论文，我们提出了一种基于self-attention的graph pool方法，我们的pool方法包括node feature/graph topology两个特征，为了公平，我们使用一样的训练过程以及模型结构，实验结果证明我们的方法在Graph classification中表现的好。

1 Introduction

深度学习的方法在数据的识别和增强等方面有突飞猛进。特别，CNNs成功地挖掘了数据的特征，例如 欧几里得空间的images，speech，video。CNNs包括卷积层和下采样层，卷积和池化操作都有 shift-invariance特性（也叫作 stationary property）。因此CNNs只需要很小的参数就可以获得较好的结果。

在很多领域，然而，大量的数据，都是以非欧数据的形式储存的，例如 Social Network，Biological network，Molecular structure都是通过Graph中的Node以及Edge的形式表示的，因此很多人尝试将CNN迁移到非欧空间数据上。

在Graph Pool领域，方法远远少于Graph Convolution，之前的方法只考虑了Graph topology，还有其他的方法，希望获得一个更小点的Graph表示，最近，也有一些方法希望学习Graph的结构信息，这些方法允许GNNs用一种End2End的方法。然而，这些池化方法都还有提升空间，譬如需要立方级别的存储复杂度，Gao & Ji 的方法[link]解决了复杂度的问题，但是没有考虑图的拓扑结构。

由此我们提出了一种 SAGPool模型，是一种 Self-Attention Graph Pooling method，我们的方法可以用一种End2End的方式学习结构层次信息，Self-attention结构可以区分哪些节点应该丢弃，哪些应该保留。因为Self-attention结构使用了Graph convolution来计算attention分数，Node features以及Graph topology都被考虑进去，简而言之，SAGPool继承了之前模型的优点，也是第一个将self-attention 加入Graph pooling中，实现了较高的准确度。

2 Related Work

2.1 Graph Convolution

Graph卷积在之前文章里说了很多了。主要是Spectral/Spatial两个领域，Spatial领域的卷积主要是直接在Graph中计算，中心节点通过邻接矩阵接受邻居节点的信息。Hamilton et al提出了GraphSAGE，通过采样传递信息学习节点的embedding。但是GraphSAGE是在一个固定大小的邻居域内操作，而GAT模型是根据attention结构，计算节点所有的邻居，然后信息传递直到稳态（stationary）。

2.2 Graph Pooling

Pooling layer让CNN结构能够减少参数的数量【只需要卷积核内的参数】，从而避免了过拟合，为了使用CNNs，学习GNN中的pool操作是很有必要的，Graph pool的方法主要为三种：topology based，global，hierarchical pooling。

Topology based pooling。早先的工作使用Graph coarsening 算法，而不是神经网络。谱聚类方法使用特征值分解来获得粗化图，但是特征值分解是一个花费算力的过程，Graclus不需要特征值，使用介于general spectral clustering objective and a weighted kernel k-means objective方法。

Global pooling。不想之前的方法，global pool方法考虑Graph feature，使用summation or neural networks在每一个layer pool所有的节点表示，不同结构的图都适用，因为这个方法一次性处理所有的representations。Gilmer et al. 将GNNs看做信息传递的结构，提供了一个通用的结构，可以使用Set2Set来初始化进而获得Entire Graph的表示。SortPool根据在结构中的角色来给节点的embedding 分类，然后将排序后的embedding传递到下一层。

3. Proposed Method

SAGPool的key points是使用GNN来计算self-attention scores。在3.1结构我们详细叙述了SAGPool的结构以及它们的变体。3.2中详细解释了模型的结构，SAGPool layer和模型结构在Fig 1和Fig 2中展示出来。

3.1 Self-Attention Graph Pooling

Global pooling architecture 使用一个Global pooling结构，如Fig 2所示

Global pooling结构包含三个卷积层，将它们的输出连接起来。Node features在readout layer+pooling layer之下流动，Graph feature representions之后传输到线形层做分类。

Hierarchical pooling architecture 在这个设置下，如Fig 2所示那样，做一次卷积，做一次pooling，最后将三次pooling的结果加起来使用MLP来分类。

4. Experiments

使用Graph分类问题来测试global pooling/hierarchical pooling方法。在4.1讨论了evaluation的数据集，4.3描述了我们怎么训练模型，结果的比较在4.4/4.5中描述。

4.1. Datasets

Graph中节点超过1K的benchmark datasets共有5个节点，datasets的数据在Table 1中描述。

4.3 Training Procedures

Shchur et al 证明数据集的不同分割可能会影响GNN模型的表现。在我们的实验里，我们使用10-fold cross validation，使用20个随机种子，每个数据集一共得到200个实验结果。在训练的时候，10%的训练数据用来做验证。使用Adam optimizer，early stoping。如果每50轮后validation准确率没有明显提升就停止训练，最多训练100K轮次。使用grid search的方式来确定参数。

4.4 Baselines

4.6 Summary of Results

结果是如Table 3/Table 4所示。可以看出SAGPool表现不错。

5. Analysis

在这个部分，我们提供了实验结果的分析。

5.1 Global and Hierarchical Pooling

很难说哪种结构更好，POOLg最小化了信息的loss，在节点数较少的数据集【NCI1，NCI109，FRANKENSTEIN】上表现更好，然而，POOLh在节点数多的数据集上表现更好【D&D，PROTEINS】，因为POOLh在提取large scale graphs信息方面更拿手。不过，SAGPool比其他的模型更好。

5.2 Effect of Considering Graph Topology

SAGPool使用的是第一阶近似，这也就允许SAGPool考虑图的拓扑结构。正如Table 3，考虑图的拓扑结构表现更好。此外，graph Laplacian不需要重新计算，因为可以从相同位置的Graph Convolution layer传递过来。当SAGPool和gPool一样的参数，SAGPool在图分类问题上表现更好。

5.3 Sparse Implementation

邻接矩阵经常是稀疏的，所以Manipulating graph data with a sparse matrix非常重要。使用sparse martix可以降低内存复杂度和时间复杂度。

5.4 Relation with the Number of Nodes

在DiffPool中，cluster zise需要重新定义，因为GNN使用了matrix S。cluster size需要设置合适，否则会导致2个问题。1）参数的数量和最大节点数是相关的。

2）当Graph的大小不一的时候，很难决定合适的cluster size。

5.5 Comparison of the SAGPool Variants

省略

5.6 Limitations

我们在模型中使用了pooling ratio k，来处理不同的various size。在SAGPool，我们难以量化这个比例K，为了解决这个问题，我们使用二分类来觉得节点的保留与否，但是这没有解决问题。

6 Conclusion

老生常谈。