$1、Introduction$1、Introduction

前人工作的不足之处：

• 早期图CNN的缺点：数据低维，卷积核过于局部化，无法从复杂图中学习层次表示。
• 现存图CNN的缺点：无法充分利用图的几何性质，因为很难设计能够匹配不同数量邻居的参数化空间核。此外，考虑到图的灵活性和参数的规模，为每一个独特的图学习一个定制的保留拓扑结构的空间核是不切实际的。
• 共享卷积核。为了保证层输出的统一维数，必须调整输入的大小。然而，这种对图数据的预处理可能会破坏信息的完整性。如果图CNN能够接受不同图结构的原始数据样本就好了。
• 输入到图CNN的数据要么有固有的图结构，要么通过聚类人为构建。在之前的图CNN中，初始图结构在整个训练过程中是被固定的。然而，很难去评估这个通过无监督聚类（或领域知识）得到的图结构对于监督学习任务是否是最优的。尽管利用全连接网络的有监督图构建已经被提出，他们的密集训练权重限制了图只能是小图。此外，由另一个独立网络学习得到的图结构并不能保证最适合图卷积。

本文图CNN的创新点：

• 构建独有的图Laplacian：构建并学习batch中每个独立样本独有的残差Laplacian 矩阵，学习到的残差图Laplacian 将会被加到初始图中（聚类得到的或固有图）。
• 学习图更新的距离度量：通过学习数据共享的最优距离度量参数，随着预测网络的训练，拓扑结构被更新。学习复杂度$O（d^2）$O（d2）和尺寸无关。
• 卷积中的特征嵌入：结点特征的转换是在卷积连接**intra-(类内)和inter-(类间)**结点特征之前完成的。
• 接受灵活的图输入：本网络可以输入不同的图结构和尺寸，解锁了图的度。

$2、Method$2、Method

$2.1\ SGC-LL\ Layer$2.1 SGC−LL Layer

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

1.学习图Laplacian

谱卷积核的k阶多项式

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

1. 图是在特征提取和转换之前的原始特征域上构建的。
2. 图拓扑结构是固有的，它仅仅表示物理连接，如分子中的化学键。

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

最后，SGC-LL层表示为：

用切比雪夫展开来计算$k$k阶多项式$T_{k}(\tilde{L})X$Tk​(L~)X .

2.训练图更新的度量

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

此时，广义$mahalanobis$mahalanobis距离隆重登场。$x_i$xi​和$x_j$xj​之间的广义$mahalanobis$mahalanobis距离表示为：

如果$M=I$M=I，则退化为欧式距离。在本文模型中，$M=W_{d}{W^{T}}_{d}$M=Wd​WTd​对称半正定矩阵，其中$W_d$Wd​是$SGC-LL$SGC−LL层中可训练的权重之一（$SGC-LL$SGC−LL层只有三个可训练权重：这里的$M(W_d)$M(Wd​),重参数化里的$W_b$Wb​，相当于转换到了可以计算欧式距离的空间。然后，用距离计算高斯核：

归一化$G$G之后，$\tilde{A}$A~得到密集邻接矩阵。在模型中，最优度量$\tilde{W}_d$W~d​能够建立最优的图$Laplacian$Laplacian集$\tilde{L}$L~，使得预测损失最小化。

3.特征转换重参数化

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

总之，在每个$SGC-LL$SGC−LL层，参数${(M_i,W_i,b_i)}$(Mi​,Wi​,bi​)具有的学习复杂度$O(d_id_{i-1})$O(di​di−1​)，与图的大小和度无关。在下一个$SGC-LL$SGC−LL层，谱卷积核将会在不同度量的另一个特征域上建立。

4. 残差图Laplacian

大多数数据没有天然的图结构，所以在送入网络之前要给他们构造一个图结构，最常见的情况就是图是用无监督方法构造的，不能有效地对特定任务表达全部有意义的拓扑结构.

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

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

2.2 AGCN网络

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

Graph Max Pooling层

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

Graph Gather层

图形收集层逐个元素地汇总了此处表示数据的所有顶点特征向量。聚集层的输出向量将用于$graph-level$graph−level预测。 如果没有图收集层，也可以训练$AGCN$AGCN并将其用于$vertex-wise$vertex−wise的预测任务（给定顶点上的标签）。 逐点预测包括图完成和社交网络上的许多预测。

双边卷积核

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

网络配置

$AGCN$AGCN包含了很多连续的组合层，其中的核心层就是$SGC-LL$SGC−LL. 一个组合层由一个$SGC-LL$SGC−LL层、一个$BN$BN层、一个$Graph Max Pooling$GraphMaxPooling层构成。残差图$Laplacian$Laplacian就是在每个$SGC-LL$SGC−LL中被训练，在$Max Pooling$MaxPooling中，适应图（固有图+残差图）被再次使用直到下一个$SGC-LL$SGC−LL，因为$SGC-LL$SGC−LL会做特征变换，所以下一个$SGC-LL$SGC−LL需要重新训练一个新的残差图。
经过一个组合层，图结构就被更新了，但图大小保持不变。任何的图粗燥化或者特征平均都会破坏具有有用信息的图局部结构的完整性，所以用了$Max Pooling$MaxPooling并且不在卷积中跳过任何结点。测试是$graph-wise$graph−wise预测任务。

不同图的batch训练

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

• Adaptive Graph Convolutional Neural Networks