On the Representation Power of Set Pooling Networks
Authors: Christian Bueno
Alan Hylton
Venue: NeurIPS 2021 Poster (2021)
Keywords: universal approximation
point clouds
sets
topology
functional analysis
non-euclidean
invariance

Abstract: Point clouds and sets are input data-types which pose unique problems to deep learning. Since sets can have variable cardinality and are unchanged by permutation, the input space for these problems naturally form infinite-dimensional non-Euclidean spaces. Despite these mathematical difficulties, PointNet (Qi et al. 2017) and Deep Sets (Zaheer et al. 2017) introduced foundational neural network architectures to address these problems. In this paper we present a unified framework to study the expressive power of such networks as well as their extensions beyond point clouds (partially addressing a conjecture on the extendibility of DeepSets along the way). To this end, we demonstrate the crucial role that the Hausdorff and Wasserstein metrics play and prove new cardinality-agnostic universality results to characterize exactly which functions can be approximated by these models. In particular, these results imply that PointNet generally cannot approximate averages of continuous functions over sets (e.g. center-of-mass or higher moments) implying that DeepSets is strictly more expressive than PointNet in the constant cardinality setting. Moreover, we obtain explicit lower-bounds on the approximation error and present a simple method to produce arbitrarily many examples of this failure-mode. Counterintuitively, we also prove that in the unbounded cardinality setting that any function which can be uniformly approximated by both PointNet and normalized-DeepSets must be constant. Finally, we also prove theorems on the Lipschitz properties of PointNet and normalized-DeepSets which shed insight into exploitable inductive bias in these networks.

On the Representation Power of Set Pooling Networks
Christian Bucno
Alan G. Hylton
Department of Mathematics University of California, Santa Barbara
Space Communications and Navigation
NASA Glenn Research Center Cleveland, OH 44135, USA alan. g hyltonenasaa gov
Santa Barbara. CA 93106 christianbueeno@ucss.. edu
Abstract
Point clouds and sets are input data-types which pose unique problems to deep learn- ing. Since sets can have variable cardinality and are unchanged by permutation, the input space for these problems naturally form infinite-dimensionn spaces. Despite these mathematical difficulties, PointNer [18] and Deep Sets [31] introduced foundational neural network architectures to address these problems. this paper we present a unified framework study the expressive power of such networks as well as their extensions beyond point clouds (partially addressing a conjecture on extendibility of DeepSets along the way). To this end, we demonstrate the crucial role that the Hausdorff and Wasserstein metrics play and prove new cardinality-agnossi functions can be approximated by these models. In particular, these results imply that PointNet generally cannot approximate averages of continuous functions over sets (c.g. center-of- mass or higher moments) implying that DeepSets is strietly more expressive than PointNet in the constant cardinality setting. Moreover, we ob- tain explicit lower- bounds the approximation error and present simple method to produce arbitrarily many examples of this failure-mode. Counterintuitively, we also prove that in the unbounded cardinality setting that any function which be uniformly approximated by both PointNet and hormalized-DeepSeet must be constant. Finally, we also prove theorems on the Lipschitz properties of PointNet and normalized-DeepSeee which shed insight into exploitable inductive bias in these networks.
non-Euclidean
universality results to characterize exactly which
Introduction
The architectures introduced in PointNet [18] and Deep Sets [31] are foundational contributions the direct analysis of point clouds and sets via deep learning. These works provided two of the earliest such methods and continue to be of theoretical interest since both provide simple architectures which are permutation-invarian by construction. In addition to this, a single invariant model of either approach can handle sets of differing sizes and can theoretically scale any cardinality with enough computational resources.
In either case the procedure to process point cloud A in R" is simply as follows: (1) apply network &o to each element of A, (2) apply permutation-invarian pooling operation to aggregate these soint-fcatures into global feature for A (i.c. max-pooling for PointNet, sum-pooling for DeepSets), and lastly (3) pass this global feature to the second network to obtain the final output. For general PointNet and DeepSets sermutationiivvarint models, this be concisely expressed mathematically as
PPPintNet (A)= (maxx(() and DeepSeets (A) aEd
(Ev(aa)
LaEA
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

respectively. Depending on the output layer of p this can be used for either set-regression or set- classification. Note that arbitrarily large point clouds can be passed through and that the permutation- invariance of the max/sum-pooliing operations ensure that rearrangement of the elements of A do not alter the output.
Importandly each of these prior works provide their own universal approximation theorems (UATs) to support the empirical success of their methods. In this work we prove substantial extensions of these results motivated by the following points:
Unified Approach and Minimal Universality: The pre-existing universality results use very differ- ent approaches. Additionally, these results do not explore the minimum architecture requirements needed for universality. In this paper we present proof method that applies more than one model and provides universal "shallow" examples.
The universality results in [18, 31] both assume that the cardinality of the inputs are fixed to some size n and thus do not make use of the cardinality-agnosti nature of these models. This gap is of worthy of investigation because (1) real-world point cloud datasets can have heterogencous cloud sizes and (2) it may happen that the deployed model encounters point clouds with cardinalities that did not exist in the training data (e.g. if better sensors become available). It is not immediately clear whether one should expect these model classes to have enough power to universally approximate the functions of interest when allowing for such changes in set size.
Cardinality Limitations:
One approach for learning with mesh inputs is to sample the mesh and feed the resulting point cloud into suitable neural network [18, 19, 9J. Although PointNet and DeepSets can readily accept samples of any size and via any sampling method, the computation graph at the input layers necessarily widens the point clouds get larger. Understanding the expressiveness and consistency as sampling cardinality (and hence input-laycr size) grows to infinity may provide thcoretical insight on this approach to learning from meshes. Models such as Neural ODEs [6] and Neural Tangent Kernels [11] have benefited from similar considerations (infinite depth and infinite hidden-layer width limits respectively).
Infinite Input-Layer Width Limit:
DeepSets Extension Conjecture: was conjectured in the supplementary materials of [31] (below their proof Theorem 9) that the DeepSets invariant model should be extendable to input sets of countably infinite or even uncountably infinite size and retain universality in that setting. However, they note that there are fundamental topological obstructions to answering this question. We provide partial resolutions to this conjecture by showing that a change in the pooling function allows for inputs beyond finite sets (Sec. 3.4).
Comparison of Representational Power: In this work we slightly modify the permutation innaaration-nnvariant DeepSets model by use of average -oooling instead of sum aun-pooling. The only change is re- re-scaling by the set size before applying p so we call this version pormalized-DeepSeer We find that:
PointNet (hormalized-DeepSSets) DeepSets) uniformly approximate only the functions which uniformly continuous with respect to the Hausdorff (Wasserstein) metric (Theorem 3.4).
Only the constant functions be simultaneously uniformly approximated by both PointNet and normalized- DeepSSts when input sets are allowed to be arbitrarily large (Theorem 4.1). Even when cardinality is fixed to size k there is substantial difference in approximation power. In particular, PointNet cannot uniformly approximate averages of continuous func- tions over sets such as the center-of-mass or higher moments for k > We prove an explicit сттor lower bound for Icarnability of these functions by PointNet and provide a simple method for generating examples of problematic inputs for this failure-mode (Theorem 4.2).
Lipschitz Properties and Inductive Bias. In this work also show that PointNet and normalized-
DeepSets are Lipschitz with respect to the Hausdorff and 1- W-Wasserstein metrics (Theorem 3.7). quantitative generalization of the qualitative stability theorem in [18].
This result be Moreover, the Lipschitz-ness of these models suggest an interpretable inductive bias which we exploit in the experiments in Sec. 5.
Related work. Besides permutation-invaaian networks, there also exists permutation-equivariiai networks which have the property that a permutation of the inputs results in a corresponding permu- lation of the output. In addition to the invariant PointNet model in [18] and the invariant DeepSets model in [31], equivariant models are also introduced. Though these equivariant networks are also

---

commonly referred to as PointNet and DeepSets networks, they are fundamentally different and are in general not permutation-invarian. In this paper, we will only consider the invariant models.
After the introduction of PointNet and DeepSets, other deep learning approaches for sets and point clouds quickly appeared. These include hierarchical variants such as PointNet++ [19] and attention- based models such as Set Transformer
[13]. Models which were additionally equivariant to 3D rigid motions were also developed such as the hicrarchical Tensor Field Networks [24] and the attention- based (rrt)))Taaffommet [8]. There is also the closely related field of graph neural networks (GNNs) which shares many similar difficulties and questions as do neural networks for sets. See [9] and [27] for comprehensive surveys on deep learning methods for point clouds and graphs respectively.
Whether a wwtpuuttttiooonviiaann function F can be exactly represented by sun-decomposition - i.e.
whether (AA) = ,(> a voa)) for some p and yp has been addressed by [31, 26, 28] with positive and negative results depending on whether the point clouds come from a countable or uncountable universe. In particular, [31] proves that sum-decomposition is possible when the sets are drawn from countable universe and [26] shows that there are continuous permutation-invariann functions that are not sum-dccomposable when the latent space is too small (and similarly for max cccoopooooosiiin
Approximation results for other permutation- permutation-equuiaiiinnnnnntntt equivariant/nnvarian models have also been presented in the literature. In [22] and [15] special kinds of equivariant models are introduced and proofs of universality are provided. In [29] polynomial-boe based G-invariant networks are introduced for which fixed-cardinality universal approximation results are proved via the Hilbert's finiteness theorems from classical invariant theory.
theorem and
Lastly, there has been much closely related work on the expressiveness of GNNs. GNN universality results are proved in [12, 1], the degree to which GNNs can generalize graphs of varying sizes is investigated in [30], and the relative power of max/mcan/suum-pan pooliin in GNNs is studied in [28].
2
Preliminaries
Our focus will be on understanding which functions can be uniformly approximated by architectures like that of PointNet and Deep Sets. Although tasks such as point cloud segmentation or point cloud generation are not directly addressed, some results may apply depending on architecture details. All presented theorems have proofs in the paper's main body or in the supplementary materials.
2.1 Set Pooling Networks: PointNet, DeepSets, & Hermaalzee-DeepSSee
In addition to the max-pooling of PointNet and sum-pooling of DeepSets, we also consider average- pooling. For A C R= finite point cloud, the network archilectures are respectively given by
Wmax (A) p
( max p(a)) aEA
Vaav (A)= =
1 A
Σ p(a)) acA
Suum (A) = P Σ v(a)) aEA
Here 90 : RT + IRm creates features for each point in A which gets symmetrically pooled and then passed to p Rm + Xe (where max is the component-wis maximum). For simplicity, we will usually take & = 1 and in practice we want both and & to be neural networks or some other parametrized model with learnable parameters. Once again, note that because of the pooling operation before p. the output will not depend on the ordering of points in the point cloud, and the size of the point cloud is not an issue because the pooling operations scale to arbitrary finite cardinalities. In general, we call these and any other network of the form p(pool A (a)) set pooling network.
It may first seem that the of average-pooling instead of sum-pooling makes no difference. Indeed, this is true when cloud cardinality is fixed since then the |A| factor is constant and can be absorbed into p. However, when cardinality is free to change this factor can no longer be absorbed and makes difference. To see this, imagine a finer and finer uniform sampling of the unit circle with Pp > O everywhere. If we use average- poolling the inside of will converge to the average value of so on the circle, but will explode if we use aum-ooolin. This good behavior in the large cardinality limit will be critical later on.
It will be useful introduce some abstractions and simplifying notation. Let F(?) denote the set of all nonempty finite subsets of a set S (i.e. point clouds in Ω), FFS(( the set of nonempty subsets of
3

---

size I k. and Fk()) the set of k-point subsets. Now consider a set Ω function f Ωt - IR", and define max ave,, s : F(22 -> RR" as the set-functions given by component-wise pooling
maxx (A) = max f fa), (Ae =
1 [AI
Σ f(a), aEA
suny (A) = Σ{(a)
a
a
With these conventions, p o maxp; P o sump, and p ave will be the general form of what we call PointNet, DeepSets, and normalized- DeeepSSss architectures respectively. The case of p sum will prove difficult to treat in the same manner as the others and so will get a separate treatment (Sec. 3.4).
2.2 Function Spaces and Uniform Approximation
Here we review some standard functional analysis. For more detailed background see [21, 20, 3].
Let C(X, X') and (M, .M' denote respectively the set of all continuous functions from topological space X to topological space X' and the set of all uniformly continuous functions from metric space (M, d) to metric space (M' d"). Unless otherwise specificd we always assume that R" carries the standard Euclidean norm ||-|| and for simplicity we let ((X) == C(X,R) and (M) == (M,, R).
For any set A, we define (A4 to be the set of all IR-valued bounded functions on A. With this we can define the bounded function spaces (x) = C(X) n (X) and (MM (MM) n (nB(B)). When X is compact or M is precompact (i.e. has compact metric completion) then we have C(X) Co (X) and LMMM) = Up (M). We can endow all of these R-valued functions spaces with the topology of uniform convergence by equipping them with the supremum norm' given by [I supae lf)). In particular, the bounded families Us (M), (X),, ((A) are all Banach spaces with this norm.
The uniform closure of family of R-vauued functions A is the set of all functions which can be uniformly approximated via members of A, i.c. the topological closure with respect to III-II. One of our key focuses will be determining the uniform closure of families of set pooling networks as this tells us exactly which functions can and can't be approximated.
Lastly, given an injective map i: A >> X, we say that A - R (uniquely) continuously extends to X if there is (unique) 인 E C(X) such that & i = yp. We say family of functions A on A (uniquely) continuously extends to X if every ş E A (uniquely) continuously extends to X. One nice property of uniformly continuous functions on a metric space (M, d) is that they uniquely continuously extend to the metric completion (M, d) i.e ((M) uniquely continuously extends to M.
2.3 Topologies and Metries for Point Clouds
From now on we will assume (S2, d) is a compact metric space unless otherwise stated and when
Ω C R" it will be a compact set equipped with the Euclidean metric (c.g. [0, 1]m). Let K(()) denote the set of all compact subsets of Ω and ((2)) denote the set of all Borel probability measures on Ω. The Hausdorff metric du [17, 16] is natural metric for KC( and 1-Wasserstein metric dw [25] (also called the Earth-mover distance) is a natural metric for P(2). With these metrics, K(() and
P(2) become compact metric spaces of their own whenever (S, d) is compact [10, 25). From now on we will assume these two spaces are always equipped with the aforementioned metrics.
We also brielly mention (Q), the Banach space of finite signed regular Borel measures on Ω. By the Riesz-Markov theorem it is the topological dual space of C(S)). Of interest to us is that P(N) C (S2) and that the weak-* topology on P(lt) coincides with the topology induced by dw. This means that dw (pn, 14) + 0 iff ddn - f f du for all f E C(2).
Next, note that F(2) C K((2) and let ix denote the natural inclusion map. We can also define an injective map ip F(2) + P(l2) by mapping E F((2) its associated empirical measure (A) = M4 [А| EaEA A 6a E P(Ω) where 8, is the Dirac delta measure supported at a. The injective maps रا and ip allow us to induce the dæ and dw metrics on F(l)). We will denote the metrized versions by Fu (92) and Fw (92) respectively and use the same convention for the bounded
In general, III |II will not always be true norm C(X) or U(M) since there may unbounded functions.
"The topology induced on K(()) and P(2) by du and dw depends only on the topology of (2, d) and not on the choice of metric d. These topologies are called the Vietoris [16] and weak- topologies [21] respectively. Indeed, in parts of this paper we could have proceeded without metrics at all and directly used these topologies. However, the particular metrics da and dw will be necessary to prove certain results such those in Sec. 3.3.

---

cardinality spaces e.g. FF (St) and Fü (2).. Importantly, ix: and ip embed F(2)) as dense subset of (()) and P(S)) respectively. The former follows from compactness of the members of X(()) and the latter is true because you can approximate any distribution with samples (see [7, 25J for details),
For f C( define Max, : K(()) + R and Ave, P(2) + E. as the functions given by Max, (K) = maX fx) and Aver(u) = Sn du = (f
Lemma 2.1. Let (S2, d) be compact, f E C(2). Then Max, E C(K(())) and Ave, E C(((())) and Max, o ik = j and Aver o tpp a.e As a consequence, PointNet and normalized Deeesstts are uniformly continuous on (H) and (9)) respectively.
This lemma tells us that max, and ave, continuously extend to (()) and P(12) and hence PointNet and normalized-DeepSSS
must as well (since composing with the continuous & preserves continuity). Thus, we will be able analyze such architectures as continuous functions on compact metric spaces, which is mathematically much better setting than set-theoretic functions on an un-metrized F(2)..
2.4 Notation for Families of Neural Networks
In this section will introduce notation to help abstract away neural network architecture details and instead focus on classes of neural networks and the functions they can represent.
For collection A of functions from X to Y and a collection B of functions from Y to Z, we denote the set of all compositions by B o A = {f o f B, g C A]. In the case of a single function Y - Z we let o A {o) o A = {o o f A). For a collection of RR-vlued functions A, span A is the set of all linear combinations of the functions in A.
Next, let A" denote the set of all functions which can be written as f(x) = Σin (,o(w, x + bz). i.c. the set of single-hidden layer neural networks with activation a and linear scalar oulput-layer. Deeper H H-layered network classes are denoted by N where 0 = (aI..... oH) is a list of H H-many activation functions which can be deepened like so No, := Nu. == span o NT))
Next we define various classes of PointNets. Let max == span {maxy f <V* then define Amax span (r N We use the subscript 'max' to recall which pooling is used and remind ourselves that these networks take set-inputs, not vector-inputs. As before, we can inductively define deeper networks and denote them via vector-bold activations as in Amir. but we now also distinguish by the placement of 'I' whether the depth occurs before or after the pooling.
Next we do the same for normalized-Deeppett ave, + ave, = a and aaaeey = ave,f. Thus since N has no effect and so A/ar {avey f E NV). Adding a layer post-pooling yields the new family Nave :- span (T o oo which gets us new functions. Like with PointNet, we can inductively develop deeper families by deepening pre nee-pooling or post-pooling.
Let No ave := span (avez I f EW... Note that
linear space, taking the span
By Lemma 2.1 we can extend all the operations of our neural networks to K(()) and P()) a natural way. This let's us talk about about PointNet networks on K(()) and normalized-DeepSee networks on P(2). We define them analogously by replacing max, with Max, and ave, with Avey. Thus
ralr Max
-pan (T NN
Ave span (T o N
where Max / structure of N means No Ave could have been defined without the span. Here the pooling subscripts matter much more as a 'Max' subscript implies that the networks take compact sets as inputs and an 'Ave' subscript implies that the networks take probability measures as inputs.
span (Max, f E No) and Wgg = span (Ave, f E As before, the linear
For further explanation of this notation and examples it describes see Appendix C.
3 Universality Results
3.1 Topological UAT
In [14] it is proven that N with E C(R) has the universal approximation property iff' a is not polynomial. For this reason, we will say a a C(R) is 'universal' if it is non-poll non-polynomial and denote the set of all such such functions by ((R).. Using this theorem and Stone- Weierstrass we prove a UAT Stone-Weierstrass
5

---

for certain kinds of generalized neural networks an abstract compact Hausdorff space. Though we independently arrived at this theorem, we later discovered this result was essentially proven in [23] (Theorem 5.1) for a different context, However, proof is slightly different and we provide detailed proof in the supplementary materials for completeness and the benefit the reader.
Recall that a family of functions S on ? separates points if for any x + y there is an f E S so that f()) + fg).
Theorem 3.1 (Topological-UAT). Let X be a compact Hausdorff space and ((R).. IfS C C(X) separates points and contains a nonzero constant, then span(o o span S) is dense in C(X). Addi- tionally, if S also happens to be a linear subspace, then span(o c S) is dense in C(X).
3.2 Point Cloud UAT
With the following lemma, we will have met all the conditions required to use the topological-UAT on (())) and P(2)).
Lemma 3.2 (Separation Lemma). Let 52 IN be compact and E (()).. Then the set of functions SMax [Maxy E ] and SAve {Ave, f E e separate points and contain constants.
The following theorems show that one hidden layer in the inner network y and one hidden layer in the outer network p suffice to prove the universal approximation theorems for PointNet and Hemalized-DeepSeee (for further explanation see Appendix C).
Theorem 3.3. Let Ω C R be compact and a, (((R). Then Nelr and N are dense in C(A)
and CBB respectively, whenever A C K(S2) and B C P(Z)) are closed subsets.
Proof. Recall decall.Narr N
Max span {T o span SMax and A Ave span { o SAveJ. Since K(()) and P(22)
are compact metric spaces, and A and B are closed, they must be also be compact Hausdorff. By Lemma 3.2 we know SMax and SAve separale points and contain nonzero constants and so the topological-UAt (Theorem 3.1) yields the desired result.
Now we restrict this result to F(2). For f F(2) + R the following result tells that under mild hypothesis that (1) PointNets can uniformly approximate f iff f is d -u-unffrmll continuous and (2)
DormalizedDDeepSeee can uniformly approximate f iff f is dw-uniformly continuous.
Theorem 3.4 (Point-Cloud- UAT). Let Ω C R.N be compact. Ifa, (I(R), then the uniform closure of N and Nade within ((1()) is (FH({)) (nd respectively.
Proof. (()) and (St) are isometrically isomorphic to ix (F(()) and ip (F(S)) which are in turn dense in (IC()), dx) and (P(12), dw). By Lemma 2.1 we have that max and N continuously extend to KC())) and (()) as N and Ave By Thcorem 3.3 we know Nall and M are dense in C(C(S))) and ((P(S))). Finally, by Lemma A.1 we have the desired result.
It is worth noting that we could have directly used another UAT proven in [23] for neural networks on locally convex spaces [Coroolyy 5.1.2) for the universality of naturally lives within topological vector space and Ave, is always a continuous linear functional. However this result would not directly work for PointNet since K(()) lacks natural vector space structure. Hence we chose the above route for consistency of technique and to be self-contained.
DeepSets since P(2)
We now prove as corollary a refinement of the universal approximation theorems of [18] and [31], both of which applied the the case of k-point point clouds (for fixed k). In this version of the thcorem we are able to restrict the depth of the neural network to just three hidden layers. Additionally, as with the above, this result simultancously establishes which functions cannot be uniformly approximated by these architectures. The proof is essentially the same as Theorem 3.4.
Corollary 3.5. Let Q C R be compact. If o, E (RR), then the uniform closure of Natr and Nolle within B(F* (1) are ((FFF(F))))) (1)) and (F (f)) respectively.
In [23]. the motivation was to study expressiveness of neural networks on all of IR" (not just a compact subset of it) and this necessitated an extension of the classical UAT.

---

Proof. (St) and FW (12) are isometrically isomorphic to ix: (F)) and in (FF) which are in turn dense in their respective closures which we denote (2) C (({t) and GW( _ P()).
Thus by Lemma 2.1 and Theorem 3.3 we have that MM Max and W Ave are dense in C( (S)) and
(S)). Finally, by Lemma 2.1 we have the desired result.
3.3 Stability and Lipschitz Property
function f from a metric space (M1,d1) to a metric space (M2, d2) is Lipschitz if there is a constant K (called the Lipschitz constant) such that (x)), [v)) S Kdj (x, y) for all x, E M1- This is a valuable property for understanding how rapidly/ f can vary with respect to the inputs, especially in the absence of differentiiaiiityy. By refining the continuity arguments for Maxy and Avey, we can deduce the Lipschitz constant of these maps from the Lipschitz constant of f.
Lemma 3.6. Suppose (9), d) is compact and f : Ω + R is Lipschitz continuous with Lipschitz constant L. Then Max, E ((()) and Ave, E ((2)) have Lipschitz constant 2L and L.
As consequence of Lemma 3.6, we can show that whenever the activation functions are Lipschitz, the whole neural network architecture will be Lipschitz. This is particularly valuable in the variable cardinality case since derivatives with respect to cardinality do not make sense.
Theorem 3.7. Suppose & S N is compact. Then every PointNet and Sarmaalized-eeepSeee network with Lipschitz activation functions Lipschitz on FF (St) and Fw (St) respectively.
In particular, this means that for a PointNet Fmax and normalized-DeepSee Fave there exists constants Kmax and Kave so that
[|Fmax (A) Faax (B)I S (A, B), and
Fave (B)Il S d (A, B),
where the constants Kmax and Kave are determined by architectures of Fmax and Fave respectively.
One implication of this is that if one were to sample a mesh sufficiently well, and knew the Lipschitz constant of the whole soauttee/nommliied--eeeeee how big a difference could be produced in the output under two different samplings of the same object. This bound would not depend on the cardinality, but on the quality of the sample with respect to the metrics dæ and dw. This makes Theorem 3.7 something of a quantitative analogue and extension of the stability theorem for PointNet presented in Theorem 2 of [18].
network, then it would be possible to bound
Theorem 3.7 also provides us with a qualitative way to understand what these networks are most responsive to. For example, if two point clouds A and B had very large dæ (A, B) but very small dw (A, would stand to reason that PointNet would more readily be able tell them apart than normalized-Deque DeepSets. We explore this promising inductive bias further in Sec. 5.
3.4 DeepSets Conjecture and Theoretical Issues with Standard DeepSets
To use the universal approximation results developed here, it was key for the there to exists an underlying compact Hausdorff space on which to study the networks. In the case of PointNet and normalized- normalized-DeeppSett,, the compact Hausdorff space was not obvious, but we identified the appropriate extension spaces K())) and P(2) to which we could unambiguously and continuously extend the networks. This gave a partial answer to the DeepSets extension conjecture of [31] in the sense that if we replace sum-pooo num-pooling with max- max-pooling then these networks can be made to theoretically accept sets of uncountably infinite cardinality (so long they are compact i.c. members of K())).. Similarly, for sufficiently nice sets like compact smooth manifolds M S I (c.g. a sphere) one can feed the uniform probability measure μa of M to the extension of ceimalized-DeepSeeee to P(2)).
However, we were not able do this for standard DeepSets. This is because, generally speaking. there is no compact Hausdorff space to which we can continuously extend sum, for all reasonable neural networks f. This because continuous function on a compact space is necessarily a bounded function but sum, =(()) - IR is generally unbounded. To illustrate this, let Ω = [0, 1] S IR and let be a continuous function, e.g. a neural network, which is not identically zero. Then there must be a
closed interval K on which |f| > for some > O. From this we can see that sumy (A) for A C K grows arbitrarily large in absolute value as the size of A increases. Thus, in this case, every sum, except sump is unbounded on F(S2) meaning there is compact extension space.
7

---

One potential way to address this issue would be to only consider bounded non-linearities such the sigmoid or arctan the second network as a way to control the wild behavior as cloud size gets large. Even it is not immediately clear what the natural underlying compact Hausdorff space for such model would be and it may very well depend on the activation functions. Alternative tools that do not depend on compactness may be needed.
4 Limitations of PointNets and Normalized-DeepSets
Unlike the classical UAT, we cannot expect to be able to approximate all continuous functions. This is because (M) & C(M) for non-compact metric spaces M, and both (2 and Fw (S2) are non-compact when (S2, d) is an infinite compact metric space e.g. the Euclidean unit ball. Since the Point-Cloud-UAT says can only approximate the uniformly continuous functions, this will immediately impose some surprising limitations on the approximation power of PointNet and Srrmallzee-DeepSete
The following is a counter-intuitive limitation that occurs when considering arbitrarily large point clouds. Define the point cloud diameter and center-of-mass functions by Diam(A (A) = max=,ve4 d(x, y) and (A) = [ EmEa X.
Theorem 4.1. Suppose (St, d) has no isolated points. Then f F(!)) + R is continuous with respect to both du and dw iff it is constant. Thus, for Ω = [0, 1]", there is no non-constant function on F(I)) which can be uniformly upproximated by both PointNets and Sermalized-DeppSeee In particular, PointNets can uniformly approximate Diam but not Cent and normalized DeepSets Seeepissd-DeepSets approximate Cent but not Diam.
can uniformly
At high level, this dramatic disagreement in approximation power over F(l?) stems from how du and dw handle infinite cardinality limits. Both metrics allow for sequences A, E F(22) with lim |An| do which nonetheless converge to some finite A E F(2). However, they in general do not agree on what the the limiting point cloud A should be. As result, which functions count as continuous "at infinity," and hence on all of F(S2), are radically different.
While it is interesting to know that these neural networks describe dramatically different kinds of functions in the unbounded cardinality setting, in practice there is always a bound due to computational limitations. Nevertheless, the above result sheds some light on the differences between PointNet and normalized-DeeppS in the limit of large cloud size. The next results show that under mild assumptions, and even when we bound point cloud cardinality, PointNet still cannot uniformly approximate many interesting yet simple functions.
Theorem 4.2. Suppose (St, d) is has isolated points, f E (M), and F E (LFF((()) ( R Then for every p. E a and J E (0, 1] there exists a k-point set A such that p, 9 E A C Ω and
[FA)) - uvey 2 (1-
[lf(p) - f(a)ll
2k
In terms of supremum norm, this simplifies
F - aveay 2
Diam( (S2)).
2k
In particular, this error bound inequality applies to PointNets. Thus for k 2 3 and f (0, 1]" >> R continuous, avey is uniformly approximable by PointNets on Fk (I0, 11m) iff f is constant."
This thcorem considcrably sharpens prior results on what cannot be represented by PointNet. In the proof of Theorem B.1 of [26), the fixed cardinality case for Ω = [0, 1] is considered and it is shown that sum,a (A) Σ. a cannot be exactly represented as p max, when the output dimension of f is too small. With Theorem 4.2, we can now say (without any additional assumptions on the architecture details) that PointNets cannot even approximate sum, and ave, if f is non-constant. Moreover, Theorem 4.2 can quantify how badly attempts at approximation must fail.
Notably, the function class which being missed by PointNet is very broad and contains some important functions. For example in ID, if f(x) = xm then ave, computes the m-th statistical
'Noe that obtain version of this result for sumy by dividing both sides by k.
8

---

moment. This suggest that if the learning task requires making use of statistical properties of the point cloud that PointNet may struggle or even fail (see Fig. 2 and Sec. 5). By the fixed cardinality and standard DeepSets are strictly more expressive function classes than PointNet in the fixed cardinality setting.
universality result of [31], this implies that normalized-DeepSeee
For some intuition as to why the result works, let's sketch why PointNet cannot uniformly approximate Cent. Let p F q be two points in a k-point set. Continuously moving and merging the other I: points entircly to p or entirely to q results in the same 2-clement set {p, } in a dy continuuuus way. By dи continuity, this means PointNet must output similar predictions for the center-of-men approach this 2-element set along each of these two paths. However, this will lead to conflicting estimates for the center of mass along the way. Quantifying this discrepancy leads to Theorem 4.2.
as we
Upon an initial reading of Theorem of [18] it is easy to overstep and conclude that every continuous permutation-invarian function is uniformly approximable by PointNets. However, this is not the case. Moreover, in light of Theorem 4.2 we can see that this fails to be true for a large class of functions.
5 Experiments
In all the experiments, cloud cardinality is fixed so there is no theoretical difference between DeepSets and normalized-Deephe will use the terms interchangcably.
Problematic Example Errors Predicted Error Lower Bound 5000NN
and so we
1.0
Lower Bound 0 Problematic Example Errol
Testing the Error Lower Bound. The proof of Theorem 4.2 not only establishes the enror bound but also suggest an algorithmic approach to finding point clouds that exhibit the failure of uniform approximation. This let's us produce difficult examples for the centor-of-mass prob- lem for PointNet (even if the weights change). When SZ additionally convex - e.g. the unit disk D in R²² - it becomes fairly casy to con- struct many examples of AS and A explicitly for a given PointNet model, allowing us to em- pirically verify the uniform-nore error lower bound. In the following experiment, we train simple PointNet architecture to learn the center- of-mass for 10-element point clouds in D. We train on a synthetic dataset of million point clouds (each element uniformly sampled from D) labeled with their center-of-mass. The PointNet architecture has 500K trainable parameters. The network has the form F(A) - p(maXAEA pp(a) where &p has 2-D input layer. 500-D hidden layer, and 500-D lincar oulput layer, and p has 500-D input layer, 500-D hidden layer and 2-D lincar output layer (in accordance with the Point-Cloud-UAN) The hidden layer activation functions of & and respect to the uniform norm, we opt to train with the traditional 2 loss.
0.6
0.2
0.00
0.25
0.50
0.75
1.00
1.25
3.50
1.75
2.00
Iip-oll
Figure 1: Generated problematic examples (blue) for a PointNet trained to compute the center-of- mass. The method always produces errors at least as large as the theoretical guarantee (orange).
ReLU. Since it is not possible to train with
To form our problematic examples, we pick nonzero 7 = 0.01 and two distinct points p. q E D at random. We set 8 = T [pp - q/l /4. We then sample D another times and then linearly pull those points towards p and towards g to within 8. This {p. q) adjoined with the 8 points pulled towards p and form A², and A (resp). So that the criteria in the proof of Theorem 4.2 is satisfied, we continue pulling the 8 points closer until F(Ag) and F(Ag) are within 8 of F((p. q}). We are theoretically ensured one of these two will have error larger than our bound. In Fig. we plot the the produced error vs |lp qll for the p.q E D that were used in AS, and A As predicted, all the errors for the discovered problematic examples lie above the line representing the uniform-norm error lower bound.
Lipschitz Constants and Inductive Bias. Theorem 3.7 showed us that PointNet and normalized- DeepSets are Lipschitz with respect to dæ and dw respectively. Intuitively, if ( B) is small this means that A and B have similar shupes, and if dw B) is small then this means A and B has similar distribution of points (in the statistical sense). In this experiment we create two synthetic binary classification datasets: one where the two classes have similar shape but differing distributions

---

Validation Entropy Pooling of parameters
Validation Entropy parameters
Pooling
DeepSets
05-
05
04-
Northet DeepSets
04
01
01
80
(a) Similar shape, different distributions
(b) Similar distributions, different shapes
Figure 2: Learning curves for RingLine (left) and DiscSquare (right) binary classification datasets.
(Fig. 2a). and one where the two classes have similar distribution but differeing shapes (Fig. 2b). These datasets are designed to produce advantages and disadvantages for PointNet and DeepSets.
Each dataset contains 2000 examples per class, and the per-example cardinality is kept fixed to 1500 points per cloud for both datasets. The first dataset, RingLine, comprised of 750 samples from a unit square + 750 samples from small ring or small vertical line (see right panel of Fig. 2a). The class labels are determined by whether the point cloud contains a ring or a line. Here the main difference is the internal distribution of points because the point clouds both have square shape. The second dataset, DiscSquare, is comprised of 1000 samples from small internal disc + 500 samples from an ambient large disc or large square (see right panel of Fig. 2b). The class labels are determined by whether the ambient shape was a disc or square. Here the most salient difference is the cloud shape because the interal distributions are similar (concentrated in the center, sparse elsewhere).
In each experiment we train PointNet and DeepSets correctly classify the two classes on an 80-20 train-test split. The set pooling networks involved have identical architecture except for the choice of pooling (max vs average). each experiment, we train both for 60 epochs with eross-entropy loss via SGD with learning rate 0.1 and 32 point clouds per batch.
When training RingLine, DeepSets rapidly learns how perfectly classify the the dataset, but PointNet never progresses beyond random guessing (Fig. 2a). Because PointNet is fundamentally incapable of approximating avey (Theorem 4.2), it struggles compute anything which could help it distinguish two squares with different internal distributions. Conversely, PointNet rapidly learns to perfectly classify DiseSquare, but DeepSets takes about 10x as long reach the same performance (Fig. 2b). Notably, in this case DeepSets does eventually learn how to solve the dataset, but languishes for a long while. We suspect this has to do with the fact that DeepSets has more expressive power than PointNet. This let DeepSets eventually learn the right thing to do, but it also means it had to waste many epochs trying out useless possibilities. On the DiseSquare dataset, PointNet's inability to see beyond shape became powerful inductive bias.
6 Conclusion
The failure of the perceptron learn XOR was a blow that raised the spectre of limited representation power until UATs arose to ease concerns. In this paper we studied analogous impossibility and universality questions for three kinds of set pooling networks. By carefully choosing the underlying topologies and metrics we showed how the choice of pooling function can have dramatic impact on the expressivity of these networks. future works would be valuable to further unify, systematize, and generalize this topological approach to handle all pooling functions and perhaps even other architectures such as transformers.
Acknowledgements
The first author would like to acknowledge partial support from grant DOE ASCR PhILMS DE- SC0019246, as well as support from NASA SCAN during their internships at NASA Glenn Research Center. Additional thanks to Arturo Deza, Garo Sarajian, and Steve Trettel for invaluable discussions.
10

---

References
[1] Waiss Azizian et al. Expressive power invariant and equivariant graph neural networks. In International Conference Learning Representations, 2020.
[2] Michael Fielding Barnsley. Superfractals. Cambridge University Press, 2006.
[3] Vladimir Bogachew, Oleg Georgievich Smolyanov, and VI Sobolev. Topological vector spaces and their applications. Springer, 2017.
[4] Christian Bueno. Universal Approximation for Neural Nets Sets. PhD thesis, University of California, Santa Barbara, 2021.
[5] Christian Bueno and Alan G. Hylton. Limitations deep learning on point clouds. NeurIPS Sets & Partitions Workshop, 2019.
[6] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. arXiv preprint arXiv: 180,666666,36 2018.
[7] Nicolas Fournier and Amaud Guillin. On the ratc of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, 1627344)707-738, 2015.
[8] Fabian B Fuchs, Daniel E Worrall, Volker Fischer, and Max Welling. (rn-transformmrs: 3d roto-translation equivariant attention networks. arXiv preprint arXiv:2006. 10503, 2020.
[9] Yulan Guo, Hanyun Wang, Qingyong Hu, Hao Liu, Li Liu, and Mohammed Bennamoun. Deep learning for 3d point clouds: survey. IEEE transactions on pattern analysis and machine intelligence, 2020.
[10] Jeff Henrikson. Completeness and total boundedness of the hausdorff metric. MIT Undergradu- ate Journal of Mathematics, 1(69-80):10, 1999.
[11] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint I 07572, 2018.
[12] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32:7092-7101, 2019. 2019.
[13] Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention- based permutation-invan International Conference Machine Learning, pages 3744 3753. PMLR, 2019.
neural networks. In
[14] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 666)8861-867, 1993.
[15] Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In International Conference on Machine Learning, pages 9734-6744 PMLR, 2020.
[16] Ernest Michael. Topologies spaces of subsets. Transactions of the American Mathematical Society, 522111522-182 1951.
[17] James Raymond. Munkres. Topology. Prentice Hall, 2000.
[18] Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 652-660, 2017.
[19] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets metric space. In I. Guyon, V. Luxburg, S. Bengio, Wal- lach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5099-5108. Curran Associates, Inc., 2017.
[20] W. Rudin. Functional Analysis. International series in pure and applied mathematics. Tata McGraw-Hill, 1974.

---

[21] Walter Rudin. Real and complex analysis. Tata McGraw-hill education, 2006.
[22] Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In International Conference on Learning Representations, 2019. 2019.
[23] M.b. Stinchcombe. Neural network approximation of continuous functionals and continuous functions on compactifications. Neural Networks, 12(3):66-4777, 1999.
[24] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang. Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equiiariann neural networks for 3d point clouds. arXiv preprint arXiv:1802.08219. 2018.
[25] Cedric Villani. Optimal transport: old and new. Springer, 2009.
[26] Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Ingmar Posner, and Michael Oshorne. On the limitations of representing functions on sets. arXiv preprint
2019.
[27] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 22(1):4-24, 2020.
[28] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[29] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arXiv preprint 1804 10306, 2018
[30] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures size generalization in graph neural networks. In International Conference on Machine Learning, pages 1 11975-11986. PMLR, 2021.
[31] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 3391-3401. Curran Associates, Inc., 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] The work of theoretical nature and
difficult say exactly what impact could have
on society if any.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs can be found in main paper or in supplemental materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] Will be included with supplemental.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] The experiment was with synthetic data so was mostly a sanity check for the theorems so there was not much to describe.
12

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] The sole experiment not of nature that lends itself to emror bars. It merely checks whether every single case has an error above the theoretical prediction. A single violation of this would suggest there an error the code or proof.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] It is a deliberately lightweight experiment so this omitted.
4. If you using cxisting assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xbzPcQKdTo", "reviewer": "Reviewer_prSH", "summary": "This paper develops universal approximation theory for deep sets / pointNet architectures which consist of the composition of a deep network on a permutation invariant aggregation of embeddings (i.e. $f(x) = \\rho \\circ \\text{agg} \\circ \\phi \\circ x$ where 'agg' is sum(), max() or mean()). It was already known from the original Deep Sets paper [Zaheer et al 2017] that these architectures are universal approximators of set functions on finite and countably infinite input sets, and there exist negative results [Wagstaff et al 2019] for the uncountable case. This paper refines the story in the uncountable case: it shows that the choice of aggregation function (max or mean) defines the class of functions that can be approximated in the uncountable case, and they give lower bounds on approximation power in the finite input case.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "[Clarity] I found this paper frustrating to review because it's clear that a lot of careful work has gone into proving the results, but it is written in a way that makes their results almost impenetrable to those without a strong topology background. In many respects, I'm the perfect audience for this paper: I know the related work well, and am very interested in the approximation power of these methods, but honestly - if I was just reading this paper as a researcher (rather than a reviewer), I would have stopped at the end of page 3 (it is very clearly written up to that point). Now, that is a style choice that the authors are free to make, but I think it severely limits the potential audience of this work, and it's a shame because I think it could have been written in a way that teaches those readers who are unfamiliar with topology about how we can leverage existing results from topology in building approximation theorems. The prose in section 3.4 (which explains why it's hard to get the same results with sum pooling) is a good example of well-written, accessible text that I would have liked to see at the beginning of section 2 and section 3.\n\n[Quality / significance] My main takeaway from this paper was that Deep Sets (with average pooling instead of sum pooling) and PointNet can each uniformly approximate different classes of functions (in the uncountable case) --- so the aggregation function matters --- and this difference in approximation power remains for finite sized sets (in the case of PointNet). From the counter example functions (centre of mass & diameter of a point cloud) it's intuitive that max / mean (respectively) would be the wrong choice of aggregation function, but I was not left with a good sense of what the properties of the two classes of functions are in general. I.e., given some new problem do the properties of the respective function classes give some guidance on the choice of aggregation function (as the paper suggests when it alludes to inductive biases)?\n\nI also didn't get a good sense of the relationship between these two classes of functions. For finite sized inputs, we can smoothly vary between the two aggregation functions using a weighted sum, $\\sum_{i} \\alpha(x_i / T) x_i$, where the $ \\alpha(x_i / T)$ is the output of the softmax function with temperature $T$ (mean and max are the limits as $T$ goes to 0 and $\\infty$ respectively) --- are there analogous  weighted sums that allow us to approximate both classes of functions in the infinite case? (I am tempted to ask analogous questions about what attention-weighting schemes buy us, but it's not clear how the attention weights are even defined if you have infinitely large sets - feel free to comment if you have thoughts).\n\nOverall, I thought this was a useful contribution that was let down by it's presentation. I don't have the background to evaluate the correctness of the theoretical claims, but assuming that they are correct, I think that it deserves to be published. Still - I would strongly encourage the authors to try make the paper more broadly accessible.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are clear about the limitations of their work. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "mXrq6vvAQuO", "reviewer": "Reviewer_FQK3", "summary": "The paper studies the representation power of two prominent set-learning deep architectures: pointnet and deep sts, that differ in their pooling mechanism (max vs sum/mean). While these two architectures are universal when considering constant-size sets, their expressivity when considering sets of varying cardinalities is not yet well understood. \nThe main contribution of this paper is establishing an understanding of which function spaces can be approximated by each of these architectures when set sizes vary (Both in the unbounded and bounded set size cases).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Positive points:\n-- the paper addresses an important and real problem: in practice, in many applications, set sizes vary. The paper analyzes the most fundamental set learning architectures in this case.\nThe authors did a good job writing the paper. I especially like the introduction which discusses all the key issues and presents good motivations.  \nNegative points: \n-- I found it difficult to follow the math from the paper itself without the supp. But this is understandable considering the page limit.\n\nAdditional related literature that could be of interest to the authors:\n-- Other papers that discuss the universality of set networks. “On Universal Equivariant Set Networks”, “On Learning Sets of Symmetric Elements”.\n-- There is an ongoing effort in the graph learning community to understand expressive power with varying graph sizes which seem to be related. “Size-Invariant Graph Representations for Graph Classification Extrapolation” “from local structures to size generalization in graph neural networks”, “Universal invariant and equivariant graph neural networks” “Expressive Power of Invariant and Equivariant Graph Neural Networks” (appendix F).\nIn particular, there are universality results for high-order graph networks in the variable node set size case. Could be interesting to discuss if this can be leveraged for the set learning case in this paper.\n\nTo summarise, this paper studies an important topic in a mathematically rigorous way. I support acceptance,\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jcee7Zmg8Jw", "reviewer": "Reviewer_U3mP", "summary": "The authors prove universality results for permutation invariant networks: in particular for PointNet and 'normalized DeepSets'. The two classes of networks differ in the pooling layer: max pooling for PointNet and averaging for Normalized DeepSets.\n\nDespite their apparent similarity, the authors show that these two networks approximate a different set of functions and according to different topologies (Haussdorf vs Wasserstein).\nA second important contribution is that the paper shows uniform approximation results while allowing for varying number of inputs which can be potentially uncountable (Thm 3.4). This is novel compared to recent prior work which considered fixed input cardinality. It also requires different mathematical tools for achieving this. \n\nA third contribution comes in the form of thm 3.7 which shows these networks to be Lipschitz. Along with Thm 3.4, this allows to control the approximation error made by the network when the input signal is subsampled.\n\nFinally, the authors identify a failure case where PointNet fails to approximate a seemingly simple function 'average' (Thm 4.2 and Lemma 4.3), thus illustrating the theory from which it is reach the same conclusion as the failure case does not belong to the set of functions that can be approximated by PointNet.\n\n--------------------------------------------------------------------------\n\nUpdate: After reading all other reviews and the authors' responses, I think still think the paper might be of interest to the community and is thus worth publishing under the condition that the clarifications asked by the reviewers are taken into account.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "General comments:\n- Significance: This is a significant work as it provides a clear distinction between the approximating power of two popular set networks : PointNet and DeepSets. The results have practical consequences which can be useful to the ML community for choosing the most appropriate network architecture depending on the task.\n- Originality:  The work is original in that it treats both classes of networks using the same theoretical framework while still capturing meaningful qualitative differences between the two classes. \n- Quality: The proof technic relies on standard Stone-Weierstrass theorem as well as the UAT [6] and do not represent a significant challenge, but the results themselves are useful.\n- Clarity: This is the weakest point of the paper. The notations are often cluttered and heavy especially in section 2. \n\nDetailed comments:\nNotations: \n-Notations are defined at several places in section 2, which makes it difficult to localize where they are defined especially in a paper with heavy notations.\n-The notations seems unnecessarily complicated for a rather simple concept in particular in section 2.4. The authors should simplify or clarify and illustrate these notations using examples.\nFor instance, it is hard to parse the nuances between the different notations for sets of networks as they only differ in a particular subscript or superscript : $\\mathcal{N}^{\\sigma}$, $\\mathcal{N}^{\\sigma,\\tau}$, $\\mathcal{N}^{\\sigma,\\tau}_{Max}$, $\\mathcal{N}^{\\sigma,\\tau}_{max}$, etc.\n\nDefinitions:\nThe authors discuss two ways to build deeper networks either inductively or using 'deeper weights' (l:199), however, it is hard to relate these constructions to the notation that is introduced. In particular, the authors use the notation $\\mathcal{N}^{\\sigma,\\tau}$ where sigma and tau are either nonlinearities or a collection of nonlinearities (when written in bold). However, in the latter case (collection of nonlinearities), it not clear how the set of functions $\\mathcal{N}^{\\sigma,\\tau}$ is defined. \n\n\nIllustrative figures: \nThe authors should illustrate the importance of having an approximation result that is independent on the input dimension. While the authors mention the case of subsampling a signal at different resolutions, it might be beneficial to illustrate this on simple visual examples. In particular, this could give a better intuition for failure cases in section 4.\n \n\n\nDiscussion of related work: \nAs the authors point out, Thm 3.1 is a general known result. Can the authors explain further why the result of [11] cannot be applied for PointNet but only to normalized DeepSets?\n\n\nApproximation power of PointNet:\n\nThe phrasing in l 324 suggests that PointNet is less powerful than normalized DeepSet, however, as discussed earlier in the paper, they just approximate different sets of functions (that are not really comparable) using different topologies. In that sense, thm 4.2 which quantifies the error made by a PointNet in approximating an average $ave_f$ might be misleading. Wouldn't it be possible to obtain worst case errors for normalized deepSet using a suitable function like max_f(A)?\n\nApproximation power of standard DeepSets:\nOn section 3.4 : The authors mention that standard DeepSets are not covered by the proposed framework and provide a nice explanation for why this is the case in general. Could it be possible to express a standard DeepSets as a normalized one when the nonlinearity sigma is positively homogeneous (like ReLU)? In this case, it should be possible to absorb the normalizing constant in the weights of the second network.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cLoQuyDxTv", "reviewer": "Reviewer_K3ic", "summary": "This paper presents theoretical results on two prominent architectures for representing functions on sets, PointNet and (a normalised version of) Deep Sets (or equivalently, max-pooled functions and mean-pooled functions). The authors analyse these architectures from the perspective of appropriately-defined metrics on sets of sets, and the associated function spaces. They obtain universal approximation results which show that each architecture is capable of approximating all functions which are uniformly continuous with respect to the appropriate metric. There are also interesting results on the Lipschitz properties of the architectures and on the limitations of PointNet in particular.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "This paper is clearly a valuable, interesting and novel contribution to the theory of models for learning functions on sets. The architectures considered in this paper are of interest to a reasonably wide audience, and the results presented are novel, strong, and say interesting things about the approximation strength of these architectures. I was not able to check the details of the proofs for these results - my review assumes that the proofs are actually correct. I have seen nothing to make me doubt the mathematical competence of the authors.\n\nIn general the writing is clear and the paper is well-structured. The paper would benefit from a pass to check for grammar/punctuation/typos (e.g. the word \"different\" appears as \"different different\" on lines 42-43). The mathematics is necessarily densely presented, and would benefit from having more room for discussion/explanation - the page limit obviously limits what can be done here, but perhaps the experimental section could be moved to supplementary material to make room? I didn't find the experimental demonstration of Lemma 4.3 necessary to the narrative (though it is certainly an interesting illustration). Nevertheless, I don't have a strong opinion that this needs changing, and the mathematics was presented well given the tight constraints on space.\n\nA minor point on related work: in the introduction subsection Cardinality Limitations, the authors note a lack of previous work on variable-cardinality sets. This is partially addressed (strictly speaking in the case of multisets rather than sets) in On the Limitations of Representing Functions on Sets (Wagstaff et al 2019), which the authors cite elsewhere in this paper but don't mention at this point in the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is very mathematically focused and I don't believe it has any potential negative societal impact (except perhaps very indirectly).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "SG4bE0KO5u7", "reviewer": "Reviewer_GPE3", "summary": "This paper study the expressiveness of popular two processing models such as deepset and pointnet. This paper proves that (1) PointNet can uniformly approximate only the functions which are uniformly continuous with respect to the Hausdorff (Wasserstein) metric and (2) Only the constant functions can be simultaneously uniformly approximated by both PointNet and normalized-DeepSets when input sets are allowed to be arbitrarily large. A lower bound of PointNet to approximate the center-of-mass is proved and a toy experiment is performed to confirm this lower bound.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This is a good theoretical paper that investigates the representation power of set models when the cardinality becomes arbitrarily large. However, I am more interested in what benefit this paper can bring to practical applications.  The lower bound proved in this paper is only for center-of-mass, but in practical applications of the set, the tasks are not limited to estimate the mass center. Practitioners are also doing set compression, point cloud segmentation, classification, etc. Therefore I'd like to know how this paper could lead to the advancement of these application areas.\n\nAlso, Set Transformers [1] is the STOA model for set modeling. Can the theory introduced in this paper be applied to set transformers?\n\n[1] Set transformer: A framework for attention-based permutation-invariant neural networks, ICML, 2019", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "35Uv0_pZ98d", "reviewer": "Reviewer_4f3Q", "summary": "This paper studies the theoretical expressive power of the PointNet and (modified) DeepSets methods, on which many recent point-cloud neural-network methods are based. It proves both universality theorem under specific settings, and shows some of its theoretical limitations.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper clarity could be improved. The abstract could be re-arranged to make the paper's contributions more obvious. In all, I found the paper hard to follow.\n\nThe experiment used is an excellent way of showing the error bound from Lemma 4.3\n\nMinor remarks:\n1. Line 43 - \"different\" used twice.\n2. Line 213 - the beginning of the sentence is unclear.\n3. It will help if it will be stated for each theorem, if its proof is in the appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are addressed in the paper. The societal impact is irrelevant.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a novel theoretical understanding on what functions "normalized" DeepSets and PointNets can represent, from a topological point of view. The work is novel and provides meaningful guidance to the community about the difference between these approaches; many of the (numerous) reviewers, however, had complaints about the clarity of the presentation as well as confusions on some specific points. It will greatly benefit the paper to take these into account for the camera-ready version.
Decision: Accept (Poster)