Permutation Equivariant Neural Networks for Symmetric Tensors
Authors: Edward Pearce-Crump
Venue: ICML 2025 poster (2025)
Keywords: Equivariance
deep learning
permutations
symmetric tensors
Primary area: theory->deep_learning

Abstract: Incorporating permutation equivariance into neural networks has proven to be useful in ensuring that models respect symmetries that exist in
data. Symmetric tensors, which naturally appear
in statistics, machine learning, and graph theory,
are essential for many applications in physics,
chemistry, and materials science, amongst others. However, existing research on permutation
equivariant models has not explored symmetric
tensors as inputs, and most prior work on learning
from these tensors has focused on equivariance
to Euclidean groups. In this paper, we present
two different characterisations of all linear permutation equivariant functions between symmetric
power spaces of $\mathbb{R}^{n}$. We show on two tasks that
these functions are highly data efficient compared
to standard MLPs and have potential to generalise
well to symmetric tensors of different sizes.

Permutation Equivariant Neural Networks for Symmetric Tensors
Edward Pearce-Crump'
Abstract
2021; Batatia et al., 2022; Batzner et al., 2022; Hoogeboom et al., 2022; Liao & Smidt, 2023), reinforcement learning (van der Pol et al., 2020; Wang et al., 2022a;b;c), computer vision (Marcos et al., 2017; Worrall et al., 2017; Esteves et al., 2019; Deng et al., 2021; Chatzipantazis et al., 2023; Kaba et al., 2023), and modelling compositional structures in natural language (Gordon et al., 2020; Petrache & Trivedi, 2024).
Incorporating permutation equivariance into neu- ral networks has proven to be useful in ensur- ing that models respect symmetries that exist in data. Symmetric tensors, which naturally appear in statistics, machine learning, and graph theory, are essential for many applications in physics, chemistry, and materials science, amongst oth- ers. However, existing research on permutation equivariant models has not explored symmetric tensors as inputs, and most prior work on learning from these tensors has focused on equivariance to Euclidean groups. In this paper, we present two different characterisations of all linear permu- tation equivariant functions between symmetric power spaces of "R... We show on two tasks that these functions are highly data efficient compared to standard MLPs and have potential to generalise well to symmetric tensors of different sizes.
In this paper, we consider linear permutation (Sx) equiv- ariant functions f on symmetric tensors T E )R") In particular, these functions must satisfy
fle, 8c,, R.. -.,,) f(eiac)) Ge -Ci (1)
for all i E Sk, where CJy are standard basis vectors in I",, since the coefficients of T, when expressed in this basis, satisfy T Ta.. Ti (oc)))oa))))))) for all π Sk.
Symmetric tensors and linear permutation equivariant func- tions on them play fundamental role in many scientific domains owing to their ability to capture invariant and equiv- ariant relationships in nigh-dimensional data. In statistics, these functions preserve the defining properties of covari- ance matrices, which are symmetric and equivariant under permutations of their coordinates (McCullagh, 2018). These functions and tensors also important in machine learn- ing, where they enable robust parameter estimation in la- tent variable models (Anandkumar et al., 2014; Jaffe et al., 2018; Goulart et al., 2022). They also appear in clustering algorithms, which must treat all data points equivalently (Khouja, 2022). However, the most notable example is in graph theory, where symmetric adjacency matrices formed from undirected graphs (Maron et al., 2019a) and high-order adjacency tensors are used to identify affinity relations in hypergraphs (Shashua et al., 2005; Georgii et al., 201 1; Ghoshdastidar & Dukkipati, 2017). This framework is essential for many real-world applications: for example, in fluid dynamics simulations, particle interactions must be invariant under exchange (Gao al., 2022); in materi- als science, stress-straie relationships must maintain their physical meaning under permutation symmetry (Garanger et al., 2024; Wen et al., 2024); and in neuroscience, brain connectome mapping requires consistent representation of neural pathways (Guha & Guhaniyogi. 2020).
1. Introduction
Equivariance has proven to be an effective approach for en- coding known structure about problem directly into neu- ral network's 's architecture, making learning more efficient and interpretable (Cohen & Welling, 2016; 2017; Qi et al., 2017; Ravanbakhsh et al., 2017: Zaheer et al., 2017: Cohen et al., 2018; Esteves et al., 2018; Kondor & Trivedi, 2018:
Kondor et al., 2018; Thomas et al., 2018; Weiler et al., 2018:
Maron et al., 2019a; Finzi al., 2021; Satorras al., 2021;
Villar et al., 2021; Yarotsky, 2022; Pearce-Crump, 2023).
Equivariant neural networks have been applied successfully in wide range of problems, including, but not restricted to, particle physics (Bogatskiy et al., 2020; Villar et al., 2021; Gong et al., 2022), biological and medical imaging (Bekkers et al., 2018; Lafarge et al., 2021; Suk et al., 2024), molecular and quantum chemistry (Thomas et al., 2018; Finzi al., 2020; Fuchs et al., 2020; Miller al., 2020; Schütt al.,
'Departeent of Mathematics, Imperial College London, United Kingdom. Correspondence to: Edward Pearce- Pearce-Crump <ep1011 @ic.ac.uk>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The range and nature of these applications highlight the

---

Permutation Equivariant Neural Networks for Symmetric Tensors
importance of achieving a complete and exact characterisa- tion of permutation equivariant linear functions applied to symmetric tensors. However, most studies in the existing machine learning literature on symmetric tensors focus only on equivariance to Euclidean groups, and no prior work on permutation equivariant neural networks has considered the situation where the only inputs are symmetric tensors.
A few prior works have characterised equivariant functions symmetric tensors, but none have provided an exact characterisation of permutation equivariant weight matrices for these tensors. Kunisky et al. (2024) used graph moments to characterise ((n)-invariant polynomials on symmetric tensors, while Blum-Smith et al. (2024) introduced a set of ("2 + functions that can universally approximate S, -invariaant functions on almost all real symmetric n n matrices.
To address this gap, we make the following contributions. We obtain a complete and exact characterisation of all per- mutation equivariant linear functions between any two sym- metric powers of I", deriving this result using two different bases. In particular, we show that, by embedding symmetric powers of R" into tensor power space, our characterisation includes all linear scalar-valued and vector-valued permu- tation equivariant functions that are defined on symmetric tensors. As corollary, we also recover the Deep Sets char- acterisation (Zaheer et al., 2017). Crucially, we address the implementation challenges that are associated with storing large weight matrices in memory by introducing what we call map label notation. This notation makes it possible for us to express the transformation of an input symmetric tensor by a permutation equivariant weight matrix as a se- ries of equations in the input tensor, eliminating the need to store the weight matrices explicitly in memory. In particular, we can then use the same set of equations to compute the transformation between symmetric tensors of fixed orders k and for any dimension n, climinating the need to generate separate weight matrices for each choice of n. We validate our approach on two toy problems and show that these func- tions exhibit high data efficiency and strong potential for generalising well to symmetric tensors of different sizes.
Permutation Equivariant Neural Networks. These neural networks have been constructed for a number of different types of data. They include permutation equivariant neural networks to learn from set-structured data (Qi et al., 2017: Zaheer al., 2017; Sverdlov et al., 2024); to learn mappings between different sized sets (Ravanbakhsh et al., 2017); to learn the interaction between sets (Hartford et al., 2018);
to learn from graphs and hypergraphs (Maron et al., 2019a;
Thiede et al., 2020; Finzi et al., 2021; Morris et al., 2022;
Godfrey et al., 2023; Puny et al., 2023; Pearce-Crump, 2024; Pearce- Pearce-Crump & Knottenbelt, 2024); and to learn from sets of symmetric elements (Maron et al., 2020). Pan & Kondor (2022) studied how to organise the computations that are involved in high-order tensor power networks. Other works have studied the expressive power of permutation equivariant neural networks (Keriven & Peyré, 2019; Maron et al., 2019b; Segol & Lipman, 2020; Yarotsky, 2022).
3. Symmetrie Powers of R"
We present the key definitions and concepts that are needed to study linear permutation equivariant functions on sym- metric tensors. We first introduce an action of S, on set of k-length indices S[n]* which will then index a basis of a real vector space, S (RR), known as the 1eth symmetric power of R". We let [m]] == {l...., n) throughout.
2. Related Work
We describe two important classes of related works.
Equivariant Machine Learning on Symmetrie Tensors. Most prior research on learning from symmetric tensors has only considered equivariance to Euclidean groups. Gao et al. (2022) applied tensor contractions to achieve (equivvauvv on high-order symmetric tensors, us- ing their network to simulate fluid systems. Lou & Ganose (2024) and Wen et al. (2024) each introduced (3)) equivariant graph neural networks to respectively discover highly anisotropic dielectric crystals and learn from elas- ticity tensors, which are fourth-order symmetric tensors that fully characterise a material's 's elastic behavior. Heilman et al. (2024) designed an S -equiiratvr graph neural network architecture to predict material property tensors directly from crystalline structures. Garanger et al. (2024) constructed neural network that is equivariant to subgroups of the orthogonal group On) in order to learn from sym- metric n x matrices, and applied it to the constitutive modelling of materials with symmetries.
Define the set Sin]]* to consist of all tuples of the form
= i i2....,
mi
my
such that p E [n), S in < is < ip S n, and Σ m, = k. By a "stars and bars" argument, we see that the cardinality of Sin]* is (k+z-1).
We obtain an action of the symmetric group S, on S[n] by applying the permutation to each element in the tuple and then reordering the result (via a permutation in Sy) to restore ascending numerical order.
Example I. Choosing the element (1, 1, 2,,, 3) of S[3]6 and applying the permutation (132) in Sş to it, we first obtain (3, 3, 3, 1, 1,2,2) 2) and then reorder it to to give another element of S[3]6.
Consequently, we define the th symmetric power of R., S (R*), to be the vector space that has standard basis
2

---

Permutation Equivariant Neural Networks for Symmetric Tensors
{ez} indexed by the elements of S[n].*. Moreover, we can raise the action of Sn on the set S(m]] representation of Sn. on & (IR") in the usual way; we call the representation itself pk.
we get that
f(er)= = Σ SI,res IES(M)
(7)
Given that Homs, (5 (,"), (R")) is subspace of Hom(5 (R²), S (IR") )), we have that f is an S.- equivariant linear map if and only if, for all a E Sn and standard basis elements e, S* (RR),
We wish to characterise full the linear permutation equiv- ariant functions between any two symmetric power spaces of R.. They are defined follows.
Definition 3.2. A linear map f (*R)) + (RR") is said to be permutation equivariant if, for all a E Sn and E S (IR")
( - of (o)][()))
(8)
(8) holds if and only if
[of(( - (f))(((())
E f1a(U))0c)) rES
Σ f1, TES|n]
(9)
We denote the vector space of all such maps by Homs, (S (BR))
for some [o( E S2 and To(T), E St that restores as- cending numerical order in (J) and ol) respectively.
Since our goal is to calculate all of the permutation equiv- ariant weight matrices that can appear between any two symmetrie power spaces of TR.", is enough to construct a basis of matrices for Homs,, (St (R"), St (RR)), by viewing it as a subspace of Hom(S* (R"), St (R")) and choosing the standard basis for each symmetric power space, since any weight matrix will be weighted linear combination of these basis matrices. This characterisation includes the following functions:
(9) now holds and only if
fo(()acnaa = fI,J for all E Sn. I E S(m]' and J E S|n]*.
(10)
Therefore, taking the Cartesian product set Sin]' x S[r] ()), we define an action of Sn.
and writing its elements S[n]' S'nn by
Proposition 3.3. Linear permulation equivariant scalar- valued and vector-valued functions symmetric tensors y in ( are elements of Homs,, (S* (IR"), (1z") and Homs, (S*()")) S' ()"),, respectively.
(4) = 3==(()maa
(11)
Consequently, (10) tells us that the basis elements of Homs.. (S* (R"), (IK") correspond bijectively with the orbits coming from the action of S,, on Sin]' x STn]*.
4. Orbit Basis of Homs,
We construct our first basis of Homs, (S*( S (R") by associating the basis with the orbits of action of S, the Cartesian product set S[n]'' x S[n]* and understanding each orbit as a diagram. We begin with the following result.
Now, consider an orbit coming from the action of S, on Sin]' x S[m]². Suppose that ()) is a class representative. We form diagram in the following way:
Proposition 4.1. There is a basis of Homs,, (S*)))) (R"")) that corresponds bijectively with the orbits coming from the action of Sn on the set S|n]l S[n]*.
We place the values of / one row and the values of J in a second row directly below it. For each value x E [n]. x appears either I or J, then we insert a central green node between the two rows and connect it to every occurrence of x: drawing edges downward from entries in / and upward from entries in J. If a does not appear in either row, then no central green node is added.
We see that the vector space (R"), has a standard basis of matrix units
Proof.
(Er,J (eess))),esss[)
(4)
where E1,J has 1 in the J) position and is elsewhere
Example 4.2. Suppose that = 6, k = 4, and n = 3. Consider the S3 orbit of S[3]6 x S13) that contains the element (111233)
Hence, for any standard basis element ep E 5* (R"),, we have that
1123
Eijepp = ôJ.pes
(5)
Then, by the construction given above, obtain
and so, for any linear map f (RR") + St (RR), express- ing f in the basis of matrix units as
3
(12)
f Σ Σ fI,
(6)
[ESTN J
3
3

---

Permutation Equivariant Neural Networks for Symmetric Tensors
2
reurder
4
and propagate
2
3
4
6
Figure For the (9, 7) bipartition (33 11, [2, 2), [2, 1], [1, [1, [1,0]]. show how obtain the element the corresponding So orbit
of S[6]" x S'6]" that comes from labelling its blocks with the 5-length tuple (6, 2,3, 1, 1,4.. By reordering the labelled green nodes of the (9, orbbtt bipartition diagram propagating these values to the ends of the wires, we see that this element (1132236
Removing the labels gives the diagram that corresponds to the orbit.
which is the same (4, -r-brit bipartition diagram (12), except the spiders are in different order. However, the underlying (4, 6),66) biparttiiss are the same.
This diagram is, in fact, diagrammatic representation of (ks, -ipiarrtiiio having at most n. blocks that for now we call a (ke oorit bipartition diagram. We define bipartitions below.
Remark 4.5. Example 4.4 highlights an important point: in drawing a (k. l)-orbit bipartition diagram for a (k, ()- hipartition, the order of the spiders corresponding to the blocks does not matter. Hence each (A, ()-bri bipartition diagram represents entire equivalence class of diagrams that correspond to (k, () bipaaiiiiin.iinnn
Definition 4.3. A (k, 1) bipparttiiooon having some blocks the set
(13) of f pairs [ yi] such that v,, 2 for all i, not both zero, such that Ei= 24 = l and Et=1 Y/ = These were first introduced and studied by Major Percy A. MacMahon (1893; 1896; 1899; 1900; 1906; 1908; 1912; 1918). For (ks, orbit bipartition diagrams, call the blocks spiders and the black edges wires, referring to them input wires or output wires, as appropriate.
V1), [x2, v2). v2l........ ... [st, [e]]
Now, we also see that such (A:, I) bi-iiarrttiions having at most blocks must appear in this process: representing each (k, -ipparttiin having some [ni] blocks (of the form (13)) as a (As, 1)-orbit bipartition diagram by connecting, for each i E [t]. x; wires from below and wires from above to a central green node, we obtain its orbit by following the six steps in the bluc-coloured box below.
The number of (k: ()bbipartstions having at most n blocks the value Pa (k, 1). We provide a novel procedure for how to generate (k:, b)-biarttiiio having at most n blocks, and hence determine Pa 1k), in Appendix B.
1. Form all possible t-length tuples with elements in [n]. not allowing for repetitions amongst the elements.
Note that the (k, bi-biaartiiion that is obtained from an S,, orbit is independent of the choice of class representative: if we choose (=(()=(())))) instead and form diagram using the same procedure given in the red-coloured box above, then the spiders that appear in each of the diagrams (viewed without their labels) will be the same, just potentially in different order. However, both diagrams give the (k:, 1)-bii bipartition.
2. Then, for each (-length tuple, label the central green nodes in the diagram from left to right with the elements of the tuple.
(J)))
3. If necessary, reorder the spiders that they appear from left to right in increasing order of their labels.
Then, for each spider, propagate the block label to the end of each wire.
Example 4.4. Continuing on from Example 4.2, we see that (122333) is in the same orbit as (111233), ), since it is obtained by applying the permutation (132) to (111233). then apply- ing permutations in Sg and S₃ to reorder each component into ascending numerical order. Hence, by applying the procedure given above to 1233 obtain the diagram
5. This produces the element (+), where the top row's labels are and the bottom row's labels are
6. Doing this for each t-length tuple gives the entire Sn orbit.
(122333)
Example 4.6. In Figure 1, we give an exam- plc of how to obtain, for the (9, biipaaiinonniiion [(3, 11, [2, 21, [2, 1], [1, [}, the element in the corresponding Sg orbit S(6) x Si6] that comes from labelling its blocks with the 5-length tuple (6, 2, 1,1,4,
3
(14)
3

---

Permutation Equivariant Neural Networks for Symmetric Tensors
In particular, by reordering the labelled green nodes of the corresponding (9, orbit bipartition diagram and propagating these values to the ends of the wires, we see that this element is (122331066)
Hence, the Sg-equivariant weight matrix from S²(R2) to 5t (TR3) is of the form
1.1
1
2
2,3
3,3
X1
X
X
X2
A
X2
Hence, overall, we have shown the following result:
X2
X
A
X1
A
X2
(16)
Proposition 4.7. The orbits that come from the action of Su on S(n]'' x S(n]* correspond bijectively with the (k, 1)- bipartitions (or (k, lorbi bipartition diagrams) having at most blocks.
A2
A
A
X2
A
A1
for weights λI, A2, A3, d E E.
5. Diagram Basis of Homs, (S (R*), S (RR")
Combining Proposition 4.1 and Proposition 4.7, we obtain
We are able to obtain Homs, (S* (RT), (R")) that we will show is more efficient for performing linear transformations in the following section. To obtain this second basis, we first need to define the following vector space and reformulate the construction given in the previous section as linear map.
second basis of
Theorem 4.8. There is a basis of Homs,, (I*T), St (I")) that corresponds bijectively with the (k:, biparrtiiiss hav- ing most n blocks. Consequentl, its dimension is py (r(kk,) I). Moreover, call this basis of Homs, (S* (RR) S' (R")) the orbit basis.
To find the orbit basis element X in Homs, (B"), S' (RT)) that corresponds to (ke, []- bipartition ı having at most n blocks, we represent i as a (ki ()-orbit bipartition diagram In and follow the same steps through 5 inclusive as before, except we now form the matrix unit Er,J from each element (+) that comes
Definition 5.1. We define the formal R-linear span of the set of all (k. orbit bipartition diagrams to be the vector space S (n). We call this vector space the spherical par- tition vector space since is an adaptation of the spherical partition algebra that was first discovered by Bastías et al. (2024). We also call the generating basis the orbit basis of (n).
from t-length tuple. Adding together all of these matrix units (over all of the tuples) gives Xx. Hence have the following corollary:
Definition 5.2. For all non-negative integers k, and posi- tive integers n, we define a surjective map
Corollary 4.9. The Se-equivvrian weight matrix from St (B") to (RR") ) is En,>,,, for weights \n, where the sum is over all (k, -ibiaaartissons having most n blocks.
T n. (P.(m) + Homs,, (S* S²
(17)
on the orbit basis of (n) as follows, and extend linearly:
Example 4.10. Continuing on from Example 4.6, see that the (111223) 1236,
(2334666))entty of the basis matrix X in Homs, ( (IR", S7 (R)) corresponding to the (9, 7)- bipartition = [[3, 1], 22 2), [2, 1], [1, [1, {}} is 1.
Xa if has n or fewer blocks if has more than blocks (18)
In the Appendix, we provide a general procedure summaris- ing the results above for calculating the equuqivvari weight matrix from (IR") to St (IR") from all of the (I= orbit bipartition diagrams having at most blocks.
We now introduce a new diagram da for each (k: 1)- bipartition म.: it is formed exactly the same way as a (k, (krb)t bipartition diagram, except the central green nodes are now filled in. We call such a diagram a (k,, l)- bipartition diagram.
Example 4. 1. Suppose that we would like to find the S3- equivariant weight matrix from (RR) S (IR) R
Example 5.3. Let n be the (9, biipattiin
We need to consider the (2, orbbt bipartition diagrams having at most n 3 blocks. They are
= (3, 1). [2, 2),2),22 (. [1, [1,3), [1,0]}
(19)
Then its corresponding (9, 7) bipartition diagram, d,, is
(15)
(20)
Each of these four diagrams corresponds to an orbit basis matrix in Homs, (oom,((2))) (13),, S (R3)) of size 3 x 6. Example C.1 gives the calculations of these matrices.
As with the orbit bipartition diagrams, the order of the spi- ders corresponding to the blocks does not matter in drawing the bipartition diagram.
5

---

Permutation Equivariant Neural Networks for Symmetric Tensors
A General Procedure for Caleulating the S, -n-Equiivariant Weight Matrix from 5* to S (RR)) using the Diagram Basis of (n).
Perform the following steps:
1. Calculate all of the (k, bippaaattisss и that have at most n blocks, and express each (), -)ppaattiiooo ग as a (k, bibbaarttinoo diagram d,y in (n)...
2. Then, if / is the number of blocks in form all possible I-length tuples with elements in [n], allowing for repetitions amongst the elements.
3. For each t-length tuple, label the central green nodes in dg from left to right with the elements of the tuple. Reorder the spiders in d, such that they are in increasing order from left to right. Fuse together any spiders whose central green nodes are labelled with the same value. Then, for each spider, propagate the block label to the end of each wire. We obtain the matrix unit F from this diagram by setting to be the labels in the top row and J to be the labels in the bottom row.
4. Since each tuple corresponds to obtain the basis matrix D that is associated with d, Attach weight X IK to each matrix Dz. Finally, calculate Σ Au Dr to give the overall weight matrix.
matrix unit, add together all of the resulting matrix units from all of the tuples
We define dy to be an element of (n) as follows:
where b(0) is the number blocks in 0. Now define
d Σ re
(21)
D
Σ
X
(25)
ST 1-,0, b(A)
where = is the partial order defined on all (ks biparrttsss as follows: such that each pair in appears in exactly Example 5.4. We see that if π = {[L, 1], []] then, by (21), we have that
Clearly, Dr an element of Hom,, (S"),, St (R")).
if every pair in 0 is the sum of pairs in æ
Hence we have defined 0 (ddr) = Dx. O becomes map on S (n) by extending the definition by linearity to the entire diagram basis of S ( We claim the following.
sum.
Theorem 5.7. For all non-negative integers k. and positive integers n, the (Dx dy has most n blocks) forms basis of Homs, (St (R"), (R")) (RR))). We call this basis the diagram basis of Homs,, (S* (R") In particular, the map O km is surjective.
(22)
Lemma 5.5. The set of (k,1)- -iipapattnnioon diagrams {dz)
Note that whilst O is defined all diagram basis elements in (n), is only those that have at most n blocks whose image under O creates a basis of Homs, S""), lowing corollary.
forms basis of (n). We call this basis the diagram basis of (n).
We can combine the results in this section to define another map
In particular, we have the fol-
Corollary 5.8. The Sn-equivariant weight matrix from S* (R") to St ((R") is Ex Dr for weights Xg. where the sum over all (ks, (h.1))bipe I)-biaartiiions having at most blocks.
% SP)(() + Homs, (S* (IR")) ((R))
(23)
this time on the diagram basis of (n).
Definition 5.6. We define O (dz) in the following way. First change the basis in SP (n. from the diagram basis to the orbit basis using (21), and then apply Ty Th to each of the orbit basis diagrams that appear in (21) for dz. We get that O (dx) is defined to be
We would like to be able caleulate the diagram basis of Homs, (R"), St sis of SPE(n), without having to go via the orbit basis of SP We claim the following:
(IR)) directly from the diagram ba-
Proposition 5.9. The diagram basis element Dr in Homs, (S* ((R")) that corresponds to a (k, l)- bipartition diagram d, having some S n blocks can be found as follows: we follow the same steps through
Tt k.
Σ 3o
Σ
(x0)
Σ
Xa
(24)
T50, b(0)
6

---

Permutation Equivariant Neural Networks for Symmetric Tensors
reorder
and fuse
2
Figure 2. After labelling the central green nodes of (5, 4) bipartition diagram with the tuple (1, 1) and reordering the spiders into ascending numerical order, we fuse together any spiders that are labelled with the same value.
inclusive in the blue-coloured box as before, except in Step I we now allow repetitions amongst the elements in each t-length tuple, and in Step 3, after reordering the spiders, we fuse together any central green nodes that are labelled with the same value. See Figure for an example. Adding together all the resulting matrix units gives Da-
the unrolled S, -quuqivvri weight matrix, and the process of representing the original matrix in this way unrolling.
The e)netry in the unrolled weight matrix is the same as the (I ) in W, where Ty JJJ are any permutations Sj and Sg. respectively, that restore ascend- ing numerical order in I and J, respectively.
In the orange-coloured box, we provide general proce- dure for calculating the Sq--quivariant weight matrix from S* (RR") to St (IR*) using the diagram basis of SPA (n). Example 5.10. We return Example 4. 4.11 and calculate the Sy-equivariant weight matrix from S (133) S (R²) using the diagram basis of SP (3) instead.
This is because the hthh symmetric power of R can be thought of as the quotient space of (I"))* by the ideal generated by elements of the form x & y @ x.
The benefit of unrolling an S,,-equivariant weight matrix to become map from (I to (IR ) that we can now operate symmetric tensors in (R2)00 whilst retaining the original properties of the matrix. Going forward, we now consider any weight matrix to be in its unrolled form. Example 6.1. Continuing on from Example 4.11, we see that the unrolled Sy-equivariant weight matrix from (RR3) to R is
We now consider the (2, 1) bipartiition diagrams having at most 3 blocks:
(26)
1,2
1,3
2,1
2.2
233
3,1
3,2
3,3
1
X
A
A
A
A2
A4
Aa
Aa
A2
2
A2
A
A4
A
A
A
A4
A2
(28)
As before, the calculations of the corresponding matrices given in Example C.2.
3
A2
Aa
Ag
A4
A2
A
A
A
Hence, the Sgeqquivariant weight matrix from (RR) to S (RR)) using the diagram basis is of the form
7. Map Label Notation
In practice, when it comes to implementing the transforma- tion of an imput tensor T by an unrolled weight matrix W, expressed in tensor form, restrictions on memory make impractical for the entire weight matrix be stored in mem- ory. Instead we use what term map label notation to describe, for each basis matrix D, that appears in W, the transformation of an input T into its output D, (T'). It is here where the diagram basis shines over the orbit basis, in that it much easier to vectorize the map label for each diagram basis element, since includes, as a result of (21), all labels that come from all of the possible fusings of the spiders in the bipartition diagram d, that corresponds to D.. In fact, instead of calculating separate weight matrix explicitly for each value of when 2 1 + k. we will see that a single set of map labels can be used to obtain the trans- formation for any value of n, and, when n < [ k. we only need to retain map labels that come from (k, bipparttiii diagrams having most blocks. Consequently, the only
1,1
1.2
1,3
2,2
2,3
3,3
1,2,3,4
A
22,4
X4
22,4
2
22,1
A
\1
21,2,3,
A3,1
22,4
(27)
X2,4
Aa
A3.4
X2,4
11,2,3.4
for weights A2; λ3, A4 R, where AA Eiea Ao.
Remark 5.11. In Example C.3 in the Appendix, we show that we can recover the Deep Sets (Zaheer et al., 2017) characterisation of any -quequuivai weight matrix from 1. R using the diagram basis of SP] (n).
6. Embedding into Tensor Power Space
There is a useful way of representing any S Sy-equivvriant weight matrix W from (*(R") ) to S' (IR)) as a matrix from (R") to (R namely by embedding S* (R²) into (R and similarly for St (R.). We call the latter matrix

---

Permutation Equivariant Neural Networks for Symmetric Tensors
requirements on memory come from needing store the input tensor 7 and the output tensor (T) in memory.
SymmPermEquiv
Definition 7.1. Let dz be a (k:, 1) bibiiaatiniion diagram. We associate to d a set of map labels, where each map label consists of an arrow f. fixed pattern of indices I on its left hand side, and, on its right hand side, formal linear combination of tuples of indices that are associated with I.
100
80
Test MSE
60
We immediately use each map label for dz to obtain the values in Dr (2'), for unrolled Da and input tensor T E (R")) by replacing, in each map label, by D* and each tuple that appears on the right hand side by Ty, and treating the result as map that describes how to find Dx(TT) ,. The resulting transformation map labels coming from all of the map labels ultimately determine D (T).
40
20
0-
We have provided a full procedure for how to obtain the map labels and the resulting transformation for any (k, bipartition diagram dx and for any value of in the green- coloured box. The implementations of Subprocedures I to V, along with illustrative examples for each, are provided in Appendix D. We give definitions of the important terms that appear in the procedure below.
500
1000
1500
2000
2500
3000
2500
4000
Training Set Size
Figure 3. Data efficiency for the synthetic S12-invariant task. The shaded regions depict 95% confidence intervals taken over 3 runs.
Definition 7.2. Let d, be (R:, bippaaatinooon diagram. A grouped output for d is any tuple of labels that can be obtained by labelling all the spiders that have output wires, allowing repeats, sorting the spiders in decreasing order of output wires, propagating the labels to the ends of the out- put wires, and reading off the resulting tuple. A partially labelled diagram of dz identical to d,, except all spiders that have output wires are assigned a label, allowing repeats. A fully labelled diagram of d, is identical to dz, except now all spiders are assigned label, allowing repeats. A grouped map label is obtained from a fully labelled di- agram of dx by propagating the labels to the ends of the wires, placing the tuple on the output wires to the left of an arrow _ and placing the tuple on the input wires to the right of the arrow. A left grouped map label is obtained from a grouped map label by unrolling only the right hand side of grouped map label, and replacing - with /g
DT (T);
Σ j=1
[ T3a1
Tí
(31)
3 3
D (T); =
Σ j=1k=1
Ti
(32)
where i [3].
However, the power of this method lies in the fact that if n 2 3, then only need change the value 3 in each sum to and if 2, then we remove n and change the value 3 in each sum to 2.
8. Numerical Experiments
We demonstrate our characterisation the following toy experiments.
Example 7.3. Continuing on from Example 5.10, and con- sidering once again the (2, 1) -iiipaatiiioon diagrams having at most n = blocks given in (26), we show in Example D.7 that the transformations corresponding to each (2, 1)- bipartition diagram, for 3. are fully determined by the following transformation map labels in this case, only one for each (2, 1) bipaartiiin diagram:
Inv-riitr Task: We evaluate our model on synthetic -ig-invariant task given by the function f(T) == Σ. Te,j. where a 3-order symmetric tensor. We demonstrate the high data efficiency of our model compared with a standard MLP for this task, as shown in Figure We attribute this superior performance our model's strong inductive bias.
Dz, (T"; -Tis
Sg E-uivariiian Task: We evaluate our model on syn- thetic Sg-cquivariant task from (R$)63 to IR namely, to extract the diagonal from 8 x 8 x 8 symmetric tensors. We (30) evaluate our model against a standard MLP and a standard Sg Ss-equivariant model from (R&) 83 to R&. We show the Test
(29)
D (T), Σ
Tjj
j=1
8

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Procedure: Generation of the Transformation Map Labels That Describe the Transformation Corresponding to a (A: -iiiaartiiio Diagram of a Symmetrie Tensor in (IR") yok a Symmetric Tensor in (R"))o.
Input: A (k. I) bipartition diagram dx and value of n.
1. Apply Subprocedure I obtain all possible grouped outputs for du. and for each one, its associated set of partially labelled diagrams, where only spiders that have output wires are labelled in these diagrams.
2. For each grouped output for dz:
(a) Apply Subprocedure to each partially labelled diagram in the grouped output's associated set. Take the set union of all fully labelled diagrams that are returned from each call the subprocedure, giving a of fully labelled diagrams that associated with the grouped output.
(b) Remove all fully labelled diagrams in the set with more than n spiders. If the set becomes empty, delete the grouped output and proceed to the next iteration of the loop.
(c) Apply Subprocedure III to each fully labelled diagram convert it into grouped map label.
(d) For each grouped map label, apply Subprocedure to unroll its right hand side, returning left grouped map label.
(e) Formally add together the right hand side of the resulting left grouped map labels, creating one left grouped map label that is associated with the grouped output.
(f) Unroll the left hand side of the left grouped map label according Subprocedure V obtain set of map labels that associated with the grouped output.
3. The union the resulting map label sets from all grouped outputs are the map labels that correspond to the (ke, bipaarttitiion diagram d,.
4. Finally, for each map label in Step 3, convert each index J on the right hand side to be TJ, and convert the index / on the left hand side to be Dr(T), to obtain its corresponding transformation map label.
Output: A set of transformation map labels describing the transformation D of symmetric tensor T (R") to symmetric tensor (T) E (R")@t for the given value of n, where D2 corresponds to the (k: bbipaaiiiaoniiion diagram dz.
Mean Squared Error (MSE) for each of these models in Ta- ble Furthermore, Table shows that the network appears to generalise well to symmetric tensors having different sizes, even though it was trained on symmetric tensors of a particular size.
9. Conclusion
We obtained a complete characterisation of permutation equivariant linear functions between symmetric powers of R" using two different bases. This characterisation includes all scalar-valued and vector-valued permutation equivariant functions symmetric tensors in ) We introduced map label notation to address limitations memory, en- abling the efficient transformation of input tensors without explicitly storing large sized weight matrices in memory. We validated our approach through two toy examples and demonstrated the potential for transfer learning symmet- ric tensors of different sizes.
Method
Test MSE
MLP
0.6486
PermEiquiv
0.0447
SymmPermEquiv
0.0035
Table 1. Diagonal Extraction
A Acknowledgements
16
32
The author is deeply grateful to Chen Lin for his valuable insights and constructive discussions on designing experi- ments. This work supported by the UKRI-EPSRE grant EP/Y028872/1, Mathematical Foundations of Intelligence: An Erlangen Programme" for Al.
Test MSE
0.0035
0.0048
0.0088
Table 2, Generalisation

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Impact Statement
Bogatskiy, A., Anderson, B., Offermann, J., Roussi, M.,
Miller, D., and Kondor, R. Lorentz Group Equivariant Neural Network for Particle Physics. In International Conference on Machine Learning, pp. 992-1002. PMLR, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Carlitz, L. A Problem in Partitions. Duke Mathematical Journal, 30(2):203-213, 1963.
References
Anandkumar, A., Ge, R., Hsu, D. J., Kakade, S. M., and Tel- garsky, M. Tensor Decompositions for Learning Latent
Carlitz, and Roselle, D. P. Restricted Bipartite Partitions. Pacific Journal of Mathematics, 19(2):221-22 -228, 1966.
Variable Models. Journal of Machine Learning Research, 15:2773-2832, 2014.
Chatzipantazis, E., Pertigkiozzolou, S., Dobriban, E., and Danilidis, K. 3E(3)--qqivarrint Attention Networks for Shape Reconstruction Function Space. In The Eleventh International Conference on Learning Representations, 2023.
Andrews, G. F. An extension of Carlitz's s bipartition identity. Proceedings of the American Mathematical Society, 63 (1):180-184 184, 1977.
Andrews, G. The Theory of Partitions, volume 2. Cam- bridge University Press, 1998.
Cohen, T. and Welling, M. Group Equivariant Convolutional Networks. In Proceedings of The 33rd International Con- ference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2990-2999, New York, USA, 20-22 Jun 2016 PMLR.
Andrews, G. E. and Paule, P. MacMahon's Dream. In Partitions, q-Series, and Modular Forms, volume 23 of Developments in Mathematics, pp. 1-12. Springer, New York, NY, 2012.
Cohen, T. and Welling, M. Steerable CNNs. In International Conference on Learning Representations, 2017.
Auluck, F. C. On Partitions of Bipartite Numbers. Math- ematical Proceedings of the Cambridge Philosophical Society, 49(1):72 1953.
Cohen, T., Geiger, M., Köhler, J., and Welling, M. Spher- ical CNNs. In International Conference on Learning Representations, 2018.
Bastías, K. O., Martin, P. and Ryom-Hansen, S. On the spherical partition algebra, 2024.
Deng, C., Litany, O., Duan, Y., Poulenard, A., Tagliasacchi, A., and Guibas, L. J. Vector Neurons: A General Frame- work for S0(3) Eqqii--qqia Networks. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pp. 12200-12209, 2021.
arXiv:2402. 01890.
Batatia, I., Kovacs, D. P., Simm, G., Ortner, C., and Csanyi,
G. MACE: Higher Order Equivariant Message Passing Neural Networks for Fast and Accurate Force Fields. In Advances in Neural Information Processing Systems, vol- ume 35, pp. 11423-11444 11436, 2022.
Esteves, C., Mel-Alle-lanchee Blanchette, C., Makadia, A., and Dani- ilidis, K. Learning SO(3) Equivariant Representations with Spherical CNNs. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 52-68, 2018.
Batzner, S., Musaelian, A., Lixin Sun, M. G., Mailoa, P., Kornbluth, M., Molinari, N., Smidt, T. E., and Kozin- sky, B. E(3--equivariant graph neural networks for data- efficient and accurate interatomic potentials. Nature Com- munications, 13:2453, 2022.
Esteves, Xu, Y., Allen-Blanchettee C., and Daniilidis, K. Equivariant Multi- Networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Bekkers, E. J., Lafarge, M. W., Veta, M., Eppenhof, K. A. J., Pluim, J. P. W., and Duits, R. Roto-Translation Covariant Convolutional Networks for Medical Image Analysis. In Medical Image Computing and Computer Assisted Intervention-MICCAI 2018: 21st International Conference, Granada, Spain, September 16-20, 2018 Proceedings, Part I, pp. 440-448. Springer International Publishing, 2018
Finzi, M., Stanton, S., Izmailov, P., and Wilson, A. G. Gener- alizing Convolutional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data. In Proceed- ings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 3165-3176. PMLR, 13-18 Jul 2020.
Blum-Smin Smith, B., Huang, N., Cuturi, M., and Villar, S. Learning functions on symmetric matrices and point clouds via lightweight invariant features, 2024. v: v:255:2405.0 08097.
Finzi, M., Welling, M., and Wilson, A. G. A Practical Method for Constructing Equivariant Multilayer Percep- trons for Arbitrary Matrix Groups. In Proceedings of the
10

---

Permutation Equivariant Neural Networks for Symmetric Tensors
38th International Conference on Machine Learning, vol- 139 of Proceedings of Machine Learning Research, pp. 3318-3328. PMLR, 18-24 Jul 2021.
Heilman, A., Schlesinger, C., and Yan, Q. Equivariant Graph Neural Networks for Prediction of Tensor Material Properties of Crystals, 2024. arXiv:2400 03563.
Fuchs, F. B., Worrall, D. E.,, Fischer, V., and Welling, M. tEns)-transformrs:: 3D roto-transkation equivariant atten- tion networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Hoogeboom, E., Satorras, V. G., Vignac, C.,, and Welling, M. Equivariant Diffusion for Molecule Generation in 3D. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 8867-8887, PMLR, 17- 23 Jul 2022.
Gao, L., Du, Y., Li, H., and Lin, G. RetEqNet: Rotation- equivariant network for fluid systems with symmetric high-order tensors. Journal of Computational Physics, 461:111205, 2022.
Jaffe, A., Weiss, R., Nadler, B., Carmi, S., and Kluger, Y. Learning Binary Latent Variable Models: Tensor Eigenpair Approach. In International Conference on Machine Learning, pp. 2196-2200 PMLR, 2018.
Garanger, K., Kraus, J., and Rimoli, J. Symmetry- enforcing neural networks with applications to consti- tutive modeling. Extreme Mechanics Letters, 71:102188, 2024.
Kaba, S.-O., Mondal, A. K., Zhang, Y., Bengio, Y., and Ravanbakhsh. S. Equivariance with Learned Canonical- ization Functions. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 15546- 15566. PMLR, 23-29 Jul 2023.
Georgii, E., Tsuda, K., and Schölkopf, B. Multi-way set enumeration in weight tensors. Machine Learning, 82: 123-155, 2011.
Keriven, N. and Peyré, G. Universal Invariant and Equiv- ariant Graph Neural Networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ghoshdastidar, D. and Dukkipati, A. Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques. Journal of Machine Learning Research, 18 (50): 2017.
Khouja, R. Optimization algorithms for the tensor rank approximation problem: application to clustering in ma- chine learning. PhD thesis, Université Côte d' Azur; Uni- versité Libanaise, 2022.
Godfrey, C., Rawson, M. G., Brown, D., and Kvinge, H. Fast computation of permutation equivariant layers with the partition algebra. In ICLR 2023 Workshop on Physics for Machine Learning, 2023.
Kim, J. K. and Hahn, S. G. Partitions of bipartite numbers. Graphs and Combinatorics, 13:73-78, 1997.
Kondor, R. and Trivedi, S. On the Generalization of Equiv- ariance and Convolution in Neural Networks to the Action of Compact Groups. In Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2747- 2755. PMLR, 10-15 15 Jul 2018
Gong, S., Meng, Q.. Zhang. J., Qu. H., Li, C., Qian, S., Du, W., Ma, Z.-M., and Liu, T.-Y. An Efficient Lorentz Equiv- ariant Graph Neural Network for Jet Tagging. Journal of High Energy Physics, 2022(7):1-22, 2022.
Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. Permutation Equivariant Models for Compositional Generalization in Language. In International Conference on Learning Representations, 2020.
Kondor, R., Lin, Z.., and Trivedi, S. Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network. In Advances in Neural Information Processing Systems, volume 31, 2018.
Goulart, J. H. M., Couillet, R., and Comon, P. A Random Matrix Perspective Random Tensors. Journal of Ma- chine Learning Research, 23(264):1-36, 2022.
Kunisky, D., Moore, C., and Wein, A. S. Tensor cumulants for statistical inference invariant distributions, 2024. a arxiv: ::: 2404 18735.
Guha, S. and Guhaniyogi, R. Bayesian Generalized Sparse Symmetric Tensor-on- Vector Regression. Technometrics, 6302)1160-170, 2020.
Lafarge, M. W., Bekkers, E. J., Pluim, J. P. W., Duits, R., and Veta, M. Roto-translation equivariant convolutional networks: Application to histopathology image analysis. Medical Image Analysis, 68:101849, 2021.
Hartford, J. S., Graham, D. R., Leyton- K., and Ravanbakhsh, S. Deep Models of Interactions Across Sets. In Proceedings of the 35th International Conference on Machine Learning, pp. 1914-1923. PMLR, 2018
Landman, B. M., Brown, E. A., and Portier, F. J. Partitions bi birptrtite numbers into at most j parts. Graphs and Combinatorics, 8:65-73, 1992.

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Liao, Y.-L. and Smidt, T. Equiformer: Equivariant Graph Attention Transformer for 3D Atomistic Graphs. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. In- variant and Equivariant Graph Networks. In International Conference on Learning Representations, 2019a.
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. On the Universality of Invariant Networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4363 4371. PMLR, 09-15 Jun 2019b.
Lou, Y. and Ganose, A. M. Discovery of highly anisotropic dielectric crystals with equivariant graph neural networks, 2024. arXiv: 2405. 07915.
MacMahon, P. A. XVII Memoir on the Theory of the Compositions of Numbers. Philosophical Transactions of the Royal Society of London. (A.), 184:835-901, 1893.
Maron, H., Litany, O., Chechik, G., and Fetaya, E. On Learning Sets of Symmetric Elements. In Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Machine Learning Research, pp. 6734-6744, PMLR, 13-18 Jul 2020.
MacMahon, P. A. XVI. Memoir the Theory of the Par- tition of Numbers. Part I. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 187:619-673, 1896.
Mathews, G. B. On the partition of numbers. Proceedings of the London Mathematical Society, s1-28(1):486449)) 1896.
MacMahon, P. A. Memoir on the Theory of the Partitions of Numbers. Part II. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 192:351-48 1899.
McCullagh, P. Tensor Methods in Statistics. Courier Dover Publications, 2018.
MacMahon, P. A. Combinatorial Analysis. The Foundations of New Theory. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 194:361-386,
Miller, B. K., Geiger, M., Smidt, T. E., and Noé, F. Relevance of rotationally equivariant convolutions for predicting molecular properties. arXiv preprint wrXiv:208.08866/ 2020.
1900.
Morris, C., Rattan, G., Kiefer, S., and Ravanbakhsh, S. SpeqNets: Sparsity-aware Permutation-cquivare graph networks. In Proceedings of the 39th International Con- ference on Machine Learning, volume 162, pp. 16017- 16042, 17-23 Jul 2022.
MacMahon, P. A. Memoir on the Theory of the Partitions of Numbers. Part III. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 205:37-59, 1906.
MacMahon, P. A. II. Second Memoir on the Composi- tions of Numbers. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 207(413-426)) 65-134, 1908.
Nanda, V. Bipartite partitions. Mathematical Proceedings of the Cambridge Philosophical Society, 53(2):273-277, 1957.
Pan, H. and Kondor, R. Permutation Equivariant Layers for Higher Order Interactions. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 5987-6601. PMLR, 28-30 Mar 2022.
MacMahon, P. A. III. Memoir on the Theory of the Parti- tions of Numbers. Part V. Partitions in Two-Dimensions Space. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 211(471-433):5-
1912.
MacMahon, P. A. Seventh Memoir on the Partition of Num- bers. A Detailed Study of the Enumeration of the Parti- tions of Multipartite Numbers. Philosophical Transac- fions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 217: 81-113, 1918.
Pearce- Carcee-rrupp E. Brauer's Group Equivariant Neural Net- works. In Proceedings of the 40th International Confer- ence on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 27461-27482. PMLR, 23 29 Jul 2023.
Marcos, D., Volpi, M., Komodakis, N., and Tuia, D. Rota- tion Equivariant Vector Field Networks. In Proceedings of the IEEE International Conference on Computer Vi- sion, pp. 5048-50555 2017.
Pearce-Crump. E. Connecting Permutation Equivariant Neu- ral Networks and Partition Diagrams. In Proceedings of the 27th European Conference on Artificial Intelligence, volume 392, pp. 1511-1518. IOS Press Ebooks, 2024.
12

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Pearce-Crump. E. and Knottenbelt, W. J. Graph Automor- phism Group Equivariant Neural Networks. In Proceed- ings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learn- ing Research, pp. 40051 40077. PMLR, 21-27 Jul 2024.
Sverdlov, Y., Springer, I., and Dym, N. Revisiting Multi- Permutation Equivariance through the Lens of Irreducible Representations, 2024, arXiv:2410 06665.
Thiede, E. H., Hy, T. S., and Kondor, R. The gen- eral theory of permutation equivarant neural networks and higher order graph variational encoders, 2020. a arXiv: 2004. 03990.
Petrache, M. and Trivedi, S. Position Paper: Generalized grammar rules and structure-based generalization beyond classical equivariance for lexical tasks and transduction, 2024. a arxiv: 2402. 01 629.
Thomas, N., Smidt, T., Kearnes, S., Yang, L., Li, L., Kohlhoff, K., and Riley, P. Tensor field networks: Rotation-and translation-equivariie neural networks for 3d point clouds, 2018. arXiv: 1802 08219.
Puny, O., Lim, D., Kiani, B., Maron, H., and Lipman, Y. Equivariant Polynomials for Graph Neural Networks. In International Conference Machine Learning, pp- 28191-28222. PMLR, 2023.
van der Pol, E., Worrall, D., van Hoof, H., Oliehoek, F, and Welling, M. MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 33, pp. 4199 4210, 2020.
Qi. C. R., Su, H., Mo, K., and Guibas, L. J. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 652-660, 2017.
Villar, S., Hogg, D. W., Storey-Fisher, K., Yao, W. and Blum-Smith, B. Scalars are universal: Equivariant ma- chine learning, structured like classical physics In Ad- vances in Neural Information Processing Systems, 2021.
Ravanbakhsh, S., Schheider, J., and P6czos, B. Equivari- ance Through Srrameter-Sharing In Proceedings of the 34th International Conference on Machine Leurning, vol- ume 70, pp. 2892-2901, 06-11 11 Aug 2017.
Wang, D., Jia, M., Zhu, X., Walters, R., and Platt, R. On- Robot Learning with Equivariant Models. In 6th Anmual Conference on Robot Learning. 2022a.
Satorras, V. G., Hoogeboom, E., and Welling, M. E(n) Equivariant Graph Neural Networks. In Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pp.
Wang. D., Walters, R., and Platt, R. SQuia--Euivarian Reinforcement Learning. In International Conference on Learning Representations, 2022b.
PMLR, 18 24 Jul 2021.
Wang. D.,, Walters, R., Zhu, X., and Platt, R. Equivariant Q Learning in Spatial Action Spaces. In Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pp. 1713- 1723. PMLR, 08-11 Nov 2022c.
Schütt, K., Unke, O., and Gastegger, M. Equivariant Mes- sage Passing for the Prediction of Tensorial Properties and Molecular Spectra. In Proceedings of the 38th In- ternational Conference on Muchine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9377-9388. PMLR, 18-24 Jul 2021.
Weiler, M. and Cesa, G. General E(2)-Equivariant Steerable CNNs. In Advances in Neural Information Processing Systems, volume 32, 2019.
Segol, N. and Lipman, Y. On universal equivariant set networks. In International Conference on Learning Rep- resentations, 2020.
Weiler, M., Geiger, M., Welling, M., Boomsma, W., and Cohen, T. 3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data. In Advances in Neural Information Processing Systems, volume 31, 2018.
Shashua, A., Zass, R., and Hazan, T. Multi-way Clustering Using Super-Symmetrue Non-Negative Tensor Factoriza- tion. In European Conference on Computer Vision, pp. 595-608, 2005.
Wen, M., Horton, M. K., Munro, J. M., Huck, P., and Pers- son, K. A. An equivariant graph neural network for the elasticity tensors of all seven crystal systems. Digital Discovery, 3(5):669-)))))) 2024.
Stanley, R. P. Enumerative Combinatorics: Volume 1. Cam- bridge University Press, 1997.
Worrall, D. E., Garbin, S. J., Turmukhambetov, D., and Brostow, G. J. Harmonic Networks: Deep Translation and Rotation Equivariance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017. 2017.
Suk, J., de Haan, P., Lippe, P., Brune, C., and Wolterink, J. M. Mesh neural networks for -Equieaauiaa hemo- dynamics estimation on the artery wall. Computers in Biology and Medicine, 173, 2024.
13

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Wright, E. M. The number of partitions of large bi-partite number. Proceedings of the London Mathematical Soci- ety, 3(1):150-160, 1957.
Wright, E. M. Partitions of large bipartites. American Journal of Mathematics, 80(3):443-658 1958.
Wright, E. M. Partition of multipartite numbers into k parts. Journal für die reine und angewandte Mathematik, 1964 (216):101-112, 1964.
Yarotsky, D. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55(1): 407-474 474, 2022.
Zaheer, M. Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, J. J. Deep Sets. In Advances in Neural Information Processing Systems, vol- ume 30, 2017.
14

---

Permutation Equivariant Neural Networks for Symmetric Tensors
A. Supplementary Proofs and Definitions
Proof of Proposition 3.3. Suppose that f is a linear permutation equivariant function on a symmetric tensor T in (R"))* to (R"))), where is either 0 or 1.
Then, for all tuples of indices J = (kk)...;Jk) Jk) that index the standard basis ey E (R") we can partition these indices into disjoint sets such that I and J are in the same set if and only if there is permutation in Sy such that (I) = J.
Moreover, for each such set, f must map each element in the set to the same value, by the definition of f. Hence, for cach set, we can select the unique tuple in the set that is in ascending numerical order.
The union of these tuples across all of the sets gives 5 S'n]*, which indexes the standard basis of S (IB"), by construction. Moreover, since is either O or 1, we see that IR- (TR.) and R S (R"), giving the result.
Proof of Lemma 5.5. Let Bo = { be the set of (orbit bipartition diagrams and let Bp == {dd be the set of (ks, bi-baaattin diagrams.
To see why the set BD forms a basis of (n), first we form an ordered set of (k: bipparttisssons by ordering the bipartitions by the number of blocks that they have from smallest to largest, with any arbitrary ordering allowed for pair of bipartitions that have the same number of blocks. Call this set Si+k-
Then, because the square matrix that maps elements of Bn to linear combinations of the set Bo whose rows and columns are indexed (in order) by the ordered set S1+* is unitriangular by (21), is therefore invertible. Since Bo is the generating basis of S (n), we get that BD also forms basis of S (n), as required.
Proof of Theorem 5.7. Consider the two sets BD == } and Bo = {Xo} where each set is over all (k, 1) bipartiition that have at most n blocks. We see that, by the definition of D in (25), the transition matrix from Bp to Bo is unitriangular. As Bo forms basis of H (S*(),) ('(())) by Theorem 4.8, this implies that Bn is also basis of Homs, (1²",, St (R")). Since BD is basis, where each element in BD is the image under O kmn of diagram basis element in S P (n), and Ok,n is linear, the surjectivity O is immediate.
Proof of Proposition 5.9. Suppose that de is a diagram basis element in (n). Assume that we have placed the indices I on the top row of d. and the indices J on the bottom row of dg.
Consider the following cases.
Case 1: J) does not label the central nodes of d,, consistently.
Then, by (21) and the definition of the partial ordering = on biparabipttii JJ) does not label the central nodes of any of the xy consistently, since such zy are formed diagrammatically by fusing together some of the spiders of xa at the central nodes. Hence the (I,J)-entry entry of each Xo that is the image of xg under 1 is O, and so the (I, -enttry of Dz is also O, by (25).
Case 2: JJ, labels the central nodes of d consistently.
Then, by (21), we see that JI labels the central nodes of exactly one za in (21) consistently and distinctly. Indeed, this Ty is obtained by fusing together the central nodes of all of the spiders of the labelled diagram Vx whose labels are the same. Hence the (I, Jenntry for Xe that is the image of this Fe under 1%y kn is 1, and is 0 for the images of all of the other orbit basis diagrams in (21) that are not zg. Hence the (I, en-etryy of D is 1, by (25).
B. How to Generate All (ki, Bipparrtiii Diagrams Having at Most n. Blocks.
In Theorem 4.8 and Theorem 5.7, we constructed two different bases for Homs, ("""), using the set of all (k: bibiiartiss having at most n blocks. However, we have yet to outline a method for how to generate all of these bipartitions. To the best of our knowledge, there have only been a few studies on (k. bibbiaartssions restricted to a certain number of blocks (Wright, 1964; Landman et al., 1992; Kim & Hahn, 1997). In particular, no-one has given an explicit procedure for generating all (k:, 2) bipaaaatsss having at most n blocks: best, Kim & Hahn (1997) suggest that one
15

---

Permutation Equivariant Neural Networks for Symmetric Tensors
A General Procedure for Caleulating the S, -s-Equivarr Weight Matrix from 5* S*("") to S (R") using the Orbit Basis of (n).
Perform the following steps:
1. Calculate all of the (k, bibparatiiss и that have at most n blocks, and express each () -)-piaattiiion л as a (k, o)-ot bipartition diagram 2 in (
2. Then, if is the number of blocks in form all possible t-length tuples with elements in [n], not allowing for repetitions amongst the elements.
3. For each t-length tuple, label the central green nodes 4x from left to right with the elements of the tuple. Reorder the spiders in 2 such that they are in increasing order from left right. Then, for each spider, propagate the block label to the end of each wire. We obtain the matrix unit Er,, from this diagram by setting / to be the labels in the top row and J to be the labels in the bottom row.
4. Since each tuple corresponds to obtain the basis matrix X, that is associated with T.. Attach weight X R to each matrix X Finally, calculate Σ Xx to give the overall weight matrix.
matrix unit, add together all of the resulting matrix units from of the tuples
can obtain them from the set of all (k 1, bipaatittsss having at most blocks, but they do not explain how to do this explicitly.
In the green- and orange-coloured boxes below, we present a procedure for generating these bipartitions, notably without creating any duplicates. While the procedure described for (k:, I) bipartition diagrams, applies equally to (k, orbiit bipartition diagrams. Only the choice of diagram that is specified in Step 6 of the green-coloured box changes.
To explain why this procedure works, need to introduce some definitions.
Definition B.1. An integer partition \ of m is defined to be tuple (21,A2.... Ar) of positive integers A such that Σ A; = m and À 2 A2 2 2 X, > 0. We say that À consists of parts, and we define its length to be
We often extend the tuple of any integer partition of m that has some < n parts to have exactly a parts by appending n zeros X. Hence À (Ar, . of non-negative integers A; such that Σ A m and Å Z X2 2 ... An 0. Example B.2. We that 2, 2) is integer partition of 8 into exactly 3 parts. If 5, then write À as (4, 2, 2, 0, 0) instead.
Integer partitions must be written in non-decreasing order. The following definition relaxes this requirement. Definition B.3. A weak composition of into parts is r-length tuple (M1, .2...., (n. of non-negative integers μ4 m.
such that D
We say that a weak composition is in partition order if it also an integer partition.
Example B.4. (2, 0, 4, 2) a weak composition non-decreasing order, (4, 2, 2, 0, 0). gives weak composition
not in partition order. However, sorting these entries into that in partition order.
Definition B.5. We can represent integer partitions and weak compositions Young diagrams. For each tuple (01, 42,-22.00 a.). we create diagram consisting of n rows, where row i consists of boxes (by convention, the row number increases downwards).
Note that if a; 0 for some i, we leave row's worth of space for it and move onto the next value the tuple.
Example B.6. We represent the integer partition (4, 2, 0, 0) and the weak composition (2, 0, 4, 0, as Young diagrams:
(33)
16

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Definition B.7. Let À be integer partition of y having exactly parts, where we allow zero entry parts. Let ja be weak composition of m into n parts. We say that js fits inside À if X; Z #4 for all i [n].
We can see this diagrammatically by considering the Young diagrams for each of À and jı: if we can shade y in À without going outside the boundary of X, then j fits inside X, otherwise it does not.
Example B.8. À is the integer partition (6, 4, 4, 2, 2,0,0) 0) and y is the weak composition (2,3, 0, 2, 2, 0), then we see that fits inside X:
(34)
However, the weak composition does not fit inside X, as indicated by the red boxes in the diagram below, which fall outside the boundary of A:
(35)
The key insight behind why our procedure generates all (ks,)) (,,,))biipe -bipartition diagrams having at most blocks can be stated as follows: every integer partition of k + having exactly n parts (allowing for zero element parts) can be expressed as (ks + bij)-biiaartiiion, and every (k, bibbaaartiiion having some t E [n]] blocks must come from a integer partition of l having exactly parts. In particular, we can then represent each (I: 1, bipparttiiio (I: + I, 0) bipartition diagram (or (k: + orbbit bipartition diagram).
Indeed, if À A2........ An)) is an integer partition of k having exactly parts, with zero element parts allowed, then, by first removing all zero element parts to give the integer partition X = (A1, ....... A₂) of k + for some t E [m]] such that A is positive for all i [t). we obtain the (k + I, O)-biaartition À {[A1. 0], [A2, OJ. ......,, [Ne, 0}} having precisely blocks. (Remark: we remove all zero element parts in À first since the definition of a hipartition does not allow parts [r, yi] where
J; = y/.)) We can then represent the (k: + I, O.ppaaiiatiition À as a one-row (k + I, bipparttiin diagram
(36)
A1
X2
A
or with open green circles for (k orbit bipartition diagram. We retain the order of the integer partition in the diagram; that is, the number of legs is decreasing from left to right in each spider.
To see why every (k, biparrttinn having t blocks must come from integer partition of & + having exactly t parts, let = {[r,, 31 (2l. y2l.... [z,, 3t]} be (k, 1) biparttition having blocks. We form (k: + I, 0) bipartiitio by subtracting, for each part i, y4 from the second element of the bracket and then adding it to the first element of the bracket. This gives the (I: + 1, -ipbaarttin {[>1 + y1. 0), [x22 + y/2 O)...., [2 + Dr. 0]}. Without loss of generality, we can assume that the parts this (A + I, 0) bipaartiioo have been reordered in decreasing size order from left to right. Hence, this (k + I, -)-biartiiio precisely the integer partition (x1 8/. x2 + . 3e + 31) of + into exactly parts.
Hence, to generate all (k, -ipparttiiss having at most blocks, first need generate all integer partitions of k k++ having exactly parts, with zero element parts allowed, and express them as (A: + biipartittss (or bipartition diagrams), We then need to work out how to create all possible (k:, bipiaratisso (or diagrams) from each such + 7, 1, (diagram), which is the reverse procedure of the process described in the previous paragraph.
We see that, for a given (k + I, biparttiin diagram having t blocks, where E [n]] to obtain a (k: I) Dipaattrtiiion diagram, we need to turn I legs up across all of the spiders. This the same as creating a weak composition μ of into exactly
17

---

Permutation Equivariant Neural Networks for Symmetric Tensors
parts, where set the last n parts in j O. Hence, calculating all weak compositions of I into exactly n parts will be enough to determine all of the (R:, 1) bipparttin diagrams from a given (k 1, 1,00)-biprrttti diagram having most blocks.
In effect, this produces a matrix where the integer partitions À of i + I into exactly n parts, with zero element parts allowed, index the rows, and the weak compositions je of I into exactly n parts index the columns. We then need to see, for each (A, (1) pair, whether the elements of μ are a well-fitting combination for turning up the legs of A. We call such a pair valid. A simple way to determine if each (X. (1) pair is valid is to see whether i fits inside X. If it does, then the pair is valid, otherwise is not. Then, for each valid pair (A, pt), we can create (k, bibbaartinoo diagram by turning up μ legs in each spider i of X, viewed
(K: 1, 0) bipartition diagram.
Hence, if 1 = (J,, M2,, Me, 0, ... 0) is a weak composition of l into exactly n parts such that (A, (4) is a valid pair, where À is the (A + 1, biipartttinoo diagram given in (36), then, for each spider i in (36), we can turn up p legs to obtain the (kt bipaarttiino diagram
A1
22
(37)
\1 f1
X2 μ2
A M
At this stage, this would be enough to generate all (k:, 1) bipartiiiionn diagrams having at most n blocks. However, this procedure in its current state would create potentially multiple duplicate (k: bbiiarrtiiio diagrams from any (k + 1, bipartition diagram where spiders have the same number of legs; that is, this procedure will overgenerate the (k, bbiiaariiinn diagrams having at most n blocks that we need. Indeed, if block and block j have the same number of legs, that is, A = A/ then, if μ is the weak composition with entry /4; in position i and entry J4y in position j such that (A, 2²) is valid, and n is the weak composition with entry μúj in position and entry μ4 in position j such that (A, n²²) is valid, with the entries of p² and μ² being equal at all other indices in the tuples, we see that using n² to turn up the legs of X gives the same (kc, ()- biparttiin diagram as using μ² to turn up the legs of X, even though the spiders might be in different order.
Hence, we can improve this procedure so that only the exact number of (k, I)bbiaartiiion diagrams having at most n blocks are generated, in the following way: after the matrix that is indexed by (A, 14) pairings is created, perform what we have termed the (X, μ1) Duplication Test to eliminate all pairings that fail the test first before checking the rest for validity.
The pA. Duplication Test does the following: to avoid duplicating (k, 1) bipartiiio diagrams from given (k + 0) bipartition diagram X, for spiders whose legs have the same size, we only need turn up the legs on these spiders in decreasing order, since any other order will produce duplicate diagrams. That is, in the subtuple of a weak composition formed by taking those elements of the weak composition at the same indices as the blocks of the spiders, we only need to consider the subtuple that is in partition order. Hence we can set any (h, 1) pairing that fails this Duplication Test to be invalid.
We can also speed up the process of determining whether a (X, 14) pair is valid or not as follows. Suppose that À has non-zero entries only in its first parts. If μ contains non-zero entry in any index from t + 1 to n, then this pair is automatically invalid. Hence, for a given À having non-zero entries only in its first t parts, we only need to consider the validity of (A, (1) pairings where y is of the form μ (1), (2,,,,,..... ,.,,,..,,, /4, O,..., 0), with the hr being non-negative integers. We perform this before the (A, μ)) Duplication Test.
There is one further optimisation that we can make to the entire procedure. As it stands, we chose to turn / legs up in a (k: + Oiiiaaiatnnioo diagram and found all possible ways of doing this by considering weak combinations of into exactly n parts. In fact, we could choose instead to not turn up le legs in total, which would be the same as considering all weak combinations of k into exactly n parts. As the number of weak combinations of number m into n parts increases as m increases, by considering the sizes of l and I, we can reduce the number of weak combinations that need to consider for each (): + I, bipbaaatti diagram by choosing the smaller value between i and l.
Example B.9. Suppose that we would like to find all (3, 2) biparttiii diagrams having at most 3 blocks. We follow the procedure that is given in the green- and orange-coloure boxes below.
18

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Procedure: How to Generate All - -iiparrrtnnnnonn Diagrams Having at Most Blocks.
1. Calculate all integer partitions À of k: + into most parts, and express each integer partition n-length tuple whose elements are in decreasing order, allowing zero element parts.
2. Choose the smaller value between k and l. Let min(k, (,4) !). Calculate all weak compositions μ of m into exactly n parts.
3. Create a matrix where the integer partitions À index the rows and the weak compositions μ index the columns.
4. Put 0 in any (A, ententry where has a non-zero entry in any index that is greater than the number of parts in
X.
5. Now consider only those À that have parts that are equal. For each such X, put each remaining (A, (1) enttyy that fails the (x, Duplication Test.
6. For each remaining (A, p) determine whether j fits inside X, viewing each as a Young diagram. If does, put in that entry, and call the pair (A, 11) valid. Otherwise, put 0 in that entry.
7. For each valid (A, pd) pair, remove all zero element parts of À and express it as (A + 1, O))biiaatiiiinn diagram. Hence, each block in A is spider that corresponds to the pair [Λ,, OJ, viewing À as a (k + I, O)-iittrtiiion. Then:
m 1, then, for each block i X, turn (4s legs up to the top row. Otherwise (m k), for each block i in X, turn X; μ4; legs up to the top row.
Note that this procedure also works for generating (ki, 1)rbt bipartition diagrams; simply express each in Step 6 as a (k, ooriit bipartition diagram instead.
Procedure: The (A, μ4) Duplication Test.
1. Suppose that À has non-zero parts, where i [n]. Partition into blocks, where two elements i, are the same block if and only if X; = Aj-
2. For each block in the partition whose size is greater than 1, create a subtuple from μ by only considering those elements in a that are indexed by the elements of the block.
3. Consider each subtuple in turn, If subtuple is not in partition order, then we say that (A, u)) has failed the duplication test.
4. Otherwise, we say that (X, p)) has passed the duplication test.
Step 1: We calculate all integer partitions À of - 2 = into at most n = 3 parts, and express each as 3-length tuple whose elements are in decreasing order, allowing zero element parts.
They are: (5, 0, 0), (4, 1), (3, 0), (3, 1), and 22 1).
k, we calculate all weak compositions y m min 2) into exactly parts. They are: (2, 0, 0), (0, 0), (0, 2). (1, (1,0, 1), and (0, 1)
Step As (
Steps 3, and 5: We create a matrix where the integer partitions À index the rows and the weak compositions μ index the columns. We put any (A, jn)entry where y has non-zero entry in any index that greater than the number of parts in A. We then look to find any remaining (A, entertisss that fail the Duplication Test. For this test, we only need to consider those À that have repeating parts: they are (3, 1) and (2, 2, 1).
19

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Consider À (3, 1, 1) and μ = (1, O, 1). We form the partition {1 2.3) of [3] from A, and form the subtuple (0, 1) of from the only block in the partition of size greater than 1. As this subtuple not in partition order, see that this pair (A, ()) has failed the Duplication Test.
Likewise, consider À = 22 and μ = (0, 1).. We form the partition {1,2 3) of [3] from A, and form the subtuple (0, 1) of from the only block in the partition of size greater than 1. As this subtuple not in partition order, we see that this pair (A, μ) has failed the Duplication Test.
For these two pairs, we put O in the (A, p)-entry of the matrix. All other pairs pass the Duplication Test.
Step 6: For each remaining (7, pl)-entr,, we determine whether fits inside X, viewing each Young diagram.
At the end of this step, we see that the matrix contains the following entries:
[2,0,0]
(0.2.0)
(0,0.2)
(1,,0)
(1,0.1)
(0.1,1)
(5,0,0)
1
0
0
0
0
(4,1,0)
1
1
0
(322,0)
1
1
1
0
(38)
(3,1,1)
1
0
0
1
1
(2,2,1)
1
0
1
0
At this point, see that (3, 2)
13.
Step 7: We form the (3, bipartiiti diagram that is associated with each valid (A, 11) pair. They are:
(2,0,0)
(0,2,0)
(0,0,2)
(1,2,0)
(1,0,1)
[0,1.])
X
(5,0,0)
0
0
0
(4.1.0)
0
O
0
0
(39)
(3,2.0)
(3,1,)
0
V
(2,2.1)
To finish this section, we note that there exists more generic partition function, p(k, 1), which counts the number of possible
20

---

Permutation Equivariant Neural Networks for Symmetric Tensors
(ki bibbaratisss without any restriction the number of blocks. In particular, the sequence p(k; k) (i.e k 1) is the OEIS sequence A002774, Bipartitions without any restriction the number of blocks have been studied in many prior works (MacMahon, 1893; 1896; Mathews, 1896; MacMahon, 1899; 1918; Auluck, 1953; Nanda, 1957; Wright, 1957; 1958; Carlitz, 1963; Carlitz & Roselle, 1966; Andrews, 1977; 1998). It is fair to say that most of these authors, with the exception of MacMahon and Mathews, primarily focused on determining either generating functions or asymptotic formulas for (k.,().
We see from our analysis that p(k, 1) is equal to (k, 1), the number of (k bipartiiios having at most & | parts. We give the value of p(k, !) up to k ( in Table Note that p(k, is symmetric in and and that p(k, 0) p(0, k) is precisely the number of integer partitions of & (into most parts).
Table 3. The number of (k, bipartiiio::: p(k,
0
2
4
5
k
0
1
2
3
5
7
1
1
2
4
7
12
19
2
2
9
16
29
47
(40)
3
3
16
31
57
97
4
5
12
29
57
109
189
5
7
19
47
97
189
339
C. Supplementary Weight Matrix Calculations
Example C.1 (Calculations for Example 4.11). Recall that we would like to find the Sg-equivariant weight matrix from (RR) 8 (R3) R using the orbit basis of SP2 (3).
We need to consider the (2, orbit bipartition diagrams having at most n 3 blocks. They are
!
O
(41)
For example, for the second diagram which has two blocks, we see that, since 3, there are only six possible 2-length tuples having distinct elements in [3]:
(1, (1,3); (2,3) (3,
(42)
Assigning these tuples the central green nodes of the diagram and reordering the spiders where appropriate gives
O
1
O
1O
R.
3 2 2
(43)
By propagating the central values to the ends of the wires in each diagram, then reading the tuple off the top row and the tuple off the bottom row to form the matrix unit E1,J for each diagram, and then adding these matrix units together gives the following orbit basis matrix X= corresponding the second diagram (41):
21

---

Permutation Equivariant Neural Networks for Symmetric Tensors
2,2
3,3
0
0
0
1
1
2
1
0
0
0
0
1
(44)
3
1
0
0
1
0
Hence, in full, from left to right, the four diagrams in (41) correspond to the following basis matrices Xx of size x 6:
1.3
2,3
1.2
1,3
2.3
3,3
1
0
0
0
0
0
0
1
0
2
0
0
0
2
0
0
0
(45)
0
0
3
0
1,1
1,2
1,3
2,2
2,3
3,3
1,1
1,2
1,3
2,2
2,3
3,3
0
0
0
0
1
0
(46)
0
1
1
0
Hence, the Sg-equivariant weight matrix from S
(RR)
to
S
(R$)
using the orbit basis of (3) is of the form
1,1
122
1,3
2,2
2,3
3,3
X1
23
22
A2
A2
A1
X
A2
(47)
A2
A
A
22
A
A1
for weights Å1, A2, A3, A4 E R. Example C.2 (Calculations for Example 5.) Recall that would like to find the Sæ-equivariant weight matrix from (RR)) to St (R3) R using the diagram basis of SP (3) instead.
We need to consider the (2, bipparttiino diagrams having at most n 3 blocks. They are
(48)
For example, for the third diagram which has two blocks, we see that, since n 3, there are now nine possible 2-1ength tuples whose elements are in [3], since the elements in each tuple no longer need to be distinct:
(L. 1): (1, 2); (1, 3); (2, 1): (2, 2); (2, 3); (3, 1); (3, 2); (3,3)
(49)
Assigning these tuples to the central green nodes of the diagram, reordering the spiders where appropriate, and fusing together any spiders whose central green nodes are labelled with the same value gives
3
3
(50)
and
3
2
(51)
By propagating the central values to the ends of the wires in each diagram, then reading the tuple off the top row and the tuple off the bottom row to form the matrix unit E1,J for each diagram, and then adding these matrix units together gives the following diagram basis matrix D, corresponding to the third diagram in (48):
22

---

Permutation Equivariant Neural Networks for Symmetric Tensors
1,2
1,3
2:2
2,3
3.3
1
1
1
0
0
0
2
0
1
0
1
1
0
(52)
3
0
0
1
0
1
Hence, full, from left to right, the four diagrams in (41) correspond to the following basis matrices D, of size
1,3
2,3
1,2
2,3
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
1
(53)
3
0
0
0
3
0
0
1
0
1,3
2,3
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
1
1
1
(54)
0
1
1
3
1
1
Hence, the Sy-qquivariant weight matrix from (RR) to S (R*) using the diagram basis of (3) is of the form
1,1
11,,,3,4
A3,4
22,4
A
X2,4
22,4
A
A4
21,2,3,4
22,4
(55)
A
A3,1
22,1
X
21,2,3,4
for weights λ1 λ3, A4 R. where AA EiEad Ai.
Example C.3 (Deep Sets S, SquEaviaar Weight Matrix from R² I.). To find the Deep Sets S, Su-equivrriant weight matrix from from R." to IR", we need to find the diagram basis of Homs, (S' ( (RR)) from the diagram basis of (P), since 5 (R") IR"
We need consider all (1, b-bparrtitiion diagrams having at most n blocks. Assuming that n > 1, they are
(56)
For the first diagram, the only valid 1-length tuples the elements of [n]. Hence, the matrix that corresponds to this (1, bibbarattnn diagram is the n x n identity matrix. For the second diagram, all possible 2-length tuples with elements from [n] are valid, since the elements in each tuple do not need to be distinct. Hence, the matrix that corresponds to this (1, b)-baatrttioon diagram the n x n all ones matrix.
Hence, the (intr of the -quequiivri weight matrix from En E is λι Xa if j. and is Xe i * j. for weights X1, E R. This is precisely the Deep Sets characterisation given in Zaheer et al. (2017).
D. Map Label Implementation and Examples
At the end of the paper, we present complete implementations of the five subprocedures (I to V) that appear in the procedure for generating the transformation map labels that correspond to a (k, bippartiino diagram for a given value of n. We provide illustrative examples of each of the subprocedures below.
23

---

Permutation Equivariant Neural Networks for Symmetric Tensors
D.I. Subprocedure
Example D.I. Consider the (3, 2)-barartinionn diagram dx given by
(57)
We follow Subprocedure obtain all possible grouped outputs for d, and, for each one, its associated set partially labelled diagrams. (In this case, the resulting diagrams will also be fully labelled, that is, there would be need apply Subprocedure II to the outcome).
Step 1: We sort the spiders in decreasing order of output wires, breaking ties by sorting them in decreasing order of input wires. This gives
(58)
Step 2:
We partition the spiders into groupings where spiders are in the same grouping if and only if they have the same number of output wires. Labelling each spider with Oz, where x denotes the number of output wires that the spider has, we see that, for the diagram given (58), the partition x is {01, which consists of only one grouping, TØ {01, O1}.
Step 3: For иa, form new partition of the spiders such that spiders are in the same grouping in the partition NB, if and only if they have the same number of input wires. Labelling each spider in Tn with I,, where denotes the number of input wires that the spider has, we see that T. is {12 11}.
Step 4:
We calculate all integer partitions of t, where is the number of spiders in d that have output wires. Here 2, since both spiders (58) have output wires. The integer partitions of are + and only.
Step Consider each integer partition in turn.
a): For À = ++++ 1, we form the multiset {i,}} and compute all partitions of this multiset that correspond to the original partition structure of modulo isomorphism. There is only one non-isomorphic partition of the multiset, namely L. {i.j} itself, which has only one grouping, LB = {i.j}.
We now compute all partitions the grouping Lg that correspond to the partition structure of TB.I- This gives {a j) and {j i), which we convert into ordered tuples, that is, Tt,B = ((i,)),(i,))
Since L had only one grouping, we see that T1+1. {(i, j), (j, i)3. Hence the set D141,1 consists only of the following two diagrams
and
(59)
where, in each diagram, we unable to merge any spiders. Hence RI+1,E = Ø, and so P1+1, D141,L.
Moreover, since there was only one non-isomorphic partition of the multiset ji we see that Pi+1 = P1+1,--
b): For 2, we form the multiset {i, and compute all partitions this multiset that correspond structure of π, modulo isomorphism. There only one non-isomorphic partition of the multiset, namely (i. (i itself, which has only one grouping, LB = ii,
original partition
We now compute all partitions of the grouping Ly that correspond to the partition structure of NT This gives { i) only, which we convert into an ordered tuple, that is, Tı,B ((i,)))
Since L had only one grouping, we see that T2, = {ii, 0).. Hence the set D2.2 consists only of the following diagram
(60)
24

---

Permutation Equivariant Neural Networks for Symmetric Tensors
We merge spiders that labelled with the same label form:
(61)
clear that, despite the new grouping, no new partially labelled diagrams can appear from (61), and we get that 2 Ø. Hence P2.L L2
Moreover, since there was only one non non-isomorphic partition of the multiset {i, i),, we see that P2 P2.L.
Step 6: We now take the set union Px over all integer partitions of = 2, and call the new set P. Hence P has three elements, namely the two diagrams given in (59) and the one diagram given in (61). By reordering the labelled spiders in lexicographical order, and partitioning into subsets such that diagrams are in the same subset and only if their tuples of output labels are the same, obtain the following two sets output of Subprocedure for the (3, 2)-biarrtiiion diagram d
(i,j)
and
(i,
(62)
Example D.2. Consider instead the (1, bipartition diagram d, given by
(63)
We follow Subprocedure obtain all possible grouped outputs for d, and, for each one, its associated set of partially labelled diagrams. (Once again, the resulting diagrams will also be fully labelled, that is, there would be need apply Subprocedure II to the outcome).
Step 1: We sort the spiders in decreasing order of output wires, breaking ties by sorting them in decreasing order of input wires. We see that the spiders (63) are already sorted.
We partition the spiders into groupings where spiders are in the same grouping if and only if they have the same number of output wires. Labelling each spider with Oz, where x denotes the number of output wires that the spider has, we that, for the diagram given in (63), the partition is {O2 O O1), which consists of two groupings, TB, (O2) and TB. (O1, O1).
Step 2:
Step 3: For each grouping BB we form new partition of the spiders such that spiders are in the same grouping in the new partition TB if and only if they have the same number of input wires. Labelling each spider in with 1,, where æ denotes the number of input wires that the spider has, we see that T = {[1} and TB.. = (To, To}.
Step 4:
We calculate all integer partitions of f, where the number of spiders in d that have output wires. Here since all three spiders in (63) have output wires. The integer partitions of 3 1 + + + 1 and 3.
Step 5: Consider each integer partition À in turn.
a): For À = 11 + 1 1 1, we form the multiset {i.j, }- and compute all partitions of this multiset that correspond to the original partition structure of π,, modulo isomorphism. Despite there being three partitions, namely (i j, AJ. {i i, k), and {k j.j. all three are equivalent under relabelling of the labels. Hence, there is only one non-isomorphic partition of the multiset, namely L, = (i j, k), which has two groupings: LB, = {i} and LB, {j. k).
For each grouping LR, now compute all partitions of the grouping Ln, that correspond the partition structure of TB.II For LB,, this gives {i} only, and for LB,, this gives {j, k} only. Converting these into ordered tuples, we get that TI,B, = {(i) and T2,B, {Gj. k)}. Hence T1+1+1,4 is [1,, k)). Consequently, the set D1+1+1,4 consists only of the diagram
(64)
25

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Since we are unable merge any spiders, we have that 11+1+1.4 Ø, and P1+1+1,1 D1-1+1L Moreover, since there was only one non-isomorphic partition of the multiset {i,j,k), we see that P1+1+1 P1+1+1L-
b): For À= 2 + 1, we form the multiset {i,i,}} and compute all partitions of this multiset that correspond to the original partition structure of т, modulo isomorphism. There are two non-isomorphic partitions of the multiset, namely L' = {i i and L = {j i, L has two groupings, L = {i] and Lip = {i.J]. and L has two groupings, 23 - (5} and B.3 = (i.
i): Consider L For each grouping LB, we now compute all partitions of the grouping L), that correspond to the partition structure of B.,I For n,, this gives {i) only, and for L this gives {i,s} only. Converting these into ordered tuples, we get that T2 ,B. {(}) and TEt.B, = [i) Hence T2+1,2* is {(i, i, Consequently, the set D2+1, consists only of the diagram
(65)
Merging spiders that are labelled with the same label gives
(66)
is clear that, despite the new grouping, no new partially labelled diagrams can appear from (66), since there is only one spider with three output wires and one spider with one output wire. Hence, we get that R2+1, Ø, and so P2+1,1' = D2+1,11.
ii): Now consider L For each grouping L. we now compute all partitions of the grouping L3, that correspond to the partition structure of TB..I. For L'g,. this gives {i} only, and for L2g, this gives i) only. Converting these into ordered tuples, we get that T2. = } and TB, = ().. Hence T2+1, is {0, 1)).. Consequently, the set D2+1,1² consists only of the diagram
(67)
Merging spiders that are labelled with the same label gives
Y
1
(68)
However, this time, with the new grouping, we will form new partially labelled diagrams from (68). Let the newly merged bipartition diagram in (68) be dg. We retain but ignore its labels for now. We see that dg is already sorted in decreasing order on output wires, with ties broken by input wires, and so we partition the spiders into groupings based on their output wires. Hence f = (O2, O2). Moreover, for the single individual grouping in 0B. we form a new partition of 0g such that spiders in the same grouping if and only if they have the same number of input wires. Hence we have that On. r {/i [o}- Removing the labels from 6, we obtain a partition of labels İ. into individual groupings i.g. Hence L. = {j. f). We now compute all partitions of LB that correspond the partition structure of 0 This gives {j | i} and {i [), which we convert into ordered tpples Hence Ti,8 = {(i.)) i), (i.j)). and since there is only one grouping in L, we have that T2+1, = { i), ()) Creating copy of (68) without its labels for each element i of T TT+1,L= we label it with This gives back (68) and new diagram
(69)
both of which we add to 124
Taking the set union of D2 and R241, gives P241,12, which this case equal to R241,12.
26

---

Permutation Equivariant Neural Networks for Symmetric Tensors
As there were non-isomorphic partitions of the multiset {i,
that P2+1 P2+1,1' U P2+1,12.
O) For À 3, we form the multiset {i, i, and compute all partitions of this multiset that correspond to the original partition structure of modulo isomorphism. Hence, there is only one non-isomorphic partition of the multiset, namely L= {i i, i. which has two groupings: LB, = {i} and LB, = {i.1].
For each grouping LB, , we now compute all partitions of the grouping LB, that correspond to the partition structure of R., For LB. this gives {i) only, and for LB this gives { only. Converting these into ordered tuples, we get that TL.B- {{)} and TL, {(i, i)}. Hence T3 L {(i, i, i)}. Consequently, the set D3, consists only of the diagram
(70)
Merging spiders that are labelled with the same label gives
(71)
It is clear that, despite the new grouping, partially labelled diagrams appear from (71), since there is only one spider with four output wires. Hence, we get that R3,1- = 2, and so P3,L D3,L-
Moreover, since there was only one non-isomorphic partition of the multiset {i, i]. we see that P3 = P3,
Step 6: We now take the set union of Px over all integer partitions of 3, and call the new set P. Hence has five elements, namely the diagrams given (64), (66), (68), (69), and (71). By reordering the labelled spiders in lexicographical the subset if and only if their tuples of output labels order, and partitioning P into subsets such that diagrams the same, obtain the following four sets output of Subprocedure I for the (1, 4) bipartiiiion diagram d,:
(i,
(72)
(1,4,4,5)
(73)
(1,4,5.)
(74)
(i,i,
(75)
D.2. Subprocedure II
Example D.3. Consider the partially labelled diagram for the grouped output (i, i,) of the (4, biiarriiitnnno diagram d,
(76)
We follow Subprocedure obtain all possible fully labelled diagrams for this particular partially labelled diagram.
27

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Step I: We see that the partially labelled diagram has labelled spiders, and also 3 spiders with label. Hence
Lx. the set of fixed labels, is {-
Step 2: We see that the unlabelled spiders in (76) are already sorted in decreasing order of input wires.
Step 3: We partition the sorted unlabelled spiders into groupings where spiders are in the same grouping if and only they have the same number input wires. We see that π = {12 11, 41), which has two individual groupings TB, = {12) and
RB I1)
Step We consider all possible ways of labelling the unlabelled spiders, where &s of them are fixed and the remaining of them are free, for & = 0, 2,
Consider each value of & in turn:
= 0: fixed labels and 3 free labels.
First, we create the multiset {P, F, F), where denotes a free symbol. We compute all partitions of this multiset that correspond the original partition structure of æ. In this case, there is only one such partition, and 1xx.r {{F F, F,F)).
Next, calculate all possible size 0 multisets choosing labels from Lx allowing repeats, and all possible size multisets choosing free labels, introducing them as needed, and also allowing repeats. This gives (m), {k. k. 1] and {k, k, kj. We consider each of these in turn:
we compute all partitions of {k: m3 that correspond the original partition structure of the only partition in 1I,.F. namely {F F, F), modulo isomorphism. Despite there being three partitions, namely { m, {? k. m), and {m ks (]. all three are equivalent under relabelling of the free labels. Hence there is only non-isomorphic partition of the multiset, namely (I: I, m} only. Creating copy of (76), we label the spiders in order from left to right to create the fully labelled diagram
(77)
we compute all partitions of Ai k that correspond to the original partition structure of the only partition in IIx,F, namely {F F, F), modulo isomorphism. This gives {k k, {} and {1 k, k}. As before, we label the spiders in order from left to right create the following two fully labelled diagrams
k
and
k
(78)
we compute all partitions of (k, kt, k-} that correspond to the original partition structure of the only partition IIx,F, namely {F) F, F). modulo isomorphism. This gives {Te k, k} only. As before, we label the spiders in order from left to right create the following fully labelled diagrams
(79)
ii) A: = fixed label and free labels.
First, we create the multiset (X, F). where denotes fixed symbol and F denotes free symbol. We compute all partitions of this multiset that correspond the original partition structure of There two such partitions, and so IIx, [[ F, PJ, {F F))
Next, we calculate all possible size 1 multisets choosing labels from Lx. allowing repeats, and all possible size multisets choosing free labels, introducing them as needed, and also allowing repeats. Taking their Cartesian product gives all possible ways of choosing fixed label and 1 free label. This gives (i, k., 1}. {i, k. k), {j. k. 1}, and {j. k. k}. We consider each of these in turn:
28

---

Permutation Equivariant Neural Networks for Symmetric Tensors
for each partition XX.F F, we compute all partitions of (1, k; I) that correspond to the original partition structure of Xx, modulo isomorphism. For (X P, F), this gives {i k, 2) only. For {F X, F), this initially gives {k i,1] and {1 }.. but these two are equivalent under relabelling of the free labels, hence there is only { i,4). For each partition, create copy of (76) and label the spiders in order from left to right create the two fully labelled diagrams
k
and
E
(80)
A similar process occurs for (j, k, giving
and VE
h
1
(81)
for each partition Xx, E 1I,,F, F, we compute all partitions of {i, kr k. that correspond to the original partition structure of Tx modulo isomorphism. For {X F. F), this gives {i k, k} only. For {F F), this gives {k i, k} only.
As before, create copy of (76) and label the spiders in order from left to right to create the two fully labelled diagrams
and
(82)
A similar process occurs for (j. k, k), giving
V
k
k
and
K
(83)
iii) i 2: fixed labels and free label.
First, create the multiset (X, F), where X denotes fixed symbol and F denotes free symbol. We compute all partitions of this multiset that correspond to the original partition structure of There are two such partitions, and so IxxFF = f[X F). {F X}
Next, we calculate all possible size 2 multisets choosing labels from Lx allowing repeats, and all possible size multisets choosing free labels, introducing them as needed, and also allowing repeats. Taking their Cartesian product gives all possible ways of choosing 2 fixed labels and free label. This gives {i.j. k), {i, k}. and {j. k.. We consider each of these in turn:
for each partition X E II,,F, we compute all partitions of {i.j.k) that correspond to the original partition structure of F, modulo isomorphism. For {X] X, F), this gives {i and {j k) (which not isomorphic). For
{F XX, this gives (Ix i,j} only.
As usual, create copy of (76) and label the spiders in order from left to right to create the three fully labelled diagrams
and
(84)
and
(85)
29

---

Permutation Equivariant Neural Networks for Symmetric Tensors
for each partition XX.F F, we compute all partitions of { k) that correspond to the original partition structure of X,,F, modulo isomorphism. For {X X, F), this gives (i i, k) only. For {F) X, X), this gives {k i,1) only.
As usual, create copy of (76) and label the spiders in order from left right to create the fully labelled diagrams
and
(86)
similar process to { k} occurs for { k), hence we obtain
V
V K
and
(87)
iv) = 3 fixed labels and free labels.
Despite there only being two fixed labels in Lx. still label the unlabelled spiders in (76) with them. First, create the multiset (X, X, }, where X denotes fixed symbol. We compute all partitions of this multiset that correspond to the original partition structure of π. There is only one such partition, and so 1lx.r {{X X, X...
Next, we calculate all possible size 3 multisets choosing labels from Lx allowing repeats, and all possible size multisets choosing free labels, introducing them as needed, and also allowing repeats. Taking their Cartesian product gives all possible ways of choosing 3 fixed labels and free labels. This gives {i,i,), (i, {J.j. and {J.j.}}. We consider each of these in turn:
compute all partitions of {i, that correspond to the original partition structure of the only partition in IIx, F. namely {X X, J. modulo isomorphism. This gives {i i,j} and {j ú i}. As before, label the spiders in order from left to right create the following two fully labelled diagrams
and
(88)
A similar process occurs for (j.j, i), giving
and
(89)
we compute all partitions of i) that correspond to the original partition structure of the only partition in II,F F.
namely {X X, modulo isomorphism. This gives {i i, i only. A similar process for {j.j.}} gives {j j.j} only. Hence we obtain the following two fully labelled diagrams
and
(90)
Step 5: To finish, merge all of the spiders in each of the diagrams, remove duplicates, and form set result. This is the set of fully labelled diagrams corresponding to the partially labelled diagram (76) for the grouped output (i, (, of the (4, 3) bipparttiin diagram d,..
To ensure brevity, we will not reproduce the final set of merged spiders here. However, we can see that only three duplicates are removed: the right hand diagram (86) removed since the same as the left hand diagram (82); the right hand diagram in (87) removed since is the same the left hand diagram in (83); and the right hand diagram in (89) removed since it is the same as the right hand diagram in (88).
30

---

Permutation Equivariant Neural Networks for Symmetric Tensors
D.3. Subprocedures III, IV, and V
Example D.4. In Example D.I, considered the (3, 2)-biarrtniion diagram (57) and, by applying Subprocedure I, obtained two sets of partially labelled diagrams that were given in (62), one for each possible grouped output for (57). In fact, noted that the diagrams in each set actually fully labelled, hence could skip applying Subprocedure II to each of them and proceed to applying Subprocedure III to each fully labelled diagram.
Following Subprocedure III, we see that the grouped map labels that correspond to the diagrams in the set (i.j) of (62) are
i. _ i, i,
(91)
and
j _ 3.9.i
(92)
where # and the grouped map label that corresponds to the diagram in the set (i, of (62) is
2, i,
(93)
We now apply Subprocedure IV to each of these grouped map labels - that is, unroll the right hand side of each grouped map label to obtain its left grouped map label:
i,i,j + i j i.j
(94)
i,j
3,J, + i, i,9.
(95)
i, i,
(96)
For each grouped output, we can add together the right hand side of every left grouped map label where this grouped output appears the left hand side obtain single left grouped map label for each grouped output:
i.j
j. i, j.J. 1 + j. +.j.j
(97)
and
i i
(98)
Hence, by applying Subprocedure V and converting the resulting map labels transformation map labels, we see that, for input symmetric tensor T (Ra)83, where 2 2, the output symmetric tensor D, (T) E (Rn)&2, where d, given in (57), is given by
(T(T) Tiis Tigs + T3s. + Tjg. + Tjááj Tiga
(99)
for all # E [n], and
Dz(T) + Tes.
(100)
for all i E [n].
As trivial case, note that if n 1, then we would not consider the fully labelled diagrams in the set (i,j) of (62), and so the only transformation map label would be
DT(T),.1 Ti.
(101)
Example D.5. We can compare Example D.4 directly with the (3, 4) bippaatrnnn diagram d,
(102)
Subprocedure will give two sets:
(i,1,i.)
and (1,1,
(103)
31

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Once again we skip over Subprocedure II since each diagram in each set fully labelled. Applying Subprocedure III and then Subprocedure IV, obtain the following left grouped map labels
1g 2,J.J + j.2,j
i,i,j.
(104)
where / j. and
1, i,i,
(105)
We now apply Subprocedure obtain set map labels for each left grouped map label: (104) becomes
1, j,ú,i
(106)
(107)
i + j.J,4 1, 1, j.i,
(108)
and (105) becomes
1, 1, < i,
(109)
Hence, by converting the resulting map labels to transformation map labels, we see that, for an input symmetric tensor E (IR") (Rn")s,, where n 2 2, the output symmetric tensor DT( E (RR)) where dx is given in (102), is given by
DT(T)ass - Tijs + T + Tjj.a + Ti,s + Tija + Tjas
(110)
D2 DT(Tisss Tajs T3s. + T.J. Tis + Tuza +Taa
(111)
DT(T)sss + Tiss Tyas + T3sa This + Taa T3sa
(112)
for all j E [n], and
(T(() Tiga
(113)
for all i E [n].
Once again, as trivial case, note that if n = 1, then we would not consider the fully labelled diagrams in the set (1,
of (103), and so the only transformation map label would be
DT(T)a Ti.1.1
(114)
Example D.6. We obtain the left grouped map labels for the (3, 1) bipartiiion diagram d,
(115)
as follows.
We apply Subprocedure to (115) to obtain
(116)
as the only possible grouped output for (115) with its associated set of partially labelled diagrams.
We then apply Subprocedure II to the only partially labelled diagram in (i), giving five fully labelled diagrams for this grouped output:
(117)
32

---

Permutation Equivariant Neural Networks for Symmetric Tensors
and
(118)
Following Subprocedure III, we see that the grouped map labels that correspond to these fully labelled diagrams are
i
2 Σ
J.J.
_
E...
i 2
Σ i
(119)
j.
jyk
1#1
jf1
and
_
Σ i
i i i,
(120)
We now apply Subprocedure IV to each of these grouped map labels unrolling the right hand side of each grouped map label, we obtain its left grouped map label:
i
b... k j. K.J 2.1
10
E...
10 Σ 1U,55
(121)
S41
041
kgg
and
1g Σ H...J+
L/ i,
(122)
Given that there is only grouped output, add together the right hand side of every left grouped map label above to obtain single left grouped map label for this grouped output:
Σ Db.jk k + Ei.j.t
+ Σ [i, + iij
+144 + Eb...+ + j. +i,i, (123)
S71
Tidying the right hand side of (123) gives
Ig
+. + +,J.J - Σ j.j.j
(124)
j=1
Hence, by applying Subprocedure V and converting the resulting map label to transformation map label, we see that, for an input symmetric tensor 7 E (R,) where n 2 3, the output (symmetric) tensor DT E TR.", where d, is given in (115), is given by
D*(T), < Σ
(Tisk Tikks Tkisl
Σ> j=1
Tiss
(125)
J.k=1
for all i E [n].
Finally, in a similar way to the preceding examples, it is possible to obtain the transformation map label the trivial cases and 2.
33

---

Permutation Equivariant Neural Networks for Symmetric Tensors
D.4. Map Label Calculations for Example 7.3.
Example D.7 (Calculations for Example 7.3). We calculate the transformation map labels for each of the four (2, 1)- bipartition diagrams that were given in (26) for 3. We reproduce them below, for ease:
(126)
In the following, we refer to these diagrams as dzi. dra, drg, dr respectively. We follow the procedure that was given in the main paper to obtain the transformation map labels.
For da, it clear that the only grouped output, and its associated set of partially labelled diagrams, is
(127)
Since there is only one diagram in the set, and fully labelled, we skip over Subprocedure II to apply Subprocedure III, obtaining the grouped map label
_ i,
(128)
Applying Subprocedure IV to unroll its right hand side does nothing, hence we obtain
(129)
Finally, there is nothing to unroll its left hand side either, hence obtain the map label
i
(130)
which we can convert into the transformation map label
Dr, (T), + Ti,
(131)
for E (3). This is (29) in the main paper.
For d once again there is only one grouped output, whose associated set of partially labelled diagrams is
(132)
As there is only one diagram in the set, we now apply Subprocedure II to it to obtain two fully labelled diagrams that are associated with the grouped output
(133)
From these fully labelled diagrams, obtain the following grouped map labels
j.
and
i _ i,
(134)
Applying Subprocedure IV to unroll the right hand side for each grouped map label does nothing, hence we obtain
1g
1g i
j.9
and
i
(135)
34

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Adding together the right hand side of the resulting left grouped map labels gives
J.j
(136)
Finally, there is nothing to unroll on its left hand side either, hence we obtain the map label
i
j.J
(137)
==1
which we can convert into the transformation map label
(T)(
Σ
Tji
(138)
for E [3). This is (30) in the main paper.
For dry. once again there is only grouped output, whose associated set of partially labelled diagrams is
(1)
(139)
As there is only one diagram in the set, we apply Subprocedure II to it to obtain two fully labelled diagrams that associated with the grouped output
(140)
From these, we obtain the following grouped map labels
-
i
and
i i i,
(141)
Applying Subprocedure IV to unroll the right hand side for each grouped map label gives
1g
1. + j.
and
lg
(142)
jf1
Adding together the right hand side of the resulting left grouped map labels and tidying gives
3
Jg
iij+
i,
(143)
f=1
Finally, there is nothing unroll its left hand side either, hence obtain the map label
i +
[1. + j. 1,1
(144)
1=1
which we can convert into the transformation map label
3
Dzy (T), Σ
This + Tyı T,
(145)
j=1
35

---

Permutation Equivariant Neural Networks for Symmetric Tensors
i E (3). This is (31) in the main paper.
Finally, for dxa= once again there is only grouped output, whose associated set of partially labelled diagrams is
(146)
As there is only one diagram in the set, we now apply Subprocedure II to it to obtain four fully labelled diagrams that are associated with the grouped output
(147)
From these, obtain the following grouped map labels
3
2
j.
k
-
j.j
i
_
i.
i,
(148)
j=1
jfi
37
kyls
Applying Subprocedure IV to unroll the right hand side for each grouped map label gives
1g
i 19 i,
j.k
J.9
(. + j.
(149)
j=1
jyy
jyya
Adding together the right hand side of the resulting left grouped map labels and tidying gives
3
j.k
(150)
j.k=1
Finally, there is nothing to unroll on its left hand side either, hence we obtain the map label
j.k k
(151)
JAk=1
which convert into the transformation map label
3
DR. (T) +
Σ Tia
(152)
J,k=1
for i E [3). This is (32) in the main paper.
E. Implementation Details
We describe the architecture and training details that were used for each of the two tasks. In implementing' the linear permutation equivariant functions, we used batch vectorised operations for each of the unrolled basis transformations that came from the corresponding transformation map labels.
Invariatt Task: We randomly generated synthetic data set consisting 5000 symmetric tensors, split into 90% training and 10% test. We trained two models which had the following specifications:
'The code is available at https://gitttii http:/twwww.cceepeppeeereeeeeeee
36

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Symi the Siz-invariant model on symmetric tensors in (R12)04 consisted of single, trainable, linear permutation equivariant function from symmetric tensors in (IR 12 to R. The total number of parameters was 3 and the training time was 2.26 seconds.
MLP consisted of single standard linear layer from IR 12x12x11 to The total number of parameters was 1728 and the training time 1.46 seconds.
Both models were optimised with stochastic gradient descent with a learning rate of 0.0001. We trained both models for 50 epochs with batch size of 50.
Sg-Equivar Task: We randommly generated synthetic data consisting of 10000 symmetric tensors, split into 90% training and 10% test. We trained three models which had the following specifications:
SymmPermmQuiv, the Sy-equivariant model on symmetric tensors in (R*)03, consisted of a single, trainable, linear permutation equivariant function from symmetric tensors in (RR5)83 symmetric tensors in RRS. The total number of parameters was and the training time was 12.01 seconds.
PermEquiv, the standard Ss-equivariant model (Maron et al., 2019a; Pearce-Crump. 2024; Godfrey et al., 2023), consisted of a single, trainable, linear permutation equivariant function from (IR*) to R The total number of parameters was 15 and the training time was 12.17 seconds.
MLP consisted of a single standard linear layer from R8 8x888 to R. The total number of parameters was 4096 and the training time was 4.38 seconds.
Both models were optimised with stochastic gradient descent with learning rate of 0.0001. We trained both models for 50 epochs with a batch size of 50. In Table 1, we used a batch size of 50 to obtain the test mean squared error (MSE). In Table 2, we generated a test set of 1000 tensors, one for each of 8, 16, 32, using the parameters of the model that was trained in the task itself for each of these models.
Comparison between Map Label and Weight Matrix Implementations: We are grateful to the reviewers for the following suggestion: they recommended that we should provide empirical evidence to justify the time and space requirements of our map label notation method compared with the standard implementation that unrolled weight matrices.
For the -12-invriaant task, the training time of SymmPermEquiv using the map label implementation was 2.26 seconds, compared to 127.55 seconds using weight matrix implementation, resulting in 60x speedup.
For the Ss-eqiivariant task, the training time of SymmPermEquiv using the map label implementation was 12.01 seconds, compared to 2451.45 seconds using a weight matrix implementation, resulting a 200x speedup.
These results demonstrate that what we have said in theory is true in practice namely that the standard weight matrix approach becomes unfeasible as n, ie and 7 become larger, owing to constraints storing the weight matrices in memory, particularly in training the networks.
37

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Subprocedure I: How to Obtain All Possible Grouped Outputs of (A,ia--iiatttiiion Diagram.
Input: A (k: bipartition diagram dz.
1. Sort the spiders in decreasing order output wires. For spiders that have the same number output wires, break ties by sorting them decreasing order of input wires. For now, ignore the following all spiders that do not have output wires.
2. Partition the spiders having output wires into groupings where spiders are in the same grouping if and only if they have the same number of output wires. Call this partition æ and the individual groupings {TB)-
3. For each grouping TB, form new partition of the spiders in gg such that spiders are in the same grouping in the new partition if and only if they have the same number of input wires. Let TB denote the new partition that corresponds to the grouping TB.
4. Suppose that the number of spiders in dæ that have output wires is t. Calculate all integer partitions of t.
5. Then, for each integer partition of t:
(a) Assign distinet label (i. J. ...) to each part of À such that the label appears as many times as the size of the part. Treating the labels as a multiset, compute all partitions of this multiset that correspond the original partition structure of modulo isomorphism: that is, identifying partitions that are equivalent under relabelling of the labels. Denote the non non-isomorphic partitions of the multiset of labels by {L}, and for each T., denote its individual groupings by (T.)).
(b) For each non-isomorphic partition L:
i. For each grouping L, compute all partitions of La that correspond to the partition structure of i B. Convert each partition of Lg into an ordered tuple of labels by replacing curly brackets with curved brackets and the vertical bar that splits groupings with a comma. Let Tt, denote the resulting set of tuples corresponding to Lp.
ii Form the Cartesian product the sets Ti,n, maintaining the order of the individual groupings TB in т. Denote the Cartesian product set of ordered labels by TX,L-
ii.. For each tuple E I. create a copy of the sorted diagram of d, and label the output spiders with 1, resulting a set xx of partially labelled diagrams that are indexed by TX.L-
iv. Create an empty set R. For each partially labelled diagram in DA L. merge spiders that are labelled with the same label. If no merging took place, continue, otherwise:
A. Reconsider the newly merged bipartition diagram da (retaining but ignoring its labels for now) and apply Steps 1, 2, and to dg. This gives a partition whose individual groupings are {0n). ). and for each grouping fg. it further partitioned into 0B.I-
B. For each grouping Op, form set from the labels of the grouping and remove the labels from the diagram. This gives partition of labels into individual groupings {Lz}-
C. Apply Step 5b to this partition of labels L for 0B.1 up to and including Step 5(b)ii.
D. Then, for each tuple in the newly created Tx. create copy of the sorted diagram of da with its labels removed and label the output spiders with l. Add the resulting diagram for each tuple to RA,L-
Take the set union of Dx. and RALL- This gives a full set of partially labelled diagrams for each non-isomorphic partition of the multiset of labels L. Denote this set by PALL- (c) Take the union of the PA.L all non-isomorphic partitions of the multiset of labels L. This gives full of partially labelled diagrams for each integer partition À of Denote this set by Px-
6. Take the set union of PA over integer partitions À of t. Denote this set by P. For each diagram in P. reorder the labelled spiders in lexicographical order. Propagate the labels the ends of the output wires. Partition the set P into subsets such that diagrams are in the same subset if and only if their tuples of output indices are the same. Label each subset with its shared tuple of output labels; each label represents grouped output for d..
Output: All possible grouped outputs for d, and, for each one, its associated set of partially labelled diagrams.
38

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Subprocedure II: How to Determine All Fully Labelled Diagrams for Partially Labelled Diagram of Grouped Output.
Input: A partially labelled diagram for grouped output of Dippaiiiiiiiiion diagram dg.
1. Suppose that the partially labelled diagram has labelled spiders, each with a separate label, and spiders with label. Call the labels in the partially labelled diagram fixed. Let Lx denote the set of fixed labels. Any other labels that are created in the following are said to be free.
2. Leaving the labelled spiders as they are, sort the unlabelled spiders in decreasing order of input wires.
3. Partition the sorted unlabelled spiders into groupings where spiders are in the same grouping if and only if they have the same number of input wires. Call this partition and the individual groupings (T
4. Consider all possible ways of labelling the unlabelled spiders, where & of them are fixed and the remaining k of them are free, for 0, ,.,... Then, for each value of k:
(a) Create multiset of k X symbols (to denote fixed) and s symbols (to denote free). Compute all partitions of this multiset that correspond to the original partition structure of Denote this set by IIx,F. (b) Now calculate all possible k-size multisets choosing labels from Lx_ allowing repeats, and all possible (s k>-size multisets choosing free labels (by introducing them as needed), also allowing repeats. Taking their Cartesian product gives all possible ways choosing & fixed indices and 8 free indices.
(c) For each pair of fixed indices and k free indices in this set:
For each partition πx,F E XT,F, compute all partitions this pair of fixed indices and free indices that correspond to the original partition structure of x,F,, modulo isomorphism: that is, identifying partitions that are equivalent under relabelling of the free indices only.
ii For each -on-isomo partition, create a copy of the sorted partially labelled diagram from Step and label the output spiders in order from left right to create a fully labelled diagram.
(d) Take the set union of the set of fully labelled diagrams for all pairs of l fixed indices and s & free indices.
5. Finally, take the set union of the set of the fully labelled diagrams for all values of k. Merge all of the spiders in each fully labelled diagram, and remove any duplicates. If it is desired, propagate the labels the ends of the wires.
Output: of fully labelled diagrams for the partially labelled diagram of grouped output.
Subprocedure III: How to Convert Fully Labelled Diagram into a Grouped Map Label.
Input: fully labelled diagram of (k,, bibbiaatnnioon diagram dg.
Convert the fully labelled diagram into a grouped map label follows:
1. Create the arrow 2
2. On its left, write the tuple that is formed from propagating the labels of the fully labelled diagram to the output wires. In particular, distinct labels that appear on the left hand side of the arrow represent distinct values.
3. On its right, write the tuple that is formed from propagating the labels of the fully labelled diagram to the input wires, summing over any labels that do not appear on the left hand side, and not allowing any summation labels to equal each other nor any label that appears on the left hand side.
Output: A grouped map label.
39

---

Permutation Equivariant Neural Networks for Symmetric Tensors
Subprocedure IV: How to Convert the Grouped Map Label for Fully Labelled Diagram into Left Grouped Map Label.
Input: A grouped map label for fully labelled diagram of (k:, () biparrttin diagram dz.
1. Consider the right hand side of the grouped map label. The summation indices correspond to free indices in Subprocedure II, and all other indices correspond fixed indices in Subprocedure II. (Each fixed index should also appear on the left hand side of the grouped map label.)
2. Replace the tuple of indices by sum of all permutations of the tuple, modulo isomorphism under relabelling of the free indices only. Also replace 2 with Ag
Output: A left grouped map label for fully labelled diagram of (t.,1)-iipartition diagram d,,.
Subprocedure V: How to Unroll the Left Hand Side of a Left Grouped Map Label.
Input: left grouped map label.
Create set of map labels for the left grouped map label by unrolling the left hand side follows:
1. Calculate all permutations the left hand side of the left grouped map label modulo isomorphism: any two permutations are said be equivalent the first can bijectively relabelled become the second, using the multiset of letters of letters formed from the left hand side of the left grouped map label.
2. For each resulting permutation, create a map label by letting it be the left hand side of the arrow <- To its right is exactly the right hand side of the left grouped map label, unchanged.
Output: A set of map labels corresponding to the left grouped map label.
40


Reviews:
[{"review_id": "vYNvj2lue4", "reviewer": "Reviewer_W7Yy", "summary": "This paper introduces permutation equivariant neural networks for symmetric tensors. In particular, this paper provides two different characterization of all linear permutation equivariant layers between symmetric tensors: orbit basis and diagram basis. Of these two characterization, the diagram basis leads to a more practical way to construct these equivariant networks by using a “map label notation” method introduced in the paper, where, the parameter sharing scheme is stored in terms of equations, which makes the overall weight matrix cheaper to save in terms of memory. Experimental results on S12-Invariant task and S8-equivariant tasks shows performance gain compared to prior methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review. We are pleased that they recognise that our work “[p]rovides equivariant network design for a new and relevant problem”, and “provides a complete characterization of the linear space with the constraint of permutation equivariance for symmetric tensors.” In particular, we felt that they understood the purpose of our paper, namely that it is “primarily focused on the theoretical aspect of solving for an equivariant network and providing an algorithm to construct such networks.”\n\nWe welcome the reviewer’s positive comments on the ease of implementing our method and the performance gain and generalisation that we demonstrated for the $S_{12}$-invariant task. We address the points where the reviewer sought additional clarity.\n\n1A) The significance of the two classifications is as follows: the orbit basis is needed to be able to define the diagram basis and then prove that it is a basis (see equation (21), Theorem 5.7 and Proposition 5.9). This follows the historical development of “standard” permutation equivariant layers, where the orbit basis was first introduced by Maron et al. [1] and only later was the diagram basis discovered by Godfrey et al. [2]. The orbit basis emerges naturally from the “equivariance equation” (10), whereas the diagram basis requires additional work to be constructed. The diagram basis, however, is more practical for implementation purposes because, with the map label notation, the resulting transformations are easier to vectorise, leading to improved computational efficiency.\n\n1B) The map label notation saves memory in two important ways:\n\n1.\tStandard neural network methods would require us storing an explicit $n^l \\times n^k$ weight matrix in memory whereas, with our approach, we eliminate the need to store large weight matrices by using each (k,l)-bipartition diagram to encode the weight-sharing scheme directly in the map labels.\n2.\tThis leads to significant efficiency during the forward pass: since the structure of the transformation is encoded directly in the (k,l)-bipartition diagrams, this means that instead of performing a standard “weight matrix times input vector/tensor”, we can apply transformations directly to input vectors/tensors by using the diagrams to “pick out” exactly which elements of the input appear in the output and how they are combined (i.e sum). This results in a more efficient forward pass since only the necessary computations are performed on the inputs.\n\nFor DeepSets, i.e permutation equivariant functions from $\\mathbb{R}^n$ to $\\mathbb{R}^n$, in our method we need to calculate all possible (1,1)-bipartition diagrams with at most n blocks. These are given in equation (55) of our paper. From these diagrams we can immediately see that the corresponding map labels for the unrolled basis matrices are $i \\leftarrow i$ and $i \\leftarrow \\sum_{j=1}^{n} j$. \nHence we get that\nD_{\\pi_1}(T)_i = T_i\nand D_{\\pi_2}(T)_i = \\sum_{j=1}^{n} T_j\nfor an input $T$ in $\\mathbb{R}^n$, and so \n$D_{\\pi_1}(T) = T$\nand \n$D_{\\pi_2}(T)$ is $\\sum_{j=1}^{n} T_j$ times the all 1s vector in $\\mathbb{R}^n$. Note that we have not had to create an $n \\times n$ weight matrix to do this, but we can see by inspection that the operations themselves correspond to the identity matrix and the all ones matrix, respectively. Consequently we have recovered the Deep Sets characterisation while using significantly less memory ($O(n)$ vs $O(n^2)$).\n\nRegarding timings and parameter counts for the models (we will include these numbers in a revised version of our paper):\n- $S_{12}$ task:\n  -\tSymmPermEquiv: training time: 2.26 secs, inference time: 0.01 secs, number of parameters: 3\n  -\tSimpleMLP: training time: 1.46 secs, inference time: 0.006 secs, number of parameters: 1728\n-\t$S_8$ task:\n  -\tSymmPermEquiv: training time: 12.01 secs, inference time: 0.026 secs, number of parameters: 7\n  -\tSimpleMLP: training time: 4.38 secs, inference time: 0.008 secs, number of parameters: 4096\n  -\tPermEquiv: training time: 12.17 secs, inference time: 0.024 secs, number of parameters: 15\n\nFinally, on the synthetic experiments: to the best of our knowledge, there are currently no widely available real-world datasets consisting of symmetric tensors. Consequently, we designed simple experiments to validate our theoretical results in a controlled setting, following the standard approach that was adopted in prior works on permutation equivariance where synthetic datasets were used (e.g in [1]). However, we recognise that real-world applications of our results would further demonstrate their impact, and so we look forward to exploring them in future work. \n\n[1] Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. (2019). Invariant and Equivariant Graph Networks. In International Conference on Learning Representations. \n\n[2] Godfrey, C., Rawson, M. G., Brown, D., Kvinge, H. (2023). Fast computation of permutation equivariant layers with the partition algebra. arXiv:2303.06208.", "claims_and_evidence": "Looks good to me", "methods_and_evaluation_criteria": "The introduction of the paper motivates the need for permutation equivariant networks for symmetric tensors with several practical applications, but the paper does not provide any practical applications in experiments. Even the synthetic experiments seem limited. Why is that? Is it applicable in more scenarios and datasets where it can be tested?", "theoretical_claims": "Looks good to me", "experimental_designs_or_analyses": "In the experiments, how does the number of parameters and training and inference time compare for the proposed model vs existing equivariant and non-equivariant models?", "relation_to_broader_scientific_literature": "This is related to equivariant machine learning with interest to the broader research community", "essential_references_not_discussed": "Looks good to me", "other_strengths_and_weaknesses": "Strengths:\n1. Provides equivariant network design for a new and relevant problem. Provides complete characterization of the linear space with the constraint of permutation equivariant for symmetric tensors\n2. Proposes a practical method that can be implemented easily\n3. Provides experimental results showing performance gain both in terms of sample efficiency (for S12-invariant task), and MSE reduction and generalization for the S12-equivariant task\n\n\nWeaknesses:\n1. Clarity: I understand the paper is primarily focused on the theoretical aspect of solving for an equivariant network and providing an algorithm to construct such networks. But I would request the authors to provide better clarity on few aspects that seemed confusing to me.\n\tA. What is the significance of the two characterizations: orbit basis and diagonal basis? Is there any reason for introducing the orbit basis since the diagonal basis seems more useful and used for implementation. \n\tB. I am a bit confused about how the map label notation is saving memory, is it saving memory during the use of the network, e.g., during forward pass or is the memory saving only during stpring the weights? Can you explain with an example, e.g., for deepsets, how does the map label notation look like and how it the memory saved?\n2. In the experiments, how does the number of parameters and training and inference time compare for the proposed model vs existing equivariant and non-equivariant models? \n3. The introduction of the paper motivates the need for permutation equivariant networks for symmetric tensors with several practical applications, but the paper does not provide any practical applications in experiments. Even the synthetic experiments seem limited. Why is that? Is it applicable in more scenarios and datasets where it can be tested?", "other_comments_or_suggestions": "None", "questions_for_authors": "Please see weaknesses", "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": "vCzdj0mUoC", "reviewer": "Reviewer_igq4", "summary": "This work introduces an exact characterization of all linear permutation equivariant functions between symmetric power spaces. The authors introduce the map label notation, which makes it possible to express a transformation as a series of equations, thereby eliminating the need to store the weights explicitly. They validate their approach on two toy datasets.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their critique of our work. We are pleased that they recognise that our work is “the first […] to obtain an exact characterization of permutation equivariant linear functions applied to symmetric tensors”. This aligns with the opinions of all of the other reviewers. We also appreciate their positive remarks on the clarity of our writing, the conciseness of the paper, and the role of examples and figures in building intuition.\n\nWe acknowledge that our paper is mathematically rigourous. However, we made a conscious effort to make our contributions as accessible as possible to the machine learning community by supplementing the theory with concrete examples and detailed figures. We have also committed to Reviewer dHkL’s suggestion to include a background section on symmetric powers and symmetric tensors in the appendix to further aid the general reader’s understanding.\n\nWhile the primary contribution of our work is theoretical, it has direct applications in fields where symmetric tensors naturally arise, such as molecular modelling, learning on graphs and hypergraphs, simulations in physics, and statistical modelling, amongst others. The main advantage of our method is that it provides an exact characterisation of permutation equivariant layers for symmetric tensors. This ensures that models that use symmetric tensors as inputs can explicitly enforce permutation equivariance – this is a crucial property that generic permutation equivariant layers or standard MLPs do not guarantee. Additionally, our method provides significant computational benefits: rather than storing a weight matrix, we leverage our map label notation for efficient implementation, which allows for 1) exact permutation equivariance, 2) improved performance (lower test MSE), and 3) an ability to generalise to different input sizes, as demonstrated by our experimental results.\n\nOn the concern about experimental evaluation, we refer the reviewer to our response to Reviewer gZqA, where we explain that given the novelty of our characterisation and the lack of widely available real-world datasets consisting of symmetric tensors, we followed the standard approach that was adopted in prior works on permutation equivariance where synthetic datasets were used. Nevertheless, we agree that future work could explore real-world applications to further demonstrate the broader practical benefits of our contributions.", "claims_and_evidence": "The claims are supported by extensive proofs, remarks, and examples.", "methods_and_evaluation_criteria": "The two toy datasets used seem to be appropriate for the problem at hand. There are, however, no real datasets on which the proposed method demonstrates its effectiveness and efficiency.", "theoretical_claims": "I did not check the correctness of the theoretical claims.", "experimental_designs_or_analyses": "I did not check the soundness of the experimental design.", "relation_to_broader_scientific_literature": "There is a growing literature on equivariant neural networks. While symmetric tensors appear in various scientific domains, this is the first work to obtain an exact characterization of permutation equivariant linear functions applied to symmetric tensors.", "essential_references_not_discussed": "There are no essential references missing.", "other_strengths_and_weaknesses": "The paper is extremely hard to follow, unless someone is well-versed in the theory of permutation equivariant neural networks.\n\nOn the other hand, the paper is well-written, it is quite concise, with multiple examples, and nice figures that bring intuition to the theory.\n\nThe experimental evaluation is severely lacking. There are only two datasets on which the proposed method is evaluated.\n\nIn general, it is extremely unclear to me how this work would be employed in real-world applications, and what advantages does it bring in applications with symmetric tensors as inputs.", "other_comments_or_suggestions": "None", "questions_for_authors": "[1]  The experimental evaluation is severely lacking. I would expect to see evaluation on some real-world datasets. What advantages (efficiency/effectiveness) does the proposed method bring in real applications with symmetric tensors as inputs?", "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": "gTxjipJcwB", "reviewer": "Reviewer_gZqA", "summary": "The paper derives an equivariant weight matrix for symmetric tensors, for example, a covariance matrix. They found the condition of permutation equivariant and expressed it into two bases: the orbit basis and the diagram basis. The diagram basis is more efficient to compute, although both compose the same space.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing a positive critique of our work. We are pleased that the reviewer recognises that our work “invented a permutation equivariance for symmetric tensors, which had never been tackled before”, and found our theoretical and empirical evidence “convincing”.\n\nGiven that our work is primarily a theoretical contribution, the goal of our numerical experiments was to empirically validate our theoretical findings. Specifically, we aimed to demonstrate the advantages of our linear layer characterisation over both a standard MLP layer and a generic permutation equivariant layer (as introduced in [1]) in terms of test MSE. We showed that the empirical data aligned with our theoretical results.\n\nWhilst we acknowledge the importance of real-world experiments for demonstrating practical applicability, given the novelty of our characterisation and the lack of any suitable real-world datasets, we have been limited to exploring these networks’ potential on synthetic data. In doing so, we followed the approach of prior works in permutation equivariance (e.g., such as Maron et al. [1]) which have also relied on synthetic experiments. We believe that our results provide a solid foundation for future investigations on real-world datasets, and we look forward to exploring them in future work.\n\nFinally, we appreciate the suggestion to provide details of the specification of the MLPs, hence we will add this information in a revised edition of the paper.\n\n[1] Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. (2019). Invariant and Equivariant Graph Networks. In International Conference on Learning Representations.", "claims_and_evidence": "The theoretical and empirical evidence are convincing.", "methods_and_evaluation_criteria": "The method makes sense.", "theoretical_claims": "I did not check the proofs, but I could understand that the proposed bases achieve the permutation equivariance for the symmetric tensors.", "experimental_designs_or_analyses": "The experimental design and analyses are valid. However, the only concern is that the conducted experiments are only on synthetic datasets and the target function seems too simple. Real or more complicated data would be good to enhance the necessity of the symmetric tensor permutation equivariant NNs for the machine learning community.", "relation_to_broader_scientific_literature": "The paper invented a permutation equivariance for symmetric tensors, which had never been tackled before.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "G63Za8zbnX", "reviewer": "Reviewer_dHkL", "summary": "The paper studies permutation equivariant models on symmetric tensors. It presents two characterizations of all linear permutation equivariant functions between symmetric spaces. Subsequently, the paper offers methods for generating the basis of these transformations and performing them in a memory-efficient manner.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s thoughtful and positive critique of our work. We are delighted that they recognise the “novel contributions” that are contained in our paper; particularly, the characterisation of the linear permutation equivariant layers for symmetric tensors and the map label notation that improves the memory efficiency in their implementation.\n\nWe are also pleased that the reviewer found our theoretical framework to be “exceptionally well-written” and that the illustrative examples provided in both the main text and the appendix “significantly improve the understanding of the methods presented”. Furthermore, we are encouraged that the reviewer recognises the “practical relevance” of our contributions and their potential application across multiple scientific domains.\n\nWe greatly appreciate the constructive suggestions that the reviewer made to improve the overall quality of the paper. In a revised edition of this paper, we will add a background section on symmetric powers and symmetric tensors to the beginning of the appendix to aid readers who may not be familiar with these concepts. We will also include an additional section that compares the paper’s findings with previous works in order to make clear the novel aspects of our approach.\n\nThe reviewer asked us to verify their understanding regarding the novelty of our contributions. We confirm that\n- the (k,l)-bipartition diagram is novel and forms the foundation for the diagram basis, which is also a novel contribution.\n- The map label notation results in a more efficient method for performing these equivariant linear transformations, since, as we said in our response to Reviewer W7Yy, it saves memory in two important ways: it eliminates the need to store large weight matrices and it improves the forward pass through the network.\n\nRegarding the (k,l)-orbit bipartition diagram, a related concept appeared in Bastias et al. (2024) [1], but only for the case where $k = l$. Our work extends this to general $k$ and $l$, which is not a trivial extension, as it opened up the possibility to characterise equivariant linear maps between different symmetric power spaces. More importantly, our approach to construct these diagrams is fundamentally different:\n\n- We introduce a new design that connects individual wires up to central nodes, whereas Bastias et al. (2024) rely on equivalence classes of diagrams for each bipartition, which are more challenging to work with.\n- Our construction allows for a clear representation of the action of $S_n$ on these diagrams, showing that what appears to be a complex action on the set $S[n]^l \\times S[n]^k$ can be simplified to an action of $S_n$ on the set $\\{1, \\dots, n\\}$.\n- This results in an intuitive and efficient method for constructing the orbit basis between symmetric power spaces.\n\nAdditionally, our algorithm for generating all (k,l)-bipartition diagrams having at most n blocks, as presented in Appendix B, is novel. This algorithm plays a crucial role in constructing the diagram basis efficiently, and adds to the theoretical contributions in the paper itself.\n\nIn noting that “this is primarily a theoretical paper”, we felt that the reviewer really understood the purpose of our paper. Whilst we agree that including real world experiments would improve its completeness, unfortunately we have been limited to exploring these networks’ potential on synthetic data, owing to the lack of established real-world datasets consisting of symmetric tensors. Consequently, we have designed experiments with the goal of validating our theoretical findings. \n\nWe also acknowledge the reviewer’s suggestion to provide empirical evidence to justify the time and space requirements of our method compared to the vanilla approach using unrolled matrices. The following results show that what we have said in theory (namely that the standard “weight matrix times vector” approach becomes unfeasible as $n, k$ and $l$ become larger owing to constraints on storing the weight matrix in memory) is true in practice, particularly in the training of the network, with a 60x speedup for the $S_{12}$ task and a 200x speedup for the $S_8$ task:\n- $S_{12}$ task:\n  - SymmPermEquiv (map label implementation): training time: 2.26 seconds, inference time: 0.01 seconds\n  -\tSymmPermEquiv (weight matrix implementation): training time: 127.55 seconds, inference time: 0.15 seconds\n-\t$S_8$ task:\n  -\tSymmPermEquiv (map label implementation): training time: 12.01 seconds, inference time: 0.026 seconds\n  -\tSymmPermEquiv (weight matrix implementation): training time: 2451.45 seconds, inference time: 1.25 seconds\n\nWe will include some additional commentary on this comparison in a camera ready version of the paper should it be accepted for publication.\n\n[1] Bastias, K. O., Martin, P., and Ryom-Hansen, S. (2024) On the spherical partition algebra. arXiv:2402.01890. (To be published in the Israel Journal of Mathematics)", "claims_and_evidence": "The theoretical claims presented in this paper are substantiated by proofs presented in the main text and the appendix.", "methods_and_evaluation_criteria": "The authors assessed the effectiveness of their method by conducting experiments on two toy tasks. They also provided detailed implementation information in the appendix, which aligns with the methods presented in this paper.", "theoretical_claims": "The theoretical claims presented in this paper appear to be valid. The paper’s theory is exceptionally well-written, accompanied by numerous illustrative examples throughout the main text and the appendix. These examples significantly improve the understanding of the methods presented. While I haven’t identified any major flaws in the theory, I do have a few suggestions to enhance the paper’s quality:\n\n1. It would be helpful to include an introductory section in the appendix that provides a background on the theoretical concepts discussed in the paper, particularly symmetric powers and symmetric tensors. Although the paper already includes numerous examples that facilitate understanding, readers unfamiliar with these concepts may find the paper initially challenging.\n\n2. It would be helpful to include a section that compares the paper’s findings with previous works. This would help highlight the novel contributions of this paper. Based on my understanding, the $(k.l)$-orbit bipartition diagram is not novel, while the $(k.l)$-bipartition diagram is novel and is more efficient for performing equivariant linear transformations. However, I would appreciate it if the authors could verify my understanding.", "experimental_designs_or_analyses": "The authors validate the effectiveness of their method on two toy tasks. While this is primarily a theoretical paper, including real-world experiments would improve its completeness. In Section 7, the authors mentioned that using map label notation eliminates the need for additional memory for performing linear equivariant transformations between symmetric powers. It would be beneficial for the authors to provide empirical evidence, through experiments, to justify the time and space requirements of their method compared to the vanilla method using unrolled matrices.", "relation_to_broader_scientific_literature": "This paper presents a general approach to characterizing linear equivariant functions on symmetric tensors. Its applications have practical relevance in various domains such as graph analysis, molecular modeling, and physical simulations.", "essential_references_not_discussed": "There are no missing essential references for this paper.", "other_strengths_and_weaknesses": "The strengths and weaknesses are thoroughly discussed in the preceding points.", "other_comments_or_suggestions": "I have no additional comments.", "questions_for_authors": "I have no additional questions.", "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:

Meta-review: The submission received mostly positive reviews. Reviewers valued that the paper develops a new kind of equivariant NN and completely characterizes its filters. Reviewers also praised the presentation quality.

The main issues raised were about the experimental section. The method is only applied to two toy problems and the authors acknowledged that the work is primarily theoretical and there are currently no real-world datasets where it could be applied.

While one reviewer recommends rejection on the grounds of weak experiments, the other three agree that the theoretical contributions are worth being published regardless.
Decision: Accept (poster)