Summary
Neural networks that analyze 3D point clouds often need to consider how objects can be rotated or reordered to understand them correctly. The authors found concrete limits on how complex these networks need to be to tell any two point clouds apart, even when rotations and rearrangements happen. They proved that certain network types can achieve this by looking at polynomial features up to a specific complexity, and that this complexity grows roughly with the square of the number of points. The work also shows that for point clouds with regular local structure, simpler approaches focusing on small neighborhoods can still distinguish them effectively.
What this means in practice
- •For 3d vision engineers: Design neural architectures with guaranteed complexity limits for distinguishing rotated and permuted point cloud data.
- •For robotics developers: Create models that separate locally regular point cloud structures efficiently by focusing on neighborhoods instead of entire clouds.
A theory result. No direct application yet.
Authors
Snir Hordan, Harm Derksen, Mircea Petrache, Nadav Dym
Abstract
Neural networks that respect the symmetries of point clouds commonly compute high-order representations of the rotation group to improve their expressivity. Such models are known to be universal, and thus able to separate any pair of point clouds, when using representations of sufficiently high order, yet no precise bound on this order, as a function of the number of points, was previously known. We establish the first quadratic lower and upper degree bounds for polynomials that separate point clouds of n points up to rotations and permutations. By showing Tensor Field Networks and MACE can express all invariant polynomials of a given degree with sufficient representation order, we additionally derive the first explicit, quadratic bound on the representation order sufficient for these architectures to be complete, replacing previous existence results with concrete guarantees. We further show that, under local regularity assumptions, point cloud separation can be achieved with a message-passing-based model using invariants whose degree depends only on the size of a local neighborhood, rather than on the size of the full point cloud. Finally, we provide counterexamples showing MACE must compute high order irreducible representations to separate locally regular point clouds.