On Universality Classes of Equivariant Networks
Authors: Marco Pacini
Gabriele Santin
Bruno Lepri
Shubhendu Trivedi
Venue: NeurIPS 2025 spotlight ()
Keywords: Geometric Deep Learning
Theory for Equivariant Neural Networks
Expressiveness
Approximation Theory
Primary area: deep_learning
TL;DR: Equivariant neural networks can fail to approximate target functions even when they achieve maximal separation power.

Abstract: Equivariant neural networks provide a principled framework for incorporating symmetry into learning architectures and have been extensively analyzed through the lens of their *separation power*, that is, the ability to distinguish inputs modulo symmetry. This notion plays a central role in settings such as graph learning, where it is often formalized via the Weisfeilern&ndash;Leman hierarchy. In contrast, the *universality* of equivariant models&mdash;their capacity to approximate target functions&mdash;remains comparatively underexplored. 
In this work, we investigate the approximation power of equivariant neural networks beyond separation constraints.
We show that separation power does not fully capture expressivity: models with identical separation power may differ in their approximation ability.
To demonstrate this, we characterize the universality classes of shallow invariant networks, providing a general framework for understanding which functions these architectures can approximate. Since equivariant models reduce to invariant ones under projection, this analysis yields sufficient conditions under which shallow equivariant networks fail to be universal.
Conversely, we identify settings where shallow models do achieve separation-constrained universality.
These positive results, however, depend critically on structural properties of the symmetry group, such as the existence of adequate normal subgroups, which may not hold in important cases like permutation symmetry.

On Universality Classes of Equivariant Networks
Marco Pacini"
Gabriele Santin
Bruno Lepri
Shubhendu Trivedi
Abstract
Equivariant neural networks provide principled framework for incorporating symmetry into learning architectures and have been extensively analyzed through the lens of their separation power, that is, the ability to distinguish inputs modulo symmetry. This notion plays central role in settings such as graph learning, where it is often formalized via the Peisfeiler-Lemas hierarchy. In contrast, the universal- ity of equivariant models their capacity approximate target functions remains comparatively underexplored. In this work, we investigate the approximation power equivariant neural networks beyond separation constraints. We show that separation power does not fully capture expressivity: models with identical separation power may differ in their approximation ability. To demonstrate this, characterize the universality classes of shallow invariant networks, providing a general framework for understanding which functions these architectures can approximate. Since equivariant models reduce invariant ones under projec- tion, this analysis yields sufficient conditions under which shallow equivariant networks fail to be universal. Conversely, we identify settings where shallow models do achieve separation--constraied universality. These positive results, how- ever, depend critically structural properties of the symmetry group, such the existence of adequate normal subgroups, which may not hold in important cases like permutation symmetry.
1 Introduction
Equivariant neural networks offer a principled framework to incorporate symmetry into learning architectures, attracting sustained attention for both their empirical successes and theoretical rich- ness 115 While their separation power-the the capacity to distinguish inputs up to symmetry-han been extensively studied, comparatively less is understood about their approximation capabilities.
In classical approximation theory, expressivity often characterized via thi capacity of a model class to approximate any target function within given function space to arbitrary precision 6 (7) In the equivariant setting, however, this notion must refined. This is because such models treat symmetric inputs as indistinguishabl; they can only approximate functions compatible with the underlying symmetry, subject additionally to spurious constraints arising from the imperfect interactions between equivariance and linear inductive biases on neural network layers. In this context, universality becomes inherently plative-defines with respect to particular separation relation that circumscribes the model's 's ability to distinguish inputs.
Graph learning has served primary testbed for studying invariant and equivariant architectures, where models are typically required to respect node permutation symmetries [4] 8 9. Within this setting, separation power most commonly assessed using the Weisfeiler-Leman (WL) test (TO] or homomorphism counting techniques
A whole range of architectures inclluding Graph
Uniiersity of Trento; Fondazione Bruno Kessler. mpacini@fbk.cd eu "Ca" Foscari University of Venice. gabriele wwwtinuunive......m. $ Fondazione Bruno Kessler, lepridfbk.em
shubhendu@csail. wwt.aail.......mmmmmmmmmmmm....m edu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Neural Networks (GNNs) [12414] Invariant Graph Networks (IGNs) 15 and subgraph based models [66 9 have been analyzed through this lens. More recently, investigations analyzing separation power have been extended beyond graph-structure data to broader classes of equivariant models [7 18. While much of the literature in geometric deep learning has centered on separation as the primary metric of expressivity, recent work [0] has called for more comprehensive view that includes approximation capabilities more generally. The role of equivariant layers in determining approximation power remains underexplored. Typically, these are composed to increase the model's separation capacity, while a universal component-suee as a multilayer perceptron with adjustable width-is appended to approximate functions within the separation-conse constrained class. As result, universality is achieved only relative to the distinctions introduced by the equivariant backbone. However, there is no general theory describing how equivariant layers themselves contribute to approximation.
To address this gap, we examine the approximation capabilities of equivariant neural networks beyond what captured by separation constraints alone. For this purpose, it suffices to focus on invariant architectures, as the core phenomena extend to the equivariant setting. Indeed, projecting the output of an equivariant model onto the trivial representation yields an invariant network. Accordingly, our analysis of invariant networks provides insight into the approximation limits of a broad class of equivariant architectures. We begin by showing that invariant neural networks can be expressed as function that vanishes certain differential operators (Section 5.1). This formulation allows to derive sufficient conditions under which a shallow invariant network fails to be universal within the constrained continuous functions (Section 5.2).
class of separation separation-coonstriined
Our theory and analysis leads to three key insights. First, remarkably, we identify network families that possess identical separation power yet differ in their approximation capabllitie- demonstrating that separation alone does not fully characterize expressivity. In particular, we show that shallow networks composed of commonly used equivariant layers-such as PointNets and CNNs with filter width 1-fail to be universal, despite matching the separation power of permutation-invaritc continuous functions (Section T.. Second, this implies that the only two architectural choices that impact approximation power are depth and the type of hidden representations, the latter being strongly influenced by the structure of the symmetry group. Third, we show that a generalization of the results by [5] produces a broad family of shallow models that are universal within the cetaraationconsrainne function class (Section (.2). However, these constructions fundamentally rely on the structure of the symmetry group. In particular, on the existence of normal subgroups of suitable size, a condition that is not always met, as is the case for key symmetry groups such as the permutation group.
We summarize the main contributions of this work as follows:
We characterize the universality classes of shallow invariant networks (Theorem 13
We establish general sufficient conditions under which universality fails, even within function classes exhibiting maximal separation (Theorem 14 and Theorem 15).
Leveraging these results, we construct explicit examples of invariant models that attain maximal separation yet fail to be universal, demonstrating that separation is not sufficient to guarantee universality (Proposition I6].
We generalize the results by Ravanbakhsh 5 to broader family of models (Theorem 18
2
Related Work
Classical approximation theory for neural networks has established foundational results for shallow
architectures with sigmoidal activations [6. 7 2T. Necessary and sufficient conditions on activation
functions were later given by Leshno al. [22] and further refinements appear in Pinkus [23]. For
general treatments of approximation theory in modern neural networks, we refer to [4] 25
Moving beyond shallow networks, Yarotsky 26 27 proved fundamental results on the approximation
rates of deep neural networks, while Siegel 28 derived sharp bounds for deep ReLU networks. These results establish that deep networks are not only universal under mild assumptions but also more parameter-efficien than their shallow counterparts, approximating complex functions with significantly fewer parameters.

---

Equivariant neural networks offer a principled way to encode symmetry into learning architectures [
B], with early applications across physics [29] chemistry [30], biology [31, and computer vision [3]
Beyond the foundational work of Yarotsky 33 universality in equivariant and invariant settings
has been studied from multiple perspectives. A number of works [5] [3) establish universality for certain shallow equivariant networks using unconstrained hidden representations. Keriven and Peyré [37] extended this analysis to equivariant graph neural networks. These proofs rely on two main techniques. The first is the application of the Stone-Weierstrae theorem, or one of its variants, for instance via invariant polynomials [38 81 to establish density results in spaces of continuous functions. The second is the use of symmetrization operator, which enforces equivariance but causes the dimension of intermediate representations to grow exponentially. However, these approaches often impractical: the -eieeeeeessss theorem cannot be applied directly, since the network families of interest do not form function algebras, while symmetrization leads to prohibitive computational costs. Although canonicalization methods improve the efficiency of models derived through symmetrization [39 40), in many cases such techniques cannot be applied [41 or remain computationally inefficient.
complementary line of work examines permutation-cquivaaiann networks over multisets. Zaheer et al. 42 Qi et al. 43 Segol and Lipman 44] prove universality for such models under constrained hidden representations, but their results are restricted to architectures of depth three. As a result, the universality of truly shallow
soworrs-those with depth two remained unresolved.
In this work, we address this gap and show that certain shallow equivariant networks are nor universal in the space of equivariant functions. This stands in contrast to the fully connected case, where universality holds generically, and highlights that depth can play qualitatively different role in equivariant architectures, extending beyond parameter efficiency to approximation capacity itself.
To capture practical models within a theoretical framework, recent work has shifted toward studying universality up to separation. In permutation-cquiyariann networks, expressivity has been analyzed through the Weisfeiler-Leman (WL) hierarchy 49], with refinements based homomorphism counts and subgraph-aware techniques [50 51]. Joshi et al. [17 extended this approach to geometric domains, deriving depth-sensitive universality results under representation and orbit separation constraints. More generally. Pacini et al. (18) recently characterized the separation power of neural networks for arbitrary finite groups and permutation representations. While these works elucidate distinguishability,, they do not fully account for approximation behavior.
The role of equivariant layers in approximation, beyond their contribution separation, remains only partially understood. In practice, such layers are often composed to enhance separation power, followed by a universal component-typically an MLP-to approximate functions within the induced separation class. In the invariant case, this composition can yield universality. In the equivariant case, however, universality is not guaranteed and is only known hold in specific instances 44). Thus, the expressive power of the overall model remains fundamentally limited by the separation achieved by the equivariant stack. Yet equivariant layers may also contribute directly to approximation, and in some cases are known to suffice for universality within fixed separation class (5).
Our work provides a detailed analysis of the universality classes of shallow equivariant networks. We show that equivariant layers are not always sufficient to guarantee universality up to separation, and that separation alone not complete proxy for approximation. We show explicit examples of models with identical separation power but differing approximation capacity. More broadly, we introduce general techniques for comparing the approximation power of equivariant models beyond separation, offering a more refined and complete understanding of expressivity in symmetry- constrained architectures.
3 Preliminaries
3.1 Groups and Equivariance
We are interested in functions that exhibit symmetry under specified transformations. Mathematically. such symmetries are described by groups: sets of transformations closed under composition, equipped with inverses and an identity element. While group theory offers a rigorous algebraic framework for analyzing symmetry, applying these ideas within neural networks requires their reformulation in alnebr-agcc terms. This translation is achieved via representation theory, which associates
3

---

abstract group elements with matrix actions on vector spaces. For a brief overview, see Appendix for more detailed treatment, see [52].
Our focus will be on permutation representations, which naturally arise when a group G acts on finite set X. Let R denote the space real-valued functions on X. For each æ E X, define 6g E R as the function taking value at x: and elsewhere The set [ea] forms a canonical basis for x A permutation representation of G on V = IR is a linear action satisfying g(ex) = Egz for all g E G and X. If V and W are permutation representations of G, a map Φ : V W is G-equivariant ((gv) go(v) for all E G and v E V. We denote by Hom W) the space of linear maps from V to W. and by Homg(V (V, W) the subspace of G-equivariant linear maps. Similarly, let (V, W) denote the space of affine maps from V to W, and Aff W) the subspace of G-equivariant affine maps, The spaces Hom (V. W), Aff(; W). and their equivariant counterparts are real vector spaces under pointwise addition and scalar multiplication. A result from Pacini et al. [53] shows that any map f E (V, W) admits unique decomposition of the form f = Ty o á for some e E W and Φ Hom(V, W), where (wr w + v. Such map is G-equivariant iff & is G-equivariant and v WC = (v W gu = i; Vg E G). the fixed-point subspace of W. In particular, there is linear morphism À (V, W) + Homa(V, W)) that projects affine map to its linear part.
3.2 Equivariant Neural Networks
With all necessary definitions in place, we now introduce the notion of an equivariant neural network. Throughout this work, we consider networks that are equivariant under the action a finite group, using arbitrary point-wise continuous activation functions, and with layers that transform according to permutation representations. We adopt the notation introduced by Pacini et al. [8]
Definition (Point-wise Activation). Let T + I.. be nonlinear activation function, and let R denote a permutation representation of group G. We define the corresponding point-wise activation R + R-x by setting ā (Ezex aze.)) = E (an))z. When no confusion arises, we will
denote both and by the same symbol.
Definition 2 (Neural Networks and Neural Spaces). Let G' be group, and let Vo...., Va be permutation representations of G. For each = l.....d,, d, let M C Aff V;) be a set of G-equivariant affine maps. For d 2 2, the neural space associated with the layers M point-wise activation function a is defined recursively by
M)...., ...., Md and
No (M ....,, Ma) f -
Ma. rp- e NN ....., (..,),),))),,
with the base case N (M M An element of E No ..... Md is called neural network with layers in M ..... Md and activation a. When each M is taken to be the full space AV-,( Vi), we write (Vo....... Va) as shorthand for N (M?,..,,M.)
To capture architectures commonly used in practice, we adopt more structured form for the layer spaces M C (V, R-x) ). as proposed in Section 4.2 of Pacini al. [18] Specifically, assume that M takes the form
M
(v) + Σ M/ 1x, 1=1
Fl,,.., Th, D1, .....
......., We R
(I)
where o² ...., l² span subspace of Homg (V, Xi...., Xe are the orbits of X under the G-action, and 1x, := = eg for i 1,..., l. This formulation, while hotavion-heavy, plays a central role in the development of our main results.
We now present two working examples of equivariant affine maps and their associated neural spaces. These examples both reflect architectures commonly used in geometric deep learning and illustrate how standard models naturally conform to the structure in ( They will serve as recurring reference points throughout to highlight key phenomena in the universality landscape of equivariant networks.

---

3
(a) Affs, RR.,))
(h) C²
(c) Affs, (R.,
(d) Aff R)
Figure I: Colored bipartite graphs illustrating the layer spaces used in Examples 3 and along with the graph corresponding to standard fully connected layer, following the convention of Ravanbakhsh et al. (54] where arrows of the same color denote identical weights applied to different input values.
Example 3 (PointNets). We focus on the sum-pooling variant of PointNet architectures 43 which are designed to process unordered collections, such as point clouds, by enforcing permutation equivariance. An input configuration of elements with f f-dimensional features is represented by tensor A E R=*1 where each row corresponds to the features of single object. Permuling the elements corresponds permuting the rows of A, iee, the indices along is first axis. our framework, the imput tensor A is modeled as an element of TR. & R',, where X [m] and the symmetric group G == Sn acts on X via ils standard action and trivially on TR! PointNet architectures operate on such inputs using layers in the space Sff.s (Rxx @ "2/"-1,,""" &g ) where each H corresponds to space of Sn-innvrriat hidden features. Accordingly, the neural spaces corresponding these equivariant architectures and their invariant counterparts take the following forms, respectively:
(I Xo fo ,..., Xxxx @ R and No & Ro ,,,,,, Xa-1 @ fa-1 ((--1,
...........
Zaheer et al. (42 showed that understanding the structure of Aff (R. & R RR & RR) reduces to understanding Aflss (IR Rxx) Identifying X with R", they established that
Affs, ". RR") {wr (or id + x2 11 11 + yl ,1, y E [R],
where 1 = 1 = 11, T].. Figure shoss the colored bipartite graph corresponding to the 1T + x. E R). which is consistent with the notation introduced in (I). Figure la shows the colored bipartite graph corresponding to the layer space Afs (R.", (RR,,D R).
layer space Aff (IR", ). In the invariant case, Aff (R" R
Example (Convolutional Neural Networks). Circular convolutional filters can be naturally for- mulated within the framework of permutation representations. For simplicity, focus the one one-dimensional case. Let X 'n] and let G = Zn act on X by modular shifts. Identifying IR* with IR"", the spuce Homz., (I."" n2 TRah) corresponds to circulant matrices A(x). each determined by generating vector x. = (T1, ........22 .n) E IR.", as shown below.
Each map in Affz,, (RR", IR consists of linear part defined by a circulant matrix and a bias term in IR
21
Fn
Tn-1
...
22
Fn
33
A(z) =
33
P2
F1
54
and yl yl (1(m))
:
In
En-1
En-2
F1_
Observe that any circulant matrix A(x) can be written as linear combination A(e A(en). that is, A(x) Ei_, 2; A(ez) where (ei,...,en) denotes the standard basis of RR... Since limited- width convolutional filters are standard in practice, we restrict attention to the following maps:
C* c== - Σ x:A((e)uU yl
21,..., Lk. y E
(2)
This class can be seen as the one one-oineeett tine-dinnnsionll analogue of the k x k convolutional kernels widely used in 2-D computer vision applications. The corresponding neural space is given by (C*1, Cthaa) for choice of filter sizes ki, ...
...... ki S Circular invariant layers be characterized as
:= Affe. (R" R) {o (x1 y x. R.)
5

---

In particular, we focus on the spaces C¹, which correspond to convolutional filters of width one; see Figure Ic for the colored bipartite graph representing the space Aff (R", ).
Having detailed the structure of the layer spaces and their correspondence to practical architectures, we now turn to the study of universality in families of shallow neural spaces.
4 Universality in Shallow Neural Spaces
Universality Classes. To establish notation and introduce the notion of universality classes, we begin by reformulating the classical universality result for shallow neural networks [23 in terms of our framework. Observe that the full class of shallow neural networks with variable width can be written as Unere-V No (R"", TR. RR. We denote by Uo (R"", RR, R) the associated universality dlass-namen the set of continuous functions on IR" approximable by such networks. Formally, Uo (R" R. R) is defined as the closure of this union in C(RR"), equipped with the topology of uniform convergence on compact sets.
Theorem 5. The universality class for shallow neural networks, Ur (R." R, R), coincides with C(RR")) if and only if the activation function is not polynomial.
An analogous result in the equivariant setting was established by Ravanbakhsh [5) for neural networks defined on representations V and W as input and output spaces, respectively, and with regular hidden representations of the form IR We define the universality class U4 (V, Rd W) the set of functions in C(V, W) that can be approximated by elements of UhEN N & (V. & R., W). Note that, in analogy with classical networks, the role of width is played by the hyperparameter h, which determines the dimension of the invariant hidden representation. The results of Ravanbakhsh (5] can then be stated as follows.
Theorem The universality class Uo (V.R., R W) coincides with Ca W), the space of continuous G G-equivariant functions from V to W. if and only the activation function is not polynomial.
We aim to provide a definition of universality classes that encompasses the notions introduced in Theorem 5 and Theorem 6 while being general enough cover wider range of architectures, such as PointNets and CNNs with variable filter size. To this end, we introduce the following auxiliary notation. Let G be finite group and let V, W and Z be permutation representations of G. Let M be a subspace of Affa (V, W) and N a subspace of Aff (W, Z). as defined in (I. Then, for each h E N, we define Mr. as the subspace of Aff (V, W @ R given by
M₁ == fa + (x)
(x)) fi..... J.M,,
(4)
(W and define N as the subspace of Aff (W s RR., Z) given by
N =
mn) + gi (x1) + + (x())) 9I....,9h 9h E EN.
(5)
Recalling the isomorphism W W = (W)@h, note that in the special cases where M = o W) and N (W, 2), we have M₁,- ~ (V, W & R²) and N = (ff & RRA Z). With this notation in place, we can now provide a general definition of universality classes.
Definition 7 (Universality Classes). The universality class U, (M, .N) associated with a family of neural spaces N,, (M .)) for h N is the set of continuous functions approximated by these neural networks. More formally, Ud (M, N) is defined as the closure of UNEx No (Ma N) in C(V, Z), equipped with the topology of uniform convergence on compact sets. As in the case of neural spaces, when M (V, W) and N (W, (WZZ) Z), we will simply write Uo (V, W, Z).
However, comparing different universality classes is particularly challenging, and in the literature, separation power has often been used proxy for this purpose. The next section revisits this notion and critically examines its adequacy as a surrogate for universality.
On Separation- Reparation-Constranned Universality. Theorem 6 esstablisse that equivariant neural networks cannot approximate all continuous functions. In particular, invariant networks are inherently unable to distinguish between symmetric inputs- limitation that naturally constrains the class of functions they can represent. To make this precise, we formally define the notion of separation and the concept of separation--oonstrinne universality.

---

Definition 8 (Separation- Conooo-i-nnt Universality), A family of functions N S {f: : +Y is is said to separate a and / if there exists such such that f(a) + f(3). The set of point pairs not separated by N defines an equivalence relation:
p(N) - ((a, B) & X x X [f()= - - S(3) for all / EW.
A family N is said to be separation- conetionn-cnttrieeed universal if its relative universality class coincides with the entire set continuous functions that respect the equivalence relation p(N), that is,
C,(X,Y) [f E C(X,Y) f(x) f(y) for all (I, p(V)}.
It standard fact in approximation theory (55) that if family of functions N fails separate ceerratioo-oonstaannndd
two points, then it cannot approximate any function that does. As such, universality captures the maximal expressivity achievable by N. Here, we aim to investigate whether separation alone suffices to characterize expressivity i.e., whether universality classes with the same separation power must necessarily coincide. To this end, we now present three network families that share the same separation relation, despite differing in their internal representations. Throughout the remainder of the paper, we assume that all activation functions
- E are non non-polynomial.
Proposition 9. $ Let C be defined as in 2 representing convolutional filters of width 1, and let I be as defined as in (3, representing invariant circular layers. Let Sn act on R" R!1
!n via the standard permutation action. Then, the following universality classes have the same separation power:
p (Co (2o (R", P. ()) (R", (B)).
This naturally raises the following question. Question 10. Are these universality classes equal as well? More generally, is separation a complete proxy for comparing universality classes?
We answer Question in the negative via Proposition 16 after developing the necessary theory.
5 Main Results
In this section, we characterize the universality classes of invariant shallow neural networks (Sec- tion and compare them (Section[5.2 Although the characterization is restricted to the invariant case, the following remark shows that can be used to demonstrate that non-approximation in invariant setting implies failure in the equivariant case well.
Remark 11. Let Ui C U2 S CV,V, (ocVV.)) W)) be two universality classes with input space V and output space W. Let ग. : + WG denote the projection onto the trivial component of W. Define the
pullback map
-" Co W)
Ca(V, WG) π TO
where CV, W) denotes the space of continuous equivariant functions from V to W. Then, T (24) S x" (212) implies Un Ç U2 since x² is continuous linear operator. This shows that a sufficient condition for strict inclusion between spaces of invariant networks also yields a sufficient condition for strict inclusion between the corresponding spaces of equivariant networks.
With this observation, we now restrict our attention to invariant networks without loss of generality,
5.1 Characterization of Universality Classes
To characterize the universality classes of invariant shallow networks, we begin by introducing the notion of a basis map.
Definition 12 (Basis maps). As defined in (.. let M be a subspace of Aff IR where V is permutation representation and Y is a finite G-set of cardinality E, which we identify with [e]. Let 6 T be basis for the linear part of M, and for each E Y. define the linear maps
R
Rm
Φ :
Z (0) (z)
(z))
We refer the maps di...., . de as the basis maps associated with M or its basis σ² ..... 6 For clarity of presentation, all proof's deferred to the Appendix, with the exception of Proposition 16
7

---

We now state the central characterization theorem for universality classes in terms of differential constraints on invariant functions.
Theorem 13. Let M and N be, respectively, subspaces of (V, () and (W, R). Let f be an invariant function, then Ugg (M,N) if and only if P(O ................................ da)f for every polynomial P that vanishes on the spaces spanned by the rows 0; ..... 0,th of each basis map .1,..., Qt, see (6).
Here, we assume d = dim V, and let P(o Oa) denote the constant-coefficien linear differential operator associated with the polynomial The derivatives O on V are interpreted in the distributional sense; see [56] for details.
Although Theorem 13 provides complete characterization of the universality classes for arbitrary families of neural spaces, this generality may come at the cost of practicality. Indeed, computing the exact polynomials P can be particularly challenging, due the combinatorial complexity arising from the intersections of the subspaces spanned by o ....... o." not merely of theoretical interest-it plays central role in deriving sufficient conditions for universality failure. These conditions enable principled comparison of the approximation power of distinct model families, as we explore in the following sections.
Nonetheless, the theorem
5.2 Sufficient Conditions for Universality Failure
In this section, we present two sufficient conditions for the failure of separation-consee constrained uni- versality. These results will be used to resolve Question and to prove Proposition T6] We begin
with Theorem 14] which provides a general but more difficult verify- criterion, followed by
Theorem 15 less general version that is simpler to apply, despite its more convoluted appearance.
First, we introduce the notion of a directional derivative. For each vector (CI,..., ,,)) E RR", the directional derivative is defined as the differential operator D. ci 0 + .... + Ca On.
Theorem 14. A continuous function f does not belong the class Uo (M, if
De, ... DoeJ +
for some choice of ca in (er()a))e for each basis map Φ1, ;1,-..;;4
In the case of equivariant networks where each affine layer is allowed be arbitrary equivariant affine map, Theorem [4 can be strengthened as follows.
Theorem 15. Let M AV, W) and N Aff R). where V and W are permutation representations. Let 01...., de denote the basis maps associated with M, see (6). Then, the universal class Up (M,N) fails to be separation-constrainn
universal if. for some choice of:
integers 81, ; E {0,-..,f) satisfying 81 + 8
integers a1 > and a; + i < a++1 for each = 1,..,,
vectors c ker(d]) for each i ?,
Let i1, ., be the indices such that si, # The following expression is nonzero:
aig st.
ai_ (G((),) ... (r(s1))) (Ca(s)+1),2 Co(s1+52))2) ( (Co(e-ss)e) Ct,e).
5t
nES2
The Heterogeneous Landscape of Universality Classes
We now apply the tools developed in Section 5 to investigate the structure of universality classes and
illustrate their heterogeneity. In Section [. we address Question To applying Theorems [4d [5]
to exhibit concrete examples of failure. In contrast, Section 6.2 presents Theorem [8] generalization of Theorem(6] which provides sufficient conditions for achieving separation-constrainee universality- highlighting the diversity of behaviors within fixed symmetry classes.

---

6.1 Examples of Failure
Proposition 16. As established Proposition the following spaces achieve the same separation power, yet differ in their approximation capabilities when n > 2:
I S U.(R", & U.
By Remark 17
the corresponding equivariant models also have distinct approximation power.
We will prove the two strict inclusions of Proposition I6 the following three paragraphs.
Failure for CNN with filter width 1: We now apply Theorem 14 show that CNNs with filter width
I cannot approximate the function (I) +... +r," for > 1, namely (œ1 +.......0 +...+t.)) +In)" & Up (C', T). Indeed, for any a = I.... .....,,, n. we have Ea+1 E ( Span(er, eay..., en.. where a + modulo n. Moreover, note that De. 0a. thus On ... (x1 + ... In)" m! o 0, which
violates 7 in Theorem 14
Success for PointNet: We now show that shallow PointNets approximate the polynomial function
(xr 4...............
+... T.) belongs to Ms (TR." TR." IR) for any f E C(TR²). In particular, for f(x, y) == v" E C(TR2), we see that (x1 +... Fz )d Ug (IR" R IR IR. Together with the previous observation, this establishes the first
V., 2.,) By Proposition 41 Appendix f( +... +... +.... ff (Xn,
strict inclusion in Proposition 16 namely Uo (C", )) Ç (IR", RR", "e",, RR).
Failure for PointNet: We now aim show that shallow PointNets cannot approximate the polynomial function ø1 ... In, which is S,,-invariant and therefore should, in principle, be approximable in a setting. We distinguish two cases: 3 and 3. Note that for n 2, the symmetric group S2 is abelian, and universality follows directly from Theorem
separation-constrainne
We start considering (n > 3). We again employ Theorem 14 show that shallow invariant PointNets cannot approximate 2i ... En. and hence neither CNNs with filter width Indeed, note that the basis maps for Aff s, (RR". IR") in this
are given by & (x1, ....... Fn) (Ta, I1 +..... Tn). In matrix form, write d₂ = [ea, I] We define Ka, ker (Øa) Span(e; ez)ss=l Then,
define the following direction vectors:
ci =2 c2 en K1,
C2 == 63 en K2:
Cp On-2 2- Pn E K Kn-3,
Ca-2 = fn En E Kn-2,
Cn == en - e2 E K Kn-1,
On := El - e2 E Kn.
Explicit computation shows that De, Des (x) ... ..)) = 2, verifying
The previous technique does not apply in the case n = 3, for which we must instead resort to
Theorem 15 First, define C₁ 62 C3 E K1,
= C3
K2, and c3 == C2 E K3-
Note that Ci. = 0 for each i = 1, 3. For 81 = 2, 82 = 1. and 83 0, the polynomial becomes a ai(a) 1)e2 [c3.1 C2 c1,2]
-a (a) 1)a2 + by choosing a 02 3.
In view of the universality results for PointNet with depth and arbitrary widths in both hidden layers by Segol and Lipman [44). this example highlights how, in the case of permutation equivariance, universality. This contrasts with other settings where universality can be achieved without relying on depth, as we will describe in the next section.
depth crucial for achieving reparation-constrainn
6.2 Examples of
Universality
We now present Theorem 18
generalization of Theorem 6 which shows that a specific class of hidden representations can achieve separation-constraine universality. These representations arise from cosets of particular subgroups H of G, defined as follows:
Definition 17 (Normal subgroup). A subgroup H is normal if -h e H for each h E H. G. Theorem 18. Let V and Z be permutation representations of a finite group G, and let H be normal subgroup of G. Therefore, Ur (V, RG/H 7) is separation-constrainell universal.
The converse does not always hold: representations arising from non-normal subgroups may never- theless achieve separation universality, illustrated in the following remark.

---

Remark 19. Let H. be non non-normal subgroup of Sn contained in A.. Then
Uo UR (AR55./A,RR9./A., S./AA,, R. Ur (IR RS/H R) Cs. (IR Sn/n).
All subgroups of an abelian group are normal, whereas S, has only one non-trivial normal subgroup, An. with |S,/An| summarize by noting that intermediate representations built from abelian groups, such as those in standard circular CNNs, achieve pntrraaionncosstrainn universality. In contrast, architectures based on permutation representations lack this guarantee, as shown in Proposition 16
yielding hidden representations that are too small be effective. We
7 Limitations
This work represents a first step toward understanding the approximation capabilities of equivariant networks beyond separation. Several limitations, however, remain. In particular, analysis is limited to shallow networks. While these serve as minimal and analytically tractable examples, they may not fully capture the behavior of deeper architectures. Extending this framework to deeper networks particularry settings where depth interacts nontrivially with separation, as in IGNs- CoNs-poses significant challenge.
8 Conclusions
We investigated the approximation capabilities of equivariant neural networks, moving beyond their well-studied separation properties. By formulating shallow invariant networks as generalized superpositions of ridge functions (see Proposition 4Tp, we developed a novel characterization of their universality classes and examined how architectural choices influence approximation behavior. Our analysis reveals that even networks with maximal separation power may fail to approximate all functions within the corresponding
ceametry-respecting class, a phenomenon we attribute to the structure of their hidden representations. These findings suggest that approximation power cannot be deduced from separation alone and should treated as a distinct axis of expressivity. Our results thus call for more nuanced understanding of equivariant architectures that takes both axes into account in theoretical analysis and model design.
As future directions, we aim to extend our framework to determine whether failures of separation- constrained universality, such as those established in Proposition [6] persist in deeper architectures. Another important avenue for investigation is how differences in expressivity affect generalization, particularly among models that share the same separation power.
10

---

Acknoledgements
Bruno Lepri acknowledges the support of the PNRR project FAIR FAIR Future AI Research (PE00000013), under the NRRP MUR program funded by the NextGencrationEU and the support of the European Union's 's Horizon Europe research and innovation program under grant agreement No. 101 101220 (ELIAS). This work was also partly supported by Ministero delle Imprese del Made in Italy (IPCEI Cloud DM 27 giugno 2022 APCEI-CL-00000 and European Union (Next Generation EU).
References
[1] Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. In Proceedings of The 33rd International Conference on Machine Learning, pages 2990- 299002999...910 PMLR, June 2016. URL https::/proceeddng.. mlr wwwpppreessseee /0eesss/v5//chhen1666 cohenc16. html ISSN: 1938-7228.
[2] Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups. In Proceedings of the 35th International
Conference Machine Learning, pages 2747-2755. PMLR, July 2018. URL https://
proceedings.. mmr........r.................... www....resssvv..
v80/ http0///onor8810/ html ISSN: 2640-3498.
[3] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, 1rXiiv220441344 [cs, stat), May 2021. http:/ttp:///rttt /ttp://arxvvvv/// wearxivv.oggaaae hwtpg/abs/2104 13478 arXiv: 13478.
[4] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In International Conference Learning Representations, September 2018.
URL
net maeee/oorummddiaeeeeee foy
[5] Siamak Ravanbakhsh. Universal Equivariant Multilayer Perceptrons. Proceedings of the 37th International Conference Machine Learning, pages 7996 8006. PMLR, Novem- ber 2020. URL httpps:/prooeeednngs mww. wttps////1////aaaaaaaaaaiaaaaea
html ISSN:
2640-3498.
[6] G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314 December 1989. ISSN 1435-568X. doi: 10.1007/ BF02551274. URL https:://///oi http://dd...rrrr0/.oo0000////222 10070///5///////7
[7] Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks,
4(2):251-257, Jamuary 1991. ISSN 0893-6080, doi: 10. (0010016600993660000999)00000000
URL
http://wwww.ccnnccddreeee htw.iirrrttttccceeeeoemmeeeeeeee httt://c//cccinnaaaeiiiieeemeeee http://cw....o..oooooooccoocooaa
[8] Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, and Yaron Lipman. Equivariant Polynomials for Graph Neural Networks, June 2023. URL http:://trx:t //ap:v////xiv./// http://axiv..oggbbb/a/ee org/abs/23222
11556 arXiv:2302. 1556 [cs].
[9] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant Sub- graph Aggregation Networks, March 2022. URL ktttp://arxis: arXiv:2110.02910 [cs, stat].
[10] Yu Weisfeiler and A Leman. THE REDUCTION OF A GRAPH TO CANONICAL FORM AND THE ALGEBRA WHICH APPEARS THEREIN. page 11, 1968.
[11] László Lovász. Large Networks and Graph Limits. volume 60 of Colloquium Publications, Providence, Rhode Island, December 2012. American Mathematical Society. doi: 10. 1090/o//l
060.. URL /wwww/wwww///////////o/ ams. wwgo/o///ooooooooooooo co01/000
[12) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Faculty of Informatics Papers (Archive), January 2009. doi: 10.1 0009/TNN.2008.200555
URL https:t/ uow edu au/ htt/infooapers/3165
[13] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729-734 vol. 2, July 2005. doi: 10.1 LL99/I//NN.N00/00 105559999... 1555942. ISSN: 2161-4407.

---

[14] Thomas N. Kipf and Max Welling. Semi- Semi-Supervised Classification with Graph Convolutional Networks, 1609: 02907 [cs. stat], February 2017. http:///:/arxxiivoo orgg/bb////b999 02907 arXiv: 1609.02907.
[15] Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On Learning Sets of Symmetric Ele- ments. In Proceedings of the 37th International Conference on Machine Learning, pages 6734- 6744. PMLR, November 2020. URL (tLL/tttss//pprceeddiine mlr wttpp////11/mmmmm22/22... ISSN: 2640-3498.
html
[16] Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. Subgraph Neural Networks, November 2020. URL http://arxiv..rrgg http///bs///../.. 10538 arXiv:2006.
[cs, stat].
[17] Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, and Pietro Lio. On the Expressive Power of Geometric Graph Neural Networks. International Conference of Learning Representations, 2023. URL httpps:///pperreeiii www./neee//nene
http://peerrrieeeeeeeetooooooooo Rkxx 16kn__
[18] Marco Pacini, Xiaowen Dong, Bruno Lepri, and Gabriele Santin. Separation Power of Equivariant Neural Networks, December 2024. URL URtp://///arxi http:::/aaxivorrg//// htt//bba/24000 227040096666666 arXiv:2406.08966 [es].
[19] Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, ismail Îlkan Ceylan, Ron Levie, Derek Lim, Michael Bronstein, Martin Grohe, and Stefanie Jegelka. Future Directions the Theory of Graph Machine Learning, June 2024. URL (Rtp:ttp://arxt wttp:/iw..rggbb///00000 02287 arXiv:2402.022877 [cs, stat].
[20] Yair Davidson and Nadav Dym. On the Hölder Stability of Multiset and Graph Neural Networks, April 2025. URL httpth:p/aaxii..rrggg...e /2240/ 06984 arXiv:2406.066 069984 [cs].
[21] A.R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory, 39(3):930 9450 May 1993. ISSN 1557-9654. doi: 10.1109/18.22 2255500. URL
1eee org httg//dommentt2255500
[22] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Ner- works, 6(6))661-666) January 1993. ISSN 0893-6080. doi: 10. 10.10166500033-00000088831333333 URL /tc.
com ott.://chc.....oooooo.oooooooooa
[23] Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8: 143-195, Jamuary 1999. ISSN 1474-0508. 0962-4929. doi: 10.1017750962499900000999 URL
https: h/www///wwwww// httpa//wwiigggggoooooooooaaaaaaa
[24] Ronald VeVore, Boris Hanin, and Guergana Petrova.
Neural network approx-
imation. Acta Numerica, 30:327-444, May 2021. 0508.
ISSN 0962-4929, 1474-
doi: 10.1017/5096249221000055
URL attps://weee http::///wwwcammridge cambridge org/
7077 00778800986644059990000028333313
[25] Philipp Petersen and Jakob Zech. Mathematical theory of deep learning, April 2025. URL
http://arxiv.org http:/iiiiirrga//////aaao abs/2407 18384 arXiv:2407.1825 18384 [cs].
[26] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks,
14:10311 October 2017. ISSN 0893-6080. doi: 10. 10. 1ww.1066j.ncumee20117..777
URL
[27] Dmitry Yarotsky, Optimal approxiatoo of continuous functions by very deep ReLU networks, June 2018. URL http::tttp///axivoorrgg
03620 1eXiv:1802.00622 [cs].
[28] Jonathan W. Siegel. Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces, April 2024. URL http:://rxiis www.oogg////e//eeeee//..oeeeeeee wtbs//211..11. 14400
arXiv:2211 1.1 1.440 [cs, math, stat].
12

---

[29] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation- and translation-equivaniin neural networks for 3D point clouds, May 2018. http::tttt/iii..oo///
08219 arXiv: 180200829. [cs].
[30] Kristof T. Schütt, Huziel E. Sauceda, Pieter-Jan Kindermans, Alexandre Tkatchenko, and Klaus-Rober Müller SchNet a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24)244122,, June 2018. ISSN 0021-9606, 1089-7690. doi: 10. 10.1063/1.001979. URL btttp://axxiv..rr//aee [physics].
06113 arXiv:1712.06113
[31] Chaitanya K. Joshi, Arian R. Jamasb, Ramon Viñas, Charles Harris, Simon V. Mathis, Alex Morehead, and Pietro Liò. gRNAde: Geometric Deep Learning for 3D RNA inverse design, April 2024.
1101/2024 03. 31. 587283
[32] Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3D steerable CNNs: learning rotationally equivariant features in volumetric data. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pages 10402-10413, Red Hook, NY, USA, 2018. Curran Associates Inc.
[33] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks, April 2018.
10306 1Xiv:1804, 10306 [cs].
[34] Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and folle-connected networks. Proceedings of the American Mathematical Society, 148(4):1567-1581 April 2020. ISSN 0002-9939, 1088-6826. doi: 10. 10910/0//////////////// 14789, URL ottpaar....pppp/...o/////////000 000004//00000000000------------0
https://www. ams org/ wttgppoo//2000-1100gg 140-
[35] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In Proceedings of the 36th International Conference on Machine Learning, pages 4363 4371. PMLR, May 2019. BtLlhttps:///pee httpp:://proceedings mlr. ppessppessse. wwwpp/eer/////e/ https//9//marnnneee/ html ISSN: 2640-3498.
[36] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda. Universality of group convolutional neural networks based on ridgelet analysis on groups. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, pages 38680-38694, Red Hook, NY, USA, November 2022. Curran Associates Inc. ISBN 978-1-71387-1006
[37] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Net- works. In Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL /ttppers/ http://ppprs.............. wttppcpppppp...cceccccc happpppprrfeee__eseeeeeppppppeee files
httppppar...leeeppee//////////// pttpp//ppp/pppaaeaep .html
[38] Ben Blum-Smith and Soledad Villar. Machine learning and invariant theory. Notices of the
American Mathematical Society, 70(08):1, September 2023. ISSN 0002-9920, 1088-9477 doi: 10. 10900/ooi222.0. URL httl:httpp//aa http///axvvvv./ org/ absaabas////// 14991 arXiv:2209. 149991 [stat].
[39] Omri Puny, Matan Atzmon, Edward J. Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame Averaging for Invariant and Equivariant Network Design. October 2021.
URL /ttpp:://penrrevie wtwp:e/wwww.nneonnnneeoo iir
[40] Sékou-Ouman Kaba, Arna Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravan- bakhsh. Equivariance with Learned Canonicalization Functions. In Proceedings of the 40th International Conference on Machine Learning, pages 15546-15555 15566. PMLR, July 2023. URL
httpps://proceedings... mlr Stteess/v002//aaa
html
ISSN: 2640-3498.
[41] Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel. Equivariant Frames and the Impossibil- ity of Continuous Canonicalization, June 2024. URL http:://at:xii/ org/ wttgg/bb//4402.1111 2202 16077 arXiv:2402.16077 [cs].
[42] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep Sets. In Advances in Newrul Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: ///p:err////////// wwwpaaprrr.ip.pp..omo
www.:iicppppaa.aeeee cc/psprrr/ppprr paper_fileess files/
13

---

[43] Charles R. Qi, Su, Hao, Mo, Kaichun, and Guibas, Leonidas J. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 77-85, Honolulu, HI, July 2017. IEFE. ISBN 978-1-5386-0457-1 doi: 10. 20.100//VP..2007.1666 URL http:///eeeeppore ieee. .rgg. document/80999999/
[44] Nimrod Segol and Yaron Lipman. On Universal Equivariant Set Networks, January 2020. URL http:://rxxvv.rrg/ htt.aa///99...2...01 arXiv:1910.02421 [cs, stat].
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks?, February 2019. URL /ttp::///aaxxii.oo httpiii/.rr//b////aaaae 11100 00826 Number:
arXiv:1810.00526 arXiv: 1rXiv:1810000822 [cs, stat].
[46] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman Go Neural: Higher-
Higher-Order Order Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4602- 4609, July 2019. ISSN 2374 3464, 21.99-3399, doi: 10. 1aa.16609aai..3335 v33101 .3301 4602. URL https://aaai org//js////ooooo ind///ndxxx../// php/ AAAI/ AAAI/articlaa http://ttticleeeeeeeeeeeeeeeeeee /v31ew/334/4
[47] Haggai Maron, Heli CanmHamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. International Conference of Learning Representations, 2019.
[48] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs, May 2019. URLhttp //arxiv. www.ooggg//////eeoooeoooeeeeee/e ab9/ 12560 arXiv:1905.122 [cs, stat].
[49] Waïss Azizian and Marc Lelarge. Expressive Power of Invariant and Equivariant Graph Neural Networks, June 2021. URL
wttp::/p...........///// 15646 LtXiv:2006.15644 [cs,
stat].
[50] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, He, and Liwei Wang. Beyond Weisfeiler- Lehman: A Quantitative Framework for GNN Expressiveness, January 2024. URL http
7/arxiv. //arxiv.org// orgg/bs////e aas///422 2401. 08514 3XXi:2401.08854 [cs, math].
[51] Fabrizio Frasca, Beatrice Bevilaequa, Michael M. Bronstein, and Haggai Maron. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries, October 2022.
//arxiv. www./ogg//////e///e//oooeeeeee//
2206.2206..2 11140, arXiv:2206.1 1140 [cs].
[52] William Fulton and Joe Harris. Representation Theory, volume 129 of Graduate Texts in Mathematics. Springer, New York, NY, 2004. ISBN 978-3-540-00539-1 978-1-4612. 0979-9. doi: 000079978-1-4122-99777 978-1-4612-0979-9
URL http: http:/iinkk.piinnge..... springer wwwpriingr..cm/1000 10. 1000/
[53] Marco Pacini, Xiaowen Dong, Bruno Lepri, and Gabriele Santin. A Characterization Theorem for Equivariant Networks with Point-wise Activations, January 2024. http://arxx/
org/abs/2401.09253 arXiv:2401. 009235 [es] version:
[54] Siamak Ravanbakhsh, Jeff Schneider, and Barnabás Póczos. Equivariance Through Parameter- Sharing.
[55] DeVore. Constructive Approximation. 1993. URL 9783540506270
com/book/
[56] Grubb, G. Distributions and Operators, volume 252 of Graduate Texts in Mathematics, Springer, New York, NY, 2009. ISBN 77780-3387-84888 --778-937-- doi: 1001/ 118-0-387-84895 URL http::ttpp:/k...tt/////// http:///ink..sprineer http:///0.1107777755---8-----880 ISSN: 0072-5285.
[57] M. F. Atiyah and I. G. MacDonald. Introduction To Commutative Algebra. Avalon Publishing, February 1994. ISBN 978-0-8133-454444
Google-Books..e HOASFid4x18C
[58] Allan Pinkus. Ridge Fanctions.
Cambridge Tracts in Mathematics.
Cam-
bridge University Press, Cambridge,
2015. ISBN 978-1-107-12439-4,
doi:
1010077CBB09988114444884144
URL https://www. hwtp://wwmbbiidg..c htw.mbbridd...rgg/r///boooo.ooo.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The general investigation concerning the approximation power equivariant neural networks beyond separation constraints is described in Section 4 The main result, as mentioned in the abstract is described section 5 The implications are described throughout the paper, but especially in section 6
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Separate limitation section is added to the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: The definitions and notions are presented to facilitate a self-contained presen- tation of the main theorems. Additional details are relegated the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA].
Justification:
The paper presents a theoretical investigation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA].
Justification:
The paper presents theoretical investigation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /itee//ggudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA].
Justification: The paper presents theoretical investigation.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: The paper presents a theoretical investigation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification: The paper presents theoretical investigation.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////ourrr...cccc/a///////a
Answer: [Yes]
Justification; All the authors have reviewed the code of ethics. The work presents theoretical results that analyze equivariant/Invarint models. Most of the ethics concerns do not apply such work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: The work presents analysis concerning particular question regarding the universality and approximation power of equivariant models. As such it does not have broader social impacts that merit separate discussion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
Theoretical paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
No experiments and data presented in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]-
Justification:
No new assets introduced in the paper, given its theoretical nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
No crowdsourcing necessary for the presented work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification:
The presented work does involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA].
Justification: LLMs were not used to interrogate the results presented in the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy oattaa///aarrrppp.cccc//ootrreea for what should or should not be described.
21

---

A Preliminaries
A.1 Group Theory
Definition 20 (Group), A group is a set G equipped with a binary operation G + G satisfying the following properties:
Associativity: for all g, E G, we have (g h) k= = Ah).
Identity element: there exists element E G such that g e g for every g G.
Inverses: for every g E G. there exists an element y G such that 9 و ==
The group is said be finite if G contains finitely many elements. is called abelian (or commutative) if g h h- holds for all h E G.
We now define the concept of a group homomorphism, structure-preserving map between groups. Definition (Homomorphism), Let G and H be groups. function ø G + -H is called group homomorphism if, for all h E G, it holds that
$ h) = x(g) <(h)-
Definition 22 (Cosets). Let G be group and let H I G be a subgroup. The left coset of H associated with element g G is the set
gH = (gh h E H}.
The collection of all left cosets of H in G is denoted by = (gg | G).
Similarly, the right coset of H corresponding to G is defined as
Hg {hg h E H). and the set all left cosets is written as G/ [gH 1 G) Given another subgroup K < G, the double cosel associated with g Gs the set Hgk = {hgk h E H, M.
and the set all such double cosets denoted by HGG/K. Definition 23 (Normal subgroup). A subgroup H is normal if ghg- E H for each h e H.g G. Example 24. We highlight two families of normal subgroups relevant our discussion:
1. All subgroups of abelian groups are normal.
2. The alternating group Ay is the only non-trivial normal subgroup of Sn. Theorem 25. If H is normal subgroup GG then the cosets G/ H for group, where the binary operation is defined as gi H 92Hl = 9192
A.2 Group Actions and Equivariance
Let G be group and let X be a set. A group action of G on is map
X,
X, that satisfies the following two commonly written as 0g(x)) (g) for g e G and æ conditions:
Identity: idx, where is the identity element in G.
Compatibility: For all g. h E G, we have dy o db = 0gh.
In practice, we often denote the action by
simply gæ in place of (x
A set X endowed with a group action of G is referred as G-set. That is, X is G-set if there
exists well-defined action G X + satisfying the identity and compatibility conditions above.
Another fundamental notion for our analysis that of a map between G-sets that respects the group action. This leads to the definition of equivariance.
22

---

Definition 26 (Equivariance), Let X and Y be G-sets. A function f X - Y is said to be G-equivariant if, for all g G and E X, the following condition holds:
flg x) - f(x).
A.3
Group Representations and Equivariant Affine Transformations
Let G be a group and be vector space over a field R. G-action G - V G-representation if 0g is linear for each in G. Or equivalently,
G - GL(V)
:
9T0p 0g
where GL(V) is the general linear group of V, consisting of all invertible linear transformations V. We will usually identify the entire & : G x V - action with itself and write gv = +b(g v).
Let V and W be two G-representations, tween and W as Homg(V, W) and as o W) the set of equivariant affine maps. Note that Homg (V, W) is vector space. Indeed, 0 Homo(V, W) and for each f.g Homa(V, W) and each a, 8 E IR, of + 3g E Homg(V W). The same true for Aff W).
will indicate the set of equivariant linear maps be-
Let V be G-representation, we define the set of invariant vectors V {u EV gu = Vg E G}.
A.4 On Permutation Representations
Definition 27. Let be finite set and let G' be finite group acting on X. A permutation representation of G is the linear action G the space R. defined by
g(ex)
eg for all g E x
where fex denotes the standard basis of R
Proposition 28. Let X and Y be G-sets. Then, the following G-equivariant isomorphisms of representations hold:
2
ORY and x ORY
where UY denotes the disjoint union and X the Cartesian product of the two sets.
B On Commutative Algebra
For general introduction commutative algebra, we refer to Atiyah and MacDonald 57 we recall the notation necessary to prove Theorem 13 and 15
Here,
Let [R[2,,...,, xx]] denote the set of polynomials in the variables ,,,..., Ty- Definition (Ideal). An ideal I of R[x,,..., xn]] is subset such that, if ʃ E I, then p / for every p R[z,,.... In]. If X C R", define
I(X) = (f E [[[TI....,
f(x) = O e
Definition 30 (Product Ideals). Let I,J S R[ ..,, x. be ideals. Their product I J, or simply IJ, is the ideal defined by
IJ Σ Sag Sa I
Definition 31 (Generators of an Ideal), Let R = R[z xnl be the set of polynomial and let
fi...., fm R. The ideal generated by f1,....fe fm the set
(Ji,..,, fm)
Σ hafa h4 R
We say that fi...., fm are generators of the ideal.
23

---

Proposition 32. If X is linear subspace of R such that its orthogonal complement X is spanned by vectors Uy....y dd then
I(X) = (0) -.,...;00 U2 xx).
Proof. Indeed.
I(X) 2 (u] 2, ......, to z))
To prove the reverse inclusion, observe that-up to a change of coordinates- may assume 2/ x 2; for .................... d. In this case, any polynomial f(æ) E I(X) can written as
f(x) = ai (I) + ... + ax(2)=a + b(z).
where (x) E R[a,..... [n)] for each i = ,,..., d. and b(x) is polynomial whose monomials do involve the variables 21...... Zd..
Now, since vanishes on X = {a IR D1 = za = 0). it must be that b(x) = 0 identically, Therefore, f()) lies in the ideal generated by Z1..... Lz. completing the proof.
Remark 33, The following are either standard results or direct consequences of the observations above:
The intersection and the product of ideals are themselves ideals.
I(X1 -...U..U)) = I(X,) n..... (I(e)).
If Xf....... Xe are linear subspaces RR" then -.Xx)) generated by polynomials of the form (v] x) ... (vx x), where .1,.... Ug vectors respectively in ......, X
C On Superpositions of Ridge Functions
In this section, we present results on the theory of superpositions of generalized ridge functions. A detailed exposition can be found in Pinkus (58).
Definition 34 (Superpositions of Generalized Ridge Functions). Given linear map & IR" B
generalized ridge functions is an element in
M(6) = { ( C C(R").
Given Ω C pdxn, superposition of generalized functions is an element in
M(2) =Span { f tobl /ECCCRRR )
I finite, say Ω = {di hie, we may write
M( = MM(i)ier = { x +
Σ f.o f C(R")
iET
or simply write M( di) when = (di...., d
To facilitate our exposition, we introduce the following auxiliary notation. Let Bdxn be matrix, and write it as
a1
A =
Od
where a,s are the rows of A. Define
L(A) = Span fai,..., ad)-
Let Ω C R dxx be finite set of matrices. Define
L( = U L(A).
AE
In the following, will use the following fundamental result (see [58 p. 65).

---

Theorem 35. Ler Ω = (AI.....A.) _ R dd be a finite set of matrices. Then
M(Ω) = M(L(9t) = =M(I(A) U...UU L(A.)).
We can characterize the previous sets using the following notions.
Definition 36. Given ! R"", define the ideal of polynomials vanishing on f2 as
[(?t) {p E Riz z.,] p(z) O Ωt)
and then, define
((2) == {p E
((D) = 0 I(
Theorem 37 (Theorem 6.9 of [58]) In the topology of uniform convergence compact subsets
M( = C()).
We can compare the closure of spaces of superposition thanks to the following theorem. Theorem 38. Let Q and S' be subsets RR" closed under scalar mudtiplication. IfC(S) ç C(2))
then (()) & C(S)) topology of uniform convergence on compact sets.
Proof. If C(2) ç C(22') then there exist p' E C((2)) and q I(22) such that
(D) . 0, Ag E I(Ω')
and
(DD) p' #
for each C()).. Note that (D is continuous operator in the space of tempered distributions and ((2) ker q (D). Since ker D) is closed subspace by Lemma 39 then C(S2) C ker q( (D) while p' & ker (D), concluding the proof.
Lemma 39. Let (Pn)nEN be sequence of polynomials in d variables, each of arbitrary degree, that converges uniformly on compact subsets to a polynomial Let P(or..... Qa) be linear differential variables. If
operator with constant coefficients, that is, a polynomial
P(θ 02) Pr =0 for all n E N,
then
P(a.....,, 02) O.
Proof. Define:
(f.9) = [(x)g(x)dx.
Jgn
Let be a smooth function with support on a compact K. We know:
(Pn. Φ) (p. 0),
for n - 0o. Let Q( 0a) be the adjoint operator of P(o,.... 0a). This operator is still linear differential operator when defined on smooth functions with compact support. In particular, is still a smooth function with support on K. Moreover,
(nn. Q(a,. 0a)o) = - -(P(a,..., Da)Pa, の) =
(8)
for each n. Due to convergence on compacts and knowing that the support of Q(+,,...... Og) is K, we obtain
Pu, Q Ox)o) + (p.
(9)
for co. Thanks Eq.
get:
(p.
Finally,
Φ) = - Q(a......... 02) 0.
Since @ is arbitrary smooth function with compact support, we get
(P ag)p.
for each with compact support. For the fundamental theorem of calculus of variations, P(O Oxpp p is identically zero.
25

---

D Proofs and Auxiliary Results
In this section we will concentrate on a particular subset of superpositions of ridge functions, namely, the symmetric ones.
Definition 40 (Symmetric Superpositions). Let $1,..., IR" + R be linear maps. We define symmetric superpositions of ridge functions as follows:
= ( (x=))
de Is C(R*).
Proposition 41. The family of functions approximated by Ua (M, N) coincides with the class A A where 21 are the basis maps associate M.
Proof of Proposition 41 In the general setting, write the linear parts of M and N respectively as ((M) Span f ...., 6 and A(N) = Span {a + 1 ... Elements in Ma can be represented affine maps + Br + where B and have the following block representations
01 + +... ....t m
B
and c=
1 + +... 6
Ch
While elements in N can be represented as affine maps + Az + d where d e R and
a1 1
A
Og 1
Denote by of the projection of the i-th component of the function Φ. We can write elements n E N (Mash N) as
h
m
nxx) (Br +
Σ
Σ
(z) +
j=1
KEY
for some o, by,e, Oj E R. But note that
h
71x)
Σ aj Σ o
Σ (x) (x) t
(10)
1=l
KEY
h
m
a
Σ
b (x)) t0²
Σ
(x))
(11)
VEY 1=1
iEY
where
(ym..... ..n) = Σ ajo Σ
bieete t
a standard multilayer perceptron in (N IR RR.. Since, the the multilayer perceptron is universal, thanks to (10) can approximate any superposition in A(d1...., Φ1). Thus, have
A S (M.
On the other hand, by
10
NN N) C .......... A(h
NEN
It follows that their closures coincide, which concludes the proof.
"m., 3, and let N be the set Let M be a vector space of affine maps such that X(M) = Span (Ø) (o'....,"") of invariant affine maps. Denote p == p(NN(M, N)). We denote by (f=1,-.. vn)) the multiset of elements Ti,..., Zn. We have the following proposition.
26

---

Proposition 42, With the notation defined above, we have (z. v) E (M, plu (M, and only if
=
where we identify with [f], which inherits its Gestt structure from Y, and the maps oe are those defined in (6)
Proof. By the combination of Proposition 41 and Theorem 8 in 18) we have (M, N)) = p(U (M, N) ((A(01....,. Thus, suffices to verify this property for A(01, ΦE). Note that if x and satisfy
(1))......, (()))((((())....
then, for each F' E A(é1..... Φe), we have
......ffoo F(z) fo + + f +.... ff = F(v).
On the other hand, if
((11(t).... be # (()1(v)...., -
then have two possibilities: either there exists such that 6,(x) + Φv(y), there exists value y such that number of indices with 0,(x) = 7 (denoted 8) differs from the number of indices with (3) y (denoted t). In the first case,
choose interpolating function that does not vanish at Φ, (x) and is zero on the other values in consideration. this case,
(v( F(y)- In the other case, we can similarly chose a function f nonzero on 7 and zero on all the other values in consideration. In this case,
F(x)
on (x) +............................... (e(x) # 0 f (1 +
F(x) = f (x) + + ( = =](() * (5()) = x1(1)) + +..+
+ S (c(())) = F(y).
This concludes the proof.
Proposition fooposssion follosss directly from Proposition 42
Proof of Proposition Note that, by Theorem 6 plu 1)) = Cs. (R") and thus has maximal
separation power in the context of permutation invariance; that is, it separates two points if and only they lie the same S, -orbit. Note that the basis maps associated to C are eT ,..., e Hence, by Proposition 42 (x, y) (CL , I)) if and only if {[II,... In Hy..... yn }. This holds and only æ and y lie in the same -obbit Thus, (C',,, I) also has maximal separation power, and hence
plu, (R", RC IR)) p(u, (C), T)).
Since
Ua(C U. (R", R" R) C Ur "RRRR,,,,,, RCC R),
follows that
RRRR) S (R" R" R)) S (C
Therefore, all inclusions must be equalities.
Proof of Theorem 13 Note that
M(6..... =Mth-(
for basis maps .i,..., : de and .h.,..., dh such that
Span(o ..... = Span ,..., ",.
since
L(Φ:) L(bb))
for each = I,...,l. In particular,
M( bz) M(t
Thus, it suffices to restrict to specific basis 0f ..... Th chosen follows.
27

---

Consider the decomposition
Homg (R RR Homg (R*
R ") + ..... 2 Homg (R. R...)
and construct basis of x(M) by choosing, for each ,,... T, a basis of Homg (R* R )R), and embedding it in Homg (R* R via the canonical inclusion induced by the direct sum decomposition. In particular, there exists partition
I L..... III, [m]
such that
Span ( her. = Homa R)
for each i = ,....,r, where each Homa (R= R2 viewed as embedded in Homa (R* Y Equivalently, for each j E I, there exists vor E Homa ,R*' such that
(x) (O....,0, O, (x)) O).
(12)
thth block
With this notation in place, we now prove that
M( 6z) A(Di,...,
Let R :C("") - C(RR"GG be the Reynolds operator, namely
R(F)(z)= = GG|
Σ F(gx). 9EG
For each E M( Φt), write F(x) = Ei fk o Φb (x) for some continuous ; fe. Moreover, since oi ,..,..,"""" Th are G-equivariant, the induced G-action permutes the corresponding family of coordinate maps. More precisely, for each g G' and each index & we have
Φu(gæ) 1.
for all x.
Indeed, using equivariance of each ei
(ol(ox),..... 0% (gx)) ((oØ)) )))))((()))))))))()))))) (gd"))(())
(0) (z)..... 80hh 1 (I))
for each A = 1,...,6. L. Then
R(F)()) =
G Σ F(gz) G
fo o (x())) gEGA=1
gEG
fo (x)
gEG
Next, group together indices belonging the same block. For each i 1.... .,,,, let : R R/41 be the coordinate projection induced by the partition [m] = I, L ... Ir. That is,
[z 7m.) = (2z)seT.-
In particular, for each x have
0% (x)) = (0)())) = (Vi(x))
Define
F.
Σ f o
H H(y)....,,) and
:1,) Σ F((r)).
G
JEI,
28

---

Then, using the block form in 12
R(F) =
fk. 0g.k
G
gEG k=1
P:
0b
=1jer..
Σ jEL.
H 0
H Oj.
The right-hand side is sum of terms of the form > H $j. hence it belongs to A(o Φr). Moreover, the preceding regrouping shows that ( be written in this form, R(F) A(ón A(ó1,.... oz). Therefore,
M(e 22) c A Φr). Conversely, since (
28) G-invariant by construction, have
A( oc) A .0) S M(co....... .e).
Combining the two inclusions yields
M( 62)
Finally, if / an invariant function, then by Theorem 37 and Theorem 41 have
I ( = f A σz). f E M( 00) - f E ((C
P()),...,0)) =0 for each P PEI
This concludes the proof.
13 implies that if ʃ E Un (M, N), then for any P E I(L((1) .....(((6))) P(O)...... 0x)s 0. By Remark 33 know
Proof of Theorem 14
The final part of the proof of Theorem
I(I(()) U... ... T((+)) = I(L())) n (.......II((LI)))) I(L((r)) I(L(E)))
For any a = l,..., and arbitrary ca E ker oh, note that for
Hence,
2) (c) x) I(L()1)) ... I(L(Ee)).
Whose associated differential operator can be written as Doy Dog Therefore,
Da ... Dae 0,
concluding the proof.
Proof of Theorem 15 By Proposition 42 separation-constrrinedd universality is equivalent to the
ability to approximate any function of the form F(éi,...,dy dz), where F is continuous and S;- invariant.
Recall that the basis maps are defined as
Φi (0] (o)....,
Let W R for some finite G-set Y. Since M = Aff (V, RY), we can, for suitable choice of basis, select elements aç E Y such that of eT, for each = I.

---

In particular, the function
a 2..,,, C.,
for some G R + R, is one that should be approximable under separation constraints.
Specifically, we define G as the symmetrization of the monomial
( = 2 ... ..
that is,
G(ri,..., rt)
Σ ((F ... oESt
Now, observe that then
Da Dee M #0,
Da De, G + 0
for any choice of os E ker de for some i = 1, ,,..., Therefore, F cannot be approximated by Unex-V(MEsh N).
This follows because the differential operator D., Dor reduces the degree of each monomial in G by most Thanks to the hypothesis a; + + a,+1 for each i 1....., L, and a > l, all resulting monomials in Da, ... Dec G have distinct multidegrees. In particular, De, ... Dee M, being one of these monomials and being nonzero, implies that De, De, G is itself nontrivial.
This proves that if De, ......a ... * 0, then the function F cannot be approximated by URER (M N).
By direct computation, the coefficients of the monomials of multidegree (a1 - s,,...,04 st) in Do Doc M are given by
Σ 0ig!
aip! (Co()) Co(s1).1) (Co(s1+1),2 ( Co(s1+92))2) ... (Co(
Si,
St
oES2
where 81, .1,-.., E {o....,, 81 +... 8 and i ; bn are the indices such that Siz 0. at least one of these coefficients nonzero, then Do, ... ...D.. is nontrivial and thus cannot be approximated by
Proof of Theorem
18
Define V, W. and :: W as in Corollary which states that
N(VRRO/" & R². Z) = (',
R Z)
for each h N.
Since H normal in G, the quotient G/H is group and the action of H on W is trivial W is C/H-reppeseentation, and we have the identification CW Z) (C,n(W
From Ravanbakhsh (5), it is known that shallow equivariant neural networks with the regular repre- sentation as input are universal approximators. In this case,
U N(W, G/H @ RR
MEN
universal in Co(W, Ca/H((, Z).
Furthermore, the pullback map 1" C(V,Z) C(W, Z) is continuous linear operator. Hence,
U UN(KR Rh 2)
U KEN
it NNWWW, NNWWWRGG/ G/H @ RR" Z)
KEN
C @RR,2
MEN
UNWW,RC/ 0K" 12"Z))
=
WEN
= (Ca/n(W, 2)) = (Co(W, 2))
30

---

Therefore, the left-hand side is equivariant universal as well. Finally, observe that e (W, 2)) an algebra of functions containing the constants, so is separation-constrr constrained universal by the Stone -eniesssssss theorem.
equivariant-univeraal
I
Lemma 43. Let H be normal subgroup of G and K an arbitarr subgroup of G. Consider the standard immersion map
G/ BBG/K
as the standard injection induced by the subgroup inclusion K < KH.. We define the pullback map C(RG/K G/K
Z) - C(RG/HK ,2)
f fo
for any G-representation Z.
Proof. Note that L" Home (R G/K RQ/H) S Homa(R (RG/HK RG/"), since '" is linear and pre- serves equivariance. Moreover, since is injective, the induced map is surjective.
Now, assume that is normal. Then,
dim Homg [R G/K RC/ H |HGGHK] = dim Homo BRRCC/KKKK//HHH R./HH.
This equality dimensions, together with the inclusion and surjectivity above, implies that e an isomorphism of vector spaces. In particular,
L Homg
G/K (R/K p0/")= Home HomG(RC/HK
Corollary 44.
@ BR..GRG//.. G/Ka and define W = BR.G/KKR ...... G.GGG Consider the standard immersion map :: W - V as the standard injection defined component by component and induced by the subgroup inclusion K; < K,H for i 1,...,d d. We define the pullback map
C(V, 2) + C(W, Z) - for
for any G-representation Z. Then
N(V, R/H @ RR Z) = NWW, G/H @ OR"
for any G-representation Z.
Proof. By the properties of representation homomorphisms under direct sums, we have
Homo (Vmo(V R/ @ R
Home
[ G/K,
..... + BRRG/ G/Ka R// R
Homa G/K:
RC/lishh
1=1
By the definition of i and Lemma 43
it follows that
Homa (V G/H RR*)
Home Home(W,RC/A OR²)
for each h E N. Consequently,
Aff RR) Aff ( (W, G/H OR*)
for every h N as well.
Therefore, for any G-representation Z, we obtain
NVV G/H & R 2) = NWW 3R.22)
since is precomposed with the input the first layer.
31


Reviews:
[{"review_id": "MyYpKzKOsK", "reviewer": "Reviewer_Wpwm", "summary": "This paper introduces a theoretical framework to characterize the universality of shallow equivariant neural networks, without assuming universal components like MLPs. For this, concepts of separation power of equivariant networks are leveraged and links between separation power and universality and obtained. Necessary criteria for universality are derived, along with examples of applications of these ideas to widely used architectures.", "questions": "- One component that I felt would make the story more complete for me is a characterization of conditions for $C_\\rho = C_G$, e;.g. when does separation constrained universality coincide with universality? I think this would help in understanding the implications of Theorem 18. Are results from [6] enough for this? If yes, it would be nice to include them in the discussion.\n- If I understand correctly, the framework does not fully generalize to the equivariant case, since only non-universality (and not universality) transfers from invariance to equivariance. Is that right? If yes, this should be mentioned more explicitely.", "limitations": "Limitations are discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper is well-written and overall a great read despite the heaviness of the theoretical framework and notations\n- The results of the paper generalize and extend several existing results in a non-trivial and very interesting way. They have practical implications and can be used to show explicitly if some architectures satisfy universal criteria. As such they will be useful and important to the geometric deep learning community\n- The limitations of the analysis are clearly stated\n\n## Weaknesses\n- Some related works are not mentioned, notably [1,2], which formalize concepts related to separation constrained universality for graphs. Another line of work sidesteps the issues of expressivity of equivariant neural networks by adaptation of universal architectures [3,4] and is worth mentioning. \n- The paper is clearly written, but understanding could potentially be improved by including some figures (they could fit with the additional page or in appendix). One recommendation is for example to represent the constructions for the layer spaces (equation 1) using coloured bipartite graphs as is done for example in [5] (This paper is also worth citing as it introduced a formulation close to equation 1). I think this would allow to visualize all the examples provided in the paper in an intuitive way.\n- The paper would also be improved if the authors could add short proof sketches and find some intuition that is captured by each of the main theorems. In their current form the statements are a bit dry.\n\n[1] Azizian and Lelarge, Expressive Power of Invariant and Equivariant Graph Neural Networks, 2021\n\n[2] Chen et al., On the equivalence between graph isomorphism testing and function approximation with gnns, 2019\n\n[2] Puny et al., Frame averaging for invariant and equivariant network design, 2021\n\n[3] Kaba et al., Equivariance with learned canonicalization functions, 2022\n\n[5] Ravanbakhsh et al. Equivariance through parameter-sharing, 2017\n\n[6] Pacini et al. Separation Power of Equivariant Neural Networks, 2025", "was_revised": true, "final_justification": "I acknowledge the authors rebuttal and am looking forward to see the paper with the promised changes. I am happy to recommend this paper for acceptance.", "rebuttal": "We thank the reviewer for the positive and encouraging feedback. We are pleased that the paper was found to be well-written and that its conceptual and technical contributions were appreciated. We address the reviewer’s constructive suggestions and questions below.\n\n> Some related works are not mentioned, notably [1,2], which formalize concepts related to separation constrained universality for graphs. Another line of work sidesteps the issues of expressivity of equivariant neural networks by adaptation of universal architectures [3,4] and is worth mentioning.\n\nWe thank the reviewer for highlighting the missing references. We agree that these papers are very relevant to the discussion on equivariant universality, and their inclusion will strengthen our paper. We will incorporate them in the revised version and add commentary on how they relate to our framework.\n\n> The paper is clearly written, but understanding could potentially be improved by including some figures (they could fit with the additional page or in appendix). One recommendation is for example to represent the constructions for the layer spaces (equation 1) using coloured bipartite graphs as is done for example in [5] (This paper is also worth citing as it introduced a formulation close to equation 1). I think this would allow to visualize all the examples provided in the paper in an intuitive way.\n\nWe appreciate the suggestion and will incorporate it in the revision. We agree that adding figures will enhance the paper’s readability. In particular, we will include several visual representations of the layer space constructions appearing in Proposition 9, using colored bipartite graphs, as suggested. With the additional page allowance, if the paper is accepted, we can also illustrate key examples more intuitively, helping to clarify the more notation-heavy sections.\n\n> The paper would also be improved if the authors could add short proof sketches and find some intuition that is captured by each of the main theorems. In their current form the statements are a bit dry.\n\nWe appreciate the suggestion to add brief proof sketches and intuitive explanations for the main theorems. We do recognize that the current presentation may come across as overly dry. We were constrained by space and hence the concision. In the revised version, using the additional page, if the paper is accepted, we will summarize the key ideas underlying each result, with particular emphasis on the role of the differential operators and their connection to the theory of ridge functions. This should make the results more accessible without requiring extensive background on ridge functions, which could risk making the main points more cumbersome.\n\n> One component that I felt would make the story more complete for me is a characterization of conditions for $C_\\rho = C_G$, e.g., when does separation constrained universality coincide with universality? I think this would help in understanding the implications of Theorem 18. Are results from [6] enough for this? If yes, it would be nice to include them in the discussion.\n\nThe reviewer is correct that, for the invariant case, $C_\\rho = C_G$ is equivalent to $\\rho$ being equal to the orbits. Determining when a neural space with separation power $\\rho$ yields $C_\\rho = C_G$ can be understood via Theorem 1 in [6]. Although characterization may require difficult computations depending on subtle structural constraints, the difficulty arises from the complexity of the setting and the presence of multiple factors that can influence separation power. To clarify this point, we will expand on the example of $S_n/A_n$ as the input representation and $S_n/H$ with $H < A_n$ for the hidden representation. This has been only partially discussed after Theorem 18 (L364-368). \nIn this case, we can prove that $\\mathcal U (\\mathbb R^{S_n/A_n}, \\mathbb R^{S_n/A_n}, \\mathbb R) = \\mathcal U (\\mathbb R^{S_n/A_n}, \\mathbb R^{S_n/H}, \\mathbb R) = \\mathcal C_{S_n}(\\mathbb R^{S_n/A_n})$. \nIn particular, $\\rho (\\mathcal U (\\mathbb R^{S_n/A_n}, \\mathbb R^{S_n/A_n}, \\mathbb R)) = \\rho (\\mathcal U (\\mathbb R^{S_n/A_n}, \\mathbb R^{S_n/H}, \\mathbb R))$.\nThis family of examples illustrate how different representations can induce the same separation power, and how this also depends on the input representation. \nIt points to a highly non-homogeneous, asymmetric, and somewhat counterintuitive landscape in which architectural choices influence separability. \nObtaining a characterization of when $C_\\rho = C_G$ that is significantly simpler than the one provided in Theorem 1 of [6] may indeed be infeasible. We will ensure that these observations are appropriately integrated in the revised manuscript.\n\n> If I understand correctly, the framework does not fully generalize to the equivariant case, since only non-universality (and not universality) transfers from invariance to equivariance. Is that right? If yes, this should be mentioned more explicitely.\n\nThanks for the incisive comment. If referring to Remark 11, the reviewer’s understanding is correct. Examples showing that universality does not extend from the invariant case to the equivariant case can indeed be constructed, although in our opinion they tend to be somewhat artificial. We will clarify this by adding the following counterexample and subsequent discussion:\n\nLet $V$, $W$, $Z$ be permutation representations of $G$, let $Z^G$ be the trivial subspace of $Z$ and $Z’$ be its complement, i.e., $Z = Z^G \\oplus Z’$. Define $M = \\text{Aff}_G(V, W)$ and $N = \\text{Aff}_G(W, Z’)$ and consider the universality class $\\mathcal U = \\mathcal U(M, N)$. In this case, the pullback map $\\pi^*$ defined in Remark 11 always projects $\\mathcal U$ to $\\\\{0\\\\}$ independently of the choice of $M$ and $W$. Therefore two equivariant universality classes $\\mathcal U \\subsetneq \\mathcal V$ with output layer $N$ would be projected to the same invariant class $\\\\{0\\\\}$. \n\nHowever, we will also underline how the ridge-function framework does transfer to the equivariant case. We have not emphasized this result because it is difficult to formulate a closed-form characterization analogous to Theorem 13. However, to better address this question, we find it relevant to highlight the following remarks, which we will also clarify in the revision.\n\nProposition 40 (L1017-1030) transfers without much overhead to the equivariant case by decomposing $A$ through some basis of linear maps and adding another sum in the formula at L1025.\nTherefore, the first part of the proof of Theorem 13 also transfers to the equivariant case and the differential constraint is maintained, but biimplications at L1066-1067 do not transfer since we are not assuming $f$ to be invariant. Hence, leading to a more cumbersome formulation that we omitted due to its strong dependence on representations and layer spaces."}, {"review_id": "51Fu0JELVf", "reviewer": "Reviewer_Ywy9", "summary": "Observes that we should care about more than universality “up-to-separation” of equivariant neural networks, we should also care about their capacity to approximate a function. Characterize universality for shallow models. Show that there are families of models (e.g. shallow PointNets and CNNs with a filter width of 1) that differ in their approximation capacity but have identical ability to separate inputs mod symmetry.", "questions": "- For Thm 18, Stone–Weierstrass also requires point-separation?\n- The n=3 PointNet case seemed rush. Could you perhaps add a bit more detail here.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nOffers an interesting, novel perspective on the universality of equivariant networks. Construct real examples where separation and universality differ. The proofs are relatively clear and the assumptions are generally stated.\n\n## Weaknesses \n\n- Importance: the theorems target depth-2 models. It seems non-trivial to extend to deep architectures (and motivate this distinction), in-part because compositions of equivariant layers have significant approximation capacity.\n- Similarly: is there a reason why universality captures certain intuitions better than separability and why should this matter? \n- Minor: In the conclusion, you state that you formulate shallow invariant networks as superpositions of ridge functions. You do not explicitly connect these in the main body/cite your appendix.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and for highlighting the novelty of our perspective on universality beyond separation. The comments provided have helped us refine the presentation and clarify key aspects of our framework. Our responses follow below.\n\n> Importance: the theorems target depth-2 models. It seems non-trivial to extend to deep architectures (and motivate this distinction), in-part because compositions of equivariant layers have significant approximation capacity.\n\nWe acknowledge this limitation and are in fact actively working on extending our analysis to deeper architectures. While additional examples and a more comprehensive theoretical treatment for deep networks would indeed strengthen the work, we emphasize that the examples presented already suffice to tackle the key conceptual question: “Can separation alone fully capture approximation?” Our results clearly demonstrate that the answer is no, which constitutes the main message of the paper. We consider it to be a key conceptual milestone before tackling the analysis for deeper architectures. \n\n> Similarly: is there a reason why universality captures certain intuitions better than separability and why should this matter?\n\nWe thank the reviewer for highlighting this important point. As demonstrated in our paper, separability is only a necessary condition for universality but not a sufficient one. But, for learning, universality is necessary to some extent. Indeed, as we show in the paper (L339–356), shallow PointNets cannot approximate, and therefore cannot learn, even a relatively simple function such as multiplication. This strongly suggests that more complex and realistic functions are also beyond the approximation (and learning) capacity of such models. Our goal in this paper is precisely to emphasize that this limitation cannot be resolved by considering separability alone.\n\n> Minor: In the conclusion, you state that you formulate shallow invariant networks as superpositions of ridge functions. You do not explicitly connect these in the main body/cite your appendix.\n\nWe thank the reviewer for bringing this to our attention. We agree that explicitly referencing the appendix where appropriate will improve cohesion across sections. This was an oversight, and we will ensure these references are clearly added.\n\n> For Thm 18, Stone–Weierstrass also requires point-separation?\n\nThe reviewer is correct that there are multiple formulations of the Stone–Weierstrass theorem, many of which require point separation. In our case, we employ a formulation that is separation-aware, as found in DeVore’s *Constructive Approximation* (Theorem 4.3). Moreover, note that condition (a) is always satisfied here, since $g(x) = 0$ does not hold for all neural networks due to the presence of bias terms in the output layer. We will make this reasoning more explicit in the revision.\n\n> The n=3 PointNet case seemed rush. Could you perhaps add a bit more detail here.\n\nWe thank the reviewer for pointing out that this case felt rushed. We will expand this computation in the revised version to make the argument clearer and more complete."}, {"review_id": "K6MUzz0R7o", "reviewer": "Reviewer_FKDG", "summary": "The paper revisits the relationship between approximation power and separation power for equivariant neural networks. While most prior work focuses on separation power—the ability to distinguish inputs up to symmetry—the authors ask whether networks that separate equally well can also approximate equally well. By characterizing the universality classes of equivariant networks, it shows that separation power alone cannot fully describe approximation power: models with identical separation power may differ in their approximation ability. Particularly, it exhibits three popular set models whose separation power is maximal yet whose approximation power is strictly nested.", "questions": "See **Weaknesses**.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- It was known that universal approximation implies maximal separation power. This work provides another piece, suggesting that the opposite is not true: maximal separation power does not necessarily lead to universal approximation. \n- This theoretical finding implies that function approximation power and speration power of equivalence classes are fundamentally distinct. Therefore, model analysis and architectural design should address separation and approximation as distinct criteria, instead of relying on just one of them.\n\n\n\n**Weaknesses**\n- The main theoretical results are mainly restricted to shallow networks\n- There are no empirical validations \n- The notion is heavy to read", "was_revised": true, "final_justification": "After reviewing the rebuttal and the other reviewers’ comments, I maintain my score and remain inclined toward acceptance.", "rebuttal": "We are grateful to the reviewer for engaging with our work and for recognizing the significance of distinguishing separation and approximation power. The points raised, particularly regarding scope and lack of experimental evaluation, are addressed in the following.\n\n> The main theoretical results are mainly restricted to shallow networks\n\nWe certainly recognize this limitation and are actively working on extending our analysis to deeper architectures. However, we would like to take this opportunity to emphasize the motivation for our work. We were motivated by the following question *“Is separation a complete proxy for approximation?”* Our findings clearly show that it is not, which is the central message of the paper. We consider it to be a key jumping off point for the analysis of deep architectures. \n\n> There are no empirical validations\n\nWe agree that experiments would help strengthen the soundness of the work. However, approximation cannot be directly controlled by the experimenter. It can only be indirectly influenced through factors such as hyperparameters or activation functions. These factors, however, affect not only approximation but also other critical aspects, such as generalization and trainability, which in turn impact empirical outcomes. As a result, designing experimental settings that isolate the effect of approximation power is highly challenging, since disentangling the influence of these interacting components is non-trivial.\nAn example of a possible experiment would be attempting to approximate the multiplication function with a shallow PointNet. However, it would be difficult to determine whether any failure arises from the inherent approximation limitations identified in this paper or from limitations of the optimization procedure itself.\nOnce we gain a clearer understanding of these interactions, we believe it will be possible to conduct a more detailed and meaningful experimental study. In alignment with the final part of the reviewer’s comment, we see our theoretically grounded contribution as an important first step toward understanding the learning pipeline of equivariant networks, providing a foundation for future results that can be empirically validated in a principled way.\nWe will ensure to mention these points in the revised manuscript.\n\n> The notion is heavy to read\n\nWe employ the notation introduced in Pacini et al., *Separation Power of Equivariant Neural Networks*. We understand that the notation can feel heavy, and we will make sure to address these issues by improving notation and presentation and adding illustrations as suggested by Reviewer Wpwm."}, {"review_id": "24mRF1iu6Z", "reviewer": "Reviewer_JeQC", "summary": "In this paper, the authors study the universality of equivariant neural nets, and particularly its relationship with their separation power, that is, their ability to distinguish elements in different equivalence class. After a (lengthy) introduction on the different notions, they exhibit an example of networks that have the same separation power for point clouds, but different universality (one is universal, the others are not). Their main theorems pertains to necessary/sufficient conditions for universality or failure thereof, and the vanishing of certain differential operators on classes of function.", "questions": "See above, mostly related to invariance vs. equivariance and other examples of \"true\" constrained separability (the given example uses maximal separability).", "limitations": "Limitations are appropriate.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength\n- this negative results are quite original in this active literature. I believe that, at least the concept, is an important step towards a better understanding of separation, universality, and the building of invariant/equivariant architectures with such properties.\n\nWeaknesses\n- the main weakness of the paper is that it is extremely notation-heavy and quite hard to parse. It' feels like each line introduces new notations up until the very end, making the results quite obfuscated and hard to judge. Examples, main theorems, etc. feel rushed: for instance, one of the main theorem is about differentiability, and this notion is never introduced before the theorem itself! I feel like this paper would really benefit from being journal length, or from being in a much more focused and example-heavy way.\n\n- with so many notations, some of them clash, eg $M_d$ and $M_h$ with integers $d$ and $h$, and some are redundant, I believe neural nets are re-defined many times along the way. It's very easy to lose track.\n\n- proposition 9 is the core of the idea and it is a bit confusing. width-1 convolutional networks are mixed with permutation-invariance (which is weird), and the proof is quite confusing, for such seemingly simple architectures. Examples like this should be more explicitely written.\n\n- related to this, another weakness is that, as of now, all the notions and theorems feel a bit too \"heavy\" for the rather simple counter-example that is the core of the authors' demonstration. For instance, the authors introduce a quite convoluted notion of \"separation class\" and \"separation-constrained universality\", and then only apply it to maximal separation over point clouds. Could other, less trivial examples be found?\n\n- The authors claim that equivariance can be summarized to invariance, but it seems a bit imprecise. They correctly that, *for negative results*, this is the case; of course failure to be invariant-universal is also failure to be equivariant-universal. But the converse is a bit brushed off.\n\n- A large branch of proofs of universality precisely proves it by using separability + Stone-Weierstrass theorem. It could be useful to include it in a remark.\n\nIn conclusion, I believe this paper starts an important line of results, but would really benefits from being longer, with more examples that are less trivial, and more time to discuss the two \"main\" theorems, which are rushed at the end of the paper used notions that were not introduced in the rest of the paper.", "was_revised": true, "final_justification": "I keep my positive view of this paper, despite some heaviness in the notations.", "rebuttal": "We thank the reviewer for the detailed comments and for recognizing the conceptual importance of our results. We agree with the suggestions regarding clarity and presentation, and we provide detailed responses below.\n\n> the main weakness of the paper is that it is extremely notation-heavy and quite hard to parse. It' feels like each line introduces new notations up until the very end, making the results quite obfuscated and hard to judge. Examples, main theorems, etc. feel rushed: for instance, one of the main theorem is about differentiability, and this notion is never introduced before the theorem itself! I feel like this paper would really benefit from being journal length, or from being in a much more focused and example-heavy way.\n\nWe thank the reviewer for the comment and acknowledge the concern raised. The terseness was indeed because we were constrained by space. We are confident that a single additional page will be sufficient to present the essential missing material in a complete and accessible manner. Further technical developments, such as an extended treatment of ridge functions or detailed arguments relying on this theory, would not enhance the paper’s readability and, even in a journal version, would be more appropriately placed in an appendix.\nMoreover, we plan to include figures to visualize the constructions, clarify key examples, and add brief proof sketches to enhance comprehension, both in depth and breadth, as suggested by Reviewer Wpwm.\nWe also believe that these results would be of interest to the NeurIPS community and that the timely dissemination enabled by the conference format would provide greater benefit to the community. \n\n> with so many notations, some of them clash, eg $M_d$ and $M_h$ with integers $d$ and $h$, and some are redundant, I believe neural nets are re-defined many times along the way. It's very easy to lose track.\n\nThe reviewer is right. We will change the notation by clearly distinguishing between $M_d$, $M_h$, and $N_h$ (which is indeed defined differently from $M_h$).\n\n> proposition 9 is the core of the idea and it is a bit confusing. width-1 convolutional networks are mixed with permutation-invariance (which is weird), and the proof is quite confusing, for such seemingly simple architectures. Examples like this should be more explicitely written.\n\nWe understand that the reviewer found these examples confusing. To address this, we now clarify the discussion by presenting it in two separate parts:\n- First, we agree that it may seem unusual to discuss convolutions in the context of permutation invariance rather than translation invariance, which is a weaker constraint. However, when the filter length is 1, the convolution reduces to a scalar multiple of the identity which is a permutation equivariant operation. \nBy composing such layers with a final invariant layer, one obtains a permutation-invariant network, which is obviously also translation equivariant. \nNonetheless, other translation-equivariant models, constructed using larger filters, do not necessarily preserve permutation equivariance. \nIn Proposition 9 and 16, our focus is on constructing minimal working examples of separation-constrained universality failure; thus, restricting to permutation equivariance and filters of length 1 was a natural choice.\nBeyond the case of permutation equivariance, we emphasize that the characterization of universality classes provided in Theorem 13, which we regard as a central contribution of our work, applies to arbitrary equivariant layer spaces. This level of generality, however, comes at the expense of notational simplicity.\n\n- Second, we recognize that the entire proof of Proposition 9 may feel unexpectedly complex given the simplicity of the architectures involved. \nHowever, we emphasize that the most technically involved part of the proof lies in Proposition 41, whose complexity stems from the generality of the result, which applies to arbitrary layer spaces.\nAlthough Proposition 41 appears only in the appendix, we believe that its generality makes it an important contribution, even if technical. We will make this clearer and more explicit in the revision.\n\n> related to this, another weakness is that, as of now, all the notions and theorems feel a bit too \"heavy\" for the rather simple counter-example that is the core of the authors' demonstration. For instance, the authors introduce a quite convoluted notion of \"separation class\" and \"separation-constrained universality\", and then only apply it to maximal separation over point clouds. Could other, less trivial examples be found?\n\nThe notation, while admittedly dense, is necessary to formally state and prove the general theory, in particular Theorem 13 and Theorem 18. We will ease the reader in by simplifying some of the notation in the revision.\nAt present, we do not have less trivial examples beyond those already included. Nevertheless, we emphasize that the existing example is sufficient to give a negative answer to the broader question *“Does separation imply approximation?”*. \n\n> The authors claim that equivariance can be summarized to invariance, but it seems a bit imprecise. They correctly that, for negative results, this is the case; of course failure to be invariant-universal is also failure to be equivariant-universal. But the converse is a bit brushed off.\n\nWe agree with the reviewer’s comment and will address it carefully in the revision, showcasing the following technical details:\n\nThe converse implication of Remark 11 does not generally hold. It is possible to construct counterexamples in which the invariant setting fails to inform about to the equivariant case, although such examples are often somewhat contrived. To clarify this, we plan to include the following in the revision: let $V, W, Z$ be permutation representations of a group $ G $, and write $Z = Z^G \\oplus Z'$, where $Z^G$ denotes the space of invariant vectors and $ Z' $ its direct complement. Consider the layer spaces $M = \\mathrm{Aff}_G(V, W)$ and $N = \\mathrm{Aff}_G(W, Z')$, and define the universality class $\\mathcal{U} = \\mathcal{U}(M, N)$. Then, by construction, the pullback map $\\pi^* $ introduced in Remark 11 maps all functions in $\\mathcal{U}$ to $\\\\{ 0 \\\\}$, regardless of the choice of $M$ and $W$. This means that different equivariant universality classes with outputs in $Z'$ are collapsed on $\\\\{ 0 \\\\}$ by projecting through $\\pi^*$ onto $ Z^G $, hence indistinguishable from the invariant perspective.\n\nThat said, we want to emphasize that our ridge-function-based formulation does extend to the equivariant setting and can be employed to tackle the example discussed above. We did not highlight this extension in the main text because it does not yield a clean analog of Theorem 13. Nevertheless, to clarify this point, we will expand on the following: Proposition 40 (L1017–L1030) generalizes to the equivariant setting with minor adaptations, namely by expressing the matrix $A$ in terms of a suitable basis of equivariant maps and adding a sum at L1025. As a result, the first part of the proof of Theorem 13 continues to apply, and a differential constraint still characterizes the class. However, the equivalence in lines L1066–L1067 no longer holds in the equivariant case, since $f$ is not assumed to be invariant. This leads to a more complex formulation that depends explicitly on the output representation and the structure of the final layer, which is why we chose to omit it in the current version.\n\n> A large branch of proofs of universality precisely proves it by using separability + Stone-Weierstrass theorem. It could be useful to include it in a remark.\n\nThe reviewer is correct that a large portion of the literature focuses on separability combined with the Stone–Weierstrass theorem. In the revised version, we will add a dedicated remark discussing this perspective. Here, the key observation is that the classical Stone–Weierstrass argument does not apply here, as the function families under consideration, such as PointNets, do not form an algebra."}, {"review_id": "Qfaojjs2J5", "reviewer": "Reviewer_ETMU", "summary": "This paper provides a theoretical investigation into the approximation capabilities (universality) of equivariant neural networks, arguing that this property should be considered distinct from the more commonly studied separation power. The authors develop a framework for analyzing the universality classes of shallow invariant networks by connecting them to the theory of generalized ridge functions. This framework characterizes the functions a network can approximate via a set of differential equations they must satisfy.\n\nThe main contribution is a formal characterization of the universality classes for shallow invariant networks, and a demonstration for concrete examples (shallow CNNs and PointNets), that models with identical separation power can have different approximation capabilities. This directly shows that separation power is not a complete measure of expressivity. Further, the authors generalize prior universality results and show that shallow networks can be universal if the symmetry group possesses suitable normal subgroups, a condition that highlights structural limitations for important cases like the permutation group.", "questions": "1. The results clearly highlight the limitations of shallow permutation-equivariant networks. You contrast this with prior work showing depth-3 PointNets are universal. Could you speculate on how your analytical framework could be extended to deeper networks? Would a recursive application of the differential operator analysis for each layer be sufficient, or would a fundamentally different approach be necessary?\n2. Your results suggest that for groups like $S_n$, standard shallow equivariant layers are not universal. What are the practical takeaways for an ML engineer designing a permutation-equivariant model? Should they always build deep models? Or does your theory suggest alternative designs for the hidden layers that could achieve universality even with limited depth?\n3. Instead of strictly enforcing symmetry by a particular architectural design, an alternative approach is to use an unconstrained architecture and learn the symmetries of interest from (augmented) data. Assuming such a model has learned the symmetries sufficiently well (i.e. it is approximately equivariant), would it have similar limitations? Phrased differently, is it possible to derive a sort of \"tradeoff\" between achievable approximation accuracy and equivariance for a (shallow) unconstrained model?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper's central message (separation power does not fully capture expressivity) is a nice conceptual contribution to the field. Much of the theoretical work on GNNs and other equivariant models has focused on separation, often using it as a proxy for overall expressivity. This paper convincingly demonstrates the limitations of that view.\n2. The authors build a rigorous mathematical framework leveraging sophisticated tools from approximation theory (specifically, the theory of ridge functions and their characterization via differential operators). The main theorems are precise, and the proofs provided in the appendix appear sound to me (although I did not check everything carefully).\n\n**Weaknesses**\n\n1. The analysis is limited to shallow networks. While this is a necessary starting point for a deep theoretical analysis, it remains a key limitation. The authors point out that depth can be crucial for achieving universality in practice, but how exactly the interplay between depth, separation, and approximation power unfolds in deeper models remains a major open question.\n2. The main characterization theorem (Theorem 13) and its corollaries are elegant but highly technical. For a practitioner wanting to analyze a new architecture, verifying the required conditions could be very challenging. The primary value of the theory may lie more in the conceptual insights it provides than as a plug-and-play analysis tool.\n3. The fact that the paper is highly technical and dense in theory makes it comparatively hard to read. Given the topic, this is unavoidable to some degree, but I think the paper could benefit from illustrations that allow readers to develop an intuition about relevant concepts.", "was_revised": true, "final_justification": "The authors acknowledge the weaknesses I pointed out, but there are no immediately obvious ways to address all of them. I think this is fine, as this contribution is an important first step. The work would of course be more impactful with extended results (which is why I keep my rating at 4), but I think it is legitimate to leave them for future work.", "rebuttal": "We appreciate the reviewer’s thoughtful assessment and the recognition of the theoretical contribution and broader relevance. The questions and suggestions raised are addressed point by point in what follows.\n\n> The analysis is limited to shallow networks. While this is a necessary starting point for a deep theoretical analysis, it remains a key limitation. The authors point out that depth can be crucial for achieving universality in practice, but how exactly the interplay between depth, separation, and approximation power unfolds in deeper models remains a major open question.\n\nWe agree that restricting the analysis to shallow networks is a limitation. However, we would like to emphasize that even within this setting, our results already answer the central question: *“Is separation a complete proxy for approximation?”* The negative examples we provide show that it is not, which is the main takeaway of the paper. With these results in place, we are now actively working on extending the analysis to deeper architectures.\n\n> The main characterization theorem (Theorem 13) and its corollaries are elegant but highly technical. For a practitioner wanting to analyze a new architecture, verifying the required conditions could be very challenging. The primary value of the theory may lie more in the conceptual insights it provides than as a plug-and-play analysis tool.\n\nWe truly appreciate the reviewer’s remark on the elegance of the results and we acknowledge that the paper may resonate more strongly with researchers than with practitioners. Rather than a limitation, we see this as a defining feature of theory, whose purpose is to clarify concepts and provide the foundations of further investigation. \nIn this respect, we believe that the conceptual insights provided here can ultimately benefit both research and practice, even without offering direct plug-and-play tools. \n\n> The fact that the paper is highly technical and dense in theory makes it comparatively hard to read. Given the topic, this is unavoidable to some degree, but I think the paper could benefit from illustrations that allow readers to develop an intuition about relevant concepts.\n\nWe share the reviewer's concerns but, unfortunately, proving these statements necessarily required introducing some theoretical machinery. However, we will eventually use the additional page to include some further commentary to motivate and explain the results. We will add illustrations to improve readability and take advantage of the additional page to do so, as suggested by Reviewer Wpwm. Furthermore, we plan to add proof hints and additional small examples to better guide the reader through the technical details.\n\n> The results clearly highlight the limitations of shallow permutation-equivariant networks. You contrast this with prior work showing depth-3 PointNets are universal. Could you speculate on how your analytical framework could be extended to deeper networks? Would a recursive application of the differential operator analysis for each layer be sufficient, or would a fundamentally different approach be necessary?\n\nWe are currently investigating a recursive approach. However, we are already encountering significant complications even in the three-layer case. In particular, it is not yet clear how the associated differential operators behave under composition, as the standard chain rule becomes substantially more intricate in this setting. For now, we are focusing on the three-layer case as a natural first step toward a recursive strategy, while remaining open to alternative techniques should this direction prove unfruitful. Since these are preliminary efforts which do not have yet yielded concrete results, we do not plan to mention in the paper.\n\n> Your results suggest that for groups like $S_n$, standard shallow equivariant layers are not universal. What are the practical takeaways for an ML engineer designing a permutation-equivariant model? Should they always build deep models? Or does your theory suggest alternative designs for the hidden layers that could achieve universality even with limited depth?\n\nAs a simple *heuristics*, we would suggest practitioners to rely on depth as the easiest and most computationally efficient way to improve approximation power based on [3], which shows that 3-layer PointNets are universal, and [2], that shows that depth may increase separation power.\nHowever, it is worth to note that this suggestion remains a heuristics since, in our knowledge, there exists no work characterizing the role of depth in separation-contrained approximation.\n\nThat said, we are aware that in popular equivariant models, such as graph neural networks, increasing depth can harm learning due to oversmoothing and oversquashing. A practitioner encountering these phenomena may need to explore alternative hidden representations and here our contribution is a *theoretically-grounded* guide in the choice of a more expressive model, depending on the representations involved. In particular, Theorem 18 shows that representations coming from normal subgroups achieve separation-constrained universality, while Proposition 16 provides examples of subgroups or layers that do not. To assess expressivity for any particular case not covered in the previous examples, it is necessary to directly apply Theorem 13.\n\n> Instead of strictly enforcing symmetry by a particular architectural design, an alternative approach is to use an unconstrained architecture and learn the symmetries of interest from (augmented) data. Assuming such a model has learned the symmetries sufficiently well (i.e. it is approximately equivariant), would it have similar limitations? Phrased differently, is it possible to derive a sort of \"tradeoff\" between achievable approximation accuracy and equivariance for a (shallow) unconstrained model?\n\nThis is a highly relevant question whose answer is still the object of active research by the community. We believe that the next points to be relevant directions toward an answer:\n- A standard MLP can approximate functions such as multiplication arbitrarily well, whereas shallow PointNets cannot achieve this (as shown in Proposition 16). However, PointNets may still approximate such functions on a restricted domain up to a prescribed approximation error. This can be interpreted as a trade-off between equivariance, parameter efficiency, and universality; a direction we are actively investigating.\n- We are also currently validating results for MLPs that can exactly represent an equivariant network. Relaxing this setting to allow approximate representation is the next step we plan to investigate. In particular, we are exploring this direction in terms of the trade-off between parameter efficiency and approximation power.\n- Finally, it is worth noting that learning dynamics play a crucial role in the broader learning process, beyond approximation alone. Equivariant constraints may indeed act as a barrier to the learning dynamics, as highlighted in [1]. \n\n---\n\n[1] YuQing Xie, Tess Smidt, A Tale of Two Symmetries: Exploring the Loss Landscape of Equivariant Models, 2025\n\n[2] Pacini et al. Separation Power of Equivariant Neural Networks, 2025\n\n[3] N. Segol et al., On Universal Equivariant Set Networks, 2020"}]

Author rebuttal:

Meta-review: The paper theoretically studies the expressive power of equivariant neural networks, presenting several important results. The reviewers appreciated this contribution and assigned positive scores. I am happy to recommend acceptance as a spotlight presentation.
Decision: Accept (spotlight)