Universal Representation of Permutation-Invariant Functions on Vectors
  and Tensors
Puoya Tabaghi Yusu Wang
A main object of our study is multiset functions -- that is,
permutation-invariant functions over inputs of varying sizes. Deep Sets,
proposed by \cite{zaheer2017deep}, provides a \emph{universal representation}
for continuous multiset functions on scalars via a sum-decomposable model.
Restricting the domain of the functions to finite multisets of $D$-dimensional
vectors, Deep Sets also provides a \emph{universal approximation} that requires
a latent space dimension of $O(N^D)$ -- where $N$ is an upper bound on the size
of input multisets. In this paper, we strengthen this result by proving that
universal representation is guaranteed for continuous and discontinuous
multiset functions though a latent space dimension of $O(N^D)$. We then
introduce \emph{identifiable} multisets for which we can uniquely label their
elements using an identifier function, namely, finite-precision vectors are
identifiable. Using our analysis on identifiable multisets, we prove that a
sum-decomposable model for general continuous multiset functions only requires
a latent dimension of $2DN$. We further show that both encoder and decoder
functions of the model are continuous -- our main contribution to the existing
work which lack such a guarantee. Also this provides a significant improvement
over the aforementioned $O(N^D)$ bound which was derived for universal
representation of continuous and discontinuous multiset functions. We then
extend our results and provide special sum-decomposition structures to
universally represent permutation-invariant tensor functions on identifiable
tensors. These families of sum-decomposition models enables us to design deep
network architectures and deploy them on a variety of learning tasks on
sequences, images, and graphs.