Abstract
Permutation equivariance is a critical inductive bias for processing data where the order of elements is arbitrary. While well-studied for sets and graphs, symmetric tensors—higher-dimensional arrays where index order is invariant—have lacked a complete characterization of equivariant linear maps. This work provides a mathematical foundation for such maps using combinatorial bipartitions and introduces "Map Label Notation." This symbolic approach bypasses the memory bottlenecks of explicit weight matrices and allows models to generalize to tensors of varying sizes. Empirical results demonstrate superior accuracy, massive speedups, and robust zero-shot generalization.
Introduction
Symmetry serves as a powerful inductive bias in machine learning, ensuring that if input coordinates are shuffled, the output shuffles accordingly. While equivariant models for sets (Deep Sets) and graphs (GNNs) are established, symmetric tensors (e.g., $T_{i,j,k} = T_{j,i,k}$) present unique challenges. Previous research often focused on Euclidean symmetries or suffered from memory-intensive implementations that scale poorly with tensor order $k$ and dimension $n$. This paper addresses these gaps by characterizing all linear permutation-equivariant functions for symmetric tensors and providing a computationally efficient implementation strategy.
Methods
The authors derive two bases for linear permutation-equivariant functions between symmetric power spaces: the Orbit Basis and the Diagram Basis. These are grounded in the combinatorial theory of MacMahon’s $(k, l)$-bipartitions.
Diagrammatic Representation
Equivariant maps are visually represented using diagrams of "spiders" (nodes) and "wires" (indices). This visualization helps in understanding how indices are fused or partitioned during transformations.
Map Label Notation
A key technical contribution is Map Label Notation. Instead of explicitly constructing a weight matrix, which can grow exponentially, the authors represent transformations as symbolic indexing rules. This allows for vectorized operations directly on input tensors, significantly reducing memory overhead.
By using these symbolic rules, the learned parameters become independent of the input dimension $n$, enabling "size-agnostic" transfer learning.
Results
The proposed "SymmPermEquiv" model was evaluated on synthetic tasks requiring invariant and equivariant properties.
- Accuracy: In a diagonal extraction task ($S_8$-Equivariant), the model achieved a Test MSE of 0.0035, vastly outperforming standard MLPs (0.6486) and general equivariant models (0.0447).
- Efficiency: Map label notation yielded a 60x speedup on invariant tasks and a 200x speedup on equivariant tasks compared to explicit matrix methods.
- Generalization: Models trained on $n=8$ dimensions maintained high accuracy when tested on $n=16$ and $n=32$ without retraining.
Conclusion
This work bridges deep learning with classical combinatorics to provide a complete framework for symmetric tensor equivariance. By moving from explicit weight matrices to symbolic map labels, the authors enable efficient, scalable, and generalizable models. Future work includes extending this logic to non-symmetric tensors and applying these layers to real-world domains like fluid dynamics and brain connectomics.
Summary updated