In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words' embedding, represented by graphs. We present a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Importantly, the proposed technique offers the same linear computational complexity and constant learning complexity as classical CNNs, while being universal to any graph structure. Experiments on MNIST and 20NEWS demonstrate the ability of this novel deep learning system to learn local, stationary, and compositional features on graphs.
核心贡献 · Key contributions
提出使用切比雪夫多项式的谱图 CNN 公式，实现快速局部滤波。 Proposes a spectral graph CNN formulation using Chebyshev polynomials for fast localized filtering.
实现线性计算复杂度 O(K|E|)和恒定学习复杂度 O(K)，与经典 CNN 相同。 Achieves linear computational complexity O(K|E|) and constant learning complexity O(K) like classical CNNs.
通过平衡二叉树重排引入高效的图池化策略。 Introduces an efficient graph pooling strategy via balanced binary tree rearrangement.
证明谱滤波器具有 K 跳支撑的严格局部性。 Demonstrates strict localization of spectral filters with K-hop support.
在 MNIST 和 20NEWS 数据集上展示出有竞争力的性能。 Shows competitive performance on MNIST and 20NEWS datasets.
提供开源 TensorFlow 代码以确保可复现性。 Provides open-source TensorFlow code for reproducibility.
局限 · Limitations
谱滤波器是各向同性的，在网格上缺乏方向敏感性。 Spectral filters are isotropic, lacking orientation sensitivity on grids.
性能严重依赖于输入图构建的质量。 Performance heavily depends on the quality of the input graph construction.
粗化产生的虚拟节点增加了维度和计算成本。 Fake nodes from coarsening increase dimensionality and computational cost.
模型未在百万节点的大规模图上测试。 Model not tested on large-scale graphs with millions of nodes.
文本的图构建使用 word2vec 嵌入，可能并非最优。 Graph construction for text uses word2vec embeddings which may not be optimal.
论文章节 · Sections（共 14）
摘要Abstract
1 引言1 Introduction
2 提出的技术2 Proposed Technique
2.1 学习快速局部谱滤波器2.1 Learning Fast Localized Spectral Filters
2.2 图粗化2.2 Graph Coarsening
2.3 图信号的快速池化2.3 Fast Pooling of Graph Signals
3.1 图信号处理3.1 Graph Signal Processing
3.2 非欧几里得域上的 CNN3.2 CNNs on Non-Euclidean Domains
4 数值实验4 Numerical Experiments
4.1 在 MNIST 上重新审视经典 CNN4.1 Revisiting Classical CNNs on MNIST
4.2 20NEWS 上的文本分类4.2 Text Categorization on 20NEWS
4.3 谱滤波器与计算效率的比较4.3 Comparison between Spectral Filters and Computational Efficiency