图神经网络+池化模块，斯坦福等提出层级图表征学习

选自arXiv，作者：Rex Ying等，机器之心编译，参与：李诗萌、刘晓坤。

图网络（GN）在深度学习短板即因果推理上拥有巨大潜力，很有可能成为机器学习领域的下一个增长点，而图神经网络（GNN）正属于图网络的子集。GNN 近期在图形分类任务上得到了当前最佳的结果，但其存在平面化的局限，因而不能将图形分层表征。现实应用中，很多图形信息都是层级表征的，例如地图、概念图、流程图等，捕获层级信息将能更加完整高效地表征图形，应用价值很高。在本文中，来自斯坦福等大学的研究者通过在 GNN 中结合一种类似 CNN 中空间池化的操作——可微池化，实现了图形的分层表征。该方法在大部分图形分类基准上都取得了当前最佳的表现，并在较简单的约束下就能自动捕获层级结构。

近年来人们开发图形神经网络的兴趣持续激增。图形神经网络即可以在如社交网络数据 [16,21,36] 或基于图形的分子表征 [7,11,15] 的图形结构数据上运行的一般的深度学习架构。GNN 一般是将底层图形作为计算图，通过在图上传递、转换和聚合节点特征信息学习神经网络基元以生成单个节点嵌入。生成的节点嵌入可以作为输入，用于如节点分类或连接预测的任何可微预测层，完整的模型可以通过端到端的方式训练。

然而，现有的 GNN 结构的主要限制在于太过平坦，因为它们仅通过图形的边传播信息，无法以分层的方式推断和聚合信息。例如，为了成功编码有机分子的图形结构，就要编码局部分子结构（如单个的原子和与这些原子直接相连的键）和分子图的粗粒结构（如在分子中表示功能单元的原子基团和键）。对图形分类任务而言缺少分层结构尤其成问题，因为这类任务是要预测与整个图相关的标签。在图分类任务中应用 GNN，标准的方法是针对图中所有的节点生成嵌入，然后对这些节点嵌入进行全局池化，如简单地求和或在数据集上运行神经网络 [7,11,15,25]。这种全局池化方法忽略了可能出现在图中的层级结构，也阻碍了研究人员针对完整图形的预测任务建立有效的 GNN 模型。

研究者在此提出了 DIFFPOOL，这是一个可以分层和端到端的方式应用于不同图神经网络的可微图池化模块（图 1）。DIFFPOOL 允许开发可以学习在图的层级表征上运行的更深度的 GNN 模型。他们开发了一个和 CNN 中的空间池化操作相似的变体，空间池化可以让深度 CNN 在一张表征越来越粗糙的图上迭代运行。与标准 CNN 相比，GNN 的挑战在于图不包含空间局部性的自然概念，也就是说，不能将所有节点简单地以「m*m 补丁」的方式池化在一张图上，因为图复杂的拓扑结构排除了任何直接、决定性的「补丁」的定义。此外，与图像数据不同，图形数据集中包含的图形节点数和边数都不同，这使得定义通用的图形池化操作符更具挑战性。

为了解决上述问题，我们需要一个可以学习如何聚合节点以在底层图形上建立层级多层支架的模型。DIFFPOOL 在深度 GNN 的每一层学习了可微分的软分配，基于学习到的嵌入，将节点映射为一组聚类。以该方法为框架，我们通过分层的方式「堆叠」了 GNN 层建立了深度 GNN（图 1）：GNN 模块中 l 层的输入节点对应 GNN 模块中 1 层（1 个 GNN 模块）学到的簇。因此，DIFFPOOL 的每一层都能使图形越来越粗糙，然后训练后的 DIFFPOOL 就可以产生任何输入图形的层级表征。本研究展示了 DIFFPOOL 可以结合到不同的 GNN 方法中，这使准确率平均提高了 7%，并且在五个基准图形分类任务中，有四个达到了当前最佳水平。最后，DIFFPOOL 可以学习到与输入图中明确定义的集合相对应的可解释的层级簇。

4 实验

为了回答下列问题，将 DIFFPOOL 与最优秀的图分类方法相比，研究者评估了 DIFFPOOL 的优势：

• Q1：与其他已提出的 GNN 池化方法（如使用排序池化 [39] 或 SET2SET 方法 [15]）相比，DIFFPOOL 如何？
• Q2：与现有最好的图分类任务模型（包括 GNN 和基于核的方法）相比，结合了 DIFFPOOL 的 GNN 如何？
• Q3：DIFFPOOL 对输入图计算了有意义且可解释的簇吗？

4.1 基础方法

在图分类的性能比较中，研究者考虑了基于 GNN 和现有最好的基于核的方法。

基于 GNN 的方法

• 带有全局平均池化的 GRAPHSAGE[16]。这里忽略了其他如 [21] 中提出的 GNN 变体，因为从经验上讲，GraphSAGE 在任务中获得了更好的表现。
• STRUCTURE2VEC（S2V）[7] 当前是最好的图形表征学习算法，该算法将潜在变量模型和 GNN 结合在一起。该算法用的也是全局平均池化。
• CNN 中用于图形的边缘条件过滤器（ECC）[35] 将边缘信息整合到 GCN 模型中，使用图形粗化算法进行池化操作。
• PATCHYSAN[29] 为每个节点定义了接受域（邻域），并使用了规范节点排序，对节点嵌入的线性序列应用了卷积操作。
• SET2SET 通过聚合替代了传统 GNN 架构的全局平均池化。Set2Set 聚合的性能优于之前工作 [15] 中的平均池化。我们以 GRAPHSAGE 作为基础的 GNN 模型。
• SORTPOOL[39] 应用了 GNN 结构，在排好序的节点嵌入上做了单层软池化，然后进行了 1D 卷积。

表 1：分类准确率（%）。与 GRAPHSAGE 相比，最右列给出了准确率的相对增长。

4.2 图形分类结果

表 2：应用 DIFFPOOL 到 S2V 的准确率结果。

图 2：DIFFPOOL 的层级聚合分布的图，样例图形来自 COLLAB。左图（a）表示两层的层级聚合，第二层的节点与第一层的聚合簇相对应。（用颜色表示连接各层的节点/聚合簇，虚线用来表示簇。）右边的两个图（（b）和（c））显示了不同图形的两个更多的样例。注意，尽管我们全局地将聚合簇的数量设置为节点的 25%，GNN 会自动学习到合适的有意义的簇的数量，并将其分配给不同的图形。

4.3 DIFFPOOL 中聚合簇分配的分析

层级聚合结构。为了解决 Q3，研究者通过可视化不同层的簇分配研究了 DIFFPOOL 学习有意义节点簇的程度。图 2 展示了一个来自 COLLAB 数据集的图形在第一层和第二层节点分配的可视化图，图中节点颜色表示属于哪个聚合簇。通过得到簇的分配概率的 argmax 值决定节点属于哪个簇。研究者甚至观察到，在仅基于图形分类目标函数学习簇分配时，DIFFPOOL 还是可以捕获层级聚合结构。

密集和稀疏的子图结构。此外，研究者还观察到 DIFFPOOL 可以以非均匀的方式将节点坍缩（collapse）成软簇，并且倾向于将密集连接的子图坍缩成簇。因为 GNN 可以有效地在密集的、类似团的子图（直径较小）上传递信息，因此在这样密集的子图上池化所有节点不太可能会损失结构信息。这直观地解释了为什么对 DIFFPOOL 而言坍缩密集子图是有用的池化策略。相比之下，稀疏子图可能会包含许多像路径结构、循环结构和树状结构等有趣的结构，由于稀疏导致的大直径，GNN 可能无法通过信息传递捕获这些结构。因此，DIFFPOOL 可以通过分别池化稀疏子图的不同部分，学习在现有的稀疏子图区域中捕获有意义的结构（如图 2 所示）。

论文：Hierarchical Graph Representation Learning with Differentiable Pooling

论文地址：https://arxiv.org/pdf/1806.08804.pdf

近期，通过有效地学习节点嵌入改变了图表征学习领域，图神经网络（GNN）在节点分类和连接预测这样的任务中得到了最佳结果。但现有的 GNN 方法本质上讲还是平面的，因为无法学习图形的层级表征——这对于图形分类任务而言尤其成问题，因为图形分类任务的目的是预测与整个图像相关的标签。我们在此提出了 DIFFPOOL，这是一个可微分的图形池化模块，该模块可以产生图形的层级表征，还可以以端到端的方式与多个图神经网络结构结合。DIFFPOOL 在深度 GNN 的每一层针对节点学习可微分的软簇分配，将节点映射到一组簇中去，然后这些簇作为粗化输入，输入到 GNN 下一层。实验结果表明现有的 GNN 方法与 DIFFPOOL 结合后，在图形分类基准中的准确率平均可以提高 5～10%，与现有的所有池化方法相比，在 5 个基准数据集中，有 4 个都得到了当前最佳的表现。