Exponential Separations in Symmetric Neural Networks

Aaron Zweig, Joan Bruna

Introduction

In fields ranging from particle physics to population statistics and point cloud processing, machine learning models frequently encounter data represented as sets. A fundamental requirement for these models is permutation invariance—the network's output must remain identical regardless of how the input elements are ordered. Two prominent architectures designed to handle this are DeepSets and Relational Networks. While both are theoretically capable of universal approximation (meaning they can represent any continuous symmetric function given enough neurons), practitioners have long observed that Relational Networks and related architectures like Transformers perform significantly better in practice.

This paper formalizes this empirical intuition by demonstrating a novel, exponential separation between these symmetric neural network architectures. Specifically, the authors prove that Relational Networks can be exponentially more powerful than DeepSets, requiring vastly fewer resources to approximate certain symmetric functions.

Architectural Differences: DeepSets vs. Relational Networks

To understand this representational gap, we must look at how each architecture processes set data.

  • DeepSets operate by embedding each element of the set individually, summing these independent representations together, and then processing the aggregated result.
  • Relational Networks generalize this approach by embedding pairs of elements (modeling their interactions) before summing them up.
Comparison of DeepSets (left), which process elements individually, and Relational Networks (right), which process pairs of elements.

The core question addressed by the authors is whether there exists a fundamental "representational gap" between these two approaches. Are there specific functions that are computationally "easy" for Relational Networks to learn, but prohibitively "hard" for DeepSets?

Theoretical Framework and Methodology

To analyze the approximation power of these networks, the authors leverage tools from symmetric polynomial theory. Because standard empirical benchmarks are insufficient for proving theoretical lower bounds, they define a non-trivial data distribution over sets of vectors on the unit complex circle. They then construct a "hard" synthetic function based on finite Blaschke products—mathematical objects mapping the complex unit circle to itself. This function is explicitly designed to be easily represented by pairwise interactions but difficult to decompose into individual element contributions.

Key technical contributions include:

  • Multisymmetric Powersum Polynomials: Used as a basis to represent symmetric functions in high dimensions ($D > 1$).
  • Generalized Hall Inner Product: A novel extension of the Hall inner product to high-dimensional set elements, allowing the authors to define "orthogonality" for symmetric polynomials—a crucial step for proving lower bounds.
  • Rank Lemma: The authors prove that the "symmetric width" $L$ (the number of terms in the summation bottleneck) of a DeepSet corresponds to the rank of a specific coefficient matrix. By showing that certain functions require this matrix to be high-rank, they prove the network must be very wide.
  • Analytic Restriction: The proofs assume analytic activation functions (e.g., exp or sigmoid), allowing the use of complex analysis to show that depth cannot compensate for a lack of width in DeepSets.

Key Findings: The Power of Interaction

The study reveals a profound width separation between the architectures. In standard neural networks, depth is typically the source of exponential expressive power. However, for permutation-invariant models, the "symmetric width"—the bottleneck where set information is aggregated—is the critical resource.

The authors prove an exponential lower bound for DeepSets: for a set of $N$ elements in $D$ dimensions, a DeepSet requires a symmetric width growing exponentially with the input size and dimension ($L \geq \exp(O(\min(D, \sqrt{N})))$) to achieve a reasonable approximation of the constructed hard function. Even an infinitely deep DeepSet cannot efficiently approximate this function if its symmetric width is too small.

Conversely, they establish a polynomial upper bound for Relational Networks. A Relational Network with a symmetric width of just $L=1$ can approximate the exact same function to any desired accuracy using a total number of neurons that is only polynomial in $N$, $D$, and the inverse of the error margin.

This rigorous theoretical justification highlights why modeling pairwise interactions provides a fundamental jump in representational efficiency over modeling singletons, answering open questions regarding the high-dimensional representation power of DeepSets.

Limitations and Future Directions

While this paper provides a significant theoretical leap, it acknowledges certain limitations. The proofs rely heavily on the properties of analytic functions; popular non-analytic activations like ReLU are not covered, though the authors conjecture the exponential separation still holds. Furthermore, the paper focuses strictly on representation (expressivity) rather than optimization (learnability via gradient descent). Finally, exploring the representational gaps for higher-order ($k$-ary) interactions or more complex graph neural network layers remains an exciting frontier for future research.

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