Geometric Deep Learning I: A Linear G-Invariant Function of a Signal Depends on It Only Through the Group Average Ax = (1/μ(G)) ∫ g.x dμ(g)Textbook
Symmetry as a design principle
Geometric deep learning is the programme, set out by Bronstein, Bruna, Cohen and Veličković in Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (arXiv:2104.13478v2, 2021), of deriving neural network architectures from the symmetries of the domain on which the data live. Convolutional networks on images, permutation-invariant networks on sets, graph neural networks and equivariant networks for molecules are presented there as instances of one template. Chapter 3 of the book, Geometric Priors, gives that template: it fixes what a symmetry of a signal is, what it means for a function to respect it, and how invariant functions are assembled from simpler blocks. This mission formalizes the definitions and the elementary claims of Chapter 3. Its goal is the observation the book uses to explain why such networks must be non-linear.
The book numbers no theorem, lemma or definition. Its only labels are the sections, the equations (1)–(53) and the figures. Every item of this mission is therefore cited by section, equation number (where there is one) and printed page of the arXiv v2 text; a margin note is cited as "side-note, p. n".
Setting
A domain is a set . A signal on with values in a set of channels is a function ; the signals form the space (equation (1)), written when .
A group acts on through a map with . It then acts on signals by equation (3):
On real signals this action is linear, so defines a representation of on .
A function is -invariant if for all and . A map between signal spaces on which acts is -equivariant if . A map acts on signals element-wise, .
For a measure on with , the -average of a real signal is
The book takes to be the Haar measure of the group.
The metric distortion of a map between metric spaces is (§4.4, p. 51). A self-map with distortion at most is an -isometry.
The Geometric Deep Learning Blueprint (§3.5, p. 29) builds functions
from equivariant linear layers , element-wise nonlinearities , poolings onto coarser domains, and an invariant global pooling .
Formalization targets
Goal: linear invariants see only the average (§3.5, p. 27)
For a finite domain , a finite nonzero measure on , and a linear -invariant map from into a real Banach space, for every signal ,
A linear invariant therefore depends on only through .
Milestones, in attack order
- The action (3) is a group action: (p. 14).
- It is linear: (p. 15).
- It is a representation: (p. 15).
- Two -isometries compose to a -isometry, and -isometries are not closed under composition (side-note, p. 20).
- is equivariant for equivariant and any element-wise (p. 27).
- The -average is invariant, so is invariant (p. 27).
- The blueprint is -invariant (p. 29).
Companion: the Fourier modulus (§3.4, p. 25)
With and , , so .
Significance
The goal is the book's reason for non-linearity. Linear invariant models collapse to functions of the group average, so they cannot tell apart two images with the same mean colour. Expressive invariant models must interleave equivariant linear layers with non-linear maps. Milestones 5–7 are the positive half of the same argument: element-wise nonlinearities keep equivariance, the average turns equivariance into invariance, and stacking such blocks gives the blueprint that the later chapters instantiate on grids, groups, graphs and manifolds. Milestone 4 is the book's reason for leaving exact symmetry behind: small deformations do not form a group, so it replaces invariance to deformations by stability to them.
Each claim of the chapter is proved in one or two lines on the page, and none is new mathematics. What a formalization adds is the precise setting in which they hold. The book names the Haar measure but its identity needs no invariance of ; the average's invariance needs right invariance, which the page does not state; and the printed blueprint is invariant only if the poolings are equivariant. As far as a search of the platform and Mathlib shows, none of these statements has a machine-checked proof. The definitions here (the action on signals, invariance, equivariance, the average, the blueprint) are reusable by every later mission of this series.
Difficulty
The obvious argument for the goal pulls through the integral, which uses linearity in the form "a continuous linear map commutes with the Bochner integral". That needs continuity of and integrability of , and neither is stated on the page. On a finite domain both follow from the setting, finite dimension for continuity and boundedness with measurability for integrability. The measurability of has to be assumed of the group and the action.
For the average's invariance, the substitution is valid only for a right-invariant measure. For the blueprint, the composite's invariance fails for a non-equivariant pooling, so the box's claim is false as printed. For the -isometries, the subtle half is the negative one: exhibiting a deformation that is an -isometry while its square is not.
Formalization scope
- Signals are functions
Ω → C. The goal and the average use real signals on a finite domain ([Fintype Ω]), following the book's side-note on p. 15 that one must always discretise to a finite grid in practice; the other milestones allow any domain and any channel types. - The action (3) is a function
act g x := fun u => x (g⁻¹ • u)for[MulAction G Ω], not aMulActioninstance onΩ → C. - The measure is any
μwith[IsFiniteMeasure μ]andμ ≠ 0. Without those hypotheses Lean's(μ univ).toReal⁻¹would be and the goal false. The goal assumes no invariance ofμ. Milestone 6 adds[μ.IsMulRightInvariant], which the Haar measure of a compact group satisfies. - Measurability:
[MeasurableInv G],[MeasurableSMul G Ω]and the discrete σ-algebra onΩ; integrability ofg ↦ g.xis a consequence, not a hypothesis. A finite group with the counting measure and a compact group with its Haar measure both fit. - The blueprint is indexed from to . A single group acts on all domains, and the poolings are assumed equivariant (a correction of the printed box, disclosed in the statement). The box's remark that different blocks may use different groups is not formalized.
- -isometries are defined pointwise ( for all ), avoiding a real supremum that would be on an unbounded set. Non-closure is witnessed on by a continuous bijection.
- The Fourier transform of the companion is the book's (no ), a Bochner integral over .
The goal cannot be satisfied trivially. groupAverage is defined from μ and the action alone, the goal quantifies over every linear invariant f, and the measure hypotheses exclude the degenerate case in which the average is . Proofs, finite-sum encodings of the average, and versions for complex or vector-valued channels are welcome.
Selected references
- M. M. Bronstein, J. Bruna, T. Cohen, P. Veličković, Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, arXiv preprint, 2021. https://arxiv.org/abs/2104.13478v2
- S. Mallat, Group Invariant Scattering, Communications on Pure and Applied Mathematics 65(10), 2012. https://doi.org/10.1002/cpa.21413