Research map / Learning theory and algorithms / Kernels and regression theory
On Universality Classes of Equivariant Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that separation power does not fully determine approximation power for shallow invariant/equivariant networks by characterizing their universality classes via differential operators annihilating ridge superpositions, yielding failure examples (CNN width-1, PointNet) and positive results for normal-subgroup hidden representations.
Problem
Whether equivariant neural networks with identical separation power (same WL-type or orbit-level distinguishability) also have identical approximation power, i.e., whether separation-constrained universality holds for shallow equivariant architectures such as PointNets and width-1 CNNs.
Approach
Reformulates shallow invariant networks as symmetric superpositions of generalized ridge functions, so universality classes are characterized by constant-coefficient differential operators that annihilate the target; this gives sufficient conditions for failure beyond separation and positive results when hidden representations come from normal subgroups.
Key results
- Shallow CNNs with filter width 1 cannot approximate (x_1+...+x_n)^n, since the differential-operator test gives partial derivative product n! != 0, so U(C^1, I) is strictly contained in U(R^n,R^n,R) for n>2.
- Shallow PointNets can approximate (x_1+...+x_n)^n, yielding the strict inclusion U(C^1,I) subsetneq U(R^n,R^n,R), while shallow PointNets fail to approximate x_1...x_n for n>3 (and n=3 via a separate argument), so U(R^n,R^n,R) is strictly contained in U(R^n,R^{S_n},R).
- Theorem: if H is a normal subgroup of G, then U(V, R^{G/H}, Z) is separation-constrained universal; for S_n the only nontrivial normal subgroup is A_n, which yields too-small hidden representations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use width-1 circular convolutional layers (C^1) with invariant output instead of unrestricted PointNet layers | Shallow invariant networks under permutation symmetry · S_n-invariant continuous functions, n > 2 | separation-constrained universality | Hurt |
| Use unrestricted PointNet layers instead of width-1 circular convolutional layers | Shallow invariant networks under permutation symmetry · Approximation of (x_1 + ... + x_n)^n | function approximation | Helped |
| Use shallow PointNet layers rather than regular hidden representations | Shallow invariant networks under S_n · S_n-invariant continuous functions, n > 2 | separation-constrained universality | Hurt |
| Use hidden representations arising from cosets of a normal subgroup | Shallow equivariant networks · Continuous equivariant functions for a finite group with normal subgroup H | separation-constrained universality | Helped |
Surprising findings
- Models with identical separation power (CNNs of width 1, PointNets, and regular-representation networks all separate orbits in the invariant case) nonetheless differ in universality classes, so separation is not a complete proxy for approximation.
- Shallow PointNets fail to be universal for permutation symmetry, whereas depth-three PointNets are known to be universal, so depth matters qualitatively in equivariant settings.
Limitations
- Analysis restricted to shallow networks (depth two or less); deeper architectures such as IGNs are not covered.
- The characterization theorem is hard to apply in general because computing the full set of annihilating polynomials is combinatorially complex.
- Positive results depend on normal subgroups of suitable size, which do not exist for permutation groups such as S_n.
Experimental setup
Baselines: PointNet circular CNN with filter width 1
Builds on: Universal approximation theorem for shallow networks (Leshno et al.) Equivariant universality for regular representations (Yarotsky / Keriven-Peyré s PointNet Weisfeiler-Leman hierarchy
Closest papers by meaning
- On the hardness of learning under symmetries (ICLR 2024 · similarity 0.91)
- A Characterization Theorem for Equivariant Networks with Point-wise Activations (ICLR 2024 · similarity 0.91)
- Separation Power of Equivariant Neural Networks (ICLR 2025 · similarity 0.91)
- A Tale of Two Symmetries: Exploring the Loss Landscape of Equivariant Models (NeurIPS 2025 · similarity 0.91)
- Improving Equivariant Networks with Probabilistic Symmetry Breaking (ICLR 2025 · similarity 0.90)
- Learning (Approximately) Equivariant Networks via Constrained Optimization (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.