# Introduction to Robust Power Domination

Beth Bjorkman Air Force Research Laboratory<EMAIL_ADDRESS>Esther
Conrad Iowa State University<EMAIL_ADDRESS>
(December 15, 2022)

###### Abstract

Sensors called phasor measurement units (PMUs) are used to monitor the
electric power network. The power domination problem seeks to minimize the
number of PMUs needed to monitor the network. We extend the power domination
problem and consider the minimum number of sensors and appropriate placement
to ensure monitoring when $k$ sensors are allowed to fail with multiple
sensors allowed to be placed in one location. That is, what is the minimum
multiset of the vertices, $S$, such that for every $F\subseteq S$ with
$|F|=k$, $S\setminus F$ is a power dominating set. Such a set of PMUs is
called a _$k$ -robust power domination set_. This paper generalizes the work
done by Pai, Chang and Wang in 2010 on vertex-fault-tolerant power domination,
which did not allow for multiple sensors to be placed at the same vertex. We
provide general bounds and determine the $k$-robust power domination number of
some graph families.

Keywords: robust power domination, power domination, tree
AMS subject classification: 05C69, 05C85, 68R10, 94C15

##  1 Introduction

The power domination problem seeks to find the placement of the mimimum number
of sensors called phasor measurement units (PMUs) needed to monitor an
electric power network. In [3], Haynes et al. defined the power domination
problem in graph theoretic terms by placing PMUs at a set of initial vertices
and then applying observation rules to the vertices and edges of the graph.
This process was simplified by Brueni and Heath in [1].

Pai, Chang, and Wang [5] generalized power domination to create _vertex-fault-
tolerant power domination_ in 2010 to model the possibility of sensor failure.
The $k$-fault-tolerant power domination problem seeks to find the minimum
number of PMUs needed to monitor a power network (and their placements) given
that any $k$ of the PMUs will fail. The vertex containing the failed PMU
remains in the graph, as do its edges; it is only the PMU that fails. This
generalization allows for the placement of only one PMU per vertex.

We consider the related problem of the minimum number of PMUs needed to
monitor a power network given that $k$ PMUs will fail _but also allow for
multiple PMUs to be placed at a given vertex_. We call this _PMU-defect-robust
power domination_ , as it is not the vertices that cause a problem with
monitoring the network, but the individual PMUs themselves. This models
potential synchronization issues, sensor errors, or malicious interference
with the sensor outputs.

To demonstrate the difference between vertex-fault-tolerant power domination
and PMU-defect-robust power domination and how drastic the difference between
these two parameters can be, consider the star on $16$ vertices with $k=1$,
shown in Figure 1. Notice that in vertex-fault-tolerant power domination, if
one PMU is placed in the center of the star and this PMU fails, then all but
one of the leaves must have PMUs in order to still form a power dominating
set. However, with PMU-defect-robust power domination, placing two PMUs in the
center is sufficient to ensure that even if one PMU fails, the power
domination process will still observe all of the vertices.

$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$0$$1$ |  | $0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$2$
---|---|---
vertex-fault-tolerant |  | PMU-defect-robust
Figure 1: A minimum vertex-fault-tolerant power dominating set and a minimum
PMU-defect-robust power dominating set shown for a star when $k=1$.

In Section 2, we review definitions from past work and formally define PMU-
defect-robust power domination. We also include some basic results in that
section. Section 3 consists of general bounds for $k$-robust power domination
and in Section 4 we demonstrate the tightness of these bounds with a family of
complete bipartite graphs. In Section 5 we establish the $k$-robust power
domination number for trees. Section 6 contains concluding remarks, including
suggestions for future work.

##  2 Preliminaries

We begin by giving relevant graph theory definitions. Then we define power
domination, vertex-fault-tolerant power domination, and PMU-defect-robust
power domination. Finally, we include useful properties of the floor and
ceiling functions.

###  2.1 Graph Theory

A graph $G$ is a set of vertices, $V(G)$, and a set of edges, $E(G)$. Each
(unordered) edge consists of a set of two distinct vertices; the edge
$\\{u,v\\}$ is often written as $uv$. When $G$ is clear, we write $V=V(G)$ and
$E=E(G)$. A _path_ from $v_{1}$ to $v_{\ell+1}$ is a sequence of vertices and
edges $v_{1},e_{1},v_{2},e_{2},\ldots,v_{\ell},e_{\ell},v_{\ell+1}$ so that
the $v_{i}$ are distinct vertices and $v_{i}\in e_{i}$ for all $i$ and
$v_{i}\in e_{i-1}$ for all $i\geq 2$. Such a path has _length_ $\ell$. The
_distance_ between vertices $u$ and $v$ is the minimum length of a path
between $u$ and $v$. A graph $G$ is _connected_ if there is a path from any
vertex to any other vertex. _Throughout what follows, we consider only graphs
that are connected._

We say that vertices $u$ and $v$ are _neighbors_ if $uv\in E$. The
_neighborhood_ of $u\in V$ is the set containing all neighbors of $u$ and is
denoted by $N(u)$. The _closed neighborhood_ of $u$ is $N[u]=N(u)\cup\\{u\\}$.
The _degree_ of a vertex $u\in V$ is the number of edges that contain $u$,
that is, $\operatorname{deg}_{G}\left(u\right)=|N(u)|$. When $G$ is clear, we
omit the subscript. The _maximum degree_ of a graph $G$ is
$\Delta\left(G\right)=\displaystyle\max_{v\in
V}\operatorname{deg}\left(v\right)$.

A _subgraph_ $H$ of a graph $G$ is a graph such that $V(H)\subseteq V(G)$ and
$E(H)\subseteq E(G)$. An _induced subgraph_ $H$ of a graph $G$, denoted
$H=G[V(H)]$, is a graph with vertex set $V(H)\subseteq V(G)$ and edge set
$E(H)=\\{uv:u,v\in V(H)\text{ and }uv\in E(G)\\}$.

We refer the reader to Graph Theory by Diestel [2] for additional graph
terminology not detailed here.

###  2.2 Power domination, vertex-fault-tolerant power domination, and PMU-
defect-robust power domination

What follows is an equivalent statement of the power domination process as
defined in [3], and established by [1].

The _power domination process_ on a graph $G$ with initial set $S\subseteq V$
proceeds recursively by:

  1. 1.

$B=\displaystyle\bigcup_{v\in S}N[v]$

  2. 2.

While there exists $v\in B$ such that exactly one neighbor, say $u$, of $v$ is
_not_ in $B$, add $u$ to $B$.

Step 1 is referred to as the _domination step_ and each repetition of step 2
is called a _zero forcing step_. During the process, we say that a vertex in
$B$ is _observed_ and a vertex not in $B$ is _unobserved_. A _power dominating
set_ of a graph $G$ is an initial set $S$ such that $B=V(G)$ at the
termination of the power domination process. The _power domination number_ of
a graph $G$ is the minimum cardinality of a power dominating set of $G$ and is
denoted by $\gamma_{P}\left(G\right)$.

In [5], Pai, Chang, and Wang define the following variant of power domination.
For a graph $G$ and an integer $k$ with $0\leq k\leq|V|$, a set $S\subseteq V$
is called a _$k$ -fault-tolerant power dominating set of $G$_ if $S\setminus
F$ is still a power dominating set of $G$ for any subset $F\subseteq V$ with
$|F|\leq k$. The _$k$ -fault-tolerant power domination number_, denoted by
${\gamma}_{P}^{k}\left(G\right)$, is the minimum cardinality of a $k$-fault-
tolerant power dominating set of $G$.

While $k$-fault-tolerant power domination allows us to examine what occurs
when a previously chosen PMU location is no longer usable (yet the vertex
remains in the graph), it is also interesting to study when an individual PMU
fails. That is, allow for multiple PMUs to be placed at the same location and
consider if a subset of the PMUs fail. This also avoids issues with poorly
connected graphs, such as in Figure 1, where ${\gamma}_{P}^{1}\left(G\right)$
may be close to the number of vertices of $G$. Thus we define _PMU-defect-
robust power domination_ as follows.

######  Definition 2.1.

For a given graph $G$ and integer $k\geq 0$, we say that a multiset $S$, each
of whose elements is in $V$, is a _$k$ -robust power dominating set_ of $G$ if
$S\setminus F$ is a power dominating set of $G$ for any submultiset $F$ of $S$
with $|F|=k$. We shorten $k$-robust power dominating set of $G$ to $k$-rPDS of
$G$. The size of a minimum $k$-rPDS is denoted by
$\ddot{\gamma}_{P}^{k}\left(G\right)$ and such a multiset is also referred to
as a $\ddot{\gamma}_{P}^{k}\text{-set}$ of $G$. The _number of PMUs_ at a
vertex $v\in S$ is its multiplicity in $S$, denoted by
$\operatorname{\\#PMU}_{S}\left(v\right)$, or when $S$ is clear, by
$\operatorname{\\#PMU}\left(v\right)$.

There are several observations that one can quickly make.

######  Observation 2.2.

Let $G$ be a graph and $k\geq 0$. Then

  1. 1.

$\ddot{\gamma}_{P}^{0}\left(G\right)={\gamma}_{P}^{0}\left(G\right)=\gamma_{P}\left(G\right)$,

  2. 2.

$\ddot{\gamma}_{P}^{k}\left(G\right)\leq{\gamma}_{P}^{k}\left(G\right)$,

  3. 3.

$\gamma_{P}\left(G\right)=1$ if and only if
$\ddot{\gamma}_{P}^{k}\left(G\right)=k+1$.

For any minimum $k$-rPDS, having more than $k+1$ PMUs at a single vertex is
redundant.

######  Observation 2.3.

Let $G$ be a graph and $k\geq 0$. If $S$ is a
$\ddot{\gamma}_{P}^{k}\text{-set}$ of $G$, then for all $v\in S$ we have
$\operatorname{\\#PMU}\left(v\right)\leq k+1$.

###  2.3 Floor and ceiling functions

Throughout what follows, recall the following rules for the floor and ceiling
functions. Most can be found in Chapter 3 in [4] and we provide proofs for the
rest.

######  Proposition 2.4.

[4, Equation 3.11] If $m$ is an integer, $n$ is a positive integer, and $x$ is
any real number, then

$\left\lceil\frac{\left\lceil
x\right\rceil+m}{n}\right\rceil=\left\lceil\frac{x+m}{n}\right\rceil.$

######  Proposition 2.5.

[4, Ch. 3 Problem 12] If $m$ is an integer and $n$ is a positive integer, then

$\left\lceil\frac{m}{n}\right\rceil=\left\lfloor\frac{m-1}{n}\right\rfloor+1.$

######  Proposition 2.6.

[4, Equation 3.4] For any real number $x$, $\lceil-x\rceil=-\lfloor x\rfloor$.

######  Proposition 2.7.

If $x$ and $y$ are real numbers then

$\lceil x\rceil+\lceil y\rceil-1\leq\lceil x+y\rceil.$

###### Proof.

Observe that $\left\lceil x\right\rceil-1+\left\lceil y\right\rceil-1<x+y$ and
so $\left\lceil x\right\rceil+\left\lceil y\right\rceil-2<\left\lceil
x+y\right\rceil$ which is a strict inequality of integers, so $\lceil
x\rceil+\lceil y\rceil-1\leq\lceil x+y\rceil$. ∎

We can repeatedly apply the inequality in Proposition 2.7 to obtain

######  Corollary 2.8.

If $x$ is a real number and $a$ is a positive integer then

$a\lceil x\rceil\leq\lceil ax\rceil+a-1.$

##  3 General bounds

A useful property of robust power domination is the subadditivity of the
parameter with respect to $k$. This idea is established in the next three
statements.

######  Proposition 3.1.

Let $k\geq 0$. For any graph $G$,
$\ddot{\gamma}_{P}^{k}\left(G\right)+1\leq\ddot{\gamma}_{P}^{k+1}\left(G\right)$.

###### Proof.

Consider a $\ddot{\gamma}_{P}^{k+1}\text{-set}$, $S$, of $G$. Let $v\in S$.
Create $S^{\prime}=S\setminus\\{v\\}$, that is, $S^{\prime}$ is $S$ with one
fewer PMU at $v$. Observe that for any $F^{\prime}\subseteq S^{\prime}$ with
$|F^{\prime}|=k$, we have $F^{\prime}\cup\\{v\\}\subseteq S$ and
$|F^{\prime}\cup\\{v\\}|=k+1$. Hence
$S\setminus\left(F^{\prime}\cup\\{v\\}\right)$ is a power dominating set of
$G$. Thus, for any such $F^{\prime}$, we have
$\left(S\setminus\\{v\\}\right)\setminus F^{\prime}=S^{\prime}\setminus
F^{\prime}$ is a power dominating set of $G$. Therefore, $S^{\prime}$ is a
$k$-robust power dominating set of $G$ of size $|S|-1$. ∎

Proposition 3.1 can be applied repeatedly to obtain the next result.

######  Corollary 3.2.

Let $k\geq 0$ and $j\geq 1$. For any graph $G$,

$\ddot{\gamma}_{P}^{k}\left(G\right)+j\leq\ddot{\gamma}_{P}^{k+j}\left(G\right).$

Corollary 3.2 implies the lower bound in the next proposition. The upper bound
follows from taking $k+1$ copies of any minimum power dominating set for $G$
to form a $k$-rPDS.

######  Proposition 3.3.

Let $k\geq 0$. For any graph $G$,

$\gamma_{P}\left(G\right)+k\leq\ddot{\gamma}_{P}^{k}\left(G\right)\leq(k+1)\gamma_{P}\left(G\right).$

Observe that if $\gamma_{P}\left(G\right)=1$ for any graph $G$, both
Observation 2.2 and Proposition 3.3 demonstrate that
$\ddot{\gamma}_{P}^{k}\left(G\right)=k+1.$

Haynes et al. observed in [3, Observation 4] that in a graph with maximum
degree at least three, a minimum power dominating set can be chosen in which
each vertex has degree at least $3$. We observe that this is the same for
robust power domination.

######  Observation 3.4.

Let $k\geq 0$. If $G$ is a connected graph with $\Delta(G)\geq 3$, then $G$
contains a $\ddot{\gamma}_{P}^{k}\text{-set}$ in which every vertex has degree
at least 3.

A _terminal path_ from a vertex $v$ in $G$ is a path from $v$ to a vertex $u$
such that $\operatorname{deg}\left(u\right)=1$ and every internal vertex on
the path has degree 2. A _terminal cycle_ from a vertex $v$ in $G$ is a cycle
$v,u_{1},u_{2},\ldots,u_{\ell},v$ in which
$\operatorname{deg}_{G}\left(u_{i}\right)=2$ for $i=1,\ldots,\ell$.

######  Proposition 3.5.

Let $k\geq 0$ and let $G$ be a connected graph with $\Delta(G)\geq 3$. Let $S$
be a $\ddot{\gamma}_{P}^{k}\text{-set}$ in which every vertex has degree at
least 3. Any vertex $v\in S$ that has at least two terminal paths from $v$
must have $\operatorname{\\#PMU}\left(v\right)=k+1$. Any vertex $v\in S$ that
has at least one terminal cycle must have
$\operatorname{\\#PMU}\left(v\right)=k+1$.

###### Proof.

Let $v$ be a vertex in $S$ and suppose that $v$ has two terminal paths or a
terminal cycle. All of the vertices in the terminal paths or terminal cycle
have degree 1 or 2 and so are not in $S$. Thus, there are at least two
neighbors of $v$ which can only be observed via $v$. As $v$ can only observe
both of these neighbors via the domination step, it must be the case that
$\operatorname{\\#PMU}\left(v\right)=k+1$. ∎

Zhao, Kang, and Chang [6] defined the family of graphs $\mathcal{T}$ to be
those graphs obtained by taking a connected graph $H$ and for each vertex
$v\in V(H)$ adding two vertices, $v^{\prime}$ and $v^{\prime\prime}$; and two
edges $vv^{\prime}$ and $vv^{\prime\prime}$, with the edge
$v^{\prime}v^{\prime\prime}$ optional. The complete bipartite graph $K_{3,3}$
is the graph with vertex set $X\cup Y$ with $|X|=|Y|=3$ and edge set
$E=\\{xy:x\in X,y\in y\\}$.

######  Theorem 3.6.

[6, Theorem 3.] If $G$ is a connected graph on $n\geq 3$ vertices then
$\gamma_{P}\left(G\right)\leq\frac{n}{3}$ with equality if and only if
$G\in\mathcal{T}\cup\\{K_{3,3}\\}$.

This gives an upper bound for $\ddot{\gamma}_{P}^{k}\left(G\right)$ in terms
of the size of the vertex set and equality conditions, as demonstrated in the
next corollary.

######  Corollary 3.7.

Let $G$ be a connected graph with $n\geq 3$ vertices. Then
$\ddot{\gamma}_{P}^{k}\left(G\right)\leq(k+1)\frac{n}{3}$ for $k\geq 0$. When
$k=0$, this is an equality if and only if $G\in\mathcal{T}\cup\\{K_{3,3}\\}$.
When $k\geq 1$, this is an equality if and only if $G\in\mathcal{T}$.

###### Proof.

The upper bound is given by Proposition 3.3 and Theorem 3.6. From these
results, we need only consider $\mathcal{T}\cup\\{K_{3,3}\\}$ for equality.
The $k=0$ case follows directly from the power domination result. Let $k\geq
1$.

First consider $G\in\mathcal{T}$, constructed from $H$. Note that
$\Delta\left(G\right)\geq 3$, so there exists a
$\ddot{\gamma}_{P}^{k}\text{-set}$, say $S$, in which every vertex has degree
at least 3, so every vertex in $S$ is a vertex of $H$. For each $v\in V(H)$,
$\operatorname{deg}_{G}\left(v\right)\geq 3$ and there are either two terminal
paths (if $v^{\prime}v^{\prime\prime}\not\in E(H)$) or a terminal cycle (if
$v^{\prime}v^{\prime\prime}\in E(H)$). By Proposition 3.5, each $v\in V(H)$
must have at least $k+1$ PMUs.

Finally, consider $K_{3,3}$. Note that $\gamma_{P}\left(K_{3,3}\right)=2$. We
will see in Theorem 4.3 that
$\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)=k+\left\lfloor\frac{k}{5}\right\rfloor+2<2(k+1)$
for $k\geq 1$. ∎

######  Definition 3.8.

For any graph $G$, define $s\left(G\right)$ to be the size of the largest set
$A\subseteq V$ such that for any $B\subseteq A$ with
$|B|=\gamma_{P}\left(G\right)$, $B$ is a power dominating set of $G$.

Observe that $\gamma_{P}\left(G\right)\leq s\left(G\right)$. For example, the
star graph $S_{16}$ shown in Figure 1 has
$\gamma_{P}\left(S_{16}\right)=s\left(S_{16}\right)=1$. The complete bipartite
graph $K_{3,3}$ has $\gamma_{P}\left(K_{3,3}\right)=2$ and
$s\left(K_{3,3}\right)=6$ as any two vertices of $K_{3,3}$ form a power
dominating set.

######  Proposition 3.9.

For any graph $G$ and $k\geq 0$, if $s\left(G\right)\geq
k+\gamma_{P}\left(G\right)$ then
$\ddot{\gamma}_{P}^{k}\left(G\right)=k+\gamma_{P}\left(G\right)$.

###### Proof.

If $s\left(G\right)\geq k+\gamma_{P}\left(G\right)$, then there exists a set
$S$ of size at least $k+\gamma_{P}\left(G\right)$ so that any
$\gamma_{P}\left(G\right)$ elements of $S$ form a power dominating set of $G$.
Thus, any $\gamma_{P}\left(G\right)+k$ elements of $S$ form a $k$-rPDS of $G$
of size $\gamma_{P}\left(G\right)+k$ and so
$\ddot{\gamma}_{P}^{k}\left(G\right)\leq\gamma_{P}\left(G\right)+k$. By the
lower bound in Proposition 3.3,
$\ddot{\gamma}_{P}^{k}\left(G\right)\geq\gamma_{P}\left(G\right)+k$. ∎

When $s\left(G\right)>\gamma_{P}\left(G\right)\geq 2$, the following upper
bound sometimes improves the upper bound from Proposition 3.3.

######  Theorem 3.10.

If $s\left(G\right)>\gamma_{P}\left(G\right)\geq 2$, then
$\ddot{\gamma}_{P}^{k}\left(G\right)\leq\left\lceil\frac{s\left(G\right)(k+\gamma_{P}\left(G\right)-1)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil$
for $k\geq 1$.

###### Proof.

Let $A=\left\\{v_{1},v_{2},\ldots,v_{s\left(G\right)}\right\\}\subseteq V$ be
a maximum set such that any subset of size $\gamma_{P}\left(G\right)$ is a
power dominating set of $G$. For what follows, let
$p=\left\lceil\frac{s\left(G\right)(k+\gamma_{P}\left(G\right)-1)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil$.
Construct
$S=\left\\{v_{1}^{m_{1}},v_{2}^{m_{2}},\ldots,v_{s\left(G\right)}^{m_{s\left(G\right)}}\right\\}$
where

$\displaystyle m_{1}=\left\lceil\frac{p}{s\left(G\right)}\right\rceil\text{
and
}m_{i}=\min\left\\{\left\lceil\frac{p}{s\left(G\right)}\right\rceil,p-\sum_{j=1}^{i-1}m_{j}\right\\}\text{
for }i\geq 2.$

In order to show that $S$ is a $k$-rPDS of $G$, we will show that
$p-k\geq(\gamma_{P}\left(G\right)-1)\left\lceil\frac{p}{s\left(G\right)}\right\rceil+1.$
Assume this is true. Then whenever we have $p$ PMUs and $k$ fail, there are at
least
$(\gamma_{P}\left(G\right)-1)\left\lceil\frac{p}{s\left(G\right)}\right\rceil+1$
working PMUs. As each vertex has at most
$\left\lceil\frac{p}{s\left(G\right)}\right\rceil$ PMUs, there are at least
$\gamma_{P}\left(G\right)$ vertices of $A$ that must have at least one PMU
remaining and so form a power dominating set.

We prove the equivalent statement

$p-k-(\gamma_{P}\left(G\right)-1)\left\lceil\frac{p}{s\left(G\right)}\right\rceil\geq
1.$

Observe that by Proposition 2.4,

$\displaystyle
p-k-(\gamma_{P}\left(G\right)-1)\left\lceil\frac{p}{s\left(G\right)}\right\rceil$
$\displaystyle=p-k-(\gamma_{P}\left(G\right)-1)\left\lceil\frac{k+\gamma_{P}\left(G\right)-1}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil.$

Then by Corollary 2.8 and simplifying, we see that

$\displaystyle p-k-(\gamma_{P}\left(G\right)$
$\displaystyle-1)\left\lceil\frac{p}{s\left(G\right)}\right\rceil\geq
p-k-\left(\left\lceil\frac{(k+\gamma_{P}\left(G\right)-1)(\gamma_{P}\left(G\right)-1)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil+\gamma_{P}\left(G\right)-2\right)$
$\displaystyle=p-\left(\left\lceil\frac{(k+\gamma_{P}\left(G\right)-1)(\gamma_{P}\left(G\right)-1)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil+\gamma_{P}\left(G\right)-2+k\right)$
$\displaystyle=p-\left\lceil\frac{(k+\gamma_{P}\left(G\right)-1)(\gamma_{P}\left(G\right)-1)+(s\left(G\right)-\gamma_{P}\left(G\right)+1)(\gamma_{P}\left(G\right)-2+k)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil$
$\displaystyle=p-\left\lceil\frac{s\left(G\right)(k+\gamma_{P}\left(G\right)-1)-s\left(G\right)+\gamma_{P}\left(G\right)-1}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil$
$\displaystyle=p-\left\lceil\frac{s\left(G\right)(k+\gamma_{P}\left(G\right)-1)}{s\left(G\right)-\gamma_{P}\left(G\right)+1}\right\rceil+1$
$\displaystyle=1.\qed$

To see the difference between the upper bounds given in Theorem 3.10 and
Proposition 3.3, let $s\left(G\right)=\gamma_{P}\left(G\right)+r$. Then
Theorem 3.10 becomes

$\displaystyle\ddot{\gamma}_{P}^{k}\left(G\right)$
$\displaystyle\leq\left\lceil\frac{(\gamma_{P}\left(G\right)+r)(k+\gamma_{P}\left(G\right)-1)}{r+1}\right\rceil$
$\displaystyle=\left\lceil\frac{\gamma_{P}\left(G\right)(k+1)+\gamma_{P}\left(G\right)(\gamma_{P}\left(G\right)-2)+r(k+\gamma_{P}\left(G\right)-1)}{r+1}\right\rceil$
$\displaystyle=\gamma_{P}\left(G\right)(k+1)+\left\lceil\frac{-r\gamma_{P}\left(G\right)(k+1)+\gamma_{P}\left(G\right)(\gamma_{P}\left(G\right)-2)+r(k+\gamma_{P}\left(G\right)-1)}{r+1}\right\rceil$
$\displaystyle=\gamma_{P}\left(G\right)(k+1)+\left\lceil\frac{-kr(\gamma_{P}\left(G\right)-1)+\gamma_{P}\left(G\right)(\gamma_{P}\left(G\right)-2)-r}{r+1}\right\rceil.$

This means that the bound from Theorem 3.10 improves the upper bound in
Proposition 3.3 when the second term above is negative. Since $r\geq 1$ and
$\gamma_{P}\left(G\right)\geq 2$, the second term is negative as $k$
approaches infinity. Thus for $s\left(G\right)>\gamma_{P}\left(G\right)\geq
2$, we see that there exists some $k^{\prime}$ such that for every $k\geq
k^{\prime}\geq 1$, the bound from Theorem 3.10 is an improvement over the
upper bound from Proposition 3.3. It will be useful to look specifically at
Theorem 3.10 when $\gamma_{P}\left(G\right)=2$.

######  Corollary 3.11.

If $s\left(G\right)>\gamma_{P}\left(G\right)=2$, then
$\ddot{\gamma}_{P}^{k}\left(G\right)\leq\left\lceil\frac{s\left(G\right)(k+1)}{s\left(G\right)-1}\right\rceil$
for $k\geq 1$.

To illustrate the use of the bounds in this section, we use these results to
determine the $k$-robust power domination number for $K_{3,3}$ and $K_{3,b}$
for sufficiently large $b$ in Section 4.

##  4 Complete bipartite graphs

The _complete bipartite graph_ , $K_{n,m}$ is the graph with vertex set
$V=X\cup Y$ such that $|X|=n$, $|Y|=m$, and edge set $E=\\{xy:x\in X,y\in
Y\\}$. We examine the case when $n=m=3$, then the case when $n=3$ and $m\geq
4$. Next, we find bounds for the $n,m\geq 4$ case, which combine to provide a
result for the general $n=m$ case. We will need the following observation.

######  Observation 4.1.

Suppose the parts of $K_{n,m}$ are $X$ and $Y$, such that $|X|=n$ and $|Y|=m$.
If $S$ is a power dominating set of $K_{n,m}$, then $S$ contains: at least 1
vertex from $X$ and 1 vertex from $Y$; or at least $n-1$ vertices from $X$; or
at least $m-1$ vertices from $Y$.

We will also need the Reverse Pigeonhole Principle. This follows from the the
Pigeonhole Principle, which states that if $k$ objects are distributed among
$n$ sets, then one set must have at least $\left\lceil\frac{k}{n}\right\rceil$
objects.

######  Remark 4.2 (Reverse Pigeonhole Principle).

If $k$ objects are distributed among $n$ sets, then one set must have at most
$\left\lfloor\frac{k}{n}\right\rfloor$ objects.

To see why Remark 4.2 holds, observe that if $n$ sets each had at least
$\left\lfloor\frac{k}{n}\right\rfloor+1$ objects, then, for $k=qn+r$ such that
$q\geq 0$ and $0\leq r\leq n-1$, we would have

$k\geq\sum_{i=1}^{n}\left(\left\lfloor\frac{k}{n}\right\rfloor+1\right)=\sum_{i=1}^{n}\left(q+1\right)=qn+n>k,$

which is a contradiction.

We begin with $\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)$.

######  Theorem 4.3.

Let $k\geq 0$. Let $K_{3,3}$ be the complete bipartite graph with parts
$X=\\{x_{1},x_{2},x_{3}\\}$ and $Y=\\{x_{4},x_{5},x_{6}\\}$. Then

$\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)=k+\left\lfloor\frac{k}{5}\right\rfloor+2.$

###### Proof.

We begin by observing that any two vertices of $K_{3,3}$ form a power
dominating set, and so $s\left(K_{3,3}\right)=6$. First we prove the lower
bound
$k+\left\lfloor\frac{k}{5}\right\rfloor+2\leq\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)$
where $k=5q$. Assume for contradiction that there exists a
$\ddot{\gamma}_{P}^{5q}\text{-set}$ $S$ of size
$5q+\left\lfloor\frac{5q}{5}\right\rfloor+1=6q+1$. By the Pigeonhole
Principle, some $x_{i}$ contains at least
$\left\lceil\frac{6q+1}{6}\right\rceil=q+1$ of the PMUs. Observe that
$|S|-5q=q+1$. Thus, we can remove $5q$ PMUs so that some vertex $x_{i}$
contains all remaining PMUs. This is a contradiction, as
$\gamma_{P}\left(K_{3,3}\right)=2$. Thus,
$\ddot{\gamma}_{P}^{5q}\left(K_{3,3}\right)\geq
6q+2=5q+\left\lfloor\frac{5q}{5}\right\rfloor+2$, as desired. The lower bounds
when $k$ is not a multiple of $5$ then follow by Corollary 3.2.

For the upper bound, observe that by Corollary 3.11,

$\displaystyle\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)$
$\displaystyle\leq\left\lceil\frac{6(k+1)}{5}\right\rceil$
$\displaystyle=k+1+\left\lceil\frac{k+1}{5}\right\rceil.$

Then by Proposition 2.5, we see that

$\displaystyle\ddot{\gamma}_{P}^{k}\left(K_{3,3}\right)$ $\displaystyle\leq
k+1+\left\lfloor\frac{k+1-1}{5}\right\rfloor+1$
$\displaystyle=k+\left\lfloor\frac{k}{5}\right\rfloor+2.\qed$

Theorem 4.3 gives an example of a graph for which Theorem 3.10 is tight and
the structure of the $\ddot{\gamma}_{P}^{k}\text{-set}$ suggested by the proof
of Theorem 3.10 is shown in Figure 2. A larger family of complete bipartite
graphs follows the same pattern, as shown in Theorem 4.4.

$1$$1$$0$$0$$0$$0$ | $1$$1$$1$$0$$0$$0$ | $1$$1$$1$$1$$0$$0$ | $1$$1$$1$$1$$1$$0$
---|---|---|---
$k=0$ | $k=1$ | $k=2$ | $k=3$
$1$$1$$1$$1$$1$$1$ | $2$$2$$2$$2$$0$$0$ | $2$$2$$2$$2$$1$$0$ | $2$$2$$2$$2$$2$$0$
$k=4$ | $k=5$ | $k=6$ | $k=7$
Figure 2: Minimum $k$-rPDS for $K_{3,3}$ for $k=0,1,\ldots,7$.

######  Theorem 4.4.

Let $k\geq 0$. Let $K_{3,m}$ be the complete bipartite graph with parts
$X=\\{x_{1},x_{2},x_{3}\\}$ and $Y=\\{y_{1},y_{2},\ldots,y_{m}\\}$. For
$m\geq\left\lfloor\frac{k}{3}\right\rfloor+3$,

$\ddot{\gamma}_{P}^{k}\left(K_{3,m}\right)=k+\left\lfloor\frac{k}{3}\right\rfloor+2.$

###### Proof.

First we prove the lower bound when $k=3q$. Assume for eventual contradiction
that there exists a $\ddot{\gamma}_{P}^{3q}\text{-set}$, $S$, of size
$3q+\left\lfloor\frac{3q}{3}\right\rfloor+1=4q+1$. Let
$y=\sum_{i=1}^{m}\operatorname{\\#PMU}\left(y_{i}\right)$. Then

$\operatorname{\\#PMU}\left(x_{1}\right)+\operatorname{\\#PMU}\left(x_{2}\right)+\operatorname{\\#PMU}\left(x_{3}\right)+y=4q+1.$

By the Pigeonhole Principle, we see that one of $x_{1},x_{2},x_{3}$ or $y$
must represent at least

$\left\lceil\frac{4m+1}{4}\right\rceil=q+1$

of the PMUs. Observe that $|S|-3q=q+1$. Thus, we can remove $3q$ PMUs such
that either:

  1. 1.

All $q+1$ remaining PMUs are on a single $x_{i}$, which is a contradiction as
this is only one vertex and $\gamma_{P}\left(K_{3,m}\right)=2$; or

  2. 2.

All $q+1$ remaining PMUs are on the $y_{i}$ vertices. In order for the PMUs on
the $y_{i}$’s to form a power dominating set of $K_{3,m}$, $m-1$ of the
$y_{i}$’s must have a PMU. However, we also have that

$\displaystyle m-1$
$\displaystyle\geq\left\lfloor\frac{3q}{3}\right\rfloor+3-1$
$\displaystyle=q+2.$

This means that at least $q+2$ PMUs are needed but after $3q$ PMUs are removed
only $q+1$ PMUs remain, a contradiction.

Therefore, $\ddot{\gamma}_{P}^{3q}\left(K_{3,m}\right)>4q+1$. Hence,
$\ddot{\gamma}_{P}^{3q}\left(K_{3,m}\right)\geq
4q+2=3q+\left\lfloor\frac{3q}{3}\right\rfloor+2$, as desired. The lower bounds
for the remaining cases then follow by Corollary 3.2.

For the upper bound, the case of $k=0$ is given by the power domination
number. If $m=3$ we need only consider when $k=0,1,2$; this is covered by
Theorem 4.3. If $m\geq 4$ and $k\geq 1$, we have $s\left(K_{3,m}\right)=4$.
Then by Corollary 3.11,

$\displaystyle\ddot{\gamma}_{P}^{k}\left(K_{3,m}\right)$
$\displaystyle\leq\left\lceil\frac{4(k+1)}{3}\right\rceil$
$\displaystyle=k+1+\left\lceil\frac{k+1}{3}\right\rceil$

and by Proposition 2.5,

$\displaystyle\ddot{\gamma}_{P}^{k}\left(K_{3,m}\right)$ $\displaystyle\leq
k+1+\left\lfloor\frac{k+1-1}{3}\right\rfloor+1$
$\displaystyle=k+\left\lfloor\frac{k}{3}\right\rfloor+2.\qed$

Next, we examine complete bipartite graphs with at least 4 vertices in each
part, beginning with the lower bound in the following theorem.

######  Theorem 4.5.

Let $m\geq n\geq 4$ and $k\geq 1$. Then,

$\ddot{\gamma}_{P}^{k}\left(K_{n,m}\right)\geq\begin{cases}2(k+1)-4\left\lfloor\frac{k}{n+2}\right\rfloor&k\equiv
i\ (\mathrm{mod}\ n+2),\,\,0\leq i\leq n-4\\\
k+n-1+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor&\text{otherwise}\end{cases}$

###### Proof.

Let $K_{n,m}$ be the complete bipartite graph with $V(K_{n,m})=X\cup Y$,
leaving the sizes of $X$ and $Y$ generic. Let $k=q(n+2)+i$ for $q\geq 0$ and
$0\leq i<n+2.$ Observe the following:

$\displaystyle i$ $\displaystyle=k-q(n+2)$
$\displaystyle=k-\left\lfloor\frac{k}{n+2}\right\rfloor(n+2)$

First suppose that $0\leq i\leq n-4$. For the sake of contradiction, assume
that there exists a $k$-robust power dominating set $S$ such that
$|S|=2k+1-4\left\lfloor\frac{k}{n+2}\right\rfloor$. Thus,

$\displaystyle|S|$
$\displaystyle=2k+1+(n-2-(n+2))\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=k+1+k-(n+2)\left\lfloor\frac{k}{n+2}\right\rfloor+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=k+1+i+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=q(n+2)+i+1+i+q(n-2)$ $\displaystyle=q(n+2)+2i+1+q(n-2)$
$\displaystyle=2qn+2i+1.$

Without loss of generality, assume that
$\operatorname{\\#PMU}\left(X\right)\leq\operatorname{\\#PMU}\left(Y\right)$.
By Observation 4.2,
$\operatorname{\\#PMU}\left(X\right)\leq\left\lfloor\frac{2qn+2i+1}{2}\right\rfloor=qn+i\leq
k$. Observe that if $q=0$, we have equality. Let $B\subseteq S$, such that
$|B|=qn+i$ and $B$ contains all the PMUs from vertices of $X$ (and possibly
some from vertices of $Y$). Then, by definition, $S\setminus B$ contains only
PMUs from vertices of $Y$, and $|S\setminus B|=qn+i+1$. Note that if $q=0$, we
are distributing $i+1\leq n-3$ PMUs amongst the vertices of $Y$, and by
Observation 4.1, $S\setminus B$ is not a power dominating set. By Remark 4.2,
there exists a vertex $y_{1}\in Y$, such that

$\displaystyle\operatorname{\\#PMU}_{S\setminus B}\left(y_{1}\right)$
$\displaystyle\leq\left\lfloor\frac{qn+i+1}{|Y|}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{qn+n-4+1}{n}\right\rfloor$
$\displaystyle=\left\lfloor\frac{qn}{n}+\frac{n-3}{n}\right\rfloor$
$\displaystyle=q+\left\lfloor\frac{n-3}{n}\right\rfloor$ $\displaystyle=q.$

Let $B^{\prime}\subseteq S\setminus B$ such that $|B^{\prime}|=q$ and
$B^{\prime}$ contains all the PMUs from $y_{1}$ (and possibly some from other
vertices of $Y$). Then, by definition, $S\setminus(B\cup B^{\prime})$ contains
PMUs only from vertices of $Y\setminus\\{y_{1}\\}$ and $|S\setminus(B\cup
B^{\prime})|=q(n-1)+i+1$. Thus, by Remark 4.2 there exists a vertex, $y_{2}\in
Y$, such that

$\displaystyle\operatorname{\\#PMU}_{S\setminus(B\cup
B^{\prime})}\left(y_{2}\right)$
$\displaystyle\leq\left\lfloor\frac{q(n-1)+i+1}{|Y|-1}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{q(n-1)+n-4+1}{n-1}\right\rfloor$
$\displaystyle=\left\lfloor\frac{q(n-1)}{n-1}+\frac{n-3}{n-1}\right\rfloor$
$\displaystyle=q+\left\lfloor\frac{n-3}{n}\right\rfloor$ $\displaystyle=q.$

Let $B^{\prime\prime}\subseteq S\setminus(B\cup B^{\prime})$ such that
$|B^{\prime\prime}|=q$ and $B$ contains all the PMUs from $y_{2}$ (and
possibly from other vertices of $Y$). Then, by definition $S\setminus(B\cup
B^{\prime}\cup B^{\prime\prime})$ contains only PMUs from vertices of
$Y\setminus\\{y_{1},y_{2}\\}$. Note that $|B\cup B^{\prime}\cup
B^{\prime\prime}|=k$ and by Observation 4.1, $S\setminus(B\cup B^{\prime}\cup
B^{\prime\prime})$ is not a power dominating set. Therefore, no such $S$ is a
$k-$robust dominating set.

For the second case, suppose that $n-3\leq i\leq n+1$. By Proposition 3.3, to
show that $\ddot{\gamma}_{P}^{k}\left(K_{n,m}\right)\geq
k+n-1+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor$, we need only show it for
$i=n-3$. For the sake of contradiction, suppose there exists a $k$-robust
power dominating set, $S$, such that
$|S|=k+n-2+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor$. Thus,

$\displaystyle|S|$ $\displaystyle=q(n+2)+n-3+n-2+q(n-2)$
$\displaystyle=2qn+2n-5$

Without loss of generality, assume that
$\operatorname{\\#PMU}\left(X\right)\leq\operatorname{\\#PMU}\left(Y\right)$.
By Remark 4.2,

$\displaystyle\operatorname{\\#PMU}\left(X\right)$
$\displaystyle\leq\left\lfloor\frac{2qn+2n-5}{2}\right\rfloor$
$\displaystyle=qn+n-3$ $\displaystyle\leq q(n+2)+n-3$ $\displaystyle=k.$

Observe that if $q=0$, we have equality. Let $B\subseteq S$, such that
$|B|=qn+n-3$ and $B$ contains all the PMUs from $X$ (and possibly some from
$Y$). Then by definition, $S\setminus B$ contains only PMUs from vertices of
$Y$ and $|S\setminus B|=qn+n-2$. Note that if $q=0$, we are distributing $n-2$
PMUs amongst the vertices of $Y$, and by Observation 4.1, $S\setminus B$ is
not a power dominating set. By Remark 4.2, there exists a vertex, $y_{1}\in
Y$, such that

$\displaystyle\operatorname{\\#PMU}_{S\setminus B}\left(y_{1}\right)$
$\displaystyle\leq\left\lfloor\frac{qn+n-1}{|Y|}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{qn+n-1}{n}\right\rfloor$
$\displaystyle\leq q.$

Let $B^{\prime}\subseteq S\setminus B$, such that $|B^{\prime}|=q$ and
$B^{\prime}$ contains all the vertices from $y_{1}$ (and possibly from other
vertices of $Y$). Then, by definition, $S\setminus(B\cup B^{\prime})$ contains
only PMUs from vertices of $Y\setminus\\{y_{1}\\}$ and $|S\setminus(B\cup
B^{\prime})|=q(n-1)+n-2$. Thus, by Remark 4.2, there exists a vertex,
$y_{2}\in Y$, such that,

$\displaystyle\operatorname{\\#PMU}_{S\setminus(B\cup
B^{\prime})}\left(y_{2}\right)$
$\displaystyle\leq\left\lfloor\frac{q(n-1)+n-2}{|Y|-1}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{q(n-1)+n-2}{n-1}\right\rfloor$
$\displaystyle\leq q.$

Let $B^{\prime\prime}\subseteq S\setminus(B\cup B^{\prime})$ such that
$|B^{\prime\prime}|=q$ and $B$ contains all of the PMUs from $y_{2}$ (and
possibly from other vertices of $Y$). Then by definition, $S\setminus(B\cup
B^{\prime}\cup B^{\prime\prime})$ has only PMUs from vertices of
$Y\setminus\\{y_{1},y_{2}\\}$. Note that $|B\cup B^{\prime}\cup
B^{\prime\prime}|=k$ and by Observation 4.1, $S\setminus(B\cup B^{\prime}\cup
B^{\prime\prime})$ is not a power dominating set. Therefore, no such $S$ is a
$k$-robust power dominating set, a contradiction for the second case. ∎

Note that the bound found in Theorem 4.5 is not always tight. For example, we
observe that $\ddot{\gamma}_{P}^{4}\left(K_{4,6}\right)>7$. To see this,
suppose for contradiction that there exists a $k$-robust power dominating set
$S$ such that $|S|=7$. Let the parts of $K_{4,6}$ be $X$ and $Y$ but leave the
sizes of $X$ and $Y$ generic. Then, one side, say $X$, has at most $3$ PMUs.
If $Y$ has $6$ vertices, then removing all PMUs from $X$ leaves $4$ PMUs on
$Y$, and so $S$ is not a $4$-rPDS. Thus, $Y$ has $4$ vertices and $X$ has 6
vertices. We then consider if we remove $4$ PMUs from $Y$. If all of the $3$
remaining PMUs are on $X$, then $S$ is not a $4$-rPDS. Thus, the PMUs must be
some remaining PMUs on $Y$ and some on $X$, and so $X$ has at most $2$ PMUs.
Thus, $Y$ has either $5$, $6$, or $7$ PMUs. In any case, we can remove 2 PMUs
so that there are only $5$ PMUs on $Y$. However, we can still remove 2 PMUs,
which leaves us with at most 2 vertices of $Y$ that contain PMUs and no
vertices of $X$ containing PMUs, which is not a power dominating set of
$K_{4,6}$. Therefore, we see that
$\ddot{\gamma}_{P}^{4}\left(K_{4,6}\right)>7$.

Next, we provide an upper bound for complete bipartite graphs.

######  Theorem 4.6.

Let $m\geq n\geq 4$, and $k\geq 1$

$\ddot{\gamma}_{P}^{k}\left(K_{n,m}\right)\leq\begin{cases}2(k+1)+(m-n-4)\left\lfloor\frac{k}{n+2}\right\rfloor&k\equiv
i\ (\mathrm{mod}\ n+2),\,\,0\leq i\leq n-4\\\
k+m-1+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor&\text{otherwise}\end{cases}$

###### Proof.

Suppose $V(K_{n,m})=X\cup Y$ are the parts of $K_{n,m}$, such that
$X=\\{x_{1},\ldots,x_{n}\\}$ and $Y=\\{y_{1},\ldots,y_{m}\\}$. Let
$k=q(n+2)+i$ for $q\geq 0$ and $0\leq i\leq n+1$. Observe that
$i=k-q(n+2)=k-(n+2)\left\lfloor\frac{k}{n+2}\right\rfloor$.

For the first case, suppose that $0\leq i\leq n-4$. To show that
$\ddot{\gamma}_{P}^{k}\left(K_{n,m}\right)\leq
2(k+1)+(m-n-4)\left\lfloor\frac{k}{n+2}\right\rfloor$, it suffices to
construct a $k$-robust power dominating set of this size. First, we observe
that

$\displaystyle 2(k+1)+(m-n-4)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=k+2+k-(n+2)\left\lfloor\frac{k}{n+2}\right\rfloor+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=k+2+i+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=q(n+2)+i+2+i+q(m-2)$ $\displaystyle=q(n+2)+2i+2+q(m-2)$
$\displaystyle=q(n+m)+2(i+1)$

Let

$S=\\{x^{q+1}_{1},\ldots,x^{q+1}_{i+1},x^{q}_{i+2},\ldots,x^{q}_{n},y^{q+1}_{1},\ldots,y^{q+1}_{i+1},y^{q}_{i+2},\ldots,y^{q}_{m}\\}$

Observe that $|S|=q(n+m)+2(i+1)$. We will now show that $S$ is a $k$-robust
power dominating set. Let $B\subseteq S$ such that $|B|=k=q(n+2)+i$. We have
two cases:

  1. 1.

$S\setminus B$ contains vertices from both $X$ and $Y$. By Observation 4.1,
$S\setminus B$ is a power dominating set.

  2. 2.

$S\setminus B$ contains vertices only from $X$ (or only from $Y$). For
generality, call this side $Z$ with size $z$. Observe that $|S\setminus
B|=q(n+m)+2(i+1)-q(n+2)-i=q(m-2)+i+2$. By Observation 4.1, for $S\setminus B$
to be a robust power dominating set, it must have PMUs on at least $z-1$
vertices. Assume for contradiction that at most $z-2$ vertices of $Z$ have
PMUs, then,

$\displaystyle|S\setminus B|$ $\displaystyle\leq(q+1)(i+1)+q(z-3-i)$
$\displaystyle\leq(q+1)(i+1)+q(m-3-i)$ $\displaystyle=qi+i+q+1+qm-3q-qi$
$\displaystyle=q(m-2)+i+1$ $\displaystyle<|S\setminus B|,$

a contradiction.

Thus $S\setminus B$ is a power dominating set, and since $B$ was arbitrary,
$S$ is a $k$-robust power dominating set for $K_{n,m}$.

For the second case, suppose that $n-3\leq i\leq n+1$. We now show that
$\ddot{\gamma}_{P}^{k}\left(K_{n,m}\right)\leq
k+m-1+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor$ by constructing a
$k$-robust power dominating set of size
$k+m-1+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor$. By Proposition 3.3, we
need only provide the construction for $i=n+1$. Then,

$\displaystyle k+m-1+(m-2)\left\lfloor\frac{k}{n+2}\right\rfloor$
$\displaystyle=q(n+2)+n+1+m-1+q(m-2)$ $\displaystyle=q(n+m)+(n+m)$
$\displaystyle=(q+1)(n+m)$

Let $S=\\{x^{q+1}_{1},\ldots,x^{q+1}_{n},y^{q+1}_{1},\ldots,y^{q+1}_{m}\\}$.
Observe that $|S|=(q+1)(n+m)$. We will now show that $S$ is a $k$-robust power
dominating set. Let $B\subseteq S$ such that $|B|=k=q(n+2)+n+1$. We have two
cases:

  1. 1.

$S\setminus B$ contains vertices from both $X$ and $Y$. By Observation 4.1,
$S\setminus B$ is a power dominating set.

  2. 2.

$S\setminus B$ contains vertices only from $X$ or only from $Y$. For
generality, call this side $Z$ with size $z$. Observe that $|S\setminus
B|=(q+1)(n+m)-q(n+2)-n-1=qm+m-2q-1=q(m-2)+m-1$. By Observation 4.1, for
$S\setminus B$ to be a robust power dominating set, it must have PMUs on at
least $z-1$ vertices. Assume for contradiction that at most $z-2$ vertices of
$Z$ have PMUs, then,

$\displaystyle|S\setminus B|$ $\displaystyle\leq(q+1)(z-2)$
$\displaystyle\leq(q+1)(m-2)$ $\displaystyle\leq qm+m-2q-2$
$\displaystyle<qm+m-2q-1$ $\displaystyle=|S\setminus B|$

a contradiction.

Thus $S\setminus B$ is a power dominating set, and since $B$ was arbitrary,
$S$ is a $k$-robust power dominating set for $K_{n,m}$. Thus $S$ is a
$k$-robust power dominating set for $K_{n,m}$. ∎

We can combine Theorem 4.5 and Theorem 4.6 to find a complete characterization
for balanced complete bipartite graphs, as shown in the following corollary.
Moreover, the proof of Theorem 4.6 yields the construction of $k$-robust power
dominating sets for $K_{n,n}$

######  Corollary 4.7.

Let $n\geq 4$, and $k\geq 1$

$\ddot{\gamma}_{P}^{k}\left(K_{n,n}\right)=\begin{cases}2(k+1)-4\left\lfloor\frac{k}{n+2}\right\rfloor&k\equiv
i\ (\mathrm{mod}\ n+2),\,\,0\leq i\leq n-3\\\
k+n-1+(n-2)\left\lfloor\frac{k}{n+2}\right\rfloor&\text{otherwise.}\end{cases}$

##  5 Trees

In this section, we establish the $k$-robust power domination number for
trees. A _tree_ is an acyclic connected graph. A _spider_ is a tree with at
most one vertex of degree 3 or more. A _spider cover_ of a tree $T$ is a
partition of $V$, say $\\{V_{1},\ldots,V_{\ell}\\}$ such that $G[V_{i}]$ is a
spider for all $i$. The _spider number_ of a tree $T$, denoted by
$\operatorname{sp}\left(T\right)$, is the minimum number of partitions in a
spider cover. A _rooted tree_ is a tree in which one vertex is called the
root. Suppose two vertices $u$ and $v$ are in a rooted tree with root $r$. If
$u$ is on the $r-v$ path, we say that $v$ is a descendant of $u$ an $u$ is an
ancestor of $v$. If $u$ and $v$ are also neighbors, $v$ is a _child_ of $u$
and $v$ is the _parent_ of $u$. The vertex $u$ is an ancestor of $v$ if $v$ is
a descendant of $u$.

######  Theorem 5.1.

[3, Theorem 12] For any tree $T$,
$\gamma_{P}\left(T\right)=\operatorname{sp}\left(T\right)$.

######  Theorem 5.2.

For any tree $T$,
$\ddot{\gamma}_{P}^{k}\left(T\right)=(k+1)\operatorname{sp}\left(T\right)$.

###### Proof.

By Proposition 3.3, we have that
$\ddot{\gamma}_{P}^{k}\left(T\right)\leq(k+1)\gamma_{P}\left(T\right)$ for any
tree $T$, and by Theorem 5.1
$\operatorname{sp}\left(T\right)=\gamma_{P}\left(T\right)$. Therefore,
$\ddot{\gamma}_{P}^{k}\left(T\right)\leq(k+1)\operatorname{sp}\left(T\right)$.

To prove that
$\ddot{\gamma}_{P}^{k}\left(T\right)\geq(k+1)\operatorname{sp}\left(T\right)$,
we proceed by contradiction. That is, assume that
$\ddot{\gamma}_{P}^{k}\left(T\right)<(k+1)\operatorname{sp}\left(T\right)$.
Since $\operatorname{sp}\left(T\right)=\gamma_{P}\left(T\right)$, any
$\ddot{\gamma}_{P}^{k}\text{-set}$ must contain at least
$\operatorname{sp}\left(T\right)$ distinct vertices and by the pigeonhole
principle there exists at least one vertex in the set with at most $k$ PMUs.

Let $S$ be a $\ddot{\gamma}_{P}^{k}\text{-set}$ of $T$ such that
$\operatorname{deg}\left(v\right)\geq 3$ for each $v\in S$, and choose $S$ to
have the smallest number of vertices $x$ with
$\operatorname{\\#PMU}\left(x\right)\leq k$. Root $T$ at a vertex $r\in S$.

Let $A=\\{v\in S:0<\operatorname{\\#PMU}\left(v\right)\leq k\\}$. Let $v\in A$
with the property that $d(v,r)=\max\\{d(u,r):u\in A\\}$. Observe that for any
descendant $u$ of $v$, then $\operatorname{\\#PMU}\left(u\right)\geq k+1$ or
$\operatorname{\\#PMU}\left(u\right)=0$. Let $w$ be the nearest ancestor of
$v$ such that $\operatorname{deg}\left(w\right)\geq 3$. Let
$S^{\prime}=(S\cup\\{w^{\operatorname{\\#PMU}_{S}\left(v\right)}\\})\setminus\\{v^{\operatorname{\\#PMU}_{S}\left(v\right)}\\}$,
so that for each $x\in S^{\prime}$ such that $x\neq w$,
$\operatorname{\\#PMU}_{S^{\prime}}\left(x\right)=\operatorname{\\#PMU}_{S}\left(x\right)$
and
$\operatorname{\\#PMU}_{S^{\prime}}\left(w\right)=\operatorname{\\#PMU}_{S}\left(v\right)+\operatorname{\\#PMU}_{S}\left(w\right)$.
That is, $S^{\prime}$ is the same as $S$ with the exception that the PMUs on
$v$ have been moved to $w$.

We will show that $S^{\prime}$ is a $k-$robust power dominating set. First
observe that since
$S\setminus\\{v^{\operatorname{\\#PMU}_{S}\left(v\right)}\\}$ is a power
dominating set, $S^{\prime}$ is also a power dominating set. Let
$B^{\prime}\subseteq S^{\prime}$, such that $|B^{\prime}|=k$. We have two
cases:
$\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)\leq\operatorname{\\#PMU}_{S}\left(v\right)$,
or
$\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)>\operatorname{\\#PMU}_{S}\left(v\right)$.

First, assume that
$\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)\leq\operatorname{\\#PMU}_{S}\left(v\right)$.
Let

$B=(B^{\prime}\setminus\\{w^{\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)}\\})\cup\\{v^{\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)}\\}.$

Note that $S\setminus B$ removes the same PMUs as $S^{\prime}\setminus
B^{\prime}$ with the exception that the PMUs removed from $w$ in
$S^{\prime}\setminus B^{\prime}$, are instead removed from $v$ in $S\setminus
B$. Since
$\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)\leq\operatorname{\\#PMU}_{S}\left(v\right)$,
we see that $\operatorname{\\#PMU}_{S\setminus B}\left(w\right)=0$.

Now, if $w\notin S^{\prime}\setminus B^{\prime}$, then $S\setminus B$ =
$S^{\prime}\setminus B^{\prime}$. Thus $S^{\prime}\setminus B^{\prime}$ is a
power dominating set. Next consider the case where $w\in S^{\prime}\setminus
B^{\prime}$. The ancestor $w$, which is observed by virtue of being in
$S^{\prime}\setminus B^{\prime}$, will cause the observation of $v$ and $v$
can perform a zero forcing step to observe one descendant. Since
$\operatorname{deg}\left(v\right)\geq 3$, all the descendants of $v$, except
for possibly one, must be observed by forces from descendants of $v$ in
$S^{\prime}\setminus{B^{\prime}}$. To see this, recall that
$S\setminus\\{v^{\operatorname{\\#PMU}_{S}\left(v\right)}\\}$ is a power
dominating set. Since $v$ is not in the power dominating set, $v$ can only
perform the zero forcing step. Since the only path from non-descendants of $v$
to descendants of $v$ is through $v$, all descendants, except for possibly one
descendant, must be observed by descendants of $v$. Since
$\operatorname{\\#PMU}_{S\setminus
B}\left(x\right)=\operatorname{\\#PMU}_{S^{\prime}\setminus
B^{\prime}}\left(x\right)$ whenever $x$ is a descendant of $v$,
$S^{\prime}\setminus{B^{\prime}}$ will force all the descendants of $v$.

Thus, any vertices that rely on $\operatorname{\\#PMU}_{S\setminus
B}\left(v\right)>0$ to be observed in $S\setminus{B}$, will have been observed
by $w$ or the descendants of $v$. The remaining vertices will be observed by
the same vertices as they would have been by $S\setminus{B}$. Therefore,
$S^{\prime}\setminus{B^{\prime}}$ is a power dominating set.

For the second case, assume that
$\operatorname{\\#PMU}_{B^{\prime}}\left(w\right)>\operatorname{\\#PMU}_{S}\left(v\right)$.
Let

$B=(B^{\prime}\setminus\\{w^{\operatorname{\\#PMU}_{S}\left(v\right)}\\})\cup\\{v^{\operatorname{\\#PMU}_{S}\left(v\right)}\\}.$

Note that $S\setminus B$ removes the same PMUs as $S^{\prime}\setminus
B^{\prime}$ with the exception that any PMUs removed from $w$ are first
removed from $v$, and then the remaining are removed from $w$. Thus, $v\notin
S\setminus B$, $S^{\prime}\setminus B^{\prime}=S\setminus B$, and therefore
$S^{\prime}\setminus B^{\prime}$ is a power dominating set.

In either case, $S^{\prime}\setminus B^{\prime}$ is a power dominating set. If
$w\in S$, then we have found $S^{\prime}$ with fewer vertices for which
$\operatorname{\\#PMU}\left(x\right)\leq k$ for $x\in S^{\prime}$, which is a
contradiction. If $w\not\in S$, we may repeat the process. Since $r\in S$, we
know that eventually the process terminates with the same contradiction. ∎

##  6 Concluding remarks

PMU-defect-robust power domination allows us to place multiple PMUs at the
same location and consider the consequences if some of these PMUs fail. There
are many questions left to examine in future work.

Is there an improvement to the lower bound given in Proposition 3.3 for
$\gamma_{P}\left(G\right)>1$? As $K_{3,3}$ demonstrates in Theorem 4.3, it
seems likely that there is a better lower bound based on the number of
vertices and the power domination number that utilizes the pigeonhole
principle to show that the lower bound must increase at certain values of $k$.

We have begun the study of $k$-robust power domination for certain families of
graphs but work remains to be done. We have determined the $k$-robust power
domination number for trees. For complete bipartite graphs, we still have the
case of $\ddot{\gamma}_{P}^{k}\left(K_{3,b}\right)$ for $4\leq
b<\left\lfloor\frac{k}{3}\right\rfloor+3$. The question of
$\ddot{\gamma}_{P}^{k}\left(K_{a,b}\right)$ for unbalanced complete bipartite
graphs when $a,b\geq 4$ is also open and preliminary observations indicate an
extensive case analysis for this problem.

## Acknowledgments

B. Bjorkman was supported by the US Department of Defense’s Science,
Mathematics and Research for Transformation (SMART) Scholarship for Service
Program. E. Conrad was supported by the Autonomy Technology Research (ATR)
Center Summer Program.

## References

  * [1] Dennis J. Brueni and Lenwood S. Heath.  The PMU placement problem.  SIAM Journal on Discrete Mathematics, 19(3):744–761, 2005.
  * [2] Reinhard Diestel.  Graph Theory.  Springer, 2017.
  * [3] Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Michael A. Henning.  Domination in graphs applied to electric power networks.  SIAM Journal on Discrete Mathematics, 15(4):519–529, 2002.
  * [4] Donald Knuth, Ronald Graham, and Oren Patashnik.  Concrete Mathematics: a foundation for computer science, 2nd ed. Addison-Wesley Professional, 1994.
  * [5] Kung-Jui Pai, Jou-Ming Chang, and Yue-Li Wang.  Restricted power domination and fault-tolerant power domination on grids.  Discrete Applied Mathematics, 158(10):1079–1089, 2010.
  * [6] Min Zhao, Liying Kang, and Gerard J. Chang.  Power domination in graphs.  Discrete Mathematics, 306(15):1812–1816, 2006.


# Relevance-guided Neural Machine Translation

Isidora Chara Tourni
Boston University
<EMAIL_ADDRESS>
&Derry Wijaya
Boston University
<EMAIL_ADDRESS>
###### Abstract

With the advent of the Transformer architecture, Neural Machine Translation
(NMT) results have shown great improvement lately. However, results in low-
resource conditions still lag behind in both bilingual and multilingual
setups, due to the limited amount of available monolingual and/or parallel
data; hence, the need for methods addressing data scarcity in an efficient,
and explainable way, is eminent. We propose an explainability-based training
approach for NMT, applied in Unsupervised and Supervised model training, for
translation of three languages of varying resources, French, Gujarati, Kazakh,
to and from English. Our results show our method can be promising,
particularly when training in low-resource conditions, outperforming simple
training baselines; though the improvement is marginal, it sets the ground for
further exploration of the approach and the parameters, and its extension to
other languages.

##  1 Introduction

Unsupervised Neural Machine Translation (UNMT) has seen remarkable progress in
recent years, with a very large number of methods proposed aiming to NMT when
parallel data are few or non-existent for certain language pairs (Artetxe et
al., 2017; Lample et al., 2018; Conneau et al., 2017; Wang and Zhao, 2021;
Lample and Conneau, 2019; Song et al., 2019; Liu et al., 2020; Marchisio et
al., 2020; Kim et al., 2020; Lample et al., 2017; Artetxe et al., 2019; Garcia
et al., 2020; Su et al., 2019; Nguyen et al., 2022). Training techniques such
as Back-Translation (Sennrich et al., 2015) and Auto-Encoding have been widely
studied, in order to efficiently train NMT models under those data scarcity
conditions to obtain high quality translation results. However, there is
little work in enhancing Neural Machine Translation (NMT) models with
utilizing explainability of the model in order to improve quality of the
output. We propose a method, based on Layer-wise Relevance Propagation (LRP),
which leverages the contribution of the input tokens to the output, to boost
NMT performance. Our results show LRP may be beneficial during model training
for NMT output improvement, particularly in low-resource conditions and for
specific well defined model setups.

##  2 Related Work

### Layer-wise Relevance Propagation (LRP)

LRP was introduced by Bach et al. (2015), measuring the contribution of the
input components, or the neurons of a network, to the next layer’s output. Due
to its nature, it is directly applicable to layer-wise architectures, and we
extend its usage to the Transformer architecture, measuring the relevance of
source and target sentences’ tokens to the NMT output during training.

### Explanations & Explanation-guided training

Several previous works outline and summarize the findings of explainability
and interpetability- related research in NLP (Belinkov et al., 2020; Sun et
al., 2021b; Tenney et al., 2020; Madsen et al., 2021; Danilevsky et al., 2020;
Qian et al., 2021). Weber et al. (2022) provide a systematic review of
explainable AI methods employed in improving various properties of Machine
Learning models, such as performance, convergence, robustness, reasoning,
efficiency and equality. Of these, of particular interest, and the focus of
our work, are those that along with measuring feature importance and
distinguishing relevant from irrelevant features, are utilized to augment the
intermediate learned features, and improve model performance or reasoning
(Anders et al., 2022; Sun et al., 2021a; Zunino et al., 2021a; Fukui et al.,
2019; Zhou et al., 2016; Mitsuhara et al., 2019; Schiller et al., 2019; Zunino
et al., 2021b).

In our paper, we modify the approach of Sun et al. (2021a), that proposes a
model-agnostic LRP-guided training method for few shot classification, to
improve model generalization to new classes, extending it to a transformer-
based masked language model for NMT. Every intermediate feature representation
fp is weighted (multiplied) by its relevance R(fp), with respect to the
feature processing output, normalized in [-1,1]. The model is then trained on
a loss function taking into account both predictions, $p$ and $p_{lpr}$ and
given by the following formula

${L^{\prime}=\xi*L(y,p)+\lambda*L(y,p\textsubscript{lrp})}$ (1)

where ${\xi}$, ${\lambda}$ are positive scalars. In this way, the features
more relevant to the prediction are emphasized, while the less relevant ones
are downscaled. Other recent works utilize LRP for improving model performance
in the medical domain (Sefcik and Benesova, 2021), mitigating the influence of
language bias for image captioning models (Sun et al., 2022).

##  3 Method & Experiments

###  3.1 Model & Translation Quality Evaluation

In our experiments we use a 6-layers 8-heads encoder-decoder transformer-based
model, XLM (Lample and Conneau, 2019), following the training configurations
and hyperparameters suggested by the authors. We use Byte Pair Encoding
(Sennrich et al., 2016) to extract a 60k vocabulary, and have an embedding
layer size of 1024, a dropout value and an attention layer dropout value of
0.1, and a sequence length of 256. We measure the quality of the Language
Model (LM) with perplexity, and quality of the NMT output with BLEU (Papineni
et al., 2002), both used as training stopping criteria, when there is no
improvement over 10 epochs. All further parameter values are provided in the
Appendix. We first pre-train a Language Model in each language with the MLM
objective, which is then used to initialize the encoder and decoder of the NMT
model. We further train a NMT model, using backtranslation (BT) and denoising
auto-encoding (AE) with the monolingual data used for LM pretraining for UNMT,
the Machine Translation (MT) objective for the Supervised NMT model, and BT+MT
for the joint Unsupervised and Supervised approach.

###  3.2 Datasets

The languages we work with are English, French, Gujarati, Kazakh, and we’re
translating in all English-centric directions, English–French (En–Fr),
French–English (Fr–En), English–Gujarati (En–Gu), Gujarati–English (Gu–En),
English–Kazakh (En–Kk), Kazakh–English (Kk–En). For English and French, we use
5 million News Crawl 2007-2008 monolingual sentences for each language, and 23
million WMT14 parallel sentences. For Gujarati, we have 1.4 million sentences
and for Kazakh we have 9.5M monolingual sentences, collected for both
languages from Wikipedia, WMT 2018, 2019 and Leipzig Corpora
(2016)111https://wortschatz.unileipzig.de/en/download/. As parallel data, we
have 22k and 132k from the WMT 2019 News Translation
Task222http://data.statmt.org/news-crawl/ for Gu–En and Kk–En.As development
and test sets, we use newstest2013 and newstest2014, respectively, for En–Fr
and Fr–En, WMT19 for En–Gu and Gu–En and En–Kk and Kk–En.

|  |  | En–Fr |  |  |  | Fr–En |  |
---|---|---|---|---|---|---|---|---|---
Parameters’ Set Values |  | v1 | v2 | v3 | Regular | v1 | v2 | v3 | Regular
22k |  |  |  |  |  |  |  |  |
MT |  | 29.9 | 24.67 | 30.24 | 31.12 | 30.12 | 26.79 | 30.52 | 30.63
BT+AE+MT |  | 30.01 | 28.62 | 32.15 | 34.54 | 29.94 | 29.87 | 33.03 | 34.02
1m |  |  |  |  |  |  |  |  |
MT |  | 39.12 | 38.12 | 35.44 | 41.25 | 39.2 | 38.43 | 36.04 | 41.33
BT+AE+MT |  | 37.58 | 37.22 | 36.89 | 40.37 | 37.66 | 37.95 | 37.38 | 40.4
2.5m |  |  |  |  |  |  |  |  |
MT |  | 39.06 | 36.02 | 35.57 | 40.46 | 39.11 | 36.28 | 36.09 | 40.71
BT+AE+MT |  | 37.68 | 36.21 | 37.74 | 39.88 | 40.71 | 37.48 | 36.66 | 38.15
5m |  |  |  |  |  |  |  |  |
MT |  | 39.21 | 37.55 | 39 | 41.52 | 39.33 | 38.01 | 39.2 | 41.18
BT+AE+MT |  | 30.71 | 36.7 | 37.48 | 40.89 | 32.02 | 37.03 | 37.67 | 40.8
_Other methods_ |  |  |  |  | 45.9 |  |  |  | -
Table 1: BLEU scores for Supervised, and Unsupervised + Supervised NMT
Layerwise Relevance Propagation-guided experiments, for En–Fr, Fr–En. _AE_ ,
_BT_ and _MT_ stand for Auto-Encoding loss, Back Translation loss and Machine
Translation loss, respectively. Test and validation sets are from
newstest2013-14 for French. State of the art results (Other methods) for En–Fr
come from http://www.deepl.com/press.html,
http://nlpprogress.com/english/machine_translation.html.

###  3.3 Layer-wise Relevance Propagation (LRP)

We follow the method proposed by Voita et al. (2020) in calculating LRP in an
encoder-decoder Transformer architecture. The Relevance Score is first
propagated inversely through the decoder and then the encoder, up to the input
layer of the architecture. The conservation principle only holds across all
processed tokens, and the score is defined as relevance of the input neurons
to the top-1 logit predicted by the Transformer model, and the sum of the
input neurons’ relevance is regarded as the token contribution. The total
source and target sentence contributions to the result are defined as the
summation of the Relevance of tokens in the source sentence, ${x}$ and that of
those in the target sentence, ${y}$, at generation step t.

$R_{t}(source)=\sum_{i}{x_{i}},\\\ \\\ \hskip
8.53581ptR_{t}(target)=\sum_{j=1}^{t-1}{y_{j}}$ (2)

At every step t, Relevance of the source and target sentences follow the
conservation principle, summing up to 1. Moreover, for every target token past
the currently generated one, Relevance Score is 0.

|  |  | en–gu |  |  |  | gu–en |  |
---|---|---|---|---|---|---|---|---|---
Parameters’ Set Values |  | v1 | v2 | v3 | Regular | v1 | v2 | v3 | Regular
22k |  |  |  |  |  |  |  |  |
MT |  | 2 | 2.18 | 2.19 | 1.04 | 0.69 | 0.7 | 0.73 | 2.65
BT+AE+MT |  | 0.76 | 1.36 | 0.89 | 1.16 | 0.71 | 1.06 | 0.67 | 2.19
_Other methods_ |  |  |  |  | 0.1 |  |  |  | 0.3
Table 2: BLEU scores for Supervised, and Unsupervised + Supervised NMT Layerwise Relevance Propagation-guided experiments, for En–Gu, Gu–En. _AE_ , _BT_ and _MT_ stand for Auto-Encoding loss, Back Translation loss and Machine Translation loss, respectively. Test and validation sets are from WMT19 for Gujarati. State of the art results (Other methods) can be found in https://github.com/google-research/bert/blob/master/multilingual.md.  |  |  | en–kk |  |  |  | kk–en |  |
---|---|---|---|---|---|---|---|---|---
Parameters’ Set Values |  | v1 | v2 | v3 | Regular | v1 | v2 | v3 | Regular
22k |  |  |  |  |  |  |  |  |
MT |  | 2.1 | 3 | 3.2 | 2.4 | 2.2 | 2.1 | 2.7 | 2.6
BT+AE+MT |  | 1.6 | 3 | 2.3 | 2.8 | 2.1 | 2.6 | 2. | 2.9
132k |  |  |  |  |  |  |  |  |
MT |  | 4.8 | 5.6 | 5.3 | 5.2 | 6.8 | 8.5 | 8.4 | 8
BT+AE+MT |  | 5.2 | 6.8 | 6.4 | 6.6 | 8.7 | 9.4 | 9.2 | 8.9
_Other methods_ |  |  |  |  | 2.5333https://www.deepl.com/press.html |  |  |  | 7.4
Table 3: BLEU scores for Supervised, and Unsupervised + Supervised NMT
Layerwise Relevance Propagation-guided experiments, for En–Kk, Kk–En. _AE_ ,
_BT_ and _MT_ stand for Auto-Encoding loss, Back Translation loss and Machine
Translation loss, respectively. Test and validation sets are from WMT19. State
of the art results (Other methods) can be found in https://github.com/google-
research/bert/blob/master/multilingual.md.

###  3.4 LRP-weighted training

Following Sun et al. (2021a), we attempt to utilize LRP contributions during
training, and examine performance. In our case, the representation of every
intermediate source or target token $x_{i}$, with Relevance Score
$R_{t}(x_{i})$, is reweighted by its score at each layer, and included in a
new loss term, $L\textsubscript{ce}(y,x_{i})$. The formula takes the following
form

$L^{\prime}=\xi*L(y,p(x_{i}))+\lambda*L(y,p({R_{t}}(x_{i}))$ (3)

,where $p(x_{i})$ and $p({R_{t}}(x_{i}))$ are the model prediction and the
explanation-guided prediction, respectively. The loss then is the weighted sum
of the previous and the new terms, each weighted by parameters $\xi$,
$\lambda$ respectively, for which we experiment with three sets of values:

$\xi,\lambda=\\{v\textsubscript{1}=\\{1,0.5\\},v\textsubscript{2}=\\{0,1\\},v\textsubscript{3}=\\{1,1\\}\\}.$
(4)

In the first layer we only weigh the word embedding of the token. We
hypothesize that in this way, the tokens with a higher contribution to the NMT
result are enhanced, while the effect of the ones contributing less is
reduced.

##  4 Results & Discussion

In Tables 1, 2, 3, we present our results for LRP-guided training, in certain
low- and high-resource Semi-Supervised and Supervised experiments, for all
languages and directions, providing the regular NMT model results as our
baselines.

We see that for En–Fr and Fr–En NMT, in Table 1, the method fails to
outperform baseline NMT results in all cases. The model translation quality is
usually on par with baselines, and state-of-the art results on high scale
experiments, and small differences in BLEU scores in the range of 0.1-0.5 can
be considered negligible. Among the three hypermarameter settings, choosing v1
for training seems to outperform the other two in the majority of experiments
under a MT-only setting. Results could indicate unsuitability of the method in
high-resource settings; the original method was after all proposed in a few-
shot classification context, hence we also seek more promising results in low-
resource NMT experiments, examined below.

A different model behavior is observed for all cases but one in English to
Gujarati NMT, in Table 2 when either the MT-only or BT-AE-MT objectives are
used in training. This is an interesting finding - we can hypothesize that
LRP-guided training might be more useful when translating into highly complex
morphological languages such as Gujarati; Results marginally outperform
previous state-of-the-art approaches, however more research including other
languages and potentially other parameter values is required to verify that
observation.

Encouraging is also the case of LRP-guided training in En–Kk and Kk–En NMT. In
a large number of settings, training with Relevance guidance improves NMT BLEU
scores significantly compared to our regular models’ results. More
specifically, we see improvement in both low- (22k) and mid-resource (132k)
experiments, with v2-parameterized models to outperform our baselines in the
majority of cases. Also, all experiments we are able to perform better than
the state of the art current result, hence relevance guidance shows potential
again in NMT experiments where few parallel data are available.

##  5 Conclusions

We perform a series of Semi-Supervised and Supervised Neural Machine
Translation experiments, using an explainability-based metric, namely
Relevance-guided propagation, during training; we leverage the measure of
influence of the input and intermediate layer outputs to the NMT result, in an
attempt to improve NMT for three quite different languages, lying in both
high- and low- resource data regimes. Our results, though showing marginal and
very small improvements, indicate that Layerwise-relevance propagation shows
potential in boosting NMT quality when training in small data scenarios.
Further exploration of the method, different model hyperparameter setups, and
expansion of our method to other languages is strongly recommended as a next
step to identify the efficiency and robustness of the proposed method.

##  6 Limitations

Training a large Neural Machine Translation model from scratch is a hard task
computationally, and employing LRP-guidance during training significantly
raises training time, the amount and usage of required computational
resources, and the complexity of the training process, calling for more
efficient training solutions, in terms of memory distribution of the model and
parallelization. These factors constitute the limitations of our approach, and
allowed us to launch a small number of experiments, hence addressing those
factors and expanding to more languages, in more efficient training and
computational ways, is a strong requirement for further generalization of the
method.

##  7 Ethics Statement

Several ethical concerns ought to be addressed when working with large
language models regarding quality, toxicity and bias related to their training
process and output Bender et al. (2021); Chowdhery et al. (2022); Brown et al.
(2020),of which the authors of the paper are aware in their work.

## References

  * Anders et al. (2022) Christopher J Anders, Leander Weber, David Neumann, Wojciech Samek, Klaus-Robert Müller, and Sebastian Lapuschkin. 2022.  Finding and removing clever hans: Using explanation methods to debug and improve deep models.  _Information Fusion_ , 77:261–295.
  * Artetxe et al. (2019) Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2019.  An effective approach to unsupervised machine translation.  _arXiv preprint arXiv:1902.01313_.
  * Artetxe et al. (2017) Mikel Artetxe, Gorka Labaka, Eneko Agirre, and Kyunghyun Cho. 2017.  Unsupervised neural machine translation.  _arXiv preprint arXiv:1710.11041_.
  * Bach et al. (2015) Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek. 2015.  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  _PloS one_ , 10(7):e0130140.
  * Belinkov et al. (2020) Yonatan Belinkov, Sebastian Gehrmann, and Ellie Pavlick. 2020.  Interpretability and analysis in neural NLP.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts_ , pages 1–5, Online. Association for Computational Linguistics.
  * Bender et al. (2021) Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. 2021.  On the dangers of stochastic parrots: Can language models be too big? In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’21, page 610–623, New York, NY, USA. Association for Computing Machinery.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Conneau et al. (2017) Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2017.  Word translation without parallel data.  _arXiv preprint arXiv:1710.04087_.
  * Danilevsky et al. (2020) Marina Danilevsky, Kun Qian, Ranit Aharonov, Yannis Katsis, Ban Kawas, and Prithviraj Sen. 2020.  A survey of the state of explainable ai for natural language processing.  _arXiv preprint arXiv:2010.00711_.
  * Fukui et al. (2019) Hiroshi Fukui, Tsubasa Hirakawa, Takayoshi Yamashita, and Hironobu Fujiyoshi. 2019.  Attention branch network: Learning of attention mechanism for visual explanation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10705–10714.
  * Garcia et al. (2020) Xavier Garcia, Pierre Foret, Thibault Sellam, and Ankur P Parikh. 2020.  A multilingual view of unsupervised machine translation.  _arXiv preprint arXiv:2002.02955_.
  * Kim et al. (2020) Yunsu Kim, Miguel Graça, and Hermann Ney. 2020.  When and why is unsupervised neural machine translation useless? _arXiv preprint arXiv:2004.10581_.
  * Lample and Conneau (2019) Guillaume Lample and Alexis Conneau. 2019.  Cross-lingual language model pretraining.  _arXiv preprint arXiv:1901.07291_.
  * Lample et al. (2017) Guillaume Lample, Alexis Conneau, Ludovic Denoyer, and Marc’Aurelio Ranzato. 2017.  Unsupervised machine translation using monolingual corpora only.  _arXiv preprint arXiv:1711.00043_.
  * Lample et al. (2018) Guillaume Lample, Myle Ott, Alexis Conneau, Ludovic Denoyer, and Marc’Aurelio Ranzato. 2018.  Phrase-based & neural unsupervised machine translation.  _arXiv preprint arXiv:1804.07755_.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Madsen et al. (2021) Andreas Madsen, Siva Reddy, and Sarath Chandar. 2021.  Post-hoc interpretability for neural nlp: A survey.  _arXiv preprint arXiv:2108.04840_.
  * Marchisio et al. (2020) Kelly Marchisio, Kevin Duh, and Philipp Koehn. 2020.  When does unsupervised machine translation work? _arXiv preprint arXiv:2004.05516_.
  * Mitsuhara et al. (2019) Masahiro Mitsuhara, Hiroshi Fukui, Yusuke Sakashita, Takanori Ogata, Tsubasa Hirakawa, Takayoshi Yamashita, and Hironobu Fujiyoshi. 2019.  Embedding human knowledge into deep neural network via attention map.  _arXiv preprint arXiv:1905.03540_.
  * Nguyen et al. (2022) Xuan-Phi Nguyen, Shafiq Joty, Wu Kui, and Ai Ti Aw. 2022.  Refining low-resource unsupervised translation by language disentanglement of multilingual model.  _arXiv preprint arXiv:2205.15544_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Qian et al. (2021) Kun Qian, Marina Danilevsky, Yannis Katsis, Ban Kawas, Erick Oduor, Lucian Popa, and Yunyao Li. 2021.  Xnlp: A living survey for xai research in natural language processing.  In _26th International Conference on Intelligent User Interfaces-Companion_ , pages 78–80.
  * Schiller et al. (2019) Dominik Schiller, Tobias Huber, Florian Lingenfelser, Michael Dietz, Andreas Seiderer, and Elisabeth André. 2019.  Relevance-based feature masking: Improving neural network based whale classification through explainable artificial intelligence.
  * Sefcik and Benesova (2021) Frantisek Sefcik and Wanda Benesova. 2021.  Improving a neural network model by explanation-guided training for glioma classification based on mri data.  _arXiv preprint arXiv:2107.02008_.
  * Sennrich et al. (2015) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015.  Improving neural machine translation models with monolingual data.  _arXiv preprint arXiv:1511.06709_.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Song et al. (2019) Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. 2019.  Mass: Masked sequence to sequence pre-training for language generation.  _arXiv preprint arXiv:1905.02450_.
  * Su et al. (2019) Yuanhang Su, Kai Fan, Nguyen Bach, C-C Jay Kuo, and Fei Huang. 2019.  Unsupervised multi-modal neural machine translation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10482–10491.
  * Sun et al. (2022) Jiamei Sun, Sebastian Lapuschkin, Wojciech Samek, and Alexander Binder. 2022.  Explain and improve: Lrp-inference fine-tuning for image captioning models.  _Information Fusion_ , 77:233–246.
  * Sun et al. (2021a) Jiamei Sun, Sebastian Lapuschkin, Wojciech Samek, Yunqing Zhao, Ngai-Man Cheung, and Alexander Binder. 2021a.  Explanation-guided training for cross-domain few-shot classification.  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , pages 7609–7616. IEEE.
  * Sun et al. (2021b) Xiaofei Sun, Diyi Yang, Xiaoya Li, Tianwei Zhang, Yuxian Meng, Qiu Han, Guoyin Wang, Eduard Hovy, and Jiwei Li. 2021b.  Interpreting deep learning models in natural language processing: A review.  _arXiv preprint arXiv:2110.10470_.
  * Tenney et al. (2020) Ian Tenney, James Wexler, Jasmijn Bastings, Tolga Bolukbasi, Andy Coenen, Sebastian Gehrmann, Ellen Jiang, Mahima Pushkarna, Carey Radebaugh, Emily Reif, et al. 2020.  The language interpretability tool: Extensible, interactive visualizations and analysis for nlp models.  _arXiv preprint arXiv:2008.05122_.
  * Voita et al. (2020) Elena Voita, Rico Sennrich, and Ivan Titov. 2020.  Analyzing the source and target contributions to predictions in neural machine translation.  _arXiv preprint arXiv:2010.10907_.
  * Wang and Zhao (2021) Rui Wang and Hai Zhao. 2021.  Advances and challenges in unsupervised neural machine translation.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Tutorial Abstracts_ , pages 17–21.
  * Weber et al. (2022) Leander Weber, Sebastian Lapuschkin, Alexander Binder, and Wojciech Samek. 2022.  Beyond explaining: Opportunities and challenges of xai-based model improvement.  _arXiv preprint arXiv:2203.08008_.
  * Zhou et al. (2016) Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. 2016.  Learning deep features for discriminative localization.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2921–2929.
  * Zunino et al. (2021a) Andrea Zunino, Sarah Adel Bargal, Pietro Morerio, Jianming Zhang, Stan Sclaroff, and Vittorio Murino. 2021a.  Excitation dropout: Encouraging plasticity in deep neural networks.  _International Journal of Computer Vision_ , 129(4):1139–1152.
  * Zunino et al. (2021b) Andrea Zunino, Sarah Adel Bargal, Riccardo Volpi, Mehrnoosh Sameki, Jianming Zhang, Stan Sclaroff, Vittorio Murino, and Kate Saenko. 2021b.  Explainable deep classification models for domain generalization.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3233–3242.