# Densely Connected $G$-invariant Deep Neural Networks with Signed Permutation
Representations

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

###### Abstract

We introduce and investigate, for finite groups $G$, $G$-invariant deep neural
network ($G$-DNN) architectures with ReLU activation that are densely
connected– i.e., include all possible skip connections. In contrast to other
$G$-invariant architectures in the literature, the preactivations of
the$G$-DNNs presented here are able to transform by _signed_ permutation
representations (signed perm-reps) of $G$. Moreover, the individual layers of
the $G$-DNNs are not required to be $G$-equivariant; instead, the
preactivations are constrained to be $G$-equivariant functions of the network
input in a way that couples weights across all layers. The result is a richer
family of $G$-invariant architectures never seen previously. We derive an
efficient implementation of $G$-DNNs after a reparameterization of weights, as
well as necessary and sufficient conditions for an architecture to be
“admissible”– i.e., nondegenerate and inequivalent to smaller architectures.
We include code that allows a user to build a $G$-DNN interactively layer-by-
layer, with the final architecture guaranteed to be admissible. We show that
there are far more admissible $G$-DNN architectures than those accessible with
the “concatenated ReLU” activation function from the literature. Finally, we
apply $G$-DNNs to two example problems—(1) multiplication in $\\{-1,1\\}$
(with theoretical guarantees) and (2) 3D object classification—finding that
the inclusion of signed perm-reps significantly boosts predictive performance
compared to baselines with only ordinary (i.e., unsigned) perm-reps.

Keywords: deep learning, group theory, neural network, skip connection,
symmetry

##  1 Introduction

When fitting a deep neural network (DNN) to a target function that is known to
be $G$-invariant with respect to a group $G$, it only makes sense to enforce
$G$-invariance on the DNN as prior knowledge. With the rise of geometric deep
learning (Bronstein et al., 2021), this is becoming an increasingly common
practice, finding applications in various domains including computer vision
(Veeling et al., 2018; Esteves et al., 2018; Musallam et al., 2022), the
physical sciences (Luo et al., 2021; Atz et al., 2021; Kaba and Ravanbakhsh,
2022; Agrawal et al., 2023), and genomics (Mallet and Vert, 2021; Zhou et al.,
2022). In general-purpose $G$-invariant and $G$-equivariant architectures such
as $G$-equivariant convolutional neural networks ($G$-CNNs) (Cohen and
Welling, 2016) and $G$-equivariant graph neural networks (Maron et al.,
2019a), it is standard to require every linear layer to be $G$-equivariant.
Moreover, in case of the rectified linear unit (ReLU) activation, every linear
layer is $G$-equivariant only with respect to permutation representations. It
is commonly assumed that the $G$-invariant architectures constructed in this
way are sufficient for consideration (Cohen et al., 2019; Finzi et al., 2021),
but it is unclear if this layerwise construction covers all possible ways of
enforcing $G$-invariance on a fully-connected feedforward DNN, and it remains
an open conjecture (Kondor and Trivedi, 2018). While these architectures and
others are certainly sufficient for universal approximation of $G$-invariant
functions (Maron et al., 2019b; Ravanbakhsh, 2020; Kicki et al., 2020), the
way in which $G$-invariance is enforced is an aspect of the neural
architecture and thus likely plays a key role in determining the inductive
bias of the model and hence its generalization power on a given problem.

It has recently been discovered that there are, in fact, more ways to enforce
$G$-invariance on shallow ReLU neural networks than just permutations on the
hidden neurons (Agrawal and Ostrowski, 2022). In their work, Agrawal and
Ostrowski (2022) exploit the identity

$\operatorname{ReLU}(-x)=\operatorname{ReLU}(x)-x$ (1)

to show that $G$-invariance can be achieved even if $G$ acts on the hidden
neurons via a “signed permutation representation” (signed perm-rep), resulting
in novel $G$-invariant shallow architectures previously unknown. In an attempt
towards a generalization to deep architectures, we observe that the linear
term in Eq. (1) can be interpreted as a skip connection; this suggests that
skip connections may be the key to novel deep $G$-invariant architectures.

In this paper, as a partial generalization of the work of Agrawal and
Ostrowski (2022), we investigate $G$-invariant deep neural network ($G$-DNN)
architectures that are “densely connected”– i.e., include all possible skip
connections. We note that (non-$G$-invariant) densely connected neural
networks exist in the literature and have found immense success especially in
medical imaging (Huang et al., 2017). We use ReLU activation, and every
preactivation layer is still a $G$-equivariant function of the network input;
however, in contrast to previous architectures such as the $G$-CNN, the
individual weight matrices of a $G$-DNN need not be $G$-equivariant. Instead,
in each layer, only the concatenation of the weight matrix with all skip
connections from previous layers need be $G$-equivariant. This dense structure
allows us to use _signed_ perm-reps to enforce$G$-equivariance on the
preactivation layers, thus granting us access to a much larger family of
$G$-invariant architectures than seen previously.

Implementation of $G$-DNNs is nontrivial, as the group representation by which
the weight matrix (concatenated with all skip connections) in each layer
transforms is itself a function of the weights in previous layers. That is,
due to the skip connections and in contrast to previous architectures such as
the $G$-CNN, $G$-invariance is enforced in a way that couples weights across
layers. We show, however, that there is a reparameterization of $G$-DNNs in
which the equivariance conditions of the weight matrices decouple and admit a
simple implementation (Thm. 6 (a)). For efficiency, rather than transforming
back to the original weights, we express and implement the forward pass of a
$G$-DNN directly in terms of these reparameterized weights (Thm. 6 (b)).

There is additional literature suggesting the potential of $G$-DNNs. Signed
perm-reps have been used previously as design components in $G$-invariant
architectures and have proved beneficial especially in computer vision (Cohen
and Welling, 2017). These previous works incorporate signed perm-reps by
replacing ReLU with the _concatenated ReLU_ (CRELU) activation function (Shang
et al., 2016) defined as

$\operatorname{CReLU}(x)=\operatorname{ReLU}\left(\begin{bmatrix}x\\\
-x\end{bmatrix}\right),$ (2)

which sends negations of its input to transpositions of its output. CReLU was
originally introduced to capture the empirical observation that certain
feature maps in convolutional neural networks trained on images tend to pair
up (Shang et al., 2016). Since then, besides its use in $G$-invariant
architectures, CReLU has been shown to be beneficial for the trainability of
networks with skip connections– e.g., its compatibility with batch
normalization (Shang et al., 2017) and its role in the “looks linear” weight
initialization (Balduzzi et al., 2017). The CReLU literature thus suggests
that $G$-invariance, signed perm-reps, and skip connections may play well
together. and we claim that the $G$-DNN architectures introduced in this paper
are a culmination of these ideas. In contrast to the literature, however, our
perspective is top-down, and we show in this paper that a systematic study of
$G$-DNN architectures leads to the discovery of novel architecture designs not
accessible with CReLU alone (Ex. 1).

Finally, this work contributes to the ultimate goal of $G$-invariant neural
architecture search ($G$-NAS), which purports to apply search methods over
$G$-invariant architectures. In addition to finding good $G$-invariant
architectures for a given problem, $G$-NAS would relieve practitioners from
having to learn or perform specialized mathematics (in particular, group
theory), thereby making $G$-invariant deep learning more accessible and
applicable. Previous works have already begun to explore $G$-NAS with
promising results (Basu et al., 2021; Maile et al., 2022), but these works
only operate within a limited region of $G$-invariant architecture space;
indeed, Agrawal and Ostrowski (2022) argue that a more extensive $G$-NAS first
requires the characterization of all $G$-invariant architectures as well as
the so-called network morphisms between them. There has been work
characterizing $G$-invariant architectures from a graph-theoretic perspective
but not exploiting identities of the activation function (Ravanbakhsh et al.,
2017); work on the classification of $G$-invariant shallow ReLU architectures
(Agrawal and Ostrowski, 2022); and even work introducing novel $G$-invariant
architectures based on a sum-product layer (Kicki et al., 2021). Now, our
discovery of novel $G$-DNN architectures based on Eq. (1) pushes the horizon
on $G$-invariant architecture space further back, revealing new regions of
exploration. We prove Thm. 7, which lets us count numbers of distinct non-
degenerate $G$-DNNs, in terms of which we gain intuition about how many new
architectures we are now able to access.

The remainder of the paper is organized as follows: In Sec. 2, we review
signed perm-reps and state our central hypothesis with some theoretical
support. In Sec. 3, we introduce and describe the implementation of $G$-DNN
architectures. We additionally derive necessary and sufficient conditions for
a $G$-DNN architecture to be “admissible” or nondegenerate (Thm. 7), in the
sense that (1) no neuron is missing an input and (2) no two ReLU neurons can
be combined into a single ReLU neuron or a skip connection. We include
code111Code for our implementation and for reproducing all results in this
paper is available at: https://github.com/dagrawa2/gdnn_code. that allows a
user to build a $G$-DNN interactively such that the final architecture is
guaranteed to be admissible. We also verify that batch normalization placed
after ReLU is compatible with $G$-DNNs out-of-the-box. In Sec. 4, we
demonstrate that $G$-DNNs go well-beyond CReLU-based architectures, and we
test $G$-DNNs on two examples—(1) a simple mathematical function and (2) a
real-world computer vision problem—and demonstrate that signed perm-reps can,
in fact, carry useful inductive bias. Finally, in Sec. 5, we end with
conclusions, implications, and future outlook.

##  2 Signed permutation representations

###  2.1 Preliminaries

We begin by introducing some notions and notation that will be used throughout
this paper. This section is an abbreviation of Secs. 2.1-2.2 of Agrawal and
Ostrowski (2022), and we refer readers to all of Sec. 2 of that paper for
details of the below material.

Throughout this paper, let $G$ be a finite group of $m\times m$ orthogonal
matrices. Let $\operatorname{P}(n)$ be the group of $n\times n$ permutation
matrices and $\operatorname{Z}(n)$ the group of $n\times n$ diagonal matrices
with diagonal entries $\pm 1$. Let $\mathrm{PZ}(n)$ be the group of _signed
permutations_ – i.e., the group of all permutations and reflections of the
standard orthonormal basis $\\{e_{1},\ldots,e_{n}\\}$. For interested readers,
this group is the semidirect product
$\operatorname{P}(n)\ltimes\operatorname{Z}(n)$, and it 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)$. Two signed perm-reps
$\rho,\rho^{\prime}$ are said to be _equivalent_ or _conjugate_ if there
exists $A\in\mathrm{PZ}(n)$ such that $\rho^{\prime}(g)=A\rho(g)A^{-1}\forall
g\in G$– i.e., if they are related by a change of basis. A signed perm-rep
$\rho$ is said to be _reducible_ if it is equivalent to a direct sum of signed
perm-reps of smaller degrees– i.e., if there exists $A\in\mathrm{PZ}(n)$ such
that $A\rho(\cdot)A^{-1}$ is simultaneously block-diagonal with at least two
blocks. The signed perm-rep is said to be _irreducible_ (signed perm-irrep for
short) otherwise.222A useful characterization is that a signed perm-rep $\rho$
is irreducible iff for every $i,j=1,\ldots,n$, there exists $g\in G$ such that
$\rho(g)e_{i}=\pm e_{j}$.

The signed perm-irreps of $G$ can be completely classified up to equivalence
in terms of certain pairs of subgroups of $G$ (Agrawal and Ostrowski, 2022,
Thm. 1). For every pair of subgroups $K\leq H\leq G$, $|H:K|\leq 2$, define
the signed perm-rep $\rho_{HK}:G\mapsto\mathrm{PZ}(n)$, $n=|G/H|$, to be the
induced representation

$\rho_{HK}=I_{H}^{G}\sigma,\mbox{ where
}\sigma:H\mapsto\\{-1,1\\}\mid\ker(\sigma)=K.$

Then $\rho_{HK}$ is irreducible, and every signed perm-irrep is equivalent to
some $\rho_{HK}$. Moreover, $\rho_{HK}$ and $\rho_{H^{\prime}K^{\prime}}$ are
equivalent iff $(H^{\prime},K^{\prime})=(gHg^{-1},gKg^{-1})$ for some $g\in
G$. We can thus always understand a “signed perm-irrep” to mean $\rho_{HK}$
for some appropriate subgroups $H$ and $K$, and conversely we will always
understand the notation $\rho_{HK}$ to mean the above construction.

For a more explicit but equivalent construction of $\rho_{HK}$, let
$\\{g_{1},\ldots,g_{n}\\}$ be a transversal of $G/H$. If $|H:K|=1$ (i.e.,
$H=K$), then we define $\rho_{HK}(g)e_{i}=e_{j}$ iff $gg_{i}H=g_{j}H$; i.e.,
$\rho_{HK}$ is just defined in terms of its permutation action on $G/H$. On
the other hand, suppose $|H:K|=2$. Then we have the quotient group
$H/K=\\{K,hK\\}$. Define $e_{-i}=-e_{i}$ and $g_{-i}=g_{i}h$ for
$i\in\\{1,\ldots,n\\}$. Then we define $\rho_{HK}(g)e_{i}=e_{j}$ iff
$gg_{i}K=g_{j}K$ for $i,j\in\\{\pm 1,\ldots,\pm n\\}$. Intuitively,
$\rho_{HK}$ still acts on $G/H$ via permutations; however, if the cosets in
$H/K$ are swapped under this action, then a sign flip is incurred in the
representation. For more details on these constructions, see Sec. 2 of Agrawal
and Ostrowski (2022).

Every signed perm-irrep is either type 1 or type 2. A signed perm-rep is _type
1_ if it is equivalent to an _ordinary permutation representation_ (ordinary
perm-rep) $\pi:G\mapsto\operatorname{P}(n)$; it is _type 2_ otherwise. Sign
flips in a type 1 signed perm-rep are thus artifacts as they can be removed by
a change of basis. An important characterization is that a signed perm-irrep
$\rho_{HK}$ has type $|H:K|$.

Finally, as general notation, throughout this paper let $I_{n}$ denote the
$n\times n$ identity matrix and $\vec{0}_{n}$ (resp. $\vec{1}_{n}$) the
$n$-dimensional vector with all elements $0$ (resp. $1$).

###  2.2 Central hypothesis

Previous works in the equivariant deep learning literature, to our knowledge,
primarily employ type 1 signed perm-reps—and in particular, ordinary perm-
reps—to enforce layerwise $G$-equivariance in ReLU networks. The goal of this
paper is to show that type 2 signed perm-reps can also be implemented for this
purpose (although it is trickier as it requires layers to be coupled), and the
central hypothesis of this work is that type 2 signed perm-reps can indeed be
beneficial for DNN performance. In this section, we motivate this hypothesis
with theory and discussions that suggest that type 2 signed perm-reps can help
boost expressive power without necessarily sacrificing generalization power.
We note that the CReLU activation function has previously been used to
incorporate certain type 2 signed perm-reps (see Sec. 1), but we take a top-
down approach that lets us study all such architectures.

Our first theorem states that two inequivalent signed perm-irreps induced from
different reps of the same subgroup $H\leq G$ correspond to $G$-equivariant
matrices that are in a sense orthogonal.333All proofs can be found in the
supplementary material.

######  Theorem 1 (Corollary to Prop. 6 of Agrawal and Ostrowski (2022))

Let $\rho_{HK_{1}}$ and $\rho_{HK_{2}}$ be inequivalent signed perm-irreps of
degree $n$ of $G$. For each $i\in\\{1,2\\}$, let $W_{i}\in\mathbb{R}^{n\times
m}$ such that $\rho_{HK_{i}}(g)W_{i}=W_{i}g\forall g\in G$. Then there exists
$P\in\operatorname{P}(n)$ such that

$\operatorname{diag}(PW_{1}W_{2}^{\top})=0.$

Theorem 1 will be important in Sec. 4, where we will use it to construct a key
baseline $G$-DNN architecture for our experiments. We discuss Thm. 1 further
in the context of an example group $G$ later in this section.

Our second theorem describes how a signed perm-rep can be “unraveled” into an
ordinary perm-rep of twice the degree, by essentially mapping sign flips to
transpositions of two dimensions. This unraveling is particularly meaningful
for type 2 signed perm-irreps, which remain irreducible even after unraveling;
in contrast, type 1 signed perm-irreps merely unravel into reducible copies of
themselves. Let $\mathcal{H}$ be the elementwise Heaviside step function,
where we let $\mathcal{H}(0)=0$.

###### Theorem 2

Let $\rho:G\mapsto\mathrm{PZ}(n)$ be a signed perm-rep. Then:

  1. (a)

The function444In the expression for $\pi_{\rho}$, the operation $\otimes$ is
the Kronecker product.

$\pi_{\rho}(g)=\mathcal{H}\left(\begin{bmatrix}1&-1\\\
-1&1\end{bmatrix}\otimes\rho(g)\right)$

defines an ordinary perm-rep $\pi_{\rho}:G\mapsto\operatorname{P}(2n)$.

  2. (b)

Let $W\in\mathbb{R}^{n\times m}$ such that $\rho(g)W=Wg\forall g\in G$. Then

$\pi_{\rho}(g)\begin{bmatrix}W\\\ -W\end{bmatrix}=\begin{bmatrix}W\\\
-W\end{bmatrix}g\forall g\in G.$

  3. (c)

Suppose $\rho$ is irreducible. Then $\pi_{\rho}$ is irreducible iff $\rho$ is
type 2.

  4. (d)

Suppose $\rho$ is type 2 irreducible and $\rho=\rho_{HK}$. Then
$\pi_{\rho}=\rho_{KK}$.

$W_{(6,1)}$

$W_{(3,1)}$

$W_{(3,2)}$

Figure 1:  Weightsharing patterns of equivariant matrices for three example
signed perm-irreps of the group $G$ of $6\times 6$ cyclic permutation matrices
(see main text for details). 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 matrices).

To understand Thms. 1-2 and their implications for the expressive and
generalization powers of a $G$-DNN with type 2 signed perm-reps, consider the
example group $G$ of all $6\times 6$ cyclic permutation matrices (see Sec. 4.1
of Agrawal and Ostrowski (2022) for a detailed discussion of this example).
For this example, the signed perm-irreps of $G$ are completely characterized
in terms of their degrees and types; we thus let $\rho_{(n,t)}$ denote the
irrep $\rho_{HK}$ where $n=\frac{6}{|H|}$ is the degree and $t=|H:K|$ is the
type. Alternatively, if $G\cong\mathbb{Z}_{6}$, then $\rho_{(n,t)}$ denotes
the irrep $\rho_{HK}$ where $H\cong\mathbb{Z}_{\frac{6}{n}}$ and
$K\cong\mathbb{Z}_{\frac{6}{nt}}$. In this notation, the signed perm-irreps of
$G$ are $\rho_{(6,1)}$, $\rho_{(3,1)}$, $\rho_{(3,2)}$, $\rho_{(2,1)}$,
$\rho_{(1,1)}$, and $\rho_{(1,2)}$.

For each irrep $\rho_{(n,t)}$, let $W_{(n,t)}\in\mathbb{R}^{n\times m}$ such
that $\rho_{(n,t)}W_{(n,t)}=W_{(n,t)}g\forall g\in G$. The irreps
$\rho_{(3,1)}$ and $\rho_{(3,2)}$ satisfy the hypotheses of Thm. 1, and indeed
we see—in terms of their weightsharing patterns—each row of $W_{(3,1)}$ is
orthogonal to the corresponding row of $W_{(3,2)}$ (Fig. 1). In practice, this
means if we were given a dataset sampled from a $G$-invariant shallow neural
network ($G$-SNN)

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

with $W=W_{(3,2)}$ as the ground truth weight matrix, then a $G$-SNN with
weight matrix with the weightsharing pattern of $W_{(3,1)}$ would not have the
expressive power to fit the ground truth, regardless of the number of
“channels” (i.e., independent copies of $W_{(3,1)}$) used. With a limited
budget of three hidden neurons per channel, type 2 signed perm-reps thus help
to increase expressive power.

On the other hand, if we double our budget of hidden neurons, then Thm. 2
suggests $W_{(6,1)}$ has the capacity to express $W_{(3,2)}$; indeed, if we
constrain the first row of $W_{(6,1)}$ to have the same weightsharing pattern
as the first row of $W_{(3,2)}$ (Fig. 1), then $W_{(6,1)}$ effectively becomes
equivalent to $W_{(3,2)}$. The problem is, however, that $W_{(6,1)}$ can
similarly be constrained to match $W_{(3,1)}$, and with probability $1$ (e.g.,
under a Gaussian), $W_{(6,1)}$ is equivalent to neither $W_{(3,1)}$ nor
$W_{(3,2)}$. Thus, while this approach allows us to use a type 1 signed perm-
rep with the capacity to express the ground truth, it comes at the cost of
generalization power, as $W_{(6,1)}$ may have multiple configurations
consistent with a finite training set.

To ensure these concepts are made clear, we present one more very simple
example. For any even input dimension $n\geq 2$, consider the $G$-SNN
architectures

$f_{i}(x)=\vec{1}^{\top}\operatorname{ReLU}(W_{i}x)-\frac{1}{2}\vec{1}^{\top}W_{i}x\forall
i\in\\{1,2,3\\},$

where

$\displaystyle W_{1}$
$\displaystyle=\begin{bmatrix}u&u&\cdots&u&u\end{bmatrix}$ $\displaystyle
W_{2}$ $\displaystyle=\begin{bmatrix}u&-u&\cdots&u&-u\end{bmatrix}$
$\displaystyle W_{3}$
$\displaystyle=\begin{bmatrix}u&v&\cdots&u&v\end{bmatrix},$

and where $\vec{1}$ is a vector of $1$’s of the appropriate length (either 1
or 2). Here $G$ is the group of cyclic permutations on $n$ elements. To fix a
global scale, without loss of generality, let us set $u=1$. Now suppose we
take the type 2 architecture $f_{2}$ as the ground truth, and draw a sample
dataset. We then observe that the type 1 architecture $f_{1}$ does not have
the capacity to fit this dataset; in fact, $f_{1}$ and $f_{2}$ have orthogonal
level sets. On the other hand, the unraveled architecture $f_{3}$ does have
the capacity to fit the data, but it is a weaker model compared to $f_{2}$
(with respect to this dataset) as it must learn $v=-u$ from the data.

In sum, type 2 signed perm-reps may help to refine the range of expressive
powers available to us; they help to express functions different from type 1
signed perm-reps of the same degree without sacrificing generalization power
the way larger type 1 signed perm-reps would.

##  3 $G$-invariant deep neural networks

###  3.1 Parameterization redundancies

In this section, we define densely connected deep neural networks, or simply
deep neural networks, and we list some of the so-called parameterization
redundancies of such networks that will be key to enforcing $G$-invariance.
All notation introduced here will persist throughout the paper.

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be a _deep neural network_ (DNN) of
depth $d$ constructed as follows: Let $\\{n_{1},\ldots,n_{d+1}\\}$ be a set of
$d+1$ positive integers where555Note the input dimension $n_{1}=m$ is the same
number as the degree of the matrix group $G$ in Sec. 2. $n_{1}=m$ and
$n_{d+1}=1$, and let $N_{i}=n_{1}+\cdots+n_{i}$ for every
$i\in\\{1,\ldots,d\\}$. Let $W^{(i)}\in\mathbb{R}^{n_{i+1}\times N_{i}}$ and
$b^{(i)}\in\mathbb{R}^{n_{i+1}}$ for every $i\in\\{1,\ldots,d\\}$. Define
$f^{(1)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{n_{1}}$ by $f^{(1)}(x)=x$. For every
$i\in\\{1,\ldots,d-1\\}$, define
$f^{(i+1)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{N_{i+1}}$ by

$f^{(i+1)}(x)=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}.$ (3)

Then, let $f(x)=W^{(d)}f^{(d)}(x)+b^{(d)}$.

We thus define a DNN to be a feedforward ReLU network having all possible
_skip connections_. We call the $W^{(i)}$ _weight matrices_ , their rows
_weight vectors_ , and the $b^{(i)}$ _bias vectors_. The numbers
$n_{2},\ldots,n_{d}$ are the widths of the hidden layers, and the numbers
$N_{2},\ldots,N_{d}$ are the cumulative widths accounting for the skip
connections. Note the traditional definition of a DNN can be recovered by
setting all skip connections to zero.

Our first proposition below establishes a set of parameterization redundancies
(i.e., reparameterizations of the DNN leaving the input-output function
invariant) enjoyed by the above DNN architecture. For every positive integer
$n$, let $\operatorname{C}(n)$ be the group of $n\times n$ diagonal matrices
with positive diagonal entries.

###### Proposition 3

Let $i\in\\{1,\ldots,d-1\\}$, $C\in\operatorname{C}(n_{i+1})$,
$P\in\operatorname{P}(n_{i+1})$, and $Z\in\operatorname{Z}(n_{i+1})$. Then the
DNN $f$ is invariant under the transformation

$\displaystyle W^{(i)}$ $\displaystyle\rightarrow CPZW^{(i)}$ $\displaystyle
b^{(i)}$ $\displaystyle\rightarrow CPZb^{(i)}$ $\displaystyle W^{(i+1)}$
$\displaystyle\rightarrow
W^{(i+1)}\begin{bmatrix}(CP)^{-1}&\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}$ $\displaystyle b^{(i+1)}$ $\displaystyle\rightarrow
b^{(i+1)}+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\ 0\end{bmatrix}.$

Proposition 3 is the key to understanding how signed perm-reps can be used in
$G$-DNNs. Specificly, if we want the parameters $(W^{(i)},b^{(i)})$ of the
$i$th layer to transform by a signed perm-rep, then the parameters
$(W^{(i+1)},b^{(i+1)})$ of the subsequent layer must transform as in Prop. 3
to compensate and maintain invariance. This idea is the basis of the next
section.

###  3.2 $G$-invariant architectures

The following lemma gives a sufficient condition for each $f^{(i)}$ (the
subnetwork comprising the first $i-1$ layers of $f$ and acting as input of the
$i$th layer) to be $G$-equivariant; the sufficient condition takes the form of
equivariant constraints on the network parameters.

###### Lemma 4

Let $\\{\rho^{(1)},\ldots,\rho^{(d)}\\}$ be a set of signed perm-reps
$\rho^{(i)}:G\mapsto\mathrm{PZ}(n_{i+1})$ with $\rho^{(d)}$ the trivial rep.
For each $i\in\\{1,\ldots,d\\}$, let
$\pi^{(i)}:G\mapsto\operatorname{P}(n_{i+1})$ and
$\zeta^{(i)}:G\mapsto\operatorname{Z}(n_{i+1})$ be the unique functions such
that $\rho^{(i)}(g)=\pi^{(i)}(g)\zeta^{(i)}(g)\forall g\in G$. Let
$\\{\psi^{(1)},\ldots,\psi^{(d)}\\}$ be a set of reps
$\psi^{(i)}:G\mapsto\operatorname{GL}(N_{i})$ defined as:

$\displaystyle\psi^{(1)}(g)$ $\displaystyle=g$ $\displaystyle\psi^{(i+1)}(g)$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^{(i)}(g)W^{(i)})\\\
0&\psi^{(i)}(g)\end{bmatrix}\forall i\in\\{1,\ldots,d-1\\}.$

Suppose $\rho^{(i)}(g)W^{(i)}=W^{(i)}\psi^{(i)}(g)$ and
$\rho^{(i)}(g)b^{(i)}=b^{(i)}$ for all $g\in G$ and $i\in\\{1,\ldots,d\\}$.
Then $f^{(i)}(gx)=\psi^{(i)}(g)f^{(i)}(x)$ for all $g\in G$,
$x\in\mathbb{R}^{m}$, and $i\in\\{1,\ldots,d\\}$.

Since $f^{(d)}(gx)=\psi^{(d)}f^{(d)}(x)$ and $W^{(d)}\psi^{(d)}(g)=W^{(d)}$
for all $g\in G$ and $x\in\mathbb{R}^{m}$, then we see that Lemma 4 gives a
sufficient condition for $f$ to be a _$G$ -invariant deep neural network_
($G$-DNN). Note the sequence of signed perm-reps
$\\{\rho^{(1)},\ldots,\rho^{(d)}\\}$ completely determines the $G$-DNN
architecture (i.e., depth, number of hidden neurons per layer, and
weightsharing patterns), and hence we will also refer to such sequences of
reps as _$G$ -DNN architectures_. Observe that the rep $\psi^{(i)}$ depends on
the weight matrix $W^{(i-1)}$, and hence the equivariance condition on
$W^{(i)}$ introduces a coupling between $W^{(i-1)}$ and $W^{(i)}$. This
coupling makes it difficult to implement the equivariance constraints on the
weight matrices directly, and we thus proceed to find a reparameterization
admitting uncoupled equivariant weight matrices. To do this, we first state
another lemma below, which gives an explicit formula for the reps $\psi^{(i)}$
(as opposed to a recursive formula) and shows each $\psi^{(i)}$ to be
equivalent to a direct sum of layerwise reps.

For every $i\in\\{1,\ldots,d\\}$, decompose $W^{(i)}$ into blocks as

$W^{(i)}=\begin{bmatrix}W^{(i)}_{i}&W^{(i)}_{i-1}&\cdots&W^{(i)}_{1}\end{bmatrix},$

where $W^{(i)}_{j}\in\mathbb{R}^{n_{i+1}\times n_{j}}$. Define the block
matrix

$A^{(i)}=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}_{i}&-\frac{1}{2}W^{(i)}_{i-1}&\cdots&-\frac{1}{2}W^{(i)}_{1}\\\
0&I_{n_{i}}&-\frac{1}{2}W^{(i-1)}_{i-1}&\cdots&-\frac{1}{2}W^{(i-1)}_{1}\\\
0&0&I_{n_{i-1}}&\cdots&-\frac{1}{2}W^{(i-2)}_{1}\\\ 0&0&0&\ddots&\vdots\\\
0&0&0&0&I_{n_{1}}\end{bmatrix}.$

Define the rep $\Pi^{(i)}:G\mapsto\operatorname{O}(N_{i+1})$ by

$\Pi^{(i)}(g)=\operatorname{diag}(\pi^{(i)}(g),\pi^{(i-1)}(g),\ldots,\pi^{(1)}(g),g).$

###### Lemma 5

For every $i\in\\{1,\ldots,d-1\\}$, we have666The notation $A^{(i)-1}$ is
shorthand for $(A^{(i)})^{-1}$, the matrix inverse of $A^{(i)}$.

$\psi^{(i+1)}(g)=A^{(i)-1}\Pi^{(i)}(g)A^{(i)}\forall g\in G.$

Let $\pi^{(0)}:G\mapsto\operatorname{P}(n_{1})$ be the identity rep
$\pi^{(0)}(g)=g$, and let $A^{(0)}=I_{n_{1}}$. Then Lemma 5 holds for $i=0$ as
well.

We are now ready to state this section’s key theorem, which gives a
reparameterization of a $G$-DNN in which it admits uncoupled equivariant
weight matrices.

###### Theorem 6

Let $f$ be $G$-invariant, with its parameters
$\\{(W^{(1)},b^{(1)}),\ldots,(W^{(d)},b^{(d)})\\}$ satisfying the conditions
of Lemma 4 with respect to the signed perm-reps
$\\{\rho^{(1)},\ldots,\rho^{(d)}\\}$.

  1. (a)

For every $i\in\\{1,\ldots,d\\}$, there exists
$V^{(i)}\in\mathbb{R}^{n_{i+1}\times N_{i}}$ with block structure

$V^{(i)}=\begin{bmatrix}V^{(i)}_{i}&V^{(i)}_{i-1}&\cdots&V^{(i)}_{1}\end{bmatrix}$

where $V^{(i)}_{j}\in\mathbb{R}^{n_{i+1}\times n_{j}}$ such that

$\displaystyle\rho^{(i)}(g)V^{(i)}_{j}$
$\displaystyle=V^{(i)}_{j}\pi^{(j-1)}(g)\forall g\in G$ $\displaystyle
W^{(i)}$ $\displaystyle=V^{(i)}A^{(i-1)}.$

  2. (b)

For every $i\in\\{1,\ldots,d\\}$, define
$g^{(i)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{n_{i+1}}$ by
$g^{(i)}(x)=W^{(i)}f^{(i)}(x)$ and
$h^{(i)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{N_{i}}$ by
$h^{(i)}(x)=A^{(i-1)}f^{(i)}(x)$. Then we have the recursion

$\displaystyle g^{(i)}(x)$ $\displaystyle=V^{(i)}h^{(i)}(x)\forall
i\in\\{1,\ldots,d\\}$ $\displaystyle h^{(i+1)}(x)$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(x)+b^{(i)})-\frac{1}{2}g^{(i)}(x)\\\
h^{(i)}(x)\end{bmatrix}\forall i\in\\{1,\ldots,d-1\\}.$

The $V^{(i)}$ are the latent weight matrices, and in Thm. 6 (a) we see that
each $V^{(i)}$ satisfies a linear equivariant condition that is easy to
implement. The apparent weight matrices $W^{(i)}$ can then be reconstructed as
$W^{(i)}=V^{(i)}A^{(i-1)}$. In practice, however, there is no need to perform
this reconstruction; instead, we implement the recursion in Thm. 6 (b) as the
forward pass of the $G$-DNN, where the final network output is
$f(x)=g^{(d)}(x)+b^{(d)}$. Observe that the recursion is given directly in
terms of the $V^{(i)}$ as opposed to the $W^{(i)}$. This recursion leverages
the block-triangular structure of $A^{(i-1)}$ in the transformation
$W^{(i)}=V^{(i)}A^{(i-1)}$. We describe a concrete implementation of the
equivariance condition and the forward pass of the $G$-DNN in App. B.2.1.

###  3.3 Admissible architectures

Theorem 6 tells us how to construct a $G$-DNN, but it first requires us to
select a sequence of reps or “architecture” $\rho^{(1)},\ldots,\rho^{(d)}$.
Selecting the optimal sequence is the problem of $G$-invariant neural
architecture design, which is beyond the scope of this work. At the very
least, however, we would like to avoid sequences that correspond to
“degenerate” network architectures. In particular, we require that (1) every
row of each weight matrix $W^{(i)}$ be nonzero and (2) no two rows of the
augmented weight matrix $[W^{(i)}\mid b^{(i)}]$ be parallel. The first
condition ensures there are no neurons disconnected from all previous layers,
and the second condition ensures no two hidden neurons in a given layer can be
combined into a single hidden neuron or skip connection. We call a sequence of
reps $\rho^{(1)},\ldots,\rho^{(d)}$ an _admissible architecture_ if it admits
a $G$-DNN with weight matrices satisfying these two conditions. Below, Thm. 7
provides a characterization of admissible architectures that we implement in
practice. First, however, we introduce additional notions and notation.

For every $A\in\mathbb{R}^{m\times m}$, let $\operatorname{st}_{G}(A)$ be the
stabilizer subgroup

$\operatorname{st}_{G}(A)=\\{g\in G:gA=A\\},$

and for every finite orthogonal matrix group $\Gamma$, let $P_{\Gamma}$ be the
orthogonal projection operator onto the vector subspace pointwise-invariant
under the action of $\Gamma$:

$P_{\Gamma}=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}g.$

Let $\mathcal{S}(G)$ denote the set of all subgroups of $G$. Then, we define
the function $\theta:\\{(H,K,J)\in\mathcal{S}(G)^{3}:|H:K|\leq
2\\}\mapsto\mathcal{S}(G)$ by

$\displaystyle\theta(H,K,J)$
$\displaystyle=\pi_{J}^{-1}[\operatorname{st}_{\pi_{J}(G)}(P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J}(H)})]$
$\displaystyle=\\{g\in
G:\pi_{J}(g)(P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J}(H)}\\},$

where the ordinary perm-rep $\pi_{J}:G\mapsto\operatorname{P}(|G/J|)$ is
defined as usual– i.e., defined to be equivalent to the action of $G$ on
$G/J$. Note $\pi_{J}$ is defined only up to conjugation by a perm-matrix,
since no ordering on the cosets in $G/J$ is specified. It turns out, however,
that $\theta$ is invariant under conjugation of $\pi_{J}$, and more generally
$\theta$ is invariant and equivariant with respect to certain conjugations of
the input subgroups (see Prop. 8 in App. B.3).

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be a $G$-DNN with sequence of signed
perm-reps $\rho^{(1)},\ldots,\rho^{(d)}$. For every $i\in\\{1,\ldots,d\\}$,
the signed perm-rep $\rho^{(i)}$ admits the following decomposition into
irreducibles:

$\rho^{(i)}=\bigoplus_{j=1}^{r^{(i)}}k^{(i)}_{j}\rho^{(i)}_{j},\quad\rho^{(i)}_{j}=\rho^{(i)}_{H^{(i)}_{j}K^{(i)}_{j}}.$

The irreps $\rho^{(i)}_{1},\ldots,\rho^{(i)}_{r^{(i)}}$ are inequivalent, and
each $k^{(i)}_{j}$ is a positive integer where we define the notation

$k^{(i)}_{j}\rho^{(i)}_{j}=\bigoplus_{k=1}^{k^{(i)}_{j}}\rho^{(i)}_{j}.$

We say the $i$th layer of the $G$-DNN $f$ has $r^{(i)}$ distinct _irreps_ and
$k^{(i)}_{1}+\cdots+k^{(i)}_{r^{(i)}}$ _channels_. Now for every
$i\in\\{1,\ldots,d\\}$, we define the functions
$\phi^{(i)}:\\{(H,K)\in\mathcal{S}(G)^{2}:|H:K|\leq 2\\}\mapsto\mathcal{S}(G)$
recursively by

$\displaystyle\phi^{(1)}(H,K)$
$\displaystyle=\operatorname{st}_{G}(P_{K}-(|H:K|-1)P_{H})$
$\displaystyle\phi^{(i+1)}(H,K)$
$\displaystyle=\phi^{(i)}(H,K)\cap\bigcap_{j=1}^{r^{(i)}}\theta(H,K,H^{(i)}_{j})\forall
i\in\\{1,\ldots,d-1\\}.$

Following from the equivariance of $\theta$ (Prop. 8) and that inner
automorphisms respect subgroup intersection, we have the important property
that each $\phi^{(i)}$ is equivariant with respect to pairwise conjugation:

$\phi^{(i)}(gHg^{-1},gKg^{-1})=g\phi^{(i)}(H,K)g^{-1}\forall g\in G.$

We are ready to state the theorem characterizing single-channel admissible
architectures; note the following is a generalization of Thm. 4a of Agrawal
and Ostrowski (2022).

###### Theorem 7

Maintain the notation introduced in the last paragraph, and suppose
$k^{(i)}_{j}=1\forall i,j$ (single-channel architecture). Then the
architecture777By definition of $G$-DNN architecture, $\rho^{(d)}$ is trivial;
see Lemma 4 and the discussion immediately proceeding it.
$\\{\rho^{(1)},\ldots,\rho^{(d)}\\}$ is admissible iff the following
conditions hold:

  1. 1.

$\phi^{(i)}(H^{(i)}_{j},K^{(i)}_{j})=K^{(i)}_{j}\forall i,j$.

  2. 2.

If $H^{(1)}_{j}=G$ for some $j$, then $P_{G}\neq 0$.888This condition is
trivially satisfied if $G$ is a permutation matrix group.

Theorem 7 gives us a practical way to build admissible $G$-DNN architectures
layer-by-layer as follows: Suppose we have already built the first $i$ layers–
i.e., we have selected the signed perm-reps $\rho^{(1)},\ldots,\rho^{(i)}$
satisfying Thm. 7. Then the function $\phi^{(i+1)}$ is defined. We enumerate
all signed perm-irreps $\rho_{HK}$, up to equivalence,999The equivariance of
$\phi$ is why enumeration of the signed perm-irreps only up to equivalence is
sufficient. such that $\phi(H,K)=K$, and we then select a subset to comprise
$\rho^{(i+1)}$. In terms of implementation, the computation of
$\phi^{(i)}(H,K)$ boils down to the computation of $\theta(H,K,H^{(i-1)}_{j})$
for each $j$, which can be accomplished using Alg. 2 (see App. B.3 for
details). We should think of the outputs $\theta(H,K,J)$ as entries of a
precomputed table with a row for each $(H,K)$ (up to pairwise conjugation) and
a column for each $J$ (up to conjugation). We give additional implementation
details in the next section, including how we accomodate multiple input and
output channels per layer.

To gain some intuition about Thm. 7, we briefly consider its application to
$G$-SNN (i.e., depth $d=2$) architectures, which are completely characterized
in terms of the single signed perm-rep by which the weight matrix in the first
layer transforms. In this case, Thm. 7 reduces to Thm. 4 (a) of Agrawal and
Ostrowski (2022); a signed perm-rep $\rho_{HK}$ is admissible for a $G$-SNN
iff $\phi^{(1)}(H,K)=K$, or more explicitly,

$\operatorname{st}_{G}(P_{K}-(|H:K|-1)P_{H})=K.$

Here the weight vectors of the $G$-SNN are $\\{gw:gH\in G/H\\}$, where $w$ is
fixed under $K$ and flips sign under $H\setminus K$. The weight vectors are
pairwise nonparallel if $\operatorname{st}_{G}(w)=K$; if, however,
$\operatorname{st}_{G}(w)>K$, then the $G$-orbit of $w$ is smaller than the
number of weight vectors, forcing some weight vectors to be equal up to sign.
Theorem 7 serves to eliminate such degenerate architectures.

Table 1:  Ratio of the number of admissible $G$-DNN architectures to the total number of architectures for every depth and every group $G$, $|G|=8$, up to isomorphism. Only architectures corresponding to sequences of irreps of strictly decreasing degree are considered.  Depth | $C_{8}$ | $C_{2}\times C_{4}$ | $C_{2}^{3}$ | $D_{4}$ | $Q_{8}$
---|---|---|---|---|---
2 | 5/5 | 8/15 | 11/43 | 14/21 | 9/9
3 | 8/8 | 30/62 | 93/434 | 65/104 | 20/20
4 | 4/4 | 48/48 | 392/392 | 84/84 | 12/12

The number of admissible architectures can be significantly less than the
total number of architectures. For example, we consider one particular
permutation representation of every group of order $8$ up to isomorphism,
following the constructions described in App. C.1 of Agrawal and Ostrowski
(2022). For each group, we only count the architectures corresponding to
sequences of irreps of strictly decreasing degree, and we report the fraction
of these that are admissible (Table 1). Observe that the reduction from the
total number of architectures to only the admissible ones is often
significant, which could be exploited perhaps in a future implementation of
$G$-NAS. Note also that all architectures of maximum depth are admissible; we
speculate this is because as depth increases and each new weight matrix
$W^{(i)}$ grows in width (due to more skip connections to previous layers),
the conditions under which two weight vectors are parallel become harder to
satisfy. A complete answer, however, is left for future investigation.

###  3.4 Additional remarks

##### Channels

The $G$-DNN supports multiple channels in a way generalizing the notion from
traditional convolutional neural networks. As already mentioned in Sec. 3.3,
the $i$th layer of the $G$-DNN $f$ is said to have $k^{(i)}_{j}$ output
channels or copies of the irrep $\rho^{(i)}_{j}$ and $k^{(i-1)}_{j}$ input
channels from the irrep $\rho^{(i-1)}_{j}$. As a simpler case, suppose
$\rho^{(i)}$ contains the same number $k^{(i)}$ of copies of each of its
constituant irreps, and suppose the input $x$ has $k^{(0)}$ channels. Then the
$i$th layer can be said to have $k^{(i)}$ output channels and $k^{(i-1)}$
input channels. In practice, we implement the $G$-DNN assuming only one copy
of each irrep $\rho^{(i)}_{j}$, and then we regard each element of the input
$x$ as a $k^{(0)}$-dimensional vector and each element of the latent weight
matrix block $V^{(i)}_{j}$ (see Thm. 6 (a) for notation) as a $k^{(i)}\times
k^{(j-1)}$ matrix.

##### Batch normalization

It is possible to apply batch normalization (batchnorm) immediately after ReLU
in a $G$-DNN without breaking $G$-invariance. That batchnorm is compatible
with $G$-DNNs, and in particular type 2 signed perm-reps, out-of-the-box is
not obvious, and we verify the compatibility in Prop. 10 (see App. B.4). The
proof relies on the facts that (1) the first $n_{i}$ columns of $W^{(i)}$ and
$V^{(i)}$ are equal and (2) the first $n_{i}$ columns of $V^{(i)}$ sum to zero
if $\rho^{(i)}$ is a type 2 signed perm-irrep.

##  4 Examples

###  4.1 Concatenated ReLU

$G$-invariant architectures with signed perm-reps have previously been
constructed without skip connections (Cohen and Welling, 2017) by replacing
ReLU with the CReLU activation function defined in Eq. (2). The upshot is that
for every signed perm-rep $\rho:G\mapsto\mathrm{PZ}(n)$, CReLU enjoys the
equivariance property

$\operatorname{CReLU}(\rho(g)x)=\pi_{\rho}(g)\operatorname{CReLU}(x)\forall
g\in G,x\in\mathbb{R}^{n},$

where $\pi_{\rho}$ is the unraveled ordinary perm-rep appearing in Thm. 2;
CReLU architectures are thus compatible with signed perm-reps. The following
example, however, establishes that CReLU architectures are strictly special
cases of the $G$-DNN architectures presented in this paper.

###### Example 1

Let $f:\mathbb{R}^{m}\mapsto\mathbb{R}$ be a DNN of the form

$f(x)=U^{(d)}\operatorname{CReLU}(U^{(d-1)}\cdots\operatorname{CReLU}(U^{(1)}x)\cdots),$

where $U^{(1)}\in\mathbb{R}^{n_{2}\times n_{1}}$ and
$U^{(i)}\in\mathbb{R}^{n_{i+1}\times 2n_{i}}\forall i\in\\{2,\ldots,d\\}$ are
equivariant weight matrices satisfying

$\displaystyle\rho^{(1)}(g)U^{(1)}$ $\displaystyle=U^{(1)}\pi^{(0)}(g)\forall
g\in G$ $\displaystyle\rho^{(i)}(g)U^{(i)}=U^{(i)}\pi_{\rho^{(i-1)}}(g)\forall
g\in G,i\in\\{2,\ldots,d\\},$

where $\pi_{\rho^{(i-1)}}$ is the unraveling of $\rho^{(i-1)}$ as defined in
Thm. 2. Then $f$ admits an expression as a $G$-DNN of depth $d$ whose latent
weight matrices are given by the recursion

$\displaystyle V^{(1)}$ $\displaystyle=U^{(1)}$ $\displaystyle V^{(i+1)}$
$\displaystyle=\begin{bmatrix}U^{(i+1)}_{1}+U^{(i+1)}_{2}&\frac{1}{2}(U^{(i+1)}_{1}-U^{(i+1)}_{2})V^{(i)}\end{bmatrix}\forall
i\in\\{1,\ldots,d-1\\}.$

Although Ex. 1 holds for any sequence of signed perm-reps
$\rho^{(1)},\ldots,\rho^{(d)}$ with $\rho^{(d)}$ trivial, the primary case of
interest is when each $\rho^{(i)}$, $i\leq d-1$, is a direct sum only of type
2 signed perm-irreps; otherwise, if we had a subset of weight vectors that
transformed by a type 1 signed perm-irrep, then we would apply ordinary RELU
to their respective preactivations instead of CReLU. This is why it is also
sufficient to consider CReLU networks without bias vectors, as type 2 signed
perm-irreps constrain bias vectors to be zero.

Table 2:  Ratio of the number of admissible CReLU architectures to the total number of architectures for every depth and every group $G$, $|G|=8$, up to isomorphism. Only architectures corresponding to sequences of irreps of strictly decreasing degree are considered.  Depth | $C_{8}$ | $C_{2}\times C_{4}$ | $C_{2}^{3}$ | $D_{4}$ | $Q_{8}$
---|---|---|---|---|---
2 | 5/5 | 8/15 | 11/43 | 14/21 | 9/9
3 | 8/8 | 30/62 | 88/434 | 65/104 | 20/20
4 | 4/4 | 34/48 | 238/392 | 66/84 | 12/12

Example 1 implies that the $G$-DNN architectures introduced in this paper are
at least as powerful as ($G$-invariant) CReLU-based architectures, whose
utility has already been demonstrated in the literature (Shang et al., 2016;
Cohen and Welling, 2017). Moreover, we recover CReLU architectures only when
the latent weight matrices $V^{(i)}$ take a very special form; this suggests
that there may exist $G$-DNN architectures that cannot be constructed with
CReLU alone. To investigate this possibility, we count the numbers of
_admissible_ CReLU architectures for various groups following the same setup
used to obtain the results in Table 1. As before, we consider every sequence
of signed perm-irreps $\rho_{H^{(1)}K^{(1)}},\ldots,\rho_{H^{(d)}K^{(d)}}$ of
strictly decreasing degree terminating with the trivial rep. In contrast to
$G$-DNNs, however, the criterion for a CReLU architecture to be admissible is
much simpler; since there are no explicit skip connections, then the function
$\phi^{(i+1)}$ in Thm. 7 no longer depends recursively on $\phi^{(i)}$. The
resulting condition for a CReLU architecture with signed perm-irreps
$\rho_{(H^{(1)}K^{(1)}},\ldots,\rho_{H^{(d)}K^{(d)}}$ to be admissible is

$\theta(H^{(i+1)},K^{(i+1)},H^{(i)})=K^{(i+1)}\forall i\in\\{1,\ldots,d-1\\}.$

Based on this, we report fractions of admissible CReLU architectures (Table 2)
in direct analogy to Table 1. At depth $4$, there are fewer admissible CReLU
architectures than admissible $G$-DNN architectures.

Table 3:  Numbers of admissible CReLU and $G$-DNN architectures at every depth for the symmetry group $G$ of the icosahedron. Only architectures corresponding to sequences of irreps of strictly decreasing degree are considered. We do not report the total number of such sequences as we found every sequence to correspond to an admissible $G$-DNN architecture.  Depth | CReLU |  $G$-DNN
---|---|---
2 | 20 | 20
3 | 136 | 142
4 | 441 | 516
5 | 776 | 1089
6 | 769 | 1392
7 | 407 | 1064
8 | 90 | 448
9 | 0 | 80
Total | 2639 | 4751

As a more striking example, we consider the symmetry group of the icosahedron
used later for 3D object classification in Sec. 4.3. We report the numbers of
admissible CReLU and $G$-DNN architectures for this group (Table 3). There are
about $1.8\times$ as many admissible $G$-DNN architectures as there are
admissible CRELU architectures, including nine-layer $G$-DNNs with no CRELU
architectures of the same depth. We conclude that while the CRELU activation
function gives a simple way to implement equivariance with respect to signed
perm-reps, our $G$-DNNs grant us access to large parts of $G$-invariant
architecture space previously unreachable.

###  4.2 Binary multiplication

Our first example application is an exact result and demonstrates that
$G$-DNNs with type 2 signed perm-reps occur even in the context of simple
mathematical operations.

###### Example 2

For $d\geq 3$, let $m=2^{d}$ and

$\mathcal{X}=\\{x\in\\{0,1\\}^{m}:x_{2i-1}+x_{2i}=1\forall
i\in\\{1,\ldots,m/2\\}\\}.$

For $\\{e_{1},\ldots,e_{m}\\}$ the standard orthonormal basis, Let
$G<\operatorname{P}(m)$ be the subgroup of all even permutation matrices that
only transpose $e_{2i-1}$ and $e_{2i}$. Define the function
$f:\mathcal{X}\mapsto\\{-1,1\\}$ by

$f(x)=\prod_{i=1}^{m/2}(x_{2i-1}-x_{2i}).$

Then $f$ admits an expression as a $G$-DNN of depth $d$ where:

  1. (a)

For $i\in\\{1,\ldots,d\\}$ and $j\in\\{1,\ldots,i\\}$, the blocks
$V^{(i)}_{j}$ of the latent weight matrices (see Thm. 6 (a)) are given by

$V^{(i)}_{j}=\begin{cases}I_{m/2^{i+1}}\otimes\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix},&\mbox{ if }1\leq i=j<d\\\
\begin{bmatrix}1&-1\end{bmatrix},&\mbox{ if }i=j=d\\\ 0,&\mbox{
otherwise.}\end{cases}$

  2. (b)

For $i\in\\{1,\ldots,d-1\\}$, the $i$th layer transforms by the signed perm-
rep

$\rho^{(i)}=\begin{cases}\bigoplus_{j=1}^{m/2^{i+1}}\rho_{H^{(i)}_{j}K^{(i)}_{j}},&\mbox{
if }i\leq d-2\\\
\rho_{H^{(d-1)}_{1}K^{(d-1)}_{1}}\oplus\rho_{H^{(d-1)}_{1}K^{(d-1)}_{1}},&\mbox{
if }i=d-1,\end{cases}$

where

$\displaystyle K^{(1)}_{j}$ $\displaystyle=\\{g\in G:gv_{j}=v_{j}\\}$
$\displaystyle H^{(1)}_{j}$ $\displaystyle=\\{g\in G:gv_{j}=\pm v_{j}\\},$

where $v_{j}=e_{4j-3}-e_{4j-2}+e_{4j-1}-e_{4j}$, and

$\displaystyle K^{(i+1)}_{j}$ $\displaystyle=H^{(i)}_{2j-1}\cap H^{(i)}_{2j}$
$\displaystyle H^{(i+1)}_{j}$ $\displaystyle=(H^{(i)}_{2j-1}\cap
H^{(i)}_{2j})\cup((G\setminus H^{(i)}_{2j-1})\cap(G\setminus H^{(i)}_{2j})),$

for $i\in\\{1,\ldots,d-2\\}$. The rep $\rho^{(d)}$ is trivial as usual.

Here, $f(x)$ is the product of $\frac{m}{2}$ binary elements in $\\{-1,1\\}$
but where the elements are each represented as 2D one-hot vectors and are then
concatenated into the $m$-dimensional input $x$. From the perspective of
multiplication of elements in $\\{-1,1\\}$, the group $G$ corresponds to an
even number of sign flips, which clearly leaves the final product invariant.
Example 2 gives an explicit construction of a $G$-DNN that implements the
function $f$. Each layer of the $G$-DNN partitions its input into pairs and
takes each of their products; the network thus iteratively coarsegrains the
input until the final scalar product is returned.101010Although $f$ is a
simple function, we were unable to construct a $G$-DNN—in particular, a
shallower $G$-invariant architecture that (1) has $G$-equivariant
preactivations and (2) does not have an exponential number of hidden neurons
per layer—simpler than the one given in Ex. 2 that fits $f$. For example, one
could compute $f(x)$ with a shallow network that first maps $x$ linearly into
$\\{-1,1\\}^{\frac{m}{2}}$, then takes the sum $\vec{1}^{\top}x$, and finally
returns the parity of the sum using a suitable combination of ReLU neurons;
however, the function $x\rightarrow\vec{1}^{\top}x$ is not $G$-equivariant.
Each latent weight matrix of the $G$-DNN has a block-diagonal structure and no
latent skip connections; however, by Thm. 6 (a), the $G$-DNN does have skip
connections in terms of the apparent weight matrices. All signed perm-irreps
in the network–except $\rho^{(d)}$ which must be trivial–are type 2, and the
image of each one is isomorphic to the Klein-4 group. The image of the
penultimate rep $\rho^{(d-1)}$ is also isomorphic to the Klein-4 group, but
the rep itself is not irreducible and decomposes into two copies of a type 2
scalar irrep.

Table 4:  Binary cross-entropy losses (mean and standard deviation over $24$ random initialization seeds) of four $G$-DNN architectures (see main text) on the binary multiplication problem. We report both the training loss and validation loss before training (initial) and after $5$ epochs of training (final). Training and validation losses are equal because each of the two class labels corresponds to exactly one $G$-orbit, over which each $G$-DNN is constant– regardless of the dataset split. All values correspond to a classification accuracy of $50\%$, except the final losses of zero for the type 2 architecture corresponding to 100% accuracy.  Architecture | Initial train | Initial val | Final train | Final val
---|---|---|---|---
Type 1 |  $5.11$ p m 4.68 |  $5.11$ p m 4.68 |  $0.71$ p m 0.04 |  $0.71$ p m 0.04
Type 2 |  $1.33$ p m 0.60 |  $1.33$ p m 0.60 |  $0.00$ p m 0.00 |  $0.00$ p m 0.00
Unraveled (random init) |  $11.36$ p m 12.34 |  $11.36$ p m 12.34 |  $0.71$ p m 0.03 |  $0.71$ p m 0.03
Unraveled (type 2 init) |  $1.33$ p m 0.60 |  $1.33$ p m 0.60 |  $0.70$ p m 0.00 |  $0.70$ p m 0.00

We investigate Ex. 2 empirically by generating the complete dataset
$\\{(x,f(x)):x\in\mathcal{X}\\}$ for $m=16$. Since $f(x)=\pm 1$, then we
regard the estimation of $f$ as a binary classification problem. We use a
random 20% of the dataset (with class stratification) for training and the
rest for validation. We instantiate the “type 2” architecture with the type 2
signed perm-irreps in Ex. 2 (b) and randomly initialize its weights. We
compare the type 2 architecture to two type 1 baselines: (1) the “type 1”
architecture obtained by sending111111This transformation is called
topological tunneling in the literature (Agrawal and Ostrowski, 2022)
$\rho_{HK}\rightarrow\rho_{HH}$ (see Thm. 1) and (2) the “unraveled”
architecture obtained by sending $\rho_{HK}\rightarrow\rho_{KK}$ (seeThm. 2
(d)). The type 1, type 2, and unraveled architectures are thus analogous to
the three weightsharing patterns in Fig. 1 (see Sec. 2.2); i.e., the type 1
architecture has the same number of hidden neurons as the type 2 architecture
but expresses different functions, and the unraveled architecture has double
the number of hidden neurons and the capacity to express both the smaller two
architectures as well as much more.

We trained all architectures for $5$ epochs with the Adam optimizer with
minibatch size $64$, learning rate $0.01$, and learning rate decay $0.99$ per
step. Starting at 50% classification accuracy, the type 2 architecture quickly
achieves 100% training and validation accuracy as well as a final binary
cross-entropy loss of $0.00$ (Table 4). All other architectures remain stuck
at 50% accuracy even after training. To explain these results, we first note
that in the type 2 architecture, the latent weight matrices for
$i\in\\{1,\ldots,d-1\\}$ are constrained to have the form

$V^{(i)}_{j}=\begin{cases}I_{m/2^{i+1}}\otimes\begin{bmatrix}u^{(i)}_{j}&-u^{(i)}_{j}&v^{(i)}_{j}&-v^{(i)}_{j}\\\
u^{(i)}_{j}&-u^{(i)}_{j}&-v^{(i)}_{j}&v^{(i)}_{j}\end{bmatrix},&\mbox{ if
}1\leq j=i<d\\\ 0,&\mbox{ if }1\leq j<i<d,\end{cases}$

where the $u^{(i)}_{j}$ and $v^{(i)}_{j}$ are free learnable parameters. In
the type 1 architecture, the negative signs in front of $v^{(i)}_{j}$ are
omitted, and the off-diagonal blocks are no longer zero but are instead
constrained in the same way as the diagonal blocks. As a result, the very
first linear transformation $g^{(1)}(x)=V^{(1)}x$ in the architecture is
invariant to every transposition
$(x_{2i-1},x_{2i})\rightarrow(x_{2i},x_{2i-1})$– not just even numbers of
them; the rest of the architecture is thus unable to distinguish the two
classes of inputs, resulting in a flat $50\%$ accuracy. The type 1
architecture simply does not have the capacity to solve the binary
classification problem.

In contrast to the type1 and type 2 architectures, the latent weight matrices
$V^{(i)}_{i}$ of the unraveled architectures are not even constrained to be
block-diagonal, and the $V^{(i)}_{j}$ for $j<i$ are not constrained to be
zero. The unraveled architecture thus has about $6.5\times$ the number of free
learnable parameters compared to the type 2 architecture, and it must learn
the block-diagonal weight structure from data alone. Based on the training
loss, the complete failure of the unraveled architecture is likely due to a
severe trainability issue. To confirm the unraveled architecture indeed has
the capacity to express the solution and in particular the type 2
architecture, we loaded the trained weights of the type 2 architecture into
the unraveled architecture by an appropriate mapping and confirmed that the
resulting architecture indeed achieves 100% training and validation accuracy.
To test if the failure to train is due to poor initialization, we implemented
the unraveled architecture with both random initialization (called “random
init” in Table 4) and with the randomly initialized weights of the type 2
architecture (called “type 2 init” in Table 4). While initialization with the
initial weights of the type 2 architecture reduces the initial loss of the
unraveled architecture to match the type 2 architecture, it does not solve the
trainability issue. We thus conclude the unraveled architecture simply does
not have sufficient inductive bias to solve the binary classification problem.

###  4.3 3D object classification

Figure 2:  Validation classification accuracies (mean and standard deviation
over $24$ random initialization seeds) for three $G$-DNN architectures (see
main text) on the ModelNet40 dataset using different percentages of the full
training data. The mixed architecture—the only one including type 2 signed
perm-irreps—clearly outperforms the two baselines, with the performance gap
increasing as less training data is available.

Our second example application demonstrates that $G$-DNNs with type 2 signed
perm-reps carry inductive bias that can be useful “in the wild”. We consider
the ModelNet40 dataset(Wu et al., 2015), which contains $9843$ training and
$2468$ validation samples of 3D CAD mesh representations of $40$ different
objects ranging from airplanes to toilets. The problem is to predict the
object class given an input mesh. We preprocess the data in identical fashion
to Jiang et al. (2019).121212Jiang et al. (2019) perform five iterations of
refinement to increase resolution, whereas we only perform two. This is
because our current $G$-DNN implementation is based on fully-connected linear
layers and thus does not scale well to high resolution. We plan to remedy this
in future work by introducing local kernel windows. We attribute the
difference in accuracy reported in Fig. 2 and that reported by Jiang et al.
(2019) to this difference in resolution.  Specifically, we first bound each
mesh in the unit sphere and discretize the sphere into an icosahedron. To
increase resolution, we include the midpoint on each icosahedral edge as a
vertex, normalize all vertices to have unit norm, and then repeat once more on
the new polyhedron; this yields $162$ vertices in all. From each of these
vertices, we perform ray-tracing to the origin; we record the distance from
the sphere to the mesh as well as the sine and cosine of the incident angle.
The representation is further augmented with the three channels corresponding
to the convex hull of the input mesh, yielding a $6$-channel input
representation over $162$ points.

The relevant symmetry group $G$ is the symmetry group of the icosahedron,
generated by (1) the order-$3$ rotation about the normal vector to one of the
faces and (2) the order-$5$ rotation about one of the vertices; the group has
$60$ elements and is isomorphic to the alternating group $A_{5}$. We consider
$G$-DNN architectures with four layers and $16$, $32$, $64$, and $40$ output
channels per rep in each respective layer. We specify apriori the degrees of
the signed perm-irreps to be used in each layer as $30$, $15$, $10$, and $1$;
we then enumerate the admissible architectures as described after Thm. 7, and
we select the following designs: For the “mixed” architecture, we select one
type 1 and one type 2 signed perm-irrep in each of the first three
layers131313In each layer, the selected type 1 and type 2 signed perm-irreps
are cohomologous as defined in Agrawal and Ostrowski (2022); i.e., they have
the forms $\rho_{HH}$ and $\rho_{HK}$ respectively.we select the trivial rep
in the last layer, as always. We compare the mixed architecture to the
corresponding “type 1” and “unraveled” architectures, which are constructed
exactly as done in Sec. 4.2.

We trained all architectures for $500$ epochs with the Adam optimizer with
minibatch size $64$, learning rate $0.01$, and learning rate decay $0.99$ per
step. We included batchnorm as described in Sec. 3.4 after each ReLU layer. In
each run, we performed retroactive early stopping by recording the highest
validation accuracy achieved over all epochs. We find that the mixed
architecture—the only one containing type 2 signed perm-irreps—significantly
outperforms the two baseline architectures in terms of validation accuracy,
with the performance gap increasing as less training data is used. This
suggests that the mixed architecture carries stronger inductive bias, still
consistent with the ground truth, as compared to the baselines.

##  5 Conclusion

We have introduced the $G$-DNN, a $G$-invariant densely connected DNN
architecture. In contrast to previous $G$-invariant architectures in the
literature such as the $G$-CNN (Cohen and Welling, 2016), the $G$-DNN is built
with _signed_ perm-reps that do not require individual layers of the network
to be $G$-equivariant. The result is a richer family of $G$-invariant
architectures never seen before (carefully quantified in terms of admissible
architecture count), and we have demonstrated with both theoretical and
empirical examples that some of these novel architectures can boost predictive
performance.

To be clear, we do not claim the $G$-DNN to be a new state-of-the-art (SOTA)
for $G$-invariant deep learning. Rather, our work is a demonstration that
signed perm-reps, combined with skip connections, are mathematically natural
building blocks for deep $G$-invariant architectures with practical potential.
Indeed, we suspect that the structures and ideas presented in this paper, once
extended and combined with domain-specific bells and whistles, could in fact
help to boost the performance of SOTA $G$-invariant architectures.

Even at the domain-agnostic level, however, several open questions remain for
future research. First, can we extend $G$-DNNs from $G$-invariance to
$G$-equivariance? The only obstacle here is the construction of architectures
guaranteed to be admissible. Second, can we perform $G$-NAS to find the
optimal signed perm-irreps to use in each layer? Third and finally, are there
ways of enforcing $G$-invariance that go even beyond the $G$-DNN architectures
described in this paper? A complete classification of _all_ $G$-invariant
architectures would give us the finest possible control on inductive bias,
thereby allowing us—in principle—to optimize predictive performance on
$G$-invariant problems.

Acknowledgments and Disclosure of Funding

D.A. was supported by NSF award No. 2202990. J.O. was supported by DOE grant
DE-SC0018175.

##  Appendix A Signed permutation representations

###  A.1 Central hypothesis

Proof [Proof of Thm. 1] For every $J\leq G$, let $P_{J}$ be the $m\times m$
orthogonal projection operator onto the subspace of $\mathbb{R}^{m}$
pointwise-invariant under the action of $J$:

$P_{J}=\frac{1}{|J|}\sum_{g\in J}g.$

By Thm. 4b of Agrawal and Ostrowski (2022), there exists
$w_{2}\in\operatorname{ran}(P_{K_{2}}-(|H:K_{2}|-1)P_{H})$ and a transversal
$\\{g_{1},\ldots,g_{n}\\}$ of $G/H$ such that

$W_{2}=\begin{bmatrix}g_{1}w_{2}&g_{2}w_{2}&\cdots&g_{n}w_{2}\end{bmatrix}^{\top}.$

Moreover, there exists
$w_{1}\in\operatorname{ran}(P_{K_{1}}-(|H:K_{1}|-1)P_{H})$ and
$P\in\operatorname{P}(n)$ such that

$PW_{1}=\begin{bmatrix}g_{1}w_{1}&g_{2}w_{1}&\cdots&g_{n}w_{1}\end{bmatrix}^{\top}.$

(The permutation matrix $P$ is in general necessary so we can use the same
transversal of $G/H$.) We have

$\displaystyle\operatorname{diag}(PW_{1}W_{2}^{\top})$
$\displaystyle=\\{(g_{i}w_{1})^{\top}g_{i}w_{2}\\}_{i=1}^{n}$
$\displaystyle=\\{w_{1}^{\top}g_{i}^{\top}g_{i}w_{2}\\}_{i=1}^{n}$
$\displaystyle=\\{w_{1}^{\top}w_{2}\\}_{i=1}^{n}$ $\displaystyle=0,$

where the last step follows by Prop. 6 of Agrawal and Ostrowski (2022).

Proof [Proof of Thm. 2] (a)  Let $\pi:G\mapsto\operatorname{P}(n)$ and
$\zeta:G\mapsto\operatorname{Z}(n)$ be the unique functions satisfying
$\rho(g)=\pi(g)\zeta(g)\forall g\in G$ (note $\pi$ should not be confused with
$\pi_{\rho}$ appearing in the theorem statement). Evaluating the Kronecker
product, the function $\pi_{\rho}$ can be rewritten as

$\displaystyle\pi_{\rho}(g)$
$\displaystyle=\mathcal{H}\left(\begin{bmatrix}\rho(g)&-\rho(g)\\\
-\rho(g)&\rho(g)\end{bmatrix}\right)$
$\displaystyle=\mathcal{H}\left(\begin{bmatrix}\pi(g)\zeta(g)&-\pi(g)\zeta(g)\\\
-\pi(g)\zeta(g)&\pi(g)\zeta(g)\end{bmatrix}\right)$
$\displaystyle=\mathcal{H}\left(\begin{bmatrix}\pi(g)&0\\\
0&\pi(g)\end{bmatrix}\begin{bmatrix}\zeta(g)&-\zeta(g)\\\
-\zeta(g)&\zeta(g)\end{bmatrix}\right)$
$\displaystyle=\begin{bmatrix}\pi(g)&0\\\
0&\pi(g)\end{bmatrix}\mathcal{H}\left(\begin{bmatrix}\zeta(g)&-\zeta(g)\\\
-\zeta(g)&\zeta(g)\end{bmatrix}\right),$

where in the last step we exploited the permutation-equivariance of
elementwise operations. Now since $\mathcal{H}(z)=\frac{1+z}{2}$ for
$z\in\\{-1,1\\}$, then we have

$\displaystyle\pi_{\rho}(g)$ $\displaystyle=\begin{bmatrix}\pi(g)&0\\\
0&\pi(g)\end{bmatrix}\frac{1}{2}\left(\begin{bmatrix}I_{n}&I_{n}\\\
I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix}\zeta(g)&-\zeta(g)\\\
-\zeta(g)&\zeta(g)\end{bmatrix}\right)$
$\displaystyle=\frac{1}{2}\left(\begin{bmatrix}\pi(g)&\pi(g)\\\
\pi(g)&\pi(g)\end{bmatrix}+\begin{bmatrix}\pi(g)\zeta(g)&-\pi(g)\zeta(g)\\\
-\pi(g)\zeta(g)&\pi(g)\zeta(g)\end{bmatrix}\right)$
$\displaystyle=\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\\
\pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}.(*)$

Now, let $\pi(g)_{ij}$ (resp. $\rho(g)_{ij}$) be the unique nonzero element in
the $i$th row of $\pi(g)$ (resp. $\rho(g)$). Since
$\rho(g)_{ij}=\pm\pi(g)_{ij}$, then exactly one of
$\frac{1}{2}[\pi(g)_{ij}\pm\rho(g)_{ij}]$ is unity, while the other is zero.
Thus, every row of (*) is a one-hot vector. The same argument can be made for
the columns, and hence (*) is a bona fide permutation matrix; i.e.,
$\pi_{\rho}:G\mapsto\operatorname{P}(2n)$ is a well-defined function.

All that remains is to show $\pi_{\rho}$ is a homomorphism. We rewrite (*) as

$\pi_{\rho}(g)=\frac{1}{2}\left(\begin{bmatrix}I_{n}\\\
I_{n}\end{bmatrix}\pi(g)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix}I_{n}\\\
-I_{n}\end{bmatrix}\rho(g)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right).$

Then for $g,h\in G$, it is easy to verify that

$\displaystyle\pi_{\rho}(g)\pi_{\rho}(h)$
$\displaystyle=\frac{1}{4}\left(\begin{bmatrix}I_{n}\\\
I_{n}\end{bmatrix}\pi(g)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix}I_{n}\\\
-I_{n}\end{bmatrix}\rho(g)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)\left(\begin{bmatrix}I_{n}\\\
I_{n}\end{bmatrix}\pi(h)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}\right.$
$\displaystyle\quad+\left.\begin{bmatrix}I_{n}\\\
-I_{n}\end{bmatrix}\rho(h)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)$
$\displaystyle=\frac{1}{4}\left(2\begin{bmatrix}I_{n}\\\
I_{n}\end{bmatrix}\pi(g)\pi(h)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+0+0+2\begin{bmatrix}I_{n}\\\
-I_{n}\end{bmatrix}\rho(g)\rho(h)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)$
$\displaystyle=\pi_{\rho}(gh).$

(b)  Using (*) from part (a), we have

$\displaystyle\pi_{\rho}(g)\begin{bmatrix}W\\\ -W\end{bmatrix}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\\
\pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}W\\\ -W\end{bmatrix}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}\pi(g)W+\rho(g)W-\pi(g)W+\rho(g)W\\\
\pi(g)W-\rho(g)W-\pi(g)W-\rho(g)W\end{bmatrix}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}2\rho(g)W\\\ -2\rho(g)W\end{bmatrix}$
$\displaystyle=\rho(g)\begin{bmatrix}W\\\ -W\end{bmatrix}$
$\displaystyle=\begin{bmatrix}W\\\ -W\end{bmatrix}g,$

proving the claim.

(c)  For the forward implication, we prove its contrapositive; suppose $\rho$
is type 1. Then $\pi=\rho$ so that (*) implies

$\pi_{\rho}=\frac{1}{2}\begin{bmatrix}2\pi(g)&0\\\
0&2\pi(g)\end{bmatrix}=\begin{bmatrix}\pi(g)&0\\\ 0&\pi(g)\end{bmatrix},$

which is clearly reducible.

For the reverse implication, suppose $\rho$ is type 2. To show $\pi_{\rho}$ is
irreducible, we will show it is transitive on the standard orthonormal basis
$\\{\omega_{1},\ldots,\omega_{2n}\\}$. Let $i,j\in\\{1,\ldots,2n\\}$, and
without loss of generality suppose $i\leq n$.

Case 1:  Suppose $j\leq n$. Then $\omega_{i}$ is just $e_{i}$ (the $i$th
standard orthonormal basis vector of dimension $n$) concatenated with
$\vec{0}_{n}$, and similar for $\omega_{j}$. Now since $\rho$ is irreducible,
then there exists $g\in G$ such that $\rho(g)e_{i}=e_{j}$; note
$\pi(g)e_{i}=e_{j}$ as well. We thus have

$\displaystyle\pi_{\rho}(g)\omega_{i}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\\
\pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}e_{i}\\\
\vec{0}_{n}\end{bmatrix}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}\pi(g)e_{i}+\rho(g)e_{i}\\\
\pi(g)e_{i}-\rho(g)e_{i}\end{bmatrix}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}e_{j}+e_{j}\\\
e_{j}-e_{j}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}e_{j}\\\
\vec{0}_{n}\end{bmatrix}$ $\displaystyle=\omega_{j},$

establishing transitivity in this case.

Case 2:  Suppose instead $j>n$. Then $\omega_{j}$ is the concatenation of
$\vec{0}_{n}$ and $e_{j-n}$. Since $\rho$ is irreducible, then there exists
$g\in G$ such that $\rho(g)e_{i}=-e_{n-j}$. The rest of the proof proceeds in
analogy to case 1.

(d)  For every $v\in\mathbb{R}^{n}$ and linear rep
$\tau:G\mapsto\operatorname{GL}(n,\mathbb{R})$, define the stabilizer subgroup

$\operatorname{st}_{\tau}(v)=\\{g\in G:\tau(g)v=v\\}.$

Since $\rho=\rho_{HK}$, then $\operatorname{st}_{\rho}(e_{1})=K$. Since
$\pi_{\rho}$ is an ordinary perm-rep, then all we must show is
$\operatorname{st}_{\pi_{\rho}}(\omega_{1})=K$ to establish the claim. Similar
to part (c), $\operatorname{st}_{\pi_{\rho}}(\omega_{1})$ is the set of all
$g\in G$ such that

$\displaystyle\pi_{\rho}(g)\omega_{1}$ $\displaystyle=\omega_{1}$
$\displaystyle\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\\
\pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}e_{1}\\\
\vec{0}_{n}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}e_{1}\\\
\vec{0}_{n}\end{bmatrix}$
$\displaystyle\frac{1}{2}\begin{bmatrix}\pi(g)e_{1}+\rho(g)e_{1}\\\
\pi(g)e_{1}-\rho(g)e_{1}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}e_{1}\\\
\vec{0}_{n}\end{bmatrix}.$

Taking the difference of the two rows, we obtain $\rho(g)e_{1}=e_{1}$; hence,
$\operatorname{st}_{\pi_{\rho}}(\omega_{1})=\operatorname{st}_{\rho}(e_{1})=K$,
completing the proof.

##  Appendix B $G$-invariant deep neural networks

###  B.1 Parameterization redundancies

To understand the inclusion of skip connections as a reparameterization, we
rewrite Eq. 3 as

$\displaystyle f^{(i+1)}(x)$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
\operatorname{ReLU}(f^{(i)}(x))-\operatorname{ReLU}(-f^{(i)}(x))\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I_{n_{i+1}}&0&0\\\
0&I_{N_{i}}&-I_{N_{i}}\end{bmatrix}\operatorname{ReLU}\left(\begin{bmatrix}W^{(i)}\\\
I_{N_{i}}\\\ -I_{N_{i}}\end{bmatrix}f^{(i)}(x)+\begin{bmatrix}b^{(i)}\\\ 0\\\
0\end{bmatrix}\right).$

The outer matrix in the last equation can be combined with the matrix in the
next layer; the result is a DNN having the same depth as the original—and
representing the same input-output function—but with no skip connections, as
they have been transformed into additional ReLU neurons.

Proof [Proof of Prop. 3] We will show $W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)}$ is
invariant under the transformation. The function $f^{(i+1)}$ transforms as

$\displaystyle f^{(i+1)}(x)$
$\displaystyle\rightarrow\begin{bmatrix}\operatorname{ReLU}(CPZW^{(i)}f^{(i)}(x)+CPZb^{(i)})\\\
f^{(i)}(x)\end{bmatrix}$ $\displaystyle=\begin{bmatrix}CP&0\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(Z(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}$ $\displaystyle=\begin{bmatrix}CP&0\\\
0&I_{N_{i}}\end{bmatrix}\left(\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
0\end{bmatrix}\right)$ $\displaystyle=\begin{bmatrix}CP&0\\\
0&I_{N_{i}}\end{bmatrix}\left(\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right)$ $\displaystyle=\begin{bmatrix}CP&0\\\
0&I_{N_{i}}\end{bmatrix}\left(\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}\right.$
$\displaystyle\quad-\left.\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right)$ $\displaystyle=\begin{bmatrix}CP&0\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\left(\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right)$
$\displaystyle=\begin{bmatrix}CP&-CP\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\left(f^{(i+1)}(x)-\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right).$

We thus have

$\displaystyle W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)}$ $\displaystyle\rightarrow
W^{(i+1)}\begin{bmatrix}(CP)^{-1}&\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}CP&-CP\mathcal{H}(-Z)W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}\left(f^{(i+1)}(x)\right.$
$\displaystyle\quad-\left.\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right)+b^{(i+1)}+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}$
$\displaystyle=W^{(i+1)}\left(f^{(i+1)}(x)-\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}\right)+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\\
0\end{bmatrix}+b^{(i+1)}$ $\displaystyle=W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)}.$

###  B.2 $G$-invariant architectures

Proof [Proof of Lemma 4] Since $f^{(1)}$ and $\psi^{(1)}$ are both the
identity functions, then the claim is immediate for $i=1$. Suppose the claim
is true for some $i\in\\{1,\ldots,d-1\\}$. We have for all $g\in G$ and
$x\in\mathbb{R}^{m}$:

$\displaystyle f^{(i+1)}(gx)$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(gx)+b^{(i)})\\\
f^{(i)}(gx)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}\psi^{(i)}(g)f^{(i)}(x)+b^{(i)})\\\
\psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(\rho^{(i)}(g)W^{(i)}f^{(i)}(x)+b^{(i)})\\\
\psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(\rho^{(i)}(g)W^{(i)}f^{(i)}(x)+\rho^{(i)}(g)b^{(i)})\\\
\psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)\operatorname{ReLU}(\zeta^{(i)}(g)(W^{(i)}f^{(i)}(x)+b^{(i)}))\\\
\psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
\psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))W^{(i)}f^{(i)}(x)\\\
0\end{bmatrix}$
$\displaystyle\quad-\begin{bmatrix}\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)}\\\
0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))W^{(i)}\\\
0&I_{N_{i}}\end{bmatrix}f^{(i+1)}(x)+\begin{bmatrix}-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)}\\\
0\end{bmatrix}.$

Note that

$\displaystyle-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))$
$\displaystyle=-\frac{1}{2}\pi^{(i)}(g)(I_{n_{i+1}}-\zeta^{(i)}(g))$
$\displaystyle=\frac{1}{2}\pi^{(i)}(g)(\zeta^{(i)}(g)-I_{n_{i+1}})$
$\displaystyle=\frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g)).$

We thus have

$\displaystyle-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))W^{(i)}$
$\displaystyle=\frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g))W^{(i)}$
$\displaystyle=\frac{1}{2}(\rho^{(i)}(g)W^{(i)}-\pi^{(i)}(g)W^{(i)})$
$\displaystyle=\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^{(i)}(g)W^{(i)}).$

For the bias term, let
$\rho^{(i)}=\rho^{(i)}_{1}\oplus\cdots\oplus\rho^{(i)}_{k}$ be the
decomposition of $\rho^{(i)}$ into irreducibles; decompose $\pi^{(i)}$ and
$b^{(i)}$ correspondingly. Then we have

$\displaystyle-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)}$
$\displaystyle=\frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g))b^{(i)}$
$\displaystyle=\frac{1}{2}\bigoplus_{j=1}^{k}(\rho^{(i)}_{j}(g)-\pi^{(i)}_{j}(g))b^{(i)}_{j}.$

If $\rho^{(i)}_{j}$ is type 1, then $\rho^{(i)}_{j}=\pi^{(i)}_{j}$ so that the
$j$th term in the above direct sum is zero. On the other hand, if
$\rho^{(i)}_{j}$ is type 2, then $\rho^{(i)}_{j}(g)b^{(i)}_{j}=b^{(i)}_{j}$
implies $b^{(i)}_{j}=0$, so that again the $j$th summand is zero. Therefore,
$-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)}=0\forall g\in G$. We thus
have

$\displaystyle f^{(i+1)}(gx)$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^{(i)}(g)W^{(i)})\\\
0&I_{N_{i}}\end{bmatrix}f^{(i+1)}(x)+0$
$\displaystyle=\psi^{(i+1)}(g)f^{(i+1)}(x).$

The conclusion follows by induction.

Proof [Proof of Lemma 5] We will verify that $\psi^{(i+1)}$ defined as claimed
satisfies the recursion in Lemma 4. For $i=1$, we have

$\displaystyle\psi^{(2)}(g)$ $\displaystyle=A^{(1)-1}\Pi^{(1)}(g)A^{(1)}$
$\displaystyle=\begin{bmatrix}I_{n_{2}}&-\frac{1}{2}W^{(1)}\\\
0&I_{n_{1}}\end{bmatrix}^{-1}\begin{bmatrix}\pi^{(1)}(g)&0\\\
0&g\end{bmatrix}\begin{bmatrix}I_{n_{2}}&-\frac{1}{2}W^{(1)}\\\
0&I_{n_{1}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I_{n_{2}}&\frac{1}{2}W^{(1)}\\\
0&I_{n_{1}}\end{bmatrix}\begin{bmatrix}\pi^{(1)}(g)&0\\\
0&g\end{bmatrix}\begin{bmatrix}I_{n_{2}}&-\frac{1}{2}W^{(1)}\\\
0&I_{n_{1}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(1)}(g)&\frac{1}{2}(W^{(1)}g-\pi^{(1)}(g)W^{(1)})\\\
0&g\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(1)}(g)&\frac{1}{2}(W^{(1)}\psi^{(1)}(g)-\pi^{(1)}(g)W^{(1)})\\\
0&\psi^{(1)}(g)\end{bmatrix},$

which indeed agrees with Lemma 4.

Now suppose the claim holds for some $i\in\\{2,\ldots,d-1\\}$. Observe that

$\displaystyle A^{(i)}$
$\displaystyle=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}$ $\displaystyle\Pi^{(i)}(g)$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&0\\\
0&\Pi^{(i-1)}(g)\end{bmatrix}.$

We thus have

$\displaystyle\psi^{(i+1)}(g)$ $\displaystyle=A^{(i)-1}\Pi^{(i)}(g)A^{(i)}$
$\displaystyle=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}^{-1}\begin{bmatrix}\pi^{(i)}(g)&0\\\
0&\Pi^{(i-1)}(g)\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I_{n_{i+1}}&\frac{1}{2}W^{(i)}A^{(i-1)-1}\\\
0&A^{(i-1)-1}\end{bmatrix}\begin{bmatrix}\pi^{(i)}(g)&0\\\
0&\Pi^{(i-1)}(g)\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}A^{(i-1)-1}\Pi^{(i-1)}(g)A^{(i-1)}-\pi^{(i)}(g)W^{(i)})\\\
0&A^{(i-1)-1}\Pi^{(i-1)}(g)A^{(i-1)}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^{(i)}(g)W^{(i)})\\\
0&\psi^{(i)}(g)\end{bmatrix}.$

The conclusion follows by induction.

Proof [Proof of Thm. 6] (a)  By Lemmas 4-5, we have

$\displaystyle\rho^{(i)}(g)W^{(i)}$ $\displaystyle=W^{(i)}\psi^{(i)}(g)$
$\displaystyle\rho^{(i)}(g)W^{(i)}$
$\displaystyle=W^{(i)}A^{(i-1)-1}\Pi^{(i-1)}(g)A^{(i-1)}$
$\displaystyle\rho^{(i)}(g)W^{(i)}A^{(i-1)-1}$
$\displaystyle=W^{(i)}A^{(i-1)-1}\Pi^{(i-1)}(g).$

Let $V^{(i)}=W^{(i)}A^{(i-1)-1}$. Thus, $W^{(i)}=V^{(i)}A^{(i-1)}$.

All that is left is to establish equivariance of the blocks of $V^{(i)}$. We
have

$\displaystyle\rho^{(i)}(g)V^{(i)}$
$\displaystyle=\rho^{(i)}(g)W^{(i)}A^{(i-1)-1}$
$\displaystyle=W^{(i)}\psi^{(i)}(g)A^{(i-1)-1}$
$\displaystyle=W^{(i)}A^{(i-1)-1}\Pi^{(i-1)}(g)A^{(i-1)}A^{(i-1)-1}$
$\displaystyle=V^{(i)}\Pi^{(i-1)}(g).$

Since $\Pi^{(i-1)}(g)$ is a block-diagonal matrix, then blockwise equivariance
follows.

(b)  By part (a), we have

$\displaystyle g^{(i)}(x)$ $\displaystyle=W^{(i)}f^{(i)}(x)$
$\displaystyle=V^{(i)}A^{(i-1)}f^{(i)}(x)$ $\displaystyle=V^{(i)}h^{(i)}(x).$

To establish the recursion for $h^{(i)}$, first observe that $A^{(i)}$
satisfies the recursion

$A^{(i)}=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}.$

We thus have

$\displaystyle h^{(i+1)}(x)$ $\displaystyle=A^{(i)}f^{(i+1)}(x)$
$\displaystyle=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\\
0&A^{(i-1)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})\\\
f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})-\frac{1}{2}W^{(i)}f^{(i)}(x)\\\
A^{(i-1)}f^{(i)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(x)+b^{(i)})-\frac{1}{2}g^{(i)}(x)\\\
h^{(i)}(x)\end{bmatrix},$

which completes the proof.

####  B.2.1 Implementation

Here we describe how Thm. 6 translates into a concrete implementation. First,
independently for every $i\in\\{1,\ldots,d\\}$ and $j\in\\{1,\ldots,i\\}$, we
construct a basis set $\mathcal{B}^{(i)}_{j}$ for the space of all matrix
solutions to the linear system

$\rho^{(i)}(g)X=X\pi^{(j-1)}(g)\forall g\in G.$

This construction is done just once at the time of architecture
initialization. We describe the construction below; for now, however, let us
assume we have found such basis sets. Then we next constrain each latent
weight matrix block $V^{(i)}_{j}$ to be a linear combination in
$\mathcal{B}^{(i)}_{j}$. The linear coefficients are randomly initialized and
are the trainable parameters of the $G$-DNN model. The forward pass is then a
direct implementation of Thm. 6 (b), and its pseudocode is presented in Alg.
1.

Algorithm 1 Implementation of Thm. 6 (b) for the forward pass of a $G$-DNN
$f$. Here $g^{(i)}(x)$ and $h^{(i)}(x)$ should be regarded as variable names.

1:function $f$($x$)

2: $h^{(1)}(x)\leftarrow x$

3: for $i\in\\{1,\ldots,d-1\\}$ do

4: $g^{(i)}(x)\leftarrow V^{(i)}h^{(i)}(x)$

5:
$h^{(i+1)}(x)\leftarrow\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(x)+b^{(i)})-\frac{1}{2}g^{(i)}(x)\\\
h^{(i)}(x)\end{bmatrix}$

6: return $V^{(d)}g^{(d)}(x)+b^{(d)}$

All that remains is to describe the construction of the basis sets
$\mathcal{B}^{(i)}_{j}$. We phrase this as the following general problem.
Given a signed perm-rep $\rho$, an ordinary perm-rep $\pi$, and a generating
set $G_{0}$ for the group $G$, we seek a basis set for the space of matrix
solutions to the linear system

$\rho(g)X\pi(g)^{\top}=X\forall g\in G_{0}.$

While we could proceed with standard methods of numerical linear algebra,
there is a risk that numerical instabilities in the computation of the rank
could lead to an incorrect number of basis matrices, which could break
equivariance. We thus take a combinatorial approach to obtain an exact basis
set as described next.

We construct a simple directed graph $\Gamma$ to encode the (signed)
permutation of matrix elements under the mapping
$X\rightarrow\rho(g)X\pi(g)^{\top}\forall g\in G_{0}$. The nodes of $\Gamma$
are the ordered pairs $(i,j)$ indexing the elements in $X$, and we draw an arc
from $(i,j)$ to $(k,\ell)$ iff the former is sent to the latter under the
above mapping for some $g\in G_{0}$; moreover, we assign the arc a value
$z_{ij,k\ell}\in\\{-1,1\\}$ to indicate whether a sign flip is incurred. With
the graph $\Gamma$ in hand, a matrix $X$ is a solution to the linear
equivariance condition iff all constraints $x_{ij}=z_{ij,k\ell}x_{k\ell}$ are
satisfied. We are thus able to assign node values $x_{ij}$ independently
across the connected components of $\Gamma$; based on this, we generate the
desired basis set by processing each connected component $C$ as follows:

  1. Case 1.

Suppose $C$ is $2$-colorable, meaning that each node $(i,j)\in C$ can be
assigned a value $x_{ij}\in\\{-1,1\\}$ such that the constraints
$x_{ij}=z_{ij,k\ell}x_{k\ell}$ are satisfied within $C$. Then we select such
an assignment (by greedy $2$-coloring), and we assign all nodes outside $C$
the value zero. These values together yield a basis matrix.

  2. Case 2.

Suppose $C$ is not $2$-colorable. Then the only consistent assignment of
values inside $C$ is all zeros, and no basis matrix is returned for this
component.

Observe that no two basis matrices share a nonzero value in the same position,
and hence the matrices are indeed linearly independent.

###  B.3 Admissible architectures

####  B.3.1 The $\theta$ function

The following proposition establishes the invariance and equivariance of the
function $\theta$ with respect to certain conjugations.

###### Proposition 8

The function $\theta$ satisfies the following properties:

  1. (a)

For every $A\in\operatorname{P}(|G/J|)$, define the ordinary perm-rep
$\pi^{A}_{J}(g)=A\pi_{J}(g)A^{-1}$. Then $\theta(\cdot,\cdot,J)$ is invariant
under the conjugation $\pi_{J}\mapsto\pi^{A}_{J}$.

  2. (b)

$\theta(H,K,gJg^{-1})=\theta(H,K,J)\forall g\in G$.

  3. (c)

$\theta(gHg^{-1},gKg^{-1},J)=g\theta(H,K,J)g^{-1}$.

Proof  (a)  For brevity, let $\kappa=|H:K|-1$. Define the function
$\theta^{A}$ in identical fashion to $\theta$, but replace $\pi_{J}$ with
$\pi^{A}_{J}$. We wish to prove $\theta^{A}=\theta$. Since the map
$\Gamma\mapsto P_{\Gamma}$ from finite orthogonal matrix groups to orthogonal
projection operators is equivariant with respect to conjugation, then we have

$\displaystyle\theta^{A}(H,K,J)$ $\displaystyle=\\{g\in
G:\pi^{A}_{J}(g)(P_{\pi_{J}^{A}(K)}-\kappa
P_{\pi_{J}^{A}(H)})=P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}(H)}\\}$
$\displaystyle=\\{g\in G:A\pi_{J}(g)A^{-1}(P_{A\pi_{J}(K)A^{-1}}-\kappa
P_{A\pi_{J}(H)A^{-1}})=P_{A\pi_{J}(K)A^{-1}}-\kappa P_{A\pi_{J}(H)A^{-1}}\\}$
$\displaystyle=\\{g\in G:A\pi_{J}(g)A^{-1}(AP_{\pi_{J}(K)}A^{-1}-\kappa
AP_{\pi_{J}(H)}A^{-1})=AP_{\pi_{J}(K)}A^{-1}$ $\displaystyle\quad-\kappa
AP_{\pi_{J}(H)}A^{-1}\\}$ $\displaystyle=\\{g\in
G:\pi_{J}(g)(P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-\kappa
P_{\pi_{J}(H)}\\}$ $\displaystyle=\theta(H,K,J).$

(b)  The theory of ordinary perm-irreps and their correspondence to group
action on cosets is well-understood (Burnside, 1911; Bouc, 2000), and it is
known that the conjugation of $J$ in $\pi_{J}$ is equivalent to the
conjugation of $\pi_{J}$ itself. The claim thus follows by part (a).

(c)  Let $a\in G$. We will show $\theta(aHa^{-1},aKa^{-1},J)=\theta(H,K,J)$.
Note $\kappa=|H:K|-1$ is invariant under the conjugation of $(H,K)$ by $a$.
Also note $\pi_{J}(aHa^{-1})=\pi_{J}(a)\pi_{J}(H)\pi_{J}(a)^{-1}$ and similar
for $K$. Letting $A=\pi_{J}(a)$ and proceeding in analogy to part (a), we have

$\displaystyle\theta(aHa^{-1},aKa^{-1},J)$ $\displaystyle=\\{g\in
G:\pi_{J}(g)(P_{\pi_{J}(aKa^{-1})}-\kappa
P_{\pi_{J}(aHa^{-1})})=P_{\pi_{J}(aKa^{-1})}$ $\displaystyle\quad-\kappa
P_{\pi_{J}(aHa^{-1})}\\}$ $\displaystyle=\\{g\in
G:\pi_{J}(g)(P_{\pi_{J}^{A}(K)}-\kappa
P_{\pi_{J}^{A}(H)})=P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}(H)}\\}$
$\displaystyle=\\{g\in G:\pi_{J}(g)(AP_{\pi_{J}(K)}A^{-1}-\kappa
AP_{\pi_{J}(H)}A^{-1})=AP_{\pi_{J}(K)}A^{-1}$ $\displaystyle\quad-\kappa
AP_{\pi_{J}(H)}A^{-1}\\}$ $\displaystyle=\\{g\in
G:A^{-1}\pi_{J}(g)A(P_{\pi_{J}(K)}-\kappa
P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)}\\}$
$\displaystyle=\\{g\in G:\pi_{J}(a^{-1}ga)(P_{\pi_{J}(K)}-\kappa
P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)}\\}.$

By the change of variables $g\rightarrow aga^{-1}$, we have

$\displaystyle\theta(aHa^{-1},aKa^{-1},J)$ $\displaystyle=\\{aga^{-1}\in
G:\pi_{J}(g)(P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-\kappa
P_{\pi_{J}(H)}\\}$ $\displaystyle=a\\{g\in G:\pi_{J}(g)(P_{\pi_{J}(K)}-\kappa
P_{\pi_{J}(H)})=P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)}\\}a^{-1}$
$\displaystyle=a\theta(H,K,J)a^{-1},$

establishing the claim.

Algorithm 2 Implementation of the function $\theta$ that exploits existing
functions in GAP.

1:function $\theta$($H$, $K$, $J$)

2: def $\eta:K\setminus G/J\mapsto\operatorname{power}(G/J)$ by

3: $\eta(KxJ)=\\{kxJ\in G/J:k(K\cap xJx^{-1})\in K/(K\cap xJx^{-1})\\}$

4: if $|H:K|=2$ then

5: let $h\in H\setminus K$

6: $S\leftarrow\\{KxJ\in K\setminus G/J:hx\in KxJ\\}$

7: else

8: $S\leftarrow\emptyset$

9: if $S=\emptyset$ then

10: $T\leftarrow\\{\eta(KxJ):KxJ\in K\setminus G/J\\}$

11: else

12: $T\leftarrow\\{\eta(KxJ):KxJ\in(K\setminus G/J)\setminus
S\\}\cup\left\\{\bigcup_{KxJ\in S}\eta(KxJ)\right\\}$

13: return $\operatorname{st}_{G}(T)$

Algorithm 2 gives the pseudocode for an implementation of the function
$\theta$ that can be accomplished in the GAP language (GAP, ) for
computational group theory. Although the definition of the $\theta$ function
involves orthogonal projection operators, Alg. 2 completely circumvents these
operators by taking a pure group-theoretic approach in terms of double cosets.
The following proposition verifies that Alg. 2 is a correct implementation.

###### Proposition 9

Algorithm 2 correctly implements the function $\theta$.

Proof  Observe that the function $\eta$ in Alg. 2 sends each double coset
$KxJ\in K\setminus G/J$ to the set of cosets in $G/J$ whose disjoint union is
$KxJ$.

Let $H,K,J\leq G$ such that $K\leq H$ and $|H:K|\leq 2$. Let
$w\in\operatorname{ran}(P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi(H)})$. We regard $w$ as
a function $w:G/J\mapsto\mathbb{R}$. Since $w\in\operatorname{ran}(P_{K})$,
then $w$ is $K$-invariant in the sense that $w(kxJ)=w(xJ)$ for all $k\in K$
and $xJ\in G/J$. Thus, $w$ is constant over the set $\eta(KxJ)$ for every
$KxJ\in K\setminus G/J$.

If $|H:K|=2$, then let $h\in H\setminus K$. Since
$w\in\operatorname{ran}(P_{\pi_{J}(K)}-P_{\pi_{J}(H)})$, then
$w(hKxJ)=-w(KxJ)$ for every $KxJ\in K\setminus G/J$. Thus, if $hKxJ=KxJ$, then
$w(KxJ)=0$. Since $K\trianglelefteq H$, then $hKxJ=KxJ$ is equivalent to
$KhxJ=KxJ$, or just $hx\in KxJ$. We thus have the constraint

$w(KxJ)=0\forall KxJ\in K\setminus G/J\mid hx\in KxJ.$

Now select $w$ such that it takes a different nonzero value over each
$\eta(KxJ)$ for all $KxJ\in K\setminus G/J$ such that, if $|H:K|=2$, then
$hx\notin KxJ$. Then

$\displaystyle\theta(H,K,J)$
$\displaystyle=\operatorname{st}_{G}(P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J}(H)})$
$\displaystyle=\operatorname{st}_{G}(w)$ $\displaystyle=\\{g\in
G:w(gKxJ)=w(KxJ)\forall KxJ\in K\setminus G/J\\}.$

This means $\theta(H,K,J)$ is exactly the subgroup of $G$ that leaves the
level sets of $w$ invariant. Observe, however, that the sets in the collection
$T$ in Alg. 2 are exactly the level sets of $w$, and hence
$\theta(H,K,J)=\operatorname{st}_{G}(T)$.

####  B.3.2 The $\phi$ function

Proof [Proof of Prop. 7] The necessity of condition (2) is only because if
$H^{(1)}_{j}=G$ for any $j$, then at least one row $w$ of $W^{(1)}$ satisfies
$w\in\operatorname{ran}(P_{G})$ by Thm. 4a of Agrawal and Ostrowski (2022).
For $w$ to be nonzero, we thus require $P_{G}\neq 0$. We assume condition (2)
to be satisfied for the remainder of the proof.

Before proving the claim itself, we first derive a closed-form expression for
$\phi^{(i+1)}$. For notational convenience, for every $K\leq H\leq G$,
$|H:K|\leq 2$, and linear rep $\tau:G\mapsto\operatorname{GL}(n,\mathbb{R})$,
define

$\theta(H,K;\tau)=\\{g\in
G:\tau(g)(P_{\tau(K)}-(|H:K|-1)P_{\tau(H)})=P_{\tau(K)}-(|H:K|-1)P_{\tau(H)}\\}.$

Thus, $\theta(H,K,J)$ can be equivalently written as $\theta(H,K;\pi_{J})$.
For two reps $\tau_{1}$ and $\tau_{2}$, observe that
$P_{\tau_{1}\oplus\tau_{2}}=P_{\tau_{1}}\oplus P_{\tau_{2}}$ and hence

$\theta(H,K;\tau_{1}\oplus\tau_{2})=\theta(H,K;\tau_{1})\cap\theta(H,K;\tau_{2}).$

This property extends to more than two reps in the obvious way. With this
notation, and recalling the identity rep $\pi^{(0)}:G\mapsto G$, the function
$\phi^{(i+1)}$ can be rewritten as

$\displaystyle\phi^{(i+1)}(H,K)$
$\displaystyle=\operatorname{st}_{G}(P_{K}-(|H:K|-1)P_{H})\cap\bigcap_{j=1}^{i}\bigcap_{r=1}^{r^{(j)}}\theta(H,K,H^{(j)}_{r})$
$\displaystyle=\theta(H,K;\pi^{(0)})\cap\bigcap_{j=1}^{i}\bigcap_{r=1}^{r^{(j)}}\theta(H,K;\pi^{(j)}_{r})$
$\displaystyle=\theta(H,K;\pi^{(0)})\cap\theta\left(H,K;\bigoplus_{j=1}^{i}\bigoplus_{r=1}^{r^{(j)}}\pi^{(j)}_{r}\right)$
$\displaystyle=\theta\left(H,K;\pi^{(0)}\oplus\bigoplus_{j=1}^{i}\pi^{(j)}\right)$
$\displaystyle=\theta\left(H,K;\bigoplus_{j=0}^{i}\pi^{(j)}\right)$
$\displaystyle=\theta(H,K;\Pi^{(i)}).$

This is explicitly

$\displaystyle\phi^{(i+1)}(H,K)$ $\displaystyle=\\{g\in
G:\Pi^{(i)}(g)(P_{\Pi^{(i)}(K)}-(|H:K|-1)P_{\Pi^{(i)}(H)})=P_{\Pi^{(i)}(K)}$
$\displaystyle\quad-(|H:K|-1)P_{\Pi^{(i)}(H)}\\},$

and it is equivalent to

$\displaystyle\phi^{(i+1)}(H,K)$ $\displaystyle=\\{g\in
G:\Pi^{(i)}(g)(P_{\Pi^{(i)}(K)}-(|\Pi^{(i)}(H):\Pi^{(i)}(K)|-1)P_{\Pi^{(i)}(H)})=P_{\Pi^{(i)}(K)}$
$\displaystyle\quad-(|\Pi^{(i)}(H):\Pi^{(i)}(K)|-1)P_{\Pi^{(i)}(H)}\\}.$ (*)

To see that $|\Pi^{(i)}(H):\Pi^{(i)}(K)|=|H:K|$, by the First Isomorphism
Theorem we have

$|\Pi^{(i)}(H):\Pi^{(i)}(K)|=\frac{|H|/|H\cap\ker(\Pi^{(i)})|}{|K|/|K\cap\ker(\Pi^{(i)})|}.$

Since $\Pi^{(i)}$ includes in its direct sum decomposition the identity rep
$\pi^{(0)}$, then $\ker(\Pi^{(i)})$ must be trivial, and so the above
expression reduces to $|H|/|K|=|H:K|$.

We finally prove the claim. By definition, the $G$-DNN architecture
$\\{\rho^{(1)},\ldots,\rho^{(d)}\\}$ is admissible iff each row of $W^{(i)}$
is nonzero and no two rows of $[W^{(i)}\mid b^{(i)}]$ are parallel, for
$i\in\\{1,\ldots,d\\}$. By Thm. 6 (a), since $W^{(i)}=V^{(i)}A^{(i-1)}$, then
we obtain an equivalent definition if we replace $W^{(i)}$ with $V^{(i)}$. Let
$V^{(i)}_{(j)}$ be the submatrix comprising the rows (and all columns) of
$V^{(i)}$ that together transform by $\rho^{(i)}_{j}$:

$\rho^{(i)}_{j}(g)V^{(i)}_{(j)}=V^{(i)}_{(j)}\Pi^{(i-1)}(g)\forall g\in G.$

(We include the parentheses in the subscript of $V^{(i)}_{(j)}$ to distinguish
it from $V^{(i)}_{j}$ appearing in Thm. 6 (a)). Then Thm. 4a of Agrawal and
Ostrowski (2022) implies we have an admissible architecture (specifically,
that the rows of $V^{(i)}_{(j)}$ are nonzero and no two rows of the
corresponding augmented weight matrix are parallel) iff

$\operatorname{st}_{\Pi^{(i-1)}(G)}(P_{\Pi^{(i-1)}(K^{(i)}_{j})}-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})})=\Pi^{(i-1)}(K^{(i)}_{j}),$

or equivalently,

$(\Pi^{(i-1)})^{-1}[\operatorname{st}_{\Pi^{(i-1)}(G)}(P_{\Pi^{(i-1)}(K^{(i)}_{j})}-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})})=K^{(i)}_{j}$
$\displaystyle\\{g\in
G:\Pi^{(i-1)}(g)(P_{\Pi^{(i-1)}(K^{(i)}_{j})}-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})})=P_{\Pi^{(i-1)}(K^{(i)}_{j})}$
$\displaystyle\quad-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})}=K^{(i)}_{j}.$

Recalling (*), we recognize the last equation as nothing but
$\phi^{(i)}(H^{(i)}_{j},K^{(i)}_{j})=K^{(i)}_{j}$, there proving that
condition (1) is (together with condition (2)) is equivalent to admissibility.

###  B.4 Additional remarks

The following proposition establishes the compatibility of batchnorm with
$G$-DNNs.

###### Proposition 10

The addition of batchnorm immediately after any ReLU layer in a $G$-DNN
preserves $G$-invariance of the network.

Proof  Suppose we apply batchnorm immediately after the $i$th ReLU layer of
the $G$-DNN $f$, for some $i\in\\{1,\ldots,d-1\\}$. Then the activations
$r^{(i)}(x)=\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)})$ of the $i$th ReLU
layer transform as

$r^{(i)}(x)\rightarrow\gamma\left(\frac{r^{(i)}(x)-\mu\vec{1}}{\sigma+\varepsilon}\right)+\beta\vec{1},$

where $\mu\geq 0$, $\sigma\geq 0$, $\varepsilon>0$, $\gamma$, and $\beta$ are
all scalars. For each $i\in\\{1,\ldots,d\\}$, let $W^{(i)}_{i}$ and
$V^{(i)}_{i}$ be the blocks comprising the first $n_{i}$ columns of $W^{(i)}$
and $V^{(i)}$ respectively; these represent the weights of the $i$th layer
without the skip connections. Then the above affine transformation of
$r^{(i)}(x)$ is equivalent to the transformation

$\displaystyle W^{(i+1)}_{i+1}$ $\displaystyle\rightarrow CW^{(i+1)}_{i+1}$
$\displaystyle b^{(i+1)}$ $\displaystyle\rightarrow
b^{(i+1)}+DW^{(i+1)}_{i+1}\vec{1},$

where

$\displaystyle C$ $\displaystyle=\frac{\gamma}{\sigma+\varepsilon}$
$\displaystyle D$ $\displaystyle=\beta-\frac{\gamma\mu}{\sigma+\varepsilon}.$

By Thm. 6 (a), $W^{(i+1)}=V^{(i+1)}A^{(i)}$. Since $A^{(i)}$ is upper block-
triangular with the top left block $I_{n_{i+1}}$, then
$W^{(i+1)}_{i+1}=V^{(i+1)}_{i+1}$. By the above transformation of
$W^{(i+1)}_{i+1}$ under batchnorm, $V^{(i+1)}_{i+1}$ also transforms only by
the scalar factor $C$, and hence it remains equivariant as in Thm. 6a.

All that remains is to show the bias $b^{(i+1)}$ satisfies the sufficient
condition in Lemma 4 even after the batchnorm transformation, and this will
establish $G$-invariance of the network with batchnorm.

Case 1:  Suppose $\rho^{(i+1)}$ is type 1 irreducible. Then Lemma 4 implies
$b^{(i+1)}$ is parallel to $\vec{1}$. Under batchnorm, $b^{(i+1)}$ transforms
by the addition of $DV^{(i+1)}_{i+1}\vec{1}$ and thus remains parallel to
$\vec{1}$. The claim follows by Lemma 4.

Case 2:  Suppose $\rho^{(i+1)}$ is type 2 irreducible. Then Lemma 4 implies
$b^{(i+1)}=0$. Under batchnorm, the bias thus transforms to
$0+DV^{(i+1)}_{i+1}\vec{1}$. It turns out, however, that
$V^{(i+1)}_{i+1}\vec{1}=0$; to see this, by Thm. 6 (a), we have

$\rho^{(i+1)}(g)V^{(i+1)}_{i+1}=V^{(i+1)}_{i+1}\pi^{(i)}(g)\forall g\in G.$

Since $i\geq 1$ so that $\pi^{(i)}$ is type 1, then without loss of
generality, by selecting an appropriate basis, we assume $\pi^{(i)}$ is an
ordinary perm-irrep. Averaging both sides over all $g\in G$, we obtain

$P_{\rho^{(i+1)}}V^{(i+1)}_{i+1}=V^{(i+1)}_{i+1}P_{\pi^{(i)}}.$

Since $\rho^{(i+1)}$ is type 2, then its only fixed point is the zero vector,
and hence the orthogonal projection operator $P_{\rho^{(i+1)}}$ is itself
zero. Moreover, since $\pi^{(i)}$ is an ordinary perm-irrep and since
$\vec{1}$ is fixed under all permutations, then it is fixed under the
orthogonal projection operator $P_{\pi^{(i)}}$ as well– hence
$V^{(i+1)}_{i+1}\vec{1}=0$.

Case 3:  Suppose $\rho^{(i+1)}$ is reducible. Then decompose it into type1 and
type 2 irreps and apply Cases 1-2 separately to each irrep.

The extension of Prop. 10 to multiple channels is trivial. Batchnorm is
typically applied independently to each channel. Thus, if the ReLU activations
$r^{(i)}(x)$ had $c$ channels (which could be achieved by having $c$ copies of
every irrep in $\rho^{(i)}$), then the variables $\mu$, $\sigma$, $\gamma$,
and $\beta$ would be $c$-dimensional vectors. The proof would then proceed by
selecting a single arbitrary channel.

##  Appendix C Examples

###  C.1 Concatenated ReLU

Proof [Proof of Ex. 1] For every $i\in\\{1,\ldots,d\\}$, the function

$x\rightarrow
U^{(i)}\operatorname{CReLU}(U^{(i-1)}\cdots\operatorname{CReLU}(U^{(1)}x)\cdots)$

is $G$-equivariant with its output transforming by $\rho^{(i)}$. We thus
identify it with the function $g^{(i)}$ appearing in Thm. 6 (b). We now have
the recursion

$g^{(i+1)}(x)=U^{(i+1)}\operatorname{CReLU}(g^{(i)}(x))\forall
i\in\\{1,\ldots,d-1\\}.$

By definition of $\operatorname{CReLU}(\cdot)$ and the block structure of
$U^{(i+1)}$, we have

$\displaystyle g^{(i+1)}(x)$
$\displaystyle=\begin{bmatrix}U^{(i+1)}_{1}&U^{(i+1)}_{2}\end{bmatrix}\operatorname{ReLU}\left(\begin{bmatrix}g^{(i)}(x)\\\
-g^{(i)}(x)\end{bmatrix}\right)$
$\displaystyle=U^{(i+1)}_{1}\operatorname{ReLU}(g^{(i)}(x))+U^{(i+1)}_{2}\operatorname{ReLU}(-g^{(i)}(x))$
$\displaystyle=U^{(i+1)}_{1}\operatorname{ReLU}(g^{(i)}(x))+U^{(i+1)}_{2}\operatorname{ReLU}(g^{(i)}(x))-U^{(i+1)}_{2}g^{(i)}(x)$
$\displaystyle=(U^{(i+1)}_{1}+U^{(i+1)}_{2})\operatorname{ReLU}(g^{(i)}(x))-U^{(i+1)}_{2}g^{(i)}(x)$
$\displaystyle=(U^{(i+1)}_{1}+U^{(i+1)}_{2})\operatorname{ReLU}(g^{(i)}(x))-\frac{1}{2}(U^{(i+1)}_{1}+U^{(i+1)}_{2})g^{(i)}(x)+\frac{1}{2}(U^{(i+1)}_{1}-U^{(i+1)}_{2})g^{(i)}(x)$
$\displaystyle=\begin{bmatrix}U^{(i+1)}_{1}+U^{(i+1)}_{2}&\frac{1}{2}(U^{(i+1)}_{1}-U^{(i+1)}_{2})\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(x))-\frac{1}{2}g^{(i)}(x)\\\
g^{(i)}(x)\end{bmatrix}.$

Since $g^{(i)}(x)=V^{(i)}h^{(i)}(x)$ in Thm. 6 (b) and since all bias vectors
in this example are zero, then we can write the above as

$g^{(i+1)}(x)=\begin{bmatrix}U^{(i+1)}_{1}+U^{(i+1)}_{2}&\frac{1}{2}(U^{(i+1)}_{1}-U^{(i+1)}_{2})V^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(x)+b^{(i)})-\frac{1}{2}g^{(i)}(x)\\\
h^{(i)}(x)\end{bmatrix}.$

Comparing this to the definitions of $g^{(i+1)}$ and $h^{(i+1)}$ appearing in
Thm. 6 (b), we obtain the expression for $V^{(i+1)}$ as claimed.

###  C.2 Binary multiplication

Proof [Proof of Ex. 2] (a)  For $x_{1},x_{2}\in\\{-1,1\\}$, it can be verified
by hand that

$\displaystyle x_{1}x_{2}$
$\displaystyle=\begin{bmatrix}1&-1\end{bmatrix}\operatorname{ReLU}\left(\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\end{bmatrix}\right)-x_{2}$
$\displaystyle=\begin{bmatrix}1&-1&0&-1\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}\left(\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\end{bmatrix}\right)\\\
\begin{bmatrix}x_{1}\\\ x_{2}\end{bmatrix}\end{bmatrix}.(*)$

We can extend this to the product of more than two elements as follows: For
$i\in\\{1,\ldots,d\\}$, define the block-diagonal matrices

$\displaystyle A^{(i)}$
$\displaystyle=I_{m/2^{i}}\begin{bmatrix}1&-1\end{bmatrix}$ $\displaystyle
B^{(i)}$ $\displaystyle=I_{m/2^{i}}\begin{bmatrix}0&-1\end{bmatrix}$
$\displaystyle C^{(i)}$ $\displaystyle=I_{m/2^{i}}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix},$

and define the functions $p^{(i)}:\mathcal{X}\mapsto\\{-1,1\\}^{m/2^{i}}$ by

$\displaystyle p^{(1)}(x)$ $\displaystyle=A^{(1)}x$ $\displaystyle p^{(i)}(x)$
$\displaystyle=\begin{bmatrix}A^{(i)}&B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(C^{(i)}p^{(i-1)}(x))\\\
p^{(i-1)}(x)\end{bmatrix}\forall i\in\\{2,\ldots,d\\}.(**)$

The function $p^{(1)}$ maps each pair of elements $(x_{2i-1},x_{2i})$ in the
input $x$ to $x_{2i-1}-x_{2i}\in\\{-1,1\\}$. Then $p^{(i)}$ (1) partitions
$p^{(1)}(x)$ into blocks, each of two elements; (2) takes the product of each
pair of elements using (*); (3) iterates this procedure $i-1$ times. The
output $p^{(d)}(x)$ is then the product of the elements in $p^{(1)}(x)$.

Now for $i\in\\{1,\ldots,d-1\\}$, the function $g^{(i)}$ (as in Thm. 6 (b)) as
given by $g^{(i)}(x)=C^{(i+1)}p^{(i)}(x)$. By (**), we thus have

$\displaystyle g^{(i)}(x)$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)+\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle\quad+\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\frac{1}{2}g^{(i-1)}(x)\\\
0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}+\frac{1}{2}C^{(i+1)}A^{(i)}g^{(i-1)}(x)$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle\quad+\frac{1}{2}C^{(i+1)}A^{(i)}C^{(i)}p^{(i-1)}(x)$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}+\frac{1}{2}C^{(i+1)}A^{(i)}C^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&0\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
p^{(i-1)}(x)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}C^{(i+1)}A^{(i)}&0\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\\
h^{(i-1)}(x)\end{bmatrix}.$

Comparing this to the equations in Thm. 6 (b), we establish the claimed
expression for $V^{(i)}_{j}$ for $i\in\\{1,\ldots,d-1\\}$.

For the case $i=d$, we simply observe that the last weight matrix must be the
outer weight vector in (*). The $G$-invariance of the constructed DNN is
clear; the action of any $g\in G$ on an input $x\in\mathcal{X}$ corresponds to
an even number of sign flips in $p^{(1)}(x)$, which leaves the parity of the
product $p^{(d)}(x)$ invariant. Layerwise $G$-equivariance is established
next.

(b)  By part (a), The first weight matrix is

$C^{(2)}A^{(1)}=I_{m/4}\otimes\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix}.$

The $j$th pair of rows in this weight matrix is the $j$th channel, whose first
row is $v_{j}$ and which transforms by $\rho_{H^{(1)}_{j}K^{(1)}_{j}}$. The
expressions for $H^{(1)}_{j}$ and $K^{(1)}_{j}$ are thus established by
definition.

Now for $i\in\\{1,\ldots,d\\}$, part (a) implies

$\rho_{H^{(i+1)}_{j}K^{(i+1)}_{j}}(g)\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix}=\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix}\begin{bmatrix}\pi_{H^{(i)}_{2j-1}}(g)&0\\\
0&\pi_{H^{(i)}_{2j}}(g)\end{bmatrix}\forall g\in G,$

where each $\pi_{H^{(i)}_{k}}$ is the ordinary perm-rep part of
$\rho_{H^{(i)}_{k}K^{(i)}_{k}}$. By definition, $K^{(i+1)}_{j}$ is the
subgroup of all $g\in G$ such that

$\displaystyle\rho_{H^{(i+1)}_{j}K^{(i+1)}_{j}}(g)e_{1}$ $\displaystyle=e_{1}$
$\displaystyle\frac{1}{2}\rho_{H^{(i+1)}_{j}K^{(i+1)}_{j}}(g)\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix}\begin{bmatrix}1\\\ 0\\\ 1\\\ 0\end{bmatrix}$
$\displaystyle=e_{1}$ $\displaystyle\frac{1}{2}\begin{bmatrix}1&-1&1&-1\\\
1&-1&-1&1\end{bmatrix}\begin{bmatrix}\pi_{H^{(i)}_{2j-1}}(g)&0\\\
0&\pi_{H^{(i)}_{2j}}(g)\end{bmatrix}\forall g\in G\begin{bmatrix}1\\\ 0\\\
1\\\ 0\end{bmatrix}$ $\displaystyle=e_{1}.$

Since ordinary perm-reps cannot flip signs, then the last equation is
equivalent to

$\pi_{H^{(i)}_{2j-1}}e_{1}=e_{1}\mbox{ and }\pi_{H^{(i)}_{2j}}e_{1}=e_{1}.$

We thus have

$\displaystyle K^{(i+1)}_{j}$ $\displaystyle=\\{g\in
G:\pi_{H^{(i)}_{2j-1}}e_{1}=e_{1}\\}\cap\\{g\in
G:\pi_{H^{(i)}_{2j}}e_{1}=e_{1}\\}$ $\displaystyle=H^{(i)}_{2j-1}\cap
H^{(i)}_{2j}.$

Similarly, by definition we have

$H^{(i+1)}_{j}=\\{g\in G:\rho_{H^{(i+1)}_{j}K^{(i+1)}_{j}}(g)e_{1}=\pm
e_{1}\\}.$

Proceeding analogously as above, we find that $g\in G$ is contained in
$H^{(i+1)}_{j}$ iff

$(\pi_{H^{(i)}_{2j-1}}(g)e_{1}=e_{1}\mbox{ and
}\pi_{H^{(i)}_{2j}}(g)e_{1}=e_{1})\mbox{ or
}(\pi_{H^{(i)}_{2j-1}}(g)e_{1}=e_{2}\mbox{ and
}\pi_{H^{(i)}_{2j}}(g)e_{1}=e_{2}).$

The first term in the disjunction corresponds to $H^{(i)}_{2j-1}\cap
H^{(i)}_{2j}$, and the second term in the disjunction corresponds to the
intersection of the complements, as claimed.

In the case of the $(d-1)$st layer, the product output $p^{(d-1)}(x)$ is 2D
and thus can only transform by $\pm 1$. The rep $\rho^{(d-)}$ thus decomposes
into two copies of a scalar rep. Finally, that the final rep $\rho^{(d)}$ is
trivial follows from the $G$-invariance of the network, thereby completing the
proof.

## References

  * Agrawal and Ostrowski (2022) Devanshu Agrawal and James Ostrowski.  A classification of $G$-invariant shallow neural networks.  _Advances in Neural Information Processing Systems_ , 35, 2022.
  * Agrawal et al. (2023) Devanshu Agrawal, Adrian Del Maestro, Steven Johnston, and James Ostrowski.  Group-equivariant autoencoder for identifying spontaneously broken symmetries.  _Physical Review E_ , 107(5):054104, 2023.
  * Atz et al. (2021) Kenneth Atz, Francesca Grisoni, and Gisbert Schneider.  Geometric deep learning on molecular representations.  _Nature Machine Intelligence_ , 3(12):1023–1032, 2021.
  * Baake (1984) Michael Baake.  Structure and representations of the hyperoctahedral group.  _Journal of mathematical physics_ , 25(11):3171–3182, 1984.
  * Balduzzi et al. (2017) David Balduzzi, Marcus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams.  The shattered gradients problem: If resnets are the answer, then what is the question?  In _International Conference on Machine Learning_ , pages 342–350. PLMR, 2017.
  * Basu et al. (2021) Sourya Basu, Akshayaa Magesh, Harshit Yadav, and Lav R Varshney.  Autoequivariant network search via group decomposition.  _arXiv preprint arXiv:2104.04848_ , 2021.
  * Bouc (2000) Serge Bouc.  Burnside rings.  In _Handbook of algebra_ , volume 2, pages 739–804. Elsevier, 2000\.
  * Bronstein et al. (2021) Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.  _arXiv preprint arXiv:2104.13478_ , 2021.
  * 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 and Welling (2017) Taco S. Cohen and Max Welling.  Steerable cnns.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017.  URL https://openreview.net/forum?id=rJQKYt5ll.
  * 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.
  * Esteves et al. (2018) Carlos Esteves, Christine Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis.  Learning so (3) equivariant representations with spherical cnns.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 52–68, 2018.
  * Finzi et al. (2021) Marc Finzi, Max Welling, and Andrew Gordon Wilson.  A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups.  In _International conference on machine learning_ , pages 3318–3328. PLMR, 2021.
  * (15) GAP.  GAP – Groups, Algorithms, and Programming, Version 4.11.1.  https://www.gap-system.org, 2021.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4700–4708, 2017.
  * Jiang et al. (2019) Chiyu Jiang, Jingwei Huang, Karthik Kashinath, Prabhat, Philip Marcus, and Matthias Nießner.  Spherical cnns on unstructured grids.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_ , 2019.  URL https://openreview.net/forum?id=Bkl-43C9FQ.
  * Kaba and Ravanbakhsh (2022) Oumar Kaba and Siamak Ravanbakhsh.  Equivariant networks for crystal structures.  _Advances in Neural Information Processing Systems_ , 35:4150–4164, 2022.
  * 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.
  * Kicki et al. (2021) Piotr Kicki, Piotr Skrzypczyński, and Mete Ozay.  A new approach to design symmetry invariant neural networks.  In _2021 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE, 2021.
  * 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.
  * Luo et al. (2021) Di Luo, Giuseppe Carleo, Bryan K Clark, and James Stokes.  Gauge equivariant neural networks for quantum lattice gauge theories.  _Physical review letters_ , 127(27):276402, 2021\.
  * Maile et al. (2022) Kaitlin Maile, Dennis George Wilson, and Patrick Forré.  Equivariance-aware architectural optimization of neural networks.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Mallet and Vert (2021) Vincent Mallet and Jean-Philippe Vert.  Reverse-complement equivariant networks for dna sequences.  _Advances in Neural Information Processing Systems_ , 34:13511–13523, 2021.
  * Maron et al. (2019a) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  volume 7, 2019a.
  * Maron et al. (2019b) 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, 2019b.
  * Musallam et al. (2022) Mohamed Adel Musallam, Vincent Gaudilliere, Miguel Ortiz Del Castillo, Kassem Al Ismaeil, and Djamila Aouada.  Leveraging equivariant features for absolute pose regression.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6876–6886, 2022.
  * Ravanbakhsh (2020) Siamak Ravanbakhsh.  Universal equivariant multilayer perceptrons.  In _International Conference on Machine Learning_ , pages 7996–8006. PMLR, 2020.
  * Ravanbakhsh et al. (2017) Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos.  Equivariance through parameter-sharing.  In _International conference on machine learning_ , pages 2892–2901. PLMR, 2017.
  * Shang et al. (2016) Wenling Shang, Kihyuk Sohn, Diogo Almeida, and Honglak Lee.  Understanding and improving convolutional neural networks via concatenated rectified linear units.  In _international conference on machine learning_ , pages 2217–2225. PMLR, 2016.
  * Shang et al. (2017) Wenling Shang, Justin Chiu, and Kihyuk Sohn.  Exploring normalization in deep residual networks with concatenated rectified linear units.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * 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.
  * Wu et al. (2015) Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3d shapenets: A deep representation for volumetric shapes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1912–1920, 2015.
  * Zhou et al. (2022) Hannah Zhou, Avanti Shrikumar, and Anshul Kundaje.  Towards a better understanding of reverse-complement equivariance for deep learning models in genomics.  In _Machine Learning in Computational Biology_ , pages 1–33. PMLR, 2022.