acceptodds
Under review as a conference paper at ICLR 2027

Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds

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 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
invariant learning, high order representations, separating invariants, point clouds

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wrqhOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper establishes quadratic degree bounds for separating 3D point clouds using invariant polynomials. It derives explicit completeness conditions for TFN and a modified MACE architecture, together with local-neighborhood guarantees and counterexamples.

Critical strengths

The paper makes a meaningful theoretical contribution by turning qualitative completeness results into explicit bounds. The matching quadratic scaling of the polynomial bounds is particularly valuable. The local counterexamples also offer useful insights into the limitations of low-order geometric representations.

Critical weaknesses
  1. Practical interpretation. The sufficient representation orders are very large, and the associated channel requirements and computational costs remain unclear. Could the authors explain what practical architecture-design insights follow from these results?

  2. Scope of applicability. The local guarantees require strong regularity assumptions, and the MACE analysis uses a modified architecture. Could the authors more clearly discuss applicability to standard implementations and to noisy or approximately symmetric point clouds?

Questions for authors

Please refer to the Weakness.

2 comments

Thank you for your thoughtful and positive review! Our responses to your questions are given below. Changes in the revised manuscript are colored blue for your convenience.

Weakness 1. Practical interpretation. The sufficient representation orders are very large, and the associated channel requirements and computational costs remain unclear. Could the authors explain what practical architecture-design insights follow from these results?

Response. We agree that the upper bounds are far from practical settings and are not intended as hyperparameter recommendations. They do replace the existence statements in the literature with explicit bounds, and they show that quadratic growth is unavoidable for polynomial invariants (Theorem 1).

Moreover, Proposition 12 does give a meaningful lower bound for MACE expressivity in a realistic parameter range: for example, as mentioned in the text, for MACE with ℓmax⁡=νmax⁡=3\ell_{\max}=\nu_{\max}=3, completeness provably fails on locally regular clouds once the neighbourhood contains K≥11K\ge 11 (T=1T=1), K≥39K\ge 39 (T=2T=2) or K≥119K\ge 119 (T=3T=3) points. The expression ℓmax∑t=1Tνmaxt\ell_{max}\sum_{t=1}^{T}\nu_{max}^{t} in Proposition 12 can give intuition for the tradeoff in expressivity that different hyperparameters provide: specifically, while the bound depends linearly on the irreducible order ℓmax\ell_{max}, increasing the depth TT and correlation order νmax\nu_{max} has a significantly more substantial impact.

Weakness 2. Scope of applicability. The local guarantees require strong regularity assumptions, and the MACE analysis uses a modified architecture. Could the authors more clearly discuss applicability to standard implementations and to noisy or approximately symmetric point clouds?

Response. Regarding MACE modification: originally, we had three results regarding (modified) MACE in the paper. After reconsidering the arguments, we see that the third result holds for the standard MACE as well, while the first two needed this modification, but they do hold for ACE, without modification! Accordingly, in the revised manuscript, the first two results, Proposition 8 / Corollary 9 and Theorem 11 (completeness of global and local ACE) are now stated and proved for (unmodified) ACE, and Proposition 12 (incompleteness of local MACE) is now stated for both ACE and (unmodified) MACE. We believe this increase the attractiveness of the results in the paper and thank you for bringing up this point.

Regarding symmetries and noise: symmetric point clouds are not strongly regular, so Theorem 11 does not apply to them. However, symmetric point clouds can be regular, and so Proposition 12, our lower bound on the degrees needed for completeness on regular clouds, is relevant. All our other results apply globally to all point clouds, and in particular to symmetric ones. Noisy or perturbed point clouds, by contrast, are generically strongly regular, since strong regularity fails only on a measure-zero set, so Theorem 11 applies to them. We note, however, that completeness is a qualitative property: our results give no quantitative stability guarantee for clouds that are close to symmetric configurations.

Conclusion Please let us know if you have any more questions. If our responses have addressed your concerns, please consider raising our score.

The authors’ response has addressed my concerns, and I therefore maintain my weak accept rating.

Reviewer_WWa8OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks how high the degree of invariant polynomials needs to be to separate all point clouds up to rotations, translations and permutations. The main result is that, for fixed dimension d, this "separation degree" is Θ(n²): the lower bound is about n²/4, the upper bound about 6dn². For weighted graphs, the upper bound is improved from about n⁴/8 to O(n³). Turning to neural networks, the authors show that TFN and an ACE-style MACE variant can express all invariant polynomials up to the required degree, which gives the first explicit representation order sufficient for completeness (about 9n² for the MACE variant, 18n² for TFN). Under a local strong-regularity assumption, the order for MACE depends only on the neighborhood size K (about 9K²). Finally, a two-ring counterexample shows that, with bounded depth and correlation order, local MACE needs ℓ_max to grow at least linearly in K.

Critical strengths

S1. The first tight-order bounds on the separation degree of point clouds. For fixed d, the lower bound n²/4 − 1 and the upper bound 6dn² are both quadratic in n, which is a new quantitative result. The weighted-graph bound also improves from roughly n⁴/8 to O(n³). I am not an expert in invariant theory, but as far as I can tell, no quantitative result of this kind was previously known.

S2. Turning the qualitative completeness of equivariant networks into concrete numbers. TFN and the MACE variant now have explicit completeness orders. More practically useful is the local MACE lower bound: with the Eq. (6)–(7) readout and ℓ_max = ν_max = 3, the model is provably incomplete once K reaches 11 (T = 1), 39 (T = 2) or 119 (T = 3) (Table 1 in the appendix). These numbers can be compared directly with common hyperparameter settings.

Critical weaknesses

W1. The connection between the sufficient bounds and practical architectures needs clarification. For n = 10, the sufficient configuration in the paper uses ℓ_max = 814 and ν_max = 9 for the MACE variant, while TFN uses order 1,629 with 3,258 layers. The local sufficient bound gives ℓ_max = 2,164 for K = 16. These are sufficient guarantees, not necessary requirements, and smaller configurations may still be complete. I value the first explicit bounds, and the paper already acknowledges their large size. My remaining question is what architectural insight practitioners can take from them, beyond the worst-case guarantee. An explanation of the main sources of looseness would help; I am not asking for a new, tighter theorem during rebuttal.

W2. The connection to standard MACE and existing ACE completeness results could be clearer. Section 3.2 and Appendix D.2 explicitly describe the architectural modifications, including separate channel mixing for each tensor-product factor and the treatment of parity. I appreciate that these changes are disclosed. What I would like to understand better is which completeness conclusions carry over to standard MACE implementations, and which depend on these modifications. It would also help to discuss the relation to Dusson et al., “Atomic cluster expansion: Completeness, efficiency and stability” (J. Comput. Phys. 2022), which is not cited. My reading is that the explicit ℓ ≤ ⌊D/2⌋ and ν ≤ n−1 bounds, together with Theorem 4, are important additions; please clarify that distinction.

Questions for authors

Q1 (W1): Which steps account for most of the looseness in the sufficient bounds, and what practical architecture-design insights follow from them? A clarification of their interpretation would be useful; I am not requesting a new, tighter bound during rebuttal.

Q2 (W1): Theorem 11 holds for strongly regular clouds, but the two-ring family behind Theorem 37 has rotational symmetry and seems to be only regular, not strongly regular. On the strongly regular class, the only lower bound I could find is the one from Lemma 41, which does not grow with K. Does ℓ_max actually need to grow with K on strongly regular clouds? Is any upper bound known on the regular class? If this is still open, I think Remark 44 should say explicitly that the two bounds concern different classes.

Q3 (W2): Which conclusions of Proposition 8 carry over to standard MACE, and which depend on the modifications described in Section 3.2 and Appendix D.2? How does the result relate to the existing ACE completeness results of Dusson et al.?

Q4 (minor): I may be missing something, but for n = 3 and 4 the construction in Theorem 1 has q = 1, and the cloud does not seem to be centered. Do the E(d) and SE(d) cases need a separate argument there?

2 comments

Thank you for your thoughtful and positive review! Our responses to your questions are given below. Changes in the revised manuscript are colored blue for your convenience.

Q1 (W1). For n = 10 or K = 16, the sufficient conditions already require representation orders in the hundreds. Which step is loosest? Could a much tighter bound be obtained for some practically relevant class of point clouds, or could the gap to practical low-order MACE be characterized more directly?

Response. We agree that the representation orders are not practical, and they are only a first step. Two ways to mitigate this:

(a) Focus on a practically relevant class of point clouds, as the reviewer suggests. This requires us to pinpoint certain properties that these classes have, and makes separation/completeness easier.

(b) Alternatively, one could attempt to prove completeness of MACE with a fixed low representation order, for all point clouds. This is left as an open question at the end of the paper. In this regard, the main take home message from our paper is this: while previous work proved completeness of high order ACE and MACE constructions by showing they construct invariant polynomials, our lower bound on polynomial degree separation shows that this path leads to unrealistically high cardinality-dependent bound on the degree (quadratic in n by theorem 1) and irredicuble order (linear in K by Proposition 12) needed for separation. Thus, any attempt to address this problem needs to consider alternative non-polynomial routes.

Q2 (W1). Theorem 11 holds for strongly regular clouds, but the two-ring family behind Theorem 37 has rotational symmetry and seems to be only regular, not strongly regular. On the strongly regular class, the only lower bound I could find is the one from Lemma 41, which does not grow with K. Does ℓ_max actually need to grow with K on strongly regular clouds? Is any upper bound known on the regular class? If this is still open, I think Remark 44 should say explicitly that the two bounds concern different classes.

Response. Indeed the two results apply to two different classes: the two-ring family behind Theorem 12 has rotational symmetry and is regular but not strongly regular. We added a sentence clarifying this just before Theorem 12. Regarding your two further questions:

  • Strongly regular clouds. We do not know whether ℓmax⁡\ell_{\max} must grow with KK on this class; this is open. Our lower-bound construction relies on symmetry, which strongly regular clouds exclude.
  • Regular clouds. We do not know a KK-dependent upper bound on this class. Theorem 11 uses strong regularity to glue local environments, and without it the gluing can be ambiguous. The only upper bound we have on regular clouds is the global, nn-dependent bound of Corollary 9.

Q3 (W2): Which conclusions of Proposition 8 carry over to standard MACE, and which depend on the modifications described in Section 3.2 and Appendix D.2? How does the result relate to the existing ACE completeness results of Dusson et al.?

Response. We separate our answer into two parts.

Modified MACE. Originally, we had three results regarding (modified) MACE in the paper. After reconsidering the arguments, we see that the third result holds for the standard MACE as well, while the first two needed this modification, but they do hold for ACE, without modification! Accordingly, in the revised manuscript, the first two results, Proposition 8 / Corollary 9 and Theorem 11 (completeness of global and local ACE) are now stated and proved for (unmodified) ACE, and Proposition 12 (incompleteness of local MACE) is now stated for both ACE and (unmodified) MACE. We believe this increases the attractiveness of the results in the paper and thank you for bringing up this point.

Dusson et al. Thank you for the reference, which we now cite.

What their results show. Their completeness results (Theorems 6 and 8) are density statements. For a fixed interaction order NN, the symmetry-adapted ACE basis functions are dense in the space of sufficiently regular, isometry- and permutation-invariant NN-body functions. This density requires the radial and angular degrees to be unbounded, so these results give no bound on the irreducible order ℓ\ell needed.

What we add. Our results are quantitative:

  • Proposition 8 shows that a single ACE layer with νmax⁡=min⁡{D,n−1}\nu_{\max}=\min\{D,n-1\} and ℓmax⁡=⌊D/2⌋\ell_{\max}=\lfloor D/2\rfloor expresses every invariant polynomial of degree ≤D\le D exactly.
  • Combined with Theorem 4, this gives Corollary 9: ACE with νmax⁡=n−1\nu_{\max}=n-1 and ℓmax⁡=⌊D/2⌋≈9n2\ell_{\max}=\lfloor D/2\rfloor\approx 9n^2 is complete on point clouds with nn points.
  • Universal approximation of continuous invariant functions on compact sets then follows by a standard argument: feed finitely many such ACE outputs into an MLP readout.

Q4 (minor). I may be missing something, but for n = 3 and 4 the construction in Theorem 1 has q = 1, and the cloud does not seem to be centered. Do the E(d) and SE(d) cases need a separate argument there?

Response. Good catch, thanks. We added a sentence to the proof of Theorem 1 explaining that n<5n<5 needs a separate argument, and provide this separate argument as lemma 13 in the appendix.

Conclusion Please let us know if you have any more questions. If our responses have addressed your concerns, please consider raising our score.

Reviewer_SEQUOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how high the polynomial degree needs to be to distinguish point clouds up to rotations and permutations. The authors prove nearly tight quadratic bounds and use them to derive explicit completeness guarantees for TFN and MACE. They also study local point clouds and give lower bounds showing when MACE cannot distinguish certain configurations.

Critical strengths
  1. Strong theoretical contribution. The quadratic bounds are a meaningful improvement over previous existence results. I particularly like the lower-bound construction, which is elegant and provides useful insight into the problem.

  2. Good connection to neural networks. The paper goes beyond invariant theory and shows what these bounds imply for TFN and MACE. The local completeness results and counterexamples also make the analysis more interesting.

Critical weaknesses
  1. The MACE results rely on a modified architecture, so their applicability to standard MACE is unclear.

  2. The required representation orders are very large, which limits their practical relevance.

Questions for authors
  1. Besides order and depth, is it possible to bound the network width, or feature complexity, to achieve completeness?
  2. How restrictive are the strong regularity assumptions in theorem 11 for real-world point clouds? for example, real-world moleculars.
1 comment

Thank you for your thoughtful and positive review! Our responses to your questions are given below. Changes in the revised manuscript are colored blue for your convenience.

Weakness 1. The MACE results rely on a modified architecture, so their applicability to standard MACE is unclear.

Response. We agree that this was an issue, and we feel that in the revised manuscript we have now resolved this:

Originally, we had three results regarding (modified) MACE in the paper. After reconsidering the arguments, we see that the third result holds for the standard MACE as well, while the first two needed this modification, but they do hold for ACE without modification! Accordingly, in the revised manuscript, the first two results, Proposition 8 / Corollary 9 and Theorem 11 (completeness of global and local ACE), are now stated and proved for (unmodified) ACE, and Proposition 12 (incompleteness of local MACE) is now stated for both ACE and (unmodified) MACE. We believe this increases the attractiveness of the results in the paper and thank you for bringing up this point.

Question 1. Besides order and depth, is it possible to bound the network width, or feature complexity, to achieve completeness?

Response. This is a good question. Our current proofs do not optimize width. What we can say:

  • Output (embedding) width. This can be bounded linearly in nn with a known general argument. By Corollary 9, for every pair of inputs from different orbits, global linear ACE with the prescribed hyperparameters and output dimension 1 separates them for some choice of coefficients. The output is polynomial in the input and linear in the coefficients. By the finite-witness theorem (Amir et al., 2023; see also Dym and Gortler, Low dimensional invariant embeddings for universal geometric learning), 2⋅3n+12\cdot 3n+1 independent, generically parameterized copies are therefore jointly complete. So the final invariant embedding can have dimension 6n+16n+1.
  • Internal width. In the construction of Proposition 8, the internal width is not small. There are ⌊D/2⌋+1\lfloor D/2\rfloor+1 radial channels for each ℓ\ell, and one invariant feature for each tuple (k,ℓ,η)(\mathbf k,\boldsymbol\ell,\eta) with ν≤min⁡{D,n−1}\nu\le\min\{D,n-1\}, kt,ℓt≤⌊D/2⌋k_t,\ell_t\le\lfloor D/2\rfloor and total degree ∑t(2kt+ℓt)≤D\sum_t(2k_t+\ell_t)\le D. This count grows combinatorially, and we did not try to optimize it. Obtaining good bounds on the internal width is an interesting direction for future work.

Question 2. How restrictive are the strong regularity assumptions in theorem 11 for real-world point clouds? for example, real-world moleculars.

Response. Thank you for raising this. The assumptions have different natures:

  • Strong regularity (no two different ordered (d+1)(d+1)-subsets are congruent) is a generic condition. The set of clouds that violate it is contained in a proper algebraic subset, which has measure zero. In particular, conformations perturbed by thermal noise, or sampled from molecular dynamics, will generically satisfy it. It fails for clouds with exact symmetries, for example molecules in exactly symmetric equilibrium geometries such as methane, and for clouds containing repeated congruent sub-configurations, such as perfect crystals.
  • (D) and (K) are mild. Atoms assume distinct positions, and KK is the maximal number of points in a cutoff ball, which is finite for physical systems.
  • (O) (connectivity of the ρ\rho-adjacency graph, with d+1d+1 affinely independent points in the overlap of adjacent balls) requires the cutoff to be large relative to the interatomic spacing. It always holds for non-coplanar clouds once ρ\rho is at least the diameter of the cloud, though then K=nK=n; in practice it needs a cutoff that captures several neighbouring atoms in every direction. It fails for exactly planar structures (e.g. a planar molecule such as benzene in d=3d=3), which never contain 4 affinely independent points, so they violate (O) for any cutoff.

Conclusion Please let us know if you have any more questions. If our responses have addressed your concerns, please consider raising our score.

Comments on the paper

2 comments

Dear reviewers,

Could you please let us know if our response addressed your concerns? We will be happy to answer any further questions you have before the November 18th author-reviewer discussion deadline.

Thanks, The authors

Dear AC and reviewers,

As the discussion period draws to a close, we would like to summarize the situation as we see it.

Our paper discusses the problem of complete separation for point clouds. We provide tight quadratic upper and lower bounds in the polynomial setting, and use these to derive the first quantitative completeness estimates for machine learning models: Tensor Field Networks, and (initially) MACE. We also give lower bounds for MACE, but there is a substantial gap between upper and lower bounds.

The reviewers were mostly positive about the paper. Two repeated concerns were (a) the bounds for MACE used a modified model and (b) the upper bounds for MACE require quadratic high order features, while in practice a low order is used. We believe in the revision we have resolved (a), by updating the claims and proofs so that they apply for ACE (without modification). The lower bound applies for unmodified MACE. Regarding (b), we agree that this is only a first step, but we believe that we have made nice progress for a first paper on this topic, providing first upper and lower bounds for architectures, and tight bounds in the polynomial setting.

Thanks for your time and consideration,

The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.