论文标题：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

论文链接：https://arxiv.org/abs/1606.09375

论文来源：NeurIPS 2016

之前的文章：

①傅里叶级数与傅里叶变换

②图神经网络中的谱图理论基础

③第一代图卷积网络：图的频域网络与深度局部连接网络

一、概述

在将CNN泛化到图数据上的一个主要的瓶颈在于局部图卷积核的定义。本文在第一代图卷积神经网络上进行改进，定义了第二代图卷积神经网络，主要的贡献如下：

①谱图理论表达式：一种基于图信号处理（Graph Signal Processing，GSP）中已建立的工具的图上卷积神经网络的谱图理论公式。

②严格局部化的卷积核：本文提出的卷积核在中心节点的以 为半径的最短路径内是严格局部化的。

③低计算复杂度：本文提出的卷积核的复杂度是和卷积核的尺寸 以及边的数量 成线性关系的，另外由于大多数图稀疏的，我们可以估计地认为 ，也就是每个节点只和 个近邻有边，这样复杂度就和节点数量 成线性关系。另外本方法避免了使用傅里叶基底，因此不再需要进行昂贵的特征值分解以及存储傅里叶基底（使用一个 大小的矩阵）。除了数据，本方法只需要存储拉普拉斯矩阵这个包含 个非零值的稀疏矩阵。

④高效池化：本文提出了一种图上的高效池化策略。

⑤实验结果：通过实验证明了方法的有效性，并与其他方法进行了对比。

二、方法

将CNN泛化到图上需要3个基本步骤：

①设计图上的局部卷积核；

②图的粗化（coarsening）；

③图的池化（pooling）。

1. 学习快速局部谱卷积核
2. 
   

定义图卷积核的方法分空域（spatial）和频域（spectral）两种。空域的方法可以通过定义有限大小的卷积核来确保卷积核的局部性。卷积定理将卷积定义为在傅里叶基底（表示为拉普拉斯矩阵的特征向量）中对角化的线性算子，频域方法应用这一定理，然而频域卷积核存在两个限制：

①频域卷积核并非天然局部化；

②由于需要与图傅里叶基底相乘，会产生 的复杂度，转换成本很高。在本文中上述两个限制可以通过特殊的卷积核参数化选择来克服，这也是本文的主要内容之一。

• 图信号的谱卷积核

这里 ，是一个傅里叶系数向量，其实可以理解为卷积核与 相乘后的结果，这个结果的每一维相当于这一维对应的特征向量的系数。

• 局部卷积核的多项式参数化

前述非参数化的卷积核有两个局限性：

①这样的卷积核在空间上不是局部化的；

②他们的学习复杂度是 。

这些局限性可以通过采用多项式卷积核来解决：

• 应用递归多项式的快速卷积

• 卷积核的学习

2. 图的粗化

池化操作需要将相似的节点聚类到一起，对于多层网络来说做到这一点相当于对需要保持局部几何结构的图进行多尺度聚类（multi-scale clustering）。图的聚类方法存在多种，比如常见的谱聚类方法（参考链接：谱聚类|机器学习推导系列（二十））。在本文的方法中没有采用谱聚类这种方法，而是选择了一种近似能够将图的规模除以2的聚类方法，这样的方法可以精确控制粗化和池化的size。本文采用的图粗化方法为Graclus多尺度聚类算法。

Graclus方法采用一种贪婪的方法来计算给定图的连续的粗化的版本，并且能够最小化多种谱聚类的目标，在这里选择的目标为normalized cut。具体的方法是在每层进行粗化时，选择一个未标记的节点 ，然后选择一个能够最小化 的未标记的邻居节点，然后将这两个节点标记，这两个匹配的节点在池化时被合并，合并节点的信号是这两个节点的信号加和。上述匹配的过程一直进行下去知道所有节点被遍历。这种方法是非常快速的，并且能够将图的规模近似除以2，之所以近似是因为可能有一些未匹配的节点（文中称为singleton节点）。

3. 图信号的快速池化

池化操作被执行多次，所以必须是高效的。输入的图和粗化图的节点的排列方法是无意义的，因此，一个直接的池化操作的方法是需要一张表来保存匹配的节点，然而这种方法是内存低效的，并且缓慢，也不能并行处理。本文采用的方法可以使得池化操作像1D池化那样高效。

本文采用的方法分两个步骤：

①创建一个平衡二叉树；

②重排列所有节点。

在进行图的粗化以后，粗化图的每个节点要么有两个子节点（被匹配到的节点），要么只有一个节点（singleton节点）。从最粗到最细的图，将会添加fake节点（不与图连接在一起）到每一层来与singleton节点进行匹配。这样的结构是一个平衡二叉树，主要包含3种节点：

①regular节点（或者singleton节点），拥有两个regular子节点（如下图 level 1节点0）；

②regular节点（或者singleton节点），拥有一个regular节点和一个singleton节点座位子节点的节点（如下图 level 2节点0）；

③fake节点，总是拥有两个fake子节点（如下图 level 1节点1）。

fake节点的值初始化通常选择一个中性的值，比如当使用max pooling和ReLU激活函数时初始化为0。这些fake节点不与图的节点连接，因此卷积操作不会影响到它们。虽然这些节点会增加数据的维度，这样会增加计算的花费，但是在实践中证明Graclus方法所剩下的singleton节点是比较少的。在最粗化的图中任意排列节点，然后传播回最细的图中，这是由于粗化图中第 的节点的子节点是上一层图中的 节点，这样就可以在最细的图中有一个规范的排列顺序，这里规范是指相邻节点在较粗的层次上分层合并。这种pooling方法类似1D pooling。这种规范的排列能够让pooling操作非常的高效且可以并行化，并且内存访问是local的。下图是这种方法的一个例子：

                                             pooling

三、实验

这里简单列几个实验结果，具体实验设置可以自行参考原论文。

1. MNIST数据集上对比经典CNN

                                     MNIST数据集上对比经典CNN

2. 20NEWs数据集上多种架构效果

                  20NEWs数据集上多种架构效果

3. MNIST数据集上多种卷积核的对比

下图中Non-Param和Spline代表第一代GCN论文中提出的两种卷积核，Chebyshev代表本文提出的卷积核：

                          MNIST数据集上多种卷积核的对比

4. GPU加速效果对比

下图表明本文提出的GCN结构在使用GPU加速时比经典CNN能获得更多的加速倍数，说明该架构的并行化处理能力是比较可观的：

                                            GPU加速效果对比