Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
摘要
本文主要研究将CNN从低维的规则化网格(如图像、视频或语音)推广到用图表示的高维不规则域(如社交网络、大脑连接体或单词嵌入)。
我们在谱图论的背景下提出了一个CNN的公式，它为在图上设计快速局部化卷积滤波器提供了必要的数学背景和有效的数值方案。
重要的是，该技术提供了与经典CNN相同的线性计算复杂度和常量学习复杂度，同时适用于任何图结构。在MNIST和20NEWS上的实验证明了这种新型深度学习系统学习图的局部、平稳和组合特征的能力。
引言
卷积神经网络提供了一种有效的架构，用于在大规模高维数据集中提取高度有意义的统计特征。CNN学习局部平稳结构并将其组合以形成多尺度层次模式的能力已在图像、视频和声音识别任务中取得突破。准确地说，CNN通过揭示跨数据域共享的局部特征来提取输入数据或信号的局部平稳性。这些相似特征通过从数据中学习的局部卷积滤波器或核来识别。卷积滤波器是移位或平移不变滤波器，这意味着它们能够独立于空间位置识别相同的特征。本地化内核或紧凑支持的过滤器是指独立于输入数据大小提取局部特征的过滤器，其支持大小可以远小于输入大小。
社交网络上的用户数据、生物调控网络上的基因数据、电信网络上的日志数据或文字嵌入上的文本文档是位于不规则或非欧几里德域上的数据的重要示例，这些域可以用图进行结构化，图是异构成对关系的通用表示。图可以对复杂的几何结构进行编码，并且可以使用强大的数学工具（如谱图论）进行研究。
将CNN推广到图并不简单，因为卷积和池化算子仅针对规则网格定义。这使得这种扩展在理论和实现上都具有挑战性。将CNN推广到图的主要瓶颈，也是这项工作的主要目标之一，是定义高效评估和学习的局部图过滤器。确切地说，这项工作的主要贡献总结如下。
谱公式。基于图信号处理
GSP中已有的工具，建立了图上CNN的谱图理论公式。严格意义上的局部滤波器。增强了文献
[4]，可以证明所提出的谱滤波器严格局限于半径为K的球中，即距离中心顶点的K步。计算复杂度低。我们的滤波器的评估复杂度是线性的，关于滤波器支持的大小 $K$ 和边数 $\vert \mathcal{E} \vert$。重要的是，由于大多数真实世界的图都是高度稀疏的，对于广泛分布的
k-最近邻图，我们有 $\vert \mathcal{E} \vert \ll n^{2}$ 和 $\vert \mathcal{E} \vert = kn$，这导致了线性复杂度，也就是与输入数据大小 $n$ 无关。此外，该方法完全避免了傅立叶基，因此计算它所需的昂贵的特征值分解（EVD）以及存储基（大小为 $n^{2}$ 的矩阵）的需要。这在使用有限的GPU内存时尤其重要。除了数据之外，我们的方法只需要存储拉普拉斯矩阵，即 $\vert \mathcal{E} \vert$ 非零值的稀疏矩阵。有效的池化。我们在图上提出了一种有效的池化策略，在将顶点重新排列为二叉树结构后，该策略类似于一维信号的池化。
实验结果。我们进行了多次实验，最终证明我们的公式
- 是一个有用的模型
- 计算效率高
- 在精度和复杂度方面优于[4]中介绍的先锋谱图CNN。
我们还表明，我们的图公式在
MNIST上的性能类似于经典CNN，并研究了各种图结构对性能的影响。TensorFlow代码可以作为开源软件提供，用于重现我们的结果并将模型应用于其他数据。
拟议技术
将CNN推广到图需要三个基本步骤：
- 设计图上的局部卷积滤波器
- 将相似顶点分组的图粗化过程
- 将空间分辨率转换为更高的滤波器分辨率的图池操作。