A Classification of $G$-invariant Shallow Neural Networks
Authors: Devanshu Agrawal
James Ostrowski
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural network
group theory
symmetry
theorem
cohomology
architecture search

Abstract: When trying to fit a deep neural network (DNN) to a $G$-invariant target function with $G$ a group, it only makes sense to constrain the DNN to be $G$-invariant as well. However, there can be many different ways to do this, thus raising the problem of ``$G$-invariant neural architecture design'': What is the optimal $G$-invariant architecture for a given problem? Before we can consider the optimization problem itself, we must understand the search space, the architectures in it, and how they relate to one another. In this paper, we take a first step towards this goal; we prove a theorem that gives a classification of all $G$-invariant single-hidden-layer or ``shallow'' neural network ($G$-SNN) architectures with ReLU activation for any finite orthogonal group $G$, and we prove a second theorem that characterizes the inclusion maps or ``network morphisms'' between the architectures that can be leveraged during neural architecture search (NAS). The proof is based on a correspondence of every $G$-SNN to a signed permutation representation of $G$ acting on the hidden neurons; the classification is equivalently given in terms of the first cohomology classes of $G$, thus admitting a topological interpretation. The $G$-SNN architectures corresponding to nontrivial cohomology classes have, to our knowledge, never been explicitly identified in the literature previously. Using a code implementation, we enumerate the $G$-SNN architectures for some example groups $G$ and visualize their structure. Finally, we prove that architectures corresponding to inequivalent cohomology classes coincide in function space only when their weight matrices are zero, and we discuss the implications of this for NAS.

A Classification of G-Invariant Shallow Neural Networks
Devanshu Agrawal & James Ostrowski Department of Industrial and Systems Engineering
University of Tennessee Knoxville, TN 37996 dagrawa2@vols. utk. edu, jostrovs@utk. edu
Abstract
When trying fit a deep neural network (DNN) G-invariant target function with G' group, it only makes sense to constrain the DNN to be G-invariant as well. However, there can be many different ways to do this, thus raising the problem of "G-invariant neural architecture design": What is the optimal G- invariant architecture for given problem? Before we can consider the optimization problem itself, we must understand the search space, the architectures in it, and how they relate to one another. In this paper, we take a first step towards this goal; we prove theorem that gives a classification of all G-invariant single- saggelhidden-llad layer "shallow" neural network (G-SNN) architectures with ReLU activation for any finite orthogonal group G, and prove second theorem that characterizes the inclusion maps or "network morphisms" between the architectures that can be leveraged during neural architecture search (NAS). The proof is based a correspondence of every G-SNN to a signed permutation representation of G acting on the hidden neurons; the classification is equivalently given in terms of the first cohomology classes of G, thus admitting a topological interpretation. The G-SNN architectures corresponding to nontrivial cohomology classes have, our knowledge, never been explicitly identified in the literature previously. Using code implementation. we enumerate the G-SNN architectures for some example groups G and visualize their structure. Finally, we prove that architectures corresponding to inequivalent cohomology classes coincide in function space only when their weight matrices are zero, and we discuss the implications of this for NAS.
Introduction
When trying fit a deep neural network (DNN) a target function that is known to be G-invariant with respect to a group G, it is desirable to enforce G-invariance on the DNN prior knowledge. This a common scenario many applications such as computer vision, where the class of object in an image may be independent of its orientation [Veeling et al. 2018), point clouds that are permutation- invariant [Qi et al. 2017]. . Numerous G-invariant DNN architectures have been proposed over the years, including G-equivariant convolutional neural networks (G-CNNs) [Cohen and Welling 2016), G-equivariant graph neural networks [Maron et al., 2019a], and a DNN stacked on a G-invariant sum- product layer (Kicki et al. 2020). However, it is unclear which of these architectures a practitioner should choose for a given problem, and even after one selected, additional design choices must be made; for G-CNNs alone, the practitioner must select sequence of representations of G to determine the composition of layers, and it is unknown how best to do this. Moreover, despite a complete classification of G-CNNs [Kondor and Trivedi 2018 Cohen et al. 2019h). it is unknown if every G-invariant DNN is G-CNN, and hence the "optimal" GGiinvariant architecture may not even exist in the space of G-CNNs.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

For some architectures, universality theorems exist guaranteeing the approximation of any G-invariant function with arbitrarily small error [Maron et al. 2019b Ravanbakhshi 2020 Kicki et al.. 2020]. and it is thus tempting to conclude that these universal architectures are sufficient for all G-invariant problems. However, it is well-known that universality [Cybenko] 1989 alone not sufficient condition for good DNN model and that the function subspaces that a network traverses as it grows to the universality limit is just as important as the limit itself. This suggests that the way in which a DNN is constrained to be G-invariant does matter, and different G-invariant architectures may be suitable for different problems. This raises the fundamental question: For a given problem, what is the "best" way to constrain the parameters of a DNN such that it is G-invariant?
This paper takes a first step towards answering the above question. Specifically. before we can consider the optimization problem for the best G-invariant architecture, we must understand the search space: What are all the possible ways to constrain the parameters of a DNN such that it is G-invariant, and how are these different G-invariant architectures related to one another?
The above is a special case of the broader and more fundamental problem of neural architecture design. One of the most prominent approaches to this problem in the literature is neural architecture search (NAS), which at its core is trial-and-error [Eisken et al. 2019]. While trial-and-error is-in for determining, e.g., the optimal depth or hidden widths of a DNN, it less clear for G-invariant architectures, where a practitioner does not even know all their options. More generally, NAS presupposes knowledge about which architectures are in the search space, which ones are not, which ones are equivalent or special cases of others, and how best one should move from one architecture to another. Thus, to apply even the simplest approach to G-invariant neural architecture design, we must first be able to enumerate all G-invariant architectures.
Our main result is Thm. 4 which gives a classification of all G-invariant single-hidden-layee or "shallow" neural network (G-SNN) architectures with rectified linear unit (reLU) activation, for any finite orthogonal group G' acting on the input space. More precisely, every G-SNN architecture can be decomposed into a sum of "irreducible" ones, and Thm. classifies these. The classification is based on a correspondence of each irreducible architecture to a representation of G in terms of its action on the hidden neurons via co-called "signed permutations", where the representation is required to satisfy an additional condition to eliminate degenerate (linear) architectures and redundant architectures equivalent to simpler ones. The classification then boils down to the classification of these representations. These representations, and hence the corresponding architectures as well, are classified in terms of the first cohomology classes of G and thus admit topological interpretation. We note that, while connections between neural networks and the group of signed permutations have been previously made in the literature [Ojha 2000 Negrinho and Martins 2014] Arjevani and Field 2020). to our knowledge, no such connection has yet been leveraged to begin a classification program of G-invariant architectures.
We also prove Thm. 5 which characterizes the "network morphisms" linking irreducible G-SNN architectures in architecture space. In NAS, network morphisms furnish a topology on architecture space and describe how one should move from one architecture to another during the search [Wei] ctt al. 2016). Taken together, Thms. 4 give a complete description of G-SNN architecture space.
This paper is perhaps most similar in spirit to the works Kondor and Trivedi 2018 and Cohen al. (2019b) and draws on similar mathematical machinery; like them, this paper's 's contribution is also primarily theoretical. Kondor and Trivedi 2018 prove that every G-invariant DNN is a G-CNN under the assumption that every affine layer is G-equivariant; that this is true without the assumption is only conjectured. [Cohen et al. [0119b generalize this to G-CNNs where hidden activations are vector fields and provide classification of all G-CNNs, but the conjecture of Kondor and Trivedi (2018) is left open. In contrast to these works, in our paper, we do not assume the pre-activation affine transformation to be G-equivariant- only that the whole network G-invariant. Thus, future extension of Thm. 4 to deep architectures would either prove or refute the cited conjecture, at least for ReLU networks. Moreover, these works do not explicitly work out the group representations compatible with ReLU, and other works [Cohen and Welling 2016 [ohen et al. 2019a) consider only unsigned permutations with ReLU. contrast, our classification reveals G-SNN architectures (namely, those corresponding to proper signed permutation representations nontrivial cohomology classes) that, to our knowledge, have never been explicitly identified in the literature previously.
2

---

We also note the work of Maron et al. [2019a], who classify all G-equivariant linear layers for graph neural networks; however, they restrict their attention to unsigned permutation representations only, and there classification is again not guaranteed to contain all G-invariant ReL.U networks.
The remainder of the paper is organized follows: In Sec. we give classification of the "signed permutation representations" of G and relate these representations to the cohomology classes of G Then in Sec. 3 we build towards and state our main classification theorem of G-SNN architectures. While Sec. 2 makes little reference to G-SNNs, presenting it upfront helps to streamline the exposition in Sec. with much of the notation and terminology established. In Sec. 4 we visualize the G-SNN architectures for some example groups G, and in Sec. [] we make a number of remarks including theorem on the "network morphisms" between G-SNN architectures. Finally, in Sec. 6 we end with conclusions and next steps towards the problem of G-invariant neural architecture design.
2 Signed permutation representations
2.1 Preliminaries
Throughout this paper, let G be a finite group of m x m orthogonal matrices. Let P(n) be the group of all n x n. permutation matrices and 2(n) the group of all diagonal matrices with diagonal entries +1. Let PZ(n) = P(n) x (m). which the group of all signed permutations- i.e., the group of all permutations and reflections of the standard orthonormal basis Cc.....,c,]. This group is also called the hyperoctahedral group in the literature [Bakke 1984].
A signed permutation representation (signed perm-rep) of degree of G is homomorphism p:G G + PZ(n). Whenever we say p signed perm-rep, let it be understood that degree n unless say otherwise. A signed perm-rep p is said to be irreducible if for every i, ......... there exists E G such that p(g)e; = +ej. As we will see in Sec. 3.2 every G-SNN can be written of "iireducible"" C-SNNs, and every irreducible G-SNN corresponds to irredueible signed perm-rep. It is therefore sufficient for our purposes to classify all irreducible signed perm-reps of G; moreover, this need only be done up conjugacy
next.
2.2 Classification up conjugacy
Two signed perm-reps p. o' are said to be conjugate if there exists A E PZ(n) such that (' = A p(g) Afg G. We let p denote the conjugacy class of the signed perm-rep p. Note that conjugation preserves the (ir)reducibility of signed perm-rep (Prop. in Supp. A.I). and it thus makes sense to speak of the irreducibility an entire conjugacy class p The significance of the conjugacy relation is that conjugate signed perm-reps correspond to the same G-SNN (see Sec. 3.2 we are thus interested the classification of irreducible signed perm-reps only up to conjugacy.
Our first theorem below gives the desired classification of signed perm-reps For H, K S G, let (H, K) denote the paired conjugacy class
K) = Hg. = G}.
Define the following set of conjugacy classes of subgroup pairs:
Cº [HHHK)
11 < G / K| 23.
For every (H, K)C 22 we define signed perm-rep PHK as follows: Let (gi...., 9n) be
transversal of G/H with 9i E K. For each i = 1,... define g-i gch for some h E H K
H K = and h if H : K] = 1. Then define the signed perm-rep PNK such that PHK (g)e: ej if gg: K = 9j K for every i,j = +1..., tn.
Theorem 1. We have:
(a) Every P is irreducible.
We assume some familiarity with group theory including semidirect products and quotient groups, conjugacy classes subgroups, and group action [see Herstein (0066.. 2 All proofs, well as additional lemmas and useful propositions, can be found in the supplementary material.
3

---

(b) For every irreducible signed perm-rep pl, there exists a unique (H,K) K) such that p' is conjugate to РиK--
Theorem equivalently states that the set
R (G) = toHk : K) E c222
a partition on the set of all irreducible signed perm-reps into conjugacy classes. We will say Pи has rype H K|- ie.. type 1 if H K and type 2 otherwise. For the interested reader, we note that PaK is the rep of G induced from the rep ø H + {-1,1} where = ker(o).
2.3 Group cohomology
Group cohomology offers an alternative perspective on the classification of signed perm-reps and the basis for the directed graph visualizations in Sec. 4.1 and Supp. C.2 Note, however, that technical understanding of group cohomology is not required for most of this paper, and we give only a high-level overview here. Let p be a signed perm-rep and π : G + P(n) and G H+ ((n) the unique functions satisfying p(g) = w(g) (g) E G. The function is called cocycle and describes the sign flips associated to the action of through p. It can be depicted using colored directed graphs as in Fig. [1 (and Figs. o where arcs of different colors represent the actions of diffrent generators of and dashed ares represent sign flips. The cocycle w thus encodes topological information about how space "twists"
move through it by the action of G.
If p' is another signed perm-rep conjugate to p by diagonal matrix in ((2), then its corresponding cocycle w' is said to be cohomologous to w, and the set of all cocycles cohomologous to w is said to form cohomology class. the reason for this equivalence is that the number of sign flips around a cycle is unique only up to an even number of sign flips; thus, the solid vs. dashed ares of the directed graphs in Fig. [ are not unique. The set of all cohomology classes associated cohomology group, and it turns out that the classification of these cohomology groups and their elements gives another way look at the classification of the signed perm-reps of G; see Prop. [5] in Supp. A.3 for details. Type 1 signed perm-reps are then the ones corresponding to the identity elements of these cohomology groups i.e., the cohomology classes with no sign flips-and and type signed perm-reps correspond to the elements describing nontrivial sign flip patterns.
single π forms
Finally, as we are only interested signed perm-reps up to conjugation, we regard two cohomology classes as equivalent if their corresponding signed perm-reps are related by conjugation with permutation matrix in P(n) Concretely, this ensures that colored directed graphs isomorphic to those shown in Fig. I are in fact considered equivalent to them.
3 Classification of G-SNNs
3.1 Canonical parameterization
shallow neural network (SNN) is a function f : Rm + R of the form
(1) where W E Raxm and a, b I for some n, and d R.. Here ReLU is the rectified linear unit activation function defined as ReLU(()) = max(0, elementwise. The parameterization of an SNN given in Eq. D contains redundancies in the sense that different parameter configurations can define the same function. For example, applying a permutation to the rows of o, b, and W generally results different parameter configuration but always leaves of invariant. Also, by the identity
f(x)
ReLU x b) d,
ReLU(2x)) ReLU(=)- H-22)a, x E R. f-1,1);
(where H is the Heaviside step function; see Prop. 16 in Supp. B}. the reflection of one or more rows of the augmented matrix [W] 6] in Eq. together with the addition represented the sum of two hidden heurons-leave f invariant; e.g..
linear term ferm-which can be
fxx) a ReLUI- (Wx x + b)] + ReLU (Wx + b)] ReLUI-a (Wx b)] d.
"These visualizations are based geometric perspective of cohomology Cayley graphs (Druuu and Kapovich 2018 sec. 5.9]: see [Tao 2012 for intuition.
For the interested reader, this equivalence amounts to quotienting the cohomology group 71 (G, M) by the automorphism group of the G-module (M, r): Prop. 15 (b) in Sup. A.3 for details.

---

Note that these permutation and reflection redundancies form the group PZ(n). The lemma below will help us define "canonical parameterization" in which such redundancies are eliminated.
Lemma 2. Let On be the set of all augmented matrices [W bj E [Rax(m+)) such that the rows of W have unit norms and no two rows of (W b) are paraltel. Let On C +n be a fandamental domain under the action of PZ((n) Let f :R + R be SNN of the form in Eq. [ Then there exist unique n, E 14 [W, b.] E Smn.. a, E -R" with nonzero elements, C2 E RT, and d2 E R. such that:
[(x) = a. ReI.U(W,. x + b.) + c. + d, Vx E IR
Here, since the rows of [W. b.] are pairwise nonparallel, then no two hidden neurons can form a linear term; all such hidden neurons are collected the unique term cº z. As a result, n, S n as n, is the smallest number of hidden neurons possible. We refer to the unique parameterization of the SNN f terms of (a., b,: C.. dh,, W.) as its canonical parameterization, and the SNN is then said to be in canonical form. We call b., W and the rows of W. the canonical bias, weight matrix, and weight vectors of the G-SNN respectively. Note that the canonical parameterization is a function of the choice of fundamental domain ??,..
3.2 G-SNNs and signed perm-reps
For f to be G-invariant SNN (G-SNN), the action of G on the domain of f must be equivalent to one of the redundancies in the parameterization of SNNs. In the canonical parameterization, however, this means that the parameters of f and of f o g must be identical. This places constraints on the canonical parameters of a G-SNN, as made precise in the lemma below.
Lemma 3. Lei f Rm + R be an SNN expressed in canonical form with respect to fundamental domain Qr C On.. Then J is G-invariant if and only if there exists a unique signed perm-rep P: G + PZ(n.) such that the canonical purameters of J satisfy the sollowing equations for all g E G:
P = W.9
(3)
(g)a._ a2
(4)
(g)bb. = b+
(5)
gc. = c. + 1 +2(11 (T a..
We see that the constraints on the canonical parameters of a G-SNN are not necessarily unique, as they depend on a signed perm-rep p. whence the classification program of G-SNNs in this paper. Lemmal thus establishes the promised connection between G-SNNs and signed perm-reps. To formalize this correspondence, let SNN(G) be the set of all G-SNNs and RP the of all conjugacy classes of signed perm-reps of G. Define the map F SNN + R (P) such that if f SNN(G) and p is the corresponding signed perm-rep appearing in Lemma 3 then F(f) = pp% Then F is well-defined function in the sense that F(J) does not depend on the choice of fundamental domain Pn_.. Indeed, a change of fundamental domain 22, - 12, induces a transformation
[W. b.] + A(W. b.] for unique A P'(n=). By Eq. this in turn induces the conjugation + Ap(-)--1 thereby leaving F(f) = p invariant.
We now define G-SNN architecture to be subset S C SNN(G) such that S F- (7) for some 7 E (F); it consists of all G-SNNs that are constrained to respect the same representation of G. In this language, the purpose of this paper is classify all G-SNN architectures.
G-SNN f said to irreducible' if F(J) is a conjugacy class of irreducible signed perm-reps. Let fPZ denote the G-SNN architecture containing the G-SNN f, and observe that if f is irreducible, then so are all G-SNNs in frZ in this case, f is said to be an irreducible architecture.
It can be shown that every G-SNN admits a decomposition into a sum of irreducible G-SNNs in Supp. B.2 follows that to classify all G-SNN architectures, it enough to classify all irreducible G-SNN architectures. This amounts to two tasks: (1) Classify all irreducible signed perm- rep conjugacy classes ran(F), and (2) for every irreducible p. E ran(F). give a parameterization of all G-SNNs in the architecture F (pP7).
'If' a group G acts on a set X, then a fundamental domain is set Ω S. X such that {gft 9 E G is partition of X. An example fundamental domain in θ, under the action of PZ(n)) is given in Prop. 18 (see Supp. B.I
5

---

3.3 The classification theorem
We now state our main theorem, but first we introduce some notation. If A is a linear operator (resp. set of linear operators), then let PA be the orthogonal projection operator onto the vector subspace that is pointwise-invarian under the action A (resp. all elements of A). Note that is finite orthogonal group, then [Serre 1977 sec. 2.6]
PA
a.
A
Let sta( denote the stabilizer subgroup
sta((A) = E:: 9P :
Theorem 4. Let PHK be an irreducible signed perm-rep of G, and let {gl,... I be transversal
of G/H such that PHK (gg)ee e,. Let r K] 1. Then:
(a) PHK (ran(F) and only ifsta(Pk TP K. PZ
P2 if and only if the canonical parameter 6 of have (b) If PHK E &ran(F) F), then f & F=
the following forms:
W. Σ (:gguw)] w E rannPp - T PPH); || =
(7)
al, a +
(8)
b (1 T)bI,
c. 2
W., a + +c ran(
(10)
The condition in Thm. 4 a helps to exclude architectures where Eq. 7 yields redundant weight vectors. Combining this with the classification of irreducible signed perm-reps up to conjugacy [T. we obtain complete classification of the irreducible G-SNN architectures corollary. Theorems 4 can be assembled into an algorithm that enumerates irreducible G-SNN architectures for any given finite orthogonal group G. We implemented the enumeration algorithm using combination of GAI and Python: our implementation currently supports, in principle, enumerated all
immediate
all finite permutation groups G P(m) Using code implementation, irreducible G-SNN architectures for one permutation representation of every group G, |G] I 8, up to isomorphism. We report the number of architectures, broken down by type, for each group in [ (see Supp. C. a discussion included there as well). A key observation is that the number knowledge have appeared in the literature previously-
of type 2 architectures- which significant; e.g., for the dihedral permutation group G D2 on four elements, there are five type architectures compared seven type architectures.
Script execution time for each group was under 2 seconds. Nevertheless, we remark that our code is not optimized for speed and scalability as our purpose exploration and intuition. As future work, we will work out Thm. 4 for specific families groups to derive more direct and efficient implementations, We will also investigate how build G-SNN architectures from smaller G1 SNN and SNN architectures where G is a (semi)direct product of G and G2. Finally, we note that for the application of NAS, we will probably never enumerate all G-SNN architectures; instead, we will generate them on-the-fly as we move through the search space.
'This is important subtlety. By specifying "canonical parameters". we exclude from Eqs. 10 parameter values that do not correspond canonical parameterization. For example, cannot lie in proper subspace ran( Pk - 7 PHr) C ran PP - 7PH) as this would result in at least two rows of [W, | b.]] being parallel. For the same reason, for type architectures, we must have b * 0 if any two rows of W, are antiparallel.
"GAP is computer algebra system for computational discrete algebra with particular emphasis on computa- tional group theory [GAP].
*Code for our implementation and for reproducing all results in this paper is available at: https://github
com/dagrawa2/gaa gggnnn_ classification_con

---

Architecture 0.0
Architecture 2.0
1
2
3
4
<
Architecture 3.0
Architecture 1.0
Architecture 1.1
Architecture 3.1
Figure 1: Constraint pattern of the weight matrix and illustration of the cohomology class of each irreducible G-SNN architecture for the cyclic permutation group G = C-- The number of rows (resp. columns) in each pattern is the number of hidden (resp. input) neurons in the architecture. In each pattern, weights of the same color and texture (solid vs. hatched) are constrained to be equal; weights of the same color but different texture are constrained to be opposites (colors should be compared across different architectures). neurons of the architecture, and the represent the action of the generators of of the weight matrix (all arcs are the same color because Cg has only one generator). Solid (resp. dashed) ares preserve (resp. reverse) orientation. See Supp. C.2 C.2 for richer example- the dihedral permutation group De.
each cohomology class illustration, the nodes represent the hidden the rows
Examples
4.1 The cyclic permutation group
Consider the group G Ce of all cyclic permutations the dimensions of the input space R There are six irreducible G-SNN architectures for G Cs (Fig. []] "architecture i.j" refers to where Ho, H3 isomorphic to C1, Ca. Ca. and Co respectively and K₃ H; such that [[4 K2 = j 1. Architectures i.0 are thus exactly the type ones, and two architectures i.j and i.k for distinct j and correspond to inequivalent cohomology classes in the same cohomology group. Note that the architectures with n hidden neurons correspond to H, C'a.
(pt,, PZ
The type architectures i.0 correspond to ordinary unsigned perm reps of G. These are the "obvious" architectures that practitioners probably could have intuited. From Fig. [ we see that the weight matrices of these architectures are constrained to have circulant structure; cyeling the input neurons is thus equivalent cycling the hidden neurons, leaving the output invariant as all weights in the second layer (not depicted) are constrained to be equal. This circulant structure is also apparent cohomology class illustrations.
Architectures i.1 are type and are perhaps less obvious. Cycling the input neurons is equivalent to cycling the hidden neurons only up to sign; if we cycle a weight vector around all the hidden neurons,
See Supp. C for richer examples that could not fit in the main paper.

---

Type
Type 2
2.0
20
15
15
14
10-
0.5
0.5
0.0
0.0
-0
-35
-1.0
-1.0
-1.9
-15
2.0
2.0
Figure Contour plots of the two irreducible G-SNN architectures for the 2D orthogonal represen- tation of G Cg. The blue vectors are the weight vectors- i.e., rows of the weight matrix W., and their offsets from the origin in the type architecture indicate the bias b,. The red vector in the type 2 architecture is the canonical parameter of the G-SNN. See Supp. C.3 for richer example- the dihedral rotation group Dy-
then we not return to the original weight vector but instead to its opposite. we think of the dashed ares in the cohomology class illustrations "half-twists" in cylindrical band, then Architectures i.I correspond to a Möbius band, thereby distinguishing them topologically from architectures i.0. Alternatively, in terms of graph colorings, if the nodes incident to solid (resp. dashed) constrained to have the same (resp. different) color(s), then architectures i.1 are the only ones not 2-colorable.
Observe that top weight vector of architecture i.1 constrained to be orthogonal to that of architecture i.0; this is made precise in Prop. 6n Sec. 5.3 The upshot is that architectures i.0 and i.1 can coincide in function space if and only their weight matrices vanish- i.e., the architectures degenerate into linear functions. Since neural networks think it unlikely that a G-SNN being fit to a nonlinear dataset will degenerate to a linear function at any point in its training: assuming this is true, architectures i.0 and i.1 are effectively confined from one another due to their inequivalent topologies. We discuss this phenomenon more detail in Sec. 5.3
trained with local optimization, then
4.2
The cyclic rotation group
Consider again the group = Cs. this time 2D orthogonal representation where each group element acts rotation by multiple of 60 on the 2D plane. There are only two irreducible G-SNN architectures- one of each type. visualize these architectures, we set w = [1, 0] T a 1, b = 0.5, 0, and d, 0 in Thm. (b) Based on their contour plots (Fig. D we find that the level curves of the type (resp. type 2) architecture are concentric regular dodecagons (resp. hexagons); both architectures are thus clearly invariant to 60% -ot-rotaio
In the type architecture, the hexagonal level curves increase linearly with radial distance. Since the bias is required to be zero (Eq.9). a sharp minimum forms at the origin. The architecture has three weight vectors and thus three hidden neurons, and additionally has a linear term (whose gradient shown in red in Fig. 2). weight vectors with C3 symmetry. Observe that if we cycle three hidden neurons the type 2 architecture so that each weight vector is rotated three times by 60", then we obtain the three weight vectors with reversed orientation; this a manifestation of the nontrivial topology of the type 2 architecture.
when combined with weight vector 2 using Eq 2 results in three
The type architecture has six weight vectors and thus six hidden neurons. Observe that for each weight vector, there is another that is its opposite. Thus, for [W_ b_] to have pairwise nonparallel rows (see Lemma 2 the bias b, bī must be nonzero, whence the dodecahedral region in the example G-SNN (Fig- 2 where its value plateaus to zero. However, in the asymptotic limit the type architecture degenerates to the type architecture but with twice the number of hidden

---

neurons. Thus, even though the two architectures are topologically distinct, the type architecture can get arbitrarily close the type 2 architecture function space (see Supp. C.3 for a richer example- the dihedral rotation group fh-which has irreducible architectures that cannot easily access one another). This has important consequences, which we discuss more in the next section.
5 Remarks
5.1 Numbers of hidden neurons
The type 1 and type 2 irreducible architectures for the G = Cg rotation group (Fig. 2 have six and three hidden neurons respectively. In addition, the linear term C, in the canonical form of G-SNN-if not zero-can be interpreted as two additional hidden neurons. It follows that general G-SNN that is a sum of copies of the two irreducible architectures cannot have 3k + hidden neurons for any integer k. Thus, if we fit traditional fully- colleceoddeeeed SNN with 3k + hidden neurons to a dataset invariant under 60% -ottations, then the fit SNN can be a G-SNN if and only if one or more of its hidden neurons are redundant- e.g., one hidden neuron is zeroed out, or four hidden neurons sum to form linear term, leaving (3k: + 1) 4 = 3(k 1) hidden neurons corresponding to "proper" weight vectors. Although this is rather simple example, suggests the possibility of more severe or complicated restrictions on numbers of hidden neurons for larger and richer groups G. In these cases, the redundant hidden neurons could perhaps make it more difficult for the SNN to discover the symmetries in the dataset and thus weaken the model, all at the cost of additional computation. We thus conjecture that one factor that determines the optimal number of hidden neurons in traditional SNNs is whether the number admits G-SNN architecture, or or-going further-how many different G-SNN architectures the number admits.
5.2 Network morphisms
Let f. F- (p.%) i 1, be two G-SNN architectures. If for every f E f:2 there exists a that converges to f in the topology of uniform convergence on compact 2 In the cyclic rotation example in Sec. 4.2, as already discussed there, the type architecture is asymptoticly included the type architecture. In the cyclic permutation example in Sec. 4.1 the asymptotic inclusion! mIl furnish a 3-parrttee topology on the space of irreducible architectures (Fig. 3): here every directed path an asymptotic inclusion, and the individual ares could be called "irreducible asymptotic inclusions". This topology provides the necessary structure to perform neural architecture search (NAS), where the irreducible inclusions serve as the network morphisms [Wei et al. [016]. NAS, network morphisms are used to map underfitting architectures to larger ones, after which training resumes; the upshot that the larger architecture need not be re-initialized, thereby significantly cutting computation time. In future work, we will run NAS on the space of irreducible G-SNN architectures to learn an optimal
sequence [S E S 12 2
sets 10 then we say f2 is asymptotically included in f 2 and write f²² + +f"
G-SNN in greedy manner.
Although the above definition of asymptotic inclusion is functional-ande -antional-aanllyicc, the following theorem gives group-theoretic characterization that is more amenable to computation.
Theorem 5. Let f! = (p (, K. for i = 1, 2 be two irreducible G-SNN architectures. Then f8" f1% iff there exists (H, K)
such that H S H2, K < K2, and H n K2 K.
The proof (see Supp. D.I. relies on a non-canonical parameterization of G-SNNs; a lemma (Lemma 22) that invokes the Arzelà-Ascoli Theorem; and Thm. (a) Theorem thus be used to generate network morphisms such as those in Fig. algorithmicly. Observe that as a corollary, since subgroup lattices are connected and subgroup inclusion transitive, then there are no "isolated" G-SNNs; every G-SNN architecture is connected to another by some network morphism.
5.3 Topological tunneling
IIn this topology. a sequence (f)) of functions is said converge iff it converges uniformly on every compact set the domain.
'TThese inclusions are "asymptotic" because no two rows of the canonical parameter [W. b.] can be exactly antiparallel, preventing the degeneration of one architecture into another.

---

Recall the discussion in the final paragraph of Sec. 4.1] where we said architectures i.0 and i.1 coincide in function space only when their weight matrices are zero. We see this phe- nomenon again in the dihedral rotation group example (see Supp. C.3). Both these are instances of the following proposition, which states that architectures corresponding to distinct cohomology classes are in sense orthogonal.
3.0
53
Proposition 6. Let wh and w2 be the first rows of the canonical weight matrices two irre- ducible G-SNN architectures (P and F (Pikk) where Ki + K2. Then w W2
Figure 3: Network morphisms between irre-
ducible G-SNN architectures for the cyclic per- mutation group in black represents asymptotic inclusion. Red houbled-arrowed ares represent the feasibility of topological tunneling. See Supp. C.2 for richer example- the dihedral permutation group D6-
Cs. Every directed path
We call the resulting phenomenon "topological confinement", and it implies that for example, Alice generates nontrivial dataset using archi- tecture 1.1 for G = Cs (Fig. D but Bob con- structs architecture 1.0 to enforce G-invariance (as it one of the more intuitive architectures), then Bob's network will fail to fit to Alice's dataset, though Bob's network has the right "size"; this suggests that the way enforce G- i-invariance in a network is important. Rather than randomly selecting between architectures 1.0 and 1.1, or resorting to larger architecture such as 0.0, propose allow "topological tunneling", where the cohomology class of an architecture is transformed by applying the appropriate orthogonal transfor- mation the top weight vector. This allows in way analogous to cutting and regluing a Möbius band to remove the twist. Topological tunneling thus introduces "shorteuts" between certain points in architecture space, hopefully facilitating NAS (Fig. 3 We plan to test this in practice in future work.
transform weight-sharing pattern into another
Conclusion
We proved Thm. which gives classification of all (irreducible) G-SNN architectures with ReLU activation for any finite orthogonal group G' acting on the input space. The proof is based on correspondence of every G-SNN signed perm-rep of G acting on the hidden neurons. We also proved 5 which characterizes the network morphisms between irreducible G-SNN architectures and thus together with Thm. completely describes G-SNN architecture space. A key implication of our theory is the existence of the type 2 G-SNN architectures, which to our knowledge have never been explicitly identified the literature previously.
Various next steps can be taken towards the ultimate goal of G-invariant neural architecture design. On one hand, we could try extend Thm. to deep architectures, which would require us to understand the redundancies of deep network. We could then investigate the behavior and utility of type symmetry constraints the context of real deep learning benchmark tasks. the other hand, we could first go ahead and investigate NAS on G-SNNs. For a scalable NAS implementation, we could work out Thm. for specific families of groups to derive more efficient implementations, and we could try to develop an "algebra" of G-SNNs where G is a (semi)dired) product of smaller groups. Finally, we could consider what are "good" combinations of irreducible G-SNN architectures; e.g.. which sequences of irreducible architectures converge in sum to universal G-invariant approximators fastest? Perhaps answers to these questions could aid in transforming G-invariant neural architecture design from an art to science.
Acknowledgments and Disclosure of Funding
D.A. and J.O. were supported by DOE grant DE-SC0018177 D.A. was additionally supported by NSF award No. 2202990.
10

---

References
Yossi Arjevani and Michael Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry. Advances in Neural Information Processing Systems, 33:5441-5452, 2020.
Michael Baake. Structure and representations of the hyperoctahedral group. Journal of mathematical physics, 25(1133317-33182 1984.
Serge Bouc. Burnside rings. In Handbook of algebra, volume 2, pages 739-804, Elsevier, 2000.
William Burnside. Theory of groups of finite order. The University Press, 1911.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference machine learning, pages 2990-2999. PMLR, 2016.
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolutional networks and the icosahedral cnn. In International conference on Machine learning, pages 1321-1330. PMLR, 2019a.
Taco S Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant cnns on homoge- neous spaces, Advances in neural information processing systems, 32, 2019b.
George Cybenko. Approximations by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2: 183--192 1989.
Cornelia Drutu and Michael Kapovich. Geometric group theory, volume 63. American Mathematical Society, 2018.
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, al. Neural architecture search: A survey, J. Mach. Learn. Res., 20(55):1-21, 2019.
GAP. GAP Groups, Algorithms, and Programming, Version 4.11.1.
https: :/www..//www..// gap- system. org. 2021.
Israel Herstein. Topics in algebra. John Wiley Sons, 2006.
Piotr Kicki, Mete Ozay, and Piotr Skrzypczyíski. A computationally efficient neural network invariant to the action of symmetry subgroups. arXiv preprint arXiv:2002.07522 2020.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning. pages 2747-2755. PLMR, 2018.
Haggai Maron, Heli Ben- Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. volume 7, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pages 4363-4371. PMLR, 2019b.
Renato Negrinho and Andre Martins. Orbit regularization. Advances neural information processing systems, 27, 2014.
Piyush C Ojha.
Enumeration of linear threshold functions from the lattice hyperplane intersections. IEEE Transactions on Neural Networks, (44)8839-8500 2000.
Charles Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 652-660, 2017.
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In International Conference on Machine Learning, pages 1996-8006. PMLR, 2020.
Serre. Linear representations of finite groups, volume 42. Springer, 1977.
11

---

Terence Tao. Cayley graphs and the algebra of groups. https://terrytao. wordpress com/ 2012/05/11ccayloy -raaass-gaa--aa and tad-the-aad aad-the-aggebra- latggerra-ffgrrupseee -roupss 2012. Accessed: 2022-05- 01.
Bastiaan S Veeling, Jasper Linmans, Jim Winkens, Taco Cohen, and Max Welling, Rotation equiv- ariant cnns for digital pathology. In International Conference on Medical image computing and computer-assisted intervention, pages 210-218. Springer, 2018.
Tao Wei, Changhu Wang, Yong Rui, and Chang Wen Chen. Network morphism. In International Conference on Machine Learning, pages 564-572. PMLR, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. !
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "lgquMrzck27", "reviewer": "Reviewer_XXff", "summary": "While equivariance has been shown to be a useful principle for neural network design, there exist many different equivariant architectures in the literature.\nThis paper provides a first step to answer the question \"what are, in practice, the best design choices?\"\n1) by decomposing any G-equivariant depth-2 ReLU network as a sum of irreducible G-equivariant networks\n2) and by classifying all equivalence classes of such irreducible networks.\nThe paper also includes a method to find such irreducible networks and practical ideas to leverage them in a Neural-Architecture-Search (NAS) context.\n", "questions": "In the second part of the paper, the authors propose leveraging the irreducible networks to build larger model in NAS.\nBy cleverly using \"topological tunneling\", one can avoid resorting to larger architectures (i.e. full GCNN models, which use the regular representation of G).\nI am curious if similar insights can be used for the inverse process in a \"pruning\" context, i.e. starting from a large pre-trained GCNN architecture and, then, pruning redundant channels (i.e. zero/redundant irreducible sub-networks) within the regular representations.\n\n\nIs it correct that the representation in Theorem 1 is the induced representation from H to G of a 1-dimensional representation of H?\nThis might be useful to mention.\n\nLine 153-154: it is not immeditely clear what construction (with the additional two neurons) the authors have in mind. This becomes clearer later after Lemma 3 (although it's never explained the two neurons are necessary to avoid the ReLU non-linearity). I would recommend spending a few more mords earlier to clarify this construction.\n\nLine 203: Theorem 5a: $\\tau$ seems to be an integer in $\\{0, 1\\}$ while $P_H$ and $P_K$ are sets of matrices. Is that correct? Then, isn't a scalar factor multiplied to $P_A$ irrelevant in the definition of $\\text{st}_G$?\n\nLines 286-290: the statement about the additional neurons making it harder to discover symmetry and to generalize seems in contrast with the recent understanding about wide neural networks, where overparameterization is considered useful for optimization and generalization.\n\nLine 293: Shouldn't $f^{PZ}_2$ be asymptotically included in $f^{PZ}_1$?\n\nLine 343: I am not sure I understood the sentence \"any patters in G-SNN architecture space are unclear\". Could you clarify or elaborate further on it?\n\n", "limitations": "The method proposed is limited to 1-hidden layer ReLU networks.\nAs the authors clearly stated, this provides only a first step in answering the original question.\nHowever, the analysis provided applies to individual layers in a deep network and, therefore, can still turn out useful for NAS of deeper models.\n\n\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem tackled is relevant and well motivated.\nThe idea is novel and can be of practical interest in the context of NAS, as argued by the authors.\n\nThe presentation is clear, although the assumption that the reader is familiar with group cohomology makes the manuscript less accessible.\nFor instance, I think the authors could include some additional comments after Proposition 2, trying to provide some more intuitions about its meaning.\n\nWhile it would be interesting to see an implementation of the NAS ideas proposed here (maybe, in a simple experimental setting), I think the theoretical work is a sufficient contribution.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i6KdeA98NDt", "reviewer": "Reviewer_FsV1", "summary": "The paper gives a classification of all shallow (one hidden layer) ReLU networks that are G-invariant, i.e. invariant under an operation of a an element of a group G on the input. The main result of the paper is a classification theorem, that allows the authors, given some finite orthogonal group G, to classify all the \"unique\" shallow ReLU network architectures. That is, using the results in the paper one can find all the possible network architecture and weight sharing \"schemes\". To my understanding, this is the first work to achieve such result.", "questions": "- How does the number of neurons grow with the size (or \"complexity\") of the group G?\n- What is the computational cost of running the enumeration algorithm? It seems that this algorithm was run on small groups, is it practical to run on larger group, or does the run-time scale badly with the group size?\n- Is the sorting of architectures via the asymptotic inclusion applicable for every group?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a novel result that improves the fundamental understanding of group invariant networks. While group invariant networks have been well-studied in previous literature, the result in the paper enables a more detailed understanding of such invariant network, by providing a complete classification of shallow ReLU networks invariant under the operation of a finite orthogonal group. Using the main theorem, the authors can compute all the invariant network architectures given such group. These result open up interesting questions for further research, such as extension of the results to deep networks and using the technical tools developed in the paper for improving neural network architecture design in practice.\n\nWhile the mathematical contribution is sound, interesting and novel, I believe that the discussion on the implication of the results lacks clear and rigorous statements. It is not clear in what cases the sorting of the G-SNN architectures via the asymptotic inclusion can be achieved, or how exactly does this improve neural architecture search. It could be helpful to discuss in more quantitative detail what, potentially, are the computational benefit of the classification introduced in the paper to NAS. The topological tunneling section could also benefit from more rigorous statements. It is claimed that the results in the paper imply some failure cases due to bad initialization. What exactly is the chance of failure? Having a weights matrix with any weight-sharing has probability zero, so how can this fail due to initialization?\n\nAnother issue I have is with the statement of Lemma 3. It seems to introduce a unique parameterization of neural networks, but I believe it lacks some statement saying that all \"equivalent\" networks have the same paremeterization.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "a5Op7-ejwiO", "reviewer": "Reviewer_7sGN", "summary": "Before I begin, I have to note that I'm not very familiar with the concepts in algebraic topology required to fully understand this paper, so I find it unfortunate that this paper ended up in my batch. I have put my best efforts into evaluating this paper, but please take my words with a grain of salt.\n\nThis paper analyzes $G$-invariant 1-hidden-layer ReLU networks (called $G$-invariant SNNs or $G$-SNNs) for a finite orthogonal group $G$. Since fully-connected networks inherently contain redundancies such as permutation of hidden nodes, the authors first remove these redundancies via defining a \"canonical parameterization\" (Lemma 3). For any SNN $f$, the authors show that $f$ is $G$-invariant if and only if there exists a unique \"signed permutation representation\" $\\rho: G \\to PZ(n_*)$ such that the canonical parameterization satisfies a set of identities under $\\rho$ (Lemma 4). Then it can be shown (Prop 18) that any $G$-invariant SNN can be decomposed into a sum of *irreducible* $G$-SNNs (whose corresponding $\\rho$ is *irreducible*). Such irreducible $G$-SNNs has a particular form described in Theorem 5, and Theorem 1 & Prop 2 show that the corresponding $\\rho$'s can be categorized into conjugacy classes of type 1 or 2, providing a \"classification theorem\" of $G$-SNNs.", "questions": "Q1. Although the prior works by Kondor and Trivedi (2018) and Cohen et al (2019) are for sure relevant, my understanding is that this paper is looking at a very slightly different problem. The existing two papers focus on $G$-equivariant networks (using $G$-equivariant layers) whereas this paper focuses on $G$-invariant networks. Is my understanding correct? Can your results say something as well about $G$-equivariant networks? In fact, if you sum up the output nodes of a $G$-equivariant network it gives you a $G$-invariant network, and the $a_* = a1$ part in Theorem 5b is reminiscent of this observation…\n\nQ2. Can the theory extend to deeper networks? It seems to me that even defining the canonical parameterization is more challenging; what are other technical barriers? What about extensions to infinite groups (such as continuous rotation)?\n\nQ3. In Lemma 3, how does $n_*$ compare with $n$ usually? Is it smaller or bigger? Or it depends on the parameters $a, W, b$?\n", "limitations": "I think the authors were clear about the limitations of their work, and they indicated some of them as their future research directions, which can be helpful for readers.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nS1. This paper seems to convey solid mathematical theory that allows us to decompose $G$-invariant networks into several subnetworks of particular forms. This helps us understand the parametric forms of $G$-invariant networks better. Due to the lack of background, I was not able to check the correctness of the results though.\n\nS2. Theorems 1 and 5 lead to an algorithm that can enumerate all irreducible $G$-SNN architectures for any finite orthogonal group $G$, which should prove helpful if you are a practitioner and you need to build a network that is invariant to a particular $G$.\n\nS3. I found the connection to neural architecture search quite interesting, and I think further developing this theory can lead to a good algorithm for $G$-invariant NAS. Looking forward to the authors' future developments in this direction.\n\nWeaknesses\n\nW1. The paper is very math-heavy and I am worried if this paper would be readily accessible to the general audience at NeurIPS. The equations are quite heavy in notation and difficult to digest. Perhaps the authors can start with some illustrations (e.g., those in Sec 4) and then proceed to more abstract groups? Also consider reordering the main results a bit; personally I thought the paper would have been easier had it started from the canonical parameterization (Lemmas 3 and 4), then decomposition into irreducible $G$-SNNs, and then the classification of $G$-SNNs and corresponding irreducible signed perm-reps (Theorem 5, 1 and Prop 2).\n\nW2. While the current theory seems concrete, I'm not sure yet about the potential impact of this paper because it is now limited to shallow networks. Extensions to deeper networks look quite challenging.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3zBrETKKCl", "reviewer": "Reviewer_qWKe", "summary": "The paper analyses the shallow architectures that are invariant to specific group symmetries. ", "questions": "NA", "limitations": "The authors do not really discuss the limitation of this work.", "rating": 4, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Identifying and understanding G-invariant networks is an import question\n\nWeaknesses:\n- Questionable significance. The paper addresses a very specific setting that I am not sure has any merit. Specifying what specific layers are G-invariant or G-equivariant has been done before, e.g. Maron et al \"Invariant and Equivariant Graph Networks\". This paper only handles 2-layer networks.\n- The paper claims to analyses architectures so it could help find the optimal ones, but it only handles very limited and standard architectures.\n- Even in the 2-layer network case the significance of theorem 5 which is the main focus of this paper compared to previous characterizations of invariant networks it is unclear to me what additional benefit does this approach have.\n- The paper is not clear \n- Considering the reflection symmetry is very unnatural as you need to change the architecture to get an equivalent network. While this complicates the analysis greatly, it has no practical importance as one can always standardize an input dimension $x_i$ to be possitive/negative if the output was invariant to this specific sign.\n-If the paper considers symmetries of NN, then a symmetry that is relevant is homogeneity to positive scalars as $a^TReLU(Wx+b)=\\frac{1}{c}a^TReLU(cWx+cb)$.\n\n\nRemarks about the writing:\n- In proposition 2 the others talk about $M_H$ as a G-module over $\\mathbb{F}_2$, but that isn't well defined. A G-module is any abelian group that G acts on so the meaning of a abelian group over a field isn't clear. It seems from context that the authors consider $M_H$ as the vector field $\\mathbb{F}_2$ but they don't define (at least wasn't clear to me) the G-module they worth with.\n- In lemma 4 you claim there is a unique perm-rep that gives the canonical equation specific properties, however as this is the canonical  form its shapes shouldn't be influenced by a symmetry working on it. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept