Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:
The authors introduce a framework for sufficient conditions for proving universality of a general class of neural networks that operate on point clouds which takes as input a set of coordinates of points and as output a feature for each point, such that the network is invariant to joint translation of the coordinates, equivariant to permutation of the points and equivariant to joint SO(3) transformations of the coordinates and output features of all points. Notably, this class contains Tensor Field Networks (TFN). The authors accomplish this by writing the network as a composition of an equivariant function from a class F_feat and followed by a linear pooling layer. When the F_feat class satisfies a “D-spanning” criterion and the pooling layer is universal, the network is universal. For a simple class of networks and for TFNs, the authors prove D-spanning. Linear universality of the pooling layer follows from simple representation theory.

Strengths:
-	It is useful to know whether prevalent classes of neural networks are universal
-	The authors use a general construction for proving universality of equivariant networks for the point cloud group, rather than being specific to certain architectures.
-	Reading the proofs along with the main text, the argumentation is clear and relatively easy to follow for me as reviewer, unfamiliar with similar universality proofs.

Weaknesses:
-	The paper would benefit from providing more intuition behind the proposed constructions, lemmas and theorems, in particular this holds for: theorem 1 based on the split between the linear universality and D-spanning; the construction of Segol & Lipman (2019) and how this relates to the Q functions and lemma 2
-	In addition to the previous point, the proofs, currently critical for understanding the paper, are given in the appendix, which is not ideal for the self-containedness of the main paper.
-	As the authors of the TFN paper note: in practice not all higher order irreps of the tensor product of the filter and the features are computed. This seems to indicate a big difference between the theoretical analysis - which includes all irreps and thus is computationally intensive even when modelling low order polynomials – and the practical application of TFNs. It would be interesting to know how expressive such practical low order TFNs are. Another difference between the described networks and practical TFN is that in the described networks, all relevant parameters are in the pooling layer, which sums a large number of terms (looking at the proof of lemma 2, exponential in D), while in practical TFNs, the parameters are in the filters.

Recommendation:
The authors proof the useful statement of universality of a prominent class of neural networks, which is why I recommend the acceptance of this paper.

Suggestion for improvement:
-	Make the big picture clearer by providing more intuition.
-	Comment on the differences between the class of networks described and TFNs used in practice.

Minor points/suggestions:
-	P3 Add definition of W^n_T as n direct sums of W_T
-	P3 “where W_feat is a lifted representation of SO(3)”, what does lifted representation here mean? Just any rep?
-	I get a bit confused by the wording in Def 1. Unless I am mistaken, it appears like the quantifiers are reversed. Should it mean “for every polynomial …, there exists f_1, … in F_feat and linear functionals Lambda_1, …, : W_feat -> R ”?
-	Around Eq 5, perhaps the authors could clarify the clarify the domain of the Q functions, which I suppose is Q^r : R^3n -> T_T, where T=||r||_1
-	Around Eq 7, are X_j and x_j the same?
-	In lemma 4, is A_k any linear map or an equivariant linear map? 
-	In Appendix B, perhaps a new subsection B.2 would make sense before theorem 1?
-	In the proof of thm 1, it says “p: R^{d \times n} \to W_T”, should that be W_T^n?
-	In the proof of lemma 2, it says “we see that that exists a linear functional”

## Post rebuttal
I thank the authors for their response and revised version, which has been improved notably with the inclusion of the proof ideas. My previous rating still applies.
review_title: Clear and useful proof of universality, but more intuition could be given.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper mainly explores the representation ability of invariability of a point cloud network from the theoretical perspective. The universal approximation property for equivariant architectures under shape-preserving transformations is discussed. First, the authors derived two sufficient conditions for equivariant architectures with the universal approximation property. Then, they examined two methods based on the Tensor Field Network to prove that such a property holds for both of them. At last, the authors propose alternative methods which also satisfy the universal approximation property. 

This paper is full of theoretical analysis, which is based on investigating the equivariant polynomials in the group theory. The proofs are similar to the previous works, except that more transformations, including rotation, translation and permutation, are considered together. However, the proof of the rotation equivariance has been discussed in previous works, and the theorems for translation and permutation are much easier than the rotation analysis. Moreover, the proposed method based on TFN is simply modified by the authors, resulting in alternative architectures which also satisfies the universal approximation property. However, this paper fails to provide any numerical experiments to demonstrate the performance and the influence of parameters \theta.

pros:
- provide sufficient conditions for equivariance of shape-preserving architectures to satisfy the universal approximation property
- prove two methods based of Tensor Field Networks that satisfy the universal approximation property
- raise two simple models based on the TFN
 

cons:
- This paper provides complete poofs to the TFN network theoretically, but lacks auxiliary experimental verification. Therefore, it is difficult to verify the correctness and feasibility of the proofs.
- The authors do not provide experimental results to demonstrate the performance of the proposed new methods.

review_title: This paper mainly explores the representation ability of invariability of a point cloud network from the  theoretical perspective. The universal approximation property for equivariant architectures under shape-preserving transformations is discussed.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work is a theoretical paper investigating the sufficient conditions for an equivariant structure to have the universal approximation property. They show that the recent works: Tensor Field networks and Fuchs et al., are universal under the proposed framework. A simple theoretical architecture is presented as another universal architecture.

Pros:
- Achieving rotation equivariance is important to point cloud network as it is the key to improve the expressiveness of point cloud features. Hence the study of the universality of network with such property is important to the community.
- Overall, the proposed proof looks plausible to me. 
- A minimal universal architecture is proposed that satisfies the D-spanning property. This provides the theoretical starting point to design a more advanced and complex equivariant point cloud network.

Cons:
- The paper is quite difficult to follow. I'm not an expert in group theory and had a difficult time understanding some of the theorems and proofs. It would be great if the writing can be broken down into more fundamental modules and provide more illustrations.
- In addition, the paper doesn't provide any evaluation of the proposed new universal architectures. Though this is a theoretical paper, it would be nice to show the proposed theory have some practical use. For instance, it would be great to provide a simple implementation of the minimal universal architecture and show it indeed achieves the rotation equivariant features on the point cloud data. That would make this work much stronger and more practical. 

Minors:
There are some typos in the inset figure on page 1: "Equivarint" -> "Equivariant".
review_title: Difficult to understand and lack of evaluation

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Summarize what the paper claims to contribute.**
The authors claim to: (1) introduce a general approach for proving universality of rotation-translation-permutation equivariant models for point clouds; (2) prove universality of two recent rotation equivariant point cloud networks and (3) introduce two rotation equivariant architectures for point cloud processing

**Strengths:**
The paper is well organized and both the language and notation are clear
The authors consider equivariant representation learning which is of growing interest to the community
The authors present theoretical insights for the success of recent architectures 
The insights themselves are leveraged to support the introduction of two new architectures

**Weaknesses:**
The novel architectures are described but not evaluated; it is therefore unclear what impact the simplification will have in practice
It might be nice to point out rotation equivariant architecture that is not universal

**Clearly state your recommendation.**
Accept. See Strengths.

**Arguments for your recommendation.**
Theoretical issues in deep learning is a relevant topic area for ICLR. This paper provides a theoretical framework for interpreting the success of deep learning frameworks for equivariant representation learning on point clouds. Moreover, the paper leverages the insights gathered to propose two novel approaches. The paper is written in a clear and accessible way. 

**Possible typos:**
(just before Thm. 1) When these two necessary → when these two sufficient 
(just after Lemma 3)  linear function → linear functions 

**Post rebuttal**
With consideration of the authors' responses to reviewer questions and revisions to the submitted work I have changed my rating to _clear accept_.


review_title: A pedagogical piece with practical relevance

Meta-review: The paper presents a theoretical analysis of the expressive power of equivariant models for point clouds with respect to translations, rotations and permutations. The authors provide sufficient conditions for universality, and prove that recently introduced architectures, e.g. Tensor Field Networks(TFN), do fulfil this property. 

The submission received positive reviews ; after rebuttal, all reviewers recommend acceptance and highlight the valuable paper modifications made by the authors to clarify the intuitions behind the proofs. 

The AC also considers that this paper is a solid contribution for ICLR, which will draw interest for both theoreticians and practitioners in the community. \
Therefore, the AC recommends acceptance. 
Decision: Accept (Poster)