Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
Michaël Defferrard Xavier Bresson Pierre Vandergheynst EPFL, Lausanne, Switzerland
Abstract
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.
中文速览
把卷积神经网络（CNN）从图像、语音等规则网格数据推广到社交网络、脑连接组等不规则图结构数据，一直是深度学习的难题，核心障碍在于如何在图上定义既高效又有空间局部性的卷积滤波器。本文基于谱图理论，用切比雪夫多项式对图拉普拉斯算子进行参数化，从而构造出严格局限在K跳邻域内的局部滤波器，并结合Graclus多层聚类算法实现图上的池化操作，整体计算复杂度与图的边数成线性关系，完全避免了昂贵的特征值分解。在MNIST和20NEWS两个数据集上的实验表明，该方法不仅与经典CNN精度相当，还在准确率和计算效率上显著优于此前的谱图CNN方法。这项工作为把深度学习应用于任意图结构数据提供了一套兼具理论保证和工程可行性的通用框架，对社交网络分析、生物信息学等大量非欧几里得数据场景具有重要意义。
原文 arXiv:1606.09375;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1606.09375v3