On the Universality of Invariant Networks

• The central question is whether a G-invariant network can approximate any continuous G-invariant function.Source: §1 · p. 1
• The analysis covers all finite permutation groups G ≤ S_n acting by permuting coordinates, a setting encompassing several invariant-network applications.Source: §1 · pp. 1–2
• Universality is known for point-cloud, set, and finite-translation networks, but remains unknown for tabular and multi-set networks in the cited prior work.Source: §1 · p. 1
• The paper constructively proves that arbitrary continuous G-invariant functions can be approximated using equivariant layers between tensors of order k ≤ d, with d depending on G.Source: §1 · p. 2
• For the alternating group A_n, tensor order at most d = (n − 2)/2 cannot approximate arbitrary G-invariant functions.Source: §1 · p. 2
• For first-order networks, the paper asks which permutation groups permit universality and proves a necessary condition while identifying families that fail it.Source: §1 · p. 2

Setup

• The framework considers arbitrary subgroups G ≤ S_n acting on R^n by permuting coordinates, with invariant and equivariant layers respecting this action.Tensor actions apply the same permutation across each tensor dimension, while invariant functions satisfy f(g · x) = f(x).Source: §2 · p. 2

Network architecture

• A G-invariant network composes linear G-equivariant layers, possibly on high-order tensors, then a linear G-invariant layer and an MLP.Entrywise activation functions preserve equivariance, so the complete network is G-invariant.Source: Figure 1 · p. 2, §2 · p. 2

Universality with higher-order tensors

• For every continuous G-invariant f : R^n → R on a compact set, a constructive G-invariant network approximates f using hidden tensors of order d(G).The required order depends on the permutation group and can be as high as n(n−1)/2 in the worst case; even d = 2 may be computationally challenging.Source: §2 · p. 2

Lower bounds

• For the alternating group G = A_n, universality requires tensors of order at least n−2; orders at most (n−2)/2 cannot approximate arbitrary invariant functions.Thus lower-order tensor restrictions can prevent universal approximation for specific permutation groups.Source: §2 · p. 3

First-order universality

• For first-order G-invariant networks, the paper proves a necessary condition involving every strict supergroup G < H ≤ S_n and separation of the double-index space [n]^2.The condition compares the numbers of G- and H-equivalence classes of index pairs, requiring supergroups to have strictly better separation.Source: §2 · p. 3

Polynomial approximation

• G-invariant polynomials can be decomposed into homogeneous components and approximated on compact sets by G-invariant networks.Stone–Weierstrass supplies polynomial approximation, while Proposition 1 establishes network approximation of each invariant polynomial.Source: §3 · p. 3, §3.1 · p. 3

Invariant tensors

• Invariant coefficient tensors satisfy a fixed-point equation under G, so their entries are constant on the corresponding equivalence classes.This characterizes the symmetry constraints needed for invariant polynomial representations and layers.Source: §3.1 · p. 4

Invariant polynomial bases

• The polynomials indexed by k-classes form a basis for homogeneous G-invariant polynomials of degree k.A k-class identifies index tuples under both the group action and permutation of monomial factors.Source: §3.1 · p. 4

Network construction

• Each basis polynomial is approximated by mapping inputs into an order-k tensor, applying an MLP to feature channels, and summing the resulting tensor.The resulting network is Fτ = s ◦ M^k ◦ Lτ and approximates pτ on compact sets.Source: §3.1 · pp. 4–5

Bounded-order construction

• The maximal tensor order can be bounded using a generating set of invariant polynomials, making the required order depend only on G rather than the target polynomial degree.For G ≤ S_n, invariant polynomials have a generating set with degree bounded by n(n−1), and the constructed network inherits a corresponding group-dependent bound.Source: §3.2 · pp. 5–6

Equivariant layer spaces

• For k + l ≤ n−2, the spaces of A_n-equivariant and S_n-equivariant linear layers are identical.Both groups induce the same equality-pattern equivalence relation on index tuples in this range.Source: §4 · p. 7

Separating function

• The Vandermonde polynomial is A_n-invariant but not S_n-invariant, providing a continuous target that such low-order networks cannot approximate arbitrarily well.The contradiction follows by evaluating the polynomial at a point and its transposed version, where the network must agree but the polynomial changes sign.Source: §4 · p. 7

First-order universality

• First-order G-invariant networks restrict the maximal tensor order to 1, making them practically attractive when higher-order tensors are computationally prohibitive.The section frames first-order universality as an important applications-oriented question.Source: §5 · p. 7

Necessary condition

• The paper derives a necessary condition for first-order universality by constructing a continuous function that is G-invariant but not H-invariant for every strict super-group G < H ≤ S_n.The construction uses distinct-coordinate points whose H-orbit strictly contains their G-orbit.Source: §5 · p. 7
• If the linear equivariant and invariant layer spaces coincide for G and a strict super-group H, every first-order G-invariant network is also H-invariant.Such networks therefore cannot approximate a continuous function that distinguishes the G- and H-orbits.Source: §5 · pp. 7–8

Non-universal families

• Strict 2-transitive subgroups G < S_n provide infinite families that are not first-order universal, because their layers are also S_n-invariant/equivariant.Examples include projective linear and affine subgroup families over finite fields.Source: §5 · p. 8

Connections

• The necessary condition connects first-order universality to 2-closed groups and to the existence of uniquely G-equivariant linear functions.The paper notes that 2-closedness is exactly the setting in which such a uniquely equivariant function can be found.Source: §5 · p. 8

Main conclusions

• G-invariant networks are universal using tensors of order at most n(n−1)/2, although this makes the architecture impractical.The conclusion contrasts the universality construction with its computational cost.Source: §6 · p. 8
• Some permutation groups require tensor order at least (n−2)/2 to achieve universality.This lower bound shows that higher-order tensors can be unavoidable.Source: §6 · p. 8

First-order networks

• 2-closedness of G is a necessary condition for first-order G-invariant universality, and several infinite permutation-group families do not satisfy it.Thus the conclusion gives a group-theoretic obstruction to first-order universality.Source: §6 · p. 8

Open questions

• A complete classification of 2-closed groups, efficient higher-order layers for non-2-closed groups, and new possibly nonlinear invariant models remain open directions.The paper describes these as future-work challenges.Source: §6 · p. 8

Network construction

• A sum of G-invariant networks can be realized as a single unified G-invariant network.The construction combines component networks within one architecture.Source: A. Proofs · p. 10
• Each component network is lifted to the maximal tensor dimension before the networks are combined.The lifted network has a common tensor-order structure suitable for concatenation.Source: A. Proofs · p. 10

Equivariance preservation

• Equivariant operators U^b and D^a preserve equivariance when inserted around an equivariant layer L.They also satisfy D^a ◦ σ ◦ U^a = σ, preserving the pointwise activation behavior.Source: A. Proofs · p. 10

Network construction

• Networks with the same tensor order are combined by concatenating their feature channels.The concatenated map joins input channel counts and output channel counts across the component networks.Source: A. Proofs · p. 10

Equivariant layers

• The linear part of an affine equivariant operator is represented by a tensor whose entries obey the fixed-point equations under the group action.The constant part is handled similarly.Source: A. Proofs · p. 10