On the Universality of Rotation Equivariant Point Cloud Networks

Nadav Dym, Haggai Maron

Abstract

Learning functions on point clouds has applications in many fields, including computer vision, computer graphics, physics, and chemistry. Recently, there has been a growing interest in neural architectures that are invariant or equivariant to all three shape-preserving transformations of point clouds: translation, rotation, and permutation. In this paper, we present a first study of the approximation power of these architectures. We first derive two sufficient conditions for an equivariant architecture to have the universal approximation property, based on a novel characterization of the space of equivariant polynomials. We then use these conditions to show that two recently suggested models are universal, and for devising two other novel universal architectures.

Introduction: The Quest for Universality

In deep learning, "universality" is the gold standard: it signifies that a model architecture is expressive enough to approximate any continuous function to arbitrary precision, given sufficient parameters. While standard multi-layer perceptrons (MLPs) and convolutional neural networks (CNNs) are known to be universal, the situation is more complex for models designed to respect specific geometric symmetries.

For 3D point clouds, ideal models should be equivariant to the rigid motion group (rotations and translations) and invariant to the ordering of points (permutations). Numerous architectures, such as Tensor Field Networks (TFNs) and SE(3)-Transformers, have been proposed to incorporate these symmetries. However, a critical theoretical question remained: do these symmetry-aware constraints "handcuff" the models, preventing them from learning certain complex functions? This research addresses this gap by proving that these constraints do not sacrifice expressivity.

The gap between the space of all equivariant functions and the functions representable by specific equivariant networks.

Methodology: A Framework for Equivariant Approximation

The authors develop a general, architecture-agnostic framework for proving universality based on two primary pillars:

  1. Equivariant Polynomials: The study proves that continuous equivariant functions can be approximated by equivariant polynomials. This shifts the theoretical challenge from approximating abstract functions to representing specific polynomial "building blocks."
  2. The "Semi-Lifted" Approach: The framework defines two sufficient conditions for a network to achieve universality:
  3. D-spanning: The network must be capable of representing a specific set of polynomials that are translation-invariant and permutation-equivariant.
  4. Linear Universality: The network's linear layers must be able to map between any two representations of the rotation group ($SO(3)$).
The semi-lifted approach mapping inputs to a higher-dimensional representation space.

By applying this framework to Tensor Field Networks (TFN), the authors demonstrate that composing TFN layers—which utilize spherical harmonics and Clebsch-Gordan coefficients—satisfies both conditions.

Key Insights and Results

The most significant finding is the formal proof (Theorem 2) that the popular TFN architecture is a universal approximator for point clouds. This provides a rigorous mathematical justification for its widespread adoption in scientific domains like physics and chemistry.

Additional insights include:

  • Sufficiency of Low-Order Filters: Surprisingly, extremely high-order spherical harmonic filters are not strictly necessary for universality. A network can remain universal using only filters of order 0 and 1, provided it has enough layers to compose these simple operations.
  • Symmetry Separation: The proof strategy effectively decouples the handling of permutations from rotations. This suggests that high-dimensional representations are primarily needed for the rotation group to achieve full expressivity.
  • Novel Architectures: The paper introduces two new provably universal architectures: a minimal tensor-product model and an alternative TFN variant using modified convolutional layers.

Conclusion and Future Directions

While this work establishes the theoretical expressivity of equivariant networks, several avenues for future research remain. The proofs currently apply to compact sets, leaving the behavior on unbounded domains as an open question. Furthermore, while universality proves a model can learn a function, it does not address the efficiency (parameter count or depth) required to do so. Future work may also extend these findings to other groups, such as $O(3)$ (including reflections) or the Lorentz group used in high-energy physics.

Summary updated

Abstract

Learning functions on point clouds has applications in many fields, including computer vision, computer graphics, physics, and chemistry. Recently, there has been a growing interest in neural architectures that are invariant or equivariant to all three shape-preserving transformations of point clouds: translation, rotation, and permutation. In this paper, we present a first study of the approximation power of these architectures. We first derive two sufficient conditions for an equivariant architecture to have the universal approximation property, based on a novel characterization of the space of equivariant polynomials. We then use these conditions to show that two recently suggested models are universal, and for devising two other novel universal architectures.
BibTeX
@inproceedings{dym2021universality,
  author = {Nadav Dym and Haggai Maron},
  title = {{On the Universality of Rotation Equivariant Point Cloud Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=CzmiO1pC8Ao},
}
Figure