Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

This 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.
strengths_and_weaknesses: Strengths

S1. 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.

S2. 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$.

S3. 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.

Weaknesses

W1. 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).

W2. 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.
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…

Q2. 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)?

Q3. In Lemma 3, how does $n_*$ compare with $n$ usually? Is it smaller or bigger? Or it depends on the parameters $a, W, b$?

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: While equivariance has been shown to be a useful principle for neural network design, there exist many different equivariant architectures in the literature.
This paper provides a first step to answer the question "what are, in practice, the best design choices?"
1) by decomposing any G-equivariant depth-2 ReLU network as a sum of irreducible G-equivariant networks
2) and by classifying all equivalence classes of such irreducible networks.
The paper also includes a method to find such irreducible networks and practical ideas to leverage them in a Neural-Architecture-Search (NAS) context.

strengths_and_weaknesses: The problem tackled is relevant and well motivated.
The idea is novel and can be of practical interest in the context of NAS, as argued by the authors.

The presentation is clear, although the assumption that the reader is familiar with group cohomology makes the manuscript less accessible.
For instance, I think the authors could include some additional comments after Proposition 2, trying to provide some more intuitions about its meaning.

While 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.

questions: In the second part of the paper, the authors propose leveraging the irreducible networks to build larger model in NAS.
By cleverly using "topological tunneling", one can avoid resorting to larger architectures (i.e. full GCNN models, which use the regular representation of G).
I 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.


Is it correct that the representation in Theorem 1 is the induced representation from H to G of a 1-dimensional representation of H?
This might be useful to mention.

Line 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.

Line 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$?

Lines 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.

Line 293: Shouldn't $f^{PZ}_2$ be asymptotically included in $f^{PZ}_1$?

Line 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?


limitations: The method proposed is limited to 1-hidden layer ReLU networks.
As the authors clearly stated, this provides only a first step in answering the original question.
However, the analysis provided applies to individual layers in a deep network and, therefore, can still turn out useful for NAS of deeper models.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

While 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?

Another 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.
questions: - How does the number of neurons grow with the size (or "complexity") of the group G?
- 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?
- Is the sorting of architectures via the asymptotic inclusion applicable for every group?
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper analyses the shallow architectures that are invariant to specific group symmetries. 
strengths_and_weaknesses: Strength:
- Identifying and understanding G-invariant networks is an import question

Weaknesses:
- 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.
- The paper claims to analyses architectures so it could help find the optimal ones, but it only handles very limited and standard architectures.
- 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.
- The paper is not clear 
- 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.
-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)$.


Remarks about the writing:
- 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.
- 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. 



questions: NA
limitations: The authors do not really discuss the limitation of this work.
review_title: null

Meta-review: metareview: Three reviewers gave quite positive ratings and comments on the paper. One another reviewer gave lower ratings. The AC thinks the reviewer with a low rating raised quite reasonable questions but found overall, the pros outweigh the cons (which seems to mostly stem from the unclarity in writing). The AC would recommend acceptance but also encourages the reviewers to incorporate the reviews and discussions in the final version. 
confidence: Less certain
Decision: Accept