Source-linked AI summary
Deep Convolutional Networks on Graph-Structured Data
Mikael Henaff, Joan Bruna, Yann LeCun
TL;DR
The paper addresses how to build deep architectures with small learning complexity for non-Euclidean data whose graph structure may be unknown. It extends spectral networks with graph estimation and evaluates the approach on large-scale classification, where it matches or outperforms dropout-trained fully connected networks with fewer parameters. The discussion also identifies graph estimation and Graph Fourier Transform computation as important costs and limitations.
Problem
Many text and bioinformatic datasets lack the stationarity, locality, and compositionality exploited by ConvNets, while their graph structure may be unknown.
Method
The paper extends spectral networks with unsupervised and supervised graph-estimation strategies combined with supervised graph convolutions.
Results
The method matches or outperforms large dropout-trained fully connected networks on text categorization and bioinformatics using fewer parameters.
Takeaways & Limitations
When feature similarities can be estimated from unlabeled data, the model has fewer parameters to learn from labeled data, while retaining lower learning-complexity growth than fully connected architectures.
Takeaways & Limitations
Graph estimation is a statistical bottleneck, and Graph Fourier Transform evaluation requires O(N 2) operations for general graphs.
Abstract
from arXiv · showhide
Deep Learning's recent successes have mostly relied on Convolutional Networks, which exploit fundamental statistical properties of images, sounds and video data: the local stationarity and multi-scale compositional structure, that allows expressing long range interactions in terms of shorter, localized interactions. However, there exist other important examples, such as text documents or bioinformatic data, that may lack some or all of these strong statistical regularities. In this paper we consider the general question of how to construct deep architectures with small learning complexity on general non-Euclidean domains, which are typically unknown and need to be estimated from the data. In particular, we develop an extension of Spectral Networks which incorporates a Graph Estimation procedure, that we test on large-scale classification problems, matching or improving over Dropout Networks with far less parameters to estimate.
1 Introduction
Convolutional Networks exploit stationarity, locality, and compositionality on grid-structured data, but many text and bioinformatic datasets lack these regularities. The paper extends spectral graph convolutions and estimates unknown graph structure for such domains.
- 1 Introduction: Grid-structured signals support stationarity, locality, and compositionality, enabling ConvNets to extract shared local features.These properties are associated with natural images, video, and speech.
- 1 Introduction: Text documents and other high-dimensional data may lack the low-dimensional grid structure and statistical assumptions used by standard ConvNets.Text documents represented as bags of words can be viewed as signals on graphs whose nodes are vocabulary terms.
- 1 Introduction: For data of dimension N without these assumptions, fully connected strategies require O(N 2) parameters.Weight decay and dropout are used for regularization in this setting.
- 1 Introduction: The paper generalizes spectral networks to large-scale classification and to settings where the graph structure is unavailable beforehand.It proposes unsupervised and supervised graph estimation combined with supervised graph convolutions.
- 1 Introduction: In text categorization and bioinformatics, the method matches or outperforms large dropout-trained fully connected networks with fewer parameters.The introduction also identifies Imagenet Object Recognition as an application area.
2 Related Work
Prior work explored local receptive fields, graph-based convolution, and graph estimation, but existing approaches did not jointly provide the paper’s target of general graph convolution with learned structure and weight sharing.
- 2 Related Work: Earlier local-receptive-field architectures were mostly applied to image recognition and did not generally exploit weight sharing.One cited approach learned feature groupings from unsupervised similarity measures.
- 2 Related Work: Spectral networks generalized convolutions to graphs through the Graph Laplacian and used O(1) parameters per feature map.The prior construction required the graph structure in advance and was demonstrated only on simple, low-dimensional graphs.
- 2 Related Work: Other research studied statistical graph estimation and unsupervised deep architectures based on learned Haar contractions.These lines of work address graph learning or representation construction separately from the paper’s combined approach.
3 Generalizing Convolutions to Graphs
The paper defines graph convolution spectrally using the Graph Fourier Transform and constrains spectral filters to preserve low learning complexity. Graph neighborhoods and pooling are constructed through multi-resolution spectral clustering.
- 3.1 Spectral Networks: A graph signal uses the normalized Graph Laplacian, whose eigenvectors form the Graph Fourier Transform matrix U.The Laplacian is defined from the similarity matrix W and degree matrix D.
- 3.1 Spectral Networks: Graph convolution transforms the input and filter into the graph Fourier domain, multiplies them pointwise, and applies U^T to return to the signal domain.The operation is x ∗G g = U^T(Ux ⊙ Ug).
- 3.1 Spectral Networks: Learning graph filters amounts to learning spectral multipliers, which can also be written as x ∗G g := U^T(diag(wg)Ux).For multiple input channels, the transformation U is applied to each channel and multipliers are indexed by locations and input channels.
- 3.1 Spectral Networks: Localized filters require restricting spectral multipliers because spatially small kernels provide learning complexity independent of the number of input pixels N.The paper connects spatial localization with smoothness in the frequency domain.
- 3.1 Spectral Networks: The graph convolution layer computes interpolated weights and forward and backward transformations using the Graph Fourier Transform.Algorithm 1 specifies weight interpolation in the forward pass and gradients with respect to inputs and weights in the backward pass.
- 3.2 Pooling: Graph pooling uses neighborhoods at multiple scales constructed by multi-resolution spectral clustering, with average and max-pooling considered.This transfers the resolution-versus-feature trade-off of standard convolutional architectures to graphs.
4 Graph Construction
The paper estimates feature graphs before spectral convolution, using either unlabeled joint statistics or supervised first-layer network features. These graph constructions support adaptive similarity modeling while retaining lower learning complexity than fully connected alternatives in suitable settings.
- Graph construction: The method estimates a feature similarity matrix before constructing the spectral network, using unsupervised or supervised graph construction.The unsupervised strategy measures joint feature statistics; the supervised strategy uses an initial network as a proxy.
- Unsupervised graph estimation: Unsupervised estimation builds feature distances from column-wise data measurements and can use Gaussian or self-tuning diffusion kernels.The self-tuning variant adapts the kernel variance locally around each feature rather than sharing one variance.
- Unsupervised graph estimation: The unsupervised Gaussian-kernel approach requires no labeled data, allowing similarity estimation from multiple datasets sharing the same features.This property is explicitly identified as its main advantage in text classification settings.
- Supervised graph estimation: Supervised estimation first trains a fully connected network, then uses its first-layer features to define task-specific feature distances for the Gaussian kernel.The resulting similarity reflects how the initial network uses features within its learned linear measurements.
- Complexity: The supervised construction distills information from a first network into a kernel, extracting N^2/2 parameters generally or mN parameters after projection onto m leading graph directions.Feature normalization is used in the experiments, while complete whitening is presented as an alternative.
- Complexity: Replacing the graph-Laplacian eigenbasis with an optimized arbitrary unitary matrix has the same learning complexity as a fully connected network, requiring O(KN^2) parameters.The paper reports no results for this strategy.
5 Experiments
Experiments evaluate spectral networks with estimated graphs on Reuters and Merck, and compare spectral and classical convolutional networks on ImageNet. Results show supervised graph estimation can preserve performance with fewer parameters, while ImageNet performance is nearly identical between models.
- Experimental setup: Experiments cover text categorization, computational biology, and computer vision using graph-based and classical convolutional architectures.The experiments use Torch with a custom CUDA backend.
- Experimental setup: The spectral network architecture interleaves graph convolution, ReLU, and graph pooling layers before fully connected layers.The notation defines GCk, Pk, and FCk for graph convolutions, pooling, and fully connected layers, respectively.
- Reuters: Reuters experiments use 201,369 training and test documents across 50 classes, represented by 2,000-word log-normalized bags of words, with a dropout fully connected baseline.Hyperparameters were selected on one-tenth of the training data, and models used the same selected settings.
- Reuters: Factorizing the first hidden layer across feature maps and a subsampled graph has a beneficial regularizing effect, but excessive graph-feature tradeoff degrades performance.The degradation is especially pronounced for unsupervised graph estimation, while supervised estimation is more robust.
- Merck Molecular Activity Challenge: On Merck DPP4, supervised graph estimation performs similarly to the fully connected network with far fewer parameters, whereas unsupervised strategies cause a significant performance drop.The DPP4 dataset contains 8,193 samples and 2,796 features; evaluation uses squared correlation between predictions and targets.
- ImageNet: On ImageNet, spectral and classical convolutional networks achieve nearly identical performance, although the spectral network learns faster early in training and both converge around the same time.The comparison uses 4 convolution/ReLU/max-pooling layers and 3 fully connected layers, trained for 40 epochs on 128 × 128 images.
6 Discussion
The paper generalizes convolutional architectures to high-dimensional, unstructured data by combining spectral networks with graph estimation. The approach can reduce labeled-data parameter requirements, but graph estimation and evaluation remain significant challenges.
- ConvNet-inspired architectures are motivated for high-dimensional, unstructured data because traditional ConvNets exploit informative local statistics with low learning complexity.
- When stationarity and compositionality hold, spectral networks have learning complexity of the same order as ConvNets.
- In general graphs, estimating feature similarities costs O(N 2), while deeper spectral models do not increase learning complexity as much as fully connected architectures.
- Feature similarities estimated from unlabeled data can reduce the number of parameters learned from labeled data.
- Evaluation requires Graph Fourier Transform multiplication costing O(N 2), unlike traditional ConvNets, which require O(N).
- When the graph is unknown, graph estimation is the statistical bottleneck, and the architecture is sensitive to graph estimation errors.