# Characterization of digraphs with three complementarity eigenvalues

Diego Bravo<EMAIL_ADDRESS>Florencia Cubría111Corresponding author:
<EMAIL_ADDRESS>Herrera y Reissig 565, Montevideo, Uruguay.
<EMAIL_ADDRESS>Marcelo Fiori<EMAIL_ADDRESS>Instituto de Matemática
y Estadística “Rafael Laguardia”, Facultad de Ingeniería,
Universidad de la Republica, Uruguay.  Vilmar Trevisan<EMAIL_ADDRESS>UFRGS – Universidade Federal do Rio Grande do Sul, Instituto de Matemática,
Porto Alegre, Brazil.

###### Abstract

Given a digraph $D$, the complementarity spectrum of the digraph is defined as
the set of complementarity eigenvalues of its adjacency matrix. This
complementarity spectrum has been shown to be useful in several fields,
particularly in spectral graph theory. The differences between the properties
of the complementarity spectrum for (undirected) graphs and for digraphs,
makes the study of the latter of particular interest, and characterizing
strongly connected digraphs with a small number of complementarity eigenvalues
is a non trivial problem. Recently, strongly connected digraphs with one and
two complementarity eigenvalues have been completely characterized. In this
paper we study strongly connected digraphs with exactly three elements in the
complementarity spectrum, ending with a complete characterization. This leads
to a structural characterization of general digraphs having three
complementarity eigenvalues.

##  1 Introduction

Spectral Graph Theory studies the connection between structural graph
properties and the spectral decomposition of certain matrices associated with
the graph. As prominent examples, from a powerful result of Sachs [1], the
cycles of a given graph allows one to compute the characteristic polynomial of
the adjacency matrix. On the other direction, the seminal work of Fiedler [2]
relates the eigendecomposition of the Laplacian matrix and the connectivity of
the graph for instance, and it is well known that certain properties of the
eigenvalues and eigenvectors of the adjacency matrix give information about
the automorphism group of the graph, or the regularity of the graph, just to
name a few examples.

One of the problems early addressed in this area was the characterization of a
graph by its spectrum. The initial belief that only isomorphic graphs share
their spectra was soon proven wrong by the first examples of coespectral non-
isomorphic graphs and digraphs from the 1950s [3]. Since then, the progress
and the built knowledge in spectral graph theory is remarkable. We refer to
the books [4, 5, 6] and references therein for an account of this progress.

More recently, the concept of complementarity eigenvalues for matrices was
introduced [7], and later on, applications were found in the context of graph
theory [8, 9]. It has been observed that this complementarity spectrum allows
to distinguish more graphs than the traditional eigenvalues, so a natural
question is whether a graph is determined by its complementarity eigenvalues
that is, whether only connected isomorphic graphs share their complementarity
spectra. This question remains unanswered as of today.

The concept of complementarity eigenvalues for graphs, and in particular its
relationship to structural properties, was recently extended to digraphs [10].
It is worth noticing that it is shown that there exist examples of non-
isomorphic digraphs with the same complementarity spectrum. However, several
questions concerning digraph characterization through the complementarity
spectrum remain open. In particular, determining which digraphs have a small
number of complementarity eigenvalues is a proposed problem.

In this paper we address the problem of characterizing all the strongly
connected digraphs with exactly three complementarity eigenvalues. For the
traditional spectrum, the characterization of graphs with few eigenvalues
seems to be easier than for digraphs [11, 5]. In the context of the
complementarity spectrum, the problem of describing all graphs with three
complementarity eigenvalues presents no challenges, since necessarily these
graphs must have three vertices or less [9], and therefore the problem becomes
trivial. However, this characterization problem becomes interesting for
digraphs, since this size restriction is no longer present.

In [10], all digraphs with one or two complementarity eigenvalues are
completely characterized, and the characterization problem for digraphs with
three complementarity eigenvalues is posed. In this work we extend this
characterization for these digraphs.

Our main results are as follows. We first observe that in the context of
digraphs, we may assume that digraphs are strongly connected (see Section 2).
Our preliminary result, Theorem 2.5, gives a characterization of strongly
connected digraphs with three complementarity eigenvalues in terms of its
cyclic structure. We then use this structural characterization to prove the
main result of this paper, which is a full characterization theorem in Section
4.3. In other words, we determine exactly which strongly connected digraphs
have this structural property, thus giving a complete characterization of
digraphs with three complementarity eigenvalues.

We build the proof of this result through the paper, structuring it as
follows. In Section 2 we present the preliminaries and useful results. In
particular, we present the definition of complementary eigenvalues for
matrices, for digraphs, and the main results connecting these eigenvalues with
structural properties of the digraph, which will be heavily used in what
follows. In Section 3, we present families of strongly connected digraphs
having three complementarity eigenvalues. In particular, in Subsection 3.1 we
present two fundamental examples of digraphs with three complementarity
eigenvalues, namely, the $\infty$-digraphs, and the $\theta$-digraph. In
sections 3.2 and 3.3, we see how these digraphs may be modified, by adding
arcs, while keeping three complementarity eigenvalues. We are able to list
seven of these types of digraphs, three of them having an underlying
$\infty$-subdigraphs and four of them having an underlying $\theta$-subdigraph
and not an underlying $\infty$-subdigraph.

It turns out that these seven types are the only strongly connected digraphs
that have three complementarity eigenvalues. Section 4 contains the proof of
this result. Giving the cyclic structure characterization we give in Theorem
2.5, the problem has a natural combinatorial flavor and so does our approach
to prove the result, which is algebraic in nature. We believe that this
interplay between algebra and combinatorics is an interesting feature of our
proof that gives a complete characterization of strongly connected digraphs
with three complementarity eigenvalues.

##  2 Preliminaries

Let $D=(V,E)$ be a finite simple digraph with vertices labelled as
$1,\ldots,n$. The adjacency matrix of $D$ is defined as $A(D)=(a_{ij})$ where

$a_{ij}=\begin{cases}1\quad\text{if }(i,j)\in E,\\\
0\quad\text{otherwise.}\end{cases}$

The multiset of roots of the characteristic polynomial of $A(D)$, counted with
their multiplicities, is the spectrum of $D$, denoted by $Sp(D)$. If $D$ is a
digraph with strongly connected components $D_{1},\ldots,D_{k}$, then
$Sp(D)=\sqcup_{i=1}^{k}Sp(D_{i})$ where $\sqcup$ denotes the union of
multisets.

Throughout this paper, $\rho(\cdot)$ denotes the spectral radius (i.e., the
largest module of the eigenvalues) of a matrix. For nonnegative irreducible
matrices, it is well known that the spectral radius coincides with the largest
eigenvalue, due to the Perron-Frobenius Theorem. Additionally, in this case,
the spectral radius is simple and may be associated with an eigenvector
$x>\textbf{o}$, where o denotes the null vector in $\mathbb{R}^{n}$ and $\geq$
(or $>$) means that the inequality holds for every coordinate.

This real positive value $\rho(A(D))$ is called the _spectral radius of the
digraph $D$_ and is denoted by $\rho(D)$. As we will see, the spectral radius
of the digraph plays a fundamental role in the results obtained in this note.

A digraph $H=(V^{\prime},E^{\prime})$ is a subdigraph of $D$ (denoted $H\leq
D$) if $V^{\prime}\subset V$ and $E^{\prime}\subset E$. We say that $H$ is an
induced subdigraph if $E^{\prime}=E\cap(V^{\prime}\times V^{\prime})$ and a
proper subdigraph if $E^{\prime}\neq E$.

The following is well known, but we state here for easy reference.

######  Lemma 2.1.

Let $H$ be a proper subdigraph of a strongly connected digraph $D$. Then
$\rho(H)<\rho(D)$.

We use the term cycle to refer to a directed cycle in a digraph. As noted in
[10], the spectral radius of the cycle digraph $\vec{C}_{n}$, is
$\rho(\vec{C}_{n})=1.$

The Eigenvalue Complementarity Problem (EiCP) introduced in [7] has found many
applications in different fields of science, engineering and economics [12,
13, 14, 15].

Given a matrix $A\in\mathcal{M}_{n}(\mathbb{R})$, the set of complementarity
eigenvalues is defined as those $\lambda\in\mathbb{R}$ such that there exist a
vector $x\in\mathbb{R}^{n}$, not null and nonnegative, verifying
$Ax\geq\lambda x$, and

$\langle x,Ax-\lambda x\rangle=0.$

If we write $w=Ax-\lambda x\geq\textbf{o}$, the previous condition results in

$x^{t}w=0$

which means to ask for

$x_{i}=0\quad\text{or}\quad w_{i}=0\text{ for all }i=1\ldots,n.$

This last condition is called complementarity condition.

The set of all complementarity eigenvalues of a matrix $A$ is called the
complementarity spectrum of $A$, and it is denoted $\Pi(A)$. Unlike the
regular spectrum of a matrix, the complementarity spectrum is a set (not a
multiset), and the number of complementarity eigenvalues is not determined by
the size of the matrix.

It is known that if $\lambda$ is a complementarity eigenvalue of $A$, then it
is a complementarity eigenvalue of $PAP^{t}$ as well, for every permutation
matrix $P$ [14].

This fact allows us to define the complementarity spectrum of a digraph, since
the complementarity spectrum is invariant in the family of adjacency matrices
associated to the digraph.

The following theorem [10], which extends an existing result for graphs, leads
to a simple and useful characterization of the complementarity eigenvalues for
digraphs. It allows us to characterize the complementarity eigenvalues of a
digraph in terms of its structural properties.

######  Theorem 2.2.

Let $D$ be a digraph and $\Pi(D)$ its complementarity spectrum. Then

$\Pi(D)=\\{\rho(H):{H\text{ induced strongly connected subdigraph of }D}\\}.$

Particularly, the complementarity spectrum of a digraph is then a set of
nonnegative real numbers, which always contain zero as an element.

The next result, which can be found in [10], allows one to focus on the study
of strongly connected digraphs.

######  Proposition 2.3.

Let $D$ be a digraph and $D_{1},\ldots,D_{k}$ the digraph generated by the
strongly connected components of $D$. Then,

$\Pi(D)=\cup_{i=1}^{k}\Pi(D_{i}).$

The following result, also appearing in [10], relates the complementarity
spectrum with the cyclic structure of the digraph, showing that the
complementarity spectrum determines structural properties of the digraph.

######  Theorem 2.4.

Let $D$ be a digraph and $\Pi(D)$ its complementarity spectrum. The three
statements in (1) are equivalent to each other, and the three statements in
(2) are equivalent to each other.

  1. 1.

    1. (a)

$\Pi(D)=\\{0\\}$,

    2. (b)

$\\#\Pi(D)=1$,

    3. (c)

$D$ is acyclic.

  2. 2.

    1. (a)

$\Pi(D)=\\{0,1\\}$,

    2. (b)

$\\#\Pi(D)=2$,

    3. (c)

$D$ is not acyclic and its strongly connected components are either cycles or
isolated vertices.

Here, $\\#\Pi(D)$ denotes the cardinality of $\Pi(D)$. The result of Theorem
2.4 shows that the digraphs with one or two complementarity eigenvalues were
completely determined in [10]. In particular, only acyclic digraphs have a
single complementarity eigenvalues, which is 0. The digraphs with two
complementarity eigenvalue are cyclic whose unique strongly connected
components are cycles and isolated vertices. We conclude that 0 and 1 are
always complementarity eigenvalues of any digraphs that has a cycle as a
subdigraph. In the following sections we will describe precisely the types of
strongly connected digraphs with three complementarity eigenvalues.

We now present a structural characterization of digraphs having three
complementarity eigenvalues.

######  Theorem 2.5.

A strongly connected digraph $D$ has three complementarity eigenvalues if, and
only if, the only induced strongly connected proper subdigraphs of $D$ are
isolated vertices and cycles.

###### Proof.

Let $D$ be a strongly connected digraph with three complementarity
eigenvalues. We show that $D$ verifies that its induced strongly connected
proper subdigraphs are isolated vertices or cycles. We first notice that, by
Theorem 2.4(1), $D$ needs to have a cycle as a subdigraph, hence $1\in\Pi(D)$.
Now let $D^{\prime}$ be a proper subdigraph of $D$; If $D^{\prime}$ is neither
a cycle nor an isolated vertex then, using Perron-Frobenius Theorem we have
that

$1<\rho(D^{\prime})<\rho(D),$

and therefore $\\#\Pi(D)\geq 4$ which contradicts the cardinality of the
complementarity spectrum.
Reciprocally, let $D$ be a strongly connected digraph whose only proper
strongly connected subdigraphs are cycles and isolated vertices. Then we
observe that $0,1\in\Pi(D)$. Also, by Theorem 2.4(2) $D$ is not a cycle and,
using Perron-Frobenius Theorem we have that $1<\rho(D)$. Hence
$\Pi(D)=\\{0,1,\rho(D)\\}$ what finishes the proof.
∎

We notice that this result gives a characterization of digraphs with three
complementarity eigenvalues in terms of their cyclic structure. In the
remainder of the paper, we determine exactly which strongly connected digraphs
have this property, thus giving a complete characterizing of digraphs with 3
complementarity eigenvalues.

##  3 Families of strongly connected digraphs with three complementarity
eigenvalues

In this section we introduce families of strongly connected digraphs with 3
complementarity eigenvalues. First, we present two basic strongly connect
digraphs which are in the core of results. In fact, we show that these
digraphs are subdigraphs of any strongly connected digraph that is not a
cycle. Next, we show how to modify these basic digraphs, by adding arcs,
maintaining the number of complementarity eigenvalues. Later, in the next
section, we show that these are the only families of strongly connected
digraphs with three complementarity eigenvalues, giving a complete description
of such digraphs.

###  3.1 Basic Families

We first present our basic types of strongly connected digraphs having three
complementarity eigenvalues, which we call $\infty$-digraph and
$\theta$-digraph.

$\infty$-digraph (coalescence of cycles)

The $\infty$-digraph $\infty=\infty(r,s)$ is the coalescence of two cycles
$\vec{C_{r}}$ and $\vec{C_{s}}$. It is easy to see that the only strongly
connected induced subdigraphs are the cycles $\vec{C_{r}}$ and $\vec{C_{s}}$,
besides the digraph $\infty$ itself and isolated vertices. Therefore, by
virtue of Theorem 2.2, the complementarity spectrum can be computed by means
of the spectral radii of these induced subdigraphs:

$\Pi(\infty)=\\{0,1,\rho(\infty)\\}.$

Figure 1 shows one example of a digraph in this family and a schematic
representation.

Figure 1: Digraph $\infty(3,5)$ and a schematic representation of the same
digraph.

In the figures throughout this manuscript, we will represent digraphs using
the following convention: a single arrow between two vertices indicates one
arc joining them, while a double arrow indicates that there may be other
vertices in the path joining them.

$\theta$-digraph.

The $\theta$-digraph [16, 10] consists of three directed paths
$\vec{P}_{a+2},\vec{P}_{b+2},\vec{P}_{c+2}$ such that the initial vertex of
$\vec{P}_{a+2}$ and $\vec{P}_{b+2}$ is the terminal vertex of $\vec{P}_{c+2}$,
and the initial vertex of $\vec{P}_{c+2}$ is the terminal vertex of
$\vec{P}_{a+2}$ and $\vec{P}_{b+2}$, as shown in Figure 2. It will be denoted
by $\theta(a,b,c)$ or simply by $\theta$.

Figure 2: Digraph $\theta(0,2,1)$ and a schematic representation of the same
digraph.

Since ${\theta}(a,b,c)$ and ${\theta}(b,a,c)$ are isomorphic and we are not
considering digraphs with multiple arcs, we can assume $a\leq b$ and $b>0$,
without loss of generality.

We have that the number of vertices is $n=a+b+c+2$, and the only strongly
connected induced subdigraphs are the cycles $\vec{C_{r}}$ and $\vec{C_{s}}$
(where $r=a+c+2$ and $s=b+c+2$), in addition to the digraph $\theta$ itself,
and isolated vertices. Therefore, we have,

$\Pi({\theta})=\\{0,1,\rho({\theta})\\}.$

Note that an equivalent construction of the $\theta$-digraph can be made by
taking a cycle, and adding a simple path joining two different vertices.

These two types: $\infty$ and $\theta$ digraphs, are the only strongly
connected bicyclic digraphs [16]. These digraphs are fundamental for the
results presented in this paper, since every strongly connected digraph with
$\\#\Pi(D)>1$ contains one of these digraphs as a subdigraph, as shown in the
next Proposition.

######  Proposition 3.1.

If $D$ is a strongly connected digraph different from a cycle, then it has an
$\infty$-subdigraph or a $\theta$-subdigraph. Moreover, $\\#\Pi(D)>1$.

###### Proof.

Since $D$ is strongly connected, it has a cycle $\vec{C_{r}}$ as a subdigraph,
for some integer $r$. Since $D$ is not a cycle, there are vertices $x,y$ in
this cycle and a non-trivial path from $x$ to $y$, with all the arcs not lying
in the cycle. If $x=y$, then $D$ has an infinity digraph as a subdigraph. If
$x\neq y$ then $D$ has a $\theta$ digraph as a subdigraph. The fact that
$\\#\Pi(D)>1$ follows from item (1) of Theorem 2.4. ∎

###  3.2 Digraphs with an $\infty$-subdigraph

Let us now study in which ways we can modify the $\infty$-digraph, maintaining
the number of complementarity eigenvalues. We first present two examples of
strongly connected digraphs with three complementarity eigenvalues, containing
the $\infty$-digraph as a subdigraph. In the next section we show that they
are the only ones with this property.

For simplicity, we will refer to vertices in $\vec{C}_{r}$ as $1,2,\ldots,r$,
and to vertices in $\vec{C}_{s}$ as $1^{\prime},2^{\prime},\ldots,s^{\prime}$,
identifying $1$ with $1^{\prime}$.

Type 1 digraph

Consider the digraph $D_{1}(r,s)=\infty(r,s)\cup\\{e\\}$, where $e$ denotes
the arc connecting the vertex $r$ with the vertex $2^{\prime}$, as shown in
Figure 3 (left). The only strongly connected induced subdigraphs of $D_{1}$
are both cycles $\vec{C_{r}}$ and $\vec{C_{s}}$, besides the digraph $D_{1}$
itself and isolated vertices. Then, we have

$\Pi(D_{1})=\\{0,1,\rho(D_{1})\\}.$

Observe that in this case the added arc distinguishes both cycles, and
therefore we cannot assume $r\leq s$ like in the previous example. In other
words, it is not the same to add an arc from the smaller cycle to the larger
one, than the other way around.

Figure 3: Type 1 digraph(left) and Type 2 digraph (right).

The left of Figure 3 show the Type 1 digraph. We can add a second arc,
connecting the cycles in the other direction, resulting in digraphs like in
the following Type.

Type 2 digraph

Let $D_{2}$ be the digraph $D_{2}(r,s)=\infty(r,s)\cup\\{e,\tilde{e}\\}$,
where $e=(r,2^{\prime})$ and $\tilde{e}=(s^{\prime},2)$, as shown in Figure
3(right). It is still true that the only strongly connected induced
subdigraphs are both cycles $\vec{C_{r}}$ and $\vec{C_{s}}$, besides the
digraph $D_{2}$ itself and isolated vertices. Then, we have

$\Pi(D_{2})=\\{0,1,\rho(D_{2})\\}.$

Observe that these two types of digraphs, not only have $\infty$-subdigraphs,
but also $\theta$-subdigraphs. For instance, for the Type 1 digraph, by
removing the $(r,1)$ arc from $D_{1}$ we obtain a $\theta$-digraph,
specifically a $\theta(0,r-1,s-2)$.

######  Remark 3.2.

The three examples presented above have three complementarity eigenvalues,
namely, zero, one, and the spectral radius of the digraph itself. A direct
application of Perron-Frobenius Theorem, gives us an important observation: if
we consider the three digraphs mentioned (all with $n$ vertices), then, by
Lemma 2.1, $\rho(\infty)<\rho(D_{1})<\rho(D_{2})$. In particular, these
digraphs are not isomorphic to each other.

###  3.3 Digraphs with a $\theta$-subdigraph, and without an
$\infty$-subdigraph.

As we did in the previous subsection, let us now study in which ways we can
modify the $\theta$-digraph keeping the number of complementarity eigenvalues,
excluding those cases in which an $\infty$-subdigraph appears, since this
family will be studied separately. In the next section we show that these are
the only families of $\theta$-digraph having three complementarity
eigenvalues.

Type 3 digraph

Let $D_{3}$ be the digraph $D_{3}=\vec{C_{n}}\cup\\{e,\tilde{e}\\}$ where
$e=(1,i)$ and $\tilde{e}=(i-1,j)$ with $2<i<j\leq n$, as shown in the left
Figure 4.

The only strongly connected induced subdigraphs of $D_{3}$ are the cycles
$\vec{C}_{n-(i-2)}$, $\vec{C}_{n-(j-i)}$ besides the digraph $D_{3}$ and
isolated vertices. Then, we have

$\Pi(D_{3})=\\{0,1,\rho(D_{3})\\}.$

Type 4 digraph
Let $2\leq k$ be a positive integer. Consider the digraph
$D_{4}=\vec{C_{n}}\cup\\{e_{1},e_{2},\ldots,e_{k}\\}$ where
$e_{i}=(x_{i},y_{i})$ with $1<y_{i}<x_{i}<y_{i+1}<x_{i+1}\leq n$ for all
$i=1,\ldots,k-1$. Observe that the conditon $y_{i}<x_{i}$ prevents the
appearence of an $\infty$-subdigraph. Figure 4 (center) shows an example of
such a digraph with $k=3$ added arcs, generating the three cycles
$\vec{C}_{r_{1}},\vec{C}_{r_{2}}$ and $\vec{C}_{r_{3}}$.

The only strongly connected induced subdigraphs of $D_{4}$ are the cycles
$\vec{C}_{r_{1}},\ldots,\vec{C}_{r_{k}}$ (where $C_{r_{i}}$ is the digraph
induced by the vertices in-between $y_{i}$ and $x_{i}$ for all $i=1,\ldots,k$)
besides the digraph $D_{4}$ and isolated vertices. Then, we have

$\Pi(D_{4})=\\{0,1,\rho(D_{4})\\}.$

Figure 4: Type 3 digraph(left), Type 4 digraph(center) and Type 5
digraph(right). Observe that one $\theta$-subdigraph can be identified in
these three examples by taking the larger (round) cycle in each case, and any
other arc.

Type 5 digraph

Consider the digraph
$D_{5}=\vec{C_{n}}\cup\\{e,e^{\prime},e^{\prime\prime}\\}$ where $e=(1,i)$,
$e^{\prime}=(i-1,j)$ and $e^{\prime\prime}=(j-1,2)$ with $3<i<i+1<j\leq n$. In
this case, condition $3<i$ as much as condition $i+1<j$ prevents the
appearence of an $\infty$-subdigraph. Figure 4(right) shows an example of a
digraph in this family.

The only strongly connected induced subdigraphs of $D_{5}$ are the cycles
$\vec{C}_{n-(i-2)}$, $\vec{C}_{n-(j-i)}$ and $\vec{C}_{j-2}$ besides the
digraph $D_{5}$ and isolated vertices. Then, we have

$\Pi(D_{5})=\\{0,1,\rho(D_{5})\\}.$

Note that the three types of digraphs defined above, as well as the $\theta$
digraph, do not have an infinity digraph as a subdigraph.

It is easy to see that these seven types of digraphs presented above are non
isomorphic to each other.

##  4 Characterization of strongly connected digraphs with three
complementarity eigenvalues

For convenience, we are going to refer to the $\infty$-Family the three types
that have the $\infty$-digraph as subdigraphs, namely, $\infty$-digraph and
its modifications we called Type 1 and Type 2 digraphs of the previous section
and are illustrated in Figures 1 and 3. Likewise we will refer to the
$\theta$-Family the four types that have $\theta$-digraph as subdigraph and
not an $\infty$-digraph, namely, $theta$-digraph and its modifications we
called Type 3, Type 4 and Type 5 digraphs of the previous section and are
illustrated in Figures 2 and 4.
In this section, we will prove that $\infty$-Family and $\theta$-Family are
the only families of strongly connected digraphs with three complementarity
eigenvalues. This will lead to a partial characterization of strongly
connected digraphs having three complementarity eigenvalues.

###  4.1 $\infty$-Family characterization

We first show that the only strongly connect digraphs with three
complementarity eigenvalues having an $\infty$-subdigraph belong to the
$\infty$-Family.

######  Theorem 4.1.

Let $D$ be a strongly connected digraph with three complementarity
eigenvalues. If $D$ contains an $\infty$-subdigraph, then $D$ belongs to the
$\infty$-Family. Precisely, $D$ is either an $\infty$-digraph, a Type 1
digraph or a Type 2 digraph.

###### Proof.

Let us first suppose that there is a vertex $v$ in $D$ outside $\infty(r,s)$
(i.e. there are more vertices than those of the coalescence of the cycles).
Let $D^{\prime}$ be the induced digraph obtained from $D$ by removing $v$. We
notice that $D^{\prime}$ contains an induced strongly connected proper
subdigraph different from a cycle, which is $\infty(r,s)$ itself. This
contradicts Theorem 2.5.

We have then that the vertices in $D$ are exactly the ones of $\infty(r,s)$.
Let us analyze which arcs in $D$ are not in $\infty(r,s)$.

We recall that $\infty(r,s)=\vec{C_{r}}\cdot\vec{C_{s}}$. We first suppose
that there is an arc between vertices of $\vec{C_{r}}$. Considering the
digraph ${D^{\prime}}$ generated by the vertices of $\vec{C_{r}}$, then
$D^{\prime}$ is an induced strongly connected proper subdigraph different from
a cycle or an isolated vertex, which contradicts Theorem 2.5. Figure 5
illustrates all possible arcs within $C_{r}$ and an obtained subdigraph
$D^{\prime}$ in red that is not a cycle.

Figure 5: A schematic representation of all possible cases of added arcs
$(x,y)$ with $x,y\in V(\vec{C}_{r})$.

Of course with the same argument we can rule out arcs between vertices of
$\vec{C_{s}}$. Therefore, we can only add arcs with one vertex in each cycle.

Let us now suppose that there is an arc $(x,y)$ with $x\in V(\vec{C_{r}})$ and
$y\in V(\vec{C_{s}})$.

We will first see that, in order to maintain the cardinality of the
complementarity spectrum, the arc must start from the last vertex of
$\vec{C_{r}}$. This is, $x=r$.

Indeed, if $x\neq r$, we can consider the digraph $D^{\prime}$ generated by
the vertices of $D$ except $r$ (see the left of Figure 6). Since $D^{\prime}$
is an induced strongly connected proper subdigraph of $D$, which contradicts
Theorem 2.5. Therefore the only way to keep three complementarity eigenvalues
is to have $x=r$.

Figure 6: Added arc $(x,y)$ with $x\in\vec{C_{r}}$, $y\in\vec{C_{s}}$ and
$x\neq r$ (left). $(x,y)$ with $x\in\vec{C_{r}}$, $y\in\vec{C_{s}}$ and $y\neq
2^{\prime}$ (right).

With the same arguments we can see that the arc has to end in the second
vertex of $\vec{C_{s}}$, this is, $y=2^{\prime}$ (see the right of Figure 6).

Then, the only arc that we can add from $\vec{C_{r}}$ to $\vec{C_{s}}$
maintaining three complementarity eigenvalues is $(x,y)=(r,2^{\prime})$.

Analogously, we have that the only possible arc $(x,y)$ with $x\in
V(\vec{C_{s}})$ and $y\in V(\vec{C_{r}})$ is $(s^{\prime},2)$.

We have then three possibilities:

  * 1.

we add no arc to the coalescence of the two cycles,

  * 2.

we add either $(r,2^{\prime})$ or $(s^{\prime},2)$, so we end up with a
digraph of Type 1,

  * 3.

we add both arcs $(r,2^{\prime})$ and $(s^{\prime},2)$, so we end up with a
digraph of Type 2,

which concludes the proof. ∎

######  Corollary 4.2.

Let $D$ be a strongly connected digraph with $n$ vertices and three
complementarity eigenvalues. If $D$ contains an $\infty(r,s)$-subdigraph, then
$n=r+s-1$.

###  4.2 $\theta$-Family characterization

As we did in Subsection 4.1 with the $\infty$-Family, we will now show that
the $\theta$-digraphs presented above are all the possible digraphs with three
complementarity eigenvalues that can be obtained from the $\theta$-digraph,
obtaining a second partial characterization result.

######  Theorem 4.3.

Let $D$ be a strongly connected digraph with exactly three complementarity
eigenvalues, with a $\theta$-subdigraph and without an $\infty$-subdigraph,
then $D$ belongs to the $\theta$-Family. Precisely $D$ is either a
$\theta$-digraph, a Type $3$ digraph, a Type $4$ digraph, or a Type $5$
digraph.

###### Proof.

Let us first suppose that there is a vertex $v$ in $D$ outside $\theta(a,b,c)$
(i.e. there are more vertices than those of the $\theta$-subdigraph). Let
$D^{\prime}$ be generated from the vertices of $D$ by removing $v$. We notice
that $D^{\prime}$ contains an induced strongly connected proper subdigraph
different from a cycle or an isolated vertex, because it contains
$\theta(a,b,c)$ as a proper subdigraph, and therefore it contradicts Theorem
2.5.

Then the vertices in $D$ are exactly the ones in $\theta(a,b,c)$.

We will analyze which arcs can be added to the digraph $\theta(a,b,c)$ using
the following strategy: for any arc $(x,y)$ added to $\theta(a,b,c)$ we will
try to find a non-trivial strongly connected induced subdigraph $D^{\prime}$
different from a cycle and different from $D$. In the figures illustrating
each case, this digraph $D^{\prime}$ will be colored in red. If this is
possible, then the arc $(x,y)$ can not be added because it would contradict
Theorem 2.5. If not, the digraph obtained will be one of the four different
types. Furthermore, we will need to guarantee that if we combine different
permitted arcs we also obtain one of the four different types of digraphs.

Figure 7: $\theta$-digraph and some distinguished vertices in it.

For simplicity, since these vertices are used more than once in what follows,
let us denote by $v_{a}=pred_{\vec{P}_{a}}(v)$, $v_{b}=pred_{\vec{P}_{b}}(v)$,
and $v_{c}=suc_{\vec{P}_{c}}(v)$ the predecessor vertices of $v$ in the paths
$\vec{P}_{a}$, $\vec{P}_{b}$ and $\vec{P}_{c}$, respectively. Analogously, we
denote, respectively, by $w_{a}=suc_{\vec{P}_{a}}(w)$,
$w_{b}=suc_{\vec{P}_{b}}(w)$, $w_{c}=pred_{\vec{P}_{c}}(w)$ the successor
vertices of $w$. See the representation in Figure 7.

For the analysis it will be useful to analyze cases $a\geq 1$ and $a=0$
separately.

Case 1 $a\geq 1$
We will further separate the study in five subcases.

  1. 1.

$x,y\in V(\vec{P}_{a+2})\cup V(\vec{P}_{c+2})$,

  2. 2.

$x,y\in V(\vec{P}_{b+2})$,

  3. 3.

$x\in V(\vec{P}_{b+2})$ and $y\in V(\vec{P}_{c+2})$ or viceversa,

  4. 4.

$x\in V(\vec{P}_{a+2})$ and $y\in V(\vec{P}_{b+2})$,

  5. 5.

$x\in V(\vec{P}_{b+2})$ and $y\in V(\vec{P}_{a+2})$.

Subcase (1). We will prove that we cannot add arcs $(x,y)$ with $x,y\in
V(\vec{P}_{a+2})\cup V(\vec{P}_{c+2})$.
Indeed, let us suppose that we added such an arc. Then, by considering the
digraph ${D^{\prime}}$ generated by $V(\vec{P}_{a+2})\cup V(\vec{P}_{c+2})$
(see Figure 8(left and center), where $D^{\prime}$ is in red) we obtain an
induced strongly connected proper subdigraph different from a cycle and from
an isolated vertex which contradicts Theorem 2.5.

Figure 8: Added arc $(x,y)$ with $x,y\in V(\vec{P}_{a+2})\cup
V(\vec{P}_{c+2})$ (left and center). Added arc $(x,y)$ with $x,y\in
V(\vec{P}_{b+2})$ (right).

Then there are no arcs between vertices of $\vec{P}_{a+2}$ or vertices of
$\vec{P}_{c+2}$. The same proof could be done with $a=0$.

Subcase (2). We will prove that we cannot add arcs $(x,y)$ with $x,y\in
V(\vec{P}_{b+2})$. Indeed, let us suppose that we added such an arc. Hence,
considering the digraph ${D^{\prime}}$ generated by $V(\vec{P}_{b+2})\cup
V(\vec{P}_{c+2})$ (see Figure 8 (right)) we obtain an induced strongly
connected proper subdigraph different from a cycle and from an isolated vertex
which contradicts Theorem 2.5.

Then there are no arcs between vertices of $\vec{P}_{b+2}$. Note that we used
that $a\geq 1$.

Subcase (3) We will prove that we can neither add arcs $(x,y)$ with $x\in
V(\vec{P}_{b+2})$ and $y\in V(\vec{P}_{c+2})$ nor viceversa. Indeed, let us
suppose that we added such an arc. Hence, considering the digraph
${D^{\prime}}$ generated by $V(\vec{P}_{b+2})\cup V(\vec{P}_{c+2})$ (see
Figure 9) we obtain an induced strongly connected proper subdigraph different
from a cycle and from an isolated vertex which contradicts Theorem 2.5.

Figure 9: Added arc $(x,y)$, with $x\in V(\vec{P}_{a+2})$ and $y\in
V(\vec{P}_{c+2})$, and viceversa.

Then there are no arcs $(x,y)$ with $x\in V(\vec{P}_{b+2})$ and $y\in
V(\vec{P}_{c+2})$ or viceversa that keep the number of complementarity
eigenvalues.

Subcase (4). We will prove that the only arc $(x,y)$ with $x\in
V(\vec{P}_{a+2})$ and $y\in V(\vec{P}_{b+2})$ that could be added is
$({v}_{a},{w}_{b})$, where the vertices $v,~{}w.~{}v_{a},~{}w_{b}$ are located
in $D$ as Figure 7 illustrates.

We can assume $x\neq v$ and $y\neq w$, otherwise we obtain a subcase already
analysed.

Let us first see that the starting vertex $x$ of the arc cannot be other than
$v_{a}$. Indeed, if $x\neq v_{a}$ considering the strongly connected digraph
${D^{\prime}}$ generated by removing vertex $v_{a}$ (see the left of Figure
10), we obtain an induced strongly connected proper subdigraph different from
a cycle and from an isolated vertex which contradicts Theorem 2.5., so that
$x={v_{a}}$.

Figure 10: Added arc $(x,y)$, with $x\in V(\vec{P}_{a+2})$, $x\neq v_{a}$ and
$y\in V(\vec{P}_{b+2})$ (left). Added arc $(v_{a},y)$, with $y\in
V(\vec{P}_{b+2})$ and $y\neq w_{b}$ (right).

Analogously, the ending vertex $y$ of the added arc can only be $w_{b}$.
Indeed, if $x={v}_{a}$ and $y\neq{w}_{b}$ considering the strongly connected
digraph ${D^{\prime}}$ generated by removing vertex ${w}_{b}$ (see the right
of Figure 10) we obtain an induced strongly connected proper subdigraph
different from a cycle and from an isolated vertex which contradicts Theorem
2.5, so that $y={w}_{b}$.

Figure 11: Added arc $({v}_{a},{w}_{b})$ and its conversion into a Type $3$
digraph

We conclude that the only arc we are able to add in this item is
$({v}_{a},{w}_{b})$ and we obtain a Type $3$ digraph (see Figure 11).

Subcase (5). Analogously to the previous item we can prove that the only arc
$(x,y)$ with $x\in V(\vec{P}_{b+2})$ and $y\in V(\vec{P}_{a+2})$ that could be
added is $({v}_{b},w_{a})$ and we obtain a Type $3$ digraph (see Figure 12).

Figure 12: Added arc $({v}_{b},{w}_{a})$ and its conversion into a Type $3$
digraph.

We have proved so far that in case $D$ has a $\theta(a,b,c)$-subdigraph with
$a\geq 1$, the only arcs that could be added are $({v}_{a},{w}_{b})$ and
$({v}_{b},{w}_{a})$. If we add one of them we obtain a type $3$ digraph as
seen before and if we add both we obtain a Type $5$ digraph as shown in Figure
13.

Figure 13: Added arcs $({v}_{a},{w}_{b})$ and $({v}_{b},{w}_{a})$, and its
conversion into a Type $5$ digraph.

Case 2 $a=0$
We will analyse separetely the arcs $(x,y)$ with

  1. 1.

$x,y\in V(\vec{P}_{a+2})\cup V(\vec{P}_{c+2})$,

  2. 2.

$x,y\in V(\vec{P}_{b+2})$,

  3. 3.

$x\in V(\vec{P}_{a+2})$ and $y\in V(\vec{P}_{b+2})$ or viceversa,

  4. 4.

$x\in V(\vec{P}_{b+2})$ and $y\in V(\vec{P}_{c+2})$,

  5. 5.

$x\in V(\vec{P}_{c+2})$ and $y\in V(\vec{P}_{b+2})$.

Subcase (1). Due to the observation made in subcase (1) of the previous case
we know that there could not be arcs between vertices in $V(\vec{P}_{a+2})\cup
V(\vec{P}_{c+2})$ despite $a=0$.

Subcase (2). Consider in $\vec{P}_{b+2}$ the natural order (in the figures,
from right to left). We will prove that if an arc $(x,y)$ with $x,y\in
V(\vec{P}_{b+2})$ can be added, its vertices should verify that $v<y<x<w$,
where $v$ and $w$ are located as in Figure 7. Furthermore, we will prove that
if we add $k$ of these arcs $(x_{i},y_{i})$ with $i=1,\ldots,k$ they should
verify $w<y_{i}<x_{i}<y_{i+1}<x_{i+1}<v$ for all $i=1,\ldots,k$.

If $x<y$ there exists $z$ such that $x<z<y$, otherwise we would have added an
existing arc. Considering the strongly connected digraph ${D^{\prime}}$
generated by removing vertex $z$ we obtain an induced strongly connected
proper subdigraph different from a cycle and from an isolated vertex which
contradicts Theorem 2.5. This is shown in red in Figure 14.(left)

Figure 14: Added arc $(x,y)$, with $x\in V(\vec{P}_{b+2})$, $x<y$(left) and
Added arc $(x,y)$, with $x\in V(\vec{P}_{b+2})$, $w<y<x<v$ (center) and its
conversion to a Type $4$ digraph (right).

If $y<x$ we have that $w<y<x<v$ because if either $y=w$ or $x=v$, we would
have an $\infty$-subdigraph, which was excluded in the hypothesis. Then, we
obtain a Type 4 subdigraph as shown in the Figure 14 (center). The right of
Figure 14 shows how the obtained digraph may be seen as a Type 4. Notice that
the case $y=w$ and $x=v$ was analyzed in subcase (1).

Let us analyze what happens if we add another arc $(x^{\prime},y^{\prime})$ of
this form. The vertices of these two arcs should verify one of the following
three options

  * 1.

$w<y\leq y^{\prime}<x^{\prime}\leq x<v$,

  * 2.

$w<y<y^{\prime}<x<x^{\prime}<v$,

  * 3.

$w<y<x<y^{\prime}<x^{\prime}<v$.

If $w<y\leq y^{\prime}<x^{\prime}\leq x<v$, considering the digraph
$D^{\prime}$ generated by vertices between $y$ and $x$ (including both), as
shown in left of Figure 15, we obtain a digraph different from a cycle and
from $D$ itself, what contradicts Theorem 2.5.

If $w<y<y^{\prime}\leq x<x^{\prime}<v$ considering the digraph $D^{\prime}$
generated by vertices between $y$ and $x^{\prime}$ (including both), as shown
in right of Figure 15, we obtain an induced strongly connected proper
subdigraph different from a cycle and from an isolated vertex which
contradicts Theorem 2.5.

Figure 15: Added arcs $(x,y)$ and $(x^{\prime},y^{\prime})$, $w<y\leq
y^{\prime}<x^{\prime}\leq x<v$ (left). Added arcs $(x,y)$ and
$(x^{\prime},y^{\prime})$ with $w<y\leq y^{\prime}<x^{\prime}\leq x<v$
(right).

Then we have that these arcs necessarily verify
$w<y<x<y^{\prime}<x^{\prime}<v$. If we add $k$ of these arcs, $(x_{i},y_{i})$
with $i=1,\ldots,k$, then $w<y_{i}<x_{i}<y_{i+1}<x_{i+1}<v$ for all
$i=1,\ldots,k$ (reordering if necessary) what is a Type 4 digraph as shown in
Figure 16.

Figure 16: Added arcs $(x_{i},y_{i})$ with $w<y_{i}<x_{i}<y_{i+1}<x_{i+1}<v$,
$i=1,\ldots,k$ and its conversion into a Type $4$ digraph.

Subcase (3). This item is reduced to subcases (1) or (2) because, since $a=0$,
then $\vec{P}_{a+2}$ contains only two vertices, which can be seen as vertices
in $\vec{P}_{b+2}$.

Subcase (4). We will prove that if an arc $(x,y)$ with $x\in V(\vec{P}_{b+2})$
and $y\in V(\vec{P}_{c+2})$ can be added, then $x=v_{b}$ (see Figure 7 for
location of the vertex $v$) and that not any other arc of these type can be
added.

Indeed, let us suppose that we added such an arc $(x,y)$ with $x\neq{v_{b}}$.
Hence, considering the strongly connected digraph $D^{\prime}$ generated by
vertices in $D$ different from $v_{b}$, as shown in Figure 17 (left), we
obtain a digraph different from a cycle and from $D$ itself, which contradicts
Theorem 2.5.

Figure 17: Added arc $(x,y)$, with $x\in V(\vec{P}_{b+2})$, $x\neq v_{b}$ and
$y\in V(\vec{P}_{c+2})$.(left) Added arc $(v_{b},y)$ with $y\in\vec{P}_{c+2}$
(center) and its conversion into a Type $3$ digraph (right).

Moreover, if $x={v}_{b}$ then $y\neq v$ because $D$ has no multiple arcs, and
$y\neq w$ because $D$ has not an $\infty$-subdigraph and we obtain a Type 3
digraph as shown in the Figure 17 (center).

Notice that just one of these arcs could be added, otherwise, considering the
strongly connected digraph $D^{\prime}$ generated by vertices in $D$ different
from $v$ (see Figure 18(left)) we obtain an induced strongly connected proper
subdigraph different from a cycle and from an isolated vertex which
contradicts Theorem 2.5.

Figure 18: Added arcs $(v_{b},y)$ and $(v_{b},y^{\prime})$ with $x\in
V(\vec{P}_{c+2})$ (left). Added arc $(x,y)$, with $x\in V(\vec{P}_{c+2})$,
$x\in V(\vec{P}_{b+2})$ $y\neq w_{b}$ (right).

Subcase (5). We will prove that if an arc $(x,y)$ with $x\in V(\vec{P}_{c+2})$
and $y\in V(\vec{P}_{b+2})$ can be added, then $y=w_{b}$ and that no other arc
of this type can be added.

Indeed, let us suppose that we added such an arc $(x,y)$ with $y\neq{w_{b}}$.
Hence, considering the strongly connected digraph $D^{\prime}$ generated by
removing ${w_{b}}$ (see Figure LABEL:grafos_50b) we obtain an induced strongly
connected proper subdigraph different from a cycle and from an isolated vertex
which contradicts Theorem 2.5. Then $y=w_{b}$.

If $y={w}_{b}$ then $x\neq w$ because $D$ has no multiple arcs, and $x\neq v$
because $D$ does not have an $\infty$-subdigraph, then we obtain a Type $3$
digraph as shown in Figure 19 (left and center).

Figure 19: Added arc ($x,w_{b})$ (left) and its conversion to a Type $3$
(center). Added arcs $(x,w_{b})$ and $(x^{\prime},w_{b})$ (right).

Notice that only one of these arcs could be added, otherwise, considering the
strongly connected digraph $D^{\prime}$ generated by removing $v$ (see Figure
19 (right)), we obtain an induced strongly connected proper subdigraph
different from a cycle and from an isolated vertex which contradicts Theorem
2.5.

We have proved so far that in case $D$ has a $\theta(0,b,c)$-subdigraph, the
only arcs that can be added, maintaining three complementarity eigenvalues,
are those from Subcases 2, 4, and 5. Let us study what happens if we try to
add simultaneously arcs from

  * 1.

Subcases 2 and 4,

  * 2.

Subcases 2 and 5,

  * 3.

Subcases 4 and 5.

Firstly we will see that there cannot be arcs obtained from Subcases 2 and 4.
Consider an arc $({v_{b}},y)$ with $y\in V(\vec{P}_{c+2})$ and an arc
$(x^{\prime},y^{\prime})$ with $x^{\prime},y^{\prime}$ in $V(\vec{P}_{b+2})$
with $w<y^{\prime}<x^{\prime}<v$, then, considering the strongly connected
digraph $D^{\prime}$ generated by vertices in $D$ different from $v$ (see left
of Figure 20), we obtain a digraph different from a cycle and from $D$ itself,
and this contradicts Theorem 2.5.

Secondly, we will see that there cannot be arcs obtained from Subcases 2 and
5. Consider an arc $(x,y)$ with $x,y$ in $V(\vec{P}_{b+2})$ with $w<y<x<v$ and
an arc $(x^{\prime},w_{b})$ with $x^{\prime}$ in $V(\vec{P}_{c+2})$.
Considering the strongly connected digraph $D^{\prime}$ generated by vertices
in $D$ different from $w$ (see Figure 20(right)) we obtain a digraph different
from a cycle and from $D$ itself, which contradicts Theorem 2.5.

Figure 20: Added arcs $(v_{b},y)$ and $(x^{\prime},y^{\prime})$ with
$y^{\prime}<x^{\prime}$(left). Added arcs $(x,w_{b})$ and
$(x^{\prime},y^{\prime})$ with $y^{\prime}<x^{\prime}$(right).

Finally, we analyze what happen if we add arcs obtained in Subcases 4 and 5
simultaneously. Suppose that we have an arc $({v}_{b},y)$ with $y\in
V(\vec{P}_{c+2})$ and an arc $(x,{w}_{b})$ with $x\in V(\vec{P}_{c+2})$.
Assuming the natural order in $\vec{P}_{c+2}$ (from left to right), if $y\leq
x$, we consider the strongly connected digraph $D^{\prime}$ generated by
removing $v$ (see left of Figure 21) we obtain an induced strongly connected
proper subdigraph different from a cycle and from an isolated vertex which
contradicts Theorem 2.5.
If $x<y$ and there exists $z\in V(\vec{P}_{c+2})$ such that $x<z<y$. We then
consider the strongly connected digraph $D^{\prime}$ generated by removing $z$
(see right of Figure 21) we obtain an induced strongly connected proper
subdigraph different from a cycle and from an isolated vertex which
contradicts Theorem 2.5.

Figure 21: Added arcs $(v_{a},y)$ and $(x,w_{b})$ with $y\leq x$(left).
$(v_{a},y)$ and $(x,w_{b})$ with $x<y$(right).

If $x<y$ and it does not exist such $z$, we have that $y=suc_{\vec{P}_{c}}(x)$
and we obtain a Type 5 digraph as shown in Figure 22.

Figure 22: Added arcs $(v_{a},y)$ and $(x,w_{b})$ with
$y=suc_{\vec{P}_{c}}(x)$ and its convertion into a type $5$ digraph.

This concludes the proof. ∎

######  Corollary 4.4.

Let $D$ be a strongly connected digraph with $n$ vertices and three
complementarity eigenvalues. If $D$ contains a $\theta(a,b,c)$-subdigraph,
then $n=a+b+c+2$.

###  4.3 Characterization of strongly connected digraphs with exactly three
complementarity eigenvalues

In this subsection we describe all the families of strongly connected digraphs
with exactly three complementarity eigenvalues using our previous results.

######  Theorem 4.5.

Let $D$ be a strongly connected digraph with exactly three complementarity
eigenvalues. Then $D$ belongs either to the $\infty$-Family or to the
$\theta$-Family. Precisely $D$ is either an $\infty$-digraph, or
$\theta$-digraph, or a Type $1$, or a Type $2$ , or a Type $3$, or a Type $4$,
or type $5$ digraph.

###### Proof.

Since $D$ has three complementarity eigenvalues, we know that $D$ is a
strongly connected digraph different from a cycle, and therefore, by
Proposition 3.1 we have that $D$ has an $\infty$-subdigraph or a
$\theta$-subdigraph.

If $D$ has an $\infty$-subdigraph we know by Theorem 4.1 that $D$ belongs to
the $\infty$-Family, e.g. it is either an $\infty$-digraph, a Type $1$ or Type
$2$ digraph. If $D$ does not have an $\infty$-subdigraph, then the digraph $D$
verifies the hypothesis of Theorem 4.3, and then $D$ belongs to the
$\theta$-Family, e. g. $D$ is either a $\theta$-digraph, or a Type $3$, or a
Type $4$, or Type $5$ digraph. ∎

In view of Proposition 2.3, we have the following structural characterization
of digraphs having 3 complementarity eigenvalues.

######  Corollary 4.6.

Let $D$ be a digraph with three complementarity eigenvalues. Then, its
strongly connected components are either isolated vertices, cycles, or any of
the seven types of digraphs presented above. Moreover, at least one of these
seven types must appear, and if two or more strongly connected components
belongs to these seven types, then they should share the same spectral radius.

##  5 Conclusions

Throughout this work we presented a structural characterization result, and a
precise determination of strongly connected digraphs with exactly three
complementarity eigenvalues. Namely, the characterization presented in Theorem
2.5 states that the strongly connected digraphs $D$ with $\\#\Pi(D)=3$ are
those such that, when removing any vertex, the resulting digraph only has
cycles or isolated vertices as strongly connected induced subdigraphs. On the
other hand, Theorem 4.5, which is the main contribution of this paper, states
that any strongly connected digraph with three complementarity eigenvalues
belongs to one of the seven families of digraphs presented in the text, giving
a complete description, determining exactly which digraphs have three
complementarity eigenvalues.

One way to take these results one step further is to consider digraphs with
four complementarity eigenvalues. However, even a structural characterization
result similar to the one given by Theorem 2.5 , seems to be significantly
harder, due to the combinatorial nature of the problem and the many
possibilities that arise in the process. The key to characterize digraphs with
three complementarity eigenvalues was that strongly connected digraphs with
two complementarity eigenvalues are cycles or isolated vertices. When
considering digraphs $D$ with $\\#\Pi(D)=4$, the digraphs that result when
removing a vertex have much more diversity, since there are seven families of
such digraphs with three complementarity eigenvalues, and a combinatorial
approach to analyse the cases which they can be modified to yield four
complementarity eigenvalues may be unfeasible.

Another interesting and natural question is the following. Once strongly
connected digraphs with three complementarity eigenvalues are characterized,
can one determine the digraph through its complementarity spectrum? The answer
to this question, given in [10] is negative, since examples of non-isomorphic
digraphs with the same three complementarity spectrum are presented. In the
notation of this manuscript, those digraphs are Type $4$ digraphs. We can ask
whether any family of digraphs with three complementarity eigenvalues is
determined by their complementarity spectrum. As a motivating example, it
follows from the discussion in Remark 3.2 of Section 3.2 that the digraphs in
the $\infty$-Family can be distinguished by their complementarity spectrum.

## Acknowledgments

This research is part of the doctoral studies of F. Cubría. V. Trevisan
acknowledges partial support of CNPq grants 409746/2016-9 and 310827/2020-5,
and FAPERGS grant PqG 17/2551-0001. M. Fiori and D. Bravo acknowledge the
ﬁnancial support provided by ANII, Uruguay. F. Cubría thanks the doctoral
scholarship from CAP-UdelaR. We thank Lucía Riera for the help with the
figures.

## References

  * [1] H. Sachs, Beziehungen zwischen den in einem graphen enthaltenen kreisen und seinem charakteristischen polynom, Publ. Math. Debrecen 11 (1) (1964) 119–134.
  * [2] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 (2) (1973) 298–305.
  * [3] L. Von Collatz, U. Sinogowitz, Spektren endlicher grafen, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 21 (1) (1957) 63–77.
  * [4] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, New York, NY, 2012.  doi:10.1007/978-1-4614-1939-6.
  * [5] M. Doob, Graphs with a small number of distinct eigenvalues, Annals of the New York Academy of Sciences 175 (2007) 104 – 110.
  * [6] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applications, Wiley, New York, 1998.
  * [7] A. Seeger, Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions, Linear Algebra and its Applications 292 (1-3) (1999) 1–14.
  * [8] R. Fernandes, J. Judice, V. Trevisan, Complementary eigenvalues of graphs, Linear Algebra and its Applications 527 (2017) 216–231.
  * [9] A. Seeger, Complementarity eigenvalue analysis of connected graphs, Linear Algebra and its Applications 543 (2018) 205–225.
  * [10] D. Bravo, F. Cubría, M. Fiori, V. Trevisan, Complementarity spectrum of digraphs, Linear Algebra and its Applications 627 (2021) 24–40.
  * [11] A. Olivieri, J. Rada, A. Rios Rodriguez, Digraphs with few eigenvalues, Utilitas Mathematica 96 (2015) 89–99.
  * [12] S. Adly, H. Rammal, A new method for solving second-order cone eigenvalue complementarity problems, Journal of Optimization Theory and Applications 165 (2) (2015) 563–585.
  * [13] F. Facchinei, J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems, Springer Science & Business Media, 2007.
  * [14] A. Pinto da Costa, A. Seeger, Cone-constrained eigenvalue problems: theory and algorithms, Computational Optimization and Applications 45 (2010) 25–57.
  * [15] A. Pinto da Costa, J. Martins, I. Figueiredo, J. Júdice, The directional instability problem in systems with frictional contacts, Computer Methods in Applied Mechanics and Engineering 193 (3-5) (2004) 357–384.
  * [16] H. Lin, J. Shu, A note on the spectral characterization of strongly connected bicyclic digraphs, Linear Algebra and its Applications 436 (7) (2012) 2524–2530.


tells the story of the critters, who are people living in peace in an unknown
colony in a forest. Unfortunately, a disease outbreak causes many of the
critters to turn into mutants. These mutants do not behave like the other
critters and are destroying the colony, forcing the healthy critters to flee
into a tower across the forest. Along their walk to the tower, the player has
to place magic mines, which check the behavior of the critters and only let
healthy ones pass.

##  0.1 Game Concept

Figure 1: The critter under test Figure 2: A mutant of the critter under test

integrates mutation testing and block-based programming around the well-known
game Tower Defense. In a classic Tower Defense game, the player has to place
turrets along a route that enemies take to reach a certain point on the
gameboard. The more enemies are eliminated on their way to this point, the
more points the player receives in the end. Unlike traditional Tower Defense
games, in there are not only enemies but also civilians who have to be
protected. The behavior of critters is represented by the critter under test
(CUT) as a short block-based code snippet (fig:cut). Enemies (_mutants_) are
mutations of the CUT (fig:mutant). To avoid the rather violent notion of
killing enemies, in the turrets are replaced with mines that represent test
cases; these mines use magic to trap the mutants instead of shooting them.

Figure 3: The gameboard of

##  0.2 Game Mechanics

The gameboard (fig:game) represents both the colony (the spawn point) and the
tower (the destination), including the dirty trail from one to the other with
the surrounding forest. The board is made of 256 tiles, represented with x and
y coordinates from 1 to 16. Each tile can hold one specific texture, namely
grass, dirt, water, ice, or wood, and critters can only walk on grass, dirt,
and ice. In addition, mines can only be placed on tiles where critters can
walk, which is also the first move the player has to make before starting the
game.

The behavior of critters is described with short snippets of code which are
continuously executed in a loop while the critters are exploring the
gameboard. A CUT is conceptually similar to an object oriented class and
consists of two parts, the initialization and the code under test. The
initialization behaves like a constructor and defines the initial values of
the attributes of a critter like their shirt or hair color. The code under
test is like a method that is called continuously in a loop while the critter
walks, and receives texture and coordinates as inputs. A simple example of a
healthy critter is the CUT shown in fig:cut, which is initialized with a red
shirt, and its color changes when walking on dirt tiles.

Mutant critters contain one or more code mutations, such as the incorrect
shirt color initialization and wrong choice of shirt color shown in
fig:mutant. The goal of the game is to let only healthy critters reach and
enter the tower, while mutants are held off and trapped by the mines.

Mines represent test cases: A mine is placed on exactly one tile by clicking
on one of the walkable tiles, which represent the test inputs with their
coordinates and texture. Clicking on a tile opens a dialog (fig:game) in which
a new test for the CUT can be created for a given input location (tile).
Players can implement assertions for the mines with the same block-based
language that represents the CUT or mutants. The available blocks on the left
side of the dialog in fig:game can be placed on the right side via drag and
drop and combined into a test case. The main block of each test is the assert-
block, which is divided into the property to be checked and the value it
should have at this point. Properties include the color of a critter’s shirt
and hair as well as their size. Shirt and hair colors are enumerations, while
size properties are integers that can be checked for their value, whether they
are even, odd, negative, positive or prime value. It is also possible to store
and check basic information in variables and to perform basic mathematical
operations on numerical values. The test represented by a mine is executed
during active gameplay against any critter who steps onto the mine.

To trap the mutant in fig:mutant, two different mines have to be placed along
the route to detect it: The first one somewhere on a grass tile which covers
the mutation in the initialization, and the second mine on a dirt tile to find
the mutation in the if-condition (see fig:play). Both mines need to assert the
expected value of the shirt color. These mines in combination with the mutants
are also an abstraction layer to generate a test suite. A secondary goal of
the game is to use as few mines as possible to detect all mutants, in other
words, to minimize the test suite. In general, there is no limitation on the
number of mines, but points are deducted if too many of them are used.

Figure 4: The scoreboard after finishing the current level

After the player has placed all necessary mines on the board, the game can be
started (fig:play). The critters now start from the colony on the left and
take a random route to the tower. A running game can be paused at any time as
well as reset or sped up. A valid mine lets healthy critters pass without
harm, while it traps mutants if the test fails (see sec:levels). Consequently,
invalid assertions may lead to false positives and trap healthy critters
rather than mutants, which leads to the player losing points. At the bottom of
the screen (fig:game), the critters and mutants are displayed, and those who
reached the tower will be marked as saved while trapped ones will be greyed
out. When the last free critter or mutant reaches the tower, the game ends and
the scoreboard is shown (fig:victory). It contains information about saved
critters and detected mutants, as well as the number of mines used and the
given time bonus. After finishing the game, the mutants can be viewed to gain
insights into how the CUT was mutated. The achieved score is accumulated with
points earned from prior games and displayed on a public leaderboard on the
starting page of (fig:leveloverview).

##  0.3 Levels

Figure 5: Different levels in with the leaderboard Figure 6: The level editor
of

provides different levels, organized into tutorial, beginner, and advanced
(fig:leveloverview) categories. Our current proof-of-concept integrates ten
levels, but also provides a level editor (fig:levelgenerator) to create new
ones. The level editor allows the creation of a custom map with the five
different texture types and the start and end points. Each level needs a CUT
to be created and, based on the CUT, one or more mutants. In addition, the
number of critters, the number of mines the player can use without point
deduction as well as the difficulty grade have to be set.

Since each level is based on one CUT, the difficulty and learning goals can be
adjusted by choosing an appropriate CUT. Players need to consider the
following parts of the CUT and write tests for them to trap all mutants:

  * •

Initialization: Mutation in the initial configuration of the critter

  * •

Assignments: Changes in all property or variable assignments

  * •

Branches: Removal or changes in if-else-clauses

  * •

Conditions: Removal or changes of conditions in if-else-clauses

Levels can capture different testing concepts by adjusting those parts. For
example, using a set of mutants where each mutant has one or more changed
assignment statements, the concept of full statement coverage can be taught
while changing the order or the content of if-else-clauses teaches about
branch coverage. Changing or even removing conditions within conjunctions or
disjunctions leads to the understanding of condition coverage.

Not only the CUT can be mutated in various ways to increase the difficulty,
but the gameboard itself can be altered and designed in a way to add more
difficulty. For example, the board can be adjusted to provide more than one
path the critters and mutants can take to the tower. This leads to the
requirement for different mines on different tracks because of the texture and
the coordinates of the tiles; some mines may be unique in one of the routes,
and others have to be added in every route to ensure all mutants are caught,
essentially teaching about input partitioning [collard2002practical].

##  0.4 Implementation

is designed as a web application that can be deployed on any server and
reached from the internet to be playable for everyone in a web browser. Like
Scratch and many other block-based programming environments, we decided to
build using the Blockly111https://developers.google.com/blockly library for
representing and editing code. Scratch adds an abstraction layer over basic
programming aspects by defining different blocks that the learners can combine
into a meaningful program. In we reuse these concepts by defining the CUT with
different blocks instead of source code (fig:cut).


# Personalizing ASR With Limited Data using Targeted Subset Selection

###### Abstract

We study the task of personalizing ASR models to a target non-native
speaker/accent while being constrained by a transcription budget on the
duration of utterances selected from a large unlabelled corpus. We propose a
subset selection approach using the recently proposed submodular mutual
information functions, in which we identify a diverse set of utterances that
match the target speaker/accent. This is specified through a few target
utterances and achieved by modelling the relationship between the target
subset and the selected subset using submodular mutual information functions.
This method is applied at both the speaker and accent levels. We personalize
the model by fine tuning it with utterances selected and transcribed from the
unlabelled corpus. Our method is able to consistently identify utterances from
the target speaker/accent using just speech features. We show that the
targeted subset selection approach improves upon random sampling by as much as
2% to 5% (absolute) depending on the speaker and accent and is 2x to 4x more
label-efficient compared to random sampling. We also compare with a skyline
where we specifically pick from the target and our method generally
outperforms the oracle in its selections.111The code for our experiments is
publicly available at https://github.com/iMayK/TSSSpeechPersonalization

Index Terms—  Personalization, Data Selection, Accent and Speaker Adaptation,
Submodular Mutual Information

##  1 Introduction

State-of-the-art speech recognition systems have seen tremendous progress in
the last few years, with end-to-end architectures becoming a default modeling
choice. While end-to-end models yield impressive WER reductions and work well
for certain user populations [1, 2], they severely underperform when
confronted with out-of-domain test utterances in target accents that are
unseen or rarely seen during training. A common solution to address such
mismatched settings is to adapt a well-trained, speaker-independent ASR model
with a small amount of target-specific data to build personalized models for
each target setting.

Prior work on personalizing end-to-end models proposes finetuning pre-trained
ASR models using small amounts of speaker-specific utterances [3, 4]. While
these works propose different finetuning schedules that would be most
beneficial given the limited amount of target data, the question of which
speaker-specific utterances should be chosen in order to be transcribed and
further used for finetuning has received far less attention. [5] presents a
method to select sentences within a fixed budget that are most likely to
induce ASR errors and result in higher-quality personalized ASR models for
target accents compared to random selection. However, they assume access to a
small seed set of labeled utterances from the target speaker. We address the
more realistic setting where we have access only to a limited number of
_unlabeled_ utterances from the target setting.

In this work, we propose a targeted subset selection approach that makes use
of a suite of submodular mutual information (SMI) functions optimizing
different objective functions (originally defined in [6]). For a specific
target speaker or a target accent, given access to a few speech utterances, we
aim at identifying the most informative subset of speech utterances from a
larger unlabeled pool that best matches the target set. Here, the best match
is characterized by the underlying criteria of SMI functions, that makes use
of pairwise similarities between speech representations. We find this to be an
effective targeted subset selection technique for personalizing ASR models in
two settings, one involving a specific target speaker and the other involving
a specific target accent spanning multiple speakers. Our proposed technique
uses much less budgets: as low as 25% of that of random. It also results in
better fine-tuning of the ASR than an oracle system that chooses a subset
assuming access to information about the target speaker/accent.

##  2 Related work

A number of works have studied subset selection for speech recognition. [7]
and [8] use submodular functions for selecting subsets of speech utterances
for speeding up and reducing the amount of labeled data required for ASR
training. Similarly, [9] study subset selection to obtain low-vocabulary
speech corpora for ASR, while [10] uses submodular approaches for targeted
selection in machine translation. Many recent papers [11, 12] have studied
uncertainty and gradient based approaches for active learning to reduce the
transcription time for ASR models, while [13] uses a committee-based active
learning method to select speech utterances.

A number of approaches have studied personalized speech recognition, such as
for dysarthric and accented speech [3] by finetuning a subset of layers using
labelled data of targeted accents or accent adaptation [14] using labelled
data for the target accent. [15] personalizes ASR on-device using RNN
Transducers. [5] works on a problem that corresponds exactly to the reverse of
our setting by trying to determine the most error-prone sentences for the
model to record utterances on. While this can be effective for user-driven
personalization, our method is suited for when we have fixed speech utterances
and the only actionable item for us is to transcribe a subset of them.

Finally, a number of recent works have leveraged the submodular mutual
information functions (used in this work) for targeted selection. [16] use the
SMI functions for query focused and privacy-preserving summarization, while
[17] uses the SMI functions for improving the model performance on targeted
slices. Recently, [18] proposed an active learning approach using the SMI
functions for rare classes, redundancy, and OOD data.

##  3 Submodular Mutual Information (SMI) Functions

Submodular Functions: We let $\mathcal{V}$ denote the _ground-set_ of $n$ data
points $\mathcal{V}=\\{1,2,3,...,n\\}$ and a set function
$f:2^{\mathcal{V}}\xrightarrow{}\Re$. The function $f$ is submodular [19] if
it satisfies the diminishing marginal returns, namely
$f(j|\mathcal{X})=f(\mathcal{X}\cup j)-f(\mathcal{X})\geq f(j|\mathcal{Y})$
for all
$\mathcal{X}\subseteq\mathcal{Y}\subseteq\mathcal{V},j\notin\mathcal{Y}$.
Submodularity ensures that a greedy algorithm achieves bounded approximation
factor when maximized [20].

Submodular Mutual Information (SMI): Given a set of items
${\mathcal{S}},{\mathcal{T}}\subseteq\mathcal{V}$, the submodular mutual
information (MI) [21, 6] is defined as
$I_{f}({\mathcal{S}};{\mathcal{T}})=f({\mathcal{S}})+f({\mathcal{T}})-f({\mathcal{S}}\cup{\mathcal{T}})$.
Intuitively, this measures the similarity between ${\mathcal{T}}$ and
${\mathcal{S}}$ and we refer to ${\mathcal{T}}$ as the targeted set. In the
setting considered in this paper, the set ${\mathcal{T}}$ (target set)
comprises of a small set of unlabeled utterances of a speaker or an accent,
and $\mathcal{V}$ is a large unlabeled set of utterances of multiple speakers
and accents. To find an optimal subset given a target set ${\mathcal{T}}$, we
can define
$g_{{\mathcal{T}}}({\mathcal{S}})=I_{f}({\mathcal{S}};{\mathcal{T}})$,
${\mathcal{S}}\subseteq\mathcal{V}$ and maximize the same. With a greedy
algorithm, these submodular functions can be efficiently optimized within a
minimum bound (1-1/$e$) fraction of the global maximum.

###  3.1 Examples of SMI functions

We use the MI functions recently introduced in [6] and their extensions
introduced in [16, 17]. For any two data points $i\in\mathcal{V}$ and
$j\in{\mathcal{T}}$, let $s_{ij}$ denote the similarity between them.

Graph Cut MI: The submodular mutual information (SMI) instantiation of graph-
cut (GCMI) is defined as [17, 6]:

$\displaystyle
I_{f}({\mathcal{S}};{\mathcal{T}})=2\sum_{i\in{\mathcal{S}}}\sum_{j\in{\mathcal{T}}}s_{ij}$
(1)

Since maximizing GCMI maximizes the joint pairwise sum with the query set, it
will lead to a summary similar to the query set $Q$. GCMI models only query-
relevance and does not select based on diversity [17].

Facility Location MI: The Facility Location Mutual Information (FLMI) function
[17] takes the expression:

$\displaystyle
I_{f}({\mathcal{S}};{\mathcal{T}})=\sum_{i\in{\mathcal{T}}}\max_{j\in{\mathcal{S}}}s_{ij}+\sum_{i\in{\mathcal{S}}}\max_{j\in{\mathcal{T}}}s_{ij}$
(2)

FLMI is very intuitive for query relevance as well. It measures the similarity
between representation of data points that are the most relevant to the query
set, and vice versa.

Log Determinant MI: The SMI instantiation of logDMI can be defined as [17]:

$\displaystyle
I_{f}({\mathcal{S}};{\mathcal{T}})=\log\det(S_{{\mathcal{S}}})-\log\det(S_{{\mathcal{S}}}-S_{{\mathcal{S}},{\mathcal{T}}}S_{{\mathcal{T}}}^{-1}S_{{\mathcal{S}},{\mathcal{T}}}^{\intercal})$
(3)

$S_{{\mathcal{S}},{\mathcal{T}}}$ denotes the cross-similarity matrix between
the items in sets ${\mathcal{S}}$ and ${\mathcal{T}}$ and $S_{{\mathcal{S}}}$
denotes the similarity sub-matrix with rows and columns from the set
${\mathcal{S}}$. This function provides a trade-off between query-relevance
and diversity.

##  4 Our Algorithm

Setting:  We are provided a few unlabeled utterances of the speaker/accent (a
target set $\mathcal{T}$) which we would like the ASR model $M$ to be
personalized to. This target set is either a specific speaker or a specific
accent.

Goal:  The goal of the paper is to select the most informative subset
${\mathcal{S}}$ w.r.t. target ${\mathcal{T}}$ from a large corpus
$\mathcal{V}$ of unlabeled data, called the ground set. We are given a budget
constraint, which is a constraint on the total time of the selected
utterances. This corresponds to the transcription budget, since the selected
utterances need to be later transcribed by a human.

Approach:  The approach is outlined in Algo. 1. The first step is to define
the SMI functions. The SMI functions are defined by computing a euclidean
similarity kernel $s_{ij}$ on the MFCC features of the utterances.
Specifically, we set
$s_{ij}=\exp(-||\operatorname{mfcc_{i}}-\operatorname{mfcc_{j}}||^{2})$ where
$\operatorname{mfcc_{i}},\operatorname{mfcc_{j}}$ are the MFCC features of
utterances $i,j$. Using the SMI functions defined above, we select a subset
that maximizes
$g_{{\mathcal{T}}}({\mathcal{S}})=I_{f}({\mathcal{S}};{\mathcal{T}})$ for the
given targeted set of utterances ${\mathcal{T}}$. Specifically, we optimize
$g_{{\mathcal{T}}}({\mathcal{S}})=I_{f}({\mathcal{S}};{\mathcal{T}})$ subject
to the constraint $c({\mathcal{S}})\leq B$, where $c$ corresponds to the time
(in seconds) of the specific utterance and $B$ is the time budget. We use the
greedy algorithm [20, 22] with a knapsack constraint for optimizing, where
specifically given the current set ${\mathcal{S}}$, we select the item
$i=\mathop{\mathrm{argmax}}_{j\in\mathcal{V}\backslash{\mathcal{S}}}g_{{\mathcal{T}}}(j|{\mathcal{S}})$,
with the stopping criterion as $c({\mathcal{S}})\leq B$. Once, we obtain the
set $\hat{{\mathcal{S}}}$ as the solution of this optimization problem, we
obtain the transcriptions from a human, and finetune the ASR model on the
utterances in $\hat{{\mathcal{S}}}$.

1

Require: target $\mathcal{T}$, budget $B$, SMI function type $f$

Data: large unlabelled ground set $\mathcal{V}$

2 Define an SMI function
$g_{{\mathcal{T}}}({\mathcal{S}})=I_{f}(\mathcal{S};\mathcal{T})$ using
Gaussian kernel similarity with the MFCC features

3
$\hat{\mathcal{S}}\leftarrow\mathop{\mathrm{argmax}}\limits_{\mathcal{S}\subseteq\mathcal{V},~{}c(\mathcal{S})\leq
B}g_{{\mathcal{T}}}({\mathcal{S}})$

4 $D\leftarrow$ Transcribe utterances in $\hat{\mathcal{S}}$

5

6Fine-tune ASR model $M$ on $D$

7

8

Algorithm 1 Personalizing ASR model $M$

##  5 Experimental Setup

Tasks: We experiment with personalizing ASR models in two settings:  1. The
target set comes from a specific speaker, and  2. The target set comes from a
specific accent.

Datasets: We report results on two public datasets, viz., L2-Arctic and
IndicTTS, containing English speech in non-native accents. L2-Arctic has
English speech from 24 speakers spanning six non-native accents: Hindi (HIN),
Vietnamese (VTN), Chinese (CHN), Korean (KOR), Arabic (ARB) and Spanish (ESP).
IndicTTS consists of speech from 8 Indian speakers, each with a different
accent depending on their native language: Kannada (Kn), Tamil (Ta), Malayalam
(Ml), Hindi (Hi), Rajasthani (Ra), Assamese (As) and Manipuri (Ma). For each
target speaker and accent, we created data splits by partitioning $70\%$ of
the data into a ground set ($\mathcal{V}$) and a very small target set
$\mathcal{T}$ (with sizes varying from 10 to 50) and we created
test/development sets from the remaining 30% using a 27/3 split, respectively.
For L2-Arctic, the test sets for a target speaker and a target accent
contained roughly 300 utterances and 1.2K utterances, respectively. When
grouped by target speakers, $|\mathcal{V}|\approx 740$, and for a specific
target accent, $|\mathcal{V}|\approx 3000$. For IndicTTS, the average sizes of
the ground set and the test set are 4.3K and 1.9K utterances respectively.
Given that this dataset contains speech from only one speaker per accent, it
was not used for accent personalization.

Fig. 1: 2-component t-SNE (using MFCC features) on the IndicTTS dataset with 8
speakers of 8 accents.

Features. We represent each utterance as a 39-dimensional feature vector of
MFCC coefficients averaged over the duration of the utterance. Fig. 1 shows a
t-SNE plot of MFCC features of IndicTTS test set utterances coloured using
speaker IDs. We observe good speaker-specific clusters that are well-separated
from each other.

ASR Models: Following [5], our pre-trained model is based on the
QuartzNet-15x5 [23] architecture. It is trained on LibriSpeech [24] for 400
epochs using the CTC-loss [25] and yields a WER of 3.90 on the test-clean
split of LibriSpeech. The QuartzNet-15x5 architecture is fully convolutional
with residual connections. This model is finetuned with our selected subsets
of accented speech to minimize CTC loss using the NovoGrad optimizer [26] for
100 epochs with a batch size of 16, a linearly decaying learning rate of
$10^{-5}$ and early stopping based on the dev set. In all our experiments, we
report results averaged over three runs using three different seeds.

##  6 Experiments and Results

We experiment with personalized ASR systems for a specific target speaker and
a specific target accent. For each setting, we compare the following
approaches: (i) random selection (baseline), (ii) SMI-based selection using
three SMI functions, FLMI, GCMI and LogDMI and (iii) a skyline oracle system
that uses the speaker/accent metadata and randomly samples from the targeted
accent/speaker. Unless specified otherwise, we use target sets of size 10 and
a transcription budget of 360 sec for L2-Arctic and 492 sec for IndicTTS,
amounting to an average of 100 utterances in each dataset.

Accent | Pre-train | Random | FLMI | GCMI | LogDMI | Skyline
---|---|---|---|---|---|---
arabic | 24.29 | 23.96 | 22.38 | 22.49 | 22.08 | 22.05
hindi | 18.05 | 17.58 | 15.47 | 16.58 | 16.26 | 16.15
chinese | 30.66 | 29.19 | 27.51 | 27.78 | 27.87 | 27.91
korean | 19.05 | 18.06 | 17.08 | 18.45 | 18.45 | 17.18
spanish | 23.44 | 22.97 | 21.92 | 22.32 | 21.96 | 22.39
vietnamese | 37.03 | 35.37 | 33.10 | 33.20 | 32.78 | 33.2

Table 1: Accent personalisation in L2-Arctic ($B=360s$)

Speaker | Pre | Random | FLMI | GCMI | LogDMI | Skyline
---|---|---|---|---|---|---
ABA[ARB/M] | 23.98 | 23.97 | 21.22 | 21.67 | 21.75 | 21.80
ASI[HIN/M] | 14.30 | 14.77 | 12.80 | 12.90 | 13.01 | 13.33
BWC[CHN/M] | 33.17 | 32.46 | 28.06 | 28.94 | 27.58 | 27.58
HJK[KOR/F] | 13.28 | 13.06 | 11.70 | 12.00 | 11.77 | 11.21
NJS[ESP/F] | 16.31 | 15.75 | 14.67 | 14.84 | 14.70 | 14.26
PNV[VTN/F] | 19.36 | 18.48 | 18.26 | 17.20 | 17.97 | 17.38

Table 2:  Speaker personalisation in L2-Arctic ($B=360s$). Speaker ID is
followed by [accent/gender].

Speaker | Pre-train | Random | FLMI | GCMI | LogDMI | Skyline
---|---|---|---|---|---|---
Kn, M | 18.73 | 15.79 | 14.07 | 13.90 | 14.77 | 14.20
Ml, M | 19.49 | 18.17 | 15.36 | 15.73 | 15.65 | 15.76
Ra, M | 21.88 | 16.87 | 15.71 | 15.31 | 15.23 | 15.8
Hi, M | 11.14 | 9.86 | 9.59 | 9.62 | 9.09 | 8.89
Ta, M | 12.48 | 11.88 | 11.79 | 11.66 | 12.26 | 11.92
As, F | 27.06 | 23.21 | 20.26 | 20.40 | 19.89 | 19.75
Gu, F | 13.73 | 11.21 | 9.98 | 10.40 | 9.83 | 10.17
Ma, F | 53.08 | 46.98 | 41.78 | 42.69 | 42.39 | 42.15

Table 3: Speaker personalisation in IndicTTS ($B=492s$). Speaker ID is denoted
as “accent, gender”.

Personalized ASR for a target accent: Table 1 shows our main results with
accent personalization on L2-Arctic test sets. We observe consistent WER
reductions using the SMI functions compared to random selection with FLMI
performing the best, followed by LogDMI and GCMI. In our skyline, we finetune
using a subset created by randomly selecting an equal number of test samples
from each speaker of the target accent. We find that the best SMI-based
systems outperform the skyline for nearly all accents (except Arabic).

We further examine the distribution of selected samples across accents using
each of the three SMI functions. FLMI selects utterances almost exclusively
from the target accent ($99.4\%$ on average), while LogDMI and GCMI select
$93.5\%$ and $89.8\%$ samples from the target accent, respectively. When
subject to a limited budget, we hypothesize that both FLMI and LogDMI perform
better than GCMI, since the latter does not explicitly reward diversity and
might disproportionally favour specific speakers within an accent.
(Distinctions between the SMI functions are diminished with increasing the
budget as we will see in Fig 2.)
Personalized ASR for a target speaker: Tables 2 and 3 show our main results by
personalizing to a target speaker in L2-Arctic and IndicTTS, respectively.
Again, we see consistent WER reductions using all three SMI functions compared
to the random selection baseline. The skyline picks utterances exclusively
from the target speaker. Our best SMI-based systems, LogDMI and FLMI perform
comparably to the skyline.

Both FLMI and GCMI almost exclusively select speech samples from the target
speaker ($99.8\%$), and LogDMI picks $94.8\%$ samples in the selected subset
from the target speaker. When personalizing to a target speaker under a
limited budget, GCMI largely selects from the target speaker (given its
objective which does not explicitly reward diversity) unlike in the target
accent setting.

Rankings among SMI functions based on WER reductions are less consistent when
the budgets are increased, as seen in Fig. 2 that shows the WER improvements
using GCMI, FLMI and LogDMI for a specific accent (Chinese) and target speaker
(Assamese female) by varying durations of the selected subsets. However, they
always consistently outperform random selection. For Chinese-accented English,
we observe that FLMI yields a WER reduction of 3.15 with 6 minutes of data,
while a similar reduction needs 24 minutes using random selection.

$\displaystyle{0}$$\displaystyle{10}$$\displaystyle{20}$$\displaystyle{30}$$\displaystyle{40}$$\displaystyle{0}$$\displaystyle{1}$$\displaystyle{2}$$\displaystyle{3}$$\displaystyle{4}$$\displaystyle{5}$$\displaystyle{6}$WER
improvementTarget: Chinese accentFLMILogDMIGCMIRandom

$\displaystyle{0}$$\displaystyle{10}$$\displaystyle{20}$$\displaystyle{30}$$\displaystyle{40}$$\displaystyle{50}$$\displaystyle{60}$Duration
of selections
(min)$\displaystyle{0}$$\displaystyle{2}$$\displaystyle{4}$$\displaystyle{6}$$\displaystyle{8}$$\displaystyle{10}$WER
improvementTarget: Assamese speaker [F]FLMILogDMIGCMIRandom

Fig. 2: Plotting WER improvements against $|\hat{S}|$ (in minutes)

##  7 Conclusion

In this work, we propose a targeted subset selection approach using submodular
mutual information functions that help identify speech utterances that best
match an unlabeled target set of limited size. We evaluate our approach by
limiting the target set to either a single speaker or a single accent. Our
method consistently outperforms random selection methods and even beats an
oracle system when the target set is from a specific accent. Future work will
explore extensions of this approach to adapt to speakers with speech
impediments.

## References

  * [1] Kanishka Rao, Haşim Sak, and Rohit Prabhavalkar,  “Exploring architectures, data and units for streaming end-to-end speech recognition with rnn-transducer,”  in 2017 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU). IEEE, 2017, pp. 193–199.
  * [2] Chung-Cheng Chiu, Tara N. Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Zhifeng Chen, Anjuli Kannan, Ron J. Weiss, Kanishka Rao, Ekaterina Gonina, Navdeep Jaitly, Bo Li, Jan Chorowski, and Michiel Bacchiani,  “State-of-the-art speech recognition with sequence-to-sequence models,”  in ICASSP 2018. IEEE, 2018, pp. 4774–4778.
  * [3] Joel Shor, Dotan Emanuel, Oran Lang, Omry Tuval, Michael Brenner, Julie Cattiau, Fernando Vieira, Maeve McNally, Taylor Charbonneau, Melissa Nollstadt, Avinatan Hassidim, and Yossi Matias,  “Personalizing asr for dysarthric and accented speech with limited data,”  in Proc. Interspeech 2019, 2019, pp. 784–788.
  * [4] Khe Chai Sim, Petr Zadrazil, and Françoise Beaufays,  “An investigation into on-device personalization of end-to-end automatic speech recognition models,”  arXiv preprint arXiv:1909.06678, 2019.
  * [5] Abhijeet Awasthi, Aman Kansal, Sunita Sarawagi, and Preethi Jyothi,  “Error-driven fixed-budget asr personalization for accented speakers,”  in ICASSP 2021. IEEE, 2021, pp. 7033–7037.
  * [6] Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, and Himanshu Asnani,  “Submodular combinatorial information measures with applications in machine learning,”  In ALT, 2021.
  * [7] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes,  “Using document summarization techniques for speech data subset selection,”  in NAACL, 2013, pp. 721–726.
  * [8] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes,  “Unsupervised submodular subset selection for speech data,”  in ICASSP 2014, 2014, pp. 4107–4111.
  * [9] Yuzong Liu, Rishabh Iyer, Katrin Kirchhoff, and Jeff Bilmes,  “SVitchboard II and fiSVer i: high-quality limited-complexity corpora of conversational English speech,”  in Proc. Interspeech 2015, 2015, pp. 673–677.
  * [10] Katrin Kirchhoff and Jeff Bilmes,  “Submodularity for data selection in machine translation,”  in EMNLP, 2014.
  * [11] Yang Yuan, Soo-Whan Chung, and Hong-Goo Kang,  “Gradient-based active learning query strategy for end-to-end speech recognition,”  in ICASSP 2019. IEEE, 2019, pp. 2832–2836.
  * [12] Ali Raza Syed, Andrew Rosenberg, and Michael Mandel,  “Active learning for low-resource speech recognition: Impact of selection size and language modeling data,”  in ICASSP 2017, 2017, pp. 5315–5319.
  * [13] Yuzo Hamanaka, Koichi Shinoda, Sadaoki Furui, Tadashi Emori, and Takafumi Koshinaka,  “Speech modeling based on committee-based active learning,”  in ICASSP 2010, 2010, pp. 4350–4353.
  * [14] Sining Sun, Ching-Feng Yeh, Mei-Yuh Hwang, Mari Ostendorf, and Lei Xie,  “Domain adversarial training for accented speech recognition,”  in ICASSP 2018, 2018, pp. 4854–4858.
  * [15] Katrin Tomanek, Françoise Beaufays, Julie Cattiau, Angad Chandorkar, and Khe Chai Sim,  “On-device personalization of automatic speech recognition models for disordered speech,” 2021.
  * [16] Vishal Kaushal, Suraj Kothawade, Ganesh Ramakrishnan, Jeff Bilmes, Himanshu Asnani, and Rishabh Iyer,  “A unified framework for generic, query-focused, privacy preserving and update summarization using submodular information measures,”  arXiv preprint arXiv:2010.05631, 2020.
  * [17] Vishal Kaushal, Suraj Kothawade, Ganesh Ramakrishnan, Jeff Bilmes, and Rishabh Iyer,  “Prism: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization,”  arXiv preprint arXiv:2103.00128, 2021.
  * [18] Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer,  “Similar: Submodular information measures based active learning in realistic scenarios,”  to appear in NeurIPS, 2021.
  * [19] Satoru Fujishige,  Submodular functions and optimization,  Elsevier, 2005.
  * [20] G.L. Nemhauser, L.A. Wolsey, and M. L. Fisher,  “An analysis of approximations for maximizing submodular set functions—i,”  Mathematical programming, vol. 14, no. 1, pp. 265–294, 1978.
  * [21] Anupam Gupta and Roie Levin,  “The online submodular cover problem,”  in ACM-SIAM Symposium on Discrete Algorithms, 2020.
  * [22] Hui Lin and Jeff Bilmes,  “Multi-document summarization via budgeted maximization of submodular functions,”  in NAACL-HLT, 2010, pp. 912–920.
  * [23] Samuel Kriman, Stanislav Beliaev, Boris Ginsburg, Jocelyn Huang, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, and Yang Zhang,  “Quartznet: Deep automatic speech recognition with 1d time-channel separable convolutions,”  in ICASSP 2020, 2020, pp. 6124–6128.
  * [24] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur,  “Librispeech: an asr corpus based on public domain audio books,”  in ICASSP 2015, 2015.
  * [25] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber,  “Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,”  in ICML, 2006, pp. 369–376.
  * [26] Boris Ginsburg, Patrice Castonguay, Oleksii Hrinchuk, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, Huyen Nguyen, Yang Zhang, and Jonathan M. Cohen,  “Stochastic gradient methods with layer-wise adaptive moments for training of deep networks,”  arXiv preprint arXiv:1905.11286, 2019.