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.
Figures & tables
Figure 1: From left to right we have plotted the coordinates of w(0) , w(0.1) and w(152π)=w(0.4189) in the complex plane for n=8 . We have p=5 , q=3 and r=4 . As t goes from 0 to 0.1 the pentagon moves counterclockwise and the triangle moves clockwise. The point clouds of w(0) and w(152π) are isometric. The latter is obtained from the first by rotation over 158π and applying the permutation (12345)(876) to the columns of w .
Figure 2: A family of regular point clouds which cannot be separated by mace without high degree/correlation order. See Proposition 12 for details.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
ℓmax\νmax
1
2
3
4
1
4†/4∗/7
4†/9/17
7/15/41
7/23/87
2
4†/4∗/9
4†/15/31
9/27/81
11/43/171
3
4†/4∗/11
4†/21/45
11/39/119
15/63/255
4
4†/4∗/15
4†/27/59
15/51/159
19/83/339
Appendix
Table 1: Smallest number K of points per cutoff ball from which local MACE with the readout equation 6 –equation 7 , irreducible degree ℓmax (rows), correlation order νmax (columns) and T iterations is provably not (SE(3)×Sn,Rρ,K) -complete, by Corollary 43 . Each cell lists the thresholds for T=1 / T=2 / T=3 , in this order. All entries equal to 4 come from Lemma 41 : the invariant channels of the model are unchanged under X↦−X , so it cannot tell a chiral cloud from its mirror image; 4 is the least possible value, since Rρ,K contains only one-point clouds when K≤3 (Remark 40 ). Entries marked 4† were known before this work : with T=1 the invariant channels are functions of distances ( νmax=1 ) or three-body invariants ( νmax=2 ), which are classically inversion invariant. Entries marked 4∗ rest on the same known mechanism , but the observation that two iterations with νmax=1 still produce no pseudoscalar is stated here. Entries in bold are new : they come from the two-ring family of Definition 34 and Theorem 37 , apply to models that can produce pseudoscalars, and grow linearly in ℓmax and like νmaxT in νmax .
We introduce two new methods for boundary detection in high-dimensional point cloud data, intended to work in situations with non-uniform density, high ambient dimension, and substantial noise. Our first method fits a separating hyperplane on local neighborhoods after doing local dimension reduction---this method works best when one can reliably estimate the intrinsic dimension of the data. Our second method measures the directional uniformity of local neighborhoods, and has the best overall performance on synthetic data. In addition to pointwise numerical boundary scores, our algorithms yield an estimated normal vector at each boundary point. We validate our methodology on synthetic data as well as two real examples: we analyze spatial transcriptomics data, where we show that we can detect the boundary of a tumor, and we also study LLM activation geometry.
Abigail Hickok, Valerio Galanti, Osama Al Dalahmah +1
Department of Mathematics Columbia University New York, NY, USA · Department of Computer Science Columbia University New York, NY, USA · Department of Pathology and Cell Biology Columbia University New York, NY, USA +1
While invariant architectures are standard for processing symmetric data, there is growing interest in achieving invariance by applying group averaging or canonization to non-invariant backbones. However, the theoretical generalization properties of these alternative strategies remain poorly understood. We introduce a theoretical framework to analyze the generalization error of these methods by bounding their covering numbers. We establish a rigorous generalization hierarchy: the error bounds of canonized models are at best equal to the error bounds of structurally invariant and group-averaged models, and at worst equal to the bounds of non-invariant baselines. Furthermore, we show that there exist optimal canonizations which attain the optimal error bounds, and poor canonizations which attain the non-invariant error bounds, and that this depends on the regularity of the canonization. Finally, applying this framework to permutation groups in point cloud processing, we rigorously prove that the covering number of lexicographical sorting grows exponentially with point cloud dimension, whereas Hilbert curve canonization guarantees polynomial growth. This provides the first formal theoretical justification for the empirical success of Hilbert curve serialization in state-of-the-art point cloud architectures. We conclude with experiments that support our theoretical claims. Code is available at https://github.com/yonatansverdlov/Canonization
Yonatan Sverdlov, Benjamin Friedman, Snir Hordan +1
In many practical applications it is important to build symmetries into neural network architectures. Consider the important case of permutation symmetry on point clouds consisting of n points in d dimensions. In this case the network learns a function on a set of n points in Rd, and a natural paradigm for constructing invariant networks is Janossy pooling, which generalizes the popular Deep Sets architecture. We study the universality of this approach, in particular the important question of how large the embedding dimension must be to guarantee universality of this architecture. Specifically, using a novel technique, we prove new lower bounds on the required size of this embedding dimension. For Deep Sets, this gives the correct minimal dimension up to a constant factor for all d>1. For k-ary Janossy pooling, we prove the first non-trivial lower bound on the required embedding dimension when k>1.
Ali Syed, Aditya Nambiar, Jonathan W. Siegel
Department of Mathematics Texas A&M University College Station, TX 77843