# Defending against Contagious Attacks on a Network
with Resource Reallocation111Funded by the Science and Technology Development
Fund, Macau SAR (File no. SKLIOTSC-2018-2020), the Start-up Research Grant of
University of Macau (File no. SRG2020-00020-IOTSC). This work was supported in
part by the Science and Technology Development Fund, Macau SAR under File no.
0060/2019/A1, and in part by Research Grant of University of Macau under Grant
MYRG2018-00237-FST.

Rufan Bai1, Haoxing Lin1, Xinyu Yang1, Xiaowei Wu1, Minming Li222City
University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China.
The work described in this paper was partially sponsored by Project 11771365
supported by NSFC.2, Weijia Jia 333BNU-UIC Institute of Artificial
Intelligence and Future Networks, Beijing Normal University (Zhuhai),
Guangdong, China. The work was partially supported by Chinese National
Research Fund (NSFC) Key Project No. 61532013; NSFC grant No. 61872239; and
Guangdong Provincial Key Lab of AI and Multi-modal Data Processing at BNU-HKBU
UIC.3

###### Abstract

In classic network security games, the defender distributes defending
resources to the nodes of the network, and the attacker attacks a node, with
the objective to maximize the damage caused. Existing models assume that the
attack at node $u$ causes damage only at $u$. However, in many real-world
security scenarios, the attack at a node $u$ spreads to the neighbors of $u$
and can cause damage at multiple nodes, e.g., for the outbreak of a virus. In
this paper, we consider the network defending problem against contagious
attacks.

Existing works that study shared resources assume that the resource allocated
to a node can be shared or duplicated between neighboring nodes. However, in
real world, sharing resource naturally leads to a decrease in defending power
of the source node, especially when defending against contagious attacks. To
this end, we study the model in which resources allocated to a node can only
be transferred to its neighboring nodes, which we refer to as a reallocation
process.

We show that this more general model is difficult in two aspects: (1) even for
a fixed allocation of resources, we show that computing the optimal
reallocation is -hard; (2) for the case when reallocation is not allowed, we
show that computing the optimal allocation (against contagious attack) is also
-hard. For positive results, we give a mixed integer linear program
formulation for the problem and a bi-criteria approximation algorithm. Our
experimental results demonstrate that the allocation and reallocation
strategies our algorithm computes perform well in terms of minimizing the
damage due to contagious attacks.

##  1 Introduction

In recent years, security games have attracted much research attention within
the artificial intelligence community and have been widely adopted for the
computation of optimal allocation of security resources in many areas of the
field [18, 26, 30, 25]. A considerable portion of these works consider the
security games played within a network structure, i.e., the network security
games [3, 11, 31, 23]. In a network security game, there is an underlying
graph, where each node of the graph represents a target with a defending
requirement and a value to protect. The game is played between a defender who
allocates defensive resources to the nodes of the graph and an attacker who
picks a node to attack, depending on how the nodes are defended.

Many existing works consider the setting when the allocated resource can be
shared between neighboring nodes [29]. For example, Gan et al. [10] considered
a network security game in which allocating one unit of resource to some
target protects not only the target but also the neighboring targets. Li et
al. [19] studied the model in which the defending power of each node $u$ is
determined by the resource $r_{u}$ allocated to $u$, plus a linear function of
the resources allocated to its neighbors. These models are mainly motivated by
surveillance or patrolling applications, in which when a node $u$ shares
resource with its neighbor, we do not need to worry about the defending power
of $u$.

However, for defending problems in which the attack is contagious, it is
necessary to take into account the decrease in the defending power of node
$u$, especially when $u$ is at the risk of being involved in the attack.
Consider a contagious attack, e.g., the spread of a virus, on a node $v$.
Suppose the attack spreads to the neighbors of $v$ and can cause damage at
each of the nodes the attack spreads to, depending on how well the node is
defended. In this case, if we measure the defending power of $v$ by taking
into account the resources shared from its neighbor $u$, then naturally, we
need to consider the decrease in the defending power of $u$.

Ideally, a node $u$ can only _transfer_ (a fraction of) the resource it owns
to its neighbor $v$, which increases the defending power of the receiver $v$
but decreases its own defending power. When defending against attacks without
spreading effects, this assumption is equivalent to being able to duplicate
resources between neighbor nodes, as we can always transfer the maximum
possible resources towards the node under attack. However, when the attack can
spread to neighbors of the node under attack, this assumption demands a
stronger defending requirement. Specifically, the following example shows that
when resources can only be transferred (instead of being duplicated), the
total resource required to obtain a good defending result can be much larger.

###### Example 1.1

Consider a star graph, with node $u$ in the center, and
$v_{1},v_{2},\ldots,v_{n-1}$ being neighbors of $u$. Suppose each node
requires $1$ unit of resource to defend himself. Suppose node $u$ is attacked
and the attack spreads to all neighbors of $u$. When resources can be
duplicated, allocating one unit of resource at node $u$ guarantees that every
node is sufficiently defended, and thus no loss is incurred. However, when
resources can only be transferred, as long as the total resources allocated
are less than $n$ units, there always exists at least one insufficiently
defended node.

In the paper, we consider the problem of defending against contagious attack,
in which the defending resources can only be transferred between neighboring
nodes. Specifically, when the attacker attacks a node $u$ in the network, the
attack spreads to neighbors of $u$ and may cause damage at multiple nodes. The
defender decides an allocation strategy of defending resources to nodes in the
graph before the attack happens, and is allowed to transfer some resources
between neighboring nodes (subject to some capacity constraints) when the
attack happens. Our model is motivated by real-world applications like
defending against virus spreading. In these applications, it is reasonable to
assume that we can transfer medical resources or doctors between neighboring
cities or countries in order to minimize the damage when the virus breaks out.
Unfortunately, existing models fail to capture such applications as most of
them do not consider the reallocation of defending resources.

###  1.1 Our Results

We study the problem of computing optimal allocations and reallocations of
defending resources. Since our main motivation of the problem is defending
against virus spreading and, in real world, the allocation of defending
resources is usually public information, we focus only on pure strategies,
i.e., deterministic defending algorithms. We propose a mathematical model that
generalizes that of [10, 19], and assume that (1) an attack spreads to a
subset of nodes and may cause damage at each of them; (2) defending resources
can be transferred between neighboring nodes, which we refer to as a
reallocation of resources. The objective is to minimize the maximum possible
damage due to an attack.

We show that this general model is difficult in two aspects. We first show
that even with a given allocation of resources and a node that is attacked,
computing the optimal reallocation is -hard (Section 3). Then we show that if
no reallocation is allowed, the problem of computing the optimal allocation
strategy is also -hard (Section 4.1).

Regarding positive results, we provide mixed integer linear programs (MILPs)
to model the computation of allocation and reallocation strategies (in Section
4.2). We show that the optimal solutions for the MILPs provide optimal
allocation and reallocation strategies. Since solving an MILP is not
guaranteed to terminate in polynomial time, we also propose polynomial time
algorithms for special cases and approximation algorithms. We give a
polynomial time algorithm that decides whether there exists a defending
strategy in which no loss incurs, and outputs one if it exists (Section 4.3).
Then we give a polynomial time bi-criteria
$(\frac{1}{1-\epsilon},\frac{1}{\epsilon})$-approximation algorithm, for any
$\epsilon\in(0,1)$ (see Section 4.4 for a formal definition of bi-criteria
approximations). Specifically, for $\epsilon=0.5$ we have a bi-criteria
$(2,2)$-approximation. Moreover, we show that under the Unique Game Conjecture
[16], there does not exist $(2-\delta,2-\delta)$-approximation, for any
constant $\delta>0$.

Finally, we extensively evaluate our algorithms on synthetic and real-world
datasets in Section 5.

###  1.2 Other Related Work

As mentioned, there is a sequence of existing works in the network security
game domain that consider resource sharing between nodes. Gan et al. [10, 11]
consider models in which allocating a unit of defending resource to a node can
also protect the neighbors of that node. Their models only study the binary
version of resource allocation, i.e., $r_{u}\in\\{0,1\\}$. Yin et al. [29]
also study a model in which the resource can be shared, and they assume
sharing resources takes time. However, these existing models does not consider
the contagious attacks or the resource reallocation.

There are also works that study the contagion in network security games [22,
4, 28, 1, 20, 12, 2]. Besides, Tsai et al. [27] study a zero-sum two-player
influence blocking maximization game, in which the attacker and the defender
try to maximize their influence on a network. However, these works do not
model the problem in terms of allocating defending resources to meet defending
requirements and minimizing the loss due to attack, and thus are incomparable
to our model. There are other works that study contagion of attack by assuming
that an insufficiently protected node can affect the defending result of its
neighboring nodes [8, 19]. There are also works that study game-theoretic
models of the security games [17, 15, 7].

##  2 Model Description

We model the network as an undirected444While we assume the graph is
undirected, it can be verified that all our results extend straightforwardly
to directed graphs. connected graph $G(V,E)$, where each node $u\in V$ has a
_threshold_ $\theta_{u}$ that represents the defending requirement, and a
_value_ $\alpha_{u}$ that represents the possible damage due to an attack at
node $u$. We use $N(u):=\\{v:(u,v)\in E\\}$ to denote the set of neighbors for
node $u\in V$. We use $N_{k}(u)$ to denote the set of nodes at distance at
most $k$ from $u\in V$. By definition we have $N_{1}(u)=\\{u\\}\cup N(u)$. We
use $n$ and $m$ to denote the number of nodes and edges in the graph $G$,
respectively.

###  2.1 Defending Resource and Defending Power

The defender has a total resource of $R$ that can be distributed to nodes in
$V$, where $r_{u}$ is the _defending resource_ 555Similar to [19], we assume
the resource can be allocated continuously in our model. allocated to node
$u$, and $\sum_{u\in V}r_{u}=R$. Each node $u$ can transfer at most
$w_{uv}\cdot r_{u}$ units of defending resource to each of its neighbor $v$,
where $w_{uv}\in[0,1]$ is the _weight_ of edge $(u,v)$, which represents the
efficiency (or willingness) when transferring defending resource between $u$
and $v$.

######  Definition 2.1 (Allocation Strategy)

We use $r_{u}\geq 0$ to denote the resource allocated to node $u$. We use
$\mathbf{r}=\\{r_{u}\\}_{u\in V}$ to denote an _allocation strategy_.

######  Definition 2.2 (Reallocation Strategy)

We use $t(u,v)\geq 0$ to denote the resource $u$ transfers to its neighbor
$v$. In general $v$ can also send resource to node $u$ (which is denoted by
$t(v,u)\geq 0$). We use $\mathbf{t}=\\{t(u,v),t(v,u)\\}_{(u,v)\in E}$ to
denote a _reallocation strategy_.

The fractions of resource transferred between $u$ and $v$ are upper bounded by
the edge weight as follows:

$t(u,v)\leq w_{uv}\cdot r_{u},\qquad t(v,u)\leq w_{uv}\cdot r_{v}.$

That is, each node $u$ can transfer at most $w_{uv}$ fraction of the resource
$r_{u}$ to its neighbor $v$. Additionally, we need to guarantee that the total
resources node $u$ sends out is at most the total resource it owns:

$\textstyle\sum_{v\in N(u)}t(u,v)\leq r_{u}.$

Since the resources can be sent and received, the defending power of a node is
not fixed. Instead, depending on the attack, the defending power at each node
can be adaptive by deciding an appropriate reallocation strategy.

######  Definition 2.3 (Defending Power)

The defending power of node $u$ is defined as the total resource node $u$ owns
after the reallocation, which is given as follows:

$p_{u}=r_{u}-\sum_{v\in N(u)}t(u,v)+\sum_{v\in N(u)}t(v,u).$

We use $\mathbf{p}=\\{p_{u}\\}_{u\in V}$ to denote defending powers of nodes.

Depending on the reallocation, the defending power $p_{u}$ of node $u$ can
take values in range $[\bar{p}_{u},\hat{p}_{u}]$, where

$\displaystyle\bar{p}_{u}$ $\displaystyle=\max\\{\textstyle 1-\sum_{v\in
N(u)}w_{uv},0\\}\cdot r_{u},$ $\displaystyle\hat{p}_{u}$
$\displaystyle=r_{u}+\textstyle\sum_{v\in N(u)}w_{uv}\cdot r_{v}.$

Note that the allocation strategy $\mathbf{r}$ (which allocates the defending
resources) must be decided before the attack happens. In contrast, the
defender can decide the reallocation strategy depending on which node is
attacked. Specifically, the defender can define $n$ reallocation strategies
$\\{\mathbf{t}^{u}\\}_{u\in V}$, one for each node when it is attacked.

Put differently, there are four sequential steps:

  * (1)

the algorithm decides an allocation strategy $\mathbf{r}$, which allocates a
total of $R$ resources;

  * (2)

the attacker picks a node $u$ to attack;

  * (3)

the algorithm decides a reallocation strategy $\mathbf{t}^{u}$ to minimize the
loss due to the attack. Note that at this point, the allocation strategy is
fixed, but the defending power depends on the reallocation strategy.

  * (4)

the loss due to the attack is evaluated.

######  Definition 2.4 (Defending Strategy)

We refer to a solution for the defending problem as a _defending strategy_
$(\mathbf{r},\\{\mathbf{t}^{u}\\}_{u\in V})$, which consists of an allocation
strategy $\mathbf{r}$ and $n$ reallocation strategies
$\\{\mathbf{t}^{u}\\}_{u\in V}$.

###  2.2 Loss Due to An Attack

Next, we define the loss due to an attack. Let $\mathbf{p}=\\{p_{u}\\}_{u\in
V}$ be the defending powers of nodes. Suppose $u$ is attacked, the attack
spreads to all nodes in $N_{k}(u)$, where $k$ is a parameter that represents
the level of contagiousness of the attack. The loss due to the attack is the
total damage caused at nodes in $N_{k}(u)$, where each node $v\in N_{k}(u)$
suffers from a damage of $\alpha_{v}$ if $p_{v}<\theta_{v}$. If
$p_{v}\geq\theta_{v}$, then no damage is caused at $v$.

######  Definition 2.5 (Defending Result)

Given defending strategy $(\mathbf{r},\\{\mathbf{t}^{u}\\}_{u\in V})$, let
$\textsf{Loss}(u)$ be the total damage when $u$ is attacked and the
reallocation strategy $\mathbf{t}^{u}$ is deployed. The defending result is
defined as the maximum loss due to an attack, i.e., $\max_{u\in
V}\textsf{Loss}(u)$.

The objective of the problem is to compute a defending strategy with the
minimum defending result. We use $\mathsf{OPT}$ to denote the optimal
(minimum) defending result. In the remaining part of the paper, we use DCA
(Defending against Contagious Attack) to refer to the problem of computing the
defending strategy against contagious attack. Note that the decision problem
of verifying whether a defending strategy has result at most some value is in
. Given the defending strategy, the verification can be done by computing
$\textsf{Loss}(u)$ for every node $u$ and taking the maximum, both of which
take polynomial time.

##### Remark.

When $k=0$, there is no spreading effect and we only need to protect the node
under attack by borrowing defending resources from its neighbors. Hence in
this case we have $p_{u}=\hat{p}_{u}$ if node $u$ is attacked. Consequently,
the problem degenerates to the single-threshold model of [19], which can be
solved in polynomial time. However, in general (when $k\geq 1$), when the
attack spreads to multiple nodes, the reallocation must be carefully designed
so as to protect multiple nodes, because when a node transfers resource to its
neighbors, its own defending power decreases.

##  3 Optimal Response to an Attack

As a warm-up towards further analysis, in this section, we first focus on the
subproblem of computing optimal reallocations. That is, given a fixed
allocation strategy $\mathbf{r}=\\{r_{u}\\}_{u\in V}$ and suppose node $u$ is
under attack, we compute the reallocation strategy $\mathbf{t}^{u}$ with which
$\textsf{Loss}(u)$ is minimized. The following example shows how an
appropriate reallocation of resources helps reduce the damage due to an
attack.

###### Example 3.1

Consider the graph given in Figure 1(a), and node $a$ is under attack.
Assuming $k=1$, the attack spreads to $N_{1}(a)=\\{a,b,d,e\\}$. Suppose (1)
all edges have weight $0.5$; (2) $\theta_{a}=4,\theta_{b}=\theta_{d}=2$ and
$\theta_{e}=3$; and (3) all nodes have defending resource $2$. Obviously,
without any reallocation, we suffer from a total loss of
$\alpha_{a}+\alpha_{e}$ since only nodes $b$ and $d$ are sufficiently
defended. However, if we reallocate the resources as shown in Figure 1(b),
then all nodes in $N_{1}(a)$ are well defended, and no loss incurs.

Figure 1: Example of a reallocation strategy, where a directed edge indicates
a transfer of resource. For example, the edge from $b$ to $a$ with value $1$
indicates that node $b$ transfers $t(b,a)=1$ unit of resource to node $a$.

However, in general, we cannot guarantee that there always exists a
reallocation strategy under which all nodes under attack are well defended. In
this case, we need to compute a reallocation strategy to minimize the total
loss. For example, we can choose to protect nodes $u$ with larger value
$\alpha_{u}$ while leaving some nodes $v$ with smaller $\alpha_{v}$
insufficiently defended. Unfortunately, we show that the problem of computing
the optimal reallocation strategy is -hard. For space reasons, we move the
proof of the following hardness result to the full version of the paper.

###### Theorem 3.1

Unless ¶=, there does not exist any polynomial time algorithm that, given an
allocation strategy and a node under attack, computes the optimal reallocation
strategy, for any $k\geq 1$.

Next, we formulate the problem of computing the optimal reallocation strategy
as a Mixed Integer Linear Program (MILP). Recall that we are given an
allocation strategy $\mathbf{r}$ and a node $u$ that is attacked.

$\displaystyle\text{minimize}\quad\textstyle\sum_{v\in
N_{k}(u)}(1-x_{v})\cdot\alpha_{v}$ $\displaystyle\text{subject to
}\quad\textstyle r_{v}-\sum_{z\in N(v)}t(v,z)+$
$\displaystyle\textstyle\sum_{z\in N(v)}t(z,v)$
$\displaystyle\geq\theta_{v}\cdot x_{v},$ $\displaystyle\quad\forall v\in
N_{k}(u)$ (1) $\displaystyle 0\leq t(v,z)\leq w_{vz}\cdot r_{v},$
$\displaystyle\quad\forall z,v\in V$ (2) $\displaystyle\textstyle\sum_{z\in
N(v)}t(v,z)\leq r_{v},$ $\displaystyle\quad\forall v\in V$ (3) $\displaystyle
x_{v}\in\\{0,1\\},$ $\displaystyle\quad\forall v\in N_{k}(u).$

For each node $v\in N_{k}(u)$ we introduce an integer variable
$x_{v}\in\\{0,1\\}$ that indicates whether $p_{v}\geq\theta_{v}$. We introduce
fractional variables $t(v,z),t(z,v)$ for each $(v,z)\in E$. The objective of
the MILP is the total loss due to the attack, which is the sum of values
$\alpha_{v}$ for $v\in N_{k}(u)$ that is not well defended ($x_{v}=0$).
Constraints (1) guarantee that if we set $x_{v}=1$, then $v$ should be well
defended, i.e., $p_{v}\geq\theta_{v}$. Constraints (2) and (3) ensure that the
transfers of resource between neighboring nodes are feasible.

Note that $\\{r_{v}\\}_{v\in V}$ are given and are not variables.

The optimal solution $(\mathbf{x},\mathbf{t})$ for the MILP gives an optimal
reallocation $\mathbf{t}$ that minimizes $\textsf{Loss}(u)$, with the fixed
allocation $\mathbf{r}$ and node $u$ that is attacked.

##### Remark.

There are redundant variables that can be removed from the MILP. Recall that
$N_{k}(u)$ are the nodes the attack spreads to. For each $v\in V\setminus
N_{k}(u)$, we have no defending requirements and thus do not need to transfer
any resources towards these nodes. Consequently, it is unnecessary to
introduce variable $t(z,v)$, for any $z\in N(v)$. In other words, we only
introduce the variable $t(z,v)$ if $v\in N_{k}(u)$. With this observation, we
can reduce the total number of fractional variables from $|E|$ to $\sum_{v\in
N_{k}(u)}|N(v)|$, which is much smaller when $k$ is small and the graph is
sparse.

Note that the MILP can not be solved exactly in time polynomial in
$|N_{k}(u)|$. A natural idea is to relax the integer variables $\mathbf{x}$ to
take values in $[0,1]$. However, the following instance shows that the
integrality gap between the MILP and its LP relaxation is unbounded.

######  Example 3.2 (Integrality Gap)

Consider the trivial graph with only one node $u$, where
$\theta_{u}=\alpha_{u}=1$. Suppose $R=r_{u}=1-\epsilon$, where $\epsilon>0$ is
arbitrarily small. Obviously we have $\textsf{Loss}(u)=1$. However, the
optimal objective of the LP relaxation is $\epsilon$, by setting
$x_{u}=1-\epsilon$.

##### Observations.

While the integrality gap of MILP and its LP relaxation is unbounded, we still
have two useful observations. First, the optimal objective of the LP
relaxation provides a lower bound on the optimal objective of the MILP, which
will be utilized to do a pruning on the MILP in later sections. Second, for a
fixed $\\{0,1\\}$-vector $\mathbf{x}\in\\{0,1\\}^{N_{k}(u)}$, the MILP becomes
a feasibility LP, which can be solved efficiently. For example, we use this
idea to compute defending strategies with defending result $0$ in Section 4.3.
We also extend this idea in Section 4.4 to compute a polynomial time bi-
criteria approximation. The idea is to find a vector
$\mathbf{x}\in\\{0,1\\}^{N_{k}(u)}$ for which the induced LP is feasible, and
the objective $\sum_{v\in V}(1-x_{v})\cdot\alpha_{v}$ is as small as possible.

##  4 Computing the Defending Strategy

In this section, we consider the computation of defending strategies and
extend the observations and ideas from the previous section. Recall that the
defending result is $\max_{u\in V}\textsf{Loss}(u)$, and is uniquely
determined by the defending strategy $(\mathbf{r},\\{\mathbf{t}^{u}\\}_{u\in
V})$. We have shown in Theorem 3.1 that given a fixed allocation strategy and
a node under attack, computing the optimal reallocation strategy is -hard.
However, the hardness result does not necessarily imply a hardness result for
computing the allocation strategy. In the following, we show that computing
the allocation strategy is indeed -hard.

###  4.1 Hardness

We first define a simple special case of the DCA problem called _isolated
model_ , and then show that even for this special case, the problem is -hard.

######  Definition 4.1 (Isolated Model)

We refer to the DCA problem where $w_{uv}=0$ for all $(u,v)\in E$ as the
_isolated model_.

Note that in the isolated model, the defending strategy consists of only an
allocation strategy since no reallocation is allowed. When $k=0$, the special
case can be solved trivially by greedily allocating resources to the nodes
with maximum value, because the defending result is defined by the not-well-
defended node with maximum value.

However, in contrast to the case when $k=0$, we show that when $k\geq 1$, the
problem becomes -hard.

###### Theorem 4.1

Computing the optimal defending strategy is -hard for $k\geq 1$, even for the
isolated model with identical thresholds.

  * Proof:

We prove by a reduction from the (unweighted) vertex cover (VC) problem, which
is known to be -hard [9]. Given an instance $G_{vc}=(V_{vc},E_{vc})$, the VC
problem is to select a minimum size subset $S\subseteq V_{vc}$ such that each
edge $(u,v)\in E_{vc}$ has at least one endpoint in $S$. We construct an
instance $G=(V,E)$ of the DCA problem in which $w_{uv}=0$ for all edges
$(u,v)\in E$ and $\theta_{u}=1$ for all nodes $u\in V$ as follows.

Let the instance $G$ of the DCA problem be obtained by inserting a node for
every edge $(u,v)\in E_{vc}$, splitting the edge. Specifically, we first
initialize $G=G_{vc}$. Then for each $e=(u,v)\in E_{vc}$, we remove $e$,
insert a new node $u_{e}$ and two edges $(u,u_{e}),(u_{e},v)$ into $E$. We
refer to these nodes (that split edges) the _splitting nodes_ , and the other
nodes as _original nodes_. Note that each splitting node has exactly two
neighbors, both of which are original nodes. The neighbors of each original
node are all splitting nodes. Note that we have $|V|=|V_{vc}|+|E_{vc}|$ and
$|E|=2|E_{vc}|$. Set $\alpha_{u}=0$ for splitting nodes, and $\alpha_{u}=1$
for original nodes. In other words, only the original nodes are valuable and
worth defending. Let $\theta_{u}=1$ for all $u\in V$ and $k=1$.

Observe that since resource cannot be transferred, the optimal allocation
strategy assigns resource either $0$ or $1$ to each original node, and $0$ to
each splitting node. We call a node $u$ _defended_ if $r_{u}=1$, _undefended_
otherwise. Since $k=1$, when the attacker chooses to attack an original node
$u$, the total loss is $0$ if $u$ is defended, $1$ otherwise. However, if the
attacker attacks a splitting node, the total loss is the number of undefended
neighbors of the splitting nodes, which can be $2$.

Suppose there exists an allocation strategy using total resource $R$ for which
the defending result is at most $1$, then there must exist a vertex cover of
size at most $R$ for $G_{vc}$. Specifically, the defended original nodes form
a vertex cover for $G_{vc}$ (otherwise, there exists a splitting node whose
two neighbors are both undefended). Hence if there exists a polynomial time
algorithm for the DCA problem, then we can use binary search on
$R\in\\{1,2,\ldots,|V_{vc}|-1\\}$ to identify the minimum $R$ with which the
defending result is $1$. Consequently, we can compute a minimum vertex cover
in polynomial time, which is a contradiction. $\Box$

Interestingly, we show that the reduction also implies a hardness of
approximation.

###### Corollary 4.1

For any $c<2$, computing a $c$-approximation defending strategy when $k\geq 1$
is -hard, even for the isolated model with identical thresholds.

  * Proof:

Observe that in the above reduction, for any $R<|V_{vc}|$, the defending
result is either $1$ or $2$. Let $\mathsf{OPT}$ be the optimal defending
result and $\mathsf{ALG}$ be that of the $c$-approximation algorithm, where
$c<2$. Note that both $\mathsf{OPT}$ and $\mathsf{ALG}$ take values in
$\\{1,2\\}$. Observe that for $\mathsf{OPT}=1$, we must have $\mathsf{ALG}=1$
since otherwise the approximation ratio is $2$. Similarly, for
$\mathsf{OPT}=2$, we have $\mathsf{ALG}=2$. Hence any better-than-$2$
approximation algorithm is equivalent to an exact algorithm, and the corollary
follows from Theorem 4.1. $\Box$

###  4.2 MILP Formulation

Nevertheless, we show that we can formulate the computation of the optimal
defending strategy as an MILP as we have done in Section 3. Similar as before,
we introduce a set of variables for the case when $u$ is under attack: we
introduce an integer variable $x^{u}_{v}\in\\{0,1\\}$ for each $v\in
N_{k}(u)$, which indicates whether $p_{v}\geq\theta_{v}$ when $u$ is under
attack; we also introduce a variable $t^{u}(z,v)$ for each $v\in N_{k}(u)$ and
$z\in N(v)$, which represents the resource $z$ sends to $v$.

Unlike before, where the allocation strategy is given, here we introduce a
variable $r_{u}$ to denote the resource allocated to node $u\in V$. We also
changed the objective from minimizing $\textsf{Loss}(u)$ to minimizing
$\max_{u\in V}\textsf{Loss}(u)$, by introducing a variable Loss that is at
least $\textsf{Loss}(u)=\sum_{v\in N_{k}(u)}(1-x^{u}_{v})\alpha_{v}$ for all
$u\in V$. The computation of the defending strategy is then formulated as
follows.

minimize Loss $\displaystyle\text{subject to}\quad\textstyle\sum_{u\in
V}r_{u}\leq R,\quad$ $\displaystyle\textstyle r_{v}-\sum_{z\in N(v)\cap
N_{k}(u)}t^{u}(v,z)+$ $\displaystyle\textstyle\sum_{z\in N(v)}t^{u}(z,v)$
$\displaystyle\geq\theta_{v}\cdot x^{u}_{v},\quad$ $\displaystyle\forall u,v$
(4) $\displaystyle 0\leq t^{u}(v,z)\leq w_{vz}\cdot r_{v},\quad$
$\displaystyle\forall u,v,z$ (5) $\displaystyle\textstyle\sum_{z\in N(v)\cap
N_{k}(u)}t^{u}(v,z)\leq r_{v},\quad$ $\displaystyle\forall u,v,z$ (6)
$\displaystyle\textstyle\sum_{v\in
N_{k}(u)}(1-x^{u}_{v})\alpha_{v}\leq\textsf{Loss},\quad$ $\displaystyle\forall
u$ (7) $\displaystyle x^{u}_{v}\in\\{0,1\\},\quad$ $\displaystyle\forall u,v.$

Similar as before, the set of constraints (4) guarantees that the defending
power of a node $v$ is at least $\theta_{v}$ when $x^{u}_{v}=1$. Constraints
(5) and (6) guarantee feasibility of transfers of resource. Constraints (7)
ensure $\textsf{Loss}=\max_{u\in V}\textsf{Loss}(u)$ in the optimal solution.
As before, we only need to introduce variable $t^{u}(z,v)$ if $v\in N_{k}(u)$
and $z\in N(v)$. We use MILP$(R)$ to denote the above program that uses total
resource $R$. Note that in the program $r_{u}$’s and $t^{u}(z,v)$’s are
fractional variables while $x^{u}_{v}$’s are integer variables. We denote by
LP$(R)$ the linear program relaxation when we replace each constraint
$x^{u}_{v}\in\\{0,1\\}$ with $x^{u}_{v}\in[0,1]$. As Example 3.2 shows, the
integrality gap of LP$(R)$ and MILP$(R)$ is unbounded. Nevertheless, LP$(R)$
provides a lower bound for MILP$(R)$, which can be used for a pruning on MILP.

##### Prunings.

Suppose we have a lower bound $l$ of the optimal defending result
$\mathsf{OPT}$, i.e., the optimal objective of MILP$(R)$. Then for every node
$u$ with $\sum_{v\in N_{k}(u)}\alpha_{v}\leq l$, we can remove all variables
with superscript $u$ and all constraints containing such variables. The reason
is, when $u$ is attacked, the maximum loss (even if we do not allocate or
reallocation any resource) is at most $\sum_{v\in N_{k}(u)}\alpha_{v}$. Given
$\mathsf{OPT}\geq l$, not defending nodes in $N_{k}(u)$ does not increase the
objective of MILP$(R)$. Note that the optimal solution of LP$(R)$ gives one
such lower bound $l$. The closer the optimal objectives of LP$(R)$ and
MILP$(R)$ are, the better the pruning reduces the size of MILP$(R)$. We can
further reduce the number of constraints by exploiting the dominance between
them. For example, if for a node $v$ we have $\sum_{z\in N(v)}w_{vz}\leq 1$
then Constraint (6) of node $v$ will be dominated by Constraints (5), and
hence can be removed. On the other hand, if for a node $v$ we have $w_{vz}=1$
for all $z\in N(v)$ then Constraints (5) of node $v$ will be dominated by
Constraint (6), and hence can be removed.

###  4.3 Existence of Perfect Defending Strategy

While the general problem of computing the optimal allocation strategy is
-hard, we show in this section that deciding whether there exists a defending
strategy with defending result $0$ (which we refer to as a _perfect defending
strategy_) is polynomial time solvable. Moreover, if they exist, then we can
compute one in polynomial time.

###### Theorem 4.2

For every $k\geq 0$, there exists a polynomial time algorithm that computes a
perfect defending strategy for the DCA , if perfect defending strategies
exist.

  * Proof:

Recall that MILP$(R)$ computes the optimal defending strategy. If there exist
perfect defending strategies, then we have $\textsf{Loss}=0$ in the optimal
solution for MILP$(R)$. Since $\textsf{Loss}\geq\sum_{v\in
N_{k}(u)}(1-x^{u}_{v})\alpha_{v}$, we must have $x^{u}_{v}=1$ for all integer
variables in the optimal solution.

Therefore, by fixing $x^{u}_{v}=1$ for all integer variables, MILP$(R)$ must
be feasible. Observe that after fixing an assignment to the integer variables,
MILP$(R)$ becomes a feasibility LP, which can be solved exactly in polynomial
time. Any feasible solution $(\mathbf{r},\\{\mathbf{t}^{u}\\}_{u\in V})$ for
the LP provides a perfect defending strategy, as claimed. $\Box$

###  4.4 Bi-criteria Approximation

As Example 3.2 indicates, it is impossible to obtain any bounded approximation
of the reallocation by rounding the LP relaxation of MILP$(R)$. However, we
show that by augmenting the total resource we use, good approximation
solutions (in terms of defending results) can be obtained.

######  Definition 4.2 (Bi-criteria Approximation)

We call a defending strategy $(\gamma,\beta)$-approximate if it uses $R$ total
resource and its defending result is at most $\gamma\cdot\mathsf{OPT}$, where
$\mathsf{OPT}$ is the optimal defending result using $R/\beta$ resource.

While it is not possible to obtain bounded (standard) approximations by
rounding LP$(R)$, we show that achieving bi-criteria approximations is
possible. We defer the proof of the following theorem to the full version of
the paper.

###### Theorem 4.3

For any $\epsilon\in(0,1)$, we can compute a
$(\frac{1}{1-\epsilon},\frac{1}{\epsilon})$-approximate defending strategy in
polynomial time. In particular, with $\epsilon=0.5$ we can compute a
$(2,2)$-approximate solution in polynomial time.

Interestingly, we show that under the Unique Game Conjecture (UGC) [16], there
do not exist strong Pareto improvements over our bi-criteria $(2,2)$
approximation ratio. The proof is deferred to the full version of the paper.

###### Lemma 4.1

Under UGC, there does not exist polynomial time
$(2-\delta,2-\delta)$-approximate algorithm for the DCA problem, for any
constant $\delta>0$.

##### Implementation.

In practice, we can enumerate different $\epsilon\in(0,1)$ to compute
different defending strategies, and then pick the one with the best defending
result. In the following, we show that we might be able to improve the
defending result further by deploying a more aggressive rounding on
$\mathbf{x}$. Specifically, we first solve $\textsf{LP}(\epsilon\cdot R)$ and
get the optimal solution. Then we pick some $\tau\in[0,\epsilon]$, round each
$x$ variable that is less than $\tau$ to $0$, and those at least $\tau$ to
$1$. With the fixed integer variables, we solve MILP$(R)$, which has become a
feasibility LP. If the resulting LP is feasible, then we obtain a defending
strategy with defending result at most $\frac{1}{1-\tau}\cdot\mathsf{OPT}$,
where $\mathsf{OPT}$ is the optimal defending result of defending strategies
using $\epsilon\cdot R$ resources. Hence the resulting solution is a
$(\frac{1}{1-\tau},\frac{1}{\epsilon})$-approximate defending strategy. For
different problem instances, the minimum $\tau$ with which the induced LP is
feasible can be different. However, the LP must be feasible when
$\tau=\epsilon$. As we will show in our experiments, in all datasets we
consider, the defending result after optimizing $\tau$ is much smaller than
using $\tau=\epsilon$.

##  5 Experimental Evaluation

In this section, we evaluate the effectiveness and efficiency of our
algorithms on synthetic and real-world datasets. Our datasets contain
synthetic graphs, including random graphs and power-law distribution graphs,
which are well recognized as the best in modeling random networks and social
networks. We also consider real-world networks, including aviation networks
and social networks, in order to demonstrate the practical performance of our
algorithms on defending against contagious attacks in the real world. The
datasets are generated as follows. For each dataset, $n$ and $m$ denote the
number of nodes and edges, respectively.

| Rand | Pow-S | Pow-L | USAir | FB | Twit
---|---|---|---|---|---|---
# Node | 200 | 400 | 700 | 221 | 600 | 1000
# Edge | 803 | 1579 | 2087 | 2166 | 4638 | 13476

  * •

Random: We generate the dataset with $n=200$ and $p=0.04$ using the algorithm
by [5], where there is an edge between each pair of nodes independently with
probability $p$. The thresholds $\theta_{u}$’s and values $\alpha_{u}$’s are
chosen uniformly at random from integers in $[1,10]$. The edge weights
$w_{uv}$’s are uniformly chosen from $[0.3,1]$.

  * •

Power-law distribution graphs (Pow): We use the graph generator by NetworkX
[14] to generate the power-law distribution graphs, where we set the
parameters666For the details regarding how the parameters define the graph,
please refer to
https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.random˙graphs.powerlaw˙cluster˙graph.html.
to be $(400,4,0.5)$ for Pow-S and $(700,3,0.5)$ for Pow-L. The parameters
$\theta_{u}$’s, $\alpha_{u}$’s and $w_{uv}$’s are generated randomly as before
(for dataset Rand).

  * •

USAir: We select the flight records in the US from years $2008$ to $2010$ [24]
to generate a directed graph where each node represents a city. There is a
directed edge from city $u$ to city $v$ if the number of flights per week from
$u$ to $v$ is at least $25$. We set the edge weight as the ratio between the
flights-per-week of the edge and the maximum flights-per-week value of all
edges. We set $\theta_{u}$ and $\alpha_{u}$ as the population (in millions) of
city $u$.

  * •

Social networks: We use the network of Facebook (undirected) and Twitter
(directed) to generate our datasets [21]. The dataset FB (resp. Twit) is
extracted from the source network by picking a random node in the network and
expand using breath-first-search until the size of the dataset reaches $n=600$
(resp. $n=1000$). We set $\theta_{u}=\alpha_{u}=w_{uv}=1$ for all nodes and
edges.

#### Experiment Environment.

We perform our experiments on an AWS Ubuntu 18.04 machine with 32 threads and
128GB RAM without GPU. We use Gurobi optimizer [13] as our solver for the LPs
and MILPs.

We evaluate the effectiveness of our exact and approximation algorithms by
comparing the results of defending strategies under different settings and
datasets. Throughout all the experiments, we fix the contagiousness parameter
$k=2$.

#### Effectiveness of Reallocation.

One of the main innovations of our work is that we consider the reallocation
of defending resources between the nodes. The reallocation allows the
algorithm to react adaptively against the attack. In particular, we compare
the results of defending strategies with and without reallocation as follows.

We first use the algorithm in Section 4.3 to compute for each dataset the
minimum total resource required in a perfect defending strategy (a strategy
with defending result $0$). As our experiment (in Table 1) shows, reallocation
(see the row with $w\neq 0$) always helps in reducing the requirement on the
defending resource, for all datasets. For example, for the first dataset Rand,
the resource required in a perfect defending strategy is 40% less than the
case when reallocation is not allowed (see the row with $w=0$).

| Rand | Pow-S | Pow-L | USAir | FB | Twit
---|---|---|---|---|---|---
$w=0$ | 1037 | 1892 | 3406 | 341 | 600 | 1000
$w\neq 0$ | 587 | 1687 | 2320 | 340 | 524 | 623

Table 1: Resource required to achieve defending result $0$.

#### Comparing Different Algorithms.

We also evaluate the effectiveness of our bi-criteria approximations from
Section 4.4, and compare it with the exact solution and the Greedy algorithms.
The results are shown in Table 2, where BA$(\epsilon)$ stands for the
approximation algorithm by rounding the optimal solution for LP$(\epsilon\cdot
R)$ and optimizing $\epsilon\in(0,1)$; BA$(\epsilon,\tau)$ stands for the
approximation algorithm that further optimizes $\tau\in(0,\epsilon]$ in the
more aggressive rounding. We use Greedy to refer to the algorithm that
greedily allocates resources to nodes with the maximum value (break tie
arbitrarily) and does not use reallocation; Greedy-R is based on Greedy but
uses greedy reallocation. Specifically, when node $u$ is attacked, for each
node $v\in N_{k}(u)$ in decreasing order of their values, the algorithm
transfers resource to $v$ until its defending power is at least its threshold,
or when no more resource can be transferred from its neighbors. In the
experiments, we fix $R=0.5\cdot\sum_{u\in V}\theta_{u}$ for all datasets.

| Rand | Pow-S | Pow-L | USAir | FB | Twit
---|---|---|---|---|---|---
Greedy | 278 | 859 | 1168 | 178.7 | 188 | 302
Greedy-R | 225 | 819 | 1025 | 178.7 | 186 | 281
BA$(\epsilon)$ | 289 | 1134 | 1230 | 291.8 | 109 | 148
BA$(\epsilon,\tau)$ | 107 | 785 | 701 | 204.3 | 58 | 55
Exact | 69 | 740 | 616 | 170.3 | 51 | 53

Table 2: Defending results by the bi-criteria approximations.

From Table 2, we observe that by deploying a more aggressive rounding on the
fractional solutions, the approximation solutions by BA$(\epsilon,\tau)$
outperform BA$(\epsilon)$ dramatically, and are very close to the optimal
solutions in all datasets. Moreover, in general, BA$(\epsilon,\tau)$ achieves
much smaller defending results when compared with both Greedy approaches in
most datasets. The only exception is the dataset USAir, in which the values of
nodes differ greatly. Thus, Greedy allocation of resources achieves the almost
optimal result. BA$(\epsilon)$ does not perform well because the solution is
obtained by a very loose rounding on the solution of LP$(\epsilon\cdot R)$.
Observe that with the help of reallocation, Greedy-R obtains advantages over
Greedy, which again demonstrates the critical role of reallocation. Note that
the defending results by Pow-S are larger than that of Pow-L because it has a
larger density of edges, which crucially affects the number of attacked nodes.

#### Efficiency Evaluation.

Finally, we evaluate the efficiency of our algorithms and summarize the
running times in Table 3, where No-Prune refers to the algorithm by solving
the MILP without using the pruning we mentioned in Section 4.2; Pruning refers
to the one with pruning; BA$(\epsilon,\tau)$ refers to our bi-criteria
approximation algorithm.

| Rand | Pow-S | Pow-L | USAir | FB | Twit
---|---|---|---|---|---|---
No-Prune | 4637 | 8180 | 36293 | 10686 | 32608 | 8441
Pruning | 4259 | 3351 | 8227 | 2920 | 18929 | 2757
BA$(\epsilon,\tau)$ | 246 | 867 | 1508 | 416 | 2540 | 1294

Table 3: Running times of different algorithms (in seconds).

As we can see from the Table 3, the running times for solving MILPs are
obviously improved after pruning, which shows the effectiveness of removing
redundant variables. In particular, for the dataset Pow-L, which admits the
long tail phenomenon, there is a 77% improvement on the running time after
pruning. Our approximation algorithm improves the running time even further,
e.g., is several times faster than that of Pruning in all datasets, which
demonstrates its great efficiency in practical use. Recall that from Table 2,
the defending results of our approximation algorithms are very close to the
exact solutions by MILP.

## References

  * [1] D. Acemoglu, A. Malekian, and A. E. Ozdaglar.  Network security and contagion.  J. Econ. Theory, 166:536–585, 2016.
  * [2] J. Aspnes, K. L. Chang, and A. Yampolskiy.  Inoculation strategies for victims of viruses and the sum-of-squares partition problem.  J. Comput. Syst. Sci., 72(6):1077–1093, 2006.
  * [3] N. Assimakopoulos.  A network interdiction model for hospital infection control.  Computers in biology and medicine, 17(6):413–422, 1987.
  * [4] Y. Bachrach, M. Draief, and S. Goyal.  Contagion and observability in security domains.  In Allerton, pages 1364–1371. IEEE, 2013.
  * [5] V. Batagelj and U. Brandes.  Efficient generation of large random networks.  Phys. Rev. E, 71:036113, Mar 2005.
  * [6] P. Berman and T. Fujito.  On approximation properties of the independent set problem for low degree graphs.  Theory Comput. Syst., 32(2):115–132, 1999.
  * [7] H. Chan, M. Ceyko, and L. E. Ortiz.  Interdependent defense games: Modeling interdependent security under deliberate attacks.  In UAI, pages 152–162. AUAI Press, 2012.
  * [8] H. Chan, M. Ceyko, and L. E. Ortiz.  Interdependent defense games with applications to internet security at the level of autonomous systems.  Games, 8(1):13, 2017.
  * [9] M. Chlebík and J. Chlebíková.  Complexity of approximating bounded variants of optimization problems.  Theor. Comput. Sci., 354(3):320–338, 2006.
  * [10] J. Gan, B. An, and Y. Vorobeychik.  Security games with protection externalities.  In AAAI, pages 914–920. AAAI Press, 2015.
  * [11] J. Gan, B. An, Y. Vorobeychik, and B. Gauch.  Security games on a plane.  In AAAI, pages 530–536. AAAI Press, 2017.
  * [12] S. Goyal and A. Vigier.  Attack, defence, and contagion in networks.  The Review of Economic Studies, 81(4):1518–1542, 2014.
  * [13] L. Gurobi Optimization.  Gurobi optimizer reference manual, 2020.
  * [14] A. A. Hagberg, D. A. Schult, and P. J. Swart.  Exploring network structure, dynamics, and function using networkx.  In G. Varoquaux, T. Vaught, and J. Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008\.
  * [15] B. Johnson, J. Grossklags, N. Christin, and J. Chuang.  Uncertainty in interdependent security games.  In GameSec, volume 6442 of Lecture Notes in Computer Science, pages 234–244. Springer, 2010.
  * [16] S. Khot and O. Regev.  Vertex cover might be hard to approximate to within 2-epsilon.  J. Comput. Syst. Sci., 74(3):335–349, 2008.
  * [17] H. Kunreuther and G. Heal.  Interdependent security.  Journal of risk and uncertainty, 26(2-3):231–249, 2003.
  * [18] J. Letchford, V. Conitzer, and K. Munagala.  Learning and approximating the optimal strategy to commit to.  In SAGT, volume 5814 of Lecture Notes in Computer Science, pages 250–262. Springer, 2009.
  * [19] M. Li, L. Tran-Thanh, and X. Wu.  Defending with shared resources on a network.  In AAAI, pages 2111–2118. AAAI Press, 2020.
  * [20] J. Lou, A. M. Smith, and Y. Vorobeychik.  Multidefender security games.  IEEE Intell. Syst., 32(1):50–60, 2017.
  * [21] J. J. McAuley and J. Leskovec.  Learning to discover social circles in ego networks.  In NIPS, pages 548–556, 2012.
  * [22] K. C. Nguyen, T. Alpcan, and T. Basar.  Stochastic games for security in networks with interdependent nodes.  In GAMENETS, pages 697–703. IEEE, 2009.
  * [23] A. Schlenker, O. Thakoor, H. Xu, F. Fang, M. Tambe, L. Tran-Thanh, P. Vayanos, and Y. Vorobeychik.  Deceiving cyber adversaries: A game theoretic approach.  In AAMAS, pages 892–900, 2018.
  * [24] A. Sharma.  Usa airport dataset, 2020.
  * [25] A. Sinha, F. Fang, B. An, C. Kiekintveld, and M. Tambe.  Stackelberg security games: Looking beyond a decade of success.  In IJCAI, pages 5494–5501. ijcai.org, 2018.
  * [26] M. Tambe.  Security and Game Theory - Algorithms, Deployed Systems, Lessons Learned.  Cambridge University Press, 2012.
  * [27] J. Tsai, T. H. Nguyen, and M. Tambe.  Security games for controlling contagion.  In AAAI. AAAI Press, 2012.
  * [28] Y. Vorobeychik and J. Letchford.  Securing interdependent assets.  Auton. Agents Multi Agent Syst., 29(2):305–333, 2015.
  * [29] Y. Yin, H. Xu, J. Gan, B. An, and A. X. Jiang.  Computing optimal mixed strategies for security games with dynamic payoffs.  In IJCAI, pages 681–688. AAAI Press, 2015.
  * [30] Z. Yin and M. Tambe.  A unified method for handling discrete and continuous uncertainty in bayesian stackelberg games.  In AAMAS, pages 855–862. IFAAMAS, 2012.
  * [31] Y. Zhang, B. An, L. Tran-Thanh, Z. Wang, J. Gan, and N. R. Jennings.  Optimal escape interdiction on transportation networks.  In IJCAI, pages 3936–3944. ijcai.org, 2017.

##  Appendix A Missing Proofs

Proof of Theorem 3.1:  We prove this by a reduction from the maximum
independent set (MIS) problem, which is -hard [6]. In the MIS problem we are
given a graph ${G_{mis}=(V_{mis},E_{mis})}$ and the problem is to find a
maximum size set $S\subseteq V_{mis}$ such that no two vertices in $S$ are
adjacent. We construct an instance of the DCA problem as follows. We first
initialize the graph structure ${G=(V,E)}$ to be the same as $G_{mis}$, and
set the parameters as follows. Let $n=|V_{mis}|$ and $d(u)=N(u)$ be the degree
of node $u$ in $G$.

  * •

Let $r_{v}=n$, $\theta_{v}=n+d(v)$ and $\alpha_{v}=1$ for all $v\in V$.

  * •

Let $w_{uv}=\frac{1}{n}$ for all $(u,v)\in E$.

Finally, we insert a new vertex $s$ to $V$ with $r_{s}=\alpha_{s}=0$,
$\theta_{s}=1$, and let $s$ be connected with all other nodes with edges with
weight $0$. Note that the final instance of DCA has $n+1$ nodes and
$n+|E_{mis}|$ edges.

Suppose $s$ is under attack. Since $N_{1}(s)=V$, the attack spreads to the
whole graph $G$, for $k\geq 1$.

Observe that for each node $u\in V_{mis}$, its resource $r_{u}=n$ is lower
than its threshold $\theta_{u}=n+d(u)$. Moreover, its maximum possible
defending power

$\hat{p}_{u}=n+\sum_{v\in N(u)}w_{uv}\cdot r_{v}=n+d(u)=\theta_{u}$

can be obtained only by (1) not transferring any resource to its neighbors;
(2) receive $w_{uv}\cdot r_{v}=1$ unit of resource from each of its neighbors.

Hence under any reallocation strategy, if a node $u$ is well defended
($p_{u}\geq\theta_{u}$), then none of its neighbors $v\in N(u)$ is well
defended ($p_{v}<\theta_{v}$). Let $S^{*}\subseteq V_{mis}$ be the set of
nodes that are well defended under the optimal reallocation strategy, we have

  * •

$S^{*}$ is an independent set (by the above argument);

  * •

$\textsf{Loss}(s)=n-|S^{*}|$, since each $u\in V_{mis}$ has $\alpha_{u}=1$.

Since $\textsf{Loss}(s)$ is minimized in the optimal reallocation strategy, we
know that $|S^{*}|$ is maximized. In other words, $S^{*}$ is a maximum size
independent set of $G_{mis}$.

Since the reduction is polynomial time, if there exists a polynomial time
algorithm to compute the optimal reallocation strategy, then we can solve the
MIS problem in polynomial time, which is a contradiction. Consequently,
computing the optimal reallocation strategy is -hard.

Proof of Lemma 4.1:  We use the same reduction from vertex cover problem as in
the proof of Theorem 4.1. It is shown in [16] that under the Unique Game
Conjecture (UGC), there does not exist $(2-\delta)$-approximation for the
vertex cover problem, for any constant $\delta>0$. Suppose there exists a
polynomial time $(2-\delta,2-\delta)$-approximate algorithm for the DCA
problem, we show that it can be transformed into a $(2-\delta)$-approximation
algorithm for the vertex cover problem, which contradicts the UGC.

Given any instance $G_{vc}=(V_{vc},E_{vc})$ of a VC problem instance, we
construct an instance $G=(V,E)$ of DCA as in the proof of Theorem 4.1. Then
for each $R=1,2,\ldots,|V_{vc}|-1$, we run the
$(2-\delta,2-\delta)$-approximate algorithm to compute a defending strategy,
and let $R^{*}$ be the smallest such that when $R=R^{*}$, the defending result
is $1$.

Suppose $S^{*}\subseteq V_{vc}$ is the minimum size vertex cover. By the
construction of the DCA problem, when $R=|S^{*}|$, the optimal defending
result is $\mathsf{OPT}=1$. Hence with $R=(2-\delta)|S^{*}|$ total defending
resource, the $(2-\delta,2-\delta)$-approximate algorithm computes a defending
strategy with defending result at most $(2-\delta)\cdot\mathsf{OPT}=2-\delta$.
Since defending results are integers, the defending result by the
approximation algorithm is $1$. Observe that since all nodes have threshold
$1$ and resource cannot be transferred, a defending strategy with
$R=(2-\delta)|S^{*}|$ is equivalent to one with
$R=\lfloor(2-\delta)|S^{*}|\rfloor$. In other words, when
$R=\lfloor(2-\delta)|S^{*}|\rfloor$, the defending result of the approximation
algorithm is $1$, which implies $R^{*}\leq\lfloor(2-\delta)|S^{*}|\rfloor$.
Moreover, since the defending result is $1$, the set of defended nodes is a
vertex cover. Hence we have found a vertex cover of size

$R^{*}\leq\lfloor(2-\delta)|S^{*}|\rfloor\leq(2-\delta)|S^{*}|,$

which gives a $(2-\delta)$-approximation for the VC problem, and contradicts
the UGC.

Proof of Theorem 4.3:  Recall that by the definition of bi-criteria
approximations, we need to compute a strategy with the defending result at
most $\frac{1}{1-\epsilon}\cdot\mathsf{OPT}$, where $\mathsf{OPT}$ is the
optimal defending result of defending strategies that use $\epsilon\cdot R$
total defending resource, i.e., $\mathsf{OPT}$ is the optimal objective of
MILP$(\epsilon\cdot R)$.

We first run $\textsf{LP}(\epsilon\cdot R)$ and obtain the optimal
(fractional) solution. Note that the optimal objective of
$\textsf{LP}(\epsilon\cdot R)$ is at most $\mathsf{OPT}$, but in the solution
each $x^{u}_{v}$ can take arbitrary values in $[0,1]$. In the following, we
round the optimal solution $(\mathbf{x},\mathbf{r},\mathbf{t})$ of
LP$(\epsilon\cdot R)$ and construct a feasible solution
$(\hat{\mathbf{x}},\hat{\mathbf{r}},\hat{\mathbf{t}})$ for MILP$(R)$. We show
that the objective of the solution is at most
$\frac{1}{1-\epsilon}\cdot\mathsf{OPT}$. Since each feasible solution for
MILP$(R)$ corresponds to a defending strategy, the theorem follows. For each
variable $x^{u}_{v}\in[0,1]$, let $\hat{x}^{u}_{v}=1$ if
$x^{u}_{v}\geq\epsilon$, and let $\hat{x}^{u}_{v}=0$ otherwise. Let
$\hat{r}_{u}=\frac{1}{\epsilon}\cdot r_{u}$ and
$\hat{t}^{u}(z,v)=\frac{1}{\epsilon}\cdot t^{u}(z,v)$, for the corresponding
variables. We show that the solution
$(\hat{\mathbf{x}},\hat{\mathbf{r}},\hat{\mathbf{t}})$ we have constructed is
feasible for MILP$(R)$. Since originally $\sum_{u\in V}r_{u}\leq\epsilon\cdot
R$, we have $\sum_{u\in V}\hat{r}_{u}\leq R$, i.e., the first constraint of
MILP$(R)$ is satisfied. Constraints (4) in which $\hat{x}^{u}_{v}=0$ are
trivially satisfied. For those with $\hat{x}^{u}_{v}=1$, since we increase
$x^{u}_{v}$ by a factor of at most $\frac{1}{\epsilon}$ and increase all $r$
and $t$ variables by a factor of $\frac{1}{\epsilon}$, Constraints (4) of
MILP$(R)$ are satisfied. Since all $r$ and $t$ variables are scaled by the
same factor, Constraints (5) (6) of MILP$(R)$ are all satisfied.

Finally, since we decrease each $x^{u}_{v}$ (to $0$) only if
$x^{u}_{v}<\epsilon$, by rounding $\mathbf{x}$ into $\hat{\mathbf{x}}$, for
each $u\in V$, we have

$\textstyle\sum_{v\in
N_{k}(u)}(1-\hat{x}^{u}_{v})\alpha_{v}\leq\frac{1}{1-\epsilon}\sum_{v\in
N_{k}(u)}(1-x^{u}_{v})\alpha_{v}.$

Hence the objective of solution
$(\hat{\mathbf{x}},\hat{\mathbf{r}},\hat{\mathbf{t}})$ for MILP$(R)$,
$\textsf{Loss}=\max_{u\in V}(\sum_{v\in
N_{k}(u)}(1-\hat{x}^{u}_{v})\alpha_{v})$, is at most
$\frac{1}{1-\epsilon}\cdot\mathsf{OPT}$, as claimed.


# Debiasing Neural Retrieval via In-batch Balancing Regularization

Yuantong Li1, Xiaokai Wei2†, Zijian Wang2†, Shen Wang2,
Parminder Bhatia2, Xiaofei Ma2, Andrew Arnold2
1UCLA
2AWS AI Labs
<EMAIL_ADDRESS>xiaokaiw, zijwan, shenwa, parmib,
xiaofeim<EMAIL_ADDRESS>Work done during an internship at AWS. Equal
contribution.

###### Abstract

People frequently interact with information retrieval (IR) systems, however,
IR models exhibit biases and discrimination towards various demographics. The
in-processing fair ranking methods provide a trade-offs between accuracy and
fairness through adding a fairness-related regularization term in the loss
function. However, there haven’t been intuitive objective functions that
depend on the click probability and user engagement to directly optimize
towards this. In this work, we propose the In-Batch Balancing Regularization
(IBBR) to mitigate the ranking disparity among subgroups. In particular, we
develop a differentiable normed Pairwise Ranking Fairness (nPRF) and leverage
the T-statistics on top of nPRF over subgroups as a regularization to improve
fairness. Empirical results with the BERT-based neural rankers on the MS MARCO
Passage Retrieval dataset with the human-annotated non-gendered queries
benchmark (Rekabsaz and Schedl, 2020) show that our IBBR method with nPRF
achieves significantly less bias with minimal degradation in ranking
performance compared with the baseline.

##  1 Introduction

Recent advancements in Natural Language Processing and Information Retrieval
(Palangi et al., 2016; Devlin et al., 2019; Zhao et al., 2020; Karpukhin et
al., 2020) have led to great progress in search performances. However, search
engines easily expose various biases (e.g., (Biega et al., 2018; Baeza-Yates,
2018; Rekabsaz and Schedl, 2020; Rekabsaz et al., 2021)), which sabotage the
trust of human beings from day to day. Many methods have been proposed
recently to reduce the bias of the retrievers. Existing fairness-aware ranking
methods can be categorized into pre-processing methods, in-processing methods,
and post-processing methods (Mehrabi et al., 2021; Zehlike et al., 2021). Pre-
processing methods typically focus on mitigating bias in data before training
the model. Lahoti et al. (2019) discussed the individual fairness pre-
processing method to learn the fair representation of data. However, the
representation-based method will undermine the value of the features
determined by domain experts (Zehlike et al., 2021). The in-processing methods
usually transform the fairness in ranking task into an optimization problem
consisting of an accuracy objective and a fairness objective. These methods
learn the best balance between these two objectives (Kamishima et al., 2011;
Berk et al., 2017; Bellamy et al., 2018; Konstantinov and Lampert, 2021).
Zehlike and Castillo (2020) handles different types of bias without knowing
the exact bias form; Post-processing algorithms (Singh and Joachims, 2018;
Zehlike et al., 2017, 2020; Cui et al., 2021) are model agnostic without
requiring access to the training process, but these methods re-order the
ranking at the expense of accuracy (Menon and Williamson, 2018).

Among recent works on fair neural retrieval, Beutel et al. (2019) introduce
the pairwise ranking fairness (PRF) metric for ranking predictions. This
pairwise fairness metric evaluates whether there is a difference in accuracy
between two groups. Rekabsaz et al. (2021) (AdvBert) mitigates the bias
magnitude from the concatenation of query and passage text rather than
treating the bias magnitude from query and passage separately through an
adversarial neural network.

In this paper, we propose the In-Batch Balancing Regularization (IBBR) method
combined with the neural retrieval model. IBBR is an in-processing debiasing
method that balances the ranking disparity among different demographic groups
by adding an in-batch balancing regularization term to the objective function.
We design two batch-level regularization terms, Pairwise Difference (PD) and
T-statistics (TS) that measure biases within demographic groups. In addition,
we introduce normed Pairwise Ranking Fairness (nPRF), a relaxed version of the
PRF (Beutel et al., 2019) that is differentiable, thus could be directly
optimized. We apply IBBR to MS MARCO passage re-ranking task (Nguyen et al.,
2016) on gender bias using pre-trained $\text{BERT}_{L_{2}}$ and
$\text{BERT}_{L_{4}}$ models (Turc et al., 2019). Empirical results show that
our model could achieve significantly less bias with minor ranking performance
degradation, striking a good balance between accuracy and fairness. Our
contributions can be summarized as follows:

  * •

We introduce IBBR, an in-processing debiasing method based on pairwise
difference and T-statistics.

  * •

We introduce normed PRF, a relaxed version of the pairwise ranking fairness
(PRF) metric (Beutel et al., 2019). The normed PRF solves the non-
differentiable issue and could be directly optimized during training.

  * •

We perform experiments on the MS MARCO passage re-ranking task with IBBR and
normed PRF. Empirical results show that IBBR and normed PRF could achieve a
statistically significant improvement in fairness while maintaining good
ranking performance.

Figure 1: An example of In-Batch Balancing Regularization method. For each
query, we calculate the typical ranking loss and the fairness loss from IBBR
on top $K$ retrieved passages. We jointly optimize the ranking loss and the
fairness loss. There are two ways of computing the IBBR, pairwise difference
loss and T-statistics Loss.

##  2 PROBLEM DEFINITION

We first introduce notations in the ranking task in §2.1. §2.2 provides the
definition of the bias of the passage. In §2.3, we propose the definition of
the group fairness in the ranking task.

###  2.1 Notations in the Ranking Task

Formally, we define the task of Gender Debiased Neural Retrieval (GDNR) as:
given a query $q$ and top $K$ passages retrieved by the neural retrieval
system, we adapt the ranking to mitigate bias in the retrieval result. We
first define the whole query set as $Q=\\{q_{1},q_{2},...,q_{N}\\}$. For each
query $q_{i}$, we denote
$P_{i}=\\{p_{i,1},p_{i,2},\ldots,p_{i,j},\ldots,p_{i,K}\\}$ as the
corresponding retrieved passages’ set for query $q_{i}$. With query $q_{i}$
and corresponding retrieved passages $P_{i}$,
$s_{i}=\\{q_{i},p_{i,1}^{+},p_{i,2}^{-},\ldots,p_{i,K}^{-}\\}$ is defined as
one data pair. Here $p_{i,1}^{+}$ is the ground truth passage (clicked
passage) and $p_{i,j}^{-}$ is the non-clicked passage, $\forall
j\in\\{2,3,...,K\\}$. We use $Y_{i,j}=1$ to label the passage $p_{j}$ as a
clicked passage, otherwise, $Y_{i,j}=0$. Finally, the whole dataset is defined
as $D=\\{s_{1},s_{2},...,s_{N}\\}$. For notation simplicity, we use $[1:K]$ to
represent $\\{1,2,...,K\\}$.

###  2.2 Bias Label of Passage

We first provide the definition of the bias label of one passage, and consider
the gender bias as a running example. Rekabsaz and Schedl (2020) use the
degree of gender magnitude in the passage to define the bias value, where the
gender concept is defined via using a set of highly representative gender
definitional words. Such a gender definitional set usually contains words such
as she, woman, grandma for female definitional words ($G_{f}$), and he, man,
grandpa for males definitional words ($G_{m}$).

The definition of the bias of the passage in our method is different from
(Rekabsaz and Schedl, 2020) who assume that one passage has two magnitudes:
female magnitude and male magnitude. However, we assume that one passage has
only one implication or tendency and use the gender magnitude difference as
the bias value. So the bias value of the passage $p$, $mag(p)$, defined as

$mag(p)=\sum_{w\in G_{m}}\log|\langle w,p\rangle|-\sum_{w\in
G_{f}}\log|\langle w,p\rangle|,$ (1)

where $|\langle w,p\rangle|$ refers to the number of occurrences of the word
$w$ in passage $p$, $w\in G_{m}$ or $G_{f}$. Furthermore, we define the bias
label for the passage $p$ as $d(p)$, if $mag(p)>0$, then $d(p)=1$ (male-
biased); if $mag(p)<0$, then $d(p)=-1$ (female-biased); if $mag(p)=0$, then
$d(p)=0$ (neutral). So for each retrieved passage
$p_{i,j},j\in[1:K],i\in[1:N]$, it has one corresponding bias label
$d(p_{i,j})\in\\{-1,0,1\\}$.

###  2.3 Group Fairness in Ranking

In §2.3.1, we introduce one metric of ranking group fairness (pairwise ranking
fairness) proposed by (Beutel et al., 2019). In §2.3.2, we provide a more
refined definition of pairwise ranking fairness.

####  2.3.1 Pairwise Ranking Fairness

If $R(p)\in[0,1]$ is the ranking score of passage $p$ from one retrieval model
, $\text{PRF}_{m}(s_{i})$ measures the probability level of a male-biased
random passage selected from the male group $m$ higher than all random female-
biased passages of data pair $s_{i}$

$\displaystyle\text{PRF}_{m}$
$\displaystyle(s_{i})=\frac{1}{n_{1}^{m}(s_{i})n_{0}(s_{i})}\sum_{j\in
g_{1}^{m}(s_{i})}$ (2) $\displaystyle\sum_{k\in
g_{0}(s_{i})}\mathbbm{1}[R(p_{i,j})\geq R(p_{i,k})],$

where $g_{1}^{m}(s_{i})=\\{j|d(p_{i,j})=1,Y_{i,j}=1,j\in[1:K]\\}$ represents
passages clicked ($Y_{i,j}=1$) as well as belonging to male biased group
($d(p_{i,j})=1$). $n_{1}^{m}(s_{i})=|g_{1}^{m}(s_{i})|$ represents the number
of male-biased clicked passages. $g_{0}(s_{i})=\\{j|Y_{i,j}=0,j\in[1:K]\\}$
represents the group of non-clicked passages. $n_{0}(s_{i})$ represents the
number of all non-clicked samples in retrieved passages. Beutel et al. (2019)
use the probability that a clicked sample is ranked above another non-clicked
sample for the sample query as the pairwise accuracy. The pairwise fairness
asks whether there is a difference between two groups when considering the
pairwise accuracy as the fairness level metric.

However, we find that PRF is not directly applicable as an argument in the
regularizer of a loss function that works as a trade-off of accuracy and
fairness. Because PRF is a 0-normed objective function, which is non-convex
and non-differentiable. So we propose a modified PRF that can be optimized
directly.

####  2.3.2 Normed-Pairwise Ranking Fairness

We propose a relaxed version of PRF called normed-PRF (nPRF), which measures
the degree of group fairness in retrieval results for a given query and
considering the ranking performance as well. The detailed definition of
$\text{nPRF}_{m}$ is defined over all clicked male-biased passages $p_{i}$ in
a data pair $s$ is

$\displaystyle\text{nPRF}_{m}=\biggl{\\{}\frac{1}{n_{1}^{m}(s_{i})n_{0}(s_{i})}\sum_{j\in
g_{1}^{m}(s_{i})}$ (3) $\displaystyle\sum_{k\in
g_{0}(s_{i})}|R(p_{i,j})|^{2}\mathbbm{1}[R(p_{i,j})\geq
R(p_{i,k})]\biggl{\\}}^{\frac{1}{2}},$

where $n_{1}^{m}(s_{i})$ is the number of all clicked male-biased passages in
a data pair, usually $n_{1}^{m}(s_{i})=1$ in the ranking system.

In order to avoid the drawback of PRF being non-differentiable, we multiply
the square of the ranking score ($|R(p_{i,j})|^{2}$) of the passage $p_{j}$ to
the indicator function $\mathbbm{1}[R(p_{i,j})\geq R(p_{i,k})]$, which is
differentiable. Besides, $\frac{1}{n_{0}(s_{i})}\sum_{j\in
g_{0}(s_{i})}|R(p_{i,j})|^{2}\mathbbm{1}[R(p_{i,j})\geq R(p_{j,k})]$ measures
the average harm of the biased passage $p_{i,j}$. If this value is large, it
means that on average, these non-clicked passages are more relevant to the
clicked passage $p_{i,j}$. This contributes more harm to the society since
people are more willing to accept the ranking result. If this value is small,
it means that on average, these non-clicked passages are less irrelevant to
the click passage $p_{i}$. This contributes less harm to the society since
people are less willing to accept the ranking result. Thus, the nPRF not only
considers the magnitude of the ranking performance of the retrieval results
but also inherits the explainable society impact into the PRF.

##  3 Algorithms

In this section, we create a regularizer based on the nPRF to mitigate the
gender bias. In §3.1, we introduce necessary components for the neural
retrieval task. In §3.2, we provide the definition of the ranking loss and two
fairness loss functions, Pairwise Difference Loss and T-statistics Loss,
acting as a regularizer, named as in-batch balancing regularization method
(IBBR).

###  3.1 Rank Model

Given the data set $D$, we use the two-tower dense passage retriever (DPR)
model (Karpukhin et al., 2020) as our retrieval model. DPR uses two dense
encoders $E_{P},E_{Q}$ which map the given text passage and input query to two
$d$-dimensional vectors ($d=128$) and retrieves $K$ of these vectors which are
close to the query vector. We define the ranking score between the query and
the passage using the dot product of their vectors produced from DPR as
$\text{sim}(q_{i},p_{i,j})=z_{q_{i}}^{\top}z_{p_{i,j}}$, where
$z_{q_{i}}=E_{Q}(q_{i})$ and $z_{p_{i,j}}=E_{P}(p_{i,j})$ are the
corresponding query and passage dense embeddings.

##### Remarks.

Here we use two-tower DPR for two reasons. (I) Computational considerations.
Humeau et al. (2019) thoroughly discussed the pros and cons between cross-
encoders (Nogueira and Cho, 2019) and bi-encoders such as DPR and stated that
cross-encoders are too slow for practical use. (II) Using cross-encoders can
cause ill-defined problem such as, if the query’s bias label belongs to groups
$m$ and the passage’s bias label belongs to group $f$, the concatenation of
these two texts’ bias label is unclear, based on the definition provided in
Eq. (2) from (Rekabsaz et al., 2021). So the two-tower BERT model is applied
separately on the query and document to tackle this ill-defined problem. Here
we only consider the DPR as our ranking model.

##### Encoders.

In our work, in order to demonstrate the robustness of IBBR, we use two BERT
models (Turc et al., 2019), (1) tiny BERT (base, uncased); (2) mini BERT
(base, uncased) as our encoders, and take the representation at the [CLS]
token as the output.

##### Inference.

For the data pair $s_{i}$, the ranking score $R(p_{i,j})$ of passage $p_{j}$
for query $q_{i}$ is simply the inner product of $\text{sim}(q_{i},p_{i,j})$
produced by DPR encoders.

###  3.2 Loss Functions

####  3.2.1 Ranking Loss

The ranking loss is the negative log-likelihood loss by computing the inner
product of query and passage embeddings to measure the ranking performance for
the data pair $s_{i}$,

$\displaystyle\text{L}^{\text{Rank}}=-\log\frac{e^{(\text{sim}(q_{i},p_{i,1}^{+}))}}{e^{(\text{sim}(q_{i},p_{i,1}^{+}))}+\sum_{j=2}^{K}e^{(\text{sim}(q_{i},p_{i,j}^{-}))}}.$

####  3.2.2 Fairness Loss

To mitigate the bias for two groups, we use the ranking disparity as a measure
to evaluate the fairness level of the neural retrieval system. And this
ranking disparity works as a regularization in the loss function. Here we
propose two regularization terms as follows.

##### (I) Pairwise Difference Loss.

The pairwise difference (PD) loss $\text{L}^{\text{Fair}}_{\text{P}}$ measures
the average ranking disparity between two groups $m$ and $f$ over a batch size
($B$) of data pairs,

$\displaystyle\text{L}^{\text{Fair}}_{\text{P}}$
$\displaystyle=\frac{1}{n_{m}n_{f}}\sum_{c\in p_{[1:B]}^{m}}\sum_{d\in
p_{[1:B]}^{f}}$ (4)
$\displaystyle(\text{nPRF}_{m}(s_{c})-\text{nPRF}_{m}(s_{d}))^{2},$

where $P_{[1:B]}^{m}=\\{i|p_{i,j}\in g^{m}_{1}(s_{i}),i\in[1:B],j\in[1:K]\\}$
is the set that the clicked passage belongs to group $m$ over batch size $B$
data. $P_{[1:B]}^{f}=\\{i|p_{i,j}\in g^{f}_{1}(s_{i}),i\in[1:B],j\in[1:K]\\}$
is the set that the clicked passage belongs to group $f$ over batch size $B$
data, and $n_{m}=|P_{[1:B]}^{m}|$ and $n_{f}=|P_{[1:B]}^{f}|$.

##### Remarks.

If there are many $\text{nPRF}_{m}(s_{x})$ which are different from other
$\text{nPRF}_{f}(s_{y})$, this means that group $m$ and group $f$ have
different fairness level over this batch data and will introduce more loss.
However, this PD loss does not consider distribution information over this
batch data, and imbalanced-data issue when group $m$ and group $f$ samples are
imbalanced. Thus we propose the T-statistics loss to overcome this.

##### (II) T-statistics Loss.

The design of T-statistics (TS) loss is also based on the ranking disparity
but considers the second order information (variance effect) of each group for
each batch data. We use the square of T-statistics as the ranking disparity
measure and defined as,

$\displaystyle\text{L}^{\text{Fair}}_{T}=\big{\\{}(\hat{\mu}_{m}-\hat{\mu}_{f})^{2}/\sqrt{\hat{\text{var}}_{m}/n_{m}+\hat{\text{var}}_{f}/n_{f}}\big{\\}}^{2},$

where $\hat{\mu}_{m}=\frac{1}{n_{m}}\sum_{j\in
P_{[1:B]}^{m}}\text{nPRF}_{m}(j)$ is the mean of the male group’s nPRF, and
$\hat{\text{var}}_{m}=\frac{1}{n_{m}}\sum_{j\in
P_{[1:B]}^{m}}(\text{nPRF}_{m}(j)-\hat{\mu}_{m})^{2}$ is the variance of the
male group’s nPRF. Besides, $\hat{\mu}_{f},\hat{\text{var}}_{f}$ can be
defined similarly.

##### Remarks.

This TS loss can provide a robust measure for the ranking disparity especially
when the batch data pair is imbalanced. The square of the T-statistics, i.e.,
$\chi^{2}$ distribution, provides the theoretical guarantee and power to
reject the similarity between group $m$ and group $f$.

##### Total Loss.

The total loss will be the sum of the ranking loss and fairness loss,
represented as $L^{\text{total}}_{[1:B]}=L^{\text{rank}}_{[1:B]}+\lambda
L^{\text{fair}}_{[1:B]}$, where $L^{\text{fair}}$ can be the PD loss or TS
Loss. $\lambda$ is a hyperparameter to control the balance of the fairness
loss and ranking loss. In the experiment, we try manually and automatically to
tune $\lambda_{\text{fair}}$. The details of our method can be found in Figure
1.

##  4 Experiments

In this section, we describe data resources in §4.1, experiment setup in §4.2,
evaluation metrics in Section 4.3, baseline models in Section 4.4, and
corresponding result analysis in Section 4.5.

nPRF | Ranking Metric | Fairness Metric
---|---|---
| IBBR | $\lambda_{\text{fair}}$ |  Recall@10 $\uparrow$ |  MRR $\uparrow$ |  NDCG $\uparrow$ |  $|\Delta\text{A-PRF}|$ $\downarrow$ |  RaB@5 $\downarrow$ |  RaB@10 $\downarrow$
DPR BERT(L2) |  |  | 0.357 | 0.164 | 0.196 | 0.005 | 0.091 | 0.079
PD | Best | 0.238 (-33.3%) | 0.112 (-31.7%) | 0.124 (-36.7%) | 0.034 (+580%) | 0.094 (+3.3%) | 0.083 (+5.1%)
Auto | 0.270 (-24.3%) | 0.126 (-23.2%) | 0.143 (-27.0%) | 0.033 (+560%) | 0.098 (+7.7%) | 0.083 (+5.1%)
TS | Best | 0.349 (-2.2%) | 0.170 (+3.6%) | 0.198 (+1.0%) |  0.001‡ (-80%) | 0.091 (0%) |  0.075‡ (-5.1%)
Auto | 0.333 (-6.7%) | 0.160 (-2.4%) | 0.185 (-5.6%) | 0.006 (+20%) | 0.109 (+19.7%) | 0.077 (-2.5%)
DPR BERT(L4) |  |  | 0.429 | 0.205 | 0.243 | 0.043 | 0.016 | 0.011
PD | Best | 0.381 (-11.1%) | 0.213 (+3.9%) | 0.236 (-2.8%) | 0.034‡ (-20.9%) | 0.033 (+106%) | 0.025 (+127%)
Auto | 0.373 (13.1%) | 0.214 (+4.4%) | 0.234 (-3.7%) | 0.030‡ (-30.2%) | 0.033 (+106%) | 0.021 (+90.9%)
TS | Best | 0.365 (-14.9%) | 0.193 (-5.9%) | 0.217 (-10.7%) |  0.000‡ (-100%) |  0.003‡ (-81.3%) |  0.012 (+9.1%)
Auto | 0.389 (-9.3%) | 0.205 (0%) | 0.234 (-3.7%) | 0.022‡ (-48.8%) | 0.004‡ (-75.0%) | 0.017 (+54.5%)
Table 1:  The ranking and fairness results of two IBBR methods, pairwise
difference and T-statistics, combined with nPRF in $\text{BERT}_{L_{2}}$ and
$\text{BERT}_{L_{4}}$ models. We compare IBBR with baseline models DPR L2, L4
in the re-ranking tasks and experimenting with different fairness
hyperparameter $\lambda_{\text{fair}}$ tuning methods. The bold value in each
column shows the best result in that metric. $\uparrow$ and $\downarrow$
indicate larger/smaller is better in corresponding definition of metrics. ‡
indicates statistically significant improvement (p-value$<0.05$) over the DPR
baseline in fairness metrics.

###  4.1 Dataset

We experimented on the passages re-ranking task from MS MARCO (Nguyen et al.,
2016). This collection includes 8.8 million passages and 0.5 million queries,
comprised of question-style queries from Bing’s search logs, accompanied by
human-annotated clicked/non-clicked passages. Additionally, data bias labels
over this dataset are available from (Rekabsaz and Schedl, 2020).

##### Data For DPR.

The whole dataset is composed of total 537,585 queries and $K*537,585$
retrieved passages where $K=200$, for the baseline DPR model. Each query has
top $K$ passages including one ground truth and 199 negative samples. The
details of splitting the dataset used for training, development, and test
(7:2:1) for the DPR model can be found in Appendix A Table 3. There are 126
queries used for the final evaluation.

##### Data For Fair Model.

The fairness dataset (Rekabsaz and Schedl, 2020) is also created upon this MS
MARCO dataset. These queries were annotated into one of four categories: non-
gendered (1765), female (742), male (1,202), other or multiple genders (41).
Here we only use the non-gendered queries, and assume the query is unbiased
given it does not have any gender definitional terms. There are 1,252 unique
queries in total. Examples of non-gendered queries are: what is a synonym for
beautiful?, what is the meaning of resurrect?, etc.

###  4.2 Experiment Setup

The maximum length of query and passage are set to 100. Batch size $B$ is 150
optimized over $\\{100,120,150\\}$. Learning rate is $3e^{-5}$ optimized over
$\\{3e^{-6},3e^{-5},3e^{-4}\\}$. A warmup ratio of 10% with linear scheduler
and a weight decay of 0.01 are set. In addition, we searched the fairness
penalty parameter $\lambda=[0.1,0.5,1,5,10]$ (Best). We also experimented
setting the $\lambda_{\text{fair}}$ as a trainable parameter (Auto). All
experiments are conducted ten times and we reported the average.

###  4.3 Evaluation Metrics

##### Ranking metrics.

We use Recall@10, MRR, and NDCG@10 to evaluate the ranking performance.

##### Fairness metrics.

We use RaB@5, RaB@10, and ranking disparity $|\Delta\text{A-PRF}|$ to evaluate
the fairness magnitude.

#####  $\text{RaB}_{t}$.

$\text{RaB}_{t}$ is a measurement of ranking bias, which is based on the
average of the gender magnitude of passages at top $t$ ranking list (Rekabsaz
and Schedl, 2020). To measure the retrieval bias, RaB calculates the mean of
the gender magnitudes of the top $t$ (5 or 10) retrieved documents for the
data pair $s_{i}$, for females,
$\text{qRaB}_{t}^{f}(s_{i})=\frac{1}{t}\sum_{j=1}^{t}mag_{f}(p_{i,j})$. Using
these values, the RaB metric of the query $q$,
$\text{RaB}_{t}(s_{i})=\text{qRaB}_{t}^{m}(s_{i})-\text{qRaB}_{t}^{f}(s_{i})$,
and the RaB metric of the retrieval model over all the queries,
$\text{RaB}_{t}=\frac{1}{N}\sum_{s_{i}\in D}\text{RaB}_{t}(s_{i})$. The
smaller the absolute value of $\text{RaB}_{t}$, the less the ranking disparity
is.

#####  $|\Delta\text{A-PRF}|$.

$|\Delta\text{A-PRF}|$ measures the ranking disparity over two groups, which
is the difference over two averaged PRF,
$|\Delta\text{A-PRF}|=|\frac{1}{|T_{m}|}\sum_{i\in
T_{m}}\text{PRF}_{i}-\frac{1}{|T_{f}|}\sum_{i\in T_{f}}\text{PRF}_{i}|$, where
$T_{m}$ is the dataset that the clicked passage belongs to group $m$,
$T_{m}=\\{i|Y_{i,j}=1,d_{i,j}=1,\forall i\in[1:N]\\}$. With the running
example, we denote $|T_{m}|$ as the number of male-biased clicked pairs and
similar definitions are for $T_{f}$ and $|T_{f}|$. The smaller the
$|\Delta\text{A-PRF}|$ is, the smaller the ranking disparity is. If
$|\Delta\text{A-PRF}|$ is close to zero, it means that the retrieved results
are relatively fair since the two groups’ PRF are close to each other. To
avoid selection bias, $|\Delta\text{A-PRF}|$ measures the whole dataset’s
fairness level rather than the subset’s result such as top 5 and top 10.

###  4.4 Baseline Models

The baseline methods contain the classical IR models, BM25, and RM3 PRF, and
neural based models: Match Pyramid (MP), Kernel-based Neural Ranking Model
(KNRM), Convolutional KNRM (C-KNRM), Transformer-Kernel (TK), and the fine-
tuned BERT Model. These results are available in in Appendix Section A. For
the BERT rankers, we use BERT-Tiny ($\text{BERT}_{L_{2}}$) and BERT-Mini
($\text{BERT}_{L_{4}}$).

###  4.5 Results Analysis

##### Ranking Performance.

In Table 1, we present the result of original $\text{BERT}_{L_{2}}$ and
$\text{BERT}_{L_{4}}$ and $\text{BERT}_{L_{2}}$ and $\text{BERT}_{L_{4}}$ with
IBBR (PD and TS). We found that in $\text{BERT}_{L_{2}}$, after adding IBBR,
the ranking performance decreases 2.2% in Recall@10 and the bias level
decreases 80% when applying the TS. Overall, TS outperforms PD on average when
considering the ranking metrics because it downgrades the ranking metric less,
which can be found in the ranking metric columns. This phenomenon exists both
in hand-tuned or auto-tuned hyperparameter $\lambda_{\text{fair}}$ and
$\text{BERT}_{L_{2}}$ and $\text{BERT}_{L_{4}}$.

##### Fairness Performance $|\Delta\text{A-PRF}|$.

$\text{BERT}_{L_{2}}$ \+ TS can achieve $80\%$ reduction in mitigating
$|\Delta\text{A-PRF}|$ bias. The $|\Delta\text{A-PRF}|$ fairness metric in
$\text{BERT}_{L_{4}}$+TS can achieve $100\%$ reduction in mitigating bias
compared with the original $\text{BERT}_{L_{4}}$. Besides, PD performs
unsatisfied in the fairness metric compared with TS in $\text{BERT}_{L_{2}}$
and $\text{BERT}_{L_{4}}$, we found that the variance of nPRF and the
imbalance affects the performance of PD, which is usually found in the
training phase ($\\#$male-biased > $\\#$female-biased). Overall nPRF + TS can
achieve the best performance in mitigating the $|\Delta\text{A-PRF}|$ ranking
disparity, which achieves our goal in mitigating the ranking disparity.

##### Fairness Performance RaB.

As for RaB, we hope to use another fairness metric to demonstrate our
regularization’s robustness. We realize RaB is focusing on the top-ranking
result and $|\Delta\text{A-PRF}|$ is focusing on the overall ranking result by
definition. We present the RaB result in the last column. In the last two
columns, the TS method is still better than the PD method on average. For
RaB@5, the TS method’s performance is similar to the PD method in
$\text{BERT}_{L_{2}}$ (3.3% vs 0%); The TS method’s performance is better than
the PD method in $\text{BERT}_{L_{4}}$ (106% vs -81.3%). For RaB@10, in
$\text{BERT}_{L_{2}}$, the TS method is similar to the PD method (5.1% vs
-2.5%); In $\text{BERT}_{L_{4}}$, the TS method is better than the PD method
(90.9% vs 9.1%). After evaluating the the fairness level on
$\text{BERT}_{L_{4}}$ and $\text{BERT}_{L_{2}}$, we found that the more
complicated the model is, the more bias it is, which is also demonstrated in
(Rekabsaz and Schedl, 2020). We find that the RaB performance not consistent
with the $|\Delta\text{A-PRF}|$ is mainly because $|\Delta\text{A-PRF}|$ is
focusing more on the lower-ranked passages and RaB is focusing the higher-
ranked passages. This makes these two fairness metrics are relatively
exclusive. However, when the ranking system performs well (rank the clicked
passage high), the $|\Delta\text{A-PRF}|$ will finally consider the overall
ranking result.

##  5 Conclusion

In this paper, we present a novel in-processing in-batch balancing
regularization method to mitigate ranking disparity and retain ranking
performance. We also overcome the non-differentiable and non-convex properties
of the 0-normed PRF and propose the nPRF. We conduct experiments on the MS
MARCO dataset and find that the nPRF with T-statistics regularization method
outperforms other methods in terms of fairness metrics and ranking metrics. In
future work, we will consider generalizing our method to multiple protected
variables such as age, income, etc, and also addressing bias in the query by
employing adversarial networks.

## Bias Statement

In this paper, we study gender bias in the neural retrieval system. If a
ranking system allocates resources or opportunities unfairly to specific
gender groups (e.g., less favorable to females), this creates allocation harm
by exhibiting more and more male-dominated passages, which also forms a more
biased dataset in turn. When such a ranking system is used in reality, there
is an additional risk of unequal performance across genders. Our work is to
explore the bias level of the dense passage retrieval model with
$\text{BERT}_{L_{2}}$ and $\text{BERT}_{L_{4}}$ on the MS MARCO passage
reranking task. Thus, the community can use these benchmarks with a clearer
understanding of the bias level, and can work towards developing a fairer
model.

## References

  * Baeza-Yates (2018) Ricardo Baeza-Yates. 2018.  Bias on the web.  _Communications of the ACM_ , 61(6):54–61.
  * Bellamy et al. (2018) Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. 2018.  Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias.  _arXiv preprint arXiv:1810.01943_.
  * Berk et al. (2017) Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. 2017.  A convex framework for fair regression.  _arXiv preprint arXiv:1706.02409_.
  * Beutel et al. (2019) Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Li Wei, Yi Wu, Lukasz Heldt, Zhe Zhao, Lichan Hong, Ed H. Chi, and Cristos Goodrow. 2019.  Fairness in recommendation ranking through pairwise comparisons.  In _KDD_ , pages 2212–2220. ACM.
  * Biega et al. (2018) Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. 2018.  Equity of attention: Amortizing individual fairness in rankings.  In _SIGIR_ , pages 405–414. ACM.
  * Cui et al. (2021) Sen Cui, Weishen Pan, Changshui Zhang, and Fei Wang. 2021.  Towards model-agnostic post-hoc adjustment for balancing ranking fairness and algorithm utility.  In _KDD_ , pages 207–217.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , pages 4171–4186, Minneapolis, Minnesota.
  * Humeau et al. (2019) Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2019.  Poly-encoders: Transformer architectures and pre-training strategies for fast and accurate multi-sentence scoring.  _arXiv preprint arXiv:1905.01969_.
  * Kamishima et al. (2011) Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. 2011.  Fairness-aware learning through regularization approach.  In _2011 IEEE 11th International Conference on Data Mining Workshops_ , pages 643–650. IEEE.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _EMNLP_ , pages 6769–6781, Online.
  * Konstantinov and Lampert (2021) Nikola Konstantinov and Christoph H Lampert. 2021.  Fairness through regularization for learning to rank.  _arXiv preprint arXiv:2102.05996_.
  * Lahoti et al. (2019) Preethi Lahoti, Krishna P Gummadi, and Gerhard Weikum. 2019.  ifair: Learning individually fair data representations for algorithmic decision making.  In _2019 ieee 35th international conference on data engineering (icde)_ , pages 1334–1345. IEEE.
  * Mehrabi et al. (2021) Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ , 54(6):1–35.
  * Menon and Williamson (2018) Aditya Krishna Menon and Robert C Williamson. 2018.  The cost of fairness in binary classification.  In _Conference on Fairness, Accountability and Transparency_ , pages 107–118. PMLR.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  Ms marco: A human generated machine reading comprehension dataset.  In _CoCo@ NIPS_.
  * Nogueira and Cho (2019) Rodrigo Nogueira and Kyunghyun Cho. 2019.  Passage re-ranking with bert.  _arXiv preprint arXiv:1901.04085_.
  * Palangi et al. (2016) Hamid Palangi, Li Deng, Yelong Shen, Jianfeng Gao, Xiaodong He, Jianshu Chen, Xinying Song, and Rabab Ward. 2016.  Deep sentence embedding using long short-term memory networks: Analysis and application to information retrieval.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 24(4):694–707.
  * Rekabsaz et al. (2021) Navid Rekabsaz, Simone Kopeinik, and Markus Schedl. 2021.  Societal biases in retrieved contents: Measurement framework and adversarial mitigation for bert rankers.  _ArXiv preprint_ , abs/2104.13640.
  * Rekabsaz and Schedl (2020) Navid Rekabsaz and Markus Schedl. 2020.  Do neural ranking models intensify gender bias? In _SIGIR_ , pages 2065–2068. ACM.
  * Singh and Joachims (2018) Ashudeep Singh and Thorsten Joachims. 2018.  Fairness of exposure in rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2219–2228.
  * Turc et al. (2019) Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Well-read students learn better: On the importance of pre-training compact models.  _ArXiv preprint_ , abs/1908.08962.
  * Zehlike et al. (2017) Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. 2017.  Fa*ir: A fair top-k ranking algorithm.  In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017_ , pages 1569–1578. ACM.
  * Zehlike and Castillo (2020) Meike Zehlike and Carlos Castillo. 2020.  Reducing disparate exposure in ranking: A learning to rank approach.  In _WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020_ , pages 2849–2855. ACM / IW3C2.
  * Zehlike et al. (2020) Meike Zehlike, Philipp Hacker, and Emil Wiedemann. 2020.  Matching code and law: achieving algorithmic fairness with optimal transport.  _Data Mining and Knowledge Discovery_ , 34(1):163–200.
  * Zehlike et al. (2021) Meike Zehlike, Ke Yang, and Julia Stoyanovich. 2021.  Fairness in ranking: A survey.  _ArXiv preprint_ , abs/2103.14000.
  * Zhao et al. (2020) Sendong Zhao, Yong Huang, Chang Su, Yuantong Li, and Fei Wang. 2020.  Interactive attention networks for semantic text matching.  In _ICDM_ , pages 861–870. IEEE.

##  Appendix A Appendix

Model |  | Ranking Metric | Fairness Metric
---|---|---|---
|  | Recall@10 | MRR | NDCG | D-PRF | RaB@5 | RaB@10
BM25 |  | 0.230 | 0.107 | 0.125 | - | - | -
RM3 PRF |  | 0.209 | 0.085 | 0.104 | - | - | -
MP |  | 0.295 | 0.141 | 0.191 | - | - | -
KNRM |  | 0.297 | 0.169 | 0.167 | - | - | -
C-KNRM |  | 0.325 | 0.170 | 0.197 | - | - | -
TK |  | 0.360 | 0.212 | 0.231 | - | - | -
DPR(L2) |  | 0.357† | 0.164† | 0.196† | 0.005 | 0.091 | 0.079
DPR(L4) |  | 0.429† | 0.205† | 0.243† | -0.043 | 0.016 | 0.011
Table 2: IR Model and DPR, † indicates significant improvement over BM25.

In this section, we provide the baseline model performance in Table 2. We also
provide the training, development, and test of the origin dataset and the
fairness dataset (with fairness label) in Table 3.

Data | Train | Dev | Test | Total
---|---|---|---|---
DPR | 510,586 | 26,873 | 126 | 537,585
Fairness111Here we use Non-gendered queries | 876 | 250 | 126 | 1,252
Table 3: The number of training, development and testing examples for the DPR
model and fairness model