On Universal Equivariant Set Networks
Authors: Nimrod Segol
Yaron Lipman
Venue:  (2020)
Keywords: deep learning
universality
set functions
equivariance

Abstract: Using deep neural networks that are either invariant or equivariant to permutations in order to learn functions on unordered sets has become prevalent. The most popular, basic models are DeepSets (Zaheer et al. 2017) and PointNet (Qi et al. 2017). While known to be universal for approximating invariant functions, DeepSets and PointNet are not known to be universal when approximating equivariant set functions. On the other hand, several recent equivariant set architectures have been proven equivariant universal (Sannai et al. 2019, Keriven and Peyre 2019), however these models either use layers that are not permutation equivariant (in the standard sense) and/or use higher order tensor variables which are less practical. There is, therefore, a gap in understanding the universality of popular equivariant set models versus theoretical ones. 
			
In this paper we close this gap by proving that: (i) PointNet is not equivariant universal; and (ii) adding a single linear transmission  layer makes PointNet universal. We call this architecture PointNetST and argue it is the simplest permutation equivariant universal model known to date. Another consequence is that DeepSets is universal, and also PointNetSeg, a popular point cloud segmentation network (used e.g., in Qi et al. 2017) is universal.
		
The key theoretical tool used to prove the above results is an explicit characterization of all permutation equivariant polynomial layers. Lastly, we provide numerical experiments validating the theoretical results and comparing different permutation equivariant models.

Published as a conference paper at ICLR 2020
ON UNIVERSAL EQUIVARIANT SET NETWORKS
Nimrod Segol & Yaron Lipman
Department of Computer Science and Applied Mathematics
Weizmann Institute of Science
Rehovot, Israel
(nimrod.segol) yaron. 1 Lipman @wei zmann ac. i1
ABSTRACT
Using deep neural networks that are either invariant or equivariant to permutations in order to learn functions on unordered sets has become prevalent. The most pop- ular, basic models are DeepSets (Zaheer al.) 2017) and PointNet (Qi et al. 2017). While known to be universal for approximating invariant functions, DeepSets and PointNet are not known to be universal when approximating equivariant set fune- tions. On the other hand, several recent equivariant set architectures have been proven equivariant universal (Sannai et al. 2019 Keriven & Peyré 2019), however these models either use layers that are not permutation equivariant (in the standard sense) and/or higher order tensor variables which are less practical. There is, therefore, a gap in understanding the universality of popular equivariant set models versus theoretical ones.
this paper we close this gap by proving that: (i) PointNet is not equivariant universal: and (ii) adding single linear transmission layer makes PointNet univer- sal. We call this architecture PointNetST and argue it is the simplest permutation equivariant universal model known date. Another consequence is that DeepSets is universal, and also PointNetSeg, popular point cloud segmentation network (used e.g., in (Qi al. 2017) universal.
The key theoretical tool used to prove the above results an explicit characteriza- tion of all permutation equivariant polynomial layers. Lastly, we provide numerical experiments validating the theoretical results and comparing different permutation equivariant models.
INTRODUCTION
Many interesting tasks in machine learning can be described by functions F that take as in- put a set, X (#1...., Zn), and output some per-element features or values, F(X) (F(X),,..., F()).). Permulation equivariance is the property required of F so it is well- defined. Namely, assures that reshuffling the elements in X and applying F results in same output, reshuffled the same manner. For example, if X (æ22, 11 T., vn) then F(X) = (F(X)2 F(X),, F(X)a,..... ((X)),).,FF(),,,.
Building neural networks that permutation equivariant by construction proved extremely useful in practice. Arguably the most popular models are DeepSets Zaheer et al. (2017) and PointNet Qi et al. (201)). These models enjoy small number of parameters, low memory footprint and computational efficiency along with high empirical expressiveness. Although both DeepSets and PointNet are known to be invariant universal (i.e., can approximate arbitrary invariant continuous functions) they are not known to be equivariant universal (i.e., can approximate arbitrary equivariant continuous functions).
On the other hand, several researchers have suggested theoretical permutation equivariant models and proved they are equivariant universal. Sannai al. (2019) builds a universal equivariant network by taking n copies of (n 1 -iivarriin networks and combines them with layer that is not permutation invariant in the standard (above mentioned) sense. Keriven & Peyré (2019) solves more general problem of building networks that are equivariant universal over arbitrary high order input tensors Rnd (including graphs); their construction, however, higher order tensors hidden variables

---

Published as a conference paper at ICLR 2020
which is of less practical value. Yarotsky (2018) proves that neural networks constructed using finite set of invariant and equivariant polynomial layers are also equivariant universal, however his network is not explicit (i.c., the polynomials are not characterized for the equivariant case) and also of less practical interest due to the high degree polynomial layers.
In this paper we close the gap between the practical and theoretical permutation equivariant construc- tions and prove:
Theorem
(i) PointNet is not equivariant universal.
(ii) Adding single linear transmission layer (i.e., X + 11 X) to PointNet makes il equivariant universal.
(ii) Using ReLU activation the minimal width required for universal permutation equivariant network satisfies w S kout + kmn + + kin
(n.tkus).
This theorem suggests that, arguably, PointNet with an addition of single linear layer the simplest universal equivariant network, able to learn arbitrary continuous equivariant functions of sets. An immediate corollary this theorem
Corollary 1. DeepSets and PointNetSeg universal.
PointNetSeg is network used often for point cloud segmentation (e.g., in Qi et al. (2017)) One of the benefit of result is that provides simple characterization of universal equivariant architectures that can be used in the network design process to guarantee universality.
The theoretical tool used for the proof of Theorem is explicit characterization of the permutation equivariant polynomials over sets of vectors in IR" using power-sum multi multi-syymmtric polynomials. We prove:
Theorem 2. Let P Rank + Ruxl be permutation equivariant polynomial map. Then,
P(X)
-x)==
=E baga
Ja|5n
where ba = (xf..... x...,,,,). TT qa -9a........ ax.))² where qa.3 qa. st), ) t (n*th), are polynomials; 85 (X) Σn= x.," are the power-sum multi-symmetric polynomials. On the other hand every polynomial map P satisfying Equation] iis equivariant.
This theorem, which extends Proposition 2.27 in Golubitsky & Stewart 2002) to sets of vectors using multivariate polynomials, lends itself to expressing arbitrary equivariant polynomials as composition of entry-wise continuous functions and single linear transmission, which in turn facilitates the proof of Theorem 1
We conclude the paper by numerical experiments validating the theoretical results and testing several permutation equivariant networks for the tasks of set classification and regression.
PRELIMINARIES
Equivariant maps. Vectors R* are by default column vectors; 0, 1 are the all zero and all one vectors/tensors; e; is the i-th standard basis vector; I the identity matrix; all dimensions are inferred from context mentioned explicitly. We represent set of n vectors in R matrix X Rank and denote X = (æt, 22 "",."", where æ; E R E [n]. are the columns of X. We denote by S, the permutation group of [n]; its action X is defined by X (1)) (2)) -........ ... (n))(n)) YT, E Sn- That is, a is reshuffling the rows of X. The natural class of maps assigning a value or feature vector to every element in an input set is permutation equivariant maps:
Definition 1. A map F Bank + Baxl satisfying F(a X) F(X) for all a Sn and X E Raxd is called permutation equivariant.
Power-sum multi-symmetric polynomials. Given a vector (Z mn) E R the power-
sum symmetric polynomials sy(z) E zf. with j E [n]], uniquely characterize up permuting
2

---

Published as a conference paper at ICLR 2020
its entries. In other words, for y R" we have y for some S, if and only if s) 8y(z) for all j E [ra]. An equivalent property that every S, invariant polynomial can be expressed polynomial in the power-sum symmetric polynomials, i.c., p(z) (z)) Sn (z)), see Rych (2007) Corollary 8.4, BBrind (2004) Theorem 3. This fact was previously used in Zaheer et al. (2017) prove that DeepSets is universal for invariant functions. We extend this result equivariant functions and the multi-feature (sets of vectors) case.
For vector æ E R& and multi-index vector a (a1,...,, aus E N define x" 21 and |a:| = ΣiE(k] Oti. A generalization of the power-sum symmetric polynomials to matrices exists and is called power-sum multi-symmetric polynomials, defined with bit of notation abuse: s, Σ o." where N is multi-index satisfying |a| S n. Note that the number of power-sum sullti- polynomials acting on E Baxk is t = (*++))) ) For notation simplicity
let a....., Oc, be list of all a E N with |al < n.. Then we index the collection of power-sum multi-symmetric polynomials as $1...., St.
Similarly to the vector case the numbers (x)), j [t] characterize X up to permutation of its rows. That is every S, invariant polynomial p Rn k R can be expressed as polynomial in the power-sum multi-symmetric polynomials (see (Rydh 2007 corollary 8.4), i.e.,
X for some E Sn iff sY sY for all j [t]. Furthermore,
p ( g(s) (X)
xx)),
(2)
These polynomials were recently used to encode multi-sets in Maron et al. 2019)
EQUIVARIANT MULTI-SYMMETRE POLYNOMIAL LAYERS
In this section develop the main theoretical tool of this paper, namely, a characterization of all permutation equivariant polynomial layers. As far as we know, these layers were not fully characterized before.
Theorem provides an explicit representation of arbitrary permutation equivariant polynomial maps P RiiX + Rnxi using the basis of power- sum multi- multi-symmetric polynomials, s, (X).. The particular use of power-sum polynomials 8; (X) has the advantage it can be encoded efficiently using a neural network: as we will show 8 (()) can be approximated using a PointNet with a single linear transmission layer. This allows approximating arbitrary equivariant polynomial map using PointNet with a single linear transmission layer.
A version of this theorem for vectors instead of matrices (i.e., the case of A: 1) appears as Proposition 2.27 in Golubitsky & Stewart (2002); we extend their proof to matrices, which is the relevant scenario for ML applications it allows working with sets of vectors. For k Theorem 2 reduces to the following form: p(x); Easn Pa (s), ....)................... 8, (=f) with sy(x) Σ; ar{ For matrices the monomial o is replaced by æ. for multi-index a and the power-sum symmetric polynomials are replaced by the power-sun multi-symment polynomials.
First, note that it enough to prove Theorem for / = and apply it to every column of P. Hence, deal with vector of polynomials p R R and need to prove it be expressed as Jolsa bada. for S,, invariant polynomial ga-
Given a polynomial p(X) and the eyclic permutation o- (123 n) the following operation, taking a polynomial to a vector polynomials, useful characterizing equivariant polynomial maps:
p(X)
pla X)
plo² x))
[x](x)=
(3)
p(o x)
Theorem 2 will be proved using the following two lemmas:
Lemma 1. Let p: PRR + R be an equivariant polynomial map. Then, there exists a polynomial p: Back RR invariant to Sa-1 (permuting the last n. rows of X so that p [p].
3

---

Published as a conference paper at ICLR 2020
Proof. Equivariance of p means that for all a E Sn it holds that p(X) p(o X)
(( = p(a X).
(4)
Choosing an arbitrary permutation о E stab(1) < S., namely permutation satisfying a = 1, and
observing the first in Equation 4 get pi (X) pi (a X) pi (æ), (2)- ................................ - (x))
Since this is true for all sTab(1) P1 is S, invariant. Next, applying (1x) to Equation
and observing the first row again we get px( Pı Et.............................. ..,...). Using the invariance of pr to
S we get p [pi].
Lemma 2. Let R - R be polynomial invariant to Sn-1 (permutting the last rows of X) then
p(X)
Σ (X),
(5)
|A|So
where are Sn invariant.
Proof. Expanding with respect to 3 we get
( Σ lalsm
for some N. We first claim Pa are Sn-1 invariant. Indeed, note that if p(X) p(111 I2..... Fn)) is Sn-1 invariant, i.e., invariant to permutations ,2,..., In. then also its deriva- tives aldi
aæy p( X) are Sn-1 permutation invariant, for all / E N*. Taking the derivative ØlÅl /ax both sides of Equation 6 we get that ps is - equivariant.
For brevity denote p = Pa- Since p S invariant can be expressed as a polynomial in the power- sum multi-symmetric polynomials, i.e. p(222 Fx,) (x2) Fn). Sx znn)
Note that 8; (2 vn) = 8; (X) x and therefore
p ................................ ..) (X) of"..................... (x - =x(
Since is polynomial, expanding its monomials in (X) and æf shows p be expressed as = Ejais Sm Pfp.. where m' E N, and p. are S, invariant (as multiplication of invariant S, polynomials (X))). Plugging this in Equation 6 we get Equation 5 possibly with the sum over some n > n. It remains show n' can be taken to be at-most n. This is proved in Corollary 5 in Briand 2004)
Proof. (Theorem 2 Given an equivariant p as above, use Lemma I to write p = [-pp where p(X) is to write p(X) = Σ Jalgn x qa (X)).
invariant to permuting the last n 1 rows of X. Use Lemma 2 where lo are S, invariant. We get,
pp
Σ
baqa-
Sal
The converse direction is immediate after noting that b, are equivariant and Ja are invariant.
4 UNIVERSALITY OF SET EQUIVARIANT NEURAL NETWORKS
We consider equivariant deep neural networks f Runks + Baxkaut
F(X)= = Lm o ovo........... ... (X),,
where L; x - R B are affine equivariant transformations, and v is an entry-wise non- linearity (e.g., ReLU). We define the width of the network to be w max; k;; note that this definition different from the one used for standard MI.P where the width would nw, see e.g., Hanin & Sellke (2017). Zaheer al. (2017) proved that affine cquivariant L; are of the form
L XA+
T ICT
(8)
n
4

---

Published as a conference paper at ICLR 2020
where A, E R and c E R are the layer's trainable parameters; call the linear transformation X + -11xXB. a linear transmission layer.
We now define the equivariant models considered in this paper: The DeepSets Zaheer et al. 2017) architecture is Equation 7 with the choice of layers as in Equation X Taking B = in all layers is the PointNet architecture (Qi et al. 2017). PointNetST is equivariant model of the form Equation 7 with layers as in Equation g where only a single layer L; has a non-zero B. The PointNetSeg (Qi et al. 2017) architecture is PointNet composed with invariant max layer, namely max F ()) maX:E[m]
F(X):, )a, and then concatenating it with the input X, i.e., [X, 1 (max(F(X)) and feeding is as input to another PointNet G, that is ((X, max max(F(X)) (F))))
We will prove PointNetST permutation equivariant universal and therefore arguably the simplest permutation equivariant universal model known to date.
Universality of equivariant deep networks is defined next.
Definition 2. Permutation equivariant universality of a model F : :Ruxken - Bnnkkos means that for every permutation equivariant continuous function H Ruxkkn - Bruxkow defined over the cube K [0, 1]mxXit. C RRn*ks,, and O there exists choice of m (i.e., network depth), kt (i.e., network width) and the trainable parameters of so that (X( -( < for all E K.
Proof. (Theorem D Fact (i), namely that PointNet is not equivariant universal is consequence the following simple lemma:
Lemma 3. Let h = (hi...., hn) R. + R" be the equivariant linear function defined by h(x)= = 11 x. There is no f F: R. that (,,(x) - fz,)) for all [n] and [0, 1lm
Proof. Assume such f exists. Let = (1.0....,, 0)" E R.. Then,
1 1 ((2(e1) - h2)( s (/2(ee) - ((0) + 1S(0) b2 (0) <
reaching a contradiction.
To prove (ii) we first reduce the problem from the class of all continuous equivariant functions to the class of equivariant polynomials. This is justified by the following lemma.
Lemma 4. Equivariant polynomials P Ruxkin - Ruxkout are dense in the space of continuous equivariant functions F gunkinn + Roukkoou over the cube K.
Proof. Take an arbitrary 6 > O. Consider the function ftz -Raxkin - I. which denotes the (i. output entry of F. By the Stone- Weieesrsesssssss Theorem there exists polynomial Ptj guxkin + R such that [| (X) - (xj(X))l S e for all X K. Consider the polynomial map P: Baxkia + Banxkou defined by (P); = Pij- P in general not equivariant. To finish the proof we will symmetrize P:
1
F(X) Eo. X
Σ
o. F -1 1.) O.P P o
n! TES,
oES
oES
Σ (Flo -1 -1 x) - P
n!
dES
20
c=c,
TES
where in the first equality used the fact that F is equivariant. This concludes the proof since Eres, o Pla-1. X) is an equivariant polynomial map.
Now, according to Theorem 2 an arbitrary equivariant polynomial can be written as P Epssn (X)", where b. (X) [>p] E R" and qa
Bunkio + Bunkous
'Or just equivariant universal in short.
5

---

Published as a conference paper at ICLR 2020
19a,1:.... ....:........................... Nout E RRout are invariant polynomials. Remember that every S, invariant polynomial can be expressed
polynomial in the t ( kin
(m*tkun) power-sum multi-symmetric polynomials
8y(X) +/4 Ei= ". j E [4] (we use the 1/n normalized version for a bit more simplicity later on). We can therefore write P composition of three maps:
P = Q L L
where Ruxkin - Rax! defined by
((x) (b(x1); ((,bb((())) b(xn))"
b(x)) = (x ..... x² L is defined as in Equation with B [0, I] and A (ei...., Ckis 0,. where I E Rixt the identity matrix and e; E IR' represents the standard basis (as-usual). We assume Oj = Ej IRki for E [kin]. Note that the output of L is of the form
L(B(X)) = (x, (X) (X), (x)).
Finally, Q Rax +1) - R kont is defined by
181, 18;) = (1) st).... q( $1, st))..,s)))"
and q( S1..............................
.0.............................. s1) Eaalsn x² qa (s.........)
The decomposition in Equation of P suggests that replacing Q, B with Multi- Perceptrons (MLPs) would lead to a universal permutation equiv- ariant network consisting of PointNet with a single linear transmission layer, namely PointNetST.
kin
koud
S
L
The F approximating P will be defined as
= +
(10)
where b Ruxkin Rxx and v R Banaaau are both of PointNet architecture, namely
Figure 1: The construction of the universal
network (PointNetST).
there exist MLPs Φ 1R R' and sb Rethiin - ghout so that (XX) = (Ø(x1),... o(x,))² and (X) = (+b())),... ( ( See Figure !
for illustration of F.
To build the MLPs Φ ab we will first construct 2! to approximate that is. we use the universality of MLPS (see (Hornik 1991 Sonoda & Murata 2017 Hanin & Sellke 2017)) construct &p so that ( 81,.... Il) < I for all (ær, 01,.8 8t) E [0, 1 kin Furthermore, as ab over 00, 1) is uniformly continuous, let 5 be such that if 2, z' E [0. 1 1
[|, (1,.,,,,
|| *t
2'1l <
then [|<(()) (222))loc < Now, we use universality again to construct & approximating b, that is we take Φ so that [|Ø(x) - -b(x)ll> < for all æ E [0, 1
[F(X P(X)I S |+(((((X)) & (L((()) (|LBB( -
=err + err2
First, (x)) - L(B(x))ll 8 for all X K and therefore err < Second, note that X E K then B(X) E [0, 1| and L(B(X)) [0, (p.. +t), Therefore by construction of zb we have err2 5.
To prove (ili) we use the result in Hanin & Sellke (2017) (see Theorem 1) bounding the width of an MLP approximating a function f. [0, 1 Jen + Roout by d,n + dout- Therefore, the width of the
MLP Φ is bounded by kin + t, where the width of the MLP &b is bounded by t + kin houts proving the bound.
We can now prove Cororllary I
Proof. (Corollary
The fact that the DeepSets model is equivariant universal is immediate. Indeed, The PointNetST model can be obtained from the DeepSets model by setting = 0 in all but one layer, with B as in Equation 8

---

Published as a conference paper at ICLR 2020
For the PointNetSeg model note that by Theorem 1 in Qi et al. (2017) every invariant function f: IR"* + R' can be approximated by a network of the form v max F(X))), where (F(X) is PointNet model and V is an MLP. In particular, for every > 0 there exists such F, & for which / (max(F( F)))) - (x1(X)) )..... ,....,&t( +x(X)) < & for every X E [0, 1|=xkin where 81 (X),.... s (X) are the power-sum multi-symmetric polynomials. It follows that
use
PointNetSeg to approximate ((x.()))..,s(()))) The rest of the proof closely resembles the proof of Theorem
(x))).
Graph neural networks with constructed adjacency. One approach sometimes applied to learn- ing from sets of vectors is to define an adjacency matrix (e.g.. by thresholding distances of node feature vectors) and apply a graph neural network to the resulting graph (e.g., Wang et al. 2201), Li
et al. (2119). Using the common message passing paradigm (Gilmer et al. 2017) in this case boils to layers of the form: L(X), = (x LjEN, 6 xz)) Φb 2 jEin) [2 zy ) +z)), where o, e are MLPs, N; is the index set of neighbors of node i, and (ax; my) is the indicator function for the edge (i, If N can be approximated by a continuous function, which is the case at least in the L2 sense for finite set of vectors, then since L is also equivariant it follows from Theorem T that such network can be approximated (again, at least in L2 norm) arbitrarily well by any universal equivariant network such as PointNetST or DeepSets.
We tested the ability of a DeepSets model with varying depth and width to approximate a single graph convolution layer. We found that DeepSets model with small number of layers can approximate graph convolution layer reasonably well. For details see Appendix A
5 EXPERIMENTS
We conducted experiments in order to validate our theoretical observations. We compared the results of several equivariant models, as well as baseline (full) MLP, on three equivariant learning tasks: a classification task (knapsack) and two regression tasks (squared norm and Fiedler eigen vector). For all tasks we compare results of 7 different models: DeepSets, PointNet, PointNetSeg, PointNetST. PointNerQT and GraphNet. PointNerQT is PointNet with a single quadratic equivariant transmission layer as defined in Appendix [ GraphNet is similar to the graph convolution network in Kipf & Welling 2016) and is defined explicitly in Appendix B We generated the adjacency matrices for GraphNet by taking 10 nearest neighbors of each set element. In all experiments we used network 6 depth and varying width, fixed across all layers.
of the form Equation 7 with
Equivariant classification. For classification, chose to learn the multidimensional knapsack problem, which is known to be NP-hard. We are given a set of 4-vectors, represented by X e R2x4 and our goal is to learn the equivariant classification function f Rnxx + {0, 1)" defined by the following optimization problem:
f(X) arg max
s.t.
2if24 S Wjj [=1
j = 2,3,4
24 E {0,
i [n]]
Intuitively, given set of vectors X E Rxx4 (X)is = æzj. where each row represents an element in a set, our goal is find a subset maximizing the value while satisfying budget constraints. The first column of X defines the value of each element, and the three other columns the costs.
To evaluate the success of trained model we record the percentage of sets for which the predicted subset is such that all the budget constrains are satisfied and the value is within 10% of the optimal value. Appendix C we detail how we generated this dataset.
Equivariant regression. f(x) -
The first equivariant function we considered for regression is the function
(X.,
1)2 Hanin Sellke (017)) showed this function cannot be approxi-
"The code can be found at http:///.....cc.oooiiioll//o//le Netwokks

---

Published as a conference paper at ICLR 2020
Knapsack test
Fiodler teat
Σvex (w 23 test
040
0000
250
140
Knapsack train
Fledler train
Σ ze (1)
train
140
100
1.501
0.011
Figure 2: Classification and regression tasks with permutation equivariant models. All the universal permutation equivariant models perform similarly, while the equivariant non-universal PointNet demonstrates reduced performace consistently; MLP baseline (with the same number of parameters as the equivariant models) performs poorly.
mated by MLPs small width. We drew 10k training examples and 1k test examples i.i.d. from a N/3, 1) distribution (per entry of X).
The second equivariant function considered is defined point clouds X E R2 For each point cloud we computed a graph by connecting every point to its 10 nearest neighbors. We then computed the absolute value of the first non trivial eigenvector of the graph Laplacian. We used the ModelNet dataset (Wu et al., 2015) which contains ~ 9k training meshes and ~ 2k test meshes. The point clouds are generated by randomly sampling 512 points from each mesh.
Result summary. Figure 2 summarizes train and test accuracy of the 6 models after training (training details in Appendix C as function of the network width w. We have tested 15 w values
cquidistant in [5, nkaa].
As can be seen in the graphs, in all three datasets the equivariant universal models (PointNetST. PointNeiQT DeepSets, PointNetSeg) achieved comparable accuracy. PointNet, which is not equivariant universal, consistently achieved inferior performance compared to the universal models, as expected by the theory developed in this paper. The -quiiirivar MLP, although universal, used the same width (i.e., same number of parameters) as the equivariant models and was able to over-fit only on one train set (the quadratic function); performance on the test sets was inferior by large margin to the equivariant models. We also note that in general the GraphNet model achieved comparable results to the equivariant universal models but was still outperformed by the DeepSets model.
An interesting point is that although the width used in the experiments much smaller than the bound kout + kin + (m+tkx) established by Theorem the universal models are still able to learn kin
well the functions we tested on. This raises the question of the tightness of this bound, which we leave to future work.
CONCLUSIONS
In this paper we analyze several set equivariant neural networks and compare their approximation power. We show that while vanilla PointNet (Qi al. 2017) is not equivariant universal, adding a single linear transmission layer makes it equivariant universal. Our proof strategy is based on a characterization of polynomial equivariant functions. As corollary we show that the DeepSets model
8

---

Published as a conference paper at ICLR 2020
Zaheerr et al. 2017) and PointNetSeg (Qi et al. 2017) equivariant universal. Experimentally. tested the different models on several classification and regression tasks finding that adding a single linear transmitiigg layer to PointNet makes significant positive impact performance.
7
ACKNOWLEDGEMENTS
This research supported in part by the European Research Council (ERC Consolidator Grant, LiftMatch 771136) and the Israel Science Foundation (Grant No. 1830/17).
REFERENCES
Emmanuel Briand. When is the algebra of multisymmetric polynomials generated by the elementary multisymmetric polynomials. Beitrge zur Algebra und Geometrie, 45, 01 2004.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. CoRR, 2017.
Martin Golubitsky and lan Stewart. The symmetry perspective. 2002.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. CoRR, ftbs/1710.11278 2017.
11278
Kurt Hornik. Approximation capabilities multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. arXiv preprint arXiv:1905.0494: 2019.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 141.6694 2014.
Thomas Kipf and Max Welling. Semi- semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
Guohao Li, Matthias Mller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In The IEEE International Conference Computer Vision (ICCV), 2019.
Haggai Maron, Heli Ken-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. CoRR, abs/1905. 1136,, 2019. URL http::/ http//iiiivv..///i//eee httpp/////aaxvv.ooo///////////// wttp://gg............. 11136
Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA, 1990. ISBN 0-471-92420-
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 652-660, 2017.
David Rydh. minimal set of generators for the ring of multisymmetric functions. In Annales de l'institut Fourier, volume 57, pp. 1741-1769, 2007.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint arXiv: 1903.01999 2019.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, 2017.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph for learning point clouds. ACM Transactions Graphies (TOG), 2019.

---

Published as a conference paper at ICLR 2020
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arXiv preprint arXiv: 10306 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp- 3391-3401, 2017.
A APPROXIMATING GRAPH CONVOLUTION LAYER WITH DEEPSETS
To test the ability of equivariant universal model approximate graph convolution layer, conducted an experiment where we applied a single graph convolution layer (see Appendix for full description of the graph convolution layers used in this paper) with 3 in features and 10 out features. We constructed knn graph by taking 10 neighbors. We sampled 1000 examples in I 100x3 ii.d from (22, 1) distribution (per entry of X). The results are summarized in Figure regressed to the output of graph convolution layer using the smooth L1 loss.
We
Destre2
Widdi=33
Septh
With 36
Death-4
With
-eat
besth-d
wdth-173
Desth-p
widh-132
302
125
150
200
apocts
agochs
Figure 3: Using DeepSets regress to single graph convolution layer. In the left image we varied the depth and took a constant width of 200. In the right we varied the width and took fixed depth of 6 layers. The y axes are log scale, Note that even layer DeepSets can approximate graph convolution layer up to an error of 0.01.
B DESCRIPTION OF LAYERS
B.1 QUADRATIC LAYER
One potential application of Theorem is augmenting equivariant neural network (Equation 7 with equivariant polynomial layers P pank - Raxl some maximal degree This can be done
in the following way: look for all solutions a, 31, . N so that |a| + E, |3:| S
d. Any
solution to this equation will give a basis element of the form p(X) x II,
Σ x
In the paper we tested PointNetQT, an architecture that adds to PointNet a single quadratic equivariant layer. We opted use only the quadratic transmission operators: For a matrix X xgr we define L(X) Rax as follows:
L(X)= XW, 11" XW2 (11' о (11" X)W, + (X @ X)W, + (11' x) XW,
where @ is point-wise multiplication and W, Baxk
[5] are the learnable parameters.
10

---

Published as a conference paper at ICLR 2020
B.2 GRAPH CONVOLUTION LAYER
We implement graph convolution layers as follows
L(X) = B + XW, + 1c
with W1. W2, e learnable parameters. The matrix B is defined as in Kipf & Welling (2016) from the knn graph of the set. B D AD- where D is the degree matrix of the graph and the adjacency matrix of the graph with added self-connections.
C IMPLEMENTATION DETAILS
Knapsack data generation. We constructed dataset of 10k training examples and 1k test exam- ples consisting of 50 4 matrices. We took w) 100, w2 = 80, Wig = 50. To generate X E R50x4 we draw an integer uniformly at random between and 100 and randomly choose 50 integers between 1 as the first column of X. We also randomly chose an integer between and 25 and then randomly chose 150 integers in that range as the three last columns of X. The labels for each input were computed by standard dynamic programming approach, see Martello & Toth (1990).
Optimization. We implemented the experiments in Pytorch Paszke et al. (017)) with the Adam Kingma & Ba (2014) optimizer for learning. For the classification used the cross entropy loss and trained for 150 epochs with learning rate 0.001, learning rate decay of 0.5 every 100 epochs and batch size 32. For the quadratic function regression
trained for 150 epochs with leaning rate of 0.001, learning rate decay 0.1 every 50 epochs and batch size 64; for the regression to the leading eigen vector we trained for 50 epochs with leaning rate of 0.001 and batch size 32. To regress the output of a single graph convolution layer we trained for 200 epochs with leaning rate of 0,001 and batch size 32.


Reviews:
[{"review_id": "rke3Frfx5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "TLDR: The function these deep set networks can approximate is too limited to call these networks universal equivariant set networks. Authors should scope the paper to the specific function family these networks can approximate. No baseline comparison with GraphNets.\n\n\n\nThe paper proposes theoretical analysis on a set of networks that process features independently through MLPs + global aggregation operations. However, the function of interest is limited to a small family of affine equivariant transformations.\n\nA more general function is\n\n\\begin{equation}\nP(X)_i = Ax_i + \\sum_{j \\in N(x_i, X)} B_{(x_j, x_i)} x_j + c\n\\end{equation}\n\nwhere $N(x_i, X)$ is the set of index of neighbors within the set $X$. It is trivial to show that this function is permutation equivariant.\n\nThen, can the function family the authors used in the paper approximate this function? No.\nCan the proposed permutation equivariant function represent all function the authors used in the paper? Yes.\n\n1) If $B=0$, then the proposed function becomes MLP.\n2) If $A=0, N(x_i, X) = [n]$ and $B_{(x_j, x_i)} \\leftarrow B$, then this is $\\mathbf{1}\\mathbf{1}^TXB$, the global aggregation function.\n\nAlso, this is the actual function that a lot of people are interested in. Let me go over few more examples.\n\n3) If $N(x_i, X) = $adjacency on a graph and $B_{(x_j, x_i)} \\leftarrow B$, then this is a graph neural network \"convolution\" (it is not a convolution)\nExample adjacency $N(x_i, X) = \\{j \\;| \\; \\|x_i - x_j\\|_p < \\delta, x_j \\in X\\}$.\n\\begin{equation}\n\\text{GraphOp}(X)_i = Ax_i + \\sum_{j \\in \\{j \\;| \\; \\|x_i - x_j\\|_p < \\delta, x_j \\in X\\}} Bx_j + c\n\\end{equation}\n\n4) If $x_i = [r,g,b,u,v]$ where $[r,g,b]$ is the color, $[u,v]$ is the pixel coordinate and $N(x_i, X) =$ pixel neighbors within some kernel size, $B(x_j, x_i)$ to be the block diagonal matrix only for the first three dimensions and 0 for the rest, then this is the 2D convolution.\n\n\nAgain, the above function is a more general permutation equivariant function that can represent: a graph neural network layer, a convolution, MLP, global pooling and is one of the most widely used functions in the ML community, not MLP + global aggregation.\n\n\nRegarding the experiment metrics and plots:\n\nOn the Knapsack test, the metric of interest is not the accuracy of individual prediction. Rather, whether the network has successfully predicted the optimal solution, or how close the prediction is to the solution.\nFor example: success rate within the epsilon radius of the optimal solution while satisfying all the constraints. Fail otherwise. If these networks can truly solve these problems, authors should report the success rate while varying the threshold, not individual accuracy of the items which can be arbitrarily high by violating constraints.\n\nAlso, the authors should compare with few more graphnet + transmission layer (GraphNetST) baselines with the graph layers: $P(X)_i = Ax_i + \\sum_{j \\in N(x_i, X)} Bx_j + c$ and the same single transmission layer $\\mathbf{1}\\mathbf{1}^TXB$ in PointNetST.\nPointNet is a specialization of graphnets and GraphNetST should be added as a baseline with reasonable adjacency.\n\nAlso experiment figures are extremely compact. Try using log scale or other lines to make the gaps wider.\n\n\n\n\n\n\nMinor\n\nI am quite confused with the name PointNetST. Authors claim adding one layer of DeepSet layer to a PointNet becomes PointNetST, but I see this as a special DeepSet with a single transmission layer. The convention is B -> B', not A + B -> A'. In this case, A: PointNet, B: DeepSet\n\nLemma 3 is too trivial.\n\nThe paper is not very self contained. Spare few lines of equations to define what are DeepSets and PointNetSeg in the paper and point out the difference since these networks are used throughout the paper extensively without proper mathematical definition.\n\nP.2 power sum multi-symmetric polynomials. \"For a vector $x \\in R^K$ and a multi-index ...\" I think it was moved out of the next paragraph since  the same $x$ is defined again as $x \\in R^n$ again in the next sentence.\nAlso, try using the consistent dimension for x throughout the paper, it confuses the reader.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SyxwgLc0tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents proof that the DeepSets and a variant of PointNet are universal approximators for permutation equivariant functions. The proof uses an expression for equivariant polynomials and the universality of MLP. It then shows that the proposed expression in terms of power-sum polynomials can be constructed in PointNet using a minimal modification to the architecture, or using DeepSets, therefore proving the universality of such deep models. \n\nThe results of this paper are important. In terms of presentation, the notation and statement of theorems are precise, however, the presentation is rather dry, and I think the paper can be significantly more accessible. For example, here is an alternative and clearer route presenting the same result: one may study the simple case of having single input channel, for which the output at index \"i\" of an equivariant polynomial is written as the sum of all powers of input multiplied by a polynomial function of the corresponding power-sum. This second part is indeed what is used in the proof of the universality of the permutation invariant version of DeepSets, making the connection more visible. Generalizing this to the multi-channel input as the next step could make the proof more accessible. \n\nThe second issue I would like to raise is related to discussions around the non-universality of the vanilla PointNet model. Given the fact that it applies the same MLP independently to individual set members, it is obvious that it is not universal equivariant (for example, consider a function that performs a fixed permutation to its input), and I fail to see why the paper goes into the trouble of having theorems and experiments just to demonstrate this point. If there were any other objectives beyond this in the experiments could you please clarify? \n\nFinally, could you give a more accurate citation (chapter-page number) for the single-channel version of Theorem 2.? \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylapLxoKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*CAVEAT*\nI must caveat that this paper is out of my comfort zone in terms of topic, so my review below should only be taken lightly. It also explaina the brevity of my review. My apologies to the authors and other reviewers.\n\n*Paper summary*\n\nThe authors design a set architecture, which is equivariant to permutations on the input. They show the simplest such set architecture, which preserves equivariance, while being a universal approximator. Nicely this architecture relies on a correction to PointNet, called PointNetST, which they show is not equivariant universal. Furthermore, they run experiments on a few toy examples demonstrating that their system performs well.\n\n*Paper decision*\n\nI have decided to give this paper a weak accept, since it contains both theory and nice experiments. To change to a firm accept, I think the paper needs some changes in written style mainly, to make it friendlier to newcomers to the area, which can easily be implemented in the camera ready stage of paper preparation. For instance, the omission of a results discussion section or a conclusion are clearly not reader friendly.\n\n*Supporting arguments*\n\n- The paper is written clearly. This said, it requires a great deal of effort to follow the maths if you are not already fluent in a lot of the ideas used in the paper (this includes myself). \n- I think the structure of the paper is fine for this sort of work. Perhaps at the beginning it would be more useful to spend more time on a roadmap of the results presented in the paper and to explain the exact significance of why the reader should want to continue reading.\n- I think the selection of experiments is nice, containing both regression and classification. What would have been nicer would be to perform some sort of ablation study, where the authors studied how the representational capacity of the network changed as a result of them introducing the universal linear transmission layer.\n- A direct theoretical and experimental comparison between PointNet and PointNetST would have been useful for me to understand the impact of the change that the authors introduce.\n\n*Questions/notes for the authors*\n\n- Please answer my concerns in the support arguments\n- Where is the conclusion section?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that DeepSets and PointNet, which are known to be universal for approximating functions, are also universal for approximating equivariant set functions. Reviewer are in agreement that this paper is interesting and makes important contributions. However, they feel the paper could be written to be more accessible.

Based on the reviews and discussions following author response, I recommend accepting this paper. I appreciate the authors for an interesting paper and look forward to seeing it at the conference.
Decision: Accept (Poster)