When we design neural networks to respect the laws of physics or geometry, we bake in symmetry constraints. We use Convolutional Neural Networks (CNNs) for translation invariance, Deep Sets for permutation invariance, and specialized geometric layers for rotational invariance.
By forcing a network to obey a symmetry group $G$, we restrict its search space. This introduces a fundamental theoretical tension: Do these symmetry constraints inadvertently create functional blind spots? Or is the network still capable of approximating any continuous function that shares those same symmetries? This property is known as equivariant universal approximation.
Understanding why and how equivariant networks achieve universality requires moving past standard approximation theorems and looking at how symmetries interact with polynomials, tensor products, and layer geometry.
The Core Obstacle: Why Standard Proofs Fail
Standard universal approximation proofs (like the classic Cybenko or Hornik theorems for MLPs) rely on the Stone-Weierstrass theorem. This theorem states that an algebra of functions can approximate any continuous function if it can "separate points"—meaning for any two distinct inputs $x \neq y$, there exists a function $f$ in the algebra such that $f(x) \neq f(y)$.
When we restrict our function space to be invariant under a group $G$, separating points becomes impossible if those points belong to the same group orbit. If $y = gx$ for some group element $g \in G$, then by definition, any invariant function must yield $f(x) = f(gx) = f(y)$.
Because standard point-separation fails, proving that symmetric networks are universal requires a different mathematical strategy: bridging continuous symmetric functions to symmetric polynomials, and leveraging classical invariant theory.
The Polynomial Bridge and Invariant Theory
To prove that an invariant network architecture is universal, researchers typically show that the network can represent a dense set of invariant polynomials. As established by Haggai Maron et al., if a network architecture can express arbitrary invariant polynomials, it inherits the ability to approximate any continuous invariant function over compact domains. This is because polynomial averaging over a compact group preserves both density and symmetry.
But how do we design a network to express these polynomials without manually hardcoding every possible symmetric interaction? The answer often lies in the First Fundamental Theorem of Invariant Theory.
For physical symmetries like rotations (the Orthogonal group $O(n)$) or relativistic boosts (the Lorentz group), the theorem provides a massive simplification. As Soledad Villar et al. demonstrated, any polynomial equivariant function of a set of vectors can be expressed as a linear combination of those input vectors, where the scalar coefficients are functions purely of their inner products (dot products).
$$\mathbf{f}(\mathbf{v}_1, \dots, \mathbf{v}_k) = \sum_{i=1}^k \phi_i(\{\mathbf{v}_j \cdot \mathbf{v}_l\}) \mathbf{v}_i$$
This explains why simple scalar-based architectures work: instead of tracking complex, high-dimensional irreducible representations of a continuous group, a network can achieve universal expressivity simply by computing scalar dot products and using them to scale the input vectors.
Permutation Symmetries and Set Networks
For discrete, unordered data like point clouds or particle collections, the underlying symmetry is the symmetric group $S_n$ (permutations). In their foundational work on Deep Sets, Manzil Zaheer and Alex Smola proved that any permutation-invariant function can be decomposed into a per-element transformation followed by a sum-pooling operation.
When moving from invariant outputs (a single score for a set) to equivariant outputs (where the output must permute in exact tandem with the input), the architecture requires global information sharing. Nimrod Segol and Yaron Lipman formalized the expressivity of these architectures by characterizing permutation-equivariant maps using power-sum multi-symmetric polynomials.
They proved that standard sum-pooling architectures are indeed universal equivariant approximators. The intuition is that sum-pooling acts as a channel for global context; by passing sums of non-linear transformations of the elements back to each individual element, the network can uniquely identify the collective state of the set, satisfying the polynomial spanning conditions required for universality.
The Tensor Order Bottleneck
While permutation universality can be achieved with simple sum-pooling, continuous groups like $SO(3)$ (3D rotations) introduce a representation bottleneck.
To map out the full space of equivariant functions, early geometric deep learning models relied on high-order tensor products (e.g., tensor fields and spherical harmonics). Haggai Maron et al. showed that symmetry-constrained networks require internal layers utilizing tensors of a sufficiently high order to guarantee universality. Without these high-order interactions, the network cannot compute certain geometric invariants, such as the joint orientation of multiple vectors.
Because high-order tensors are computationally expensive, researchers have sought ways to achieve universality using lower-order representations. Nadav Dym and Haggai Maron established a framework showing that universality can be guaranteed if an architecture satisfies two conditions:
- D-spanning: The network can represent a specific set of equivariant polynomials.
- Linear Universality: The network can express all possible linear equivariant mappings between its internal representations.
Building on this framework, Ben Finkelshtein et al. showed that by parameterizing the network's expressive power via a maximal representation order, one can bypass complex group representation theory entirely. Instead, universal approximation of rotation-equivariant functions can be achieved using basic tensor products and contractions, allowing lower-order models to compute complex geometric descriptors (like the eigenvalues of a covariance matrix) that were previously thought to require higher-order tensors.
Universality via Regular Group Actions
For finite groups, a clean architectural blueprint for achieving universality comes from the geometric arrangement of the hidden layers.
Siamak Ravanbakhsh proved that a multilayer perceptron constrained to be equivariant to a finite group is a universal approximator if its hidden layers employ a regular group action.
[Input Layer] ──> [Hidden Layer (Regular Action)] ──> [Output Layer]
│
└─► Each group element permutes
neurons to unique positions
(No information loss)
In a regular action, the size of the hidden layer is a multiple of the group's order, and each group element permutes the neurons to entirely unique positions. Why does this guarantee universality? In representation theory, the regular representation is guaranteed to contain every irreducible representation of the group. By structuring the hidden layer this way, the network preserves all symmetry channels simultaneously, ensuring that no valid equivariant transformation is blocked by the network's structural constraints.
Key Foundational Work
Mixed batches and symmetric discriminators for GAN training (2018) — contributed 2 concept elements to this direction.