Position: Categorical Deep Learning is an Algebraic Theory of All Architectures
Bruno Gavranović, Paul Lessard, Andrew Dudzik, Tamara von Glehn, João G. M. Araújo, Petar Veličković
ICML 2024
cs.LG, cs.AI, math.CT, math.RA, stat.ML
2024-02-23
An ICML 2024 position from Symbolica and DeepMind: monad algebras in the 2-category Para recover GDL equivariance and implement RNNs, including weight tying, in one language.
Deep learning still lacks a single drawing that states both the constraints a model must satisfy and the tensor program that implements it. Top-down, geometric deep learning (GDL) writes layers as solutions to equivariance constraints: convolution for translation, message passing and self-attention for permutation on graphs. It struggles with non-invertible targets. Algorithmic alignment to a shortest-path contraction irreversibly folds the data, and group actions are the wrong language. Bottom-up, PyTorch and JAX treat networks as pure functions, which is excellent for shape checks and backprop and weak at recovering which semantic constraint the implementation actually obeys.
This ICML 2024 position paper, from Symbolica AI and Google DeepMind (including Petar Veličković), argues that a guiding framework has to bridge those two directions, and that the bridging language should come from computer science. Group theory plus functional programming already have a common generalization: category theory. The precise claim is the universal algebra of monads valued in a 2-category of parametric maps.
GDL is recovered as monad algebra. A group G induces the group-action monad G×− on Set. Its algebras are group actions; its algebra homomorphisms are equivariant maps, f(g ▹ x)=g ▹ f(x). Translation, rotation, and permutation all fit the template, and convolution, GNNs, spherical CNNs, and G-CNNs fall out as special cases. Equivariance is the name of monad-algebra homomorphism in the group-action instance.
Drop the group axioms and keep endofunctor (co)algebras. Lists are algebras of 1+A×−, binary trees of A+(−)², Mealy machines coalgebras of I→O×−. Algebra homomorphisms are necessarily folds; coalgebra homomorphisms are unfolds. The list equations fr(Nil)=r₀ and fr(Cons(h,t))=r₁(h, fr(t)) are "generalized equivariance" for an operation that is not an invertible group action. That package lines up with folding RNNs, recursive nets, and full RNNs.
Weights and nonlinear maps need a 2-category. In Para, objects are still sets, a 1-morphism is a parametric map (P, f: P×A→B), and sequential composition places parameter spaces in parallel. 2-morphisms are reparameterizations; the copy map ΔP: P→P×P is weight tying. The slogan: recurrent and recursive networks are lax algebras for the free parametric monad generated by a parametric endofunctor. In this construction the lax cells are comonoids, which is why vectors can be copied and deleted, and why weight tying is an algebraic fact rather than a coding convention.
There is no accuracy table. The evidence is derivation. GDL equivariance is rewritten as algebra homomorphisms of the group-action monad. Lists, trees, and automata are rewritten as endofunctor (co)algebras. Folding RNNs, unfolding RNNs, recursive nets, full RNNs, and Moore-machine RNNs appear as parametric (co)algebras in Para (Figure 1). Weight sharing is a 2-morphism, not an implementation comment. 1-cocycles used for asynchronous nets are claimed to sit inside morphisms of lax algebras.
The baseline is conceptual coverage, not GLUE. GDL handles symmetry and not irreversible algorithmic alignment. Tensor programs handle implementation and not constraint recovery. The paper writes both in one (2-)algebra.
Questions like "is this weight tying correct?" get a checkable criterion, instead of reading whether two Linears share an nn.Parameter. GDL typically stops at linear equivariant layers and outsources nonlinearity to pointwise activations. Morphisms in Para are parametric maps, so the object of analysis can span several layers. For people who already design equivariant or structured nets, this is a dictionary that puts constraints and implementations on the same page.
It is a position plus a reconstruction, not a new architecture paper. Nobody leaves with a drop-in layer. Type-safe networks, verifiable logical arguments, and fairness via categorical logic are listed under "new horizons". Those are research directions, not results.
2-categories, lax algebras, and algebraically free monads are heavy relative to the examples used to defend the position (CNNs, GNNs, RNNs), which GDL and functional programming already know. Para itself comes from Cruttwell et al. (2022) on gradient-based learning; this paper pushes it onto architecture constraints rather than inventing the 2-category. No experiment shows that a network designed from this drawing wins on any benchmark. The fairness and "verifiable argument" paragraphs are a wish list without a construction. Choosing the category is the same design move as choosing the group in GDL, and a bad choice writes an empty constraint. Linear equivariant layers still have to live in Vect before weight sharing becomes a matrix condition, and the theory of nonlinearities in the main text remains a program.