Processing sets or other unordered, potentially variable-sized inputs in neural networks is usually handled by aggregating a number of input tensors into a single representation. While a number of aggregation methods already exist from simple sum pooling to multi-head attention, they are limited in their representational power both from theoretical and empirical perspectives. On the search of a principally more powerful aggregation strategy, we propose an optimization-based method called Equilibrium Aggregation. We show that many existing aggregation methods can be recovered as special cases of Equilibrium Aggregation and that it is provably more efficient in some important cases. Equilibrium Aggregation can be used as a drop-in replacement in many existing architectures and applications. We validate its efficiency on three different tasks: median estimation, class counting, and molecular property prediction. In all experiments, Equilibrium Aggregation achieves higher performance than the other aggregation techniques we test.

Modelling functions of sets, or equivalently, permutation-invariant functions, is a long-standing challenge in machine learning. Deep Sets is a popular method which is known to be a universal approximator for continuous set functions. We provide a theoretical analysis of Deep Sets which shows that this universal approximation property is only guaranteed if the model's latent space is sufficiently high-dimensional. If the latent space is even one dimension lower than necessary, there exist piecewise-affine functions for which Deep Sets performs no better than a naïve constant baseline, as judged by worst-case error. Deep Sets may be viewed as the most efficient incarnation of the Janossy pooling paradigm. We identify this paradigm as encompassing most currently popular set-learning methods. Based on this connection, we discuss the implications of our results for set learning more broadly, and identify some open questions on the universality of Janossy pooling in general.

This paper introduces a generative model equivariant to Euclidean symmetries: E(n) Equivariant Normalizing Flows (E-NFs). To construct E-NFs, we take the discriminative E(n) graph neural networks and integrate them as a differential equation to obtain an invertible equivariant function: a continuous-time normalizing flow. We demonstrate that E-NFs considerably outperform baselines and existing methods from the literature on particle systems such as DW4 and LJ13, and on molecules from QM9 in terms of log-likelihood. To the best of our knowledge, this is the first flow that jointly generates molecule features and positions in 3D.

We introduce the SE(3)-Transformer, a variant of the self-attention module for 3D point-clouds, which is equivariant under continuous 3D roto-translations. Equivariance is important to ensure stable and predictable performance in the presence of nuisance transformations of the data input. A positive corollary of equivariance is increased weight-tying within the model. The SE(3)-Transformer leverages the benefits of self-attention to operate on large point clouds with varying number of points, while guaranteeing SE(3)-equivariance for robustness. We evaluate our model on a toy N-body particle simulation dataset, showcasing the robustness of the predictions under rotations of the input. We further achieve competitive performance on two real-world datasets, ScanObjectNN and QM9. In all cases, our model outperforms a strong, non-equivariant attention baseline and an equivariant model without attention.

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.

In this paper we evaluate distributed node coloring algorithms for wireless networks using the network simulator Sinalgo [1]. All considered algorithms operate in the realistic signal-to-interference-and-noise-ratio (SINR) model of interference. We evaluate two recent coloring algorithms, Rand4DColor and ColorRed, proposed by Fuchs and Prutkin in [2], the MW-Coloring algorithm introduced by Moscibroda and Wattenhofer [3] and transferred to the SINR model by Derbel and Talbi [4], and a variant of the coloring algorithm of Yu et al. [5]. We additionally consider several practical improvements to the algorithms and evaluate their performance in both static and dynamic scenarios. Our experiments show that Rand4DColor is very fast, computing a valid (4Δ)-coloring in less than one third of the time slots required for local broadcasting, where Δ is the maximum node degree in the network. Regarding other O(Δ)-coloring algorithms Rand4DColor is at least 4 to 5 times faster. Additionally, the algorithm is robust even in networks with mobile nodes and an additional listening phase at the start of the algorithm makes Rand4DColor robust against the late wake-up of large parts of the network. Regarding (Δ + 1)-coloring algorithms, we observe that ColorRed it is significantly faster than the considered variant of the Yu et al. coloring algorithm, which is the only other (Δ + 1)-coloring algorithm for the SINR model. Further improvement can be made with an error-correcting variant that increases the runtime by allowing some uncertainty in the communication and afterwards correcting the introduced conflicts.

We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a~(4Δ)-coloring in O(Δ log n) time slots. The results of our experimental evaluation show that the algorithm is extremely fast. Combined with a new color reduction scheme, the algorithm computes a (Δ+1)-coloring in O(Δ log n) time. This improves on current distributed coloring algorithms for the SINR model either in terms of the number of colors or runtime, and matches the asymptotical runtime of one round of local broadcasting, which can be seen as a lower bound.