Source-linked AI summary
Spectral Networks and Locally Connected Networks on Graphs
Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann LeCun
TL;DR
Standard CNNs do not directly apply to signals on domains without grid-like geometry, motivating graph-based generalizations. The paper proposes spatial and spectral graph convolutions and finds they reduce parameters without worsening, and often improving, test error while accelerating forward propagation.
Problem
Standard convolutional networks cannot directly exploit data defined on domains lacking regular geometric structure, including graphs, meshes, and social networks.
Method
The paper develops spatial locally connected and spectral graph convolution constructions using hierarchical clustering and graph-Laplacian eigenvectors.
Results
Graph-based convolutional architectures reduce parameters without worsening, and often improving, test error while providing faster forward propagation.
Takeaways & Limitations
Graph convolutional analogues can scale neural networks to large-coordinate data when the domain has a notion of locality.
Takeaways & Limitations
The authors do not yet consistently improve on fully connected networks for manifold-like graphs and identify deeper networks and more careful training as future needs.
Abstract
from arXiv · showhide
Convolutional Neural Networks are extremely efficient architectures in image and audio recognition tasks, thanks to their ability to exploit the local translational invariance of signal classes over their domain. In this paper we consider possible generalizations of CNNs to signals defined on more general domains without the action of a translation group. In particular, we propose two constructions, one based upon a hierarchical clustering of the domain, and another based on the spectrum of the graph Laplacian. We show through experiments that for low-dimensional graphs it is possible to learn convolutional layers with a number of parameters independent of the input size, resulting in efficient deep architectures.
1 Introduction
CNNs efficiently exploit translation, metric, and multiscale structures on regular grids, but many structured domains lack these properties. The paper generalizes neural networks to graphs through locally connected and pooling layers with O(n) parameters and a second construction using O(1) parameters.
- 1 Introduction: CNNs are highly successful on grid-structured data with translational equivariance or invariance, including speech, images, and video.Their efficiency comes from exploiting structures that align on regular grids.
- 1 Introduction: Translation enables weight sharing, metric structure enables compactly supported filters, and multiscale dyadic clustering enables subsampling through strides and pooling.Together, these structures reduce the number of parameters relative to generic linear layers.
- 1 Introduction: Fully connected layers require O(n2) parameters, while arbitrary filters or locally connected networks require O(n) parameters per feature map.Combining translation and metric structure yields O(k · S) parameters, where k is the number of feature maps.
- 1 Introduction: Graphs provide a framework for extending low-dimensional grid concepts to domains such as meshes, meteorological networks, and social networks where standard CNNs do not apply.The paper proposes graph-based deep neural-network constructions for such structured inputs.
- 1 Introduction: The paper introduces an O(n)-parameter construction based on weak geometric structure and a second O(1)-parameter construction connected to harmonic analysis on graphs.The constructions are empirically validated on low-dimensional graph datasets.
2 Spatial Construction
The spatial construction generalizes CNNs to graphs by combining multiscale clustering with localized receptive fields. Each layer trades spatial resolution for feature coordinates while using sparse filters, yielding O(n) learnable parameters under typical conditions.
- Graph locality: A weighted graph G = (Ω, W) replaces the grid, with graph weights defining local neighborhoods through thresholding.The graph has m vertices and W is an m×m symmetric, nonnegative matrix.
- Graph locality: Sparse filters restricted to graph neighborhoods form locally connected networks with O(S · n) parameters per filter layer.S denotes the average neighborhood size.
- Multiscale layers: At each of K scales, the network partitions Ωk−1 into clusters and transforms an fk−1-dimensional signal on Ωk−1 into an fk-dimensional signal on Ωk.This transformation trades spatial resolution for newly created feature coordinates and applies pooling over each cluster.
- Parameter efficiency: O(Sk · |Ωk| · fk · fk−1) = O(n) parameters are learned at layer k, with Sk ·|Ωk| ≈α·|Ωk−1| and α typically in (1, 4).The linear parameter count follows from the sparse neighborhood supports used by the construction.
- Limitations: The construction requires relatively weak graph regularity assumptions and supports localized neighborhoods on low-intrinsic-dimension graphs, but does not easily induce weight sharing across locations.A global low-dimensional embedding is offered as one possible option, though it is described as rare in practice.
3 Spectral Construction
The spectral construction generalizes convolution by operating on graph-Laplacian eigenvectors, whose diagonal spectral filters modulate signal smoothness. Truncating to low frequencies reduces parameters, while spectral high-frequency limitations and computational costs motivate smooth spectral multipliers for localized filters.
- Spectral construction: Graph-Laplacian eigenvectors provide a Fourier-like basis in which diagonal operators modulate signal smoothness.The eigenvalues encode smoothness through the signal’s coefficients in the Laplacian eigenbasis.
- Spectral construction: Keeping the first d eigenvectors retains the graph’s smooth geometry, but each layer still requires fk−1 ·fk ·d = O(|Ω|) trainable parameters.The cutoff d depends on the graph’s intrinsic regularity and sample size.
- Limitations: The construction may miss meaningful information carried collectively by high-frequency eigenvectors because it becomes nearly diagonal at the highest frequencies.Individual high-frequency eigenvectors may be uninformative even when their cohort contains useful information.
- Limitations: Efficient forward- and backpropagation is not immediate because spatial nonlinearities require expensive multiplications by V and V^T, while spectral-side standard nonlinearities are unclear.The passage identifies both space-side and spectral-side implementation difficulties.
- Natural-image specialization: Using the covariance as similarity kernel recovers classic convolutions on natural images without prior knowledge, because the resulting operators are diagonal in the Fourier basis.The covariance’s principal components are experimentally organized by frequency, yielding translation-invariant Fourier-diagonal operators.
- Localized spectral filters: Smooth spectral multipliers, parameterized by cubic-spline interpolation, can produce spatially localized filters with qk ∼|Ω| · α−1 = O(1) coefficients per filter.Choosing a spectral sampling step α ∼|Ω| makes the coefficient count independent of input size while targeting constant spatial support.
4 Relationship with previous work
The work relates graph-based CNN constructions to wavelets, locally connected networks, and methods for discovering grid topologies from data. It also connects its proposed multiscale clustering to multigrid methods and suggests clustering that works with the graph Laplacian could improve and unify the constructions.
- Wavelets on graphs: Graph wavelet methods construct bases with smoothness and sparsity properties, whereas this work constrains filters to retain wavelet-like regularity while also training them.The comparison concerns graph smoothness replacing grid smoothness and contrasts explicit wavelet construction with learned filters.
- Topology discovery: Prior work discovers grid topology from data by recovering 2-D structure through second-order statistics or estimating feature similarities for locally connected networks.These approaches provide related ways to infer domain structure or connectivity from data.
- Multiscale clustering: A multiscale clustering compatible with the graph Laplacian could improve and partially unify both constructions by avoiding repeated mapping of spectral constructions to the finest grid.On grids, dyadic cubes make Fourier-function subsampling equivalent to finding Fourier functions on the coarser grid.
- Multigrid connections: The proposed clustering is related to multigrid methods for discretized PDEs and linear systems, including extensions to settings more general than regular grids.For simplicity, the work uses a naive multiscale clustering.
5 Numerical Experiments
The experiments evaluate graph CNN constructions on subsampled MNIST and MNIST digits projected onto a sphere. Locally receptive and smooth spectral constructions improve spatial localization and classification relative to unconstrained spectral filters and nearest-neighbor baselines, while performance declines under stronger rotations.
- Experimental datasets: The study tests graph architectures on MNIST subsampled to 400 coordinates and on 4096 points sampled from the 3-D unit sphere.The subsampled coordinates retain a 2-D structure, while sphere experiments project MNIST images onto randomly sampled spherical points.
- Subsampled MNIST: Locally receptive fields better capture MNIST’s localized oriented strokes, while unconstrained spectral filters tend to be spatially delocalized.Adding spectral smoothness improves classification by encouraging spatially localized filters.
- Mild rotations: On the MNIST-sphere dataset with mild rotations, all neural architectures substantially outperform nearest-neighbor classification, while both convolutional constructions match fully connected models with fewer parameters.The convolutional constructions do not improve fully connected performance in this setting.
- Mild rotations: Smooth spectral constructions consistently improve performance and learn spatially localized filters that detect similar features across different graph locations.This behavior occurs even with the naive 1-D organization of eigenvectors.
- Uniform rotations: Under uniform rotations, all neural architectures outperform nearest-neighbor classification, but performance is notably worse than with mild rotations and requires fully roto-translation-invariant representations.The stronger rotations create substantially greater intra-class variability.
6 Conclusion
Graph-based convolutional architectures reduce parameter counts and speed forward propagation without worsening test error, while scaling to large coordinate sets with locality. The authors identify deeper training, manifold-like graphs, recommendation problems, and broader O(1)-parameter dual constructions as directions for future work.
- Contributions: Graph-based convolutional architectures reduce neural-network parameters without worsening, and often improving, test error while enabling faster forward propagation.The methods can also scale to data with many coordinates when those coordinates have a notion of locality.
- Future work: More careful training and deeper networks may consistently improve performance over fully connected networks on manifold-like graphs such as the sampled sphere.The authors present this as an area requiring further work.
- Future work: The techniques are intended for less artificial problems, including Netflix-like recommendation data with biclustering of data and coordinates.This extends the proposed graph-based methods beyond the settings studied in the paper.
- Future work: Smoothness in the naive eigenvector ordering improves results and localizes filters, suggesting dual constructions with O(1) parameters per filter beyond grids.The authors suggest that this possibility may hold in much greater generality than the grid.