A $2$-closed permutation group with nonuniversal first-order invariant networks

We give a counterexample to a conjecture of Maron--Fetaya--Segol--Lipman on the universality of certain neural networks. More precisely let $G\cong S_6$ act on the $15$ unordered pairs of a six-element set. We show that this permutation group is $2$-closed, but every first-order $G$-invariant neural network, with arbitrary activation function, identifies the edge indicator vectors of a six-cycle and two disjoint triangle graphs. Since these vectors can be separated by a $G$-invariant cubic polynomial, we get that the latter cannot be approximated arbitrarily well by such neural networks.