On Universal Equivariant Set Networks

By Nimrod Segol, Yaron Lipman. 2019

74 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, methodology): “We denote for an arbitrary tensor A ∈ R a × b ×···× c its inﬁnity norm by For an arbitrary (cid:15) > 0 , there exists an equivariant polynomial This is a standard lemma, similar to (Yarotsky, 2018; Maron et al., 2019c; Segol & Lipman, 2020); for completeness we provide a proof in the supplementary.”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “…distributions, and in that sense they are related to the recent literature on universal approximations (as in Cybenko, 1989; Hornik, 1991) of invariant and equivariant functions (e.g., Yarotsky, 2018; Maron et al., 2019; Keriven and Peyré, 2019; Segol and Lipman, 2020; Ravanbakhsh, 2020).”
Universal Equivariant Multilayer Perceptrons (2020, background): “Universality results for some of these models exists [20, 35, 44].”
On Learning Sets of Symmetric Elements (2020, background): “The proof follows a similar line to the universality proof in (Segol & Lipman, 2019): First, we use the fact that equivariant polynomials are dense in the space of continuous equivariant functions.”