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

2018/07/16 AM 9:46

李诗萌刘晓坤编译

图网络（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 卷积。

6v6Zbun.png!web

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

4.2 图形分类结果

YBN7NvN.png!web

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

vyeiian.png!web

图 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 DifferentiablePooling

ZnEVBbf.png!web

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

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

相关数据

神经网络技术

Neural Network

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

映射技术

Mapping

映射指的是具有某种特殊结构的函数，或泛指类函数思想的范畴论中的态射。逻辑和图论中也有一些不太常规的用法。其数学定义为：两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。其中，y称为元素x在映射f下的象，记作：y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域，记作f(A)。同样的，在机器学习中，映射就是输入与输出之间的对应关系。

来源： Wikipedia

池化技术

Pooling

池化（Pooling）是卷积神经网络中的一个重要的概念，它实际上是一种形式的降采样。有多种不同形式的非线性池化函数，而其中“最大池化（Max pooling）”是最为常见的。它是将输入的图像划分为若干个矩形区域，对每个子区域输出最大值。直觉上，这种机制能够有效的原因在于，在发现一个特征之后，它的精确位置远不及它和其他特征的相对位置的关系重要。池化层会不断地减小数据的空间大小，因此参数的数量和计算量也会下降，这在一定程度上也控制了过拟合。通常来说，CNN的卷积层之间都会周期性地插入池化层。

来源： cs231n

目标函数技术

Objective function

目标函数f(x)就是用设计变量来表示的所追求的目标形式，所以目标函数就是设计变量的函数，是一个标量。从工程意义讲，目标函数是系统的性能标准，比如，一个结构的最轻重量、最低造价、最合理形式；一件产品的最短生产时间、最小能量消耗；一个实验的最佳配方等等，建立目标函数的过程就是寻找设计变量与目标的关系的过程，目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

来源：百度百科

表征学习技术

Representation learning

在机器学习领域，表征学习（或特征学习）是一种将原始数据转换成为能够被机器学习有效开发的一种技术的集合。在特征学习算法出现之前，机器学习研究人员需要利用手动特征工程（manual feature learning）等技术从原始数据的领域知识（domain knowledge）建立特征，然后再部署相关的机器学习算法。虽然手动特征工程对于应用机器学习很有效，但它同时也是很困难、很昂贵、很耗时、并依赖于强大专业知识。特征学习弥补了这一点，它使得机器不仅能学习到数据的特征，并能利用这些特征来完成一个具体的任务。

来源： Wikipedia

堆叠技术

Stacking

堆叠泛化是一种用于最小化一个或多个泛化器的泛化误差率的方法。它通过推导泛化器相对于所提供的学习集的偏差来发挥其作用。这个推导的过程包括：在第二层中将第一层的原始泛化器对部分学习集的猜测进行泛化，以及尝试对学习集的剩余部分进行猜测，并且输出正确的结果。当与多个泛化器一起使用时，堆叠泛化可以被看作是一个交叉验证的复杂版本，利用比交叉验证更为复杂的策略来组合各个泛化器。当与单个泛化器一起使用时，堆叠泛化是一种用于估计（然后纠正）泛化器的错误的方法，该泛化器已经在特定学习集上进行了训练并被询问了特定问题。

来源： Wolpert, D. H. (1992). Stacked generalization. Neural networks, 5(2), 241-259

深度学习技术

Deep learning

深度学习（deep learning）是机器学习的分支，是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。深度学习是机器学习中一种基于对数据进行表征学习的算法。观测值（例如一幅图像）可以使用多种方式来表示，如每个像素强度值的向量，或者更抽象地表示成一系列边、特定形状的区域等。而使用某些特定的表示方法更容易从实例中学习任务（例如，人脸识别或面部表情识别）。近年来监督式深度学习方法（以反馈算法训练CNN、LSTM等）获得了空前的成功，而基于半监督或非监督式的方法（如DBM、DBN、stacked autoencoder）虽然在深度学习兴起阶段起到了重要的启蒙作用，但仍处在研究阶段并已获得不错的进展。在未来，非监督式学习将是深度学习的重要研究方向，因为人和动物的学习大多是非监督式的，我们通过观察来发现世界的构造，而不是被提前告知所有物体的名字。至今已有数种深度学习框架，如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

来源： LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. nature, 521(7553), 436.

准确率技术

Accuracy

分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数

来源： Google ML Glossary

刘晓坤

机器之心编辑