Discovering Group Structures via Unitary Representation Learning
Authors: Dongsung Huh
Venue: ICLR 2025 Poster (2025)
Keywords: group theory
representation theory
representation learning
symmetry discovery
symbolic relationship
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Discovering group structures within data poses a fundamental challenge across diverse scientific domains. A key obstacle is the non-differentiable nature of group axioms, hindering their integration into deep learning frameworks. To address this, we introduce a novel differentiable approach leveraging the representation theory of finite groups. Our method features a unique network architecture that models interactions between group elements via matrix multiplication of their representations, along with a regularizer promoting the unitarity of these representations. The interplay between the network architecture and the unitarity condition implicitly encourages the emergence of valid group structures. Evaluations demonstrate our method's ability to accurately recover group operations and their unitary representations from partial observations, achieving significant improvements in sample efficiency and a $\times 1000$ speedup over the state of the art. This work lays the foundation for a promising new paradigm in automated algebraic structure discovery, with potential applications across various domains, including automatic symmetry discovery for geometric deep learning.

Published as a conference paper at ICLR 2025
DISCOVERING GROUP STRUCTURES VIA UNITARY REPRESENTATION LEARNING
Dongsung Huh IBM Research huh @ 8ibm. com
ABSTRACT
Discovering group structures within data poses fundamental challenge across di- verse scientific domains. A key obstacle is the non-differentiable nature of group axioms, hindering their integration into deep learning frameworks. To address this, we introduce a novel differentiable approach leveraging the representation theory of finite groups. Our method features unique network architecture that models interactions between group elements via matrix multiplication of their rep- resentations, along with regularizer promoting the unitarity of these representa- tions. The interplay between the network architecture and the unitarity condi- tion implicitly encourages the emergence valid group structures. Evaluations demonstrate our method's ability to accurately recover group operations and their unitary representations from partial observations, achieving significant improve- ments in sample efficiency and x x1000 speedup over the state of the art. This work lays the foundation for promising new paradigm in automated algebraic structure discovery, with potential applications across various domains, including automatic symmetry discovery for geometric deep learning.
INTRODUCTION
Identifying algebraic structures, particularly groups, has been cornerstone of progress across di- verse scientific fields. In mathematics, groups formalize the concepts of symmetry and transfor- mation, underpinning abstract algebra, geometry, topology, and number theory. In physics, group theory is indispensable for understanding the fundamental laws of nature, from classifying elemen- tary particles to formulating quantum field theory. Within computer science, groups play key roles in cryptography, coding theory, and algorithm design. Furthermore, in deep learning, group theory informs the design of symmetry-aware architectures (e.g., convolutional and equivariant neural net- works), enhancing parameter efficiency, generalization, and enabling applications on non-Fuclidean domains (Bronstein al. 2021).
Despite their profound significance, uncovering group structures within data remains a significant challenge, traditionally requiring substantial domain expertise and human intuition. A key obstacle is the inherent non- differentiability of the defining criteria for groups - the group axioms which impedes their direct integration into gradient- based learning frameworks. In this work, we introduce novel method for automatically discovering groups and their unitary representations, leveraging the representation theory of finite groups. Our approach uses novel network architecture that models interactions between group elements through the product of their matrix representations, along with a regularizer promoting their unitarity. This interplay naturally encourages the emergence of valid group structures, without direct evaluation of the non-differentiable group axioms.
This work demonstrates the effective embedding of fundamental group structure criteria within the differentiable learning framework, paving the way for automated discovery of algebraic structures.
GROUPS AND REPRESENTATIONS
Algebraic structures sets endowed with operations satisfying specific axioms offer powerful framework for studying abstract mathematical objects and their interactions. Among these struc- tures, groups are foundational building blocks of abstract algebra, underpinning the construction of

---

Published as a conference paper at ICLR 2025
more complex entities like rings and fields. Furthermore, the well-established theory of group repre- sentations provides a crucial tool for analyzing group structures by mapping their abstract properties to the concrete domain of linear algebra. In this section, we present a concise overview of groups and their representations, emphasizing key concepts pertinent to our work.
Groups A group (G, o) is G with a binary operation o that satisfies four axioms: Closure: Va,b b E G, a b b E G. Associativity: (a o b) o = a (bo c). Identity: There exists an identity element E G such that for all g G. g o coo = g. Inverse: For every g E G, there exists unique inverse element g such that g go = g o g =
Representations A representation of group (G, o) on a vector space a group homomorphism g: G + GV) that preserves the group structure: i.e.
e 92) = e(g))
Vg,, 92 E G.
In essence, it maps each group element to an invertible linear transformation on the vector space, en- suring that the composition of transformations mirrors the group operation. For finitedimeensionll vector space of dimension we can choose basis to identify GL(V) as GL(n, K), the group of n X n invertible matrices over the field K.
Unitary Representations A representation e of group (G, o) is called unitary if for every g E G, e(g) is a unitary transformation, i.e. preserves the inner product. This property makes unitary representations particularly well-hehaved and amenable to analysis. Notably, the Unitarity Theorem guarantees that for many important classes of groups, such as compact and finite groups, every finite-dimensional representation is equivalent to unitary one. Unitary representations naturally arise in the study of quantum systems, and have deep connections to other areas of mathematics, e.g., harmonic analysis and operator algebras.
Irreducible Representations A representation is considered reducible if it can be decomposed into a direct sum of smaller representations via similarity transform, leading to block-diagonal matrix form where each block corresponds to a simpler representation. Irreducible representations (irreps), on the other hand, cannot be further decomposed and serve as the fundamental building blocks for constructing all possible group representations.
Regular Representations Every group (G, o) possesses an inherent action on itself that can be viewed as permutation, where each group element rearranges the other elements. The regular representation uses the permutation's basis vectors to construct a linear representation. It is decom- posible into direct sum of the complete set of irreps, where each irrep appears with a multiplicity equal to its dimension. Moreover, its trace, also known as character, is a simple function:
Tr(e(g)) if e, 0 otherwise.
Real vs Complex Representations Complex representations (K = C) provide a rich mathemati- cal framework for analyzing group structures in representation theory. We utilize this framework to establish the theoretical foundations of our approach in Sections[fandd However, for finite groups, real representations (K = R) often suffice in practice offering advantages in implementation and visualization. Our empirical results in Sections and
thus utilize real representations.
3 BACKGROUND
Binary Operation Completion In this study, we adopt the Binary Operation Completion (BOC) problem (Power al. 2022) as our experimental setting. BOC entails completing the Cayley table of a binary operation over finite set of abstract symbols. This problem isolates the fundamental challenge of discovering group structures solely from interactions between elements, eliminating the confounding influence of extraneous factors. Consequently, BOC provides crucial theoretical framework for analyzing structure learning within the discrete symbolic domain, serving role analogous to that of matrix completion in the continuous domain.
For finite groups, every complex representation can be realized over the real numbers with doubling of the dimension.
2

---

Published as a conference paper at ICLR 2025
C
Aa
Bb
B
Figure I: Illustration of matrix and tensor products. Nodes are factors and edges are indices. (Left)
Matrix product. (Middle) Matrix product with trace operation. (Right) HyperCube product.
Matrix Completion Matrix completion aims infer missing entries of partially observed ma- trix, assuming an underlying low-rank structure. Classical methods typically enforce this assump- tion by either imposing explicit rank constraints (Burer and Monteiro (2003] by minimizing the nuclear norm as a convex proxy for rank (Fazel et al. 2001; Candès and Recht 2009, Recht et al., 2010 Candes and Tao 2010). Matrix completion provides theoretical Foundation for numerous applications, spanning recommender systems, data imputation, compressed sensing.
Implicit Complexity Metric Recent research has revealed that deep matrix factorization net- works, when regularized with L2 regularization (or initialized with small weights), implicitly define complexity metric that approximates rank, such the nuclear norm or Schatten norm (Srebro et al. 2004 Gunasekar et al. 2017). Furthermore, these implicit approaches have demonstrated superior performance in matrix completion, especially with limited data (Arora al. 2019).
Bridging the Gap While Binary Operation Completion (BOC) shares con- ceptual similarities with matrix completion, its discrete symbolic nature poses distinct challenges. To bridge this gap, we reformulate the BOC problem into a tensor completion problem. We then propose novel solution rooted in the representation theory of finite groups: specialized tensor- factorization architecture coupled with a novel regularizer. This approach implicitly defines a com- plexity metric that acts differentiable proxy for the group criterion, thus providing a learning- based methodology for discovering group structures directly from data.
Our Contributions:
MODELING FRAMEWORK
Notations and Definitions We use the following capital symbols for order-3 tensor factors: A, B, C. A₂ denotes the matrix slice of the first index and At denotes its conjugate transpose. Br denotes the matrix product of A, and B₁. Einstein convention is used throughout, where repeated index implies contraction: e.g. A. A En A, unless otherwise specified.
4.1 LINEARIZED FRAMEWORK: BINARY OPERATIONS AS BILINEAR MAPS
Consider binary operation S + S over finite set S containing n elements: i.e. aob c, where a, 0, e E S. To facilitate modeling, we linearize the problem by considering a homomorphism 6: (S, o) + (V, D), where V is vector space and D V x V + V is bilinear map over V. such ő(a b). Concretely, by choosing the vector space V = C with a basis (for instance, encoding each element one-hot vector), the bilinear map D be represented by an order-3 tensor D E C whose entries are
that ((o(a), (b))
Date if 0 otherwise.
where the elements of are used as tensor indices for clarity. Hereafter, we will use D to denote the ground-truth data tensor be learned by the model.
The linearized framework reveals that any binary operation over a finite set can be fully modeled by bilinear map, equivalently. by its tensor representation. Crucially, this framework transforms BOC into a tensor completion problem, where we recover the missing entries of from the observed entries in the training set.
3

---

Published as a conference paper at ICLR 2025
4.2 HYPERCUBE PARAMETERIZATION
To solve the tensor completion problem, we train a model tensor T to recover the data tensor D. However, treating the entries of T independent model parameters would prevent the model from leveraging the structural relationships between observed and unobserved entries, limiting its ability to generalize.
To address this, we introduce HyperCube factorization (Fig. D. structured parameterization that factorizes the model tensor as a product of three order-3 factors (i.e. cubes) A, B, C CuXXxa
1 Tr(A. 1 Σ
Tabe n
Aaki MaaiBusceett
(4)
agk
This architecture employs matrix embeddings to represent the elements of the set S. Factors A and B serve as embedding dictionaries, mapping each element a and to their respective matrix embed- dings: A. and Bi P The interaction between and is then modeled as the matrix multiplication: A. Factor C then acts as an unembedding dictionary, mapping the result back to the space of S.
This architecture is inspired by the representation theory of finite groups, which also employs ma- trix multiplication to model group operations (eq (I). A key advantage of this approach is that it directly encodes the associativity axiom of groups through the inherent associativity of matrix multiplication, providing a strong inductive bias for capturing group structures. In contrast, conven- tional tensor factorization methods typically use lower-order factors to reduce model complexity but lack this useful inductive bias. As a result, they are less effective at modeling group structures (see Appendix D for detailed comparison).
4.3 HyPERCUBE REGULARIZER
The model is trained by minimizing the following regularized objective:
L= C.; D) + cH C).
(5)
where C. is a differentiable loss the model tensor T (e.g.. squared error over the training data) and H is the HyperCube regularizer, which penalizes the Jacobian of T with respect to the parameters:
3T 0A
OT
OT ac
1 Tr [ALA.BBD) + B,B.C.Ct + C/CoANA!] n
H =
(6)
aB
which can be viewed as dual to standard L2 regularization: | + [B]] + |CC In subse- quent sections, demonstrate that eq (6) encourages the factors learn full-rank, unitary matrix embeddings, contrasting with L2 regularization, which promotes low-rank solutions.
The Unitarity Theorem of representation theory guarantees that for compact and finite groups, every finite-dimensional representation is equivalent to a unitary representation. Therefore, the unitarity bias of the HyperCube regularizer can leverage this theorem to promote solutions within the space of unitary matrix embeddings without loss of generality. This focused learning within relevant subspace of representations leads to faster convergence and improved sample complexity.
4.4 INTERNAL SYMMETRY OF MODEL
The over- peeepparameteiieed eq 4 implies the presence of internal symmetries that leave the model unchanged. For instance, one can introduce arbitrary invertible matrices M,, My, Mr and their in- verses between the factors as A, = Mx A₂ M,, B, = M, B, , and C. MJ*C. These yield an equivalent parameterization of T, since TTJÁ,B,CC = B.Ce)- These symmetry transformations can be understood as changing the internal basis coordinate represent the factors.
Note that while the model loss (T)) is invariant under such coordinate changes, the regularizer H(A, B, C) is not. However, the regularizer is invariant under unitary basis changes, in which the introduced matrices are unitary, such that M = M = =. Therefore, the regularizer imposes stricter form of symmetry. This leads the following Proposition.
Proposition 4.1. If A, B, C form an optimal solution of the regularized loss eq 5). then any unitary basis changes leave the solution optimal, but non-unitary busis changes generally increase the loss.
This embedding process is closely related to the generalized Fourier transform groups (See Appendix T
4

---

Published as a conference paper at ICLR 2025
A
4
3
2
2
5 0
2-
2
8
5
24
3
5
5
3-
2
5-
2
5
Figure 2:
"Multiplication" tables (i.e. Cayley tables) of small binary operations: symmetric group Sg. modular addition, subtraction, and squared addition. Elements of Sy are illustrated in Figure g
ANALYZING HYPERCUBE'S INDUCTIVE BIAS
While HyperCube eq does not explicitly restrict the model's hypothesis space, the regularizer eq 66) induces a strong implicit bias on the model. In this section, we introduce key concepts for analyzing this inductive bias. See Appendix for proofs.
Lemma 5.1 (Balanced Condition). At stationary points ofeq 5 imbalance terms vanish to zero:
Er EJ = =
where Eτ C.(C - B,(C.Ct)B. E. = (A C.(A,AA)C and EK = C CB - (B, are the imbalances across edge i, and k. respectively.
The following statements demonstrate that the regularizer promotes a unitarity condition.
Definition 5.2 (Contracted Unitarity). factor A is C-unitary if it satisfies the following: A,A,, A, Aa X (with contracting the repeated index a).
Proposition 5.3. C-unitary factors satisfy the balanced condition eq 7 given that they share common scalar multiple of the identity matrix: i.e.
AaA = At = B,B, - C.C. na?1,
(8)
Lemma 5.4. Under the fixed Frobenius norm, all C-unitary factors are stationary points of the regularizer H.
Remarkably, we also observe stronger form of unitarity in the converged solutions. Definition 5.5 (Slice Unitarity). A factor A is S-unitary if every matrix slice of A is scalar multiple of an unitary matrix: i.e. Ag = A = a²x,' I (without contracting the repeated index a). Observation 5.6. When optimizing the regularized loss eq
(5). C-unitary solutions are consistently achieved via S-unitarity, in which eq (8) reduces to E, a'. =E, az = =. a² = naa.
Although the exact mechanism driving S-unitarity remains an open question, this observation em- phasizes the strong unitarity bias induced by the HyperCube regularizer. In Section Ø we rigorously demonstrate the learning dynamics, revealing a consistent reduction in imbalance and unitarity mea- sures during optimization with HyperCube regularization. These findings compellingly suggest that unitarity is not merely byproduct, but a fundamental attribute HyperCube's 's optimal solutions.
ANALYSIS ON SMALL-SCALE BOC EXPERIMENTS
We begin with detailed qualitative analysis of how HyperCube learns small-scale binary opera- tions. First, we examine the model's learning dynamics on the group operation in S3 (Section 6. followed by analysis of the learned matrix embeddings (Section 6.2). Finally, we extend these results to other operations from Figure (Section 6.3
6.1 LEARNING DYNAMICS ON SYMMETRIC GROUP S3
Figure compares the effect different regularization strategies on the model's learning dynam- ics the symmetric group S3 with 60% of the Cayley table sampled as training data. (See also
5

---

Published as a conference paper at ICLR 2025
Loss
Accuracy
Imoalance
Unitarity
Singular Values
10"
100
Unregularizer
1.5
10-3
10
10P
50-
10
10
1.0
10-3
10-5
10
L2 regularized
100
10-4
75-
10
10P
1.0
10:2
train
50-
10
10:2
25
regularizer
10
10-5
10
0.0
300
109
10'
H regularized
100
1.0
10"1
10"4
10P
50
10
10"²
0.6
10-2
10
10a
iteration
Figure 3: Optimization trajectories on the S3 dataset with 60% training data fraction. (Top) Un- regularized, (Middle) Læ-regularized, and (Bottom) H-regularized training. Column shows the average imbalance (| + ||3 + ||xx and column 4 shows deviation from C-unitarity 11 AuAl/n /n - -aa a and S-unitarity ||A,AA! a² I averaged over all factors and slices. Column shows normalized singular values of unfolded factors A, B,C.
Figure 15 for direct visualization of the evolution of the model tensor and parameters.) Similar analysis on the learning of the modular addition operation is presented in Figure 18 and 19
In the absence of regularization. the model quickly memorizes the training dataset, achieving perfect training accuracy, but fails generalize the test dataset. Also, the singular values of the unfolded factors remain largely unchanged during training, indicating minimal internal structural changes.
Under H. regularization, the model also first memorizes the training data, but then continues to improve on the test set. A critical turning point is observed around t = 200, marked by a sud- den collapse of the singular values towards a common value, signifying convergence solution. Simultaneously. the C/S-unitaris and imbalance measures rapidly decrease to zero. This internal restructuring coincides with a substantial improvement in test performance, achieving 100% test accuracy, highlighting its crucial role in enabling generalization. Notably, when the regulariza- tion coefficient drops to 0 around 450, both the train and test losses plummet to O, confirming perfect recovery of D.
unitary
In contrast, under L2 regularization, the model converges to low-rank solution, as evidenced by a portion of the singu- lar values decaying zero. Although it manages to achieve perfect test accuracy in this specific case F L2 regularization fails to reduce test loss to zero, indicat- ing imperfect recovery of D. Figure fur- ther confirms these findings, demonstrat- ing that only H-regularization accurately recovers the group operation, while the Le-regularized solution significantly devi- ates from D. This result underscores the importance learning full-rank, unitary solutions in recovering group operations.
Deta
H reqularized regularizet Uranguartoed
Figure 4: Model tensor T trained the S3 dataset. Training data are marked by stars (1s) and circles (Os).
This is not always the case. For example, La regularization only achieves ~60% test accuracy in the modular addition task. See Figure

---

Published as a conference paper at ICLR 2025
6.2 HYPERCUBE LEARNS UNITARY GROUP REPRESENTATIONS
We analyze the structure of the learned factors by applying the unitary basis change described in Section 4.4 The results are visualized in Figure [6 While the raw factor values may appear un- structured (top panel), simple basis change reveals remarkable properties (middle panel).
First, the learned factors share a common embedding: Ag B, Cj., for all g E G. Furthermore, as illustrated in Figure 17 multiplication of the factor slices respects the underlying group operation: Ag. Agiogs demonstrating the group homomorphism property from eq ( The slices are also verifiably unitary matrices. These properties collectively imply that the learned factors form unitary matrix representation & the group:
Ag = C = e(g).
Further structures are revealed in block-diagonalizing basis (bottom panel of Figure 16). where the factors show the complete set of irreducible representations (irreps) contained the regular representation of the group, including the trivial (1-dim), sign (1-dim), and duplicate standard rep- resentations (2-dim). The trace the factor slices also satisfies eq 2 confirming that @ is indeed a regular representation of the group. Notably, this representation is unique up to similarity transfor- mations.
Key Operating Mechanism groups. Applying eq D and the homomorphism property of a. the model eq (4) can be expressed as
These results reveal the operating mechanism of HyperCube
Tabe -Tre(())(()))(TT = [[(elaabbe""))
(10)
where the unitarity of g used for the unembedding map: C. e(g)t e(g Applying eq ( for regular representations yields the exact reconstruction of the data tensor, Tabe Dabes since a b o c- = e is equivalent to a = e eq (3). Notably, this mechanism universally applies for all finite groups. This insight leads to the following conjecture:
Conjecture 6.1. Subject to the constraint unitary group representation eq (9) is the unique minimizer of HyperCube Regularizer eq (6) up to unitary basis changes, and the minimumn value is H. (D) = D 3n².
D, where represents a group operation table, the
reveals that, for group operations, the same embedding is used across all symbol positions. This motivates tying the embeddings across factors, resulting in a parameter- efficient model tailored for learning group operations: HyperCube-SE (shared embedding).
Baaredd-mmeeding Eq (
6.3 DISCOVERING UNITARY REPRESENTATION BRYOND TRUE GROUPS
We extend our analysis to HyperCube trained on the remaining small operation tasks from Figure 2 In each case, the model accurately recovers the underlying operations from small subset (60%) of training examples. Remarkably, the model learns closely related representations across these tasks (Figure 20 even though the operations deviate from strict group axioms.
Modular Addition (a + b = c) forms the cyclic group Cs- As expected, HyperCube learns the regular representation e(g) of Cg in its factors, as described by eq (9).
Modular Subtraction (a-b = c) violates associativity and therfore not a true group. Surprisingly, HyperCube still learns the same representation addition but with transposed factors: A Bg
C2 =()). This reflects the equivalence:
b
b
Modular Squared Addition (a² + 12 = c) violates the inverse axiom. Still, HyperCube learns the same representation as addition for elements with unique inverses (e.g., 0,3), For others, learns duplicate representations reflecting the periodicity of squaring modulo: e.g., A AA since 2² = (mod 6).
These results highlight the remarkable flexibility of HyperCube's inductive bias: Even for group-like operations (i.e., those deviating from strict group axioms), HyperCube often discovers meaningful unitary representations and recovers the full Cayley table. This finding highlights the potential of unitary representations as powerful tool for understanding binary operations in broader contexts than group theory.

---

Published as a conference paper at ICLR 2025
mod 97
mod
a/b mod 97
a/b b odd else
Transformer HyperCube HyperCube-SE
a² 62 mod 97
a² ab bb mod a² ab + mod
a² ab mod 97
1000
Test Accuracyy
50
8² ab² + mod 97
ab in S.s
aba in Ss
aba in S.
100
50
0.2
0.4
0.6
0.8
0.2 0.4 0.6
0.8
0.2
0.4 0.6
0.8
0.2
0.4
0.6
0.8
Training data fraction
Generalization performance (test accuracy) of HyperCube and HyperCube- shown as functions of training data fraction a diverse of BOC tasks. The results of the Transformer baseline from Power et al. (2022) are also shown for comparison.
Figure 5:
7 RESULTS ON DIVERSE BOC TASKS
We evaluate HyperCube and HyperCube-SE on diverse BOC datasets from Power al. 2022
encompassing wide spectrum of group and non-group operations (details in Appendix B These problems significantly larger than our previous examples, with dimensions ranging from 97 to 120. Figure the test accuracy of models as functions of training data fraction over various BOC tasks.
7.1 HYPERCUBE PRIORITIZES GROUPS OVER NON-GROUP OPERATIONS
HyperCube exhibits clear preference for learning operations that admit unitary representations, For these "simple" tasks, including group (a+bb and S;) and group-like operations (a-b, a/b and a²+b²), HyperCube demonstrates remarkable generalization, achieving perfect accuracy with ~88 of the data. This strong generalization extends even to the group conjugation operation (aba- in S5), despite its lack of unitary representations. Conversely, for more "complex" operations, such as aba in S5. conditional operations, and high-order polynomials, HyperCube necessitates significantly more data for effective generalization.
HyperCube-SE exhibits similar behavior, but with an even stronger emphasis on prioritizing group structures. It further differentiates between group and group-like operations, requiring even less data (~5%) for group operations attain perfect test accuracy group operations.
For group-like operations, HyperCube-Si remains competitive with HyperCube in terms of test accuracy, despite its inherent limitation in recovering unitary representations due to the shared- embedding constraint (Eq. (9). Moreover, HyperCube-SBi shows further reduction in generaliza- tion performance compared to HyperCube on "complex" operations like high-order polynomials, consistent with its heightened prioritization group structures.
7.2 HYpERCUBE'S IMPLICIT COMPLEXITY METRIC
In the previous section, we categorized tasks as "simple" or "complex" without rigorous definition. To address this, now leverage the intrinsic complexity metric implicitly defined by HyperCube. We formally define the complexity an operation as the minimum regularizer loss, denoted H", attained when fitting the fully observed Cayley table D (t.e., under the constraint T D).
This metric closely aligns with the intuitive notion of complexity (Figure 6). Group operations achieve the minimum complexity of H" 3 D [2, signifying their inherent simplicity within the
8

---

Published as a conference paper at ICLR 2025
HyperCube HyperCube-S
Transfrmer HyperCube HyperCube-SE
ab in
a-
aba-tinn t
Steps Perfect Test Accuracy
Test Accuracy AUC
S
10
0.6
a" ab
of ab ab
04
10a
02-
10a
0.0
Complexity: HC/ HC/10l
Training data fraction
Figure 6: Complexity Generalizability (AUC Area Under Curve).
Figure 7: Number of training steps to achieve perfect test accuracy the Sş task.
HyperCube framework. In contrast, more "complex" tasks, such as high-order polynomials, incur substantially higher complexity costs.
Figure fillustates the generalization trend as function of complexity, revealing clear monotonic relationship: as task complexity increases, generalizability (measured by the total area under the test accuracy curve in Figure 5) decreases. This observation parallels the well-known relationship in matrix completion, where higher matrix rank (analogous to higher complexity) generally leads to poorer generalization and requires more data for effective learning. This underscores the critical role of our proposed complexity metric in determining the generalization bound for BOC.
7.3 COMPARISON TO TRANSFORMER
To rigorously evaluate HyperCube, we compare against a Transformer baseline from Power et al. (2022). Crucially, this Transformer baseline was meticulously tuned for peak performance due its inherent sensitivity to hyperparameters. In contrast, HyperCube demonstrates notable robustness across a broade range of hyperparameter configurations (see Appendix C).
Test Accuracy Performance Figure illustrates that Transformer accuracy trends mirror Hyper- Cube's, requiring more data for increasingly "complex" tasks. However, Transformers favor com- mutative operations (e-g., a+-,, b, a² +ab+ over non-commutative ones (e-g., Sş tasks). This likely stems from Transformers' shared vector emheddings across all input locations (Power et al. 2022 Liu et al. (022), which misaligns their inductive bias with group structure learning. Overall, HuperCube achieves comparable or slightly better generalization than Transformers in test accuracy across most tasks.
Learning Speed HyperCuhe drastically outperforms Transformers in learning speed (Figure 7 As reported by Power et al. (2022), Transformer's learning progress on BOC is remarkably slow, requiring orders of magnitude more time to generalize the set than fit the training phenomenon, known as "grokking," " becomes exacerbated with less training data. This has been widely observed subsequent works across various deep learning architectures (Nanda al. 2022 Liu et al. 2022 Chughtai et al.) 2023).
This
In contrast, HyperCube exhibits exceptional learning speed, converging to perfect accuracy 100 times faster than the Transformer baseline in most cases, while also requiring less data. HyperCube- SE, which employs chared-embedding of symbols similarly to Transformers, achieves an additional
'These include learning rate, batch size, weight decay, dropout, update noise level, and optimizer type. See Section 3.3 and A.1.2 of Power al. (202) for further details.

---

Published as a conference paper at ICLR 2025
10x speedup and requires only 5% of the data for perfect generalization. This dramatic x improvement learning speed demonstrates the effectiveness HyperCube's inductive bias toward group structures.
CONCLUSION
This work introduced novel differentiable framework for discovering the structure of finite groups and their representations. Through thcoretical analysis and empirical validation, we demonstrated that proposed model exhibits strong inductive bias towards learning group structures and their unitary representations. Furthermore, we have elucidated an implicit complexity metric inherent in model, which quantifies the model's prioritization for discovering group structures and provides insights into the generalization properties in recovering binary operations. Crucially, this inductive bias is universal, directed towards the general algebraic structure of all groups, rather than being specific to any particular group symmetry.
This research pioneers new opportunities for employing deep learning to automatically uncover group structures from data - challenge with far-reaching implications across diverse scientific domains. Prominent potential applications include: Automatic Symmetry Discovery: Identifying symmetries in complex systems, such as physical systems or molecular structures. Representation Learning: Learning meaningful representations of data that capture underlying algebraic relation- ships. Algorithmic Reasoning: Developing deep learning models capable of symbolic reasoning and algorithmic problem-solving.
Related Works Prior works on group discovery, particularly symmetry-foeuser approaches, are related to our work. However, existing symmetry- baased methods typically require external infor- mation specifying the symmetry structure. For instance, /Anselmi al. (2019) leverage data aug- mentation with known orbit information. while Forestano et al. (2023) similarfy presume an oracle providing orbit information. Yang et al. (2023) employs semi-supervised approach to infer orbit information, and Zhou al. (2021) utilizes meta-lcarning, assuming shared group convolution structure across tasks. In contrast, our approach uniquely derives a universal inductive bias to- wards the general algebraic structure of groups, independent of specific symmetries. Consequently, our method is complementary to, and potentially synergistic with, these existing symmetry-focused techniques.
Scalability HyperCube's tensor-factorizztion architecture can lead to substantial memory and computational costs, scaling as Onn²). However, efficient parallelization of einsum operations enables cear-constant runtime complexity GPUs (Appendix (F). Moreover, constraining embeddings to band-diagonal matrices can effectively reduce memory and computa- tional costs to Onn²) (Appendix Ep. underscoring the potential for scaling HyperCube larger problem sizes.
demonstrate that
Limitations Our analysis is primarily focused on Binary Operation Completion (BOC) tasks and currently necessitates prior knowledge of the group size, Furthermore, while method is not directly applicable to continuous Lie groups in its present form, we anticipate that an analogous differentiable approach be developed encode the axioms of Lie algebras.
Open Questions This work naturally leads to several open questions for future research. Promi- nent among these are deriving rigorous generalization bounds for BOC tasks and formally proving the optimality of unitary representations, suggested by Observation 5n6 Conjecture[6.]] Fur- thermore, extending our methodology to accommodate multiple symbols and operations beyond binary operations would significantly broaden its scope and applicability.
ACKNOWLEDGMENTS
The authors thank Nima Dehmamy and Ken Clarkson for their helpful discussions, which greatly benefited this work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Anselmi, F., Evangelopoulos, G., Rosasco, L., and Poggio, T. (2019). Symmetry-adapted represen- tation learning. Pattern Recognition, 86:201-208.
Arora, S., Cohen, N., Hu, W., Luo, Y. (2019). Implicit Regularization Deep Matrix Factor- ization. arXiv:19055 13655 [es, stat].
Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.134 13478 [cs, stat].
Burer, S. and Monteiro, R. D. (2003). A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):22--357.
Candes, E. J. and Tao, T. (2010). The Power of Convex Relaxation: Near-Optimal Matrix Comple- tion. IEEE Transactions on Information Theoory 56(5):2053-25
Candès, J. and Recht, B. (2009). Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics, 17-777.
Chughtai, B., Chan, L., and Nanda, N. (2023). Neural Networks Learn Representation Theory: Reverse Engineering how Networks Perform Group Operations. In ICLR 2023 Workshop on Physics for Machine Learning.
Fazel, M., Hindi, H., and Boyd, S. (2001). A rank minimization heuristic with application to min- imum order system approximation. In Proceedings of the 2001 American Control Conference. (Cat. No.0ICH37146) volume 6, pages 4734 4739 vol.6. ISSN: 0743-1619.
Forestano, R. T., Matchev, K. T., Matcheva, K., Roman, A., Unlu, E., and Verner, S. (2023). Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles. arXiv:2301.05636 [hep-ph, physics:physies).
Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. (2017). Implicit Regularization in Matrix Factorization. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Kawaguchi, K. (2016). Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594.
Liu, 7., Kitouni, O., Nolte, N., Michaud, F. Tegmark, M., and Williams, M. (2022). Towards Un- derstanding Grokking: An Effective Theory of Representation Learning. In Advances in Neural Information Processing Systems.
Nanda, N., Chan, L., Lieberum, T.. Smith, J., and Steinhardt, J. (2022). Progress measures for grokking via mechanistic interpretability. In The Eleventh International Conference on Learning Representations.
Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, V. (2022). Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets.
Recht, B., Fazel, M., and Parrilo, P. A. (2010). Guaranteed Minimum- Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Review, 52(3):471-501
Srebro, N., Rennie, J., and Jaakkola, T. (2004). Maximum-Mann Margin Matrix Factorization. In Advances in Neural Information Processing Systems, volume 17. MIT Press.
Tucker, L. R. (1966). Some mathematical notes on three-mode factor analysis. Psychometrika, 3193)1279-311
Yang, J., Walters, R., Dehmamy, N., and Yu, R. (2023). Generative Adversarial Symmetry Discov- ery. arXiv:2302.00236 [cs].
Zhou, A., Knowles, T., and Finn, C. (2021). Meta-Learning Symmetries by Reparameterization. arXiv:2007.0299 02933 [cs, stat].
11

---

Published as a conference paper at ICLR 2025
A TRAINING PROCEDURE
The factor tensors are initialized with entries randomly drawn from a normal distribution: No 1//nn/ We employ full-batch gradient descent to optimize regularized loss with learn- ing rate of 0.5 and momentum of 0.5. For the small scale experiments in Section the HyperCube regularizer coefficient is set to < 0.1. For the larger scale experiments in Section 7 we use 0.05 for HyperCube and 0.01 for HyperCube- See Appendix [ for discussion of hyperparameter sensitivity. Each experiment quickly runs within a few minutes on a single GPU.
e-scheduler To overcome the limitations in standard regularized optimization, which often pre- vents full convergence to the ground truth (D), we employ e-scheduler: Once the model demon- strates sufficient convergence (e.g., the average imbalance falls below threshold of 10-5), the scheduler sets the regularization coefficient e to This allows the model to fully fit the training data. The effect of c-scheduler on convergence is discussed in Appendix G.3
The main implementation of HyperCube shown below.
import torch
def HyperCube product praduucttpppoucctttcc (A, B, C)
return torch, ferccheiisum/fc (1 aij, bjk, cki->abe', B, C) / A. shahape [0]
def Hyporcube_regulariesss (A, C)
def helper (M, N)
мM torch.einsum aimm"jj'' M,
NN = torch.einsun (' ('bj,, bmk-> N, N]
10
return corch.einsum [jm jm-s', MX, NN)
return (helper B) helper (B, helper (C,
A. shape [0]
B LIST OF BINARY OPERATIONS
Here is the list of binary operations from Power et al. (2022) that are used in Section (with = 97).
(with
(add) b (mod p) for 0 a, < p. (Cyclic Group)
(sub) a b (mod p) for s a. <.
(div) a a/b (mod p) for S a < p. <b<p.
(cond) a b |a/b b (mod p) if b is odd, otherwise b (mod p)] for 0 S a, <
(quadl) a = a² + 12 (mod p) for 0 < a, <.
(quad2) o a² ab 12 (mod p) for a, p.
(quad3) o a² ab 12 + a (mod p) for - a, b < p.
(cubel) a h = a² + ab (mod p) for S a, <.
(cube2) a o = 8 + ab² + (mod p) for 0 S a, < p. (ab in St) o b b for a, b E Sz. (Symmetric Group)
(oba in 85) o a- a for a, E Ss.
(aba in S5) a a b. for a, E Ss.
Figure 8: Elements of the symmetric group S₃ illustrated as permutations of 3 items. Green color indicates odd permutations, and white indicates permutations. Adapted from https://en
12

---

Published as a conference paper at ICLR 2025
C HYPERPARAMETER SENSITIVITY ANALYSIS
We tested HyperCube across a wide range of hyperparameter settings, including learning rate, reg- ularization coefficient, and weight initialization scale. Figure | shows the final test accuracy and Figure [ shows the number of training steps to achieve 100% test accuracy across a subset of tasks from Appendix
B under a fixed training budget of 1000 training steps.
HyperCube exhibits robust performance over the range of hyperparameter settings. Notably, in- creasing the learning rate or regularization coefficient primarily raises the convergence speed with- out significantly affecting the final test accuracy. The learning dynamics starts to become unstable at large learning rate 1.5) or regularization coefficient (c 0.1). The weight initialization scale has no effect on either the final test accuracy or the convergence speed.
This robustness, particularly to weight initialization scale and regularization strength, noteworthy. Deep neural networks exhibit saddle point with zero Hessian at zero weights (Kawaguchi (016) which becomes a local minimum under L2 regularization. This local minimum can cause the net- work weights to collapse to zero when initialized with small values under strong regularization. (This mechanism also promotes low-rank solutions in Ly-regularized deep neural networks.)
In contrast, HyperCube's quartic regularization loss, also featuring zero Hessian at zero weights, maintains the saddle point at zero. The absence of local minimum at zero prevents weight collapse, contributing significantly robust learning dynamics and promoting the emergence of full-rank unitary representations in HyperCube.
earning rate
32 barten
12l
Reg coeff
08
24 50 bantsarlen
121 (ifezeal))
Init scala
30
Test accuracy vs Hyperparameters: (Top) learning rate, (Middle) regularization strength, and (Bottom) weight initialization scale. Trained under a fixed training budget of 1000 steps. Default hyperparameter setting: 0.5, reg coeff = 0.05, init scale 1.0.
Figure 9:
Jel stt
JaNe
thaming rate
Vodlor
Vaciin Laci E.
Eaclin
211.11
Lel Al)
couff
vutter 1st =0000)))))
thecier
midtinn Leo 5:)
Eactien lade 1n
Iao 13 old dis 2-30
(P at)
Inc ocale
Votlor
Figure 10: Steps to 100% accuracy vs Hyperparameters: Same settings as Fig 9 but showing number of training steps to achieve 100% test accuracy.
13

---

Published as a conference paper at ICLR 2025
D ALTERNATIVE TENSOR FACTORIZATIONS
HyperCube distinguishes itself from conventional tensor factorization architectures, which typically employ lower-order, matrix factors for decomposition: e.g., Tucker and CP decomposition. This difference is crucial for capturing the rich structure of binary operations.
Tucker Decomposition (Tucker 1966) employs core tensor M and three matrix factors:
Tabe Σ 2.j.k
Mu Cok:
(11)
While flexible, Tucker decomposition suffers from a critical limitation: In eq 11). the role of ma- trix factors is limited to simply mapping individual external indices to individual internal indices (e.g. A maps a to i). This presents recursive challenge, since learning the algebraic relationships between the external indices (a, b, c) in ''' requires learning the relationships between the internal indices(i, J. k) in M, which is not inherently simplifying the core learning problem. Consequently, Tucker decomposition severely overfits the training data and fails to generalize to unseen examples (Figure
CP Decomposition
CP decomposition utilizes only matrix factors for decomposition:
Tabe =
Σ Aas Cok
(12)
This is equivalent to HyperCube with diagonal embeddings (ie. Aaki Aan Buij Bridij. Cesk = Cejōft), since
Σ 15k
Ansi Cojk Aas Br C ijk
Σ
Σ
Aak Bir Cok.
(13)
Therefore, while CP decomposition can fully capture commutative Abelian groups (e.g modular addition), which admit diagonal representations (i.e., 1 irreps) in K C, it lacks the expressive power to capture more complex operations. In experiments (Figure I.I. CP decomposition indeed shows reasonable performance only for the modular addition task, struggling to generalize to other structures in data.
Toclo decampps Bon
2am-41 M
ball
kalle 12 22l
balle
21
CP decompottionn
100
Figure 11: Alternative Tensor Factorization Methods: Test accuracy of (Top) Tucker and (Bot-
tom) CP decomposition methods, trained across range of L2 regularization strengths.
'CP decomposition can also be viewed a special case of Tucker decomposition with fixed core tensor
Mysa = if = = ke otherwise.
14

---

Published as a conference paper at ICLR 2025
E BAND-DIAGONAL HYPERCUBE
As mentioned above, HyperCube with diagonal embeddings lacks the capacity to effectively capture general group structures. However, the regular representation of group generally decomposes into a direct sum of smaller irreducible representations, resulting in a sparse, block-diagonal matrix structure. Such block-diagonal structure can be effectively captured within the parameter space of hand-diagonee matrices.
Therefore, enhance the scalability of HyperCube, we explore the band-diagonal variant where the factor matrices are constrained to have fixed bandwidth around the diagonal. This reduces the model's s parameter count from (nn)) to (nn)), offering significant computational advantages.
Figure 12 compares the performance of the full HyperCube and the band-diagonal HyperCube with a bandwidth of 8 on subset of tasks from Appendix [ (n 97 or 120). Remarkably, the band- diagonal version exhibits comparable performance to the full HyperCube model, demonstrating its effectiveness in capturing group structures even with a significantly reduced number of parameters. This result highlights the potential of band-diagonal HyperCube for scaling larger problems.
2
1ext sccuncy
19t Vodtor
300 Footen
14h teation
ten Parten
pr002 100%
Lach tuit
Lapin
Figure 12: Full HyperCube vs Band-diagonal HyperCube model. (Top) final test accuracy, and (Bottom) steps 100% test accuracy. 0.5, reg coeff e 0.05, init scale 1.0.
15

---

Published as a conference paper at ICLR 2025
F RUN-TIME COMPLEXITY
We empirically evaluate the run-time complexity of HyperCube. As expected, CPU execution time scales as O However, due to the efficient parallelization of einsum operations in PyTorch (See Appendix A GPU execution time remains nearly constant with increasing n (up to n 200, the maximum size that fits the 16GB memory of Tesla V100 GPU). This demonstrates the practical efficiency of HyperCube when leveraging GPU acceleration.
Run-time complexity
complesity
16
HyperClube Oyn'1
10a
19a
10-2
15-2
10-
10.
Figure 13: Run-time complexity for computing the HyperCube architecture (eq as functions of Other tensor decomposition methods (CP and Tucker) are also shown. (Left) Run-time on CPU. (Right) Run-time on GPU (Tesla V100 16GB). Results are averaged over 10 runs.
Run-time complexity Regularizer (CPU) sec]
Run-time complexity Regularizer (GPU, sec)
16
16
CP
CF
Ticker
Titker TyperCibbe
10F
HyparCLute
10A
On!!
Onni
10ah
15ah
10-
10a
1044
13a
19a
10a
12
16
12
Figure 14: Same above but for computing the regularizers.
16

---

Published as a conference paper at ICLR 2025
G DEFERRED PROOFS
G.1 PROOF OF LEMMA 5.1 ON BALANCED CONDITION OF HYPERCUBE
Here, we derive the balanced condition eq (H,,, C)C) is
The gradient of the regularized loss C = Lo(T;
VA.C
((V Tabo L.) + ((AA,
(14)
71
V Bg C
((V A (4
7
Vc C = ((Vrns. 2c(C + (B,
where VA, =A,C=00/0AA BB -= OL/OB,, Vc, L = aC/0C,, and V = uLo / / abc-
Define the imbalances as the differences of loss gradients:
(AL(VA, A. - (Ve,))B))
-
2E
{ (B) B. ()- (Vc.)cc) B](A)A))) -C(AAA)
εK (C.
- (VA.C)A -
Setting the gradient to zero yields the balanced condition at stationary points, Er = = Ex = 0, which proves Lemma 5.1 Note that imbalance terms defined to cancel out the VT terms. Therefore, the balanced condition is independent of the loss function L..
G.2 PROOF LEMMA 5.4
Proof. The constraint Frobenius norm can be integrated with the regularizer into augmented loss via the Lagrange multiplier A
+ A(F - -constant),
(15)
where == ALAA + B, + C.C. the Frobenius norm
The gradient of eq (15) with respect to Aa is proportional to
VA, (7 + AF) & AB,BB + (C.C.)A, + AAa
(16)
In the case of C-unitary factors B and C, all terms in eq (16) become aligned to Aa i.e.
V (H XF) (a o A)
(17)
and thus an appropriate value for the Lagrange multiplier can be found to vanish the gradient, which confirms stationarity. This result also applies to gradient with respect to Bd and C. by the symmetry parameterization.
G.3 PERSISTENCE GROUP REPRESENTATION
The following lemma demonstrates a key property of our model's convergence behavior: once group representation is learned, the solution remains within this representational form throughout optimization.
Lemma G.1. Let D represent a group operation table. Once gradient descent of the regularized loss eq 5 converges to a group representation (including scalar multiples), i.e.
A. = aA,())()) B, aB,e((), C. accelc)',
(18)
the solution remains within this representation form.
17

---

Published as a conference paper at ICLR 2025
Proof. For the squared loss
DT;
Σ
(Tabe - Dabe)
(19)
(ags
the gradient with respect to A₂ eq becomes
V VA,C= -
+ ((A, + (CCC.))))
(20)
where A = T - D is the constraint error, and M is the mask indicating observed entries in the train set.
Substituting the group representation form 18 into eq 200) we get:
1 c (Aa + (o.) 2E0 2 e(a))
(21)
n
for the last two terms, where a² = Es n /n E. /
Since the product tensor
Tabe = B.Co, = -a aB, Tre(a)g(())(c]]] = a.a aB, aC. Dabe:
and Dabe Sooble = 6,,00b (6 is the Kronecker delta function), the first term in (20
becomes
Σ b.c
Mabe
Σ
Mabella OB CC. - 1), e(cob=
n
b.c
Σ
Mar(uos) (a OB, OCaes - 1)BB, OC.on a(a).
(22)
Note that both eq 22 and eq (2I proportional to e(a). Consequently, we have VA, C x e(a).
Similar results for other factors can also be derived: Ve, C x e(b), and Vc, C x e(c)². This implies that gradient descent preserves the form of the group representation (eq (88 ) only updating
the coefficients OAA,, O.B,,, OCC.
Effect of e-Scheduler Lemma G.I holds true even when gets modified by e-scheduler, which reduces to 0. In this case, the coefficintss converge to a.,, an, ac. = 1, resulting in the exact group representation form eq
18

---

Published as a conference paper at ICLR 2025
H GROUP CONVOLUTION AND FOURIER TRANSFORM
H.1 FOURIER TRANSFORM ON GROUPS
The Fourier transform of a function f : - R representation e: - GT. IR) of G
f(e) Σ f(g)e(9).
(23)
JEG
For each representation e of G. f(e) a do x de matrix, where dg is the degree of P.
H.2 DUAL GROUP
Let & be complete set indexing the irreducible representations of G up isomorphism, called the dual group, thus for each & we have an irreducible representation & : G + UVVe). and every irreducible representation is isomorphic to exactly one Pç-
H.3 INVERSE FOURIER TRANSFORM
The inverse Fourier transform at an element of G is given by
f(g)
1
Ede dec Ir (ee(g-))((e)) ')((e))
(24)
G
EEG
where the summation goes the complete set of irreps in G.
H.4 GROUP CONVOLUTION
The convolution of two functions over a finite group f,g G - IR is defined as
hf+ [cocbb h(b)
(25)
BEG
H.5 FOURIER TRANSFORM OF GROUP CONVOLUTION
Fourier transform of a convolution at any representation g of G is given by the matrix multiplication
h(()) f(g)h(e).
(26)
In other words, in Fourier representation, the group convolution is simply implemented by the matrix multiplication.
Proof.
F
Σ e(c) Σ fleo (coob)))(()
(27)
Σ e(c) Σ ((a))(6))(aamob>))
(28)
a.b
Σ f(a)((b) Σ e(c))
(29)
Σ (())M())((a
(30)
a
Σ M(a)((a) Σ h(b))(b)
(31)
(32)
where 8 is the Kronecker delta function, and the equivalence between a = co b- and a o cs used between the second and the third equality.
19

---

Published as a conference paper at ICLR 2025
1 GROUP CONVOLUTION AND FOURIER TRANSFORM IN HYPERCUBE
HyperCube shares a close connection with group convolution and Fourier transform. On finite groups, the Fourier transform generalizes classical Fourier analysis functions defined the group: f G + R. Instead of decomposing by frequency, it uses the group's s irreducible repre- sentations {eg), where indexes the irreps (See Appendix H.2). A function's 's Fourier component at & is defined as:
f= (()ee)))))) 9EG
(33)
Fourier Transform in HyperCube The Fourier transform perspective offers a new way to under- stand how HyperCube with group representation eq ( processes general input vectors. Consider a vector f representing a function, i.e., fg = f(g). Contracting f with a model factor A (or B) yields:
f= fgA f(9))()))
(34)
which calculates the Fourier transform of f using the regular representation p. As contains all irreps of the group. f holds the complete set of Fourier components. Conversely, contracting f with of (I.e. factor C)) performs the inverse Fourier transform:
Tr|fCyl=
100=111, fgr 1() = n
E 9'EG
(35)
72
where eq 2 is used. This reveals that the factor tensors generalize the discrete Fourier transform (DFT) matrix, allowing the model to map signals between the group space and its Fourier (fre- quency) space representations.
Through the lens Fourier transform, we can understand how the model eq (T)) processes general input vectors (f and h): calculates their Fourier transforms (f, h), multiplies them in the Fourier domain (fî), and applies the inverse Fourier transform. Remarkably, this process is equivalent to performing group convolution (f h). This is because the linearized group operation (Section 4.1) naturally entails group convolution (see Appendix I.1 ??).
This connection reveals profound discovery: HyperCube's ability learn symbolic operations is fundamentally the same as learning the core structure of group convolutions. This means HyperCube can automatically discover the essential architecture needed for equivariant networks, without the need to hand-design them. This finding highlights the broad potential of HyperCube's inductive bias, extending its applicability beyond the realm of symbolic operations.
1.1 REINTERPRETING HYPERCUBE'S COMPUTATION
HyperCube equipped with group representation eq
10 processes general input vectors and
Sabi Σ
(a)M(b) Tr [o(a)e(t)e(c)]]
= 1 Ir (Eotostca) ( ((0o)1))) e(c)t
a
= Tr((f))o(c)]] = Trff+ he()"
= =f( l)).
(36)
Therefore, the model calculates the Fourier transform of the inputs (/ and h), multiplies them in the Fourier domain (ff), and applies the inverse Fourier transform, which is equivalent the group convolution, as shown in Appendix H.5
20

---

Published as a conference paper at ICLR 2025
J SUPPLEMENTARY FIGURES FOR SECTION 6
Unregularized
regularized
T.00
Prodict Tenser Sices
T..L
T
T12
Visualization of the end-to-end model tensor T and the factor A over the training iteration steps on the symmetric group S3 task in Sec Only the first three slices of the tensors are shown. (Top) End-to-end model tensor T: In the un un-regularized case, the model tensor quickly converges to fit the observed data tensor entries in the training dataset (marked by stars and circles), but not in the test dataset. The H-regularized model converges to generalizing solution around t = 200. It accurately recovers D) when the regularization diminishes around t = 400 (e + 0). (Bottom) Factor tensor A. The unregularized model shows minimal changes from random initial values, while H-regularized model shows significant internal restructuring. Shown in the block- diagonalizing coordinate. See Fig 16 (Bottom). (color scheme: red=1, white=0, blue=-1.)
Figure 15:
21

---

Published as a conference paper at ICLR 2025
Aa
8/
8,
Raw
G1
C2
C2
C4
A
A
A
Ao Bo Co
C2
Ao
A
Az
A
A
A
Block- Diagonal
81
82
Pg
Figure 16: Learned factors of the H. regularized model trained on the S3 group. (Top) Raw factor weights shown their native coordinate representation. (Middle) Unitary basis change as described
Sec 4..4 with M, I. .M Ao. M, = B such that Åo = Bo C = Note that the factors share same weights (up to transpose in factor Ć). (Bottom) Factors represented block-diagonaliziin basis coordinate, revealing the decomposition into direct of irreducible representations (irreps). (color scheme: red=1, white=0, blue=-1.)
22

---

Published as a conference paper at ICLR 2025
AcAc
AcA:
ApA:
AsAo
AcA
AsAs
ALAc
A,AL
A:A,
A,Ai
A,Ar
A.Á:
Arfe
AsA::
Ap/o
1cA4
Apds
AcA
A,Ax
A,44
Ajá,
Multiplication table of matrix slices of factor A from the mid panel of Fig 16 Note that this table share the same structure the Cayley table of the symmetric group S3 Fig 2A. (color scheme: red=1, white=0, blue=-1.)
Figure 17:
23

---

Published as a conference paper at ICLR 2025
Accuracy
Imbalance
Orthogonality
Singular Value
104
10a
Unregularized
100
10"
1.25
10'
10
25
0.75
10'"
10"4
10
L2 regularized
10"
100
75
10n2
10"
10"7
10
train
contracted
regularizer
Test
siice
10-3
10
10
100
200
300
100
200
300
100
200
300
100
200
300
100
200
300
7 regularized
10"
100
75
10
10P
10-2
0.6
10
10"
100
200
400
500
200
400
600
200
400
600
200
400
600
200
400
600
Reration
Optimization trajectories on the modular addition (cyclic group C²) dataset, with 60% of the Cayley table used as train dataset (see Fig 19). (Top) Unregularized, (Middle) Ln-regularized, and (Bottom) H-regularized training. The Læ-regularized model only achieves ~60% test accuracy.
Figure 18:
Unrogularized
T.
T
H regularized regulartzed
T-t
T.
Tic
Tat
Tia
Figure 19: Visualization of end-to-end model tensor 7 trained on the modular addition (cyclic group Cg) under different regularization strategies (see Fig [8]. The observed training data are marked by asterisks (Is) and circles (Os). Only the H-regularized model perfectly recovers the data tensor D. (color scheme: red=1, white=0, blue=-1.)
24

---

Published as a conference paper at ICLR 2025
Ac
A:
A
A
c=a+ mod
A:
Áo
c=a- mod
B,
Ac
A
A
12 b2 mod 6
Figure 20: Visualization of factors trained on small Cayley tables from Figure (Top) c = a mod 6, satisfying Ag B, = Cj e(g). (Middle) c = b mod 6, satisfying Aj B, = C. e(g). (Bottom) e for elements with unique inverses (e.g., 9 0. For others, it learns duplicate representations
12 mod which exhibits the same representation as modular addition
reflecting the periodicity of squaring modulo 6: e.g., Ag = A₁ and Ai = As. since 2² 42 and 1 5?. (color scheme: red=1, white=0, blue=-1.)
25


Reviews:
[{"review_id": "juNLo3Xiuc", "reviewer": "Reviewer_wdaY", "summary": "The paper presents a novel differentiable approach for discovering group structures in data using group representation theory and tensor-factorization models. It effectively learns group operations and unitary representations from limited data while defining a complexity metric that enhances group structure discovery, impacting various scientific domains and automatic symmetry discovery applications.", "questions": "1.  In Line 185, can a and b mapped to vector embeddings or diagonal matrix embeddings?\n\n2. Can the tensor T be parameterized using other tensor decomposition models?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes a differentiable approach to the automatic discovery of finite group structures through the learning of their underlying representations.\n\n2. This paper introduces a novel regularization technique that encourages the matrices to maintain unitarity, thereby improving the preservation of group structures.\n\n3. This paper offers a theoretical analysis of the inductive bias associated with HyperCube.", "weaknesses": "1. The clarity of the paper's writing is lacking, which makes it somewhat challenging to read. For example, the rationale for introducing HyperCube and its advantages are not adequately explained. Additionally, the underlying intuition behind HyperCube regularization is insufficiently articulated.\n\n2. The paper does not include a comprehensive set of experiments. L2 regularization is relatively weak compared to other regularization techniques. To strengthen the paper's contributions, it is essential to compare HyperCube regularization with more robust regularization methods.\n\n3. Given that HyperCube regularization involves matrix multiplication, it is important to present both the computation and runtime in the experimental results. This information would provide valuable insights into the efficiency of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TPXCv66hTe", "reviewer": "Reviewer_13RW", "summary": "This paper studies a method to predict the complete group elements based on partial observations of the action of a finite group using tensor decomposition. The HyperCube decomposition and the regularization term presented in equation (6) are newly proposed. This regularization term theoretically promotes the \"Imbalance\" and \"Unitarity\" of the decomposed factor parameters. Experiments are conducted on data involving simple operations like integer addition and subtraction, comparing the performance with a Transformer.", "questions": "- The paper solves the problem of predicting group actions, but how does this lead to symmetry discovery? Could the authors provide concrete ideas?\n- How could this method be adapted to continuous groups, such as Lie groups?\n- Could the authors explain in what criterion the inductive bias introduced by (5) was chosen? For example, the tensor T[i, j, :] is strongly constrained to become a one-hot vector for all i, j. Could another approach, like a classification model where $y_{ijk} = \\langle A_i, C_k, B_j \\rangle$ (with parameters $A_i, B_j \\in \\mathbb{R}^k $ and $ C_k \\in \\mathbb{R}^{k \\times k}$ where k is an embedding dimension) serve as a better model? What advantages does the proposed inductive bias offer compared to this alternative?\n- The authors claim that the sample complexity is better than that of a Transformer, but what about the computational time (wallclock) in comparison?\n- Could the authors provide a more intuitive explanation of the \"Imbalanceness\" in Lemma 5.1?\n- How sensitive is the prediction accuracy to $ \\epsilon $?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "- The idea of connecting group theory to tensor decomposition to solve this problem is unique and interesting.\n- The paper is written in a clear and accessible way, starting from fundamental concepts.", "weaknesses": "- The necessity of the inductive bias introduced in this work is not adequately explained, particularly why this specific bias was chosen over others.\n- The proposed method does not scale well. If the number of group elements is n, the computational complexity is O(n^3).\n- The experimental results mentioned in the text (Figures 10 and 11) are pushed to the appendix, potentially violating the page limit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4IZ67YvxZy", "reviewer": "Reviewer_SQSt", "summary": "The paper introduces a novel differentiable approach for discovering group structures within data by leveraging group representation theory. Traditionally, the non-differentiable nature of group axioms has posed challenges for their integration into deep learning frameworks. The proposed method addresses this limitation by employing a tensor-factorization model with matrix embeddings for each group element, along with a regularizer that encourages the learning of unitary matrix representations. This setup provides a strong inductive bias toward capturing group structures in data. The model is evaluated using Symbolic Operation Completion (SOC) tasks, where it successfully learns group operations from limited data and accurately discovers unitary representations. Furthermore, the model introduces an implicit complexity metric, facilitating the discovery of group structures in a variety of datasets, with potential applications in areas like symmetry discovery.\n\nThe method builds on well-established principles from group representation theory but extends them into a differentiable framework, making it applicable in modern deep learning contexts. By transforming SOC tasks into a tensor completion problem, the authors present a linearized framework that captures binary operations through bilinear maps, with a novel architecture—Hypercube—used to factorize the tensors. The accompanying regularizer plays a critical role in promoting unitary representations, ensuring that the model adheres to group properties.", "questions": "The paper does not provide much detail on how sensitive the performance of HyperCube is to various hyperparameters, such as the regularization strength, learning rate, or factor initialization. Understanding the impact of these hyperparameters, especially across different tasks (group vs. non-group operations), would be useful for replicating and extending the work to new datasets and applications. Can the authors provide more clarity on the tuning process and how these parameters affect the model's performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Differentiable Framework for Group Discovery: A notable strength of the paper is its introduction of a differentiable method for discovering group structures, addressing a long-standing challenge in integrating group theory with deep learning. By employing tensor-factorization and matrix embeddings, along with a regularizer promoting unitary matrices, the approach allows for the learning of group representations within a differentiable framework. This innovation enhances the applicability of group theory in machine learning, providing a more seamless way to incorporate group structures into data-driven models, particularly in contexts requiring automatic discovery of algebraic properties.\n- Solid Theoretical Foundation with Practical Relevance: Another strength lies in the paper's solid grounding in group representation theory, combined with its practical application to SOC tasks. The method’s reliance on well-established theoretical principles, such as the use of a complexity metric and regularization to guide learning, is complemented by its practical effectiveness in recovering group operations and unitary representations from limited data. This balance between theory and practice makes the approach both rigorous and relevant, showcasing its potential for broader applications in tasks involving the discovery of group structures within data.", "weaknesses": "- Narrow Focus on SOC Tasks: One of the paper's weaknesses is its narrow focus on SOC tasks for evaluation. While SOC tasks provide a controlled environment to test group structure discovery, they may not fully capture the model’s performance or versatility in real-world applications, where data and tasks are often more varied and complex. By limiting the scope to SOC tasks, the paper does not explore how well the proposed method generalizes to other tasks like graph classification, natural language processing, or scientific data analysis, which could broaden the understanding of its practical impact.\n- Limited Baseline Comparisons: The comparison of Hypercube to other models, especially the Transformer from Power et al. (2022), is somewhat limited. While the paper shows that Hypercube outperforms the Transformer in terms of learning speed, the focus on just one baseline model limits the robustness of the evaluation. There is no detailed comparison against other relevant methods that also target group discovery or structure learning. Including a wider range of baseline comparisons would provide a more comprehensive assessment of Hypercube's relative strengths and weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)