论文笔记 | Graph Pooling

文章目录

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的架构如下:
论文笔记 | Graph Pooling

其中,前半部分相当于encoder,图中表示有两个block,每个block中包含一个GCN和一个gPool。pooling层的目的与CNN中类似,是要减小feature map的size,扩大感受野,这样可以得到更好的泛化性和性能。具体graph pooling操作的图示为:
论文笔记 | Graph Pooling

这一层的计算如下:
论文笔记 | Graph Pooling

其中,p表示映射向量,也就是计算特征向量X在p上的映射值,是一个标量。rank操作返回k个映射值最大的node 的idx。第四个式子是说根据上一层所有节点的embedding矩阵,选择这一层仍然保留的节点的embedding,组成一个特征矩阵。第五个式子表示从上一层的邻接矩阵中,选择这一层仍然保留的那些节点的邻接关系,组成邻接矩阵。最后一个式子是:元素按位相乘的符号右边是将选中的n个节点对应的y值向量,变成一个矩阵,矩阵的每一行的元素都是一样的,比如:第一行就表示idx1节点在p上的映射值,组成了一个n* C的矩阵。按位相乘得到下一层的特征向量,主要操作是将上一层对应节点的embedding都乘以一个映射值。

后半部分相当于decoder,根据pooling之后得到的节点,保存的节点位置信息,恢复原来的graph结构。graph unpooling的操作图示为:
论文笔记 | Graph Pooling

其中的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

研究动机

  1. 原始的GNN只是相当于一层CNN,只能在原本的图结构上做一次信息抽取,不能再在更粗粒度上做信息抽取。
  2. 对于graph classification任务来说,我们需要获取整个图的表示,但之前的方法基本是先获取每个节点的embedding,然后通过求平均或者其他方式得到整个图的embedding。但这种方式在整合的时候没有考虑到节点的结构信息。

研究内容

作者构建一个多层次的GNN网络。每一层中,不仅要完成信息抽取,还需要把当前的图聚合成一个更粗粒度的图,供下一层使用。也就是L层GNN+pooling的组合。这种方式在得到整个图的embedding的同时,还考虑了节点之间的结构信息。

具体步骤:

  1. 对于一个初始的图,首先利用GNN得到每个节点的embedding
  2. 根据簇分配矩阵(cluster assignment matrix)将节点分簇
  3. 分好的簇作为下一层的节点,再利用GNN得到embedding
  4. 重复以上步骤。

过程如图所示:

论文笔记 | Graph Pooling

这其中还涉及到簇分配矩阵的计算,论文中是利用GNN计算,再经过softmax来得到值。这里是soft assignment。

在实验部分,作者想要验证三个问题:

  1. 提出的DiffPool是否有效果?
    作者通过两方面进行比较,一方面是比较GNN+其他pooling的方法,一方面是STRUCTURE2VEC+其他pooling的方法比较。
  2. GNN+DiffPool的方法和其他graph classification的方法相比是否更好?
  3. DiffPool是否能够获得有意义的簇?
    作者通过可视化两层中的cluster来说明。

优点:

  1. 改进了mean pooling,结合结构信息,对节点进行pooling操作,训练簇分配矩阵,实现节点从这一层分配到下一层的簇中的目的
  2. 实验设计的思路可以借鉴,非常完整。

不足之处:

  1. GNN+DiffPool的结构层数预先设定,模型配置中写的2层。这样的话,大规模的图如何处理?适应性不强。
  2. 每一层的簇的个数也是根据节点个数直接定义好的。hard definition。

可继续研究的点:

  1. 在引言部分,作者提到在graph上pooling的难点在于节点和边的个数不同。我想到节点的类型也不一定相同,目前有没有研究GNN用于异构图上的工作呢?

知乎讲解:DiffPool 论文讲解

上一篇:图推荐算法在E&E问题上的应用


下一篇:推荐系统 - 排序算法 - 神经网络:WDL