Geometric Deep Learning
Symmetry as inductive bias
Why Geometry Matters
A model's output can respond to a rotation of its input in two ways. Rotating an image should leave its class label unchanged, but it should turn the box an object detector draws around the object by the same angle. The label is invariant to the rotation; the box transforms with the input.
Geometric deep learning makes this precise: it designs networks that are equivariant to a group of transformations of the input (Bronstein et al., 2021).
Equivariance
A function f is equivariant to a group of transformations if transforming the input transforms the output in a matching way. Write ρ(g) for how a transformation g acts on inputs and ρ′(g) for how it acts on outputs:
f(ρ(g)x) = ρ′(g)f(x) for every g in the group
Invariance is the case ρ′(g) = identity: f(ρ(g)x) = f(x)
The figure has its own rotation control. Turn the input arrow: an equivariant output, such as an object detector's box, turns with it; an invariant output, such as a class label, stays put.
Explore in depth →CNNs as Translation Equivariance
Convolutional neural networks are built to be equivariant to translations. A feature detected at position (x, y) will be detected at position (x+Δx, y+Δy) when the input is shifted by (Δx, Δy).
So a network does not need to learn separate detectors for "cat in the top-left corner" and "cat in the bottom-right corner". The guarantee is exact for a convolution and shifts by whole pixels; strides, pooling and image borders make a full network only approximately shift-equivariant, and small shifts can change its output (Azulay & Weiss, 2019).
The same convolutional kernel is applied at every spatial location, encoding translation equivariance into the architecture.
Chapter 9 of Goodfellow, Bengio & Courville (2016) explains how weight sharing gives this property. Group-equivariant CNNs (Cohen & Welling, 2016) share weights across rotations and reflections as well, in the same way.
Group Theory
The symmetries of a problem form a group: a set of transformations that can be composed, that includes doing nothing, and in which every transformation can be undone. Common examples:
| Group | Symmetry | Application |
|---|---|---|
| SO(2) | Rotation in the plane | Aerial imagery |
| SE(3) | Rotation + translation in 3D | Molecules, robotics |
| Sn | Permutation of n items | Sets, graphs |
The figure shows a related idea for curved spaces. On a sphere, carrying a vector around a closed loop without turning it can bring it back rotated, so there is no single way to compare directions at different points. Networks on curved surfaces have to account for this (Cohen et al., 2019).
Graph Neural Networks
The numbering of a graph's nodes is arbitrary, so a graph network should not depend on it. In message passing (Gilmer et al., 2017), each node updates its state from its own state and an aggregate of its neighbours' states:
hv(k) = UPDATE(hv(k-1), AGG({hu(k-1) : u ∈ N(v)}))
The aggregation (sum, mean, max) ignores the order of the neighbours, and the same UPDATE is applied at every node. Renumbering the nodes therefore renumbers the outputs in the same way: the network is permutation-equivariant. Summing over all nodes at the end gives a permutation-invariant output for the whole graph.