On the Limitations of Representing Functions on Sets

By Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, Michael A. Osborne. 2019

186 citations recorded by the source corpus.

Recent work on the representation of functions on sets has considered the use of summation in a latent space to enforce permutation invariance. In particular, it has been conjectured that the dimension of this latent space may remain fixed as the cardinality of the sets under consideration increases. However, we demonstrate that the analysis leading to this conjecture requires mappings which are highly discontinuous and argue that this is only of limited practical use. Motivated by this observation, we prove that an implementation of this model via continuous mappings (as provided by e.g. neural networks or Gaussian processes) actually imposes a constraint on the dimensionality of the latent space. Practical universal function representation for set inputs can only be achieved with a latent dimension at least the size of the maximum number of input elements.

Subfields: Artificial Intelligence, Model Architectures, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Model Architectures

In Statistical Learning Theory

Citations in the corpus

Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, background): “The only settings where iDSPN + momentum performed worse than DSPN is when n × d approaches the dimensionality of the latent vector, 512 (Figure 1, right). encoder In these cases, the set runs into fundamental representation limits of set functions (Wagstaff et al., 2019).”
SE(3)-Transformers: 3D Roto-Translation Equivariant Attention Networks (2020, background): “[33] recently showed that this mechanism can theoretically approximate all permutation equivariant functions.”
A Gentle Introduction to Deep Learning for Graphs (2019, background): “unctions are the sum, mean, and product of the input elements. Under some conditions, it is possible to approximate all permutation invariant continuous functions by means of suitable transformations [140, 124]. More concretely, if the input elements belong to an uncountable space X, e.g., Rd, and t”
MetaSDF: Meta-learning Signed Distance Functions (2020, background): “This is corroborated by theoretical evidence, showing that to guarantee universality of the embedded function, the embedding requires a dimensionality of at least the number of context points [7].”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “Wagstaff et al. (2019) take up the problem for functions defined on sets.”
Everything is Connected: Graph Neural Networks (2023, background): “A natural question arises, following similar discussions over sets (Zaheer et al., 2017; Wagstaff et al., 2019): Do GNNs, as given by Equation 10, represent all of the valid permutation-equivariant functions over graphs?”
Point Transformer (2020, background): “[15] argue that reducing the latent representation to a vector of fixed length can be impractical since the cardinality of the input set is usually not considered.”
A Fair Comparison of Graph Neural Networks for Graph Classification (2019, background): “Very recently, Wagstaff et al. (2019) gave an upper bound to the number of hidden units needed to learn permutation-invariant functions over sets and multi-sets.”
On Learning Sets of Symmetric Elements (2020, background): “Wagstaff et al. (2019) provided a theoretical study on the limitations of representing functions on sets with such networks.”