Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes to make any neural network equivariant by symmetrizing over a subset of the group, rather than over whole group. If the subset selection F(X), depending on input X, is equivariant (gFX=FgX), then the symmetrization is equivariant.
The authors furthermore prove:
1)	When interested in invariant prediction, the subset can be chosen in the quotient G/G_X, where G_X is the stabilizer subgroup of X.
2)	When symmetrizing with a random subsample of F(X), the probability of a particular subsample that deviates from symmetrizing with all of F(X) by less than some epsilon, is bounded below.
3)	When using the symmetrization of a universal model, the resulting model class is universal in the class of equivariant functions.

main_review: Strengths:
-	The paper proposes a very practical strategy of building equivariant nets
-	The universality proof helps convince the reader to use this method
-	The paper considers and experiments on three different instantiations of their method, showing wide applicability.
-	The experimental results show the method performs competitively.

Weaknesses:
-	I don’t understand what’s happening in theorem 4. It considers a subsample $\hat\mu$ of F(X) to be ‘good’ when the symmetrizer that uses the subsample is epsilon-close to the full F(X) symmetrizer. Then it says that the probability of *one particular* good subsample is bounded below.
However, that bound seems vacuus, as plugging any reasonable number brings the bound quickly close to 0. Also, it’s counter-intuitive why the bound should become looser as epsilon grows or as k grows.
What one would want instead is giving a lower bound of the probability that we get *any* $\hat\mu$ that is epsilon-close to the full F(X) symmetrizer. And we want this bound to get higher when epsilon or k increases.
The line below theorem 4 draws a conclusion that would follow from a theorem as I propose it above, not from the theorem in the paper.
As it is currently stated – and I’m not completely misunderstanding – theorem 4 can best be removed from the paper. 
-	It is a bit unclear when the results apply to finite and infinite groups and frames F(X). Everywhere, a summation symbol is used, but in some places, F(X) is infinite. In the infinite cases, which measure should then be used? Can one always use some canonical Haar-like measure? In particular, in the proofs of theorem 1 and theorem 4 this should be discussed.
-	The writing of the paper can be improved. I don’t follow the choice of F(X) for the E(d) case. Which are the 2^d O(d) matrices? Perhaps the authors can elaborate in more detail one of the examples how to construct F(X) in the main paper, and then do the other two in the appendix. 
-	I would like some more theoretical discussion about the choice of F(X). Does the choice of F(X) affect the output? If so, how? Is F(X) required to be continuous / does a continuous (non-trivial) F(X) always exist? What does the topology on 2^G look like? How does this affect the continuity of the symmetrized function? If it is discontinuous, does that affect the universality? When can F(X) be chosen to be finite?
 
Other comments:
-	Why does GA-MLP and GA-GIN+ID only get 50% score on EXP-classify? Are you there using a finite subsample of G or F(X)? And could you give any insight into why we’d expect then complete failure for a G subsample and complete success for a F(X) subsample?
-	In the proof of theorem 5, which norm is used for ||rho_2(g)|| ? It can’t be the max K-norm because K is a subset of the input of phi, not the output. Is it the operator norm?
-	I would like theorem 1 to be put in the main paper, as it shows why the key construction is correct.
-	I think a citation would be appropriate to Finzi et al 2020, “Generalizing Convolutional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data”, as they also consider sampling from the group to build equivariant networks.
-	Why have the authors chosen the name “frame” for F(X)? I know frame as a set of vectors or in the context of a frame bundle.

summary_of_the_review: I think this is a great paper, as it proposes a new practical method for building equivariant networks which is broadly applicable, universal and performs well in practice. I have serious concerns about theorem 4. If the authors convince me why it makes sense, or if they remove it, I will increase my score.

I've updated my score after the response and revision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: **Summary and Contributions**:

The paper introduces a framework called Frame Averaging (FA) that can adapt existing backbone architectures to become invariant/equivariant to new symmetry types. It achieves this by averaging over an input-dependent frame which outputs a subset of groups. Frame averaging is often much more efficient to compute than averaging over the entire group, while at the same time, guarantees exact invariance/equivariance.

On the technical side, the paper also proves that FA-based models have the same expressive power as the original backbone architectures.

On the empirical side, the paper provides new classes of models using FA such as universal Euclidean motion invariant point cloud networks / Message Passing GNNs, and demonstrates their practical effectiveness on several tasks.

main_review: **Strengths**:

- *FA is a very simple framework yet it is potentially very useful*. Group equivariance is an important form of inductive bias in deep learning architectures, but designing architectures that has such equivariance is challenging. It would be very useful if we could adapt any back architecture to become invariant/equivariant to a certain group. However, the previously studied group averaging is computationally infeasible when the group is large, so this paper, which greatly reduces the computational cost of group averaging, could be potentially very useful. I really like this work, and will be looking forward to seeing future development of this work.
- *Technical statements are all sound and proved*. Mathematical statements in this paper all look correct to me, and they have provided proofs. These statements are clear and rigorous.
- *Impressive results*. Using the simple idea of frame averaging, the paper demonstrates state-of-the-art results on several tasks. The results are impressive, which suggests that the FA framework can be very useful in practice.

**Weaknesses**:
- *Lack of simple examples*. While it is not hard to check the correctness of all these statements, it takes me some time to form an intuition of what is proposed in this paper. It would help me a lot if the authors could provide a simple example at the beginning to give readers some intuition. For example, it might be good to work through an example to make MLP translation equivariant (with the simplest possible construction of frames)?  
- *Insufficient study and explanation of the proposed frames*. 
  - The construction of frames in Section 3.1 seems to come out of nowhere. While I could check they are indeed equivariant, I don’t think I understand the motivation or thinking process behind such designs. 
  - Furthermore, can the frames be simplified? As an example, if we let the input $X$ be a function on groups, i.e. $X=f(g),g\in G$. Can we let $F(f) = \arg\max_{g} ||f(g)||$? I might be wrong, but I think this simple construction is also equivariant? 
  - Are the number of elements output by frames the smaller the better, or is there a balance between performance and computational efficiency?

**Questions**:
*How stable are the proposed frames*? For the proposed frames, I would be interested to know how stable they are? That is to say, if I add noise to the inputs, will the output subset of groups be significantly different? 

summary_of_the_review: The paper studies an important problem that could potentially have great impact: How to adapt existing architectures to become invariant/equivariant to a certain group while maintaining the expressive power and computational efficiency of the original backbone model? The paper provides a simple yet effective solution. The technical statements are sound and the empirical results are impressive.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a method to transform a model into an invariant/equivariant model using the Reynolds operator.
In addition, they define a notion called the equivariant frame to compute the Reynolds operator efficiently.
main_review: Strengths 
This paper proposes a general method for transforming existing models into invariant/equivariant models using Reynolds operators.
Combined with other methods, it provides state-of-the-art experimental results.

Weaknesses & Questions
First of all, I would like to point out that the idea of using Reynolds operators to transform a model into an invariant model is found in Kicki et al. 2021, where the construction is exactly the same except for the use of frames.
The authors should be cited for this paper.
Also, the name "frame" is confusing with the concept of frame in differential geometry and should be given a different name.

Theorem 1: It is proved that if a frame is an equivariant function, then a partial sum over the frame gives a transformation to an invariant/equivariant function, but the fact that the frame is defined depending only on the input space is not appropriate.
For example, if we have an invariant model F, the proposed method will sum over frames to convert it to an invariant function, which will increase the computational complexity. The transformation should be done without any transformation for the invariant model F.
This leads to the problem of overlapping invariants when combined with other models in the experimental section.

Also, since calculating the specific frame itself involves mathematical difficulties, I believe that the evaluation should be done on the model for which the frame has been calculated, i.e., for which the experiment has been conducted.

Point cloud models:
The $S_n \times E(d)$ or $SE(d)$-invariant model is constructed by computing a frame for $E(d)$ or $SE(d)$ and transforming the model of the Deep sets with that frame.
The simple question is why don't you construct a frame for $S_n \times E(d)$ or $SE(d)$?
If this method is good enough, the point permutation action should also be subject to the frame averaging model.
I would like you to explain the rationale reason for not doing so.

Graph models:
Two types of models have been proposed: MLP+FA and GNN+FA.
The problem with MLP+FA is that it uses the adjacency matrix itself as input, so when the number of nodes is large, the input space is also large, and the number of parameters is significantly larger than, for example, the model in Maron et al.
Is it possible to train MLP+FA with, say, 50 nodes?
Also, in a real task, the number of nodes in a graph can take many different values, is it possible to train MLP+FA for such a case?
In GNN+FA, the problem seems to be that invariance is calculated redundantly as described above, and the contribution of this method is not clear.

Reference

Zaheer et al.
Deep sets
Neural Information Processing Systems (NeurIPS) 2017.

Maron et al. Invariant and Equivariant Graph Networks
International Conference on Learning Representations (ICLR) 2019

Kicky et al.
A New Approach to Design Symmetry Invariant Neural Networks
International Joint Conference on Neural Networks (IJCNN) 2021




summary_of_the_review: The structure of the proposed model has already been seen in Kicki et al. 2021 except for the use of frames, and even if frames are used, MLP+FA for example does not seem to be able to handle changes in inputs such as changes in the number of nodes in the graph.
When combined with the existing strong methods, it gives good results, but this could be achieved by, for example, concatting two GNNs and then transforming them with FNN, so we decided that it is not worthy of evaluation.

After some discussion, the score was raised because the theoretical uncertainties and doubts were resolved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors introduce Frame Averaging (FA), a general framework for adapting known architectures to become invariant or equivariant with respect to a general group by using group averaging operator. The idea of FA is to replace the averaging operator over the entire group by the averaging over a smaller set of group elements but still achieve the full invariant/equivariant property.
main_review: *Strengths*
- The idea of replacing the averaging operator over the entire group by the FA is innovative. FA is simpler to compute and has less complexity in comparison with the averaging operator over the entire group.

- The authors prove that the FA-based models preserve the universality property of their backbone architectures. 

- The FA framework is then applied to design several invariant and equivariant architectures for point clouds and graphs.

*Weaknesses*

- My concern is mostly about the incompleteness of the framework. It may happen the case that for some $\mathbf{X}$, $\mathcal{F}(\mathbf{X})$ is a small set, but for some other $\mathbf{X}$, $\mathcal{F}(\mathbf{X})$ is large or even infinity. (For example the frame choice in Subsection 3.1 is in this case). In this case, a deeper analysis on how to separate these two cases and how to deal when $\mathcal{F}(\mathbf{X})$ is large or even infinity is necessary.

- It is also not clear how the FA is adapted in the DA-Local-PointNet. A detailed explanation here would be helpful.

- No comparison with the previous equivariant architectures are presented. Therefore, it is hard to estimate how novel and efficient the framework is in the world of current group equivariant architectures.

- Some technical parts are quite compact and not easy to read. Maybe the reason is that the paper includes rich contents and the authors tried to fix all of them in 9 pages.
summary_of_the_review: In addition, I have some comments on the technical parts of the paper:

- The definition of the frame $\mathcal{F}(\mathbf{X})$ for the case of point clouds and $G=E(d)$ in page 5 is not clear. Why "$\mathcal{F}(\mathbf{X})$ [...] is the collection of E(3) Euclidean transformations defined by [...]", while in this case, I think, $\mathcal{F}(\mathbf{X})$ must be a subset of $E(d)$?

- I am curious to know why "generically the frame would consist of $2^d$ elements [...], while for rare inputs $\mathbf{X}$ the frame can be an infinite set"? I think this remark is crucial for the proposed method as it affects the size of the FA framework.

- I think the proof of Proposition 1 (Appendix A.6) has some flaws:

     -- Line 3: What is $\Lambda$? It is not defined yet.

     -- Line 6-7: It seems to me that, you need to prove that $\mathbf{RO}$ consists of eigenvectors of 
$$[(\mathbf{R},\mathbf{t})\mathbf{X}]^T \cdot (I-\frac{1}{n} \mathbf{1} \mathbf{1}^T) \cdot [(\mathbf{R},\mathbf{t})\mathbf{X}]$$
which is 
$$(\mathbf{R}+\mathbf{t} \mathbf{1}^T) \mathbf{X}^T \cdot (I-\frac{1}{n} \mathbf{1} \mathbf{1}^T) \cdot \mathbf{X} (\mathbf{R}+\mathbf{t} \mathbf{1}^T)^T$$
rather than 
$$C = \mathbf{R} \mathbf{X}^T \cdot (I-\frac{1}{n} \mathbf{1} \mathbf{1}^T) \cdot \mathbf{X} \mathbf{R}^T$$
as you claimed. If this is exactly the case, I do not know how it can be true.
review_title: null

Meta-review: The submission proposes a method to make a pre-existing model equivariant to desired symmetries: frame averaging. The strategy relies on a significant reduction of the number of symmetries to average over (with respect to the Reynolds operator) and uniform subsampling. The paper also demonstrates the usefulness of this method theoretically (universal approximation result) and practically (competitive performance). The contributions are clear and the core idea is simple.
I recommend this paper for acceptance with spotlight.
Decision: Accept (Oral)