Spectral Networks and Deep Locally Connected Networks on Graphs
Code link:
摘要：CNN在图片识别与语音等任务上取得很大的成功，由于其具有局部转变不变性，在本文中，探索一种可能的CNN应用于更多的领域，特别的，我们提出一种基于层次聚类的框架，另外是基于图拉普拉斯谱图的，展示了低维图上使用少量参数来运用卷积层，表现很好的性能
1 引言
CNN面对机器学习问题取得成功，其潜在的数据表征存在1-3维框架，数据被研究在这些对应的坐标上不变性/不变性，语言【11】，图片【14】【20】【22】，视频【23】【18】都归于此类，CNN能组合架构并减少参数
- 翻译结构、使用卷积核并非线性映射所以共享权重
- 规则格子内度量，紧凑的卷积核，可以支持比输入图片小的多个卷积核
- 多尺度的双积汇聚，可以子采样、使用步长与池化
如果d维有n个输入坐标，全连接有m个输出，需要n*m个参数，O（n^2）参数级别；如果使用使用任意卷积核，可以减少到O（n）参数在每个特征图上；通过建立局部连接框架网络[8]【17】使用度量结构；使用两者结合在一起使用O(K*S)参数，k为特征图的数量，S是支持的卷积核，作为结果的学习复杂度为n，使用多尺度聚簇使得连续层使用2^d因子每个过滤器；
然而在很多领域，缺少相应的坐标，几何属性，例如三维图上表面张力与温度图，气象台数据、社交网络等无法使用标准的卷积网络；另外一个是神经网络结构的中间表达，即使空间卷积结构可以使用几层，经典CNN不能假设任何几何都在特征空间；
图提供了更加一般性的低维度网格框架并扩展了卷积的概念，本文中提出了深度神经网络在图上的应用，提出了两种框架，在第一个框架中，把性质2、3扩展到图中，使用局部连接与池化层，构造了复杂度为O(n)的空间架构；另一个是在傅里叶域的卷积，可以进行高效的前向传播能够应用到大型的数据集中；
1.1贡献
在输入域 展示了一种弱几何结构可以达到高效的框架，使用O(n)的参数，并在低纬度图 数据集 得到验证
引入一种O（1）的参数验证，讨论了其在图上的与谐波分析的联系
2 空间结构
CNN最直接的概况生成图需要考虑多尺度、分层次、局部接受野【3】，用权重图G=（Ω，W）Ω是离散尺寸节点，W是m*m的对称非负矩阵
2.1 通过W定位
图中的定位很简单，使用图中节点之间的权重来确定，直接的方法是定位邻节点在矩阵W上，可以将注意力限制在稀疏过滤器上，接受域由邻居提供，以获得局部连接的网络
2.2 图上的多分辨率分析
CNN减少尺寸通过池化与子采样层，在图上使用多尺度汇聚特征图并单特征的输出，网格中，二元聚类在度量与拉普拉斯行列式方面表现的很好，大量的文献资料在多尺度聚类方面【16】【25】【6】【13】。多尺度聚类在图上是个开放性的研究在 拉普拉斯方法做的很好，这里我们使用朴素的聚类方法
2.3 深度局部网络
在图上多尺度空间聚类与【3】类似，可以认为K个尺寸，定义k层网络，假设没有一般性损失，信号是真是的信号，fk是过滤器的数量，每一层都将fk-1维信号转换为fk维信号，空间分辨率与定位特征点的平衡；
Lk是池化、h() 函数 F k I j 是稀疏矩阵，创建过程如图2所示
具体可以参考文献【10】
Sk 是领节点的均值，验证公式2.1 在k 层的参数数量是
图是低纬定位领节点，并未更好的全局嵌入退出机制，然而没有简单的方式进行不同位置的权重共享。
3谱结构
使用图的拉普拉斯生成对图的卷积操作
3.1 对权重图的谐波分析
拉普拉斯矩阵以及其归一化矩阵L = D-A 归一化的矩阵L = I − D−1=2W D−1=2
频率和相对W的平滑度通过这些算子相互联系【2】【25】，简单起见使用拉普拉斯矩阵，
如果x是个m维度的向量，在每个节点上的定义平滑函数是
每个连续的vi 是L的特征向量，特征值从x的系数读出平滑系数，相应的作为傅里叶信号系数，因此拉普拉斯的特征向量是傅里叶特征向量，拉普拉斯的谱对角操作修改操作数的平滑系数，而且使用对角操作可以减少过滤器的参数从m的平方到m.
这三种结构紧密的连结拉普拉斯的操作在d维网络中
- 卷积核是在拉普拉斯特征值的乘法器
- 平滑函数系数有快速的衰减
- 子采样的拉普拉斯特征向量是低纬度的特征向量
3.2通过拉普拉斯谱扩充卷积
W是权重图，V是L的特征向量，给予一个权重图我们可以尽量卷积通过操作谱权重，依据图拉普拉斯的特征向量，使用下列函数作为传播函数
通常，使用特征向量中前几个，其携带图的几何性，截至频率取决于图的规则性与尺寸，在图中有很多潜在在图的不变性等待发现，不能像标准CNN一样，图的结构是不同的，在不同的位置需要使用不同的模板，图并非都是同质的，图的全局与局部特征可以产生O（1）参数，比如说可以学习的参数的数量并不却决于输入的尺寸；
这种结构可能会受到这样一个事实的影响，即大多数图只有在谱的最顶端才有有意义的特征向量。即使个别的高频特征向量是没有意义的，一组高频特征向量可能包含有意义的信息。
但是这个结构可能无法访问这个信息，因为它在最高频率上几乎是对角的；
最后，无论是前向还是后向传播算法应用线性运算并不明显，在频谱上使用高昂的乘法也不明显。
3.3 标准CNN的重新发现
简述了数据的协方差为权重矩阵的构建，数据都符合统一的分布特性，拉普拉斯的分解操作简化为信号的主成分度量，图片的主成分与DCT的系数相对应反映在频率方面，这被解释为图像的平移不变性，并且自然图像信号符合从低到高的频率与相邻像素的联系更加紧密，其包含标准的傅里叶成分构建；
我们使用协方差作为相似的核恢复作为标准的无先验知识的卷积网络，相应的在傅里叶上面体现，作为平移不变性；
3.4 O(1) 构建平滑的谱乘法器
在规则的网格中，不需要参数对每个傅里叶函数因为其紧密的在空间范围内，但是本文中每个过滤器需要一个参数对于特征值，即便过滤器紧凑在空间分别，也不能少于O（n）参数级在空间每个位置对应不同的空间响应
在欧式网格中，在空间谱上函数的衰减转化为傅里叶域的平滑，反之亦然；本文中，拉普拉斯的特征向量可被认为原始空间网格的同构，此表明特征学习要进行位置与原始域的分享，然而平滑的引用会需要谱域的坐标的测量，通过3.1的W，但并不能扩展到其他图
使用策略对谱域坐标的策略，需要考虑输入信号空间的分别，测量其相似度使用W表示，公式是
4 与之前工作的联系
有大量的工作关于图上的小波变化【21】【7】【4】【5】【9】，小波系数在网格中，在神经网络中其为拥有正则性质的线性自动编码器，经典网络最后中，小波变化与神经网络中前向传播相似，在图这方面，目的是相同的，多数工作是基于图的建立小波，经过训练所有从稀疏到平滑处理是适合的，然而【21】其建立线性编码器，此工作在于非线性的构建，另外是从数据中找到拓扑结构，在【19】中，作者强调验证3.3的借助二次统计恢复二维结构；在【3】【12】中作者强调在特征中构建局部连接网络
4.1 多重网络
两种结构在一定程度上统一他们，多尺度聚集在拉普拉斯发挥作用，正如之前所示，标准的立方将傅里叶函数抽样到较粗的傅里叶函数相同的特性，其消除了将谱结构映射到网格上进行非线性处理的必要性并可以通过插值实现空间结构更深层次的局部滤波器转为会低频
使用【24】多重网格方法，使用空间的建构不能保证遵循原始图的拉普拉斯，在谱建构上无明确的空间聚类
5 数值实验
使用mnist数据集，首先使用28*28的方格得到400个坐标，这些坐标是二维结构，但是不能使用标准卷积，我们使用d=4096*4096的点映射到3维上，然后随机映射图片到一组点 如5.2所描述
在此实验中，使用RLU与最大池化，使用交叉熵函数损失，学习率0.1 momentum 0.9
5.1 子采样mnist
运用3.2、2.3的章节进行子采样，图三是输入信号的结果，图4、5分别是图的多层聚类建构与图的图的拉普拉斯特征函数，图结构如表1所示，作为基线，进行最近领分类，其性能比全部的MNIST低2.8%，两层卷积CNN错误为1.8%，局部视野的效果优于全连接网络，特别的是两层过滤与最大池化能够高效聚类信息，基于谱的结构稍微糟糕一点，我们考虑频域的一半 N/2=200,然而 3.4描述的频域结构包含最少的参数，却性能最佳
结果分析如下，手写体识别需要强调方向空间的定位，局部视野满足这个需求，谱域并不能进行空间定位，平滑限制提高性能，因为过滤器可以进行更好的空间定位；
事实如图6所示，我们验证不同接受野与不同的空间领域， c d 对应谱乘不受约束、受到约束、对应傅里叶分析编码的局部分析的限制；e-f 拉普拉斯通过图谱恢复某种形式的空间定位，创建过滤器与不同位置的泛化，这正是卷积运算所期望的
5.2 mnist在球体
最后,我们考虑均匀旋转的情况,现在Ui是一个随机R3的基础的基础。在这种情况下,内部类的可变性更严重,如通过检查最近邻分类器的性能。所有以前描述神经网络体系结构显著改善在这个分类器,虽然性能明显比在轻微旋转场景中。在这种情况下,需要一种有效表示完全roto-translation不变。由于这是一个non-commutative很可能比这里模型考虑更深层次的架构表现得更好
6 结论
使用基于图的卷积架构的类似物可以在减少(通常是改善)测试误差的情况下，大大减少神经网络中的参数数量，同时提供更快的正向传播。这些方法可以扩展到具有大量具有局部性概念的坐标的数据。这里有许多事情要做。我们怀疑，通过更仔细的训练和更深层次的网络，我们可以持续改进流形图上的‘流形’网络，比如采样球面。
此外，我们打算将这些技术应用到不那么复杂的问题上，例如在推荐问题，那里有一个数据和坐标的集合。最后，在特征向量的朴素排序上的平滑性导致了改进的结果和局部化的滤波器，这一事实表明，有可能使每个滤波器具有O(1)参数的“对偶”结构比网格具有更大的通用性。