Decomposition of Equivariant Maps via Invariant Maps: Application to Universal Approximation under Symmetry.
Authors: Akiyoshi Sannai
Yuuki Takai
Matthieu Cordonnier
Venue: Accepted by TMLR ()

Abstract: In this paper, we develop a theory about the relationship between invariant and equivariant maps with regard to a group $G$. We then leverage this theory in the context of deep neural networks with group symmetries in order to obtain novel insight into their mechanisms. More precisely, we establish a one-to-one relationship between equivariant maps and certain invariant maps. This allows us to reduce arguments for equivariant maps to those for invariant maps and vice versa. As an application, we propose a construction of universal equivariant architectures built from universal invariant networks. We, in turn, explain how the universal architectures arising from our construction differ from standard equivariant architectures known to be universal. Furthermore, we explore the complexity, in terms of the number of free parameters, of our models, and discuss the relation between invariant and equivariant networks' complexity. Finally, we also give an approximation rate for $G$-equivariant deep neural networks with ReLU activation functions for finite group $G$.

Published in Transactions on Machine Learning Research (09/2024)
Decomposition of Equivariant Maps via Invariant Maps: Application to Universal Approximation under Symmetry
Akiyoshi Sannai*
sanmai.akiyoshi. wot.
Department of Physics, Kyoto University, RIKEN Kilashérukawa, Sakyo, 606-8502, Kyoto, Japan
Yuuki Takai'
Kanazawa Institute of Technology 7-1 Ohgigaoka, Nonoichi, 921-8501, Ishikawa, Japan
Matthicu Cordonnier
matthieu. matthiew.cortommieer@pppppaaaaa
GIPSA-lab Grenoble INP, Grenoble INP, Université Grenable Alpes
11 rue des Mathématiques, Grenoble Campus BP46, F-98402 SAINT MARTIN D'HERES CEDEX, France
Reviewed on OpenReview: https: // openreview. net/ forum? id= ddycOLLythiUe
Abstract
In this paper, we develop a thoory about the relationship between invariant and equivariant maps with regard a group G. We then leverage this theory in the conlext of deep neural networks with group symmetries in order to obtain novel insight into their mechanisms. More precisely, we establish one-to-one relationship between equivariant maps and certain invariant maps. This allows us to reduce arguments for equivariant maps to those for invariant maps and vice versa. As application, propose construction of universal equivariant architectures built from universal invariant networks. We, in turn, explain how the universal architectures arising from our construction differ from standard equivariant architectures known to be universal. Furthermore, we explore the complexity, in terms of the number free parameters, of our models, and discuss the relation between invariant and equivariant networks' complexity. Finally, we also give an approximation equivariant deep neural networks with ReLU activation functions for finite group G.
for G-
1 Introduction
Symmetries play a fundamental role in many machine learning tasks. Incorporating these symmetries into deep learning models has proven be successful strategy in various contexts. Notable examples include the use of convolutional neural networks (CNNs) address translation symmetries (LeCun et al., 2015; Cohen & Welling, 2016), deep sets and graph neural networks for permutation symmetries (Zaheer et al., 2017; Scarselli et al., 2008; Kipf & Welling, 2017; Defferrard et al., 2016), and spherical CNNs for rotation symmetries (Cohen et al., 2018; Esteves et al., 2020). The underlying common principle in all these cases is as follows: once the inherent symmetries of a target task are identified, the learning model is designed to encode these symmetrics. In doing so, we aim to improve the quality of learning by building model that fits the characteristics of the task better.
In mathematics, symmetries are represented by the concepts of groups and group actions. group is a set of transformations, and the action of group results in transformation of a given set. The symmetrics of group actions are usually divided into two categories: invuriand tasks and equivariant tasks. Incoriiant
Bott authors contributed equally to this research. This work includes results obtained while the author was affiliated with the Matsuo- Matsno-Iwasawa Iwasawa Laboratory at The University of Tokyo, Japan.

---

Published in Transactions on Machine Learning Research (09/2024)
tasks require the output to remain unchanged by any transformation of the input via the group action. On the other hand, in equivariant tasks, transformation of the input results in similar transformation of the output. For example, in computer vision, object detection is an invariant task whereas image segmentation is an equivariant task with regard to rotations and shift transformations.
Despite appearing tasks of different natures, there are some mathematical relations between invariant and equivariant maps. One can easily verify that the composition of an equivariant map followed by an invariant one results in an invariant map. This relation is at the core of convolutional architectures, which consist of layers made of an equivariant convolution followed by invariant pooling (LeCun et al., 2015). The same is done by Maron et al. (2019b; 2020) to define G-invariant networks for finite group G.
In this paper, we explore the relation between invariant and equivariant maps. Our main result Theorem 1 states that for a given group G acting on a set, there a one-to-one correspondence between G-equivariant maps and H,-invariant maps, where the H; are some stabilizer subgroups of G. This allows us reduce any equivariant tasks to some invariant tasks and vice versa.
As a main application of Theorem 1, we study universal approzimation for equivariant maps. The universal approzimation theorem (Pinkus, 1999), which is fundamental in deep learning, asserts that any reasonably smooth function can be approximated by an artificial neural network with arbitrary accuracy. In the presence of symmetries, we enforce the neural network architecture to match the symmetries of the target tasks, and, by doing 80, we significantly reduce the hypothesis class of neural networks. Naturally, it essential to ensure that the universal approximation property is not compromised.
It turns that the universal approximation problem is more involved in the equivariant than in the invariant setup. Indeed, for the symmetric group of permutations of n elements S,, Zaheer et al. (2017) showed that the DeepSets invariant architecture is universal via representation theorem which is famous as a solution for Hilbert's 13th problem by Kolmogorov (1956) and Arnold (1957). However, they do not provide such a thcoretical guarantce for their equivariant architccture. Their result for invarianco was then exlended to more general groups by Maron et al. (2019b) and Yarousky (2022), but it another series of papers which later solved the equivariant case, each with their own techniques (Keriven & Peyré, 2019; Segol & Lipman, 2019; Ravanbakhsh, 2020).
Using our decompasition Theorem 1, propose, in Theorem 2 an alternative way to build universal Geeqivvariant architectures via H--invariant maps for some suitable subgroups H; C G. As we explain in Remarks and 2, the equivariant universal approximator that we obtain is different from others in the literature.
As a second application of our main theorem, we examine the number of parameters as well as the rate of approximation by invariant/ ceraannt/qqvvvaeee /equivrrininttt neural networks with ReLU activation. In Theorem 3, we provide both lower and upper bounds on the minimal number of parameters required to approximate map to given accuracy with regard to the minimal number of parameters required to approximate an invariant map in that same accuracy. Finally, in Thcorem 4 and Corollary 1, we give an approximation rate for G-equivariant neural networks among G-equivariant functions with Hölder smoothness condition. This last result is an extension of a result from Sannai et al. (2021) from S, to any finite group G.
equivariant
1.1 Contributions
Our contributions are summarized as follows:
We introduce relation between invariant maps and equivariant maps. This allows us to reduce some problems for equivariant maps to those for invariant maps.
We apply the relation to constructing universal approximators by equivariant deep neural network models for oquivariant maps. Our models for universal approximators are different from the standard models, such as the ones from Zaheer et al. (2017) or Maron al. (2019a). However, the number of parameters in our models be very small compared to the fully connected models.
2

---

Published in Transactions on Machine Learning Research (09/2024)
As other applications of the relation, we show some inequalities among invariant and equivariant deep neural networks regarding their ability to approximate any invariant and equivariant continuous maps, respectively, for a given accuracy. Moreover, we show an approximation rate of G-invariant and G-equivariant ReLU doep neural networks for clements of a Hölder space.
1.2 Related work
Symmetries in machine lcarning Symmetrics have been considered since the early days of machine learning by Shawe-Taylor (1989; 1993); Wood & Shawe-Taylor (1996). In contemporary deep learning, they keep generating increasing interest following seminal works from Kondor (2008); Gens & Domingos (2014); Qi et al. (2017); Ravanbakhsh et al. (2017); Zaheer et al. (2017). The most commonly encountered symmetries involve translations, addressed by convolutional architectures (LeCun et al., 2015) and their generalization to arbitrary compact groups (Cohen & Welling, 2016; Kondor, 2008); rotations (Cohen et al., 2018; Esteves et al., 2020); as well as permutations. The latter are particularly relevant for set data (Zaheer et al., 2017; Qi et al., 2017; Maron et al., 2020) as well as for graph data via most of the graph neural network architectures (Scarselli et al., 2008; Defferrard et al., 2016; Kipf & Welling, 2017; Bruna et al., 2014). Permutation symmetries are also present in modern Transformers of architectures, via self attention (Vaswani et al., 2017) and positional encoding. Recent extension of Transformers for graph learning as proposed by Kim et al. (2021), utilize Laplacian eigenvectors for positional encoding features. Thus, to address ambiguity in eigenvector choices, Lim et al. (2023) recently proposed an architecture that is invariant to change of basis in the eigenspaces. Villar et al. (2021; 2024) are interested in the symmetries arousing from classical physics and the distinction between "passive symmetries" coming from physical law and being empirically observed, and "passive symmetries" " coming from arbitrary choice of cesign such as labeling of elements of a set or nodes of a graph. Regarding the connection between invariant and equivariant maps, this work is a direct follow-up of Sannai et al. (2019). The methods and results from Theorems 1 and 2 extend the content. of Sannai et al. (2019) from the symmetric group Sn to an arbitrary group. More recently, Blum-Smith & Villar (2023) explain how to build equivariant maps from invariant polynomials using invariant thcory. Finally, we shall mention that invariant/ invariant/equivariantt equivariant deep learning is now a fast growing field with a plethora of various architectures. Some researchers have recently proposed to unify most of existing approaches through a general framework known as Geometric Deep Learning (Bronstein et al., 2021).
Symmetries and universal approximation Universal Approximation property is fundamental classical deep learning, extensively studied since the pioneer works by Cybenko (1989); Hornik et al. (1989); Funa- hashi (1989); Barron (1994); Kūrková (1992); Pinkus (1999) and more and further explored by Sonoda & Murata (2017); Hanin & Selkke (2017); Hanin (2019). Concerning invariant architecture, Yarotsky (2022) observed that it is straighttorward to build a universal invariant architecture from universal classic architec- ture just by group averaging when the group is finite. However, this is unfeasible for large groups such as Sn. Additionally, this issue was recently addressed by Sannai el al. (2024) who showed that, it can sometimes be enough to average over subset of the group rather that the entire group. By doing so, they are, for instance, able to reduce the averaging operation complexity from O(n!) to O(n2) in the case of graph neural networks. Zaheer et al. (2017) prove universality of DeepSets via representation theorem from Kolmogorov (1956) and Arnold (1957) coupled with a sum decompasition. The effectiveness of this universal decompo- sition for continuous functions on sets is discussed by Wagstaff et al. (2022), who argue that the underlying latent dimension must be high-dimensional. Recently, Tabaghi & Waag (2023) improved the universality result from Zaheer et al. (2017). Some generalizations to other groups have been proposed by Maron et al. (2019b) and Yarotsky (2022), and universality of some invariant graph neural networks was proved by Maron et al. (2019b) and Keriven & Peyré (2019).
In the case of equivariant networks, Keriven & Peyré (2019); Segol & Lipman (2019); Ravanbakhsh (2020) established universality results for finite groups using high order tensors. More recently, Dym & Maron (2021) suggested a universal architecture for rolation equivariance and Yarotsky (2022) for the semii-direct product of R² and (R) (translation plus rotation). In this paper, we propose circumventing the challenge of directly addressing cquivariant universality by constructing equivariant universal architectures directly from invariant networks, known to be universal, via our decomposition theorem. The resulting architecture differs from oehers in the literature, as explained in more details in Remarks 1 and 2.
3

---

Published in Transactions on Machine Learning Research (09/2024)
2 Preliminaries
In this section, we review some notions of group actions and introduce invariance/eqqiivriinee for maps. In Appendix A, we summarize some necessary notions and various examples for groups.
For sets X and V, we consider the set Map(X, V) = v = [f: X + V} of maps from X to V. In many situations, we regard X as an index set and V as a set of objects (such as channels or pictures). We show some examples.
Example
......................... n and V R, then Map(X, V) is idenfied with R" by Map(X, R=: (10))
(1)
(ii) Let E, m be positive integers, and X = (1,2..... x f1.2..... mz and V = {0, (,....... 255}². Then, Map(X, V) can be regarded as the set of digital images of E m pixels with the RGB color channels. For Map(X, V) and (i.j) E X, f(i.j) Vigs,9i,,bb b,y) (reg, big (1, 255)) represents RGB color al (i,j)-th pivel.
(iil) Let V c CVX be a set of some digital images as in Example 1(61) and X' = 21, n}. Then, Vix' the set of n-tuples of the digital images in V"
(iv) For X = R2 and =R, Map((R, = (RR)RR² can be regarded as the space of "ideal" images. Here, the "ideal" means that the size of the image is "infinitely extended" and the pizels of the image are "infinitely detailed" in the sense of Yarotsky (2022). This is a similar notion to the set I (RR" R of the "signals" introduced in Yarotsky (2022, Section 3.2).
Next, we consider a group action on the set VX Let G be group and X be a G-set, i.e., a set on which G acts from the left. Then, G also acts on VX from the left for any set V by
fx)
f(o-111)))
(1)
for f E V and a E G. For f VX, let O, be the G-orbit type of action are listed below.
(-ooo- A few examples of such
Example 2.
(i) The permulation group Sn of the set X = (1, nn acts on X by permulation. Any unordered set (21, U2,...,,, of n elements of V can be regarded as an Sw-orbit of the ordered n-tuple (1), U2,...,u,) E VV for X = =1,2, ,n.
(ii) The Sn-orbit of an element f in M ... .,, R2) can be regarded as point cloud consisting of n points in R33
(iii) Let X= = (1, ....................... .n2 and V R. We consider the diogonal Sa-action (i.j) (o(i), (o Sn)) X. Then, S. also acts on Vx Rax= Let Sym(n) be the subset of symmetric matrices in Ruxn, This Sym(n) is stable by the diagonal action of Sn. The Sn-orbit S, A of E Sym(n) C Raxa can be regarded as an isomorphism class of undirected weighted graph. Indeed, Sym(n) is the set of adjacency matrices of undirected weighted graphs, and two graphs are isomorphic if and only if the corresponding adjacency matrices A1, A2 satisfy A = 5 Ag for an element o E Sn.
We define invariant and equivariant maps as follows:
Definition 1. Let G be a group, X.Y be two G-sets, and V.W be two sets. Then, a map F from VX to W is G-invariant if F satisfies F(a- f) = F(f) for every a E G and f f V. map F from VX to WY is G G-equivariant if F satisfies F(a. . f) = a F(J) for every a E G and JEVX, We denole
Inve(V* .w = (F: VX + W| G-invariant).
and
Equiv - = ( W G-equivariant)
"Acting from the left mcans that for any a, C G, the formula (T. (aT) holds. To ensure this, we must a-1, rather than a, on the right-hand part of equation (1). Otherwise we would have (7 f) (Ta)- f.
4

---

Published in Transactions on Machine Learning Research (09/2024)
Some examples of invariant equivariant tasks are the following Example 3. (i) Let = Y = f1,2,...,,1 nn and V = R² The classification task of point clouds can be regarded as a task to find an appropriate Sn-tneoriant map from Vx to a set of classes == (..,.2......
(10) lask of anomaly detection from n pictures is a permulation equivariant lask as in Zaheer et al. (2017, Appendia 1). This is to find an appropriate Sn Sn-equivariant map VX WY for W {0, 1], and X = n1)..
V = (f0, ((0,I....,,00) 255]37exm, (50,1,...,55533)cc.
(wi) A lask of classification of digital images of l x E pizels is finding on appropriale 90-degree rolation invariant map VX to set of classes W = {c1, (mm.,,,,,, where V {0, ,,,,,,............... 255), and X (1.2..... .12. An image segmentation task can be regarded as finding an appropriate de-reee rolation equivariant map VX to WY for the same V, W, as Example 3 (ii) and Y 11, e}²
(it) An extension of Example 3 (iii) to "ideal images" is finding an 502 502((RR-im)) (I)-iirariian map from VX to W (or SO₂(RR -D)(()-eeuvvariant map from VX to WY) for and X = R2, V =R², and W IR for X Y R2, TR',, and W R respeclively).
3
enariaant-eqiiaariian relation and universal approximation
3.1 Warm up example with S,
We begin this section with warm-up example. In this subsection, G = Sn, X (1...,,n and V, W are generic sets. We denote as f an element of VX The action of S, on VX is as in equation (1)
(o) = (O), A 1 ssisn,
(2)
and so is the action of Sn on wx Let F be a map from V to W then there exist n maps Fi...., Fn from VX to W such that
F(f(1) = =(()), visisn.
(3)
F is just a shorter notation for the map F())(). Now let us make the assumption that belongs to Equivs, (VX, W the equivariance property F(a f) = a (F())) implies for all i,
Píaa . f) = (f)
(4)
Let us focus on = Notice that if a permutation such (1) 1, it is straightforward from equation (4)
that fo- = (f) for all f yx, Since it is fairly known that the of permutations such that a1) 1
is subgroup of Sn, denoted Stabs,, (1), (this group is isomorphic to S,-1), we deduce from equation (4) that
F F() E InVstabg, (1)(V* W).
(5)
Moreover, if we let (1 be the transposition that exchanges 1 and i and fix any other j E X, we obtain easily from equation (4) that for all f
Fi((L f)= Fo (f)
(6)
To sum up, we have almost proven the following claim.
Proposition 1. F E Equivs, (VX, WX) if and only if there exists Fi E InVVstabs, (i) W) such that for all f E VX, for io n,
F()()= = (( i).
(7)
Proof. The discussion above a proof of the nontrivial implication. Reciprocally, one easily verifies that picking Fi InVstaby, (V)(VX W) and defining F: yx W by
F(f()) (1 i)-
yields map F Equiv s. (VX, WxX.
The rest of this section is dedicated generalization of this result to generic group G.
5

---

W) Published in Transactions on Machine Learning Research (09/2024)
3.2 Invariant-equiivriian relation
Our main theorem is relation between G-equivariant maps and some invariant maps for some subgroups of G. Recall that, for any y in a G-set Y, its stabilizer, denoted as Staba is the subgroup of all the G such that a y = y (sce the recall en groups and group actions in Appendix A).
Theorem 1. Let G be a group and X,Y be two G-sets. Let V, W be two sets. Let Y = Liker On be the Then, the following map is
G-orbit decomposition of Y. We fix system of representatives {y, E E E bijective:
T: Eq (VX)
Ili InV (VX, W)
F
Φ(F) = (F()
Moreover, its inverse map
V Nhr (T) (VX, - Equiv wx)
(Fi)ier
- v (FiieE))
is defined by
V ((i)se))) (f)(v) Fi(o (5l0-10 f),
(8)
for any f E VX and y E Y such that Og, and -² Yi for some G.
In addition, if V and W are vector spaces over R then Vx, W Equiv Equiva(V*, WY) and Ihe InVstabo (VX, W) are also vector spaces over R and and v are R-linear isomorphisms.
Proof. To prove Theorem 1, we shall prove that the maps and v are well-defined and these maps are the inverse maps of each other, i.e, V o & is the identity on Equiva(V*, w and & is the identity on Iher (t.) (VX, W).
We first show the well-definedness of क. That is, for ((F) (F())))))e we shall prove that F()(::): vx + W is Stabo -invaiaaaia for any i I. To do so, check that for E Stabo (1)) and f E Vx, F(a ()))) = (v:). Let F be G-equivariant map from Vx to WY and a be an element in (ta This implies o y/ = yı, hence the inverse -- also in (taba Then, by G-equivariance of F, we have
F(a (v)) (a F)()(())) (o 9.) F()
Hence, the map (w:) is Stabo ( -invariant. This implies that the map
Φ: Equiva(V ,W²) +
II RET
Invsubbc (V* (F()))(()))))
is well-defined.
Next, we prove that the map & well-defindd. The well-definodness of can be rephrased that the image ((( = (T
for T E G such that y ---1-y y: of (Fa)ez IIier InVstabo(e)) is independent of the choice of E G and is G-equivariant. We first. notice that such a exists since, from the G-orbit decomposition Y Lier Oy, there is orbit representative yi such that y E Og,, and thus y = -=r-"p "y for some 7 E G. If E G is another choice so that y = -'-1 .Ye, then we have -'-1 .3 = y = - This implies that r-'-1 stabilizes y/- Thus, we can represent 7' = aT for some a E Staba(y:). The value of F, at r'. becomes
F F((or)) F (r f)) = F( f).
Here, the last equality is deduced from Stabe (y:)) innvariacc of F.. This implics that the definition of the value V. (v)) is independent of the choice of G satisfying y: y-

---

Published in Transactions on Machine Learning Research (09/2024)
We set F ((((F))e)) To show G-equivariance of F, it is sufficient to check that for any E G, any E VV and any EY, ; a. F(J)v) = F(a () holds. Tet y E Oy: and y --1. yi for some 7 E G. Then, because o (o (o T-) ) -. Oy:
(LHS) (( =(f((o v)) =(((((( v.) = - ..)) F.((To)) f).
Here, the last equality follows from the definition of the map of v in equation (8). On the other hand, we have
(RHS) F(a f))) F(a. ()(r-111)) y:) F.(T- ()) f))==((((T)) f)-
Here, the third equality also follows from the definition of the map of v in equation (8). Therefore, F satisfies a. ......FF. FF))()) = F(a fv) for any a E G, any f E VX, and any E Y. Hence, F is G-equivariant.
Finally, we show that the map y is the inverse map of the map + and vice versa, i.c., both v oot & and $ W are identities. Let F be a map in Equiv WV). Then, the image of the map & can be written as (Fi)ter such that Ff( = (x)) Then, the map v takes (Fi)ez to F" such that F"()(v)) Fi(T- F(v for y E Y and r E G' such that y = -- Vi- Because F is G-oquivariant, we have
(v)) =F(f((T (T =))
= (or-))))))))) (()))=F(((()))) = ((F()))))
Hence, F - 1² (FF) holds for any F Equiva W In particular, & the identity.
Conversely, (Fi),er E IIier suVstaba(u:) W) is given. Let = ((FF)ver)) Then, the image of F by & becomes (f) = (F(f)())))iz- Now, for in E I,
F()()))))
(T
for T G satisfying Vig 7 Vig In particular, is in SlaberlVo) By Slabo((w,)invariiann of Fi.. F. f) Fro (f) holds. Thus, have
( o
- =FA(i))eer = (f)).
Therefore, the composition & & is the identity.
Finally, we justify the final statement of the thcorem in the case V and W are real vector spaces. Under this assumption, is fairly known that Vx, WY, Map(VX, WY) as well as Map(VX, W) are real vector spaces. Therefore, I Map(VX, W) also a vector space as the Cartesian product of vector spaces. By an abuse of notation, consider & as a map between Map(VX, WX) and Il Map(VX, ,W), and let show that it is linear.
Let F, F' Map(VXX W and X E RR It is clear that for all f f VX, (F+ F() + AF'(F) and thus for all y YYY, (F + (x)) = F(f)()) + (F))) Hence,
+ + ((F =(F+AF)))))))) =(F())(ss) + (F))))))
= =(F())(s))er + ((F(()())))ee
Which justifies the linearity of 4 Map(V W + Ilier Map(V W).
Next, we shall show that Equiv& w linear subspace of Map(VX, WY). In order to do that, first have to show that the action of F' Map(VX WX) is itself linear. Let F' E Map(VX WY) and
7

---

Published in Transactions on Machine Learning Research (09/2024)
À R, for any f E VX any y e Y, and any G, we have
a. (F)))))))()))) (F(f) + (F
= =F()(o .)) (f) =o-F(f(()) + λo FF(())))
Which yields o xF") - o.. F..F+ to . F". That being done, go back on showing that Equiva W is a linear subspace of Map(V*; W.). Let F, E Equiv (V* W and A E R, for any E G, we have
(F+ (F) (a. F Ao Ff)(f)
=a.F(f) + No F()) F(()
= ( = =F
where the third equality is due to the G-equivariance property. Hence, since the null map is clearly equivariant too, this makes Equiva W a real vector subspace of Map(VX, WY)
Consequently, the image of a WY) by V must be vector subspace of Ihee Map(VX, W). (VX,)) Since we have proven earlier that 4 Equiv (VX (V WX) - [Tee/ Invstabe(u)) (VX W) bijection, in particular, it is a surjection. Hence, the aforementioned image llie Invscabelys) (VX, W), therefore it is vector space.
To conclude, notice that we have shown that + Equiva W - Ile InVstaba(u.) (VX W) is a linear bijection between vector spaces. Thus, by fairly known fact from lincar algebra, its inverse V must be linear Loo.
Theorem 1 implies that any Gequivvriant map F is determined by the (y.) maps (w) for T. In other words, the parts (() for y (y: i T} redundant. to construct G-equivariant map F.
This theorem is quite elementary, in the sense that its statement as well as its proof, only requires basic knowledge in group theory. However, the idea of linking G-equivariant maps to invariant maps on some subgroups of G is not new and has more profound implications. For instance, is central in group representation theory as relates to the so-called Frobenius reciprocity theorem (Curtis & Reiner, 1966), about the relationships between the representation of G and the representations of its subgroups. In addition, the result from Thcorem can be recovered from some other more general theorems in more advanced topics, such Theorem 1.1.4 in Cap & Slovák (2009), about homogeneous vector bundles.
3.3 Construction of universal approximators
As an application of Theorem 1, we construct universal approximators for continuous G-equivariant maps. In this section, we assume that V and W are normed vector spaces over IR whose norms are ||-llv and |I-|ww respectively. Then, define norms on yx and W by the supremum norms
|1
sup [l]vv xEX
(9)
for f E V and similarly for e WY. Let K C V be compact subset. We assume that K is stable by the action of G, i.e., o. K for any a E G and f E K. We denote Equi (K, WV) (resp. Tny (K, W) for subgroup H) the subset of continuous maps in (Q,, WX) (resp. Inv W)):
cout (K, W {F Equiv w Equiv
continuous]
Iny
cont (K, W) = (F E Tnv K, W) continuous)
For a subgroup H C G, let HH-iuv be a hypothesis set in Inv cont (K, W) consisting of some deep neural networks. We assume that any maps in cout (K, W) be approximated by element. in Hu-iny iec
8

---

The conclusion of this Theorem relies on the assumption that some universal classes HH-mav of invariant maps do exist for the subgroups of G. We argue that this assumption is always fulfilled. Indeed, given any Published in Transactions on Machine Learning Research (09/2024)
for any F In
cont (K, W) and any e > O, there is an element F E Hi--iny such that
((())-(())) <c.
sup FeK
We define hypothesis set Ha-equiv in Equiva(K, WX) by aggregating the W-valued hypothesis sets ( iin as follows:
MG-equiv
II ViET
(Staaa(os)-inv
(10)
where V/ is the map defined in Theorem 1. Then, the set Ha-equiv is included in Equiv (K, W Indeed, by Theorem 1, this set is included in Equiva(K, w and we show that F = (F wer) K + W is continuous if and only if Fy: K + W is continuous for all E Y because we consider the supremum norm on W
The following theorem constructs a universal approximator for G-equivariant map from some invariant universal approximators:
Theorem 2. Any element in Equiv cont (K, W can be approzimated by an element of HG-eqoso defined equation (10). More precisely, for any F Equiv (K, W and any O, there erists an element in F E Ha-opuu such that
[()) F(f)llr Sc.
sup feK
Proof. By the definition of the hypothesis set Hstaba (v.)-inv: for any & > 0 and any E I, there is an element F, HStaba (p) -ine such that
T [IF(()) (A())l SE
sup
(11)
feK
We set F- (((F)))tt) The map F can also be written as F= ==v((P)) Then, the norm of the difference
between F: and F' for K at y E Y becomes as follows: If O,, and y = ys for G, then
[[{(f(()) - FF()())l = -IF y:) - ((f)(o- v:llw
=Ilā(a f)(,)) F(a f)())l
-IEi(o f) f)FFo(o flww
|FF f) - -F.(a flllw
S sup jek
[FF((f) F.(flll S jek
S sup
The second inequality follows from the stability of K by the action of G, and the last inequality follows from inequality equation (11).
Hence, the difference between 8 and F at f e K can be written as
[F((f) F(f]l = sup (F(())))))))))))))))()))(()))))) - F(F)) S..
(12)
wEY
This completes the proof because f K is arbitrary in the above argument.

---

Published in Transactions on Machine Learning Research (09/2024)
universal class with priori no symmetry, for instance, usual multi-layers perceptrons, one can always turn it into universal class of invariant maps by simple group averaging, as remarked by Yaroisky (2022).
However, such straightforward constructions are clearly unrealistic for large groups like Sn. The interest of Theorem 2 is to enable reducing the study of efficient G-equivariant universal architecture to the study of (y: ones. It offers an alternative to the equivariant or invariant "symmetrization-bar constructions in Yarotsky (2022, Section 2.1) by group averaging.
3.3.1 On the structural characteristics of universal equivariant networks arising from Theorem
On the G-action between the hidden layers. Several works have studied the design of multi-layer universal equivariant architectures, including Zaheer et al. (2017), Maron et al. (2019b), Segol & Lipman (2019), and Ravanbakhsh (2020). How do a universal architecture arising from our Theorem 2, differ from the already existing aforementioned ones?
The main difference resides in the nature of the G-action in the hidden layers. In fact the way our architecture is built involves new G-action, noted "*", which is different from the original action 4.". We provide below an explanation of this phenomenon in the form of a remark. The rigorous demonstrations are left to Appendix B and require some background in group Representation Theory.
Remark 1. Say that we seek to design multi-layer architectures that are equivariant to some G-action 4. The usual stralegy, as in the case of the previously mentioned works, is to socus on designing a single layer block that is equivariant for ".", Then by stacking these blocks, we obtain an equivariant multi-layer architecture, because equivariance is preserved by composition.
Now, consider the scenario of our construction from Theorem 2. Assume that we are given some families of multi-layers Hę-inwariant maps, for the action ".", where the H4 C G are some subgroups that have been identified thanks to the decomposition from Theorem 1. Then, by "aggregating" some of these Hą-invoriant maps, and applying V is equetion (10), new malti-layer architecture F is built. Moreover, by Theorem 1 again, the F obtained by this procedure are guaranteed to be equivariant for the action 9."
What can be said about the layer- wise structure of such F& It turns out that the G-equivariance of the hidden layers is no longer realized by 5." on both. the input and the first hidden space. Instead, it involves another G-action 5*" in the hidden space. If we look at the first layer PP,, which consists in "plugging-in" the "oggregated" " invariant maps to the inpul space (see Figure 2), ils equivariance, from the inpul layer to the first hidden layer of F, will be written as Pi(a f)== ===o0 (p((), as seen in Figure 1(b).
Overall, using commulative diagrams, Figure 1 highlights the differences between the group actions involved in these architectures.
This new action "x", which is still an action of the group G, can be described as the "induced representation of the restricted represenlation action on the hidden layers". In Appendir B, a rigorous discussion aboul this phenomenon and definition of this action "* " are done using tools from Representation Theory-
On the number of free parameters. Another notorious advantage of multi-layer equivariant architec- tures such Zaheer et al. (2017); Maron et al. (2020), is that the design of equivariant blocks requires few free parameters thanks to a phenomenon of parameters sharing enabled by the symmetry. Hence, in terms of the total number of free parameters, there is a significant, advantage in using layer-wise equivariant networks, rather than naive fully connected ones, in order to approximate an equivariant map. Is it also the case for our architecture?
We clarify that point in the following remark. We claim that, indeed, our equivariant architecture is more efficient than naive fully connected networks, in terms of number of free parameters. Proofs and rigorous explanations are left in appendix C.
Remark 2. Allhough our equivariant model differs from the slandard equivariand. models, the number of parameters of our models can also be less than that of fully connected neural network. For example, let G = Sn act on X Y = nI, by permutation and V. W be vector spaces over R. For Sn-equuvoriant map F: V W": we can take G-equivariant deep neural network Fo appresimating F by Theorem 2. Then,
10

---

Published in Transactions on Machine Learning Research (09/2024)
V
91
V1
P2
V22
0
0
Vo
V1
P2
V2
(a) Usual equivariant architecture: the action ", is the same in the imput space as well as each hidden spaces.
V
P1
V1
P2
V
Vo
V2
(b) Equivariant architecture arising from Theorem 2: the action 5." on the input space is different than the action "*", in red, on the hidden spaces.
Figure Commutative diagrams for comparing between a usual equivariant multi-layer architecture, and ours arising from Thcorem For each diagram, the two lines both represent the same multi-layer oquivariant architecture with the Pi being the equivariant layers between hidden spaces. Each square encapsulating a O symbol is commutative diagram that represents the equivariance of the layer (i, í.e, the fact that yo commutes with some action of the group. This means that, within these squares, from the top left to the bottom right the two possible paths are equal.
the first hidden layer of F can be wrillen as the form Vi² for a vector space V1. The linear map V + Vin is equivariant. for permulation action on v and the direct sum of "induced representations of restriction representations to the stabilizer subgroup" number of parameters of the linear map between the input loyer V and the first hidden layer VIr² becomes dim V dim Vi. Because the number of parometers of the linear map V + Vi for the fully connected model is n dim V dim V1, our model can be constructed by much fewer paramelers than the fully connected model. Appendiz C, precise statement and proof of this fact are concluded using Schur's Lemma and Young's 's diagrams.
Vir By the argument
irreducible representations, the
4 Some specific cases
In this section, we propose an application of Theorems 1 and 2 to few examples.
4.1 Permutation equivariant maps
As first example, we consider Sq-equivariant maps. Recall the context from Section 3.1 where X Y {1, [1, and V, W generic sets. The set Y only has single orbit by the Sn action: O S, which can be written as
0 = ( 1,.. n =
where () E S, is the transposition between and j.
Hence, we recover Proposition from Theorem 1. Namely, that an Squeqiivari map F VX W uniquely determined by its Stab(()-invariant component. Fi: yx W via
F()) (7i i). D)
By this argument, any analysis of S.-qquivariance of the map F can be reduced to analyze only one Stabs, (1)- invariant map F. yx W (Figure 2).
11

---

Published in Transactions on Machine Learning Research (09/2024)
VX
F
W
id
F: VX
id
VX
F
W
= W
id
VX
F
W
15
VX
F
W
F: VX
(12)
VX
F
W
WY
n)
VX
F
W
Figure 2: The case of G S,, and X Y {1, ........ The S,-orbit of 1 E is the whole set Y, thus Sn-equivariant map F is determined by only one Stabs, (1) -iviiiariann map Fl.
In this case, as a hypothesis set Hstabs, (1) of Stabs, (1)-invariant deep neural networks, we can use the universal approximators defined in Maron et al. (2019b). By this Hstabs, (1) and Theorem 2, we obtain universal approximators for S,-eqqivvriant maps.
4.2 Finite groups
In this subsection, G' is any finite group. By Proposition 3 in Appendix A, G is subgroup of S, for some n. Hence, G acts on X = Y (1,2...., via permutation action of S,,
The G-orbit docomposition of Y is generally nontrivial. Let Y L Oy, be the G-orbit decompasition of Y and 31, ./..... 2t be elements of G such that Og, Gyj for i 1,2,...,k. k. We represent Oy, O2 (Va .2...., ) and choose 0i E such that Vij = o.j y4- Then, we remark that Dx= m, = n.
We consider a G-equivariant map F from v to WY for vector spaces V, W over R. By Theorem 1, F can be writton by
F(f) (F.(ay f)) ei.....
(13)
for any f e V.X, where = is Staba -inree(riiiiv invariant. We remark that this map F is determined the (Mabo(y))-ivvriin map F, from Vx W for 1,2,...,4.
For general finite group G, hypothesis space Hstaao neural networks with tensors introduced in Maron et al. (2019b), which is guaranteed to approximate any Stabe (y, -invariaant continuous maps. Keriven & Peyré (2019) also construct a universal approximator for graph neural networks.
choose the set of models by using deep
4.3
The special orthogonal group SO2(R)
As for Example 3 (iii), we consider the rotation actions on the set of the ideal images. The index sets are y= R22 We consider Map(X, R-) (R3)x the set of ideal images with the values for ideal RGB color channels V R3. Let W be set of output labels. Then, the 2-dimensional special orthogonal group SO₂(R) acts on = 2 We consider an S0₂(R) (B)(())-quivariann (i.e., rotation equivariant) map F: -R² - WR²
Then, the orbit Og S02(R) ys of yi (i, 0) IR2 for i [0, oo) is Oy, {(a, R22 la 12 =2).
12

---

Published in Transactions on Machine Learning Research (09/2024)
VR²
W
F
(Filiel
Figure 3: Rotation equivariant map F is determined the maps {Fihie where I is the nonnegative real line
R20- We can recover F from (Fi)eer by "rotating" (eE
and Y = -Lier Oz holds. On the other hand, the stabilizer subgroup of SO2(R) for ys (1, 0)
{(: }}
i 0,
(3)
(O) i
Then, by Theorem 1, the (Qeuvvvvavaar map F can be written by
F(f) = (FFilo f) (e Fo(5))
(E802(2)
This means that (O)(([)))nuvvariaan) map is determined by the maps F3: (IO, 1|9) W for i [0, oo) as Figure Unfortunately, F; for >> does not have any invariance because the stabilizer subgroup of (O2(IR for (i,0) is {(: }
We assume that X, are the disk D ((x, v) x² 222 < R) of radius R> 0. We can apply Theorem 2. Then, if there is universal approximators (Fi)ier of (F.),er, (((F))eer) approximates the map ((F))ee))
In this case, as a hypothesis set Hstabso, (v.)-inv Stabso (y:)) invariant deep neural networks, we can use the universal approximators defined in Yarotsky (2022, Definition 3.2). By this ()) and Theorem 2, we obtain universal approximators for SO2 -equivvrari maps.
4.4 The translation group T for R?
It is known that the convolutional layers of convolution neural networks are translation equivariant. In this subsection, we consider an example for X = R² and the actions of the translation group T for R² on yx and WYY The translation group T is defined by
T= (To R
where each translation T, is defined by Tx( + v. For ʃ E VX the action of Tn on is defined by (To ()))) ((T, f(x - v).
We consider an T-equivariant (i.e., translation equivariant) map F: ya² - Wx In this case, for (0,0) e Y 2 the orbit ( T (0, 0) is same as Y R and Stab.((O, 0)) [Id]. Then, by Theorem 1, the T-equivariant map F can be written by
F(f) ( (T. f))EEY.
In particular, T-oquivariant map F determined by one iIda-invariant map (i.c., usual map without in- variance) Fro.o): vx + W. this situation, by Theorem 2, if there is a universal approximators Fro.o) of Foo,) (F (0.0)) approximates the map F = T (F
13

---

Published in Transactions on Machine Learning Research (09/2024)
5 Application to the numbers of parameters
5.1 A relation of the numbers of parameters for invariant/equivariant maps
In the case of finite group G, we investigate the number of parameters from the point of view of approxi- mations. Let G be a group and X, Y be two finite G-sets. Let Y = Likz Oz, be the G-orbit decomposition of Y and K' C VX be compact subsct which is stable by the G-action. For F E Equiv (K, W we define Ea Fs; to be the minimum number of the parameters of G-equivariant deep neural networks that can approximate F in accuracy >> O. More preciscly, there exists G-oquivariant deep neural network F of which the number of parameters is equal to (e; F)) and Se [I F(])]l wr S, and there is no such G-equivariant deep neural network of which the mumber of parameters is less than (=: F). Similarly, for subgroup H of G and F ot (K, W), we define (e; F*) to be the minimum number of the parameters of H-inyariant deep neural networks that can approximate F in accuracy E > 0. The existences of such cny (c; F) and Ga (e; F) are guaranteed by the results for universal approximation theorems such as Maron et al. (2019b) or Theorem 2 in this volume.
For F E Equiv cu (K, WY), F; E Invstabo (V-, W) is defined by (Fi)ier = (FF) in the sense of Theorem 1. Then, we have the following:
Theorem 3. For any E > 0, the following holds:
max luv ET
(tabalu)) (c; F.)5 S (); Σ
luv Stabo (v.) (e; F.).
(14)
NEI
Proof. We first show the left inequality. Let Fro InVStabo(u,,) (V* W) for an in We can find a G-equivariant, deep neural network F such that [I²(S) F(f)lwrr Se for any I E K and the number of parameters of F is equal to (e; F). The existence of F is guarantced by Theorem For this F, F()) satisfies (l - Fi, (fllw S E and the number of parameters of the deep neural network F()) is less than equal to <e F). Thus, F.,, can be approximated in accuracy E by Staba (Vin -invariaat deep neural network of which the number of parameters is less than or equal to (e; F). This implies jnv (taa Fio) S (E; Because in I is arbitrary, we have the first inequality of equation (14).
We next show the second inequality of equation (14). For any E I, there is a deep neural network P. such that - - FF(O)ll S e for f K and the nunber of parameters of this is day Stabo (e; Pt). We set
F= ( ==(((F))er) Then, by Theorem 1 and inequality equation (12), we have
sup || [F( F(f]lwy = sup sup (((()))) - F(f)()llw FER yEY
SEK
sup [F(() -( villlw))
sup fEK
sup
iE7
sup || f)())) - F(a. F(ww)ll))
sup
sup iel
SeK
oeG
sup [[(()))))) - FUNGWIII)))
< sup
iEl
/EEK
(1 - R(CHIIN) Sc.
sup ie?
sup
(15)
VER
Because the number of parameters of F(f) is less than or equal to EiEr inv (e) F.), any elements in Equiv (K, W can be approximated in accuracy E by G-oquivariant deep neural network of which the number of parameters is less than equal to Eiez Stabblla Eier luv .uv Stabbll,) (c; F.). This is the second inequality of equation (14).
inv (s; F.). This implies c (E: <
14

---

Published in Transactions on Machine Learning Research (09/2024)
5.2 Approximation rate for G-equivariant deep neural networks
In the case of G Sn, X = 21, V = W R, and K [0, 1J" C V", Sannai et al. (2021, Theorem 4) showed an approximation rate of S, -n-invariant ReLU deep neural networks for elements in a Hölder space. In this subsoction, we gencralize this result to G-invariant maps for a finite group G C S, and show an approximation rate for G-equivariant ReLU deep neural networks.
Let be positive constant. The Hölder space of order a the space of continuous functions such that all the partial derivatives of up order [a] exist and the partial derivatives of order [a]] are a a [a] Hölder-smooth. This space is usually denoted Ca.a-Laj, but denote it C here for convenience. For f: K + R. the Hölder norm is defined by
100 f(x) 0 f(x'))
Ilflew = max 8:3][|a|
1100 (xx))l=<<)) + max
sup 8: [8|= a.d Kazyaa
| x [/118-la) [a]
For B > 0, B-radius ball in the Hölder space K is defined as CB = =f Ca llfflle I B}.
The following is a generalization of Sannai et al. (2021, Theorem 4) to finite group G C Sn.
Theorem 4. Let G c Sn be a finite group acting on the sets = = 21. nn} and Y Y= Li= O be the G-orbit decomposition, and K = [0, 1]"h C RR. For any E > 0, let HG-inv be set of G-invariant ReLU deep neural networks from K to I which has at most (log(1/E)) layers and O(g-n/a log(1/s)) non-zero
parameters. Then, for anyy G-invariant, function F E Cß. there exists F Haa-in such that
sup JEK
Proof. To generalize Sannai et al. (2021, Theorem 4), it is sufficient to define the fundamental domain AG for finite group G C Sn and a sorting map Sort: [0, 1j" -> Åc. and to show that Sort can be realized by ReLU deep neural networks. The remaining part of the proof is similar to the proofs Sannai al. (2021, Proposition 9, Theorem 4)
Let (1,2,..., = L O, be a G-orbit docomposition and I, = fil....,,t,, Hm, satisfying ig < Eg for
< C.
Then, fundamental domain Ag for G is given as
AG (II1...,, zn) E [0, 11"h Ig ze. if < l' for j 1.2
We consider the reordered index (i), i from (R, to this index
11 12.
......
ma
2/. 1..)
We define the permutation
1 2
i
12
Then, by oo (I1, .2. TA) E 10 is permutated as to (I1, (..,, TT (Ioo(1)) Too(2) 2 2oo(n)) T
Izt. )
We remark that this permutation can be realized by linear map. On the other hand, we define Sorto: [0, 1)" + [0. 11"d by
Sortg(a1,.... (max) (II,..,, Rn), max...1......................... .n...... max (II,...,In))
Here, max 2n) is the l-th largest value in {mp +2 ........... Tp, } where pj Σ m, As Tp, proven in Sannai et al. (2021, Proposition 8), we show that the map Sorte represented by deep
15

---

Published in Transactions on Machine Learning Research (09/2024)
neural networks with ReLU activation functions. We define Sorte do Sorte .o. Then, the image (o .n) in the fundamental domain Ag and Sorte can also be realized by a ReLU deep neural network.
By applying Sannai et al. (2021, Proposition and Proof of Theorem 4) with this Sorte, we can complete the proof.
As mentioned in Sannal et al. (2021) for G Sn also for finite group G C Sn. the approximation rate in Theorem 4 is the optimal rate without invariance obtained by Yarotsky (2022, Theorem 1). Thus, show that G- G-invariant deep neural networks can also achieve the optimal approximation rate even with invariance.
By combining Theorem 4 and similar argument in the proof of Theorem 3, we can show the approximation rate for G-equivariant maps:
Corollary 1. Let G Sn be a finite group acting on the sets == f1.2..... m and Y Y O2 the G-orbil decomposition. Let = equivariant ReLU U deep neural networks from to R with most ((log(1/E) layers and OKe-n//a log(1/s)) non-zero porameters. Then, for any G- G-equivariant map F E (Cg)", there exists F E Ha-equio such that
R and K = [0, 11 C CR. For any 0, let HG-equio be set of G-
sup fek
Se.
Proof. Let F E (Cz)a be G-oquivariant map and (Fi)ier ((F). Then, by Theorem 1, Fg a Stabo(y:)- invariant contimuous function on K. By Theorem 4, there is an element F, in Hstabo such that
sup
fek
We set F= (((F))))) Then, by the similar argument in inequality equation (15), we have
sup [f()) F(F S sup sup ie fek
- -
fek
Now, F has at most (1lg((//E) layers and O/k--n/a log(1 (1/e) non-zero parameters because of the assump- tions for F. (i 1..,....AA This concludes the proof.
6 Conclusion
In this study, we explained a Tundamental relationship between equivariant maps and invariant maps for stabilizer subgroups. The relation allows any equivariant tasks for a group be reduced to some invariant tasks for some stabilizer subgroups. As application of this relation, proposed the construction of universal approximators for equivariant continuous maps by using some invariant deep neural networks.
Although our model is different from the other standard models introduced by Zaheer et al. (2017) or Maron et al. (2019b), the number of paramcters of our models is fewer than fully connected models. Morcover, by the relation, we showed inequalities of the number of parameters of invariant or equivariant deep neural networks to approximate any contin awariann//qquivariant maps. We also showed an approximation rate of G-equivariant ReLU deep neural networks for elements of Hölder space for finite group G.
The invariant-equivariann relation is fundamental and applicable to wide variety of situations. We believe that this study will lead to further research in the field of machine learning.
Acknowledgments
AT was supported in part by JSPS KAKENHI Grant No. JP20K03743, JP23H04484 and JST PRESTO JPMJPR2123. YT partly supported by JSPS KAKENHT Grant Numbers JP21K11763 and Grant for
16

---

Published in Transactions on Machine Learning Research (09/2024)
Basic Science Research Projects from The Sumitomo Foundation Grant Number 200484. MC partly supported by the French National Research Agency in the framework of the LabEx PERSYVAL--ab (ANR- 11-LABX-0025-01). The previous version of this work was done during MC's visit to RIKEN AIP.
References
Vladimir 1. Arnold. On functions of three variables. Proceeding of the USSR Academy of Sciences, 114: 679-681, 1957. English translation: Amer. Math. Soc. Transl., 28 (1963), pp. 51-54.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-133, 1994.
Ben Blum-Smith and Soledad Villar. Machine learning and invariant theory, 2023.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges, 2021.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. 2nd International Conference on Learning Representations, ICLR 2014, 2014.
Cap and J. Slovák. Parabolic Geometries I. Mathematical surveys and monographs. American Mathe- matical Society, 2009. ISBN 978082182687 URL https://books: wwwogle.frbbooss/iiei http/boookss.d--MyPAAAAAAAAA.A
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pp. 2990-29909 2016.
Taco S. Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical CNNs. In International Conference on Learning Representations, 2018. URL
Charles W Curtis and Irving Reiner. Representation theory of finite groups and associative algebras, volume 356. American Mathematical Soc., 1966.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-33) 314, 1989.
Michaäl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garneut (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https: httpas///poceedigs..eeee neurips.... cc/paper files/paperr2266/Eiee. D4f44434481c5b777beeeeebe 1ee65 Paper.pde
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. Tn International Conference on Learning Representations, 2021. URL https::/openrreiie: wtw.arrrrreeeeettooouuiiieee
GNFBvWIRXaG.
Carlos Esteves, Christine Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis. Learning so(3) equiv- ariant representations with spherical cnns. International Journal of Computer Vision, (28(3):588-60) Mar 2020. ISSN 1573-1405. 1111233-19-01220-1
doi: 10.1077/411233-000-00222-- URL https://doi. 10t./10.010///
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 2(3):183 192, 1989.
Robert Gens and Pedro M Domingos. Deep symmetry networks. In Advances in Neural Information Pro- cessing Systems, pp. 2537-2545, 2014.
Boris Hamin. Universal function approximation by deep neural nets with bounded width and relu activations. Mathematics, 7(10), 2019. ISSN 2227-7390. doi: 10.3390 m1117099..7 URL https: //www//wwww///// mdpi com/ 2227-77990//10/899..
17

---

Published in Transactions on Machine Learning Research (09/2024)
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprinl Xiv: 1710. 1278, 2017.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(3):359-366, 1989.
Gordon D James. The representation Uheory of the symmetric groups. In Proc. Symposia in Pure Molh, volume 47, pp. 111-126, 1987.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. arXiv preprinl ar 1rv: 04943, 2019.
Jinwoo Kim, Saeyoon Oh, and Seunghoon Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs. A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vanghan (eds.), Advances in Neural Information Processing Systems, 2021. URL https://openrete httppperreviee..ne/rrrurrru net/forumiid- scn3RYn1DYx.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017. URL https:// http///ppeeeeveeeeeeeeeee wtwprr/wwwwweeetoouuiiicceee SJU4ayYgl.
Andrey Nikolaevich Kolmogorov. On the representation of continuous functions of several variables by superpositions of continuous functions of smaller number of variables. Proceeding of the USSR Academy of Sciences, 108:176-182, 1956. English translation: Amer. Math. Soc. Transl., 17 (1961), pp. 369-373.
Imre Risi Kondor. Group theorelical methods in machine learning. Columbia University, 2008.
Véra Kúrková, Kolmogorov's theorem and multilayer neural networks. Neural networks, 5(3):501-555 506, 1992.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553)::366 444, May 2015. ISSN 1476-4687. doi: 10.1038/nature 14399. URL https://doi.oon org/10orrg1000 10////0..11 wwtp///...////atuuuoooo 1038/nature14539.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. Tn The Fleventh International Conference on Learning Representations, 2023. URL https: //tpp//////peeeiier/ wtt.i/ewwwn//oouummiiii Q- q-UHqMorzil.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivarian graph networks. In International Conference on Learning Representations, 2019a. URL https::/openreeee wwtpwiiwwwwee/.frrrreeeee id=Syx72jC9tm.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Proceedings of the 36th International Conference on Machine Learning, 97, 2019b.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6734-6744 PMTR, 13-18 Jul 2020. URL https: hatpc///pooceeeeeeee mlr.
wttppes.mm.p...e....mm wwr.peeeiiiii h1t///1/19///00000/ html.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143-195, 1999.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnel: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the TEFE Conference on Computer Vision and Pattern Recognition, pp. 652 660, 2017.
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In International Conference on Machine Learning, pp.
PMLR, 2020.
18

---

Published in Transactions on Machine Learning Research (09/2024)
Siamak Ravanbakhsh, Jeff Schneider, and Barnabás Póczos. Equivariance through parameter-sharing, In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2892 2901, PMLR, 06 11 Aug 2017. URL https://ppll https://pocceedng..ooe www.eddiinnimm......mmmmmemme wttp://nnw.......eeee///oo//
Joseph J Rotman. An introduction to the theory of groups, volume 148. Springer Science & Business Media, 2012.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invari- ant/equivariaat functions by deep neural networks. ar preprint (xXix:1903.0999 2019.
Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group invari- ant/equivariant deep networks via quotient feature spaces. In Uncertainty in Artificial Intelligence, pp. 771 780. PMLR, 2021.
Akiyoshi Sannai, Makoto Kawano, and Wataru Kumagai. Invariant and equivariant reynolds networks. Journal of Machine Learning Research, 25(42):1-36, 2024. URL ptttt::/jjmll www.oogg///o..ooooooo pttpppssvs//2220000/000 html.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 80, 2008.
Nimrod Segol and Yaron Lipman. On universal equivariant set networks In International Conference on Learning Representations, 2019.
J. Shawe-Taylor. Building symmetries into feedforward networks. In 1989 First IEE International Conference on Artificial Neural Networks, (Conf. Publ. No. 313), pp. 158-162, 1989.
J. Shawe-Taylor. Symmetrics and discrininability in feedforward network architectures. IEEE Transactions on Neural Networks, 4(5):816-88) 826, 1993. doi: 10.1109/72.248..
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approx- imator. Applied and Computational Harmonic Analysis, 43(2):233-28) 268- 2017.
Puoya Tabaghi and Yusu Wang. Universal representation of permutattion-invariant functions on vectors and tensors, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL
wtwpeeediinnnn.uuippi..ee neurips cc/ cc/paper_ateeeeeeeeeeeeeeeee popprrffless files/ files/paper/ paper/ pdf.
2017/file/
Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are univorsal: Equivariant machine learning, structured like classical physics. In A. Beygekzmer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: //openreview wttprrvvveweeeeeeeeeeeee met/forumm/ Btt.iidNNNNttggtgeeee
Soledad Villar, David W Hogg, Weichi Yao, George A Kevrekidis, and Bernhard Schölkopf. Towards fully covariant machine lcarning. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL
https://oppenreverr http:://wperrreeeeeeeeeetttraaea net//forum/ddggllnnpnn
Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Michael A. Osborne, and Ingmar Posner. Univensal approximation of functions sets. Journal of Machine Learning Research, 23(151):1 56, 2022. URL html.
Jeffrey Wood and John Shawe- Taylor. Representation theory and invariant neural networks. Discrete Applied Mathematics, 69(1):33-60 60, 1996. ISSN 0166-218X. doi: http:///ooorr///0//.///11161111/ URL http:////wwww.ccceeeeeeeee..... http::/scccaclliiitttttaaaaaaaas
19

---

Published in Transactions on Machine Learning Research (09/2024)
Dmitry Yarotsky. Universal approxinations of invariant maps by neural networks. Constructive Ap- prozimation, 55(1):407-474, Feb 2022. ISSN 1432-0940. doi: 10. 10.1007/600365--21--096544 URL
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391 3401, 2017.
A Groups, actions, and orbits
To introduce a precise statement of the main thcorem, we briefly review several notions of groups, actions, and orbits. In general, group set transformations and an action of the group on transformation rule. This is further explained in the following examples. For more details, refer the readers to Rotman (2012).
Let G be a set with a product or E G for any elements T, of G. Then, G is called group if G satisfies the following conditions:
1. (Existence of the unit) There is an element e e G such that ea = dre for all a G.
2. (Existence of the inverse element) For any E G, there is an element o-1 G such that aa
0- 0- =6
(Associativity) For any O, E G, (ar) o(To).
We call G a finite group the number elements G is finile. If the product of G commutative, i.e., for any O, E G, OT To holds, then G is called an abelian (or a commutative) group. Let G be a group and H subset of G. We call H subgroup of G if H is group with the same product as that of G. Example 4. (i) The permatation group Sn is one of the most important ezamples of finite groups:
S. = (1.....m n) (1. (I.....,, n) bijective]
and the product of O, E Sn is given by the composition a o t as maps. The permutation group Sn is also called by the symmetric group.
(ii) The special orthogonal group (O2(R) is also an abelian group:
(RR {A Rx2
A A = I, det A 1)
- ={(- cos A
sin 0) 0 [0, 2n
sin
cos 0)
where I is the x 2 wnil matriz. As seen above, the elements of (OR) include the rolations R.2
Next, review group actions sets. Let X be set. A left (resp. right action of G on X is defined map X + Xiz x for E G satisfying the following:
For any x E X, ==
For any a and x E x, (OT) = - xT) (resp. (OT) . = == (a. x)).
Then, we say that G acts on X from left (resp. right). Here, the reason why we call the latter a right action is that the condition (aT)- x= = T (a r) seems as the condition "x (OT) = (x o) o).
Example 5. (i) The permutation group Sn acts on the set (1,2....,m) from left by the permutation a i (1)).
(ii) The special orthogonal group (R2(R) acts R2 from left by the rolation transfrrmations.
20

---

Published in Transactions on Machine Learning Research (09/2024)
We introduce subgroup that is often considered in this article. Let G be group acting set X from left. For an element E X, the subset Stabo(z) of G consisting of elements stabilizing is subgroup of G:
Stabo(x) = for E G o 1..oo. ==)
This group (z) is called the stabilizer subgroup of G with respect to æ.
Next, introduce the notion of orbits by the group actions. An orbit is the set of elements obtained by transformations of a fixed base element. Let G be group acting on X from left. Then, for X, we define the G-orbit O₂ of as
= G x .o.a. a a G).
Then, it is easy to demonstrate that X can be decomposed into a disjoint union of the G-orbits X X= L Os:- We call this the G-orbit decomposition of X. We remark that the index set I might be infinite.
Example 6. (i) We consider the permutation action of Sn X is same as X, i.e., X = O1 Sn 1.
n.. Then, the orbit of E X
(ii) The orbit of X E IR? of the action of SO2(RR on X = R is same as
[ ((a,b) R² + +
x
if + 0, if = 0.
Ox
[0)
When | l| then represent the orbits as ((r,0) Ox Hence, the orbit decomposition of X IR² is same X = Ur2 (ir,0)-
Let H be a subgroup of a finite group G. Then, H acts on G from left and right by the product: For T E H and a E G, acts on from left (resp. right) by a + to (resp. a + ØT). For any E G, we define the set
O = (or T
This is nothing but the right H-orbit of for the above right action of H on G. This is called the left coset of H with respect to Because the left coset is identical to the H-orbit for the right action of H, we can decompose G into a disjoint union of the left cosets as a H-orbit decomposition:
G
L O,H.
iET
We refer to this as the left coset decomposition of G by H. We define G/H as the set of the left cosets of G by H:
G/H = |
The right cosets, the right coset decomposition, and the set of right cosets H H are also defined similarly.
Then, a relation exists between an orbit and a set of cosets:
Proposition 2. Let G be group acting on set X from left. For any a E X, the map
G/Stabo(z) + Ozi oStabo(x) to
is béjective. In particular, G/Stabo(x)) (o,Stabo(z)) i E T}, then the orbit of in be written by O2 (o, x I)E
Proof. It is easy to check well-definenness and bijectivity.
Example 7. (i) For G = Sn. acting
1.,....,n... 21,,,..., the G-orbit of only one, ie.,
O = 1 (1.2....,
Hence, by Proposition 2, the following map is bijective:
Sw/Stabs, (1) (, ... n)) oStabs, (1) + 1 o(1)
21

---

Published in Transactions on Machine Learning Research (09/2024)
(it) For G (R), the orbit could be represented by (r..0) SO2(R) (r,0) for 2 0. Then, the stabilizer subgroup of S02(1B) for (r, (r, is
[1} ifr>
(L 0))
(O2(RR)
r-==0 = 0.
By Proposition 2, the map
0)) ~ (v.03 oStabso. ((r; 0)) + a (r,
is bijective for any 0. Indeed, this is compatible with Exomple (t).
One reason for the importance of the permutation group Sn is the following proposition:
Proposition 3. Any finite group G can be realized as subgroup of Sn for some positive integer n.
Proof. Let n n= |G| and G = (0 ,
Jx). For any a E G, 00; = oj for some j E 21 21.
n). because
the product oo; is in G. We set To = j. Then, we define a map :: G - S + Ta This map is injective and preserves the product, i.., Tool = To Tor. Through this map, can be regarded as a subgroup Sp.
Theoretical explanation of Remark
To explain the architecture our models, we introduce some notions of representation theory.
Let G' be a finite group, be vector space over E, and GL(V) be the group of the automorphisms of V. Here, an automorphism of V is lincar bijection from V to V. Then, group homomorphism p: G GL(V) is called (linear) representation of G V. Defining representation p: G - GL(V) is equivalent to defining an action of G on V by p. Then, it is also known that considering a representation p: + GL(V) is equivalent to considering an R[G]]module V. Here, [[[] is the group algebra defined as
RIG
Σ 0 ag
Moreover, for algebra A with unit 1, an A-module M is an abelian group with summation +, endowed with a "scalar product" by A, denoted as satisfying
0 (x x') =
(0 +T) x 0.
(OT)
(T.x),
x
for T, E and x, x' E M. This means that an A-module is an analog of a vector space with the scalar product by algebra A. When representation p: - GL(V) given, V can be regarded as an [[]]-module by the action
Σ Eaol - Σ (p)( DEG
GEG
for Eoec a E [[G] and v E V.
Two representations (p. V), V') of group G are called isomorphic, denoted V) (p', V') if there is a linear isomorphism E: V + V satisfying the commutativity
E(p(a)(v)) = (Eo)(E)())
(16)
for any a e and E V. A lincar map (not necossarily isomorphism) satisfying commutativity equation (16) is called an intertwining operator. We set (omg(V, V') as the set of intertwining operators from (p. V) (d/, V*).
22

---

Published in Transactions on Machine Learning Research (09/2024)
For subgroup H C G and representation p: G GL(V). the restriction map pla: H GL(V) is representation of H on V. This representation is called the restricted representation of p to H and denoted by (p). Then, considering the restricted representation pl is equivalent to considering V as an IR module..
On the other hand, for a subgroup H c and a representation p': H - GL(W) of H on W, the coefficient extension of moodlee W to [[G]
R|G @R(M] W
is an moolll. Here, the tensor product R[G] @RTH W is defined as the quotient (R x W)/~ of the direct product R[G] x W, by the equivalent relation ~ which defined for a, E R[G], E H, w, w E W and c E R by:
(o+ ~ (a,w) w) + (d), (e (a,
(o, w + w') (a,w) (a,
(OT, w) ~ (o, (z))
Then, the action of of E G on an element a @ w E TR. G OaMM W is defined by
d' 2 w) = (a Ø w.
We call the representation defined by this the induced representation of p' to G and denote by Ind (p'). We remark that the following equality holds:
& ('(
for any a E G. T H, w E W. Let G L Ho; be the right coset decomposition of by H. Then, we have the directed sum decomposition
R G
o
RHH.
(17)
By equation (17), we have
m
m
R (R( W
0; [[
@3(H]
W + o 8 W Wm
Therefore, the dimension of R [ 83[H] W is mim W = (G H) dim W, where (G: H) is the index of H in G.
Let G c S, be a finite group, F: V + Wa be a G-equivariant continuous map, and let Y = (1,2,.... m} = -m_ Oy, be a G-orbit decomposition with Oy, = (o (wx) o e G} of y E Y. By Theorem 1, we have ((F) (F for the (y.- continuous map F.(.) = (m)) Then, we have an (y. deep neural network of the Slabo(y; Slabo(gs)innvaiinn -invariaat map
approximator F,; Fa W F; (cf. Sogol & Lipman (2019), Ravanbakhsh (2020)) and, by Thcorem 2, can reconstruct an approximator F (((F)).
Let G = -ن=- Stabo be right coset decomposition for Stabo(y:). Then, by Proposition 2, we have O,, = (o (yi) j = 1,..., l... By using this, an approximator For of F is constructed from ( by
f(x) ((Fi 1)
(18)
for X (0i,..., R..) E V"
23

---

Published in Transactions on Machine Learning Research (09/2024)
We focus on a Stabo((;)-invaril approximator F.: V - W. By Segol & Lipman (2019), we assume that F; can be realized as deep neural network model as
(v 2
(V22
(V(0))n 2 (V&41) W
where 1/ is finite dimensional vector space over R and the Fk is map defined by
4 ( (x) ReLU(W X BB
for X (V2 w E nn v xn dim v and 0 (b (1)
ki b E (V(0) such that wh (resp.
) is (jaba()))eqquvaaae (resp. (ya (Usss--i)-vaaant, i.e., for any X E (V )" and any E Staba(())
( x)= = (),,
X), B = =B
holds. Here, (ta c c Sn acts on (V ()) t by the restriction of the permutation action.
By combining the equation (18) and this notation, the weight matrix from the input layer V the first hidden layer D 4. (V()))n of F is
(WW/0 ozs)s=1)
Then, by the action of G, we have
Wh oiylo X) = X)
((Toig)) X)
-W X)
-T X),
where j' Y and (y) are determined by = Stabe
In particular, by the action of E G, the (i.j)-th part w( (X) E (V/l))n is replaced by (i.j')-th part TW (aay X) with the action of oy E (ta)o From this observation, we define the action of G on the i-th part ( (0)) follows: For a E G and j 1,2, ,..,, bo we define ()) (1,2..... 4 such that
oz0= (0 (1)
E H. HHO ())
(19)
Then, for V = -005")) E 0/=1 (v
(V()))n we define the action of by
-=
o * v i = (101500
105 )
(20)
The following thoorem shows that this action of G equivalent to the induced represcntation of the restricted representation on (V.)).
Theorem 5. For our proposed model, we define the action of G on the k-th layer 4 + (V, by the action defined equation (20). Then, the representation defined by the action isomorphic to the swm of the induced representation of the restrictions
m e
Ind (Res (n.) (()()))))
Moreover, for any k. 2 1, any affine maps from (k - 1) layer to k-th layer are G-equivariant for the action (Only for the ingrut layer, the action is the restriction of the permulation action to G.)
24

---

Published in Transactions on Machine Learning Research (09/2024)
Proof. We set H, = (t)) and G ي Hoo.. For i-th part, the induced representation of the restricted representation of (V())) can be regarded as the R|G]-m
G @aH (v
o & (V
j=1 ij @ (V yn is changod as 2 u E
Then, by the action of o, an element oij
10 @v) = (oo 2 (0,,0 ) 2
-
dij' T
oij (T-
(21)
where j' E Y and H, are determined by 0íj0 To E Hy We remark that this j' is equal
(j) by the notation defined in equation (19). This means that by the action of o G, the (i,j)-th part
og & v is replaced to the (i, (3) - 10 (1) @ (T. v) with the action of T oijo o ( E He.
We define the map E from the i-th part of k-th hidden layer c (V (V) to R[G] @R(H.]] (V (V( j=1 Tit 2 (r by
E: v = (0)0))
oi
By definition, this map is bijective and equivariant for the action of G on Dz (V (V(0)) by equation (20)
and on [R]]] @R(H)) (V)))) by equation (21). Indeed, we have
E(o ( E(( ())
6 Ø (aij00
j=)
10
i=1
4
(oij0
10
j=1
6
(
(
j=1
= 0 E
ij
1=1
This means that (V and R[G] @R(H.] (V(() yd are isomorphic as R[G]]
The equivariance of affine maps is deduced by the definition of the action *, This concludes the proof.
C Theoretical explanation of Remark
In the remaining part, we argue about the mumber of parameters the affine maps between layers. If a weight matrix between two layers of neural networks equivariant by some G-action, this can be regarded an intertwining operator. To count the number of parameters of intertwining operators, we need the notion of irreducible representations. We here review these notions briefly.
25

---

Published in Transactions on Machine Learning Research (09/2024)
For representation (p. V) of group G, we call a subspace W C V G-invariant subspace if p())(W) W for any E G. Then, (p, W) is also a representation of G. This representation (p, W) is called a subrepresentation of V). When a representation (p, V) has no nontrivial subrepresentation this is called irreducible representation. This mcans that if (p. W) is a subrepresentation of the irreducible representation (p, V), then (p. W) is equal to (p, (0)) or (p, V). By Maschke's theorem ( (Curtis Reiner, 1966, (10.7), (10.7),)10.8), any finite-dimensional representation over IR can be factorized to the direct sum of irreducible representations up to isomorphic. In particular, irreducible representations are "building blocks" of representations.
By Schur's Lemma (Curtis & Reiner, 1966, (27.3)), for two irreducible representations (p. (d'v), Homg (V, V*) O holds if and only if (p, V) is not isomorphic to (d'.V). Thus, by this fact with Maschke's theorem, any intertwining operator can be factorized to the sum of intertwining operators between irreducible representations.
For G = Sn, by the argument with Young's diagrams, we can calculate how the irreducible representations change by induction and restriction of them. By combining such argument and Theorem 5, we can calculate the number of parameters of the weight matrix between the input layer and the first hidden layer as follows:
Proposition 4. For G Sn, Sp Sn-equivoriant continuous map F: V + t can be recovered by one Stabs, (1) invariant map Fi F = =((F). Let F1 be universal approzimator of Fr and ((V ((V be the k-th hiddent layer of == ((Fi.
Then, the number of free parameters of the affine mop from the inpul layer V to the first hidden layer p (o is dim V dim v²" + dim v(th. Moreover, the number of free porameters of the offine map from the (k- - 1)-th hidden layer ((v()) ymyn to the k-th hidden layer ((V) for l == 2.... d is at most 21 dim k-1 dim v(() + +2dim ((2).
Proof. For G = Sn, (1a = Sn-1 holds and the left coset decomposition is S, = Li= Stabo i). Thus, the first hidden layer isomorphic to R[Sa] @x[s.-.] (11"))n for a finite vector space v,th.
By permutation, Sn, acts on the part. Rn part of V = RD 60 V. By the argument of Young tableau (c.f. (James, 1987, 9.2)), the permutation representation on 1 is the sum of two irreducible representations corresponding to the partitions X (n) (trivial reprosentation) and X2 (n (n-1,11 1, of n. On the other hand, the representation on R(S,) @B[s.-1] )r = (R[S-1] IR" 8z V(") is the induced representation of the restricted representation of the permutation representation on R". By the argument of Young tableau again fc.f. (James, 1987, 9.2)), the restricted representation is the sum of irreducible representations corresponding to the partitions An (n 1), A21 (n- 1), and X22 (n 2, 1) of n 1. Then, the induced representation of it is the sum of irreducible representations corresponding to the partitions Am (n), A112 = (n 1, 1), A2n1 (n), A212 (n- 1, 1), 2221 (n 1) A222 (n 2, 2), and A223 (n 1).. Let V, be the irreducible representation over R corresponding to the partition À of n. Then, we have the irreducible reprosentation dccomposition
R[SA] @a[s.-.] Rd
v 03 (m)
+ ((n)222) + (1n-2111)-
(22)
(n-1,1)
The permutation representation can be decomposed into
E
(m)) V(n-1,1).
We set (V, V*) as the set of G-equivariant linear maps from an [G]]-modlle V to an R[G]-module V Then, by Schur's lemma ((Curtis & Reiner, 1966, (27.3)), Homs, (Vx, Vv) = 0 holds if X o X. Moreover, it is also known that
dimg Ho (Von). V(m) = dimg Homs, (Vn-1,1), V(n-1,1) =
(23)
holds. Indeed, it is known that
Vin = (c E T
c R} and
V(n-1,1) ~ (X E RR
1 x 0),
26

---

bin- This means that the number of free parameters of Published in Transactions on Machine Learning Research (09/2024)
where 1 E R" is the all one vector and 1 is the transposition of vector and we show directly that Homs,, (Vm), V(n) = R and Homs, (V(n-,1); ((--1,1) = IR. More explicitly, we can show that
111 n
Homs. (Vi) + ((--,11) 1,1), (i)) @ (1)),1)) R
+ R
R
where I R=x" is the unit matrix, and (1/n)11" (resp. (-(n is the identity on V(n) (resp. V(n-1,1)) and the zero map 11-1,11 (resp. V-n))- This implies that
Homg, (V", R(S,] @3(s.-1] (V("))))
= Homs,, (R" Ør V, [(,)) Sx(s, 1] R" &R ()
Homs, [ 1R( R") @R Hom V, v1(1)
(Homs, (V(n), ( Homs, (V 1,1), (( (n-1,1)) &R Hom vi
(24)
Thus, by equation (23), the dimension of Homs, (V", [[S,] S.. (V1 ym) is equal to d V dim v1(
Next, we consider the bias vector (B,) E ((V)") )0)0 ~ R[S.] @RIS.-1) (n(")),, where B, = (b.1....,,b bjn) E (v Then, by the action * of Sn, (B, B,}ド= is invariant, i.e,
(B,)i=1 (101500 - ()) 0 o0 (B,)
holds for any a Sn.
Without of loss of generality, we may assume that on is the unit element e. We consider Tijo To for H1 Stabs, (1), we have 01j. TOi1 In particular, (00 (jo) Thus, ju-th entry of (o))'T)+ 7)* (B,) becomes
10
16 100) (10)
(1o) = BB.
(25)
Because (B,) invariant by the action * of Sn,
B B
holds for any ju = 1,2,.... n and T E Stabs, (1). This implics that by T= Bj B1 holds for any j = 1,,, 1.2,...,tt n. Furthermore, T. B, = B, holds for any T E Stabs, (1). Because the orbit decomposition of (1,2...., n by H1 Stabs, (1) is
(1,2. 1.2....., n) (1,,,
B (b11, b12...., bin) satisfies that b12
Bi (hence, of (B,) 2im v(2).
Thus, the number of free parameters of the affine map from the input layer to the first hidden layer is dim V dim v,2) + 2 dim (2())
Next, we consider the linear part of the affine map from the (k- - 1)-th layer (V )ry" to the k-th layer ((V) ()ye for k > 1. Then, by Theorem 5, S,, acts these layers by the action *, and the representations defined by this action is isomorphic to the sum of the induced representation of the restricted representation. by equation (22) and similar argument equation (24), we have
Homs, (R[SS) 02(S.-11 (V [[SA] @R[S.-.] (V
Homs, (R[S,,) @R(S. Ra ØR R[S.) @R(S. R" &R (1)
Homs, (K[Sp) @x(s.-11 12 R
[ S R3 BR Hom (V- (1))
2 (Homs, (V (m) + Homs, (v (,) V
C Homs, (V/n-2,2), 2(n-222) @ Homs, (V(n-2111) V(n-2,1)) OR Hom(V(U) k-1: v())).
27

---

Published in Transactions on Machine Learning Research (09/2024)
Because the dimension of the division algebra over R is at most 4, the dimensions of Homs, (V(n-22), ((nn222)) and Homs, (Vn-22 (n11),,)), (1,))),)) are at most 4. Thus, the dimension of Homs, (((V=-)))) ((V) )m)p)) is at most 21 dim (1) k-1 dim (()) k
On the other hand, the number of free parameters of the bias vectors is dim V k by the similar argument as above.
28


Reviews:
[{"review_id": "jFqL8MdGRd", "reviewer": "Reviewer_3BTQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe main strength is showing the relation between equivariant and invariant tasks as stated in their main theorem, using various algebraic techniques. Then they use it to provide universal approximation theorems for architectures with such symmetries, which allows them to argue about equivariant tasks through invariant tasks (for which universal approximation theorems are known for important finite groups such as $S_n$).\n\nWeaknesses:\n\n1. While their Theorem 1 talks about the reduction from equivariant to certain invariant tasks, their universal approximation results only seem to hold for finite groups.\n2. In Remark 1, they mention that their proofs talk about certain equivariant deep network architectures that are different from the existing architectures and that the parameters are less than that of those existing architectures described in (Zaheer et al. 2017) and (Maron et al. 2019).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors theoretically study the relationship between equivariant and invariant learning tasks and show a different approach to obtaining a universal approximation theorem under these symmetries. More precisely, \n\n1. They show that any G-equivariant task can be reduced to some Stabiliser(G)-invariant task, for any group G.\n2. Moreover, using this they show universal approximation theorems under symmetry for finite groups, going beyond just $S_n$ (cf.Sannai et al.2021) for both invariant tasks and equivariant tasks.\n3. They particularly rely on their reduction to the invariant tasks to argue about the universal approximation theorem for equivariant deep networks, which is a complementary approach to methods used in works such as (Yarotsky 2022).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions:\n1. Could the authors explain any added benefit of this reduction and the applications to the universal approximations, apart from the existing approaches for the equivariant tasks being complicated. It could help if they mention how their approach helps alleviate these complications?\n\n2. Do the authors think if the universal approximators are merely a theoretical construct, or such architectures which have fewer parameters than fully connected networks be trained for such equivariant/invariant tasks?\n\n3. I think the theoretical explanation of Remark 1 provided in the appendix, while it is useful does not generally help improve the intuition about the remark. Maybe having some pictorial descriptions of the ``differences\" in the architectures from previous work and this paper would help significantly.\n\n4. As an extension of the previous point, I think this paper is not an easy read for those without any abstract algebra background. They have a 2 page introduction to Groups and orbits, but they dont seem to suffice. In Section B, in the appendix, they start talking about modules and automorphisms, the definitions of which are not necessarily contained in this paper. It would be great if the authors could consider adding some more basic definitions and properties and keep the paper as self-contained as possible.\n\n5. The applications targeting universal approximation results are described for finite groups. It would be nice to understand the challenges to extend this for infinite groups/particular interesting infinite groups, such as rotations etc. \n\nMinor comments/typos:\n\n1. Page 3, first paragraph: which was mention as a possible... -> mentioned\n2. Page 3, first paragraph: with a plethora of various architecture... -> architectures\n3. It would help to add a bit more intuition about why equation (1) is defined as is.\n4. In the orbit notation in page 18, it is better to remove the $\\sigma.x$ in between.\n5. In Section 3.1, first line, just before the equation, there is an additional white space before the words \"equation 1\".\n6. In page 19, right after the Example 6, small $h$ is defined, but never used and in that sentence it is not clear what is $\\tau$ and what is $h$, the equation following it doesnt seem to make sense.\n7. In page 20, right after equation 16, the word equation appears twice.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "a13XqQtjoQ", "reviewer": "Reviewer_LapW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: This article is well written, and the obtained main result provides a novel way to build equivariant maps. Even though the results are theoretical, the results are made easy to understand through illustrative examples. \n\nLimitation: There is one case which is important to discuss, in relation to convolutional neural networks. I am wondering if you take G = translation group on X=Y=R^2, what will happen to Theorem 1? Is Stab_G(0) = Id, so that I do not see the connection of the proposed way to construction translation equivariant maps to the convolutional layer in convolutional neural networks. Therefore the theory seems limited to include known architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article studies how to construct equivariant maps through invariant maps with regard to a group. Based on the sub-group structure of a group, the relationship between these maps are established. From this, universal approximation of equivariant maps are obtained based on existing results for invariant maps. Further discussion on the complexity of the universal approximation are analyzed for finite group.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Define what is Stab_G(y_i) in Theorem 1 before-hand. \nTypo: know -> known on page 7.\nIs there any reduction of number of parameter in the case G= translation group, compared to fully connected neural networks ?\nClarify in Remark 1 or latter the relation to convolutional neural networks.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QelHXOCocf", "reviewer": "Reviewer_NyZF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The topic of learning and representing functions under group symmetry has gained considerable traction recently and is of interest across the ML community.\n- The current work proposes a somewhat general principle that connects invariant and equivariant maps, potentially addressing a wide range of cases.\n\nWeakness:\n- My primary concern revolves around the novelty of the work, which I will elaborate on in the next section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Given a fixed group G acting on a function space, the paper studies the problem of representing G-equivariant and related invariant maps using deep neural networks. \nThe main technical result of the paper is a correspondence between G-equivariant maps and H-invariant maps, where H is a stabilizer subgroup of G. Using this correspondence, the authors are able to provide new universal approximation theorems for equivariant maps, when a corresponding theorem is known for invariant maps with respect to stabilizer subgroups.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have several concerns about the novelty and the contributions of the paper and I would be happy to hear the authors' response on these matters:\n\n1. First, if a group $G$ acts on a space $Y$ (say transitively) and $H$ is the stabilizer subgroup of $G$, one can think about the question of relating $G$-equivariant maps to $H$-invariant maps, as evoking a relationship between the representations of $G$ and the representations of $H$. Connecting between representations of a group and its subgroup, through inductions and restrictions, is a very old question in representation theory which goes back to the Frobenius reciprocity theorem.\nGiven that, I suspect that the correspondence the authors claim as their main result is a known result in the representation theory community. I have searched the literature for this result and while I could not find the exact statement, I did find some similar results. In fact, there is a way to realize the main result of the paper as a special case of the results I found in the literature.\nFor example, Theorem 2.3.5 (which states and proves the result, but is certainly not the origin of the theorem) from the following thesis https://phaidra.univie.ac.at/detail/o:1299980, is a much more general statement about the relationship between invariant and equivariant maps. In the case where $G$ acts transitively on $Y$, we can replace $X$ by $V^X$ in Theorem 2.3.5 and take $Y = G/H$ with $W = E_0$. In this case, the space of section $\\Gamma(E)$ is precisely functions from Y to W, and we recover the Theorem 1. To cover the general case, when the action of $G$ is not transitive, we can now apply the theorem to each orbit separately.\nLet me point out that the fact that Theorem 1 is not new does not mean it is not useful. I do think that there is some merit in the exact statement of Theorem 1 which is useful for problems more specific to learning theory. I also think that there is some benefit in presenting and explaining the result to the learning community, which, in general, is not well-initiated in representation theory. However, what the paper misses at the moment is a **serious** discussion about the context, history, and related literature of the result.\n\n2.  I feel that some of the discussion around Theorem 2 can sometimes be misleading. Rather than being a **universal** approximation result it is a **conditional** approximation result. The authors indeed establish that equivariant maps can always be approximated by the corresponding invariant maps (I'm not sure I would call this universal). However, in order to get an approximation result by some hypothesis class, like neural networks, one must first prove a universal approximation result for invariant maps (resp. equivariant maps) for the given class, and then use the Theorem to move to equivariant maps (resp. invariance maps). It seems to me that my last point should be emphasized better and discussed. I don't think it is true that there is a general universal approximation theorem for equivariant maps of **general** group actions.\n\n3. In line with my last comment, the applications the authors present are all based on existing approximation results. Due to this and because of the current writing it is sometimes hard to decipher which results are new and which results were already known. A more in-depth comparison with the literature is in order. In particular, it is important to explain which results from Sections 4 and 5 already appear in the literature, perhaps with different architectures, both from a quantitative and a qualitative perspective.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies links between equivariant and invariant architectures, and applies this to obtain approximation results for equivariant maps whenever universal approximation holds for corresponding invariant maps (and vice versa). The reviewers found the theoretical results and their implications interesting and relevant for the community, and were satisfied with the authors' responses. I recommend acceptance.
Decision: Accept (poster)