# Autoequivariant Network Search via Group Decomposition

Sourya Basu
Department of Electrical
and Computer Engineering
University of Illinois at Urbana-Champaign
Illinois, USA
<EMAIL_ADDRESS>
&Akshayaa Magesh
Department of Electrical
and Computer Engineering
University of Illinois at Urbana-Champaign
Illinois, USA
<EMAIL_ADDRESS>
Harshit Yadav∗
Department of Mathematics
Rice University
Texas, USA
<EMAIL_ADDRESS>
&Lav R. Varshney
Department of Electrical
and Computer Engineering
University of Illinois at Urbana-Champaign
Illinois, USA
<EMAIL_ADDRESS>
equal contribution

###### Abstract

Recent works show that group equivariance as an inductive bias improves neural
network performance for both classification and generation. However, designing
group-equivariant neural networks is challenging when the group of interest is
large and is unknown. Moreover, inducing equivariance can significantly reduce
the number of independent parameters in a network with fixed feature size,
affecting its overall performance. We address these problems by proving a new
group-theoretic result in the context of equivariant neural networks that
shows that a network is equivariant to a large group if and only if it is
equivariant to smaller groups from which it is constructed. Using this result,
we design a novel fast group equivariant construction algorithm, and a deep
Q-learning-based search algorithm in a reduced search space, yielding what we
call _autoequivariant networks_ (AENs). AENs find the right balance between
equivariance and network size when tested on new benchmark datasets, G-MNIST
and G-Fashion-MNIST, obtained via group transformations on MNIST and Fashion-
MNIST respectively that we release. Extending these results to group
convolutional neural networks, where we optimize between equivariances,
augmentations, and network sizes, we find group equivariance to be the most
dominating factor in all high-performing GCNNs on several datasets like
CIFAR10, SVHN, RotMNIST, ASL, EMNIST, and KMNIST.

##  1 Introduction

Recent progress in deep learning owes much of its success to novel network
architectures for efficient processing of large datasets. One example for
image, video, and audio data is the convolutional neural network (CNN) [1].
CNNs efficiently process high-dimensional data using two key principles:
_translation equivariance_ and _parameter sharing_. The convolutional layers
in CNNs are translation equivariant, so when the input to these layers is
shifted in space, the extracted features also get shifted. Translation
equivariance encodes the prior that translating an input does not change its
labels into the neural network and helps efficiently extract features from raw
data. Parameter sharing then not only efficiently uses parameters, but also
helps induce translation equivariance in CNNs. ††This work was funded in part
by the IBM-Illinois Center for Cognitive Computing Systems Research (C3SR), a
research collaboration as part of the IBM AI Horizons Network and the National
Science Foundation Grant CCF-1717530.

The idea of equivariance using convolutions and parameter sharing has been
generalized to general group symmetries [2, 3, 4]. These group-equivariant
networks use efficient parameter sharing techniques to encode symmetries in
data beyond translation, such as rotations and flips, as priors. Much further
research has focused on inducing equivariances for different group symmetries
and data types such as [5] for spherical symmetries, [6, 7] for scale-
equivariance, [8, 9, 10] for Lie groups, and [11, 12, 13] for group-
equivariance within attention mechanisms.

But all these works assume knowledge of symmetries in the data is known _a
priori_. Very recently, [14] proposed to learn appropriate parameter sharing
from the data itself using meta-learning techniques; [15] proposed using
$L$-conv layers to automatically search and approximate group convolutions.

Figure 1: A $3\times 3$ network with input N and output M is equivariant to a
larger group $S_{3}$ if and only if it is equivariant to the smaller groups
$\mathbb{Z}_{3}$ and $\mathbb{Z}_{2}$ since
$S_{3}=\mathbb{Z}_{3}\rtimes\mathbb{Z}_{2}$.

Here, we propose _autoequivariant networks_ (AEN) that automatically induce
group equivariance from a reduced search space using deep Q-learning, building
on new group theory results that we prove. Compared to [14], we are able to
restrict to a much smaller search space of relevant symmetries by proving an
equivalence relation between parameter sharing schemes using large groups and
its subgroups that it can be constructed from, as illustrated in Fig. 1
(technical details deferred to Sec. 3). Further, this property proved in Sec.
3 leads to faster construction of equivariant neural networks, as discussed in
Sec. 4. Unlike [15], we focus on exact symmetries formed by combining several
smaller symmetries. The overall performance of a network is a function of not
only the symmetry in its parameters but also on the number of parameters and
features in them. Hence, when the group symmetries are large, then equivariant
networks constructed using parameter sharing with fixed number of parameters
might have too many features or if we fix the number of features, the number
of parameters might be too few. This issue with group equivariant networks was
identified by [16] and reiterated by [2, 17], which limits their application
and makes it difficult to choose the right balance between equivariance,
number of parameters, and number of features needed to design high-performing
equivariant neural networks with reasonable number of parameters and features.
We mitigate this issue by letting our search algorithm find the right balance
automatically.

Our contributions are summarized as follows. Sec. 3 proves that a neural
network is equivariant with respect to a set of group symmetries if and only
if it is equivariant to any group symmetry constructed using semidirect
products from them. Using this result, Sec. 4.1 provides an efficient
algorithm to induce equivariance for large symmetry groups in multilayered
perceptrons (MLPs). Sec. 4.2 describes our deep Q-learning algorithm for
equivariant network architecture search with reduced search space. Sec. 5
develops and releases new group-augmented datasets, G-MNIST and G-Fashion-
MNIST, which augment the standard MNIST and Fashion-MNIST datasets using
several large symmetry groups. These are used to evaluate AENs and also
provide a standard benchmark for further research. Sec. 5 also uses deep
Q-learning for searching group equivariant CNNs (GCNNs) of different sizes,
group equivariances, and trained using different augmentations on several real
datasets like CIFAR10, SVHN, RotMNIST, ASL, EMNIST, and KMNIST. We find that
the top-performing GCNNs have several group equivariances in them.

###  1.1 Related work

#### GCNNs and parameter sharing

GCNNs were introduced by [2] and have been extended to various groups for
image processing [3, 5, 18, 19, 20, 21, 22], where the general idea is to
modify the filters as per the groups used and then perform planar convolution.
An alternative is to construct equivariant MLPs using parameter sharing
directly, which divides parameters into relevant orbits to induce equivariance
in them [4]. Both methods add significant computational load if the size of
the group is large.Our work provides a method of breaking groups down while
preserving equivariance for a wide class of groups and hence making it easier
to construct networks equivariant to large symmetries. GCNNs have also been
extended to relevant groups in particle physics [23], reinforcement learning
[24], graphs [25, 26, 27, 28, 29], and natural language processing [17].

#### Generative and attention models

Group equivariance have also been used in generative models like normalizing
flows [30, 31, 32], variational autoencoders [33, 34], and GANs [35]. These
works replace planar convolutions with group convolutions to achieve better
representation capabilities. Work dealing with group convolutions are mainly
motivated from the result by [36] that shows linear equivariant maps over
scalar fields are necessarily convolutional in nature. However, recent work
has extended group equivariance to nonlinear equivariant maps such as the
popular attention mechanism [37] for data in the form of point clouds, graphs,
images, and language [38, 13, 11]. Our main result is very general and works
for classification and generation models with linear and nonlinear maps. For
brevity, this paper only shows experimental and algorithmic results for
classification tasks with linear maps, but our results extend to the other
forms of equivariant maps as well.

#### Other forms of equivariant networks

So far we have discussed equivariance in neural networks via various forms of
parameter sharing. Let us also point out other popular methods of obtaining
equivariance in the literature. Spatial [39] and polar transformer networks
[40] introduce differentiable modules that are used on top of existing
classifiers that transform the input itself to obtain invariance. Capsule
networks use dynamic routing instead of pooling to make convolutional networks
equivariant [41, 42], whereas novel pooling schemes introduce shift-invariance
[43, 44].

#### Group neural architecture search (NAS)

NAS using reinforcement learning yields networks that outperform hand-
constructed CNNs [45, 46, 47]. Several recent works have proposed automatic
architecture construction for group equivariant networks by using meta-
learning for reparameterization [14] or learning generators of groups [15]. A
key distinction in our work is in first proving an equivalence relation
amongst groups to significantly reduce the search space and then using deep
Q-learning to learn relevant symmetries in the data. Further, inducing
symmetry in a network varies its number of parameters, which may yield too
many / too few parameters, thereby reducing performance. Our Q-learning
algorithm instead chooses the appropriate network size within a desired range
to maximize performance.

#### Efficient group equivariant MLP construction

Recent work [24] constructs equivariant MLPs by formulating it as an
optimization problem with equivariance as its constraints. But the complexity
of this algorithm has a dependency on the size of the group. Contemporaneous
work in [48] uses a similar optimization framework with novel constraints on
generators of groups rather than the group itself to derive efficient
construction algorithms that do not depend on the size of the group and
outperforms the algorithm in [24]. But [48] does not use the structure of
groups like direct or semidirect products and leaves it for further
investigation to speed up their algorithm. Our work on the other hand only
uses the product structure of groups to speed up the parameter sharing
algorithm by [4], instead of an optimization framework. We leave investigation
into efficient design of equivariant networks using both generators of groups
and group structures to future work. Further, because of the modular structure
of our search algorithm in AEN, any such algorithm can be used as a drop-in
replacement of our algorithm. Moreover, [48] formulates their problem inducing
equivariance in linear networks, whereas our main theorem on group
decomposition does not assume linearity.

##  2 Preliminaries

Here we provide definitions related to group equivariance and various products
of groups. For more background on groups and group actions please refer to
Sec. A in the supplementary material. First define equivariant functions.

######  Definition 1 (Equivariance).

A function $\phi:\mathcal{X}\mapsto\mathcal{Y}$ is called _$G$ -equivariant_
(or, _equivariant_ to a group $G$) if
$\phi(\Gamma_{g}x)=\Gamma^{\prime}_{g}\phi(x)$ for all $g\in G$ and
$x\in\mathcal{X}$, where $\Gamma_{g}$ and $\Gamma^{\prime}_{g}$ are actions of
$G$ on $\mathcal{X}$ and $\mathcal{Y}$ respectively.

Now define forms of group products: direct products, semidirect products, and
central extensions.

######  Definition 2 (Direct product).

For two groups $G_{1},G_{2}$, the _direct product_ group $G_{1}\times G_{2}$
is defined as the group with underlying set the Cartesian product $G_{1}\times
G_{2}$ with (i) multiplication:
$(g_{1},g_{2})(g_{1}^{\prime},g_{2}^{\prime})=(g_{1}g_{1}^{\prime},g_{2}g_{2}^{\prime})$,
for $g_{1},g_{1}^{\prime}\in G_{1}$ and $g_{2},g_{2}^{\prime}\in G_{2}$, (ii)
identity: $(e_{G_{1}},e_{G_{2}})\in G_{1}\times G_{2}$ is the identity
element, (iii) inverse: $(g_{1},g_{2})^{-1}=(g_{1}^{-1},g_{2}^{-1})$ is the
inverse of $(g_{1},g_{2})$.

######  Definition 3 (Semidirect product).

Let $G_{1}$ and $G_{2}$ be groups, and $\alpha:G_{2}\rightarrow$Aut$(G_{1})$
be a homomorphism of $G_{2}$ into automorphism group of $G_{1}$. The
_semidirect product_ group $G_{1}\rtimes_{\alpha}G_{2}$ is the set
$G_{1}\times G_{2}$ under the multiplication
$(g_{1},g_{2})(g_{1}^{\prime},g_{2}^{\prime})=(g_{1}\alpha_{g_{2}}(g_{1}^{\prime}),g_{2}g_{2}^{\prime})$
and identity $(e_{G_{1}},e_{G_{2}})$.

######  Definition 4 (Central extension).

Let $G_{1}$ be an abelian group and $G_{2}$ be an arbitrary group. A map
$\psi:G_{2}\times G_{2}\rightarrow G_{1}$ satisfying
$\psi(e_{G_{2}},e_{G_{2}})=e_{G_{1}},$
$\psi(g,g^{\prime}g^{\prime\prime})\psi(g^{\prime},g^{\prime\prime})=\psi(g,g^{\prime})\psi(gg^{\prime},g^{\prime\prime})$
is called a $2$-cocycle. The _central extension_ of $G_{2}$ by $G_{1}$ (using
the $2$-cocycle $\psi$), is defined as the set $G_{1}\times G_{2}$ with the
group operation
$(g_{1},g_{2})*(g^{\prime}_{1},g^{\prime}_{2})=(g_{1}g^{\prime}_{1}\psi(g_{2},g^{\prime}_{2}),g_{2}g^{\prime}_{2}),$
where $g_{1},g^{\prime}_{1}\in G_{1}$, $g_{2},g^{\prime}_{2}\in G_{2}$. The
identity element is $(e_{G_{1}},e_{G_{2}})$.

##  3 Group Decomposition

Here we prove our main theoretical results, first discussing them at a high
level. We show that a function $\phi$ is equivariant to a group $G$ that can
be written as semidirect products of several smaller groups if and only if
$\phi$ is equivariant to each of the smaller groups. This implies that for
constructing a $G$-equivariant function $\phi$, where $G$ is a possibly large
group that can be constructed from several smaller groups using semidirect
products, it is sufficient to make the function equivariant to the smaller
groups. Further, since all the semidirect product groups
$G_{1}\rtimes_{\alpha}G_{2}$ for any valid homomorphism $\alpha$ have the same
components $G_{1},G_{2}$, we show that a function $\phi$ is equivariant to
$G_{1}\rtimes_{\alpha}G_{2}$ if and only if it is equivariant to
$G_{1}\rtimes_{\alpha_{0}}G_{2}$ for any fixed homomorphism $\alpha_{0}$.
Hence, this result gives an equivalence class of groups consisting of exactly
the same decomposition in terms of semidirect products. Now we formally state
and prove this idea.

######  Theorem 1.

Let $\mu^{G_{i}}$, $\bar{\mu}^{G_{i}}$ be group actions of $G_{i}$ on
$\mathcal{X}$ and $\mathcal{Y}$ respectively for $i\in\\{1,2\\}$. Let
$\Gamma$, $\bar{\Gamma}$ be actions of $G_{1}\rtimes_{\alpha}G_{2}$ on
$\mathcal{X}$ and $\mathcal{Y}$ respectively for some homomorphism
$\alpha:G_{2}\mapsto\text{Aut}(G_{1})$ such that

$\displaystyle\Gamma_{(g_{1},e)}(x)$
$\displaystyle=\mu_{g_{1}}^{G_{1}}(x)\hskip 5.69054pt\forall g_{1}\in
G_{1},x\in\mathcal{X}$ (1) $\displaystyle\bar{\Gamma}_{(g_{1},e)}(y)$
$\displaystyle=\bar{\mu}_{g_{1}}^{G_{1}}(y)\hskip 5.69054pt\forall g_{1}\in
G_{1},y\in\mathcal{Y},$ (2) $\displaystyle\Gamma_{(e,g_{2})}(x)$
$\displaystyle=\mu_{g_{2}}^{G_{2}}(x)\hskip 5.69054pt\forall g_{2}\in
G_{2},x\in\mathcal{X}$ (3) $\displaystyle\bar{\Gamma}_{(e,g_{2})}(y)$
$\displaystyle=\bar{\mu}_{g_{2}}^{G_{2}}(y)\hskip 5.69054pt\forall g_{2}\in
G_{2},y\in\mathcal{Y},$ (4)

Then, any function $\phi:\mathcal{X}\mapsto\mathcal{Y}$ is equivariant to
$G_{1}\rtimes_{\alpha}G_{2}$ under group actions $(\Gamma,\bar{\Gamma})$ if
and only if $\phi$ is equivariant to $G_{i}$ under group actions
$(\mu^{G_{i}},\bar{\mu}^{G_{i}})$ for both $i\in\\{1,2\\}$.

In the next sections we describe algorithms using this decomposition. Before
that, we show that although the idea of decomposing groups that can be written
as semidirect products is quite general and useful for most practical
applications, this form of decomposition might fail in other forms of products
of groups and needs to be used with caution. To this end, consider the example
of central extensions from Def. 4. We show that it is not trivial to extend
the results beyond semidirect products. Recall that in the proof for the
semidirect product result in Thm. 1 we used the following equations
$\phi(\Gamma_{(g_{1},g_{2})}(x))=\phi(\Gamma_{(g_{1},e)}\Gamma_{(e,g_{2})}(x))=\bar{\Gamma}_{(g_{1},e)}\phi(\Gamma_{(e,g_{2})}(x)).$
But for central extensions we
have$(g_{1},e)(e,g_{2})=(g_{1}e\psi(e,g_{2}),eg_{2})=(g_{1}\psi(e,g_{2}),g_{2}),$
which is not necessarily the same as $(g_{1},g_{2})$. Hence, here we restrict
our discussions to semidirect products, which in itself covers a wide range of
groups and is useful for practical purposes. Now we look at a consequence of
Thm. 1.

######  Corollary 1.

Let $\mu^{G_{i}}$, $\bar{\mu}^{G_{i}}$ be group actions of $G_{i}$ on
$\mathcal{X}$ and $\mathcal{Y}$ respectively for $i\in\\{1,2\\}$ as in Thm. 1.
Let $\Delta$, $\bar{\Delta}$ be actions of $G_{1}\times G_{2}$ on
$\mathcal{X}$ and $\mathcal{Y}$ respectively such that

$\displaystyle\Delta_{(g_{1},e)}(x)$
$\displaystyle=\mu_{g_{1}}^{G_{1}}(x),\hskip
5.69054pt\bar{\Delta}_{(g_{1},e)}(y)=\bar{\mu}_{g_{1}}^{G_{1}}(y)\hskip
11.38109pt\forall g_{1}\in G_{1},x\in\mathcal{X},y\in\mathcal{Y}$
$\displaystyle\Delta_{(e,g_{2})}(x)$
$\displaystyle=\mu_{g_{2}}^{G_{2}}(x),\hskip
5.69054pt\bar{\Delta}_{(e,g_{2})}(y)=\bar{\mu}_{g_{2}}^{G_{2}}(y)\hskip
11.38109pt\forall g_{2}\in G_{2},x\in\mathcal{X},y\in\mathcal{Y}$

Then, any function $\phi:\mathcal{X}\mapsto\mathcal{Y}$ is equivariant to
$G_{1}\times G_{2}$ under group actions $(\Delta,\bar{\Delta})$ if and only if
$\phi$ is equivariant to $G_{i}$ under group actions
$(\mu^{G_{i}},\bar{\mu}^{G_{i}})$ for both $i\in\\{1,2\\}$.

The proof to Cor. 1 follows directly from Thm. 1 since direct product is a
special case of semidirect product. By symmetry of direct product in Cor. 1,
it implies that the order in which equivariance is induced in a network for a
set of smaller groups does not matter. Also note that our decomposition result
is purely in the context of neural networks, unlike works in abstract algebra
like Jordan-Hölder [49] and Iwasawa [50] decompositions that have different
algebraic significance.

##  4 Inducing Equivariance in MLPs

We first review a method used by [4] to induce discrete group equivariances in
fully connected layers of MLPs. Then, drawing from Thm. 1, we show how to
extend this method to induce equivariance of a large group by iteratively
inducing equivariances corresponding to smaller symmetries that the larger
group is constructed from, using semidirect product.

Represent a fully connected bipartite layer of a MLP by a triple
$\Omega=(\mathbf{N},\mathbf{M},\Delta)$, where $\mathbf{N}$ and $\mathbf{M}$
are two sets of nodes corresponding to the input and output layers
respectively, and $\Delta:\mathbf{N}\times\mathbf{M}\mapsto\mathbf{C}$ is the
edge function that assigns color from the set $\mathbf{C}$ to each of the
edges. Edges with the same color share the same trainable parameter. Let the
group action of group $G$ on $\mathbf{N}$ and $\mathbf{M}$ be represented by
$\Gamma_{\mathbf{N}}$ and $\Gamma_{\mathbf{M}}$ respectively. And let
$\Gamma_{\mathbf{N},\mathbf{M}}$ represent the pairing of actions
$\Gamma_{\mathbf{N}}$ and $\Gamma_{\mathbf{M}}$, i.e.,
$\Gamma_{\mathbf{N},\mathbf{M}}$ acts on $(n,m)\in\mathbf{N}\times\mathbf{M}$
to output $(\Gamma_{\mathbf{N}}(n),\Gamma_{\mathbf{M}}(m))$. Hence,
$\Gamma_{\mathbf{N},\mathbf{M}}$ can be seen as permuting the edges in
$\Omega$ instead of the vertices. The action of
$\Gamma_{\mathbf{N},\mathbf{M}}$ on the set of edges partitions them into
orbits $\\{\Gamma_{\mathbf{N},\mathbf{M}}(n_{p},m_{q})\\}_{n_{p},m_{q}}$,
where $(n_{p},m_{q})$ is a representative edge of an orbit. Thus, this fully
connected layer only has as many independent parameters as the number of
orbits that $\Gamma_{\mathbf{N},\mathbf{M}}$ divides
$\mathbf{N}\times\mathbf{M}$ into. Consider the following construction of a
fully connected layer using parameter sharing

$\displaystyle\Omega=(\mathbf{N},\mathbf{M},\\{\Delta(\Gamma_{\mathbf{N},\mathbf{M}}(n_{p},m_{q}))\\}),$
(5)

where $\\{\Delta(\Gamma_{\mathbf{N},\mathbf{M}}(n_{p},m_{q}))\\}$ is the set
of all independent parameters with one independent parameter per orbit. An
algorithmic version of this construction is provided in Alg. 2 in the for
further discussion later. Now we define the notion of $G$-equivariance in a
fully connected layer $\Omega$.

######  Definition 5.

Let $\Omega=(\mathbf{N},\mathbf{M},\Delta)$ be a fully connected layer of a
MLP taking input $x\in\mathcal{X}$ and producing output
$\Omega(x)=y\in\mathcal{Y}$. Then $\Omega$ is defined to be $G$-equivariant
under group actions $\Gamma$ and $\bar{\Gamma}$ of $G$ on $\mathcal{X}$ and
$\mathcal{Y}$ respectively if
$\Omega(\Gamma_{g}(x))=\bar{\Gamma}_{g}(\Omega(x))$ for all $g\in G$.

Recall a theorem by [4] that states that the construction of $\Omega$ given by
(5) is $G$-equivariant.

######  Theorem 2 ([4]).

The neural network construction $\Omega$ given by (5) is equivariant to $G$.

Now consider the construction of $\Omega$ in (5) when the group $G$ is of the
form $G=G_{1}\rtimes_{\alpha}G_{2}$. We claim that in this case, a
$G$-equivariant fully connected layer $\Omega$ can be obtained by having
$\Omega$ respect the parameter sharing laws in (5) for $G_{1}$ and $G_{2}$
both. This claim follows directly from Thm. 1. This result can further be
extended to any group $G$ constructed by using semidirect product on groups
from a set $\mathcal{G}=\\{G_{1},G_{2},\ldots,G_{m}\\}$. We leverage this
result to get an efficient algorithm for construction of equivariant networks
for large groups in Sec. 4.1. We will further use the symmetry of arguments
$G_{1},G_{2}$ in Cor. 1 for searching large symmetries in Sec. 4.2. In
particular, we will use the fact that the order in which the group
equivariances for groups from the set $\mathcal{G}$ are induced does not
matter, which reduces the search space for our algorithm.

#### Example

Before looking at various construction and search algorithms, consider some
examples demonstrating an implication of Thm. 1. Consider an example with
$\mathbf{N}=\mathbf{M}=\\{1,2,3\\}$, i.e. a $3\times 3$ fully connected layer
$\Omega$. First we construct a symmetric group $S_{3}$-equivariant network by
using the design in (5). In Fig. 1, for $S_{3}$-equivariance, there are only
two independent parameters illustrated using red and blue colors. Now,
consider an alternate construction of the same network by first inducing
$\mathbb{Z}_{3}$ cyclic equivariance followed by parameter sharing rules for
$\mathbb{Z}_{2}$ flip equivariance as shown in Fig. 1. Note that by combining
the parameter sharing restrictions for both $\mathbb{Z}_{3}$-equivariance and
$\mathbb{Z}_{2}$-equivariance, we obtain the parameter sharing obtained for
$S_{3}$-equivariance. This can be explained from the fact
$S_{3}=\mathbb{Z}_{3}\rtimes_{\alpha}\mathbb{Z}_{2}$ for some $\alpha$ and a
consequence of Thm. 1. Hence, breaking symmetries down helps reduce the search
space of groups by introducing equivalence relations between them

###  4.1 Fast Equivariant Network Construction

Here we give a construction algorithm, Alg. 1, for inducing equivariance in
fully connected layers. For a group $G$ constructed by iteratively using
semidirect product of $m$ smaller groups in any order from an array
$G_{array}=[G_{1},G_{2},\ldots,G_{m}]$, inducing $G$-equivariance through the
parameter sharing method in (5) has $\mathcal{O}(|G|\times N)$ computational
complexity, where, clearly $|G|=|G_{1}|\times\dots\times|G_{m}|$. We use Thm.
1 to reduce this complexity to
$\mathcal{O}\left((|G_{1}|+\cdots+|G_{m}|)\times N\right)$. Note that
trivially using (5) for each $G_{i}\in G_{array}$ to induce equivariance might
not give a computational advantage. For example, for
$G_{array}=[G_{1},G_{2}]$, individually inducing equivariance would give us
two sets of orbits of size $\mathcal{O}(N/|G_{i}|)$. But, then merging these
two sets of orbits with arbitrary partitioning of indices in each orbit would
take $\mathcal{O}(N^{2}/(|G_{1}|\times|G_{2}|))$ computations, which for most
experimental cases considered in this paper is impractical. Now we describe
Alg. 1 that produces a $G$-equivariant network with
$\mathcal{O}\left((|G_{1}|+\cdots+|G_{m}|)\times N\right)$ computational
complexity. The main idea behind Alg. 1 is to take inspiration from Thm. 1 and
produce the orbits that resemble a $G$-equivariant network, but visiting each
element of $G_{i}$ for $i\in\\{1,\ldots,m\\}$ exactly once per number of
parameters.

#### Notation for Algs. 1 and 2

The total number of parameters in the network is $N$. Define an array
$\mathbf{V}$ of length $N$ which is initialized to all $-1$s. When the $i$th
parameter is visited, $\mathbf{V}[i]$ is set to $1$. The sharing amongst
parameters is indicated by an array, $\mathbf{I}$, of length $N$, which is
initialized to $\mathbf{I}[i]=i$, and $\mathbf{I}[i]=j$ indicates the $i$th
parameter belongs to the $j$th orbit. An integer $C$ initialized to $-1$ is
the current orbit number. The array of small groups that construct $G$ is
stored in an array $G_{array}$ of size $g_{size}$. Define another array
$\mathbf{L}$ with $\mathbf{L}[i]=i$ and an empty queue, $Q$, to enumerate
parameters.

for $i\in\mathbf{L}$ do

if $\mathbf{V}[i]<0$ then

$\mathbf{V}[i]=1$

$Q.append(i)$

$C=C+1$

while $len(Q)>0$ do

$index=Q.pop()$

$I[index]=C$

for $G\in G_{array}$ do

for $g\in G$ do

$index_{g}=\Gamma_{g}(index)$

if $V[index_{g}]<0$ then

$V[index_{g}]=1$

$Q.append(index_{g})$

$I[index_{g}]=C$ return $\mathbf{I},C$

Algorithm 1 Fast Equivariant MLP Construction

In Alg. 2 in Sec. C in the supplementary material, we give an algorithmic
version of the construction of a G-equivariant MLP in (5) using the same
notations as in Alg. 1 to illustrate the difference between the two algorithms
in Fig. 2. Take the group $G$ to be of the form $G=G_{1}\rtimes G_{2}$, then
the main difference between the two algorithms is that in Alg. 2 for each
index $i\in L$, we iterate through all elements of $G$ to construct the
orbits, whereas in Alg. 1 for each index $i\in L$, we only go through the
elements of $G_{1}$ and $G_{2}$. Fig. 2 illustrates this difference

Now we prove correctness and computational complexity of Alg. 1. Claim 1 shows
that for a weight matrix $\mathbf{W}$ with $N$ parameters, the matrix
$\mathbf{W}[\mathbf{I}]$ is $G$-equivariant, where $\mathbf{W}[\mathbf{I}]$ is
a matrix satisfying the parameter sharing introduced by $I$ and has $C$ total
trainable parameters, the total number of orbits returned by Alg. 1. The proof
to which is provided in Sec. G in the supplementary material. Claim 2 shows
that Alg. 1 has computational complexity
$\mathcal{O}\left((|G_{1}|+\cdots+|G_{m}|)\times N\right)$.

Figure 2: Steps in inducing equivariance of
$\mathbb{Z}_{3}\times\mathbb{Z}_{2}$ in a $3\times 3$ MLP using Alg. 1 as
compared to a basic approach in Alg. 2. Here (a) represents the orbits of a
singles-layered $3\times 3$ MLP as the starting point for both the algorithms.
Alg. 1 takes the steps (d), (e), and (f) in that order, whereas Alg. 2 takes
step (b) followed by (c) to obtain the same equivariant MLP. Both methods give
the same equivariant network as proved in Claim. 1, but Alg. 1 is
significantly faster than Alg. 2 as proved in Claim. 2

######  Claim 1.

The weight matrix with parameter sharing given by $\mathbf{W}[\mathbf{I}]$ is
$G$-equivariant. Here, $\mathbf{W}[\mathbf{I}]$ is a weight matrix with $N$
parameters sharing $C$ trainable parameters using $\mathbf{I}$ returned by
Alg. 1.

######  Claim 2.

The computational complexity of Alg. 1 is
$\mathcal{O}\left((|G_{1}|+\cdots+|G_{m}|)\times N\right)$.

###### Proof.

Each index $i$ gets appended to $Q$ exactly once and when $i$ is popped out,
using group transformations $\Gamma_{g}$s it checks at most
$|G_{1}|+\cdots+|G_{m}|$ more indices to add to Q. ∎

###  4.2 Fast Equivariance Search

We use deep Q-learning [51] with $\epsilon$-greedy strategy [52] and
experience replay [53, 54] as our search algorithm. In the $\epsilon$-greedy
strategy, the agent starts searching for networks with a large value of
$\epsilon$ close to 1 when it _explores_ various networks and slowly decreases
$\epsilon$ to _exploit_ better performing networks as the search progresses.
Experience replay helps store large numbers of transitions in the state-action
space and reuse them in a decorrelated way, which empirically performs well
[54]. We represent a network topology by a state vector describing equivariant
properties of the network, which acts as the state of the Q-learning agent. At
each step of learning, the agent moves from current state to another by
changing group equivariances present in the network. Various components of our
$Q$-learning agent including search space, action space, evaluation strategy,
reward function, and training strategy follow [45] and are detailed in Sec. H
of the supplementary materials.

##  5 Experiments

We conduct two sets of experiments in Sec. 5.1 and 5.2 for group equivariant
MLPs and CNNs respectively. The dataset construction for Sec. 5.1 is described
in Sec. B in the supplementary material using various group transformations on
MNIST and Fashion-MNIST datasets. We report the performance of group
equivariant MLPs with fixed number of features and varying number of
parameters, where we use one or more groups from the same set of group
transformations for inducing equivariance as used for dataset construction.
Group equivariances are induced in these networks using deep Q-learning
without knowledge of transformations present in the datasets, but only the
possible set of groups that can be used to construct it. For a set of
symmetries, a large number of groups can be constructed from their semidirect
products by changing the automorphism and components involved in the product.
These experiments show that in general, using the same group for inducing
equivariance actually in the dataset tends to perform well. But, cases where
number of group symmetries are too many, our search algorithm does not choose
MLPs with all the relevant symmetries, rather finds a balance between symmetry
and parameters. In Sec. 5.2, our deep Q-learning algorithm chooses appropriate
equivariances, augmentations, and channel sizes in GCNNs to maximize their
performance on various image datasets. Code is available at
https://github.com/basusourya/autoequivariant_networks.

###  5.1 Group Equivariant MLPs

We first perform single equivariance tests where we use the G-MNIST and
G-Fashion-MNIST datasets with single group transformations from Tab. 4,
followed by deep Q-learning, where we consider the datasets with combination
of group transformations from Tab. 5.

#### Single Equivariance Testing

Here we perform single equivariance tests on G-MNIST and G-Fashion-MNIST
datasets as shown in Fig. 4 and Fig. 5 in Sec. B in the supplementary material
respectively. The training details are given in Sec. D.1 in the supplementary
material. From the accuracies in Tab. 7 and Tab. 8 we find the following key
insights. We find that test accuracies are a function of equivariances and
number of parameters in them. Appropriate equivariances in MLPs perform well,
but, when the number of parameters are too few for single equivariance, as in
the case of Eq4 and Eq5 in Tab. 1, the networks perform poorly across all the
datasets. We conclude that equivariance helps in general, but a balance
between number of parameters and symmetry induced is important. Hence, in the
next subsection, we use deep Q-learning to automatically find the appropriate
equivariances with balanced number of parameters to induce in an MLP.

Table 1: Trainable parameters in MLPs of dimension $784\times 400\times 400\times 10$ with various equivariances. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Params ($\times 10^{6}$) |  0.47 |  0.12 |  0.24 |  0.24 |  0.04 |  0.04 |  0.24 |  0.30 |  0.30 |  0.30 |  0.30 |  0.12 |  0.24

#### Deep Q-learning

Tab. 2 gives the results for group neural architecture search using deep
Q-learning for G-MNIST and G-Fashion-MNIST for augmentations Aug3 and Aug5.
More detailed results are presented in Tab. 9 and Tab. 10, and training
details are provided in Sec. D.1 in supplementary material. Each network in
the columns are trained for datasets of size 10K for 10 epochs. Now we
describe the method to obtain the AEN results. We train our DQN with the
hyperparameters described in Sec. H. Our DQN takes in the current child
network state and outputs an action, using which we get the next state of the
child network. The reward is a function of the performance of the child
network as described in Sec. H. To make our search efficient, following [45],
we store the rewards from each state and reuse them when a state is revisited.
Fig. 3 illustrate the average test accuracies obtained by the child model per
value of $\epsilon$ for Aug3 and Aug5 augmented G-MNIST and G-Fashion-MNIST
datasets. The complete set of plots are illustrated in Fig. 8 and Fig. 9 for
the two datasets. Each DQN was trained for 12 hours on an Nvidia V100 GPU
available on HAL cluster [55]. Once the DQNs are trained, we use the top
states obtained and retrain them using identical training hyperparameters as
the MLPs in the other columns to obtain the results in Tab. 2, Tab. 9 and Tab.
10 under the column AEN. Further training details and top states obtained are
given in Sec. D.1 of the supplementary material. In Tab. 9 and Tab. 10, we
find that test accuracies obtained from DQN outperform any other network
states in the tables from single equivariances in most of the cases.

Table 2: Test accuracies for equivariant MLPs for G-MNIST and G-Fashion-MNIST with augmentations Aug$i$ corresponding to the array of transformations from Tab. 5 and the columns indicate equivariant MLPs with Eq$i$ having equivariance to transformation IAug$i$ from Tab. 4. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12 |  AEN
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
MNIST |  |  |  |  |  |  |  |  |  |  |  |  |  |
Aug3 |  73.7 |  73.9 |  73.9 |  72.1 |  46.3 |  41.4 |  72.7 |  69.4 |  70.1 |  75.3 |  68.1 |  71.8 |  73.2 |  77.4
Aug5 |  51.0 |  57.6 |  54.4 |  55.8 |  38.6 |  37.8 |  54.8 |  54.3 |  53.9 |  54.8 |  55.2 |  62.2 |  56.2 |  69.4
Fashion |  -MNIST |  |  |  |  |  |  |  |  |  |  |  |  |
Aug3 |  58.0 |  59.8 |  58.2 |  57.8 |  43.5 |  41.2 |  58.0 |  59.8 |  58.8 |  60.0 |  57.7 |  59.7 |  57.1 |  63.4
Aug5 |  50.8 |  54.6 |  53.1 |  52.5 |  36.6 |  34.6 |  53.8 |  54.1 |  53.3 |  53.5 |  52.6 |  57.8 |  52.3 |  60.4

###  5.2 Group Equivariant Convolutional Neural Networks

We use deep Q-learning on GCNNs with varying group equivariances,
augmentations, and size. We replace the child network in Sec. 5.1 with a GCNN
with symmetries from rotation (P4), horizontal flips (H2), and vertical flips
(V2). We also allow two network sizes: small and large with the large network
having 1.5 times the number of channels as the small network. This is to
understand the impact of number of parameters versus other factors like
equivariance and augmentations. We adjust the number of channels in GCNNs so
for any combination of groups from {P4, H2, V2} the number of parameters are
nearly equal for the small network. The DQN also chooses augmentations from
Tab. 6 for training the child network. Thus, we directly compare the effect of
augmentations and equivariances in the overall performance. We train a fixed
number of models per value of $\epsilon$ as shown in Tab. 14. Fig. 3 shows the
test accuracies obtained during the deep Q-learning process averaged over
$\epsilon$ values for CIFAR10 [56] and EMNIST [57]. A complete set of plots
for more datasets SVHN [58], RotMNIST [59], ASL [60], KMNIST [61] is given in
Sec. F of the supplementary material.

(a) Aug3 MNIST

(b) Aug3 Fashion-MNIST

(c) Aug5 MNIST

(d) Aug5 Fashion-MNIST

(e) CIFAR10

(f) EMNIST

Figure 3: Deep Q-learning performance for various image datasets. The Q-learning agent chooses from various group equivariances for G-MNIST and G-Fashion-MNIST, and from various equivariances, augmentations, and network sizes for CIFAR10 and EMNIST. Table 3: Top states from deep Q-learning for equivariances, augmentations, and sizes used in training a GCNN on several image datasets and comparison with translation (Zn) equivariant CNNs. Dataset |  Equivariances |  Augmentations |  Size |  Test |  Base (Zn)
---|---|---|---|---|---
|  |  |  |  accuracies |  accuracies
CIFAR10 |  (P4, H2, V2, Zn) |  (HFlip (0.5), Scale (0.1)) |  Large |  $65.25\%$ |  $55.17\%$
SVHN |  (P4, H2, V2, Zn) |  — |  Large |  $89.70\%$ |  $85.72\%$
RotMNIST |  (P4, H2, V2, Zn) |  (Scale (0.1)) |  Small |  $94.57\%$ |  $92.60\%$
ASL |  (P4, H2, V2, Zn) |  (Scale (0.1)) |  Small |  $94.21\%$ |  $89.33\%$
EMNIST |  (P4, V2, Zn) |  (Shear (10)) |  Large |  $93.99\%$ |  $92.93\%$
KMNIST |  (P4, H2, V2, Zn) |  (Shear (10)) |  Large |  $93.59\%$ |  $90.94\%$

We obtain the top 4 states of the child network with highest rewards from the
DQN and retrain them on entire datasets for 10 epochs and report the top
states and their performances in Tab. 13 in the supplementary material. Tab. 3
summarizes the results for the best pest performing state amongst the top 4
states for each dataset and compares it with a large size traditional CNN.
From Tab. 13 we observe that all top performing models have group
equivariances in them, showing how critical it is for performance in each of
the datasets considered. Also note that augmentations do appear in the top
models, but not as frequently: although augmentations help with invariance,
perhaps they also consume network complexity to learn it. Moreover, we find
there is not much impact on the size of the network for a significant change
in the network size (1.5 times) since the network size seems to be almost
uniformly distributed across the rows in Tab. 13. As a takeaway, we conclude
that equivariance can induce symmetry without using any network complexity and
hence gives superior performance to augmentations.

##  6 Conclusion, limitations, and societal impacts

We prove new group-theoretic results for improving the complexity of
construction and search of group-equivariant neural networks. We find
experimentally that AENs, in general, outperform other networks across all the
datasets we tested on: G-MNIST, G-Fashion-MNIST, CIFAR10, SVHN, RotMNIST, ASL,
EMNIST, and KMNIST. We work with discrete symmetries since we use parameter
sharing, which is developed only for discrete symmetries. In future work, we
wish to generalize our methods and extend our work to continuous symmetries.
We also assume that we know the set of groups from which the group symmetries
are constructed using semi-direct products. In future work, we want to
generalize our work to other forms of group extension methods in group theory.
Our work improves the complexity of construction and search of equivariant
networks. Our work does not have direct negative societal impact we are aware
of, beyond the general AI safety and governance issues identified in the
literature [62] from improved AI models. NAS does aim to optimize neural
networks as usually done by human researchers, but in the current scale of our
experiments we do not think it poses a threat to their employment.

## References

  * [1] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _Nature_ , vol. 521, no. 7553, pp. 436–444, May 2015.
  * [2] T. Cohen and M. Welling, “Group equivariant convolutional networks,” in _Proceedings of the 33rd International Conference on Machine Learning (ICML)_ , Jun. 2016, pp. 2990–2999.
  * [3] T. S. Cohen and M. Welling, “Steerable CNNs,” in _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , Apr. 2017.
  * [4] S. Ravanbakhsh, J. Schneider, and B. Póczos, “Equivariance through parameter-sharing,” in _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , Aug. 2017, pp. 2892–2901.
  * [5] T. S. Cohen, M. Geiger, J. Köhler, and M. Welling, “Spherical CNNs,” in _Proceedings of the 6th International Conference on Learning Representations (ICLR)_ , May 2018.
  * [6] D. Worrall and M. Welling, “Deep scale-spaces: Equivariance over scale,” in _Proceedings of the 32nd Conference on Neural Information Processing Systems_ , Dec. 2019, pp. 7366–7378.
  * [7] I. Sosnovik, M. Szmaja, and A. Smeulders, “Scale-equivariant steerable networks,” in _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , Apr. 2020.
  * [8] E. J. Bekkers, “B-spline CNNs on Lie groups,” in _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , Apr. 2020.
  * [9] M. Finzi, S. Stanton, P. Izmailov, and A. G. Wilson, “Generalizing convolutional neural networks for equivariance to Lie groups on arbitrary continuous data,” in _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , Jul. 2020, pp. 3165–3176.
  * [10] D. W. Romero, E. J. Bekkers, J. M. Tomczak, and M. Hoogendoorn, “Wavelet networks: Scale equivariant learning from raw waveforms,” arXiv:2006.05259 [cs.LG]., Jun. 2020.
  * [11] M. Hutchinson, C. L. Lan, S. Zaidi, E. Dupont, Y. W. Teh, and H. Kim, “LieTransformer: Equivariant self-attention for Lie groups,” arXiv:2012.10885 [cs.LG]., Dec. 2020.
  * [12] D. W. Romero and M. Hoogendoorn, “Co-attentive equivariant neural networks: Focusing equivariance on transformations co-occurring in data,” in _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , Apr. 2020.
  * [13] D. W. Romero, E. J. Bekkers, J. M. Tomczak, and M. Hoogendoorn, “Attentive group equivariant convolutional networks,” in _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , Jul. 2020, pp. 8188–8199.
  * [14] A. Zhou, T. Knowles, and C. Finn, “Meta-learning symmetries by reparameterization,” in _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , May 2021.
  * [15] N. Dehmamy, Y. Liu, R. Walters, and R. Yu, “Lie algebra convolutional neural networks with automatic symmetry extraction,” 2021. [Online]. Available: https://openreview.net/forum?id=cTQnZPLIohy
  * [16] R. Gens and P. M. Domingos, “Deep symmetry networks,” in _Proceedings of the 27th Conference on Neural Information Processing Systems_ , Dec. 2014, pp. 2537–2545.
  * [17] J. Gordon, D. Lopez-Paz, M. Baroni, and D. Bouchacourt, “Permutation equivariant models for compositional generalization in language,” in _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , Apr. 2020.
  * [18] D. E. Worrall, S. J. Garbin, D. Turmukhambetov, and G. J. Brostow, “Harmonic networks: Deep translation and rotation equivariance,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , Jul. 2017, pp. 5028–5037.
  * [19] M. Weiler and G. Cesa, “General $\mbox{E}(2)$-equivariant steerable CNNs,” in _Proceedings of the 32nd Conference on Neural Information Processing Systems_ , Dec. 2019, pp. 14 334–14 345.
  * [20] C. Esteves, C. Allen-Blanchette, A. Makadia, and K. Daniilidis, “Learning ${SO}(3)$ equivariant representations with spherical CNNs,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , Sep. 2018, pp. 52–68.
  * [21] T. Cohen, M. Weiler, B. Kicanaoglu, and M. Welling, “Gauge equivariant convolutional networks and the icosahedral CNN,” in _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , Jun. 2019, pp. 1321–1330.
  * [22] C. Esteves, A. Makadia, and K. Daniilidis, “Spin-weighted spherical CNNs,” in _Proceedings of the Conference on Neural Information Processing Systems (NeurIPS)_ , Dec. 2020, pp. 8614–8625.
  * [23] A. Bogatskiy, B. Anderson, J. Offermann, M. Roussi, D. Miller, and R. Kondor, “Lorentz group equivariant neural network for particle physics,” in _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , Jul. 2020, pp. 992–1002.
  * [24] E. Van der Pol, D. Worrall, H. Van Hoof, F. Oliehoek, and M. Welling, “MDP homomorphic networks: Group symmetries in reinforcement learning,” in _Proceedings of the 33rd Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , Dec. 2020, pp. 4199–4210.
  * [25] P. de Haan, M. Weiler, T. Cohen, and M. Welling, “Gauge equivariant mesh CNNs: Anisotropic convolutions on geometric graphs,” in _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , May 2021\.
  * [26] M. Horie, N. Morita, T. Hishinuma, Y. Ihara, and N. Mitsume, “Isometric transformation invariant and equivariant graph convolutional networks,” in _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , May 2021.
  * [27] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman, “Provably powerful graph networks,” in _Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019)_ , Dec. 2019, pp. 2156–2167.
  * [28] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman, “Invariant and equivariant graph networks,” in _Proceedings of the 7th International Conference on Learning Representations (ICLR)_ , May 2019.
  * [29] N. Keriven and G. Peyré, “Universal invariant and equivariant graph neural networks,” in _Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS)_ , Dec. 2019, pp. 7092–7101.
  * [30] L. Falorsi, P. de Haan, T. R. Davidson, and P. Forré, “Reparameterizing distributions on Lie groups,” in _Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS)_ , Apr. 2019, pp. 3244–3253.
  * [31] J. Köhler, L. Klein, and F. Noé, “Equivariant flows: Exact likelihood generative learning for symmetric densities,” in _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , Jul. 2020, pp. 5361–5370.
  * [32] M. Biloš and S. Günnemann, “Equivariant normalizing flows for point processes and sets,” arXiv:2010.03242 [cs.LG]., Oct. 2020.
  * [33] D. Kuzminykh, D. Polykovskiy, and A. Zhebrak, “Extracting invariant features from images using an equivariant autoencoder,” in _Proceedings of the 10th Asian Conference on Machine Learning_ , Nov. 2018, pp. 438–453.
  * [34] L. Falorsi, P. de Haan, T. R. Davidson, N. De Cao, M. Weiler, P. Forré, and T. S. Cohen, “Explorations in homeomorphic variational auto-encoding,” in _ICML Workshop on Theoretical Foundations and Applications of Deep Generative Models_ , Jul. 2018.
  * [35] N. Dey, A. Chen, and S. Ghafurian, “Group equivariant generative adversarial networks,” in _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , May 2021.
  * [36] R. Kondor and S. Trivedi, “On the generalization of equivariance and convolution in neural networks to the action of compact groups,” in _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , Jul. 2018, pp. 2747–2755.
  * [37] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Proceedings of the 30th Conference on Neural Information Processing Systems_ , Dec. 2017, pp. 5998–6008.
  * [38] F. B. Fuchs, D. E. Worrall, V. Fischer, and M. Welling, “$\mbox{SE}(3)$-transformers: 3D roto-translation equivariant attention networks,” in _Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS)_ , Dec. 2020, pp. 1970–1981.
  * [39] M. Jaderberg, K. Simonyan, A. Zisserman, and K. Kavukcuoglu, “Spatial transformer networks,” in _Proceedings of the 28th Conference on Neural Information Processing Systems_ , Dec. 2015, pp. 2017–2025.
  * [40] C. Esteves, C. Allen-Blanchette, X. Zhou, and K. Daniilidis, “Polar transformer networks,” in _Proceedings of the 6th International Conference on Learning Representations (ICLR)_ , May 2018.
  * [41] S. Sabour, N. Frosst, and G. E. Hinton, “Dynamic routing between capsules,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , Dec. 2017, pp. 3859–3869.
  * [42] J. E. Lenssen, M. Fey, and P. Libuschewski, “Group equivariant capsule networks,” in _Proceedings of the 31st Conference on Neural Information Processing Systems_ , Dec. 2018, pp. 8844–8853.
  * [43] R. Zhang, “Making convolutional networks shift-invariant again,” in _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , Jun. 2019, pp. 7324–7334.
  * [44] A. Chaman and I. Dokmanić, “Truly shift-invariant convolutional neural networks,” arXiv:2011.14214 [cs.CV]., Nov. 2020.
  * [45] B. Baker, O. Gupta, N. Naik, and R. Raskar, “Designing neural network architectures using reinforcement learning,” in _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , Apr. 2017.
  * [46] B. Zoph and Q. Le, “Neural architecture search with reinforcement learning,” in _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , Apr. 2017.
  * [47] H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean, “Efficient neural architecture search via parameters sharing,” in _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , Jul. 2018, pp. 4095–4104.
  * [48] M. Finzi, M. Welling, and A. G. Wilson, “A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups,” _arXiv preprint arXiv:2104.09459_ , 2021.
  * [49] B. Baumslag, “A simple way of proving the Jordan-Hölder-Schreier theorem,” _The American Mathematical Monthly_ , vol. 113, no. 10, pp. 933–935, Dec. 2006.
  * [50] K. Iwasawa, “On some types of topological groups,” _Annals of Mathematics_ , vol. 50, no. 3, pp. 507–558, Jul. 1949.
  * [51] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. MIT Press, 2018.
  * [52] J. Vermorel and M. Mohri, “Multi-armed bandit algorithms and empirical evaluation,” in _Proceedings of the European Conference on Machine Learning_ , Oct. 2005, pp. 437–448.
  * [53] L.-J. Lin, “Reinforcement learning for robots using neural networks,” Ph.D. dissertation, Carnegie Mellon University, Jan. 1993.
  * [54] S. Adam, L. Busoniu, and R. Babuska, “Experience replay for real-time reinforcement learning control,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C_ , vol. 42, no. 2, pp. 201–212, Mar. 2011.
  * [55] V. Kindratenko, D. Mu, Y. Zhan, J. Maloney, S. H. Hashemi, B. Rabe, K. Xu, R. Campbell, J. Peng, and W. Gropp, “HAL: Computer system for scalable deep learning,” in _Practice and Experience in Advanced Research Computing (PEARC ’20)_ , Jul. 2020, pp. 41–48.
  * [56] A. Krizhevsky, “Learning multiple layers of features from tiny images,” _Master’s thesis, University of Toronto_ , 2009.
  * [57] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik, “Emnist: Extending mnist to handwritten letters,” in _2017 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2017, pp. 2921–2926.
  * [58] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” in _NIPS Workshop on Deep Learning and Unsupervised Feature Learning_ , Dec. 2011.
  * [59] H. Larochelle, D. Erhan, A. Courville, J. Bergstra, and Y. Bengio, “An empirical evaluation of deep architectures on problems with many factors of variation,” in _Proceedings of the 24th international conference on Machine learning_ , 2007, pp. 473–480.
  * [60] tecperson, “Sign language mnist: Drop-in replacement for mnist for hand gesture recognition tasks,” 2017. [Online]. Available: https://www.kaggle.com/datamunge/sign-language-mnist
  * [61] T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha, “Deep learning for classical japanese literature,” arXiv:1812.01718 [cs.CV]., Dec. 2018.
  * [62] L. R. Varshney, N. S. Keskar, and R. Socher, “Pretrained AI models: Performativity, mobility, and change,” arXiv:1909.03290 [cs.CY]., Sep. 2019.
  * [63] N. Qian, “On the momentum term in gradient descent learning algorithms,” _Neural networks_ , vol. 12, no. 1, pp. 145–151, 1999.
  * [64] E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V. Le, “AutoAugment: Learning augmentation strategies from data,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , Jun. 2019, pp. 113–123.

## Checklist

##  Appendix A Background on Groups

Here we provide basic definitions on groups and group actions.

######  Definition 6 (Group).

A group $(G,\circ)$ is a set $G$ equipped with a binary operator $\circ$ that
satisfies the following axioms.

  * •

Closure: For any $g_{1},g_{2}\in G$, $g_{1}\circ g_{2}\in G$.

  * •

Associativity: For any $g_{1},g_{2},g_{3}\in G$, $g_{1}\circ(g_{2}\circ
g_{3})=(g_{1}\circ g_{2})\circ g_{3}$.

  * •

Identity: There exists an $e\in G$, such that $g\circ e=e\circ g=g$ for all
$g\in G$.

  * •

Inverse: For any $g\in G$, there is a corresponding $g^{-1}$, such that
$g\circ g^{-1}=g^{-1}\circ g=e$.

When clear from context, we omit the symbol $\circ$ and write $g_{1}\circ
g_{2}$ as $g_{1}g_{2}$. A group is called an abelian group if the group
operation commutes. Next we define a homomorphism between two groups that is
useful to define group actions.

######  Definition 7 (Sym$(\mathcal{X})$).

For any set $\mathcal{X}$, Sym($\mathcal{X}$) is the group of all bijective
maps from $\mathcal{X}$ to itself. The group operation is composition of maps
and the identity element is the identity map on $\mathcal{X}$.

######  Definition 8 (Homomorphism).

A map between groups $\Gamma:G\mapsto H$ is called a _(group) homomorphism_ if
it preserves group multiplication,
$\Gamma(g_{1}g_{2})=\Gamma(g_{1})\Gamma(g_{2})$.

######  Definition 9 (Group action).

An _action_ of a group $G$ on a set $\mathcal{X}$ is defined as a homomorphism
$\Gamma:G\rightarrow$ Sym$(\mathcal{X})$. We will denote the image of $g\in G$
under $\Gamma$ as $\Gamma_{g}$.

A bijective homomorphism from a group to itself is called an automorphism.

##  Appendix B Datasets

We consider a set of 12 group transformations of which 5 are real group
transformations: rotation, horizontal and vertical flips, horizontal and
vertical translations, and the remaining 7 are synthetic group symmetries used
to scramble the data described in Tab. 4. We illustrate samples from G-MNIST
and G-Fashion-MNIST with these 12 symmetries applied individually in Fig. 4
and Fig. 5 respectively. Similarly, we also apply a combination of 5 subsets
of these transformations shown in Tab. 5 to obtain the samples from G-MNIST
and G-Fashion-MNIST shown in Fig. 6 and Fig. 7. The data we are providing does
not contain personally identifiable information or offensive content.

(a) Original

(b) Rotations

(c) Horizontal flips

(d) Vertical flips

(e) Horizontal translations

(f) Vertical translations

(g) Rotation scrambles

(h) Horizontal scrambles

(i) Vertical scrambles

(j) Left vertical scrambles

(k) Right vertical scrambles

(l) Top horizontal scrambles

(m) Bottom horizontal scrambles

Figure 4: Samples of the digits ‘5’,‘7’,‘2’,‘1’ from the G-MNIST dataset with
randomly applied single group transformations.

(a) Original

(b) Rotations

(c) Horizontal flips

(d) Vertical flips

(e) Horizontal translations

(f) Vertical translations

(g) Rotation scrambles

(h) Horizontal scrambles

(i) Vertical scrambles

(j) Left vertical scrambles

(k) Right vertical scrambles

(l) Top horizontal scrambles

(m) Bottom horizontal scrambles

Figure 5: Samples of the items ‘Sneaker’, ‘Sandal’, ‘Pullover’, ‘Ankle boot’ from the G-Fashion-MNIST with randomly applied single group transformations. Table 4: Description of individual transformations. These transformations and their combinations were used to construct the G-MNIST and G-Fashion-MNIST datasets.  |  Augmentation descriptions
---|---
IAug0 |  Original
IAug1 |  Rotations
IAug2 |  Horizontal flips
IAug3 |  Vertical flips
IAug4 |  Horizontal translations
IAug5 |  Vertical translations
IAug6 |  Rotation scrambles
IAug7 |  Horizontal scrambles
IAug8 |  Vertical scrambles
IAug9 |  Left vertical scrambles
IAug10 |  Right vertical scrambles
IAug11 |  Top horizontal scrambles
IAug12 |  Bottom horizontal scrambles
Table 5: Augmentation arrays showing the groups contained in each augmentation array. Here, 1 in $i$th row and $j$th column indicates the presence of the $j$th group in the array Aug$i$. |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12
---|---|---|---|---|---|---|---|---|---|---|---|---
Aug0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0
Aug1 |  0 |  1 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  1
Aug2 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  1 |  0 |  0
Aug3 |  1 |  0 |  0 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  1 |  0
Aug4 |  1 |  1 |  1 |  1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0
Aug5 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1

(a) Original

(b) Aug1

(c) Aug2

(d) Aug3

(e) Aug4

(f) Aug5

Figure 6: Samples of the digits ‘5’,‘7’,‘2’,‘1’ from the G-MNIST dataset with
a combination of group transformations from Tab. 5 randomly applied.

(a) Original

(b) Aug1

(c) Aug2

(d) Aug3

(e) Aug4

(f) Aug5

Figure 7: Samples of the items ‘Sneaker’, ‘Sandal’, ‘Pullover’, ‘Ankle boot’
from the G-Fashion-MNIST dataset with a combination of group transformations
from Tab. 5 randomly applied.

Tab. 4 provides descriptions for the individual transformations used for
constructing the datasets G-MNIST and G-Fashion-MNIST. In Tab. 4, the
transformations IAug0 to IAug5 are real transformations where as the rest of
the them correspond to well defined but synthetic groups. Samples of datasets
generated from these groups are shown in Fig. 4, 5, 6, and 7.

Tab. 11 and 12 shows the top 5 states obtained from the deep Q-learning
experiments in Sec. 5.1 for G-MNIST and G-Fashion-MNIST datasets respectively.

Table 6: Abbreviations for equivariance and augmentations used for describing top states obtained in deep Q-learning for GCNN.  |  Equivariance or Augmentation descriptions
---|---
P4 |  90°-rotation symmetry equivariance
H2 |  Horizontal symmetry equivariance
V2 |  Vertical symmetry equivariance
Zn |  Translation symmetry equivariance
Rot (30) |  Random rotation between +30°and -30 °
HFlip (0.5) |  Horizontal flips with prob 0.5
VFlip (0.5) |  Vertical flips with prob 0.5
Trans (0.2) |  Random translations of 0.2 times the image size
Scale (0.1) |  Random upscaling or downscaling of images by 10% size
Shear (10) |  Random shear transformations of 10°

##  Appendix C Basic Equivariant MLP construction Algorithm

Alg. 2 is the algorithmic version of the equivariant construction algorithm
using parameter sharing in (5).

for $i\in\mathbf{L}$ do

if $\mathbf{V}[i]<0$ then $C=C+1$

for $g\in\mathbf{G}$ do

$index_{g}=\Gamma_{g}(i)$

$I[index_{g}]=C$ return $\mathbf{I}$,C

Algorithm 2 Basic Equivariant MLP Construction [4]

##  Appendix D Training Details

Here we provide training details used in experiments in Sec. 5.

###  D.1 Group Equivariant MLPs

#### Single Equivariance Testing

We train the networks for single equivariance testing for datasets of size 10K
for 10 epochs using stochastic gradient descent with momentum [63] with
learning rate $10^{-3}$ and report the test accuracies on datasets of size 1K
in Tab. 7, 8 in Sec. E.

#### Deep Q-learning

For the deep learning part, the child group equivariant MLPs were trained on
mini datasets of size 4K with batchsize 64 for 4 epochs using stochastic
gradient descent with momentum [63] with a learning rate of $10^{-3}$ and
tested on mini datasets of size 1K to obtain the reward using (8). Once the
DQNs are trained, we obtain the top states for each case in the rows of Tab. 9
and Tab. 10 with maximum rewards. Then we retrain equivariant networks with
these states on datasets of size 10K for 10 epochs and report the accuracies
obtained in Tab. 2, Tab. 9 and Tab. 10 under the column AEN. Further, we also
provide the top states obtained in each case and the number of parameters in
them for general interest in Tab. 11 and Tab. 12 for G-MNIST and G-Fashion-
MNIST datasets in Sec. E, respectively.

###  D.2 Group Equivariant Convolutional Neural Networks

For the deep Q-learning part, the GCNNs were trained on mini datasets of size
6K with batchsize 32 for 4 epochs using stochastic gradient descent with
momentum with a learning rate of $10^{-3}$ and tested on mini datasets of size
1K.

##  Appendix E Additional Results

Here we provide complete set of experimental results, summary of which is
given in Sec. 5.

Table 7: Test accuracies for equivariant networks for data with single augmentations from G-MNIST. Transformation IAug$i$ in the row correspond to the single transformations from Tab. 4 and the columns indicate equivariant networks with Eq$i$ having equivariance to transformation IAug$i$. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12
---|---|---|---|---|---|---|---|---|---|---|---|---|---
IAug0 |  95.9 |  96.7 |  95.8 |  96.4 |  83.2 |  65.7 |  95.8 |  95.3 |  96.1 |  96.4 |  96.1 |  96.0 |  96.6
IAug1 |  83.5 |  87.2 |  85.6 |  82.5 |  50.1 |  49.1 |  84.1 |  83.9 |  81.8 |  81.8 |  83.2 |  83.6 |  85.4
IAug2 |  91.2 |  93.0 |  93.0 |  93.4 |  81.9 |  59.1 |  92.9 |  92.6 |  92.1 |  91.9 |  91.5 |  93.8 |  92.9
IAug3 |  92.3 |  92.7 |  93.2 |  93.2 |  79.2 |  62.9 |  93.0 |  91.8 |  91.6 |  91.9 |  92.5 |  92.7 |  92.9
IAug4 |  95.6 |  95.9 |  96.2 |  96.6 |  81.6 |  64.8 |  96.3 |  95.4 |  95.3 |  96.4 |  95.5 |  96.1 |  96.4
IAug5 |  95.7 |  96.2 |  96.0 |  96.4 |  81.0 |  64.8 |  96.1 |  95.3 |  95.6 |  96.2 |  96.0 |  96.0 |  97.0
IAug6 |  94.2 |  94.4 |  93.9 |  93.5 |  84.8 |  72.3 |  94.3 |  93.8 |  93.6 |  94.0 |  94.7 |  95.3 |  94.8
IAug7 |  94.2 |  94.7 |  94.8 |  94.1 |  81.8 |  62.3 |  94.4 |  93.9 |  93.2 |  95.8 |  95.4 |  94.5 |  95.9
IAug8 |  94.4 |  94.8 |  94.4 |  94.1 |  77.1 |  61.1 |  95.2 |  94.1 |  94.8 |  93.3 |  93.3 |  94.7 |  94.3
IAug9 |  94.6 |  95.2 |  93.9 |  94.8 |  83.7 |  64.9 |  94.9 |  95.5 |  95.1 |  94.2 |  94.1 |  94.5 |  94.7
IAug10 |  94.6 |  95.6 |  95.2 |  95.5 |  83.5 |  63.4 |  94.9 |  94.5 |  96.4 |  95.3 |  95.2 |  95.2 |  95.4
IAug11 |  95.6 |  95.1 |  95.6 |  94.1 |  82.1 |  72.0 |  95.2 |  94.8 |  95.1 |  95.6 |  95.1 |  95.2 |  96.3
IAug12 |  95.1 |  95.4 |  95.4 |  95.8 |  81.5 |  71.5 |  95.2 |  95.2 |  95.6 |  94.3 |  96.3 |  95.1 |  95.9
Table 8: Test accuracies for equivariant networks for data with single augmentations from G-Fashion-MNIST. Transformation IAug$i$ in the row correspond to the single transformations from Tab. 4 and the columns indicate equivariant networks with Eq$i$ having equivariance to transformation IAug$i$. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12
---|---|---|---|---|---|---|---|---|---|---|---|---|---
IAug0 |  84.8 |  85.9 |  84.6 |  84.8 |  73.4 |  76.4 |  85.5 |  84.1 |  85.4 |  85.2 |  84.1 |  85.4 |  85.5
IAug1 |  66.3 |  72.0 |  69.9 |  68.9 |  49.1 |  48.0 |  66.1 |  65.8 |  66.4 |  64.7 |  66.0 |  66.2 |  66.3
IAug2 |  83.8 |  84.3 |  85.4 |  84.5 |  73.5 |  74.6 |  84.7 |  83.9 |  84.0 |  82.7 |  83.3 |  84.2 |  83.9
IAug3 |  81.8 |  82.8 |  82.6 |  84.0 |  71.5 |  74.2 |  82.7 |  82.2 |  81.8 |  82.5 |  81.9 |  82.1 |  83.2
IAug4 |  84.8 |  85.0 |  84.3 |  85.2 |  72.6 |  72.7 |  84.9 |  84.2 |  83.6 |  83.7 |  84.3 |  83.3 |  84.6
IAug5 |  84.3 |  84.3 |  83.9 |  84.2 |  71.6 |  74.4 |  85.0 |  84.0 |  83.4 |  84.4 |  83.9 |  84.5 |  84.9
IAug6 |  84.6 |  83.3 |  84.6 |  84.9 |  71.6 |  76.9 |  84.2 |  84.0 |  83.8 |  84.3 |  83.7 |  84.5 |  84.0
IAug7 |  83.9 |  84.4 |  83.3 |  85.1 |  70.3 |  72.6 |  84.7 |  84.8 |  84.1 |  84.4 |  84.6 |  84.7 |  86.8
IAug8 |  82.6 |  84.1 |  83.1 |  83.8 |  69.5 |  75.4 |  85.3 |  85.2 |  84.8 |  82.7 |  82.8 |  84.2 |  83.1
IAug9 |  84.7 |  84.0 |  84.2 |  85.2 |  74.8 |  76.0 |  85.0 |  84.7 |  83.7 |  84.8 |  83.9 |  84.2 |  84.8
IAug10 |  84.6 |  84.2 |  83.2 |  83.8 |  72.3 |  74.8 |  84.3 |  83.7 |  84.0 |  84.3 |  83.5 |  83.7 |  83.9
IAug11 |  85.7 |  84.2 |  84.4 |  84.6 |  72.8 |  74.6 |  85.6 |  85.5 |  84.7 |  84.6 |  84.6 |  84.7 |  84.8
IAug12 |  84.3 |  84.4 |  84.3 |  85.0 |  73.8 |  75.8 |  84.9 |  84.4 |  83.9 |  84.3 |  84.1 |  84.7 |  84.5
Table 9: Test accuracies for equivariant networks for data with multiple augmentations from G-MNIST. Transformation Aug$i$ in the row correspond to the array of transformations from Tab. 5 and the columns indicate equivariant networks with Eq$i$ having equivariance to transformation IAug$i$ from Tab. 4. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12 |  AEN
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Aug0 |  95.9 |  96.7 |  95.8 |  96.4 |  83.2 |  65.7 |  95.8 |  95.3 |  96.1 |  96.4 |  96.1 |  96.0 |  96.6 |  96.0
Aug1 |  85.7 |  86.7 |  87.5 |  88.4 |  78.2 |  54.2 |  86.5 |  84.1 |  84.3 |  87.1 |  87.7 |  83.4 |  87.1 |  91.4
Aug2 |  66.9 |  71.9 |  72.0 |  70.6 |  39.9 |  48.1 |  71.7 |  70.4 |  71.5 |  65.0 |  67.5 |  66.4 |  67.3 |  77.5
Aug3 |  73.7 |  73.9 |  73.9 |  72.1 |  46.3 |  41.4 |  72.7 |  69.4 |  70.1 |  75.3 |  68.1 |  71.8 |  73.2 |  77.4
Aug4 |  69.5 |  73.9 |  69.2 |  68.6 |  44.2 |  44.3 |  67.7 |  66.8 |  66.1 |  67.1 |  66.6 |  69.8 |  66.8 |  72.9
Aug5 |  51.0 |  57.6 |  54.4 |  55.8 |  38.6 |  37.8 |  54.8 |  54.3 |  53.9 |  54.8 |  55.2 |  62.2 |  56.2 |  69.4
Table 10: Test accuracies for equivariant networks for data with multiple augmentations from G-Fashion-MNIST. Transformation Aug$i$ in the row correspond to the array of transformations from Tab. 5 and the columns indicate equivariant networks with Eq$i$ having equivariance to transformation IAug$i$ from Tab. 4. |  Eq0 |  Eq1 |  Eq2 |  Eq3 |  Eq4 |  Eq5 |  Eq6 |  Eq7 |  Eq8 |  Eq9 |  Eq10 |  Eq11 |  Eq12 |  AEN
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Aug0 |  84.8 |  85.7 |  84.6 |  84.8 |  73.4 |  76.4 |  85.5 |  84.1 |  85.4 |  85.2 |  84.1 |  85.4 |  85.5 |  85.7
Aug1 |  77.3 |  78.5 |  78.0 |  79.8 |  65.6 |  68.5 |  78.5 |  77.4 |  77.7 |  78.7 |  79.6 |  77.9 |  79.4 |  80.3
Aug2 |  60.1 |  61.8 |  60.1 |  63.8 |  41.1 |  47.2 |  63.0 |  60.9 |  61.9 |  59.5 |  58.3 |  60.7 |  59.6 |  64.4
Aug3 |  58.0 |  59.8 |  58.2 |  57.8 |  43.5 |  41.2 |  58.0 |  59.8 |  58.8 |  60.0 |  57.7 |  59.7 |  57.1 |  63.4
Aug4 |  59.4 |  60.3 |  60.5 |  59.1 |  40.8 |  39.2 |  59.8 |  60.1 |  58.7 |  60.1 |  58.1 |  59.8 |  60.1 |  60.9
Aug5 |  50.8 |  54.6 |  53.1 |  52.5 |  36.6 |  34.6 |  53.8 |  54.1 |  53.3 |  53.5 |  52.6 |  57.8 |  52.3 |  60.4
Table 11: Top group symmetries obtained from deep Q-learning corresponding to different combination of transformations in the G-MNIST dataset. Each row correspond to an array of group symmetry, where a 1 in the $i$th column indicates the presence of equivariance to IAug$i$ and $0$ indicates the absence of it. |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  # parameters (millions)
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Aug0 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  0 |  0 |  0.15
Aug1 |  0 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  0 |  1 |  0.04
Aug2 |  0 |  1 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  0.04
Aug3 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  1 |  0 |  1 |  1 |  0.018
Aug4 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  0 |  0.03
Aug5 |  1 |  0 |  0 |  0 |  0 |  1 |  0 |  1 |  0 |  0 |  1 |  0 |  0.018
Table 12: Top group symmetries obtained from deep Q-learning corresponding to different combination of transformations in the G-Fashion-MNIST dataset. Each row correspond to an array of group symmetry, where a 1 in the $i$th column indicates the presence of equivariance to IAug$i$ and $0$ indicates the absence of it. |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  # parameters (millions)
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Aug0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0.12
Aug1 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  0.12
Aug2 |  0 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0.12
Aug3 |  0 |  0 |  1 |  0 |  0 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0.04
Aug4 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0.06
Aug5 |  1 |  0 |  1 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  1 |  0 |  0.015
Table 13: Top states obtained from deep Q-learning corresponding to equivariances, augmentations, and size used in training a GCNN on several image datasets and comparison with traditional translational (Zn) equivariant CNNs. Dataset |  Equivariances |  Augmentations |  Size |  Test accuracies
---|---|---|---|---
|  (P4, H2, V2, Zn) |  (HFlip (0.5), Scale (0.1)) |  Large |  $65.25\%$
|  (P4, H2, V2, Zn) |  — |  Large |  $63.06\%$
CIFAR10 |  (P4, H2, V2, Zn) |  (HFlip (0.5)) |  Large |  $63.84\%$
|  (P4, H2, V2, Zn) |  (Shear (10)) |  Large |  $62.55\%$
|  (Zn) |  — |  Large |  $55.17\%$
|  (P4, H2, V2, Zn) |  (Scale (0.1), Shear (10)) |  Small |  $87.91\%$
|  (P4, H2, V2, Zn) |  — |  Large |  $89.70\%$
SVHN |  (P4, H2, V2, Zn) |  (Shear (10)) |  Small |  $87.81\%$
|  (P4, H2, V2, Zn) |  (Rot (30), Scale (0.1)) |  Large |  $87.66\%$
|  (Zn) |  — |  Large |  $85.72\%$
|  (P4, H2, V2, Zn) |  (Rot (30)) |  Small |  $93.45\%$
|  (P4, H2, V2, Zn) |  — |  Small |  $94.05\%$
RotMNIST |  (P4, H2, V2, Zn) |  (Shear (10)) |  Small |  $94.44\%$
|  (P4, H2, V2, Zn) |  (Scale (0.1)) |  Small |  $94.57\%$
|  (Zn) |  — |  Large |  $92.60\%$
|  (P4, H2, V2, Zn) |  — |  Small |  $92.74\%$
|  (P4, H2, V2, Zn) |  (Scale (0.1)) |  Small |  $94.21\%$
ASL |  (P4, H2, V2, Zn) |  (Shear (10)) |  Small |  $90.93\%$
|  (P4, H2, V2, Zn) |  (VFlip (0.5)) |  Large |  $93.41\%$
|  (Zn) |  — |  Large |  $89.33\%$
|  (P4, H2, V2, Zn) |  — |  Large |  $91.51\%$
|  (P4, H2, V2, Zn) |  — |  Small |  $92.26\%$
EMNIST |  (P4, H2, V2, Zn) |  (Rot (30)) |  Large |  $91.01\%$
|  (P4, V2, Zn) |  (Shear (10)) |  Large |  $93.99\%$
|  (Zn) |  — |  Large |  $92.93\%$
|  (P4, H2, V2, Zn) |  (Shear (10)) |  Large |  $93.59\%$
|  (P4, H2, V2, Zn) |  — |  Large |  $93.57\%$
KMNIST |  (P4, H2, V2, Zn) |  (Rot (30), Scale (0.1)) |  Large |  $88.30\%$
|  (P4, H2, V2, Zn) |  — |  Small |  $93.55\%$
|  (Zn) |  — |  Large |  $90.94\%$

##  Appendix F Additional Plots

Here we provide complete set of plots, selected ones are shown in Sec. 5 to
summarize and explain the results.

(a) Aug0

(b) Aug1

(c) Aug2

(d) Aug3

(e) Aug4

(f) Aug5

Figure 8: Deep Q-learning performance for datasets with various combinations
of transformations from G-MNIST. The Q-learning agent samples group
symmetries, which is used for creating equivariant network. A function of the
accuracy is used as the reward function. The Q-learning agent shows
improvement in accuracy as the $\epsilon$ decreases.

(a) Aug0

(b) Aug1

(c) Aug2

(d) Aug3

(e) Aug4

(f) Aug5

Figure 9: Deep Q-learning performance for datasets with various combinations
of transformations from G-Fashion-MNIST. The Q-learning agent samples group
symmetries, which is used for creating equivariant network. A function of the
accuracy is used as the reward function. The Q-learning agent shows
improvement in accuracy as $\epsilon$ decreases.

(a) CIFAR10

(b) SVHN

(c) RotMNIST

(d) ASL

(e) EMNIST

(f) KMNIST

Figure 10: Deep Q-learning performance on several image datasets where the
child network is a group convolutional neural network with groups symmetries
being any combination of rotation, horizontal symmetry, and vertical symmetry.
In addition to group symmetries for network equivariance the Q-learning agent
chooses from one or more of six augmentations, namely, random rotation,
horizontal flip, vertical flip, translate, scale, and shear. A function of the
accuracy is used as the reward function. The Q-learning agent shows
improvement in accuracy as $\epsilon$ decreases. Across all the datasets
above, we find that equivariance dominates the high-performing networks chosen
by the Q-learning over augmentations.

##  Appendix G Proofs

###### Proof to Thm. 1.

($\Rightarrow$) First we show that $\phi$ is equivariant to $G_{1}$ under
$(\mu^{G_{1}},\bar{\mu}^{G_{1}})$ and $G_{2}$ under
$(\mu^{G_{2}},\bar{\mu}^{G_{2}})$ implies $\phi$ is equivariant to
$G_{1}\rtimes_{\alpha}G_{2}$ under $(\Gamma,\bar{\Gamma})$. Thus, we want to
show that for all $g_{1}\in G_{1},g_{2}\in G_{2}$, and $x\in\mathcal{X}$,
$\phi(\Gamma_{(g_{1},g_{2})}(x))=\bar{\Gamma}_{(g_{1},g_{2})}(\phi(x)),$
assuming $\phi(\mu_{g_{i}}^{G_{i}}(x))=\bar{\mu_{g_{i}}^{G_{i}}}(\phi(x))$ for
$i\in\\{1,2\\}$.

Since $(g_{1},e)(e,g_{2})=(g_{1}\alpha_{e}(e),eg_{2})=(g_{1},g_{2})$ from the
definition of multiplication in semidirect product in Def. 3, and $\Gamma$ is
a homomorphism, we have

$\phi(\Gamma_{(g_{1},g_{2})}(x))=\phi(\Gamma_{(g_{1},e)}(\Gamma_{(e,g_{2})}(x))),$
(6)

Continuing from (6) and noting the assumptions in the theorem from (1), (2),
(3), (4) gives us

$\displaystyle\phi(\Gamma_{(g_{1},e)}(\Gamma_{(e,g_{2})}(x)))$
$\displaystyle=\phi(\mu_{g_{1}}^{G_{1}}(\mu_{g_{2}}^{G_{2}}(x)))\stackrel{{\scriptstyle(a)}}{{=}}\bar{\Gamma}_{(g_{1},e)}(\phi(\mu_{g_{2}}^{G_{2}}(x)))$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\bar{\Gamma}_{(g_{1},e)}\bar{\Gamma}_{(e,g_{2})}(\phi(x))$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\bar{\Gamma}_{(g_{1},g_{2})}(\phi(x))$

where (a) holds since
$\phi(\mu_{g_{1}}^{G_{1}}(\mu_{g_{2}}^{G_{2}}(x)))=\bar{\mu}_{g_{1}}^{G_{1}}(\phi(\mu_{g_{2}}^{G_{2}}(x)))$
because $\phi(\mu_{g_{1}}^{G_{1}}(x))=\bar{\mu}_{g_{1}}^{G_{1}}(\phi(x))$, and
follows from the assumption
$\bar{\Gamma}_{(g_{1},e)}(y)=\bar{\mu}_{g_{1}}^{G_{i}}(y)$, (b) follows from
the equivariance property
$\phi(\mu_{g_{2}}^{G_{2}}(x))=\bar{\mu}_{g_{2}}^{G_{2}}(\phi(x))$ and from the
assumption in the theorem
$\bar{\mu}_{g_{2}}^{G_{2}}(y)=\bar{\Gamma}_{(e,g_{2})}(y)$, and (c) follows
since $\bar{\Gamma}$ is a homomorphism and $(g_{1},g_{2})=(g_{1},e)(e,g_{2})$.
Thus, we have
$\phi(\Gamma_{(g_{1},g_{2})}(x))=\bar{\Gamma}_{(g_{1},g_{2})}(\phi(x))$, for
all $x\in\mathcal{X},g_{1}\in G_{1},g_{2}\in G_{2}$.

Now we prove the other direction of the theorem. Given

$\displaystyle\phi(\Gamma_{(g_{1},g_{2})}(x))=\bar{\Gamma}_{(g_{1},g_{2})}(\phi(x)),$
(7)

for all $x\in\mathcal{X},g_{1}\in G_{1},g_{2}\in G_{2}$, we want to show
$\phi(\mu_{g_{i}}^{G_{i}}(x))=\bar{\mu}_{g_{i}}^{G_{i}}(\phi(x)),$ for all
$x\in\mathcal{X}$, $g_{i}\in G_{i}$ for $i\in\\{1,2\\}$. For $i=1$, setting
$g_{2}=e,x\in\mathcal{X}$ in (7), we have
$\phi(\Gamma_{(g_{1},e)}(x))=\bar{\Gamma}_{(g_{1},e)}(\phi(x))$, which implies
$\phi(\mu_{g_{1}}^{G_{1}}(x))=\bar{\mu}^{G_{1}}_{g_{1}}(\phi(x))$ from the
assumption $\Gamma_{(g_{1},e)}(x)=\mu_{g_{1}}^{G_{1}}(x)$,
$\bar{\Gamma}_{(g_{1},e)}(x)=\bar{\mu}_{g_{1}}^{G_{1}}(x)$. The proof for
$i=2$ follows the same procedure and is omitted. ∎

###### Proof to Claim. 1.

For simplicity, take $G=G_{1}\rtimes_{\alpha}G_{2}$, i.e.
$G_{array}=[G_{1},G_{2}]$, which can be easily extended to general semidirect
products. From Thm. 2, if for each $i\in\mathbf{L}$, if $\Gamma_{g}(i)$
belongs to the same orbit for all $g\in G$, then $\mathbf{W}$ is
$G$-equivariant.

Taking any index $i$, we want to show that all the indices in the set

$\displaystyle\Gamma_{G}(i)=\\{\Gamma_{(g_{x},g_{y})}(i):g_{x}\in
G_{1},g_{y}\in G_{2}\\}$

belong to the same orbit.

First we note that all elements in $Q$ at any point in time in Alg. 1 belong
to the same orbit. This is easy to see since for any index $i$ popped out of
Q, the visited nodes added to $Q$ are of the form $\Gamma_{g}(i)$ for some
$g\in G$, which belong to the same orbit as $i$.

Now we show that starting with a non-empty $Q$ consisting of an index $i$, $Q$
becomes empty only when all indices in $\Gamma_{G}(i)$, the orbit in which $i$
belongs, has been visited and assigned the same orbit number, denoted by $C$
in Alg. 1. Without loss of generality, say, $i$ is the first index of an orbit
popped out of $Q$. Then the indices $\Gamma_{g}(i)$ are added to $Q$ and
assigned the same orbit for $g\in G_{1}\cup G_{2}$. So, thus far we have added
$\Gamma_{G_{1}}(i)\cup\Gamma_{G_{2}}(i)$ to the orbit and $Q$, where

$\displaystyle\Gamma_{G_{1}}(i)$
$\displaystyle=\\{\Gamma_{g_{x},e}(i):g_{x}\in G_{1}\\}$
$\displaystyle\Gamma_{G_{2}}(i)$
$\displaystyle=\\{\Gamma_{e,g_{y}}(i):g_{y}\in G_{2}\\}.$

Now, when $\Gamma_{(g_{0},e)}(i)$ is popped out of $Q$ for some $g_{0}\in
G_{1}$, the indices $\Gamma_{(g_{0},g_{y})}(i)$ for all $g_{y}\in G_{2}$ get
added to the orbit. Similarly, when $\Gamma_{(e,g_{0})}(i)$ is popped out of
$Q$ for some $g_{0}\in G_{2}$, the indices $\Gamma_{(g_{x},g_{0})}$ for all
$g_{x}\in G_{1}$ get added to the orbit. Hence, all the indices in the current
orbit are visited and assigned the same orbit number. Further, we only add
indices $i$ to $Q$ that were previously not visited, hence $Q$ gets emptied
when all the indices in the orbit are visited.

We also know that orbits of a group are disjoint, hence, when $Q$ gets emptied
and new indices $i$ with $V[i]<0$ in $L$ are added to $Q$ with a new orbit,
these indices would not overlap with any of the indices already added to other
orbits. ∎

##  Appendix H Deep Q-learning details

#### Search space

For Sec. 5.1 where we work with fully connected layers, we represent each
architecture by a discrete state vector $S$ of length $g_{size}$ and $S[i]$
takes binary values with the network equivariant to the $i$th group if
$S[i]=1$, otherwise not.

For Sec. 5.2 where we work with convolutional neural networks, the state $S$
is a vector of length $10$ with the first $3$ binary entries indicating
indicating the presence of the groups $P4,H2,V2$ from Tab. 6 in that order.
The next 6 entries indicate the presence of the 6 augmentations in Tab. 6 in
that order. The last binary entry is to choose between a large and a small
model. We ensure that these networks with small size and different
equivariances have the same number of trainable parameters by adjusting the
channel numbers in them. For the large network size, we simply multiply the
number of channels by a factor of 1.5. This is to check whether a DQN has any
particular preference over network sizes.

#### Action space

For MLPs and GCNNs, each action is a one-hot vector of length $g_{size}$ and
10 respectively, where if the non-zero index is $i$, then the binary value of
$S[i]$ is toggled.

#### Evaluation strategy

Since we use the validation accuracy of a trained network as a reward, at each
step of the search algorithm, the Q-learning agent trains a network that is
equivariant to groups indicated by the state vector by computing the parameter
sharing scheme using Alg. 1 for MLPs and directly using precomputed parameter
sharing indices of relevant groups from [2] for GCNNs. However, training a
network over the entire dataset at each step is computationally expensive.
Hence we use several tricks to speed up our search, inspired by recent works
in neural architecture search.

For computing the validation accuracy, we choose small subsets of sizes $4000$
and $1000$ of the dataset as our training and testing sets, similar to [64].
Further, to ensure that a model with the same configuration of groups and
sizes is not trained twice in the process of search, we store and reuse
validation accuracies, as in [45]. We train each network for 4 epochs and use
maximum validation accuracy obtained from after each epoch for computing the
reward.

#### Reward function

The agent receives a reward proportional to the validation accuracy of the
network corresponding to the next state, which it uses to compute $Q$-values
in the state-action space. More precisely, we use the reward function

$\displaystyle R(s,a)=x\exp{\\{|x|\\}},$ (8)

where $x=acc(s,a)-acc_{0}$, $acc(s,a)$ is the validation accuracy of the
network obtained by taking action $a$ at state $s$, $acc_{0}$ is the accuracy
of a baseline MLP without any group equivariance, and $|\cdot|$ is the
absolute value. This reward function amplifies both reward for accuracies
above baseline accuracies and penalties for accuracies below baseline
performance.

#### Training details

For training our deep Q-learning agent, we use the discount factor
$\gamma=0.5$, which allows learning from the rewards obtained from the current
state as well as the expected rewards that can be obtained in the future. We
use the $\epsilon$-greedy strategy with starting value of $\epsilon=1.0$ and
train a fixed number of models per value of $\epsilon$, as shown in Tab. 14.
We use a fully connected network with dimension $12\times 400\times 400\times
400\times 12$ to compute $Q$-values in our deep Q-learning algorithm. We store
the transitions in a replay memory and use a batch size of $512$ and $128$ for
training the agent for MLPs and GCNNs respectively to take into account that
the number of possible states we considered for GCNNs were relatively fewer.

Table 14: A fixed number of models were trained per value of $\epsilon$ in our deep Q-learning search for group equivariant MLPs (GEMLPs) and group convolutional neural networks (GCNN). $\epsilon$ value |  1.0 |  0.9 |  0.8 |  0.7 |  0.6 |  0.5 |  0.4 |  0.3 |  0.2 |  0.1 |  0.05 |  0.01
---|---|---|---|---|---|---|---|---|---|---|---|---
# models (GEMLP) |  200 |  100 |  100 |  100 |  100 |  100 |  100 |  50 |  50 |  50 |  50 |  —
# models (GCNN) |  50 |  50 |  50 |  50 |  50 |  50 |  50 |  50 |  50 |  50 |  50 |  50