LexiCan: Lexicographic Canonicalization of Point Clouds for Machine Learning Applications

arXiv:2610.15171 · cs.LG · Submitted 2026-10-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "LexiCan: Lexicographic Canonicalization of Point Clouds for Machine Learning Applications".

Jane: The gist LexiCan introduces a lexicographic canonicalization method for labeled 3D point clouds that provides a provable canonical representative under permutation and either SO(3) or O(3) transformations,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we’re wrapping up on LexiCan, looking at the paper "LexiCan: Lexicographic Canonicalization of Point Clouds for Machine Learning Applications". It’s this method that uses a lexicographic ordering to make three-dimensional labeled point clouds canonical under rotations or reflections, and it beats ASUN in speed.

Jane: Yeah, the authors did something pretty smart by proving that this specific ordering works using those circular words and least cyclic shifts idea. What does that actually mean for someone building models?

Lu: It means we can get a provable representative of the point cloud under groups GSO3 or GO3 without having to guess how to find the best one manually. It’s a mathematically sound construction.

Meng: I care about deployment cost, though, and the runtime is O of n squared in the worst case, which is okay for training but we need fast inference when we run into a lot of data points.

Lalam: What matters is that it avoids those big jumps or failures you see with PCA-based methods when you change the orientation slightly. The mean errors they got on QM9 were around ten to the negative six Å, which is pretty tight for geometry.

Tom: That precision is what sells it for me. And I’m still looking at that runtime comparison against ASUN; a factor of one hundred or five thousand speedup sounds huge when you’re dealing with large datasets.

Jane: It really does improve things for non-invariant architectures, which is where most real-world data lives anyway. So, the big picture here is taking a representation method that used to be shaky and making it solid and fast for actual use cases.

Lu: Exactly. The paper shows that you can get high precision invariance on complex structures by using this specific sorting rule based on label rarity ranks. It’s a concrete construction, not just an empirical trick.

Meng: If we can trust the canonical form to be stable, it makes our downstream classification models much more robust against minor data noise or slight variations in how the cloud was captured. That robustness is what I need for production.

Tom: Yeah, so LexiCan isn't just another benchmark result; it’s a new way to represent data that gives us confidence in the input before we even feed it to the AI. It moves us away from relying on eigenvalue tricks when we need something more stable and faster.

Jane: So, once you have this canonical representation, what do you think comes next? Are there any limitations they mentioned about when this method might fall short?

Lu: They did mention that the exact construction is locally Lipschitz almost everywhere in the space of centered point clouds with fixed labels. That's a statement about its stability and regularity in those specific settings.

Jane: So the big picture here is taking a representation method that used to be shaky and making it solid and fast for actual use cases. If this construction holds up across all kinds of labeled data, it could fundamentally change how we preprocess three dee data for deep learning models.

Conclusion: Tom: So we’re wrapping up on LexiCan, looking at the paper "LexiCan: Lexicographic Canonicalization of Point Clouds for Machine Learning Applications". It’s this method that uses a lexicographic ordering to make three-dimensional labeled point clouds canonical under rotations or reflections, and it beats ASUN in speed.

Meng: From a deployment standpoint, I’m interested in how stable this construction is when we use real-world data that isn't perfectly symmetric, because that’s where most of our models will see things break.

Jane: It really does improve things for non-invariant architectures, which is where most real-world data lives anyway. So the big picture here is taking a representation method that used to be shaky and making it solid and fast for actual use cases.

Jane: So once you have this canonical representation, what do you think comes next? Are there any limitations they mentioned about when this method might fall short?

Lu: They did mention that the exact construction is locally Lipschitz almost everywhere in the space of centered point clouds with fixed labels, which is a statement about its stability and regularity in those specific settings.

Tom: Right, so it’s not perfect everywhere, but it’s regular enough to be predictable. We still have to worry about how much data we need to prove that regularity holds across the whole distribution of inputs.

Daniel Sanchez, Djordje Mihajlovic, Federica Valeau, Luka Benić, Raghuwansh Raj, Soutrik Sarangi

Imperial College London University of Edinburgh AMLab University of Amsterdam Ruđer Bošković Institute University of Zagreb University of Luxembourg Microsoft Research India Technion Israel Institute of Technology

cs.LG

Submitted: 2026-10-10

Updated: 2026-10-10

Code: https://github.com/Utah-Math-Data-Science/alignment

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist LexiCan introduces a lexicographic canonicalization method for labeled 3D point clouds that provides a provable canonical representative under permutation and either SO(3) or O(3)

Key concepts

Lexicographic Canonicalization: This is a method that organizes labeled 3D point clouds by sorting them according to a specific set of rules. These rules involve sorting based on the rarity ranks of each label and breaking ties using the order of the label set. This systematic ordering guarantees that two clouds considered identical under rotation will always be represented in the exact same canonical form.
Provable Canonicalization: The method's correctness is mathematically proven through specific lemmas and theorems (Lemma 1, Theorem 2, and Theorem 3). It proves that the construction correctly handles transformations under groups like GSO3 = Sn × SO(3) and GO3 = Sn × O(3), ensuring the resulting canonical form is truly invariant under these geometric operations.
High-Precision Invariance: LexiCan achieves very small error margins when comparing point clouds, specifically reaching mean invariance errors of about 10^-6 Å on the QM9 dataset. This level of precision is significantly better than PCA or ASUN methods, meaning the resulting canonical representation is highly accurate and stable across different configurations.
Runtime Efficiency: The algorithm has a worst-case runtime complexity of O(n^2 log n). While this might seem high, empirical testing shows LexiCan is much faster than ASUN, often 130 to 5,400 times faster on ModelNet40 and significantly faster on QM9. This makes the method practical for large-scale machine learning applications.

Terminology

Point Clouds — 1× in this paper · explained in 2 episodes

Summary

The gist LexiCan introduces a lexicographic canonicalization method for labeled 3D point clouds that provides a provable canonical representative under permutation and either SO(3) or O(3) transformations, while achieving high-precision invariance and a substantially improved runtime over ASUN. This method is important because it avoids the invari-ance failures and discontinuity jumps observed in PCA- and ASUN-based approaches, while improving downstream performance for non-invariant architectures.

Provable Canonicalization

LexiCan constructs a provable canonicalization for labeled point clouds under groups GSO3 = Sn × SO(3) and GO3 = Sn × O(3), using circular words and least cyclic shifts, proving its correctness in Lemma 1, Theorem 2, and Theorem 3 The construction involves sorting points by their rarity ranks based on the count of points carrying each label, with ties broken by the order of the label set A.

Efficient Implementation

The algorithm is efficient with a worst-case runtime complexity of O(n squared log n) (see Theorem 4 in Appendix C) However, empirically, across the evaluated input sizes, LexiCan is faster than ASUN by a factor of 130 to 5,400 on ModelNet40 and of 6 to 22 on QM9.

High-Precision Invariance

On the QM9 dataset, LexiCan achieves mean invariance errors of 10-6 Å, four to five orders of magnitude lower than those of PCA- and ASUN-based canonicalizations (0.89 and 0.04 Å on molecules of rank 3). Furthermore, it shows no jumps on any of the 82 pilot geometries (see Table 4).

Robustness and Stability

LexiCan’s exact construction is locally Lipschitz almost everywhere in the space of centered point clouds with fixed labels (Theorem 1) This establishes generic local regularity and it assesses stability on molecular configurations specifically through our perturbation experiments. In Table 4, LexiCan shows no jumps on any of the 82 pilot geometries.

End-to-End Learning Performance

In the classification of 3D point clouds using ModelNet40, LexiCan produces overall best accuracy of 37.1% across architectures Specifically, for non-invariant models, LexiCan beats ASUN for 4/4 non-invariant models and produces overall best accuracy of 37.1% across architectures.

Tolerance Threshold Dependence

LexiCan treats as equal two lengths within ηR of each other (R the largest distance from the centroid) and two angles within η radians, so that one tolerance means the same on clouds of any size The mean EMD for LexiCan stays within the 0.1 Å threshold on every molecule in QM-sym (mean EMD 2×10-7 Å), while the baselines do not.

Perturbation Across Symmetric Polyhedra

In Table 14, LexiCan shows 0 clouds with invariance errors (the ‘Not invariant’ column in the table below) against 18/18 and 6/17 for baselines The p95 amplification rate of the worse version of LexiCan is 30 times smaller than the best baseline.

Machine Dependence of PCA

The PCA values in Tables 4 and 5 were computed on an Intel Xeon Gold 6336Y CPU with NumPy 2.5.3 (OpenBLAS 0.3.34) They may differ on other machines, since PCA’s eigenbasis at repeated eigenvalues is set by floating-point rounding, which depends on the processor’s linear-algebra kernels (for example, 5,680 instead of 5,301 discontinuities on the CH4 stretch on an Intel Xeon 6710E).

Conclusion

In this work, we introduced LexiCan, a lexicographic canonicalization method for labeled 3D point clouds that provides a provable canonical representative under permutation and either SO(3) or O(3) transformations, while achieving high-precision invariance and a substantially improved runtime over ASUN. This method is important because it avoids the invari-ance failures and discontinuity jumps observed in PCA- and ASUN-based approaches, while improving downstream performance for non-invariant architectures.

--- Page 1 ---

LexiCan: Lexicographic Canonicalization of Point Clouds

Improvements for AI systems

The improved system can perform geometric tasks on 3D point clouds with provable invariance under GSO(3) and GO(3) transformations by using LexiCan, which is provably invariant under either O(3) or SO(3) and satisfies C SO 2(g · P) = C SO 2(P), ∀g ∈ GSO 2 and C O 3(·) ∈ GO 3 · P.
The system can achieve superior performance in molecular property prediction, as demonstrated by the result that LexiCan achieves the lowest error and improves on ASUN on every seed in QM9 isotropic polarizability prediction (Table 7).
The system can be deployed for 3D shape classification using non-invariant architectures, as LexiCan beats ASUN for 4/4 non-invariant models and produces overall best accuracy of 37.1% across architectures on ModelNet40 (Table 8).
The system can operate robustly in real-world scenarios with controlled perturbations; specifically, it maintains invariance against significant geometric changes, as LexiCan shows no jumps on the pilot set and has a lower flip rate than baselines in Table 6 for QM-sym molecules.
The system can be utilized for training models on unlabeled or non-invariant representations by leveraging LexiCan's ability to provide a consistent reference frame, as shown by the finding that LexiCan beats ASUN for 4/4 non-invariant architectures in shape classification (Table 8).
The system can be optimized for faster inference on large point cloud datasets; empirically, LexiCan is faster than an existing canonicalization by factors ranging from ∼ 130 to ∼ 5,400 on ModelNet40.

Abstract

Canonicalization resolves the rotational and permutation ambiguity of 3D point clouds by selecting a unique orbit representative, maintaining their geometric information while allowing standard architectures, such as Transformers, to operate on them. Existing canonicalizations, however, exhibit discontinuity jumps on molecular configurations and non-trivial invariance errors in popular molecular datasets, which lead to ambiguity in their representation. To bridge this gap, we introduce LexiCan, a canonicalization that is provably invariant under either O(3) or SO(3), empirically invariant to rotations to within about 10-6 angstroms on the QM9 and QM-sym molecular datasets, and mitigates discontinuity jumps on QM-sym, while running orders of magnitude faster than an existing canonicalization. Finally, non-invariant models perform better on QM9 property prediction and ModelNet40 shape classification with LexiCan than with that canonicalization.