Source-linked AI summary
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst
TL;DR
CNNs are designed for regular grids, but many important data domains are represented by irregular graphs. This paper formulates CNNs with localized spectral graph filters and shows that the resulting model extracts graph features efficiently across image and text tasks.
Problem
The paper addresses how to generalize CNNs’ learning of local, stationary, and compositional features from regular grids to high-dimensional irregular graph domains.
Method
It formulates graph convolutions spectrally and parameterizes filters as localized polynomials evaluated recursively with sparse graph operators, avoiding the explicit Fourier basis.
Results
Experiments on MNIST and 20NEWS show that the model extracts local and stationary graph features, achieves near-standard-CNN performance on grid graphs, and scales linearly while outperforming prior spectral filters.
Takeaways & Limitations
The work provides an efficient graph-CNN formulation applicable to both regular-grid data and unstructured text represented by feature graphs.
Takeaways & Limitations
Graph-CNN performance critically depends on whether the input graph satisfies the data’s locality, stationarity, and compositionality assumptions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper generalizes CNNs to graph-structured data using spectral graph theory and graph signal processing. It proposes strictly localized filters, linear computational complexity, avoidance of Fourier bases, and efficient pooling for graph CNNs.
- Motivation: CNNs learn local stationary features and compose them into multi-scale hierarchical patterns, enabling breakthroughs in image, video, and sound recognition.This motivates extending CNNs beyond regular-grid data to irregular graph domains.
- Contributions: The paper formulates graph CNNs spectrally using established tools from graph signal processing.This provides the mathematical foundation for convolutional operations on graphs.
- Contributions: Graph filters are provably strictly localized within a ball of radius K, corresponding to K hops from the central vertex.The localization guarantee enhances prior spectral filtering approaches.
- Contributions: The filters have evaluation complexity linear in the support size K and the number of edges |E|, yielding linear complexity with respect to input size n.The method avoids Fourier bases and eigenvalue decomposition, while storing only the sparse Laplacian with |E| non-zero values.
- Contributions: The paper proposes an efficient pooling strategy as part of its graph convolutional architecture.Pooling is identified as one of the proposed ingredients for graph CNN layers.
2 Proposed Technique
The proposed graph CNN uses spectral graph convolutions with polynomial filters, recursive sparse computation, and learned multiscale pooling to extend localized, efficient CNN operations to irregular graphs.
- Overview: Graph CNNs require localized graph filters, graph coarsening that groups similar vertices, and pooling that trades spatial resolution for higher filter resolution.These three steps define the proposed generalization of CNNs to graphs.
- Spectral filtering: Spectral graph convolution defines filtering in the graph Fourier domain, where the Laplacian eigenvectors provide Fourier modes and its eigenvalues provide graph frequencies.The graph Fourier transform is ˆx = U^T x, with inverse x = Uˆx.
- Polynomial parametrization: Kth-order Laplacian polynomials produce exactly K-localized spectral filters with learning complexity O(K), matching classical CNNs.Localization follows because dG(i, j) > K implies (L^K)i,j = 0.
- Recursive formulation for fast filtering: Recursive evaluation of Chebyshev polynomial filters replaces O(n^2) Fourier-basis filtering with O(K|E|) operations using sparse Laplacian multiplications.The recurrence computes successive filtered signals from the scaled Laplacian.
- Learning filters: Training convolutional layers costs O(K|E|FinFoutS) operations for each forward or gradient computation, using sparse matrix-vector products and dense feature mixing.The intermediate Chebyshev responses only need to be computed once.
- Graph coarsening and pooling: Efficient graph pooling depends on approximate multilevel clustering and vertex arrangements that make pooling analogous to 1D pooling and suitable for parallel hardware.Graph clustering is NP-hard, while local memory accesses avoid fetching matched nodes separately.
3 Related Works
This section situates graph CNNs within graph signal processing and related geometric and neural approaches. It highlights prior spectral formulations and their scalability limitations due to graph Fourier-basis computations.
- Graph Signal Processing: Graph signal processing bridges signal processing and spectral graph theory to generalize operations from regular grids to graph-structured signals.The field combines graph theory and harmonic analysis, but standard grid operations do not directly extend to irregular graph structures.
- Graph Neural Networks: The Graph Neural Network framework embeds nodes in Euclidean space using a recurrent neural network for node or graph classification and regression.A simplified formulation replaces the learned transition with diffusion, yielding s = Wx.
- Geometric Deep Learning: A geometric deep learning architecture enabled comparisons across manifolds and achieved state-of-the-art results for 3D shape recognition.The passage describes this work as operating on mesh patches.
- Spectral Graph CNNs: A prior spectral graph CNN parameterized filters with a cubic B-spline basis, but its approach did not scale because it required graph Fourier-basis multiplications and Laplacian eigendecomposition.The dominant computational cost was the necessary multiplication by the graph Fourier basis U, beyond computing U itself via EVD.
4 Numerical Experiments
The numerical experiments evaluate graph CNNs on MNIST and 20NEWS, showing near-classical-CNN performance on grid data and applicability to unstructured text graphs. They also report localized-filter advantages in parameterization and computational scaling, while emphasizing that graph construction must preserve data structure.
- MNIST: MNIST uses an 8-NN graph of the 28 × 28 grid with n = 976 nodes and |E| = 3198 edges.The graph includes 784 pixels and 192 fake nodes.
- MNIST: On MNIST, the graph model achieves performance very close to a classical CNN with the same architecture.The reported gap may result from the isotropic nature of spectral filters, which lack pixel-edge orientations.
- 20NEWS: On 20NEWS, the method is evaluated on 18,846 documents from 20 classes using the 10,000 most common words and bag-of-words representations.The dataset contains 11,314 training and 7,532 testing documents.
- Filter comparison and complexity: The proposed Chebyshev parametrization outperforms Spline and non-parametric filters, while its computational complexity scales as O(n) instead of O(n2) for [4].The non-parametric filters are non-localized and require O(n) parameters.
- Graph construction: Classification performance depends critically on graph quality: a simple k-NN grid graph nearly recovers standard-CNN performance, whereas a random graph causes a large accuracy drop.The experiments also find that the value of k has little influence on results for Euclidean grid data.
5 Conclusion and Future Work
The paper develops foundations for efficiently generalizing CNNs to graphs using graph signal processing, with experiments showing extraction of local and stationary features. Compared with prior spectral graph CNNs, the model offers strict filter-support control and greater computational efficiency.
- The work introduces mathematical and computational foundations for an efficient generalization of CNNs to graphs using graph signal processing.
- Experiments show that graph convolutional layers can extract local and stationary features.
- Compared with the first spectral graph CNN, the model provides strict control over filter locality and improves computational efficiency by avoiding explicit use of the Graph Fourie.