论文标题：Spectral Networks and Locally Connected Networks on Graphs

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

论文来源：NeurIPS 2014

本文需要的前置知识：傅里叶变换与谱图理论基础

链接：

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

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

一、概述

CNN在机器学习领域内的一些问题上取得了比较成功的效果，这主要得益于它处理的底层数据通常有一个坐标网格结构（在1，2，3维度上），因此这些数据就存在平移不变性（ translational equivariance/invariance）。图像、语音、视频就属于这一类数据。由于网络不具备平移不变性（网络中的每个节点的邻居数量是不固定的），因此在网络上直接应用CNN是比较困难的。

对于常规的网格数据，CNN能够利用以下几个很好地结合在一起的结构来大大减少系统中的参数数量：

①平移结构（translation structure），使用滤波器在数据的网格结构上平移处理数据，从而实现参数共享，并没有使用线性映射；

②网格上的度量，使用紧凑支持滤波器（compactly supported filters），紧凑支持滤波器是指与输入数据大小无关的滤波器，它的大小可能远小于输入数据的大小；

③网格的多尺度二元聚类（multiscale dyadic clustering），是指CNN应用了跨步卷积（stride convolution）和池化（pooling）来进行下采样（subsampling）。

然而某些数据并不具备上述几何结构，比如表面张力或温度、从一个气象台网络中观测到的数据、来自社交网络或协同过滤的数据，这些数据都不能直接应用CNN。虽然CNN可以应用于多层，但是在特征维度上没有假设任何几何属性，导致一个4-D tensor只能沿其空间坐标进行卷积，即对于一个4-D的tensor而言，其有 四个维度，典型的CNN只能对 三个维度（即空间维度）进行卷积操作（通过3D convolution 操作），而不能对 维度（特征维度）进行操作。

网络提供了低维网格数据的一种泛化的框架，也就是GCN是CNN在domain上的推广，推广的方式是通过推广卷积的概念。在本文中将会讨论将深度卷积应用于网络数据的方法。本文一共提供两种架构。第一种为空域架构（spatial construction），这种架构能够对网络数据应用上述②和③，应用它们可以构建网络数据的局部连接网络，参数复杂度为 而非 。另一种架构称为频域架构（spectral construction），能够在傅里叶域内应用卷积。频域架构对于每一个feature map最多需要 的参数复杂度，也可以构建参数数量与 无关的架构。这两种架构都可以应用高效的前向传播并且能够应用在有多个坐标的数据的数据集上。

二、空域架构

2. 图的多尺度聚类

CNN通过池化和下采样来降低网格的大小，这一操作也就是网格的多尺度聚类（ multiscale clustering）：为每个cluster输入多个特征，输出一个特征。在图上被证明更为有效的聚类方法仍然有待研究，在本文中选择了一种比较朴素的聚类方法。如下图所示，下图中有两层聚类，灰色的点为数据中的无向图节点，然后进行聚类得到下一层带颜色的节点，然后再对这些带颜色的节点进行聚类，第一层为12个节点，第二层6个节点，第三层3个节点：

                                                  图上的聚类

3. 深度局部连接网络

                                               空域架构

4. 评价

这种架构的优点在于不需要很强的前提假设，只需要图具备邻域结构即可，甚至不需要很好的embedding向量。但是缺点在于没办法进行参数共享，对于每一层的每一个节点都要有单独的参数进行卷积而不能像CNN那样使用同一个卷积核在数据网格上进行平移。

三、频域架构

1. 图的拉普拉斯矩阵

③Random walk normalized Laplacian，也就是随机游走归一化拉普拉斯矩阵：

2. 加权图的调和分析

上面提到的一组特征向量其实就是 空间的一组基，前面的文章里说过图傅里叶变换其实就是将信号向量投影到拉普拉斯矩阵的各个特征向量上：

特征值的大小表示平滑程度，它对应传统傅里叶变换中的频率，频率高表示短时间内变动多，和这里的相邻节点变动大（变动越大越不平滑）能对应起来。因此图傅里叶变换就是在将一个图信号分解到不同平滑程度的图信号上，就像传统傅里叶变换将函数分解到不同频率的函数上一样。

3. 图卷积

两个函 数和 进行卷积可以应用卷积定理，用公式表达卷积定理就是：

应用卷积定理可以在频域上进行图的卷积操作，具体的方法是将滤波器 和图信号 都通过图傅里叶变换转换到频域然后计算转换后的结果的乘积（哈达玛积，也就是向量对应元素相乘），然后将相乘的结果再通过图傅里叶逆变换转换回空域，整个过程如下：

4. 频域架构

四、实验

本文中提出的两种架构在两个数据集上进行了实验验证效果。具体实验设置参看原论文，这里不做赘述。

1. 采样MNIST数据集

这个数据集是从MNIST数据集的每张图片（ ）上采样 个样本点构建图。实验样本如下图：

                                                  样本

实验结果如下图所示：

                                                    结果

2. 球体上的MNIST数据集

这个数据集将MNIST数据集中的样本提升到3维空间中。实验样本如下图：

                                                          样本

实验结果如下图所示：

                                              结果1

                                               结果2

参考资料

ref:图傅里叶变换

ref:paper reading：[第一代GCN] Spectral Networks and Deep Locally Connected Networks on Graphs