# Some adjacency-invariant spaces on products of short cycles

Jeffrey A. Hogan
School of Mathematical and Physical Sciences
University of Newcastle
Callaghan NSW 2308 Australia
email<EMAIL_ADDRESS>Joseph D. Lakey
College of Arts and Sciences
New Mexico State University
Las Cruces, NM 88003–8001
email<EMAIL_ADDRESS>
###### Abstract

We study certain spaces of vertex functions on the Cayley graphs
$\mathcal{C}_{m}^{N}$ of $\mathbb{Z}_{m}^{N}$, where $m=3,4,5$, that are
invariant under the adjacency operator that maps a value at a given vertex to
each of its neighbors. An application to spatio–spectral limiting—an analogue
of time and band limiting—is also discussed.

##  1 Introduction

We study spaces of vertex functions on the Cayley graphs $\mathcal{C}_{m}^{N}$
of $\mathbb{Z}_{m}^{N}$, where $m=3,4,5$, that are invariant under the
adjacency operator that maps a value at a given vertex to each of its
neighbors. In spectral graph theory, _graph filters_ are typically described
as polynomials in the adjacency operator, e.g., [11]. Thus, adjacency
invariant spaces are ones on which filters can, in principle, admit simple
implementations.

This work extends our work [6, 5] in which certain adjacency-invariant spaces
on Boolean cubes $\mathcal{B}_{N}$—Cayley graphs on $\mathbb{Z}_{2}^{N}$—were
identified. These spaces were shown to contain eigen-spaces of
_spatio–spectral limiting operators_ —analogues on $\mathbb{Z}_{2}^{N}$ of
classical time- and band-limiting operators, e.g., [4] that are in turn
relevant to uncertainty principles on more general graphs, e.g., [1, 15].
Broadly, these spaces were defined in terms of level sets $\Sigma_{r}$ of path
distance $r$ to the identity of $\mathbb{Z}_{2}^{N}$. We defined a
_subadjacency_ operator $A_{+}$ of the adjacency operator $A$ that maps
functions supported in $\Sigma_{r}$ to ones supported in $\Sigma_{r+1}$, and
its adjoint $A_{-}$. We showed that spaces of the form
$\mathcal{V}_{r}=\\{\sum_{k=0}^{N-r}c_{k}A_{+}f,f\in\mathcal{W}_{r},c_{0},\dots,c_{N-r}\in\mathbb{R}\,{\rm
or}\,\mathbb{C}\\}$, where $\mathcal{W}_{r}$ consists of those vertex
functions $f$ supported in $\Sigma_{r}$ in the kernel of $A_{-}$, are
invariant under the adjacency operator $A$. Moreover,
$\mathcal{V}_{r}\simeq\mathcal{W}_{r}\times\mathbb{R}^{N+1-r}$ and, as an
operator on $\mathcal{V}_{r}$, $A$ depends only on the factor
$\mathbb{R}^{N+1-r}$ and can thus be expressed as multiplication on
$\mathbb{R}^{N+1-r}$ by a _level matrix_ of size $(N+1-r)$. The action of any
polynomial graph filter on $\mathcal{B}_{N}$ can then be expressed on
$\mathcal{V}_{r}$ as a polynomial of this level matrix. On $\mathcal{B}_{N}$,
any vertex function can be expressed, in any neighborhood of the identity, as
a sum of components in spaces $\mathcal{V}_{r}$. Thus such decomposition
provides a tool to analyze graph filters on $\mathcal{B}_{N}$.

After setting notation, we establish corresponding results in
$\mathcal{C}_{m}^{N}$ for the cases $m=3,4,5$ in Sects. 3–5 respectively,
showing that the corresponding adjacency matrices are invariant on suitable
analogues of the spaces $\mathcal{V}_{r}$ outlined above. We comment on
applications to spatio–spectral limiting in Sect. 6 and briefly comment on
extensions to larger values of $m$ in Sect. 7.

##  2 Background and notation

Let $\Gamma$ be a finite abelian group and $S$ a symmetric subset (i.e.,
$S=-S$) of generators of $\Gamma$, meaning that each $\gamma\in\Gamma$ can be
written $\gamma=s_{1}+\dots+s_{n}$ for some $n$ with each $s_{i}\in S$. The
Cayley graph $(\Gamma,S)$ is then the (unweighted, symmetric) graph whose
vertices are the elements of $\Gamma$ and whose edges correspond to ordered
pairs $(\gamma_{1},\gamma_{2})$ such that $\gamma_{1}-\gamma_{2}\in S$.

In this paper we study certain properties of Cayley graphs
$\mathcal{C}_{m}^{N}$ of the groups $\mathbb{Z}_{m}^{N}$, specifically for
$m=3,4,5$. The one-dimensional cycles
$\mathcal{C}_{3},\mathcal{C}_{4},\mathcal{C}_{5}$ are depicted in Fig. 1. The
cycle group $\mathbb{Z}_{m}$, the group of _integers modulo $m$_, can be
identified with the set of the first $m$ integers $\\{0,1,\dots,m-1\\}$ with
addition modulo $m$. The identity is the (equivalence class of the) integer
$0$ and the inverse of $k\in\\{1,\dots,m-1\\}$ is $m-k$. We will express the
element $m-k$ ($k\leq\lfloor m/2\rfloor$) instead as “$-k$” to emphasize that
it is the $k$th-order sum of the inverse $-1$ of the generator 1. We write
elements of $\mathbb{Z}_{m}^{N}$ as $v=(\ell_{1},\dots,\ell_{N})$,
$\ell_{i}\in\\{-\lfloor(m-1)/2\rfloor,\dots,\lfloor m/2\rfloor\\}$. Addition
in $\mathbb{Z}_{m}^{N}$ is coordinate-wise addition in $\mathbb{Z}_{m}$.

|
---|---
$\textstyle{-1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
1}$$\textstyle{0}$
---
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{-1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$
---
$\textstyle{-2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
2}$$\textstyle{-1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$

Figure 1:  Graphic representation of cycles $\mathcal{C}_{3}$ (left),
$\mathcal{C}_{4}$ (middle) and $\mathcal{C}_{5}$

We denote by $e_{k}\in\mathbb{Z}_{m}^{N}$ the element equal to
$1\in\mathbb{Z}_{m}$ in the $k$th coordinate and equal to $0\in\mathbb{Z}_{m}$
in the other coordinates. We denote by $\mathcal{C}_{m}^{N}$ the Cayley graph
on $\mathbb{Z}_{m}^{N}$ with generators $S=\\{\pm e_{k}\\}_{k=1}^{N}$. Two
vertices $v,w$ are adjacent, denoted $v\sim w$, if $v-w=\pm e_{k}$ for some
$k=1,\dots,N$. It will be useful to define the _$k$ -reflection_ of a vertex
$v=(\ell_{1},\dots,\ell_{N})$ to be the vertex $\tilde{v}_{k}$ whose $j$th
coordinate is $\ell_{j}$ if $j\neq k$ and whose $k$th coordinate is
$-\ell_{k}$. The _$k$ -reflection_ operator $\rho_{k}$ is defined on vertex
functions $f$ by $(\rho_{k}f)(v)=f(\tilde{v}_{k})$. To an element
$v=(\ell_{1},\dots,\ell_{N})\in\\{-\lfloor(m-1)/2\rfloor,\dots,\lfloor
m/2\rfloor\\}^{N}$ we define its _level vector_ to be the vector whose $k$th
entry is the $k$th _level_ , $d_{k}(v)=|\ell_{k}|$. The path distance from $v$
to the origin is $d(v):=\sum_{k=1}^{N}d_{k}(v)$. If
$0<d_{k}(v)<\lfloor{m/2}\rfloor$ then $v_{k}^{-}$ denotes the (unique) vertex
satisfying $d_{k}(v_{k}^{-})=d_{k}(v)-1$ and $d_{j}(v_{k}^{-})=d_{j}(v)$ if
$j\neq k$. Similarly, $v_{k}^{+}$ denotes the (unique) vertex satisfying
$d_{k}(v_{k}^{+})=d_{k}(v)+1$ and $d_{j}(v_{k}^{+})=d_{j}(v)$ if $j\neq k$.
Observe that if $v\sim w$ and $d(v)<d(w)$ then there is a unique coordinate
$k$ such that $d_{k}(w)=d_{k}(v)+1$. If $d_{k}(v)>0$ then $w=v_{k}^{+}$ (and
if $d_{k}(w)<\lfloor m/2\rfloor$ then $v=w_{k}^{-}$). Otherwise $d_{k}(v)=0$
and we regard $v_{k}^{+}=v\pm e_{k}$ as a pair of vertices. Similarly, if
$d_{k}(w)=\lfloor m/2\rfloor$ and $m$ is even we also regard $w_{k}^{-}=w\mp
e_{k}$ as a vertex pair. As an example in $\mathcal{C}_{5}^{2}$,
$(-1,1)_{1}^{+}=(-2,1)$ and $(-1,1)_{1}^{-}=(0,1)$ while $(0,1)_{1}^{+}=(\pm
1,1)$. Two vertices $v,w$ are equi-level if they have an equal number of
coordinates at each level. For example, $v=(0,1,2,1)$ and $w=(-1,0,1,2)$ are
equi-level in $\mathcal{C}_{4}^{4}$. Set $M=\lfloor m/2\rfloor$. The level set
$\Sigma_{q_{1},\dots,q_{M}}$ is the set of all vertices that have $q_{\ell}$
coordinates at level $\ell$, $\ell=1,\dots,M$.

The graph Laplacian is the operator $(Lf)(v)=\sum_{w\sim v}f(v)-f(w)$ where
$f$ is a complex-valued function defined on $\mathbb{Z}_{m}^{N}$. When $N=1$,
the eigenvectors are $E_{k}=\\{{\rm e}^{2\pi ik\ell/m}\\}_{\ell=0}^{m-1}$,
with eigenvalue $2\cos(2\pi k/N)$. Given the Cartesian product of two graphs
with an appropriate vertex ordering on the product, the eigenvectors of the
product Laplacian are the tensor products of eigenvectors of the Laplacians on
the separate factors, whose eigenvalues are the sums of the corresponding
factor eigenvalues., e.g., [7]. The graph Fourier transform is the operator
that maps a vertex function to its coefficients in a basis of Laplacian
eigenvectors. For any $r$-regular graph (i.e., each vertex is adjacent to $r$
other vertices), the Laplacian can also be written as $L=rI-A$ where the
adjacency operator $A$ is defined by $(Af)(v)=\sum_{w\sim v}f(w)$.

Once an indexing of the $m^{N}$ vertices of $\mathcal{C}_{m}^{N}$ is fixed,
the matrix $A$ of the adjacency operator with respect to this ordering can be
defined as the matrix whose $(i,j)$-entry is equal to one precisely when
$v_{i}$ and $v_{j}$ are adjacent vertices. In what follows we will not
distinguish notationally between the operator $A$ versus a matrix realization
$A$, and simply write $A$ in either case. The same will apply to _partial_
adjacencies—restrictions of adjacency to subsets of (ordered) vertex pairs—and
compositions of them. We define the _outer adjacency_ operator ${A}_{+}$ by
$({A}_{+}f)(v)=\sum_{w\sim v,d(v)<d(w)}f(w)$. If vertices are ordered in
nondecreasing order of path distance $d$ to the origin, the corresponding
matrix $A_{+}$ of $A$ is lower triangular. We define ${A}_{-}$ to be the
adjoint of ${A}_{+}$. Finally, we define the _neutral adjacency operator_
${A}_{0}$ by $({A}_{0}f)(v)=\sum_{w\sim v,\,d(w)=d(v)}f(w)$.

The commutator $C=[{A}_{-},\,{A}_{+}]={A}_{-}{A}_{+}-{A}_{+}{A}_{-}$ will be
important.

######  Lemma 1.

The commutator $C=A_{-}A_{+}-A_{+}A_{-}$ has its support in pairs of vertices
that have equal level vectors.

Specifically, we think of ${A}_{+}$ as mapping values at vertices of a given
level to vertices of an outer level and ${A}_{-}$ does the reverse. If
$f=\bm{1}_{v}$ is supported at a single vertex
$v\sim(\ell_{1},\dots,\ell_{N})$ and
$w=(\ell_{1}^{\prime},\dots,\ell_{N}^{\prime})$ is an equi-level vertex such
that for fixed $j\neq k$, $\ell_{j}^{\prime}=\ell_{j}+1$ and
$\ell_{k}^{\prime}=\ell_{k}-1$, then
$({A}_{-}{A}_{+}\bm{1}_{v})(w)=({A}_{+}{A}_{-}\bm{1}_{v})(w)$.

##  3 Adjacency-invariant spaces on $\mathcal{C}_{3}^{N}$

The graph $\mathcal{C}_{3}^{N}$ is an $N$-fold product of triangles. Let
$\Sigma_{r}$ denote the set of vertices $v$ such that $d(v)=r$. These are the
vertices that have $\pm 1$ in $r$ coordinates and are null in the other $N-r$
coordinates. Thus $\Sigma_{r}$ has $2^{r}\binom{N}{r}$ vertices. The identity
$\sum_{r=0}^{N}2^{r}\binom{N}{r}=3^{N}$ reflects that the vertices of
$\mathcal{C}_{3}^{N}$ are the disjoint union of $\Sigma_{r}$, $r=0,\dots,N$.
The outer adjacency operator maps vectors supported on $\Sigma_{r}$ to ones
supported on $\Sigma_{r+1}$. In particular, $A_{+}^{k}f=0$ if $f$ is supported
in $\Sigma_{r}$ and $k>N-r$. Two vertices $v,w\in\Sigma_{r}$ that are equal in
all but one coordinate are adjacent to one another. Specifically, if
$v,w\in\Sigma_{r}$ and $v-w=\pm e_{k}$ then $v\sim w$ and $w=\tilde{v}_{k}$.
We call $w$ the $k$th neutral neighbor of $v$. The neutral adjacency operator
on $\mathcal{C}_{3}^{N}$ is $(A_{0}f)(v)=\sum_{k:d_{k}(v)=1}f(\tilde{v}_{k})$.

######  Theorem 2.

${C}+{A}_{0}$ is diagonal on the space of vectors supported on $\Sigma_{r}$,
the vertices of distance $r$ from the origin in $\mathcal{C}_{3}^{N}$.
Specifically, for such $f$, ${C}f=(2N-3r)f-{A}_{0}f$.

###### Proof.

Fix $v\in\Sigma_{r}$. In view of Lem. 1, ${C}f(v)$ takes its input from
vertices that differ from $v$ in at most a single coordinate, meaning ${C}$
will have a diagonal component at $v$ and, possibly, a neutral neighbor
component. Given a vertex $v$, for each null coordinate of $v$, there are two
edges to vertices in $\Sigma_{r+1}$ that are level one in that coordinate and
otherwise equal to $v$, so there are $2(N-r)$ paths from $v$ to a vertex in
$\Sigma_{r+1}$ and back to $v$ under ${A}_{-}{A}_{+}$. On the other hand, for
each level-one coordinate $k$ of $v$, there is a path from $v$ to the vertex
$v_{k}^{-}$ that is null in that coordinate and equal to $v$ in all other
coordinates, then back to $v$, and another path through $v_{k}^{-}$ to
$\tilde{v}_{k}$, under ${A}_{+}{A}_{-}$. Altogether then,
${C}(f)(v)=({A}_{-}{A}_{+}-{A}_{+}{A}_{-})(f)(v)=2(N-r)f(v)-[rf(v)+\sum_{k:d_{k}(v)=1}f(\tilde{v}_{k})]=(2N-3r)f(v)-({A}_{0}f)(v)$.
This proves the theorem. ∎

######  Lemma 3.

Let $f$ be a vertex function supported in $\Sigma_{r}$ such that for each
vertex $v\in\Sigma_{r}$, $f$ is $k$-symmetric in $s$ of the level-one
coordinates of $v$ and $k$-antisymmetric in the other $r-s$ level-one
coordinates. Then $f$ is an eigenvector of ${A}_{0}$ with eigenvalue $2s-r$.

###### Proof.

Each vertex $v\in\Sigma_{r}$ has $r$ coordinate neutral neighbors, namely
$\\{\tilde{v}_{k}:d_{k}(v)=1\\}$ and

$({A}_{0}f)(v)=\sum_{k:d_{k}(v)=1}f(\tilde{v}_{k})=sf(v)-(r-s)f(v)=(2s-r)f(v)\,$

by hypothesis. ∎

The possible $A_{0}$-eigenvalues $\lambda$ of $f$ on $\Sigma_{r}$ are
$(2s-r)$, $s=0,1\dots,r$.

######  Lemma 4.

Let $f$ be a $\lambda$-eigenvector of ${A}_{0}$ supported in $\Sigma_{r}$.
Then ${A}_{+}f$ is a $(\lambda+1)$-eigenvector of ${A}_{0}$ supported in
$\Sigma_{r+1}$.

###### Proof.

One has $(A_{0}f)(v)=\sum_{k:d_{k}(v)=1}f(\tilde{v}_{k})$. Since
$A_{+}f(w)=\sum_{\nu:d_{\nu}(w)=1}f(w_{\nu}^{-})$, altogether,

$(A_{0}A_{+}f)(w)=\sum_{\mu:d_{\mu}(w)=1}(A_{+}f)(\tilde{w}_{\mu})=\sum_{\mu:d_{\mu}(w)=1}\sum_{\nu:d_{\nu}(\tilde{w}_{\mu})=1}f((\tilde{w}_{\mu})_{\nu}^{-})\\\
=\sum_{\mu:d_{\mu}(w)=1}\sum_{\nu:d_{\nu}(w)=1}f((\tilde{w}_{\mu})_{\nu}^{-})=\sum_{\nu:d_{\nu}(w)=1}\sum_{\mu:d_{\mu}(w)=1}f((\tilde{w}_{\mu})_{\nu}^{-})\\\
=\sum_{\nu:d_{\nu}(w)=1}[f((\tilde{w}_{\nu})_{\nu}^{-})+\sum_{\mu:d_{\mu}(w)=1,\,\mu\neq\nu}f((\tilde{w}_{\mu})_{\nu}^{-})]\\\
=\sum_{\nu:d_{\nu}(w)=1}[f(w_{\nu}^{-})+(A_{0}f)(w_{\nu}^{-})]=(\lambda+1)\sum_{\nu:d_{\nu}(w)=1}f(w_{\nu}^{-})=(\lambda+1)(A_{+}f)(w)$

since $d_{\nu}(w_{\nu}^{-})=0$ implies that
$\\{(\tilde{w}_{\mu})_{\nu}^{-}:d_{\mu}(w)=1,\,\mu\neq\nu\\}$ is the set of
all level-one reflections of $w_{\nu}^{-}$ and that
$f((\tilde{w}_{\nu})_{\nu}^{-})=f(w_{\nu}^{-})$. We also used that
$A_{0}f=\lambda f$. ∎

In $\mathcal{C}_{3}^{N}$, $\Sigma_{r}$ has $2^{r}\binom{N}{r}$ vertices. For
each choice $S_{r}$ of $r$ nonzero coordinates, a basis for the vertex
functions whose nonzero coordinates are $S_{r}$ can be obtained by ordering
the elements of $S_{r}$ and forming the Hadamard matrix $H_{r}$ of size
$2^{r}$ (i.e., the $r$-th Kronecker power of the Haar matrix with rows
$[1,1]/\sqrt{2}$ and $[1,-1]/\sqrt{2}$) on these indices. For each such
$S_{r}$, there is an $\binom{r}{s}$-dimensional eigenspace of $A_{0}$ with
eigenvalue $2s-r$ spanned by the columns of $H_{r}$ that are symmetric in $s$
of the $S_{r}$-coordinates and antisymmetric in the others. A basis for the
$(2s-r)$-eigenspace of $A_{0}$ on $\Sigma_{r}$ results from ranging over
choices of $S_{r}$.

######  Lemma 5.

Let $f$ be a $\lambda$-eigenvector of $A_{0}$ supported in $\Sigma_{r}$ and in
the kernel of $A_{-}$. Then $A_{-}A_{+}^{k+1}f=m(r,k,\lambda)A_{+}^{k}f$ where
$m(r,k,\lambda)$ is defined inductively by $m(r,0,\lambda)=2N-3r-\lambda$ and
$m(r,k,\lambda)=m(r,k-1,\lambda)+(2N-3r-4k)-\lambda$.

If $A_{+}^{k}f=0$ for some $k$ then $A_{+}^{k+1}f=0$ also. The identity
reflects this property.

###### Proof.

First, since $A_{-}f=0$ we have
$Cf=A_{-}A_{+}f-A_{+}A_{-}f=A_{-}A_{+}f=((2N-3r)-\lambda)f$ by Thm. 2. Thus
the result holds with $k=0$ and $m(r,0,\lambda)=(2N-3r-\lambda)$. Suppose that
the result is true for $k-1$. Then, again by Thm. 2,

$A_{-}A_{+}^{k+1}f=[A_{-}A_{+}-A_{+}A_{-}+A_{+}A_{-}]A_{+}^{k}f=CA_{+}^{k}f+A_{+}(A_{-}A_{+}^{k}f)\\\
=CA_{+}^{k}f+m(r,k-1,\lambda)A_{+}^{k}f=(2N-3(r+k))A_{+}^{k}f-A_{0}A_{+}^{k}f+m(r,k-1,\lambda)A_{+}^{k}f\\\
=[(2N-3(r+k))-(\lambda+k)+m(r,k-1,\lambda)]A_{+}^{k}f=m(r,k,\lambda)A_{+}^{k}f\qed$

######  Theorem 6.

Let $\mathcal{W}_{r,\lambda}$ denote the space of vertex functions supported
in $\Sigma_{r}$ that are in the kernel of ${A}_{-}$ and are
$\lambda$-eigenvectors of ${A}_{0}$. Let
$\mathcal{V}_{r,\lambda}=\\{\sum_{k=0}^{N-r}c_{k}{A}_{+}^{k}f:f\in\mathcal{W}_{r,\lambda},\,c_{k}\in\mathbb{C}\\}$.
Then for each eigenvalue $\lambda$ of ${A}_{0}$, the space
$\mathcal{V}_{r,\lambda}$ is invariant under the adjacency operator $A$ on
$\mathcal{C}_{3}^{N}$.

###### Proof.

By its definition, $\mathcal{V}_{r,\lambda}$ is invariant under $A_{+}$. By
Lem. 4, $A_{+}^{k}f$ is an eigenvector of $A_{0}$ for each $k$ if
$f\in\mathcal{W}_{r,\lambda}$ and therefore $A_{0}$ maps any sum of the form
$\sum_{k=0}^{N-r}c_{k}{A}_{+}^{k}f:f\in\mathcal{W}_{r,\lambda}$ to another sum
of the same form. Finally, by Lem. 5, $A_{-}$ maps any sum of this form to
another such sum. Since $A=A_{-}+A_{0}+A_{+}$, the theorem follows. ∎

Evidently, $\mathcal{V}_{r,\lambda}$ is isomorphic to
$\mathcal{W}_{r,\lambda}\times\mathbb{C}^{N+1-r}$. The action of $A$ on
$\mathcal{V}_{r,\lambda}$ only depends on the $\mathbb{C}^{N+1-r}$ factor and
can be represented by a size $N+1-r$ tri-diagonal _level matrix_ that has ones
on the diagonal below the main diagonal, entries $\lambda+k$ on the main
diagonal, and $m(r,k,\lambda)$ on the diagonal above the main diagonal. This
representation can make application of polynomials of $A$ on
$\mathcal{V}_{r,\lambda}$ feasible when $N$ is large, cf., [5].

##  4 Adjacency-invariant spaces on $\mathcal{C}_{4}^{N}$

In this case, $\Sigma_{r}=\\{v:\,d(v)=r\\}=\cup_{2q+p=r}\Sigma_{p,q}$ where
$\Sigma_{p,q}$ consists of those vertices that have $q$ level-two coordinates
and $p$ level-one coordinates. For example
$\Sigma_{5}=\Sigma_{5,0}\cup\Sigma_{3,1}\cup\Sigma_{1,2}$.

######  Theorem 7.

Let $f$ be supported on $\Sigma_{r}$, the vertices of distance $r$ from the
origin in $\mathcal{C}_{4}^{N}$. Then ${C}f=2(N-r)f$.

###### Proof.

It suffices to show that the same multiplier applies to $\Sigma_{p,q}$ for
each case of $p+2q=r$. We write $A_{+}$ and $A_{-}$ explicitly in this case as
$(A_{+}f)(v)=\sum_{d_{k}(v)=2}f(v_{k}^{-})+\sum_{d_{k}(v)=1}f(v_{k}^{-})$ and
$(A_{-}g)(w)=\sum_{d_{k}(w)=0}f(w_{k}^{+})+\sum_{d_{k}(w)=1}f(w_{k}^{+})$.
Thus

$(A_{-}A_{+}f)(v)=\Bigl{(}\sum_{d_{k}(v)=0}+\sum_{d_{k}(v)=1}\Bigr{)}(A_{+}f)(v_{k}^{+})\\\
=\Bigl{(}\sum_{d_{k}(v)=0}+\sum_{d_{k}(v)=1}\Bigr{)}\Bigr{(}\sum_{d_{\nu}(v_{k}^{+})=2}+\sum_{d_{\nu}(v_{k}^{+})=1}\Bigr{)}f((v_{k}^{+})_{\nu}^{-})\\\
=\Bigl{(}\sum_{d_{k}(v)=0}+\sum_{d_{k}(v)=1}\Bigr{)}f((v_{k}^{+})_{k}^{-})+{\rm
other\,\,terms}$

Similarly,

$(A_{+}A_{-}f)(v)=\Bigl{(}\sum_{d_{\nu}(v)=1}+\sum_{d_{\nu}(v)=2}\Bigr{)}(A_{-}f)(v_{\nu}^{-})\\\
=\Bigl{(}\sum_{d_{\nu}(v)=2}+\sum_{d_{\nu}(v)=1}\Bigr{)}\Bigl{(}\sum_{d_{k}(v_{\nu}^{-})=0}+\sum_{d_{k}(v_{\nu}^{-})=1})f((v_{\nu}^{-})_{k}^{+})\Bigr{)}\\\
=\Bigl{(}\sum_{d_{\nu}(v)=2}+\sum_{d_{\nu}(v)=1}\Bigr{)}f((v_{\nu}^{-})_{\nu}^{+})+{\rm
other\,\,terms}$

Contributions to $(A_{\pm}A_{\mp}f)(v)$ come from two-edge paths of two types:
paths in which the level changes are in the same coordinate and paths that
involve a level increase in one coordinate and a level decrease in a different
coordinate. The latter account for the _other terms_ above. As observed in
Lem. 1, these _other terms_ cancel between $A_{-}A_{+}$ and $A_{+}A_{-}$.
Also, if $d_{k}(v)=1$ then the $k$th coordinate contribution to
$A_{-}A_{+}f(v)$ is $f(v)+f(\tilde{v}_{k})$, since $(v_{k}^{+})_{k}^{-}$ is
the pair $(v,\tilde{v}_{k})$. The $k$th coordinate contribution to
$A_{+}A_{-}f(v)$ is also $f(v)+f(\tilde{v}_{k})$, since $(v_{k}^{-})_{k}^{+}$
is also the pair $(v,\tilde{v}_{k})$, so the _level-one_ terms cancel in $Cf$.
If $d_{k}(v)=0$ then $v_{k}^{+}$ and $\widetilde{(v_{k}^{+})}_{k}$ are both
assigned the value $f(v)$ under $A_{+}$ so the $k$th coordinate contribution
to $(A_{-}A_{+}f)(v)$ is $2f(v)$ whereas the $k$th contribution to
$(A_{+}A_{-}f)(v)$ is zero, so the net contribution to $Cf$ from level-zero
terms is $2(N-(p+q))f$. On the other hand, if $d_{\nu}(v)=2$ then the $\nu$th
coordinate contribution to $(A_{-}A_{+}f)(v)$ is zero, whereas $v_{\nu}^{-}$
and $(\widetilde{v_{\nu}^{-}})_{\nu}$ are both assigned the value $f(v)$ under
$A_{-}$, so the $v_{\nu}$-th contribution to $(A_{+}A_{-}f)(v)$ is $2f(v)$,
and the net level-two contribution to $Cf$ is $-2qf$. Altogether, the
different coordinate contributions to $(Cf)(v)$ add up to
$2(N-(p+q)-q)f(v)=2(N-r)f(v)$, independent of the level component,
$\Sigma_{p,q}\subset\Sigma_{r}$, of $v$. This proves the theorem. ∎

######  Lemma 8.

Suppose that $f$ is supported in $\Sigma_{p,q}$ and $A_{-}f=0$. Then
$(A_{-}A_{+}^{k+1}f)(v)=m(r,k)f(v)$ where $m(r,k)$ is defined iteratively by
$m(r,0)=2(N-r)$ and $m(r,k)=[m(r,k-1)+2(N-(r+k))]$, $r=p+2q$.

###### Proof.

The case $k=0$ follows from Thm. 7 and the hypothesis that $f$ is in the
kernel of $A_{-}$. Suppose that the conclusion holds for $k$ replaced by
$k-1$. Then

$A_{-}A_{+}^{k+1}f=(A_{-}A_{+}-A_{+}A_{-}+A_{+}A_{-})A^{k}f=CA_{+}^{k}f+A_{+}A_{-}A_{+}^{k}f\\\
=2(N-(r+k))A_{+}^{k}f+A_{+}(m(r,k-1))A_{+}^{k-1}f=m(r,k)A_{+}^{k}f\,.$

Here we used again Thm. 7. It applies because $A_{+}^{k}f$ is supported in
$\Sigma_{r}=\cup_{p+2q=r}\Sigma_{p,q}$, and then applied the induction
hypothesis. This proves the lemma. ∎

######  Theorem 9.

Let $\mathcal{W}_{p,q,0}$ be the space of vertex functions supported in
$\Sigma_{p,q}$ and in the kernel of $A_{-}$. Set
$\mathcal{V}_{p,q}=\\{\sum_{k=0}^{N-r}c_{k}A_{+}^{k}f,\,f\in\mathcal{W}_{p,q,0}\\}$.
Then $\mathcal{V}_{p,q}$ is invariant under $A$.

###### Proof.

Observe that there are no neutral adjacencies, that is, vertex pairs
$v,w\in\Sigma_{r}$ such that $v\sim w$. Thus $A=A_{+}+A_{-}$. Evidently
$\mathcal{V}_{p,q}$ is invariant under $A_{+}$. If
$g=\sum_{k=0}^{N-r}c_{k}A_{+}^{k}f$, $f\in\mathcal{W}_{p,q,0}$ then

$A_{-}g=\sum_{k=1}^{N-r}c_{k}m(r,k-1)A_{+}^{k-1}f=\sum_{k=0}^{N-r-1}c_{k+1}m(r,k)A_{+}^{k}f$

which is also in $\mathcal{V}_{p,q}$ (with no term $A_{+}^{N-r}f$). ∎

Similar to the case of $\mathcal{C}_{3}^{N}$,
$\mathcal{V}_{p,q}\simeq\mathcal{W}_{p,q,0}\times\mathbb{C}^{N+1-r}$
($r=p+2q$), and the action of $A$ on $\mathcal{V}_{p,q}$ can be realized as a
tridiagonal level matrix on $\mathbb{C}^{N+1-r}$. In this case the matrix has
ones on the diagonal below the main diagonal, $m(r,k)$ on the diagonal above
the main diagonal, and zeros on the main diagonal.

##  5 Adjacency-invariant spaces on $\mathcal{C}_{5}^{N}$

As in the $\mathcal{C}_{3}^{N}$ case, $\mathcal{C}_{5}^{N}$ has _neutral
adjacencies_ , this time because “$-2$” and “$2$” are adjacent in
$\mathcal{C}_{5}$, see Fig. 1. Additionally, a path from “$1$” to “$-1$”
through the origin in $\mathcal{C}_{5}$ can be viewed as a reflection, which
arises under composite partial adjacencies $A_{+}A_{-}$. These properties
translate into more technical description of adjacency invariant spaces on
$\mathcal{C}_{5}^{N}$, to which we will refer as $\mathcal{V}_{p,q}$-type
spaces, compared to the invariant spaces $\mathcal{V}_{r,\lambda}$ on
$\mathcal{C}_{3}^{N}$ and $\mathcal{V}_{p,q}$ on $\mathcal{C}_{4}^{N}$. To
facilitate such description, we in turn describe _subadjacencies_
$A_{(p,q)\to(p-1,q+1)}$ and $A_{(p,q)\to(p+1,q)}$ of $A_{+}$ that map values
on vertices $v\in\Sigma_{p,q}$ such that $d(v)=p+2q$ to corresponding values
on adjacent vertices $w$ in $\Sigma_{p-1,q+1}$ or $\Sigma_{p+1,q}$,
respectively, such that $d(w)=p+2q+1$. Similarly, we denote by
${A}_{(p,q)\to(p-1,q)}$ and ${A}_{(p,q)\to(p+1,q-1)}$ subadjacencies of
${A}_{-}$ that map $\Sigma_{p,q}$ to $\Sigma_{p-1,q}$ and $\Sigma_{p+1,q-1}$,
respectively. Finally, we denote by ${A}_{(p,q)\to(p,q)}$ the _neutral
subadjacency_ operator on $\Sigma_{p,q}$ that replaces a vertex function value
$f(v)$ at $v\in\Sigma_{p,q}$ by the sum $\sum_{k:d_{k}(v)=2}f(\tilde{v}_{k})$
of the values at its neutral neighbors in $\Sigma_{p,q}$. For $q=1$,
$A_{(p,1)\to(p,1)}^{2}=I$. More generally, ${A}_{(p,q)\to(p,q)}$ is in the
kernel of a nontrivial polynomial of degree $q+1$. We refer to the
subadjacencies from $\Sigma_{p,q}$ to $\Sigma_{p\pm 1,q\mp 1}$ as _internal
adjacencies_ , referring to raising and lowering the level in a non-null
coordinate, and to ${A}_{(p,q)\to(p\pm 1,q)}$ as _external adjacencies_ that
involve adjacencies between vertices with different numbers of null
coordinates. We will use the symbols $A_{-},A_{+},A_{0}$ as abbreviations for
particular inner, outer, and neutral subadjacencies when appropriate.

In defining suitable analogues on $\mathcal{C}_{5}^{N}$ of the adjacency-
invariant subspaces of type $\mathcal{V}_{p,q}$ defined in Thms. 6 and 9,
between successive powers of $A_{+}$ that occur in their description, we need
to allow application of a neutral adjacency after every subadjacency of the
form $A_{(p,q)\to(p-1,q+1)}$ that increases the number of level-two
coordinates. So elements of $\mathcal{V}_{p,q}$-type spaces will be sums of
compositions of outer and neutral subadjacencies starting from a fixed level.
The different subadjacencies in turn give rise to different multipliers for
each different level. As before, establishing adjacency invariance of
$\mathcal{V}_{p,q}$-type spaces boils down to understanding compositions of
the different subadjacencies.

The commutator $C=[{A}_{-},{A}_{+}]$ acting on vectors supported in
$\Sigma_{p,q}$ breaks into components as follows.

$\left.C\right|_{\Sigma_{p,q}}={A}_{(p+1,q)\to(p,q)}{A}_{(p,q)\to(p+1,q)}+{A}_{(p-1,q+1)\to(p,q)}{A}_{(p,q)\to(p-1,q+1)}\\\
+{A}_{(p+1,q)\to(p+2,q-1)}{A}_{(p,q)\to(p+1,q)}+{A}_{(p-1,q+1)\to(p-2,q+1)}{A}_{(p,q)\to(p-1,q+1)}\\\
-{A}_{(p-1,q)\to(p,q)}{A}_{(p,q)\to(p-1,q)}-{A}_{(p+1,q-1)\to(p,q)}{A}_{(p,q)\to(p+1,q-1)}\\\
-{A}_{(p-1,q)\to(p-2,q+1)}{A}_{(p,q)\to(p-1,q)}-{A}_{(p+1,q-1)\to(p+2,q-1)}{A}_{(p,q)\to(p+1,q-1)}\\\
=[{A}_{(p+1,q)\to(p,q)}{A}_{(p,q)\to(p+1,q)}-{A}_{(p-1,q)\to(p,q)}{A}_{(p,q)\to(p-1,q)}]\\\
+[{A}_{(p-1,q+1)\to(p,q)}{A}_{(p,q)\to(p-1,q+1)}-{A}_{(p+1,q-1)\to(p,q)}{A}_{(p,q)\to(p+1,q-1)}]\\\
+[{A}_{(p-1,q+1)\to(p-2,q+1)}{A}_{(p,q)\to(p-1,q+1)}-{A}_{(p-1,q)\to(p-2,q+1)}{A}_{(p,q)\to(p-1,q)}]\\\
+[{A}_{(p+1,q)\to(p+2,q-1)}{A}_{(p,q)\to(p+1,q)}-{A}_{(p+1,q-1)\to(p+2,q-1)}{A}_{(p,q)\to(p+1,q-1)}],$

expressing the commutator on $\Sigma_{p,q}$ as a sum of external and internal
commutators with targets in $\Sigma_{p,q}$, $\Sigma_{p-2,q+1}$ and
$\Sigma_{p+2,q-1}$ respectively. The terms that map data on $\Sigma_{p,q}$ to
$\Sigma_{p-2,q+1}$ and to $\Sigma_{p+2,q-1}$ vanish because of Lem. 1. That
lemma also implies that all vertex-pair terms affected in

${A}_{(p+1,q)\to(p,q)}{A}_{(p,q)\to(p+1,q)}-{A}_{(p-1,q)\to(p,q)}{A}_{(p,q)\to(p-1,q)}$

vanish except those in which the extension and reduction occurs in the same
coordinate. There are $N-(p+q)$ null coordinates in any $\Sigma_{p,q}$-vertex,
hence $2[N-(p+q)]$ _out-and-back paths_ to any vertex in $\Sigma_{p,q}$ via
this term, while there are $p$ _in-and-back_ paths plus an _in-and-out_ path
to each level-one vertex reflection. Consequently the action of this term on a
vertex function $f$ supported in $\Sigma_{p,q}$ is multiplication by
$2(N-q)-3p$, plus ${R}_{1}$, the level-one reflection of $f$, defined by
$(R_{1}f)(v)=\sum_{d_{k}(v)=1}(\rho_{k}f)(v)$. Finally, Lem. 1 also implies
that any vertex-pair term in

${A}_{(p-1,q+1)\to(p,q)}{A}_{(p,q)\to(p-1,q+1)}-{A}_{(p+1,q-1)\to(p,q)}{A}_{(p,q)\to(p+1,q-1)}$

also vanishes except for those in which the extension and reduction ends in
the same coordinate. However, in this case all extensions are level one to
level two and all reductions are level two to level one. Thus the in-
coordinate elements of both terms
${A}_{(p+1,q-1)\to(p,q)}{A}_{(p,q)\to(p+1,q-1)}$ and
${A}_{(p-1,q+1)\to(p,q)}{A}_{(p,q)\to(p-1,q+1)}$ map a vertex value to itself,
so the two terms cancel and this term of the commutator vanishes. Altogether
we have proved the following.

######  Theorem 10.

As an operator on the space of vectors supported on $\Sigma_{p,q}$, the
vertices that have $p$-coordinates at level one and $q$ coordinates at level
two in $\mathcal{C}_{5}^{N}$, $C=[A_{-},\,A_{+}]=(2(N-q)-3p)I+R_{1}$.

Adjacency invariant space analogues of those presented for
$\mathcal{C}_{3}^{N}$ and $\mathcal{C}_{4}^{N}$ in Thms. 6 and 9 are
necessarily more complicated in the case of $\mathcal{C}_{5}^{N}$. As in
$\mathcal{C}_{3}^{N}$, there is a role played by eigenvectors of
neutral/reflection maps.

######  Lemma 11.

$({\rho}_{k}{A}_{+}f)(w)=({A}_{+}{\rho}_{k}f)(w)$ and
$({\rho}_{k}{A}_{-}f)(w)=({A}_{-}{\rho}_{k}f)(w)$

###### Proof.

We prove that $({\rho}_{k}{A}_{+}f)(w)=({A}_{+}{\rho}_{k}f)(w)$ and leave
$({\rho}_{k}{A}_{-}f)(w)=({A}_{-}{\rho}_{k}f)(w)$ as an exercise. Observe that
on the right, the reflection is in vertices in $\Sigma_{p,q}$ and on the left
the reflection is in vertices in $\Sigma_{p+1,q}$ or $\Sigma_{p-1,q+1}$. Since
${A}_{+}$ can be expressed as ${A}_{(p,q)\to(p+1,q)}+{A}_{(p,q)\to(p-1,q+1)}$,
it suffices to prove the commutation separately for these.

First, let $w\in\Sigma_{p-1,q+1}$ with $d_{k}(w)=2$. Observe that

$({A}_{(p,q)\to(p-1,q+1)}{\rho}_{k}f)(w)=\sum_{\nu:d_{\nu}(w)=2}({\rho}_{k}f)(w_{\nu}^{-})=\sum_{\nu:d_{\nu}(w)=2}f((w_{\nu}^{-})_{k}^{\sim})\\\
=\sum_{\nu:d_{\nu}(\tilde{w}_{k})=2}f((\tilde{w}_{k})_{\nu}^{-})=({A}_{(p,q)\to(p-1,q+1)}f)(\tilde{w}_{k})=({\rho}_{k}{A}_{(p,q)\to(p-1,q+1)}f)(w)\,.$

Here we used the fact that
$(\tilde{w}_{k})_{\nu}^{-}=(w_{\nu}^{-})_{k}^{\sim}$. When $k\neq\nu$ the
$k$th coordinate of both sides is level two. When $k=\nu$ the $k$th coordinate
of both sides is level one and the identity reduces to the fact that reduction
commutes with reflection in each coordinate. The identity in Lem. 11 clearly
holds when $d_{k}(w)\in\\{0,1\\}$ since in these cases the reduction
coordinate $\nu$ ($d_{\nu}(w)=2$) in the sum defining outer adjacency is never
equal to the reflection coordinate $k$.

Next let $w\in\Sigma_{p+1,q}$ such that $d_{k}(w)=1$. Observe now that

$({A}_{(p,q)\to(p+1,q)}{\rho}_{k}f)(w)=\sum_{\nu:d_{\nu}(w)=1}({\rho}_{k}f)(w_{\nu}^{-})=\sum_{\nu:d_{\nu}(w)=1}f((w_{\nu}^{-})_{k}^{\sim})\\\
=\sum_{\nu:d_{\nu}(\tilde{w}_{k})=1}f((\tilde{w}_{k})_{\nu}^{-})=({A}_{(p,q)\to(p+1,q)}f)(\tilde{w}_{k})=({\rho}_{k}{A}_{(p,q)\to(p+1,q)}f)(w)\,.$

Here, again, $(\tilde{w}_{k})_{\nu}^{-}=(w_{\nu}^{-})_{k}^{\sim}$: when
$k\neq\nu$ the $k$th coordinate of both sides is level one. When $k=\nu$ the
$k$th coordinate of both sides is level zero so the reflection is trivial. The
identity in Lem. 11 clearly holds when $d_{k}(w)\in\\{0,2\\}$ since in these
cases the reduction coordinate $\nu$ is never equal to the reflection
coordinate $k$. ∎

######  Lemma 12.

If $f$ supported in $\Sigma_{p,q}$ is a $\lambda$-eigenvector of $R_{1}$ then
(i) $A_{(p,q)\to(p+1,q)}f$ is a $(\lambda+1)$-eigenvector of $R_{1}$ on
$\Sigma_{p+1,q}$ and (ii) $A_{(p,q)\to(p-1,q+1)}f$ is a $\lambda$-eigenvector
of $R_{1}$ on $\Sigma_{p-1,q+1}$.

###### Proof.

First we consider the case of $A_{(p,q)\to(p+1,q)}f$. Suppose that
$w\in\Sigma_{p+1,q}$, and $d_{k}(w)=1$ so $w_{k}^{-}=\tilde{w}_{k}^{-}$. Then

${\rho}_{k}(A_{+}f)(w)={\rho}_{k}f(w_{k}^{-})+\sum_{\nu\neq
k,d_{\nu}(w)=1}{\rho}_{k}f(w_{\nu}^{-})=f(w_{k}^{-})+\sum_{\nu\neq
k,d_{\nu}(\tilde{w}_{k})=1}f(\widetilde{(w_{\nu}^{-})}_{k})\,.$

Summing over all $k$ such that $d_{k}(w)=1$ then gives

$\sum_{k:d_{k}(w)=1}{\rho}_{k}(A_{+}f)(w)=\sum_{k:d_{k}(w)=1}f(w_{k}^{-})+\sum_{k:d_{k}(w)=1}\sum_{\nu\neq
k,d_{\nu}(\tilde{w}_{k})=1}f(\widetilde{(w_{\nu}^{-})}_{k})\\\
=(A_{+}f)(w)\,+\sum_{\nu:\,d_{\nu}(w)=1}\sum_{k\neq\nu:d_{k}(w)=1}f(\widetilde{(w_{\nu}^{-})}_{k})\\\
=(A_{+}f)(w)\,+\sum_{\nu:\,d_{\nu}(w)=1}R_{1}f(w_{\nu}^{-})\,.$

If $f$ is a $\lambda$-eigenvector of $R_{1}$ on $\Sigma_{p,q}$ then the last
term becomes

$(A_{+}f)(w)+\sum_{\nu:\,d_{\nu}(w)=1}\lambda
f(w_{\nu}^{-})=\lambda(A_{+}f)(w)+(A_{+}f)(w)=(\lambda+1)A_{+}f(w)\,.$

This gives the desired result for $A_{(p,q)\to(p+1,q)}$.

For the case $A_{(p,q)\to(p-1,q+1)}$, let $w\in\Sigma_{p-1,q+1}$ such that
$d_{k}(w)=1$. Then $k$ cannot be one of the reduction coordinates defining
$(A_{+}f)(w)$, so

${\rho}_{k}(A_{+}f)(w)={\rho}_{k}\Bigl{[}\sum_{d_{\nu}(w)=2}f(w_{\nu}^{-})\Bigr{]}=\sum_{d_{\nu}(w)=2}{\rho}_{k}f(w_{\nu}^{-})=\sum_{d_{\nu}(\tilde{w}_{k})=2}f(\widetilde{(w_{\nu}^{-})}_{k})\,.\\\
$

Summing over all $k$ such that $d_{k}(w)=1$,

$\sum_{k:d_{k}(w)=1}{\rho}_{k}(A_{+}f)(w)=\sum_{k:d_{k}(w)=1}\sum_{d_{\nu}(\tilde{w}_{k})=2}f(\widetilde{(w_{\nu}^{-})}_{k})=\sum_{\nu:\,d_{\nu}(w)=2}\sum_{k:d_{k}(w)=1}f(\widetilde{(w_{\nu}^{-})}_{k})\,\\\
=\sum_{\nu:\,d_{\nu}(w)=2}R_{1}f(w_{\nu}^{-})={A}_{+}(R_{1}f)(w)=\lambda({A}_{+}f)(w)\,$

if $f$ is a $\lambda$-eigenvector of $R_{1}$. Thus $A_{(p,q)\to(p-1,q+1)}$
preserves eigenvalues of $R_{1}$. ∎

As a further observation, each coordinate reflection $\rho_{k}$ commutes with
$R_{1}$, the sum of the level-one coordinate reflections. Consequently,
coordinate reflections preserve eigenvalues of $R_{1}$. Thms. 2 and 7 played
crucial roles in the inductive steps of the proofs of the Thms. 6 and 9
describing adjacency invariant spaces on $\mathcal{C}_{3}^{N}$ and
$\mathcal{C}_{4}^{N}$, as they allowed to interchange inner and outer
adjacencies. In $\mathcal{C}_{5}^{N}$, the corresponding spaces of type
$\mathcal{V}_{p,q}$ also involve neutral adjacency maps at different levels.
To establish invariance of the corresponding spaces under inner adjacencies,
we need a similar method to interchange inner and neutral adjacencies.

On $\mathcal{C}_{5}^{N}$, the neutral adjacency operator is
$(A_{0}f)(w)=\sum_{d_{k}(w)=2}f(\tilde{w}_{k})$. When
$A_{+}=A_{(p,q)\to(p-1,q+1)}$, $A_{+}f(w)=\sum_{d_{\nu}(w)=2}f(w_{\nu}^{-})$,
so

$A_{0}A_{+}f(w)=\sum_{d_{k}(w)=2}A_{+}f(\tilde{w}_{k})=\sum_{d_{k}(w)=2}\sum_{d_{\nu}(w)=2}f((\tilde{w}_{k})_{\nu}^{-})\\\
=\sum_{d_{\nu}(w)=2}\sum_{d_{k}(w)=2}f((\tilde{w}_{k})_{\nu}^{-})=\sum_{d_{\nu}(w)=2}[f((\tilde{w}_{\nu})_{\nu}^{-})+\sum_{k\neq\nu,d_{k}(w)=2}f((\tilde{w}_{k})_{\nu}^{-})]\\\
=\sum_{d_{\nu}(w)=2}[f((\tilde{w}_{\nu})_{\nu}^{-})+(A_{0}f)(w_{\nu}^{-})]=(A_{+}A_{0}f)(w)+\sum_{d_{\nu}(w)=2}f((\tilde{w}_{\nu})_{\nu}^{-})\,.$

We refer to the commutator $A_{0}A_{+}-A_{+}A_{0}$ in the form
$A_{+}=A_{(p,q)\to(p-1,q+1)}$ that maps $f$ to
$(\widetilde{A_{+}}f)(v):=\sum_{\nu:d_{\nu}(v)=2}(\rho_{\nu}f)(v_{\nu}^{-})$
as _twisted outer adjacency_ since, without the reflections,
$(A_{+}f)(v)=\sum_{\nu:d_{\nu}(v)=2}f(v_{\nu}^{-})$.

If
$g(w)=\widetilde{A_{+}}f(w)=\sum_{d_{\nu}(w)=2}f((\widetilde{w_{\nu}^{-}})_{\nu})$,
$w\in\Sigma_{p-1,q+1}$, then

$(A_{-}g)(v)=\sum_{\sum_{\mu:d_{\mu}(v)=1}}\sum_{\nu:d_{\nu}(v_{\mu}^{+})=2}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu}),\quad
v\in\Sigma_{p,q}\,.$ (1)

But

$\sum_{\mu:d_{\mu}(v)=1}\sum_{d_{\nu}(v_{\mu}^{+})=2}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu})=\sum_{\mu:d_{\mu}(v)=1}\Bigl{[}f((\widetilde{(v_{\mu}^{+})_{\mu}^{-}})_{\mu})+\sum_{\nu\neq\mu,d_{\nu}(v_{\mu}^{+})=2}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu}))\Bigr{]}$
$=\sum_{\mu:d_{\mu}(v)=1}\Bigl{[}f(\tilde{v}_{\mu})+\sum_{d_{\nu}(v)=2}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu})\Bigr{]}=R_{1}f(v)+\sum_{\mu:d_{\mu}(v)=1}\sum_{d_{\nu}(v)=2}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu})$
(2)

since $d_{\mu}(v)=1$, $d_{\nu}(v_{\mu}^{+})=2$ and $\nu\neq\mu$ imply
$d_{\nu}(v)=2$.

For each fixed $\nu$ in the outer sum of

$\sum_{d_{\nu}(v)=2}\sum_{\mu:d_{\mu}(v)=1}f((\widetilde{(v_{\mu}^{+})_{\nu}^{-}})_{\nu})=\sum_{d_{\nu}(v)=2}\sum_{\mu:d_{\mu}(v)=1}f((\widetilde{(v_{\nu}^{-})_{\mu}^{+}})_{\nu}),$
(3)

the vertices $v\in\Sigma_{p,q}$ and
$\\{(v_{\nu}^{-})_{\mu}^{+}:d_{\mu}(v)=1\\}$ together form the set of
$(p,q)$-outer neighbors of $v_{\nu}^{-}\in\Sigma_{p+1,q-1}$ ($d_{\mu}(v)=1$
implies $\mu\neq\nu$). Thus, the inner sum on the right of (3), without
reflections, would amount to $-f(v)+(A_{-}f)(v_{\nu}^{-})$. Accounting for
reflections, the inner sum (for fixed $\nu$) is
$-f(\tilde{v}_{\nu})+(\rho_{\nu}A_{-}f)(v_{\nu}^{-})$. Summing over
$\\{\nu:d_{\nu}(v)=2\\}=\\{\nu:d_{\nu}(v_{\nu}^{-})=1\\}$, the expression (3)
is then equal to

$-(A_{0}f)(v)+\sum_{\nu:d_{\nu}(v)=2}(\rho_{\nu}A_{-}f)(v_{\nu}^{-})\,.$ (4)

Combining (1), (2), and (4) gives the following.

######  Theorem 13.

Let $f$ be supported in $\Sigma_{p,q}$. Denote $A_{-}=A_{(p-1,q+1)\to(p,q)}$
and $A_{+}=A_{(p,q)\to(p-1,q+1)}$. Then

$(A_{-}(A_{0}A_{+}-A_{+}A_{0}))f(v)=((R_{1}-A_{0})f)(v)+\sum_{\nu:d_{\nu}(v)=2}(\rho_{\nu}A_{-}f)(v_{\nu}^{-})$
(5)

considered as operators on and between $\Sigma_{p,q}$ and
$\Sigma_{(p-1,q+1)}$.

The formula (5) can be rewritten as
$A_{-}\widetilde{A_{+}}f=(R_{1}-A_{0})f+\widetilde{A_{+}}A_{-}f$ where, on the
left, $A_{-}=A_{(p-1,q+1)\to(p,q)}$ and, on the right,
$A_{-}=A_{(p,q)\to(p+1,q-1)}$. The composition $A_{-}\widetilde{A_{+}}$
simplifies in some cases. For example, when $f$ itself is in the kernel of
$A_{-}$, one also has $\rho_{\nu}A_{-}f=0$ for each $\nu$ so
$\sum_{\nu:d_{\nu}(v)=2}(\rho_{\nu}A_{-}f)(v_{\nu}^{-})=0$ for each
$v\in\Sigma_{p,q}$. Consider next a case in which $f=A_{+}h$ where $h$ is
supported in $\Sigma_{p+1,q-1}$. Then

$A_{-}f=A_{-}A_{+}h=[A_{-},A_{+}]h+A_{+}A_{-}h=m(p+1,q-1)h+R_{1}h+(A_{+}A_{-})h$
(6)

where $m(p,q)=(2(N-q)-3p)$ by Thm. 10.

######  Theorem 14.

Denote by $\mathcal{W}_{p,q,\lambda,0}$ the space of vertex functions on
$\mathcal{C}_{5}^{N}$ supported in $\Sigma_{p,q}$ such that $f$ is in the
kernel of each subadjacency of $A_{-}$, is a $\lambda$-eigenvector of $R_{1}$,
and is an eigenvector of $A_{0}$. Let $\mathcal{V}_{p,q,\lambda}$ consist of
those vertex functions that are sums of multiples of images of elements of
$\mathcal{W}_{p,q,\lambda,0}$ under a sequence of compositions of
subadjacencies of $A_{0}$ and $A_{+}$. Then $\mathcal{V}_{p,q,\lambda}$ is
adjacency invariant.

###### Outline of Proof.

If $\mathcal{V}_{p,q,\lambda}$ did not include applications of $A_{0}$ in its
definition (only applications of $A_{+}$), then the proof would essentially
parallel that of Thm. 6. By definition, $\mathcal{V}_{p,q,\lambda}$ is
invariant under subadjacencies of $A_{0}$ and $A_{+}$. So it suffices to show
that it is invariant under subadjacencies of $A_{-}$. The proof is by
induction along similar lines as those of Thms 6 and 9. We argue that if a
composition of $k$ subadjacencies of $A_{+}$ and $A_{0}$ gets mapped back to
$\mathcal{V}_{p,q,\lambda}$ by the appropriate subadjacencies of $A_{-}$, then
so does any composition of $k+1$ subadjacencies of $A_{+}$ and $A_{0}$. The
base case ($k=1$) considers $A_{-}g$ where $g=A_{+}f$ or $g=A_{0}f$,
$f\in\mathcal{W}_{p,q,\lambda,0}$. The case $g=A_{0}f$ is trivial since $f$ is
an eigenvector of $A_{0}$ and in the kernel of $A_{-}$. The case $g=A_{+}f$
follows from Thm. 10 and the hypotheses that $R_{1}f=\lambda f$ and
$A_{-}f=0$.

Let $g_{r,s}$ be the component of $g\in\mathcal{V}_{p,q,\lambda}$ supported in
$\Sigma_{r,s}$, $r\geq p$ and $s\geq q$. We can assume that $g_{r,s}$ has one
of the forms (i) $A_{(r-1,s)\to(r,s)}g_{r-1,s}$, (ii)
$A_{(r+1,s-1)\to(r,s)}g_{r+1,s-1}$, or $A_{0}$ in the form $A_{(r,s)\to(r,s)}$
applied to one of these forms. Consider the specific case in which
$g_{r,s}=A_{(r-1,s)\to(r,s)}g_{r-1,s}$. Then

$A_{(r,s)\to(r-1,s)}g_{r,s}=(A_{(r,s)\to(r-1,s)}A_{(r-1,s)\to(r,s)}-A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)})g_{r-1,s}\\\
+A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)}g_{r-1,s}\\\
=(C+A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)})g_{r-1,s}\\\
=((2(N-s)-3(r-1))I+R_{1})g_{r-1,s}+A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)})g_{r-1,s}\\\
=[(2(N-s)+3(r-1)+\lambda_{r-1,s}]g_{r-1,s}+A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)})g_{r-1,s}$

by Thm. 10. Here, $\lambda_{r,s}$ is defined by
$R_{1}g_{r,s}=\lambda_{r,s}g_{r,s}$ according to the definition of $g$ as an
image of a fixed number of outer adjacencies applied to
$f\in\mathcal{W}_{p,q,\lambda,0}$, invoking Lem. 12 in the corresponding
number of instances, and observing that $R_{1}$ commutes with $A_{0}=R_{2}$,
the sum of reflections in level-two coordinates. On the other hand, if we
assume the induction hypothesis that any lower level components of
$g\in\mathcal{V}_{p,q,\lambda}$ are mapped back into
$\mathcal{V}_{p,q,\lambda}$ under inner adjacency, then
$A_{(r-1,s)\to(r-2,s)})g_{r-1,s}\in\mathcal{V}_{p,q,\lambda}$ and then so is
$A_{(r-2,s)\to(r-1,s)}A_{(r-1,s)\to(r-2,s)})g_{r-1,s}$. In this case, then,
$A_{(r,s)\to(r-1,s)}g_{r,s}\in\mathcal{V}_{p,q,\lambda}$. A corresponding
argument applies to prove that
$A_{(r,s)\to(r+1,s-1)}g_{r,s}\in\mathcal{V}_{p,q,\lambda}$.

To prove that $A_{(r,s)\to(r-1,s)}$ and $A_{(r,s)\to(r+1,s-1)}$ map
$A_{0}g_{r,s}$ back to $\mathcal{V}_{p,q,\lambda}$, first write
$A_{-}A_{0}g_{r,s}=A_{-}A_{0}A_{+}g_{r-1,s}=A_{-}[A_{0}A_{+}-A_{+}A_{0}]g_{r-1,s}+A_{-}A_{+}A_{0}g_{r-1,s}$.
The term $A_{-}A_{+}A_{0}g_{r-1,s}$ is shown to belong to
$\mathcal{V}_{p,q,\lambda}$ along the same lines as above with $g_{r-1,s}$
replaced by $A_{0}g_{r-1,s}$. The term $A_{-}[A_{0}A_{+}-A_{+}A_{0}]g_{r-1,s}$
is addressed using Thm. 13. Specifically, by (5),

$(A_{-}(A_{0}A_{+}-A_{+}A_{0}))g_{r-1,s}(v)=((R_{1}-A_{0})g_{r-1,s})(v)+\sum_{\nu:d_{\nu}(v)=2}(\rho_{\nu}A_{-}g_{r-1,s})(v_{\nu}^{-})\,.$
(7)

As above, $(R_{1}-A_{0})g_{r-1,s}\in\mathcal{V}_{p,q,\lambda}$. We can assume
$g_{r-1,s}=A_{+}h$ for some $h\in\mathcal{V}_{p,q,\lambda}$ where $h$ is the
image of a composition of strictly fewer outer or neutral adjacencies than
$g_{r-1,s}$. It follows from the induction hypothesis that
$A_{-}A_{+}h\in\mathcal{V}_{p,q,\lambda}$ (see also (6)), and then from the
definition of $\mathcal{V}_{p,q,\lambda}$ that
$\widetilde{A}_{+}A_{-}g_{r-1,s}$, the sum on the right in (7), also belongs
to $\mathcal{V}_{p,q,\lambda}$, since $\widetilde{A}_{+}=[A_{0},\,A_{+}]$. ∎

##  6 Application to spatio–spectral limiting

The current work is motivated in part by an effort to develop a theory
parallel to the Bell Labs theory of time and band limiting [8, 9, 14, 12, 13]
in the context of certain finite graphs, e.g., [6, 3]. The Bell Labs theory
studies eigenfunctions and eigenvalues of the operators $P_{\Omega}Q_{T}$
where $(Qf)(t)=f(t)\mathbbm{1}_{[-T,T]}$ and
$(P_{\Omega}f)(t)=(\mathcal{F}^{-1}\mathbbm{1}_{[-\Omega/2,\Omega/2]}\mathcal{F}f)(t)$
where $(\mathcal{F}f)(\xi)=\int_{-\infty}^{\infty}f(t)\,e^{-2\pi it\xi}\,dt$
is the Fourier transform on $\mathbb{R}$. The theory takes advantage, to an
extent, of the self-dual nature of the Fourier transform on $\mathbb{R}$. As
finite abelian groups, $\mathbb{Z}_{m}^{N}$ also have self-dual Fourier
transforms that can be realized as Kronecker powers of the matrix with $k$th
column $e^{2\pi ijk/m}$, $j,k=0,\dots,m-1$. Spatio–spectral limiting operators
on $\mathbb{Z}_{m}^{N}$ are analogues of $P_{\Omega}Q_{T}$, where an analogue
$Q$ of $Q_{T}$ truncates spatially on $\mathcal{C}_{m}^{N}$ by multiplying a
vertex function $f$ by the characteristic function of a symmetric neighborhood
of the origin, and an analogue $P$ of $P_{\Omega}$ truncates in the graph
Fourier transform domain by projecting onto the span of certain eigenvectors
of the graph Laplacian on $\mathcal{C}_{m}^{N}$. It is typical to truncate to
the space of vectors that are _bandlimited_ to eigenvalues below a certain
threshold, e.g., [10], but in the graph setting it can also be useful to
truncate to other eigenspaces of the graph Fourier transform, specifically in
questions of recovery from (sub)samples, e.g. [2].

We consider a very specific example here of spatio–spectral limiting in
$\mathcal{C}_{5}^{4}$, which has 625 vertices. We order the vertices first by
increasing distance $d(v)$ to the identity element of $\mathbb{Z}_{5}^{4}$,
then truncate by applying the diagonal matrix $Q$ equal to one on the indices
of the vertices of distance at most 3 from the origin. The truncated adjacency
matrix is shown in Fig. 2. We then restrict in the spectral domain also by
applying the graph Fourier transform $F$ (indexed with respect to the same
ordering), multiplying by the same matrix $Q$, and taking the inverse Fourier
transform. We write $P=F^{-1}QF$.

The cardinalities of $\Sigma_{p,q}$ ($p+2q\leq 3$) are listed in Tab. 1.
Altogether, there are $1+8+24+8+32+48=121$ vertices $v$ such that $d(v)\leq
3$. The range of $Q$ thus has dimension 121. The operator $P$ is injective on
this range, so the self-adjoint operator $PQ$ has 121 linearly independent
eigenvectors. In Figs. 4 and 5 we plot the Fourier transforms of the
eigenvectors $PQ$ (equivalently, the eigenvectors of $FPQF^{-1}$) arranged by
the base support $\Sigma_{p,q}$. As explained in [5], $FPQ$ is a polynomial in
the adjacency operator and these eigenvectors lie in spaces of the form
$\mathcal{V}_{p,q,\lambda}$. The vectors were computed using the svd function
in matlab.

We refer to the vectors plotted in Fig. 4 as _level vectors_. They are
constant on the distance level sets $\Sigma_{p,q}$. Their span is that of the
vectors in the space $\mathcal{V}_{0,0}$ that are nonzero on $\Sigma_{0,0}$.
The dimension (six) is the number of distinct levels (neutral adjacencies in
Thm. 14 preserve the property of being constant on each level), and thus the
number of potential nonzero coefficients $c_{k}$ of a vector in
$\mathcal{V}_{0,0}$ vanishing on $\\{v:d(v)>3\\}$. Consider next the vectors
whose base support lies in $\Sigma_{1,0}$. Here there are six eigenspaces each
of dimensions 3 and 4 (see Tab. 2). The number of eigenspaces of $FPQ$ of each
dimension is equal to the number of free coefficients of nonzero outer
subadjacencies defining those $\mathcal{V}_{1,0}$ vectors vanishing on
$\\{v:d((v)>3\\}$. The dimension of each eigenspace is determined by the
conditions of Thm. 14. The set $\Sigma_{1,0}$ has eight vertices coming in
coordinate pairs. Eigenspaces of the reflection $R_{1}$ on vectors supported
in $\Sigma_{1,0}$ thus have dimension four. Eigenvectors of $R_{1}$ with
eigenvalue $-1$ automatically have average value zero so are orthogonal to
constant vectors on $\Sigma_{1,0}$ (hence in kernel of $A_{-}$), but for
eigenvectors of $R_{1}$ with eigenvalue $+1$, having average zero is an
additional constraint on the coefficients of $g\in\mathcal{V}_{1,0,1}$ in its
expansion in compositions of $A_{+}$ and $A_{0}$ on
$f\in\mathcal{W}_{1,0,1,0}$, in order to be orthogonal to constants. This
implies that the $1$-eigenspaces of $R_{1}$ on $\Sigma_{1,0}$ in the kernel of
$A_{0}$ can have dimension at most three. The dimensions of the eigenspaces of
$FPQ$ based on the other levels $\Sigma_{p,q}$ listed in Tab. 2 can be
explained along similar lines. There are no eigenvectors with base support in
$\Sigma_{0,1}$.

Table 1:  Cardinalities of distance level sets Base | Cardinality | Indices
---|---|---
$\Sigma_{0,0}$ | 1 | 1
$\Sigma_{1,0}$ | $\binom{4}{1}\times 2=8$ | 2–9
$\Sigma_{2,0}$ | $\binom{4}{2}\times 4=24$ | 10–33
$\Sigma_{0,1}$ | $\binom{4}{1}\times 2=8$ | 34–41
$\Sigma_{3,0}$ | $\binom{4}{3}\times 8=32$ | 42–73
$\Sigma_{1,1}$ | $\binom{4}{1}\times\binom{3}{1}\times 4=48$ | 74–121
Table 2:  Eigenspaces of $PQ$, $m=5$, $N=4$, $K=3$ Base | Dim (#) |  $R_{1}$ eigenvalue | eigenvector indices
---|---|---|---
$\Sigma_{0,0}$ | 1 (6) | 0 | 1,9,29,92,93,121
$\Sigma_{1,0}$ | 4 (6) | $-1$ | 5-8,30-33,37-40,59-62,110-113,117-120
$\Sigma_{1,0}$ | 3 (6) | 1 | 2-4,10-12,49-51,56-58, 89-91,114-116
$\Sigma_{2,0}$ | 6 (2) | $-2$ | 23-28,96-101
$\Sigma_{2,0}$ | 8 (3) | 0 | 15-22,41-48,102-109
$\Sigma_{2,0}$ | 2 (2) | 2 | 13-14,94-95
$\Sigma_{3,0}$ | 4 (1) | $-3$ | 52-55
$\Sigma_{3,0}$ | 18 (1) | $-1$ | 63-80
$\Sigma_{3,0}$ | 8 (1) | 1 | 81-88
$\Sigma_{1,1}$ | 3 (1) | $-1$ | 34-36
Figure 2:  Adjacency matrix, $m=5$, $N=4$ (left) and principal minor of size
121 (right). Vector indices are ordered by increasing level $p+2q$, and by
increasing $q$ for fixed $p+2q$.  Figure 3:  Nonzero eigenvalues of $PQ$,
$m=5$, $N=4$, $K=3$. Intervals of fixed eigenvalue conform to indices of the
eigenspaces listed in Tab. 2 Figure 4:  Real parts of eigenvectors of the
matrix $FPQ$, $m=5$, $N=4$, $K=3$. These are the vectors listed in Tab. 2 with
base $\Sigma_{0,0}$. They are constant on the level sets $\Sigma_{p,q}$ Figure
5:  Partially sorted eigenvectors of the matrix $FPQ$, $m=5$, $N=4$, $K=3$.
Real part of one eigenvector is plotted from each group listed in Tab. 2
corresponding to base level greater than zero. Values are sorted within each
level set to make value symmetries more evident

##  7 Conclusions

We have described certain spaces of vertex functions on products of cycles
$\mathcal{C}_{m}^{N}$ for $m=3,4,5$ that are invariant under the adjacency
operators on these Cayley graphs. In the cases $m=3,4$ these spaces are
observed to be isomorphic to spaces of the form
$\mathcal{W}_{L}\times\mathbb{C}^{M}$ where $\mathcal{W}_{L}$ is a space of
vectors supported on a set $L$ of fixed path distance to the identity of
$\mathbb{Z}_{m}^{N}$, and the action of the adjacency operator can be
expressed solely on the $\mathbb{C}^{M}$ factor. The techniques can be
extended to describe corresponding adjacency-invariant spaces on
$\mathcal{C}_{m}^{N}$ for larger $N$ in terms of inner- and-outer
subadjacencies, and level-one and level $m/2-1$ reflections ($m$-even), or
level-one reflections and level $(m-1)/2$ neutral adjacencies ($m$ odd).
Completeness properties—how to decompose the restriction of a vertex function
to a neighborhood of the identity into a sum of terms, each of which lies in
one of the invariant spaces described here—will be addressed in future work
(cf., [5] for the $\mathbb{Z}_{2}^{N}$ case).

The results presented here, of course, do not readily extend to broad families
of graphs. The methods should extend, with further complication, to powers of
other small graphs having ample symmetry, e.g., [3].

## References

  * [1] J.J. Benedetto and P.J. Koprowski, _Graph theoretic uncertainty principles_ , 2015 International Conference on Sampling Theory and Applications (SampTA), May 2015, pp. 357–361.
  * [2] S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, _Discrete signal processing on graphs: Sampling theory_ , IEEE Trans. Signal Process. 63 (2015), no. 24, 6510–6523.
  * [3] J.A. Hogan and J.D. Lakey, _Spatio-spectral limiting on redundant cubes: A case study_ , preprint.
  * [4] J.A. Hogan and J.D. Lakey, _Duration and Bandwidth Limiting. Prolate Functions, Sampling, and Applications._ , Birkhäuser, Boston, MA, 2012.
  * [5] J.A. Hogan and J.D. Lakey, _Spatio-spectral limiting on hypercubes: eigenspaces_ , 2018.
  * [6] , _An analogue of Slepian vectors on Boolean hypercubes_ , J. Fourier Anal. Appl. 25 (2019), 2004–2020, Online first.
  * [7] T. Kurokawa, T. Oki, and H. Nagao, _Multi-dimensional graph fourier transform_ , 2017.
  * [8] H.J. Landau and H.O. Pollak, _Prolate spheroidal wave functions, Fourier analysis and uncertainty. II_ , Bell System Tech. J. 40 (1961), 65–84.
  * [9] , _Prolate spheroidal wave functions, Fourier analysis and uncertainty. III. The dimension of the space of essentially time- and band-limited signals._ , Bell System Tech. J. 41 (1962), 1295–1336.
  * [10] I. Pesenson, _Sampling in Paley-Wiener spaces on combinatorial graphs_ , Trans. Amer. Math. Soc. 360 (2008), no. 10, 5603–5627.
  * [11] A. Sandryhaila and J. M. F. Moura, _Discrete signal processing on graphs_ , IEEE Trans. Signal Process. 61 (2013), no. 7, 1644–1656.
  * [12] D. Slepian, _Prolate spheroidal wave functions, Fourier analysis and uncertainty. IV. Extensions to many dimensions; generalized prolate spheroidal functions_ , Bell System Tech. J. 43 (1964), 3009–3057.
  * [13] , _Prolate spheroidal wave functions, Fourier analysis, and uncertainty. V - The discrete case_ , Bell System Tech. J. 57 (1978), 1371–1430.
  * [14] D. Slepian and H.O. Pollak, _Prolate spheroidal wave functions, Fourier analysis and uncertainty. I_ , Bell System Tech. J. 40 (1961), 43–63.
  * [15] M. Tsitsvero, S. Barbarossa, and P. Di Lorenzo, _Signals on graphs: Uncertainty principle and sampling_ , IEEE Trans. Signal Process. 64 (2016), 4845–4860.


# “FIJO”: a French Insurance Soft Skill Detection Dataset

###### Abstract.

Understanding the evolution of job requirements is becoming more important for
workers, companies and public organizations to follow the fast transformation
of the employment market. Fortunately, recent natural language processing
(NLP) approaches allow for the development of methods to automatically extract
information from job ads and recognize skills more precisely. However, these
efficient approaches need a large amount of annotated data from the studied
domain which is difficult to access, mainly due to intellectual property. This
article proposes a new public dataset, FIJO, containing insurance job offers,
including many soft skill annotations. To understand the potential of this
dataset, we detail some characteristics and some limitations. Then, we present
the results of skill detection algorithms using a named entity recognition
approach and show that transformers-based models have good token-wise
performances on this dataset. Lastly, we analyze some errors made by our best
model to emphasize the difficulties that may arise when applying NLP
approaches.

###### keywords:

Keywords: Soft Skill Detection, NLP, French Supervised Corpus, Machine
Learning

David Beauchemin⋄, Julien Laumonier*⋄, Yvan Le Ster⋄, Marouane Yassine⋄
---
Departement of Computer Science and Software Engineering, Université Laval,
Québec, Canada
Institute Intelligence and Data, Université Laval, Québec, Canada

<EMAIL_ADDRESS>
##  1\. Introduction

††⋄Authors contributed equally to this work.

The digital transformation’s impact on professional practices has led to a
rapid evolution of in-demand job skills, making it difficult to track these
changes for enterprises and workers. Manual evaluation is becoming exceedingly
complex and time-consuming, justifying the need for an automatic evaluation of
these changes [bakhshi_future_2017]. One way to study these changes in job ads
is automatic skills recognition [squicciarini_demand_2021].

However, job offer data is not easy to access even in job offers web
platforms, mainly due to intellectual property issues. Moreover, the
annotation needed to achieve good skill recognition performances through
supervised machine learning is another complex and costly task. Indeed, many
datasets offering job descriptions are accessible online such as the
`mycareersfuture` public dataset [bhola_retrieving_2020]. However, as
[khaouja2021survey] reported in their article, very few public annotated
datasets exist, and none are in French.

As contributions, in this article, we propose “French Insurance Job Offer
(FIJO)”, a free and public non-annotated and annotated dataset, to facilitate
research in this domain. This dataset focuses on soft skills, which describe
the way employees work alone and with others, instead of hard skills, which
represent a more formal knowledge used at work [lyu2021soft]. Also, we explore
the training of a token-wise NER French skill detection algorithm in the field
of insurance with state-of-the-art algorithms111All code used to obtain these
results will be available on GitHub here..

The rest of this paper is structured as follows. Firstly, we begin with a
brief overview of the literature on skill detection in section 2. Secondly, we
will present FIJO in section 3, including how we constructed our French
complexity corpus, some statistics and analysis of the dataset. Third, we will
present our skill detection algorithm, the training settings and our results
in section 4. Finally, we will draw some concluding remarks in section 5.

##  2\. Related work

The first approach to recognizing skills inside a job offer is using
statistical techniques. It is a commonly used approach in many pieces of work
such as [malherbe_bridge_2016] who detect hard and soft skills in job offers
by matching a list of keywords in the text with a skill database. Their skill
database uses external databases knowledge, namely DBPedia and StackOverflow.
Other works [sodhi_content_2010, gardiner_skill_2018,
squicciarini_demand_2021] do not rely on skills databases but use content
analysis to detect the presence of certain words or concepts in offers.

Other approaches using machine learning to detect skills in job offers have
received lots of attention recently [khaouja2021survey]. The skill recognition
problem has been modeled either using topic modeling through Latent Dirichlet
Analysis [gurcan_big_2019], text classification with CNN and LSTM
[sayfullina2018learning], or NER with LSTM [jia_representation_2018] and
transformer-based models [tamburri_dataops_2020]. However, these pieces of
work mainly focus on specialized skills (e. g. IT skill [gurcan_big_2019]),
focus on soft skill [sayfullina2018learning] or are applied on English job ads
only.

As per [khaouja2021survey], the conclusion in their survey on skill
identification shows that very few datasets are available online. Most of the
recent works do not release their dataset nor mention the reasons for the non-
publication. For example, [cerioli20205] uses content analysis, and 5 million
non-annotated jobs adds to determine whether or not testing software is a
standard in the IT industries. The possible reason for the lack of publication
by the authors was possibly due to the intellectual property constraint from
their industrial partner. However, a recent new public dataset released by
[bhola_retrieving_2020] focuses on extracting identified hard skills in job
ads. The dataset consists of 20,298 job ads, where each ad includes nearly 20
hard skills on average. A unique skill term corresponds to a unique class.
Thus, the overall dataset includes 2,548 skill classes. For example,
“Microsoft Word” is a skill, and “Microsoft Excel” is another skill. This new
dataset lacks annotation for soft skills that have been more required than
hard skills by enterprises in the past decade [lyu2021soft].

##  3\. Data

FIJO was created in partnership with four Canadian insurance companies. The
dataset consists of non-annotated and annotated French job ads published by
them, as well as their metadata (e. g. date of publication) between the years
2009 to 2020. Each job offer’s text was manually extracted and semi-manually
cleaned using the following procedure: removal of carriage return in an
incomplete sentence (this is due to bullet point text) and multiple carriage
returns, removal of bullet point character, normalization of the apostrophe
punctuation characters, and removing of trailing whitespace at the beginning
or end of a sentence. In order to protect the interests of the companies to
whom the published data belongs, we chose to de-identify the job ads before
making them publicly available. This process consists of three steps. Firstly,
we used regular expressions to substitute the different variations of the
companies’ names and email addresses present in the offers. Next, a SpaCy
French pre-trained NER model (`fr_core_news_lg`) was used to identify
potential names and locations to help with the following step. Finally, a
manual check was conducted on each offer to substitute the following elements:
names, locations, postal addresses and miscellaneous elements that could help
identify the companies (i. e. products, department names). Table 1 describes
the substitution tags employed.

Substitution tag | Description
---|---
<anon_name> | A person’s name
<anon_location> | A postal address or a city
<anon_company> | One of the companies’ names
<anon_misc> | An element that can help identify one of the companies
Table 1. Substitution tags used for de-identification

###  3.1. Dataset Statistics

The dataset is composed of 867 de-identified French job ads. As shown in
Figure 2, job ads lengths vary greatly, with an average length of 300.97 and a
standard deviation of 119.78 tokens222Punctuations are computed as a token. We
do so since our pre-processing procedure does not include the removal of
punctuation nor lemmatization, or stemming.. We can also observe that a few
offers (16) are outliers with a length of more than 572. Moreover, Table 2
presents statistics of the dataset, where the lexical richness corresponds to
the ratio of a job offer’s number of unique words over the vocabulary
cardinality without removing the stop words or normalizing them
[van2007comparing]. We can see that the lexical richness is relatively low,
which means they are quite similar in terms of vocabulary.

Average # of Words | 300.97 | # of Words | 260,942 | Average # of Sentences | 20.66
---|---|---|---|---|---
# of Unique Words | 5,931 | Average Sentence Length | 14.57 | Average Lexical Richness | 0.023
Table 2. Unannotated dataset statistics

Figure 1. Ads length by words

Figure 2. Example of a French annotation where each color refers to a class
(i. e. skill)

###  3.2. Annotated Dataset

To learn to identify soft skills inside ads, 47 offers were annotated, and
more precisely, each job offer sentence, for a total of 499 annotations. Our
annotation process consists of creating a skills reference, which defines the
skills used for the annotations, and randomly selecting 47 offers to be
annotated by a domain expert. Annotation was conducted with non-overlapping
sentence entities done individually. However, the overall job offer was given
as a reference to the annotator for context. Each entity contains at least one
word or, at most, the complete sentence.

Based on the skill groups of the AQESSS public skills repositories and the one
used by our insurance partners, which are based on the commercial Korn Ferry
and SPB repositories, a set of four skills have been identified. Namely,
“Thoughts”, “Results”, “Relational” and “Personal”333The tag are written in
French in the dataset. Namely, “Pensée”, “Résultats”, “Relationnel” and
“Personnel”.. The number of classes has been limited to four mainly because,
in general, learning algorithms are not known for being inefficient on a large
number of tags [JMLR:v15:gupta14a] but also because of the possible confusion
between skills during the annotation process (see subsection 3.4). Figure 2
presents an example of a sentence annotation.

###  3.3. Annotated Dataset Statistics

First, as shown in Figure 5 our annotated portion of FIJO consists of 932
entities distributed unevenly between the four classes. We can see that the
class with the most entities is “Thoughts” with 317 entities, followed by
“Personal” with 297 and “Relational” with 216. The class with the lowest
number of entities is “Results” with 102 entities. Second, as illustrated in
Figure 5, our entities are on average 9.6 long with a standard deviation of
7.14 tokens. Their length ranges from a single token to 50 tokens, but 50% are
below 8. Moreover, Table 3 presents statistics of the dataset. We have a
similar average number of words and sentences as per the non-annotated
dataset. However, our annotated dataset uses fewer words and even fewer unique
words. Finally, Figure 5 presents the number of occurrences of stop words in
an entity text (blue) or outside of an entity (red). It shows that some stop
words are overly represented in entities, such as “de” and “des” that are
mostly in annotations since long skills tend to contain a high number of stop
words.

Av. # of |  | # of |
---|---|---|---
Words | 270.26 | Words | 12,702
Sentences | 16.28 | Unique Words | 1,902

Table 3. Annotated dataset statistics

Figure 3. Number of entities per class

Figure 4. Distribution of entities length base on their tokens

Figure 5. Number of time a stopwords occur in an entity (blue) or out of an
entity (red)

###  3.4. Dataset Limitations

We have identified three limitations to our dataset: unbalanced entities
classes, lexical overlapping and soft skill identification.

Firstly, as illustrated in Figure 5, our annotated dataset is composed of an
unbalanced number of classes where two classes are more represented than the
two others. When classes imbalance exists in training data, a classification
algorithm will typically over-classify the majority group (“Thoughts”) due to
its increased prior probability. As a result, the instances belonging to the
minority group (“Results”) will likely be misclassified more often than those
belonging to the majority group [johnson2019survey].

Secondly, footnote 5 illustrates the 2-dimension PCA of the TF-IDF score of
each entity’s text after stop words removal and lemmatization, separated by
class. It shows that we can separate the terms (and centroids) present in
skills from those that are not. For example, the “Personal” (purple) centroid
(upper left) and “Thoughts” (red) centroid (down left) can be distinctly
separated from each other and the other two centroids. Such separation may
make it easier to discern the two cases since skills use specific terms that
are less common in other skill texts. For example, the word “collaborer”
(collaborate) appears only in the “Personal” entities. By contrast, well-
distributed terms among the different groups may be more challenging. For
example, the word “atteindre” (achieve) occurs in all four classes. However,
we can also see that some terms are quite close to each other, possibly
leading to a more difficult distinction between the four classes’ word
terminologies.

Figure 6. 2-dimensions555The third dimension is not represented here due to
difficulty representing the third dimension in a non-reactive figure. However,
we would like to clarify that using the third dimension makes the “Relational”
and “Results” class way more spaced out than in two dimensions only. PCA of
the TF-IDF separated by entities groups with the removal of stop words and
lemmatization of terms

Finally, soft skill identification is not an easy task, as mentioned by
[squicciarini_demand_2021], and our dataset reflects it. Firstly, some
distinctions between skills can be quite confusing, as seen in the example in
Figure 9. This example can be read as “Welcoming visitors and responding to
their various requests for information” and is tagged as Thoughts. However,
one reader might find that such a skill could also represent a Relational one.
Thus, creating a confusing distinction between some examples. Secondly, some
examples contain two consecutive skills of the same class separated by
coordinating conjunctions as seen in Figure 9. We can see that the French
coordinating conjunction “et” (and) split the two Personal entities. However,
such coordinating conjunction is not always used to do so. It can also be used
as an addition of information, such as in “vérifier et contrôler” (verify and
control). Thus, it can be quite challenging to determine if a subset of a
sentence is one or two skills in some cases. Finally, it is common to see job
ads that list expected soft skills in the same sentence, but all skills do not
belong to the same skill class. An example of such switching between two
entity types is illustrated in Figure 9. We can see that the first token is an
entity, followed by another entity of a different type and the rest of the
sentence is another entity of the same class as the first entity. This kind of
“squeezing” of two entities sharing the same class around an entity of a
different class can be challenging for a NER model. All these limitations
justify the fact that, in this article, we apply token-wise approaches to the
dataset to start with an easier learning task.

Figure 7. An example of a possible confusion between the classes “Thoughts”
and “Relational” (“Welcoming visitors and responding to their various requests
for information”)

Figure 8. An example of two consecutive skill annotations with the same class
that are separated by a coordinating conjunction

Figure 9. An example of an entity “squeezed” between two other entity of a
different class

##  4\. Skill detection

Since skill detection is a sequence classification task similar to NER, we
approach it using a recurrent neural network, namely a bidirectional long
short-term memory (bi-LSTM) network [lstm]. First of all, we encode each word
in a given sequence using FastText’s pre-trained French embedding model
[Bojanowski2017EnrichingWV] which produces 300-dimensional word embeddings.
Once a sequence is encoded, we feed each of the word embeddings to our bi-LSTM
which has a hidden state dimension of 300 and obtain a new representation for
each word. The final step in the prediction process is to classify each word
using a fully connected network comprised of one linear layer followed by a
softmax activation function.

LSTM-based classifiers have proven to be quite efficient in terms of
performance for sequence classification tasks. However, these models usually
require a large amount of data to guarantee such performances. Therefore,
since our annotated dataset contains a limited amount of data, we also use a
pre-trained transformer model [transformer] in a transfer learning setting.
Our model of choice is CamemBERT [martin-etal-2020-camembert] a French
transformer encoder based on the BERT architecture
[DBLP:conf/naacl/DevlinCLT19]. Consequently, we use it to encode our text
sequence, and we employ a fully connected network identical to the one
employed with the bi-LSTM model in order to accomplish the classification. We
experiment with two configurations of this model, one in which CamemBERT’s
weights are frozen and one in which they are not. We dub these models
CamemBERT frozen and CamemBERT unfrozen respectively.

To further investigate the sensibility of our models to the amount of training
data, as well as the transfer learning potential of the pre-trained
transformer model, we experiment with different data subset sizes and report
the results in subsection 4.2.

###  4.1. Experiments

We train each of the aforementioned models five times using different random
initialization seeds ($[5,10,15,20,25]$). The models were trained for 300
epochs at most with an initial learning rate of $0.01$ for bi-LSTM and
CamemBERT frozen and of $0.0001$ for CamemBERT unfrozen as suggested by
[DBLP:conf/naacl/DevlinCLT19]. Therefore, a learning rate schedule that
decreased the learning rate by a factor of 0.1 after every five epochs without
any decrease of the validation cross-entropy loss was applied. An early
stopping with a patience of 15 epochs to prevent overfitting. Additionally,
for the CamemBERT unfrozen model, we experimented with the training procedure
and hyperparameters proposed in [mosbach2021on] in order to address the
possible training instability associated with fine-tuning transformer-based
language models. As such, an additional five experiments (using the same
random seeds) were run with CamemBERT unfrozen by limiting the number of
epochs to $20$ and scheduling the learning rate as follows: we start the
training with a linear learning rate warmup (i. e. the learning rate was
linearly increased) up to $0.2\mathrm{e}{-5}$ for the first $10\%$ of epochs,
followed by a linear learning rate decay for the rest of the training epochs.
We use CamemBERT unfrozen warmup to refer to this model.

The training data was divided using a $80\%-10\%-10\%$ train-validation-test
split with simple random sampling, resulting in a total of $400$ training
samples. We also experiment with different training data subsets. Each subset
is composed by sampling the first X data samples from the full training set
placed in order, with $\mathrm{X}\in\\{50,100,150,200,350,400\\}$.

The models and training procedures were implemented using Poutyne [poutyne],
HuggingFace’s Transformers [wolf-etal-2020-transformers] and spaCy
[Honnibal_spaCy_Industrial-strength_Natural_2020].

###  4.2. Results

Data subset size | CamemBERT unfrozen warmup | CamemBERT unfrozen | CamemBERT frozen | bi-LSTM
---|---|---|---|---
50 | $46.40\pm 3.72$ | $61.25\pm 5.23$ | $46.55\pm 0.59$ | $25.53\pm 0.58$
100 | $66.71\pm 6.86$ | $75.24\pm 2.13$ | $56.02\pm 0.22$ | $43.74\pm 15.64$
150 | $75.73\pm 2.39$ | $77.67\pm 1.54$ | $59.87\pm 0.28$ | $47.92\pm 7.72$
200 | $76.40\pm 2.57$ | $79.78\pm 1.12$ | $64.23\pm 0.21$ | $55.44\pm 6.43$
250 | $78.97\pm 2.03$ | $80.23\pm 3.82$ | $65.78\pm 1.64$ | $57.71\pm 10.65$
300 | $78.18\pm 0.78$ | $74.99\pm 4.76$ | $61.99\pm 0.22$ | $53.24\pm 2.85$
350 | $78.27\pm 3.73$ | $78.72\pm 2.42$ | $\mathbf{67.47\pm 0.21}$ | $56.34\pm 4.25$
400 | $\mathbf{80.85\pm 1.67}$ | $\mathbf{83.69\pm 1.80}$ | $67.29\pm 0.23$ | $\mathbf{60.69\pm 9.23}$

Table 4. Mean token-wise accuracy and one standard deviation on test data
across different seeds for training subsets (bold values correspond to maximum
mean accuracy for a model)

Table 4 presents the mean token-wise accuracy and one standard deviation on
the test set for the four trained models where bold values correspond to
maximum mean accuracy for each model. As expected, fine-tuning the complete
CamemBERT model yields the best performance with both CamemBERT unfrozen and
CamemBERT unfrozen warmup leading the scoreboard. Based on the accuracy, the
best single model performance is obtained with CamemBERT unfrozen. However, a
McNemar normalize test [mcnemar1947note] using the contingency table
illustrated in Table 5 of both unfrozen models using only the best seed model
per approach (i. e. 20 and 25, respectively) yielded a p-value of $0.5334$.
Thus, we can only assume no significant difference between the predictive
models.

| CamemBERT unfrozen
---|---
Correct | Incorrect
CamemBERT unfrozen warmup | Correct | 1367 | 78
Incorrect | 87 | 94
Table 5. Contingency table for unfrozen models (token-wise) using only the
best seed model per approach (i. e. 20 and 25, respectively)

Moreover, the CamemBERT unfrozen model seems to suffer from a certain degree
of instability, as shown by the consistently high standard deviation. This
issue mostly persists when using a learning rate warmup followed by a linear
decay as proposed by [mosbach2021on]. CamemBERT frozen is the least sensitive
to random initialization while bi-LSTM presents the highest sensitivity and
the lowest performance. When it comes to training subsets, we can observe that
all models perform best with a high amount of data. However, performance seems
quite close across the 200 to 350 subset size range. We hypothesize that this
is due to the data distribution of the training and test sets since companies
use slightly different ways to express skills. For example, one uses a bullet
point style to enumerate skills in a pragmatic approach, while another uses a
more situational approach that puts skill within context. Thus, Figure 10
shows that both the train and test sets contain skills belonging, in the
majority, to one company (sky blue). Two more companies (light green and pink)
are present in the test set, while their skills are underrepresented in the
training set. Furthermore, Figure 11 shows that the dominant company’s (sky
blue) skills are well represented in most training subsets, including smaller-
sized ones, while augmenting the number of training samples mostly adds skills
related to the company that is not present at all in the test set (red). It
means that the training is quite sensitive to how the data is shuffled because
of the limited number of data samples. Therefore, more data would need to be
annotated to reach a more balanced dataset and use a stratified random
sampling instead of the current simple random sampling to reflect imbalance
better when splitting the data.

Figure 10. Number of tokens per skill in the annotated dataset (the “O” tag
means that a token doesn’t belong to a skill) where each colour represents one
of our four company partners Figure 11. Number of tokens per skill in the
training subsets dataset where each colour represents one of our four company
partners

Finally, Table 6 presents the mean token-wise accuracy and one standard
deviation per skill on the test set for CamemBERT unfrozen warmup and
CamemBERT unfrozen for a subset size of $400$. We can see that for both
approaches, the best performance occurs in the class with the lowest example
(Results). We hypothesize that it might be due to the “simplicity” of those
examples that are shorter than the average with an average length of around
seven tokens. Thus, these examples are possibly more straightforward than the
others, leading to an easier classification. Also, we observe a higher
variance on both Thoughts and Personal class for both our models. These two
tags have the highest standard deviation, even if they are the classes with
the most examples. It means that the training is quite sensitive to the
initialization of the models. Because we have a limited number of data
samples, minimizing such instability during training is more difficult.
Therefore, more data would need to be annotated to reach a more stable
training for all classes. Furthermore, we can see that there is still room for
improvement for most tags.

CamemBERT unfrozen warmup | CamemBERT unfrozen
---|---
O | Thoughts | Results | Relational | Personal | O | Thoughts | Results | Relational | Personal
$84.50\pm 4.51$ | $82.72\pm 7.84$ | $91.21\pm 0.00$ | $73.41\pm 4.44$ | $80.77\pm 4.97$ | $83.30\pm 3.63$ | $80.97\pm 6.56$ | $92.31\pm 4.85$ | $77.73\pm 3.48$ | $85.21\pm 9.65$

Table 6. Mean token-wise accuracy and one standard deviation per skill for
CamemBERT unfrozen warmup and CamemBERT unfrozen on the test set for a subset
size of $400$ (the “O” tag means that a token does not belong to a skill)

###  4.3. Error Analysis

Using the approaches that yielded the higher accuracy (CamemBERT unfrozen), we
conducted an error analysis on is 24 errors. We found that most of these were
types that are similar to the cases illustrated in Figure 9, namely two
consecutive skill annotations with the same class but separated by a
coordination conjunction. The NER identified the two skills as a single skill
in all those error cases. Moreover, some cases (3) were a similar error type
where a part of the sentence, before a coordination conjunction, is not an
entity as illustrated in Figure 12. The figure introduces each token’s ground
truth and prediction (“Prob” rows), along with the model probabilities, using
the same color scheme as footnote 5, namely red is the “Thoughts” class,
purple is “Personal”, blue is “Relational”, orange is “Results”, and green is
a word not in an entity. We can see that not only does the NER wrongly predict
the class, Personal rather than Thoughts, but it also wrongly predicted that
the first part of the sentence, “les dossiers sont de nature courante”, is
also a skill. We hypothesize that it is due to two things. First of all, the
presence of the words “dossiers”, “nature”, “courante” that appear in other
Personal examples. For instance, the word “dossiers” appears 49 times in a
Personal entity, which could confuse our model as to whether such a sentence
piece is a skill. Second of all, the presence of the coordinating conjunction
“et” plus the determinant “les” which mostly appear within an entity and
rarely appear just outside of it (a token before). We argue that our model
annotated the overall sentence as a skill in that specific case due to the
overwhelming examples of such cases. However, the entity class prediction is
inconsistent with the sentence vocabulary distribution. The second part of the
sentence is composed of words that only appear in Thoughts examples, such as
“décision”, “analyse” and “recherche”. It leads to lower probability
confidence of our NER, where those three words have the lowest probabilities.

Token | les | dossiers | sont | de | nature | courante | et | les | décisions
---|---|---|---|---|---|---|---|---|---
Prob | 0.82 | 0.80 | 0.83 | 0.84 | 0.83 | 0.83 | 0.78 | 0.53 | 0.49
Token | requièrent | un | niveau | habituel | d’ | analyse | et | de | recherche
Prob | 0.81 | 0.85 | 0.82 | 0.83 | 0.78 | 0.51 | 0.73 | 0.74 | 0.64
Figure 12. Example of a wrongly predicted sentence using the best seed
CamemBERT unfrozen model where color represent the skill class (red is the
“Thoughts” class, purple is “Personal”, blue is “Relational”, orange is
“Results”, and green is a word not in an entity)

##  5\. Conclusion

This article presents a new public dataset in French, including annotated and
non-annotated job offers in the insurance domain. It aims to develop machine
learning models to perform automatic skill recognition inside job ads, which
is an increasingly useful task for understanding the evolution of the labour
market. The dataset statistics and characteristics show limitations that could
have made it challenging to perform the learning task well. It can be further
improved by rebalancing companies’ and skill classes’ to make the annotated
dataset more representative of the non-annotated distribution. Moreover, the
impact of lexical overlapping and soft skill identification could be lowered
by allowing more experts to annotate more job ads. In any case, this dataset
will be improved by adding annotations.

Despite these dataset limitations, we have obtained interesting results with
pre-trained models despite the size of the dataset with a token-wise approach.
Although the skill-wise problem is closer to our main objective, our
preliminary experiments on the skill-wise problem with common NLP algorithms
seem to lead to poor accuracy. Since our results here are token-wise and not
skill-wise, it is harder to extract the correct span of skill entities, and
consequently, we cannot conclude the actual number of skills inside the non-
annotated dataset. Thus, our work is a first step toward discovering some
trends in the labour market and studying the evolution of skills. As our next
step, our objective is to make efficient models identifying skills instead of
tokens. Indeed, our models cannot distinguish two skills with the same tag if
they are next to each other. Therefore, we need to detect the beginning of
each skill inside the text. To achieve that, we plan to use the BIO tags
scheme instead of IO [konkol2015segment]. However, adding a new beginning tag
for each skill group would probably reduce the overall accuracy because of the
small size of the dataset. At last, improving the cleaning phase by detecting
more precisely the usual conjunctions between two skills could be another way
to keep the token-wise results and identify the skills more efficiently.

We have made some error analyses, but this kind of analysis is limited by the
limited explainability possibilities of deep learning models. In the long
term, we would like to make our model more explainable both to help us
understand the strengths and weaknesses of our model and explain results to
recruiters and human resources staff to allow them to adapt their needs in
recruitment. To do so, we plan to explore counterfactual generation
[madaan2021generate, fern2021text].

Finally, we have only explored a few possibilities this dataset can offer.
Some other tasks that can be performed could include the measurement of the
impact of redaction style (e. g. long sentences vs. bullet points, different
ways of addressing a potential applicant) on the performance, the impact of
gendered wording [gaucher2011evidence], the impact of COVID and teleworking on
skill requirements [gaffney2021trends] or even the extension of the dataset to
include new tools used by human resources such as social media
[ruparel2020influence].

## Acknowledgements

This research was made possible thanks to the support of the Future Skills
Centre and four Canadian insurance companies. We wish to thank the reviewers
for their comments regarding our work and methodology.