# On the Symmetries of Deep Learning Models and their Internal Representations

Charles Godfrey1,∗, Davis Brown1,∗, Tegan Emerson1,3,4, Henry Kvinge1,2,3
1Pacific Northwest National Laboratory
2Department of Mathematics, University of Washington
3Department of Mathematics, Colorado State University
4Department of Mathematical Sciences, University of Texas, El Paso
∗Equal contribution
<EMAIL_ADDRESS>

###### Abstract

Symmetry has been a fundamental tool in the exploration of a broad range of
complex systems. In machine learning, symmetry has been explored in both
models and data. In this paper we seek to connect the symmetries arising from
the architecture of a family of models with the symmetries of that family’s
internal representation of data. We do this by calculating a set of
fundamental symmetry groups, which we call the _intertwiner groups_ of the
model. Each of these arises from a particular nonlinear layer of the model and
different nonlinearities result in different symmetry groups. These groups
change the weights of a model in such a way that the underlying function that
the model represents remains constant but the internal representations of data
inside the model may change. We connect intertwiner groups to a model’s
internal representations of data through a range of experiments that probe
similarities between hidden states across models with the same architecture.
Our work suggests that the symmetries of a network are propagated into the
symmetries in that network’s representation of data, providing us with a
better understanding of how architecture affects the learning and prediction
process. Finally, we speculate that for ReLU networks, the intertwiner groups
may provide a justification for the common practice of concentrating model
interpretability exploration on the activation basis in hidden layers rather
than arbitrary linear combinations thereof.

##  1 Introduction

Symmetry provides an important path to understanding across a range of
disciplines. This principle is well-established in mathematics and physics,
where it has been a fundamental tool (e.g., Noether’s Theorem [Noe18]).
Symmetry has also been brought to bear on deep learning problems from a number
of directions. There is, for example, a rich research thread that studies
symmetries in data types that can be used to inform model architectures. The
most famous examples of this are standard convolutional neural networks which
encode the translation invariance of many types of semantic content in natural
images into a network’s architecture. In this paper, we focus on connections
between two other types of symmetry associated with deep learning models: the
symmetries in the learnable parameters of the model and the symmetries across
different models’ internal representation of the same data.

The first of these directions of research starts with the observation that in
modern neural networks there exist models with different weights that behave
identically on all possible input. We show that at least some of these
equivalent models arise because of symmetries intrinsic to the nonlinearities
of the network. We call these groups of symmetries, each of which is attached
to a particular type of nonlinear layer $\sigma$ of dimension $n$, the
_intertwiner groups_ $G_{\sigma_{n}}$ of the model. These intertwiner groups
come with a natural action on network weights for which the realization map to
function space of [JGH18] is invariant (proposition 3.4). As such they provide
a unifying framework in which to discuss well-known weight space symmetries
such as permutation of neurons [Bre+19] and scale invariance properties of
$\operatorname{ReLU}$ and batch-norm [NH10, IS15].

Next, we tie our intertwiner groups to the symmetries between different
model’s internal representations of the same data. We do this through a range
of experiments that we describe below; each builds on a significant recent
advance in the field.

Neural stitching with intertwiner groups: The work of [BNB21, Csi+21, LV15]
demonstrated that one can take two trained neural networks, say A and B, with
the same architecture but trained from different randomly initialized weights,
and connect the early layers of network A to the later layers of network B
with a simple “stitching” layer and achieve minimal loss in prediction
accuracy. This was taken as evidence of the similarity of strong model’s
representations of data. Though the original experiments use a fully connected
linear layer to stitch, we provide theoretical evidence in theorem 4.2 that
much less is needed. Indeed, we show that the intertwiner group (which has far
fewer parameters in general) is the minimal viable stitching layer to preserve
accuracy. We conduct experiments stitching networks at $\operatorname{ReLU}$
activation layers with the stitching layer restricted to elements of the group
$G_{\operatorname{ReLU}}$. We show that one can stitch CNNs on CIFAR10 [Kri09]
with only elements of $G_{\operatorname{ReLU}}$ incurring less than $\approx
10\%$ accuracy penalty at most activation layers. This is surprisingly close
to the losses found when one allows for a much more expressive linear layer to
be used to stitch two networks together.

Figure 1: Full, reduced rank, and $G_{\operatorname{ReLU}}$ 1-by-1 convolution
stitching penalties (4.3) for two independently initialized Myrtle CNNs
[Pag18] on CIFAR10 . Confidence intervals were taken over 5 independent runs.
The accuracy of the independently initialized models was 90.5 $\pm$ 0.2 %.

Representation dissimilarity metrics for $G_{\operatorname{ReLU}}$: In section
5 we present two statistical dissimilarity measures for
$\operatorname{ReLU}$-activated hidden features in different networks, say $A$
and $B$, that are maximized when the hidden features differ by a
transformation from $G_{\operatorname{ReLU}}$ (that is, permutations and
independent scaling of variables). These metrics are analogous to the metrics
CKA [Kor+19] and SVCCA [Rag+17], which are invariant to orthogonal
transformations, and are maximized when both hidden features differ only up to
orthogonal rotation and isotropic scaling. We compare and contrast these
metrics with their orthogonal counterparts, as well as with stitching
experiment results.

(a)

(b)

Figure 2: $G_{\operatorname{ReLU}}$-CKA and orthogonal CKA for two
independently initialized ResNet20s trained on CIFAR10. Layers marked with ‘*’
occur inside residual blocks (remark 3.6). Results averaged over 5 independent
runs of the experiment.

Impact of activation functions on interpretability: An intriguing finding from
[Bau+17, §3.2] was that individual neurons are more interpretable than random
linear combinations of neurons. Our results on intertwiner groups (theorem
3.3) predict that this is a particular feature of ReLU networks. Indeed, we
show in section 6 that in the absence of $\operatorname{ReLU}$ activations
interpretability does not decrease when one moves from individual neurons to
linear combinations of neurons. This result suggests that intertwiner groups
provide a theoretical justification for the explainable AI community’s focus
on individual neuron activations, rather than linear combinations thereof
[Erh+09, ZF14, Zho+15, Yos+15, Na+19], but that this justification is only
valid for layers with certain activation functions.

Figure 3: Fraction of network dissection interpretable units under rotations
of the representation basis for a ResNet-50, as well as a modified ResNet-50
and ConvNeXt model (both without an activation function on the residual
output). We note that the models without residual activation functions also
have far fewer concept covering units for a given basis.

Taken together, our experiments provide evidence that a network’s symmetries
(realized through intertwiner groups) propagate down to symmetries of a
model’s internal representation of data. Since understanding how different
models process the same data is a fundamental goal in fields such as
explainable AI and the safety of deep learning systems, we hope that our
results will provide an additional lens with which to grapple with these
problems.

##  2 Related Work

The research on symmetries of neural networks is extensive, especially when
one considers that symmetry considerations are a frequently used tool even
when they are not the primary focus of a given paper, hence we aim to provide
a representative sample knowing it will be incomplete. [GBC16, Bre+19, FB17,
Yi+19] study the effect of weight space symmetries on the loss landscape. On
the other hand, [BMC15, GBC16, Kun+21, Men+19] study the effect of weight
space symmetries on training dynamics, while [GBC16, RK20] show that weight
space symmetries pose an obstruction to model identifiability.

Neural stitching was introduced as a means of comparing learned
representations between networks in [LV15]. In [BNB21] it was shown to have
intriguing connections with the “Anna Karenina ” (high performance models
share similar internal representations of data) and “more is better”
(stitching later layers of a weak model to early layers of a model trained
with more data/parameters/epochs can improve performance) phenomena. [Csi+21]
considered constrained stitching layers by restricting the rank of the
stitching matrix or by introducing an $\ell_{1}$ sparsity penalty — our
methods are distinct in that we explicitly optimize over the intertwiner group
for ReLU nonlinearities (permutations and scalings). Both [BNB21, Csi+21]
compare their stitching results with statistical dissimilarity metrics such as
CKA. One of our dissimilarity metrics in section 5 is a close relative of the
permutation Procrustes distance introduced in [Wil+21], and also closely
related to the orthogonal Procrustes distance considered in [DDS21]. The other
is a variant of CKA [Kor+19] in which a certain dot product
$\sum_{i=1}^{d}x_{i}y_{i}$ is replaced by the operation $\max\\{x_{1}\cdot
y_{1},\dots,x_{d}\cdot y_{d}\\}$.

Approaches to deep learning interpretability often assume that the activation
basis is special [Erh+09, ZF14, Zho+15, Yos+15, Na+19]. Studying individual
neurons rather than linear combinations of neurons significantly reduces the
complexity of low-level interpretability approaches to the understanding of
neural networks [Elh+21]. In tension with this, many different projections of
hidden layer activations appear to be semantically coherent [Sze+14]. However,
Bau et al. found evidence that the representations closer to the coordinate
basis align more with human concepts than random unitary transformations.

##  3 The Symmetries of Nonlinearities

Let $\operatorname{Mat}_{n_{1},n_{0}}(\mathbb{R})$ be the algebra of all
$n_{0}\times n_{1}$ real matrices and $GL_{n}(\mathbb{R})$ be the group of all
invertible $n\times n$ matrices. Let $\sigma:\mathbb{R}\rightarrow\mathbb{R}$
be a continuous function. For any $n\in\mathbb{N}$, we can build a
_nonlinearity_ $\sigma_{n}$ from $\mathbb{R}^{n}$ to $\mathbb{R}^{n}$ by
applying $\sigma$ coordinatewise, i.e.,
$\sigma_{n}(x_{1},\dots,x_{n})=(\sigma(x_{1}),\dots,\sigma(x_{n}))$. Let
$\ell_{i}:\mathbb{R}^{n_{i-1}}\rightarrow\mathbb{R}^{n_{i}}$ be the
composition of an affine layer and a nonlinear layer, so that
$\ell_{i}(x):=\sigma_{n_{i}}(W_{i}x+b_{i})$ if $1\leq i<k$, and
$\ell_{k}(x):=W_{k}x+b_{k}$. Here
$W_{i}\in\operatorname{Mat}_{n_{i},n_{i-1}}(\mathbb{R})$ and
$b_{i}\in\mathbb{R}^{n_{i}}$ are the weights and bias of the layer
respectively. We define $f:\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}^{n_{k}}$ to
be the neural network $f=\ell_{k}\circ\dots\circ\ell_{1}$. For each $1\leq
i<k-1$ we can then decompose $f$ as $f=f_{>i}\circ f_{\leq i}$ where

$f_{\leq i}=\ell_{i}\circ\dots\circ\ell_{1}\quad\text{and}\quad
f_{>i}=\ell_{k}\circ\dots\circ\ell_{i+1}.$

We define

$W:=(W_{i},b_{i}\,|\,i=1,\dots,k)\quad\text{and}\quad\mathcal{W}:=\prod_{i=1}^{k}(\operatorname{Mat}_{n_{i},n_{i-1}}(\mathbb{R})\times\mathbb{R}^{n_{i}})$

where the former is the collection of all weights of $f$ and the latter is the
space of all possible weights for a given architecture. When we want to
emphasize the dependence of $f$ on weights $W$, we write $f(-,W)$ (and
similarly $f_{\leq i}(-,W),f_{>i}(-,W)$).

One of the topics this work will consider is vector space bases for $f$’s
hidden spaces $\mathbb{R}^{n_{i}}$, for $1\leq i\leq k-1$. We will investigate
the legitimacy of analyzing features $f_{\leq i}(D)$ for dataset
$D\subset\mathbb{R}^{n_{0}}$ with respect to the _activation basis_ for
$\mathbb{R}^{n_{i}}$ which is simply the usual coordinate basis,
$e_{1},\dots,e_{n_{i}}$ where $e_{j}=[\delta_{j\ell}]^{n_{i}}_{\ell=1}$ is
naturally parameterized by individual neuron activations. Note that
$\mathbb{R}^{n_{i}}$ has an infinite number of other possible bases that could
be chosen.

###  3.1 Intertwiner Groups

For any $0\leq i<k$, elements of $GL_{n_{i}}(\mathbb{R})$ can be applied to
the hidden activation space $\mathbb{R}^{n_{i}}$ both before and after the
nonlinear layer $\sigma_{n_{i}}$. We define

$G_{\sigma_{n_{i}}}:=\\{A\in GL_{n_{i}}(\mathbb{R})\,|\,\text{ there exists a
}B\in GL_{n_{i}}(\mathbb{R})\text{ such that }\sigma_{n_{i}}\circ
A=B\circ\sigma_{n_{i}}\\}.$

Informally, we can understand $G_{\sigma_{n_{i}}}$ to be the set of all
invertible linear transformations whose action on $\mathbb{R}^{n_{i}}$ prior
to the nonlinear layer $\sigma_{n_{i}}$ has an equivalent invertible
transformation after $\sigma_{n_{i}}$. This is a generalization of the common
procedure of understanding a function by understanding those operators that
commute with it. For any $A\in GL_{n_{i}}(\mathbb{R})$, we can write
$\sigma(A)$ for the $n_{i}\times n_{i}$ matrix formed by applying $\sigma$ to
all entries in $A$.

######  Lemma 3.1.

Suppose $\sigma(I_{n})$ is invertible and for each $A\in GL_{n}(\mathbb{R})$
define $\phi_{\sigma}(A)=\sigma(A)\sigma(I_{n})^{-1}$. Then $G_{\sigma_{n}}$
is a group, $\phi_{\sigma}:G_{\sigma_{n}}\to GL_{n}(\mathbb{R})$ is a
homomorphism and $\sigma_{n}\circ A=\phi_{\sigma}(A)\circ\sigma_{n}$.

We defer all proofs to appendix E. We include concrete examples of $\sigma$
for small $n_{i}$ there as well.

######  Definition 3.2.

When the hypotheses of lemma 3.1 are satisfied (namely, $\sigma(I_{n})$ is
invertible) we call $G_{\sigma_{n}}$ the intertwiner group of the activation
$\sigma_{n}$. We denote the image of the homomorphism $\phi_{\sigma}$ as
$\phi_{\sigma}(G_{\sigma_{n}})$.

The intertwiner group $G_{\sigma_{n}}$ and $\phi_{\sigma}$ are concretely
described for a range of activations in fig. 4 — the last two examples
motivate the generality of definition 3.2. Note also that in both of those
cases $A\mapsto\phi_{\sigma}(A)$ is _not_ a homomorphism on all of
$GL_{n}(\mathbb{R})$, but _is_ a homomorphism when restricted to the
appropriate subgroup $G_{\sigma_{n}}$. Details related to the calculations can
be found in section E.2.

Activation |  $G_{\sigma_{n}}$ |  $\phi_{\sigma}(A)$
---|---|---
$\sigma(x)=x$ (identity) |  $GL_{n}(\mathbb{R})$ |  $A$
$\sigma(x)=\frac{e^{x}}{1+e^{x}}$ |  $\Sigma_{n}$ |  $A$
$\sigma(x)=\operatorname{ReLU}(x)$ |  Matrices $PD$, where $D$ has positive entries |  $A$
$\sigma(x)=\text{LeakyReLU}(x)$ |  Same as $\operatorname{ReLU}$ as long as negative slope $\neq 1$ |  $A$
$\sigma(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}$ (RBF) |  Matrices $PD$, where $D$ has entries in $\\{\pm 1\\}$ |  $\mathrm{abs}(A)$
$\sigma(x)=x^{d}$ (polynomial) |  Matrices $PD$, where $D$ has non-zero entries |  $A^{\odot d}$
Figure 4: Explicit descriptions of $G_{\sigma_{n}}$ and $\phi_{\sigma}$ for
six different activations. Here $P\in\Sigma_{n}$ is a permutation matrix, $D$
is a diagonal matrix, $\mathrm{abs}$ denotes the operation of taking the
absolute value of every entry of $A$, and $A^{\odot d}$ denotes the process of
taking the $d$th power of every entry of $A$.

The following theorem shows that the activation basis is intimately related to
the intertwiner group of $\operatorname{ReLU}$: $G_{\operatorname{ReLU}}$
admits a natural group-theoretic characterization in terms of the rays spanned
by the activation basis, and dually the rays spanned by the activation basis
can be recovered from $G_{\operatorname{ReLU}}$ . While both its statement and
proof are elementary, our interest in this theorem lies in the question of
whether it could _potentially_ provide theoretical justification for focusing
model interpretation studies on individual activations. We investigate this
question further in section 6.

######  Theorem 3.3.

The group $G_{\operatorname{ReLU}_{n}}$ is precisely the stabilizer of the set
of rays $\\{\mathbb{R}_{\geq 0}e_{i}\subset\mathbb{R}^{n}|i=1,\dots,n\\}$.
Moreover if $\mathbb{R}_{\geq 0}v_{1},\dots,\mathbb{R}_{\geq
0}v_{N}\subseteq\mathbb{R}^{n}$ is a finite set of rays stabilized by
$G_{\operatorname{ReLU}}$, then for each $v_{i}=[v_{i1},\dots,v_{in}]^{T}$, it
must be that $v_{ij}=0$ for all but one $j\in\\{1,\dots,n\\}$. Equivalently up
to multiplication by a positive scalar every $v_{i}$ is of the form $\pm
e_{j}$ for some $j$.

###  3.2 Weight space symmetries

The intertwiner group is also a natural way to describe the weight space
symmetries of a neural network. We denote by $\mathcal{F}\subseteq
C(\mathbb{R}^{n_{0}},\mathbb{R}^{n_{k}})$ the space of continuous functions
that can be described by a network with the same architecture as $f$. As
described in [JGH18] there is a realization map
$\Phi:\mathcal{W}\to\mathcal{F}$ mapping weights $W\in\mathcal{W}$ to the
associated function $f\in\mathcal{F}$. $\Phi$ arises because there are
generally multiple sets of weights that yield the same function. We will show
that $\Phi$ is invariant with respect to an action of the intertwiner groups
on $\mathcal{W}$ so that intertwiner groups form a set of “built-in” weight
space symmetries of $f$. This result, which encompasses phenomena including
permutation symmetries of hidden neurons, is well known in many particular
cases (e.g., [GBC16, §8.2.2], [Bre+19, §3], [FB17, §2], [Men+19, §3], [RK20,
§3, A]). From Proposition 3.4 we can also derive corollaries regarding
symmetries of the loss landscape — these are included in section E.6.

######  Proposition 3.4.

Suppose $A_{i}\in G_{\sigma_{n_{i}}}$ for $1\leq i\leq k-1$, and let

$W^{\prime}=(A_{1}W_{1},A_{1}b_{1},A_{2}W_{2}\phi_{\sigma}(A_{1}^{-1}),A_{2}b_{2},\dots,W_{k}\phi_{\sigma}(A_{k-1}^{-1}),b_{k})$

Then, as functions, for each $m$

$f_{\leq m}(x,W^{\prime})=\phi_{\sigma}(A_{m})\circ f_{\leq m}(x,W)\text{ and
}f_{>m}(x,W^{\prime})=f_{>m}(x,W)\circ\phi_{\sigma}(A_{m})^{-1},$ (3.5)

In particular, $f(x,W^{\prime})=f(x,W)$ for all $x\in\mathbb{R}^{n_{0}}$.
Equivalently, we have $\Phi(W^{\prime})=\Phi(W)\in\mathcal{F}$.

######  Remark 3.6.

We will show in appendix E that the this theorem no longer holds if the
architecture of $f$ contains residual connections, and that it fails most
dramatically when the layer $m$ occurs inside a residual block. We see
empirical evidence consistent with this failure in figs. 11, 2 and 8 below.

##  4 Intertwining group symmetries and model stitching

In this section we provide evidence that some of the differences between
distinct model’s internal representations can be explained in terms of
symmetries encoded by intertwiner groups. We do this using the stitching
framework from [BNB21, Csi+21]. We start by reviewing the concept of network
stitching.

Suppose $f,\tilde{f}$ are two networks as in section 3, with weights $W$,
$\tilde{W}$ respectively. For any $1\leq l\leq k-1$ we may form a stitched
network $S(f,\tilde{f},l,\varphi):\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{k}}$
defined in the notation of section 3 by
$S(f,\tilde{f},l,\varphi)=\tilde{f}_{>l}\circ\varphi\circ f_{\leq i}$ – here
$\varphi:\mathbb{R}^{n_{l}}\to\mathbb{R}^{n_{l}}$ is a stitching layer. In a
typical stitching experiment one freezes the weights of networks $f$ and
$\tilde{f}$ respectively where $f$ and $\tilde{f}$ were trained from different
initializations, constrains $\varphi$ to some simple function class
$\mathcal{S}$ (e.g., affine maps in [BNB21]), and trains
$S(f,\tilde{f},l,\varphi)$ to optimize $\varphi$ alone. The final validation
accuracy $\operatorname{Acc}S(f,\tilde{f},l,\varphi)$ of
$S(f,\tilde{f},l,\varphi)$ is then considered a measure of similarity (or lack
therof) of the internal representations of $f$ and $\tilde{f}$ in
$\mathbb{R}^{n_{l}}$ — in this framework the situation

$\operatorname{Acc}S(f,\tilde{f},l,\varphi)\approx\operatorname{Acc}f,\operatorname{Acc}\tilde{f}$
(4.1)

corresponds to high similarity since the hidden representations of model $f$
and $\tilde{f}$ could be related by a transformation $\mathcal{S}$.

Recall that even though the networks $f(W)$ and $f(W^{\prime})$ may be _equal
as functions_ , their hidden representations need not be the same (an example
of this is given in appendix C). Our next result shows that in the case where
$f$ and $\tilde{f}$ do only differ up to an element of $G_{\sigma_{n_{l}}}$,
eq. 4.1 is achievable even when the stitching function class $\mathcal{S}$ is
restricted down to elements of $G_{\sigma_{n_{l}}}$ or
$\phi_{\sigma}(G_{\sigma_{n_{l}}})$ (see definition 3.2).

######  Theorem 4.2.

Suppose
$\tilde{W}=(A_{1}W_{1},A_{1}b_{1},A_{2}W_{2}\phi_{\sigma}(A_{1}^{-1}),A_{2}b_{2},\dots,W_{k}\phi_{\sigma}(A_{k}^{-1}),b_{k})$
where $A_{i}\in G_{\sigma_{n_{i}}}$ for all $i$. Then eq. 4.1 is achievable
with equality _if_ the stitching function class $\mathcal{S}$ containing
$\varphi$ contains $\phi_{\sigma}(G_{\sigma_{n_{l}}})$.

Motivated by theorem 4.2, we attempt to stitch various networks at
$\operatorname{ReLU}$ activation layers using the group
$G_{\operatorname{ReLU}}$ described in Figure 4. Every matrix $A\in
G_{\operatorname{ReLU}}$ can be written as $PD$, where $P$ is a permutation
matrix and $D$ is diagonal with positive diagonal entries — hence optimization
over $G_{\operatorname{ReLU}}$ requires optimizing over permutation matrices.
We use the well-known convex relaxation of permutation matrices to doubly
stochastic matrices. See Section D.1 in the Appendix for details related to
our optimization procedure.

Figure 1 gives the difference between the average test error of Myrtle CNN
[Pag18] networks 111This is a simple 5-layer CNN, with no residual
connections; we describe its architecture and training hyperparameters in
further detail in appendix D. $f$ and $\tilde{f}$ and the network
$S(f,\tilde{f},l,\varphi)$,

$\text{Avg}(\text{Acc}(f),\text{Acc}(\tilde{f}))-\text{Acc}(S(f,\tilde{f},l,\varphi))$
(4.3)

where $S(f,\tilde{f},\varphi)$ was stitched together at layer $l$ via a
stitching transformations $\varphi$ that was either optimized over all affine
transformations, reduced rank affine transformations as in [Csi+21] or
transformations restricted to $G_{\operatorname{ReLU}}$. We consider only the
$\operatorname{ReLU}$ activation layers, as these are the only layers where
the theory of section 3 applies, and we only act on the channel tensor
dimension — in practice, this is accomplished by means of 1-by-1 convolution
operations. In particular, with $G_{\operatorname{ReLU}}$ we are _only
permuting and scaling channels_. Lower values indicate that the stitching
layer was sufficient to translate between the internal representation of $f$
at layer $l$ and the internal representation of $\tilde{f}$.

We find that when we are allowed to learn a stitching layer over arbitrary
affine transformations of channels, we can nearly achieve the accuracy of the
original models. When we are only allow to optimize over
$G_{\operatorname{ReLU}}$ there is an appreciable increase in test error
difference (consistent with findings in [Li+15, Wan+18, Csi+21] discussed in
section 2, and also consistent with observations that hidden features of
neural networks exhibit distributed representations and polysemanticism
[Ola+20]). Nonetheless, that $S(f,\tilde{f},l,\varphi)$ is able get within
less than $10\%$ of the accuracy of $f$ and $\tilde{f}$ in all but one layer
suggests that elements of $G_{\operatorname{ReLU}}$ can account for a
substantial amount of the variation in the internal representations of
independently trained networks. We include the reduced rank transformations as
the dimension of their parameter spaces is greater than that of
$G_{\operatorname{ReLU}}$, and yet they incur significantly higher stitching
penalties. If $n_{l}$ is the number of channels, we have $\dim
G_{\operatorname{ReLU}_{n_{l}}}=n_{l}$ whereas the dimension of rank $r$
transformations is $2n_{l}\cdot r-r^{2}$ (hence greater than $\dim
G_{\operatorname{ReLU}_{n_{l}}}$ even for $r=1$). Finally, the stitching
penalties incurred when using any layer other than 1-by-1 convolution with a
rank 1 matrix all follow similar general patterns: they increase up to the
third activation layer, then decrease at the final activation layer.

Further stitching results on the ResNet20 architecture can be found in section
D.2. This includes results where we modify the architecture to have LeakyReLU
activation functions, vary the negative slope of the LeakyReLU, and find
similar stitching penalties up to but not including a slope of 1, providing
further evidence of the importance of the intertwiner group.

##  5 Dissimilarity metrics for the intertwiner group of $\operatorname{ReLU}$

Stitching penalties can be viewed as task oriented measures of hidden feature
dissimilarity. From a different perspective, we can consider raw statistical
measures of hidden feature dissimilarity. In the design of measures of
dissimilarity, a crucial choice is the group of transformations under which
the dissimilarity measure is invariant. For example, Centered Kernel Alignment
($\operatorname{CKA}$) [Kor+19] is invariant with respect to orthogonal
transformation and isotropic scaling. We ask for a statistical dissimilarity
metric $\mu$ on datasets $X,Y\in\mathbb{R}^{N\times d}$ with the properties
that (0) $0\leq\mu(X,Y)\leq 1$, (i) (_$G_{\operatorname{ReLU}}$ -Invariance_)
If $A,B\in G_{\operatorname{ReLU}_{d}}$ and $v,w\in\mathbb{R}^{d}$ then
$\mu(XA+\mathbf{1}v^{T},YB+\mathbf{1}w^{T})=\mu(X,Y)$, and (ii) (_Alignment
Property_) $\mu(X,Y)=1$ if $(\ast)$ $Y=XA+\mathbf{1}v^{T}\text{ for some }A\in
G_{\operatorname{ReLU}_{d}},v\in\mathbb{R}^{d}$. To motivate this question, we
note that given such a metric $\mu$, one can detect if $X$ and $Y$ do _not_
differ by an element of $G_{\operatorname{ReLU}}$ by checking if $\mu(X,Y)<1$.
Our basic tool for ensuring (i) is the next lemma.

######  Lemma 5.1.

Suppose $\mu(XA,YB)=\mu(X,Y)$ if $A,B$ are _either_ positive diagonal matrices
or permutation matrices. Then, (i) holds.

In effect, this allows us to divide the columns of $X$ and $Y$ by their norms
to achieve invariance to the action of positive diagonal matrices and then
apply dissimilarity metrics for the permutation group such as those presented
in [Wil+21]. Ensuring (ii) seems to require case-by-case analysis to determine
an appropriate normalization constant.

######  Definition 5.2 ($G_{\operatorname{ReLU}}$-Procrustes).

Let $D_{X}=\operatorname{diag}(\lvert X_{[:,i]}\rvert)$ and
$D_{Y}=\operatorname{diag}(\lvert Y_{[:,i]}\rvert)$. Assuming these are
invertible, let $\tilde{X}=XD_{X}^{-1}$ and $\tilde{Y}=YD_{Y}^{-1}$. Let
$\delta$ be the permutation Procrustes distance between $\tilde{X},\tilde{Y}$,
defined by

$\delta:=\min_{P\in\Sigma_{d}}\lvert\tilde{X}-\tilde{Y}P\rvert$

(as pointed out in [Wil+21] this can be computed via the linear sum assignment
problem). Then the $G_{\operatorname{ReLU}}$-Procrustes distance is

$\mu_{\text{Procrustes}}(X,Y):=1-\frac{\delta}{2\sqrt{d}}.$

The factor of $2\sqrt{d}$ ensures this lies in $[0,1]$, and equals $1$ if (and
only if) the condition $\ast$ of (ii) holds.

| layer 3 | layer 6 | layer 10 | layer 14
---|---|---|---|---
$G_{\operatorname{ReLU}}$ | 0.645 $\pm$ 0.017 | 0.521 $\pm$ 0.008 | 0.447 $\pm$ 0.003 | 0.483 $\pm$ 0.002
Orthogonal | 0.810 $\pm$ 0.006 | 0.662 $\pm$ 0.004 | 0.530 $\pm$ 0.003 | 0.601 $\pm$ 0.001
Figure 5: $\mu_{\text{Procrustes}}$ and orthogonal Procrustes similarities for
two independently initialized Myrtle CNNs trained on CIFAR10. Confidence
intervals correspond to 5 independent runs of the experiment.

We apply $G_{\operatorname{ReLU}}$-Procrustes and orthogonal Procrustes
similarities to $4$ different hidden representations from Myrtle CNNs in fig.
5 and many more layers of ResNet20s in fig. 11, all trained on CIFAR10
[Kri09]. In keeping with the discussion of section 4, we only consider
permutations or orthogonal transformations of channels (for details on how
this is implemented we refer to section D.3). We see that distinct
representations register less similarity in terms of
$G_{\operatorname{ReLU}}$-Procrustes than they do in terms of orthogonal
Procrustes. This makes sense as similarity up to
$G_{\operatorname{ReLU}}$-transformation requires a greater degree of absolute
similarity between representations than is required of similarity up to
orthogonal transformation (the latter being a higher-dimensional group
containing all of the permutations in $G_{\operatorname{ReLU}}$). Otherwise
patterns in $G_{\operatorname{ReLU}}$-Procrustes similaritiy largely follow
those of $G_{\operatorname{ReLU}}$-orthogonal, with similarity between
representations decreasing as one progresses through the network, only to
increase again in the last layer. This correlates with the stitching penalties
of fig. 1, which increase with depth only to decrease in the last layer.

######  Definition 5.3 ($G_{\operatorname{ReLU}}$-CKA).

Assume that $X$ and $Y$ are data matrices that have been centered by
subtracting means of rows: $X\leftarrow X-\mathbf{1}\mathbf{1}^{T}X$ and
$Y\leftarrow Y-\mathbf{1}\mathbf{1}^{T}Y$. Let $\tilde{X}=XD_{X}^{-1}\text{
and }\tilde{Y}=YD_{Y}^{-1}$. Let $\tilde{x}_{1},\dots,\tilde{x}_{N}$ be the
rows of $X$, and similarly for $Y$. Form the matrices $K,L\in\mathbb{R}_{\geq
0}^{N\times N}$ defined by $K_{ij}=\max(\tilde{x}_{i}\odot\tilde{x}_{j})$ and
$L_{ij}=\max(\tilde{y}_{i}\odot\tilde{y}_{j})$ where $\odot$ is the Hadamard
product. Then the $G_{\operatorname{ReLU}}$-CKA for $X$ and $Y$ is defined as:

$\mu_{\text{CKA}}(X,Y):=\frac{\mathrm{HSIC}_{1}(K,L)}{\sqrt{\mathrm{HSIC}_{1}(K,K)}\sqrt{\mathrm{HSIC}_{1}(L,L)}}.$
(5.4)

where $\mathrm{HSIC}_{1}$ is the unbiased form of the Hilbert-Schmidt
independence criterion of [NRK21, eq. 3].

Symmetry of the $\max$ function ensures (i), the Cauchy-Schwarz inequality
ensures $\mu_{\text{CKA}}(X,Y)\in[0,1]$, and we claim that
$\mu_{\text{CKA}}(X,Y)=1$ if the condition $\ast$ of (ii) is met. We do not
claim ‘if and only if’, however we point out the following in lemma E.25: if
$A$ is a matrix such that $\max(Ax_{1}\odot Ax_{2})=\max(x_{1}\odot x_{2})$
for all $x_{1},x_{2}\in\mathbb{R}^{d}$, then $A$ is of the form $PD$ where $P$
is a permutation matrix and $D$ is diagonal with diagonal entries in $\\{\pm
1\\}$.

As with CKA [Kor+19], this metric makes sense even if $X,Y$ are datasets in
$\mathbb{R}^{d},\mathbb{R}^{d^{\prime}}$ respectively with $d\neq d^{\prime}$.
Results for a pair of Myrtle CNNs independently trained on CIFAR10, as well as
standard orthogonal CKA for comparison, are shown in fig. 6. Analogous results
for ResNet20s are shown in fig. 2. We find that $G_{\operatorname{ReLU}}$-CKA
respects basic trends found in their orthogonal counterparts: model layers at
the same depth are more similar, early layers are highly similar, and the
metric surfaces the block structure of the ResNet in fig. 2: layers inside
residual blocks are less similar than those at residual connections. One
notable difference for $G_{\operatorname{ReLU}}$-CKA in fig. 2 is that the
similarity difference between early and later layers in the orthogonal CKA
(discussed for ResNets in [Rag+21]) shown in (b) is less pronounced in (a),
and in fact later layers are found to be less similar between runs. We found
similar results for stitching in fig. 1.

(a)

(b)

Figure 6: $G_{\operatorname{ReLU}}$-CKA and orthogonal CKA for two
independently initialized Myrtle CNNs trained on CIFAR10 (results averaged
over 5 independent runs of the experiment).

##  6 Interpretability of the coordinate basis

In this section we explore the confluence of model interpretability and
intertwiner symmetries using network dissection from [Bau+17]. Network
dissection measures alignment between the individual neurons of a hidden layer
and single, pre-defined concepts. The Broden concept dataset, compiled by Bau
et al., contains pixel-level annotations for hierarchical concepts including
colors, textures, objects, and scenes. For every channel activation, network
dissection assesses the binary segmentation performance with every visual
concept from Broden. The method first computes the channel activation for
every Broden image. The distribution of the activations for the channel is
used to binarize the activation (where we threshold by the top $0.5\%$ of all
activations for the channel) to define a segmentation mask for the channel
activation which is interpolated to the size of the input image. If the
Intersection over Union (IoU) of the activation segmentation mask and a
concept mask is high enough (namely where $\text{IoU}>0.04$), network
dissection labels the activation an interpretable detector for the concept.

We use an experiment from [Bau+17] to compare the axis-aligned
interpretability of hidden activation layers with and without an activation
function. Bau et al. compares the interpretability of individual neurons,
measured via network dissection, with that of random orthogonal rotations of
neurons. We likewise rotate the hidden layer representations and then measure
their interpretability. Using the methodology from [Dia05], we define a random
orthogonal transform $Q$ drawn uniformly from $SO(n)$ by using Gram-Schmidt to
orthonormalize the normally-distributed $QR=A\in\mathbb{R}^{n^{2}}$. Like in
[Bau+17], we also consider smaller rotations $Q^{\alpha}\in SO(n)$ where
$0\leq\alpha\leq 1$, where $\alpha$ is chosen to form a minimal geodesic
gradually rotating from I to Q. [Bau+17] found that the number of
interpretable units decreased away from the activation basis as $\alpha$
increased for layer5 of an AlexNet.

We compare three models trained on ImageNet: a normal ResNet-50, a modified
ResNet-50 where we remove the ReLU on the residual outputs (training details
in section F.1), and a ConvNeXt [Liu+22] analog of the ResNet-50, which also
does not have an activation function before the final residual output. We give
results in fig. 3, and provide sample unit detection outputs and full concept
labels for the figures in appendix F. As was shown in [Bau+17],
interpretability decreases as we rotate away from the axis for the normal
ResNet-50. On the other hand, with no activation function and therefore no
canonical basis, interpretability does not drop with rotation for the modified
ResNet-50 and the ConvNeXt. Interestingly, while the number of interpretable
units remains constant for the residual output of the modified ResNet-50, for
the ConvNeXt model it actually increases. We find similar results, where the
number of interpretable units increase with rotation, for the convolutional
layer inside the residual block for the modified ResNet-50 in fig. 15.

##  7 Limitations

Our theoretical analysis does not account for standard regularization
techniques that are known to have symmetry-breaking effects (for example
weight decay reduces scaling symmetry). More generally, we do not account for
any implicit regularization of our training algorithms. As illustrated in
figs. 1 and 8, stitching with intertwiner groups appears to have significantly
more architecture-dependent behaviour than stitching with arbitrary affine
transformations (however, since different architectures have different
symmetries this is to be expected). Our empirical tests of the dissimilarity
metrics in section 5 are limited to what [Kor+19] terms “sanity tests”; in
particular we did not perform the specificity, sensitivity and quality tests
of [DDS21].

##  8 Conclusion

In this paper we describe groups of symmetries that arise from the nonlinear
layers of a neural network. We calculate these symmetry groups for a number of
different types of nonlinearities, and explore their fundamental properties
and connection to weight space symmetries. Next, we provide evidence that
these symmetries induce symmetries in a network’s internal representation of
the data that it processes, showing that previous work on the internal
representations of neural networks can be naturally adapted to incorporate
awareness of the intertwiner groups that we identify. Finally, in the special
case where the network in question has ReLU nonlinearities, we find
experimental evidence that intertwiner groups justify the special place of the
activation basis within interpretable AI research.

## References

  * [Bau+17] David Bau et al.  “Network Dissection: Quantifying Interpretability of Deep Visual Representations”  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 3319–3327
  * [BMC15] Vijay Badrinarayanan, Bamdev Mishra and R. Cipolla  “Understanding Symmetries in Deep Networks”  In _ArXiv_ , 2015
  * [BNB21] Yamini Bansal, Preetum Nakkiran and Boaz Barak  “Revisiting Model Stitching to Compare Neural Representations”  In _NeurIPS_ , 2021
  * [Bre+19] Johanni Brea, Berfin Simsek, Bernd Illing and Wulfram Gerstner  “Weight-Space Symmetry in Deep Networks Gives Rise to Permutation Saddles, Connected by Equal-Loss Valleys across the Loss Landscape”, 2019  arXiv: http://arxiv.org/abs/1907.02911
  * [Csi+21] Adrián Csiszárik et al.  “Similarity and Matching of Neural Network Representations”  In _Advances in Neural Information Processing Systems_ , 2021  URL: https://openreview.net/forum?id=aedFIIRRfXr
  * [DDS21] Frances Ding, Jean-Stanislas Denain and J. Steinhardt  “Grounding Representation Similarity with Statistical Testing”  In _ArXiv_ , 2021
  * [DDS21a] Frances Ding, Jean-Stanislas Denain and Jacob Steinhardt  “Grounding Representation Similarity Through Statistical Testing”  In _Advances in Neural Information Processing Systems_ , 2021  URL: https://openreview.net/forum?id=_kwj6V53ZqB
  * [Den+09] Jia Deng et al.  “Imagenet: A large-scale hierarchical image database”  In _2009 IEEE conference on computer vision and pattern recognition_ , 2009, pp. 248–255  Ieee
  * [Dia05] Persi Diaconis  “What is a random matrix”  In _Notices of the AMS_ 52.11, 2005, pp. 1348–1349
  * [Elh+21] N Elhage et al.  “A mathematical framework for transformer circuits”, 2021
  * [Erh+09] Dumitru Erhan, Yoshua Bengio, Aaron Courville and Pascal Vincent  “Visualizing higher-layer features of a deep network”  In _University of Montreal_ 1341.3, 2009, pp. 1
  * [FB17] C. Freeman and Joan Bruna  “Topology and Geometry of Half-Rectified Network Optimization”  In _ArXiv_ abs/1611.01540, 2017
  * [Fog+13] Fajwel Fogel, Rodolphe Jenatton, Francis R. Bach and Alexandre d’Aspremont  “Convex Relaxations for Permutation Problems”  In _SIAM J. Matrix Anal. Appl._ , 2013
  * [GBC16] Ian Goodfellow, Yoshua Bengio and Aaron Courville  “Deep Learning” http://www.deeplearningbook.org MIT Press, 2016
  * [IS15] S. Ioffe and Christian Szegedy  “Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift”  In _ICML_ , 2015
  * [JGH18] Arthur Jacot, Franck Gabriel and Clément Hongler  “Neural tangent kernel: convergence and generalization in neural networks (invited paper)”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2018
  * [Kor+19] Simon Kornblith, Mohammad Norouzi, Honglak Lee and Geoffrey E. Hinton  “Similarity of Neural Network Representations Revisited”  In _ICML_ , 2019
  * [Kri09] Alex Krizhevsky  “Learning multiple layers of features from tiny images”, 2009
  * [KTB19] J. Kileel, Matthew Trager and Joan Bruna  “On the Expressive Power of Deep Polynomial Neural Networks”  In _NeurIPS_ , 2019
  * [Kun+21] Daniel Kunin et al.  “Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics”, 2021  arXiv: http://arxiv.org/abs/2012.04728
  * [Lec+22] Guillaume Leclerc et al.  “ffcv” commit 849, https://github.com/libffcv/ffcv/, 2022
  * [Li+15] Yixuan Li et al.  “Convergent Learning: Do Different Neural Networks Learn the Same Representations?”  In _FE@NIPS_ , 2015
  * [Liu+22] Zhuang Liu et al.  “A ConvNet for the 2020s”  In _arXiv preprint arXiv:2201.03545_ , 2022
  * [LV15] Karel Lenc and A. Vedaldi  “Understanding Image Representations by Measuring Their Equivariance and Equivalence”  In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015  DOI: 10.1109/CVPR.2015.7298701
  * [LW14] Cong Han Lim and Stephen J. Wright  “Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems”  In _NIPS_ , 2014
  * [Men+18] Gonzalo Mena, David Belanger, Scott Linderman and Jasper Snoek  “Learning Latent Permutations with Gumbel-Sinkhorn Networks”  In _International Conference on Learning Representations_ , 2018  URL: https://openreview.net/forum?id=Byt3oJ-0W
  * [Men+19] Qi Meng et al.  “G-SGD: Optimizing ReLU Neural Networks in Its Positively Scale-Invariant Space”  In _ICLR_ , 2019
  * [MR10] Sébastien Marcel and Yann Rodriguez  “Torchvision the machine-vision package of torch”  In _Proceedings of the 18th ACM international conference on Multimedia_ , 2010, pp. 1485–1488
  * [Na+19] Seil Na, Yo Joong Choe, Dong-Hyun Lee and Gunhee Kim  “Discovery of natural language concepts in individual units of cnns”  In _arXiv preprint arXiv:1902.07249_ , 2019
  * [NH10] Vinod Nair and Geoffrey E. Hinton  “Rectified Linear Units Improve Restricted Boltzmann Machines”  In _ICML_ , 2010
  * [Noe18] E Noether  “Invariante Variationsprobleme”  In _Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen_ , 1918, pp. 235–257
  * [NRK21] Thao Nguyen, Maithra Raghu and Simon Kornblith  “Do Wide and Deep Networks Learn the Same Things? Uncovering How Neural Network Representations Vary with Width and Depth”  In _International Conference on Learning Representations_ , 2021  URL: https://openreview.net/forum?id=KJNcAkY8tY4
  * [Ola+20] Chris Olah et al.  “Zoom in: An introduction to circuits”  In _Distill_ 5.3, 2020, pp. e00024–001
  * [Pag18] David Page  “How to Train Your ResNet”, 2018  Myrtle  URL: https://myrtle.ai/learn/how-to-train-your-resnet/
  * [Pas+19] Adam Paszke et al.  “PyTorch: An Imperative Style, High-Performance Deep Learning Library”  In _Advances in Neural Information Processing Systems 32_ Curran Associates, Inc., 2019, pp. 8024–8035  URL: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
  * [PE20] Sebastian Prillo and Julian Martin Eisenschlos  “SoftSort: A Continuous Relaxation for the argsort Operator”  In _ICML_ , 2020
  * [Rag+17] M. Raghu, J. Gilmer, J. Yosinski and J. Sohl-Dickstein  “SVCCA: Singular Vector Canonical Correlation Analysis for Deep Learning Dynamics and Interpretability”  In _NIPS_ , 2017
  * [Rag+21] Maithra Raghu et al.  “Do vision transformers see like convolutional neural networks?”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [RK20] D. Rolnick and Konrad Paul Kording  “Reverse-Engineering Deep ReLU Networks”  In _ICML_ , 2020
  * [Rud76] Walter Rudin  “Principles of Mathematical Analysis”  McGraw-Hill, 1976  GOOGLEBOOKS: kwqzPAAACAAJ
  * [Ser77] Jean-Pierre Serre  “Linear representations of finite groups”  Springer, 1977
  * [Sin64] Richard Sinkhorn  “A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices”  In _The Annals of Mathematical Statistics_ 35.2 Institute of Mathematical Statistics, 1964, pp. 876–879  DOI: 10.1214/aoms/1177703591
  * [Sze+14] Christian Szegedy et al.  “Intriguing properties of neural networks”  In _CoRR_ abs/1312.6199, 2014
  * [Vir+20] Pauli Virtanen et al.  “SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python”  In _Nature Methods_ 17, 2020, pp. 261–272  DOI: 10.1038/s41592-019-0686-2
  * [Wan+18] Liwei Wang et al.  “Towards Understanding Learning Representations: To What Extent Do Different Neural Networks Learn the Same Representation”  In _NeurIPS_ , 2018
  * [Wig19] Ross Wightman  “PyTorch Image Models”  In _GitHub repository_ GitHub, https://github.com/rwightman/pytorch-image-models, 2019  DOI: 10.5281/zenodo.4414861
  * [Wil+21] Alex H. Williams, Erin Marie O’Mara Kunz, Simon Kornblith and Scott W. Linderman  “Generalized Shape Metrics on Neural Representations”  In _NeurIPS_ , 2021
  * [Yi+19] Mingyang Yi et al.  “Positively Scale-Invariant Flatness of ReLU Neural Networks”  In _ArXiv_ , 2019
  * [Yos+15] Jason Yosinski et al.  “Understanding Neural Networks Through Deep Visualization”  In _Deep Learning Workshop, International Conference on Machine Learning (ICML)_ , 2015
  * [ZF14] Matthew D Zeiler and Rob Fergus  “Visualizing and understanding convolutional networks”  In _European conference on computer vision_ , 2014, pp. 818–833  Springer
  * [Zho+15] Bolei Zhou et al.  “Object Detectors Emerge in Deep Scene CNNs.”  In _ICLR_ , 2015  URL: http://arxiv.org/abs/1412.6856

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 7.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]
This paper is largely focused on the mathematical aspects of deep learning so
we do not think there are any immediate negative societal impact to the
methods described. From a broader perspective though, we see this work helping
to create a more principled groundwork for many explainable AI techniques. We
explain why this could have positive societal impacts in Section A.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] All proofs
can be found in appendix E.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [TODO]
We are in the process of making code publicly available.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]  See appendix D.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]  See appendix
D — while we did not keep precise track of CPU/GPU hours, we do specify the
hardware used.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [Yes] See Section G.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Societal Impact

Though deep learning models are in the process of being deployed for safety
critical applications, we still have very little understanding of the
structure and evolution of their internal representations. In this paper we
discuss one aspect of these representations. We hope that by better
illuminating the inner workings of these networks, we will be a small part of
the larger effort to make deep learning more understandable, reliable, and
fair.

##  Appendix B Code availability

We are in the process of releasing code — once available it will be located at
https://github.com/TvfBaRoZCKqJ/FjEsAbqqjdeY.

##  Appendix C Examples

We first give an example of two networks with distinct weights which are
functionally equivalent. Let $f$ be a 2 layer network with
$\operatorname{ReLU}$ activations and weight matrices

$W_{1}=\begin{bmatrix}1&0\\\ 0&2\end{bmatrix}\quad\text{and}\quad
W_{2}=\begin{bmatrix}3&0\\\ 0&1\end{bmatrix}$

(and biases = 0). Let $\tilde{f}$ be a network with the same architecture, but
with weights

$W_{1}=\begin{bmatrix}0&2\\\ 1&0\end{bmatrix}\quad\text{and}\quad
W_{2}=\begin{bmatrix}0&3\\\ 1&0\end{bmatrix}.$

Then one can verify that $\tilde{f}$(x) = f(x) for all $x\in\mathbb{R}$, but
that the weights of $f$ and $\tilde{f}$ differ.

We also work through a small example of $\phi_{\sigma_{n}}$ where $n=2$.
Assume that $\sigma$ is the ReLU nonlinearity. Then,

$A=\begin{bmatrix}0&2\\\ 1&0\end{bmatrix}$

belongs to $G_{\sigma_{2}}$, and we can compute directly that

$\operatorname{ReLU}\circ\begin{bmatrix}0&1\\\
2&0\end{bmatrix}\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}=\begin{bmatrix}\operatorname{ReLU}(x_{2})\\\
\operatorname{ReLU}(2x_{1})\end{bmatrix}=\begin{bmatrix}\operatorname{ReLU}(x_{2})\\\
2\operatorname{ReLU}(x_{1})\end{bmatrix},$

where in the last equality we used the fact that
$\operatorname{ReLU}(ax)=a\operatorname{ReLU}(x)$ when $a$ is positive. On the
other hand,

$\begin{bmatrix}0&1\\\
2&0\end{bmatrix}\circ\operatorname{ReLU}(\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix})=\begin{bmatrix}0&1\\\
2&0\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(x_{1})\\\
\operatorname{ReLU}(x_{2})\end{bmatrix}=\begin{bmatrix}\operatorname{ReLU}(x_{2})\\\
2\operatorname{ReLU}(x_{1})\end{bmatrix}.$

##  Appendix D Experimental Details

In this section we provide additional experimental results, as well as
implementation details for the purposes of reproducibility. All experiments
were run on an Nvidia GPUs using PyTorch [Pas+19].

####  D.0.1 A “sanity test” for intertwiners

We include a simple experiment related to section 3. In this experiment, we
take an even simpler Myrtle CNN (with no batch normalization) trained for 50
epochs, fix a _pre-activation layer_ $l$, and apply a transformation $A$ to
the weights $W_{l}$ and biases $b_{l}$ to obtain $AW_{l}$ and $Ab_{l}$ (again,
we only act on channels, hence in practice this is implemented by an auxiliary
1-by-1 convolution layer). We consider 2 choices of $A$:

  * •

A random element of $G_{\operatorname{ReLU}}$ where we generate $P$ via a
random permutation and we generate $D$ via a diagonal matrix with random
lognormal entries (normalized to ensure that the expected value of $D$ is the
identity).

  * •

A random orthogonal matrix, generated using the QR decomposition as in section
6.

Next, we freeze layers up to and including $l$ and finetune the later layers
for another 50 epochs. Based on the theory in section 3, when $A\in
G_{\operatorname{ReLU}}$ the network should be able to recover reasonable
performance even with the transformed features — for example, by updating
$W_{l+1}$ to $W_{l+1}\phi_{\sigma}(A)^{-1}$. On the other hand, with
probability 1 there is no matrix $B$ such that updating $W_{l+1}$ to
$W_{l+1}B$ counteracts the effect of an orthogonal rotation $A$ on all
possible input. We see that this is indeed the case in fig. 7: transforming by
$A\in G_{\operatorname{ReLU}}$ rather a random orthogonal matrix results in
significantly higher fine-tuned accuracy.

Figure 7: “Rotation penalties” for a simple Myrtle CNN, measured in baseline
validation accuracy (before transforming layer $l$ minus validation accuracy
after fine-tuning later layers. Baseline accuracy was $\approx 81\%$. Results
averaged over 5 independent runs of the experiment.

###  D.1 Stitching Experiments

We began by training 5 pairs of independently initialized models (hence 10
independently initialized models total) for each of the following
architectures:

  1. (i)

Myrtle CNN: a simple 5-layer feed-forward CNN with batch normalization.

  2. (ii)

ResNet20: a ResNet tailored to the CIFAR10 dataset (numbers of channels are
$16,32,64$ respectively in the 3 residual blocks).

  3. (iii)

ResNet18: an ImageNet-style ResNet adapted to the input size of CIFAR10 — much
wider than the above (numbers of channels are $64,128,256$ respectively in the
3 residual blocks).

More detailed architecture schematics are included in figs. 22(a), 23(a) and
24(a).

All models were trained for 50 epochs using the Adam optimizer with PyTorch’s
default settings. We use a batch size of 32, initial learning rate $0.001$ and
4 evenly spaced learning rate drops with factor $0.5$. We augment data with
random resized cropping and left-right flips, and we save the weights with
best validation accuracy.

For stitching layers, we train for 20 epochs with batch size 32 and learning
rate $0.001$ (with no drops), however we use SGD with momentum 0.9 (we found
Adam interacted in complicated ways with the PGD algorithm described in
section D.1.1 below, even after following some helpful advice from the
Internet222https://datascience.stackexchange.com/questions/31709/adam-
optimizer-for-projected-gradient-descent). Augmentation is described in the
previous paragraph.

We parameterize reduced rank 1-by-1 convolutions as a composition of 2 1-by-1
convolutions, with
$\mathtt{in\\_channels,out\\_channels}=\mathtt{in\\_channels,rank}$ and
$\mathtt{rank,in\\_channels}$ respectively. In contrast to [BNB21] we omit
both batch norm and bias from stitching layers (to stick closely to the
statement of theorem 4.2).

####  D.1.1 Approximate Optimization over Permutation Matrices

By far the most complicated stitching layer is the one using
$G_{\operatorname{ReLU}}$, which we describe here. Recall that
$G_{\operatorname{ReLU}}$ is equal to the $n\times n$ matrices of the form
$PD$, where $P\in\Sigma_{n}$ is a permutation matrix and $D$ is a diagonal
matrix with positive entries We parameterize $D$ simply as
$D=\operatorname{diag}(\lambda_{i})$ where
$\lambda_{1},\dots,\lambda_{n_{l}}\in\mathbb{R}_{\geq 0}$ — we preserve non-
negativity during training by a projected gradient descent step
$D\leftarrow\operatorname{ReLU}(D)$. During stitching layer training, we
parameterize $P$ as a doubly stochastic matrix, that is, an element of the
Birkhoff polytope

$\mathcal{B}=\\{A=(a_{ij})\in\operatorname{Mat}_{n_{l},n_{l}}(\mathbb{R})\,|\,a_{ij}\geq
0\text{ for all }i,j,\mathbf{1}^{T}A=\mathbf{1}^{T}\text{ and
}A\mathbf{1}=\mathbf{1}\\}$

— after each gradient descent step we project $P$ back onto $\mathcal{B}$ by
the operation $P\leftarrow\operatorname{ReLU}(P)$ followed by
$P\leftarrow\mathrm{sink}(P)$, where “$\mathrm{sink}$” denotes Sinkhorn
iterations. These consist of $T$ iterations of

$A\leftarrow A\operatorname{diag}(\mathbf{1}^{T}A)^{-1}\text{ followed by
}A\leftarrow\operatorname{diag}(A\mathbf{1})^{-1}A$

(it is a theorem of Sinkhorn that this sequence converges to a doubly
stochastic matrix of the form $DAE$ with $D,E$ positive diagonal matrices
[Sin64]). We use $T=16$ in all experiments (this choice drew on the work of
[Men+18]). In addition, we add a regularization term $-\alpha\lvert
P\rvert_{2}$ to the stitching objective, where $\alpha>0$ is a hyperparameter
(the motivation here is that permutation matrices are precisely the elements
of $\mathcal{B}$ with maximal $\ell_{2}$-norm). In all our experiments
$\alpha=0.1$.

At evaluation time, we threshold $P$ to an actual permutation matrix via the
Hungarian algorithm (specifically its implementation in
scipy.optimize.linear_sum_assignment [Vir+20]). This amounts to

$P_{\mathrm{eval}}=\max_{Q\in\Sigma_{n_{l}}}\operatorname{tr}(P_{\mathrm{train}}Q^{T})$

As stated above, we train for 20 epochs with batch size 32 and learning rate
$0.001$ (with no drops), using SGD with momentum 0.9. However, we allow the
permutation factor to get a “head start” by keeping $D$ fixed at the identity
$I$ for the first $10$ epochs. This may not be essential. More generally,
_there is no reason to assume any of our stitching hyperparameters (
$T,\alpha$, learning rate, head start etc.) are optimal as we did not perform
any thorough hyperparameter sweeps_.

Finally, before evaluating the stitched model on the CIFAR10 validation set,
we perform a no-gradient epoch _on the training data_ with stitching layer
$P_{\mathrm{eval}}$. This is critical as it allows the batch normalization
running means and variances in later layers to adapt to the thresholded
permutation matrix $P_{\mathrm{eval}}$; observe that if we omitted this step,
during evaluation the “batch normalization layers” would not even be
performing batch normalization per se, since their running statistics would be
computed from features produced by a layer $P_{\mathrm{train}}$ no longer in
use.

As an aside, we also experimented with the differeniable relaxation of
permutation matrices SoftSort [PE20]. Our final results were comparable,
however this method took far longer ($>10\times$) to optimize than the
Birkhoff polytope method. It is perhaps of interest that we used SoftSort on
permutations far larger than those of [PE20] (e.g., the 512 channels of late
layers of our Myrtle CNN). The next section (section D.1.2) contains some of
our technical findings.

We wish to aknowledge a couple articles, [Fog+13] and [LW14], that provided us
with useful backround on optimization over doubly stochastic matrices.

####  D.1.2 Stitching with SoftSort

We parameterized $D$ simply as $D=\operatorname{diag}(e^{\lambda_{i}})$ where
$\lambda_{1},\dots,\lambda_{n_{l}}\in\mathbb{R}$. During stitching layer
training, we parameterized $P$ using SoftSort [PE20], a continuous relaxation
of permutation matrices given by the formula

$P=\operatorname{SoftSort}(s,\tau):=\operatorname{softmax}\exp\big{(}-\frac{1}{\tau}(\operatorname{sort}(s)\mathbf{1}^{T}-\mathbf{1}s^{T})\big{)},\text{
where }s\in\mathbb{R}^{n_{l}},$

$\operatorname{sort}(s)$ denotes $s$ sorted in descending order, and
$\operatorname{softmax}$ is applied over rows. The parameter $\tau>0$ controls
$\operatorname{softmax}$ temperature, and we were only able to obtain
reasonable results when tuning it according to $\tau\approx 1/n_{l}$ . At
validation time, we threshold $P$ to an actual permutation matrix by applying
$\arg\max$ over rows as in [PE20].

###  D.2 Stitching and $G_{\operatorname{ReLU}}$-dissimilarity metrics for
ResNets

Here we include further results for ResNet20 and ResNet18 architectures.
Figure 8 and fig. 9 include results for full 1-by-1 convolution, reduced randk
1-by-1 convolution and $G_{\operatorname{ReLU}}$ 1-by-1 convolutions stitching
in the ResNet20 and ResNet18 architectures respectively. Note that in general,
layers inside residual blocks incur higher penalties, consisent with remark
3.6. This holds even in the full 1-by-1 convolution case, a finding that to
the best of our knowledge is new.

In the case of ResNet20 we also observe that the relative ranking of the
different stitching constraints tends to change inside of residual blocks:
whereas $G_{\operatorname{ReLU}}$ stitching consistently outperforms rank 1
(and sometimes rank 2) stitching outside residual blocks, it consistently
underperforms all strategies inside residual blocks. Lastly, we remark that
the ResNet20 is significantly narrower than the Myrtle CNN (channels are 16,
32, 64 vs. 64, 128, 256, see figs. 23(a) and 24(a)), and hence the low-rank
transformations account for a larger _proportion_ of the available total rank
(for example, in early layers of the ResNet20 rank 4 is
$0.25\cdot\mathrm{fullrank}$ whereas in the early layers of the Myrtle CNN
rank 4 is $0.0625\cdot\mathrm{fullrank}$). Heuristically, in the narrower
network low-rank transformations may suffice to align for a larger fraction of
the principal components of hidden features.

We also observe generally lower stitching penalties in the ResNet18 with the
exception of the penultimate inside-a-residual-block layer — we do not have a
satisfactory explanation for random chance performance at that layer. We also
remark that while the penalties in fig. 8 are significantly higher than those
in fig. 1, especially in later layers, we also saw significant dissimilarity
in fig. 2 (a), especially in later layers.

We also modify the ResNet20 to use the $\operatorname{LeakyReLU}$ activation
function and train models with different negative slopes $s$. Accuracy for two
independently trained models at different $\operatorname{LeakyReLU}$ given in
table 1. We perform $G_{\operatorname{ReLU}}$ stitching in fig. 8. Note that
for a negative slope $s=1$, the activation function is the identity. We find
the results difficult to interpret due to the significant decrease in CIFAR-10
accuracy for larger $s$. With this being said, unlike for $s<<1$, we note that
the stitching penalties for $s=1$ (and to a lesser extent, $s=0.9$) are mostly
constant throughout the layers of the network. This is most prominent for the
final two ResNet20 layers ($72$ and $75$), where the stitching penalty for
models with small $\operatorname{LeakyReLU}$ slopes is the lowest.

Figure 8: Full/reduced rank and $G_{\operatorname{ReLU}}$ 1-by-1 convolution
stitching penalties (4.3) for two independently initialized ResNet20s on
CIFAR-10. Confidence intervals were taken over 5 independent runs. Accuracy of
the independently initialized models was 89.6 $\pm$ 1.2 %. Layers marked with
‘*’ occur inside residual blocks (remark 3.6). Figure 9: Full/reduced rank and
$G_{\operatorname{ReLU}}$ 1-by-1 convolution stitching penalties (4.3) for two
independently initialized ResNet18s on CIFAR-10. Confidence intervals were
taken over 5 independent runs. Accuracy of the independently initialized
models was 91.0 $\pm$ 1.6 %. Layers marked with ‘*’ occur inside residual
blocks (remark 3.6). Rank 2 and 4 cases are omitted only since those
experiments did not return in time for submission (they could easily be
included in a revision). Table 1: ResNet20 with $\operatorname{LeakyReLU}$
CIFAR-10 accuracy $\operatorname{LeakyReLU}$ slope
---
| $1\mathrm{e}{-4}$ | $1\mathrm{e}{-3}$ | $1\mathrm{e}{-2}$ | 0.1 | 0.5 | 0.9 | 1.0
% acc. | $89.3\pm 0.2$ | $89.4\pm 0.2$ | $89.2\pm 0.2$ | $89.4\pm 0.1$ | $86.6\pm 0.1$ | $73.0\pm 0.2$ | $41.8\pm 0.1$
Figure 10: Stitching penalties (4.3) for independently initialized ResNet20s
on CIFAR-10, where respective ResNet20 models are trained with
$\operatorname{LeakyReLU}$ activation functions with different slopes.
Accuracy of the independently initialized models with different
$\operatorname{LeakyReLU}$ slopes is given in table 1.

Figure 11 contains $G_{\operatorname{ReLU}}$ and orthogonal Procrustes
dissimilarities for the ResNet20. The 2 metrics seem qualitatively quite
similar in this case. For the most part the same applies to the ResNet18 in
fig. 12, with the exception of layer 70 (penultimate inside-a-residual-block
layer), where we see high $G_{\operatorname{ReLU}}$ _similarity_ , in conflict
with both fig. 9 and fig. 13 below.

Figure 11: $G_{\operatorname{ReLU}}$ and orthogonal Procrustes dissimilarities
for two independently initialized ResNet20s trained on CIFAR10. Layers marked
with ‘*’ occur inside residual blocks (remark 3.6). Confidence intervals
correspond to 5 independent runs for the experiment. Figure 12:
$G_{\operatorname{ReLU}}$ and orthogonal Procrustes dissimilarities for two
independently initialized ResNet18s trained on CIFAR10. Layers marked with ‘*’
occur inside residual blocks (remark 3.6). Confidence intervals correspond to
5 independent runs for the experiment.

We include $G_{\operatorname{ReLU}}$ and orthogonal CKA dissimilarities for
the wider ResNet18 in fig. 13. For the most part the qualitative remarks on
fig. 2 apply here as well — note also the extreme dissimilarity in layer 70
(in both $G_{\operatorname{ReLU}}$ and orthogonal cases) consistent with fig.
9.

(a)

(b)

Figure 13: $G_{\operatorname{ReLU}}$-CKA and orthogonal CKA for two
independently initialized ResNet18s trained on CIFAR10. Layers marked with ‘*’
occur inside residual blocks (remark 3.6). Results averaged over 5 independent
runs of the experiment.

###  D.3 Implementing dissimilarity metrics

As mentioned in section 5, we aim to capture invariants to permuting and
scaling channels, but not spatial coordinates. This requires some care;
practically speaking it means we cannot simply flatten feature vectors.

In all cases we compute our metrics over the entire CIFAR10 validation set. In
particular, we do not require batched computations as in [NRK21].

####  D.3.1 Procrustes

As in [Wil+21, DDS21a]

$\min_{P\in\Sigma_{d}}\lvert\tilde{X}-\tilde{Y}P\rvert=\sqrt{\min_{P\in\Sigma_{d}}\lvert\tilde{X}-\tilde{Y}P\rvert^{2}}$

so it suffices to consider minimizing the Frobenius norm-squared, and
expanding as

$\lvert\tilde{X}-\tilde{Y}P\rvert^{2}=\lvert\tilde{X}\rvert^{2}+\lvert\tilde{Y}\rvert^{2}-2\operatorname{tr}(\tilde{X}^{T}\tilde{Y}P)$

we see that this is equivalent to _maximizing_
$\operatorname{tr}(\tilde{X}^{T}\tilde{Y}P)$. In our case $X,Y$ have shape
$(N,C,H,W)$ where $N$ is the size of the entire CIFAR10 validation set and
$C,H,W$ are the channels, height, and width at the given hidden layer
respectively. We want $P$ to be a $C\times C$ permutation matrix. Hence for
$\tilde{X}^{T}\tilde{Y}$ we compute the tensor dot product

$(\tilde{X}^{T}\tilde{Y})_{c,c^{\prime}}=\sum_{n,h,w}\tilde{X}_{n,c,h,w}\tilde{Y}_{n,c^{\prime},h,w}$
(D.1)

The same method is used for orthogonal Procrustes, where instead of
scipy.optimize.linear_sum_assignment we use the nuclear norm of eq. D.1 as in
[DDS21].

####  D.3.2 CKA

In this case for a set of hidden features $X$ of shape $(N,C,H,W)$ as above,
we first subtract the mean over all but the channel dimension:

$X_{n,c,h,w}\leftarrow
X_{n,c,h,w}-\frac{1}{NHW}\sum_{n^{\prime},h^{\prime},w^{\prime}}X_{n^{\prime},c,h^{\prime},w^{\prime}}$

and divide by the norms over all but the channel dimension:333In retrospect,
it would arguably make more sense to use standard deviation rather than
$\ell_{2}$ norm; however, for us the choice is irrelevant in the end since the
2 choices differ by a factor of $\sqrt{NHW}$ which gets cancelled in eq. 5.4.

$X_{n,c,h,w}\leftarrow\frac{X_{n,c,h,w}}{\sqrt{\sum_{n^{\prime},h^{\prime},w^{\prime}}X_{n^{\prime},c,h^{\prime},w^{\prime}}^{2}}}.$

Next, we compute a tensor dot product of $X$ with itself _over spatial
dimensions_ , to obtain the shape $(N,N,C)$ tensor

$J_{m,n,c}:=\sum_{h,w}X_{n,c,h,w}X_{n,c,h,w}$

and finally we apply $\max$ over the channel dimension to get

$K_{m,n}=\max_{c}J_{m,n,c}.$

######  Remark D.2.

It could be interesting to refrain from applying a dot product over spatial
dimensions, and thus measure not only similarity between hidden features of
different images, but similarity between hidden features of different images
_at certain locations_. However, the memory requirements would have been far
beyond our computational limits.

##  Appendix E Proofs

###  E.1 A proof of lemma 3.1, plus some abstractions thereof

###### Proof of lemma 3.1.

Since by definition $G_{\sigma_{n}}\subseteq GL_{n}(\mathbb{R})$, to prove
$G_{\sigma_{n}}$ is a subgroup it suffices to show that if $A_{1},A_{2}\in
G_{\sigma_{n}}$ then $A_{1}A_{2}^{-1}\in G_{\sigma_{n}}$. By hypotheses, there
are matrices $B_{1},B_{2}\in GL_{n}(\mathbb{R})$ so that

$\displaystyle\sigma_{n}\circ A_{1}$ $\displaystyle=B_{1}\circ\sigma_{n}$
(E.1) $\displaystyle\text{ and }\quad\sigma_{n}\circ A_{2}$
$\displaystyle=B_{2}\circ\sigma_{n}.$ (E.2)

Applying $A_{2}^{-1}$ on the right hand side of eq. E.1 gives

$\sigma_{n}\circ(A_{1}A_{2}^{-1})=B_{1}\circ\sigma_{n}\circ(A_{2}^{-1}).$
(E.3)

On the other hand, applying $A_{2}^{-1}$ on the right hand side of eq. E.2
gives $\sigma_{n}=B_{2}\circ\sigma_{n}\circ(A_{2}^{-1})$ and hence

$\sigma_{n}\circ(A_{2}^{-1})=B_{2}^{-1}\circ\sigma_{n}.$ (E.4)

Combining eqs. E.3 and E.4 we obtain

$\sigma_{n}\circ(A_{1}A_{2}^{-1})=B_{1}B_{2}^{-1}\circ\sigma_{n}$ (E.5)

and hence $G_{\sigma_{n}}$ is a subgroup. Next, we solve

$\sigma_{n}\circ A=B\circ\sigma_{n}$

for $B$ in terms of $A$ by evaluating both sides at
$e_{1},\dots,e_{n}\in\mathbb{R}^{n}$ (standard basis vectors). Letting
$A[:,j]$ denote the $j$-th column of $A$ we obtain

$\sigma_{n}(A[:,j])=B\sigma_{n}(e_{j}),\text{ for }j=1,\dots,n$

and stacking these columns to obtain the full $n\times n$ matrix yields

$\sigma(A)=B\sigma(I)$

where $I\in GL_{n}(\mathbb{R})$ is the identity matrix and $\sigma(A)$ denotes
$\sigma$ applied to the coordinates of $A$ (similarly for $\sigma(I)$). As
$\sigma(I)$ is invertible by hypotheses, this implies
$B=\sigma(A)\sigma(I)^{-1}=:\phi_{\sigma}(A)$, and finally substituting
$B_{i}=\phi_{\sigma}(A_{i})$ for $i=1,2$ in eq. E.5 shows that

$\sigma_{n}\circ(A_{1}A_{2}^{-1})=\phi_{\sigma}(A_{1})\phi_{\sigma}(A_{2})^{-1}\circ\sigma_{n}$

while at the same time

$\sigma_{n}\circ(A_{1}A_{2}^{-1})=\phi_{\sigma}(A_{1}A_{2}^{-1})\circ\sigma_{n}$

so that
$\phi_{\sigma}(A_{1}A_{2}^{-1})\circ\sigma_{n}=\phi_{\sigma}(A_{1})\phi_{\sigma}(A_{2})^{-1}\circ\sigma_{n}$.
Using the invertibility of $\sigma(I)$ one more time, we conclude

$\phi_{\sigma}(A_{1}A_{2}^{-1})=\phi_{\sigma}(A_{1})\phi_{\sigma}(A_{2})^{-1},$

which implies $\phi_{\sigma}$ is a homomorphism. ∎

######  Remark E.6 (for the mathematically inclined reader).

Here is a more abstract definition of $G_{\sigma_{n}}$ that makes lemma 3.1
appear more natural: let $X$ be a topological space with a continuous (left)
action of a topological group $G$. There is a natural (right) action of $G$ on
$C(X,\mathbb{R})$ by precomposition ($(f,g)\mapsto f\circ g$). For any
subspace $V\subseteq C(X,\mathbb{R})$ define

$G_{V}:=\\{g\in G\,|\,V\cdot g\subseteq V\\}$

(that is, the elements of $G$ stabilize $V$ _as a subspace_ , but not
necessarily pointwise — one can show this is always a subgroup of $G$). Then,
for every such subspace $V$, the group $G_{V}$ acts linearly on $V$, and if we
have a basis $f_{1},\dots,f_{n}\in V$, we can obtain a matrix representation
of $G$ in $GL_{n}(\mathbb{R})$. To obtain the special case in lemma 3.1, we
take $X=\mathbb{R}^{n}$, $G=GL_{n}(\mathbb{R})$ with the usual action, and $V$
to be the subspace spanned by the functions
$f_{i}(x_{1},\dots,x_{n})=\sigma(x_{i})$. The condition that $\sigma(I)$ is
invertible is equivalent to the condition that the column space of the matrix
$(f_{i}(e_{j})$ is $n$-dimensional, which in turn implies $V$ is
$n$-dimensional.

We end this section with a lemma that allows for easy verification that
$\sigma(I)$ is invertible. We used this on all the activation functions
considered in fig. 4.

######  Lemma E.7.

Let $\sigma:\mathbb{R}\to\mathbb{R}$ be any function and let $I\in
GL_{n}(\mathbb{R})$ be the identity matrix. Then $\sigma(I)$ is invertible
provided

$\sigma(1)\neq\sigma(0)\text{ and }\sigma(1)\neq-(n-1)\sigma(0).$ (E.8)

###### Proof.

Let $N=\mathbf{1}\mathbf{1}^{T}-I$. Then

$\sigma(I)=\sigma(1)I+\sigma(0)N.$

Note that the eigenvalues of $\mathbf{1}\mathbf{1}^{T}$ are $n$ (corresponding
to eigenvector $\mathbf{1}$) and 0’s (corresponding to the orthogonal
complement of $\mathbf{1}$). For any linear operator
$A\in\operatorname{Mat}_{n}(\mathbb{R})$ with eigenvector/eigenvalue pair
$(v,\lambda)$, $v$ is easily seen to be an eigenvector of $A-I$ with
eigenvalue $\lambda-1$. Hence the eigenvalues of $N$ are $n-1$ and $-1$, and
it follows that the eigenvalues of $\sigma(I)$ are

$\sigma(1)+\sigma(0)(n-1),\sigma(1)-\sigma(0),\dots,\sigma(1)-\sigma(0)$

which are all non-zero if and only if eq. E.8 holds. ∎

######  Remark E.9.

In particular eq. E.8 holds when $\sigma(1)=1,\sigma(0)=0$ (which holds for
example when $\sigma(x)=\operatorname{ReLU}(x)$ or $\sigma(x)=x^{d}$). In this
situation, $\sigma(I)=I$ and $\phi_{\sigma}(A)=\sigma(A)$ (coordinatewise
application of $\sigma$). For example, if $\sigma\geq 0$ is non-negative, then
$\phi_{\sigma}(A)=\sigma(A)$ has non-negative entries.

###  E.2 Calculating intertwiner groups (for fig. 4)

We begin with two lemmas: the first puts a “lower bound” on $G_{\sigma_{n}}$
and the second is a “differential form” of the definition of the intertwiner
group from section 3. Together, these two results effectively allow us to
reduce calculation of intertwiner groups to the $n=1$ case.

######  Lemma E.10 (cf. [GBC16, §8.2.2], [Bre+19, §3]).

$G_{\sigma_{n}}$ always contains the permutation matrices $\Sigma_{n}$, and
$\phi_{\sigma}$ restricts to the identity on $\Sigma_{n}$.

###### Proof.

If $A\in\Sigma_{n}$ is a permutation matrix, so that $Ae_{i}=e_{\pi(i)}$ where
$\pi$ is a permutation of $\\{1,\dots,n\\}$ then for any $x\in\mathbb{R}^{n}$
we observe

$A\sigma(x)=A(\sum_{i}\sigma(x_{i})e_{i})=\sum_{i}\sigma(x_{i})Ae_{i}=\sum_{i}\sigma(x_{i})e_{\pi(i)}$

which is exactly $\sigma$ applied coordinatewise to
$\sum_{i}x_{i}e_{\pi(i)}=Ax$. ∎

######  Corollary E.11.

If $A\in GL_{n}(\mathbb{R}),P\in\Sigma_{n}$, and $AP\in G_{\sigma_{n}}$ or
$PA\in G_{\sigma_{n}}$, then $A\in G_{\sigma_{n}}$.

###### Proof.

If $B=AP\in G_{\sigma_{n}}$, then $A=BP^{-1}$, where $B\in G_{\sigma_{n}}$ by
hypothesis and $P\in G_{\sigma_{n}}$ by lemma E.10. The result follows as
$G_{\sigma_{n}}$ is a group (lemma 3.1) and hence closed under multiplication.
The other case is similar. ∎

######  Lemma E.12.

Suppose $A,B\in GL_{n}(\mathbb{R})$ and $\sigma_{n}\circ A=B\circ\sigma_{n}$.
Suppose $x=(x_{1},\dots,x_{n})^{T}\in\mathbb{R}^{n}$ and assume $\sigma$ is
differentiable at $x_{1},\dots,x_{n}$ as well as

$(Ax)_{i}=\sum_{j}a_{ij}x_{j},\quad\text{ for }i=1,\dots,n.$

Then,

$\operatorname{diag}(\sigma^{\prime}((Ax)_{i})|i=1,\dots,n)A=B\operatorname{diag}(\sigma^{\prime}(x_{i})|i=1,\dots,n)$

(here $\operatorname{diag}:\mathbb{R}^{n}\to\operatorname{Mat}_{n\times
n}(\mathbb{R})$ takes a vector to a diagonal matrix). Explicitly, for each
$i,j\in\\{1,\dots,n\\}$

$\sigma^{\prime}(\sum_{k}a_{ik}x_{k})a_{ij}=b_{ij}\sigma^{\prime}(x_{j}).$
(E.13)

###### Proof.

By the chain rule [Rud76, Thm. 9.15], and since the differential of a matrix
is itself,

$d\sigma_{n}|_{Ax}A=Bd\sigma_{n}|_{x}.$

Finally, by the definition of $\sigma_{n}$

$\frac{\partial(\sigma_{n}(x))_{i}}{\partial
x_{j}}=\frac{\partial\sigma(x_{i})}{\partial
x_{j}}=\begin{cases}\sigma^{\prime}(x_{j})&\text{ if }i=j\\\ 0&\text{
otherwise}.\end{cases}$

∎

######  Theorem E.14.

Suppose $\sigma$ is non-constant, non-linear, and differentiable on a dense
open set with finite complement.444The differentiability assumption is
probably not necessary, however it holds in all of the examples we consider
and allows us to safely use lemma E.12. Then,

  1. (i)

Every $A\in G_{\sigma_{n}}$ is of the form $PD$, where $P\in\Sigma_{n}$ and
$D$ is diagonal.

  2. (ii)

For a diagonal $D=\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})\in
G_{\sigma_{n}}$, we have $\lambda_{i}\in G_{\sigma_{1}}$ for $i=1,\dots,n$ and

$\phi_{\sigma}(\operatorname{diag}(\lambda_{1},\dots,\lambda_{n}))=\operatorname{diag}(\phi_{\sigma}(\lambda_{1}),\dots,\phi_{\sigma}(\lambda_{1}))$

where we make a slight abuse of notation: on the right hand side
$\phi_{\sigma}$ is the homomorphism $G_{\sigma_{1}}\to GL_{1}(\mathbb{R})$.

In particular, $\phi_{\sigma}$ is determined by lemma E.10 and its behavior
for $n=1$.

###### Proof.

For any $A\in G_{\operatorname{ReLU}}$ we observe that the differentiability
hypotheses of lemma E.12 holds for $x\in U$ where $U$ is a dense open set with
measure-0 complement. Indeed, if $t_{1},\dots,t_{M}\in\mathbb{R}$ are the
points where $\sigma$ fails to be differentiable, we can take $U$ to be the
complement of the hyperplane arangement given by

$(\bigcup_{ij}\\{x\in\mathbb{R}^{n}\;|\;x_{i}=t_{j}\\})\cup(\bigcup_{ij}\\{x\in\mathbb{R}^{n}\;|\;(Ax)_{i}\in=t_{j}\\})\subseteq\mathbb{R}^{n}$

Fix a row $i$ — the matrix $A$ is invertible by hypotheses, and so there must
be some $j$ such that $a_{ij}\neq 0$ (otherwise the $i$-th row of $A$ is 0).
For any $x\in U$, we have by lemma E.12

$\sigma^{\prime}(\sum_{k}a_{ik}x_{k})a_{ij}=b_{ij}\sigma^{\prime}(x_{j})$
(E.15)

and we claim that this cannot hold unless $a_{ik}=0$ for $k\neq j$. First,
there is a $(x_{1},\dots,x_{n})\in U$ such that $\sigma^{\prime}(x_{j})\neq 0$
(otherwise $\sigma$ would be constant). Next, fixing $x_{j}$ at a value with
$\sigma^{\prime}(x_{j})\neq 0$ and rearranging eq. E.15 we have

$\frac{\sigma^{\prime}(a_{ij}x_{j}+\sum_{k\neq
j}a_{ik}x_{k})}{\sigma^{\prime}(x_{j})}a_{ij}=b_{ij}=\text{ constant}.$ (E.16)

By hypothesis $\sigma$ is non-linear and so $\sigma^{\prime}$ is non-constant
— hence if there were some $a_{ik}\neq 0$ for $k\neq j$, the left hand side of
eq. E.16 would be non-constant.

We have shown each row of $A$ has at most one non-0 entry $a_{ij}$ and that
$a_{ij}\neq 0$. For $A$ to be invertible, it must be that these non-0 entries
land in distinct _columns_. This is exactly the form described in item i.

Next, we note that for any $ij$ (without assuming $a_{ij}\neq 0$) eqs. E.15
and E.16 tell us

$a_{ij}=0\implies b_{ij}=0,$

and hence if $D=\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})\in
G_{\sigma_{n}}$ and $\sigma_{n}\circ D=E\circ\sigma_{n}$ (i.e.
$E=\phi_{\sigma}(D)$), it must be that
$E=\operatorname{diag}(\mu_{1},\dots,\mu_{n})$ for some
$\mu_{1},\dots,\mu_{n}\in\mathbb{R}$. Now the equation $\sigma_{n}\circ
D=E\circ\sigma_{n}$ is equivalent to

$\sigma(\lambda_{i}x_{i})=\beta_{i}\sigma(x_{i})\text{ for }i=1,\dots,n$

which in turn is equivalent to $\lambda_{i}\in G_{\sigma_{1}}$ and
$\beta_{i}=\phi_{\sigma}(\lambda_{i})$ for $i=1,\dots,n$, proving item ii. ∎

In light of theorem E.14, to fill in the table of fig. 4 it will suffice to
deal with the $n=1$ cases, which we do below.

###### Calculation of $G_{\operatorname{ReLU}}$.

We remark that this is just the “positive homogeneous” property of
$\operatorname{ReLU}$, which is quite well known (cf. [GBC16, §8.2.2], [FB17,
§2], [Kun+21, §3], [Men+19, §3], [RK20, §3, A], [Yi+19, §2-3]). Using remark
E.9 if $a\in G_{\sigma_{1}}$

$\max\\{0,ax\\}=\max\\{0,a\\}\max\\{0,x\\}.$

If $a<0$ then setting $x=-1$ results in $a=0$, a contradiction. So $a>0$ and
$\max\\{0,ax\\}=a\max\\{0,x\\}$, showing $\phi_{\sigma}(a)=a$. ∎

###### Modifications for $\operatorname{LeakyReLU}$.

By definition, for $0<s\ll 1$.

$\operatorname{LeakyReLU}(x,a):=\begin{cases}sx&\text{ for }x<0\\\ x&\text{
for }x\geq 0\end{cases}$

which we may simplify to
$\operatorname{LeakyReLU}(x)=sx+(1-s)\operatorname{ReLU}(x)$. Suppose now that

$\begin{split}\operatorname{LeakyReLU}(ax)&=b\operatorname{LeakyReLU}(x),\text{
or using our simplification }\\\
sax+(1-s)\operatorname{ReLU}(ax)&=b(sx+(1-s)\operatorname{ReLU}(x)).\end{split}$
(E.17)

If $a<0$, we may choose $x=-1$ to obtain

$-a=-sa-(1-s)a=-bs\text{ and $x=1$ to obtain}$ $sa=b$

showing that $a=as^{2}$, which is impossible when $0<s\ll 1$. So it must be
$a>0$, and then evaluating eq. E.17 at $x=1$ gives $a=b$. ∎

###### The sigmoid case: $\sigma(x)=1/(1+e^{x})$.

We will leverage of a useful fact about the sigmoid function:

$\sigma^{\prime}(x)$ is a smooth probability distribution function on
$\mathbb{R}$, with $\sigma^{\prime}(x)>0$ for all $x\in\mathbb{R}$. (*)

If $\sigma(ax)=b\sigma(x)$, differentiating with respect to $x$ gives

$\sigma^{\prime}(ax)a=b\sigma^{\prime}(x).$ (E.18)

Using eq. * and the fact that to probability distribution functions are
proportional if and only if they are equal, we get
$\sigma^{\prime}(ax)=\sigma^{\prime}(x)$. Then integrating from $-\infty$ to
$x$ tells us $\sigma(ax)/a=\sigma(x)$; setting $x=0$ we see
$\frac{1}{2a}=\frac{1}{2}$, hence $a=1$.

To show $\phi_{\sigma}=\mathrm{id}$, backtracking to eq. E.18 and setting
$x=0$ shows $b=a$. ∎

###### The Gaussian RBF case:
$\sigma(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}$.

We make use of several properties of this $\sigma(x)$:

  1. (i)

For any $a>0$ the function $\sigma(ax)$ is a probability distribution function
with mean $0$ and variance $\frac{1}{a^{2}}$,and with $\sigma(ax)>0$ for all
$x\in\mathbb{R}$ and

  2. (ii)

$\sigma$ is an even function ($\sigma(-x)=\sigma(x)$).

Now if $\sigma(ax)=b\sigma(x)$, then the pdfs $\sigma(ax)$ and $\sigma(x)$ are
proportional hence equal by item i. Therefore they have the same means and
variances — since these are $0,\frac{1}{a^{2}}$ and $0,1$ respectively we
conclude $a=\pm 1$.

Finally, we explain why $\phi_{\sigma}(A)=\operatorname{abs}(A)$ (entrywise
absolute value). Differentiating with respect to $x$ gives

$\sigma^{\prime}(ax)a=b\sigma^{\prime}(x).$ (E.19)

This implies $b=1$ when $a=1$. On the other hand differentiating item ii tells
us $-\sigma^{\prime}(-x)=\sigma^{\prime}(x)$, so when $a=-1$

$b\sigma^{\prime}(x)=-\sigma^{\prime}(-x)=\sigma^{\prime}(x)$

and hence $b=1$. ∎

###### The polynomial case: $\sigma(x)=x^{d}$.

We remark that the description given in fig. 4 is implicit in [KTB19]. By
theorem E.14 we only need to describe $\phi_{\sigma}:G_{\sigma_{1}}\to
GL_{1}(\mathbb{R})$; for any $a\neq 0$

$(ax)^{d}=a^{d}x^{d}$

and this shows $G_{\sigma_{1}}=\mathbb{R}\setminus\\{0\\}$ and
$\phi_{\sigma}(a)=a^{d}$. ∎

###  E.3 Proof of theorem 3.3

###### Proof.

The explicit description of $G(\operatorname{ReLU},n)$ in fig. 4 is enough to
show $G(\operatorname{ReLU},n)$ _stabilizes_ $\\{\mathbb{R}_{\geq
0}e_{i}|i=1,\dots,n\\}$. Indeed, any $A\in G(\operatorname{ReLU},n)$ may be
written as $PD$ where $D=\operatorname{diag}(a_{i})$ for some $a_{i}>0$ and
$P$ is a permutation matrix associated to a permutation $\pi$. It suffices to
show that $P$ and $\operatorname{diag}(a_{i})$ each preserves
$\\{\mathbb{R}_{\geq 0}e_{i}|i=1,\dots,n\\}$. First,

$\operatorname{diag}(a_{i})\\{\mathbb{R}_{\geq
0}e_{i}|i=1,\dots,n\\}=\\{\mathbb{R}_{\geq
0}a_{i}e_{i}|i=1,\dots,n\\}=\\{\mathbb{R}_{\geq 0}e_{i}|i=1,\dots,n\\}$

since the $a_{i}>0$ so scaling by $a_{i}$ preserves the ray $\mathbb{R}_{\geq
0}e_{i}$. Second,

$P\\{\mathbb{R}_{\geq 0}e_{i}|i=1,\dots,n\\}=\\{\mathbb{R}_{\geq
0}Pe_{i}|i=1,\dots,n\\}=\\{\mathbb{R}_{\geq
0}e_{\pi(i)}|i=1,\dots,n\\}=\\{\mathbb{R}_{\geq 0}e_{i}|i=1,\dots,n\\}$

(the last equality is due to the fact that we only consider the set of rays,
not the ordered tuple of rays).

Conversely, if $A\in GL(n)$ stabilizes $\\{\mathbb{R}_{\geq
0}e_{i}|i=1,\dots,n\\}$, then in particular for each $j$
$Ae_{j}\in\mathbb{R}_{\geq 0}e_{i}\text{ for some }i$ and as $A$ is
invertible, setting $j=\pi(i)$ yields a permutation of $\\{1,\dots,n\\}$.
Moreover,since $Ae_{j}\neq 0$ ($A$ is invertible) there must be some $a_{j}>0$
so that $Ae_{j}=a_{j}e_{i}$. One can now verify that $A=PD$ where $P$ is the
permutation matrix associated to $\pi$ and $D=\operatorname{diag}(a_{j})$
which matches the description of $G(\operatorname{ReLU},n)$ from fig. 4.

For the “moreover,” we prove the contrapositive, namely that if
$v=(v_{1},\dots,v_{n})\in\mathbb{R}^{n}$ has at least 2 non-0 coordinates
$v_{i},v_{j}$, then the $G_{\operatorname{ReLU}}$-orbit of the ray
$\mathbb{R}_{\geq 0}v$ that $v$ generates cannot be finite. Indeed, suppose
$t\geq 0$ and let $D=\operatorname{diag}(1,\dots,1,t,1,\dots,1)$ ($t$ in the
$i$th position). The $n\times 2$ matrix $(v|Dv)$ has a $2\times 2$ minor

$\begin{pmatrix}v_{i}&tv_{i}\\\ v_{j}&v_{j}\end{pmatrix}\text{ with
deteriminant }(1-t)v_{i}v_{j}\neq 0\text{ as long as }t\neq 1.$ (E.20)

Thus $v$ and $Dv$ are linearly independent, and hence define distinct rays,
for all $t\neq 1$. It follows that any set of rays stabilized by
$G(\operatorname{ReLU},n)$ that contains $\mathbb{R}_{\geq 0}v$ is
uncountable. ∎

###  E.4 Proof of proposition 3.4

To give a rigorous proof we use induction on the depth $k$; since this to some
extent obscures the main point, we briefly outline an informal proof: consider
a composition of 2 layers of the network $f$ with weights $W^{\prime}$:

$\sigma(A_{i+1}W_{i+1}\phi_{\sigma}(A_{i})^{-1}\sigma(A_{i}W_{i}\phi_{\sigma}(A_{i-1})^{-1}x+A_{i}b_{i})+A_{i+1}b_{i+1}).$
(E.21)

Using the defining properties of $G_{\sigma}$ and $\phi_{\sigma}$, we can
extract $A_{i}$ like

$\sigma(A_{i}W_{i}\phi_{\sigma}(A_{i-1})^{-1}x+A_{i}b_{i})=\phi_{\sigma}(A_{i})\sigma(W_{i}\phi_{\sigma}(A_{i-1})^{-1}x+b_{i}).$
(E.22)

The resulting copy of $\phi_{\sigma}(A_{i})$ on the right hand side of eq.
E.22 is cancelled by the copy of $\phi_{\sigma}(A_{i})^{-1}$ right-multiplying
$W_{i+1}$ in eq. E.21, so that eq. E.21 reduces to

$\sigma(A_{i+1}W_{i+1}\sigma(W_{i}\phi_{\sigma}(A_{i-1})^{-1}x+b_{i})+A_{i+1}b_{i+1}).$

In this way, in between any two layers $\ell_{i+1}\circ\ell_{i}$ the $A_{i}$
in $A_{i}W_{i}\phi_{\sigma}(A_{i-1})^{-1}$ and the $\phi_{\sigma}(A_{i})^{-1}$
in $A_{i+1}W_{i+1}\phi_{\sigma}(A_{i})^{-1}$ _cancel_. However, the factors
$\phi_{\sigma}(A_{m})$ and $\phi_{\sigma}(A_{m})^{-1}$ appear on endpoints of
the truncated networks $f_{\leq m},f_{>m}$ and so they are not cancelled.

To keep track of $W,W^{\prime}$ while using the notation from section 3, we
write

$\ell_{i}(x,W)=\sigma(W_{i}x+b_{i})\text{ and
}\ell_{i}(x,W^{\prime})=\sigma(W^{\prime}_{i}x+b^{\prime}_{i})\text{ for }i<k$

and so on.

###### Proof.

By induction on $k$, the depth of the network. The case $k=1$ is trivial,
since there $W^{\prime}=W$ and there is nothing to prove. For $k>1$ we
consider 2 cases:

Case $m=1$: In this case let $V=(W_{2},b_{2},\dots,W_{k},b_{k})$ and
$V^{\prime}=(A_{2}W_{2},A_{2}b_{2},A_{3}W_{3}\phi_{\sigma}(A_{2})^{-1},A_{3}b_{3},\dots,W_{k}\phi_{\sigma}(A_{k-1}^{-1}),b_{k})$,
and let

$g(x,V)=\ell_{k-1}(x,V)\circ\cdots\circ\ell_{1}(x,V)\text{ and
}g(x,V^{\prime})=\ell_{k-1}(x,V^{\prime})\circ\cdots\circ\ell_{1}(x,V^{\prime})$

where $\ell_{i}(x,V)=\sigma(W_{i+1}x+b_{i+1})$ and similarly for $V^{\prime}$.
In other words, the weights $V,V^{\prime}$ and function $g$ represent the
architecture obtained by removing the earliest layer of $f$. Then, $f_{\leq
1}(x,W)=\sigma(W_{1}x+b_{1})$ and on the other hand

$f_{\leq
1}(x,W^{\prime})=\sigma(A_{1}W_{1}x+A_{1}b_{1})=\sigma(A_{1}(W_{1}x+b_{1})).$

Using the identity $\sigma(A_{1}z)=\phi_{\sigma}(A_{1})\sigma(z)$ for any
$z\in\mathbb{R}^{n_{1}}$, we obtain

$f_{\leq
1}(x,W^{\prime})=\phi_{\sigma}(A_{1})\sigma(W_{1}x+b_{1})=\phi_{\sigma}(A_{1})\sigma(W_{1}x+b_{1}).$

This shows $f_{\leq 1}(x,W^{\prime})=\phi_{\sigma}(A_{1})\circ f_{\leq
1}(x,W)$. Next, $f_{>1}(x,W)=g(x,V)$ but _because_ $V^{\prime}_{1}=A_{2}W_{2}$
whereas $W^{\prime}_{2}=A_{2}W_{2}\phi_{\sigma}(A_{1})^{-1}$

$f_{>1}(x,W^{\prime})=g(x,V^{\prime})\circ\phi_{\sigma}(A_{1})^{-1}.$

By induction on $k$, we may assume $g(x,V)=g(x,V^{\prime})$ and it follows
that $f_{>1}(x,W^{\prime})=f_{>1}(x,W)\circ\phi_{\sigma}(A_{1})^{-1}$

Case $m>1$: Defining $V,V^{\prime}$ and $g$ as above, we observe that

$\begin{split}f_{\leq i}(x,W)&=g_{\leq i-1}(\sigma(W_{1}x+b_{1}),V)\text{ and
}\\\ f_{\leq i}(x,W^{\prime})&=g_{\leq
i-1}(\phi_{\sigma}(A_{1})^{-1}\sigma(A_{1}W_{1}x+A_{1}b_{1}),V^{\prime})=g_{\leq
i-1}(\sigma(W_{1}x+b_{1}),V^{\prime}).\end{split}$ (E.23)

By induction on $k$ we may assume $g_{\leq
i-1}(x,V^{\prime})=\phi_{\sigma}(A_{i})g_{\leq i-1}(x,V)$ and so

$f_{\leq i}(x,W^{\prime})=\phi_{\sigma}(A_{i})g_{\leq
i-1}(\sigma(W_{1}x+b_{1}),V)=\phi_{\sigma}(A_{i})f_{\leq i}(x,W).$

Finally, $f_{>i}(x,W)=g_{>i-1}(x,V)$ and
$f_{>i}(x,W^{\prime})=g_{>i-1}(x,V^{\prime})$ and we may assume by induction
on $k$ that
$g_{>i-1}(x,V^{\prime})=g_{>i-1}(x,V)\circ\phi_{\sigma}(A_{i})^{-1}$, hence
$f_{>i}(x,W^{\prime})=f_{>i}(x,W)\circ\phi_{\sigma}(A_{i})^{-1}$. ∎

###  E.5 Proof of theorem 4.2

###### Proof.

Observe that by proposition 3.4,
$\tilde{f}_{>l}=f_{>l}\circ\phi_{\sigma}(A_{l}^{-1})$. Hence

$S(f,\tilde{f},l,\varphi)=\tilde{f}_{>l}\circ\varphi\circ f_{\leq
i}=f_{>l}\circ\phi_{\sigma}(A_{l}^{-1})\circ\varphi\circ f_{\leq l}.$

If $\mathcal{S}$ contains $\phi_{\sigma}(G_{\sigma_{n_{l}}})$ we may choose
$\varphi=\phi_{\sigma}(A_{l})$ to achieve $S(f,\tilde{f},l,\varphi)=f$ as
functions. Similarly, $\tilde{f}_{\leq l}=\phi_{\sigma}(A_{l})\circ f_{\leq
l}$ so if $\mathcal{S}$ contains $\phi_{\sigma}(G_{\sigma_{n_{l}}})$ we may
choose $\varphi=\phi_{\sigma}(A_{l}^{-1})$ to achieve
$S(f,\tilde{f},l,\varphi)=\tilde{f}$ as functions. In either case eq. 4.1
holds. ∎

###  E.6 Symmetries of the loss landscape

Given that the intertwiner group describes a large set of symmetries of a
network, it is not surprising that it also provides a way of understanding the
relationship between equivalent networks. Proposition 3.4 has an
interpretation in terms of the loss landscape of model architecture. For any
layer $n_{i}$ in $f$, the action of $G_{\sigma_{n_{i}}}$ on the weight space
$\mathcal{W}$, translates to the obvious group action on the loss landscape.

######  Corollary E.24.

For any $1\leq i\leq k$, the group $G_{\sigma_{n_{i}}}$ acts on $\mathcal{W}$
and for any test set $D_{t}\subset X\times Y$, model loss on $D_{t}$ is
invariant with respect to this action. More precisely, if $\ell(\Phi(W),D)$ is
the loss of $\Phi(W)$ on test set $D_{t}$, then for any $g\in
G_{\sigma_{n_{i}}}$, $\ell(\Phi(W),D)=\ell(\Phi(gW),D)$.

###  E.7 Calculations related to dissimilarity metrics (for section 5)

###### Proof of lemma 5.1.

By fig. 4 any $A\in G_{\operatorname{ReLU}}$ can be factored as $A=PD$ with
$P$ a permutation matrix and $D$ a positive diagonal matrix, and we can obtain
a similar factorization $B=QE$. Then

$\mu(XA,YB)=\mu(XPD,YQE)=\mu(XP,YQ)=\mu(X,Y)$

where the second equality uses the hypothesis that $\mu$ is invariant to right
multiplication by positive diagonal matrices, and the third uses the
hypothesis that $\mu$ is invariant to right multiplication by permutation
matrices. ∎

######  Lemma E.25.

Suppose $A$ is a matrix such that $\max(Ax_{1}\odot Ax_{2})=\max(Ax_{1}\odot
Ax_{2})$ for all $x_{1},x_{2}\in\mathbb{R}^{d}$. Then, $A$ is of the form $PD$
where $P$ is a permutation matrix and $D$ is diagonal with diagonal entries in
$\\{\pm 1\\}$.

###### Proof.

We only need the special case where $x=y$: observe that

$\max(x\odot x)=\max\\{x_{1}^{2},\dots,x_{d}^{2}\\}=(\max\\{\lvert
x_{1}\rvert,\dots,\lvert x_{d}\rvert\\})^{2}=\lvert x\rvert_{\infty}^{2}$

This means that if $\max(Ax_{1}\odot Ax_{2})=\max(Ax_{1}\odot Ax_{2})$, then
$A$ preserves the $\ell_{\infty}$ norm on $\mathbb{R}^{d}$, hence in
particular preserves the unit hypercube in $\mathbb{R}^{d}$, and it is known
that symmetries of the hypercube have the form $PD$ where $P$ is a permutation
matrix and $D$ is diagonal with diagonal entries in $\\{\pm 1\\}$ (see for
example [Ser77, §5.9]). ∎

###  E.8 Intertwiners and more general architecture features (justification of
remark 3.6)

Here we briefly discuss how ubiquitous architecture features like batch
normalization and residual connections interact with intertwiner groups. For
simplicity in this section we only consider $\sigma=\operatorname{ReLU}$.

####  E.8.1 Batch normalization

A batch normalization layer that takes as input $X\in\mathbb{R}^{b\cdot n}$
(where $b$ is the batch size and $n$ is the dimension of the layer) and
returns

$\tilde{X}\operatorname{diag}(\tilde{X}^{T}\tilde{X})^{-1}\operatorname{diag}(\gamma)+\beta\text{
where }\tilde{X}=X-\mathbf{1}\mathbf{1}^{T}X$

and where $\gamma,\beta\in\mathbb{R}^{n}$ are the “gain” and “bias” parameters
of the batch normalization layer, is _invariant_ under independent scaling of
coordinates, that is transformations of the form $X\leftarrow XD$ where $D$ is
an $n\times n$ positive diagonal matrix (see e.g. [BMC15]). Hence a $k$-layer
$\operatorname{ReLU}$ MLP as in section 3 enhanced with batch normalization
(_pre_ -activation, as is standard) is invariant under the action of the
slightly larger group $\prod_{l=1}^{k-1}(\mathbb{R}^{n_{l}}_{>0}\rtimes
G_{\operatorname{ReLU}_{n_{l}}})$, where the action is given by555As is best
practice we omit the biases on the linear layers $\ell_{l}$ for $l<k$, since
they would be redundant now that we have biases on batch norm layers.

$\begin{split}&(c_{1},A_{1},\dots,c_{k-1},A_{k-1})\cdot(W_{1},\gamma_{1},\beta_{1},\dots,W_{k-1},\gamma_{k-1},\beta_{k-1},W_{k},b_{k})\\\
&=(A_{1}W_{1},\pi(A_{1})\operatorname{diag}c_{1}\gamma_{1},\pi(A_{1})\operatorname{diag}c_{1}\beta_{1},\\\
&A_{2}W_{2}(\pi(A_{1})\operatorname{diag}c_{1})^{-1},\pi(A_{2})\operatorname{diag}c_{2}\gamma_{2},\pi(A_{2})\operatorname{diag}c_{2}\beta_{2},\\\
&\dots,A_{k-1}W_{k-1}(\pi(A_{k-2})\operatorname{diag}c_{k-2})^{-1},\pi(A_{k-1})\operatorname{diag}c_{k-1}\gamma_{k-1},\pi(A_{k-1})\operatorname{diag}c_{k-1}\beta_{k-1},\\\
&W_{k}(\pi(A_{k-1})\operatorname{diag}c_{k-1})^{-1},b_{k}).\end{split}$ (E.26)

Here,

  * •

$c_{l}\in\mathbb{R}^{n_{l}}_{>0}$ and $A_{l}\in
G_{\operatorname{ReLU}_{n_{l}}}$, for all $l=1,\dots,k-1$

  * •

$\pi:G_{\operatorname{ReLU}_{n_{l}}}\to\Sigma_{n_{l}}$ is the homomorphism
setting the positive entries to 1.

The key point is that we get another factor of $\mathbb{R}^{n_{l}}_{>0}$ at
each layer. We also note that the space of matrices of the form
$\pi(A_{l})\operatorname{diag}c_{l}$ is, incidentally, exactly
$G_{\operatorname{ReLU}_{n_{l}}}$, and that using eq. E.26 one can generalize
propositions 3.4 and 4.2 to the case of networks with batch normalization.

####  E.8.2 Residual connections

We expand on remark 3.6 and explain what exactly transpires with residual
connections below.

Suppose we have a $k$-layer MLP as in section 3 (again for simplicity with
$\sigma=\operatorname{ReLU}$), together with residual connections between a
set of layers $R=\\{r_{1},\dots,r_{m}\\}\subseteq\\{2,\cdots,k-1\\}$666In
particular we assume there is at least one linear layer before the first
outgoing/after the last incoming residual connection, as occurs in e.g.
ResNets.:

${\mathbb{R}^{n_{0}}}$${\cdots}$${\mathbb{R}^{n_{r_{i-1}}}}$${\cdots}$${\mathbb{R}^{n_{r_{i}}}}$${\cdots\mathbb{R}^{n_{k-1}}}$${\mathbb{R}^{n_{L+1}}}$$\scriptstyle{\sigma
W_{1}}$$\scriptstyle{\sigma W_{r_{i-1}}}$$\scriptstyle{\sigma
W_{r_{i-1}+1}}$$\scriptstyle{\mathrm{id}}$$\scriptstyle{W_{r_{i}}}$$\scriptstyle{\sigma}$$\scriptstyle{W_{k}}$
(E.27)

(for legibility biases $b_{l}$ are suppressed). In addition we assume that the
depth of each residual block is some fixed, that is $r_{i}-r_{i-1}=b=$
constant for all $i$.

First, we claim that a $(A_{1},\dots
A_{k-1})\in\prod_{l=1}^{L}G_{\operatorname{ReLU}_{n_{l}}}$ stabilizes the
function $f$ _if_ (not claiming if and only if) $A_{r_{i}}=A_{r_{j}}$ for all
$r_{i},r_{j}\in R$. To see this suppose $g_{i}(x,W)$, $i=1,\dots,m$ are the
depth $b$ feedforward networks of the residual blocks, so that the $f_{\leq
r_{i}}$ is given by

$\begin{split}f_{\leq r_{i}}(x,W)&=f_{\leq r_{i-1}}(x,W)+g_{i}(f_{\leq
r_{i-1}}(x,W),W)\text{ where }\\\
g_{i}(z,W)&=\sigma(W_{r_{i}+b}\sigma(\cdots\sigma(W_{r_{i-1}+1}z)\cdots)).\end{split}$
(E.28)

Assuming by induction on $i$ that proposition 3.4 applies _at the residual
connections in $R$_ we note that with weights $W^{\prime}$ eq. E.28 turns into

$\begin{split}f_{\leq r_{i}}(x,W^{\prime})&=f_{\leq
r_{i-1}}(x,W^{\prime})+g_{i}(f_{\leq r_{i-1}}(x,W^{\prime}),W^{\prime})\\\
&=A_{r_{i-1}}f_{\leq r_{i-1}}(x,W)+g_{i}(A_{r_{i-1}}f_{\leq
r_{i-1}}(x,W),W^{\prime}).\end{split}$ (E.29)

Note that proposition 3.4 applies directly to the $g_{i}$, so we may compute
$g_{i}(z,W^{\prime})=A_{r_{i}}g_{i}(A_{r_{i-1}}^{-1}z,W)$. Hence

$\begin{split}f_{\leq r_{i}}(x,W^{\prime})&=A_{r_{i-1}}f_{\leq
r_{i-1}}(x,W)+A_{r_{i}}g_{i}(A_{r_{i-1}}^{-1}A_{r_{i-1}}f_{\leq
r_{i-1}}(x,W),W)\\\ &=A_{r_{i-1}}f_{\leq r_{i-1}}(x,W)+A_{r_{i}}g_{i}(f_{\leq
r_{i-1}}(x,W),W).\end{split}$ (E.30)

and we see that the only way $f_{\leq r_{i}}(x,W^{\prime})=Bf_{\leq
r_{i}}(x,W)$ for some matrix $B$ is if $A_{r_{i-1}}=A_{r_{i}}$, proving our
claim. This also shows that if $A_{r}$ denotes the common value of the
$A_{r_{i}}$ for $r_{i}\in R$, we have $f_{\leq
r_{i}}(x,W^{\prime})=A_{r}f_{\leq r_{i}}(x,W)$ for all $i$. It is also true
that $f_{>r_{i}}(x,W^{\prime})=f_{>r_{i}}(A_{r}^{-1}x,W)$: observe that

$f_{>r_{i}}(x,W)=f_{>r_{i+1}}(x+g_{i+1}(x,W),W).$ (E.31)

By _descending_ induction on $k$, we may assume
$f_{r_{i+1}}(x,W^{\prime})=f_{r_{i+1}}(A_{r}^{-1}x,W)$, and as above
$g_{i+1}(z,W^{\prime})=A_{r}g_{i+1}(A_{r}^{-1}z,W)$, so that with weights
$W^{\prime}$ eq. E.31 becomes

$\begin{split}f_{>r_{i}}(x,W^{\prime})&=f_{>r_{i+1}}(x+g_{i+1}(x,W^{\prime}),W^{\prime})\\\
&=f_{>r_{i+1}}(A_{r}^{-1}(x+A_{r}g_{i+1}(A_{r}^{-1}x,W)),W)\\\
&=f_{>r_{i+1}}(A_{r}^{-1}x+g_{i+1}(A_{r}^{-1}x,W),W)=f_{>r_{i}}(A_{r}^{-1}x,W).\end{split}$
(E.32)

as claimed.

Finally, we describe how stitching fails inside a residual block. Suppose we
use weights $W_{l}$ for $l\leq r_{i}+j$ where $0<j<b$) (recall $b=$ depth of
our basic block) and weights $W^{\prime}_{l}$ for $l>r_{i}+j$. The resulting
stitched network is (attempting to use indentation to increase legibility)

$\begin{split}f_{r_{i+1}}(&\\\ &f_{\leq r_{i}}(x,W)+g_{>j}(\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\varphi g_{\leq j}(f_{\leq
r_{i}}(x,W),W),\\\ &\quad\quad\quad\quad\quad\quad\quad\quad W^{\prime}),\\\
&W^{\prime}).\end{split}$ (E.33)

By proposition 3.4 $g_{>j}(z,W^{\prime})=A_{r}g_{>j}(A_{r_{i}+j}^{-1}z,W)$,
and we have shown $f_{>r_{i+1}}(z,W^{\prime})=f_{>r_{i+1}}(A_{r}^{-1}z,W)$.
Combining these facts eq. E.33 becomes

$\begin{split}f_{r_{i+1}}(&\\\ &A_{r}^{-1}f_{\leq
r_{i}}(x,W)+A_{r}^{-1}A_{r}g_{>j}(\\\
&\quad\quad\quad\quad\quad\quad\quad\quad A_{r_{i}+j}^{-1}\varphi g_{\leq
j}(f_{\leq r_{i}}(x,W),W),\\\ &\quad\quad\quad\quad\quad\quad\quad\quad W),\\\
&W).\end{split}$ (E.34)

_Even after cancelling to remove the $A_{r}^{-1}A_{r}$ and in the ideal case
where $\varphi=A_{r_{i}+j}$, we are left with an extra factor of $A_{r}^{-1}$
left multiplying $f_{\leq r_{i}}(x,W)$_:

$\begin{split}f_{r_{i+1}}(&\\\ &A_{r}^{-1}f_{\leq r_{i}}(x,W)+g_{>j}(\\\
&\quad\quad\quad\quad\quad\quad\quad\quad g_{\leq j}(f_{\leq
r_{i}}(x,W),W),\\\ &\quad\quad\quad\quad\quad\quad\quad\quad W),\\\
&W).\end{split}$ (E.35)

##  Appendix F Network dissection details

Here we include some supplementary results and experiments for examining
coordinate basis interpretability with network dissection. fig. 14 breaks down
the categories of interpretable units for the models and rotations examined in
fig. 3. The number of interpretable units tends to be dominated by the object
and scene concept detectors for the ResNet-50 and the ConvNeXt models.

Figure 14: Supplement for the same network dissection experiment for the
ResNet-50, modified ResNet-50, and ConvNeXt models in fig. 3, highlighting the
categories of interpretable units for each model and basis on the right. The
y-axis for the plot on the right is distinct concepts. Figure 15: Fraction of
network dissection interpretable units under rotations of the representation
basis for a ResNet-50 and a modified ResNet-50 without an activation function
on the residual output.

We also perform an analogous network dissection experiment to section 6 within
the residual blocks for the normal and modified ResNet-50 in fig. 15. Like the
ConvNeXt model in fig. 3 we find that, surprisingly, the percentage of
interpretable units actually tends to increase away from the activation basis.

Per-concept breakdowns produced by network dissection for three different
rotation powers in the experiment in fig. 3 are given for the ResNet-50 in
fig. 16, the modified ResNet-50 (without a ReLU activation function on the
residual output) in fig. 18, and the ConvNeXt in in fig. 20. We also include
the units with the highest concept intersection over union scores for the the
three representative rotations for the ResNet-50 in fig. 17, the modified
ResNet-50 (without a ReLU activation function on the residual output) in fig.
19, and the ConvNeXt in in fig. 21

Figure 16: Network dissection bar graph of categories of unique concepts at
three different rotation powers for the ResNet-50 model in fig. 3. Figure 17:
Top two highest scoring units for network dissection at three different
rotation powers for the ResNet-50 model in fig. 3. Figure 18: Network
dissection bar graph of categories of unique concepts at three different
rotation powers for the modified ResNet-50 model (without a ReLU activation
function on the residual output) in fig. 3. Figure 19: Top two highest scoring
units for network dissection at three different rotation powers for the
modified ResNet-50 model (without a ReLU activation function on the residual
output) in fig. 3. Figure 20: Network dissection bar graph of categories of
unique concepts at three different rotation powers for the ConvNeXt model in
fig. 3. Figure 21: Top two highest scoring units for network dissection at
three different rotation powers for the ConvNeXt model in fig. 3.

###  F.1 Model training details

We train a ResNet-50 without ReLU (or any activation function) on the residual
blocks in PyTorch using [Lec+22] on ImageNet [Den+09]. We train with SGD with
momentum for 88 epochs with a cyclic learning rate rate of $1.7$, label
smoothing of $0.1$, a batch size of 512, and weight decay of $10^{-4}$. The
model achieves 76.1% top-1 accuracy. We use pretrained weights for the
ResNet-50 (unmodified) and ConvNeXt models from [MR10] and [Wig19]
respectively.

##  Appendix G Dataset Details

CIFAR10: CIFAR10 is covered by the MIT License (MIT). We use canonical
train/test splits (imported using torchvision).

Broden: the code used to generate the dataset is covered by the MIT license.

ImageNet: ImageNet is covered by CC-BY 4.0. We use canonical train/test
splits.

(a) Myrtle CNN architecture, summary courtesy of torchinfo.

(b) Myrtle CNN architecture without batch norm (only used in section D.0.1),
summary courtesy of torchinfo.

(a) Our ResNet20 architecture, summary courtesy of torchinfo.

(b) Internals of the 1st BasicBlock (the sequential contains the residual
connection).

(a) Our ResNet18 architecture, summary courtesy of torchinfo.

(b) Internals of the 1st BasicBlock (the sequential contains the residual
connection).