Year: 2021

Abstract:
Learning functions on point clouds has applications in many fields, including computer vision, computer graphics, physics, and chemistry. Recently, there has been a growing interest in neural architectures that are invariant or equivariant to all three shape-preserving transformations of point clouds: translation, rotation, and permutation. In this paper, we present a first study of the approximation power of these architectures. We first derive two sufficient conditions for an equivariant architecture to have the universal approximation property, based on a novel characterization of the space of equivariant polynomials. We then use these conditions to show that two recently suggested models (Thomas et al., 2018; Fuchs et al., 2020) are universal, and for devising two other novel universal architectures.

heading: 1 INTRODUCTION
text: Designing neural networks that respect data symmetry is a powerful approach for obtaining efficient deep models. Prominent examples being convolutional networks which respect the translational invariance of images, graph neural networks which respect the permutation invariance of graphs (Gilmer et al., 2017; Maron et al., 2019b), networks such as (Zaheer et al., 2017; Qi et al., 2017a) which respect the permutation invariance of sets, and networks which respect 3D rotational symmetries (Cohen et al., 2018; Weiler et al., 2018; Esteves et al., 2018; Worrall & Brostow, 2018; Kondor et al., 2018a). While the expressive power of equivariant models is reduced by design to include only equivariant functions, a desirable property of equivariant networks is universality: the ability to approximate any continuous equivariant function. This is not always the case: while convolutional networks and networks for sets are universal (Yarotsky, 2018; Segol & Lipman, 2019), popular graph neural networks are not (Xu et al., 2019; Morris et al., 2018).
In this paper, we consider the universality of networks that respect the symmetries of 3D point clouds: translations, rotations, and permutations. Designing such networks is a popular paradigm in recent years (Thomas et al., 2018; Fuchs et al., 2020; Poulenard et al., 2019; Zhao et al., 2019). While there have been many works on the universality of permutation invariant networks (Zaheer et al., 2017; Maron et al., 2019c; Keriven & Peyré, 2019), and a recent work discussing the universality of rotation equivariant networks (Bogatskiy et al., 2020), this is a first paper which discusses the universality of networks which combine rotations, permutations and translations.
We start the paper with a general, architecture-agnostic, discussion, and derive two sufficient conditions for universality. These conditions are a result of a novel characterization of equivariant polynomials for the symmetry group of interest. We use these conditions in order to prove universality of the prominent Tensor Field Networks (TFN) architecture (Thomas et al., 2018; Fuchs et al., 2020). The following is a weakened and simplified statement of Theorem 2 stated later on in the paper: Theorem (Simplification of Theorem 2). Any continuous equivariant function on point clouds can be approximated uniformly on compact sets by a composition of TFN layers.
We use our general discussion to prove the universality of two additional equivariant models: the first is a simple modification of the TFN architecture which allows for universality using only low dimensional filters. The second is a minimal architecture which is based on tensor product representations, rather than the more commonly used irreducible representations of SO(3). We discuss the advantages and disadvantages of both approaches.
To summarize, the contributions of this paper are: (1) A general approach for proving the universality of rotation equivariant models for point clouds; (2) A proof that two recent equivariant models (Thomas et al., 2018; Fuchs et al., 2020) are universal; (3) Two additional simple and novel universal architectures.

heading: 2 PREVIOUS WORK
text: Deep learning on point clouds. (Qi et al., 2017a; Zaheer et al., 2017) were the first to apply neural networks directly to the raw point cloud data, by using pointwise functions and pooling operations. Many subsequent works used local neighborhood information (Qi et al., 2017b; Wang et al., 2019b; Atzmon et al., 2018). We refer the reader to a recent survey for more details (Guo et al., 2020). In contrast with the aforementioned works which focused solely on permutation invariance, more related to this paper are works that additionally incorporated invariance to rigid motions. (Thomas et al., 2018) proposed Tensor Field Networks (TFN) and showed their efficacy on physics and chemistry tasks.(Kondor et al., 2018b) also suggested an equivariant model for continuous rotations. (Li et al., 2019) suggested models that are equivariant to discrete subgroups of SO(3). (Poulenard et al., 2019) suggested an invariant model based on spherical harmonics. (Fuchs et al., 2020) followed TFN and added an attention mechanism. Recently, (Zhao et al., 2019) proposed a quaternion equivariant point capsule network that also achieves rotation and translation invariance.
Universal approximation for invariant networks. Understanding the approximation power of invariant models is a popular research goal. Most of the current results assume that the symmetry group is a permutation group. (Zaheer et al., 2017; Qi et al., 2017a; Segol & Lipman, 2019; Maron et al., 2020; Serviansky et al., 2020) proved universality for several Sn-invariant and equivariant models. (Maron et al., 2019b;a; Keriven & Peyré, 2019; Maehara & NT, 2019) studied the approximation power of high-order graph neural networks. (Maron et al., 2019c; Ravanbakhsh, 2020) targeted universality of networks that use high-order representations for permutation groups(Yarotsky, 2018) provided several theoretical constructions of universal equivariant neural network models based on polynomial invariants, including an SE(2) equivariant model. In a recent work (Bogatskiy et al., 2020) presented a universal approximation theorem for networks that are equivariant to several Lie groups including SO(3). The main difference from our paper is that we prove a universality theorem for a more complex group that besides rotations also includes translations and permutations.

heading: 3 A FRAMEWORK FOR PROVING UNIVERSALITY
text: In this section, we describe a framework for proving the universality of equivariant networks. We begin with some mathematical preliminaries:

heading: 3.1 MATHEMATICAL SETUP
text: An action of a group G on a real vector space W is a collection of maps ρ(g) : W → W defined for any g ∈ G, such that ρ(g1) ◦ ρ(g2) = ρ(g1g2) for all g1, g2 ∈ G, and the identity element of G is mapped to the identity mapping on W . We say ρ is a representation of G if ρ(g) is a linear map for every g ∈ G. As is customary, when it does not cause confusion we often say that W itself is a representation of G .
In this paper, we are interested in functions on point clouds. Point clouds are sets of vectors in R3 arranged as matrices:
X = (x1, . . . , xn) ∈ R3×n.
Many machine learning tasks on point clouds, such as classification, aim to learn a function which is invariant to rigid motions and relabeling of the points. Put differently, such functions are required
to be invariant to the action of G = R3 o SO(3)× Sn on R3×n via ρG(t, R, P )(X) = R(X − t1Tn )PT , (1) where t ∈ R3 defines a translation, R is a rotation and P is a permutation matrix. Equivariant functions are generalizations of invariant functions: If G acts on W1 via some action ρ1(g), and on W2 via some other group action ρ2(g), we say that a function f : W1 → W2 is equivariant if f(ρ1(g)w) = ρ2(g)f(w),∀w ∈W1 and g ∈ G. Invariant functions correspond to the special case where ρ2(g) is the identity mapping for all g ∈ G. In some machine learning tasks on point clouds, the functions learned are not invariant but rather equivariant. For example, segmentation tasks assign a discrete label to each point. They are invariant to translations and rotations but equivariant to permutations – in the sense that permuting the input causes a corresponding permutation of the output. Another example is predicting a normal for each point of a point cloud. This task is invariant to translations but equivariant to both rotations and permutations.
In this paper, we are interested in learning equivariant functions from point clouds into WnT , where WT is some representation of SO(3). The equivariance of these functions is with respect to the action ρG on point clouds defined in equation 1, and the action of G on WnT defined by applying the rotation action from the left and permutation action from the right as in 1, but ‘ignoring’ the translation component. Thus, G-equivariant functions will be translation invariant. This formulation of equivariance includes the normals prediction example by taking WT = R3, as well as the segmentation case by setting WT = R with the trivial identity representation. We focus on the harder case of functions into WnT which are equivariant to permutations, since it easily implies the easier case of permutation invariant functions to WT .
Notation. We use the notation N+ = N ∪ {0} and N∗+ = ⋃ r∈N Nr+. We set [D] = {1, . . . , D} and [D]0 = {0, . . . , D}. Proofs. Proofs appear in the appendices, arranged according to sections.

heading: 3.2 CONDITIONS FOR UNIVERSALITY
text: The semi-lifted approach In general, highly expressive equivariant neural networks can be achieved by using a ‘lifted approach’, where intermediate features in the network belong to high dimensional representations of the group. In the context of point clouds where typically n 3, many papers, e.g., (Thomas et al., 2018; Kondor, 2018; Bogatskiy et al., 2020) use a ‘semi-lifted’ approach, where hidden layers hold only higher dimensional representations of SO(3), but not high order permutation representations. In this subsection, we propose a strategy for achieving universality with the semi-lifted approach.
We begin by an axiomatic formulation of the semi-lifted approach (see illustration in inset): we assume that our neural networks are composed of two main components: the first component is a family Ffeat of parametric continuous G-equivariant functions ffeat which map the original point cloud R3×n to a semi-lifted point cloud Wnfeat = ⊕n i=1Wfeat, where Wfeat is a lifted (i.e., high-order) representation of SO(3). The second component is a family of parametric linear SO(3)-equivariant functions Fpool, which map from the high order representation Wfeat down to the target representation WT . Each such SO(3)–equivariant function Λ : Wfeat →WT can be extended to a SO(3)×Sn equivariant function Λ̂ : Wnfeat → WnT by applying Λ elementwise. For every positive integer C, these two families of functions induce a family of functions FC obtained by summing C different compositions of these functions:
FC(Ffeat,Fpool) = {f |f(X) = C∑ c=1 Λ̂c(gc(X)), (Λc, gc) ∈ Fpool ×Ffeat}. (2)
Conditions for universality We now describe two conditions that guarantee universality using the semi-lifted approach. The first step is showing, as in (Yarotsky, 2018), that continuousG-equivariant functions CG(R3×n,WnT ) can be approximated by G-equivariant polynomials PG(R3×n,WnT ). Lemma 1. Any continuous G-equivariant function in CG(R3×n,WnT ) can be approximated uniformly on compact sets by G-equivariant polynomials in PG(R3×n,WnT ).
Universality is now reduced to the approximation of G-equivariant polynomials. Next, we provide two conditions which guarantee that G-equivariant polynomials of degree D can be expressed by function spaces FC(Ffeat,Fpool) as defined in equation 2. The idea behind these conditions is that explicit characterizations of polynomials equivariant to the joint action of translations, rotations and permutations is challenging. However, it is possible to explicitly characterize polynomials equivariant to translations and permutations (but not rotations). The key observation is then that this characterization can be rewritten as a sum of functions to Wnfeat, a high dimensional representations of SO(3) which is equivariant to translations, permutations and rotations, composed with a linear map which is permutation equivariant (but does not respect rotations). Accordingly, our first condition is that Ffeat contains a spanning set of such functions to Wnfeat. We call this condition D-spanning:
Definition 1 (D-spanning). For D ∈ N+, let Ffeat be a subset of CG(R3×n,Wnfeat). We say that Ffeat is D-spanning, if there exist f1, . . . , fK ∈ Ffeat, such that every polynomial p : R3×n → Rn of degree D which is invariant to translations and equivariant to permutations, can be written as
p(X) = K∑ k=1 Λ̂k(fk(X)), (3)
where Λk : Wfeat → R are all linear functionals, and Λ̂k : Wnfeat → Rn are the functions defined by elementwise applications of Λk.
In Lemma 4 we explicitly construct a D-spanning family of functions. This provides us with a concrete condition which implies D-spanning for other function families as well.
The second condition is that Fpool contains all SO(3) linear equivariant layers. We call this condition Linear universality. Intuitively, taking linear rotation equivariant Λk in equation 3 ensures that the resulting function p will be rotation equivariant and thus fully G-equivariant, and linear universality guarantees the ability to express all such G invariant functions.
Definition 2 (Linear universality). We say that a collection Fpool of equivariant linear functionals between two representations Wfeat and WT of SO(3) is linearly universal, if it contains all linear SO(3)-equivariant mappings between the two representations.
When these two conditions apply, a rather simple symmetrization arguments leads to the following theorem:
Theorem 1. If Ffeat is D-spanning and Fpool is linearly universal, then there exists some C(D) ∈ N such that for all C ≥ C(D) the function space FC(Ffeat,Fpool) contains all G-equivariant polynomials of degree ≤ D.
Proof idea. By the D-spanning assumption, there exist f1, . . . , fK ∈ Ffeat such that any vector valued polynomial invariant to translations and equivariant to permutations is of the form
p(X) = K∑ k=1 Λ̂k(fk(X)), (4)
While by definition this holds for functions p whose image is Rn, this is easily extended to functions to WnT as well.
It remains to show that when p is also SO(3)-equivariant, we can choose Λk to be SO(3) equivariant. This is accomplished by averaging over SO(3).
As a result of Theorem 1 and Lemma 1 we obtain our universality result (see inset for illustration) Corollary 1. For all C,D ∈ N+, let FC,D denote function spaces generated by a pair of functions spaces which are D-spanning and linearly universal as in equation 2. Then any continuous G-equivariant function in CG(R3×n,WnT ) can be approximated uniformly on compact sets by equivariant functions in
F = ⋃ D∈N FC(D),D.

heading: 3.3 UNIVERSALITY CONDITIONS IN ACTION
text: In the remainder of the paper, we prove the universality of severalG-equivariant architectures, based on the framework we discussed in the previous subsection. We discuss two different strategies for achieving universality, which differ mainly in the type of lifted representations of SO(3) they use: (i) The first strategy uses (direct sums of) tensor-product representations; (ii) The second uses (direct sums of) irreducible representations. The main advantage of the first strategy from the perspective of our methodology is that achieving the D-spanning property is more straightforward. The advantage of irreducible representations is that they almost automatically guarantees the linear universality property.
In Section 4 we discuss universality through tensor product representations, and give an example of a minimal tensor representation network architecture that would satisfy universality. In section 5 we discuss universality through irreducible representations, which is currently the more common strategy. We show that the TFN architecture (Thomas et al., 2018; Fuchs et al., 2020) which follows this strategy is universal, and describe a simple tweak that achieves universality using only low order filters, though the representations throughout the network are high dimensional.

heading: 4 UNIVERSALITY WITH TENSOR REPRESENTATIONS
text: In this section, we prove universality for models that are based on tensor product representations, as defined below. The main advantage of this approach is that D-spanning is achieved rather easily. The main drawbacks are that its data representation is somewhat redundant and that characterizing the linear equivariant layers is more laborious.
Tensor representations We begin by defining tensor representations. For k ∈ N+ denote Tk = R3 k
. SO(3) acts on Tk by the tensor product representation, i.e., by applying the matrix Kronecker product k times: ρk(R) := R⊗k. The inset illustrates the vector spaces and action for k = 1, 2, 3. With this action, for any i1, . . . , ik ∈ [n], the map from R3×n to Tk defined by
(x1, . . . , xn) 7→ xi1 ⊗ xi2 . . .⊗ xik (5) is SO(3) equivariant.
A D-spanning family We now show that tensor representations can be used to define a finite set of D-spanning functions. The lifted representation Wfeat will be given by
W Tfeat = D⊕ T=0 TT .
TheD-spanning functions are indexed by vectors ~r = (r1, . . . , rK), where each rk is a non-negative integer. Denoting T = ‖r‖1, the functions Q(~r) : R3×n → T nT , Q(~r) = (Q (~r) j ) n j=1 are defined for fixed j ∈ [n] by
Q (~r) j (X) = n∑ i2,...,iK=1 x⊗r1j ⊗ x ⊗r2 i2 ⊗ x⊗r3i3 ⊗ . . .⊗ x ⊗rK iK . (6)
The functionsQ(~r)j are SO(3) equivariant as they are a sum of equivariant functions from equation 5. Thus Q(~r) is SO(3)×Sn equivariant. The motivation behind the definition of these functions is that known characterizations of permutation equivariant polynomials Segol & Lipman (2019) tell us that the entries of these tensor valued functions span all permutation equivariant polynomials (see the proof of Lemma 2 for more details).
To account for translation invariance, we compose the functions Q(~r) with the centralization operation and define the set of functions
QD = {ι ◦Q(~r)(X − 1
n X1n1
T n )| ‖~r‖1 ≤ D}, (7)
where ι is the natural embedding that takes each TT into W Tfeat = ⊕D
T=0 TT . In the following lemma, we prove that this set is D-spanning.
Lemma 2. For every D ∈ N+, the set QD is D-spanning.
Proof idea. It is known (Segol & Lipman, 2019) (Theorem 2) that polynomials p : R3×n → Rn which are Sn-equivariant, are spanned by polynomials of the form p~α = (p j ~α) n j=1, defined as
pj~α(X) = n∑ i2,...,iK=1 xα1j x α2 i2 . . . xαkik (8)
where ~α = (α1, . . . , αK) and each αk ∈ N3+ is a multi-index. We first show that these polynomials can be extracted from Q(~r) and then use them to represent p.
A minimal universal architecture Once we have shown that QD is D-spanning, we can design D-spanning architectures, by devising architectures that are able to span all elements of QD. As we will now show, the compositional nature of neural networks allows us to do this in a very clean manner.
We define a parametric function f(X,V |θ1, θ2) which maps R3×n⊕T nk to R3×n⊕T nk+1 as follows: For all j ∈ [n], we have fj(X,V ) = (xj , Ṽj(X,V )), where
Ṽj(X,V |θ1, θ2) = θ1 (xj ⊗ Vj) + θ2 ∑ i (xi ⊗ Vi) (9)
We denote the set of functions (X,V ) 7→ f(X,V |θ1, θ2) obtained by choosing the parameters θ1, θ2 ∈ R, by Fmin . While in the hidden layers of our network the data is represented using both coordinates (X,V ), the input to the network only contains an X coordinate and the output only contains a V coordinate. To this end, we define the functions
ext(X) = (X, 1n) and πV (X,V ) = V. (10)
We can achieve D-spanning by composition of functions in Fmin with these functions and centralizing:
Lemma 3. The function set QD is contained in
Ffeat = {ι ◦ πV ◦ f1 ◦ f2 ◦ . . . ◦ fT ◦ ext(X − 1
n X1n1
T n )| f j ∈ Fmin, T ≤ D}. (11)
Thus Ffeat is D-spanning.
Proof idea. The proof is technical and follows by induction on D.
To complete the construction of a universal network, we now need to characterize all linear equivariant functions from W Tfeat to the target representation WT . In Appendix G we show how this can be done for the trivial representation WT = R. This characterization gives us a set of linear functions Fpool, which combined withFfeat defined in equation 11 (corresponds to SO(3) invariant functions)
gives us a universal architecture as in Theorem 1. However, the disadvantage of this approach is that implementation of the linear functions in Fpool is somewhat cumbersome. In the next section we discuss irreducible representations, which give us a systematic way to address linear equivariant mappings into any WT . Proving D-spanning for these networks is accomplished via the D-spanning property of tensor representations, through the following lemma Lemma 4. If all functions in QD can be written as
ι ◦Q(~r)(X − 1 n X1n1 T n ) = K∑ k=1 Âkfk(X),
where fk ∈ Ffeat, Ak : Wfeat → W Tfeat and Âk : Wnfeat → (W Tfeat)n is defined by elementwise application of Ak, then Ffeat is D-spanning.
We note that as before, Ak are not necessarily SO(3)- equivariant.
Proof idea. The lemma follows directly from the assumptions.

heading: 5 UNIVERSALITY WITH IRREDUCIBLE REPRESENTATIONS
text: In this section, we discuss how to achieve universality when using irreducible representations of SO(3). We will begin by defining irreducible representations, and explaining how linear universality is easily achieved by them, while the D-spanning properties of tensor representations can be preserved. This discussion can be seen as an interpretation of the choices made in the construction of TFN and similar networks in the literature. We then show that these architectures are indeed universal.
5.1 IRREDUCIBLE REPRESENTATIONS OF SO(3)
In general, any finite-dimensional representation W of a compact group H can be decomposed into irreducible representations: a subspaceW0 ⊂W isH-invariant if hw ∈W0 for all h ∈ H,w ∈W0. A representationW is irreducible if it has no non-trivial invariant subspaces. In the case of SO(3), all irreducible real representations are defined by matrices D(`)(R), called the real Wigner D-matrices, acting on W` := R2`+1 by matrix multiplication. In particular, the representation for ` = 0, 1 are D(0)(R) = 1 and D(1)(R) = R.
Linear maps between irreducible representations As mentioned above, one of the main advantages of using irreducible representations is that there is a very simple characterization of all linear equivariant maps between two direct sums of irreducible representations. We use the notation Wl for direct sums of irreducible representations, where l = (`1, . . . , `K) ∈ NK+ andWl = ⊕K k=1W`k .
Lemma 5. Let l(1) = (`(1)1 , . . . , ` (1) K1 ) and l(2) = (`(2)1 , . . . , ` (2) K2
). A function Λ = (Λ1, . . . ,ΛK2) is a linear equivariant mapping between Wl(1) and Wl(2) , if and only if there exists a K1 ×K2 matrix M with Mij = 0 whenever ` (1) i 6= ` (2) j , such that
Λj(V ) = K1∑ i=1 MijVi (12)
where V = (Vi)K1i=1 and Vi ∈W`(1)i for all i = 1, . . . ,K1.
Proof idea. This lemma is a simple generalization of Schur’s lemma, a classical tool in representation theory, which asserts that a non-zero linear map between irreducible representations is a scaled multiply of the identity mapping. Lemma 5 was stated in the complex setting in Kondor (2018). While Schur’s lemma, and thus Lemma 5, does not always hold for representations over the reals, we observe here that it holds for real irreducible representations of SO(3) since their dimension is always odd.
Clebsch-Gordan decomposition of tensor products As any finite-dimensional representation of SO(3) can be decomposed into a direct sum of irreducible representations, this is true for tensor representations as well. In particular, the Clebsch-Gordan coefficients provide an explicit formula for decomposing the tensor product of two irreducible representationsW`1 andW`2 into a direct sum of irreducible representations. This decomposition can be easily extended to decompose the tensor product Wl1 ⊗Wl2 into a direct sum of irreducible representations, where l1, l2 are now vectors. In matrix notation, this means there is a unitary linear equivariant U(l1, l2) mapping of Wl1 ⊗Wl2 onto Wl, where the explicit values of l = l(l1, l2) and the matrix U(l1, l2) can be inferred directly from the case where `1 and `2 are scalars.
By repeatedly taking tensor products and applying Clebsch-Gordan decompositions to the result, TFN and similar architectures can achieve the D-spanning property in a manner analogous to tensor representations, and also enjoy linear universality since they maintain irreducible representations throughout the network.

heading: 5.2 TENSOR FIELD NETWORKS
text: We now describe the basic layers of the TFN architecture (Thomas et al., 2018), which are based on irreducible representations, and suggest an architecture based on these layers which can approximate G-equivariant maps into any representation WnlT , lT ∈ N ∗ +. There are some superficial differences between our description of TFN and the description in the original paper, for more details see Appendix F.
We note that the universality of TFN also implies the universality of Fuchs et al. (2020), which is a generalization of TFN that enables adding an attention mechanism. Assuming the attention mechanism is not restricted to local neighborhoods, this method is at least as expressive as TFN.
TFNs are composed of three types of layers: (i) Convolution (ii) Self-interaction and (iii) Nonlinearities. In our architecture, we only use the first two layers types, which we will now describe:1.
Convolution. Convolutional layers involve taking tensor products of a filter and a feature vector to create a new feature vector, and then decomposing into irreducible representations. Unlike in standard CNN, a filter here depends on the input, and is a function F : R3 → WlD , where lD = [0, 1, . . . , D]T . The `-th component of the filter F (x) = [ F (0)(x), . . . , F (D)(x) ] will be given by
F (`)m (x) = R (`)(‖x‖)Y `m(x̂), m = −`, . . . , ` (13)
where x̂ = x/‖x‖ if x 6= 0 and x̂ = 0 otherwise, Y `m are spherical harmonics, and R(`) any polynomial of degree≤ D. In Appendix F we show that these polynomial functions can be replaced by fully connected networks, since the latter can approximate all polynomials uniformly.
The convolution of an input feature V ∈ Wnli and a filter F as defined above, will give an output feature Ṽ = (Ṽa)na=1 ∈Wnl0 , where lo = l(lf , li), which is given by
Ṽa(X,V ) = U(lf , li) ( θ0Va +
n∑ b=1 F (xa − xb)⊗ Vb
) . (14)
More formally we will think of convolutional layer as functions of the form f(X,V ) = (X, Ṽ (X,V )). These functions are defined by a choice of D, a choice of a scalar polynomial R(`), ` = 0, . . . , D, and a choice of the parameter θ0 ∈ R in equation 14. We denote the set of all such functions f by FD.
Self Interaction layers. Self interaction layers are linear functions from Λ̂ : Wnl →WnlT , which are obtained from elementwise application of equivariant linear functions Λ : Wl →WlT . These linear functions can be specified by a choice of matrix M with the sparsity pattern described in Lemma 5.
Activation functions. TFN, as well as other papers, proposed several activation functions. We find that these layers are not necessary for universality and thus we do not define them here.
Network architecture. For our universality proof, we suggest a simple architecture which depends on two positive integer parameters (C,D): For given D, we will define Ffeat(D) as the set of
1Since convolution layers in TFN are not linear, the non-linearities are formally redundant
function obtained by 2D recursive convolutions
Ffeat(D) = {πV ◦ f2D ◦ . . . f2 ◦ f1 ◦ ext(X)| f j ∈ FD}, where ext and πV are defined as in equation 10. The output of a function in Ffeat(D) is in Wnl(D), for some l(D) which depends on D. We then define Fpool(D) to be the self-interaction layers which map Wnl(D) to W n lT
. This choice of Ffeat(D) and Fpool(D), together with a choice of the number of channels C, defines the final network architecture FTFNC,D = FC(Ffeat(D),Fpool(D)) as in equation 2. In the appendix we prove the universality of TFN: Theorem 2. For all n ∈ N, lT ∈ N∗+,
1. ForD ∈ N+, everyG-equivariant polynomial p : R3×n →WnT of degreeD is inFTFNC(D),D.
2. Every continuous G-equivariant function can be approximated uniformly on compact sets by functions in ∪D∈N+FTFNC(D),D
As discussed previously, the linear universality of Fpool is guaranteed. Thus proving Theorem 2 amounts to showing that Ffeat(D) is D-spanning. This is done using the sufficient condition for D-spanning defined in Lemma 4.
Proof idea. The proof is rather technical and involved. A useful observation (see Dai & Xu (2013)) used in the proof is that the filters of orders ` = 0, 1, . . . , D, defined in equation 13, span all polynomial functions of degree D on R3. This observation is used to show that all functions in QD can be expressed by Ffeat(D) and so Ffeat is D-spanning, as stated in Lemma 2.
Alternative architecture The complexity of the TFN network used to construct G-equivariant polynomials of degree D, can be reduced using a simple modifications of the convolutional layer in equation 14: We add two parameters θ1, θ2 ∈ R to the convolutional layer, which is now defined as:
Ṽa(X,V ) = U(lf , li) ( θ1
n∑ b=1 F (xa − xb)⊗ Vb + θ2 n∑ b=1 F (xa − xb)⊗ Va
) . (15)
With this simple change, we can show that Ffeat(D) is D-spanning even if we only take filters of order 0 and 1 throughout the network. This is shown in Appendix E.

heading: 6 CONCLUSION
text: In this paper, we have presented a new framework for proving the universality ofG-equivariant point cloud networks. We used this framework for proving the universality of the TFN model Thomas et al. (2018); Fuchs et al. (2020), and for devising two additional novel simple universal architectures. In the future we hope to extend these simple constructions to operational G-equivariant networks with universality guarantees and competitive practical performance.
Our universal architectures do not require activation functions, and use a single self-interaction layer. In Appendix H we present an experiment indicating that the performance of TFN is not significantly altered by these simplifications. Our architectures also require high order representations, and our experiments show that using increasingly high order representations does indeed improve performance. To date, practical TFN implementation included a relatively small amount of layers, and did not use very high order representations. We believe our theoretical results will inspire interest in stable implementation of larger architectures. On the other hand, an interesting open problem is understanding whether universality can be achieved using only low-dimensional representations.
Finally, we believe that the framework we developed here will be useful for proving the universality of other G-equivariant models for point cloud networks, and other related equivariant models. We note that large parts of our discussion can be easily generalized to symmetry groups of the form G = Rd oH × Sn acting on Rd×n, where H can be any compact topological group.
Acknowledgments The authors would like to thank Fabian B. Fuchs for making code available and Taco Cohen for helpful discussion. N.D. is supported by THEORINET Simons award 814643.

heading: A NOTATION
text: We introduce some notation for the proofs in the appendices. We use the shortened notation X̄ = X − 1nX1n1 T n and denote the columns of X̄ by (x̄1, . . . , x̄n). We denote
ΣT = {~r ∈ N∗+| ‖~r‖1 = T}

heading: B PROOFS FOR SECTION 3
text: B.1 G-EQUIVARIANT POLYNOMIALS ARE DENSE
A first step in proving denseness of G-equivariance polynomials, and in the proof used in the next subsection is the following simple lemma, which shows that translation invariance can be dealt with simply by centralizing the point cloud.
In the following, ρWT is some representation of SO(3) on a finite dimensional real vector spaceWT . this induces an action ρWT×Sn of SO(3)× Sn on WnT by
ρWT×Sn(R,P )(Y ) = ρWT (R)Y P T
This is also the action of G which we consider, ρG = ρWT×Sn , where we have invariance with respect to the translation coordinate. The action of G on R3×n is defined in equation 1. Lemma B.1. A function f : R3×n → WnT is G-equivariant, if and only if there exists a function h which is equivariant with respect to the action of SO(3)× Sn on R3×n, and
f(X) = h(X − 1 n X1n1 T n ) (16)
Proof. Recall thatG-equivariance means SO(3)×Sn equivariance and translation invariance. Thus if f is G-equivariant then equation 16 holds with h = f .
On the other hand, if f satisfies equation 16 then we claim it is G-equivariant. Indeed, for all (t, R, P ) ∈ Rd o SO(3)× Sn , since PT 1n1Tn = 1n1Tn = 1n1TnPT ,
f (ρG(t, R, P )(X)) =f(R(X + t1n)P T ) = h(R(X + t1n)P T − 1 n R(X + t1)PT 1n1 T n )
= h(R(X − 1 n X1n1 T n )P T ) = h
( ρR3×Sn(R,P )(X − 1
n X1n1
T n ) ) = ρWT×Sn(R,P )h ( X − 1
n X1n1
T n ) = ρG(t, R, P )f(X).
We now prove denseness of G-equivariant polynomials in the space of G-invariant continuous functions (Lemma 1). Lemma 1. Any continuous G-equivariant function in CG(R3×n,WnT ) can be approximated uniformly on compact sets by G-equivariant polynomials in PG(R3×n,WnT ).
Proof of Lemma 1. Let K ⊆ R3×n be a compact set. We need to show that continuous Gequivariant functions can be approximated uniformly in K by G-equivariant polynomials. Let K0 denote the compact set which is the image of K under the centralizing map X 7→ X − 1nX1n1 T n . By Lemma B.1, it is sufficient to show that every SO(3)×Sn equivariant continuous function f can be approximated uniformly on K0 by a sequence of SO(3) × Sn equivariant polynomials pk. The argument is now concluded by the following general lemma:
Lemma B.2. Let G be a compact group, Let ρ1 and ρ2 be continuous2representations of G on the Euclidean spaces W1 and W2. Let K ⊆ W1 be a compact set. Then every equivariant function f : W1 → W2 can be approximated uniformly on K by a sequence of equivariant polynomials pk : W1 7→W2.
Let µ be the Haar probability measure associated with the compact group G. Let K1 denote the compact set obtained as an image of the compact set G×K under the continuous mapping
(g,X) 7→ ρ1(g)X. Using the Stone-Weierstrass theorem, let pk be a sequence of (not necessarily equivariant) polynomials which approximate f uniformly on K1. Every degree D polynomial p : W1 → W2 induces a G-equivariant function
〈p〉(X) = ∫ G ρ2(g −1)p(ρ1(g)X)dµ(g).
This function 〈p〉 is a degree D polynomial as well: This is because 〈p〉 can be approximated uniformly on K1 by “Riemann Sums” of the form ∑N j=1 wjρ2(g −1 j )p(ρ1(gj)X) which are degree D polynomials, and because degree D polynomials are closed in C(K1).
Now for all X ∈ K1, continuity of the function g 7→ ρ2(g−1) implies that the operator norm of ρ2(g −1) is bounded uniformly by some constant N > 0, and so
|〈pk〉(X)− f(X)| = ∣∣∣∣∫ G ρ2(g −1)pk(ρ1(g)X)− ρ2(g−1)f(ρ1(g)X)dµ(g) ∣∣∣∣ =
∣∣∣∣∫ G ρ2(g −1) [pk(ρ1(g)X)− f(ρ1(g)X)] dµ(g) ∣∣∣∣ ≤ N‖f − pk‖C(K1) → 0 B.2 PROOF OF THEOREM 1
Theorem 1. If Ffeat is D-spanning and Fpool is linearly universal, then there exists some C(D) ∈ N such that for all C ≥ C(D) the function space FC(Ffeat,Fpool) contains all G-equivariant polynomials of degree ≤ D.
Proof. By the D-spanning assumption, there exist f1, . . . , fK ∈ Ffeat such that any vector valued polynomial p : R3×n → Rn invariant to translations and equivariant to permutations is of the form
p(X) = K∑ k=1 Λ̂k(fk(X)), (17)
where Λk are linear functions to R. If p is a matrix valued polynomial mapping R3×n to WnT = Rt×n, which is invariant to translations and equivariant to permutations, then it is of the form p = (pij)i∈[t],j∈[n], and each pi = (pij)j∈[n] is itself invariant to translations and permutation equivariant. It follows that matrix valued p can also be written in the form equation 17, the only difference being that the image of the linear functions Λk is now Rt.
Now let p : R3×n → WnT be a G-equivariant polynomial of degree ≤ D. It remains to show that we can choose Λk to be SO(3) equivariant. We do this by a symmetrization argument: denote the Haar probability measure on SO(3) by ν, and the action of SO(3) on Wfeat and WT by ρ1 and ρ2 respectively Denote p = (pj)nj=1 and fk = (f j k) n j=1. For every j = 1, . . . , n, we use the SO(3) equivariance of pj and f j k to obtain
pj(X) = ∫ SO(3) ρ2(R −1) ◦ pj(RX)dν(R) = K∑ k=1 ∫ SO(3) ρ2(R −1) ◦ Λk ◦ fkj (RX)dν(R)
= K∑ k=1 ∫ SO(3) ρ2(R −1) ◦ Λk ( ρ1(R) ◦ f jk(X) ) dν(R) = K∑ k=1 Λ̃k ◦ f jk(X),
2By this we mean that the maps (g,X) 7→ ρj(g)X, j = 1, 2 are jointly continuous
where Λ̃k stands for the equivariant linear functional from Wfeat to WT , defined for w ∈Wfeat by
Λ̃k(w) = ∫ SO(3) ρ2(R −1) ◦ Λk (ρ1(R)w) dν(R).
Thus we have shown that p is in FC(Ffeat,Fpool) for C = K, as required.

heading: C PROOFS FOR SECTION 4
text: We prove Lemma 2 Lemma 2. For every D ∈ N+, the set QD is D-spanning.
Proof. It is known (Segol & Lipman, 2019) (Theorem 2) that polynomials p : R3×n → Rn which are Sn-equivariant, are spanned by polynomials of the form p~α = (p j ~α) n j=1, defined as
pj~α(X) = n∑ i2,...,iK=1 xα1j x α2 i2 . . . xαkik (18)
where ~α = (α1, . . . , αK) and each αk ∈ N3+ is a multi-index. It follows that Sn-equivariant polynomials of degree ≤ D are spanned by polynomials of the form pj~α where ∑K k=1 |αk| ≤ D. Denoting rk = |αk|, k = 1, . . .K, the sum of all rk by T , and ~r = (rk)Kk=1, we see that there exists a linear functional Λ~α,~r : TT → R such that
pj~α(X) = Λ~α,~r ◦Q ~r j(X) where we recall that Q~r = ( Q
(~r) j (X) )n j=1 is defined in equation 6 as
Q (~r) j (X) = n∑ i2,...,iK=1 x⊗r1j ⊗ x ⊗r2 i2 ⊗ x⊗r3i3 ⊗ . . .⊗ x ⊗rK iK .
Thus polynomials p = (pj)nj=1 which are of degree ≤ D, and are Sn equivariant, can be written as pj(X) = ∑ T≤D ∑ ~r∈ΣT ∑ ~α||αk|=rk Λ~α,~r ( Q (~r) j (X) ) = ∑ T≤D ∑ ~r∈ΣT Λ~r ( ι ◦Q(~r)j (X) ) , j = 1, . . . , n,
where Λ~r = ∑ ~α||αk|=rk Λ~α,~r ◦ ι −1 T , and ι −1 T is the left inverse of the embedding ι. If p is also translation invariant, then
p(X) = p(X − 1 n X1n1 T n ) = ∑ T≤D ∑ ~r∈ΣT Λ̂~r ( ι ◦Q(~r)(X − 1 n X1n1 T n ) ) .
Thus QD is D-spanning.
We prove Lemma 3 Lemma 3. The function set QD is contained in
Ffeat = {ι ◦ πV ◦ f1 ◦ f2 ◦ . . . ◦ fT ◦ ext(X − 1
n X1n1
T n )| f j ∈ Fmin, T ≤ D}. (11)
Thus Ffeat is D-spanning.
Proof. In this proof we make the dependence of Ffeat on D explicit and denote Ffeat(D). We prove the claim by induction onD. AssumeD = 0. ThenQ0 contains only the constant function X 7→ 1n ∈ T n0 , and this is precisely the function πV ◦ ext ∈ Ffeat(0). Now assume the claim holds for all D′ with D − 1 ≥ D′ ≥ 0, and prove the claim for D. Choose ~r = (r1, . . . , rk) ∈ ΣT for some T ≤ D, we need to show that the function Q(~r) is in Ffeat(D). Since Ffeat(D − 1) ⊆ Ffeat(D) we know from the induction hypothesis that this is true if T < D. Now assume T = D. We consider two cases:
1. If r1 > 0, we set r̃ = (r1 − 1, r2, . . . , rK). We know that ι ◦Q(r̃)(X̄) ∈ Ffeat(D − 1) by the induction hypothesis. So there exist f2, . . . , fD such that
ι ◦ πV ◦ f2 ◦ . . . ◦ fD ◦ ext(X̄) = ι ◦Q(r̃)(X̄). (19)
Now choose f1 ∈ Fmin to be the function whose V coordinate Ṽ = (Ṽj)nj=1, is given by Ṽj(X,V ) = xj ⊗ Vj , obtained by setting θ1 = 1, θ2 = 0 in equation 9. Then , we have
Ṽj(X̄,Q (r̃)(X̄)) = n∑ i2,...,iK=1 x̄j ⊗ x̄⊗(r1−1)j ⊗ x̄ ⊗r2 i2 ⊗ . . .⊗ x̄⊗rKiK
= Q (~r) j (X̄).
and so
ι ◦ πV ◦ f1 ◦ f2 ◦ . . . ◦ fD ◦ ext(X − 1
n X1n1
T n ) = ι ◦Q(~r)(X̄). (20)
and ι ◦Q(~r)(X − 1nX1n1 T n ) ∈ Ffeat(D).
2. If r1 = 0. We assume without loss of generality that r2 > 0. Set r̃ = (r2 − 1, r3, . . . , rK). As before by the induction hypothesis there exist f2, . . . , fD which satisfy equation 19. This time we choose f1 ∈ Fmin to be the function whose V coordinate Ṽ = (Ṽj)nj=1, is given by Ṽj(X,V ) = ∑ j xj ⊗ Vj , obtained by setting θ1 = 0, θ2 = 1 in equation 9. Then
we have
Ṽj(X̄,Q (r̃)(X̄)) = n∑ j=1 n∑ i3,...,iK=1 x̄j ⊗ x̄⊗(r2−1)j ⊗ x̄ ⊗r2 i3 ⊗ . . .⊗ x̄⊗rKiK
= n∑ i2,i3,...,iK=1 x̄⊗r2i2 ⊗ x̄ ⊗r2 i3 ⊗ . . .⊗ x̄⊗rKiK
= Q (~r) j (X̄).
Thus equation 20 holds, and so again we have that ι ◦Q(~r)(X − 1nX1n1 T n ) ∈ Ffeat(D).
Finally we prove Lemma 4
Lemma 4. If all functions in QD can be written as
ι ◦Q(~r)(X − 1 n X1n1 T n ) = K∑ k=1 Âkfk(X),
where fk ∈ Ffeat, Ak : Wfeat → W Tfeat and Âk : Wnfeat → (W Tfeat)n is defined by elementwise application of Ak, then Ffeat is D-spanning.
Proof. If the conditions in Lemma 4 hold, then sinceQD is D-spanning, every translation invariant and permutation equivariant polynomials p of degree D can be written as
p(X) = ∑
~r|‖~r‖1≤D
Λ̂~r
( ι ◦Q(~r)(X − 1
n X1n1
T n )
) = ∑ ~r|‖~r‖1≤D Λ̂~r ( K~r∑ k=1 ι ◦ Âk,~rfk,~r(X) )
= ∑
~r|‖~r‖1≤D
K~r∑ k=1 Λ̂k,~r (fk,~r(X))
where we denote Λk,~r = Λ~r ◦ ι ◦Ak,~r. Thus we proved Ffeat is D-spanning.

heading: D PROOFS FOR SECTION 5
text: We prove Lemma 5
Lemma 5. Let l(1) = (`(1)1 , . . . , ` (1) K1 ) and l(2) = (`(2)1 , . . . , ` (2) K2
). A function Λ = (Λ1, . . . ,ΛK2) is a linear equivariant mapping between Wl(1) and Wl(2) , if and only if there exists a K1 ×K2 matrix M with Mij = 0 whenever ` (1) i 6= ` (2) j , such that
Λj(V ) = K1∑ i=1 MijVi (12)
where V = (Vi)K1i=1 and Vi ∈W`(1)i for all i = 1, . . . ,K1.
Proof. As mentioned in the main text, this lemma is based on Schur’s lemma. This lemma is typically stated for complex representations, but holds for odd dimensional real representation as well. We recount the lemma and its proof here for completeness (see also (Fulton & Harris, 2013)).
Lemma D.1 (Schur’s Lemma for SO(3)). Let Λ : W`1 → W`2 be a linear equivariant map. If `1 6= `2 then Λ = 0. Otherwise Λ is a scalar multiply of the identity.
Proof. Let Λ : W`1 → W`2 be a linear equivariant map. The image and kernel of Λ are invariant subspaces of W`1 and W`2 , respectively. It follows that if Λ 6= 0 then Λ is a linear isomorphism so necessarily `1 = `2. Now assume `1 = `2. Since the dimension of W`1 is odd, Λ has a real eigenvalue λ. The linear function Λ − λI is equivariant and has a non-trivial kernel, so Λ − λI = 0.
We now return to the proof of Lemma 5. Note that each Λj : Wl(1) → W`(2)j is linear and SO(3) equivariant. Next denote the restrictions of each Λj to W`(1)i , i = 1, . . . ,K2 by Λij , and note that
Λj(V1, . . . , VK1) = K1∑ i=1 Λij(Vi). (21)
By considering vectors in Wl(1) of the form (0, . . . , 0, Vi, 0 . . . , 0) we see that each Λij : W`(1)i →
W ` (2) j
is linear and SO(3)-equivariant. Thus by Schur’s lemma, if `(1)i = ` (2) j then Λij(Vi) = MijVi
for some real Mij , and otherwise Mij = 0. Plugging this into equation 21 we obtain equation 12.
We prove Theorem 2 which shows that the TFN network described in the main text is universal:
Theorem 2. For all n ∈ N, lT ∈ N∗+,
1. ForD ∈ N+, everyG-equivariant polynomial p : R3×n →WnT of degreeD is inFTFNC(D),D.
2. Every continuous G-equivariant function can be approximated uniformly on compact sets by functions in ∪D∈N+FTFNC(D),D
Proof. As mentioned in the main text, we only need to show that the function space Ffeat(D) is D-spanning. Recall that Ffeat(D) is obtained by 2D consecutive convolutions with D-filters. In general, we denote the space of functions defined by applying J consecutive convolutions by GJ,D.
If Y is a space of functions from R3×n → Y n, we denote by 〈Y, TT 〉 the space of all functions p : R3×n → T nT of the form
p(X) = K∑ k=1 Âkfk(X), (22)
where Ak : Y → TT are linear functions, Âk : Y n → T nT are induced by elementwise application, and fk ∈ Y . This notation is useful because: (i) by Lemma 4 it is sufficient to show that Q(~r)(X̄) is in 〈G2D,D, TT 〉 for all ~r ∈ ΣT and all T ≤ D, and because (ii) it enables comparison of the expressive power of function spaces Y1,Y2 whose elements map to different spaces Y n1 , Y n2 , since the elements in 〈Yi, TT 〉, i = 1, 2 both map to the same space. In particular, note that if for every f ∈ Y2 there is a g ∈ Y1 and a linear map A : Y1 → Y2 such that f(X) = Â ◦ g(X), then 〈Y2, TT 〉 ⊆ 〈Y1, TT 〉. We now use this abstract discussion to prove some useful results: the first is that for the purpose of this lemma, we can ‘forget about’ the multiplication by a unitary matrix in equation 14, used for decomposition into irreducible representations: To see this, denote by G̃J,D the function space obtained by taking J consecutive convolutions withD-filters without multiplying by a unitary matrix in equation 14. Since Kronecker products of unitary matrices are unitary matrices, we obtain that the elements in GJ,D and G̃J,D differ only by multiplication by a unitary matrix, and thus 〈G̃J,D, TT 〉 ⊆ 〈GJ,D, TT 〉 and 〈GJ,D, TT 〉 ⊆ 〈G̃J,D, TT 〉, so both sets are equal. Next, we prove that adding convolutional layers (enlarging J) or taking higher order filters (enlarging D) can only increase the expressive power of a network.
Lemma D.2. For all J,D, T ∈ N+,
1. 〈GJ,D, TT 〉 ⊆ 〈GJ+1,D, TT 〉.
2. 〈GJ,D, TT 〉 ⊆ 〈GJ,D+1, TT 〉.
Proof. The first claim follows from the fact that every function f in 〈GJ,D, TT 〉 can be identified with a function in 〈GJ+1,D, TT 〉 by taking the J + 1 convolutional layer in equation 14 with θ0 = 1, F = 0.
The second claim follows from the fact that D-filters can be identified with D + 1-filters whose D + 1-th entry is 0.
The last preliminary lemma we will need is
Lemma D.3. For every J,D ∈ N+, and every t, s ∈ N+, if p ∈ 〈GJ,D, Tt〉, then the function q defined by
qa(X) = n∑ b=1 (x̄a − x̄b)⊗s ⊗ pb(X)
is in 〈GJ+1,D, Tt+s〉.
Proof. This lemma is based on the fact that the space of s homogeneous polynomial on R3 is spanned by polynomials of the form ‖x‖s−`Y `m(x) for ` = s, s − 2, s − 4 . . . (Dai & Xu, 2013). For each such `, and s ≤ D, these polynomials can be realized by filters F (`) by setting R(`)(‖x‖) = ‖x‖s so that
F (`)m (x) = ‖x‖sY `m(x̂) = ‖x‖s−`Y `m(x). For every D ∈ N and s ≤ D, we can construct a D-filter F s,D = (F (0), . . . , F (D)) where F (s), F (s−2), . . . are as defined above and the other filters are zero. Since both the entries of F s,D(x), and the entries of x⊗s, span the space of s-homogeneous polynomials on R3, it follows that there exists a linear mapping Bs : WlD → Ts so that
x⊗s = Bs(F s,D(x)),∀x ∈ R3. (23)
Thus, since p can be written as a sum of compositions of linear mappings with functions in GJ,D as in equation 22, and similarly x⊗s is obtained as a linear image of functions in G1,D as in equation 23, we deduce that
n∑ b=1 (xa − xb)⊗ pb(X) = n∑ b=1 (x̄a − x̄b)⊗ pb(X)
is in 〈GJ+1,D, Tt+s〉
As a final preliminary, we note thatD-filters can perform an averaging operation by settingR(0) = 1 and θ0, R(1), . . . , R(D) = 0 in equation 13 and equation 14 . We call thisD-filter an averaging filter.
We are now ready to prove our claim: we need to show that for every D,T ∈ N+ where T ≤ D, for every ~r ∈ ΣT , the function Q(~r) is in 〈G2D,D, TT 〉. Note that due to the inclusion relations in Lemma D.2 it is sufficient to prove this for the case T = D. We prove this by induction on D. For D = 0, vectors ~r ∈ Σ0 contains only zeros and so
Q(~r)(X̄) = 1n = πV ◦ ext(X) ∈ 〈G0,0, T0〉.
We now assume the claim is true for all D′ with D > D′ ≥ 0 and prove the claim is true for D. We need to show that for every ~r ∈ ΣD the function Q(~r) is in 〈G2D,D, TD〉. We prove this yet again by induction, this time on the value of r1: assume that ~r ∈ ΣD and r1 = 0.. Denote by r̃ the vector in ΣD−1 defined by r̃ = (r2 − 1, r3, . . . , rK). By the induction assumption on D, we know that Q(r̃)(X̄) ∈ G2(D−1),D−1,D−1 and so
qa(X) = n∑ b=1 (x̄a − x̄b)⊗Q(r̃)b (X̄) = n∑ b=1 (x̄a − x̄b)⊗ x̄⊗r2−1b ⊗ n∑ i3,...,iK=1 x̄⊗r3i3 ⊗ . . .⊗ x̄ ⊗rK iK
= ( x̄a ⊗
n∑ b=1 Q (r̃) b (X̄)
) −Q(~r)(X̄)
is in 〈G2D−1,D−1, TD〉 by Lemma D.3, which is contained in 〈G2D−1,D, TD〉 by Lemma D.2. Since x̄a has zero mean, while Q (~r) a (X̄) does not depend on a since r1 = 0, applying an averaging filter to qa gives us a constant value −Q(~r)a (X̄) in each coordinate a ∈ [n], and so Q(~r)(X̄) is in 〈G2D,D, TD〉. Now assume the claim is true for all ~r ∈ ΣD which sum to D, and whose first coordinate is smaller than some r′1 ≥ 1, we now prove the claim is true when the first coordinate of ~r is equal to r′1. The vector r̃ = (r2, . . . , rK) obtained from ~r by removing the first coordinate, sums to D′ = D − r′1 < D, and so by the induction hypothesis on D we know that Q(r̃) ∈ 〈G2D′,D′ , TD′〉. By Lemma D.3 we obtain a function qa ∈ 〈G2D′+1,D′ , TD〉 ⊆ 〈G2D,D, TD〉 defined by
qa(X) = n∑ b=1 (x̄a − x̄b)⊗r1 ⊗Q(r̃)b (X̄)
= n∑ b=1 (x̄a − x̄b)⊗r1 ⊗ x̄⊗r2b ⊗ n∑ i3,...,iK=1 x̄⊗r3i3 ⊗ . . .⊗ x̄ ⊗rK iK
= Q(~r)a (X̄) + additional terms
where the additional terms are linear combinations of functions of the form PDQ (r′) a (X̄) where r′ ∈ ΣD and their first coordinate r1 is smaller than r′1, and PD : TD → TD is a permutation. By the induction hypothesis on r1, each such Q(r ′) is in 〈G2D,D, TD〉. It follows that PDQ(r ′) a (X̄), a = 1, . . . , n, and thus Q(~r)(X̄), are in 〈G2D,D, TD〉 as well. This concludes the proof of Theorem 2.

heading: E ALTERNATIVE TFN ARCHITECTURE
text: In this appendix we show that replacing the standard TFN convolutional layer with the layer defined in equation 15:
Ṽa(X,V ) = U(lf , li) ( θ1
n∑ b=1 F (xa − xb)⊗ Vb + θ2 n∑ b=1 F (xa − xb)⊗ Va
) ,
we can obtain D-spanning networks using 2D consecutive convolutions with 1-filters (that is, filters inWl1 , where l1 = [0, 1] T ). Our discussion here is somewhat informal, meant to provide the general
ideas without delving into the details as we have done for the standard TFN architecture in the proof of Theorem 2. In the end of our discussion we will explain what is necessary to make this argument completely rigorous.
We will only need two fixed filters for our argument here: The first is the 1-filter FId = (F (0), F (1)) defined by setting R(0)(‖x‖) = 0 and R(1)(‖x‖) = ‖x‖ to obtain
FId(x) = ‖x‖Y 1(x̂) = ‖x‖x̂ = x.
The second is the filter F1 defined by setting R(0)(‖x‖) = 1 and R(1)(‖x‖) = 0, so that
F1(x) = 1.
We prove our claim by showing that a pair of convolutions with 1-filters can construct any convolutional layer defined in equation 9 for the D-spanning architecture using tensor representations. The claim then follows from the fact that D convolutions of the latter architecture suffice for achieving D-spanning, as shown in Lemma 3.
Convolutions for tensor representations, defined in equation 9, are composed of two terms:
Ṽ tensor,1a (X̄, V ) = x̄a ⊗ Va and Ṽ tensor,2a (X̄, V ) = n∑ b=1 x̄b ⊗ Vb.
To obtain the first term Ṽ tensor,1a , we set θ1 = 0, θ2 = 1/n, F = FId in equation 15 we obtain (the decomposition into irreducibles of) Ṽ tensor,1a (X̄, V ) = x̄a ⊗ Va. Thus this term can in fact be expressed by a single convolution. We can leave this outcome unchanged by a second convolution, defined by setting θ1 = 0, θ2 = 1/n, F = F1.
To obtain the second term Ṽ tensor,2a , we apply a first convolution with θ1 = −1, F = FId, θ2 = 0, to obtain
n∑ b=1 (xb − xa)⊗ Vb = n∑ b=1 (x̄b − x̄a)⊗ Vb = Ṽ tensor,2a (V, X̄)− x̄a ⊗ n∑ b=1 Vb
By applying an additional averaging filter, defined by setting θ1 = 1n , F = F1, θ2 = 0, we obtain Ṽ tensor,2a (V, X̄). This concludes our ‘informal proof’.
Our discussion here has been somewhat inaccurate, since in practice FId(x) = (0, x) ∈ W0 ⊕W1 and F1(x) = (1, 0) ∈ W0 ⊕W1. Moreover, in our proof we have glossed over the multiplication by the unitary matrix used to obtain decomposition into irreducible representations. However the ideas discussed here can be used to show that 2D convolutions with 1-filters can satisfy the sufficient condition for D-spanning defined in Lemma 4. See our treatment of Theorem 2 for more details.

heading: F COMPARISON WITH ORIGINAL TFN PAPER
text: In this Appendix we discuss three superficial differences between the presentation of the TFN architecture in Thomas et al. (2018) and our presentation here:
1. We define convolutional layers between features residing in direct sums of irreducible representations, while (Thomas et al., 2018) focuses on features which inhabit a single irreducible representation. This difference is non-essential, as direct sums of irreducible representations can be represented as multiple channels where each feature inhabits a single irreducible representation.
2. The term θ0Va in equation 14 appears in (Fuchs et al., 2020), but does not appear explicitly in (Thomas et al., 2018). However it can be obtained by concatenation of the input of a self-interaction layer to the output, and then applying a self-interaction layer.
3. We take the scalar functions R(`) to be polynomials, while (Thomas et al., 2018) take them to be fully connected networks composed with radial basis functions. Using polynomial scalar bases is convenient for our presentation here since it enables exact expression of
equivariant polynomials. Replacing polynomial bases with fully connected networks, we obtain approximation of equivariant polynomials instead of exact expression. It can be shown that if p is a G-equivariant polynomial which can be expressed by some network FC,D defined with filters coming from a polynomial scalar basis, then p can be approximated on a compact set K, up to an arbitrary error, by a similar network with scalar functions coming from a sufficiently large fully connected network.

heading: G TENSOR UNIVERSALITY
text: In this section we show how to construct the complete setFpool of linear SO(3) invariant functionals from W Tfeat = ⊕D T=0 TT to R. Since each such functional Λ is of the form
Λ(w0, . . . , wD) = D∑ T=0 ΛT (wT ),
where each ΛT is SO(3)-invariant, it is sufficient to characterize all linear SO(3)-invariant functionals Λ : TD → R. It will be convenient to denote
W = R3 and W⊗D ∼= R3 D = TD.
We achieve our characterization using the bijective correspondence between linear functional Λ : W⊗D → R and multi-linear functions Λ̃ : WD → R: each such Λ corresponds to a unique Λ̂, such that Λ̃(ei1 , . . . , eiD ) = Λ(ei1 ⊗ . . .⊗ eiD ), ∀(i1, . . . , iD) ∈ [3]D, (24) where e1, e2, e3 denote the standard basis elements of R3. We define a spanning set of equivariant linear functionals onW⊗D via a corresponding characterization for multi-linear functionals onWD. Specifically, set KD = {k ∈ N+|D − 3k is even and non-negative. } For k ∈ KD we define a multi-linear functional:
Λ̃k(w1, . . . , wD) = det(w1, w2, w3)× . . .× det(w3k−2, w3k−1, w3k)× 〈w3k+1, w3k+2〉 × . . . × 〈wD−1, wD〉, (25)
and for (k, σ) ∈ KD × SD we define
Λ̃k,σ(w1, . . . , wD) = Λ̃k(wσ(1), . . . , wσ(D)) (26)
Proposition 1. The space of linear invariant functions from TD to R is spanned by the set of linear invariant functionals λD = {Λk,σ| (k, σ) ∈ KD × SD} induced by the multi-linear functional Λ̃k,σ described in equation 25 and equation 26
We note that (i) equation 24 provides a (cumbersome) way to compute all linear invariant functionals Λk,σ explicitly by evaluating the corresponding Λ̃k,σ on the 3D elements of the standard basis and (ii) the set λD is spanning, but is not linearly independent. For example, since 〈w1, w2〉 = 〈w2, w1〉, the space of SO(3) invariant functionals on T2 = W⊗2 is one dimensional while |λ2| = 2.
Proof of Proposition 1. We first show that the bijective correspondence between linear functional Λ : W⊗D → R and multi-linear functions Λ̃ : WD → R, extends to a bijective correspondence between SO(3)-invariant linear/multi-linear functionals. The action of SO(3) on WD is defined by
ρ̃(R)(w1, . . . , wD) = (Rw1, . . . , RwD).
The action ρ(R) = R⊗D of SO(3) on W⊗D is such that the map
(w1, . . . , wD) 7→ w1 ⊗ w2 . . . wD
is SO(3)- equivariant. It follows that if Λ̃ and Λ satisfy equation 24, then for all R ∈ SO(3), the same equation holds for the pair Λ̃ ◦ ρ̃(R) and Λ ◦ ρ(R). Thus SO(3)-invariance of Λ̃ is equivalent to SO(3)-invariance of Λ.
Multi-linear functionals onWD invariant to ρ̃ are a subset of the set of polynomials onWD invariant to ρ̃. It is known (see (Kraft & Procesi, 2000), page 114), that all such polynomials are algebraically generated by functions of the form
det(wi1 , wi2 , wi3) and 〈wj1 , wj2〉, where i1, i2, i3, j1, j2 ∈ [D].
Equivalently, SO(3)-invariant polynomials are spanned by linear combinations of polynomials of the form det(wi1 , wi2 , wi3) det(wi4 , wi5 , wi6) . . . 〈wj1 , wj2〉〈wj3 , wj4〉 . . . . (27) When considering the subset of multi-linear invariant polynomials, we see that they must be spanned by polynomials as in equation 27, where each w1, . . . , wD appears exactly once in each polynomial in the spanning set. These precisely correspond to the functions in λD.

heading: H EXPERIMENTS
text: This section provides an experimental evaluation of different design choices of the TFN architecture, inspired by our theoretical analysis. We study the following questions:
1. The importance of non-linear activation. Our proof shows that using non-linear activation functions is not necessary for proving universality. Here, we empirically test the possibility of removing these layers.
2. The importance of high-dimensional irreducible representations. Our theoretical analysis shows that in order to represent/approximate high degree polynomials, high-order representations should be used. Here, we check whether using high-order representations has practical benefits.
3. The effect of self-interaction layers. Our proof suggests that it is enough to use self interaction linear layers at the end of the model. We empirically compare this approach with the more common approach of using self-interaction layers after each convolutional layer.
Dataset. We use the QM9 (Ramakrishnan et al., 2014) dataset for our experiments. The dataset contains 134K molecules, with node 3D positions, 5 categorical node features and 4 categorical edge features. The task is a molecule property prediction regression task.
Framework. We used pytorch (Paszke et al., 2017)as the deep learning framework and the Deep Graph Library (DGL) (Wang et al., 2019a) as the graph learning framework. All experiments ran on NVIDIA GV100 GPUs.
Experimental setup. We use the the TFN implementation from Fuchs et al. (2020). We trained each model variant for 50 epochs on the homo target variable using an `1 loss function and the ADAM optimizer with learning rate 10−3 and report results on the test set on the final epoch averaged over two runs. We used the default parameters and data splits from Fuchs et al. (2020).
Architecture. The architecture consists of 4 TFN convolutional layers, each followed by a linear self-interaction layer. We used 16 copies of each irreducible representation used. We used normbased non-linearity as in the original TFN paper (Thomas et al., 2018). These convolutional layers are followed by a max-pooling layer and two fully connected layers with 16d features in the hidden layer, where d is the maximal degree of irreducible representations used.
Results. Table 1 and Figure 1 present the results. The main conclusions are: (1) The experiments show that, at least for this task, using non-linear activations does not improve performance. This result fits our theoretical analysis which shows that these layers are not needed for universality. (2) Figure 1 presents a plot of error vs representation degrees used. The plot clearly shows that using high-dimensional representations (up to order 3) improves performance, which also fits our analysis. Using representation orders higher than 3 is significantly more time consuming, and was found to have little effect on the results (as in in Fuchs et al. (2020)), though we believe this to be application-dependent. (3) Using self interaction layers only at the end of the model is shown to have marginal negative effect on the results.

Review summaries:
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.

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.