文章目录
Graph U-Nets
会议：ICML 2019
Authors：Hongyang Gao, Shuiwang Ji
Departments: Texas A&M University
Recommend Score: 8.5 / 10.0
Keywords: graph classification, encoder-decoder, GCN, pooling
研究动机
受到2015年提出的U-Net（类似encoder-decoder，其中的计算模型是CNN）的启发，作者认为U-Net架构在image pixel-wise prediction任务上取得了很好的结果，但对于graph data却不适用，因为其中的pooling和unpooling操作不能直接适用于graph data。所以为了适应graph data，作者提出graph u-nets，设计了适合graph data 的pooling（gPool） 和 unpooling（gUnpool）。
主要内容
想要在graph data上进行pooling和unpooling具有挑战，因为在graph data不像是图像和文本，没有pooling操作需要的空间位置和顺序信息。
Graph U-Nets的架构如下：
其中，前半部分相当于encoder，图中表示有两个block，每个block中包含一个GCN和一个gPool。pooling层的目的与CNN中类似，是要减小feature map的size，扩大感受野，这样可以得到更好的泛化性和性能。具体graph pooling操作的图示为：
这一层的计算如下：
其中，p表示映射向量，也就是计算特征向量X在p上的映射值，是一个标量。rank操作返回k个映射值最大的node 的idx。第四个式子是说根据上一层所有节点的embedding矩阵，选择这一层仍然保留的节点的embedding，组成一个特征矩阵。第五个式子表示从上一层的邻接矩阵中，选择这一层仍然保留的那些节点的邻接关系，组成邻接矩阵。最后一个式子是：元素按位相乘的符号右边是将选中的n个节点对应的y值向量，变成一个矩阵，矩阵的每一行的元素都是一样的，比如：第一行就表示idx1节点在p上的映射值，组成了一个n* C的矩阵。按位相乘得到下一层的特征向量，主要操作是将上一层对应节点的embedding都乘以一个映射值。
后半部分相当于decoder，根据pooling之后得到的节点，保存的节点位置信息，恢复原来的graph结构。graph unpooling的操作图示为：
其中的GCN是获得节点embedding，gUnpool是要恢复上一层节点的结构，encoder和decoder层的对应block之间利用skip-connection。
skip connection叫做跳跃连接，通常用于残差网络中。作用是在比较深的网络中，解决在训练过程中梯度爆炸和梯度消失的问题。但这里的作用看着是恢复上一层的节点结构。
文中还有一点需要注意，在pooling的时候，每一层选择k个映射值最大的节点，作为下一层的GCN输入，但节点如果很少，就会导致连接性差，GCN进行表示可能效果不好。所以作者这里考虑二阶连接关系，也就是需要对gPool中的第五个式子进行一些改进，让它不仅包含一阶关系，还包含二阶关系。
本文的灵感来自于：U-Net，可以思考如何想到这个思路的，以及如何做的改进。
Hierarchical Graph Representation Learning with Differentiable Pooling
会议：NIPS 2018
Authors: Rex Ying, Jianxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, Jure Leskovee
Departments: Stanford University, TU Dortmund University, University of Southern California
研究动机
- 原始的GNN只是相当于一层CNN，只能在原本的图结构上做一次信息抽取，不能再在更粗粒度上做信息抽取。
- 对于graph classification任务来说，我们需要获取整个图的表示，但之前的方法基本是先获取每个节点的embedding，然后通过求平均或者其他方式得到整个图的embedding。但这种方式在整合的时候没有考虑到节点的结构信息。
研究内容
作者构建一个多层次的GNN网络。每一层中，不仅要完成信息抽取，还需要把当前的图聚合成一个更粗粒度的图，供下一层使用。也就是L层GNN+pooling的组合。这种方式在得到整个图的embedding的同时，还考虑了节点之间的结构信息。
具体步骤：
- 对于一个初始的图，首先利用GNN得到每个节点的embedding
- 根据簇分配矩阵（cluster assignment matrix）将节点分簇
- 分好的簇作为下一层的节点，再利用GNN得到embedding
- 重复以上步骤。
过程如图所示：
这其中还涉及到簇分配矩阵的计算，论文中是利用GNN计算，再经过softmax来得到值。这里是soft assignment。
在实验部分，作者想要验证三个问题：
- 提出的DiffPool是否有效果？
作者通过两方面进行比较，一方面是比较GNN+其他pooling的方法，一方面是STRUCTURE2VEC+其他pooling的方法比较。 - GNN+DiffPool的方法和其他graph classification的方法相比是否更好？
- DiffPool是否能够获得有意义的簇？
作者通过可视化两层中的cluster来说明。
优点：
- 改进了mean pooling，结合结构信息，对节点进行pooling操作，训练簇分配矩阵，实现节点从这一层分配到下一层的簇中的目的
- 实验设计的思路可以借鉴，非常完整。
不足之处：
- GNN+DiffPool的结构层数预先设定，模型配置中写的2层。这样的话，大规模的图如何处理？适应性不强。
- 每一层的簇的个数也是根据节点个数直接定义好的。hard definition。
可继续研究的点：
- 在引言部分，作者提到在graph上pooling的难点在于节点和边的个数不同。我想到节点的类型也不一定相同，目前有没有研究GNN用于异构图上的工作呢？
知乎讲解：DiffPool 论文讲解