AGCN：自适应图大小的图卷积网络模型

论文标题｜ Adaptive Graph Convolutional Neural Networks
论文来源｜ AAAI 2018
论文链接｜ https://arxiv.org/abs/1801.03226
源码链接｜ https://github.com/uta-smile/Adaptive-Graph-Convolutional-Network

TL;DR

目前大部分 GCN 模型都是在固定大小的图结构上进行卷积操作，但现实中图的大小和结构都是不同的，因此这篇论文中提出一个通用且灵活的图卷积网络 AGCN 来解决存在的局限性。在训练过程中学习对于任意输入的图学习到一个任务驱动的自适应图表示，并且引入距离度量学习来更有效地学习图表示。实验过程中在九个图数据集中验证了本文提出的模型具有较高的收敛性和预测准确率。

Algorithm/Model

论文中提出的 AGCN 模型架构如下图所示：

从上面的模型图结构可知，AGCN 主要创新是使用 SGC_LL 卷积层来对不同大小的图进行卷积，当然模型中还有其他结构包括 Bilateral Filtering 、Graph Gather 结构等。下面主要来讲讲 SGC_LL layer 的设计思想

SGC-LL Layer

SGC-LL Layer 的主要作用是可以适应不同结构和大小的图来进行卷积操作，论文中主要引入了距离度量来参数化图拉普拉斯算法。

📢 这篇文章中的 SGC-LL Layer 是在二代图卷积网络中的卷积操作上进行改进，而不是现在流行的 GCN 框架。关于图卷积网络的背景知识可以参考另一篇文章图卷积网络 GCN（三）详解三代图卷积网络理论

Learning Graph Laplacian

对于图 $\mathcal{G}=(V, E)$ 及其对应的邻接矩阵 $A$ 和度矩阵 $D$ , 首先给定归一化的图拉普拉斯矩阵 $L$ 如下：

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

记得曾经有个同学问我为何拉普拉斯矩阵需要归一化？当时仅认为数学定义是这样的。实际上是为了使训练过程中不产生梯度爆炸或者梯度消失的问题。

**拉普拉斯矩阵为何要归一化？**解：采用加法规则时，对于度大的节点特征越来越大，而对于度小的节点却相反，这可能导致网络训练过程中梯度爆炸或者消失的问题。

由于归一化后的拉普拉斯矩阵是对称的正定矩阵，因此可以进行特征值分解为 $L=U \Lambda U^{T}$ ，其中 $U$ 是特征向量 $\left\{u_{s}\right\}_{s=0}^{N-1}$ 组成的矩阵，如果以 $U$ 为一组基来表示图的傅里叶变换，那么可以定义为 $\hat{x} = U^T x$ 。

详细推导过程也可以参考另一篇文章图卷积网络 GCN（二）图上的傅里叶变换和逆变换

对于图的拓扑结构可以使用谱 $\Lambda$ 表示（即拉普拉斯矩阵的特征值对角矩阵），因此谱滤波器 $g_{\theta}(\Lambda)$ 可以为图生成不同大小的卷积核，利用多项式表示为：

$g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}$

上式中的 $K$ 表示当前节点仅与路径长度为 $K$ 的节点进行卷积操作，距离越远那么对当前节点越小，通过参数 $\theta _k$ 进行控制。这就是第二代谱图卷积的近似计算方法，第三代谱图卷积就是令 $K=2$ ，直接融合当前节点及其邻居节点的特征。

那么问题来了！这种基于邻居近似计算就限制了谱图卷积核的灵活性，可能邻接节点的相似性比不邻接的节点更低，因为在一定情况下图的结构是固定的并不代表节点相邻特征相似。因此论文中重新定义了一种谱图卷积核参数化拉普拉斯矩阵 $L$ 而不是使用参数 $\theta_k$ 。给定拉普拉斯矩阵 $L$ 和节点特征矩阵 $X$ 及其参数 $\Gamma$

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

其中函数 $\mathcal{F}(L, X, \Gamma)$ 是更新的拉普拉斯矩阵 $\widetilde{L}$ 的谱。那么代入谱图卷积的公式得到 SGC_LL 的计算公式如下：

$Y=U g_{\theta}(\Lambda) U^{T} X=U \sum_{k=0}^{K-1}(\mathcal{F}(L, X, \Gamma))^{k} U^{T} X$

~~竟然没有讲 $\mathcal{F}(L, X, \Gamma)$ 中参数意义？~~下面的一些列操作就是为了计算更新的拉普拉斯矩阵 $\widetilde{L}$ 。由于此处涉及 $k$ 阶幂计算，论文中使用切比雪夫多项式展开计算。

Training Metric for Graph Update

对于图结构数据不适用图欧式距离来度量顶点间的相似性，因此在训练过程中需要根据任务特征来选择距离度量的方法。论文中用到的是马氏距离 (Mahalanobis Distance) 来度量图间的距离。

对于样本 $x_i$ 和 $x_j$ 间的马氏距离为：

$\mathbb{D}\left(x_{i}, x_{j}\right)=\sqrt{\left(x_{i}-x_{j}\right)^{T} M\left(x_{i}-x_{j}\right)} \quad\quad\quad\quad (6)$

上式中如果 $M$ 是单位矩阵 $I$ 那么就是欧式距离，在 AGCN 模型中 $M$ 是对称的半正定矩阵 $M=W_dW_d^T$ 且 $W_d \in \mathbb{R}^{d\times d}$ 是可训练的权重参数。基于马氏距离得到高斯核计算公式如下：

$\mathbb{G}_{x_{i}, x_{j}}=\exp \left(-\mathbb{D}\left(x_{i}, x_{j}\right) /\left(2 \sigma^{2}\right)\right) \quad\quad\quad\quad (7)$

对 $\mathbb{G}$ 进行标准化后得到 dense 的邻接矩阵 $\hat{A}$ ，在论文的模型中为了最小化预测损失需要基于图的拉普拉斯矩阵集合 $\{\hat{L}\}$ 优化 $\hat{W}_d$ 。这一步没太看懂怎么优化？

Re-parameterization on feature transform

为了构造节点内部和外部的特征映射，论文中引入了重参数（Re-parameterization） 对谱图卷积后的输出结果进行变换，可以直接理解为增加了一个全连接层：

$Y=\left(U g_{\theta}(\Lambda) U^{T} X\right) W+b \quad\quad\quad\quad (8)$

从这上面描述来看，现在每层 SGC-LL 具有参数 $\{ M_i, W_i, b_i\}$ ，这应该就是 $\mathcal{F}(L, X, \Gamma)$ 中参数 $\Gamma$ 的含义吧！

Residual Graph Laplacian

为了加速训练过程并且提升所学到图结构的稳定性，论文中假设模型优化的图拉普拉斯矩阵 $\hat{L}$ 仅与原始的拉普拉斯矩阵 $L$ 有微小的变化，因此模型直接学习残差图拉普拉斯矩阵而不是直接学习 $\hat{L}$ ，类似于 ResNet 的思路。

$\hat{L}=L+\alpha L_{r e s}\\ L_{r e s}(i)=\mathcal{L}\left(M_{i}, X\right)$

综上每层 SGC_LL Layer 的过程如下所示：

这个地方得总结下为什么 SGC_LL Layer 可以接受不同大小的图作为输入，要不然有点乱！对于每个输入的图，首先根据马氏距离构造的高斯核函数得到重构的邻接矩阵 $\hat{A}$ ，根据 $\hat{A}$ 得到残差拉普拉斯矩阵 $L_{res}$ ，再根据公式 (8) 谱图卷积方法进行计算。在这个过程中所有的参数 $\{ M, W, b, \alpha\}$ 不涉及图的大小维度 $N$ ，仅与图中节点的特征维度 $d$ 有关。

AGCN network

上面的 SGC_LL 层可以对任意大小的图进行卷积操作，除了这一卷积层 AGCN 还采用了 Graph Max Pooling 、Graph Gather 和 Bilateral Filter 层。

Graph Max Pooling
最大池化层是根据当前节点的邻居节点的特征值来进行池化，对于节点 $v$ 的新特征计算如下：

$\hat{x}_{v}(j)=\max \left(\left\{x_{v}(j), x_{i}(j), \forall i \in N(v)\right\}\right)$

Graph Gather
图聚集层是将所有节点的特征向量进行相加来表示整个图特征。这一层适用于图级别的预测任务，除去这一层也可以得到每个节点的特征，适用于节点级别的预测任务。
Bilateral Filter
为了防止过拟合，论文中使用双边过滤器通过扩充拉普拉斯矩阵 $L$ 的局部性来正则化 SGC_LL 的输出结果。这一点没有细讲计算方法，可以参考文中的引用文献。