Source-linked AI summary
On the Universality of Invariant Networks
Haggai Maron, Ethan Fetaya, Nimrod Segol, Yaron Lipman
TL;DR
The paper studies whether networks whose linear layers respect a finite permutation-group symmetry can approximate arbitrary continuous invariant functions. It develops constructive higher-order tensor results, proves that some groups require high tensor order, and derives a necessary condition for universality using only first-order tensors.
Problem
The paper addresses whether a G-invariant network can approximate any continuous G-invariant function for finite permutation groups G ≤ S_n.
Method
The paper uses constructive equivariant tensor-layer networks and analyzes tensor-order lower bounds and first-order universality through permutation-group structure.
Results
G-invariant networks are universal with sufficiently high-order tensors, some groups require tensor order at least (n − 2)/2, and 2-closedness is necessary for first-order universality.
Takeaways & Limitations
Universality may require higher-order tensors, while first-order universality is restricted to groups satisfying the paper’s necessary condition.
Takeaways & Limitations
Higher-order tensor constructions can be computationally challenging or impractical, and the analysis is scoped to finite permutation groups.
Abstract
from arXiv · showhide
Constraining linear layers in neural networks to respect symmetry transformations from a group $G$ is a common design principle for invariant networks that has found many applications in machine learning. In this paper, we consider a fundamental question that has received little attention to date: Can these networks approximate any (continuous) invariant function? We tackle the rather general case where $G\leq S_n$ (an arbitrary subgroup of the symmetric group) that acts on $\mathbb{R}^n$ by permuting coordinates. This setting includes several recent popular invariant networks. We present two main results: First, $G$-invariant networks are universal if high-order tensors are allowed. Second, there are groups $G$ for which higher-order tensors are unavoidable for obtaining universality. $G$-invariant networks consisting of only first-order tensors are of special interest due to their practical value. We conclude the paper by proving a necessary condition for the universality of $G$-invariant networks that incorporate only first-order tensors.
1. Introduction
The paper asks whether symmetry-respecting neural networks can approximate arbitrary continuous invariant functions, studying arbitrary finite permutation groups and applications including sets, tabular data, graphs, and related symmetries. It proves universality with bounded higher-order tensors, establishes groups requiring substantial tensor order, and derives a necessary condition for first-order universality.
- The central question is whether a G-invariant network can approximate any continuous G-invariant function.
- The analysis covers all finite permutation groups G ≤ S_n acting by permuting coordinates, a setting encompassing several invariant-network applications.
- 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.
- 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.
- For the alternating group A_n, tensor order at most d = (n − 2)/2 cannot approximate arbitrary G-invariant functions.
- For first-order networks, the paper asks which permutation groups permit universality and proves a necessary condition while identifying families that fail it.
2. Preliminaries and main results
The paper studies universality of networks invariant to arbitrary permutation subgroups G ≤ S_n and establishes results on tensor order needed for approximation. It proves universality with sufficiently high-order tensors, lower bounds for alternating groups, and a necessary condition for first-order universality.
- 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).
- 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.
- 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.
- 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.
- 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.
3. G-invariant networks universality
The paper proves universality by approximating invariant polynomials with G-invariant networks, then bounding the tensor order independently of polynomial degree. The construction uses invariant polynomial bases and multiplication-approximating MLPs.
- 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.
- 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.
- 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.
- 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.
- 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.
4. A lower bound on equivariant layer order
The paper proves that low-order networks for the alternating group cannot be universal. When k + l ≤ n−2, A_n and S_n have identical equivariant-layer spaces, forcing sufficiently low-order A_n-invariant networks to be S_n-invariant.
- 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.
- 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.
5. Universality of first order networks
This section studies when first-order G-invariant networks are universal for finite permutation groups, deriving a necessary group-theoretic condition and showing that some groups fail it.
- 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.
- 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.
- Necessary condition: 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.
- 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.
- 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.
6. Conclusion
The conclusion establishes universality with sufficiently high-order tensors, proves that some groups require tensor order at least (n−2)/2, and identifies 2-closedness as necessary for first-order universality. It presents the work as an initial step, with group classification and efficient higher-order architectures left open.
- 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.
- Main conclusions: 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.
- 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.
- 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.
A. Proofs
The proofs construct unified G-invariant networks by lifting component networks to a common maximal tensor order and concatenating their features while preserving equivariance.
- 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.
- Network construction: 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.
- 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.
- 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.
- 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.