On Universal Equivariant Set Networks
  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 \emph{equivariant} set functions. On the other hand, several
recent equivariant set architectures have been proven equivariant universal
[Sannai et al. 2019], [Keriven et al. 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 eg, 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.
