Source-linked AI summary
Submanifold Sparse Convolutional Networks
Benjamin Graham, Laurens van der Maaten
TL;DR
Dense convolutional networks are inefficient for naturally sparse spatial and spatiotemporal data, while prior sparse implementations dilate active regions through the network. The paper introduces SC and VSC operators that preserve sparsity, and reports state-of-the-art performance with substantially lower computation and memory requirements.
Problem
Naturally sparse data are inefficiently processed by dense convolutions, while prior sparse implementations dilate active sites at every layer.
Method
The paper introduces sparse convolution (SC) and valid sparse convolution (VSC), with VSC preserving the input active-site set across layers.
Results
SC and VSC achieve state-of-the-art performance while reducing computation and memory requirements by ∼50%.
Takeaways & Limitations
VSC facilitates efficient, deep convolutional networks for sparse data while maintaining state-of-the-art accuracies on datasets of embedded curves and surfaces.
Takeaways & Limitations
The paper notes that its use of “submanifold” is a slight abuse because inputs may contain multiple connected components or mixtures of 1D and 2D objects.
Abstract
from arXiv · showhide
Convolutional network are the de-facto standard for analysing spatio-temporal data such as images, videos, 3D shapes, etc. Whilst some of this data is naturally dense (for instance, photos), many other data sources are inherently sparse. Examples include pen-strokes forming on a piece of paper, or (colored) 3D point clouds that were obtained using a LiDAR scanner or RGB-D camera. Standard "dense" implementations of convolutional networks are very inefficient when applied on such sparse data. We introduce a sparse convolutional operation tailored to processing sparse data that differs from prior work on sparse convolutional networks in that it operates strictly on submanifolds, rather than "dilating" the observation with every layer in the network. Our empirical analysis of the resulting submanifold sparse convolutional networks shows that they perform on par with state-of-the-art methods whilst requiring substantially less computation.
1 Introduction
Convolutional networks handle spatial and temporal data, but dense computation is inefficient for naturally sparse datasets. The paper develops sparse operators that preserve sparsity while maintaining state-of-the-art performance.
- Motivation: Naturally sparse data include handwriting, RGB-D point clouds, and surfaces embedded in higher-dimensional grids.Such datasets occupy only a small subset of their ambient spatial or spatiotemporal grid.
- Motivation: Prior sparse convolutional implementations dilate sparse data at every layer by using full convolutions.The paper instead targets networks that keep the same sparsity pattern throughout their layers.
- Results: The proposed SC and VSC networks achieve state-of-the-art performance while reducing computation and memory requirements by ∼50%.The experiments cover handwritten-digit recognition and 3D-shape recognition.
2 Motivation
Regular convolutions rapidly expand active sites in sparse data, destroying sparsity across deep networks. The paper motivates operators that preserve active-site structure while retaining enough neighboring information for recognition.
- Submanifold Dilation: A single active site expands to 3^d active sites after one 3^d convolution and 5^d after a second, making deep networks costly.The resulting growth is especially problematic for curves and surfaces embedded in higher-dimensional spaces.
- Proposed Operators: The proposed operators ignore ground-state inputs, and the most efficient one considers only the central input so output active sites mirror input active sites.This design addresses dilation while retaining convolutional processing on active sites.
- Submanifold Dilation: Restricting outputs to active input points preserves sparsity but can prevent neighboring connected components from interacting before pooling or strided convolution.The networks use pooling or strided convolutions to allow neighboring components to merge in hidden representations.
- Submanifold Dilation: Regular 3 × 3 convolutions rapidly reduce feature-map sparsity even for a one-dimensional curve embedded in a two-dimensional grid.Figure 1 compares the original curve with the results after one and two regular convolutions.
- Deep Architectures: Existing sparse implementations are poorly suited to very deep architectures because multiple paths and large receptive fields can rapidly destroy sparsity.These concerns affect architectures such as VGG networks, ResNets, and DenseNets.
3 (Valid) Sparse Convolutions: SC and VSC
The paper introduces SC and VSC operators for sparse convolutional networks, with VSC preserving the input sparsity pattern while supporting deep VGG, ResNet, and DenseNet architectures.
- Sparse convolution: SC determines active output sites from any active input within each receptive field while treating non-active inputs as zero.For SC(m, n, f, s), the output size is (ℓ−f+s)/s.
- Valid sparse convolution: VSC is an SC(m, n, f, 1) variant whose output site is active if and only if the corresponding input site is active.The input is padded by (f−1)/2 on each side, preserving spatial size.
- Valid sparse convolution: VSC computes output features with the SC operation only at sites retained from the input sparsity pattern.This prevents the layer from automatically dilating the active-site set.
- Submanifold convolutional networks: Sparse networks combine VSC convolutions, strided SC convolutions, and sparse pooling to build VGG, ResNet, and DenseNet variants.The architectures use VSC layers within resolution-preserving blocks and SC or pooling operations when reducing resolution.
- Submanifold convolutional networks: The design targets sparse data whose active structures may be low-dimensional and embedded in higher-dimensional spaces.The paper notes that inputs can contain multiple connected components and mixtures of one- and two-dimensional objects in 3D.
4 Implementation
The implementation represents sparse layers with a hash table and feature matrix, then uses rule books to perform efficient sparse matrix operations and reuse unchanged sparsity patterns.
- Sparse representation: Each sparse input or hidden layer is stored as a hash table of active locations and a matrix containing one feature row per active site.The matrix has size a × m, while the hash table maps coordinate locations to matrix rows.
- Rule-book construction: For SC, the implementation builds the output hash table and rule book by iterating through the input hash table once.The rule book records input-output row pairs grouped by spatial offset.
- Sparse computation: The output matrix is initialized to zero and accumulated through matrix-matrix multiply-add operations using offset-specific parameter matrices.These operations can be implemented efficiently on GPUs.
- Pattern reuse: For VSC, the input hash table is reused for the output because the sparsity pattern does not change.The same rule book can be reused through VGG, ResNet, and DenseNet blocks until pooling or subsampling occurs.
- Complexity: O(a) is the cost of building all hash tables and rule books for VGG, ResNet, and DenseNet networks under multiplicative active-site reduction at pooling layers.Here, a is the number of active input points.
5 Experiments
Experiments on CASIA, using VGG, ResNet, DenseNet, and expanded-receptive-field variants, show that sparse operations substantially reduce computation and memory with minimal accuracy loss. On ModelNet-40, submanifold VGG networks approach dense-network performance at much lower computational cost.
- CASIA experiments: The CASIA evaluations measured classification error, FLOPs, and memory load across VGG, ResNet, DenseNet, and branch-augmented architectures.The tables report memory load as the number of hidden states, and lower values are better.
- CASIA experiments: ResNet results reduced computational and memory requirements by at least a factor of 2 at a minimal loss in accuracy.Stride-2 modules used SC convolutions to align active sites across residual branches and avoid information loss during transitions.
- ModelNet-40 experiments: On ModelNet-40, VGG-A made 2% more errors at 13× fewer computations, while VGG-B performed roughly on par with dense 3DNiN at ∼5× fewer computations.These results compare two submanifold VGG networks with the dense 3DNiN network.
6 Related Work
The paper contrasts submanifold networks with prior sparse approaches that expand active sites layer by layer. It reports lower computational and memory costs than OctNets in a representative ModelNet-40 example, while noting possible implementation combinations.
- Prior sparse networks: Prior sparse networks typically use standard convolutions that increase the number of active sites with each layer, whereas submanifold networks retain greater sparsity.The paper reports that this retention makes deep and efficient VGG and ResNet models practical.
- Comparison conventions: In the CASIA overview, V denotes submanifold networks, D denotes submanifold networks with SC-VSC-DC connections, S regular sparse networks, and C regular dense networks.Locations closer to the bottom-left corner represent better results.
- OctNet comparison: For one ModelNet-40 sample, VSC required 0.6% of dense-convolution work, compared with about 35% for an OctNet convolution.The sample contained 423 active sites, or 1.3% of 32^3 grid sites.
- OctNet comparison: In that example, an OctNet convolution had a computational cost 60 times higher than a VSC convolution.OctNet’s cost reflects convolutions over surfaces of sub-cubes at multiple spatial resolutions.
- Memory comparison: Submanifold networks store one feature vector per active site, whereas OctTrees store roughly three times as many features because of empty child nodes.The reported OctTree structure contains about twice as many empty child nodes as active nodes.
- Possible combinations: Oct-tree structures could potentially serve as faster hash functions for VSC than universal hash functions over integer tuple keys.The paper presents this as a possible combination rather than an evaluated result.
7 Conclusion
The paper concludes that valid sparse convolution enables efficient, deep networks for sparse data while preserving state-of-the-art accuracy. It also releases implementations and reproduction code for the sparse operations and experiments.
- Conclusion: VSC facilitates efficient, deep convolutional networks for sparse data.The conclusion presents VSC as the paper’s new sparse convolutional operator.
- Conclusion: VSC produced substantial computational savings while maintaining state-of-the-art accuracies on two datasets involving embedded one-dimensional manifolds and two-dimensional surfaces.The datasets cover sparse structures embedded in two- and three-dimensional spaces, respectively.
- Reproducibility: The authors released easy-to-use implementations of VSC and the other sparse operations used in the networks, along with code to reproduce the experiments.The release covers the operations described in the paper’s networks and the experimental results.