Geometric Deep Learning

Reorder a graph’s nodes and a plain network changes its answer, though the graph is the same. A layer built from the graph’s symmetry does not. This paper shows how to build that layer for any data.

Grids, Groups, Graphs, Geodesics and Gauges: one blueprint behind convolutional networks, graph networks, transformers and more.

Press Reorder the nodes a few times on each network. Watch the score. Then we build, piece by piece, the idea underneath: what a symmetry is, why convolution falls out of it, and how one blueprint covers every kind of data.

You need a little linear algebra: a grid of numbers called a matrix, and how it multiplies a list. You need a first feel for a neural network, a stack of simple functions with adjustable weights. We build the rest from zero.

Paper: Michael M. Bronstein, Joan Bruna, Taco Cohen and Petar Veličković, Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (arXiv 2104.13478, 2021). One of the assigned readings for the lecture MIT MMAI, Multimodal AI: Datasets and Research (Spring 2026, Paul Liang, MIT Multisensory Intelligence group). Every idea is re-taught here in our own words and devices.

Reorder the nodes

Illustrative toy, not a result from the paper. Six nodes A to F, two numbers per node, seven edges. The plain network reads the node table and the adjacency table in row order (48 numbers, 8 hidden units). The symmetric network gives every node the same small layer, adds up its neighbours, and sums over nodes (the recipe of Chapter 6). Both have fixed random weights, the same on every visit, and nothing is trained.

Chapter 0

Why a Blank Network Is Doomed

See why a network that knows nothing about its data would need more examples than there are atoms in the universe

Picture a photo of a cat, 64 pixels wide and 64 tall, with three colour values per pixel. That photo is 12,288 numbers. Write them in one long list and you have a single point in a space with 12,288 dimensions. A dimension is one number you need to pin down a data point, like one coordinate on a map.

You want a function that looks at such a point and says “cat” or “not cat”. You have N labelled photos. This is supervised learning: a hidden rule f gives every input its label, and you must guess the rule from the examples. A neural network is your guess, written as a function with adjustable weights (the numbers training sets).

Examples alone say nothing about photos you have not seen. You need an assumption. The cheapest one is smoothness: nudge the input a little and the output moves only a little. The paper states it as 1-Lipschitz (named for the mathematician Rudolf Lipschitz).

|f(x) − f(x′)|
How far the label moves between two inputs, x and x′. The bars mean “size, ignoring sign”.
‖x − x′‖
How far apart the two inputs are, measured as a length. The label may move by at most that much.

That sounds gentle. It is not. Suppose you want the guess to be within a tolerance ε (epsilon) of the truth everywhere. Chop the input space into small cubes of side ε and put one example in each cube. In d dimensions the number of cubes is (1/ε)d.

The paper makes the same point with a picture (its Figure 2). Put a bump in each of the 2d quadrants of the space, some pushing up and some down. Unless you have seen most quadrants, a bump you missed leaves a constant error. So the sample size needed grows as ε−d: exponentially in d. This is the curse of dimensionality.

Count the samples you would need

The warm line is log10 of the samples needed, N = (1/ε)d. The dashed line is about 1080, a common estimate for atoms in the universe. Pick a tolerance, then drag the dimensions.

12

The rule N = (1/ε)d is the paper’s scaling, N of order ε−d (Section 2.2, Figure 2); the constant is dropped. The 1080 atoms figure is a common rough estimate, not from the paper. Computed live in your browser.

Look at the photo again. At a tolerance of 1/10 the 64×64 colour photo needs about 1012,288 examples. Even 12 dimensions and a 1/10 tolerance asks for a trillion. Real data sets hold millions, not 1012,288. Yet networks do learn to find cats. Something other than smoothness must be helping.

Fitting is easy. Generalising is the hard part.

You may have heard that a network with one hidden layer is a universal approximator: it can match any continuous function as closely as you like. The paper cites the 1990s results behind this. But the paper is blunt that this does not mean there is no inductive bias. An inductive bias is a built-in preference for some functions over others. A student who assumes a pattern continues in a straight line has one.

Weight decay is a bias: it prefers small weights. The paper adds that sparsity-promoting networks can beat the curse, but only if f depends on a few low-dimensional projections of the input (its Figure 3). A photo does not. Blur it and the meaning stays, yet most of the detail is gone.

A zoo, and a way out

The field responded with a zoo: convolutional networks for images, recurrent networks for sequences, graph networks for molecules and social networks, transformers for text, Deep Sets for unordered collections. Each came with its own vocabulary. The authors compare this to geometry in the nineteenth century, before Felix Klein.

In 1872 Klein proposed the Erlangen Programme: define a geometry by what it leaves unchanged. Euclidean geometry cares about lengths and angles because rotations and shifts preserve them. The paper borrows the move. Start from the symmetry of the data, and derive the architecture from it.

The key observation is that real data is not a generic point in 12,288 dimensions. It is a signal on a domain: pixel values on a grid, atom features on a molecule, user features on a social network. The domain has structure, and two principles use it. Symmetry says some transformations should not change the answer. Scale separation says that nearby details can be summarised before far-away ones are combined.

The road

The paper’s five Gs name the domains it covers: grids, groups, graphs, geodesics and gauges. This lesson follows its argument in order, with one device per idea.

  1. Symmetry and groups: what a symmetry is, and the four rules every set of symmetries obeys.
  2. Signals, invariance and equivariance: two ways a function can respect a symmetry.
  3. Convolution from shifts: the one linear layer left when you demand shift symmetry.
  4. Stability and scale: why exact symmetry is not enough, and what pooling adds.
  5. The blueprint: four building blocks that make a whole architecture.
  6. Graphs and sets: the permutation symmetry, Deep Sets and three kinds of graph layer.
  7. Attention is a graph network: the transformer on a complete graph.
  8. Groups, geodesics and gauges: rotations, curved surfaces and local frames.
  9. The whole paper on one page: numbers, code, limits and where to go next.
A learner knows only that the target function is smooth (1-Lipschitz). The data has d dimensions. How does the number of examples needed for a fixed accuracy scale?

Chapter 1

Symmetry and Groups

Learn what a symmetry is, and why every set of symmetries obeys the same four rules

Hold a triangular road sign by its centre and turn it one third of a full circle. It looks exactly as before. Flip it left to right. Again it looks the same. You have just found two symmetries of the sign. A symmetry is a change that leaves some property of an object untouched.

The property matters. A photo of a cat is still a cat photo if you slide it three pixels right. So sliding is a symmetry of the question “is this a cat?”. A molecule has the same energy if you spin it. A list of friends is the same group of friends in any order. Each task has its own symmetries, and the paper’s whole plan is to build them into the network.

Four rules that every set of symmetries obeys

Do one symmetry and then another. The result is again a symmetry, because both leave the property alone. That is the first rule, closure. Each symmetry can also be undone by another symmetry, its inverse. Doing nothing is a symmetry too: the identity. Last, when you chain three moves, it does not matter where you put the brackets: associativity.

A collection with those four rules is called a group. The paper writes the composition of g and h as gh and reads it right to left: first h, then g. It stresses one thing the rules do not include. Order may matter. Groups where it never matters are called commutative (or Abelian, after the mathematician Niels Henrik Abel). Many groups are not.

The road sign is the smallest case. Its symmetry group has six members: three turns (including no turn) and three flips. Two moves generate all six: a turn r and a flip f. A set of moves that builds the whole group by chaining is called a set of generators. Try the sign below.

Chain moves, then swap their order

Corners start as 1, 2, 3 (top, bottom right, bottom left). Add up to eight moves. The left triangle applies them in your order. The right one applies the same moves in reverse.

Try:

Toy example of the dihedral group D3 (the paper’s example in Section 3.1, an equilateral triangle). A turn moves each corner one place clockwise; a flip swaps the two bottom corners. All six outcomes are computed live in your browser.

The worked example, step by step

Start with corners [1, 2, 3], read top, bottom right, bottom left. Do turn, then flip. The turn sends the top corner to the bottom right, the bottom right to the bottom left, and the bottom left to the top. That gives [3, 1, 2]. The flip swaps the last two: [3, 2, 1].

Now reverse the order: flip, then turn. The flip gives [1, 3, 2]. The turn gives [2, 1, 3]. The two results differ: [3, 2, 1] against [2, 1, 3]. Order matters in this group. The group is non-commutative, and the paper warns that we must not assume otherwise.

Why a group, and not just a list

You might ask why the paper bothers with the four rules instead of just listing transformations. The rules give you two powers. First, they let you check a candidate symmetry set quickly: if composing two members can leave the set, you missed some. Second, they let you describe a huge set by a few generators. Rotations of a ball are infinitely many, but the rules still tell you exactly how any two combine.

Groups you will meet again

The sign’s group is tiny. The groups in machine learning are not. Shifting a row of n pixels with wrap-around gives n symmetries (the cyclic shifts). Reordering n items gives n! of them: 6 items have 720 orders, and 20 items have about 2.4 × 1018. Spinning a ball in space gives a continuous family called SO(3), the group of all 3D rotations, with no finite count at all.

The hero at the top of this page used the second group. Reordering six nodes is one of the 720 symmetries of a set of six. The paper also counts the symmetries of a particular graph, the Folkman graph, which has 3,840 automorphisms. An automorphism of a graph is a way to relabel its nodes that keeps every connection. A graph with many of them is highly symmetric.

Why bother with the algebra? Four rules are all it takes to state what “respecting a symmetry” means for any data. The same definition covers a triangle, a pixel grid, a set of atoms and a sphere. That is how one paper can unify so many architectures.

One more idea, from the paper’s Section 3.1. A symmetry of the domain (the shape the data lives on) acts on the signal (the numbers sitting on that shape). To shift an image, you move the pixel values, not the grid. Chapter 2 makes that precise.

Two symmetries g and h of an object are applied one after the other. What does the group definition guarantee?

Chapter 2

Signals, Invariance and Equivariance

Separate the answers that must not move when the input moves from the answers that must move with it

A phone camera takes a photo of a mug. You slide the mug three pixels to the right and shoot again. Ask two questions. “Is there a mug?” should still get the answer yes. “Which pixels belong to the mug?” should get the same outline, slid three pixels right. Both answers respect the shift. They respect it in different ways.

Data as a signal on a domain

To talk about this precisely, the paper separates two things. The domain Ω (omega) is the shape the data lives on: a row of pixels, a grid, a graph, a sphere. A signal x is a function that gives every point of the domain a list of numbers, called its channels. A colour image has the grid as domain and three channels (red, green, blue) at every pixel.

Signals on one domain can be added and scaled, point by point. So they form a vector space, a set where sums and multiples make sense. That is why the paper can use plain linear algebra on them.

How a symmetry moves a signal

A symmetry g of the domain moves points around. To move the signal, look up where each value came from. The paper writes this as a representation ρ(g): for each group element, a linear map that acts on signals.

ρ(g)x
The new signal you get after applying the symmetry g to the signal x.
u
A point of the domain, such as one pixel position.
g−1u
The point that g would send to u. The new value at u is the old value found there.

For a shift by two cells, a bump that sat at cell 3 now sits at cell 5. The new value at cell 5 comes from cell 3, which is 5 minus 2. The inverse is what makes the bookkeeping come out right.

Two ways to respect a symmetry

A function f is invariant if the answer does not change when the input is moved. It is equivariant if the answer moves in step with the input. Think of a weather map. “What is the highest temperature?” is invariant to sliding the map. “The temperature at every town” is equivariant: slide the map and the list slides with it.

Invariance
Move the input, get the identical output. Use it for one answer about the whole thing, like a class label.
Equivariance
Move the input, and the output moves the same way. Use it for answers at every point, like a mask or one feature per node.

Try four functions on a row of 16 cells. Slide the shift and read the check.

Shift the signal, test the function

Top row: the signal and the same signal shifted. Below: the function’s output on the shifted signal against the shifted output. Choose a function, then drag the shift.

5

Toy signal of 16 cells with wrap-around ends (so a shift never loses values). The weights in the last function are 1/16, 2/16 and so on up to 1, one per cell. Errors are computed live as the largest cell-by-cell difference.

The worked numbers

Take the five-cell signal (0, 1, 3, 0, 0) and shift it right by two: (0, 0, 0, 1, 3). “Biggest value” gives 3 both times, so it is invariant. Now blur, replacing each cell with the average of itself and its two neighbours (wrapping around). The original gives (0.33, 1.33, 1.33, 1, 0). The shifted signal gives (1, 0, 0.33, 1.33, 1.33).

Shift the first blurred list right by two and you get exactly the second one. The blur is equivariant. “Own weight per cell” multiplies each cell by a number tied to its position, so it fails the test: it cares where the bump is.

Failure, measurement, fix

The symptom: the mug moves by three pixels and a model changes its label. The measurement: shift every test image and count disagreements, or compute the gap in the device above. The paper’s fix is to stop hoping and to build the property in. If the layers are equivariant and the last step is invariant, the whole network is invariant to the symmetry, by construction and not by luck.

The paper also notes a trap. A function that is linear and invariant can depend on the input only through its average over the group. For images and shifts, that means only the average colour. Invariance alone is far too blunt. Linear equivariant maps are much richer, and they are what the next chapter builds.

Two last words from Section 3.2. An isomorphism is a structure-preserving match between two domains, such as two drawings of the same graph. An automorphism is such a match from a domain to itself. The automorphisms of a domain are the raw material for its symmetries.

You shift the input image. A network layer returns a feature map that shifts by the same amount. Which property does the layer have?

Chapter 3

Convolution Is What Shift Symmetry Leaves

Derive the convolution layer from one demand: moving the input must move the output

Take a ring of eight cells, numbered 0 to 7, with cell 7 touching cell 0. A signal puts one number on each cell. You want a linear layer: a rule that turns the eight input numbers into eight output numbers by multiplying and adding. Written as a table of weights, it is an 8 by 8 matrix, with 64 free numbers.

Now add one demand from Chapter 2. The layer must be shift-equivariant. Slide the input one cell and the output must slide one cell. How many of the 64 weights survive? The answer is the paper’s first big payoff, and it is a famous layer.

From a local rule to a matrix

On a grid, each cell has a fixed left neighbour and a fixed right neighbour. Every cell is treated alike, so the same rule must run at every cell u. Let that rule look at u−1, u and u+1 and mix them: the new value at u is a sum of three terms.

yu
The output at cell u.
θ−1
The weight on the left neighbour.
θ0
The weight on the cell itself.
θ1
The weight on the right neighbour. The same three numbers serve every u. Machine learning calls this weight sharing.

Write all eight such equations as one matrix. Row u holds θ−1, θ0, θ1 in columns u−1, u, u+1. Row u+1 holds the same three numbers, one column to the right. Every diagonal of the matrix is constant. Such a matrix is called circulant, written C(θ), because each row is the row above it, shifted round the ring.

Multiplying by a circulant matrix is the discrete convolution: C(θ)x = x ⋆ θ. The shift itself is a circulant matrix, with θ = (0, 1, 0, …). The paper proves the reverse as well: a matrix is circulant exactly when it commutes with the shift. Convolution is not a design choice. It is the only linear layer that respects shifts.

Share the weights, keep the symmetry

The grid shows the 8 by 8 layer as a matrix. Set the three shared weights, or switch to a layer with 64 free weights, and test: does shifting then applying equal applying then shifting?

0.3
0.4
0.3

Toy: 8 cells, wrap-around ends, a fixed made-up input (0, 1, 3, 0, 0, 2, 1, 0). The free layer holds fixed random weights, the same on every visit. Teal marks a positive weight and red a negative one; the numbers come from the sliders.

Two worked layers

Set (θ−1, θ0, θ1) = (1/3, 1/3, 1/3) and you get the blur of Chapter 2. On x = (0, 1, 3, 0, 0), cell 2 gives (1 + 3 + 0)/3 = 1.33. Now set (−1, 0, 1). The output is xu+1 − xu−1, an edge detector. On the same x the five values are: y0 = 1 − 0 = 1, y1 = 3 − 0 = 3, y2 = 0 − 1 = −1, y3 = 0 − 3 = −3, y4 = 0 − 0 = 0. The edge detector lights up where the signal rises and falls.

What the symmetry saved

A free layer on n cells has n2 weights. A circulant one has n, one per diagonal. And if you also ask the rule to be local, as in the equation above, it has just 3 weights, whatever n is. The paper calls this Theta(1) parameters per layer, and notes that scale separation is what justifies keeping filters small.

Illustrative arithmetic for a 64 by 64 colour image: a free layer from 12,288 numbers to 12,288 numbers has 12,2882 = 150,994,944 weights. A 3 by 3 convolution from 3 channels to 3 channels has 3 × 3 × 3 × 3 = 81. With several input and output channels, the filter becomes a small tensor of shape (height, width, input channels, output channels), and the paper writes the same idea in its Equation 26.

Where the Fourier transform comes from

Circulant matrices all commute with each other: apply two of them in either order and you get the same result, because shifts on a ring commute (the group is Abelian). Linear algebra then gives one useful fact. Matrices that commute can all be made simple, one number per direction, in a shared set of directions. The paper computes those directions for the shift: they are the waves of the discrete Fourier transform. In that basis every convolution is just a multiplication, one number per frequency. So the Fourier transform is not a trick. It is what the shift group dictates. Chapter 4 uses it to show a weakness.

The lesson of the chapter. Demand shift equivariance and linearity, and out comes convolution, with weight sharing and a built-in tiny parameter count. The same recipe will give graph layers and rotation layers when the symmetry changes.
Which statement about a linear layer on a ring of cells does the paper establish?

Chapter 4

Stability and Scale Separation

See why exact symmetry is too strict for the real world, and how pooling gives a softer kind of robustness

Film a busy street. Between two frames, one person steps left, a cyclist rolls right and a bus barely moves. No single shift turns frame one into frame two. Yet you would say both frames show the same street. The picture changed a little everywhere, in a different way at each place.

Chapters 2 and 3 handled exact symmetries: one move applied to the whole signal. Real data rarely moves that cleanly. The paper therefore asks for something softer, in Section 3.3.

Small deformations do not form a group

A deformation τ (tau) is a smooth warp of the domain, different at different points. You might hope to treat all small warps as symmetries. The paper explains why you cannot: chain enough small warps and you get a large one, one that can change what the picture means. The collection of small warps is not closed under composition, so it is not a group.

The fix is to measure how far a warp is from the true symmetry, and to let the output change by no more than that. Write c(τ) for this distance: zero for an exact symmetry and growing with the size of the warp.

‖f(ρ(τ)x) − f(x)‖
How much the output changes when the signal x is warped by τ.
C
A fixed constant that does not depend on the signal.
c(τ)
The size of the warp. The paper’s example for images is the Dirichlet energy, the summed squared steepness of τ, which measures how elastic the warp is.
‖x‖
The overall size of the signal, so a louder signal may change more.

A function that obeys this is called geometrically stable. It contains exact invariance as the special case c(τ) = 0. The same idea applies when the domain itself is deformed, such as a graph that gains an edge. For graphs the paper measures that with the graph edit distance, and for surfaces with the Gromov-Hausdorff distance.

Why the Fourier modulus is not enough

Chapter 3 showed that shifts only change the phase of each Fourier wave. So the Fourier modulus, the size of each wave with the phase thrown away, is exactly shift-invariant. It looks ideal. The paper shows the catch: under a near-shift, a slightly different warp, the modulus can change by an amount that does not shrink with how small the warp is. Fourier waves are global, so a small local nudge disturbs every one.

The alternative is a multi-scale view. Wavelets use building blocks that are local in space and in frequency at once, and they stay stable under small warps. Try both views below on a signal of seven narrow bumps.

Shift the bumps, or nudge each one

Top: the signal (blue) and the changed signal (purple). Bottom: how much each feature changes, as a share of its own size. Choose the kind of change, then drag its amount.

1.0

Toy, not a result from the paper: 64 cells with wrap-around, seven Gaussian bumps of width 1.5 cells, nudged by plus or minus the amount in a fixed pattern. The Fourier feature is the modulus of the first 32 coefficients. The pooled feature is the signal blurred with a Gaussian of width 7 cells (a low-pass filter), sampled every 8 cells. Changes are root-mean-square relative to the feature’s own size.

Read the shift mode first. The Fourier modulus changes by 0% at every amount, because a shift is its exact symmetry. The pooled feature moves a little, because sampling every 8 cells is not perfectly shift-proof. Now switch to nudging. At 1 cell the Fourier feature changes by about 25% and the pooled one by about 6%. A tiny local warp wrecks the global feature and barely touches the local one.

Scale separation

That result leads to the paper’s second prior, scale separation. A function f is locally stable if it splits as f ≈ fj ∘ Pj. Here Pj is a coarsening: blur a little, then keep fewer points, like zooming out on a map. The function fj then works on the coarse version. Details are combined near by first, and only their summaries travel far.

This gives the receptive field: the patch of input that one output value can see. A stack of local layers grows it slowly. Take a filter 3 cells wide. One layer sees 3 cells. Add a second layer and it sees 5, then 7, growing by 2 per layer. Halve the grid after every layer and each new layer reaches twice as far: the field becomes 3, 7, 15, 31. Four pooled layers see 31 cells where four plain ones see 9, with the same number of weights.

A feature is exactly invariant to shifts, yet a tiny local jitter of the input changes it a lot. According to the paper, what is missing?

Chapter 5

The Blueprint

Assemble a whole network from four building blocks and read off which symmetry each one keeps

You now hold three ideas: symmetry (Chapter 1), equivariant layers (Chapters 2 and 3) and stability through coarsening (Chapter 4). The paper fuses them into one recipe, in its Section 3.5. Think of four kinds of brick. Every architecture in the rest of the paper is a different way to stack the same four.

The four bricks

The first brick is a local equivariant layer B. It is linear, it moves with the symmetry, and each output looks only at a small neighbourhood. On a grid this is convolution. The second brick is a nonlinearity σ applied at every point on its own, such as ReLU, which sets negative numbers to zero. It is needed because without it, stacking layers gives only one big linear layer.

A pointwise nonlinearity keeps equivariance. Here is the one-line reason. σ looks at one point at a time and treats all points alike. Moving the points and then applying σ gives the same as applying σ and then moving them. So σ∘B is equivariant whenever B is.

The third brick is local pooling P, the coarsening of Chapter 4. It blurs and then keeps fewer points, so the domain shrinks and the receptive field grows. The fourth is a global invariant layer A, such as the mean or the maximum over all points. It throws away position and leaves one vector per signal.

f
The whole network. The small circle ∘ means “apply the right-hand part first”.
Bj
A local equivariant linear layer, with its own weights at each of the J levels.
σj
A pointwise nonlinearity after each layer.
Pj
A coarsening between levels. It makes the domain smaller.
A
The final invariant pooling. It makes the output independent of the symmetry.

The paper stresses that the bricks fix the properties, not the details. Each architecture picks its own domain, its own symmetry group and its own versions of B, P and A. The blocks must also match: the output space of one is the input space of the next.

The data flow, with shapes

Take an image classifier with three colour channels first. The input is (H, W, 3). A 3 by 3 convolution to 16 channels gives (H, W, 16). ReLU keeps the shape. Pooling gives (H/2, W/2, 16). Repeat. After J levels, global average pooling gives one vector of length C. A plain linear layer then maps it to class scores.

Training is ordinary: a loss, then backpropagation. One detail changes. Because every position shares the same filter weights, the gradient of a filter is the sum of its gradients from all positions.

For a graph with n nodes and d features: the input is a matrix X of shape (n, d) plus the connections A. A graph layer gives (n, d′). Pooling coarsens the graph. The final readout sums or averages the rows to give one vector of length d′ for the whole graph. The paper draws this in its Figure 8. The skeleton is identical.

Now run a small pipeline of this kind and shift its input. There are two levels, each pooling by 2, so the output can be exactly invariant only for shifts that are multiples of 4.

Push a shifted signal through the blueprint

Rows, top to bottom: the shifted input, level one after convolution and ReLU, after pooling, level two after pooling. Bars: the three final outputs, original (grey) against shifted (purple). Drag the shift and switch the pooling.

1

Toy, not a result from the paper: 32 cells with wrap-around ends. Level one has two fixed 3-tap filters, level two has three channels of random 3-tap filters (the same on every visit), ReLU after each, then pooling, then a mean over cells. Nothing is trained. The error is the largest output gap divided by the largest original output.

What the device shows

Shift by 4, 8 or 12 and the final outputs match to the last digit, with either pooling: the whole pipeline is invariant to shifts of that size. Shift by 1 and the story depends on the pooling. Keeping every second cell without blurring first moves the final outputs by about 37%. Averaging pairs first moves them by about 1%.

This is aliasing, the same fault that makes a thin striped shirt flicker on video. The paper’s remedy, in Section 5.1, is to apply a low-pass anti-aliasing filter before downsampling. It also explains why the claim is approximate invariance: after pooling by 2 the domain has only half the positions, so a one-cell shift has no exact meaning there.

The paper also notes a theoretical comfort. Shallow networks built from these bricks are universal approximators of functions with the chosen symmetry, much as ordinary shallow networks are for unstructured inputs. Building in the symmetry removes a huge set of wrong functions without removing a right one.

In the blueprint, which block turns a stack of equivariant feature maps into an answer that no longer depends on where things are?

Chapter 6

Graphs and Sets: The Permutation Symmetry

Build a layer for data that has no order, and meet the three flavours of graph network

A social network app wants to suggest friends. Each user is a node. A friendship is an edge between two nodes. Each user also has features: a list of numbers such as age and interests. Nobody ordered the users. If the database stores them as user 1, 2, 3 or as 3, 1, 2, the network is the same. A model must give the same answer either way. That demand is the symmetry of this chapter.

Sets first: no edges at all

Start with the simplest case, a set: n items with features and no edges. Stack the features as the rows of a matrix X of shape (n, d). Reordering the items means reordering the rows. The paper writes that as multiplying by a permutation matrix P, a grid of zeros and ones with exactly one 1 in each row and column. The group of all such reorderings is called Σn, and it has n! members.

An invariant function satisfies f(PX) = f(X). A simple recipe builds one: apply the same small function ψ to each row, add up the results, and apply a final function φ. Because a sum ignores order, the answer cannot depend on it. This is the Deep Sets architecture of Zaheer and colleagues.

f(X)
One output for the whole set, the same for every ordering of the rows.
ψ(xu)
The same small network applied to each item on its own.
∑u
Add over all items. A mean or a maximum would also ignore order.
φ
A final network that reads the sum.

An equivariant function F gives one output row per item and obeys F(PX) = PF(X). The simplest is again ψ applied row by row. The paper shows that the only linear equivariant maps on sets are mixes of two things: leave each row alone, and replace each row with the average of all rows.

Adding edges

Now add structure. The edges go into an adjacency matrix A of shape (n, n), with Auv = 1 when u and v are connected. Reordering the nodes now reorders both: X becomes PX and A becomes PAPT. A graph function must handle both together.

The blueprint says: keep it local. Let the neighbourhood Nu be the node u and the nodes one edge away. Build a local function φ(xu, XNu) that reads u and its neighbours, but gives the same result whatever order the neighbours come in. Apply this one φ at every node. The result, with rows in step with the input rows, is permutation equivariant by construction. The paper draws it in its Figure 10.

The paper adds a link to older theory. If φ is injective, meaning different neighbourhoods always give different outputs, one such step equals one step of the Weisfeiler-Lehman test. That is a classic colour-refinement check for whether two graphs could be the same graph.

Three flavours

Almost all graph layers in the literature fit three patterns. All of them add up the neighbours, which is why they ignore order. They differ in how the neighbours are weighted.

These nest: convolution is inside attention, and attention is inside message passing. Make attention a lookup table and you get convolution. Let the message ignore the receiver and use only a scalar weight and you get attention. The paper adds practical advice. Most real graphs are homophilous, meaning linked nodes tend to share a label, and there the cheap convolutional flavour is often best. Try all three on one node.

Update one node, then reorder the table

Pick a flavour and a node. Arrows into the node carry the weight each neighbour gets. Then press Reorder the rows: the table order changes, and the node’s new features should not.

Toy graph and features (the hero’s). Every node is also its own neighbour. Fixed, untrained weights: a 2 by 2 matrix W for the first two flavours, a 2 by 4 matrix for messages. Attention scores are dot products of the transformed features, passed through a softmax. Layers are computed on the row-ordered matrices X (6 by 2) and A (6 by 6), as a real implementation would.

Check the worked case by hand. Take node C with neighbours B and D. Its features are xB = (0.2, 0.8), xC = (0.5, 0.5), xD = (0.1, 0.2). Use the convolutional flavour with c = 1/3 and W as the identity. The first number is (0.2 + 0.5 + 0.1)/3 = 0.27. The second is (0.8 + 0.5 + 0.2)/3 = 0.50. So C’s new features are (0.27, 0.50), whichever row C sits in.

A grid is a graph too, with a fixed, ordered neighbourhood: left, right, up, down. There φ need not ignore order, and that extra freedom is exactly why a convolution can have a different weight for each direction while a graph layer cannot.

Why does summing over the neighbours of a node make a graph layer permutation equivariant?

Chapter 7

Attention Is a Graph Network

Read the transformer as the attentional graph layer of Chapter 6, run on a graph where every word is linked to every other

Take the sentence “the cat sat on the mat”. Which words should talk to which? “Sat” needs “cat”. “Mat” needs “on”. A grammar could list the links, but we do not want to write a grammar. We have a set of words and no edges. What should the graph be?

Three answers to “no edges given”

The paper's Section 5.4 walks through them. No edges: treat each item alone, with a shared function applied to each. That is Deep Sets, and it never lets words talk. Every edge: link all pairs, the complete graph. Now a convolutional layer fails, for a neat reason. Each node would add up the same total over all nodes, so every node would see an identical summary and the neighbours would add nothing.

The third answer is to learn the edge weights. Use the attentional flavour from Chapter 6 on the complete graph. Each pair gets a score from the two features, and a softmax turns each node’s scores into weights that add up to 1. That is self-attention, the core of the transformer. The weights form a soft adjacency matrix that the network infers while it trains. The paper's claim is exact: a transformer is an attentional graph network over a complete graph.

The mechanism, with shapes

Take n words with d features each: X of shape (n, d). Three learned matrices turn it into queries Q, keys K and values V, each of shape (n, dk). A query is what a word is looking for. A key is what a word offers. A value is what it hands over when chosen.

QKT
An (n, n) table of scores. Entry (u, v) says how well word u’s query matches word v’s key.
√dk
A scale that keeps the scores from growing with the key length.
softmax
Turns each row of scores into positive weights that add up to 1. Each row is a node’s weights over its neighbours.
V
The messages. Row u of the result is the weighted mix of all values.
H
The new features, shape (n, dk), one row per word.

A tiny check by hand. Suppose word u scores 2 against one word and 0 against another. The softmax weights are e2 / (e2 + e0) = 7.39 / 8.39 = 0.88 and 1 / 8.39 = 0.12. Word u takes 88% of its new features from the first word.

Order has to be added back

On a bare set this layer is permutation equivariant, as Chapter 6 promised. But a sentence is not a set. “Dog bites man” and “man bites dog” must differ. A transformer that ignores order cannot tell them apart. The cure is a positional encoding: extra numbers, built from the word’s position with sine waves of different frequencies, added to its features before the layer.

The paper makes a pretty remark. Those sine waves are the discrete Fourier waves of Chapter 3. They are also the eigenvectors of the graph Laplacian of a ring of nodes. So positional encodings quietly assume that the words sit on a grid. For a general graph, one can use the Laplacian eigenvectors of that graph instead, an idea the paper credits to Dwivedi and Bresson.

Masks change the graph too. A causal mask, as in GPT-style models, keeps only the edges from earlier words to later ones, a directed graph. A sliding window keeps only near neighbours, which looks like a grid again. Test all of this on five words.

Choose the graph, then shuffle the words

The table is the attention each word (row) pays to each word (column): the soft adjacency matrix. Choose the graph and the position codes, then press Shuffle the words and read whether the output rows just reordered.

Toy, not a result from the paper: five words with random 4-number embeddings, random 4 by 4 projection matrices for queries, keys and values (fixed, untrained), and position codes of four sine and cosine values at two frequencies. The test compares the layer run on shuffled words against the original output with its rows shuffled the same way.

Failure, measurement, fix

The symptom: a model gives the same output for two sentences with the same words in different orders. The measurement: shuffle the words and compare, as the device does. With the complete graph and no position codes, the gap is exactly 0.000. The fix: add position codes or use a mask that depends on position. Then the gap becomes positive, and the model can see order. Notice the pattern: the symmetry is not always something to keep. Sometimes you break it on purpose, and you choose how.

One cost deserves a note. The complete graph has n² edges, so every layer scores n² pairs. The paper does not dwell on cost, but it is why masks and local windows are popular for long inputs. For the language-model side of this story, see the transformer lesson and the graph transformer lecture.

According to the paper, what is self-attention in the language of graph networks?

Chapter 8

Groups, Geodesics and Gauges

Slide filters by rotations instead of shifts, then follow the idea onto curved surfaces where even “which way is up” is a choice

A pathologist looks at a stained slice of tissue under a microscope. There is no up. Turn the slide a quarter turn and the cells are still the same cells. A network that marks tumour cells should mark the turned image with a turned mask. An ordinary convolutional network does not promise that. It handles shifts, not turns, so it must learn each orientation from separate examples.

Group convolution

Recall what convolution does: it matches a filter against the signal at every shifted position and records how well each one fits. The shifts are the symmetry group. The paper's insight in Section 4.3 is to swap the group. To match at every position and orientation, slide the filter with the rotations as well.

(x ⋆ θ)(g)
One output number for each group element g: how well the signal fits the filter moved by g.
⟨x, ρ(g)θ⟩
An inner product, which multiplies matching cells and adds them up. ρ(g)θ is the filter after the move g.

Why is this equivariant? Moving the signal by h and then matching against the filter moved by g is the same as matching the original signal against the filter moved by h−1g. So the output is the old output, with its labels moved by h. That is the equivariance, in one line.

How to build it: transform, then convolve

The paper gives a practical recipe for discrete groups. First make copies of the filter, one per rotation. A 3 by 3 filter has four copies for the quarter turns. Then run an ordinary convolution with each copy. The result is a stack of orientation channels, one feature map per rotation, stored as an ordinary array of shape (H, W, 4 × filters). Turn the input a quarter turn and every map turns, and the maps also move one channel along the cycle. For 3D medical scans the paper shows the 24 rotations of the cube.

The same trick handles DNA. A strand read from one end is equivalent to the reversed, complemented strand read from the other end, so ACCCTGG matches CCAGGGT. That two-element group, with a 1D shift, gives filters with a built-in reverse-complement symmetry. Try the quarter turns below.

Turn the picture, watch the feature maps

Top row: feature maps for the original picture. Bottom row: maps for the turned picture. Choose a layer and a turn. For the group layer, each bottom map should be a turned copy of one top map.

Toy, not a result from the paper: a 7 by 7 picture of an asymmetric hook shape and one fixed 3 by 3 filter. The group layer uses the four quarter-turn copies of that filter (the group of quarter turns, the paper’s transform-and-convolve recipe). Zero padding at the edges. The error is the largest cell difference between the maps on the turned picture and the expected turned maps.

In the plain layer, a quarter turn of the picture gives a map that is not the turned old map: the worst cell is off by 2.0. In the group layer the error is 0.0 for every turn. The extra cost is four copies of the filter, which share one set of weights.

Two honest limits. The output of a group convolution lives on the group, not on the picture, so the next layer must act on that stack too. And for the sphere, the group of rotations SO(3) is a three-dimensional space, bigger than the two-dimensional sphere. The paper then computes with spherical harmonics, the Fourier waves of the sphere.

Geodesics: when there is no global symmetry

Most curved surfaces are not so tidy. A human body, a protein surface and a car body have no global rotation that slides them onto themselves. The paper treats such a surface as a manifold: a space that looks flat when you zoom in near any point, as the Earth does. The shortest path along the surface between two points is a geodesic. Its length defines a distance that does not need the surface to be placed in space at all.

That distance gives a new symmetry. An isometry is a deformation that keeps all geodesic distances: bending a sheet of paper without stretching it. A person moving an arm changes the surface but nearly preserves the distances along it. A network that respects isometries would treat all those poses alike. The paper builds such tools from the Laplacian, an operator that measures how a value differs from the average of its surroundings. Its eigenvectors play the role that sine waves play on a ring, and they depend only on intrinsic distances.

Gauges: the choice of “which way is up”

To run a convolution on a mesh, you need a way to lay a filter on the surface. At each point you shoot geodesics in all directions to build a small patch in polar coordinates, a distance r and an angle θ. But angle from what? There is no natural zero direction on a curved surface, and the choice may differ at every point. That choice of a frame at each point is a gauge. Changing it applies a matrix at each point to the coordinates of the features.

A safe option is the isotropic filter, which depends on r alone and ignores direction. It cannot be fooled by the gauge, but it also cannot see direction. The paper's richer answer asks the layer to be gauge equivariant: when the frames change, the features change by the matching rule, so the result is the same geometric object. Gauges generalise from tangent vectors to any feature at a point, using a structure called a bundle: at every point of the surface, a small space of features hangs off it.

You build a layer by making four quarter-turn copies of a filter and convolving the image with each. What do you get when you turn the input a quarter turn?

Chapter 9

The Whole Paper on One Page

Review the blueprint across all five Gs, with the numbers, the code that tests it, the limits and where to go next

You can now rebuild the paper’s argument from memory. Real data is not a generic point in a huge space. It is a signal on a domain, and the domain has symmetries. Demand that each layer respects them and the layer is nearly fixed: shifts give convolution, reorderings give sums over neighbours, rotations give turned filter copies. Add stability and coarsening, and you have a network that needs far fewer examples. The same four bricks carry the whole zoo.

The blueprint across the five Gs

Pick an architecture below to see which domain it lives on, which symmetry it respects and what plays each brick of the blueprint.

Find the bricks in each architecture

Choose an architecture. The four bricks of Chapter 5 light up where the architecture uses them. The text lists what fills each.

A summary of Sections 4 and 5 of the paper in our words, not a measurement. The pooling entry for the plain transformer is left as “none” because the paper’s transformer discussion does not describe a coarsening step.

The numbers and terms that matter

WhatNumberWhy it matters
Samples for a smooth functionN of order ε−dThe curse: exponential in dimension (Chapter 0)
Symmetries of a triangle6 (3 turns, 3 flips)A small non-commutative group (Chapter 1)
Reorderings of n itemsn! (720 for 6)The permutation group of sets and graphs
Folkman graph automorphisms3,840A highly symmetric graph (paper, Section 3.3)
Weights of a layer on n cellsn² free, n circulant, 3 localEquivariance and locality cut the count (Chapter 3)
Linear equivariant maps on sets2 generatorsKeep each row, or average all rows (Chapter 6)
Linear equivariant maps on graphs15 generators, for any nBell number B4, from Maron and colleagues; the blueprint picks the local ones
Receptive field, 3-wide filters9 plain, 31 pooled after 4 layersScale separation widens the view (Chapter 4)
Orientation channels4 quarter turns; 24 cube rotationsGroup convolution stacks one map per move (Chapter 8)
GNN containmentconvolution ⊂ attention ⊂ message passingMore general costs more memory (Chapter 6)

What the paper’s figures show

This paper has no benchmark tables and no training runs. It is a unifying survey, a draft of a book, and its figures are diagrams. Figure 2 shows bumps in the quadrants of a space and why unseen quadrants leave a constant error. Figure 3 shows that a blurred image keeps its meaning but loses information, so “low-dimensional projection” is a bad model for photos. Figure 6 draws the symmetry group as a circle inside all possible bijections, with a ring of near-symmetries around it.

Figure 7 shows a classifier on a coarse grid standing in for one on the fine grid. Figure 8 is the blueprint on a graph. Figure 9 names the five Gs. Figure 10 shows one function applied to one neighbourhood. Figure 16 shows a 3 by 3 filter rotated by all 24 cube rotations. Figure 17 shows the three flavours of graph layer.

The paper covers more than this lesson. It treats gated recurrent networks for sequences, where the LSTM keeps a memory cell and learns input and forget gates. It ends with a chapter on problems and applications and a historical perspective.

It states its scope plainly. It does not survey generative models or reinforcement learning. It studies several architectures in depth rather than all of them.

Limits, in the paper’s own words and ours

The recipe as a checklist

  1. Name the domain Ω and the channels of the signal.
  2. Name the symmetry group G of the task: what may change without changing the answer?
  3. Choose a local, G-equivariant linear layer B.
  4. Follow it with a pointwise nonlinearity σ.
  5. Coarsen with P, blurring first, so the receptive field grows.
  6. End with an invariant layer A for one answer per input, or stay equivariant for an answer per point.
  7. Test it: compare f(ρ(g)x) with ρ(g)f(x) on random inputs, and again under small deformations.

The core, as code

Four small functions and the test the whole paper asks for. This is a runnable sketch; it checks all three equivariances on random data.

pythonimport numpy as np
from scipy.signal import correlate2d

def circulant_conv(x, theta):
    """x: (n,)  theta: (3,) = (left, self, right).  Shift-equivariant."""
    return theta[0] * np.roll(x, 1) + theta[1] * x + theta[2] * np.roll(x, -1)

def deep_sets(X, psi, phi):
    """X: (n, d).  Permutation-invariant: sum the rows after a shared psi."""
    return phi(psi(X).sum(axis=0))

def gnn_layer(X, A, W, kind="conv"):
    """X: (n, d)  A: (n, n) 0/1  W: (d, d2).  Returns (n, d2)."""
    Ah = A + np.eye(len(A))                       # each node is its own neighbour
    T = X @ W                                     # (n, d2)
    if kind == "conv":                            # fixed c_uv from the graph
        C = Ah / Ah.sum(axis=1, keepdims=True)
    else:                                         # attention: a(x_u, x_v)
        S = np.where(Ah > 0, T @ T.T, -np.inf)
        S = np.exp(S - S.max(axis=1, keepdims=True))
        C = S / S.sum(axis=1, keepdims=True)
    return np.maximum(C @ T, 0)                   # sum over neighbours, then ReLU

def group_conv(img, filt):
    """Transform + convolve: four turned copies of the filter -> (4, H, W)."""
    return np.stack([correlate2d(img, np.rot90(filt, r), mode="same") for r in range(4)])

# the test the whole paper asks for: f(rho(g) x) == rho(g) f(x)
rng = np.random.default_rng(0)
x, th = rng.normal(size=16), np.array([.3, .4, .3])
assert np.allclose(circulant_conv(np.roll(x, 5), th), np.roll(circulant_conv(x, th), 5))

n, d = 6, 2
X, W = rng.normal(size=(n, d)), rng.normal(size=(d, 4))
A = np.triu((rng.random((n, n)) < .4).astype(float), 1); A = A + A.T
P = np.eye(n)[rng.permutation(n)]
for kind in ("conv", "att"):
    assert np.allclose(gnn_layer(P @ X, P @ A @ P.T, W, kind), P @ gnn_layer(X, A, W, kind))

img, f = rng.normal(size=(7, 7)), rng.normal(size=(3, 3))
o, o_rot = group_conv(img, f), group_conv(np.rot90(img), f)
assert np.allclose(o_rot, np.stack([np.rot90(o[(r - 1) % 4]) for r in range(4)]))
print("all three equivariance tests pass")

Where to go next

The takeaway. Do not hope a network will find the symmetry of your data. State it, build each layer to respect it, coarsen for stability, and test with a shift, a reordering or a turn. One recipe, many architectures.

Credit. This lesson re-teaches “Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges” by Michael M. Bronstein, Joan Bruna, Taco Cohen and Petar Veličković (arXiv 2104.13478, 2021, read it here). Every toy example is ours and is labelled as such.

You must design a network for point clouds of atoms in a molecule, where the property to predict does not change if the molecule is spun. Following the blueprint, what do you do first?

Now press Teach and explain, from memory, how a convolution follows from shift symmetry and how a graph layer follows from reordering. Then go back to the graph at the top, reorder the nodes on each network, and say which brick of the blueprint makes the symmetric one hold its answer.

Geometric Deep Learning: Grids, Groups, Graphs, Geodesics and Gauges
Read the paper · The lecture this paper belongs to · Back to Gleams