二、GCN

1. 卷积神经网络 CNN 要求输入数据为网格结构，并且要求数据在网格中具有平移不变性，如一维语音、二维图像、三维视频都是这类数据的典型代表。CNN 充分利用了以下几个特点来大幅度降低模型的参数数量：

   • 权重共享：同一个卷积核可以应用于不同的位置。
   • 空间局部性：卷积核的大小通常都远远小于输入信号的尺寸。
   • 多尺度：通过步长大于一的卷积或者池化操作来减少参数，并获得更大的感受野 receptive field 。

   在网格数据结构中，顶点的邻居数量都是固定的。但是在很多任务中，数据并不是网格结构，如社交网络数据。在这些图数据结构中，顶点的邻居数量是不固定的。

   图结构是一种比网格结构更通用的结构，论文 《Spectral Networks and Deep Locally Connected Networks on Graphs》 在图结构上扩展了卷积的概念，并提出了两种构建方式：

   • 基于空域的卷积构建Spatial Construction ：直接在原始图结构上执行卷积。
   • 基于谱域的卷积构建Spectral Construction ：对图结构进行傅里叶变换之后，在谱域进行卷积。
2. 在网格数据中的卷积可以采用固定大小的卷积核来抽取特征；但是在图数据中，传统的卷积核无能为力。图卷积的本质是找到适合于图结构的可学习的卷积核。

2.1 空域构建

1. 空域构建主要考虑的是 CNN 的空间局部性、多尺度特点。

   给定图 ，其中 为大小为 的顶点集合， 为对称、非负的邻接矩阵。即这里为无向图。

   • 可以很容易的在图结构中推广空间局部性。对于顶点 ，定义其邻域为：

     

     其中 为阈值。

     在对顶点 卷积时我们仅考虑其邻域：

     

     其中 为顶点 的 representation 向量， 为卷积核。

   • CNN 通过池化层和下采样层来减小feature map 的尺寸，在图结构上我们同样可以使用多尺度聚类的方式来获得多尺度结构。

     在图上如何进行多尺度聚类仍然是个开发的研究领域，论文这里根据顶点的邻域进行简单的聚类。

     下图给出了多尺度层次聚类的示意图（两层聚类)：

     • 原始的12 个顶点为灰色，每个顶点可以同时被划分到多个聚类。
     • 第一层有6 个聚类，聚类中心为彩色顶点，聚类以彩色块给出。
     • 第二层有3 个聚类，聚类以彩色椭圆给出。

     

2. 现在考虑 个尺度。定义第 0 个尺度表示原始图，即 ；对于之后每个尺度的feature map，定义为 。我们采用聚类算法将feature map 划分到 个聚类，其中 为原始图的顶点数量 。

   定义 每个顶点的邻域集合的集合为：

   

   在 中的顶点就是原始图的顶点，在 中的顶点就是第 层聚类的中心点。

   不失一般性，假设 中原始图每个顶点的特征为标量。我们假设第 层卷积核的数量为 ，则网络的第 层将 维特征（因为第 层卷积核数量为 ）转化为 维特征。

   假设第 层网络的输入为：

   

   其中 的第 行定义为 为第 层聚类的第 个中心点的 feature ， 为第 层网络的输入 feature map 。

   网络第 层的输出经过三步：

   • 卷积操作：

     

     其中 表示输入通道， 表示输出通道， 表示当前顶点， 表示邻域顶点。

     写成矩阵的形式为：

     

     其中 表示卷积操作，卷积核 ，它和位置 有关，其定义为：

     

     则矩阵 仅仅在顶点 的邻域所在的列非零，其它列均为零。

   • 非线性层： 。其中 为非线性激活函数。

   • 聚类：通过 聚类算法（或者其它聚类算法）将 个顶点聚成 个簇。 算法将所有的顶点聚合为 个簇，使得簇内距离小于 、簇间距离大于 。

   • 池化层：

     构造池化矩阵 ，行表示聚类 cluster id，列表示顶点id ，矩阵中的原始表示每个顶点对应于聚类中心的权重：如果是均值池化，则就是 1 除以聚类中的顶点数；如果是最大池化，则是每个聚类的最大值所在的顶点。

     

   最终第 层网络的输出为：

   

   其中：矩阵 的第 行第 列表示顶点 的第 个卷积核的输出。

   如下图所示 。

   • 表示第零层，它有 12 个顶点（灰色），每个顶点只有一个通道（标量）
   • 表示第一层，其输入为 ，输出 6 个顶点，每个顶点有四个通道（四个卷积核）
   • 表示第二层，其输入为 ，输出 3 个顶点，每个顶点有六个通道（六个卷积核）

   每一层卷积都降低了空间分辨率spatial resolution，但是增加了空间通道数。

   

3. 和 的构建过程：

   • 初始化：

   • 构建簇中心连接权重：对于 ，其簇中心 之间的连接权重为两个簇之间的所有连接的权重之和：

     

     然后按行进行归一化：

     

   • 最后进行层次聚类，得到 和 。

     这里聚类按照对 的 得到，理论上也可以采取其它聚类算法。

4. 假设 为 中平均邻居数量，则第 层卷积的平均参数数量为：

   

   实际应用中我们可以使得 ， 为一个升采样系数，通常为 。

   其中 依次递减， 依次递增，总体有 ，而 。

5. 空域构建的实现非常朴素，其优点是不需要对图结构有很高的规整性假设 regularity assumption。缺点是无法在顶点之间实现权重共享。

2.2 图卷积

2.2.1 拉普拉斯算子

1. 给定向量场 ，设 为围绕某一点 的一个封闭曲面， 为曲面上的微元， 为该微元的法向量，则该曲面的通量为：

   

   当 趋近于零时，即可得到 点的散度：

   

   其中 。

   散度的物理意义为：在向量场中从周围汇聚到该点或者从该点流出的流量。

2. 给定向量场 ，设 为围绕某一点 的一个封闭曲线， 为曲线上的微元， 为该微元的切向量，则该曲线的环量为：

   

   当 趋近于零时，即可得到 点的旋度：

   

   • 在三维空间中，上式等于：

     

   • 旋度的物理意义为：向量场对于某点附近的微元造成的旋转程度，其中:

     • 旋转的方向表示旋转轴，它与旋转方向满足右手定则
     • 旋转的大小是环量与环面积之比

3. 给定函数 ，其中 ，则有：

   • 梯度：

     

     梯度的物理意义为：函数值增长最快的方向。

   • 梯度的散度为拉普拉斯算子，记作：

     

     • 由于所有的梯度都朝着 极大值点汇聚、从 极小值点流出，因此拉普拉斯算子衡量了空间中每一点，该函数的梯度是倾向于流出还是流入。
     • 拉普拉斯算子也能够衡量函数的平滑度smoothness：函数值没有变化或者线性变化时，二阶导数为零；当函数值突变时，二阶导数非零。

4. 假设 为离散的一维函数，则一阶导数为一阶差分：

   

   二阶导数为二阶差分：

   

   一维函数其自由度可以理解为2，分别是 +1 和 -1 两个方向。因此二阶导数等于函数在所有自由度上微扰之后获得的增益。

   推广到图 ，其中顶点数量为 。假设邻接矩阵为 ，任意两个顶点之间存在边（如果不存在边则 ）。对于其中任意顶点 ，对其施加微扰之后该顶点可以到达其它任意顶点，因此图的自由度为 。

   令 为函数 在顶点 的值，定义 ，它表示函数 在图 上的取值。对于顶点 ，其扰动到顶点 的增益时 ，不过这里通常写成负的形式，即 。考虑到边的权重，则增益为： 。

   对于顶点 ，总的增益为拉普拉斯算子在顶点 的值。即：

   

   其中 为顶点 的邻域， 为图的度矩阵。

   考虑所有的顶点，则有：

   

   定义拉普拉斯矩阵 ，因此在图的拉普拉斯算子就是拉普拉斯矩阵。

   上述结果都是基于 为标量推导，实际上当 为向量时也成立。

5. 图的拉普拉斯矩阵 是一个半正定对称矩阵，它具有以下性质：

   • 对称矩阵一定有 个线性无关的特征向量，其中 为顶点数。
   • 半正定矩阵的特征值一定是非负的。
   • 杜晨矩阵的特征向量相互正交，即：所有特征向量构成的矩阵为正交矩阵。

   因此有拉普拉斯矩阵的谱分解：

   

   其中 为第 个特征向量， 为第 个特征值。

   解得： ，其中 ：

   

   每一列为特征向量构成的正交矩阵， 为对应特征值构成的对角矩阵。

2.2.2 卷积

1. 给定函数 ， 其傅里叶变换为：

   

   其中 为傅里叶系数，即频率为 的振幅， 为傅里叶基 fouries basis 。

   可以证明： 为拉普拉斯算子的特征函数。证明：

   

2. 如果将傅里叶变换推广到图上，则有类比：

   • 拉普拉斯算子对应于拉普拉斯矩阵 。

   • 频率 对应于拉普拉斯矩阵的特征值 。

   • 傅里叶基 对应于特征向量 。

   • 傅里叶系数 对应于 ，其中

     

     写成矩阵形式为：

     

     其中 为图的傅里叶变换，它是不同特征值下对应的振幅构成的向量； 为顶点特征构成的 维向量。

   • 传统的傅里叶逆变换：

     

     对应于：

     

     其中 对应于特征向量 的第 个分量。

     写成矩阵的形式为：

     

   因此图的傅里叶变换是将图从Spatial Domain 转换到 Spectural Domain 。

3. 卷积定理：两个函数在时域的卷积等价于在频域的相乘。

   

   对应于图上有：

   

   其中 为逐元素乘积， 为拉普拉斯矩阵 特征向量组成的矩阵， 为对角矩阵：

   

   这里将逐元素乘积转换为矩阵乘法。

4. 图卷积神经网络的核心就是设计卷积核，从上式可知卷积核就是 。我们可以直接令 ，然后学习卷积核：

   

   我们并不关心 ，仅仅关心傅里叶变换之后的 。

2.3 频域构建

1. 假设构建一个 层的卷积神经网络，在第 层将输入的 feature map 映射到 ，则第 层网络为：

   

   其中 表示 的第 列， 为非线性激活函数， 为拉普拉斯矩阵特征向量组成的矩阵， 为第 层针对第 个 feature map 的第 个卷积核。

   将 按列进行计算，则根据空域构建的傅里叶变换有：

   

   • 实际应用中，通常仅仅使用拉普拉斯矩阵的最大 个特征向量，截断阈值 取决于图的固有规整性 regularity 以及图的顶点数量。此时上式中的 替换为 。这可以减少参数和计算量，同时去除高频噪声。

   • 第 层卷积核的参数数量为： 。

   • 非线性必须作用在空域而不是频域，这使得我们必须使用代价很高的矩阵乘法将频域的卷积结果映射回空域。

     如何在频域进行非线性处理目前还未解决。

2. 我们还可以使用三次样条插值来增加平滑约束。具有空间局部性的函数（如脉冲函数）在谱域具有连续的频率响应。

   此时有：

   

   其中 为三次样条核函数， 为 个样条参数， 代表第 层网络， 代表第 个输出feature map， 代表第 个输入 feature map 。

   假设采样步长正比于顶点数量，即步长 ，则 ， 则频域卷积的参数数量降低为： 。

3. 三次样条曲线：给定以下顶点： ，其中 ，定义样条曲线 ，它满足以下条件：

   • 在每个分段区间 ， 为一个三次多项式，且满足
   • 函数 、一阶导数 、二阶导数 在 [a,b] 上是连续的。

   令 ，则有：

   

   令 ，则有：

   • 根据 得到：

   • 根据 得到：

     

   • 根据 得到：

     

   • 根据 得到：

     

   令 ，则可以得到：

   

   代入 有：

   

   由 的取值范围可知，一共有 个公式，但是却有 个未知量。如果需要求解方程，则需要两个端点的限制。有三种限制条件：

   • 自由边界Natural：首尾两端的曲率为零，即 ，即 。则有：

     

   • 固定边界Clamped：首位两端的一阶导数被指定，即 ，即 。则有：

     

   • 非结点边界Not-A-Knot ：指定样条曲线的三次微分匹配，即 。则有：

     

     不同边界的效果如下：

     

4. 频域卷积的问题：

   • 计算复杂度太高。我们需要对拉普拉斯矩阵进行谱分解求解 ，当图很大时谱分解的计算代价太大。另外每次前向传播都需要计算矩阵乘积，其计算复杂度为 。
   • 每个卷积核的参数数量为 ，当图很大时参数数量太大。
   • 卷积的空间局部性不好。

2.4 实验

1. 论文对 MNIST 数据集进行实验，其中MNIST 有两个变种。所有实验均使用 ReLU 激活函数以及最大池化。

   模型的损失函数为交叉熵，初始学习率为0.1 ，动量为 0.9 。

2.4.1 降采样 MNIST

1. 我们将MNIST 原始的 28x28 的网格数据降采样到 400 个像素，这些像素仍然保留二维结构。由于采样的位置是随机的，因此采样后的图片无法使用标准的卷积操作。

   采样后的图片的示例，空洞表示随机移除的像素点。

   

   采用空域卷积进行层次聚类的结果，不同的颜色表示不同的簇，颜色种类表示簇的数量。图 a 表示 ，图 b 表示 。可以看到：层次越高，簇的数量越少。

   

   采用频域卷积的拉普拉斯特征向量（特征值降序排列）的结果，结果经过了傅里叶逆变换。图a 表示 ，图b 表示 。可以看到：特征值越大的特征向量对应于低频部分，特征值越小的部分对应于高频部分。

   

2. 不同模型在 MNIST 上分类的结果如下。基准模型为最近邻模型 kNN ，FCN 表示带有 N 个输出的全连接层，LRFN 表示带有 N 个输出的空域卷积层，MPN 表示带有 N 个输出的最大池化层，SPN 是带有 N 个输出的谱域卷积层。

   • 基准模型 kNN 的分类性能比完整的（没有采样的）MNIST 数据集的 2.8% 分类误差率稍差。
   • 两层全连接神经网络可以将测试误差降低到 1.8% 。
   • 两层空域图卷积神经网络效果最好，这表明空域卷积层核池化层可以有效的将信息汇聚到最终分类器中。
   • 谱域卷积神经网络表现稍差，但是它的参数数量最少。
   • 采用平滑约束的谱域卷积神经网络的效果优于常规的谱域卷积神经网络。

   

3. 由于 MNIST 中的数字由笔画组成，因此具有局部性。空域卷积很明确的满足这一约束，而频域卷积没有强制空间局部性。

   • 图 (a),(b) 表示同一块感受野在空域卷积的不同层次聚类中的结果。
   • 图 (c),(d) 表示频域卷积的两个拉普拉斯特征向量，可以看到结果并没有空间局部性。
   • 图 (e),(f) 表示采用平滑约束的频域卷积的两个拉普拉斯特征向量，可以看到结果有一定的空间局部性。

   

2.4.2 球面 MNIST

1. 我们将MNIST 图片映射到一个球面上，构建方式为：

   • 首先从单位球面上随机采样 4096 个点 。
   • 然后考虑三维空间的一组正交基 ，其中 ，以及一个随机方差算子 ，其中 是一个方差为 的独立同部分的高斯分布的分布矩阵。
   • 对原始 MNIST 数据集的每张图片，我们采样一个随机方差 并考虑其PCA 的一组基 。这组基定义了一个平面内的旋转。我们将图片按照这组基进行旋转并使用双三次插值将图片投影到 上。

   由于数字 6 和 9 对于旋转是等价的，所以我们从数据集中移除了所有的 9 。

   下面给出了两个球面 MNIST 示例：

   

   下面给出了频域构建的图拉普拉斯矩阵的两个特征向量。结果经过了傅里叶逆变换。图a 表示 ，图b 表示 。可以看到：特征值越大的特征向量对应于低频部分，特征值越小的部分对应于高频部分。

   

2. 首先考虑“温和”的旋转： ，结果如下表所示。

   • 基准的 kNN 模型的准确率比上一个实验（随机采样 MNIST ）差得多。
   • 所有神经网络模型都比基准 KNN 有着显著改进。
   • 空域构建的卷积神经网络、频域构建的卷积神经网络在比全连接神经网络的参数少得多的情况下，取得了相差无几的性能。

   

3. 不同卷积神经网络学到的卷积核如下图所示。

   • 图 (a),(b) 表示同一块感受野在空域卷积的不同层次聚类中的结果。
   • 图 (c),(d) 表示频域卷积的两个拉普拉斯特征向量，可以看到结果并没有空间局部性。
   • 图 (e),(f) 表示采用平滑约束的频域卷积的两个拉普拉斯特征向量，可以看到结果有一定的空间局部性。

   

4. 最后我们考虑均匀旋转，此时 代表 中的随机的一组基，此时所有的模型的效果都较差。这时需要模型有一个完全的旋转不变性，而不仅仅是平移不变性。