Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges

Michael M. Bronstein; Joan Bruna; Taco Cohen; Petar Veličković

Source-linked AI summary

Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges

Michael M. Bronstein, Joan Bruna, Taco Cohen, Petar Veličković

arXiv:2104.13478v2Apr 27, 2021cs.LGcs.AIcs.CGcs.CVstat.ML

TL;DR

Generic high-dimensional function learning faces a curse of dimensionality, while real-world data contain exploitable geometric regularities. The paper unifies neural architectures through symmetries and invariances, showing how these principles encode physical knowledge and guide architecture design, while acknowledging important geometric and survey-scope limitations.

Problem
High-dimensional learning of generic functions suffers from the curse of dimensionality, motivating priors that capture regularities arising from physical structure.
Method
The paper develops Geometric Deep Learning by deriving inductive biases and architectures from symmetries, invariances, and geometric structure across data domains.
Results
The resulting geometric framework connects CNNs, RNNs, GNNs, and Transformers while providing a procedure for incorporating prior physical knowledge into architectures.
Takeaways & Limitations
Geometric principles provide a common framework for studying existing architectures and a principled route toward future architectures.
Takeaways & Limitations
The geometric treatment cannot generally use a globally shared filter on manifolds, and a smooth global gauge may not exist, as on S2.

Abstract

from arXiv · show

The last decade has witnessed an experimental revolution in data science and machine learning, epitomised by deep learning methods. Indeed, many high-dimensional learning tasks previously thought to be beyond reach -- such as computer vision, playing Go, or protein folding -- are in fact feasible with appropriate computational scale. Remarkably, the essence of deep learning is built from two simple algorithmic principles: first, the notion of representation or feature learning, whereby adapted, often hierarchical, features capture the appropriate notion of regularity for each task, and second, learning by local gradient-descent type methods, typically implemented as backpropagation. While learning generic functions in high dimensions is a cursed estimation problem, most tasks of interest are not generic, and come with essential pre-defined regularities arising from the underlying low-dimensionality and structure of the physical world. This text is concerned with exposing these regularities through unified geometric principles that can be applied throughout a wide spectrum of applications. Such a 'geometric unification' endeavour, in the spirit of Felix Klein's Erlangen Program, serves a dual purpose: on one hand, it provides a common mathematical framework to study the most successful neural network architectures, such as CNNs, RNNs, GNNs, and Transformers. On the other hand, it gives a constructive procedure to incorporate prior physical knowledge into neural architectures and provide principled way to build future architectures yet to be invented.

Notation

The notation formalizes signals, functions on signals, symmetries, and discrete geometric domains such as meshes and their metrics.

A domain signal x(u) maps domain elements u to values in C.
A function f(x) maps signals on a domain to outputs in Y.
G denotes a group, while g denotes an element of that group.
For discrete domains, x_u is a vector at element u, and x_uj is its jth scalar component.
F(X) maps discrete domain signals to another discrete domain signal represented as a matrix.
A mesh T=(V,E,F) consists of nodes V, edges E, and faces F; ℓ(γ) and ℓ_uv denote curve length and edge metric.

1 Introduction

The paper frames Geometric Deep Learning as a unifying geometric perspective for neural architectures, using symmetries and physical structure to define inductive biases and guide architecture design.

Deep learning succeeds partly through representation learning, which adapts hierarchical features to task-specific regularities.
High-dimensional learning is difficult for generic functions, whereas real tasks contain regularities from the physical world’s low-dimensional structure.
Geometric Deep Learning derives inductive biases and network architectures from first principles of symmetry and invariance.
The framework provides a common mathematical language for CNNs, RNNs, GNNs, and Transformers.
It also offers a constructive procedure for incorporating prior physical knowledge and designing future architectures.
The scope centers on representation-learning architectures and symmetries, not self-supervised, generative, reinforcement-learning, optimization, or regularization pipelines.
The text studies selected well-known architectures in depth rather than accurately summarizing all Geometric Deep Learning research.

2 Learning in High Dimensions

Learning in high dimensions requires inductive biases that capture regularity, because generic function estimation suffers from severe dimensionality-dependent sample complexity.

Supervised learning estimates an unknown function from N i.i.d. observations in a high-dimensional data space.
Neural networks can interpolate training observations, but successful learning still requires an appropriate notion of regularity or inductive bias.
Universal approximation does not eliminate inductive bias, because a complexity measure can select among interpolating functions.
Complexity measures can be imposed explicitly through empirical-loss regularization or implicitly through optimization, including weight decay and path-norm choices.
For 1-Lipschitz functions, ensuring discrepancy κ(d)≃ϵ requires N=Θ(ϵ^-d), so an ϵ-net grows exponentially with dimension.
The Sobolev minimax rate is of order ϵ^-d/s, with extra smoothness helping statistically only when s∝d, described as unrealistic in practice.
Sparsity-promoting regularization can break the curse of dimensionality but assumes the target depends on low-dimensional projections.

3 Geometric Priors

Geometric Deep Learning uses domain structure, symmetries, and scale separation to derive stable, invariant, and expressive neural representations across geometric data domains.

Geometric priors: Physically structured data motivates two geometric priors: symmetry and scale separation, which underlie architectures such as CNNs through shared convolutional filters and pooling.These principles extend beyond images to graphs and manifolds.
Symmetries, representations, and invariance: Symmetries act on domains and signals, constraining functions through invariance or equivariance and providing an inductive bias for learning.The group framework formalizes compositions, inverses, and representations of these transformations.
Geometric operators: Differential operators such as the Laplacian can be expressed as convolutions, enabling Fourier-transform generalisations to graphs, groups, and manifolds.The resulting intrinsic construction extends spectral tools beyond Euclidean domains.
Deformation stability: Fourier representations can remain unstable under arbitrarily small deformations, whereas localised filters decompose signals into families of locally stable features across scales.These multiscale features are not yet invariant and require progressive processing toward low frequencies.
Scale separation: Scale separation coarsens the data domain into a hierarchy while preserving important signal characteristics, supporting classifiers defined on coarser domains.The text describes this coarsening as applicable to very general domains.
The blueprint: The Geometric Deep Learning Blueprint combines local equivariant maps, global invariant maps, and coarsening operators into expressive representations with prescribed invariance and stability.It provides necessary geometric conditions rather than prescribing one specific architecture and applies across domains through choices of domain, symmetry group, and implementation.

4 Geometric Domains: the 5 Gs

The 5 Gs organise geometric deep learning around global symmetries, graph and manifold structure, intrinsic metrics, and local reference frames. These principles derive equivariant or invariant architectures while exposing trade-offs such as spectral instability, directional limitations, and gauge dependence.

The 5 Gs: The 5 Gs comprise grids, groups and homogeneous spaces, graphs, geodesics and manifold metrics, and gauges as local reference frames.Together they provide the geometric domains and structures used throughout the framework.
Grids and groups: Translational symmetry makes convolution the linear operation that is equivariant to shifts, linking convolution directly to a symmetry principle.Shift-equivariant linear operators are convolutions, and Fourier transformation jointly diagonalises shift operators.
Graphs and spectra: Graph Fourier constructions generalise grid convolution by using eigenvectors of graph operators, but their bases depend on graph structure and can hinder cross-domain generalisation.On graphs, spectral organisation is one-dimensional, so graph filters are also oblivious to direction.
Geodesics and manifolds: Intrinsic manifold quantities can provide isometry-invariant features, while spectral filters remain vulnerable to geometric perturbations and high-frequency eigenfunction changes.Spectral transfer functions are presented as a more stable alternative to direct Laplacian diagonalisation, and intrinsic expressions extend to approximate isometries.
Geodesics and gauges: Manifold convolutions require local filters and gauges because global homogeneous-space structure, path-independent transport, and globally smooth frames may be unavailable.Near gauge singularities, filter orientations can vary wildly and produce non-smooth feature maps.
Gauges: Gauge-equivariant maps keep the underlying mapping invariant when local frames change, with input and output features transforming through group representations.This treats gauge transformations as symmetries of signals expressed relative to local frames.
Meshes and functional maps: Laplacian-based mesh operators encode intrinsic structure and support remeshing-invariant functions based on their spectra.The cotangent Laplacian is positive semidefinite, symmetric, local, and invariant under metric-preserving mesh deformations.
Meshes and functional maps: Functional maps replace point correspondences with linear correspondences between functions on domains, offering an operator-based view of mesh relations.They establish correspondence between signals on respective domains through a matrix operator.

5 Geometric Deep Learning Models

The section applies the geometric blueprint across major neural architectures by matching domains, symmetries, and locality notions. It covers CNNs, group-equivariant CNNs, GNNs, set and Transformer models, mesh networks, and RNNs.

The discussion first derives CNNs, group-equivariant CNNs, and GNNs from the geometric blueprint.
Deep Sets and Transformers are presented as GNN instances for unordered sets whose graph structure is not known upfront.
Equivariant message passing networks introduce explicit geometric symmetries into GNN computations.
Geodesic and gauge principles recover intrinsic mesh CNN families, including Geodesic CNNs, MoNet, and gauge-equivariant mesh CNNs.
The temporal-grid discussion derives translation-equivariant RNNs and studies stability to time warping, with gated RNNs enforcing invariance to such transformations.
The exposition is illustrative rather than exhaustive, aiming to help readers categorize future geometric architectures through invariances and symmetries.

5.1 Convolutional Neural Networks

CNNs arise from local translation-equivariant convolutions, combined with nonlinearities and grid coarsening to build multiscale representations. The section highlights residual parametrisation, normalization, and data augmentation as important CNN developments.

CNNs implement linear local translation-equivariant operators as convolutions with localized filters.
Directional-derivative and local-average generators provide alternative bases for equivalent local linear equivariant operations.
Multichannel convolutional filters form tensors that linearly combine input features into output feature maps.
Pooling coarsens grids after convolution, producing multiscale filters with increasing receptive fields while retaining a constant number of parameters per scale.
A vanilla CNN layer composes an equivariant linear layer, grid coarsening, and a nonlinearity; ReLU rectifies signals and supports higher-order interactions across scales.
Deep and Residual Networks: Empirical evidence favors deeper, thinner CNNs, while residual parametrisation models feature perturbations and supports training much deeper architectures through more favorable optimization geometry.
Data augmentation is empirically successful and widely used, but is provably sub-optimal in sample complexity compared with architectures using richer invariance groups.

5.2 Group-equivariant CNNs

Group-equivariant CNNs extend convolution from Euclidean domains to homogeneous spaces by moving filters with group actions, producing equivariant feature maps. The framework covers discrete rotations and reverse-complement DNA symmetry, with implementation strategies including transformed filters and Fourier-domain computation.

Group convolution generalises convolution from Euclidean domains to signals on homogeneous spaces acted upon transitively by a group.
Discrete group convolution: For 3D volumetric images, the symmetry group combines translations on Z3 with the 24-element discrete rotation group Oh.Oh is generated by 90-degree rotations about the three coordinate axes.
Discrete group convolution: DNA sequences use translation symmetry together with a two-element reverse-complement group, because either double-helix strand may be read from its 5′ end.Reverse-complement transformation reverses the sequence and replaces each letter by its complement.
Transform+Convolve approach: The transform+convolve implementation creates a transformed copy of a canonical filter for each group element, then applies ordinary translational convolution to each copy.For discrete rotations and DNA symmetry, transformations permute filter coefficients.
Group-convolution outputs can be stored as orientation channels, and group actions permute these channels while transforming their feature maps.The channel count equals the number of independent filters multiplied by the number of transformations.
For spherical domains, convolution can be computed spectrally using spherical harmonics on S2, Wigner D-functions on SO(3), and FFT-like transforms.The convolution theorem becomes an element-wise product of Fourier coefficients.

5.3 Graph Neural Networks

Graph Neural Networks implement the geometric deep learning blueprint on graphs through permutation-equivariant local aggregation. Most GNN layers are organised into convolutional, attentional, and message-passing flavours that form a representational containment hierarchy.

GNNs construct permutation-equivariant functions by applying shared permutation-invariant local neighbourhood operations to node features and adjacency structure.Neighbourhood features are transformed, aggregated, and used to update each node.
The literature is broadly organised into three GNN flavours—convolutional, attentional, and message-passing—distinguished by how neighbourhood interactions are transformed.These flavours govern the complexity with which node interactions are modelled.
Convolutional flavour: Convolutional GNNs aggregate neighbourhood features with fixed coefficients that often depend directly on graph adjacency entries.Summation aggregation can be interpreted as linear diffusion or position-dependent filtering.
Attentional flavour: Attentional GNNs compute feature-dependent importance coefficients α_uv = a(x_u, x_v), often normalised across neighbours.With summation, the result remains a linear combination, but its weights depend on node features.
Message-passing flavour: Message-passing GNNs compute vector-valued edge messages from both sender and receiver features before aggregation.The message function ψ is learnable and determines the vector sent across each edge.
The representational hierarchy is convolution ⊆ attention ⊆ message-passing, although message passing is typically harder to train and more memory-intensive.Convolution and attention are special cases of message passing under restricted message functions.
The three-flavour categorisation is intentionally brief and excludes higher-dimensional Weisfeiler–Lehman and explicitly Fourier-based spectral GNNs.

5.4 Deep Sets, Transformers, and Latent Graph Inference

Deep Sets, Transformers, and latent graph inference arise by choosing how much relational structure to model among unordered node features. This spectrum trades efficiency and simplicity against expressivity and the difficulty of learning graph structure.

Empty edge set: Deep Sets process unordered inputs with shared transformations and permutation-equivariant operations, corresponding to a GNN with empty neighbourhoods or A = I.They have theoretically established universal-approximation properties and are useful for point-cloud data.
Complete edge set: Assuming an empty edge set is efficient but discards latent relations that may exist among set elements and could improve performance.
Transformers: Transformers can be posed as attentional GNNs over a complete graph, where self-attention infers a soft adjacency matrix from node features.Normalised attention coefficients can be interpreted as soft edge weights.
Transformers: Because complete-graph aggregation ignores sequence order, Transformers augment node features with positional encodings.These encodings typically use sine waves whose frequencies depend on position.
Transformers: On graphs without natural node order, Transformer positional encodings relate to the discrete Fourier transform and Laplacian eigenvectors of a circular grid.
Inferred edge set: Latent graph inference learns an adjacency matrix between node features, potentially supporting hypotheses about useful relations or causal structure.It is more expressive than assuming either no edges or a complete graph.
Inferred edge set: Latent graph inference is challenging because discrete structure learning must be balanced against the downstream objective during gradient-based optimisation.

5.5 Equivariant Message Passing Networks

Equivariant message-passing networks incorporate Euclidean geometry into graph representations by transforming coordinates and features consistently under E(3). The basic construction is efficient but restricts feature transformations, motivating broader representation-based approaches.

Equivariant graph layers separately update node features and spatial coordinates so outputs transform consistently under Euclidean symmetries.Under an E(3) transformation, coordinates rotate or reflect through R and translate by b.
The equivariant message-passing construction depends on inter-node distances, which remain unchanged under E(3), and is therefore efficient to implement.Its computations instantiate the message-passing GNN flavour.
Satorras et al. enable coordinates to transform correctly under rotations, reflections, and translations by treating them as E(3) objects.
The basic architecture treats learned node features as invariant scalars, limiting the spatial information it can represent.Velocities are handled in one variant, but arbitrary vector and tensor features require broader representations.
Existing broader approaches use either irreducible representations with equivariant kernels or regular representations that store feature copies for group elements.Regular representations are more general but impose additional computational burden for exact equivariance.
The section places equivariant graph methods within a wider family of explicitly geometry-aware approaches, including point-cloud, Lie-group, and mesh-specific networks.

5.6 Intrinsic Mesh CNNs

Intrinsic mesh CNNs adapt convolutional ideas to irregular 3D geometry by using geodesic patches, local coordinates, and gauge-aware filters. The main design choices trade directional information against invariance to arbitrary local reference frames.

Geodesic patches: Geodesic patches represent nearby mesh nodes in local polar coordinates defined by geodesic distance and angle.A geodesic is shot from a node to a nearby point, and the resulting patch is expressed through the exponential map and a local polar frame.
Gauge handling: Local gauge ambiguity arises because geodesic patch orientation is defined only up to an arbitrary rotation that may differ at every node.Fixed-gauge methods can use principal curvature directions, although this choice is non-intrinsic and ambiguous at flat or uniformly curved points.
Gauge handling: Isotropic filters remove dependence on local direction and gauge, but they can discard directional information needed for edge-like features.Angular max pooling instead matches an anisotropic filter across rotations and aggregates the strongest responses.
Patch operators: Patch operators discretise continuous mesh convolutions by weighting multi-hop neighbours with functions that act as soft pixels and aggregating the results.The weighting functions may be predefined or learnable, while the filter coefficients are learned.
Gauge handling: Gauge-equivariant convolutions transport neighbour features between local frames and constrain learned kernels so outputs transform according to a chosen representation.The neighbour kernel depends on the neighbour angle, making the convolution anisotropic, while transporter matrices encode parallel transport.

5.7 Recurrent Neural Networks

RNNs process sequential inputs by encoding each step and repeatedly updating a shared summary vector. Their geometric analysis exposes a translation-equivariance condition tied to the initial state and shows why ordinary recurrence does not satisfy it generally.

Sequential inputs: Sequential data consists of arbitrarily many steps, each providing an input signal X(t), often over a fixed domain such as video frames or traffic graphs.The domain may also evolve over time, as in dynamic social networks, although the section focuses on fixed domains.
SimpleRNNs: An encoder f maps each input step to a latent vector z(t), after which a shared recurrent update aggregates the sequence into summary vectors h(t).For video, a translation-invariant CNN can encode each frame into a k-dimensional representation.
Translation equivariance: RNNs exhibit an unusual symmetry over input vectors, but left-shifting a sequence does not generally produce the correspondingly shifted summaries.The failure arises because the shifted computation starts from an initial state that need not match the first update.
SimpleRNNs: The final summary h(T) can be classified for whole-sequence prediction, while each intermediate h(t) can support prediction at its corresponding step.The initial summary is typically zero or learnable.
Translation equivariance: Left-shift equivariance holds when the initial summary satisfies h(0) = R(0, h(0)), making it a fixed point of γ(h) = R(0, h).If γ is a contraction, iterating R converges to a unique fixed point; this is equivalent to left-padding with sufficiently many zero-vectors.

5.8 Long Short-Term Memory networks

LSTMs extend recurrent computation with a persistent memory cell and learned gates that regulate information flow. This gating mechanism addresses vanishing gradients and supports a form of time-warping invariance unavailable to SimpleRNNs.

LSTM architecture: Gated RNNs reduce vanishing-gradient effects by learning how much information and gradient flow to retain across time steps.The forget-gate values are data-dependent and directly influence the recurrent update.
LSTM architecture: LSTMs add a memory cell c(t) whose state is preserved between steps and from which the summary h(t) is computed.The cell is only partially overwritten using the current input, previous summary, and previous cell state.
LSTM architecture: Input, forget, and output gates control how candidate features enter, previous cell content is retained, and the cell state produces the summary.The gates are vectors in [0, 1], allowing control over each memory dimension.
Time-warping invariance: Gated RNNs can be invariant to time-warping transformations, whereas SimpleRNNs are not because they fully overwrite the summary without the required derivative-dependent term.Time warping includes rescaling and variable acceleration or deceleration of sampling.
Time-warping invariance: The gates’ role under the continuous-time analysis is to fit the derivative dτ(t)/dt of the time-warping transformation.The required update form contains a learnable function Γ that accounts explicitly for the warping.
Initialisation: Chrono initialisation samples gate biases to obtain an appropriate range of gating values and has been empirically shown to improve long-range dependency modelling.The recommendation is bΓ ∼−log(U(Tl, Th)−1).

6 Problems and Applications

Geometric deep learning is applied across scientific, medical, industrial, and consumer problems, where structured representations support practical prediction and generation tasks.

Drug discovery: Drug discovery applications use graph representations to model biochemical interactions and identify therapeutic opportunities.Halicin was discovered as a potent antibiotic, including against bacteria with known antibiotic resistance, while drug repositioning evaluates approved drugs for new purposes.
Recommendation and transportation: Graph neural networks have supported large-scale recommendation and transportation systems deployed in production.Graph representation learning scaled to graphs with millions of nodes and billions of edges, while GNN-based ETA prediction was deployed in Google Maps.
Vision, games, and speech: Convolutional architectures enabled major advances in vision, game playing, sequence modeling, and speech generation.Examples include AlexNet’s ImageNet success, AlphaGo’s victory over Lee Sedol, competitive dilated convolutions, and WaveNet-based speech synthesis.
Language: Transformers achieved state-of-the-art machine translation and became widely useful through pretrained language representations.BERT embeddings supported downstream NLP applications, including Google search, while GPT-3 scaled language modeling to 175 billion parameters.
Scientific and medical applications: Geometric models have improved analysis of medical, physical, and biological data with irregular or relational structure.Applications include patient-network diagnosis, particle-jet reconstruction, astrophysical-neutrino detection, and real-time 3D hand-pose estimation.

7 Historic Perspective

The historical perspective traces symmetry from mathematical geometry and physics into machine learning, culminating in modern architectures that exploit invariance and equivariance.

Symmetry in Mathematics and Physics: Klein’s Erlangen Programme framed geometry as the study of invariants under symmetry transformations, formalized through group theory.
Symmetry in Mathematics and Physics: Symmetry principles in physics connected differentiable symmetries with conservation laws and helped organize theories of fundamental forces.
Early Use of Symmetry in Machine Learning: Machine learning adopted symmetry through invariant and equivariant feature detectors, shift-invariant neural networks, and convolutional architectures.
Graph Neural Networks: Graph neural networks emerged from several research areas, with early graph-processing models preceding the later practical adoption of generic graph structures.
Signal processing and Harmonic analysis: Harmonic-analysis approaches, including steerable pyramids and scattering transforms, sought theoretical explanations for CNN efficiency through multiscale and transformation-stable features.
Geometric Deep Learning: The text names Geometric Deep Learning as a synthesis of these developments, extending its scope from grids and graphs to groups, gauges, and geodesics.