CS Paper Radar

Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds

Snir Hordan, Harm Derksen, Mircea Petrache, Nadav Dym

cs.LG math.AC ·submitted 2026-10-19 15:47 UTC · v1

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

Comment
34 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Improving fine-grained expressivity of graph neural networks

cs.LG cs.AI ·2026-11-15 ·Yonatan Sverdlov
similarity 0.61
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.11

Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks

cs.LG math.ACmath.AG ·2026-08-27 ·Kathlén Kohn, Giovanni Luca Marchetti, Alex Massarenti, Massimiliano Mella
theoryhighly cited similarity 0.59
Abstract

Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.

0.43

Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks

cs.LG math.ACmath.AG ·2026-09-11 ·Sepehr Akbari, Shahrzad Jamshidi
similarity 0.58
Abstract · 9 pages, 1 figure

We study exact representability by bias-free shallow polynomial neural networks using algebraic geometry. Over $\mathbb{C}$, a width-$r$ network with activation $z\mapsto z^d$ computes a sum of $r$ $d$-th powers of linear forms, whose Zariski closure is a Veronese secant variety. Ideal elimination therefore yields polynomial certificates of nonrepresentability. We implement this construction as a generic architecture-to-certificate pipeline. For quadratics, we recover the exact symmetric determinantal description and explain its dimension through orthogonal symmetry. In higher degree, the implementation recovers classical catalecticant and secant equations and maps the practical reach of direct elimination across a finite architecture sweep. We also derive the exact population loss floor for a rank-two quadratic network on the sphere, illustrating how an algebraic obstruction induces irreducible approximation error.

0.22

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

cs.LG math.PRstat.ML ·2026-10-06 ·Jivan Waber, Vanessa Piccolo, Yatin Dandi, Florent Krzakala
theory similarity 0.58
Abstract · 71 pages, 3 figures

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in $\mathbb{R}^d$ and $r=Θ(d^δ)$ teacher directions forming a cyclic symmetry orbit, where $0<δ<1/2$. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent $p\ge3$, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in $\widetildeΘ(d^{p-1})$ samples, whereas the symmetry-agnostic learner requires $\widetildeΘ(rd^{p-1})$. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities $\widetildeΘ(d)$ and $\widetildeΘ(rd)$, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For $p\ge3$, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

0.56

On Making $\mathrm{SE}(2)$-Invariant Networks Optimal

cs.LG cs.AI ·2026-10-12 ·Tomas Karella, Emily Shinkle, Alice Elisabeth Anastasia Allen, Pieter J. Swart, Nicholas Lubbers +1 more
top venue similarity 0.57
Abstract · Accepted to the main track of NeurIPS 2026

Respecting a-priori known symmetries of underlying data is a key principle in designing efficient neural architectures. Convolutional neural networks are a canonical example, encoding translation equivariance. Extending this inductive bias to richer symmetry groups such as $\mathrm{SE}(2)$ in the most effective way possible is an ongoing architectural and computational challenge. Building on classical invariant theory, we derive invariant feature maps that are provably optimal: minimal and information-preserving with respect to the symmetry group. Our construction is designed to integrate seamlessly into standard architectures, requiring no modification to nonlinearities or normalization layers. As a concrete implementation, we introduce a plug-and-play module for convolutional neural networks that enforces $\mathrm{SE}(2)$ invariance, capturing both translations and rotations within standard architectures. The resulting models are both efficient and expressive. Experiments show competitive or improved accuracy compared to state-of-the-art equivariant methods at significantly lower computational cost. Finally, we provide a theoretical and empirical analysis of the relationship between equivariance and invariance, offering insight into their roles in controlling robustness and flexibility.

0.34

Memorization Capacity of Invariant Convolutional Neural Nets

cs.LG stat.MLmath.ST ·2026-10-28 ·Sjoerd Dirksen, Patrick Finke, Paul Geuchen
theory similarity 0.56
Abstract

Neural networks are powerful memorizers which are often able to interpolate their training data even when the labels have been randomized. While there exists an extensive literature on the memorization capacity of fully connected networks, in practice more specific architectures with problem-dependent properties are preferred, such as convolutional networks for image classification. In this paper we consider convolutional networks which are invariant with respect to a given arbitrary finite group of orthogonal transformations, which may include translations, reflections, and/or rotations of images and invariances of higher order tensors. We prove upper bounds on the size of an invariant convolutional neural network with threshold activations that is required to interpolate a given dataset with two classes. Our bounds are formulated in terms of a complexity measure that takes the invariant structure into account and is instance-specific, i.e., it is related to the mutual arrangement of the classes in the given dataset and their geometric properties rather than the number of samples. Our proof is constructive: for given input data, instances of an interpolating network can be computed via a randomized algorithm with high probability. In numerical experiments we investigate the practical effectiveness of this algorithm.

0.30

Graded Representation Theory of Equivariant Neural Networks

cs.LG math.RT ·2026-09-22 ·Mani Shayestehfar
similarity 0.56
Abstract · 33 pages, comments welcome

Nonlinear activations can create equivariant interactions between irreducible representations that linear maps cannot. We use the Gaussian degree decomposition to extend ordinary polynomial degree to such nonlinear maps, and prove that for a fixed coordinatewise equivariant layer each degree factors into a polynomial determined by the linear maps and a scalar determined by the activation. This separates three distinct obstructions, coming from symmetry, coordinates, and activation.

0.46

Reducing Symmetry Increase in Equivariant Neural Networks

cs.LG ·2026-08-12 ·Ning Lin, Jiacheng Cen, Anyi Li, Wenbing Huang, Hao Sun
top venuetheory similarity 0.56
Abstract

Equivariant Neural Networks (ENNs) have empowered numerous applications in scientific fields. Despite their remarkable capacity for representing geometric structures, ENNs suffer from degraded expressivity when processing symmetric inputs: the output representations are invariant to transformations that extend beyond the input's symmetries. The mathematical essence of this phenomenon is that a symmetric input, after being processed by an equivariant map, experiences an increase in symmetry. While prior research has documented symmetry increase in specific cases, a rigorous understanding of its underlying causes and general reduction strategies remains lacking. In this paper, we provide a detailed and in-depth characterization of symmetry increase together with a principled framework for its reduction: (i) For any given feature space and input symmetry group, we prove that the increased symmetry admits an infimum determined by the structure of the feature space; (ii) Building on this foundation, we develop a computable algorithm to derive this infimum, and propose practical guidelines for feature design to prevent harmful symmetry increases. (iii) Under standard regularity assumptions, we demonstrate that for most equivariant maps, our guidelines effectively reduce symmetry increase. To complement our theoretical findings, we provide visualizations and experiments on both synthetic datasets and the real-world QM9 dataset. The results validate our theoretical predictions.

0.64