The Cost of Symmetry: Universality and Hardness for Permutation-Invariant Neural Networks

Permutation-invariant machine learning architectures, such as DeepSets, Set Transformers, Graph Neural Networks, and $k$-GNNs, are each highly used and studied individually. We unify them into a single complexity-theoretic framework: noisy symmetric circuits. Each architecture falls into our hierarchy at a level $k$, parameterized by the order of interactions it captures. Within this framework, we tightly characterize the cost of symmetry. At level $1$, where DeepSets operate, every symmetric function on boolean input computable by a neural network has an equivalent DeepSet, at the cost of an additive blowup nearly linear in the input size, and we exhibit an explicit function that requires this blowup. At level $2$, where Set Transformers and GNNs operate, the same near-linear blowup suffices for WL-invariant functions, while non-WL-invariant functions are known to be uncomputable at level $2$. These results show that, in the regimes we cover, WL is the \textit{only} barrier to using a symmetric architecture; everywhere else, symmetry is \textit{low-cost}. Experiments illustrate the near-linear threshold predicted by the theory.