# A note on Morita equivalence to graph inverse semigroups

Martha Du Preez  Department of Mathematics
The University of Texas at Tyler
3900 University Boulevard
Tyler, TX 75799<EMAIL_ADDRESS>,  Robert Grimley  Department
of Mathematics
Indiana University
Bloomington, IN 47401<EMAIL_ADDRESS>,  Evan Lira  Department of Mathematics
Clarkson University
8 Clarkson Ave.
Potsdam, NY 13699<EMAIL_ADDRESS>,  David Milan  Department of
Mathematics
The University of Texas at Tyler
3900 University Boulevard
Tyler, TX 75799<EMAIL_ADDRESS>and  Shreyas Ramamurthy  Department of
Mathematics
University of California, Berkeley
970 Evans Hall #3840
Berkeley, CA 94720-3840<EMAIL_ADDRESS>
###### Abstract.

We characterize the inverse semigroups that are Morita equivalent to graph
inverse semigroups. We also consider a generalization to inverse semigroups
associated with left cancellative categories.

###### 2010 Mathematics Subject Classification:

20M18

The authors were supported by an NSF grant (DMS-2149921).

##  1\. Introduction

We characterize the inverse semigroups that are Morita equivalent to graph
inverse semigroups. They are the combinatorial inverse semigroups $S$ with $0$
satisfying two additional conditions on the semilattice of idempotents: (1) if
$e,f$ are incomparable idempotents with $e,f\leq g$ for some $g\in E(S)$, then
$ef=0$, and (2) for $0\neq e\leq f$ there are finitely many idempotents
between $e$ and $f$ in the natural partial order. A key tool in our proof is a
graph $\Gamma_{S}$ associated with any combinatorial inverse semigroup $S$
satisfying (2). We show that if $S$ is Morita equivalent to some graph inverse
semigroup $S(\Gamma)$ then the graph $\Gamma$ must be isomorphic to
$\Gamma_{S}$ (Corollary 3.5).

We also consider a generalization of these results to inverse semigroups
associated with left cancellative categories. We show that the path category
defined in [2] characterizes Morita equivalence of such inverse semigroups.

##  2\. Preliminaries

An _inverse semigroup_ is a semigroup $S$ such that for each $s$ in $S$ there
exists a unique $s^{*}$ in $S$ such that

$s=ss^{*}s\quad\text{and}\quad s^{*}=s^{*}ss^{*}.$

The set of idempotents of $S$, denoted $E(S)$, is a commutative subsemigroup
of $S$. The natural partial order is defined on $S$ by $s\leq t$ if and only
if $s=te$ for some $e\in E(S)$. Green’s relations are quite simple to define
for inverse semigroups: we have $s\mathrel{\mathcal{L}}t$ if and only if
$s^{*}s=t^{*}t$, $s\mathrel{\mathcal{R}}t$ if and only if $ss^{*}=tt^{*}$, and
$\mathrel{\mathcal{H}}\,=\,\mathrel{\mathcal{L}}\cap\mathrel{\mathcal{R}}$.
Moreover, $s\mathrel{\mathcal{D}}t$ if and only if there exists $x\in S$ such
that $s^{*}s=x^{*}x$ and $tt^{*}=xx^{*}$. For $e,f\in E(S)$ we have
$e\mathrel{\mathcal{D}}f$ if and only if there exists $x\in S$ with $e=x^{*}x$
and $f=xx^{*}$.

A directed graph $\Gamma=(\Gamma^{0},\Gamma^{1},r,s)$ consists of sets
$\Gamma^{0}$, $\Gamma^{1}$ and functions $r,s:\Gamma^{1}\to\Gamma^{0}$ called
the _range_ and _source_ maps, respectively. The elements of $\Gamma^{0}$ are
called _vertices_ , and the elements of $\Gamma^{1}$ are called _edges_. Given
an edge $e$, $r(e)$ denotes the range vertex of $e$ and $s(e)$ denotes the
source vertex. We denote by $\Gamma^{*}$ the collection of finite directed
paths in $\Gamma$. The range and source maps $r,s$ can be extended to
$\Gamma^{*}$ by defining $r(\alpha)=r(\alpha_{n})$ and
$s(\alpha)=s(\alpha_{1})$ for a path
$\alpha=\alpha_{n}\alpha_{n-1}\cdots\alpha_{1}$ in $\Gamma^{*}$. If
$\alpha=\alpha_{n}\alpha_{n-1}\cdots\alpha_{1}$ and
$\beta=\beta_{m}\beta_{m-1}\cdots\beta_{1}$ are paths with
$s(\alpha)=r(\beta)$, we write $\alpha\beta$ for the path
$\alpha_{n}\cdots\alpha_{1}\beta_{m}\cdots\beta_{1}$.

The graph inverse semigroup of the directed graph $\Gamma$ is the set

$S_{\Gamma}=\\{(\alpha,\beta)\in\Gamma^{*}\times\Gamma^{*}:s(\alpha)=s(\beta)\\}\cup\\{0\\}$

with products defined by

$(\alpha,\beta)(\gamma,\nu)=\left\\{\begin{array}[]{ll}(\alpha\gamma^{\prime},\nu)&\mbox{if
$\gamma=\beta\gamma^{\prime}$}\\\ (\alpha,\nu\beta^{\prime})&\mbox{if
$\beta=\gamma\beta^{\prime}$}\\\ 0&\mbox{otherwise}\end{array}\right.$

The inverse is given by $(\alpha,\beta)^{*}=(\beta,\alpha)$.

Let $T$ be an inverse subsemigroup of an inverse semigroup $S$. Lawson [5]
defined $S$ to be an _enlargement_ of $T$ if $STS=S$ and $TST=T$ and made the
case that the concept of enlargement should be part of a larger theory of
Morita equivalence for inverse semigroups. Later, Steinberg [7] developed a
general theory of Morita equivalence of inverse semigroups which is motivated
by similar definitions in the theory of $C^{*}$-algebras and depends on the
notion of a Morita context.

######  Definition 2.1.

A _Morita context_ consists of a 5-tuple $(S,T,X,\langle,\rangle,[,])$ where
$S$ and $T$ are inverse semigroups, $X$ is a set equipped with a left action
by $S$ and a right action by $T$ that commute, and

$\langle\;,\,\rangle:X\times X\to S,\quad[\;,\,]:X\times X\to T$

are surjective functions satisfying the following for $x,y,z$ in $X$, $s$ in
$S$, and $t$ in $T$:

  1. (1)

$\langle sx,y\rangle=s\langle x,y\rangle$,

  2. (2)

$\langle y,x\rangle=\langle x,y\rangle^{*}$,

  3. (3)

$\langle x,x\rangle x=x$,

  4. (4)

$[x,yt]=[x,y]t$,

  5. (5)

$[y,x]=[x,y]^{*}$,

  6. (6)

$x[x,x]=x$, and

  7. (7)

$\langle x,y\rangle z=x[y,z]$.

We say that $S$ and $T$ are _strongly Morita equivalent_ if there exists a
Morita context $(S,T,X,\langle,\rangle,[,])$. There is a useful
characterization of this concept in terms of category equivalence that we will
use in this paper. The _idempotent splitting_ (also called the Cauchy
completion or the Karoubi envelope) of an inverse semigroup $S$ is a category
$C(S)$ with objects $E(S)$ and morphisms $\\{(e,s,f):e,f\in E(S),s\in eSf\\}$.
Composition is given by

$(e,s,f)(f,t,g)=(e,st,g).$

An important subcategory is $L(S)$ which has the same set of objects but only
the morphisms of the form $(f,s,s^{*}s)$ where $ss^{*}\leq f$. Note that $s\in
eSf$ if and only if $ss^{*}\leq e$ and $s^{*}s\leq f$. The isomorphisms in
$C(S)$ (and in $L(S)$) are the elements of the form $(s^{*}s,s,ss^{*})$. It
follows that two objects $e,f\in E(S)$ are isomorphic if and only if
$e\mathcal{D}f$. The following theorem was proved in [4] but also relies on
[7, Corollary 5.2] and results from [3].

######  Theorem 2.2 (Funk, Lawson, Steinberg).

Let $S$ and $T$ be inverse semigroups. The following are equivalent:

  1. (1)

$S$ and $T$ are strongly Morita equivalent.

  2. (2)

The categories $C(S)$ and $C(T)$ are equivalent.

  3. (3)

The categories $L(S)$ and $L(T)$ are equivalent.

We shall say that $S$ and $T$ are _Morita equivalent_ if any of the above
conditions hold. Two Morita equivalent inverse semigroups $S$ and $T$ share a
number of algebraic properties that will be useful in this paper. For example,
given an idempotent $e$ in $S$, there is an idempotent $f$ in $T$ such that
$eSe\cong fTf$ [7]. A semigroup of the form $eSe$ is called a _local
submonoid_ of $S$. If $P$ is some property of inverse semigroups, we say that
_$S$ satisfies $P$ locally_ if $eSe$ satisfies $P$ for each idempotent $e$ in
$S$. We record here a well-known fact about local submonoids.

######  Proposition 2.3.

Suppose $S$ is an inverse semigroup and $e,f$ are idempotents in $S$ such that
$e\mathcal{D}f$. Then there is an isomorphism $\pi:eSe\to fSf$ such that
$s\,\mathcal{D}\,\pi(s)$ for all $s\in eSe$.

###### Proof.

Choose $x$ in $S$ such that $e=x^{*}x$ and $f=xx^{*}$. Then the map
$\pi(s)=xsx^{*}$ satisfies the conclusions of the proposition. ∎

##  3\. Morita Equivalence of Graph Inverse Semigroups

We are interested in determining the collection of inverse semigroups that are
Morita equivalent to graph inverse semigroups. Costa and Steinberg proved that
two graph inverse semigroups are Morita equivalent if and only if the
underlying graphs are isomorphic [1, Corollary 8.5]. This result would seem to
imply that one can recover the directed graph $\Gamma$ from any inverse
semigroup that is Morita equivalent to the graph inverse semigroup
$S(\Gamma)$. We start this section by doing just that. Given an inverse
semigroup $S$ satisfying some additional conditions on the semilattice, we
define a directed graph $\Gamma_{S}$ whose vertices are the nonzero
$\mathcal{D}$-classes of $S$. When $S$ is Morita equivalent to the inverse
semigroup of a directed graph $\Gamma$, $\Gamma_{S}$ is isomorphic to $\Gamma$
(Corollary 3.5). We then use $\Gamma_{S}$ as a tool to characterize those
inverse semigroups that are Morita equivalent to graph inverse semigroups
(Corollary 3.4).

Let $S$ be an inverse semigroup with $0$. Jones and Lawson [6] define $S$ to
be a _Perrot inverse semigroup_ if it satisfies the following properties:

  1. (P1)

The semilattice of idempotents is unambiguous.

  2. (P2)

For each nonzero idempotent $e$ there are finitely many idempotents above $e$
in the natural partial order.

  3. (P3)

$S$ admits unique maximal idempotents.

  4. (P4)

Each nonzero $\mathrel{\mathcal{D}}$-class of $S$ contains a maximal
idempotent.

Also, $S$ is a _proper_ Perrot inverse semigroup if it satisfies the above
properties and, in addition, there is a unique maximal idempotent in any
nonzero $\mathrel{\mathcal{D}}$-class. Jones and Lawson obtained the following
characterization:

######  Theorem 3.1 ([6]).

The graph inverse semigroups are precisely the combinatorial proper Perrot
semigroups.

The semilattice of an inverse semigroup with $0$ is _unambiguous_ if for any
idempotents $e,f$ such that $ef\neq 0$, $e$ and $f$ are comparable in the
natural partial order. Now, if $S$ is Morita equivalent to a graph inverse
semigroup, it must satisfy $(P1)$ locally and $(P2)$ locally. This follows
since any local submonoid of $S$ is isomorphic to some local submonoid of the
graph inverse semigroup. Notice that $S$ satisfies (P1) locally if and only if
for any incomparable elements $e,f$ with $e,f\leq g$ for some $g\in E(S)$,
$ef=0$. Also, one can quickly see that $S$ satisfies $(P2)$ locally if and
only if for any $0\neq e\leq f$, there are finitely many idempotents between
$e$ and $f$. We write $e\ll f$ if and only if $e<f$ and there is no idempotent
$g$ with $e<g<f$.

Let $S$ be an inverse semigroup with zero satisfying (P2) locally. Define a
directed graph $\Gamma_{S}=(\Gamma_{S}^{0},\Gamma_{S}^{1},r,s)$ as follows.
First, let $\Gamma_{S}^{0}$ to be the set of nonzero $\mathcal{D}$-classes of
$S$. Denote by $[f]$ the $\mathcal{D}$-class of an idempotent $f$. Next, for
each $v\in\Gamma_{S}^{0}$, choose a nonzero idempotent $e_{v}\in E(S)$ such
that $v=[e_{v}]$. Since $e_{v}Se_{v}$ satisfies (P2),
$e_{v}^{\downarrow}-\\{e_{v}\\}=\\{f\in E(S):f<e_{v}\\}$ contains a set

$A_{v}=\\{f\in E(S):0\neq f\ll e_{v}\\}$

of nonzero maximal idempotents. Moreover, every nonzero idempotent strictly
below $e_{v}$ lies under some element of $A_{v}$. For each $f\in A_{v}$ we
include an edge $x_{v,f}$ with source $[f]$ and range $v$. That is,

$\Gamma_{S}^{1}=\bigcup_{v\in{\Gamma_{S}^{0}}}\\{x_{v,f}:f\in A_{v}\\}$

and for each $x_{v,f}\in\Gamma_{S}^{1}$, we define $s(x_{v,f})=[f]$ and
$r(x_{v,f})=v$. In this construction we made a choice of representative
$e_{v}$ for each $\mathcal{D}$-class $v$. By Proposition 2.3, the number of
idempotents $f$ with $f\ll e_{v}$ and their corresponding
$\mathcal{D}$-classes are the same regardless of the choice of representative
$e_{v}$. Thus $\Gamma_{S}$ does not depend on the choice of representatives.

Given a combinatorial inverse semigroup $S$ that satisfies (P2) locally, we
define a set $\\{s_{\alpha}:\alpha\in\Gamma_{S}^{*}\\}$ in $S$ as follows:

  1. (1)

$s_{v}:=e_{v}$ for $v\in\Gamma_{S}^{0}$;

  2. (2)

for each edge $x=x_{v,f}$ in $\Gamma_{S}^{1}$, $s_{x}$ is defined to be the
unique element of $S$ such that $s_{x}^{*}s_{x}=e_{[f]}$ and
$s_{x}s_{x}^{*}=f$; and

  3. (3)

for each path $\alpha=x_{1}x_{2}\cdots x_{n}$, define
$s_{\alpha}:=s_{x_{1}}s_{x_{2}}\cdots s_{x_{n}}$.

Also, given a path $\alpha$, define $e_{\alpha}:=s_{\alpha}s_{\alpha}^{*}$.
The following lemma shows that $\\{s_{\alpha}:\alpha\in\Gamma_{S}^{*}\\}$
behaves under multiplication in a way similar to that of a graph inverse
semigroup.

######  Lemma 3.2.

Let $S$ be a combinatorial inverse semigroup that satisfies (P2) locally, let
$\Gamma_{S}$ be the associated directed graph, and let
$\\{s_{\alpha}:\alpha\in\Gamma_{S}^{*}\\}$ be as defined above. For paths
$\mu,\nu,\delta,\epsilon$ such that $s(\mu)=s(\nu)$ and
$s(\delta)=s(\epsilon)$ we have:

$s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*}=\left\\{\begin{array}[]{ll}s_{\mu\delta^{\prime}}s_{\epsilon}^{*}&\mbox{if
$\delta=\nu\delta^{\prime}$}\\\ s_{\mu}s_{\epsilon\nu^{\prime}}^{*}&\mbox{if
$\nu=\delta\nu^{\prime}$}\end{array}\right.$

###### Proof.

First, let $\alpha=x_{1}x_{2}\cdots x_{n}$ be a path where
$x_{i}=x_{v_{i},f_{i}}$ and $v_{i+1}=[f_{i}]$ for $i\leq n-1$. Notice that
$s_{x_{i}}^{*}s_{x_{i}}=e_{[f_{i}]}=e_{v_{i+1}}$. Also, since
$s_{x_{i}}s_{x_{i}}^{*}\leq e_{v_{i}}$ we have
$s_{x_{i}}^{*}e_{v_{i}}s_{x_{i}}=s_{x_{i}}^{*}s_{x_{i}}$ for all $i$. So

$\displaystyle s_{\alpha}^{*}s_{\alpha}$ $\displaystyle=s_{x_{n}}^{*}\cdots
s_{x_{2}}^{*}(s_{x_{1}}^{*}s_{x_{1}})s_{x_{2}}\cdots s_{x_{n}}$
$\displaystyle=s_{x_{n}}^{*}\cdots s_{x_{2}}^{*}(e_{v_{2}})s_{x_{2}}\cdots
s_{x_{n}}$ $\displaystyle=s_{x_{n}}^{*}\cdots(s_{x_{2}}^{*}s_{x_{2}})\cdots
s_{x_{n}}$ $\displaystyle\,\cdots$
$\displaystyle=s_{x_{n}}^{*}s_{x_{n}}=e_{s(\alpha)}$

Now we consider the case where $\delta=\nu\delta^{\prime}$ for some
$\delta^{\prime}$. Then

$s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*}=s_{\mu}s_{\nu}^{*}s_{\nu}s_{\delta^{\prime}}s_{\epsilon}^{*}=s_{\mu}e_{s(\nu)}s_{\delta^{\prime}}s_{\epsilon}^{*}=s_{\mu\delta^{\prime}}s_{\epsilon}^{*}.$

The case where $\nu=\delta\nu^{\prime}$ is similar. ∎

######  Theorem 3.3.

Let $S$ be a combinatorial inverse semigroup with $0$. Also, suppose that $S$
satisfies (P1) locally and (P2) locally. Then $S$ is Morita equivalent to the
graph inverse semigroup of $\Gamma_{S}$.

###### Proof.

Define the graph $\Gamma_{S}$ as above and let $T$ be the graph inverse
semigroup of $\Gamma_{S}$. We will define an equivalence functor $F:C(T)\to
C(S)$ as follows. On objects we define $F((\alpha,\alpha))=e_{\alpha}$ for
each path $\alpha$ and $F(0)=0$. On arrows we let
$F(((\alpha,\alpha),(\mu,\nu),(\beta,\beta)))=(e_{\alpha},s_{\mu}s_{\nu}^{*},e_{\beta})$
and $F(((\alpha,\alpha),0,(\beta,\beta)))=(e_{\alpha},0,e_{\beta})$.

Notice that

$F(((\alpha,\alpha),(\alpha,\alpha),(\alpha,\alpha)))=(e_{\alpha},s_{\alpha}s_{\alpha}^{*},e_{\alpha})=(e_{\alpha},e_{\alpha},e_{\alpha}),$

so $F$ takes identities to identities. Next we verify that $F$ is a functor.
Fix

$A=((\alpha,\alpha),(\mu,\nu),(\beta,\beta))\text{ and
}B=((\beta,\beta),(\delta,\epsilon),(\kappa,\kappa))$

in $C(T)$. We first consider the product
$s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*}$ in $S$. By Lemma 3.2, we have

$s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*}=\left\\{\begin{array}[]{ll}s_{\mu\delta^{\prime}}s_{\epsilon}^{*}&\mbox{if
$\delta=\nu\delta^{\prime}$}\\\ s_{\mu}s_{\epsilon\nu^{\prime}}^{*}&\mbox{if
$\nu=\delta\nu^{\prime}$}\end{array}\right.$

but the lemma does not give the product when the paths $\delta$ and $\nu$ are
incomparable (that is, when neither $\delta=\nu\delta^{\prime}$ nor
$\nu=\delta\nu^{\prime}$). However, since
$(\nu,\nu),(\delta,\delta)\leq(\beta,\beta)$ we have that $r(\nu)=r(\delta)$.
Any paths $\nu$ and $\delta$ with the same range that are incomparable must
diverge after some initial segment $z$. That is $\delta=zxw$ and
$\nu=zx^{\prime}w^{\prime}$ where $z,w,w^{\prime}\in\Gamma_{S}^{*}$ and $x\neq
x^{\prime}$ are distinct edges with $r(x)=r(x^{\prime})$. So in $S$ we have
distinct idempotents $f,f^{\prime}\ll e_{r(x)}$ such that $x=x_{r(x),f}$ and
$x^{\prime}=x_{r(x),f^{\prime}}$. Notice that

$e_{z}=s_{z}e_{r(x)}s_{z}^{*},\,e_{zx}=s_{z}s_{x}s_{x}^{*}s_{z}^{*}=s_{z}fs_{z}^{*},\,\text{and
}e_{zx^{\prime}}=s_{z}f^{\prime}s_{z}^{*}.$

Thus we have $e_{zx},e_{zx^{\prime}}\ll e_{z}$ and $e_{zx}\neq
e_{zx^{\prime}}$. So $e_{zx},e_{zx^{\prime}}$ are incomparable idempotents in
$e_{z}Se_{z}$. Since $S$ is locally (P1), $e_{zx}e_{zx^{\prime}}=0$. Since
$e_{\nu}\leq e_{zx^{\prime}}$ and $e_{\delta}\leq e_{zx}$ we have that
$e_{\nu}e_{\delta}=0$ and $s_{\nu}^{*}s_{\delta}=0$. Thus:

$s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*}=\left\\{\begin{array}[]{ll}s_{\mu\delta^{\prime}}s_{\epsilon}^{*}&\mbox{if
$\delta=\nu\delta^{\prime}$}\\\ s_{\mu}s_{\epsilon\nu^{\prime}}^{*}&\mbox{if
$\nu=\delta\nu^{\prime}$}\\\ 0&\mbox{otherwise}\end{array}\right.$

It follows that

$\displaystyle F(A)F(B)$
$\displaystyle=(e_{\alpha},s_{\mu}s_{\nu}^{*},s_{\beta}s_{\beta}^{*})(s_{\beta}s_{\beta}^{*},s_{\delta}s_{\epsilon}^{*},e_{\kappa})$
$\displaystyle=(e_{\alpha},s_{\mu}s_{\nu}^{*}s_{\delta}s_{\epsilon}^{*},e_{\kappa})$
$\displaystyle=F(((\alpha,\alpha),(\mu,\nu)(\delta,\epsilon),(\kappa,\kappa)))$
$\displaystyle=F(AB)$

So $F$ is a functor. Next we check that $F$ is faithful. Suppose that

$(e_{\alpha},s_{\mu}s_{\nu}^{*},e_{\beta})=(e_{\alpha},s_{\delta}s_{\epsilon}^{*},e_{\beta})$

where $(\mu,\mu),(\delta,\delta)\leq(\alpha,\alpha)$ and
$(\nu,\nu),(\epsilon,\epsilon)\leq(\beta,\beta)$. Then
$\delta=\alpha\delta^{\prime}$ and $\mu=\alpha\mu^{\prime}$ for some paths
$\delta^{\prime},\mu^{\prime}$ in $\Gamma_{S}^{*}$. Also
$e_{\mu}=s_{\mu}s_{\nu}^{*}s_{\nu}s_{\mu}^{*}=s_{\delta}s_{\epsilon}^{*}s_{\epsilon}s_{\delta}^{*}=e_{\delta}$.
Thus $e_{\mu}=e_{\delta}\leq e_{\alpha}$. We claim that $\mu=\delta$. If not,
then we can write $\mu=\alpha zx^{\prime}w^{\prime}$ and
$\delta^{\prime}=\alpha zxw$ where $z,w,w^{\prime}\in\Gamma_{S}^{*}$ and
$x,x^{\prime}$ are distinct edges. But then $e_{\alpha zx^{\prime}},e_{\alpha
zx}\ll e_{\alpha z}$, so that $e_{\alpha zx^{\prime}},e_{\alpha zx}$ are
incomparable. As before, since $S$ satisfies (P1) locally, this implies
$e_{\mu}e_{\delta}=0$, a contradiction. Thus $\mu=\delta$. Similarly,
$\nu=\epsilon$. Thus $F$ is faithful.

Next we show that $F$ is full. To this end consider an element of $C(S)$ of
the form $(e_{\alpha},s,e_{\beta})$. We have $ss^{*}\leq e_{\alpha}$. As $S$
is locally (P2), there are finitely many idempotents between $ss^{*}$ and
$e_{\alpha}$. Thus there is a path $\mu$ such that $\mu=\alpha\mu^{\prime}$
for some path $\mu^{\prime}$ and $ss^{*}=e_{\mu}$. Similarly, $s^{*}s=e_{\nu}$
for some path $\nu=\beta\nu^{\prime}$. As $S$ is combinatorial,
$s=s_{\mu}s_{\nu}^{*}$. Thus

$(e_{\alpha},s,e_{\beta})=F(((\alpha,\alpha),(\mu,\nu),(\beta,\beta))).$

Finally, we show that $F$ is essentially surjective on objects. Let $e\in
E(S)$ be nonzero. Then $v=[e]\in\Gamma_{S}^{0}$ is a vertex. Thus $(v,v)\in
E(T)$ and $e\mathcal{D}e_{v}=F((v,v))$. ∎

As discussed at the beginning of this section, any inverse semigroup that is
Morita equivalent to a graph inverse semigroup satisfies (P1) and (P2)
locally. Such semigroups must also be combinatorial and contain a zero by [7,
Corollary 5.2]. Thus we have obtained the following characterization:

######  Corollary 3.4.

An inverse semigroup $S$ is Morita equivalent to a graph inverse semigroup if
and only if $S$ is combinatorial, has a $0$, satisfies (P1) locally, and
satisfies (P2) locally.

Also we point out that the graph $\Gamma_{S}$ associated with $S$ is unique up
to isomorphism.

######  Corollary 3.5.

Let $S$ be an inverse semigroup that is Morita equivalent to the graph inverse
semigroup $S_{\Gamma}$. Then $\Gamma_{S}$ is isomorphic to $\Gamma$.

###### Proof.

By Theorem 3.3, $S_{\Gamma_{S}}$ is Morita equivalent to $S_{\Gamma}$. Thus by
[1, Corollary 8.5] we have $\Gamma_{S}$ isomorphic to $\Gamma$. ∎

##  4\. Path Categories

In this section we consider a generalization of graph inverse semigroups to
those semigroups associated with left cancellative categories. The case was
made in [2] that the path category plays a role similar to that of the paths
in the directed graph for inverse semigroups that admit unique maximal
idempotents. To what extent do the results in the previous section extend to
these inverse semigroups? In fact, every inverse semigroup with $0$ is Morita
equivalent to an inverse semigroup satisfying (P3) and (P4) [2, Corollary
6.2]. Also, any semigroup satisfying (P3) and (P4) is isomorphic to the
canonical inverse semigroup associated with its path category. Thus Corollary
3.4 has the rather decisive (if boring) generalization that every inverse
semigroup is Morita equivalent to an inverse semigroup associated with a left
cancellative category. It is interesting to determine whether the path
category alone can be used to characterize Morita equivalence for such
semigroups.

If $S$ is an inverse semigroup satisfying (P3), then for each nonzero
idempotent $e$ there is a unique maximal idempotent $e^{\circ}$ such that
$e\leq e^{\circ}$. We recall the definition of the path category $P(S)$ from
[2]. The objects are the maximal idempotents of $S$. The arrows in $P(S)$ are
the pairs $(e,s)$ such that $s^{*}s$ is maximal and $({ss^{*}})^{\circ}=e$.
Composition is given by

$(e,s)(f,t)=(e,st)$

provided $s^{*}s=f$.

######  Proposition 4.1.

Suppose $S$ is an inverse semigroup with $0$ satisfying (P3) and (P4). Then
$P(S)$ is equivalent to $L(S)$.

###### Proof.

It is straightforward to verify that $P(S)$ embeds in $L(S)$ as the
subcategory of triples $(e,s,s^{*}s)$ where $e$ and $s^{*}s$ are maximal
idempotents. As remarked earlier, two objects $e,f$ in $L(S)$ are isomorphic
if and only if $e\mathcal{D}f$. Therefore, by (P4), the inclusion of $P(S)$
into $L(S)$ is an equivalence of categories. ∎

Thus we quickly derive the following corollary as a consequence of the result
of Funk, Lawson, and Steinberg (see Theorem 2.2).

######  Corollary 4.2.

Suppose $S$ and $T$ are inverse semigroups with $0$ satisfying (P3) and (P4).
Then $S$ is Morita equivalent to $T$ if and only if $P(S)$ is equivalent to
$P(T)$.

## References

  * [1] Alfredo Costa and Benjamin Steinberg, _A categorical invariant of flow equivalence of shifts_ , Ergodic Theory Dynam. Systems 36 (2016), no. 2, 470–513.
  * [2] Allan Donsig, Jennifer Gensler, Hannah King, David Milan, and Ronen Wdowinski, _On zigzag maps and the path category of an inverse semigroup_ , Semigroup Forum 100 (2020), no. 3, 790–805.
  * [3] Jonathon Funk, _Semigroups and toposes_ , Semigroup Forum 75 (2007), no. 3, 481–520.
  * [4] Jonathon Funk, Mark V. Lawson, and Benjamin Steinberg, _Characterizations of morita equivalent inverse semigroups_ , J. Pure and Appl. Algebra 215 (2011), no. 9, 2262–2279.
  * [5] Mark V. Lawson, _Enlargements of regular semigroups_ , Proc. Edinb. Math. Soc. (2) 39 (1996), no. 3, 425–460.
  * [6] Mark V. Lawson and David G. Jones, _Graph inverse semigroups: their characterization and completion_ , J. Algebra (2014), 444–473.
  * [7] B. Steinberg, _Strong Morita equivalence of inverse semigroups_ , Houston J. Math. 37 (2011), no. 3, 895–927.


# Reviving Shift Equivariance in Vision Transformers

Peijian Ding
University of Maryland
<EMAIL_ADDRESS>
&Davit Soselia
University of Maryland
<EMAIL_ADDRESS>
&Thomas Armstrong
University of Maryland
<EMAIL_ADDRESS>
&Jiahao Su
University of Maryland
<EMAIL_ADDRESS>
&Furong Huang
University of Maryland
<EMAIL_ADDRESS>

###### Abstract

Shift equivariance is a fundamental principle that governs how we perceive the
world — our recognition of an object remains invariant with respect to shifts.
Transformers have gained immense popularity due to their effectiveness in both
language and vision tasks. While the self-attention operator in vision
transformers (ViT) is permutation-equivariant and thus shift-equivariant,
patch embedding, positional encoding, and subsampled attention in ViT variants
can disrupt this property, resulting in inconsistent predictions even under
small shift perturbations. Although there is a growing trend in incorporating
the inductive bias of convolutional neural networks (CNNs) into vision
transformers, it does not fully address the issue. We propose an adaptive
polyphase anchoring algorithm that can be seamlessly integrated into vision
transformer models to ensure shift-equivariance in patch embedding and
subsampled attention modules, such as window attention and global subsampled
attention. Furthermore, we utilize depth-wise convolution to encode positional
information. Our algorithms enable ViT, and its variants such as Twins to
achieve 100% consistency with respect to input shift, demonstrate robustness
to cropping, flipping, and affine transformations, and maintain consistent
predictions even when the original models lose 20 percentage points on average
when shifted by just a few pixels with Twins’ accuracy dropping from 80.57% to
62.40%.

##  1 Introduction

Inductive bias refers to a set of assumptions or beliefs that guide the design
of machine learning algorithms, aiming to reduce the search space for an
optimal model. Humans possess the remarkable ability to perceive and recognize
objects despite variations such as deformations, occlusions, and translations.
The success of convolutional neural networks (CNNs) can be attributed to their
inductive bias of shift equivariance, which allows them to mimic this human
ability. For instance, when we observe an image of a cat, shifting the cat’s
position within the image does not affect our recognition of the cat, and we
remain aware of the shift that has occurred.

Transformers have emerged as strong alternatives to CNNs in computer vision,
and their success in natural language processing further highlights their
potential as a research area. A key element of transformers is the self-
attention module, which exhibits permutation-equivariance. However, despite
this strong inductive bias, vision transformers are neither shift-equivariant
nor permutation-equivariant. This is due to the patch embedding, positional
embedding, and subsampled attention (in the case of ViT variants), which
disrupt shift equivariance as input shifts lead to different pixels within
each image patch or different tokens in each window, resulting in different
computations.

Integrating CNNs with vision transformers can partially address the lack of
shift equivariance, but it does not fully resolve the issue. The original
design of vision transformers already incorporates convolution within its
architecture; the patch embedding layer is functionally equivalent to strided
convolution, but its downsampling operation disrupts shift equivariance.
Although CoAtNet proposes a relative attention method that combines depthwise
convolution with attention to achieve shift equivariance, this approach still
requires computing full global attention, and shift equivariance is not
maintained when downsampled attention is required for computational efficiency
[3, 13, 7]. Both MaxViT [13] and Twins transformer [3] utilize depth-wise
convolution to encode positional information, but their block attention (or
window attention) and strided convolution are not shift equivariant.

In this work, we seek to explicitly incorporate the inductive bias of CNNs
into vision transformers, fully addressing the issue of shift equivariance. We
achieve this by introducing replaceable modules that enable a wide range of
vision transformer models to be shift-equivariant [9, 8, 3, 13, 4, 14, 16].
Our proposed solution is a nonlinear operator — the polyphase anchoring
algorithm. By consistently selecting the maximum polyphase as anchors for
computing strided convolution and subsampled attentions, we ensure shift
equivariance. Furthermore, we employ depthwise convolution with circular
padding to encode positional information, as opposed to using the absolute
positional embedding in Dosovitskiy et al. [9] or the relative positional
embedding in Liu et al. [11, 12], which are not shift equivariant.

Figure 1: The maximum polyphase is colored in blue. Each shape with distinct
color represents a token. We also illustrate the concept of _anchors_ — the
top left coordinate in each window. The red and yellow shapes indicate that
window attention produces inconsistent predictions on shifted image whereas
the composition of polyphase anchoring and window attention does not.

Our primary contributions in this work are as follows:

  * •

We present versatile and adaptable modules that seamlessly integrate with
vision transformer models, leading to improved performance in vision
transformer models.

  * •

Our innovative approach incorporates an input-adaptive nonlinear operator that
guarantees shift-equivariance, resulting in more robust and reliable outcomes
across a range of visual tasks.

  * •

We equip vision transformers with complete shift-equivariance capabilities,
substantiating our approach with both theoretical geometric guarantees and
empirical evidence that underscore its effectiveness and practical
applicability.

##  2 Preliminaries

To effectively restore shift-equivariance in vision transformers, it is
necessary to examine each individual module and identify the components
responsible for disrupting the shift-equivariance property. To achieve this,
we must first establish formal definitions for equivariance and self-
attention.

###  2.1 Equivariance

Equivariance serves as a formal concept of consistency under transformations
[10]. A function $f:V_{1}\to V_{2}$ is considered equivariant to
transformations from a symmetry group $G$ if applying the symmetry to the
input of $f$ produces the same result as applying it to the output:

$\displaystyle\forall g\in G:f(g\cdot x)=g^{\prime}\cdot f(x)$ (1)

Here, $\cdot$ denotes the linear mapping of the input by the representation of
group elements in $G$. Throughout this paper, all instances of $\cdot$ adhere
to this definition. When $g=g^{\prime}$, the function is referred to as
G-equivariant. If $g^{\prime}$ is the identity, the function is G-invariant.
For cases where $g\neq g^{\prime}$, the function is considered generally
equivariant. General equivariance is a valuable concept when the input and
output spaces have different dimensions. When $G$ represents the translation
group, the above definition yields shift-equivariance.

###  2.2 Self-attention

A self-attention operator $A_{s}$ exhibits permutation-equivariance. Let $X$
represent the input matrix, and $T_{\pi}$ denote any spatial permutation. We
can express this as:

$\displaystyle A_{s}(T_{\pi}(X))=T_{\pi}(A_{s}(X)).$ (2)

$A_{s}$ is the self-attention operator with parameter matrices
$W_{q}\in\mathbb{R}^{d\times d_{k}}$, $W_{k}\in\mathbb{R}^{d\times d_{k}}$,
and $W_{v}\in\mathbb{R}^{d\times d_{v}}$:

$\displaystyle
A_{s}=\text{SoftMax}(XW_{q}(XW_{k})^{T})XW_{v}=\text{SoftMax}(QK^{T})V.$ (3)

##  3 Approach

To achieve model-wise shift-equivariance, we first detect the modules that
lack shift equivariance. We then introduce a polyphase anchoring algorithm to
ensure shift-equivariance for strided convolution, window attention, and
global subsampled attention. Finally, we use depthwise convolution with
circular padding to guarantee shift-equivariance in positional encoding. As
the composition of shift-equivariant functions remains shift-equivariant, we
obtain a shift-equivariant model.

###  3.1 Detecting modules lacking shift equivariance

Vision transformers consist of a patch embedding layer, positional encoding,
transformer blocks, and MLP layers. We analyze each of these modules in ViT
and its variants, discovering the following:

  * •

Patch embedding layer (strided convolution) is not shift-equivariant due to
downsampling.

  * •

Absolute positional encoding [9] and relative positional embedding [11, 12]
are not shift-equivariant.

  * •

Normalization, global self-attention, and MLP layers are shift-equivariant.

  * •

Subsampled attentions such as window attention [11, 12, 13, 3] and global
subsampled attention [3] are not shift-equivariant.

##### Patch embedding

converts image patches into sequence vector representations through strided
convolution. However, strided convolution is not shift-equivariant due to
downsampling, as addressed by Zhang [17], Chaman and Dokmanic [2]. Figures 1
illustrate that the image patching layer, or strided convolution, is not
shift-equivariant. When an image is shifted by a pixel, the pixels in each
window change, leading to different computations.

##### Positional encoding

is a method for incorporating spatial location information into tokens, the
representations of input image patches. Popular positional encoding techniques
such as absolute positional encoding in ViT [9] and relative positional
encoding in Swin [11, 12] are not shift-equivariant. Absolute positional
encoding [9] adds the absolute positional information to input tokens by
considering an input image as a sequence or a grid of patches [9, 14].
Trivially, absolute positional embedding is not shift-equivariant because the
same absolute positional information is added to the input tokens regardless
of shift, as shown in Figure 2 The relative positional embedding introduced by
Liu et al. [11] is the following:

$\text{Attention}(Q,K,V)=\text{SoftMax}(\frac{QK^{T}}{\sqrt{d}}+B)V,$ (4)

where $B\in R^{M^{2}\times M^{2}}$ is the relative position bias term for each
head; $Q,K,V\in R^{M^{2}\times d}$ are the query, key and value matrices; $d$
is the query/key dimension, and $M^{2}$ is the number of patches in a window.
Although self-attention is permutation equivariant, self-attention with
relative position bias is not shift-equivariant. Further mathematical
deductions are provided in the Appendix.

##### Normalization layers

standardize the input data or activations of preceding layers to stabilize
training and enhance model performance by ensuring consistent scales and
distributions. Both batch normalization and layer normalization are shift-
equivariant. Trivially, normalizing a shifted input along batch and feature
dimensions is equivalent to shifting the normalized input.

MLP layers, or Multi-Layer Perceptron layers, are a sequence of feedforward
neural network layers that perform a linear transformation followed by a non-
linear activation function. An MLP layer is shift-equivariant. In layer $l$ of
an MLP model, we have:

$\displaystyle h^{(l)}=\phi(xW^{(l)}+b^{(l)})$ (5)

where $x$ is a row vector, $W$ is a weight matrix, and $b$ is a bias term.
Given an input matrix $X$ whose row vectors are tokens, it is obvious that the
MLP layer is shift equivariant with respect to input tokens.

In the ViT architecture, we have identified that MLP layers and normalization
layers are shift-equivariant, while patch embedding and positional encoding
are not. ViT variants [11, 12, 4, 8, 14, 13] introduce additional challenges
for shift-equivariance, as they typically employ subsampled attention
operations to reduce the quadratic computational complexity with respect to
the number of tokens in global self-attention.

Figure 2: The left figure illustrates that the identical absolute positional
encoding is applied to both the input and its circularly shifted counterpart,
resulting in a lack of shift-equivariance. The right figure highlights that,
in the context of ViT, patch embedding and positional encoding do not exhibit
shift-equivariant properties.

s

##### Subsampled attentions

are streamlined versions of global self-attentions that can be classified into
two categories: local and global [11, 12, 3, 16, 13]. Local attention is
typically employed in conjunction with subsampled global attention to encode
substantial spatial information while avoiding excessive computational costs
[13, 3, 4, 16]. However, the use of subsampled attentions often results in a
lack of shift-equivariance due to downsampling. Consequently, addressing the
shift-equivariance issue in these subsampled attentions is crucial.

The most prevalent local attention mechanism is window attention, while a
popular subsampled global attention variant is the global subsampled self-
attention (GSA) introduced by Chu et al. [3]. To directly tackle the lack of
shift-equivariance, we propose the polyphase anchoring algorithm as a
solution. This approach is designed to maintain spatial information while
reducing computational complexity, thus promoting shift-equivariance in
subsampled attention mechanisms.

###  3.2 Polyphase anchoring algorithm

####  3.2.1 Introduction

Inspired by the concept of adaptive polyphase sampling presented in Chaman and
Dokmanic [2], we propose the polyphase anchoring algorithm, an efficient
technique that can be seamlessly integrated with various types of subsampled
attention operators [13, 3, 11, 12, 8, 7] to ensure shift-equivariance. The
algorithm is implemented as an autograd function in PyTorch, making it simple
to incorporate into deep learning models.

Polyphase anchoring identifies the maximum $L_{p}$ norm polyphase and shifts
the input accordingly, so that the maximum polyphase aligns with the anchor
positions of window attention, as illustrated in Figure 1. _Anchors_ of window
attention represent the set of coordinates at the top-left of each window, as
depicted in Figure 1.

$\displaystyle\text{anchors}=\\{(i,j)\mid i\equiv 0\pmod{s},\quad j\equiv
0\pmod{s},\quad i\leq H,j\leq W,i,j\in\mathbb{Z}\\}.$ (6)

Here, $s\times s$ denotes the size of the window in window attention, $(i,j)$
is a coordinate on a 2D grid.

Algorithm 1 demonstrates polyphase ordering. For the brevity in Algorithm 1,
we define the polyphase $X_{pq}$ mathematically here. Let $S_{pq}$ be some
polyphase whose first element is at coordinate $(p,q)$ on the 2D grid,
$S_{pq}=\\{(i+p,j+q)\mid i\equiv 0\pmod{s},\quad j\equiv 0\pmod{s}\quad i\leq
H,j\leq W,i,j\in\mathbb{Z}\\}$. Let $X_{pq}$ be all the tokens on the
polyphase $S_{pq}$. $X_{pq}=\\{x=f(m,n)\in\mathbb{R}^{C}\mid\forall(m,n)\in
S_{pq}\\}$, where $(m,n)$ is a coordinate of some token in $S_{pq}$ and $f$ is
a mapping from a coordinate to its corresponding token.

Algorithm 1 Polyphase anchoring

1: Input $X\in R^{...\times H\times W}$, stride size $s\in\mathbb{Z}$

2: Maximum polyphase is $\hat{X}_{pq}=\arg\max_{X_{pq}\mid
p,q\in\\{0,\dots,s-1\\}}||X_{pq}||$

3: $\hat{X}=g_{pq}\cdot(X)$ where $g_{pq}$ circularly shifts $X$ by $(-p,-q)$
along the last two dimensions.

4: Output: $\hat{X}$

The polyphase anchoring algorithm is a nonlinear operator that conditionally
shifts the input based on its maximum $L_{p}$ norm polyphase. This guarantees
shift-equivariance in strided convolution, subsampled attention like window
attention, and GSA. As a result, the lack of shift-equivariance in patch
embedding modules and subsampled attention modules in ViT variants, such as
Twins [3], is addressed.

######  Lemma 3.1.

Polyphase anchoring operator $P$ is general equivariant with respect to
$\forall g\in G$, where G is the symmetry group of translations, and $P:V\to
V$ is a nonlinear operator that conditionally shift the input $X$. $\forall
g\in G$, $\exists g^{\prime}\in G$ s.t:

$P(g\cdot X)=g^{\prime}\cdot P(X)$ (7)

######  Corollary 3.1.

$P(g\cdot X)=g^{\prime}\cdot P(X)$ where $g^{\prime}$ translates $P(X)$ by an
integer multiple of stride size $s$. Stride size is the distance between two
consecutive tokens in the same polyphase on a 2D grid.

####  3.2.2 Addressing Shift Equivariance in Patch Embedding and Subsampled
Attention

As discussed in Section 3.1, strided convolution and subsampled attention
methods, such as window attention and GSA, inherently lack shift equivariance.
To tackle this issue, we employ the polyphase anchoring algorithm, which
conditionally shifts the input based on the maximum polyphase, ensuring shift-
equivariance in these modules.

Utilizing Lemma 3.1, which establishes that polyphase anchoring is generally
shift-equivariant, i.e., $P(g\cdot X)=g^{\prime}\cdot P(X)$, and Corollary
3.1, which states that $g^{\prime}$ translates $P(X)$ by an integer multiple
of stride size $s$, _we show that the composition of polyphase anchoring with
strided convolution, window attention, and global subsampled attention results
in shift-equivariant operations_. Consequently, we effectively address the
lack of shift equivariance in patch embedding modules and subsampled attention
modules for ViT variants such as Twins [3]. Detailed proofs are provided in
Appendix.

######  Lemma 3.2.

Let $P$ be the polyphase anchoring operator and $\ast_{s}$ represent the
strided convolution operator. $\forall g\in G$, where $G$ is the translation
group, and $\forall s_{1},s_{2}\in\mathbb{Z}$ s.t $s_{1}=s_{2}$, where $s_{1}$
is the stride size in the polyphase and $s_{2}$ is the stride size of
convolution, the composition of strided convolution and polyphase anchoring is
general shift-equivariant:

$\displaystyle P(g\cdot X)\ast_{s}h=g^{\prime}\cdot(P(X)\ast_{s}h)$ (8)

Here, $X$ denotes the input signal, $h$ is the convolution filter, and $\cdot$
signifies the linear mapping of the input by the representation of group
elements in $G$. Furthermore, $P:V\to V$ is a nonlinear operator acting on the
input space $V$.

######  Lemma 3.3.

Given a window attention operator $A_{w}$ and polyphase anchoring operator
$P$, the composition of these operators is general shift-equivariant $\forall
g\in G$, where $G$ is the translation group, and for $s,w\in\mathbb{Z}$ such
that $s=w$, where $s$ is the stride size in the polyphase and $w\times w$ is
the window size. This can be expressed as:

$A_{w}(P(g\cdot X))=g^{\prime}\cdot A_{w}(P(X))$ (9)

In the window attention operator $A_{w}$, we have:

$A_{w}(X)=\left[\begin{array}[]{ccc}A_{s}(X_{00})&\cdots&A_{s}(X_{0n})\\\
\vdots&\vdots&\vdots\\\ A_{s}(X_{m0})&\cdots&A_{s}(X_{mn}),\end{array}\right]$
(10)

where $A_{s}$ is the self-attention operator defined in section 2.2, and
$X_{ij}$ contains all the tokens in a window.

######  Lemma 3.4.

For a global subsampled attention operator $A_{g}$ [3] combined with a
polyphase anchoring operator $P$, general shift-equivariance is achieved for
$\forall g\in G$, where $G$ is the translation group, and for
$s_{1},s_{2}\in\mathbb{Z}$ such that $s_{1}=s_{2}$. Here, $s_{1}$ is the
stride size in the polyphase, and $s_{2}$ is the stride size in the global
subsampled attention. This can be expressed as:

$A_{g}(P(g\cdot X))=g^{\prime}\cdot A_{g}(P(X))$ (11)

In global subsampled attention, we have:

$A_{g}(X)=\text{SoftMax}(QK_{s}^{T})V_{s},$ (12)

where $K_{s}$ and $V_{s}$ are subsampled from the full keys $K$ and values $V$
using strided convolution.

###  3.3 Positional Embedding

Positional embedding is another factor that can cause models to lose shift-
equivariance. As demonstrated previously, both absolute positional embedding
[9] and relative positional embedding [11, 12] are not shift-equivariant.
However, the conditional positional embedding introduced by Chu et al. [4]
promotes shift-equivariance by employing zero-padded depthwise convolution to
encode positional information. By replacing positional encoding with
circularly-padded depthwise convolution, we achieve shift-equivariance.

Formally, given an input tensor $\mathbf{X}$ of shape
$(C_{\text{in}},H_{\text{in}},W_{\text{in}})$ and a set of depthwise filters
$\mathbf{W}=\\{W_{1},W_{2},\ldots,W_{C_{\text{in}}}\\}$ of size
$(C_{\text{in}},k,k)$, where $C_{\text{in}}$ denotes the number of input
channels and $k$ represents the kernel size, the depthwise convolution
operation can be defined as:

$\mathbf{Y}_{i}=W_{i}\odot\mathbf{X}_{i},\quad\forall
i\in\\{1,2,\ldots,C_{\text{in}}\\}$ (13)

Here, $\mathbf{X}_{i}$ denotes the $i$-th input channel, $\mathbf{Y}_{i}$
represents the corresponding output channel, and $\odot$ denotes the standard
convolution operation. Assuming circular padding, convolution at each channel
is shift-equivariant, making depthwise convolution shift-equivariant as well.
Since CNNs utilize convolution to encode positional information, it is
plausible that transformers can also employ depthwise convolution to encode
information, as demonstrated in [5, 4].

By ensuring shift-equivariance in patch embedding, positional embedding, and
subsampled attention (in the case of ViT variants), we can achieve a truly
shift-equivariant model. Furthermore, by incorporating a shift-invariant
pooling operation in the classification head, we can obtain a truly shift-
invariant model.

##  4 Experiments

In this section, we demonstrate that we can construct a $100\%$ truly shift-
equivariant ViT using adaptive polyphase anchoring and positional embedding.
Additionally, we show that we can make the Twins transformer [3] truly shift-
equivariant, a vision transformer variant that incorporates two types of
attention modules—window attention and global subsampled self-attention.
Models employing our algorithm exhibit superior accuracy in fair comparisons,
improved robustness under shifting, cropping, flipping, and random patch
erasing, 22.4% relative percentage point gain (or 41.6% increase) from ViT
small under worst-of-30 shift attack, and 100% consistency under shift
attacks.

###  4.1 Classification Accuracy and Consistency on ImageNet-1k

##### Settings.

We evaluate six architectures, including ViT base, ViT small, Twins [3] base,
and their shift-equivariant counterparts using polyphase anchoring on
ImageNet-1k, which contains 1.28M training images and 50K validation images
from 1,000 classes. For simplicity, we refer to ViT and Twins using polyphase
anchoring and circular depthwise convolution as ViT-poly and Twins-poly. There
are two types of Twins models introduced by Chu et al. [3], and we default
Twins to Twins-svt because it demonstrates superior performance.

##### Training.

To ensure fair comparisons, we conduct a controlled experiment by training
each model and its polyphase counterpart with the same hyperparameters from
scratch on ImageNet-1k. All training instances involve using the same data
augmentation strategy.

##### Evaluation.

We measure performance using accuracy, consistency, and accuracy under small
random shift from 0 to 15 pixels. Consistency [2] measure the likelihood of
the model assigning the image and its shifted copy to the same class.

##### Results.

Table 1 shows the comparison of ViT and Twins transformer models against its
shift equivariant counterpart using models training from scratch with exactly
the same hyperparameters. Poly version models demonstrate comparable raw
accuracy, superior accuracy under random shifts, and 100% consistency.

Table 1: ImageNet1K training from scratch Model | image size | #param. | Epochs | Acc. IN1K | Consis. | Acc. Rand. S
---|---|---|---|---|---|---
ViT_S | $224^{2}$ | 22M | 300 | 75.52 | 86.61 | 74.98
ViT_S-poly | $224^{2}$ | 22M | 300 | 76.37 | 100 | 76.37
ViT_B | $224^{2}$ | 87M | 300 | 73.85 | 85.60 | 73.01
ViT_B-poly | $224^{2}$ | 86M | 300 | 74.62 | 100 | 74.62
Twins_B | $224^{2}$ | 56M | 300 | 80.57 | 91.25 | 79.90
Twins_B-poly | $224^{2}$ | 56M | 300 | 80.59 | 100 | 80.59

###  4.2 Robustness tests on ImageNet 1k

##### Settings.

We assess the robustness of the models trained from scratch in Section 4.1
under various types of transformations, using ImageNet-1K for our experiments.

##### Evaluations.

We evaluate the accuracy and consistency of the models under random cropping,
horizontal flipping, random patch erasing, and random affine transformations.
Additionally, we perform a worst-of-N shift attack for each batch of images,
we keep the shift within a small range of $(-15,15)$ range, to keep it
inconsequential to human perception, and use the worst-case shift from the
grid search.

Some of these metrics, especially the worst-of-N shift are sensitive to the
batch size used since the worst shift is chosen per batch. We use a batch size
of 64 for all metrics and additionally evaluate worst-of-30 with a batch size
of 1 for 2000 samples to show the lowest performance.

##### Results.

As shown in Table 2, ViT_B-poly and ViT_S-poly obtain comparable or better
accuracy than their respective counterparts, ViT_B and ViT_S, under all
considered transformations. Under the worst-of-k shift attack, our models
achieve 100% consistency and significantly improved accuracy, while having
slight-to-high gains on the other transformations.

Table 2: Robustness experiments on ImageNet1K Model | Acc. Crop | Acc. Flip | Acc. Affine | Worst-of-30 Batch 1 | Worst-of-30
---|---|---|---|---|---
ViT_S | 75.09 | 75.50 | 69.85 | 53.80 | 68.90
ViT_S-poly | 76.08 | 76.34 | 69.54 | 76.20 | 76.02
ViT_B | 73.31 | 73.83 | 68.64 | 53.20 | 67.42
ViT_B-poly | 74.36 | 74.64 | 70.46 | 74.40 | 74.20
Twins_B | 80.51 | 80.60 | 75.88 | 62.40 | 73.86
Twins_B-poly | 80.43 | 80.56 | 76.12 | 80.78 | 80.78

###  4.3 Stability and shift-equivariance tests on ImageNet-1K

##### Settings.

We measure stability of output logits under small shifts as well as shift
equivariance in the feature space using models trained from scratch in 4.1.

##### Output logits variance

measures the variability of the model’s logits predictions with respect to a
range of small random shifts from -5 to 5. It quantifies the spread or
dispersion of the logits ($L$) as a function of the input shift.
Mathematically, the output logits variance can be calculated as follows:

$\text{{Variance}}=\frac{1}{N}\sum_{i=1}^{N}\left(L(x_{i})-\bar{L}\right)^{2}$
(14)

where Variance represents the output logits variance, $N$ is the total number
of samples, $x_{i}$ denotes the input sample, $L(x_{i})$ corresponds to the
logits prediction for the input $x_{i}$, $\bar{L}$ represents the mean logits
prediction for the given range of input shifts, the range of input shifts from
-5 to 5 is denoted as $\Delta x$. As demonstrated in Figure 3, the output
logits variance concerning small shift perturbations is almost zero for
ViT_S/16-poly and Twins_B-poly, indicating that the output logits remain
unchanged under small input shifts. Conversely, the output logits variance is
nonzero for nearly 50% of the input images, suggesting that the model’s
assigned probability for the input label alters in response to minor pixel
shifts.

Figure 3: The top figures display the output logits variance for ViT_S,
Twins_B, and their shift-equivariant counterparts, while the bottom figures
provide a comparison of shift-equivariance tests between ViT_S, Twins_B, and
their respective shift-equivariant versions.

##### Shift-equivariance tests

are unit tests that measure if the features are shift-equivariant. Let
$\mathcal{M}$ be a machine learning model that takes an input $\mathbf{X}$ and
produces a feature map $\mathbf{F}=\mathcal{M}(\mathbf{X})$. For a given
translation $g\in G$, define the shifted input $\mathbf{X}^{\prime}$ as
$\mathbf{X}^{\prime}=g\cdot\mathbf{X}$. Let
$\mathbf{F}^{\prime}=\mathcal{M}(\mathbf{X}^{\prime})$ be the feature map
obtained by applying the model to the shifted input. The feature shift-
equivariance test can be defined as follows:

$\text{shift-equivariance}(\mathcal{M})=\begin{cases}0,&\text{if
}\mathbf{F}^{\prime}=g^{\prime}\cdot\mathbf{F}\\\
\|\mathbf{F}^{\prime}-\mathbf{F}\|,&\text{otherwise}\end{cases}$ (15)

where $g^{\prime}\in G$ is translation in the feature space, $\|\cdot\|$ is
$L_{2}$ norm. As demonstrated in Figure 3, both the polyphase models of ViT
and Twins successfully pass all shift equivariance tests in the feature space,
while the original ViT and Twins models fail to do so and exhibit substantial
norm differences in the feature space.

##  5 Related Work

##### Data augmentation

encourages shift-equivariance by adding shifted copies of images to the
training set but lacks guarantees. In CNNs, it has been shown that models
learn invariance to transformations only for images similar to typical
training set images [1].

##### Regularization during training

encourages shift-equivariance and invariance by imposing soft constraints. A
pretraining objective during self-supervised learning can be added to predict
transformations applied to the input [6]. A loss function based on cross-
correlation of embedded features encourages equivariance [15]. However, these
regularizations do not guarantee shift-equivariance.

##### Architectural design

can also result in shift-equivariance and invariance. For CNNs, anti-aliasing
strategies [17] and adaptive polyphase sampling (APS) address the lack of
shift-equivariance due to downsampling. The former lacks guarantees, while the
latter is computationally expensive, requiring full convolution computations
that can be problematic when applied to subsampled attentions. Subsampled
attentions address the computational complexity of global attention; computing
global attention before subsampling not only increases computation but also
defeats the purpose of subsampled attentions.

##  6 Conclusions and Discussions

In this paper, we revive shift equivariance in vision transformers by
presenting versatile and adaptable modules that seamlessly integrate with
vision transformer models, leading to improved performance. We introduce an
input-adaptive nonlinear operator that guarantees shift-equivariance,
resulting in more robust and dependable outcomes across a range of visual
transformations. We provide theoretical guarantees of shift equivariance for
strided convolution, window attention, and GSA that utilize polyphase
anchoring. Through carefully controlled experiments, we demonstrate that
vision transformers with polyphase anchoring and depthwise convolution achieve
100% consistency in classification, obtain an average of 20% percentage point
gain (or 37% increase) under the worst-of-30 shift attack, and reach
comparable or superior performance under cropping, horizontal flipping, and
affine transformations.

Due to the high computational cost of training from scratch, this paper,
conducted in an academic setup, focuses on conducting controlled experiments
for comparative analysis rather than optimizing for higher accuracy. Although
the performance of the models may not achieve state-of-the-art standards, the
primary goal of this paper is to investigate whether the geometric guarantees
hold in practice and whether shift-equivariance results in more robust models.
We defer the work of using industrial-scale computing resources to obtaining
state-of-the-art performance to the future.

## References

  * Azulay and Weiss [2018] Aharon Azulay and Yair Weiss.  Why do deep convolutional networks generalize so poorly to small image transformations?  _CoRR_ , abs/1805.12177, 2018.  URL http://arxiv.org/abs/1805.12177.
  * Chaman and Dokmanic [2021] Anadi Chaman and Ivan Dokmanic.  Truly shift-invariant convolutional neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3773–3783, June 2021.
  * Chu et al. [2021] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.  Twins: Revisiting the design of spatial attention in vision transformers.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=5kTlVBkzSRx.
  * Chu et al. [2023] Xiangxiang Chu, Zhi Tian, Bo Zhang, Xinlong Wang, and Chunhua Shen.  Conditional positional encodings for vision transformers, 2023.
  * Dai et al. [2021] Zihang Dai, Hanxiao Liu, Quoc V. Le, and Mingxing Tan.  Coatnet: Marrying convolution and attention for all data sizes, 2021.
  * Dangovski et al. [2022] Rumen Dangovski, Li Jing, Charlotte Loh, Seungwook Han, Akash Srivastava, Brian Cheung, Pulkit Agrawal, and Marin Soljacic.  Equivariant self-supervised learning: Encouraging equivariance in representations.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=gKLAAfiytI.
  * Ding et al. [2022] Mingyu Ding, Bin Xiao, Noel Codella, Ping Luo, Jingdong Wang, and Lu Yuan.  Davit: Dual attention vision transformers.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXIV_ , pages 74–92. Springer, 2022.
  * Dong et al. [2021] Xiaoyi Dong, Jianmin Bao, Dongdong Chen, Weiming Zhang, Nenghai Yu, Lu Yuan, Dong Chen, and Baining Guo.  Cswin transformer: A general vision transformer backbone with cross-shaped windows, 2021.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2020.
  * Gruver et al. [2022] Nate Gruver, Marc Finzi, Micah Goldblum, and Andrew Gordon Wilson.  The lie derivative for measuring learned equivariance, 2022.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * Liu et al. [2022] Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, Furu Wei, and Baining Guo.  Swin transformer v2: Scaling up capacity and resolution, 2022.
  * Tu et al. [2022] Zhengzhong Tu, Hossein Talebi, Han Zhang, Feng Yang, Peyman Milanfar, Alan Bovik, and Yinxiao Li.  Maxvit: Multi-axis vision transformer.  _ECCV_ , 2022.
  * Wang et al. [2021] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 568–578, 2021.
  * Xie et al. [2022] Yuyang Xie, Jianhong Wen, Kin Wai Lau, Yasar Abbas Ur Rehman, and Jiajun Shen.  What should be equivariant in self-supervised learning.  In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , pages 4110–4119, 2022.  doi: 10.1109/CVPRW56347.2022.00456.
  * Zhang et al. [2021] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao.  Multi-scale vision longformer: A new vision transformer for high-resolution image encoding.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2998–3008, 2021.
  * Zhang [2019] Richard Zhang.  Making convolutional networks shift-invariant again, 2019.