Given a neural network $f$ that takes as input $n$ data points: $x_1, \dots, x_n$. We say $f$ is permutation invariant if
$$f(x_1 ... x_n) = f(\sigma(x_1 ... x_n))$$
for any permutation $\sigma$.
How could we build such a neural network? The output can be anything (e.g. a number or vector), as long as it does not depend on the order of inputs. Is there any research work on these types of neural networks?
Here is a few that might be what you are looking for:
Traditionally, due to the way the network is structured, each input has a set of weights, that are connected to more inputs. If the inputs switch, the output will too.
However, you can build a network that approaches this behaviour. In your training set, use batch learning and for each training sample, give all possible permutations to the network such that it learns to be permutation invariant. This will never be exactly invariant, it just might be close.
Another way to do this is to have the weights replicated for all inputs. For example, let's assume you have 3 inputs ($i_0, i_1, i_2$), and the next/first hidden layer has 2 nodes ($h_{10}, h_{11}$) and activation function $\phi$. Assuming a fully connected layer, you have 2 weights $w_0$ and $w_1$. The hidden layer's nodes $h_{10}$ and $h_{11}$ are given, respectively, by
$h_{10} = \phi(i_0 w_0 + i_1 w_0 + i_2 w_0)$
$h_{11} = \phi(i_0 w_1 + i_1 w_1 + i_2 w_1)$
Thus giving you a hidden layer whose values are permutation invariant from the input. From now on, you can learn and build the rest of the network as you see fit. This is an approach derived from convolutional layers.
Finally, you can use a dimension reduction to achieve this. I've published this in Exploring Communication Protocols and Centralized Critics in Multi-Agent Deep Learning, on Integrated Computer-Aided Engineering. This approach uses convolutional architectures to efficiently achieve permutation invariance.
I have implemented Permutational Layer here using Keras: https://github.com/offchan42/superkeras/blob/master/permutational_layer.py
You can call the PermutationalModule function to use it.
Implemented following this paper: Permutation-equivariant neural networks applied to dynamics prediction.
The idea is to compare all pairs of $N^2$ pairs from $N$ inputs, use the model with shared weights, then use pooling function $N$ times on $N$ inputs.
The output you can use pooling again but in the paper, they don't mention another pooling.
So, a practical application of this with a lot of research is in the deep lidar processing community. In that world, you have to do a lot of computation on point clouds which are completely unordered. One of the seminal works in this field is Point Net (https://arxiv.org/pdf/1612.00593.pdf) which solves this problem by performing all symmetric operations across channels. 1D convolutions, max pool, etc. Any network in this style that does not project to a 2D representation has to adhere to this rule.
