Learning Aggregation Functions

1 Introduction

The need to aggregate representations is ubiquitous in deep learning. Some recent examples include max-over-time pooling used in convolutional networks for sequence classification [Kim, 2014], average pooling of neighbors in graph convolutional networks [Kipf and Welling, 2017], maxpooling in Deep Sets [Zaheer et al., 2017], in (generalized) multi-instance learning [Tibo et al., 2020] and in GraphSAGE [Hamilton et al., 2017]. In all the above cases (with the exception of LSTM-pooling in GraphSAGE) the aggregation function is predefined, i.e., not tunable, which may be in general a disadvantage [Ilse et al., 2018]. Sum-based aggregation has been advocated based on theoretical findings showing the permutation invariant functions can be sumdecomposed [Zaheer et al., 2017; Xu et al., 2019]. However, recent results [Wagstaff et al., 2019] showed that this universal function representation guarantee requires either highly discontinuous (and thus poorly learnable) mappings, or a latent dimension equal to the maximum number of elements in the set. This suggests that learning set functions that are accurate on sets of large cardinality is difficult.

∗Equal Contribution. Contact Authors.

Inspired by previous work on learning uninorms [Melnikov and H¨ullermeier, 2016], we propose a new parametric family of aggregation functions that we call LAF, for learnable aggregation functions. A single LAF unit can approximate standard aggregators like sum, max or mean as well as model intermediate behaviours (possibly different in different areas of the space). In addition, LAF layers with multiple aggregation units can approximate higher order moments of distributions like variance, skewness or kurtosis. In contrast, other authors [Corso et al., 2020] suggest to employ a predefined library of elementary aggregators to be combined. Since LAF can represent sums, it can be seen as a smooth version of the class of functions that are shown in [Zaheer et al., 2017] to enjoy universality results in representing set functions. The hope is that being smoother, LAF is more easily learnable. Our empirical findings show that this can be actually the case, especially when asking the model to generalize over large sets. In particular, we find that:

• LAF layers can learn a wide range of aggregators (including higher-order moments) on sets of scalars without background knowledge on the nature of the aggregation task.
• LAF layers on the top of traditional layers can learn the same wide range of aggregators on sets of high dimensional vectors (MNIST images).
• LAF outperforms state-of-the-art set learning methods such as DeepSets and PNA on real-world problems involving point clouds and text concept set retrieval.
• LAF performs comparably to PNA on random graph generation tasks, outperforming several graph neural networks architectures including GAT [Veliˇckovi´c et al., 2018] and GIN [Xu et al., 2019].

2 The LAF Framework

We use x = {x1, . . . , xN} to denote finite multisets of real numbers xi ∈ R. Note that directly taking x to be a multiset, not a vector, means that there is no need to define properties like exchangeability or permutation equivariance for operations on x. An aggregation function agg is any function that returns for any multiset x of arbitrary cardinality N ∈ N a value agg(x) ∈ R.

Standard aggregation functions like mean and max can be understood as (normalized) Lp-norms. We therefore build our parametric LAF aggregator around functions of a form that generalizes Lp-norms:

La,b is invariant under the addition of zeros: La,b(x) = La,b(x ∪ 0) where 0 is a multiset of zeros of arbitrary cardinality. In order to also enable aggregations that can represent conjunctive behaviour such as min, we make symmetric use of aggregators of the multisets 1-x := {1-xi|xi ∈ x}. For La,b(1 - x) to be a well-behaved, dual version of La,b(x), the values in x need to lie in the range [0, 1]. We therefore restrict the following definition of our learnable aggregation function to sets x whose elements are in [0, 1]:

defined by tunable parameters a, . . . , h ≥ 0, and α, . . . , δ ∈ R. In cases where sets need to be aggregated whose elements are not already bounded by 0, 1, we apply a sigmoid function to the set elements prior to aggregation.

Table 1 shows how a number of important aggregation functions are special cases of LAF (for values in [0, 1]). We make repeated use of the fact that L0,1 returns the constant 1. For max and min LAF only provides an asymptotic approximation in the limit of specific function parameters (as indicated in the last column of Table 1). In most cases, the parameterization of LAF for the functions in Table 1 will not be unique. Being able to encode the powers of moments implies that e.g. the variance of x can be expressed as the difference 1/N ∑i x2i - (1/N ∑i xi)2 of two LAF aggregators.

Since LAF includes sum-aggregation, we can adapt the results of [Zaheer et al., 2017] and [Wagstaff et al., 2019] on the theoretical universality of sum-aggregation as follows.

Proposition 1. Let X ⊂ R be countable, and f a function defined on finite multisets with elements from X. Then there exist functions φ : X → [0, 1], ρ : R → R, and a parameterization of LAF, such that f(x) = ρ(LAF(φx); α, β, γ, δ, a, b, c, d), where φx is the multiset {φ(x)|x ∈ x}.

A proof in [Wagstaff et al., 2019] for a very similar proposition used a mapping from X into the reals. Our requirement that LAF inputs must be in [0, 1] requires a modification of the proof (contained in the supplementary material 1 ), which for the definition of φ relies on a randomized construction. Proposition 1 shows that we retain the theoretical universality guarantees of [Zaheer et al., 2017], while enabling a wider range of solutions based on continuous encoding and decoding functions.

LAF enables a continuum of intermediate and hybrid aggregators. In Figure 1 we plot 4 different randomly generated LAF functions over [0, 1] × [0, 1], i.e., evaluated over sets of size 2. Parameters α, . . . , γ were randomly sampled in [0, 1], b, d, f, h in {0, . . . , 5}, and a, c, e, g obtained as 1/i with i a random integer from {0, . . . , 5}. The figure illustrates the rich repertoire of aggregation functions with different qualitative behaviours already for non-extreme parameter values.

Learning the functions depicted in Table 1 can in principle be done by a single LAF unit. However, learning complex aggregation functions might require a larger number of independent units, in that the final aggregation is the result of the combination of simpler aggregations. Moreover, a LAF layer should be able to approximate the behaviour of simpler functions also when multiple units are used. Therefore, we analyzed the application of multiple LAF units to some of the known functions in Table 1. The details and the visual representation of this analysis is shown in the supplementary material. Although using only one function is sometimes sufficient to greatly approximate the target function, the error variance among different runs is quite high, indicating that the optimization sometimes fails to converge to a good set of parameters. Multiple units provide more stability while performing better than a single unit aggregation in some cases. We therefore construct the LAF architecture for the experimental section by using multiple aggregators, computing the final aggregation as a linear combination of the units aggregations. Several LAF units can be combined as shown in Figure 1, to capture different aspects of the input set, which can be in general a multiset of vectors x = {x1, . . . , xN}, where now xi ∈ Rd . Note that multiple aggregators are also used in related frameworks such as DeepSets [Zaheer et al., 2017] or Graph Neural Networks [Veliˇckovi´c et al., 2018;

1 See https://github.com/alessandro-t/laf for supplementary material and code.

Corso et al., 2020]. A module with r LAF units takes as input d-dimensional vectors and produces a vector of size r × d as output. Each LAF unit performs an elementwise aggregation of the vectors in the set such that Lk,j = LAF({xi,j , . . . , xN,j}; αk, βk, γk, δk, ak, bk, ck, dk) for k = 1, . . . , r and j = 1, . . . , d. The output vector can be then fed into the next layer.

3 RelatedWork

Several studies address the problem of aggregating data over sets. Sum-decomposition strategies have been used in [Zaheer et al., 2017] for points cloud classification and set expansion tasks and in [Santoro et al., 2017] for question answering and dynamic physical systems computation. Max, sum and average are standard aggregation functions for node neighborhoods in graph neural networks [Hamilton et al., 2017; Kipf and Welling, 2017; Xu et al., 2019; Veliˇckovi´c et al., 2018]. [Zaheer et al., 2017] first proved universal representation results for these standard aggregators when combined with learned mappings over inputs and results of the aggregation. However, [Wagstaff et al., 2019] showed that these universality results are of little practical use, as they either require highly discontinuous mappings that would be extremely difficult to learn, or a latent dimension that is at least the size of the maximum number of input elements.

Uninorms [Yager and Rybalov, 1996] are a class of aggregation functions in fuzzy logic that can behave in a conjunctive, disjunctive or averaging manner depending on a parameter called neutral element. [Melnikov and H¨ullermeier, 2016] proposed to learn fuzzy aggregators by adjusting these learnable parameters, showing promising results on combining reviewers scores on papers into an overall decision of acceptance or reject. Despite the advantage of incorporating different behaviours in one single function, uninorms present discontinuities in the regions between aggregators, making them not amenable to be utilized in fully differentiable frameworks. Furthermore the range of possible behaviours is restricted to those commonly used in the context of fuzzy-logic.

The need for considering multiple candidate aggregators is advocated in a very recent work that was developed in parallel with our framework [Corso et al., 2020]. The resulting architecture, termed Principal Neighborhood Aggregation (PNA) combines multiple standard aggregators, including most of the ones we consider in the LAF framework, adjusting their outputs with degree scalers. However, the underlying philosophy is rather different. PNA aims at learning to select the appropriate aggregator(s) from a pool of candidates, while LAF explores a continuous space of aggregators that includes standard ones as extreme cases. Our experimental evaluation shows that PNA has troubles in learning aggregators that generalize over set sizes, despite having them in the pool of candidates, likely because of the quasi-combinatorial structure of its search space. On the other hand, LAF can successfully learn even the higher moment aggregators and consistently outperforms PNA.

Closely connected, but somewhat complementary to aggregation operators are attention mechanisms [Bahdanau et al., 2015; Vaswani et al., 2017]. They have been explored to manipulate set data in [Lee et al., 2019] and in the context of multi-instance learning [Ilse et al., 2018]. Attention operates at the level of set elements, and aims at a transformation (weighting) of their representations such as to optimize a subsequent weighted sum-aggregation. Although the objectives of attention-based frameworks and LAF are different in principle, our method can be used inside attention frameworks as the aggregation layer of the learned representation. We discuss the combination of LAF and attention in Section 5 showing the advantage of using LAF.

4 Experiments

In this section, we present and discuss experimental results showing the potential of the LAF framework on both synthetic and real-world tasks. Synthetic experiments are aimed at showing the ability of LAF to learn a wide range of aggregators and its ability to generalize over set sizes (i.e., having test-set sets whose cardinality exceeds the cardinality of the training-set sets), something that alternative architectures based on predefined aggregators fail to achieve. We use DeepSets, PNA, and LSTM as representatives of these architectures. The LSTM architecture corresponds to a version of DeepSets where the aggregation function is replaced by a LSTM layer. Experiments on diverse tasks including point cloud classification, text concept set retrieval and graph properties prediction are aimed at showing the potential of the framework on real-world applications.

4.1 Scalars Aggregation

This section shows the learning capacity of the LAF framework to learn simple and complex aggregation functions where constituents of the sets are simple numerical values. In this setting we consider sets made of scalar integer values. The training set is constructed as follows: for each set, we initially sample its cardinality K from a uniform distribution taking values in {2, . . . ,M}, and then we uniformly sample K integers in {0, . . . , 9}. For the training set we use M = 10. We construct several test sets for different values of M (M = 5, 10, 15, 20, 25, 30, 35, 40, 45, 50). This implies that models need to generalize to larger set sizes. Contrarily to the training set, each test set is constructed in order to diversify the target labels it contains, so as to avoid degenerate behaviours for large set sizes (e.g., maximum constantly equal to 9). Each synthetic dataset is composed of 100,000 sets for training, 20,000 set for validating and 100,000 for testing. The number of aggregation units is set as follows. The model contains nine LAF (Equation 2) units, whose parameters {ak, . . . , hk}, k = 1, . . . , 9 are initialized according to a uniform sampling in [0, 1] as those parameters must be positive, whereas the coefficients {α, . . . , δ} are initialized with a Gaussian distribution with zero mean and standard deviation of 0.01 to cover also negative values. The positivity constraint for parameters {a, b, . . . , h} is enforced by projection during the optimization process. The remaining parameters can take on negative values. DeepSets also uses nine units: three max units, three sum units, and three mean units and PNA uses seven units: mean, max, sum, standard deviation, variance, skewness and kurtosis. Preliminary experiments showed that expanding the set of aggregators for PNA with higher order moments only leads to worse performance. Each set of integers is fed into an embedding layer (followed by a sigmoid) before performing the aggregation function. DeepSets and PNA do need an embedding layer (otherwise they would have no parameters to be tuned). Although LAF does not need an embedding layer, we used it in all models to make the comparison more uniform. The architecture details are reported in the supplementary material. We use the Mean Absolute Error (MAE) as a loss function to calculate the prediction error.

Figure 2 shows the trend of the MAE for the three methods for increasing test set sizes, for different types of target aggregators. As expected, DeepSets manages to learn the identity function and thus correctly models aggregators like sum, max and mean. Even if LAF needs to adjust its parameters in order to properly aggregate the data, its performance are competitive with those of DeepSets. When moving to more complex aggregators like inverse count, median or moments of different orders, DeepSets fails to learn the latent representation. One the other hand, the performance of LAF is very stable for growing set sizes. While having in principle at its disposal most of the target aggregators (including higher order moment) PNA badly overfits over the cardinality of sets in the training set in all cases (remember that the training set contains sets of cardinality at most 10). The reason why LAF substantially outperforms PNA on large set sizes could be explained in terms of a greater flexibility to adapt to the learnt representation. Indeed, LAF parameters can adjust the laf function to be compliant with the latent representation even if the input mapping fails to learn the identity. On the other hand, having a bunch of fixed, hard-coded aggregators, PNA needs to be able to both learn the identity mapping and select the correct aggregator among the candidates. Finally, LSTM results are generally poor when compared to the other methods, particularly in the case of the count and the sum.

4.2 MNIST Digits

We performed an additional set of experiments aiming to demonstrate the ability of LAF to learn from more complex representations of the data by plugging it into end-to-end differentiable architectures. In these experiments, we thus replaced numbers by visual representations obtained from MNIST digits. Unlike the model proposed in the previous section, here we use three dense layers for learning picture representations before performing the aggregation function. Results obtained in this way are very similar to those obtained with numerical inputs and due to space limitations we report them along with other architectural and experimental details in the supplementary material.

4.3 Point Clouds

In order to evaluate LAF on real-world dataset, we consider point cloud classification, a prototype task for set-wise prediction. Therefore, we run experimental comparisons on the ModelNet40 [Wu et al., 2015] dataset, which consists of 9,843 training and 2,468 test point clouds of objects distributed over 40 classes. The dataset is preprocessed following the same procedure described by [Zaheer et al., 2017]. We create point clouds of 100 and 1,000 three-dimensional points by adopting the point-cloud library's sampling routine developed by [Rusu and Cousins, 2011] and normalizing each set of points to have zero mean (along each axis) and unit (global) variance. We refer with P100 and P1000 to the two datasets. For all the settings, we consider the same architecture and hyper-parameters of the DeepSets permutation invariant model described by [Zaheer et al., 2017]. For LAF, we replace the original aggregation function (max) used in DeepSets with 10 LAF units, while for PNA we use the concatenation of max, min, mean, and standard deviation, as proposed by the authors. For PNA we do not consider any scaler, as the cardinalities of the sets are fixed. Results in Table 2 show that LAF produces an advantage in the lower resolution dataset (i.e., on P100), while it obtains comparable (and slightly more stable) performances in the higher resolution one (i.e., on P1000). These results suggest that having predefined aggregators is not necessarily an optimal choice in real world cases, and that the flexibility of LAF in modeling diverse aggregation functions can boost performance and stability.

4.4 Set Expansion

Following the experimental setup of DeepSets, we also considered the Set Expansion task. In this task the aim is to augment a set of objects of the same class with other similar objects, as explained in [Zaheer et al., 2017]. The model learns to predict a score for an object given a query set and decide whether to add the object to the existing set. Specifically, [Zaheer et al., 2017] consider the specific application of set expansion to text concept retrieval. The idea is to retrieve words that belong to a particular concept, giving as input set a set of words having the same concept. We employ the same model and hyper-parameters of the original publication, where we replace the sum-decomposition aggregation with LAF units for our methods and the min, max, mean, and standard deviation aggregators for PNA.

We trained our model on sets constructed from a vocabulary of different size, namely LDA-1K, LDA-3K and LDA5K. Table 3 shows the results of LAF, DeepSets and PNA on different evaluation metrics. We report the retrieval metrics recall@K, median rank and mean reciprocal rank. We also report the results on other methods the authors compared to in the original paper. More details on the other methods in the table can be found in the original publication. Briefly, Random samples a word uniformly from the vocabulary; Bayes Set [Ghahramani and Heller, 2006]; w2v-Near computes the nearest neighbors in the word2vec [Mikolov et al., 2013] space; NN-max uses a similar architecture as our DeepSets but uses max pooling to compute the set feature, as opposed to sum pooling; NN-max-con uses max pooling on set elements but concatenates this pooled representation with that of query for a final set feature; NN-sum-con is similar to NN-max-con but uses sum pooling followed by concatenation with query representation. For the sake of fairness, we have rerun DeepSets using the current implementation from the authors (indicated as DeepSet∗ in Table 3), exhibiting better results than the ones reported in the original paper. Nonetheless, LAF outperforms all other methods in most cases, especially on LDA-3K and LDA-5K.

4.5 Multi-task Graph Properties

[Corso et al., 2020] defines a benchmark consisting of 6 classical graph theory tasks on artificially generated graphs from a wide range of popular graph types like Erdos-Renyi, Barabasi-Albert or star-shaped graphs. Three of the tasks are defined for nodes, while the other three for whole graphs. The node tasks are the single-source shortest-path lengths (N1), the eccentricity (N2) and the Laplacian features (N3). The graph tasks are graph connectivity (G1), diameter (G2), and the spectral radius (G3). We compare LAF against PNA by simply replacing the original PNA aggregators and scalers with 100 LAF units (see Equation 2). Table 4 shows that albeit these datasets were designed to highlight the features of the PNA architecture, that outperforms a wide range of alternative graph neural network approaches LAF produces competitive results, outperforming state-of-the-art GNN approaches like GIN [Xu et al., 2019], GCN [Kipf and Welling, 2017] and GAT [Veliˇckovi´c et al., 2018] and even improving over PNA on spectral radius prediction. PNA∗ is the variant without scalers of PNA still proposed by [Corso et al., 2020].

5 SetTransformerWith LAF Aggregation

In this section we investigate the combination of LAF aggregation with attention mechanisms on sets as proposed in the SetTransformer framework [Lee et al., 2019]. Briefly, SetTransformer consists of an encoder and a decoder. The encoder maps a set of input vectors into a set of feature vectors by leveraging attention blocks. The decoder employs a pooling multihead attention (PMA) layer, which aggregates the set of feature vectors produced by the encoder. In the following experiment we replace PMA by a LAF layer. Inspired by one of the tasks described in [Lee et al., 2019], we propose here to approximate the average of the unique numbers in a set of MNIST images. Solving the task requires to learn a cascade of two processing steps, one that detects unique elements in a set (which can be done by the transformer encoder, as shown in the experiment by [Lee et al., 2019]) and one that aggregates the results by averaging (which LAF is supposed to do well). The set cardinalities are uniformly sampled from {2, 3, 4, 5} and each set label is calculated as the average of the unique digits contained in the set. We trained two SetTransformer models: one with PMA (ST-PMA) and the other with LAF (ST-LAF). The full implementation details are reported in the supplementary material. Quantitative and qualitative results of the evaluation are shown in Figure 3, where we report the MAE for both methods 2 . ST-LAF exhibits a nice improvement over ST-PMA for this particular task. Note that for ST-PMA only 25% of the sets (red points in the scatter plot), corresponding to sets with maximum cardinality, approximates well the average, while for all other cardinalities (the remaining 75% of the sets) ST-PMA predicts a constant value equal to the average label in the training set. ST-LAF instead clearly captures the distribution of the labels, generalizing better with respect to the set sizes. A similar behaviour was observed when learning to predict the sum rather than the average of the unique digits in a set (see supplementary material for the results).

2 We run several experiments by changing the number of seeds k of PMA. All of them exhibited the same behaviour. For this experiment we used k = 1.

6 Conclusions

The theoretical underpinnings for sum aggregation as a universal framework for defining set functions do not necessarily provide a template for practical solutions. Therefore we introduced a framework for learning aggregation functions that makes use of a parametric aggregator to effectively explore a rich space of possible aggregations. LAF defines a new class of aggregation functions, which include as special cases widely used aggregators, and also has the ability to learn complex functions such as higher-order moments. We empirically showed the generalization ability of our method on synthetic settings as well as real-world datasets, providing comparisons with state-of-the-art sum-decomposition approaches and recently introduced techniques. The flexibility of our model is a crucial aspect for potential practical use in many deep learning architectures, due to its ability to be easily plugged into larger architectures, as shown in our experiments with the SetTransformer. The portability of LAF opens a new range of possible applications for aggregation functions in machine learning methods, and future research in this direction can enhance the expressivity of many architectures and models that deal with unstructured data.

Acknowledgements

The work of PF was partly supported by the PRIN 2017 project RexLearn, funded by the Italian Ministry of Education, University and Research, GA No 2017TWNMH2. The work of AP was partly supported by the TAILOR project, funded by EU Horizon 2020 research and innovation programme, GA No 952215. The scholarship of GP is funded by TIM and EIT Digital.