Question

1. 尽管卷积神经网络CNN 在很多机器学习任务上取得极大成功，但是它要求输入数据为张量。例如，图像和视频分别建模为 2-D 张量和 3-D 张量。然而在实际任务中，很多数据都是不规则的图结构，如化学分子数据、点云数据、社交网络数据。这些数据被组织为图结构而不是规则形状的张量，并且不再满足平稳性stationarity和组合性compositionality （这两个性质允许执行 grid 上的 kernel-based 卷积），因此无法应用卷积操作。因此，有必要在图结构上重新构造卷积算子。

   然而将 CNN 从规则的网格推广到不规则的图，并非易事。

   • 早期的 Graph CNN （《Spectral networks and locally connected networks on graphs》，《Deep convolutional networks on graphstructured data》）通常假设数据是低维的（即 degree 较低），因为卷积器根据节点的 degree 来独立地处理节点。

   • 另外，卷积核也过度局部化 over-localized，很难从复杂的图结构中学到hierarchical representation 。

   • 某些情况下（如点云point cloud 的分类），图的拓扑结构要比节点特征包含更多信息。但是，现有的Graph CNN 无法利用图的结构特性，因为无法设计一个匹配各种各样邻域结构的空域卷积核spatial kernel 。

     GraphSAGE 或 GAT 其实可以匹配各种邻域结构，因为它们是 inductive 的。而 transductive 的 GCN 无法匹配各种邻域结构。

   • 此外，考虑到图结构的灵活性以及模型参数规模，为数据集中每个图学习定制化customized 的、保留拓扑结构的空域卷积核是不现实的。

     这里我们假设数据包含很多图（比如分子图），每个图的结构都各不相同。

   • 除了在图上进行空域卷积之外，还可以在经过傅里叶变换之后的图的频域上进行谱卷积。

     类似经典的 CNN，图的谱卷积也假设样本之间（不同的图）共享卷积核。因此，为了确保卷积层输出的维度统一，卷积层的输入必须重新调整尺寸，这也是传统 CNN 的限制。

     但是，对图数据进行这种预处理可能会破坏图数据的完整性。例如，对分子图的粗化 coarsening 在化学意义来看很难证明其合理性，粗化后的图很可能丢失了使得当前分子和其它分子有区分的关键子结构。如下图所示为有机化合物 3, 4-亮氨酸(C7H9N) 及其图结构，移除了任何一个碳原子都会破坏苯环。

     因此，如果Graph CNN 可以接受不同图结构的原始数据样本（而不是粗化处理的）作为输入，则非常有意义。

     

   • 最后，我们提供给 Graph CNN 的数据要么具有本征 intrinsic 的图结构（例如分子图），要么可以通过聚类来构建一个图结构（如点云数据）。

     在之前的Graph CNN 模型中，初始的图结构在训练过程中是固定不变的。但是，很难评估本征图或者无监督聚类产生的图是否适合于当前的任务。以化合物为例，SMILES 序列给出的本征图无法说明化合物的毒性，仅靠本征图很难了解毒性的有意义的表示。

     尽管已有人提出了使用全连接网络的有监督的图的构建方法，但是由于训练参数规模巨大，这种方法仅适用于较小的图。另外，无法保证通过网络学到的图结构很好地作用于Graph CNN 。

   因此，当前 Graph CNN 的瓶颈包括：严格的 graph degree 限制、要求输入之间共享相同的图结构、固定构造且无需训练的图结构、无法从拓扑结构中学习。

   论文 《Adaptive Graph Convolutional Neural Networks》 中提出了一种新的频域图卷积神经网络，该网络以原始数据的不同图结构作为输入，例如由不同数量苯环组成的有机分子。为实现这一点，作者不使用共享的谱卷积核，而是为每个图（数据集中每个样本代表一个图）定制化图拉普拉斯矩阵，这些拉普拉斯矩阵客观地描述了每个图独特的拓扑结构。一个定制化的图拉普拉斯矩阵导致一个定制化的谱滤波器，该滤波器根据图的拓扑结构来组合邻域特征。

   有意思的是，什么样的图结构最适合目标监督学习任务？一些图数据具有本征图结构，例如，化学键自然地生成化合物的分子图，即本征图 intrinsic graph 。这些化学键已经通过化学实验被证明是正确的。但是，无法保证卷积器 convolver 能够提取到本征图中所有有意义的特征，因为本征图的图结构不一定和任务目标紧密相关。因此，AGCN 训练了一个所谓的残差图 residual graph，从而发现本征图中未能包含的残差子结构。此外，为了确保残差图是目标任务的最佳补充，作者设计了一个方案从而在训练Graph CNN 的同时来学习残差图。

   假设训练集中有$M$$ M $ 个样本，每个样本都是一个图数据，每个图都有$n$$ n $ 个节点。对于具有$n$$ n $ 个节点的图，直接学习图拉普拉斯矩阵的计算复杂度为$O(n^2)$$ O(n^2) $ ，所有数据集的计算复杂度为$O(M\times n^2)$$ O(M\times n^2) $ ，代价太大。如果以监督学习来学习马氏距离Mahalanobis distance，则可以将学习单个图拉普拉斯矩阵的参数数量降低到$O(d^2)$$ O(d^2) $ 甚至$O(d)$$ O(d) $ ，其中$d$$ d $ 为节点的特征维度。假设度量参数 metric parameter 在不同样本之间共享，则数据集的参数数量也降低到$O(d^2)$$ O(d^2) $ 或$O(d)$$ O(d) $ 。因此，学习图拉普拉斯矩阵的复杂度和图大小$n$$ n $ 、图数量$M$$ M $ 无关。

   在经典 CNN 中，反向传播通常会更新 kernel weight 从而分别调整每个维度上相邻节点之间的关系。然后它聚合来自所有滤波器的信号从而构建 hidden layer 的 activation 。为了赋予 Graph CNN 类似的能力，作者提出使用额外变换 additional transform 来对 feature domain 进行重参数化re-parameterization 。

   最后，卷积层中总的$O(d^2)$$ O(d^2) $ 个训练参数由两部分组成：距离度量 distance metric,、以及节点的特征变换 feature transform 。给定训练好的 metric 、以及变换后的特征空间，我们可以构建更新后的残差图。

   在九个图数据集上进行的大量实验表明，AGCN 在训练速度和预测效果上都有很大的提升。

   论文主要贡献：

   • 为每个样本学习图拉普拉斯矩阵：为每个样本学习残差图的拉普拉斯矩阵，并将学到的残差图的拉普拉斯矩阵添加到初始图（由本征图或聚类图给出）上。

   • 学习度量矩阵：通过学习最佳的距离度量参数（这些参数在数据之间共享），图的拓扑结构随着训练的过程和不断更新。度量矩阵学习的算法复杂度为$O(d^2)$$ O(d^2) $ ，与图的大小无关。

     这个度量矩阵用于构建残差图。

   • 卷积中的 feature embedding ：在执行图上的卷积之前，先完成节点特征的变换。

   • 灵活的输入图：由于前面的第一点和第二点，AGCN 可以接受不同结构和大小的图作为输入，并且没有图 degree 的限制。

2. 相关工作：

   • 谱图卷积 Spectral Graph Convolution：

     《Spectral networks and locally connected networks on graphs》 首次尝试在图上应用类似 CNN 的方法。具体而言，空间卷积聚合了由图邻接矩阵${\mathbf{A}}_k$$ \mathbf A_k $ 定义的邻域的特征。卷积核是finite-size 有限尺寸的并且过度局部化。卷积层简化为类似全连接层的结构，但是使用由${\mathbf{A}}_k$$ \mathbf A_k $ 定义的稀疏转换矩阵sparse transform matrix。空间卷积具有原生的困难：无法匹配各种各样的邻域结构。因此，如果不对图的拓扑结构加以限制，则图上的空间卷积核无法定义。

     谱图理论 spectral graph theory 使得频域上定义卷积核成为可能。并且频域乘子 multiplier 的平滑性带来空间局部性spatial locality。本文的 baseline 方法建立在 《Convolutional neural networks on graphs with fast localized spectral filtering》 的基础上，并且将 one-hop 的 local kernel 扩展为带来最多 K-hop connection 的 kernel 。根据图傅里叶变换，如果$\mathbf{U}$$ \mathbf U $ 是$\mathbf{L}$$ \mathbf L $ 的图傅里叶基 graph Fourier basis ，那么：

     $${\overrightarrow{\mathbf{x}}}_{k+1}=\sigma \left(g_{\theta }\left({\mathbf{L}}^K\right){\overrightarrow{\mathbf{x}}}_k\right)=\sigma \left(\mathbf{U}{g}_{\theta }\left({\mathbf{\Lambda }}^K\right){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_k\right)\in {\mathbb{R}}^n$$

     其中：$n$$ n $ 为节点数量，$\mathbf{L}$$ \mathbf L $ 为图的拉普拉斯矩阵，$\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$ \mathbf\Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n) $ 是$\mathbf{L}$$ \mathbf L $ 的$n$$ n $ 个频率分量（即，特征值）的对角矩阵，$\sigma (\cdot )$$ \sigma(\cdot) $ 为激活函数，$g_{\theta }(\cdot )$$ g_\theta(\cdot) $ 为卷积函数，$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 为定义在图上的信号。

     • 《Convolutional neural networks on graphs with fast localized spectral filtering》 还利用契比雪夫多项式及其近似评估方案来降低计算成本并实现局部化的滤波。
     • 《Semi-supervised classification with graph convolutional networks》 展示了契比雪夫多项式的一阶近似作为 graph filter spectrum，从而导致更少的训练参数。

     尽管如此，人们已经开始构建更强调拓扑结构的定制化的 graph，甚至解除了对 input graph 的维度约束。然而，设计一个灵活的 graph CNN 仍然是一个悬而未决的问题。

   • 分子图Molecular Graph上的神经网络：对有机分子化学性质的预测通常通过人工抽取特征以及 feature embedding 来处理。由于分子自然地被建模为图，因此人们已经成功地在原始分子上构建神经网络来学习 representation。但是，由于空间卷积的局限性，这些网络无法充分利用原子的连通性connectivity（即一些原子组成的亚结构），这些连通性要比少数的化学键特征更能提供信息。

     最近，人们完成了对 progressive network、多任务学习、以及 low-shot/one-shot 学习的探索。目前为止，分子图上的 state-of-the-art 网络仍然使用无法充分利用空间信息的 non-parameterized 的 spatial kernel 。

     此外，拓扑结构可以作为有判别力discriminative的特征的丰富来源。

11.1 模型

11.1.1 SGC-LL

1. 为了使得谱卷积spectral convolution能够适用于各种类型的图结构，我们对距离度量进行了参数化，使得图拉普拉斯矩阵本身是可训练的。通过训练好的度量函数，我们可以为不同形状和大小的输入图动态构建各自的动态图，并在这个动态图上执行卷积（而不是原始图上进行谱卷积）。

   可以学习图拉普拉斯矩阵的新的谱卷积层称作 Spectral Graph Convolution layer with graph Laplacian Learning : SGC-LL 。

a. 学习图拉普拉斯矩阵

1. 给定图$\mathcal{G}=(V,E)$$ \mathcal G=(V,E) $ 以及邻接矩阵$\mathbf{A}$$ \mathbf A $ 、度矩阵$\mathbf{D}$$ \mathbf D $ ，则归一化的图拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 定义为：

   $$\mathbf{L}=\mathbf{I}-{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$

   显然$\mathbf{L}$$ \mathbf L $ 决定了node-wise 连通性（由邻接矩阵$\mathbf{A}$$ \mathbf A $ 刻画）以及节点的 degree（由$\mathbf{D}$$ \mathbf D $ 刻画），知道了拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 意味着知道图$\mathcal{G}$$ \mathcal G $ 的拓扑结构。

   由于$\mathbf{L}$$ \mathbf L $ 是半正定的对称矩阵，因此可以对它进行eigen-decomposition 特征分解：

   $$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$

   其中 ：

   • $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$ \mathbf \Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n) $ 为$n$$ n $ 个特征值构成的对角矩阵，$0\le {\lambda }_1\le \cdots \le {\lambda }_n$$ 0 \le \lambda_1\le\cdots\le \lambda_n $
   • $\mathbf{U}=[{\overrightarrow{\mathbf{u}}}_1,\cdots ,{\overrightarrow{\mathbf{u}}}_n]\in {\mathbb{R}}^{n\times n}$$ \mathbf U = \left[\mathbf{\vec u}_1,\cdots,\mathbf{\vec u}_n\right]\in \mathbb R^{n\times n} $ ，${\overrightarrow{\mathbf{u}}}_i\in {\mathbb{R}}^n$$ \mathbf{\vec u}_i\in \mathbb R^n $ 对应于${\lambda }_i$$ \lambda_i $ 的特征向量。

   类似于欧式空间中的傅里叶变换，图上的信号$\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$ \mathbf{\vec x}\in \mathbb R^n $ 在图上的傅里叶变换定义为：

   $$\widehat{\overrightarrow{\mathbf{x}}}={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   图上的一个信号定义了一个一维特征，该特征在图上每个节点都有取值。

   傅里叶逆变换为：

   $$\overrightarrow{\mathbf{x}}=\mathbf{U}\widehat{\overrightarrow{\mathbf{x}}}=\mathbf{U}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

2. 由于图的拉普拉斯矩阵的谱为$\mathbf{\Lambda }$$ \mathbf \Lambda $ ，因此谱滤波器$g_{\theta }(\mathbf{\Lambda })$$ g_\theta(\mathbf \Lambda) $ 在空域定义了一个卷积核。《Spectral graph theory》表明：平滑的频域谱会产生localized 局部化的空间卷积核。

   在 《Convolutional neural networks on graphs with fast localized spectral filtering》 中定义了一个多项式卷积核：

   $$g_{\theta }(\mathbf{\Lambda })=\sum _{k=0}^{K-1}{\theta }_k{\mathbf{\Lambda }}^k$$

   这定义了一个$K$$ K $ 阶局部化的卷积核，从而允许最短距离$d_{\mathcal{G}}<K$$ d_\mathcal G\lt K $ 的一对节点参与卷积。同时，距离较远意味着更少的相似性，因此分配的重要性也将减少，这可以通过${\theta }_k$$ \theta_k $ 来控制。

   多项式卷积核平滑了频谱，而参数${\theta }_k$$ \theta_k $ 使得卷积核的权重从中心节点到最远的、距离为 K 的节点呈圆形分布。这种做法限制了卷积核的灵活性。

   更重要的是：两个节点之间的相似性不仅和距离相关，更主要的是取决于所选的距离度量函数、节点的特征。对于在非欧几何种的数据，无法保证欧式距离是衡量相似性的最佳指标。因此，两个相连的节点之间的相似性，可能会比两个未连接节点之间的相似性更低。有两个可能的原因：

   • 图是在raw feature domain 原始特征领域构建的，没有经过任何特征抽取和变换，因此基于距离的相似性没有考虑特征信息。
   • 图结构是intrinsic本征的，它仅表示物理意义上的连接，如分子中的化学键，因此距离近不一定代表着相似。

3. 为解决卷积核的这种限制，我们提出了一个新的谱滤波器，该滤波器对拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 进行参数化，而不是对权重系数${\theta }_k$$ \theta_k $ 进行参数化。

   给定原始的图拉普拉斯矩阵$\mathbf{L}\in {\mathbb{R}}^{n\times n}$$ \mathbf L \in \mathbb R^{n\times n} $ 、特征矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d}$$ \mathbf X\in \mathbb R^{n\times d} $ ，参数$\mathrm{\Gamma }$$ \Gamma $ ，其中$d$$ d $ 为节点特征维度，定义新的图拉普拉斯矩阵为：

   $$\tilde{\mathbf{L}}=\mathcal{F}(\mathbf{L},\mathbf{X},\mathrm{\Gamma })$$

   这个新的图拉普拉斯矩阵定义了一个新的动态图，我们在这个新的动态图上进行谱卷积。

   新的滤波器为：

   $$g_{\theta }(\mathbf{\Lambda })=\sum _{k=0}^{K-1}(\mathcal{F}(\mathbf{L},\mathbf{X},\mathrm{\Gamma }){)}^k$$

   则对于输入信号$\mathbf{X}$$ \mathbf X $ ，卷积输出信号为：

   $$\mathbf{Y}=\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}\mathbf{X}=\mathbf{U}\sum _{k=0}^{K-1}(\mathcal{F}(\mathbf{L},\mathbf{X},\mathrm{\Gamma }){)}^k{\mathbf{U}}^{\mathrm{\top }}\mathbf{X}$$

   由于存在稠密矩阵的乘法${\mathbf{U}}^{\mathrm{\top }}\mathbf{X}$$ \mathbf U^\top\mathbf X $ ， 上式的算法复杂度为$O(n^2)$$ O(n^2) $ 。考虑到$\tilde{\mathbf{L}}$$ \tilde{\mathbf L} $ 的稀疏性，如果$g_{\theta }(\tilde{\mathbf{L}})$$ g_\theta(\tilde{\mathbf L}) $ 可以通过$\tilde{\mathbf{L}}$$ \tilde{\mathbf L} $ 的多项式进行近似从而直接计算，则上式的算法复杂度可以降低到$O(K)$$ O(K) $ 。因此，我们选择使用切比雪夫多项式来近似$g_{\theta }(\mathbf{\Lambda })$$ g_\theta(\mathbf \Lambda) $ 。

   注意，这里的$\theta$$ \theta $ 不再是可学习的参数，因此也就是不再是 transductive 的。

b. 度量的训练

1. 对于图结构，欧式距离不再是衡量节点相似性的很好指标。因此，距离度量在训练过程中适应目标任务、节点特征。在度量学习的论文中，算法分为监督学习和非监督学习。监督学习的最佳度量最小化监督损失，无监督学习的最佳度量最小化簇内距离（也是最大化簇间距离）。

2. 给定节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的特征${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 和${\overrightarrow{\mathbf{x}}}_j$$ \mathbf{\vec x}_j $ ，则特征之间的马氏距离定义为：

   $$D({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\sqrt{({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j{)}^{\mathrm{\top }}\mathbf{M}({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j)}$$

   如果$\mathbf{M}=\mathbf{I}$$ \mathbf M = \mathbf I $ 单位矩阵，则上式退化为欧式距离。

   在 AGCN 中，我们选择一个对称的半正定矩阵：$\mathbf{M}={\mathbf{W}}_d{\mathbf{W}}_d^{\mathrm{\top }}$$ \mathbf M = \mathbf W_d\mathbf W_d^\top $ ，其中${\mathbf{W}}_d\in {\mathbb{R}}^{d\times d}$$ \mathbf W_d \in \mathbb R^{d\times d} $ 为 SGC-LL layer 学习的参数。因此上式为：

   $$D({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\sqrt{{({\mathbf{W}}_d^{\mathrm{\top }}({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j))}^{\mathrm{\top }}({\mathbf{W}}_d^{\mathrm{\top }}({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j))}$$

   因此，${\mathbf{W}}_d$$ \mathbf W_d $ 将${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 和${\overrightarrow{\mathbf{x}}}_j$$ \mathbf {\vec x}_j $ 映射到新的欧式空间，从而在新空间中计算欧氏距离。

   然后我们使用新的距离来计算高斯核：

   $$G({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\exp (-\frac{D({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)}{2{\sigma }^2})$$

   在归一化$\mathbf{G}={\left\{G({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)\right\}}_{n\times n}$$ \mathbf G = \left\{G\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j\right) \right\}_{n\times n} $ 之后，我们得到一个新的、稠密的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 。在我们的模型中，最佳度量${\hat{\mathbf{W}}}_d$$ \hat{\mathbf W}_d $ 构建了图拉普拉斯集合$\{\hat{\mathbf{L}}\}$$ \{\hat{\mathbf L}\} $ 从而最小化预测损失。

   这个新的邻接矩阵定义了一个新的图拉普拉斯矩阵，就是前文中描述的$\tilde{\mathbf{L}}$$ \tilde {\mathbf L} $ ，它综合考虑了节点特征$\mathbf{X}$$ \mathbf X $ 以及图结构信息，并自适应地学习距离度量 。

   构建$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 的时间复杂度和空间复杂度都是$O(n^2)$$ O(n^2) $ ，因此该算法不适合大型图。

c. 特征变换上的重参数化

1. 在经典的 CNN 中，卷积层的输出特征是来自最后一层的所有特征图的sum 和，而这些特征图feature map 是由独立的滤波器计算的。这意味着新特征不仅依赖于相邻节点，也依赖于其它内部节点。

   但是在图卷积中，为同一个图上的不同节点特征创建和训练独立的拓扑结构是不可解释的（对应于独立的滤波器）。为了构建同时包含节点内特征和节点间特征的映射，在 SGC-LL 层我们引入了一个特征变换矩阵以及一个 bias 向量作用于层输出上：

   $$\mathbf{Y}=(\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }})\mathbf{W}+\overrightarrow{\mathbf{b}}$$

   假设有$L$$ L $ 个 SGC-LL 层，则在第$l$$ l $ 层，我们有待学习的参数$\{{\mathbf{M}}_l,{\mathbf{W}}_l,{\overrightarrow{\mathbf{b}}}_l\}$$ \left\{\mathbf M_l,\mathbf W_l,\mathbf{\vec b}_l\right\} $ ，其中${\mathbf{M}}_l\in {\mathbb{R}}^{d_{l-1}\times d_{l-1}},{\mathbf{W}}_l\in {\mathbb{R}}^{d_{l-1}\times d_l},{\overrightarrow{\mathbf{b}}}_l\in {\mathbb{R}}^{d_l}$$ \mathbf M_l\in \mathbb R^{d_{l-1}\times d_{l-1}},\mathbf W_l\in \mathbb R^{d_{l-1}\times d_l}, \mathbf{\vec b}_l\in \mathbb R^{d_l} $ 。

   SGC-LL 层的计算复杂度为$O(d_l\times d_{l-1})$$ O(d_l\times d_{l-1}) $ ，它们和图的大小以及节点 degree 无关。

2. 在下一个 SGC-LL 层，谱滤波器将建立在另一个具有不同度量的 feature domain 中。

d. 残差图的拉普拉斯矩阵

1. 某些图数据具有本征的图结构，如分子。分子被建模为以原子为节点、以化学键为边的分子图。这些化学键可以通过化学实验来证明。但是，大多数数据天然地不具备图结构，因此我们必须在将图输入网络之前首先构建好图。

   除了以上两种情况之外，最有可能的情况是：以无监督方式创建的图无法充分地为特定任务来表达所有有意义的拓扑结构。以化合物为例，SMILES 序列给出的本征图并不能说明化合物的毒性。仅仅依赖本征图，很难学到刻画毒性的有意义的 representation 。

2. 由于缺乏距离度量的先验知识，通常我们会随机初始化度量矩阵$\mathbf{M}$$ \mathbf M $ ，因此可能需要花费很长时间模型才能收敛。为了加快训练速度并提高被学习的图拓扑结构的稳定性，我们给出一个合理的假设：最优的图拉普拉斯矩阵$\hat{\mathbf{L}}$$ \hat{\mathbf L } $ 是原始图拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 的一个小的偏移：

   $$\hat{\mathbf{L}}=\mathbf{L}+\alpha {\mathbf{L}}_{\text{res}}$$

   即：原始的图拉普拉斯算子$\mathbf{L}$$ \mathbf L $ 已经给出了大量有用的图结构信息，除了一些无法在原始图上给出的一些虚拟节点组成的子结构（由残差图表示）。

   因此，我们并不直接学习$\hat{\mathbf{L}}$$ \hat{\mathbf L} $ ，而是学习残差图的拉普拉斯矩阵${\mathbf{L}}_{\text{res}}$$ \mathbf L_\text{res} $ ，然后将${\mathbf{L}}_{\text{res}}$$ \mathbf L_\text{res} $ 并乘以$\alpha$$ \alpha $ 并添加到原始图的拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 上。

3. SGC-LL 层算法：

   • 输入：

     • 输入节点特征$\mathbf{X}$$ \mathbf X $
     • 拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $
     • 参数$\alpha ,\mathbf{M},\mathbf{W},\overrightarrow{\mathbf{b}}$$ \alpha, \mathbf M, \mathbf W, \mathbf{\vec b} $ （注意，$\theta$$ \theta $ 不再是参数）

   • 输出：输入特征$\mathbf{X}$$ \mathbf X $ 卷积后的信号

   • 算法步骤：

     • 根据下式计算新的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A } $ ：

       $$\begin{array}{c}D({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\sqrt{{({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j)}^{\mathrm{\top }}\mathbf{M}({\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j)}\\ G({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\exp (-\frac{D({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)}{2{\sigma }^2})\end{array}$$

       将$\mathbf{G}={\left\{G({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)\right\}}_{n\times n}$$ \mathbf G = \left\{G\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j\right) \right\}_{n\times n} $ 归一化后即可得到$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 。

     • 计算残差图的拉普拉斯矩阵：

       $${\mathbf{L}}_{\text{res}}=\mathbf{I}-{\hat{\mathbf{D}}}^{-1/2}\hat{\mathbf{A}}{\hat{\mathbf{D}}}^{-1/2}$$

       其中$\hat{\mathbf{D}}$$ \hat{\mathbf D} $ 为$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 的度矩阵。

     • 计算新的图拉普拉斯矩阵：$\tilde{\mathbf{L}}=\mathbf{L}+\alpha {\mathbf{L}}_{\text{res}}$$ \tilde{\mathbf L} = \mathbf L + \alpha \mathbf L_\text{res} $ 。

     • 计算卷积输出：$\mathbf{Y}=(\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }})\mathbf{W}+\overrightarrow{\mathbf{b}}$$ \mathbf Y = \left(\mathbf Ug_\theta(\mathbf \Lambda) \mathbf U^\top\right) \mathbf W + \mathbf{\vec b} $ 。

读者注：

1. 从 transductive 变为 inductive ：

   • GCN 使用针对$\theta$$ \theta $ 的参数化（并共享$\theta$$ \theta $ ），参数的数量为$n$$ n $ ，依赖于图大小，因此无法适用于各种不同大小的图。
   • 而 SGC 使用针对距离度量的马氏矩阵$\mathbf{M}$$ \mathbf M $ 的参数化（并共享$\mathbf{M}$$ \mathbf M $ ），参数的数量为$O(d^2)$$ O(d^2) $ ，不依赖于图大小，因此适用于各种不同大小的图。

2. 根据卷积公式：$\mathbf{Y}=\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}\mathbf{X}$$ \mathbf Y = \mathbf U g_\theta(\mathbf \Lambda) \mathbf U^\top \mathbf X $ ，传统的 GCN 主要参数化$g_{\theta }$$ g_\theta $ ，而 SGC 可以视为参数化$\mathbf{U}$$ \mathbf U $ （残差图改变了特征分解的基向量）。

3. 我们可以把 SGC 和 GraphSAGE 等基于消息传播机制的方法结合起来：首先，学习自适应图；然后，在自适应图上应用 GraphSAGE 。

   唯一的局限性在于：自适应图是稠密的（时间复杂度和空间复杂度都是$O(n^2)$$ O(n^2) $ ），因此可以采用剪枝从而使其稀疏化。

11.1.2 AGCN

1. 我们提出的网络称为自适应图卷积网络 Adaptive Graph Convolution Network:AGCN，因为 SGC-LL 层能够根据数据和目标任务有效地学习自适应的图拓扑结构。

   除了 SGC-LL 层之外，AGCN 还有图最大池化层 graph max pooling layer 、图聚合层 graph gather layer 。

a. Graph Max Pooling

1. 图最大池化层是feature-wise 的最大池化。假设节点$v_i$$ v_i $ 的特征为${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ ，邻域集合为${\mathcal{N}}_i$$ \mathcal N_i $ ，则$v_i$$ v_i $ 的池化层输出为：

   $$\begin{array}{c}{\hat{x}}_{i,j}=max\{x_{i,j},x_{v,j},v\in {\mathcal{N}}_i\}\\ {\widehat{\overrightarrow{\mathbf{x}}}}_i={({\hat{x}}_{i,1},\cdots ,{\hat{x}}_{i,d})}^{\mathrm{\top }}\end{array}$$

   即：池化层将$v_i$$ v_i $ 的第$j$$ j $ 个特征$x_{i,j}$$ x_{i,j} $ 替换为节点$v_i$$ v_i $ 及其邻域节点中第$j$$ j $ 个特征的最大值。

b.Graph Gather

1. 图聚合层逐元素地将所有节点的特征向量求和，从而作为图的 graph-level representation。

   聚合层的输出向量用于 graph-level 预测，也可以没有聚合层从而训练 AGCN 并将其作为 vertex-level 预测。

c. Bilateral Filter

1. 在 AGCN 中使用双边滤波器层 bilateral filter layer 用于防止过拟合。

   学到的残差图拉普拉斯矩阵自适应地适配训练集，但是可能会存在过拟合风险。为了缓解过拟合，我们引入修正的双边滤波器层，通过增加$\mathbf{L}$$ \mathbf L $ 的空间局部性来正则化 SGC-LL 层的输出。

   我们还引入了 BN 层来加快训练速度。

d. Network Configure

1. AGCN 由多个连续的layer combo 组合而成，其核心为 SGC-LL 层。每个 layer combo 包含一个 SGC-LL 层、一个 BN 层、一个图最大池化层，如下图所示。

   • 每个 SGC-LL 层都训练一个残差图的拉普拉斯矩阵。在随后的BN 层、最大池化层中使用自适应图adaptive graph （原始图 + 残差图），直到下一个 SGC-LL 层。

     由于 SGC-LL 层会转换特征，因此下一个 SGC-LL 层需要重新训练新的残差图。

     每一层都需要重新计算$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ ，因此空间复杂度和时间复杂度太高。我们是否只需要 input 的残差图，然后在后续层中固定使用这个残差图？

   • 在通过组合层之后，我们将批量更新图结构（因为每次训练一批样本，每个样本代表一个图）。

   • 本文中我们评估的是 graph-wise 任务，因此在回归器之前还有一个 graph-gather 层。

   

2. 对于像有机化合物这类数据，一些小的子结构对于特定的化学性质（如毒性）具有决定性作用。如：芳烃通常具有毒性，而如果氢原子被甲基取代，则毒性大大降低。

   因此，如果进行图粗化或者特征平均都会损害那些信息丰富的局部结构的完整性，因此我们选择最大池化，并且不跳过卷积中的任何节点。

11.1.3 Batch 训练

1. 图数据结构上进行卷积的最大挑战之一是难以匹配训练样本（每个样本代表一个图）的各种各样局部拓扑结构：

   • 这带来设计卷积核的额外困难，因为在图上不满足核的不变性，而且节点的顺序有时也很重要
   • 对于某些数据（如分子），对图进行粗化（即调整图大小）或者调整图的形状都是不合理的（破坏分子结构）

   与在张量上进行经典卷积的网格数据不同，对于图上的卷积必须兼容多种拓扑结构。为此，我们提出了 SGC-LL 层，它训练了自适应的图拉普拉斯矩阵，从而保留了数据的所有局部拓扑结构。

   我们发现在构建图结构时真正重要的是特征空间和距离度量，因此 SGC-LL 层要求每个 batch 的样本共享相同的特征变换矩阵和距离度量。此外，训练参数的数量仅取决于特征的维度$d$$ d $ 。因此，AGCN 可以进行 batch 训练，每个 batch 可以包含具有不同拓扑结构和大小的原始图。

   注意：在训练之前需要构造原始图的拉普拉斯矩阵，这会带来额外的 RAM 开销。但是我们仍然需要保留初始拉普拉斯矩阵从而更新自适应的拉普拉斯矩阵。但是，这是可以接受的，因为图拉普拉斯矩阵是稀疏的。

11.2 实验

1. 数据集：

   • 回归任务：

     • Delaney 数据集：包含 1144 种小分子量化合物的aequeous solubility 等效溶解度数据。数据集中最大的化合物包含 492 个原子，最小的化合物仅有 3 个原子。
     • NCI 数据集：包含大约 2 万种化合物，以及60 个从药物反应到临床药理学研究的预测任务。
     • Az-LogD 数据集：来自 ADME 数据集的 4200 种化合物渗透率的 logD 数据。
     • Hydration-free energy 数据集：我们提供的包含 642 个化合物的小型数据集，用于无水合能量研究。

     我们使用5 折交叉验证，并给出每个数据集中的平均 RSME 和标准差。

   • 分类任务：

     • Tox21 数据集：包含 12 篇论文中 7950 种化合物及其label，用于毒性分析。但是额外的困难来自于这 12 项任务中缺少部分标签。对于那些缺少标签的样本，我们将其从损失函数的计算中剔除，但是仍将其保留在训练集中。
     • ClinTox 数据集：包含 1451 种化合物的公开数据集，用于临床病理学研究。该数据集同时包含两个任务的标签。
     • Sider 数据集：包含 1392 种药物及其 27 种不同副作用或不良反应的标签。
     • Toxcast 数据集：另一个病毒学研究数据集，包含 8599 个 SMILES 以及用于 617 个预测任务的标签。

     对于 N-task 预测，图模型将构建为具有$N$$ N $ 个叶结点的$L$$ L $ 层树模型，每个叶结点包含一个全连接层和task-specific 逻辑回归输出层。

   • 点云数据：

     • Velodyne HDL-64E LIDAR 点云数据集：包含澳大利亚悉尼的 Velodyne HDL-64E LIDAR 扫描的街道对象。

       由于对象的实际大小和形状存在很大差异，因此不同对象的点数也不同。如下图所示：1 表示自行车，有 124 个点；2 表示卡车，有 615 个点；3 表示行人，有 78 个点。

       

2. baseline 方法：

   • GraphConv：《Spectral networks and locally connected networks on graphs》 使用由线性双样条插值构建的谱滤波器实现卷积。
   • NFP：神经网络指纹Neural Fingerprint:NFP，它在空域中构建滤波器实现卷积。
   • GCN：使用 《Convolutional neural networks on graphs with fast localized spectral filtering.》 提出的 K 阶局部化的谱卷积核来实现卷积。

3. 我们首先来验证 SGC-LL 层的效果。SGC-LL 层的滤波器基于自适应图 adaptive graph 来构建，而自适应图由原始图加残差图 residual graph 组成。原始图可以是数据直接给出的本征图 intrinsic graph （比如分子结构），或者是通过聚类得到的聚类图。网络以原始图作为输入，这使得AGCN 能够直接读取不同结构和大小的图。

   由于在网络训练期间会更新距离度量以及特征变换矩阵，因此在训练期间会不断更新自适应图（原因是残差图被不断更新）。实验证明：更新后的自适应图与模型的效果密切相关。

   如下图所示为化合物 C20N2O5S 的节点相似度矩阵（一个 28x28 的矩阵，以自适应图来构建的相似度矩阵）的热力度。左图为训练之前的相似度矩阵（记作 0），右图为训练了 20 个 epoch 之后的相似度矩阵。从放大的细节种我们明显发现在 20 个 epoch 之后，节点的相似性发生了显著变化。这意味着由于距离度量在训练中更新，化合物的自适应图的结构也发生了变化。

   

   同时，平均 RMSE 以及加权的 L2 损失函数在前 20 个 epoch 急剧下降。另外和baseline 方法相比，AGCN 在收敛速度、预测准确性方面都呈现压倒性优势。我们将这些提升归因于 SGC-LL 层的自适应图以及残差图的拉普拉斯矩阵的学习。

   

4. 首先我们对比不同的模型在回归任务上的表现。可以看到：AGCN 在 Delaney 数据集上的 RMSE 降低了 31%~40%，在 Az-logD 数据集上的 RMSE 降低了 15%，在 NCI 数据集上降低了 2% ，在 Hydration-free 数据集上降低了 35%。 看似来似乎当数据更为稀疏时，AGCN 更为有效。

   

   然后我们对比这些模型在多任务分类上的效果。可以看到 AGCN 提升了所有数据集上的效果。对于 Toxcast 的 617 项任务，AGCN 效果比 SOA 仍然提升了 3% 。

   

5. 由化学式给出的分子图是化合物的本征图，这些本征图从图的结构到图的大小多种多样。

   • GraphConv 的谱卷积核只能连接 1 阶邻居（通过边直接相连的邻居），因此它 over-localized 过于局部化。

     当处理分子图时这是一个问题，因为分子图的某些重要子结构无法被这种过于局部化的卷积核所覆盖。

   • GCN 中的 K 阶邻域卷积核不存在过于局部化的问题，但是它假设卷积核在不同样本之间共享（每个样本代表一个分子图）。

     • 如果训练集中的样本分子共享了很多常见的子结构，如 OH（羟基）、C6H6 （苯基），则这种共享效果很好（如下图所示）。

     • 如果训练集中的样本分子来自于各种类别的化合物，则它们的子结构千差万别。这时 GCN 效果很差。尤其是当某些类别的样本数据不足时。

       这也可能是为什么 GCN 在大型数据集 （如 Sider）上具有和 AGCN 差不多的性能，但是在小型数据集（如 Delaney 和 Clintox ）上效果很差的原因。

   • AGCN 能够以更好的方式处理分子数据。自适应图允许每个输入分子图具有不同的结构和大型，因此我们可以为 AGCN 提供原始数据而不会丢失任何信息。

     此外，SGC-LL 层针对任务目标来训练距离度量函数和其它变换参数。因此当模型收敛时，对于每层 SGC-LL 我们都将找到最适合的特征空间和距离度量来构建最适合的自适应图。最终学到的自适应图可能包含原始分子图中不存在的新的边。

   下图为不同Graph CNN 模型的卷积比较，其中红点为卷积核的中心，橙点为卷积核的卷积范围。边的颜色代表谱卷积核的权重。

   • 图 (1) 为 2 维网格上的经典 3x3 的CNN卷积核。
   • 图 (2) 为 GraphConv/NFP 卷积核，可以看到它过于局部化。
   • 图 (3) 为 GCN 卷积核，它时 K 阶局部化的，并且在所有输入图上共享。
   • 图 (4) 为 AGCN 卷积核，它也是 K 阶局部化的，但是它作用在自适应图上（原始图 + 残差图）。学到的残差图的边以虚线表示。

   

6. 最后我们考察点云数据集上的表现。初始的点云图是通过 agglomerative 聚类来构建的。

   • 在将点云数据馈入 Gaph CNN 之前，通常需要经过降采样来统一大小，这必然会丢失部分结构信息。而 AGCN 通过接受不同大小的原始点云图从而克服了该问题。
   • 如果使用 GCN，则 GCN 的卷积核在不同输入之间共享。这种共享的卷积核可能会混淆点云上的特征，而不考虑点之间的实际距离。而 AGCN 能够根据空间关系精确地进行卷积。
   • 点云识别的 SOA 方法为 PointNet，但是它无法处理大小变化的点云数据。

   我们采用 5 折交叉验证并报告了不同模型在测试集上的平均 ROC-AUC 得分。可以看到，AGCN 在 All Classes 上超越了所有其它方法。

   • 在大型对象（如建筑物）上，我们的 AUC 得分接近 1.0。其它 Graph CNN 模型效果较差，因为它们必须首先降采样。
   • 对于重要的道路物体（如交通信号灯），AGCN 将 ROC-AUC 的效果提升了至少 10%。

   数据表明：AGCN 在点云图上可以提取比其他 Graph CNN 更多有意义的特征。另外，AGCN 输入信息的完整性也有利于提升性能。