Deep Sets and Permutation-Invariant Networks

Some inputs to a model are naturally sets, not sequences: a basket of correlated positions in a portfolio, the price levels sitting in an order book at one instant, or the collection of news headlines mentioning a ticker on a given day. There is no meaningful "first" element. Feed such a collection into an ordinary neural network by concatenating the elements in some order, and the network's output depends on that arbitrary order — shuffle the same basket and you can get a different answer, which is clearly wrong for something that shouldn't have an order at all.

The analogy: counting a bag of coins

The total value of a bag of coins does not depend on the order you dropped them in — you can add them up in any sequence and get the same sum. That property, unaffected by reordering, is permutation invariance, and addition is the simplest operation that has it.

The mechanics

Deep Sets builds any permutation-invariant function of a set $X = \{x_1, \dots, x_n\}$ as:

$$f(X) = \rho\left(\sum_{x \in X} \phi(x)\right)$$

In words: first, a small network $\phi$ encodes each element on its own, the same way for every element, ignoring the others entirely. Then a symmetric pooling operation — here, a sum — combines all the per-element encodings into one fixed-size vector, which cannot depend on element order because addition doesn't care about order. Finally, a second network $\rho$ turns that pooled vector into the actual output.

Worked example 1: order doesn't matter

Let $\phi$ be a simple learned scalar per element: three set elements produce $\phi$-outputs $2, 5, 3$ in that order. Sum pooling: $2+5+3=10$. Feed the same three elements in the order $5, 2, 3$: still $5+2+3=10$. Any of the $3! = 6$ orderings of these three numbers gives the identical sum — the invariance is exact, not approximate, because addition is exactly commutative.

Worked example 2: sum versus max pooling

Same three per-element outputs, $2, 5, 3$. Sum pooling gives $10$; max pooling instead gives $\max(2,5,3)=5$. Both are valid symmetric (order-independent) choices, but they encode different things: sum captures a total across the whole set (useful for something like aggregate portfolio risk contribution), while max captures only the single most extreme element (useful for something like "is there at least one order-book level at an extreme price"). Both remain invariant to reordering the same three numbers in any way.

What this means in practice

Any input that is genuinely a collection with no inherent order — a set of correlated holdings, a snapshot of order-book levels, a day's worth of news items about one name — is a candidate for a Deep Sets-style model instead of forcing it into a fixed-order vector or a sequence model that would otherwise treat item order as meaningful when it isn't.