Exponential Separations in Symmetric Neural Networks

Aaron Zweig, Joan Bruna

Abstract

In this work we demonstrate a novel separation between symmetric neural network architectures. Specifically, we consider the Relational Network architecture as a natural generalization of the DeepSets architecture, and study their representational gap. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of size $N$ with elements in dimension $D$, which can be efficiently approximated by the former architecture, but provably requires width exponential in $N$ and $D$ for the latter.

Introduction

In many scientific and engineering domains—ranging from particle physics to population statistics—learning functions that are "permutation invariant" is a fundamental requirement. A function is permutation invariant if its output remains unchanged regardless of the order of its input elements, effectively treating the input as a set rather than a sequence.

Two primary architectures have emerged to handle such data: DeepSets, which process elements individually before aggregating them, and Relational Networks, which allow for interactions between pairs of elements. While both are theoretically universal approximators, this paper provides the first rigorous mathematical proof of an exponential "representational gap" between them, demonstrating that Relational Networks are fundamentally more efficient for certain classes of symmetric functions.

Architectural Comparison

To understand the separation, we must first define the two architectures under study.

Comparison of DeepSets (left) and Relational Networks (right) architectures. DeepSets process elements individually ($\psi_l(x_i)$), while Relational Networks process pairs ($\psi_l(x_i, x_j)$).
  1. DeepSets ($Sym_L$): This model transforms each element $x_i$ independently using a neural network $\psi$ and then sums the results: $f(X) = \rho(\sum_{i=1}^N \psi(x_i))$. The "symmetric width" $L$ refers to the dimensionality of the summed features.
  2. Relational Networks ($Sym^2_L$): This architecture generalizes DeepSets by processing pairs of elements: $f(X) = \rho(\sum_{i,j=1}^N \psi(x_i, x_j))$. This allows the network to capture relational structures that are invisible to models treating elements in isolation.

Methodology

The authors employ Symmetric Polynomial Theory to quantify the expressivity of these networks. A key technical challenge addressed is the extension of the Hall inner product to high-dimensional set elements (multisymmetric polynomials). This mathematical framework allows for a precise measurement of the "orthogonality" between different symmetric functions.

To prove the separation, the authors explicitly construct a "hard" symmetric function $g$ based on a finite Blaschke product. This function is designed to be easily represented by a single pairwise interaction unit ($L=1$ in a Relational Network) but is mathematically distant from any function representable by a DeepSet architecture unless that architecture has an astronomical number of neurons.

Key Results: The Exponential Gap

The core finding of the paper is a lower bound on the width required for DeepSets to approximate the hard function $g$.

  • Relational Efficiency: A Relational Network with width $L=1$ can approximate the function $g$ to high precision.
  • DeepSet Inefficiency: To achieve the same level of approximation, a DeepSet architecture requires a symmetric width $L$ that is at least $N^{-2} \exp(O(\min(D, \sqrt{N})))$.

This result is significant because it is a width separation that is independent of the depth of the internal networks. Even with infinite depth in the individual element transformations, the pooling mechanism of DeepSets remains a bottleneck that requires exponential width to overcome.

Discussion and Future Work

This work formalizes the intuition behind the success of modern architectures like Transformers. By allowing elements to "talk" to each other via self-attention (a form of relational interaction), these models avoid the exponential costs associated with simpler pooling methods.

However, the proof currently relies on the assumption of analytic activation functions (e.g., sigmoid, tanh, or exp). While the authors conjecture that similar results hold for non-analytic functions like ReLU, proving this remains an open challenge. Additionally, while the paper proves that Relational Networks can represent these functions, it does not address whether standard training algorithms like Gradient Descent can efficiently learn them. Future research may also explore whether higher-order interactions ($k$-way) provide further exponential gains over pairwise models.

Summary updated

Abstract

In this work we demonstrate a novel separation between symmetric neural network architectures. Specifically, we consider the Relational Network~\parencite{santoro2017simple} architecture as a natural generalization of the DeepSets~\parencite{zaheer2017deep} architecture, and study their representational gap. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of size $N$ with elements in dimension $D$, which can be efficiently approximated by the former architecture, but provably requires width exponential in $N$ and $D$ for the latter.
BibTeX
@inproceedings{zweig2022exponential,
  author = {Aaron Zweig and Joan Bruna},
  title = {{Exponential Separations in Symmetric Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=jjlQkcHxkp0},
}
Figure