图池化经典之作: 18NIPS DiffPool

作者: 张楚珩

单位: 清华大学交叉信息研究院

原文链接: https://zhuanlan.zhihu.com/p/106214278

DiffPool: Differentiable Pooling介绍了一种聚合图中的节点，从而学习到包含层级信息的图表示。

原文传送门

Ying, Zhitao, et al. "Hierarchical graph representation learning with differentiable pooling." Advances in neural information processing systems. 2018.

1. 背景

图上的机器学习问题有这么几大类：node classification、link prediction、graph classification，分别对应对于图上节点和连边信息的提取，以及对于整个图全局信息的提取。图神经网络里面一类最重要的框架就是 neural message passing [1]，通过将图上的节点和邻近节点相互交互，从而实现对于图结构的信息抽取。如果我们是做 node classification 或者 link prediction，那么可以直接将相应的局部特征提取出来就可以了，但是如果要做 graph classification，那么接着还需要对于整个图的全局信息进行聚合。之前做法的方式是直接聚合，比如把所有节点的特征加合起来，而忽略了各个节点之间可能的复杂层次关系；也有方法提出采取分开的两步，即先做 message passing，再做 graph clustering。如果把 GNN 和 CNN 网络对比，会发现这之前的 GNN 只是相当于一层的 CNN，只能在原本的图结构上做一次信息抽取，不能再在更粗的粒度上做信息抽取。

这里提出的方法就是要构建一个多层次的 GNN 网络，在每一层中，不仅需要完成信息的抽取（在图上进行多次信息传递），而且需要把当前的图聚合为一个更粗粒度的图，供下一层使用。类比 CNN，在 CNN 中，图信息的聚合是自然完成的，因为在图片里面距离近的像素具有天然的临近关系，可以直接 MaxPooling、AvgPooling 等办法完成聚合；而在一般的图里面这件事情就比较困难了。文章这里提出如下图所示的框架，在做完之前的 GNN 操作之后，再利用这里提出的 DiffPool 方法自动聚合节点，然后把新聚合出来的节点当做新的图再利用之前的 GNN 算法来抽取信息，如此多层信息抽取，最后得到一个单一节点的特征。最后利用这个单一节点的特征来做 graph classification。

3. 算法

4. 正则化

到此为止，一切看起来都挺合理并且也很自然，但是一般这样简单的方案实际中肯定很难有效，因为这个方案自由度还挺大的，学起来并不容易，光看公式 (3) 和 (4) 就知道，矩阵乘法里面很多部分都需要学习。因此，要使得这个方案能够有效，就需要加上一些正则化项，避免它学成我们不想要的结果。

参考文献

[1] Gilmer, Justin, et al. "Neural message passing for quantum chemistry." Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.