Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We establish the first quadratic degree bounds for polynomials that separate point clouds of n points under rotations and permutations, resolving a key open question regarding the expressivity of symmetric neural networks. By demonstrating that Tensor Field Networks and MACE can express all invariant polynomials up to a certain degree, we provide concrete quadratic bounds on their representation order for completeness, replacing prior existential results. Furthermore, we show that local message-passing models can achieve separation with invariant degrees dependent only on local neighborhood size, with counterexamples highlighting the necessity of high-order irreducible representations for MACE in certain scenarios.
Neural networks for point clouds require quadratic representation orders to guarantee separation, a concrete bound finally established.
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.