# A Classification of $G$-Invariant Shallow Neural Networks

Devanshu Agrawal & James Ostrowski
Department of Industrial and Systems Engineering
University of Tennessee
Knoxville, TN 37996
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

When trying to fit a deep neural network (DNN) to a $G$-invariant target
function with respect to a group $G$, it only makes sense to constrain the DNN
to be $G$-invariant as well. However, there can be many different ways to do
this, thus raising the problem of “$G$-invariant neural architecture design”:
What is the optimal $G$-invariant architecture for a given problem? Before we
can consider the optimization problem itself, we must understand the search
space, the architectures in it, and how they relate to one another. In this
paper, we take a first step towards this goal; we prove a theorem that gives a
classification of all $G$-invariant single-hidden-layer or “shallow” neural
network ($G$-SNN) architectures with ReLU activation for any finite orthogonal
group $G$. The proof is based on a correspondence of every $G$-SNN to a signed
permutation representation of $G$ acting on the hidden neurons. The
classification is equivalently given in terms of the first cohomology classes
of $G$, thus admitting a topological interpretation. Based on a code
implementation, we enumerate the $G$-SNN architectures for some example groups
$G$ and visualize their structure. We draw the network morphisms between the
enumerated architectures that can be leveraged during neural architecture
search (NAS). Finally, we prove that architectures corresponding to
inequivalent cohomology classes in a given cohomology ring coincide in
function space only when their weight matrices are zero, and we discuss the
implications of this in the context of NAS.

###  1 Introduction

When trying to fit a deep neural network (DNN) to a target function that is
known to be $G$-invariant with respect to a group $G$, it is desirable to
enforce $G$-invariance on the DNN as prior knowledge. This is a common
scenario in many applications such as computer vision, where the class of an
object in an image may be independent of its orientation (Veeling et al.,
2018), or point clouds that are permutation-invariant (Qi et al., 2017).
Numerous $G$-invariant DNN architectures have been proposed over the years,
including group-equivariant convolutional neural networks (G-CNNs) (Cohen and
Welling, 2016), DNNs with high-order $G$-equivariant multilinear layers (Maron
et al., 2019), and a more recent architecture built on a $G$-invariant sum-
product layer (Kicki et al., 2020). However, it is unclear which of these
architectures a practitioner should choose for a given problem, and even after
one is selected, additional design choices must be made; for G-CNNs alone, the
practitioner must select a sequence of representations of $G$ to determine the
composition of layers, and it is unknown how best to do this. Moreover,
despite a complete classification of G-CNNs (Kondor and Trivedi, 2018; Cohen
et al., 2019), it is unknown if every $G$-invariant DNN is a G-CNN, and hence
the “optimal” $G$-invariant architecture may not even exist in the space of
G-CNNs.

For some architectures, universality theorems have been proven guaranteeing
the approximation of any $G$-invariant function with arbitrarily small
error (Maron et al., 2019; Ravanbakhsh, 2020; Kicki et al., 2020), and it is
thus tempting to conclude that these universal architectures are sufficient
for all $G$-invariant problems. However, it is well-known that universality
(Cybenko, 1989) alone is not a sufficient condition for a good DNN model and
that the function subspaces that a network traverses as it grows to the
universality limit is just as important as the limit itself. This suggests
that the way in which a DNN is constrained to be $G$-invariant does matter,
and different $G$-invariant architectures may be suitable for different
problems. This raises the fundamental question: For a given problem, what is
the “best” way to constrain the parameters of a DNN such that it is
$G$-invariant?

This paper takes a first step towards answering the above question.
Specifically, before we can consider the optimization problem for the best
$G$-invariant architecture, we must understand the search space: What are all
the possible ways to constrain the parameters of a DNN such that it is
$G$-invariant, and how are these different $G$-invariant architectures related
to one another?

The above is a special case of the broader and more fundamental problem of
neural architecture design. One of the most prominent approaches to this
problem in the literature is neural architecture search (NAS), which at its
core is trial-and-error (Elsken et al., 2019). While trial-and-error is—in
principle—straightforward for determining, e.g., the optimal depth or hidden
widths of a DNN, it is less clear for $G$-invariant architectures, where a
practitioner does not even know all their options. More generally, NAS
presupposes knowledge about which architectures are in the search space, which
ones are not, which ones are equivalent or special cases of others, and how
best one should move from one architecture to another. Thus, to apply even the
simplest approach to $G$-invariant neural architecture design, we must first
be able to enumerate all $G$-invariant architectures.

Our main result is Thm. 5, which gives a classification of all $G$-invariant
single-hidden-layer or “shallow” neural network ($G$-SNN) architectures with
rectified linear unit (reLU) activation, for any finite orthogonal group $G$
acting on the input space. More precisely, every $G$-SNN architecture can be
decomposed into a sum of “irreducible” ones, and Thm. 5 classifies these. The
classification is based on a correspondence of each irreducible architecture
to a representation of G in terms of its action on the hidden neurons via so-
called “signed permutations”, where the representation is required to satisfy
an additional condition to eliminate degenerate (linear) architectures and
redundant architectures equivalent to simpler ones. The classification then
boils down to the classification of these representations. These
representations, and hence the corresponding architectures as well, are
classified in terms of the first cohomology classes of $G$ and thus admit a
topological interpretation. We note that, while connections between neural
networks and the group of signed permutations have been previously made in the
literature (Ojha, 2000; Negrinho and Martins, 2014; Arjevani and Field, 2020),
to our knowledge, no such connection has yet been leveraged to begin a
classification program of $G$-invariant architectures.

This paper is perhaps most similar in spirit to the works of Kondor and
Trivedi (2018) and Cohen et al. (2019) and draws on similar mathematical
machinery; like them, this paper’s contribution is also primarily theoretical.
Kondor and Trivedi (2018) prove that every $G$-invariant DNN is a g-cnn under
the assumption that every layer is $G$-equivariant; that this is true without
the assumption is only conjectured. Cohen et al. (2019) generalize this to
G-CNNs where hidden activations are vector fields and provide a classification
of all G-CNNs, but the conjecture of Kondor and Trivedi (2018) is left open.
In contrast to these works, in our paper, we do not assume the pre-activation
affine transformation to be $G$-equivariant– only that the whole network is
$G$-invariant. Thus, a future extension of Thm. 5 to deep architectures would
either prove or refute the cited conjecture.

The remainder of the paper is organized as follows: In Sec. 2, we give a
classification of the “signed permutation representations” of $G$ and relate
these representations to the cohomology classes of $G$.111We assume some
familiarity with group theory including semidirect products and quotient
groups, conjugacy classes of subgroups, and group action (see Herstein, 2006).
We also assume a basic understanding of group cohomology in Sec. 2.3 (Brown,
2012), but we hope the visualizations in Figs. 1,4-6 are sufficient to convey
the concept. The visualizations are based on a geometric perspective of
cohomology on Cayley graphs (Druţu and Kapovich, 2018, sec. 5.9); see (Tao,
2012) for intuition. Then in Sec. 3, we build towards the statement of our
main classification theorem of $G$-SNN architectures. While Sec. 2 makes
little reference to $G$-SNNs, presenting it upfront helps to streamline the
exposition in Sec. 3, with much of the notation and terminology established.
In Sec. 4, we visualize the $G$-SNN architectures for some example groups $G$
and remark on the “network morphisms” between the architectures. Finally, in
Sec. 5, we end with conclusions and next steps towards the problem of
$G$-invariant neural architecture design.

###  2 Signed permutation representations

####  2.1 Preliminaries

Throughout this paper, let $G$ be a finite group of $m\times m$ orthogonal
matrices. Let $\mathcal{P}(n)$ be the group of all $n\times n$ permutation
matrices and $\mathcal{Z}(n)$ the group of all $n\times n$ diagonal matrices
with diagonal entries $\pm 1$. Let
$\mathrm{PZ}(n)=\mathcal{P}(n)\ltimes\mathcal{Z}(n)$, which is the group of
all _signed permutations_ – i.e., the group of all permutations and
reflections of the standard orthonormal basis $\\{e_{1},\ldots,e_{n}\\}$. This
group is also called the hyperoctahedral group in the literature (Baake,
1984).

A _signed permutation representation_ (signed perm-rep) of degree $n$ of $G$
is a homomorphism $\rho:G\mapsto\mathrm{PZ}(n)$. Whenever we say $\rho$ is a
signed perm-rep, let it be understood that its degree is $n$ unless we say
otherwise. A signed perm-rep $\rho$ is said to be _irreducible_ if for every
$i,j=1,\ldots,n$, there exists $g\in G$ such that $\rho(g)e_{i}=\pm e_{j}$. As
we will see in Sec. 3.2, every $G$-SNN can be written as a sum of
“irreducible” $G$-SNNs, and every irreducible $G$-SNN corresponds to an
irreducible signed perm-rep. It is therefore sufficient for our purposes to
classify all irreducible signed perm-reps of $G$; moreover, this need only be
done up to conjugacy as seen next.

####  2.2 Classification up to conjugacy

Two signed perm-reps $\rho,\rho^{\prime}$ are said to be _conjugate_ if there
exists $A\in\mathrm{PZ}(n)$ such that $\rho^{\prime}(g)=A^{-1}\rho(g)A\forall
g\in G$. We let $\rho^{\mathrm{PZ}}$ denote the conjugacy class of the signed
perm-rep $\rho$. Note that conjugation preserves the (ir)reducibility of a
signed perm-rep (Prop. 7 in Supp. A.1), and it thus makes sense to speak of
the irreducibility of an entire conjugacy class $\rho^{\mathrm{PZ}}$. The
significance of the conjugacy relation is that conjugate signed perm-reps
correspond to the same $G$-SNN (see Sec. 3.2); we are thus interested in the
classification of irreducible signed perm-reps only up to conjugacy.

Our first theorem below gives the desired classification of signed perm-
reps.222All proofs, as well as additional lemmas and useful propositions, can
be found in the supplementary material. For $H,K\leq G$, let $(H,K)^{G}$
denote the _paired conjugacy class_

$(H,K)^{G}=\\{(g^{-1}Hg,g^{-1}Kg):g\in G\\}.$

Define the following set of conjugacy classes of subgroup pairs:

$\mathcal{C}^{G}_{\leq 2}=\\{(H,K)^{G}:K\leq H\leq G\mid|H:K|\leq 2\\}.$

######  Theorem 1.

Let $(H,K)^{G}\in\mathcal{C}^{G}_{\leq 2}$ and $(g_{1},\ldots,g_{n})$ a
transversal of $G/H$ with $g_{1}\in K$. For each $i=1,\ldots,n$, define
$g_{-i}=g_{i}h$ for some $h\in H\setminus K$ if $|H:K|=2$ and $h=1$ if
$|H:K|=1$. Define the signed perm-rep $\rho_{HK}$ such that
$\rho_{HK}(g)e_{i}=e_{j}$ if $gg_{i}K=g_{j}K$ for every $i,j=\pm 1,\ldots,\pm
n$. Then:

  1. (a)

Every $\rho_{HK}$ is irreducible.

  2. (b)

For every irreducible signed perm-rep $\rho^{\prime}$, there exists a unique
$(H,K)^{G}$ such that $\rho^{\prime}$ is conjugate to $\rho_{HK}$.

Theorem 1 equivalently states that the set

$\mathcal{R}^{\mathrm{PZ}}(G)=\\{\rho_{HK}^{\mathrm{PZ}}:(H,K)^{G}\in\mathcal{C}^{G}_{\leq
2}\\}$

is a partition on the set of all irreducible signed perm-reps into conjugacy
classes.

####  2.3 Group cohomology

Every irreducible signed perm-rep is either _type 1_ or _type 2_ , which
differ in their properties; see Lemma 8 in Supp. A.1 for details. We
originally introduced this dichotomy because the two types would often give
rise to casewise results or proofs. It turns out, however, that there is a
deeper meaning as well, which will be important for interpreting the
classification of $G$-SNNs.

For every $\rho_{HK}\in\mathcal{R}(G)$, let $\pi_{H}:G\mapsto\mathcal{P}(n)$
and $\zeta^{\mathrm{L}}_{HK}:G\mapsto\mathcal{Z}(n)$ be the unique functions
satisfying $\rho_{HK}(g)=\zeta^{\mathrm{L}}_{HK}(g)\pi_{H}(g)\forall g\in
G$.333By uniqueness of factorization in a semidirect product, there exist
unique functions $\pi:G\mapsto\mathcal{P}(n)$ and
$\zeta,\zeta^{\mathrm{L}}:G\mapsto\mathcal{Z}(n)$ such that
$\rho(g)=\pi(g)\zeta(g)=\zeta^{\mathrm{L}}(g)\pi(g)\forall g\in G$. The
superscript “L” in $\zeta^{\mathrm{L}}$ indicates that it is the left factor,
in contrast to $\zeta$. Note that $\pi_{H}$ is independent of $K$ (Prop. 14 in
Supp. A.3). The following proposition relates the structure of irreducible
signed perm-reps of $G$ to its cohomology.

######  Proposition 2.

For every $\rho_{HK}^{\mathrm{PZ}}\in\mathcal{R}^{\mathrm{PZ}}(G)$, let
$M_{H}$ be a $G$-module over the field $\mathbb{F}_{2}=\\{0,1\\}$, where $G$
acts on $M_{H}$ by the perm rep $\pi_{H}$. Define
$\hat{\zeta^{\mathrm{L}}}_{HK}:G\mapsto M_{H}$ such that
$\hat{\zeta^{\mathrm{L}}}_{HK}(g)=\frac{1}{2}[I-\operatorname{diag}(\zeta^{\mathrm{L}}_{HK}(g))]$.
Then:

  1. (a)

The first cohomology group of $G$ with coefficients in $M_{H}$ is given
by444We use the notation $\\{\ldots\\}_{\neq}$ to emphasize that, during the
construction of the set, the enumerated elements are distinct.

$\mathcal{H}^{1}(G,M_{H})=\\{[hat{\zeta^{\mathrm{L}}}_{HK}]:K\leq
H\mid|H:K|\leq 2\\}_{\neq},$

where $[\hat{\zeta^{\mathrm{L}}}_{HK}]$ is the set of all cocycles
cohomologous to $\zeta^{\mathrm{L}}_{HK}$, and where the addition operation
satisfies

$[\hat{\zeta^{\mathrm{L}}}_{HK}]=[\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]+[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]\Leftrightarrow
K=K_{1}\cap K_{2}\cup((H\setminus K_{1})\cap(H\setminus K_{2})).$

  2. (b)

The partition of the first cohomology group into orbits under the action of
the $G$-module automorphism group $\operatorname{aut}(M_{H})$ is given by

$H^{1}(G,M_{H})/\operatorname{aut}(M_{H})=\\{\\{[\hat{\zeta^{\mathrm{L}}}_{HK^{\prime}}]:(H,K^{\prime})\in(H,K)^{G}\\}:(H,K)^{G}\in\mathcal{C}^{G}_{\leq
2}\\}.$

  3. (c)

$\rho_{HK}$ is type 1 if and only if $\hat{\zeta^{\mathrm{L}}}_{HK}$ is in the
zero cohomology class.

The type 1 vs. type 2 dichotomy is thus rooted in whether a signed perm-rep
“twists” over $G/H$. Proposition 2 also lets us interpret the notation
$\rho_{HK}$: The subgroup $H$ determines the coefficient module $M_{H}$ and
hence the cohomology ring, and the subgroup $K$ determines the cohomology
class in $\mathcal{H}^{1}(G,M_{H})$. Most importantly, Prop. 2 provides a
topological interpretation of the organization of the space of $G$-SNNs, as we
will see later in this paper.

###  3 Classification of $G$-SNNs

####  3.1 Canonical parameterization

A _shallow neural network_ (SNN) is a function
$f:\mathbb{R}^{m}\mapsto\mathbb{R}$ of the form

$f(x)=a^{\top}\operatorname{ReLU}(Wx+b),$ (1)

where $W\in\mathbb{R}^{n\times m}$ and $a,b\in\mathbb{R}^{n}$ for some $n$.
Here $\operatorname{ReLU}$ is the _rectified linear unit_ activation function
defined as $\operatorname{ReLU}(x)=\operatorname{max}(0,x)$ elementwise. The
parameterization of an SNN given in Eq. 1 contains redundancies in the sense
that different parameter configurations can define the same function. For
example, applying a permutation to the rows of $a$, $b$, and $W$ generally
results in a different parameter configuration but always leaves $f$
invariant. Also, by the identity

$\operatorname{ReLU}(zx)=\operatorname{ReLU}(x)-H(-z)x,x\in\mathbb{R},z\in\\{-1,1\\},$
(2)

(where $H$ is the Heaviside step function; see Prop. 15 in Supp. B), the
reflection of a row of the augmented matrix $[W\mid b]$ in Eq. 1 is equivalent
to the addition of an affine term, which can be interpreted as two additional
hidden neurons. Note that these permutation and reflection redundancies form
the group $\mathrm{PZ}(n)$. The lemma below will help us define a “canonical
parameterization” in which such redundancies are eliminated.

######  Lemma 3.

Let $\Theta_{n}$ be the set of all augmented matrices $[W\mid
b]\in\mathbb{R}^{n\times(m+1)}$ such that the rows of $W$ have unit norms and
no two rows of $[W\mid b]$ are parallel. Let $\Omega_{n}\subset\Theta_{n}$ be
a fundamental domain555If a group $G$ acts on a set $\mathcal{X}$, then a
fundamental domain is a set $\Omega\subseteq\mathcal{X}$ such that
$\\{g\Omega:g\in G\\}$ is a partition of $\mathcal{X}$. An example fundamental
domain in $\Theta_{n}$ under the action of $\mathrm{PZ}(n)$ is given in Prop.
17 (see Supp. B.1). under the action of $\mathrm{PZ}(n)$. Let
$f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be an SNN of the form in Eq. 1. Then there
exist unique $n_{*}\in\mathbb{N}$, $[W_{*}\mid b_{*}]\in\Omega_{n_{*}}$,
$a_{*}\in\mathbb{R}^{n_{*}}$ with nonzero elements, $c_{*}\in\mathbb{R}^{m}$,
and $d_{*}\in\mathbb{R}$ such that:

$f(x)=a_{*}^{\top}\operatorname{ReLU}(W_{*}x+b_{*})+c_{*}^{\top}x+d_{*}\forall
x\in\mathbb{R}^{m}.$

We refer to the unique parameterization of the SNN $f$ in terms of
$(a_{*},b_{*},c_{*},d_{*},W_{*})$ as its _canonical parameterization_ , and
the SNN is then said to be in _canonical form_. We call $b_{*}$, $W_{*}$, and
the rows of $W_{*}$ the canonical _bias_ , _weight matrix_ , and _weight
vectors_ of the $G$-SNN respectively. Note that the canonical parameterization
is a function of the choice of fundamental domain $\Omega_{n_{*}}$.

####  3.2 $G$-SNNs and signed perm-reps

For $f$ to be a $G$-invariant SNN ($G$-SNN), the action of $g\in G$ on the
domain of $f$ must be equivalent to one of the redundancies in the
parameterization of SNNs. In the canonical parameterization, however, this
means that the parameters of $f$ and of $f\circ g$ must be identical. This
places constraints on the canonical parameters of a $G$-SNN, as made precise
in the lemma below.

######  Lemma 4.

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be an SNN expressed in canonical form
with respect to a fundamental domain $\Omega_{n_{*}}\subset\Theta_{n_{*}}$.
Then $f$ is $G$-invariant if and only if there exists a unique signed perm-rep
$\rho:G\mapsto\mathrm{PZ}(n_{*})$ such that the canonical parameters of $f$
satisfy the following equations for all $g\in G$:

$\displaystyle\rho(g)W_{*}$ $\displaystyle=W_{*}g$ (3)
$\displaystyle\pi(g)a_{*}$ $\displaystyle=a_{*}$ (4)
$\displaystyle\rho(g)b_{*}$ $\displaystyle=b_{*}$ (5) $\displaystyle gc_{*}$
$\displaystyle=c_{*}+\frac{1}{2}(I-g)W_{*}^{\top}a_{*}.$ (6)

We see that the constraints on the canonical parameters of a $G$-SNN are not
necessarily unique, as they depend on a signed perm-rep $\rho$, whence the
classification program of $G$-SNNs in this paper. Lemma 4 thus establishes the
promised connection between $G$-SNNs and signed perm-reps. To formalize this
correspondence, let $\mathrm{SNN}(G)$ be the set of all $G$-SNNs and
$\mathcal{R}^{\mathrm{PZ}}(G)$ the set of all conjugacy classes of signed
perm-reps of $G$. Define the map
$F:\mathrm{SNN}(G)\mapsto\mathcal{R}^{\mathrm{PZ}}(G)$ such that if
$f\in\mathrm{SNN}(G)$ and $\rho$ is the corresponding signed perm-rep
appearing in Lemma 4, then $F(f)=\rho^{\mathrm{PZ}}$. Then $F$ is a well-
defined function in the sense that $F(f)$ does not depend on the choice of
fundamental domain $\Omega_{n_{*}}$. Indeed, a change of fundamental domain
$\Omega_{n_{*}}\rightarrow\Omega_{n_{*}}^{\prime}$ induces a transformation
$[W_{*}\mid b_{*}]\rightarrow A[W_{*}\mid b_{*}]$ for a unique
$A\in\mathrm{PZ}(n_{*})$. By Eq. 3, this in turn induces the conjugation
$\rho\rightarrow A\rho(\cdot)A^{-1}$, thereby leaving
$F(f)=\rho^{\mathrm{PZ}}$ invariant.

We now define a _$G$ -SNN architecture_ to be a subset
$S\subseteq\mathrm{SNN}(G)$ such that $S=F^{-1}(\rho^{\mathrm{PZ}})$ for some
$\rho^{\mathrm{PZ}}\in\operatorname{ran}(F)$; it consists of all $G$-SNNs that
are constrained to respect the same representation of $G$. In this language,
the purpose of this paper is to classify all $G$-SNN architectures.

A $G$-SNN $f$ is said to be _irreducible_ if $F(f)$ is a conjugacy class of
irreducible signed perm-reps. Let $f^{\mathrm{PZ}}$ denote the $G$-SNN
architecture containing the $G$-SNN $f$, and observe that if $f$ is
irreducible, then so are all $G$-SNNs in $f^{\mathrm{PZ}}$; in this case,
$f^{\mathrm{PZ}}$ is said to be an _irreducible architecture_.

It can be shown that every $G$-SNN admits a decomposition into a sum of
irreducible $G$-SNNs (Prop. 18 in Supp. B.2). It follows that to classify all
$G$-SNN architectures, it is enough to classify all irreducible $G$-SNN
architectures. This amounts to two tasks: (1) Classify all irreducible signed
perm-rep conjugacy classes in $\operatorname{ran}(F)$, and (2) for every
irreducible $\rho^{\mathrm{PZ}}\in\operatorname{ran}(F)$, give a
parameterization of all $G$-SNNs in the architecture
$F^{-1}(\rho^{\mathrm{PZ}})$.

####  3.3 The classification theorem

We now state our main theorem, but first we introduce some notation. If $A$ is
a linear operator (resp. set of linear operators), then let $P_{A}$ be the
orthogonal projection operator onto the vector subspace that is pointwise-
invariant under the action of $A$ (resp. all elements of $A$). Note that if
$A$ is a finite orthogonal group, then (Serre, 1977, sec. 2.6)

$P_{A}=\frac{1}{|A|}\sum_{a\in A}a.$

Let $\operatorname{st}_{G}(P_{A})$ denote the stabilizer subgroup

$\operatorname{st}_{G}(P_{A})=\\{g\in G:gP_{A}=P_{A}\\}.$

######  Theorem 5.

Let $\rho_{HK}$ be an irreducible signed perm-rep of $G$, and let
$\\{g_{1},\ldots,g_{n}\\}$ be a transversal of $G/H$ such that
$\rho_{HK}(g_{i})e_{1}=e_{i}$. Let $\tau=|H:K|-1$. Then:

  1. (a)

$\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$ if and only if
$\operatorname{st}_{G}(P_{K}\tau P_{H})=K$.

  2. (b)

If $\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$, then $f\in
F^{-1}(\rho_{HK}^{\mathrm{PZ}})$ if and only if the canonical parameters of
$f$ have the following forms:

$\displaystyle W_{*}$
$\displaystyle=\sum_{i=1}^{n}e_{i}(g_{i}w)^{\top},w\in\operatorname{ran}(P_{K}-\tau
P_{H}),\|w\|=1$ (7) $\displaystyle a_{*}$ $\displaystyle=a\vec{1},a\neq 0$ (8)
$\displaystyle b_{*}$ $\displaystyle=\tau b\vec{1},b\in\mathbb{R}$ (9)
$\displaystyle c_{*}$ $\displaystyle=-\frac{1}{2}\tau
W_{*}^{\top}a_{*}+c,c\in\operatorname{ran}(P_{G}).$ (10)

Combining this with the classification of irreducible signed perm-reps up to
conjugacy (Thm. 1), we obtain a complete classification of the irreducible
$G$-SNN architectures as an immediate corollary. Theorems 1&5 can be assembled
into an algorithm that enumerates all irreducible $G$-SNN architectures for
any given finite orthogonal group $G$. We implemented the enumeration
algorithm using a combination of GAP666GAP is a computer algebra system for
computational discrete algebra with particular emphasis on computational group
theory (GAP, ). and Python; our implementation currently supports, in
principle, all finite permutation groups $G<\mathcal{P}(m)$.777Code for our
implementation and for reproducing all results in this paper is available at:
https://github.com/dagrawa2/gsnn_classification_code.  Using our code
implementation, we enumerated all irreducible $G$-SNN architectures for one
permutation representation of every group $G$, $|G|\leq 8$, up to isomorphism.
We report the number of architectures, broken down by type, for each group in
Table 1 (see Supp. C.1; a discussion is included there as well).

We end this section with a proposition stating that architectures
corresponding to distinct cohomology classes in a given cohomology ring are in
a sense orthogonal, the implications of which we discuss in Sec. 4.

######  Proposition 6.

Let $w_{1}$ and $w_{2}$ be the first rows of the canonical weight matrices of
two irreducible $G$-SNN architectures $F^{-1}([\rho^{\mathrm{PZ}}_{HK_{1}}])$
and $F^{-1}([\rho^{\mathrm{PZ}}_{HK_{2}}])$ where $K_{1}\neq K_{2}$. Then
$w_{1}^{\top}w_{2}=0$.

###  4 Examples

####  4.1 The cyclic permutation group

Architecture 0.0

Architecture 1.0

Architecture 2.0

Architecture 3.0

Architecture 1.1

Architecture 3.1

Figure 1:  Constraint pattern of the weight matrix and illustration of the
cohomology class of each irreducible $G$-SNN architecture for the cyclic
permutation group $G=C_{6}$. The number of rows (resp. columns) in each
pattern is the number of hidden (resp. input) neurons in the architecture. In
each pattern, weights of the same color and texture (solid vs. hatched) are
constrained to be equal; weights of the same color but different texture are
constrained to be opposites (colors should not be compared across different
architectures). In each cohomology class illustration, the nodes represent the
hidden neurons of the architecture, and the arcs represent the action of the
generators of $G$ on the rows of the weight matrix (all arcs are the same
color because $C_{6}$ has only one generator). Solid (resp. dashed) arcs
preserve (resp. reverse) orientation. See Supp. C.2 for a richer example– the
dihedral permutation group $D_{6}$.

Consider the group $G=C_{6}$ of all cyclic permutations on the dimensions of
the input space $\mathbb{R}^{6}$.888See Supp. C for richer examples that could
not fit in the main paper. There are six irreducible $G$-SNN architectures for
$G=C_{6}$ (Fig. 1); “architecture i.j” refers to
$F^{-1}(\rho^{\mathrm{PZ}}_{H_{i}K_{j}})$ where $H_{0},\ldots,H_{3}$ are
isomorphic to $C_{1}$, $C_{2}$, $C_{3}$, and $C_{6}$ respectively and
$K_{j}\leq H_{i}$ such that $|H_{i}:K_{j}|=j+1$. Architectures i.0 are thus
exactly the type 1 ones, and two architectures i.j and i.k for distinct j and
k correspond to inequivalent cohomology classes in the same cohomology group.
Note that the architectures with $n$ hidden neurons correspond to $H_{i}\cong
C_{\frac{6}{n}}$.

The type 1 architectures i.0 correspond to ordinary perm reps of $G$. These
are the “obvious” architectures that practitioners probably could have
intuited. From Fig. 1, we see that the weight matrices of these architectures
are constrained to have a circulant structure; cycling the input neurons is
thus equivalent to cycling the hidden neurons, leaving the output invariant as
all weights in the second layer (not depicted) are constrained to be equal.
This circulant structure is also apparent in the cohomology class
illustrations. Note that $H_{i}$ is the stabilizer subgroup of each row of the
weight matrices.

Architectures i.1 are type 2 and are perhaps less obvious. Cycling the input
neurons is equivalent to cycling the hidden neurons only up to sign; if we
cycle a weight vector around all the hidden neurons, then we do not return to
the original weight vector but instead to its opposite. If we think of the
dashed arcs in the cohomology class illustrations as “half-twists” in a
cylindrical band, then Architectures i.1 correspond to a Möbius band, thereby
distinguishing them topologically from architectures i.0. Alternatively, in
terms of graph colorings, if the nodes incident to a solid (resp. dashed) arc
are constrained to have the same (resp. different) color(s), then
architectures i.1 are the only ones not $2$-colorable.

By Prop. 6, the first row of the weight matrix of architecture i.1 is
constrained to be orthogonal to that of architecture i.0; this is analogous to
the constraint that every continuous global section of a Möbius band must
vanish at some point. The upshot is that architectures i.0 and i.1 can
coincide in function space if and only if their weight matrices vanish– i.e.,
the architectures degenerate into linear functions. Since neural networks are
trained with local optimization, then we think it is unlikely that a $G$-SNN
being fit to a nonlinear dataset will degenerate to a linear function at any
point in its training; assuming this is true, architectures i.0 and i.1 are
effectively confined from one another due to their inequivalent topologies. We
discuss this phenomenon in more detail in Sec. 4.3.

####  4.2 The cyclic rotation group

|
---|---
Figure 2:  Contour plots of the two irreducible $G$-SNN architectures for the
2D orthogonal representation of $G=C_{6}$. The blue vectors are the weight
vectors– i.e., rows of the weight matrix $W_{*}$, and their offsets from the
origin in the type 1 architecture indicate the bias $b_{*}$. The red vector in
the type 2 architecture is the canonical parameter $c_{*}$ of the $G$-SNN. See
Supp. C.3 for a richer example– the dihedral rotation group $D_{6}$.

Consider again the group $G=C_{6}$, but this time a 2D orthogonal
representation where each group element acts as a rotation by a multiple of
$60^{\circ}$ on the 2D plane. There are only two irreducible $G$-SNN
architectures– one of each type. To visualize these architectures, we set
$w=[1,0]^{\top}$, $a=1$, $b=0.5$, $c=0$, and $d_{*}=0$ in Thm. 5 (b). Based on
their contour plots (Fig. 2), we find that the level curves of the type 1
(resp. type 2) architecture are concentric regular dodecagons (resp.
hexagons); both architectures are thus clearly invariant to
$60^{\circ}$-rotations.

In the type 2 architecture, the hexagonal level curves increase linearly with
radial distance. Since the bias is required to be zero (Eq. 9), a sharp
minimum forms at the origin. The architecture has three weight vectors and
thus three hidden neurons, and it additionally has a linear term (whose
gradient is shown in red in Fig. 2), which—when combined with weight vector 2
using Eq. 2—results in three weight vectors with $C_{3}$ symmetry. Observe
that if we cycle the three hidden neurons of the type 2 architecture , so that
each weight vector is rotated three times by $60^{\circ}$, then we obtain the
three weight vectors with reversed orientation; this is a manifestation of the
nontrivial topology of the type 2 architecture.

The type 1 architecture has six weight vectors and thus six hidden neurons.
Observe that for each weight vector, there is another that is its opposite.
Thus, for $[W_{*}\mid b_{*}]$ to have pairwise nonparallel rows (see Lemma 3),
the bias $b_{*}=b\vec{1}$ must be nonzero, whence the dodecahedral region in
the example $G$-SNN (Fig. 2) where its value plateaus to zero. However, in the
asymptotic limit $b\rightarrow 0$, the type 1 architecture degenerates to the
type 2 architecture but with twice the number of hidden neurons. Thus, even
though the two architectures are topologically distinct, the type 1
architecture can get arbitrarily close to the type 2 architecture in function
space (see Supp. C.3 for a richer example—the dihedral rotation group
$D_{6}$—which has irreducible architectures that cannot easily access one
another). This has important consequences, which we discuss more in the next
section.

####  4.3 Remarks

##### Numbers of hidden neurons

The type 1 and type 2 irreducible architectures for the $G=C_{6}$ rotation
group (Fig. 2) have six and three hidden neurons respectively. In addition,
the linear term $c_{*}x$ in the canonical form of a $G$-SNN—if not zero—can be
interpreted as two additional hidden neurons. It follows that a general
$G$-SNN that is a sum of copies of the two irreducible architectures cannot
have $3k+1$ hidden neurons for any integer $k$. Thus, if we fit a traditional
fully-connected SNN with $3k+1$ hidden neurons to a dataset invariant under
$60^{\circ}$-rotations, then the fit SNN can be a $G$-SNN if and only if one
or more of its hidden neurons are redundant– e.g., one hidden neuron is zeroed
out, or four hidden neurons sum to form a linear term, leaving
$(3k+1)-4=3(k-1)$ hidden neurons corresponding to “proper” weight vectors.
Although this is a rather simple example, it suggests the possibility of more
severe or complicated restrictions on numbers of hidden neurons for larger and
richer groups $G$. In these cases, the redundant hidden neurons could (1) make
it more difficult for the SNN to discover the symmetries in the dataset and
(2) make the SNN more prone to overfitting, all at the cost of additional
computation. We thus conjecture that one factor that determines the optimal
number of hidden neurons in traditional SNNs is whether the number admits a
$G$-SNN architecture, or—going further—how many different $G$-SNN
architectures the number admits.

##### Asymptotic inclusion

Let $f^{\mathrm{PZ}}_{i}=F^{-1}(\rho^{\mathrm{PZ}}_{i})$ for $i=1,2$ be two
$G$-SNN architectures. If for every $\varepsilon>0$ and $f_{2}\in
f_{2}^{\mathrm{PZ}}$, there exists $f_{1}\in f_{1}^{\mathrm{PZ}}$ such that
$\|f_{1}-f_{2}\|<\varepsilon$ (for some choice of functional norm), then we
say $f_{1}^{\mathrm{PZ}}$ is “asymptotically included” in
$f_{2}^{\mathrm{PZ}}$ and write $f_{1}^{\mathrm{PZ}}\hookrightarrow
f_{2}^{\mathrm{PZ}}$. In the cyclic rotation example in Sec. 4.2, as already
discussed there, the type 2 architecture is asymptoticly included in the type
1 architecture. In the cyclic permutation example in Sec. 4.1, the asymptotic
inclusions999These inclusions are “asymptotic” because no two rows of the
canonical parameter $[W_{*}\mid b_{*}]$ can be exactly antiparallel,
preventing the degeneration of one architecture into another.furnish a
$3$-partite topology on the space of irreducible architectures (Fig. 3). This
topology provides the necessary structure to perform neural architecture
search (NAS), where the inclusions serve as “network morphisms” (Wei et al.,
2016). In NAS, network morphisms are used to map underfitting architectures to
larger ones, after which training resumes; the upshot is that the larger
architecture need not be re-initialized, thereby significantly cutting
computation time. In future work, we will run NAS on the space of irreducible
$G$-SNN architectures to learn an optimal $G$-SNN in a greedy manner.

Figure 3:  Network morphisms between irreducible $G$-SNN architectures for the
cyclic permutation group $G=C_{6}$. Every direct path in black represents an
asymptotic inclusion. Red doubled-arrowed arcs represent the feasibility of
topological tunneling. See Supp. C.2 for a richer example– the dihedral
permutation group $D_{6}$.

##### Topological tunneling

Recall in the cyclic permutation example in Sec. 4.1, architectures i.0 and
i.1 correspond to distinct cohomology classes and coincide in function space
only when their weight matrices are zero. In the dihedral rotation group
example (see Supp. C.3)—a generalization of the cyclic rotation example in
Sec. 4.2—we observe another instance of this penomenon. We call this
“topological confinement”, and it implies that if, for example, we generate a
nontrivial dataset using architecture 1.1 for $G=C_{6}$ (Fig. 1) and if we
initialize a $G$-SNN with three hidden neurons and find that–purely by
chance–the initial parameters satisfy architecture 1.0 and not 1.1, then our
network will fail to fit to the dataset; upon a re-initialization, if this
time the initial parameters satisfy architecture 1.1., the network will
succeed. Rather than relying on random initializations and chance, or
resorting to a larger architecture such as 0.0, we propose to allow
“topological tunneling”, where the cohomology class of an architecture is
transformed by applying the appropriate orthogonal transformation to the top
weight vector (see Prop. 6). Topological tunneling thus introduces “shortcuts”
between certain points in architecture space, hopefully facilitating NAS (Fig.
3). We plan to test this in practice in future work.

###  5 Conclusion

We proved Thm. 5, which gives a classification of all (irreducible) $G$-SNN
architectures with ReLU activation for any finite orthogonal group $G$ acting
on the input space. The proof is based on a correspondence of every $G$-SNN to
a signed perm-rep of $G$ acting on the hidden neurons. Based on our code
implementation, we enumerated the irreducible $G$-SNN architectures for some
example groups and made a number of remarks, primarily on how the
architectures relate to one another in function space (Sec. 4.3). Perhaps most
interestingly, we found that architectures corresponding to inequivalent first
cohomology classes in a given cohomology ring of $G$ are practically
“confined” from one another in function space (Prop. 6).

Various next steps can be taken towards the ultimate goal of $G$-invariant
neural architecture design. On one hand, we could try to extend Thm. 5 to deep
architectures, which would require us to understand the redundancies of a deep
network; on the other, we could go ahead and investigate NAS on $G$-SNNs after
further developing the ideas of asymptotic inclusion and topological
tunneling. Alternatively, we could strengthen our intuition about the
condition in Thm. 5 (a) used to eliminate degenerate (i.e., linear) or
redundant architectures; indeed, due to this condition, and as exemplified by
the dihedral rotation group (Supp. C.3), the cohomology classes for which the
condition is satisfied need not even form a subgroup, and hence any patterns
in $G$-SNN architecture space are unclear. Finally, we could consider what are
“good” combinations of irreducible $G$-SNN architectures; e.g., which
sequences of irreducible architectures converge in sum to universal
$G$-invariant approximators fastest? Perhaps answers to these questions could
aid not just in $G$-invariant neural architecture design but could give hints
about the design problem in general.

### Acknowledgments and Disclosure of Funding

Devanshu Agrawal and James Ostrowski were supported by DOE grant DE-SC0018175.

### References

  * Arjevani and Field [2020] Yossi Arjevani and Michael Field.  Analytic characterization of the hessian in shallow relu models: A tale of symmetry.  _Advances in Neural Information Processing Systems_ , 33:5441–5452, 2020.
  * Baake [1984] Michael Baake.  Structure and representations of the hyperoctahedral group.  _Journal of mathematical physics_ , 25(11):3171–3182, 1984.
  * Bouc [2000] Serge Bouc.  Burnside rings.  In _Handbook of algebra_ , volume 2, pages 739–804. Elsevier, 2000\.
  * Brown [2012] Kenneth S Brown.  _Cohomology of groups_ , volume 87.  Springer Science & Business Media, 2012.
  * Burnside [1911] William Burnside.  _Theory of groups of finite order_.  The University Press, 1911.
  * Cohen and Welling [2016] Taco Cohen and Max Welling.  Group equivariant convolutional networks.  In _International conference on machine learning_ , pages 2990–2999. PMLR, 2016.
  * Cohen et al. [2019] Taco S Cohen, Mario Geiger, and Maurice Weiler.  A general theory of equivariant cnns on homogeneous spaces.  _Advances in neural information processing systems_ , 32, 2019.
  * Cybenko [1989] George Cybenko.  Approximations by superpositions of a sigmoidal function.  _Mathematics of Control, Signals and Systems_ , 2:183–192, 1989.
  * Druţu and Kapovich [2018] Cornelia Druţu and Michael Kapovich.  _Geometric group theory_ , volume 63.  American Mathematical Society, 2018.
  * Elsken et al. [2019] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al.  Neural architecture search: A survey.  _J. Mach. Learn. Res._ , 20(55):1–21, 2019.
  * [11] GAP.  GAP – Groups, Algorithms, and Programming, Version 4.11.1.  https://www.gap-system.org, 2021.
  * Herstein [2006] Israel N Herstein.  _Topics in algebra_.  John Wiley & Sons, 2006.
  * Kicki et al. [2020] Piotr Kicki, Mete Ozay, and Piotr Skrzypczyński.  A computationally efficient neural network invariant to the action of symmetry subgroups.  _arXiv preprint arXiv:2002.07528_ , 2020.
  * Kondor and Trivedi [2018] Risi Kondor and Shubhendu Trivedi.  On the generalization of equivariance and convolution in neural networks to the action of compact groups.  In _International Conference on Machine Learning_ , pages 2747–2755. PLMR, 2018.
  * Maron et al. [2019] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.  On the universality of invariant networks.  In _International conference on machine learning_ , pages 4363–4371. PMLR, 2019.
  * Negrinho and Martins [2014] Renato Negrinho and Andre Martins.  Orbit regularization.  _Advances in neural information processing systems_ , 27, 2014.
  * Ojha [2000] Piyush C Ojha.  Enumeration of linear threshold functions from the lattice of hyperplane intersections.  _IEEE Transactions on Neural Networks_ , 11(4):839–850, 2000.
  * Qi et al. [2017] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 652–660, 2017.
  * Ravanbakhsh [2020] Siamak Ravanbakhsh.  Universal equivariant multilayer perceptrons.  In _International Conference on Machine Learning_ , pages 7996–8006. PMLR, 2020.
  * Serre [1977] Jean-Pierre Serre.  _Linear representations of finite groups_ , volume 42.  Springer, 1977.
  * Tao [2012] Terence Tao.  Cayley graphs and the algebra of groups.  https://terrytao.wordpress.com/2012/05/11/cayley-graphs-and-the-algebra-of-groups/, 2012\.  Accessed: 2022-05-01.
  * Veeling et al. [2018] Bastiaan S Veeling, Jasper Linmans, Jim Winkens, Taco Cohen, and Max Welling.  Rotation equivariant cnns for digital pathology.  In _International Conference on Medical image computing and computer-assisted intervention_ , pages 210–218. Springer, 2018.
  * Wei et al. [2016] Tao Wei, Changhu Wang, Yong Rui, and Chang Wen Chen.  Network morphism.  In _International Conference on Machine Learning_ , pages 564–572. PMLR, 2016.

## Supplementary Material

###  Appendix A Signed permutation representations

####  A.1 Classification up to conjugacy

Let $\\{e_{1},\ldots,e_{n}\\}$ be the standard orthonormal basis set on
$\mathbb{R}^{n}$. For each $i=1,\ldots,n$, define $e_{-i}=-e_{i}$.

For every $B\in\mathcal{PZ}(n)$, let
$\psi_{B}:\mathcal{PZ}(n)\mapsto\mathcal{PZ}(n)$ be the inner automorphism
defined by $\psi_{B}(A)=B^{-1}AB$. Using this notation, two signed perm-reps
$\rho,\rho^{\prime}$ are conjugate if there exists $A\in\mathcal{PZ}(n)$ such
that $\rho^{\prime}=\psi_{A}\circ\rho$.

The following proposition states that the property of irreducibility is
invariant under conjugation, and it thus makes sense to speak of the
irreducibility of an entire conjugacy class $\rho^{\mathrm{PZ}}$.

######  Proposition 7.

Let $\rho$ be an irreducible signed perm-rep. Then every signed perm-rep
$\rho^{\prime}$ conjugate to $\rho$ is also irreducible.

###### Proof.

Let $A\in\mathcal{PZ}(n)$ such that $\rho^{\prime}(g)=A^{-1}\rho(g)A\forall
g\in G$. Note that for each $i=1,\ldots,n$, $Ae_{i}\in\\{e_{\pm
1},\ldots,e_{\pm n}\\}$. Thus, for every $i,j=1,\ldots,n$, there exists $g\in
G$ such that

$\displaystyle\rho(g)Ae_{i}$ $\displaystyle=\pm Ae_{j}$ $\displaystyle
A^{-1}\rho(g)Ae_{i}$ $\displaystyle=\pm e_{j}$
$\displaystyle\rho^{\prime}(g)e_{i}$ $\displaystyle=\pm e_{j}.$

∎

We next prove a fundamental lemma that establishes a correspondence between
irreducible signed perm-reps and the action of $G$ on certain coset spaces.
This is a generalization of the correspondence between ordinary permutation
representations and the action of $G$ on its coset spaces, which is often
formalized in terms of the so-called “Burnside ring” [Burnside, 1911, Bouc,
2000]. This lemma is also the basis for the type 1 vs. type 2 dichotomy of
irreducible signed perm-reps mentioned in Sec. 2.3.

We require two new definitions first. An _ordinary permutation representation_
(ordinary perm-rep) is a signed perm-rep $\rho$ such that
$\rho(g)\in\mathcal{P}(n)\forall g\in G$. A signed perm-rep $\rho$ is said to
be _transitive_ on a set $S\subseteq\mathbb{R}^{n}$ if for every $v,w\in S$,
there exists $g\in G$ such that $\rho(g)v=w$.

######  Lemma 8.

Let $\rho$ be an irreducible signed perm-rep. Define $K\leq H\leq G$ and
$U\in\mathcal{Z}(n)$, $U=\operatorname{diag}(u_{1},\ldots,u_{n})$, by

$\displaystyle H$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\}$
$\displaystyle K$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=e_{1}\\}$
$\displaystyle u_{i}$ $\displaystyle=\begin{cases}1,&\mbox{ if }\exists g\in
G\mid\rho(g)e_{1}=e_{i}\\\ -1,&\mbox{ otherwise.}\end{cases}$

Let $\\{g_{1},\ldots,g_{n}\\}$ be a transversal of $G/H$ such that
$U\rho(g_{i})Ue_{1}=e_{i}$. For each $i=1,\ldots,n$, define $g_{-i}=g_{i}h$
for some $h\in H\setminus K$ if $|H:K|=2$ and $h=1$ if $|H:K|=1$. Then:

  1. (a)

$|H:K|\leq 2$.

  2. (b)

If $|H:K|=1$, then $U\rho(g)Ue_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$. Moreover,
$g\rightarrow U\rho(g)U$ is an ordinary perm-rep and is transitive on
$\\{e_{1},\ldots,e_{n}\\}$.

  3. (c)

If $|H:K|=2$, then $\rho(g)e_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$. Moreover,
$U=I_{n}$ and $\rho$ is transitive on $\\{\pm e_{1},\ldots,\pm e_{n}\\}$.

###### Proof.

(a)  If there is no $h\in G$ such that $\rho(h)e_{1}=-e_{1}$, then $H=K$, and
hence $|H:K|=1$. On the other hand, suppose there exists $h\in G$ such that
$\rho(h)e_{1}=-e_{1}$. Then we have

$\displaystyle H$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\}$
$\displaystyle=\\{g\in G:\rho(g)e_{1}=e_{1}\\}\cup\\{g\in
G:\rho(g)e_{1}=-e_{1}\\}$ $\displaystyle=K\cup\\{g\in
G:\rho(h^{-1})\rho(g)e_{1}=-\rho(h^{-1})e_{1}\\}$ $\displaystyle=K\cup\\{g\in
G:\rho(h^{-1}g)e_{1}=e_{1}\\}$ $\displaystyle=K\cup hK,$

and hence $|H:K|=2$.

(b)  Suppose $|H:K|=1$. Let $i,j\in\\{\pm 1,\ldots,\pm n\\}$, and suppose
there exists $g\in G$ such that $U\rho(g)Ue_{i}=e_{j}$. We have

$\displaystyle U\rho(g)Ue_{i}$ $\displaystyle=e_{j}$ $\displaystyle
U\rho(g)UU\rho(g_{i})Ue_{1}$ $\displaystyle=U\rho(g_{j})Ue_{1}$
$\displaystyle\rho(g)\rho(g_{i})Ue_{1}$ $\displaystyle=\rho(g_{j})Ue_{1}$
$\displaystyle\rho(g_{j}^{-1}gg_{i})Ue_{1}$ $\displaystyle=e_{1}$
$\displaystyle g_{j}^{-1}gg_{i}$ $\displaystyle\in K$ $\displaystyle gg_{i}K$
$\displaystyle=g_{j}K.$

This sequence of inferences holds in reverse as well, thus establishing the
first part of the claim.

Since $|H:K|=1$, then $g_{-i}=g_{i}\forall i\in\\{1,\ldots,n\\}$, and hence
the above states that $g\rightarrow U\rho(g)U$ is equivalent to the action of
$G$ on $\\{g_{1}K,\ldots,g_{n}K\\}$, which is exactly the coset space $G/K$
since $K=H$. By the established equivalence, $g\rightarrow U\rho(g)U$ acts
transitively on $\\{e_{1},\ldots,e_{n}\\}$. That $g\rightarrow U\rho(g)U$ is
an ordinary perm-rep immediately follows from this transitivity.

(c)  Suppose $|H:K|=2$. By the same reasoning as in (b), we can establish that
$U\rho(g)Ue_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$. Since $|H:K|=2$, then clearly
$G/K=\\{g_{\pm 1}K,\ldots,g_{\pm n}K\\}$. We thus have that $g\rightarrow
U\rho(g)U$ is equivalent to the action of $G$ on $G/K$. By this equivalence,
$g\rightarrow U\rho(g)U$ acts transitively on $\\{\pm e_{1},\ldots,\pm
e_{n}\\}$. That $U=I_{n}$ immediately follows from this transitivity, and this
in turn implies that $\rho(g)e_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$ and that $\rho$
acts transitively on $\\{\pm e_{1},\ldots,\pm e_{n}\\}$. ∎

######  Remark 9.

In Lemma 8, the irreducibility of the signed perm-rep $\rho$ is necessary to
guarantee the existence of $g_{i}\in G$ such that $U\rho(g_{i})Ue_{1}=e_{i}$
for each $i=1,\ldots,n$.

######  Remark 10.

In Lemma 8, the signed perm-rep $\rho$ is said to be of _type 1_ (resp. _type
2_) if $|H:K|=1$ (resp. $|H:K|=2$).

We now prove Thm. 1.

###### Proof of Thm. 1.

(a)  Recall by definition of $\mathcal{C}^{G}_{\leq 2}$, either $|H:K|=1$ or
$|H:K|=2$. Let $i,j\in\\{1,\ldots,n\\}$. Since $G$ acts transitively on $G/H$,
then there exists $g\in G$ such that $gg_{i}H=g_{j}H$. If $|H:K|=1$, then this
is equivalently $gg_{i}K=g_{j}K$ so that $\rho_{HK}(g)e_{i}=e_{j}$; the rep
$\rho_{HK}$ is thus irreducible. If instead $|H:K|=2$, then we have either
$gg_{i}K=g_{j}K$ or $gg_{i}K=g_{j}hK=g_{-j}K$, so that
$\rho_{HK}(g)e_{i}=e_{\pm j}=\pm e_{j}$; the rep $\rho_{HK}$ is still
irreducible.

(b)  Let $\rho^{\prime}$ be an irreducible signed perm-rep. We handle type 1
and type 2 as separate cases.

(Case 1)  Suppose $\rho^{\prime}$ is type 1. Then by Lemma 8 (b),
$\rho^{\prime}$ is conjugate to an ordinary perm-rep. We can therefore assume,
without loss of generality, that $\rho^{\prime}$ is an ordinary perm-rep and
thus corresponds to the action of $G$ on $G/H^{\prime}$ for some
$H^{\prime}\leq G$. Let $(H,H)^{G}\in\mathcal{C}^{G}_{\leq 2}$ be the unique
conjugacy class such that $H$ is conjugate to $H^{\prime}$. Note that
$\rho_{HH}$ is also an ordinary perm-rep and is clearly conjugate to
$\rho^{\prime}$, thus completing the proof for the type 1 case.

(Case 2)  Suppose $\rho^{\prime}$ is type 2, and define

$\displaystyle H^{\prime}$ $\displaystyle=\\{g\in G:\rho^{\prime}(g)e_{1}=\pm
e_{1}\\}$ $\displaystyle K^{\prime}$ $\displaystyle=\\{g\in
G:\rho^{\prime}(g)e_{1}=e_{1}\\}$ $\displaystyle g^{\prime}_{i}K^{\prime}$
$\displaystyle=\\{g\in G:\rho^{\prime}(g)e_{1}=e_{i}\\}\forall i=1,\ldots,n.$

Then there exists a unique $(H,K)^{G}\in\mathcal{C}^{G}_{\leq 2}$ and
$g_{*}\in G$ such that

$\displaystyle H^{\prime}$ $\displaystyle=g_{*}Hg_{*}^{-1}$ $\displaystyle
K^{\prime}$ $\displaystyle=g_{*}Kg_{*}^{-1}.$

Note that since $\rho^{\prime}$ is type 2, then
$|H:K|=|H^{\prime}:K^{\prime}|=2$; thus, $G/K=\\{g_{\pm 1}K,\ldots,g_{\pm
n}K\\}$. Define $\sigma:G\mapsto\\{g_{\pm 1},\ldots,g_{\pm n}\\}$ such that
$g\in\sigma(g)K$, and define a permutation $\pi$ on $\\{\pm 1,\ldots,\pm n\\}$
such that

$g_{\pi(i)}=\sigma(g^{\prime}_{i}g_{*}).$

Let $A\in\mathcal{PZ}(n)$ such that $Ae_{i}=e_{\pi(i)}$ for each $i$. Then we
claim $\rho^{\prime}=\psi_{A}\circ\rho_{HK}$. For any $g\in G$ and $i\in\\{\pm
1,\ldots,\pm n\\}$, let $j\in\\{\pm 1,\ldots,\pm n\\}$ such that
$\rho^{\prime}(g)e_{i}=e_{j}$. Using Lemma 8 (c), we have

$\displaystyle\rho^{\prime}(g)e_{i}$ $\displaystyle=e_{j}$ $\displaystyle
gg^{\prime}_{i}K^{\prime}$ $\displaystyle=g^{\prime}_{j}K^{\prime}$
$\displaystyle gg^{\prime}_{i}g_{*}Kg_{*}^{-1}$
$\displaystyle=g^{\prime}_{j}g_{*}Kg_{*}^{-1}$ $\displaystyle
gg^{\prime}_{i}g_{*}K$ $\displaystyle=g^{\prime}_{j}g_{*}K$ $\displaystyle
g\sigma(g^{\prime}_{i}g_{*})K$ $\displaystyle=\sigma(g^{\prime}_{j}g_{*})K$
$\displaystyle gg_{\pi(i)}K$ $\displaystyle=g_{\pi(j)}K$
$\displaystyle\rho_{HK}(g)e_{\pi(i)}$ $\displaystyle=e_{\pi(j)}$
$\displaystyle\rho_{HK}(g)Ae_{i}$ $\displaystyle=Ae_{j}$ $\displaystyle
A^{-1}\rho_{HK}(g)Ae_{i}$ $\displaystyle=e_{j}$
$\displaystyle(\psi_{A}\circ\rho_{HK})(g)e_{i}$ $\displaystyle=e_{j}.$

This sequence of inferences holds in the reverse direction as well, and hence
$\rho^{\prime}=\psi_{A}\circ\rho_{HK}$ as claimed. ∎

######  Remark 11.

The transversal $\\{g_{1},\ldots,g_{n}\\}$ of $G/H$ used in the definition of
$\rho_{HK}$ can be recovered from the latter up to $K$. Let
$\\{g^{\prime}_{1},\ldots,g^{\prime}_{n}\\}$ be another transversal of $G/H$
such that $\rho_{HK}(g^{\prime}_{i})e_{1}=e_{i}$. By definition of
$\rho_{HK}$, $g^{\prime}_{i}g_{1}K=g_{i}K$. Since $g_{1}\in K$, then
$g^{\prime}_{i}K=g_{i}K$.

####  A.2 Some useful properties

For every $z\in\\{-1,1\\}^{n}$, define the signed perm-rep

$\rho_{HK;z}(g)=\operatorname{diag}(z)\rho_{HK}(g)\operatorname{diag}(z)\forall
g\in G.$

The following proposition and subsequent corollary list some useful properties
of the $\rho_{HK;z}$. Note that $\rho_{HK}=\rho_{HK;z}$ with $z=\vec{1}$, and
hence the statements below hold in particular for the $\rho_{HK}$ as well.

######  Proposition 12.

Let $\rho=\rho_{HK;z}\in\mathcal{R}(G)$ be an irreducible signed perm-rep. Let
$Z=\operatorname{diag}(z)$. Then the following statements are true:

  1. (a)

The subgroups $H$ and $K$ satisfy

$\displaystyle H$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\}$
$\displaystyle K$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=e_{1}\\},$

and $\rho$ is of type $|H:K|$.

  2. (b)

If $\rho$ is type 1 ($|H:K|=1$), then $\rho_{HK}(g)=Z\rho(g)Z$ is an ordinary
perm-rep that acts transitively on $\\{e_{1},\ldots,e_{n}\\}$.

  3. (c)

If $\rho$ is type 2 ($|H:K|=2$), then $\rho$ acts transitively on $\\{\pm
e_{1},\ldots,\pm e_{n}\\}$.

###### Proof.

(a)  Define the subgroups

$\displaystyle H^{\prime}$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\}$
$\displaystyle K^{\prime}$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=e_{1}\\}.$

We then have

$\displaystyle H^{\prime}$ $\displaystyle=\\{g\in G:Z\rho_{HK}(g)Ze_{1}=\pm
e_{1}\\}$ $\displaystyle=\\{g\in G:\rho_{HK}(g)Ze_{1}=\pm Ze_{1}\\}$
$\displaystyle=\\{g\in G:\rho_{HK}(g)z_{1}e_{1}=\pm z_{1}e_{1}\\}$
$\displaystyle=\\{g\in G:\rho_{HK}(g)e_{1}=\pm e_{1}\\}.$

By definition of $\rho_{HK}$ in Thm. 1, we have

$\displaystyle H^{\prime}$ $\displaystyle=\\{g\in G:gg_{1}K=g_{\pm 1}K\\}$
$\displaystyle=\\{g\in G:gK=K\mbox{ or }gK=hK\\}$ $\displaystyle=K\cup hK$
$\displaystyle=H.$

We can similarly show that $K^{\prime}=K$. By definition of type in Remark 10,
$\rho$ is of type $|H^{\prime}:K^{\prime}|=|H:K|$.

(b)  Suppose $\rho$ is type 1 so that $|H:K|=1$ and hence $H=K$. Then
$\rho_{HK}(g)e_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$, where
$\\{g_{1},\ldots,g_{n}\\}$ is the transversal of $G/H$ used in the definition
of $\rho_{HK}$ in Thm. 1. Since $H=K$, however, $\\{g_{1},\ldots,g_{n}\\}$ is
equivalently a transversal of $G/K$, and hence we see that the action of
$\rho_{HK}$ is equivalent to the action of $G$ on $G/K$. As in the proof of
Lemma 8 (b), this implies the claim.

(c)  Suppose $\rho$ is type 2. Then the claim immediately follows by Lemma 8
(c). ∎

The following corollary results from the combination of Lemma 8 and Prop. 12.

######  Corollary 13.

Let $\rho$ be an irreducible signed perm-rep. Define $K\leq H\leq G$ and
$z\in\\{-1,1\\}^{n}$ by

$\displaystyle H$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\}$
$\displaystyle K$ $\displaystyle=\\{g\in G:\rho(g)e_{1}=e_{1}\\}$
$\displaystyle z_{i}$ $\displaystyle=\begin{cases}1,&\mbox{ if }\exists g\in
G\mid\rho(g)e_{1}=e_{i}\\\ -1,&\mbox{ otherwise.}\end{cases}$

Then $\rho=\rho_{HK;z}$. Moreover, if $\rho$ is type 2 ($|H:K|=2$), then
$z=\vec{1}$ so that $\rho=\rho_{HK}$.

###### Proof.

If $\rho$ is type 2, then by Lemma 8 (c), $\rho$ is transitive on $\\{\pm
e_{1},\ldots,\pm e_{n}\\}$ so that $z_{i}=1$ for each $i=1,\ldots,n$. Now let
$\rho_{z}(g)=\operatorname{diag}(z)\rho(g)\operatorname{diag}(z)\forall g\in
G$. Then again by Lemma 8, $\rho_{z}(g)e_{i}=e_{j}$ iff $gg_{i}K=g_{j}K$;
however, recalling Thm. 1, this is identical to the definition of $\rho_{HK}$.
Hence, $\rho_{z}=\rho_{HK}$, or equivalently $\rho=\rho_{HK;z}$. ∎

####  A.3 Group cohomology

Recall the definitions of $\pi_{H}$ and $\zeta^{\mathrm{L}}_{HK}$ from Sec.
2.3. The following proposition justifies the notation $\pi_{H}$; i.e.,
$\pi_{H}$ does not depend on the choice of $K$ and $z$.

######  Proposition 14.

Let $\rho_{HK}\in\mathcal{R}(G)$, and let $\pi_{HK}:G\mapsto\mathcal{P}(n)$
and $\zeta_{HK}:G\mapsto\mathcal{Z}(n)$ be the unique functions satisfying
$\rho_{HK}(g)=\pi_{HK}(g)\zeta_{HK}(g)\forall g\in G$. Then $\pi_{HK}$ is
independent of $K$.

###### Proof.

As in Remark 11, let $\\{g_{1},\ldots,g_{n}\\}$ be a transversal of $G/H$ such
that $\rho_{HK}(g_{i})e_{1}=e_{i}$ for $i=1,\ldots,n$. In general, $g_{1}\in
K$; however, without loss of generality, assume $g_{1}=1$ so that it is
independent of $K$. If $g\in G$ and $i,j\in\\{\pm 1,\ldots,\pm n\\}$ such that
$\rho_{HK}(g)e_{i}=e_{j}$, then define $\pi_{HK}$ and $\zeta_{HK}$ such that

$\displaystyle\pi_{HK}(g)e_{i}$ $\displaystyle=e_{|j|}$
$\displaystyle\zeta_{HK}(g)e_{i}$ $\displaystyle=\operatorname{sign}(j).$

It is then easy to verify that $\rho_{HK}(g)=\pi_{HK}(g)\zeta_{HK}(g)\forall
g\in G$; hence by uniqueness, these are the correct definitions of $\pi_{HK}$
and $\zeta_{HK}$. By these definitions, for $g\in G$ and
$i,j\in\\{1,\ldots,n\\}$, $\pi_{HK}(g)e_{i}=e_{j}$ iff $gg_{i}K=g_{\pm j}K$,
which in turn holds iff $gg_{i}H=g_{j}H$. This reveals that $\pi_{HK}$ does
not depend on $K$ but only $H$. ∎

We now prove Prop. 2.

###### Proof of Prop. 2.

(a)  We first show that every $\hat{\zeta^{\mathrm{L}}}_{HK}$ is a $1$-cocycle
by verifying the cocycle condition. For $g_{1},g_{2}\in G$, we have

$\displaystyle\zeta^{\mathrm{L}}_{HK}(g_{1}g_{2})\pi_{H}(g_{1}g_{2})$
$\displaystyle=\rho_{HK}(g_{1}g_{2})$
$\displaystyle=\rho_{HK}(g_{1})\rho_{HK}(g_{2})$
$\displaystyle=\zeta^{\mathrm{L}}_{HK}(g_{1})\pi_{H}(g_{1})\zeta^{\mathrm{L}}_{HK}(g_{2})\pi_{H}(g_{2})$
$\displaystyle=\zeta^{\mathrm{L}}_{HK}(g_{1})\pi_{H}(g_{1})\zeta^{\mathrm{L}}_{HK}(g_{2})\pi_{H}(g_{1})^{\top}\pi_{H}(g_{1})\pi_{H}(g_{2}).$

Equating the factors contained in $\mathcal{Z}(n)$, we have

$\zeta^{\mathrm{L}}_{HK}(g_{1}g_{2})=\zeta^{\mathrm{L}}_{HK}(g_{1})\pi_{H}(g_{1})\zeta^{\mathrm{L}}_{HK}(g_{2})\pi_{H}(g_{1})^{\top}.$

Writing this in terms of vectors in $M_{H}$, we obtain the $1$-cocycle
condition:

$\hat{\zeta^{\mathrm{L}}}_{HK}(g_{1}g_{2})=\hat{\zeta^{\mathrm{L}}}_{HK}(g_{1})+\pi_{H}(g_{1})\hat{\zeta^{\mathrm{L}}}_{HK}(g_{2}),$

and hence $\hat{\zeta^{\mathrm{L}}}_{HK}$ is a $1$-cocycle.

Next, before proving the main claim, we characterize all cocycles cohomologous
to $\hat{\zeta^{\mathrm{L}}}_{HK}$. For every $z\in\\{-1,1\\}^{n}$, define the
signed perm-rep
$\rho_{HK;z}(g)=\operatorname{diag}(z)\rho_{HK}(g)\operatorname{diag}(z)\forall
g\in G$, and let $\pi_{H;z}:G\mapsto\mathcal{P}(n)$ and
$\zeta^{\mathrm{L}}_{HK;z}:G\mapsto\mathcal{Z}(n)$ be the unique functions
satisfying $\rho_{HK;z}(g)=\zeta^{\mathrm{L}}_{HK;z}(g)\pi_{H;z}(g)\forall
g\in G$. We have for all $g\in G$,

$\displaystyle\rho_{HK;z}(g)$
$\displaystyle=\operatorname{diag}(z)\rho_{HK}(g)\operatorname{diag}(z)$
$\displaystyle\zeta^{\mathrm{L}}_{HK;z}(g)\pi_{H;z}(g)$
$\displaystyle=\operatorname{diag}(z)\zeta^{\mathrm{L}}_{HK}(g)\pi_{H}(g)\operatorname{diag}(z)$
$\displaystyle=\operatorname{diag}(z)\zeta^{\mathrm{L}}_{HK}(g)\pi_{H}(g)\operatorname{diag}(z)\pi_{H}(g)^{\top}\pi_{H}(g).$

Equating factors in $\mathcal{P}(n)$ and equating factors in $\mathcal{Z}(n)$,
we obtain

$\displaystyle\pi_{H;z}(g)$ $\displaystyle=\pi_{H}(g)$
$\displaystyle\zeta^{\mathrm{L}}_{HK;z}(g)$
$\displaystyle=\operatorname{diag}(z)\zeta^{\mathrm{L}}_{HK}(g)\pi_{H}(g)\operatorname{diag}(z)\pi_{H}(g)^{\top}.$

The first of these equations tells us that $\pi_{H;z}$ is independent of $z$,
and we will thus omit the subscript $z$ in $\pi_{H;z}$ henceforth. Writing the
second of these equations in terms of vectors in $M_{H}$, we have

$\displaystyle\hat{\zeta^{\mathrm{L}}}_{HK;z}(g)$
$\displaystyle=\hat{z}+\hat{\zeta^{\mathrm{L}}}_{HK}(g)+\pi_{H}(g)\hat{z}$
$\displaystyle=(\pi_{H}(g)\hat{z}-\hat{z})+\hat{\zeta^{\mathrm{L}}}_{HK}(g),$

where we used the fact that $\hat{z}=-\hat{z}$ over $\mathbb{F}_{2}$. Since
$g\rightarrow\pi(g)\hat{z}-\hat{z}$ is a coboundary, then
$\hat{\zeta^{\mathrm{L}}}_{HK;z}$ is cohomologous to
$\hat{\zeta^{\mathrm{L}}}_{HK}$; from the above, the converse is also easily
verified.

We thus have

$[\hat{\zeta^{\mathrm{L}}}_{HK}]=\\{\hat{\zeta^{\mathrm{L}}}_{HK;z}:z\in\\{-1,1\\}^{n}\\},$

where distinct $z$ do not necessarily imply distinct
$\hat{\zeta^{\mathrm{L}}}_{HK;z}$.

We now prove the main claim. We first prove that the cohomology classes
$[\hat{\zeta^{\mathrm{L}}}_{HK}]$ enumerated over all $K\leq H\mid|H:K|\leq 2$
are distinct. Suppose
$[\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]=[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]$;
i.e., $\hat{\zeta^{\mathrm{L}}}_{HK_{1}}$ and
$\hat{\zeta^{\mathrm{L}}}_{HK_{2}}$ are cohomologous. We will show
$K_{1}=K_{2}$. By the above, there exists $z\in\\{-1,1\\}^{n}$ such that
$\hat{\zeta^{\mathrm{L}}}_{HK_{2}}=\hat{\zeta^{\mathrm{L}}}_{HK_{1};z}$;
Converting this back in terms of diagonal matrices and multiplying the
resulting equation from the right by $\pi_{H}$, we obtain
$\rho_{HK_{2}}=\rho_{HK_{1};z}$. By definition of $\rho_{HK_{2}}$, we have

$\\{g\in G:\rho_{HK_{2}}(g)e_{1}=e_{1}\\}=K_{2}.$

On the other hand,

$\displaystyle\\{g\in G:\rho_{HK_{2}}(g)e_{1}=e_{1}\\}$ $\displaystyle=\\{g\in
G:\rho_{HK_{1};z}(g)e_{1}=e_{1}\\}$ $\displaystyle=\\{g\in
G:\operatorname{diag}(z)\rho_{HK_{1}}(g)\operatorname{diag}(z)e_{1}=e_{1}\\}$
$\displaystyle=\\{g\in
G:\rho_{HK_{1}}(g)\operatorname{diag}(z)e_{1}=\operatorname{diag}(z)e_{1}\\}$
$\displaystyle=\\{g\in G:\rho_{HK_{1}}(g)z_{1}e_{1}=z_{1}e_{1}\\}$
$\displaystyle=\\{g\in G:\rho_{HK_{1}}(g)e_{1}=e_{1}\\}$
$\displaystyle=K_{1}.$

Ergo, $K_{1}=K_{2}$.

We next prove that every $1$-cocycle is contained in one of the cohomology
classes $[\hat{\zeta^{\mathrm{L}}}_{HK}]$. Let
$\hat{\zeta^{\mathrm{L}}}:G\mapsto M_{H}$ be a $1$-cocycle. Then
$\rho(g)=\zeta^{\mathrm{L}}(g)\pi_{H}(g)\forall g\in G$ defines an irreducible
signed perm rep. It is easy to verify that

$H=\\{g\in G:\rho(g)e_{1}=\pm e_{1}\\},$

and define

$K=\\{g\in G:\rho(g)e_{1}=e_{1}\\}.$

Then by Cor. 13, $\rho=\rho_{HK;z}$ for some $z\in\\{-1,1\\}^{n}$, and hence
$\hat{\zeta^{\mathrm{L}}}=\hat{\zeta^{\mathrm{L}}}_{HK;z}$ so that
$\hat{\zeta^{\mathrm{L}}}\in[\hat{\zeta^{\mathrm{L}}}_{HK}$.

All that is left for (a) is to prove the claimed identity for the addition
operation. First, however, given a cocycle $\hat{\zeta^{\mathrm{L}}}_{HK;z}$,
note that by Prop. 12 (a), we have

$\displaystyle K$ $\displaystyle=\\{g\in G:\rho_{HK;z}(g)e_{1}=e_{1}\\}$
$\displaystyle=\\{g\in G:\zeta^{\mathrm{L}}_{HK;z}(g)\pi_{H}(g)e_{1}=e_{1}\\}$
$\displaystyle=\\{g\in H:\zeta^{\mathrm{L}}_{HK;z}(g)e_{1}=e_{1}\\}$
$\displaystyle=\\{g\in H:\zeta^{\mathrm{L}}_{HK;z}(g)_{11}=1\\}$
$\displaystyle=\\{g\in H:\hat{\zeta^{\mathrm{L}}}_{HK;z}(g)_{1}=0\\}.$

Now consider the sum of two cohomology classes
$[\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]$ and
$[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]$. Since we have established all elements
of the cohomology group, then we know that there exists $K\leq H\mid|H:K|\leq
2$ such that

$[\hat{\zeta^{\mathrm{L}}}_{HK}]=[\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]+[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}].$

Thus, there exists $z\in\\{-1,1\\}^{n}$ such that

$\hat{\zeta^{\mathrm{L}}}_{HK;z}=\hat{\zeta^{\mathrm{L}}}_{HK_{1}}+\hat{\zeta^{\mathrm{L}}}_{HK_{2}}.$

Now by the above, we have

$\displaystyle K$ $\displaystyle=\\{g\in
H:\hat{\zeta^{\mathrm{L}}}_{HK;z}(g)_{1}=0\\}$ $\displaystyle=\\{g\in
H:\hat{\zeta^{\mathrm{L}}}_{HK_{1}}(g)_{1}+\hat{\zeta^{\mathrm{L}}}_{HK_{2}}(g)_{1}=0\\}$
$\displaystyle=\\{g\in
H:\hat{\zeta^{\mathrm{L}}}_{HK_{1}}(g)_{1}=\hat{\zeta^{\mathrm{L}}}_{HK_{2}}(g)_{1}=0\\}\cup\\{g\in
H:\hat{\zeta^{\mathrm{L}}}_{HK_{1}}(g)_{1}=\hat{\zeta^{\mathrm{L}}}_{HK_{2}}(g)_{1}=1\\}$
$\displaystyle=K_{1}\cap K_{2}\cup((H\setminus K_{1})\cap(H\setminus K_{2})),$

thereby establishing the claim.

(b)  Let $[\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]$ and
$[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]$ be two cohomology classes. We must show
$(H,K_{1})$ is conjugate to $(H,K_{2})$ if and only if there exists
$P\in\mathcal{P}(n)$ such that $[P,\pi(g)]=0\forall g\in G$ and
$[P\hat{\zeta^{\mathrm{L}}}_{HK_{1}}]=[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]$.
Suppose $(H,K_{1})$ and $(H,K_{2})$ are conjugate. Then by Thm. 1,
$\rho_{HK_{1}}$ and $\rho_{HK_{2}}$ are conjugate, so that there exist
$P\in\mathcal{P}(n)$ and $Z\in\mathcal{Z}(n)$, $Z=\operatorname{diag}(z)$,
such that for all $g\in G$,

$\displaystyle\rho_{HK_{2}}(g)$ $\displaystyle=ZP\rho_{HK_{1}}(g)(ZP)^{-1}$
$\displaystyle\rho_{HK_{2}}(g)$ $\displaystyle=ZP\rho_{HK_{1}}(g)P^{\top}Z$
$\displaystyle\rho_{HK_{2};z}(g)$ $\displaystyle=P\rho_{HK_{1}}(g)P^{\top}$
$\displaystyle\zeta^{\mathrm{L}}_{HK_{2};z}(g)\pi_{H}(g)$
$\displaystyle=P\zeta^{\mathrm{L}}_{HK_{1}}(g)\pi_{H}(g)P^{\top}$
$\displaystyle\zeta^{\mathrm{L}}_{HK_{2};z}(g)\pi_{H}(g)$
$\displaystyle=P\zeta^{\mathrm{L}}_{HK_{1}}(g)P^{\top}P\pi_{H}(g)P^{\top}.$

Equating the factors in $\mathcal{P}(n)$ and the factors in $\mathcal{Z}(n)$,
we obtain

$\displaystyle\pi_{H}(g)$ $\displaystyle=P\pi_{H}(g)P^{\top}$
$\displaystyle\zeta^{\mathrm{L}}_{HK_{2};z}(g)$
$\displaystyle=P\zeta^{\mathrm{L}}_{HK_{1}}(g)P^{\top}.$

The first of these equations establishes the commutation $[P,\pi(g)]=0$. The
second equation implies

$\displaystyle\hat{\zeta^{\mathrm{L}}}_{HK_{2};z}(g)$
$\displaystyle=P\hat{\zeta^{\mathrm{L}}}_{HK_{1}}(g)$
$\displaystyle[\hat{\zeta^{\mathrm{L}}}_{HK_{2}}]$
$\displaystyle=[P\hat{\zeta^{\mathrm{L}}}_{HK_{1}}].$

The above steps can be reversed to prove the converse.

(c)  For every $K\leq H\mid|H:K|\leq 2$, observe that

$K\cap H\cup((H\setminus K)\cap(H\setminus H))=K.$

By (a), $[\hat{\zeta^{\mathrm{L}}}_{HK}]$, $H=K$, is thus the zero cohomology
class. Therefore, $\rho_{HK;z}$ is type 1 ($|H:K|=1$, or $H=K$) if and only if
$[\hat{\zeta^{\mathrm{L}}}_{HK}]$ is the zero cohomology class. ∎

###  Appendix B Classification of $G$-SNNs

####  B.1 Canonical parameterization

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be a continuous piecewise-affine
function. An _affine region_ $X\subseteq\mathbb{R}^{m}$ of $f$ is a maximal
polytope over which $f$ is affine.

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be an SNN of the form in Eq. 1, and
note that $f$ is a continuous piecewise-affine function. Then the _signature_
$r$ of an affine region $X\subseteq\mathbb{R}^{m}$ is the binary vector
$r=H(Wx+b)$, for any arbitrary choice of $x\in X$ and where $H$ is the
Heaviside step function (where we set $H(0)=0$).

The following small proposition establishes the identity given in Eq. 2.

######  Proposition 15.

For all $x\in\mathbb{R}$ and $z\in\\{-1,1\\}$,

$\operatorname{ReLU}(x)-\operatorname{ReLU}(zx)=H(-z)x.$

###### Proof.

It is easy to verify that $\operatorname{ReLU}(x)-\operatorname{ReLU}(-x)=x$
for all $x$. Now we have two cases:

Case 1 ($z=-1$)  We have

$\displaystyle\operatorname{ReLU}(x)-\operatorname{ReLU}(zx)$
$\displaystyle=\operatorname{ReLU}(x)-\operatorname{ReLU}(-x)$
$\displaystyle=x$ $\displaystyle=H[-(-1)]x$ $\displaystyle=H(-z)x.$

Case 2 ($z=1$)  We have

$\displaystyle\operatorname{ReLU}(x)-\operatorname{ReLU}(zx)$
$\displaystyle\operatorname{ReLU}(x)-\operatorname{ReLU}(x)$ $\displaystyle=0$
$\displaystyle=H(-1)x$ $\displaystyle=H(-z)x.$

∎

We now prove Lemma 3.

###### Proof of Lemma 3.

Given access to the data $D=\\{(x,f(x)):x\in\mathbb{R}^{m}\\}$, we will show
that we can in principle determine $[W_{*}\mid b_{*}],a_{*},c_{*},d_{*}$
uniquely. Since $f$ admits the form in Eq. 1, the set of points at which $f$
is not differentiable is a union of $n_{*}$ distinct affine spaces each of
dimension $m-1$, for a unique $n_{*}\leq n$. From the data $D$, we can in
principle determine the equation of each affine space; let
$w_{*i}^{\top}x+b_{*i}=0$ be the equation defining the $i$th affine space,
where $\|w_{*i}\|=1$. Let $W_{*}\in\mathbb{R}^{n_{*}\times m}$ with $i$th row
$w_{*i}^{\top}$ and $b_{*}\in\mathbb{R}^{n_{*}}$ with elements $b_{*i}$. Note
that no two rows of $[W_{*}\mid b_{*}]$ are parallel, as parallel rows would
correspond to the same affine space. Thus, $[W_{*}\mid
b_{*}]\in\Theta_{n_{*}}$. Note that the action of any element in
$\mathrm{PZ}(n_{*})$ on $[W_{*}\mid b_{*}]$ leaves the corresponding set of
affine spaces invariant; we thus assume, without loss of generality, that
$[W_{*}\mid b_{*}]\in\Omega_{n_{*}}$, thereby establishing the uniqueness of
$[W_{*}\mid b_{*}]$. The function $f$ now admits the form

$f(x)=a_{*}^{\top}\operatorname{ReLU}[Z(W_{*}x+b_{*})]+\tilde{f}(x),$

for some $a_{*}\in\mathbb{R}^{n_{*}}$, $Z\in\mathcal{Z}(n_{*})$, and some
differentiable piecewise affine function
$\tilde{f}(x):\mathbb{R}^{m}\mapsto\mathbb{R}$. Note that $a_{*i}\neq 0$ for
each $i=1,\ldots,n_{*}$; otherwise, we could simply delete the $i$th row of
$[W_{*}\mid b_{*}]$. Since $\tilde{f}$ is both piecewise-affine and
differentiable, then it is necessarily affine; hence there exist
$\tilde{c}_{*}\in\mathbb{R}^{m}$ and $\tilde{d}_{*}\in\mathbb{R}$ such that
$\tilde{f}(x)=\tilde{c}_{*}^{\top}x+\tilde{d}_{*}$ and thus

$f(x)=a_{*}^{\top}\operatorname{ReLU}[Z(W_{*}x+b_{*})]+\tilde{c}_{*}^{\top}x+\tilde{d}_{*}.$

Now applying Prop. 15, we have

$\displaystyle f(x)$
$\displaystyle=a_{*}^{\top}\operatorname{ReLU}(W_{*}x+b_{*})-a_{*}^{\top}H(-Z)(W_{*}x+b_{*})+\tilde{c}_{*}x+\tilde{d}_{*}$
$\displaystyle=a_{*}^{\top}\operatorname{ReLU}(W_{*}x+b_{*})+c_{*}x+d_{*},$

where we define

$\displaystyle c_{*}$ $\displaystyle=\tilde{c}_{*}-a_{*}^{\top}H(-Z)W_{*}$
$\displaystyle d_{*}$ $\displaystyle=\tilde{d}_{*}-a_{*}^{\top}H(-Z)b_{*}.$

All that remains is to show $a_{*}$, $c_{*}$, and $d_{*}$ are unique. We start
by showing $a_{*}$ is unique. Consider two adjacent affine regions
$X,X^{\prime}\subset\mathbb{R}^{m}$ of $f$, where the shared boundary is
defined by the $i$th affine space. Let $r$ and $r^{\prime}$ be the signatures
of $X$ and $X^{\prime}$. Letting $x$ and $x^{\prime}$ be two arbitrary points
from the interiors of $X$ and $X^{\prime}$ respectively, we have the following
difference of gradients with respect to $x$:

$\displaystyle\nabla f(x^{\prime})-\nabla f(x)$
$\displaystyle=W_{*}^{\top}\operatorname{diag}(r^{\prime})a_{*}-W_{*}^{\top}\operatorname{diag}(r)a_{*}$
$\displaystyle=W_{*}^{\top}\operatorname{diag}(r^{\prime}-r)a_{*}.$

Since $X$ and $X^{\prime}$ differ only across the $i$th affine space, then all
entries of $r^{\prime}-r$ are zero except the $i$th entry. We therefore have

$\nabla f(x^{\prime})-\nabla f(x)=a_{*i}(r^{\prime}_{i}-r_{i})w_{*i}.$

Since $r^{\prime}-r$ and $w_{*i}$ are nonzero and unique, then we can in
principle solve this equation to determine a unique value for $a_{*i}$.

To show $c_{*}$ is unique, we recall the gradient of $f$ evaluated at the
point of differentiability $x\in X$:

$\nabla f(x)=W_{*}^{\top}\operatorname{diag}(r)a_{*}+c_{*}.$

Since $a_{*}$ and $W_{*}$ have been determined, then we can in principle solve
this equation to determine a unique value for $c_{*}$. Once this is done, we
can then evaluate $f$ at $x$ and solve for the only remaining unknown $d_{*}$,
thereby determining a unique value for $d_{*}$ as well. ∎

######  Remark 16.

Suppose $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ admits the form in Eq. 1. Then it
is possible for there to exist $i$ and $j$ such that $a_{i}=-a_{j}$,
$w_{i}=-w_{j}$, and $b_{i}=-b_{j}$. In this case, we have

$\displaystyle
a_{i}\operatorname{ReLU}(w_{i}^{\top}x+b_{i})+a_{j}\operatorname{ReLU}(w_{j}^{\top}x+b_{j})$
$\displaystyle=a_{i}\operatorname{ReLU}(w_{i}^{\top}x+b_{i})-a_{i}\operatorname{ReLU}[-(w_{i}^{\top}x+b_{i})]$
$\displaystyle=a_{i}(w_{i}^{\top}x+b_{i}),$

which follows from Prop. 15. Such affine and differentiable terms can thus
arise, which is why we include the $c_{*}x+d_{*}$ term in Lemma 3. Moreover,
observe that because $[W_{*}\mid b_{*}]\in\Theta_{n_{*}}$ in Lemma 3, no two
rows of $[W_{*}\mid b_{*}]$ are equal or opposites of one another, and thus no
two hidden neurons can be combined to yield an affine term; all affine terms
are thus collected in the $c_{*}x+d_{*}$ term, which helps to make the
canonical form of $f$ unique.

In general, given a group action on a set, the existence of a fundamental
domain is not guaranteed. The next proposition guarantees the existence of a
fundamental domain in $\Theta_{n}$ under the action of $\mathrm{PZ}(n)$ by way
of a constructive example.

######  Proposition 17.

Let $\leq_{*}$ be a total order on $\mathbb{R}^{m+1}$. Let $\Omega$ be the set
of all $[W\mid b]\in\Theta_{n}$ such that the first nonzero entry of each row
of $W$ is positive and the rows of $[W\mid b]$ are sorted in ascending order
under $\leq_{*}$. Then $\Omega$ is a fundamental domain.

###### Proof.

We will show that $\\{A\Omega:A\in\mathrm{PZ}(n)\\}$ is a partition of
$\Theta_{n}$. First, however, let $[W\mid b]\in\Omega$. Since the rows of
$[W\mid b]$ are nonzero (since the rows of $W$ have unit norm), then the
action of any non-identity $Z\in\mathcal{Z}(n)$ sends $[W\mid b]$ out of
$\Omega$. Similarly, since the rows of $[W\mid b]$ are pairwise nonparallel
and in particular distinct, then any non-identity $P\in\mathcal{P}(n)$ breaks
the ascending order of the rows of $[W\mid b]$ and sends it out of $\Omega$.
Finally, since no two rows of $[W\mid b]$ are opposites, then the actions of
$P$ and $Z$ cannot cancel one another. It thus follows that every
$A\in\mathrm{PZ}(n)$ sends $[W\mid b]$ out of $\Omega$.

We now proceed to show the elements in the claimed partition are disjoint. Let
$A,B\in\mathrm{PZ}(n)$, and suppose $A\Omega\cap B\Omega\neq\emptyset$. So,
let $[W\mid b]\in A\Omega\cap B\Omega$. Thus, $A^{-1}[W\mid b]$ and
$B^{-1}[W\mid b]$ are both in $\Omega$. We also note $(B^{-1}A)A^{-1}[W\mid
b]=B^{-1}[W\mid b]$. If $B^{-1}A$ is not the identity, then by the above, it
sends $A^{-1}[W\mid b]$ out of $\Omega$, so that $B^{-1}[W\mid
b]\notin\Omega$. Since, however, $B^{-1}[W\mid b]\in\Omega$, then $B^{-1}A=I$
so that $A=B$.

We next show that every $[W\mid b]\in\Theta_{n}$ belonds to some element of
the claimed partition. Clearly, there exists $A\in\mathrm{PZ}(n)$ such that
$A[W\mid b]\in\Omega$, so that $[W\mid b]\in A^{-1}\Omega$. ∎

####  B.2 $G$-SNNs and signed perm-reps

We prove Lemma 4.

###### Proof of Lemma 4.

We only prove the forward implication; the converse is then straightforward to
verify. We write $f$ in its canonical form:

$f(x)=a_{*}^{\top}\operatorname{ReLU}(W_{*}x+b_{*})+c_{*}^{\top}x+d_{*}.$

Let $g\in G$. Since $g$ is orthogonal and each row of $W_{*}$ has unit norm,
then so does each row of $W_{*}g$. Moreover, since the transformation
$[W_{*}\mid b_{*}]\rightarrow[W_{*}g\mid b_{*}]$ is invertible and no two rows
of $[W_{*}\mid b_{*}]$ are parallel, then the same is true for the rows of
$[W_{*}g\mid b_{*}]$. Thus, $[W_{*}g\mid b_{*}]\in\Theta_{n_{*}}$, and hence
there exists a unique matrix $\rho(g)\in\mathrm{PZ}(n_{*})$ such that
$[W_{*}g\mid b_{*}]\in\rho(g)\Omega_{n_{*}}$. Let
$\pi(g)\in\mathcal{P}(n_{*})$ and $\zeta(g)\in\mathcal{Z}(n_{*})$ such that
$\rho(g)=\pi(g)\zeta(g)$. We have

$\displaystyle f(gx)$
$\displaystyle=a_{*}^{\top}\operatorname{ReLU}(W_{*}gx+b_{*})+c_{*}^{\top}gx+d_{*}$
$\displaystyle=a_{*}^{\top}\operatorname{ReLU}[\rho(g)(\rho(g)^{-1}W_{*}gx+\rho(g)^{-1}b_{*})]+c_{*}^{\top}gx+d_{*}$
$\displaystyle=a_{*}^{\top}\operatorname{ReLU}[\pi(g)\zeta(g)(\rho(g)^{-1}W_{*}gx+\rho(g)^{-1}b_{*})]+c_{*}^{\top}gx+d_{*}$
$\displaystyle=a_{*}^{\top}\pi(g)\operatorname{ReLU}[\zeta(g)(\rho(g)^{-1}W_{*}gx+\rho(g)^{-1}b_{*})]+c_{*}^{\top}gx+d_{*}.$

Using Prop. 15, this is

$\displaystyle f(gx)$
$\displaystyle=a_{*}^{\top}\pi(g)\operatorname{ReLU}(\rho(g)^{-1}W_{*}gx+\rho(g)^{-1}b_{*})-a_{*}^{\top}H(-\zeta(g))(\rho(g)^{-1}W_{*}x+\rho(g)^{-1}b_{*})+c_{*}^{\top}gx+d_{*}$
$\displaystyle=a_{*}^{\top}\pi(g)\operatorname{ReLU}(\rho(g)^{-1}W_{*}gx+\rho(g)^{-1}b_{*})+[c_{*}^{\top}g-a_{*}^{\top}H(-\zeta(g))\rho(g)^{-1}W_{*}]x+[d_{*}-a_{*}^{\top}H(-\zeta(g))\rho(g)^{-1}b_{*}].$

Note that $\rho(g)^{-1}[W_{*}\mid b_{*}]\in\Omega_{n_{*}}$. Since $f$ is
$G$-invariant, then $f(gx)=f(x)\forall x\in\mathbb{R}^{m}$. By uniqueness of
canonical parameters with respect to the fundamental domain $\Omega_{n_{*}}$
(Lemma 3), the canonical parameters of the SNNs $f$ and $f\circ g$ must be
equal. We thus obtain the constraints

$\displaystyle W_{*}$ $\displaystyle=\rho(g)^{-1}W_{*}g$ $\displaystyle
a_{*}^{\top}$ $\displaystyle=a_{*}^{\top}\pi(g)$ $\displaystyle b_{*}$
$\displaystyle=\rho(g)^{-1}b_{*}$ $\displaystyle c_{*}^{\top}$
$\displaystyle=c_{*}^{\top}g-a_{*}^{\top}H(-\zeta(g))\rho(g)^{-1}W_{*}g$
$\displaystyle d_{*}$
$\displaystyle=d_{*}-a_{*}^{\top}H(-\zeta(g))\rho(g)^{-1}b_{*}.$

The first three constraints are clearly equivalent to the ones on $W_{*}$,
$a_{*}$, and $b_{*}$ claimed in the lemma statement; we thus take these as
established. By the established $W_{*}$ and $b_{*}$ constraints, the $c_{*}$
and $d_{*}$ constraints simplify to

$\displaystyle c_{*}^{\top}$
$\displaystyle=c_{*}^{\top}g-a_{*}^{\top}H(-\zeta(g))W_{*}$ $\displaystyle
d_{*}$ $\displaystyle=d_{*}-a_{*}^{\top}H(-\zeta(g))b_{*}.$

Now since $\zeta(g)$ is a diagonal matrix with $\pm 1$ along its diagonal,
then we have

$H(-\zeta(g))=\frac{1}{2}(I-\zeta(g)).$

Using the established $a_{*}$ constraint, we have

$\displaystyle a_{*}^{\top}H(-\zeta(g))$
$\displaystyle=\frac{1}{2}a_{*}^{\top}(I-\zeta(g))$
$\displaystyle=\frac{1}{2}a_{*}^{\top}(I-\pi(g)\zeta(g))$
$\displaystyle=\frac{1}{2}a_{*}^{\top}(I-\rho(g)).$

By the established $b_{*}$ constraint, we have
$(I-\rho(g))b_{*}=b_{*}-b_{*}=0$; we thus see that the above constraint on
$d_{*}$ is trivially satisfied. By the established $W_{*}$ constraint, the
constraint on $c_{*}$ becomes

$\displaystyle c_{*}^{\top}$
$\displaystyle=c_{*}^{\top}g-\frac{1}{2}a_{*}^{\top}(I-\rho(g))W_{*}$
$\displaystyle=c_{*}^{\top}g-\frac{1}{2}a_{*}^{\top}W_{*}(I-g)$ $\displaystyle
g^{\top}c_{*}$ $\displaystyle=c_{*}+\frac{1}{2}(I-g^{\top})W_{*}^{\top}a_{*}.$

Since this holds for all $g\in G$, then we may substitute $g^{\top}$ with $g$
to establish the claimed constraint on $c_{*}$.

Finally, we prove that $\rho:G\mapsto\mathrm{PZ}(n_{*})$ is a homomorphism.
Let $g_{1},g_{2}\in G$. By the established constraint on $W_{*}$, we have

$\displaystyle\rho(g_{1})\rho(g_{2})[W_{*}\mid b_{*}]$
$\displaystyle=\rho(g_{1})[W_{*}g_{2}\mid b_{*}]$
$\displaystyle=[W_{*}g_{1}g_{2}\mid b_{*}].$

On the other hand, by definition of $\rho$, we have
$\rho(g_{1}g_{2})[W_{*}\mid b_{*}]=[W_{*}g_{1}g_{2}\mid b_{*}]$. Thus,
$[W_{*}g_{1}g_{2}\mid b_{*}]$ is thus an element of both
$\rho(g_{1}g_{2})^{-1}\Omega_{n*}$ and of
$[\rho(g_{1})\rho(g_{2})]^{-1}\Omega_{n*}$, which in turn implies
$\rho(g_{1}g_{2})=\rho(g_{1})\rho(g_{2})$. ∎

The next proposition states that every $G$-SNN can be written as a sum of
irreducible $G$-SNNs, thereby simplifying the classification problem of
$G$-SNNs to that only of irreducible $G$-SNNs. Recall the notation introduced
in Sec. 3.2.

######  Proposition 18.

Every $G$-SNN admits a decomposition into a sum of irreducible $G$-SNNs.

###### Proof.

Let $f\in\mathrm{SNN}(G)$, and let $\rho\in F(f)$. Let $n_{*}$ be the degree
of $\rho$; i.e., the number of rows of the canonical weight matrix of $f$.
Then partition $\\{e_{1},\ldots,e_{n*}\\}$ into orbits such that $e_{i}$ and
$e_{j}$ belong to the same orbit if and only if there exists $g\in G$ such
that $\rho(g)e_{i}=\pm e_{j}$. Without loss of generality, select $\rho\in
F(f)$ such that each orbit consists of consecutive elements (this is done by
an appropriate conjugation of $\rho$); i.e., each orbit has the form
$\\{e_{i},e_{i+1},\ldots,e_{i+j}\\}$. Now write $f$ in canonical form such
that the corresponding signed perm-rep by Lemma 4 is $\rho$:

$f(x)=a_{*}^{\top}\operatorname{ReLU}(W_{*}x+b_{*})+c_{*}^{\top}x+d_{*}.$

For each $i=1,\ldots,k$, where we have $k$ orbits, define the $G$-SNN $f_{i}$
by taking only the elements $a_{*j}$ of $a_{*}$, rows $w_{*j}^{\top}$ of
$W_{*}$, and elements $b_{*j}$ of $b_{*}$ such that $e_{j}$ belongs to the
$i$th orbit; include the affine term $c_{*}^{\top}x+d_{*}$ only in $f_{k}$.
Then clearly $f=f_{1}+\ldots f_{k}$, where each $f_{i}$ is $G$-invariant and
irreducible. ∎

####  B.3 The classification theorem

This section gives a proof for Thm. 5. Recall the following notation
introduced in Sec. 3.3: If $A$ is a linear operator (resp. set of linear
operators), then let $P_{A}$ be the orthogonal projection operator onto the
vector subspace that is pointwise-invariant under the action of $A$ (resp. all
elements of $A$). Note that if $A$ is a finite orthogonal group, then [Serre,
1977, sec. 2.6]

$P_{A}=\frac{1}{|A|}\sum_{a\in A}a.$

In addition, if $P_{1},P_{2}$ are two orthogonal projection operators, then
let $P_{1}\cap P_{2}$ be the orthogonal projection operator onto
$\operatorname{ran}(P_{1})\cap\operatorname{ran}(P_{2})$.

Before proving Thm. 5, we need to state and prove two lemmas. The first of
these appears next.

######  Lemma 19.

Let $K\leq H<\mathcal{O}(m)$ be two finite orthogonal groups such that
$|H:K|=2$. Let $h\in H\setminus K$. Then $P_{K}\cap P_{2I+h}=P_{K}-P_{H}$.

###### Proof.

Since $|H:K|=2$, then $K\trianglelefteq H$, and hence $H/K=\\{K,hK\\}$ is a
bona fide group. Thus, there exists an isomorphism
$\pi:H/K\mapsto\mathbb{Z}_{2}$, where we define $\mathbb{Z}_{2}=\\{-1,1\\}$
under multiplication. Since we require $\ker(\pi)=K$, then we have

$\pi(h)=\begin{cases}1,&\mbox{ if }h\in K\\\ -1,&\mbox{
otherwise.}\end{cases}$

Now let

$V=\operatorname{ran}(P_{K}\cap
P_{2I+h})=\\{v\in\mathbb{R}^{m}:Kv=v,hKv=-v\\}.$

We thus see that $(\pi,V)$ is a representation of $H$, and since $\pi$ is
scalar-valued, then $(\pi,V)$ is a direct sum of copies of a single complex-
irreducible representation (irrep) of $H$. Noting that $\pi$ is its own
complex-irreducible character, we have the orthogonal projection

$\displaystyle P_{K}\cap P_{2I+h}$ $\displaystyle=\frac{1}{|H|}\sum_{h\in
H}\pi(h)h$ $\displaystyle=\frac{1}{|H|}\sum_{g\in
K}\pi(g)g+\frac{1}{|H|}\sum_{g\in hK}\pi(g)g$
$\displaystyle=\frac{1}{|H|}\sum_{g\in K}g-\frac{1}{|H|}\sum_{g\in hK}g$
$\displaystyle=\frac{1}{|H|}\sum_{g\in K}g-\frac{1}{|H|}\left(\sum_{g\in
H}g-\sum_{g\in K}g\right)$ $\displaystyle=\frac{2}{|H|}\sum_{g\in
K}g-\frac{1}{|H|}\sum_{g\in H}g$ $\displaystyle=\frac{1}{|K|}\sum_{g\in
K}g-\frac{1}{|H|}\sum_{g\in H}g$ $\displaystyle=P_{K}-P_{H}.$

∎

The second lemma, appearing below, will be used to characterize the condition
$[W_{*}\mid b_{*}]\in\Theta_{n_{*}}$ appearing in Lemma 3.

######  Lemma 20.

Let $J\leq G$ and $\\{g_{1},\ldots,g_{n}\\}$ a transversal of $G/J$ with
$g_{1}\in J$. Let $V\leq\operatorname{ran}(P_{J})$ be a vector subspace, and
let $P_{V}$ be the orthogonal projection operator onto $V$. Then there exists
$w\in V$ such that $g_{1}w,\ldots,g_{n}w$ are distinct vectors if and only if
$\operatorname{st}_{G}(P_{V})=J$.

###### Proof.

First we note that if $w\in V$, then $g_{1}w,\ldots,g_{n}w$ are distinct iff
$g_{i}w\neq w\forall i\in\\{2,\ldots,n\\}$; to see this, we prove the
equivalent statement that $g_{1}w,\ldots,g_{n}w$ are not distinct iff
$g_{i}w=w$ for some $i\in\\{2,\ldots,n\\}$. For the reverse implication,
$g_{i}w=w$ iff $g_{i}=g_{1}w$ since $g_{1}\in J$ and
$w\in\operatorname{ran}(P_{J})$; $g_{1}w$ and $g_{i}w$ are thus not distinct.
For the forward implication, suppose $g_{i}w=g_{j}w$ for some distinct
$i,j\in\\{1,\ldots,n\\}$. Then there exists $k\in\\{2,\ldots,n\\}$ and $g\in
J$ such that $g_{k}g=g_{j}^{-1}g_{i}$. We then have

$\displaystyle g_{i}w$ $\displaystyle=g_{j}w$ $\displaystyle g_{j}^{-1}g_{i}w$
$\displaystyle=w$ $\displaystyle g_{k}gw$ $\displaystyle=w$ $\displaystyle
g_{k}w$ $\displaystyle=w.$

We now prove the stated lemma. We have

$\displaystyle\forall w\in V,\exists i\in\\{2,\ldots,n\\}\mid g_{i}w=w$
$\displaystyle\Leftrightarrow\forall w\in V,\exists i\in\\{2,\ldots,n\\}\mid
w\in g_{i}V$ $\displaystyle\Leftrightarrow V\leq\bigcup_{i=2}^{n}g_{i}V.$

Since the $g_{i}$ are orthogonal, then each $g_{i}V$ has the same dimension as
$V$. Thus, the only way $V$ can be contained in a union of finitely many
spaces of the same dimension as $V$ is if $V$ equals one of these spaces. We
thus have

$\forall w\in V,\exists i\in\\{2,\ldots,n\\}\mid
g_{i}w=w\Leftrightarrow\exists i\in\\{2,\ldots,n\\}\mid g_{i}V=V.$

Negating both sides, we establish the claim:

$\displaystyle\exists w\in V\mid g_{i}w\neq w\forall i\in\\{2,\ldots,n\\}$
$\displaystyle\Leftrightarrow g_{i}V\neq V\forall i\in\\{2,\ldots,n\\}$
$\displaystyle\Leftrightarrow g_{i}P_{V}\neq P_{V}\forall
i\in\\{2,\ldots,n\\}$ $\displaystyle\Leftrightarrow(\forall g\in
G,gP_{V}=P_{V}\Rightarrow g\in J).$

∎

We now prove Thm. 5.

###### Proof of Thm. 5.

(b)  Suppose $\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$. We first prove
the forward implication. Suppose $f\in F^{-1}(\rho_{HK}^{\mathrm{PZ}})$. Then
the canonical parameters of $f$ satisfy Eqs. 3-6, where the signed perm-rep
$\rho$ in Lemma 4 satisfies $\rho\in\rho_{HK}^{\mathrm{PZ}}$. By an
appropriate choice of fundamental domain $\Omega_{n_{*}}$, we can assume
without loss of generality that $\rho=\rho_{HK}$. We proceed to prove the
claimed expressions for the canonical parameters of $f$.

Expression for $a_{*}$:  Regardless of its type, $\rho$ is transitive on
$\\{e_{1},\ldots,e_{n_{*}}\\}$, and thus so is $\pi$. Hence, by Eq. 4, $a_{*}$
is a constant vector. That $a\neq 0$ follows from the definition of the
canonical parameter $a_{*}$ in Lemma 3.

Expression for $b_{*}$:  If $\rho$ is type 1, then it is an irreducible
ordinary perm-rep and is transitive on $\\{e_{1},\ldots,e_{n_{*}}\\}$. Thus,
by Eq. 5, $b_{*}$ is a constant vector. On the other hand, if $\rho$ is type
2, then it is transitive on $\\{\pm e_{1},\ldots,\pm e_{n_{*}}\\}$. In
particular, for every $i=1,\ldots,n_{*}$, there exists $g\in G$ such that
$\rho(g)e_{i}=-e_{i}$. Hence, $b_{*i}=-b_{*i}$ for every $i$, so that
$b_{*}=0$.

Expression for $W_{*}$:  By Prop. 12 (a), the subgroup $K$ satisfies

$K=\\{g\in G:\rho(g)e_{1}=e_{1}\\}.$

Thus, by Eq 3, the first row $w^{\top}$ of $W_{*}$ satisfies
$w^{\top}=w^{\top}g\forall g\in K$, or equivalently $gw=w\forall g\in K$.
Thus, $w\in\operatorname{ran}(P_{K})$.

In addition, if $\rho$ is type 2, then by Prop. 12a, we have $hw=-w\forall
h\in H\setminus K$. Given any choice of $h\in H\setminus K$, we have
$hK=H\setminus K$. We thus have

$\displaystyle hKw$ $\displaystyle=-w$ $\displaystyle hw$ $\displaystyle=-w$
$\displaystyle(2I+h)w$ $\displaystyle=w.$

Combining this with $w\in\operatorname{ran}(P_{K})$, we have
$w\in\operatorname{ran}(P_{K}\cap P_{2I+h})$. By Lemma 19, we obtain
$w\in\operatorname{ran}(P_{K}-P_{H})$. Combining the results for both types 1
and 2, we establish $w\in\operatorname{ran}(P_{K}-\tau P_{H})$. That $\|w\|=1$
follows from the definition of the canonical parameter $W_{*}$ in Lemma 3.

Now let $w_{1}^{\top},\ldots,w_{n_{*}}^{\top}$ be the rows of $W_{*}$. Since
$G$ and $\rho(G)$ are both orthogonal, then $\rho(g_{i}^{\top})e_{i}=e_{1}$,
and hence the first row of $\rho(g_{i}^{\top})W_{*}$ is $w_{i}^{\top}$. By Eq.
3, the first row of $W_{*}g_{i}^{\top}$ is $w_{i}^{\top}$ as well; thus, since
$w_{1}=w$, then $w^{\top}g_{i}^{\top}=w_{i}^{\top}$, or equivalently
$w_{i}=g_{i}w$.

Expression for $c_{*}$:  We rewrite Eq. 6 as

$(I-g)c_{*}=-\frac{a}{2}(I-g)W_{*}\vec{1}\forall g\in G,$

where we have used Eq. 8. This is equivalently expressed as

$(I-P_{G})c_{*}=-\frac{a}{2}(I-P_{G})W_{*}\vec{1}.$

We focus on the term

$(I-P_{G})W_{*}\vec{1}=(I-P_{G})(g_{1}+\ldots+g_{n})w.$

Since $P_{G}$ is an average over all $g\in G$, then $P_{G}g_{i}=P_{G}\forall
i\in\\{1,\ldots,n\\}$. We thus have

$(I-P_{G})W_{*}\vec{1}=(g_{1}+\ldots+g_{n})w-nP_{G}w.$

If $\rho$ is type 1 so that
$w\in\operatorname{ran}(P_{K})=\operatorname{ran}(P_{H})$, then

$\displaystyle(g_{1}+\ldots+g_{n})w$
$\displaystyle=(g_{1}+\ldots+g_{n})P_{H}w$ $\displaystyle=nP_{G}w,$

so that $(I-P_{G})W_{*}\vec{1}=0$. On the other hand, if $\rho$ is type 2,
then $hw=-w\forall h\in H\setminus K$; thus, $w$ cannot be fixed under all of
$G$, so that $P_{G}w=0$ and hence

$(I-P_{G})W_{*}\vec{1}=(g_{1}+\ldots+g_{n})w=W_{*}\vec{1}.$

Combining the results for both types 1 and 2, we have
$(I-P_{G})W_{*}\vec{1}=\tau W_{1}\vec{1}$ and thus

$(I-P_{G})c_{*}=-\frac{1}{2}a\tau W_{*}\vec{1}.$

Since we already know the right-hand side is in $\operatorname{ran}(I-P_{G})$,
then we obtain the expression for $c_{*}$ as claimed.

For the reverse implication, let $f$ be a $G$-SNN whose canonical parameters
satisfy Eqs. 7-10. Then it is easy to see that the canonical parameters of $f$
also satisfy Eqs. 3-6. Lemma 4 thus implies $F(f)=\rho_{HK}^{\mathrm{PZ}}$.

(a)  By part (b) of this theorem,
$\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$ iff there exists a $G$-SNN
$f$ whose canonical parameters satisfy Eqs. 7-10. Without loss of generality,
we assume $a=1$ in Eq. 8 and $c=0$ in Eq. 10. Then
$\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$ iff there exists $[W_{*}\mid
b_{*}]\in\Theta_{n_{*}}$ such that $W_{*}$ satisfies Eq. 7 and $b_{*}$
satisfies Eq. 9. We now have two separate cases depending on the type of
$\rho_{HK}$.

Case 1:  Suppose $\rho_{HK}$ is type 1. Without loss of generality, we assume
$b\neq 0$ in Eq. 9. Then $[W_{*}\mid b_{*}]$ has pairwise nonparallel rows iff
$W_{*}$ has distinct rows. By Eq. 7,
$\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$ iff there exists
$w\in\operatorname{ran}(P_{K})$, such that $g_{1}w,\ldots,g_{n}w$ are
distinct; note this $w$ is necessarily nonzero, and hence without loss of
generality, we assume $\|w\|=1$. Noting that $H=K$ since $\rho_{HK}$ is type
1, and invoking Lemma 20 with $J=K$ and $V=\operatorname{ran}(P_{K})$, we
establish the claim.

Case 2:  Suppose $\rho_{HK}$ is type 2. Then $b=0$ in Eq. 9, and $[W_{*}\mid
b_{*}]$ has pairwise nonparallel rows iff so does $W_{*}$. Thus, by Eq. 7,
$\rho_{HK}^{\mathrm{PZ}}\in\operatorname{ran}(F)$ iff there exists
$w\in\operatorname{ran}(P_{K}-P_{H})$ such that $g_{1}w,\ldots,g_{n}w$ are
pairwise nonparallel; note this $w$ is necessarily nonzero, and hence without
loss of generality we can assume $\|w\|=1$. For any $h\in H\setminus K$, we
have $-g_{i}w=g_{i}hw=g_{-i}w\forall i\in\\{1,\ldots,n\\}$. Moreover,
$\\{g_{\pm 1},\ldots,g_{\pm n}\\}$ is a transversal of $G/K$. Invoking Lemma
20 with $J=K$ and $V=\operatorname{ran}(P_{K}-P_{H})$, we thus establish the
claim. ∎

Finally, we prove Prop. 6, which states that non-cohomologous irreducible
$G$-SNN architectures are in a sense orthogonal.

###### Proof of Prop. 6.

For $i=1,2$, let $\tau_{i}=|H:K_{i}|$. Then by Eq. 7, we have the constraints
$w_{i}\in\operatorname{ran}(P_{K_{i}}-\tau_{i}P_{H})$. If one of the $K_{i}$
equals $H$, say $K_{1}=H$, then in particular we have the constraints
$P_{H}w_{1}=w_{1}$ and $(P_{K_{2}}-P_{H})w_{2}=w_{2}$. We thus have

$\displaystyle w_{1}^{\top}w_{2}$
$\displaystyle=w_{1}^{\top}P_{H}^{\top}(P_{K_{2}}-P_{H})w_{2}$
$\displaystyle=w_{1}^{\top}P_{H}(P_{K_{2}}-P_{H})w_{2}$
$\displaystyle=w_{1}^{\top}(P_{H}P_{K_{2}}-P_{H})w_{2}$ $\displaystyle=0,$

where the last step holds because $K_{2}\leq H$ and hence
$P_{H}P_{K_{2}}=P_{H}$.

On the other hand, suppose $K_{1}$ and $K_{2}$ are both proper subgroups of
$H$. Since $P_{K_{i}}w_{i}=w_{i}$, then

$w_{1}^{\top}w_{2}=w_{1}^{\top}P_{K_{1}}^{\top}P_{K_{2}}w_{2}.$

Let $K=K_{1}\cap K_{2}$. It is well-known that because $K_{1}$ and $K_{2}$ are
distinct index-2 subgroups of $H$, then $K$ is an index-4 subgroup of $H$ and

$H/K=\\{K,k_{1}K,k_{2}K,hK\\},$

where $k_{i}\in K_{i}\setminus K$ for $i=1,2$ and $h\in H\setminus(K_{1}\cup
K_{2})$. We thus have

$\displaystyle P_{K_{1}}^{\top}P_{K_{2}}$
$\displaystyle=\left(\frac{1}{|K_{1}|}\sum_{k\in
K_{1}}k\right)^{\top}\left(\frac{1}{|K_{2}|}\sum_{k\in K_{2}}k\right)$
$\displaystyle=\frac{1}{|K_{1}|^{2}}\left(\sum_{k\in K}k+k_{1}\sum_{k\in
K}k\right)^{\top}\left(\sum_{k\in K}k+k_{2}\sum_{k\in K}k\right)$
$\displaystyle=\frac{|K|^{2}}{|K_{1}|^{2}}(P_{K}+k_{1}P_{K})^{\top}(P_{K}+k_{2}P_{K})$
$\displaystyle=\frac{1}{4}P_{K}^{\top}(I+k_{1}^{\top})(I+k_{2})P_{K}$
$\displaystyle=\frac{1}{4}P_{K}^{\top}(I+k_{1}^{\top}+k_{2}+k_{1}^{\top}k_{2})P_{K}.$

Since $P_{K}w_{i}=w_{i}$ for both $i=1,2$, then we have

$\displaystyle w_{1}^{\top}w_{2}$
$\displaystyle=\frac{1}{4}w_{1}^{\top}P_{K}^{\top}(I+k_{1}^{\top}+k_{2}+k_{1}^{\top}k_{2})P_{K}w_{2}$
$\displaystyle=\frac{1}{4}w_{1}^{\top}(I+k_{1}^{\top}+k_{2}+k_{1}^{\top}k_{2})w_{2}.$

Since $k_{1}\in K_{1}$, then $k_{1}w_{1}=w_{1}$, and hence
$w_{1}^{\top}k_{1}^{\top}w_{2}=w_{1}^{\top}w_{2}$. On the other hand, since
$k_{1}^{\top}\in H\setminus K_{2}$, then $k_{1}^{\top}w_{2}=-w_{2}$ so that
$w_{1}^{\top}k_{1}^{\top}w_{2}=-w_{1}^{\top}w_{2}$, thus implying
$w_{1}^{\top}k_{1}^{\top}w_{2}=0$. We can similarly show that
$w_{1}^{\top}k_{2}w_{2}=0$. This leaves

$\displaystyle w_{1}^{\top}w_{2}$
$\displaystyle=\frac{1}{4}w_{1}^{\top}(I+k_{1}^{\top}k_{2})w_{2}$
$\displaystyle=\frac{1}{4}(w_{1}^{\top}w_{2}+w_{1}^{\top}w_{2})$
$\displaystyle=\frac{1}{2}w_{1}^{\top}w_{2},$

implying $w_{1}^{\top}w_{2}=0$. ∎

###  Appendix C Examples

####  C.1 Irreducible architecture count

Table 1:  Ratio of the number of irreducible $G$-SNN architectures to the number of irreducible signed perm-reps of each type (1 vs. 2) for every group $G$, $|G|\leq 8$, up to isomorphism. The particular representations used for each group are described in the main text.  $G$ | Type 1 | Type 2 | $G$ | Type 1 | Type 2
---|---|---|---|---|---
$C_{2}$ | 2/2 | 1/1 | $\\{e\\}$ | 1/1 | 0/0
$C_{3}$ | 2/2 | 0/0 | $C_{2}^{2}$ | 4/5 | 3/6
$C_{4}$ | 3/3 | 2/2 | $C_{2}^{3}$ | 8/16 | 7/35
$C_{5}$ | 2/2 | 0/0 | $C_{2}\times C_{4}$ | 6/8 | 5/11
$C_{6}$ | 4/4 | 2/2 | $D_{3}$ | 3/4 | 1/2
$C_{7}$ | 2/2 | 0/0 | $D_{4}$ | 5/8 | 7/13
$C_{8}$ | 4/4 | 3/3 | $Q_{8}$ | 6/6 | 7/7

Using our code implementation, we enumerated all irreducible $G$-SNN
architectures for every group $G$, $|G|\leq 8$, up to isomorphism. For each
group, we consider only one particular permutation representation defined as
follows: First, let $[i_{1},\ldots,i_{n}]$ denote the permutation on the
orthonormal basis $\\{e_{1},\ldots,e_{n}\\}$ where $e_{j}\rightarrow
e_{i_{j}}$. We then represent the cyclic group $C_{n}$ by the set of cyclic
permutations generated by $[2,\ldots,n,1]$, and we represent the dihedral
group $D_{n}$ as the group generated by $C_{n}$ together with the reversing
permutation $[n,n-1,\ldots,1]$. We represent the direct product of groups by
the direct sum of the factor groups; e.g., if $G_{1}$ acts on
$[1,\ldots,n_{1}]$ and $G_{2}$ acts on $[1,\ldots,n_{2}]$, then $G_{1}\times
G_{2}$ acts on $[1,\ldots,n_{1}+n_{2}]$ with $G_{1}$ acting on the first
$n_{1}$ elements and $G_{2}$ acting on the last $n_{2}$ elements. Finally, we
represent the quaternian group $Q_{8}$ in terms of the following generators:

$\displaystyle i$ $\displaystyle=[3,4,2,1,7,8,6,5]$ $\displaystyle j$
$\displaystyle=[5,6,8,7,2,1,3,4]$ $\displaystyle k$
$\displaystyle=[7,8,5,6,4,3,2,1].$

For each group $G$, we report the ratio of the number of irreducible $G$-SNN
architectures of each type to the number of irreducible signed perm reps of
the respective type (Table 1). We see that there are generally fewer type 2
architectures—which are the topologically nontrivial ones—than type 1
architectures, although the number of type 2 architectures is not negligible.
We also observe that—especially for the direct products of groups—there is a
large number of irreducible signed perm reps that do not satisfy the condition
in Thm. 5 (a); this is likely because in the rejected architectures, some of
the weight vectors are constrained such that the architecture is equivalent to
a smaller architecture already enumerated. This trend also motivates the need
for more intuition about the condition in Thm. 5 (a).

####  C.2 The dihedral permutation group

Table 2:  Subgroups $K_{j}\leq H_{i}\leq G$ of the dihedral permutation group $G=D_{6}$ such that the irreducible signed perm rep $\rho_{H_{i}K_{j}}$ admits a corresponding irreducible $G$-SNN architecture named “i.j” in Figs. 4-6. In each row, $|H_{i}:K_{0}|=1$ and $|H_{i}:K_{j}|=2$ for $j\geq 1$. The generators $r$ and $t$ are defined in Eqs. 11-12.  | $K_{0}$ | $K_{1}$ | $K_{2}$ | $K_{3}$
---|---|---|---|---
$H_{0}$ | $\langle e\rangle$ |  |  |
$H_{1}$ | $\langle r^{3}\rangle$ | $\langle e\rangle$ |  |
$H_{2}$ | $\langle t\rangle$ | $\langle e\rangle$ |  |
$H_{3}$ | $\langle r^{3}t\rangle$ | $\langle e\rangle$ |  |
$H_{4}$ | $\langle r^{3},t\rangle$ | $\langle r^{3}\rangle$ | $\langle t\rangle$ | $\langle r^{3}t\rangle$
$H_{5}$ | $\langle r^{2},rt\rangle$ |  |  |
$H_{6}$ | $D_{6}$ | $\langle r^{2},t\rangle$ |  |

Architecture 0.0

Architecture 5.0

Figure 4:  Constraint patterns of the weight matrices and illustrations of the
cohomology classes of two irreducible $G$-SNN architectures for the dihedral
permutation group $G=D_{6}$. These are the only two architectures with no
partnering type 2 architectures. Interpretation is the same as in Fig. 1. Red
(resp. blue) arcs represent the action of the generator $r$ (resp. $t$) of
$D_{6}$ (see Eqs. 11-12). See Table 2 to interpret the names “architecture
i.j”.

Architecture 1.0

Architecture 2.0

Architecture 3.0

Architecture 1.1

Architecture 2.1

Architecture 3.1

Figure 5:  Constraint patterns of the weight matrices and illustrations of the
cohomology classes of the six-hidden-neuron irreducible $G$-SNN architectures
for the dihedral permutation group $G=D_{6}$. Interpretation is the same as in
Fig. 1. Weights colored white are constrained to equal zero. See Table 2 to
interpret the names “architecture i.j”.

Architecture 4.0

Architecture 4.2

Architecture 6.0

Architecture 4.1

Architecture 4.3

Architecture 6.1

Figure 6:  Constraint patterns of the weight matrices and illustrations of the
cohomology classes of the three-hidden-neuron and single-hidden-neuron
irreducible $G$-SNN architectures for the dihedral permutation group
$G=D_{6}$. Interpretation is the same as in Fig. 1. See Table 2 to interpret
the names “architecture i.j”.

Consider the dihedral group $G=D_{6}$ of permutations generated by

$\displaystyle r$ $\displaystyle=[2,3,4,5,6,1]$ (11) $\displaystyle t$
$\displaystyle=[6,5,4,3,2,1].$ (12)

There are 14 irreducible $G$-SNN architectures– 7 of each type. We visualize
their canonical weight matrices and corresponding cohomology classes in Figs.
4-6. Each architecture is named “i.j” where i and j index the subgroups $H$
and $K$ that are used to construct the architecture (see Thm. 5); Table 2
lists these subgroups for each architecture.

In contrast to the cyclic permutation group (Sec. 4.1), the cohomology class
illustrations for $G=D_{6}$ have arcs of two colors; red (resp. blue) arcs
represent the action of the generator $r$ (resp. $t$). The existence of any
loops with an odd number of dashed arcs indicates a nontrivial topology. For
example, the four architectures 4.j with three hidden neurons correspond to
the classes in $\mathcal{H}^{1}(G,M_{H_{4}})\cong C_{2}\times C_{2}$.

An important remark is that while there are only two architectures 6.j
corresponding to the subgroup $H_{6}$, the corresponding cohomology group is
$\mathcal{H}^{1}(G,M_{H_{6}})\cong C_{2}\times C_{2}$. Thus, there are two
cohomology classes for which the corresponding signed perm reps failed the
condition in Thm. 5 (a). It is thus not necessary for an irreducible
architecture to exist for every cohomology class.

Figure 7:  Network morphisms between irreducible $G$-SNN architectures for the
dihedral permutation group $G=D_{6}$. Every direct path in black represents an
asymptotic inclusion. Red doubled-arrowed arcs represent the feasibility of
topological tunneling.

We also draw the network morphisms given by asymptotic inclusions between the
irreducible architectures, as well as the shortcuts due to topological
tunneling (Fig. 7); see Sec. 4.3 for exposition on these concepts. As with
Fig. 3, we determined the asymptotic inclusions manually by looking at the
first rows of the weight matrices depicted in Figs. 4-6 and observing how they
nest. We obtain a $4$-partite topology on the architecture space, plus some
topological “tunnels” between architectures belonging to a common cohomology
ring.

####  C.3 The dihedral rotation group

|  |
---|---|---
|  |
Figure 8:  Contour plots of the six irreducible $G$-SNN architectures for the
2D orthogonal representation of $G=D_{6}$. The architecture names are still
based on Table 2, but the generator $r$ is now a $60^{\circ}$ rotation and $t$
is a reflection about the dashed black line. In architectures 0.0 and 1.1,
weight vector 1 is unconstrained and was chosen arbitrarily for visualization.
in the other four architectures, however, weight vector 1 is constrained to a
1D subspace as depicted. Interpretation of these plots is the same as in Fig.
2.

As our final example, we consider a 2D orthogonal representation of the
dihedral group $G=D_{6}$. In this representation, the generator $r$ is a
$60^{\circ}$ counterclockwise rotation, and the generator $t$ is a reflection
about the line $y=\tan(15^{\circ})x$; we choose this line of reflection solely
because it makes the example interesting. There are six irreducible $G$-SNN
architectures for this group—three of each type—and we visualize there contour
plots (Fig. 8). The level curves are clearly invariant under $60^{\circ}$
rotations and are symmetric about $y=\tan(15^{\circ})x$. The architecture
names are still based on Table 2, but the generators $r$ and $t$ are now 2D
orthogonal transformations instead of permutations. Note that for
architectures 0.0 and 1.1, the corresponding subgroup $K$ appearing in Thm. 5
is $K=\langle e\rangle$; for architectures 2.0 and 4.2, $K=\langle t\rangle$;
and for architectures 3.0 and 4.3, $K=\langle r^{3}t\rangle$, whence the
columns in Fig. 8.

Each type 2 architecture in the second row of Fig. 8 is asymptotically
included in the type 1 architecture depicted above it. This is the same
situation as with the cyclic rotation group in Sec. 4.2; each type 1
architecture approaches the corresponding type 2 architecture below it as its
bias parameter $b_{*}$ tends to zero. In contrast to the cyclic rotation
group, however, there are other architectures that are effectively confined
from one another. The weight vectors of architecture 2.0 are orthogonal to
those of architecture 3.0, and hence one architecture can reach the other only
if it passes through a degenerate network with zero-valued weight vectors. By
the same token, architectures 4.2 and 4.3 are topologically confined from one
another, just as Prop. 6 (see Supp. B.3) states.

Finally, we note that while we have architecture 1.1, there is no architecture
1.0; similarly, we have architectures 4.2 and 4.3 but not 4.0 and 4.1. This
example thus demonstrates that the cohomology classes in a given cohomology
ring for which the corresponding $G$-SNN architecture exists (i.e., satisfies
the condition in Thm. 5 (a)) need not form a subgroup, and this raises the
question: Are there any discernible patterns in the set of irreducible $G$-SNN
architectures (which satisfy Thm. 5 (a)) as we vary $G$? We will investigate
this further as part of future work.