文 | 全世界最乖巧的小猪

Adaptive Graph Convolutional Neural Networks

这是一篇研究自适应图卷积神经网络的论文，由来自德州大学阿灵顿分校和腾讯的作者发表于AAAI2018，下载地址：Adaptive Graph Convolutional Neural Networks

摘要

图卷积网络（Graph CNNs）是可以作用在图结构数据（如分子，点云，社交网络等）上的卷积神经网络。目前图卷积网络中的卷积核适用于固定且共享的图结构。然而，对于大多数实际数据而言，图结构在尺寸大小和连接方式上都是不一样的。本文提出了一种广义并且灵活的图卷积网络，可以将任意图结构数据作为输入。如此一来，一种任务驱动的适应性图就会在训练过程中被学习到。为了有效地学习图，本文提出了一种距离度量学习。实验做得不错！

1 文章简介

在许多实际问题中，数据是在非欧域中的，比如化学分子，点云，社交网络等。这些数据用图来表示比张量表示更为合适。所以需要可作用在图结构上的卷积神经网络。

前人工作的不足之处：

1. 早期图CNN的缺点：数据低维，卷积核过于局部化，无法从复杂图中学习层次表示。

2. 某些情况下，比如点云分类，图的拓扑结构比结点特征包含更大的信息量。现存图CNN的缺点：无法充分利用图的几何性质，因为很难设计能够匹配不同数量邻居的参数化空间核。此外，考虑到图的灵活性和参数的规模，为每一个独特的图学习一个定制的保留拓扑结构的空间核是不切实际的。

3. 现存图CNN的缺点：共享卷积核。为了保证层输出的统一维数，必须调整输入的大小。然而，这种对图数据的预处理可能会破坏信息的完整性。如果图CNN能够接受不同图结构的原始数据样本就好了。

4. 输入到图CNN的数据要么有固有的图结构，要么通过聚类人为构建。在之前的图CNN中，初始图结构在整个训练过程中是被固定的。然而，很难去评估这个通过无监督聚类（或领域知识）得到的图结构对于监督学习任务是否是最优的。尽管利用全连接网络的有监督图构建已经被提出，他们的密集训练权重限制了图只能是小图。此外，由另一个独立网络学习得到的图结构并不能保证最适合图卷积。

总结，目前graph CNN的瓶颈包括：

1. 限制图的度；

2. 无法从拓扑结构中学习；

3. 要求输入之间共享相同的图结构；

4. 不训练的固定图构建。

本文提出了一个新的谱图卷积网络，可以接收不同图结构的原数据，比如由不同数量的苯环组成的有机分子。给batch里每个样本一个定制的图Laplacian 来客观地描述它独有的拓扑结构。定制的图Laplacian将引出一个定制的谱卷积核，根据独有的图拓扑结构来综合邻居特征。

到底什么样的图结构最适合一个监督学习任务呢？比如，化合物中的化学键自然地构成一个固有图。然而，没人保证在固有图中工作的卷积核提取出了所有有意义的信息。因此，本文训练了残差图（residual graph）来探索固有图中没有包括的剩余子结构。此外，为了保证残差图是对特定任务的最佳补充，本文设计了一种方案来学习残差图。

直接学习图Laplacian花费O（N^2）复杂度，N个结点。实现M个训练样本独有的图拓扑结构表示学习M个独有的图Laplacian，太费劲了！如果利用Mahalanobis距离作为一个监督度量学习，就可以减少参数量，假定度量的参数是样本之间共享的。作为结果，学习复杂度就会和图大小N无关。在传统CNN中，反向传播逐渐更新卷积核权重，分别调整每个特征维度上相邻节点之间的关系。然后将所有卷积核的信号相加来构造隐藏层激活。为了让图CNN也能实现相同的能力，本文提出了重参数化，在特征域上加个转换权重和偏置。最后，卷积层里全部的训练参数包括：距离度量，结点特征转换权重和偏置。给定了训练好的度量和转换好的特征空间，更新的残差图就可以构建了。

本文图CNN的创新点：

1. 构建独有的图Laplacian：构建并学习batch中每个独立样本独有的残差Laplacian 矩阵，学习到的残差图Laplacian 将会被加到初始图中（聚类得到的或固有图）。

2. 学习图更新的距离度量：通过学习数据共享的最优距离度量参数，随着预测网络的训练，拓扑结构被更新。学习复杂度O（d^2）和尺寸无关。

3. 卷积中的特征嵌入：结点特征的转换是在卷积连接intra-(类内)和inter-(类间)结点特征之前完成的。

4. 接受灵活的图输入：由于1和2，本网络可以输入不同的图结构和尺寸，解锁了图的度。

2 相关工作

2.1 谱图卷积

2.2 分子图神经网络

3 方法

3.1 SGC-LL层

为了使谱卷积核在不同的图拓扑中真正可行，本文对距离度量进行参数化，使图Laplacian函数本身成为可训练的。利用训练后的度量，动态地构造不同形状和大小的输入样本的独有图。一种新的层利用自适应图构造的K-局域卷积核进行卷积。同时，对样本的图拓扑结构进行了更新，使训练损失最小化。新的具有图Laplacian学习的谱图卷积层称为SGC-LL。本节将介绍SGC-LL层的创新点。

3.1.1 学习图Laplacian

此处跳过我们都知道的图卷积的介绍，直接来到谱卷积核的k阶多项式：

这限制了卷积核的灵活性。更重要的是，两个结点之间的相似度是由所采取的距离度量和特征域决定的。因此，很有可能两个相连结点之间的相似度比不相连的相似度要低，因此图结构不是最优的。可能有两个原因：

1. 图是在特征提取和转换之前的原始特征域上构建的。

2. 图拓扑结构是固有的，它仅仅表示物理连接，如分子中的化学键。

为了打破这些限制，提出新的谱核，参数化Laplacian L来代替系数。给定原始Laplacian L，特征X和参数，函数输出更新后的L谱，卷积核表示为：

*这里的函数F就是后面那些步骤的抽象表示。

最后，SGC-LL层表示为：

     （5）

用切比雪夫展开来计算k阶多项式.

3.1.2 训练图更新的度量

在图结构数据中，欧式距离就不好用了。这里的距离度量应该在训练中根据任务和特征可以随机应变。在度量学习文章中，算法分为有监督学习和无监督学习。由无监督方法获得的最好的度量能够最小化类内距，最大化类间距。对于有监督学习，目标是要找到能够最小化损失函数的度量。

此时，广义mahalanobis距离隆重登场。和之间的广义mahalanobis距离表示为：

     （6）

如果M=I，则退化为欧式距离。在本文模型中，对称半正定矩阵，其中W_d是SGCLL层中可训练的权重之一（SGCLL层只有三个可训练权重：这里的M(W_d),重参数化里的W,b），相当于转换到了可以计算欧式距离的空间。然后，用距离计算高斯核：

     （7）

归一化G之后，得到密集邻接矩阵。在模型中，最优度量能够建立最优的图Laplacian集，使得预测损失最小化。

3.1.3 特征转换重参数化

为了建立类内和类间结点特征映射，在SGC-LL层中，引入转换矩阵和转置向量应用到输出特征上。基于式5，输出特征重参数化表示为：

      (8)

总之，在每个SGC-LL层，参数{}具有的学习复杂度，与图的大小和度无关。在下一个SGC-LL层，谱卷积核将会在不同度量的另一个特征域上建立。

3.1.4 残差图Laplacian

大多数数据没有天然的图结构，所以在送入网络之前要给他们构造一个图结构，最常见的情况就是图是用无监督方法构造的，不能有效地对特定任务表达全部有意义的拓扑结构。以化合物为例，由SMILES序列给出的固有图无法表达出与其毒性有关的任何信息，仅靠固有图，很难学到关于毒性的有意义的表达。

由于没有距离度量的先验知识，M随机初始化，可能收敛很慢。为了加速训练过程并且提高学习到的图结构的稳定性，本文提出合理的假设，最优图Laplacian 是最初L的一个小变换：.

换句话说，最初的L已经包括了大量的有用图结构信息，但不包括那些由虚拟结点连接组成的子结构，这些虚拟结点连接不能直接从固有图中学习到。因此，本文就学残差图Laplacian (i表示第i个sample).SGC-LL层完整操作如算法1所示：

3.2 AGCN网络

该网络被称为自适应图卷积网络（AGCN），因为SGC-LL层能够根据数据和学习任务的上下文有效地学习自适应图拓扑结构。除SGC-LL层外，AGCN还具有Graph Max Pooling层和Graph Gather层。

3.2.1 Graph Max Pooling层

对于第v个结点特征，pooling将第j维特征替换成它的邻居结点和它自己的第j维特征中的最大值。N(v)是v的邻居结点，则v的新特征为

3.2.2 Graph Gather层

将所有结点特征逐元素相加作为图表示，用作graph-level的预测。不加Graph Gather层可作vertex-wise预测。

3.2.3 双边卷积核

作用是防止过拟合。通过增强L的空间局部性，正则化SGC-LL的激活 。还用了BN层加速训练。

*空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。（如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。）

3.2.4 网络配置

AGCN包含了很多连续的组合层，其中的核心层就是SGC-LL. 一个组合层由一个SGC-LL层、一个BN层、一个Graph Max Pooling 层构成。残差图Laplacian就是在每个SGC_LL中被训练，在Max Pooling中，适应图（固有图+残差图）被再次使用直到下一个SGC-LL，因为SGC-LL会做特征变换，所以下一个SGC-LL需要重新训练一个新的残差图。

经过一个组合层，图结构就被更新了，但图大小保持不变。任何的图粗燥化或者特征平均都会破坏具有有用信息的图局部结构的完整性，所以用了Max Pooling并且不在卷积中跳过任何结点。测试是graph-wise 预测任务。

图3 AGCN网络结构配置

3.3 不同图的batch训练

将卷积运用到图结构数据中的一个巨大挑战就是要匹配训练样本的不同局部拓扑结构：1）造成了设计卷积核的额外困难，因为卷积核的不变性不适用于图，结点索引（node indexing）有时很重要；2）调整图的大小或重塑图对一些数据来说不合理，比如分子。不同于图像和视频在张量上运用传统卷积，不同拓扑结构的兼容性对于图卷积而言非常有必要。这里提出的SGC-LL层训练独立的图Laplacian，可以适应所有数据的局部拓扑结构。由于作者发现，正是特征空间和距离度量在构建图结构中起到重要作用，SGC-LL层仅需要batch里的所有样本去共享相同的转换矩阵和距离矩阵。此外，训练参数仅取决于特征维数。因此，AGCN接受训练batch包含不同的拓扑结构和大小的原图结构数据样本。注意，附加内存消耗会被初始图Laplacian所带来，需要在训练之前构建，并且仍然需要保留它们来更新核，然而，这是可接受的因为图Laplacian通常是稀疏的。

4 实验

实验比较了AGCN网络和一些state-of-the-art的图CNN：graphconv, NFP, GCN. 实验结果表明，AGCN比所有现存的图CNN表现的都好，并且解释了SGC-LL层是如何增强效果的。

4.1 SGC-LL层增强效果

图4 C20N2O5S（丙硫克百威）结点28×28相似矩阵的两个热图

SGC-LL层中的谱卷积核建立在自适应图上，包括个体图（individual graph）和残差图（residual graph），个体图是由数据本身直接得到的固有图，或是由聚类得到的，个体图使得网络能够读取不同结构的数据。此外，图将在训练过程中被更新，因此网络被训练来对训练数据优化距离度量和特征转换。实验表明，更新图和网络表现密切相关。图4中，如果放大来看，很容易发现20个epoch之后结点相似度的明显不同。这意味着化合物经过训练后图结构的距离度量被更新了。同时，加权l2损失在前20个epoch中骤然下降，平均RMSE也一样。此外，RMSE和loss曲线证明了AGCN（红线）在收敛速度和预测准确度方面都力压其他图CNN（图5）。这主要归功于适应性图和SGC-LL层中残差Laplacian 的学习。

图5 (1)训练损失；(2)Delaney数据集上溶解度值预测的RMSE评分

4.2 分子数据集的多任务预测

Delany数据集包括1144种低分子化合物的水溶性数据。数据集中最大的化合物有492个原子，最小的仅有3个原子。NCI数据集包括20000种化合物和60个预测任务，从药物反应试验到临床药理学研究。Az-logD数据集提供4200种化合物渗透性的logD测量。此外，还有一个包括642种化合物的小数据集用来进行水化自由能研究。所提出的任务平均RMSE评分和标准差在5倍交叉验证后得到。

Tox21数据集包括7950种化学化合物和12次实验的毒性分类标签。然而，额外的困难来自于这12次任务中有部分标签遗失，对于遗失标签的数据，不对它们计算loss，但仍放在训练集中。ClinTox是一个公开数据集，包括1451种用于临床毒理学研究的化合物以及两个任务的标签。Sider数据集记录了1392种药物和它们27种不同的副作用或不良反应。Toxcast是另一个毒理学研究数据集，包含8599简化分子线性输入规范SMILES和617个预测任务的标签。对于N任务预测，网络图模型将成为具有n个叶节点的k元树的模拟模型，每个叶节点由一个全连接层和一个逻辑回归组成。

为证明AGCN的优势，实验比较了它和其他三个state-of-the-art图CNN模型：第一个谱图CNN（graphconv）（基于样条插值），K-局域谱核的扩展（GCN），神经指纹——分子的尖端神经网络（NFP）。表1中，AGCN在Delaney数据集上将平均RMSE降低了31%-40%，在az_logd上平均降低了15%，在NCI测试集上平均降低了2%-4%。在数据较短（short）的情况下，对隐藏结构的自适应图和剩余Laplacian学习更有用。根据表2中的多任务分类结果，注意到，AGCN显著提高了小数据集和大数据集的准确性。对于617个toxcast任务，与现有技术相比，分级机的性能平均提高了3%（0.03）。

表1 各数据集RMSE均值与标准差

表2 任务平均ROC-AUC分数

分子图，直接由化学式给出，是化合物数据的固有图。它们在拓扑结构和图的大小方面都高度不一致。（这里跳过解释graphconv和GCN不足之处……）

这里夸一夸本文的AGCN：AGCN可以更好地处理分子数据。自适应图允许输入样本有独特的图Laplacian，所以每种化合物实际上都有根据其拓扑结构来定制的独特卷积核。有了这种能力，我们可以喂给网络原始数据（原子/边特征，分子图），没有任何的信息丢失。此外，SGC-LL层训练距离度量，和其他转换参数一起最小化指定任务的预测损失。因此，收敛时，在每层SGC-LL，我们可以找到最优特征空间和距离度量去建立最合适该任务的图结构，这种学习到的图可能包括原来分子图中不存在的新的边。

4.3 点云物体分类

悉尼城市点云数据集包含了631个街景扫描物体，共26个种类。由于物体的实际尺寸和形状不同，扫描物体的接收点个数也不同。（自行车：124个点，卡车：615个点，行人：78个点）

以前的CNN模型在输入点集之前需要通过下采样来统一尺寸，这会损失部分结构信息。而AGCN克服了这种缺点，可以接受不同尺寸的原始点集。以前的图卷积共享一个卷积核，但是它可能会混合点上的特征，无视实际距离。而AGCN可以根据空间关系准确地做卷积。点云的初始图由层次聚类方法建立，目前点云识别最前沿的方法PointNet也无法处理不同尺寸的点云数据。

5次交叉验证后，在包含200个样本的测试集上计算平均AUC-ROC得分，从表3中可以看出AGCN在所有样本平均得分上比其他图CNN高3-6%。对于大物体如建筑，AUC得分接近1，其他网络表现差因此他们首先把图结构变粗糙了。对于重要的道路物体比如信号灯，AGCN也提升了10%的ROC-AUC分类准确率。这有效说明AGCN能够提取到更有意义的特征。输入到AGCN的数据的信息完整性也有助于提高性能，这归功于在SGC-LL层上构造和学习的自适应图。

表3 测试集平均AUC-ROC得分

5 结论

本文提出了一种新的频谱图卷积器（SGC-LL）与自适应图一起工作。SGC-LL通过学习最优度量和特征转换形式来学习残差图Laplacian。据我们所知，AGCN是第一个接受任意图结构和大小的数据的图CNN。残差Laplacian函数的监督训练驱动模型更好地适应预测任务。对各种图形结构数据进行的大量多任务学习实验表明，在各种预测任务上，AGCN优于最先进的图CNN模型。