Sparse Convolutional Networks

A sparse convolutional network is a convolutional neural network that runs on the occupied cells of a voxel grid only. Its activations are stored as a sparse tensor, a list of integer coordinates with one feature row per coordinate, and each convolution is computed from precomputed pairs of input and output rows, so that empty space costs neither memory nor arithmetic. Scans of the world are mostly empty: a LiDAR sweep or a fused RGB-D room occupies only the voxels near its surfaces (in Graham et al.’s ShapeNet set-up at its largest scale about 99% of the voxels are empty), and a dense 3D network spends most of its work on zeros. Graham, Engelcke and van der Maaten (2018) introduced the submanifold sparse convolution, first described in an unpublished report by Graham and van der Maaten, which keeps the set of occupied sites fixed from layer to layer and, by their account, makes deep sparse networks practical to train; Choy, Gwak and Savarese (2019) generalized the operation to arbitrary input and output coordinates and kernel shapes in MinkowskiNet and the Minkowski Engine. Sparse convolutions are the backbone of many LiDAR detectors, SECOND among them, and of voxel networks for indoor and outdoor semantic segmentation, and they are implemented in the libraries SparseConvNet, spconv, MinkowskiEngine and TorchSparse.

The term means spatially sparse data. Both the SparseConvNet paper and the Minkowski Engine documentation separate it from networks with sparse (pruned) weights, which also go by the name “sparse convolutional networks” but operate on dense activations (Graham et al., 2018, footnote 4; MinkowskiEngine README).

Core Idea

A dense 3D convolution treats an $n^3$ grid as an array and visits all of its sites. Graham et al. (2018, §3) call a site active when its feature vector differs from the ground state, usually zero; inactive sites all hold the same ground-state vector, so it is computed once rather than stored for every site. A sparse convolutional network stores only the active sites and computes outputs only where they are needed.

Which output sites are “needed” is the design choice that separates the two main operations:

• A regular sparse convolution marks an output site active if any input site in its receptive field is active, exactly the sites where a dense convolution of the same input could be nonzero. The result equals the dense convolution, but the active set grows with every layer: a single active site becomes $3^d$ active sites after one size-3 convolution in $d$ dimensions and $5^d$ after two (Graham et al., 2018, §3). A curve in 2D or a surface in 3D thickens in the same way, which Graham et al. call the submanifold dilation problem.
• A submanifold sparse convolution (SSC) makes an output site active if and only if the same site is active in the input. The pattern of active sites never changes, however deep the stack, and each output still sums over its active neighbours.

The cost of the second choice is that information travels only along the occupied sites. Two parts of a scan that do not touch never exchange information through submanifold convolutions alone; strided convolutions or pooling, which merge neighbouring sites into one coarser site, let them communicate, and the closer the parts, the fewer strided operations they need (§4). Sparse networks are therefore built as encoder–decoders, like the U-Net, with submanifold convolutions at each resolution and strided sparse convolutions between them.

Building Blocks

Sparse tensors

An input or hidden layer is a coordinate matrix $C \in \mathbb{Z}^{N \times D}$ and a feature matrix $F \in \mathbb{R}^{N \times m}$, one row per active site (Choy et al., 2019, Eq. 1). Choy et al. present this as the coordinate-list (COO) format of sparse matrices extended to $D$ dimensions and add a batch index as an extra coordinate, so that sites of different scans in a mini-batch stay apart; their paper puts it in the last column, while spconv’s SparseConvTensor expects it in the first (spconv docs/USAGE.md). Features at a site can be anything: occupancy, the mean of the points that fell in the voxel, colour, intensity or a normal. Graham et al. used RGB plus a constant indicator channel for NYU Depth v2, so that a black voxel still differs from the ground state (§6.6).

Converting a point cloud to a sparse tensor is quantization: divide coordinates by the voxel size, take the floor and keep the unique cells. The Minkowski Engine’s GPU version sorts the points by a hash of the cell, removes duplicates, and, for segmentation, gives the label IGNORE_LABEL to a voxel that contains points of more than one class so that it is skipped by the loss (Choy et al., 2019, Alg. 1 and supplementary §1.1). A prediction per point is read back from its voxel; Choy et al. propagate voxel predictions to points from the nearest voxel centre (§7.2).

The hash table and the rulebook

Every convolution needs, for each kernel offset, the list of input rows that feed each output row. Graham et al. (2018, §4.2) store each layer as a hash table of (coordinate, row) pairs and a feature matrix, and build a rule book: for a filter of size $f$, one two-column integer matrix $R_i$ per offset $i \in \{0, \dots, f-1\}^d$, whose rows are (input row, output row) pairs. The convolution is then, for every offset, a gather of the input rows, a multiplication by that offset’s $m \times n$ weight matrix, and a scatter-add into the output rows: dense matrix products that run well on GPUs. The same object is a kernel map in the Minkowski Engine, a list of in-map and out-map indices per kernel cell (Choy et al., 2019, §4.2; MinkowskiEngine terminology.rst), indice pairs in spconv’s algorithm notes, and maps in TorchSparse (Tang et al., 2022, §2.1).

The hash tables are keyed by the integer coordinates of single sites, where the voxel hashing that the Voxel Grid article describes keys blocks of voxels; the libraries choose their own hash functions. SparseConvNet’s paper points to the sparsehash library, the Minkowski Engine uses a variant of the FNV-1a 64-bit hash adapted to 32-bit integer coordinates (supplementary §1.2), and the TorchSparse paper notes that the key can simply flatten the coordinates into one integer (§2.1.2).

Because a submanifold convolution’s output sites are its input sites, its rule book is the same for every submanifold layer at one resolution and is reused until a pooling or strided layer changes the sites (Graham et al., 2018, §4.2). spconv exposes this through an indice_key shared by layers, and the Minkowski Engine’s coordinate manager caches coordinates and kernel maps and reuses them when it sees the same operation again (terminology.rst). For odd kernels at stride 1 the maps are symmetric, since if $u + \delta$ feeds $u$ then $u$ feeds $u + \delta$ through $-\delta$ (Tang et al., 2022, §2.1.2).

Convolution, pooling and upsampling

Graham et al. (2018, §4.1) define three operations on sparse inputs:

• $\mathrm{SC}(m, n, f, s)$, a sparse convolution with $m$ input and $n$ output feature planes, filter size $f$ and stride $s$, whose active outputs are those with any active input in their $f^d$ receptive field. Unlike the earlier sparse convolutions of Graham (2015), which kept the ground state of inactive sites, it treats their input as zero, which the authors say cuts the cost by about 50%. With $f = 2$, $s = 2$ it is the downsampling layer of their networks.
• $\mathrm{SSC}(m, n, f)$, the submanifold sparse convolution: an $\mathrm{SC}(m, n, f, 1)$ with $(f-1)/2$ zeros of padding on each side and outputs restricted to the active input sites, for odd $f$.
• $\mathrm{DC}(\cdot, \cdot, f, s)$, a deconvolution that inverts a given $\mathrm{SC}$: its output sites are exactly the input sites of that strided convolution, and its connections are the strided convolution’s connections reversed.

Max and average pooling are variants of $\mathrm{SC}$; batch normalization and activation functions act on the feature rows of active sites only (§4.1). spconv names the same layers SparseConv3d (downsampling), SubMConv3d and SparseInverseConv3d (upsampling back to saved sites), and separates the last from SparseConvTranspose3d, a true transposed convolution that creates new sites and which its documentation recommends only for generative models (spconv docs/USAGE.md). The transposed convolution article covers the dense operation.

How Data Flows

A typical network voxelizes the input, applies a few submanifold convolutions at full resolution, and then alternates strided sparse convolutions with blocks of submanifold convolutions or residual blocks, doubling the channels at each downsampling. For segmentation, a decoder returns to the input sites through inverse convolutions with skip connections, and a linear layer and softmax label each active voxel (Graham et al., 2018, §5 and Fig. 4). Graham et al. built sparse FCNs and U-Nets this way from pre-activated $\mathrm{SSC}(\cdot,\cdot,3)$ convolutions (batch normalization and ReLU before each convolution), $\mathrm{SC}(\cdot,\cdot,2,2)$ downsampling and, optionally, residual blocks of two SSCs. Choy et al. (2019, §5.2) transcribed ResNet-18 into a sparse “MinkowskiNet18” with a $5 \times 5 \times 5 \times 1$ first layer, and built U-shaped variants such as MinkowskiUNet32 with strided convolutions, strided transposed convolutions and skip connections between layers of equal tensor stride.

Detectors usually stop the sparse part early. In SECOND’s official code, the SpMiddleFHD middle extractor applies blocks of two or three SubMConv3d layers separated by three SparseConv3d layers of stride 2, and a final convolution with kernel $(3, 1, 1)$ and stride $(2, 1, 1)$ along the height axis, then converts the result to a dense tensor and folds the remaining height into channels, giving a 2D bird’s-eye-view feature map for a 2D region proposal network (second/pytorch/models/middle.py). The car configuration voxelizes $[0, 70.4] \times [-40, 40] \times [-3, 1]$ m at $0.05 \times 0.05 \times 0.1$ m with at most five points per voxel (car.fhd.config).

Mathematical Formulation

Choy et al. (2019, §3.1) write a convolution with kernel weights $W_{\mathbf{i}} \in \mathbb{R}^{N_{\text{out}} \times N_{\text{in}}}$ for each offset $\mathbf{i}$. The dense convolution on $\mathbb{Z}^D$ is

$$\mathbf{x}^{\text{out}}_{\mathbf{u}} = \sum_{\mathbf{i} \in \mathcal{V}^D(K)} W_{\mathbf{i}}\, \mathbf{x}^{\text{in}}_{\mathbf{u} + \mathbf{i}}, \qquad \mathbf{u} \in \mathbb{Z}^D,$$

where $\mathcal{V}^D(K)$ is the set of offsets of a hypercube of side $K$ centred at the origin, for example $\mathcal{V}^1(3) = \{-1, 0, 1\}$. The generalized sparse convolution relaxes all three sets:

$$\mathbf{x}^{\text{out}}_{\mathbf{u}} = \sum_{\mathbf{i} \in \mathcal{N}^D(\mathbf{u}, \mathcal{C}^{\text{in}})} W_{\mathbf{i}}\, \mathbf{x}^{\text{in}}_{\mathbf{u} + \mathbf{i}}, \qquad \mathbf{u} \in \mathcal{C}^{\text{out}},$$

with $\mathcal{N}^D$ an arbitrary set of kernel offsets, $\mathcal{N}^D(\mathbf{u}, \mathcal{C}^{\text{in}}) = \{\mathbf{i} \in \mathcal{N}^D : \mathbf{u} + \mathbf{i} \in \mathcal{C}^{\text{in}}\}$ the offsets that land on input coordinates, and $\mathcal{C}^{\text{in}}$, $\mathcal{C}^{\text{out}}$ given input and output coordinate sets. Like deep-learning convolutions generally, this is a cross-correlation. Special cases (Choy et al., 2019; MinkowskiEngine sparse_tensor_network.rst):

• $\mathcal{C}^{\text{in}} = \mathcal{C}^{\text{out}} = \mathbb{Z}^D$, $\mathcal{N}^D = \mathcal{V}^D(K)$: the dense convolution.
• $\mathcal{C}^{\text{out}} = \mathcal{C}^{\text{in}}$, $\mathcal{N}^D = \mathcal{V}^D(K)$: the submanifold sparse convolution.
• $\mathcal{C}^{\text{out}} = \{\mathbf{u} : \mathcal{N}^D(\mathbf{u}, \mathcal{C}^{\text{in}}) \neq \emptyset\}$, the dilation of the input set by the kernel: the regular sparse convolution at stride 1 (our statement of Graham et al.’s rule in this notation).
• Strided convolutions: $\mathcal{C}^{\text{out}} \neq \mathcal{C}^{\text{in}}$. The Minkowski Engine makes the output coordinates of a layer of stride $s_l$ on an input of tensor stride $s_i$ by rounding every input coordinate down to a multiple of $s = s_l s_i$, $\lfloor \mathbf{c} / s \rfloor s$, and keeping the unique results (supplementary Alg. 3). The tensor stride is the spacing between sites, the sparse counterpart of the stride of a feature map (terminology.rst).
• Non-cubic kernels, such as a cross or the hybrid kernels below, and dilated kernels, by the choice of $\mathcal{N}^D$.

In rulebook form, with $M_{\mathbf{i}} = \{(j, k)\}$ the pairs of input row $j$ and output row $k$ for offset $\mathbf{i}$,

$$F^{\text{out}}_{k} = \sum_{\mathbf{i}} \; \sum_{(j, k) \in M_{\mathbf{i}}} W_{\mathbf{i}}\, F^{\text{in}}_{j},$$

and a layer costs $\sum_{\mathbf{i}} |M_{\mathbf{i}}|\, N_{\text{in}} N_{\text{out}}$ multiply-adds against $K^D\, |\text{grid}|\, N_{\text{in}} N_{\text{out}}$ for the dense layer. Graham et al.’s Table 2 gives the per-site version for $f = 3$: a dense convolution costs $3^d m n$ at every site; $\mathrm{SC}$ costs $a m n$ at a site with $a$ active inputs, whether or not the site itself was active, and nothing where $a = 0$; $\mathrm{SSC}$ costs $a m n$ at active sites and nothing elsewhere. Building the hash tables and rule books of a network whose active set shrinks by a constant factor at each downsampling costs $O(a)$ for $a$ active input sites, independent of depth (§4.2).

Example: Regular Against Submanifold Sparse Convolution

The script builds a voxelized surface, two concentric spheres of radii 0.40 and 0.30 in the cube $[-0.5, 0.5]^3$, from points placed deterministically on each sphere (a Fibonacci lattice, about eight points per voxel of surface area), at $n = 64$ and $n = 128$ voxels per side. Voxel indices are $\lfloor (\mathbf{p} + 0.5)\, n \rfloor$, the kernel offsets are $\{-1, 0, 1\}^3$, and every layer computes $\mathbf{x}^{\text{out}}_{\mathbf{u}} = \sum_{\boldsymbol{\delta}} W_{\boldsymbol{\delta}} \mathbf{x}^{\text{in}}_{\mathbf{u} + \boldsymbol{\delta}}$ by gather, multiply and scatter-add over a rulebook. Site lookup uses a sorted array of integer keys searched by binary search, standing in for the libraries’ hash tables. The script:

1. checks one regular and one submanifold layer with random weights (four channels in and out) against the same correlation on the dense grid by scipy.ndimage.correlate, and two submanifold layers against two dense layers;
2. checks Graham et al.’s single-site growth;
3. stacks six layers of each kind and counts active sites, multiply-adds at 64 input and 64 output channels (our choice of width), float32 feature memory and rulebook memory (two 32-bit indices per pair), against a dense layer on the $n^3$ grid;
4. puts a signal of 1 on the outer sphere and 0 on the inner, applies layers with all-ones $3 \times 3 \times 3$ kernels, and counts the layers until the inner sphere receives any signal: with submanifold convolutions only, with regular sparse convolutions, and with submanifold convolutions after one to three stride-2 downsamplings (all-ones $2 \times 2 \times 2$ kernels, output sites $\lfloor \mathbf{c}/2 \rfloor$ as in Choy et al.’s Alg. 3).

It uses NumPy 2.3.5 and SciPy 1.16.3, gives the same output on every run, and takes about a minute on our machine, most of it in the regular layers at $n = 128$.

import itertools
import numpy as np
from scipy import ndimage

OFFSETS = np.array(list(itertools.product((-1, 0, 1), repeat=3)))   # the 27 offsets of a 3x3x3 kernel


def fib_sphere(r, n_pts):
    """Deterministic, nearly uniform points on a sphere of radius r (Fibonacci lattice)."""
    i = np.arange(n_pts) + 0.5
    z = 1 - 2 * i / n_pts
    phi = np.pi * (1 + 5 ** 0.5) * i
    s = np.sqrt(1 - z ** 2)
    return r * np.stack([s * np.cos(phi), s * np.sin(phi), z], 1)


def voxelize(radii, n):
    """Active sites: voxels of side 1/n hit by points on spheres centred in [-0.5, 0.5]^3."""
    shells = []
    for r in radii:
        p = fib_sphere(r, int(np.ceil(8 * 4 * np.pi * r ** 2 * n ** 2)))   # ~8 points per voxel of area
        shells.append(np.unique(np.floor((p + 0.5) * n).astype(np.int64), axis=0))
    return shells


class SiteIndex:
    """Coordinate -> row lookup over the active sites: sorted integer keys and binary search,
    standing in for the hash tables of SparseConvNet, spconv and MinkowskiEngine."""
    def __init__(self, C):
        self.keys = self.key(C)
        self.order = np.argsort(self.keys)
        self.sorted = self.keys[self.order]

    @staticmethod
    def key(C):
        c = C + 64                                   # offset so that small negative coordinates stay valid
        return (c[:, 0] * 4096 + c[:, 1]) * 4096 + c[:, 2]

    def rows(self, Q):
        k = self.key(Q)
        pos = np.minimum(np.searchsorted(self.sorted, k), len(self.sorted) - 1)
        return np.where(self.sorted[pos] == k, self.order[pos], -1)   # -1: not an active site


def dilate(C):
    """Output sites of a regular sparse convolution (3^3, stride 1): any active input in the window."""
    return np.unique((C[:, None, :] + OFFSETS[None]).reshape(-1, 3), axis=0)


def rulebook(C_in, C_out, offsets=OFFSETS):
    """For each kernel offset d, the (input row, output row) pairs with u_out + d = u_in active."""
    index = SiteIndex(C_in)
    book = []
    for d in offsets:
        rows = index.rows(C_out + d)
        o = np.nonzero(rows >= 0)[0]
        book.append((rows[o], o))
    return book


def apply(F, book, n_out, W):
    """Gather, multiply by W_d, scatter-add: out[u] = sum_d W_d x[u + d] over active inputs only."""
    out = np.zeros((n_out, W.shape[-1]))
    for (i, o), Wd in zip(book, W):
        np.add.at(out, o, F[i] @ Wd)
    return out


def dense(G, W):
    """Reference: the same correlation on a dense (channels, n, n, n) grid, zero outside."""
    Wk = W.reshape(3, 3, 3, W.shape[1], W.shape[2])
    return np.stack([sum(ndimage.correlate(G[a], Wk[..., a, b], mode="constant") for a in range(G.shape[0]))
                     for b in range(W.shape[2])])


def to_grid(C, F, n, m=1):
    G = np.zeros((F.shape[1], n + 2 * m, n + 2 * m, n + 2 * m))   # margin m for dilated sites
    G[:, C[:, 0] + m, C[:, 1] + m, C[:, 2] + m] = F.T
    return G


def at(D, C, m=1):
    return D[:, C[:, 0] + m, C[:, 1] + m, C[:, 2] + m].T


rng = np.random.default_rng(0)
RADII = (0.40, 0.30)

# 1. One layer of each kind against the dense correlation; two submanifold layers against two dense layers.
n = 64
outer, inner = voxelize(RADII, n)
C = np.concatenate([outer, inner])
F = np.concatenate([np.ones((len(C), 1)), rng.standard_normal((len(C), 3))], 1)   # indicator + 3 channels
W1, W2 = rng.standard_normal((2, 27, 4, 4))
D1 = dense(to_grid(C, F, n), W1)
C_sc = dilate(C)
y_sc = apply(F, rulebook(C, C_sc), len(C_sc), W1)
book = rulebook(C, C)                                    # submanifold: output sites = input sites
y_ssc = apply(F, book, len(C), W1)
print(f"one layer, max |sparse - dense|: regular {np.abs(y_sc - at(D1, C_sc)).max():.1e}, "
      f"submanifold {np.abs(y_ssc - at(D1, C)).max():.1e}")
D2 = dense(D1, W2)
y2 = apply(y_ssc, book, len(C), W2)
diff = np.abs(y2 - at(D2, C)).max() / np.abs(at(D2, C)).max()
print(f"two layers, submanifold vs dense at the active sites: max difference {diff:.0%} of max |dense|")

# 2. A single active site under regular sparse convolution: 3^3, 5^3, 7^3 sites.
S = np.zeros((1, 3), np.int64)
print("single site, regular:", [len(S := dilate(S)) for _ in range(3)])

# 3. Dilation across layers and cost per layer at 64 -> 64 channels.
CH = 64
for n in (64, 128):
    C = np.unique(np.concatenate(voxelize(RADII, n)), axis=0)
    grid, N0 = n ** 3, len(C)
    pairs_ssc = sum(len(o) for _, o in rulebook(C, C))
    print(f"\nn = {n}: {N0} active sites = {N0 / grid:.2%} of the {n}^3 grid; "
          f"dense layer {27 * grid * CH * CH / 1e9:.1f} G multiply-adds, {grid * CH * 4 / 2**20:.0f} MiB of features")
    print(f"  submanifold, every layer: {N0} sites, {pairs_ssc} rule pairs ({pairs_ssc / N0:.1f} per site), "
          f"{pairs_ssc * CH * CH / (27 * grid * CH * CH):.2%} of dense multiply-adds, "
          f"{N0 * CH * 4 / 2**20:.1f} MiB features + {pairs_ssc * 8 / 2**20:.1f} MiB rulebook")
    for L in range(1, 7):
        C_out = dilate(C)
        pairs = sum(len(o) for _, o in rulebook(C, C_out))
        C = C_out
        print(f"  regular, after layer {L}: {len(C):7d} sites ({len(C) / N0:4.1f}x, {len(C) / grid:6.2%} of grid), "
              f"layer cost {pairs * CH * CH / (27 * grid * CH * CH):6.2%} of dense, {len(C) * CH * 4 / 2**20:5.1f} MiB features")

# 4. Can the outer shell's signal reach the inner shell? n = 64, gap 0.10 = 6.4 voxels.
n = 64
outer, inner = voxelize(RADII, n)
C = np.concatenate([outer, inner])
ones = np.ones((27, 1, 1))                               # all-ones 3x3x3 kernels, one channel
x0 = np.r_[np.ones(len(outer)), np.zeros(len(inner))][:, None]   # impulse: 1 on the outer shell only


def layers_to_reach(C, x, target, regular, max_layers=12):
    """Number of layers until some site of `target` (inner-shell coordinates) holds a nonzero value."""
    targets = SiteIndex(target)
    for L in range(1, max_layers + 1):
        C_out = dilate(C) if regular else C
        x = apply(x, rulebook(C, C_out), len(C_out), ones)
        C = C_out
        if (x[targets.rows(C) >= 0] > 0).any():
            return L
    return None


print(f"\nouter shell {len(outer)} sites, inner {len(inner)}; layers until the inner shell sees the outer:")
print("  submanifold only:", layers_to_reach(C, x0, inner, regular=False) or "not within 12 layers")
print("  regular:", layers_to_reach(C, x0, inner, regular=True))
for k in (1, 2, 3):
    s = 2 ** k
    Ck = np.unique(C // s, axis=0)                       # sites after k stride-2 convolutions (floor(c/2) each time)
    xk = np.zeros((len(Ck), 1))
    np.add.at(xk, SiteIndex(Ck).rows(C // s), x0)        # all-ones 2x2x2 kernels, stride 2, k times
    inner_k = np.unique(inner // s, axis=0)
    shared = (xk[SiteIndex(inner_k).rows(Ck) >= 0] > 0).any()
    L = 0 if shared else layers_to_reach(Ck, xk, inner_k, regular=False)
    print(f"  {k} stride-2 downsampling(s) ({len(Ck)} coarse sites), then submanifold layers: {L}")

Output:

one layer, max |sparse - dense|: regular 1.4e-14, submanifold 1.4e-14
two layers, submanifold vs dense at the active sites: max difference 67% of max |dense|
single site, regular: [27, 125, 343]

n = 64: 16965 active sites = 6.47% of the 64^3 grid; dense layer 29.0 G multiply-adds, 64 MiB of features
  submanifold, every layer: 16965 sites, 225559 rule pairs (13.3 per site), 3.19% of dense multiply-adds, 4.1 MiB features + 1.7 MiB rulebook
  regular, after layer 1:   55751 sites ( 3.3x, 21.27% of grid), layer cost  6.47% of dense,  13.6 MiB features
  regular, after layer 2:   88738 sites ( 5.2x, 33.85% of grid), layer cost 21.27% of dense,  21.7 MiB features
  regular, after layer 3:  109495 sites ( 6.5x, 41.77% of grid), layer cost 33.85% of dense,  26.7 MiB features
  regular, after layer 4:  130667 sites ( 7.7x, 49.85% of grid), layer cost 41.77% of dense,  31.9 MiB features
  regular, after layer 5:  152496 sites ( 9.0x, 58.17% of grid), layer cost 49.85% of dense,  37.2 MiB features
  regular, after layer 6:  175083 sites (10.3x, 66.79% of grid), layer cost 58.17% of dense,  42.7 MiB features

n = 128: 67928 active sites = 3.24% of the 128^3 grid; dense layer 231.9 G multiply-adds, 512 MiB of features
  submanifold, every layer: 67928 sites, 905188 rule pairs (13.3 per site), 1.60% of dense multiply-adds, 16.6 MiB features + 6.9 MiB rulebook
  regular, after layer 1:  222669 sites ( 3.3x, 10.62% of grid), layer cost  3.24% of dense,  54.4 MiB features
  regular, after layer 2:  377579 sites ( 5.6x, 18.00% of grid), layer cost 10.62% of dense,  92.2 MiB features
  regular, after layer 3:  532841 sites ( 7.8x, 25.41% of grid), layer cost 18.00% of dense, 130.1 MiB features
  regular, after layer 4:  667620 sites ( 9.8x, 31.83% of grid), layer cost 25.41% of dense, 163.0 MiB features
  regular, after layer 5:  756509 sites (11.1x, 36.07% of grid), layer cost 31.83% of dense, 184.7 MiB features
  regular, after layer 6:  839063 sites (12.4x, 40.01% of grid), layer cost 36.07% of dense, 204.8 MiB features

outer shell 10848 sites, inner 6117; layers until the inner shell sees the outer:
  submanifold only: not within 12 layers
  regular: 3
  1 stride-2 downsampling(s) (4582 coarse sites), then submanifold layers: 1
  2 stride-2 downsampling(s) (1121 coarse sites), then submanifold layers: 1
  3 stride-2 downsampling(s) (272 coarse sites), then submanifold layers: 0

Both kinds of layer compute the dense convolution exactly on the sites they keep (differences at rounding level), and by construction the dense result is zero off the regular layer’s sites, which have no active input in their window, so a regular sparse convolution loses nothing. A single submanifold layer also agrees with the dense layer at the active sites, but two do not: the dense network’s second layer also reads the values that the first layer produced next to the surface, which the submanifold network never creates. A submanifold network is therefore a different network from a dense one, not a faster way of computing it, as Graham et al.’s comparison of submanifold networks with dense 3D networks of the same design treats it (§6).

The dilation numbers show the problem that the submanifold convolution solves. A single site grows as $(2L + 1)^3$. A surface grows much more slowly, by roughly a constant number of sites per layer, since each layer adds a band of voxels on each side of each sphere (our reading of the counts); the increments fall once the bands of the two spheres begin to meet between them, from the third layer at $n = 64$ and from the fourth at $n = 128$. After six layers the regular network carries 10 to 12 times the input’s sites, and at $n = 64$ two thirds of the dense grid is active. Every input site of a regular layer contributes all 27 rule pairs, so a regular layer costs the same fraction of a dense layer as its input occupies of the grid, and its cost rises layer by layer. The submanifold layer keeps 13.3 pairs per site on this surface, about half of 27, and costs 3.2% of a dense layer at $n = 64$ and 1.6% at $n = 128$, a fraction that falls with resolution because a surface occupies a fraction of the grid that shrinks roughly as $1/n$ (reasoning from the surface’s dimension, as in the Voxel Grid article). Its rulebook is smaller than its 64-channel features and, being shared by all submanifold layers at one resolution, is built once.

The communication test shows the price. Submanifold convolutions alone never carry the outer sphere’s signal across the empty gap. Regular convolutions carry it in three layers, not the six or seven that the 6.4-voxel radial gap suggests, because a $3 \times 3 \times 3$ window is a cube: each layer advances one voxel in the maximum (Chebyshev) distance, and along the cube’s diagonals the radial gap is only about $6.4/\sqrt{3} \approx 3.7$ voxels in that distance, a little less between the voxelized shells, which are more than a voxel thick (reasoning from the construction). After one or two stride-2 downsamplings a single submanifold layer bridges the gap, and after three, coarse voxels of side 8 contain parts of both spheres. This is the role Graham et al. give to strided operations in submanifold networks.

Why It Works

Graham et al. (2018, §6.4) argue from their ShapeNet experiments that restricting information to the active sites does not hurt accuracy while it saves computation and memory, which can be spent on larger models. Their comparisons support the argument on the data they used. On the ShapeNet part segmentation benchmark with randomly rotated objects, submanifold networks beat shape-context features, dense 3D networks and multi-view 2D networks, with an average IoU 6–8% higher than the baselines’ at $10^8$ multiply-adds (Fig. 5a). Networks with downsampling and upsampling (FCNs and U-Nets) beat networks at a single resolution, which the authors conjecture is due to the larger receptive field (Fig. 5b).

The design also keeps the convolutional machinery of image networks. Choy et al. (2019, §1) chose sparse tensors partly because the generalized convolution is a direct extension of the 2D convolution, so residual connections, batch normalization and other architectural ideas carry over with little change, and their MinkowskiNets are transcriptions of ResNets (§5.2). At submission they described their networks as the first very deep 3D convolutional networks, with more than 20 layers (footnote 3).

Training Considerations

• Normalization and nonlinearities are applied to the feature matrix row by row; Choy et al. apply 1D batch normalization directly to $F$ (§4.5). Batch statistics are therefore averages over active sites, not over the volume.
• Voxel size sets resolution, sparsity and cost together. Graham et al. scale ShapeNet objects to a sphere of diameter $S \in \{16, 32, 48\}$ voxels inside a grid of $4S$ and report about 99% empty voxels at $S = 48$ (§6.2); Choy et al. use 5 cm voxels for ScanNet and S3DIS and report a ScanNet gain from 2 cm voxels (§7.3–§7.4 and Table 1). For outdoor LiDAR scenes, Tang et al. (2020, §3.2) point out that after the four downsamplings of a MinkowskiNet with 5 cm input voxels the voxel size is $0.05 \times 2^4 = 0.8$ m, too coarse for small objects.
• Whole scenes. Because the cost follows the occupied sites, networks can take a whole room at once; Choy et al. feed entire ScanNet rooms without cropping (§7.3).
• Augmentation and test-time ensembles follow 3D practice: Choy et al. use random scaling, rotation about the gravity axis, translation, elastic distortion and colour jitter (§7.2), and Graham et al. average predictions over several random rotations of each object at test time (§6.2).
• Optimization is ordinary: Graham et al. trained with SGD with Nesterov momentum 0.9, weight decay $10^{-4}$, learning rate 0.1 decayed by $e^{-0.04}$ per epoch, for 100 epochs at batch size 16 (§6.2); Choy et al. used momentum SGD with a polynomial schedule from 0.1 (§7.2).

Variants

Sparse convolutions before submanifold convolutions

Graham’s earlier spatially sparse networks (Graham, 2014; Graham, 2015) could not be read for this article. As Graham et al. (2018, §1–§2) describe the prior sparse convolutions of Graham (2015) and of Vote3Deep (by Engelcke and colleagues), they computed only at active sites but let the active set grow with each layer, using a sparse im2col restricted to active sites (Graham, 2015) or a voting algorithm that skips multiplications by zeros (Vote3Deep); the same paper places OctNet (Riegler et al., 2017) as another sparsity-preserving alternative, which stores voxels in octrees and whose size-3 convolution still spends about 23% of a dense convolution’s computation on an empty $8 \times 8 \times 8$ cube, where a submanifold convolution spends nothing. According to the 2018 paper, the submanifold operators first appeared in an unpublished report by Graham and van der Maaten (2017), with classification experiments. The SparseConvNet README lists the earlier work, including Chinese handwriting recognition with 2D sparse networks (2014), and describes the 2017 report as introducing deep “submanifold” SparseConvNets.

Generalized sparse convolution and 4D networks

MinkowskiNet’s aim was spatio-temporal: a sequence of 3D scans is a sparse 4D tensor, and Choy et al. (2019) process it with 4D convolutions. A $5$-wide kernel has 25 weights in 2D, 125 in 3D and 625 in 4D, an increase that, the authors write, does not necessarily improve performance and slows the network (§1), so they proposed a hybrid kernel, cubic in space and cross-shaped in time, connecting each point to the same location in neighbouring frames, in place of the full hypercube (“tesseract”) kernel (§5.1). On their 4D Synthia sequences, a 4D MinkNet20 reached 77.46 mIoU against 76.24 for the 3D network and 75.34 for the 4D tesseract-kernel network, and 78.30 with their trilateral-stationary conditional random field, which runs its mean-field updates as a 7D sparse convolution over space, time and colour (Table 2, §6). With added input noise, the 4D MinkNet42 reached 79.84 mIoU against 76.72 for the 3D one; there the tesseract-kernel network, at 78.87, also beat the 3D network (Table 3).

Point–voxel hybrids

Sparse Point-Voxel Convolution (SPVConv; Tang et al., 2020) pairs a sparse voxel branch with a branch that keeps one feature per point at full resolution: point features are averaged into voxels, processed by sparse convolution residual blocks and interpolated back to the points trilinearly from the eight neighbouring voxels, then added to the output of a per-point MLP (§3.3). The authors argue that it recovers small objects that coarse voxels merge, and combine it with neural architecture search (SPVNAS). The PointNet article covers the per-point networks of this family.

Implementations

Sparse convolution is mostly used through four libraries, each with its own algorithms and vocabulary (state as of November 2026):

• SparseConvNet (facebookresearch/SparseConvNet, BSD licence) is the PyTorch library of Graham et al. (2018), with SubmanifoldConvolution, strided convolutions, deconvolutions and ready-made sparse VGG, ResNet and U-Net builders. Its README states support for up to 10 dimensions in theory and warns that size-3 convolutions become impractical from five dimensions because the parameters grow exponentially. Its last commit, a README update, is from January 2024.
• spconv (traveller59/spconv, Apache 2.0), version 2.3.8 at the commit read, provides SparseConv3d, SubMConv3d, SparseInverseConv3d and SparseConvTranspose3d, a voxel generator and int8 quantization. Its algorithm notes describe three ways of computing a layer: the “native” gather–matrix multiply–scatter-add over indice pairs, and two “implicit GEMM” methods that fuse the work into one kernel, sorting the sites by their neighbour masks so that whole tiles of missing neighbours can be skipped. In the notes’ example of a submanifold layer with 780k valid entries out of 6,000k in the full implicit matrix, the masked method computes 1,500k and the split-mask method 970k (docs/spconv2_algo.pdf). In 2.3.8, layers whose kernel volume is at most 32 default to the masked implicit GEMM on GPU builds and to the native algorithm otherwise (spconv/pytorch/conv.py).
• MinkowskiEngine (NVIDIA/MinkowskiEngine, MIT licence), version 0.5.4 at the commit read, implements the generalized sparse convolution with arbitrary kernel shapes and output coordinates, pooling, broadcasting and a coordinate manager that caches coordinates and kernel maps; its README lists examples for segmentation, classification, reconstruction, completion and detection. Its last commit is from March 2023, and its README requires compiling it against the CUDA version of the installed PyTorch.
• TorchSparse (mit-han-lab/torchsparse, MIT licence), version 2.1.0 at the commit read, is an inference and training engine. Its MLSys paper identifies two bottlenecks: different kernel offsets have very different numbers of pairs, so per-offset matrix products underuse the GPU, and gathering and scattering features can take up to half of the runtime. It batches the matrix products of several offsets together (“adaptive MM grouping”), trading extra computation for regularity, and uses vectorized, quantized and locality-aware memory access, and reports end-to-end speedups of 1.6× over MinkowskiEngine and 1.5× over SpConv on seven models and three datasets (Tang et al., 2022, abstract and §1). The README reports larger speedups for TorchSparse++, the version 2.1 presented at MICRO 2023; that paper was not read.

The libraries’ layer names map onto one another: spconv’s docs/USAGE.md lists SubMConv3d as TorchSparse’s Conv3d at stride 1 and MinkowskiEngine’s MinkowskiConvolution at stride 1, and SparseInverseConv3d as TorchSparse’s transposed Conv3d and MinkowskiConvolutionTranspose.

Use in Computer Vision

LiDAR 3D detection. As the PointPillars paper describes it, VoxelNet applied a PointNet to the points of each voxel, then a 3D convolutional middle layer, then a 2D convolutional detection network. SECOND (Yan, Mao & Li, 2018), whose journal paper could not be read for this article, is described there as a faster sparse version of the VoxelNet encoder that raised the speed to 20 Hz, against 4.4 Hz for VoxelNet, while the 3D convolutions remained a bottleneck and the encoder of SECOND’s open-source implementation took 48 ms (Lang et al., 2019, §1, §1.1 and §6). In PointPillars’ Table 2 (KITTI test set, 3D detection), SECOND reaches 73.66 AP on cars at moderate difficulty, against 65.11 for VoxelNet and 74.99 for PointPillars, which avoids 3D convolutions by encoding vertical pillars into a pseudo-image. The KITTI article gives the benchmark’s matching rules and difficulty levels. The README of SECOND’s official code announces a “sparse convolution-based network” with version 1.5 (January 2019), and the code’s middle extractor, described above, is built from spconv layers; the README now marks the project as deprecated and points users to OpenPCDet and MMDetection3D, which it says implement SECOND and support spconv 2.x. The TorchSparse paper reports that, at its writing, nine of the top ten nuScenes detection entries and the two winning Waymo Open Dataset solutions used sparse-convolution-based detectors (Tang et al., 2022, §1).

LiDAR semantic segmentation. SemanticKITTI, as Tang et al. (2020, §5.1) describe it, annotates all 22 sequences of the KITTI odometry benchmark, with 23,201 LiDAR scans for training and 20,351 for testing. They report outdoor segmentation results on its official test set in the single-scan setting, by mean IoU. There MinkowskiNet is listed at 63.1 mIoU and SPVNAS at 66.4, while 2D projection networks (DarkNet21Seg and DarkNet53Seg) score 47.4 and 49.9 (Tables 2–3). The TorchSparse paper states that all top five SemanticKITTI segmentation submissions were based on sparse convolution at its writing (§1).

Indoor scenes. On the ScanNet 3D semantic label benchmark, MinkowskiNet42 reported 67.9% mIoU on the hidden test set at 5 cm voxels, which Choy et al. describe as 19 points above the best work published by the CVPR deadline, and 72.1% at 2 cm after the deadline; their Table 1 lists SparseConvNet at 72.5% as another post-deadline entry (Choy et al., 2019, Table 1 and §7.4). On S3DIS, which Choy et al. describe as scans of six floors of three buildings, MinkowskiNet32 reached 65.35% mIoU on the Area 5 (Fold 1) test, against 57.26% for PointCNN and 41.09% for PointNet in their Table 4. Graham et al. (2018, Table 4) reported 64.1% pixel accuracy on 40 classes of the NYU Depth v2 test set for a small submanifold FCN at 1.09 GFLOPs with single-view testing, against 61.5% for a 2D FCN at 28.50 GFLOPs; setting all depths to zero removed 60% of the FLOPs and dropped accuracy to 50.8%, which they take as evidence that the network uses the 3D structure (§6.6).

Objects. On the test set of the 2017 ShapeNet part segmentation challenge, a submanifold FCN trained on the aligned objects reached 85.98% average IoU (Graham et al., 2018, Table 1; the text calls the same number a “test error”); the ShapeNet article gives the challenge report’s own figures.

Other uses. Sparse convolutional backbones also compute dense descriptors for point cloud registration (that article describes FCGF, a sparse fully convolutional network), and are used for scene completion and generation, where transposed sparse convolutions create new sites that a classifier prunes (spconv docs/USAGE.md; MinkowskiEngine README examples). 3D occupancy prediction and bird’s-eye-view perception work with voxel or BEV grids of the same kind.

Limitations

• Quantization. Every voxel network sees the scene at its voxel size. Points in one voxel are merged, labels that disagree inside a voxel are ignored in training (Choy et al., 2019), and repeated downsampling makes deep layers coarse; Tang et al. (2020) argue that this hurts small objects such as pedestrians and cyclists in outdoor scans.
• Information flow. Submanifold convolutions cannot cross empty space, so disconnected parts communicate only through strided layers (Graham et al., 2018, §4), and the example above shows how this depends on the gap and the number of downsamplings. Regular sparse convolutions cross gaps but lose sparsity.
• No completion without new sites. Submanifold and inverse convolutions can only label sites that exist. Completing or generating geometry needs transposed convolutions that create sites and a step that removes the wrong ones; spconv’s documentation calls its transposed convolution very slow (docs/USAGE.md).
• Irregular computation. The work per kernel offset varies, features must be gathered and scattered through index lists, and rulebooks must be built for every new set of coordinates. The TorchSparse paper reports that gather and scatter can take up to half of the runtime, and that sparse convolution was not supported by general inference libraries such as TensorRT and TVM at its writing (Tang et al., 2022, §1).
• Kernel size in high dimensions. A full kernel has $K^D$ weight matrices, which is why Choy et al. use hybrid kernels in 4D and SparseConvNet’s README warns against size-3 kernels from five dimensions.
• Software. As of November 2026, the libraries depend on custom CUDA code compiled for particular CUDA and PyTorch versions, and two of the original code bases show no recent development: MinkowskiEngine’s last commit is from March 2023, and second.pytorch’s README marks the project as deprecated.

Important Models

• SSCN (Graham, Engelcke & van der Maaten, 2018): submanifold sparse FCNs and U-Nets; ShapeNet part segmentation and NYU Depth v2.
• SECOND (Yan, Mao & Li, 2018): VoxelNet-style LiDAR detection with a sparse convolutional middle extractor feeding a bird’s-eye-view region proposal network.
• MinkowskiNet (Choy, Gwak & Savarese, 2019): ResNet- and U-Net-style 3D and 4D networks on generalized sparse convolutions; ScanNet, S3DIS, Synthia 4D.
• SPVNAS (Tang et al., 2020): sparse point-voxel convolution with architecture search for SemanticKITTI.
• PointPillars (Lang et al., 2019) is a pillar-based alternative that avoids 3D convolutions altogether, and point networks such as PointNet avoid voxels.