Learning Functions over Sets via Permutation Adversarial Networks

Chirag Pabbaraju, Prateek JainarXiv 2019 · OpenReview

Abstract: In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individual element embeddings can necessitate extremely large embedding sizes for challenging functions. We address this challenge by allowing standard neural networks like LSTMs to succinctly capture the function over the set. However, to ensure invariance with respect to permutations of set elements, we propose a novel architecture called SPAN that simultaneously learns the function as well as adversarial or worst-case permutations for each input set. The learning problem reduces to a min-max optimization problem that is solved via a simple alternating block coordinate descent technique. We conduct extensive experiments on a variety of set-learning tasks and demonstrate that SPAN learns nearly permutation-invariant functions while still ensuring accuracy on test data. On a variety of tasks sampled from the domains of statistics, graph functions and linear algebra, we show that our method can significantly outperform state-of-the-art methods such as DeepSets and Janossy Pooling. Finally, we present a case study of how learning set-functions can help extract powerful features for recommendation systems, and show that such a method can be as much as 2% more accurate than carefully hand-tuned features on a real-world recommendation system.

Introduction

Many real-world data structures, such as point clouds, click histories, or graph nodes, are naturally represented as sets. Because sets are unordered, any machine learning model processing them must be permutation invariant—the output should remain identical regardless of the order in which elements are presented.

Existing methods like DeepSets achieve this by processing elements independently and applying a symmetric pooling operation (e.g., sum or max). However, this architectural constraint often limits the network's ability to capture complex, higher-order relationships between elements. While Janossy Pooling attempts to model these relationships by pooling over subsets, it suffers from a combinatorial explosion in computational cost, scaling poorly to larger sets or more complex interactions.

The SPAN Architecture

We introduce Set Permutation Adversarial Networks (SPAN), a novel approach that replaces rigid architectural constraints with an adversarial training framework. Instead of forcing invariance through pooling, SPAN uses a standard, expressive sequential model—an LSTM—and trains it to be permutation-invariant by playing a min-max game against an adversary.

The SPAN architecture uses an adversarial network to learn permutations that challenge the LSTM learner.

The architecture consists of two primary components:

  1. The Learner (LSTM): Processes the set sequentially to predict the target label. While powerful, LSTMs are naturally sensitive to input order.
  2. The Adversary (Permutation Network): Learns to find the worst-case permutation of the input set—the specific ordering that maximizes the LSTM's prediction error.

To make the discrete act of permuting differentiable, the adversary utilizes Sinkhorn updates to approximate permutation matrices. By constantly training against the most difficult possible orderings, the LSTM is forced to learn the underlying set logic rather than relying on spurious ordering biases.

Experimental Evaluation

SPAN was evaluated across a variety of synthetic benchmarks and a large-scale real-world application.

Synthetic Benchmarks

On tasks requiring the comprehension of complex relationships, such as Max $k$-ary Distance and Multi-source Maximum Flow, SPAN significantly outperformed baselines. For the Max 3-ary Distance task, SPAN achieved approximately 55% higher accuracy than DeepSets. In graph-based tasks, SPAN reduced relative error by ~30% compared to DeepSets, while Janossy Pooling proved computationally infeasible for sets of 200 elements due to its $O(n^3)$ complexity.

Real-World Case Study: Microsoft Teams

We applied SPAN to a message relevance prediction task for Microsoft Teams, utilizing a dataset of over 100,000 interaction logs. SPAN was tasked with learning set representations for user-author and user-group histories to improve recommendation accuracy.

AUC@k comparison on the Microsoft Teams recommendation task, showing SPAN outperforming DeepSets and a hand-tuned baseline.

As shown in the AUC plot, SPAN-learned features consistently outperformed both DeepSets and a production baseline of carefully hand-tuned statistical features by up to 2% in AUC@k. This demonstrates that adversarial training can effectively automate the extraction of powerful features from raw set data.

Conclusion

SPAN demonstrates that adversarial training is a viable and often superior alternative to traditional pooling-based set architectures. By allowing models to retain the expressiveness of sequential networks while enforcing permutation invariance through competition, SPAN achieves state-of-the-art performance on complex set-learning tasks and provides significant gains in real-world recommendation systems.

Summary updated

Abstract

In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individual element embeddings can necessitate extremely large embedding sizes for challenging functions. We address this challenge by allowing standard neural networks like LSTMs to succinctly capture the function over the set. However, to ensure invariance with respect to permutations of set elements, we propose a novel architecture called SPAN that simultaneously learns the function as well as adversarial or worst-case permutations for each input set. The learning problem reduces to a min-max optimization problem that is solved via a simple alternating block coordinate descent technique. We conduct extensive experiments on a variety of set-learning tasks and demonstrate that SPAN learns nearly permutation-invariant functions while still ensuring accuracy on test data. On a variety of tasks sampled from the domains of statistics, graph functions and linear algebra, we show that our method can significantly outperform state-of-the-art methods such as DeepSets and Janossy Pooling. Finally, we present a case study of how learning set-functions can help extract powerful features for recommendation systems, and show that such a method can be as much as 2% more accurate than carefully hand-tuned features on a real-world recommendation system.
BibTeX
@misc{pabbaraju2019learning,
  author = {Chirag Pabbaraju and Prateek Jain},
  title = {{Learning Functions over Sets via Permutation Adversarial Networks}},
  year = {2019},
  eprint = {1907.05638},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.05638},
}
Figure