CS Paper Radar

A Complete Geometric Message-Passing Architecture for Point Clouds

Nadav Dym, Tal Amir, Gia Chi Dang, Christopher Morris

cs.LG ·submitted 2026-11-19 16:40 UTC · v1

Abstract

Three-dimensional point clouds are a fundamental data modality, and a large family of machine learning architectures has been developed to respect their natural symmetries to rigid motions and permutations. A principled way to compare these architectures, which vary widely in complexity and cost, is through their expressive power. That is, an architecture is complete if it can distinguish any two inputs not related by the symmetries it respects. Simple distance-based message-passing networks are known to be incomplete, and while there exist complete alternatives, they typically rely on computationally intensive mechanisms like high-order representations of the rotation group or higher-order Weisfeiler-Leman-type tests. In this work, we devise a novel, simple, equivariant message-passing architecture for point clouds, and prove that it is complete. We complement our theoretical result with experiments showing that our architecture separates challenging point clouds that distance-based message passing provably cannot distinguish. Our results suggest that high-order equivariant features may not be necessary to enhance the expressivity of point cloud architectures, and can help settle completeness for other equivariant architectures for which such results are currently unknown. We give initial evidence for this by proving completeness of a slightly modified version of SEGNN.

Comment
44 pages, 4 figures, 4 tables. Ancillary files: exact-arithmetic verifier, certificate and companion notebook for the Platonic color-atom computation

Closest papers

Nearest neighbours by meaning across the whole index.

Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds

cs.LG math.AC ·2026-10-19 ·Snir Hordan, Harm Derksen, Mircea Petrache, Nadav Dym
similarity 0.75
Abstract · 34 pages, 2 figures

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.

0.28

How Do Transformers Learn to Represent Symmetries?

cs.LG ·2026-10-07 ·Eduardo Santos-Escriche, Valerie Engelmayer, Ya-Wei Eileen Lin, Stefanie Jegelka
top venuecode/datahot direction similarity 0.65
Abstract · Accepted at NeurIPS 2026

Training Transformer-based architectures with finite data augmentation has become an increasingly popular approach in geometric machine learning. Despite its empirical success, the interplay between the Transformer architecture, invariance to different symmetries, and augmentation budgets remains underexplored. In this paper, we study the ability of a vanilla Transformer to learn various symmetries through finite data augmentation for point cloud datasets. We identify an ordering of increasing learnability across the following symmetry groups: (i) non-angle-preserving symmetries, (ii) angle-preserving symmetries, and (iii) base angle-preserving subgroups, such as translation, rotation, and scale. For the base angle-preserving groups, we further investigate the Transformer's extrapolation behavior and conduct a structural analysis of the trained models, allowing us to identify interpretable mechanisms that induce invariance. Finally, we extend our analysis to equivariant functions and show that the detected mechanisms for approximate invariance can also provide a key building block for learned equivariance. Our project page is available at https://transformers-learn-symmetries.github.io/

0.55

Do We Still Need Rotation-Invariant Architectures? A Statistical Robustness Benchmark for Point Cloud Classification

cs.CV cs.LG ·2026-11-02 ·Abdulla Nasir Chowdhury, Gulpi Qorik Oktagalu Pratamasunu, Kazuhiro Fukui
publishedbenchmark similarity 0.65
Abstract · Accepted to 2nd Round of WACV 2027, 24 pages (8 main + appendix). Website: https://abdullah-nasir-chowdhury.github.io/projects/wacv2027/

A substantial line of work builds rotation invariance directly into point cloud architectures. We benchmark 10 architectures (PointNet, PointNet++, DGCNN, RIConv, RIConv++, RISurConv, PointMLP, PointTransformer, and the equivariant VN-PointNet and VN-DGCNN) across 5 domains under pose, noise, and occlusion, and analyze the results with confirmatory hypothesis tests rather than point estimates. The three rotation-invariant (RI) architectures achieve the best pose robustness but rank among the lowest on noise robustness in 4 of 5 domains. We ask whether this cost is intrinsic to invariance or specific to how invariance is obtained. We retrain all 10 architectures unchanged, with a simple invariance loss on the embedding and three training seeds each, and evaluate all models on the independently designed ModelNet40-C. Invariance training transfers narrowly but reliably. It improves exactly the corruption families its perturbations target wherever the baseline has headroom (mean occlusion +10.5, lidar +13.4 percentage points of accuracy). At matched training budget the best standard backbone and the best RI architecture end on par on unseen corruptions (within 2.5 percentage points in every seed), and invariance-trained RIConv++ is the most seed-stable top model. Once rotation augmentation is widened, standard backbones concede only a flat, angle-independent accuracy offset under full-sphere rotation. We release the benchmark along with a package for analyzing point cloud robustness and reproducing our results.

0.51

LexiCan: Lexicographic Canonicalization of Point Clouds for Machine Learning Applications

cs.LG ·2026-10-10 ·Daniel Sanchez, Djordje Mihajlovic, Federica Valeau, Luka Benić, Raghuwansh Raj +2 more
similarity 0.63
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 $\sim 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.

0.25

Rotational Equivariance in Machine Learning: A Comprehensive Tutorial

cs.LG ·2026-08-31 ·Peter Lippmann, Fred A. Hamprecht
similarity 0.62
Abstract

Rotational symmetry is one of the most important structural principles in machine learning on 3D data. In applications ranging from physics and materials science to 3D computer vision, predictions should not depend on an arbitrary choice of coordinate frame. Rotational equivariance captures this requirement mathematically by enforcing that a rotation of the input induces a corresponding transformation of the model output. This tutorial provides a comprehensive introduction to rotational equivariance, starting from the physical and geometric intuition behind coordinate independence and building up the necessary machinery from geometric deep learning, group theory, and representation theory. We introduce message passing on Euclidean graphs, group actions and representations, spherical harmonics, Wigner matrices, tensor products, and Clebsch-Gordan decomposition, and explain how these ingredients give rise to modern equivariant architectures. We then survey the principal strategies for incorporating rotational equivariance in deep learning, including group convolutions, internal tensorial representations, and canonicalization-based methods, and discuss their practical strengths and limitations. The tutorial aims to lower the barrier to the subject by connecting the underlying mathematics to practical model design, by unifying ideas that are often expressed in different formal languages, and by helping practitioners choose among competing approaches through a clear discussion of their trade-offs.

0.11

Improving fine-grained expressivity of graph neural networks

cs.LG cs.AI ·2026-11-15 ·Yonatan Sverdlov
similarity 0.62
Abstract

This thesis investigates the expressive power of neural networks for structured data, focusing on graph neural networks and symmetry-aware architectures. We present four main contributions. First, we characterize the generic expressive power of geometric message-passing neural networks on sparse graphs and introduce EGenNet, an architecture achieving the corresponding guarantees. Second, we use representation theory to characterize linear layers equivariant to multiple permutations, including wreath-product symmetries. Third, we study permutation-invariant set representations that preserve containment, establish dimensional bounds and impossibility results, and introduce MASNet. Finally, we propose FSW-GNN, a message-passing architecture combining strong expressivity and bi-Lipschitz stability guarantees with strong empirical performance on long-range graph-learning tasks. Together, these results provide a broader understanding of how neural architectures can preserve the geometric, algebraic, order-theoretic, and metric structure of their inputs.

0.09

TokenFlow: Latent Token Rectified Flow Matching for 3D Point Cloud Generation

cs.CV ·2026-10-20 ·Linhao Wang, Dongjin Huang
similarity 0.61
Abstract

3D point clouds generation requires capturing both part-level layout and surface detail while preserving permutation equivariance. Existing latent generative models often encode an entire shape into a single vector, which limits their ability to retain part-level structure. We propose TokenFlow, a hierarchical flow matching framework that represents each shape as a set of latent tokens and couples a rectified flow over these tokens with a conditional flow over points. A bottleneck of $M \ll N$ learnable tokens aggregates global context through cross-attention at $O(NM)$ cost. On ShapeNet, TokenFlow achieves the best MMD and coverage across airplane, car, and chair, while obtaining 1-NNA comparable to the strongest baselines. On ModelNet, its learned latent set reaches the best reported linear-evaluation accuracy on ModelNet10. These results show that representing a shape as a set of latent tokens, aggregated at $O(NM)$ cost, provides an effective representation for 3D point cloud generation.

0.07

SIEVE: Overcoming Topological Obstruction in Equivariant Self-Supervised Learning

cs.LG cs.AIcs.CV ·2026-10-15 ·Jongann Lee, Sun Woo Park, Yun Young Choi
publishedtheory similarity 0.60
Abstract · The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS) 2026

We identify a theoretical incompatibility between 3D point cloud masked autoencoding and SE(3)-equivariant networks. We prove that standard masking triggers a topological collapse, effectively forcing the model to hallucinate orientation without a reference frame. To resolve this, we introduce SIEVE (Scalar Invariant Extraction Via Equivariance), an SE(3)-equivariant self-supervised framework that compresses point cloud geometry into invariant scalar embeddings. At its core is the spherical projection mask, which preserves global pose while obfuscating local semantics, sidestepping the obstruction by construction. Experiments confirm that SIEVE circumvents the predicted collapse where constant and noise masks fail. On downstream point cloud tasks, the resulting embeddings improve over coordinate-based baselines and hand-crafted geometric descriptors, with the largest gains on generalization to unseen shape categories.

0.26