# PORE: Provably Robust Recommender Systems against Data Poisoning Attacks

Jinyuan Jia$\>\;{}^{1}$, Yupei Liu11footnotemark: 1${\>\;{}^{2}}$, Yuepeng
Hu2, Neil Zhenqiang Gong2
1The Pennsylvania State University, 2Duke University
<EMAIL_ADDRESS>2{yupei.liu, yuepeng.hu<EMAIL_ADDRESS>Equal
contribution.

###### Abstract

_Data poisoning attacks_ spoof a recommender system to make arbitrary,
attacker-desired recommendations via injecting fake users with carefully
crafted rating scores into the recommender system. We envision a cat-and-mouse
game for such data poisoning attacks and their defenses, i.e., new defenses
are designed to defend against existing attacks and new attacks are designed
to break them. To prevent such cat-and-mouse game, we propose PORE, the first
framework to build _provably_ robust recommender systems in this work. PORE
can transform _any_ existing recommender system to be provably robust against
_any_ untargeted data poisoning attacks, which aim to reduce the overall
performance of a recommender system. Suppose PORE recommends top-$N$ items to
a user when there is no attack. We prove that PORE still recommends at least
$r$ of the $N$ items to the user under any data poisoning attack, where $r$ is
a function of the number of fake users in the attack. Moreover, we design an
efficient algorithm to compute $r$ for each user. We empirically evaluate PORE
on popular benchmark datasets.

##  1 Introduction

Many web service platforms (e.g., Amazon, YouTube, and TikTok) leverage
recommender systems to engage users and improve user experience. Typically, a
platform first collects a large amount of rating scores that users gave to
items, which is known as a _rating-score matrix_. Then, the platform uses them
to build a recommender system that models the complex relationships between
user interests and item properties. Finally, the recommender system recommends
top-$N$ items to each user that match his/her interests.

However, due to its openness, i.e., anyone can register users and provide
rating scores to items, recommender system is fundamentally not robust to
_data poisoning attacks_ [22, 27, 23, 42, 12, 11, 18]. Specifically, in a data
poisoning attack, an attacker creates fake users in a recommender system and
assigns carefully crafted rating scores to items. Different data poisoning
attacks essentially use different methods to craft the fake users’ rating
scores. When a recommender system is built based on the _poisoned-rating-score
matrix_ , which includes the rating scores of both genuine and fake users, it
recommends attacker-chosen, arbitrary top-$N$ items to a user. As a result,
the recommendation performance (e.g., Precision@$N$, Recall@$N$, and
F1-Score@$N$) is substantially degraded. Data poisoning attacks pose severe
challenges to the robustness/security of recommender systems.

Many defenses have been proposed to enhance the robustness of recommender
systems against data poisoning attacks. In particular, one family of defenses
[7, 47, 41, 44, 12] aim to detect fake users before building a recommender
system. These methods rely on the assumption that the rating scores of fake
users and genuine users have statistically different patterns, which they
leverage to distinguish between fake and genuine users. Another family of
defenses [30, 26, 35, 8, 43, 25, 17] aim to design new methods of training
recommender systems such that they have good recommendation performance even
if they are trained on a poisoned-rating-score matrix, e.g., using trim
learning [17]. However, these defenses only achieve _empirical_ robustness,
leading to an endless cat-and-mouse game between attacks and defenses: a new
empirical defense is proposed to mitigate existing attacks but can be broken
by new attacks that adapt to the defense. For instance, fake users can adapt
their rating scores such that they cannot be detected based on the rating
scores’ statistical patterns [12, 11, 18]. As a result, a recommender system’s
performance is still substantially degraded by strong, adaptive attacks.

Our work: In this work, we aim to end such cat-and-mouse game via proposing
PORE, the first framework to build _provably_ robust recommender systems
against _any_ untargeted data poisoning attacks. Suppose, under no attacks, a
recommender system algorithm trains a recommender system on a clean rating-
score matrix, which recommends a set of top-$N$ items (denoted as
$\Gamma_{u}$) to a user $u$. Under attacks, the recommender system algorithm
trains a recommender system on a poisoned-rating-score matrix, which
recommends a set of top-$N$ items (denoted as $\Gamma_{u}^{\prime}$) to the
user. We say the recommender system algorithm is $(e,r)$-provably robust for
the user $u$ if the intersection between $\Gamma_{u}$ and
$\Gamma_{u}^{\prime}$ includes at least $r$ items when there are at most $e$
fake users, no matter how an attacker crafts the fake users’ rating scores. In
other words, an $(e,r)$-provably robust recommender system guarantees that at
least $r$ of the recommended top-$N$ items are unaffected by $e$ fake users no
matter what rating scores they use. We note that $r$ depends on the number of
fake users $e$ and we call $r$ _certified intersection size_. A provably
robust recommender system can guarantee a lower bound of recommendation
performance under _any_ data poisoning attack, i.e., no matter how fake users
craft their rating scores.

Suppose a _submatrix_ consists of $s$ rows of the rating-score matrix, i.e., a
submatrix includes rating scores of $s$ users. Intuitively, when the fraction
of fake users is bounded, a randomly sampled submatrix is likely to not
contain fake users and thus a recommender system built based on the submatrix
is not affected by fake users. Based on this intuition, PORE uses _bagging_
[5], a well-known ensemble method, to achieve provable robustness. In
particular, PORE aggregates recommendations from multiple base recommender
systems to recommend top-$N$ items to each user. Specifically, we can use any
recommender system algorithm (called _base algorithm_) to build a recommender
system (called _base recommender system_) on a submatrix. Therefore, we could
build ${n\choose s}$ base recommender systems since there are ${n\choose s}$
submatrices, where $n$ is the total number of users. Each base recommender
system makes recommendations to users. We denote by $p_{i}$ the fraction of
the ${n\choose s}$ base recommender systems that recommend item $i$ to a user
$u$. We call $p_{i}$ _item probability_.111Item probability $p_{i}$ also
depends on user $u$, but we omit it for simplicity. PORE recommends the
top-$N$ items with the largest item probabilities to user $u$.

Our major theoretical result is that we prove PORE is $(e,r)$-provably robust,
no matter what base algorithm is used to train the base recommender systems.
Moreover, for any given number of fake users $e$, we derive the certified
intersection size $r$ for each genuine user, which is the solution to an
optimization problem. PORE relies on the item probabilities $p_{i}$’s to make
recommendations. Moreover, the optimization problem to calculate $r$ also
involves item probabilities. However, it is challenging to compute the exact
item probabilities as it requires building ${n\choose s}$ base recommender
systems. To address the challenge, we design an efficient algorithm to
estimate the lower/upper bounds of the item probabilities via building
$T\ll{n\choose s}$ base recommender systems, where the $T$ base recommender
systems can be built in parallel. PORE makes recommendations based on the
estimated item probabilities in practice. Moreover, we use the estimated item
probabilities to solve the optimization problem to obtain $r$ for each user.

We empirically evaluate PORE on three benchmark datasets, i.e.,
MovieLens-100k, MovieLens-1M, and MovieLens-10M. Moreover, we consider two
state-of-the-art base algorithms, i.e., Item-based Recommendation (IR) [3] and
Bayesian Personalized Ranking (BPR) [29], to show the generality of PORE. We
also generalize state-of-the-art provably robust defense [19] against data
poisoning attacks for machine learning classifiers to recommender systems and
compare PORE with it. We have three key observations from our experimental
results. First, PORE substantially outperforms the defense generalized from
classifiers. Second, when there are no data poisoning attacks, PORE has
comparable recommendation performance (i.e., Precision@$N$, Recall@$N$, and
F1-Score@$N$) with a standard recommender system built on the entire rating-
score matrix. Third, under any data poisoning attacks, PORE can guarantee a
lower bound of recommendation performance, while the standard recommender
systems cannot.

Our key contributions are summarized as follows:

  * •

We propose PORE, the first framework to build recommender systems that are
provably robust against untargeted data poisoning attacks.

  * •

We prove the robustness guarantees of PORE and derive its certified
intersection size. Moreover, we design an algorithm to compute the certified
intersection size.

  * •

We perform extensive evaluation on popular benchmark datasets using two state-
of-the-art base recommender system algorithms.

##  2 Background

Figure 1: _Left_ : a recommender system without data poisoning attacks.
_Right_ : an attacker manipulates the recommended items for users $u_{1}$ and
$u_{3}$ by injecting a fake user (i.e., $u_{5}$) into the system.

###  2.1 Recommender Systems

Rating-score matrix: Suppose we have $n$ users and $m$ items which are denoted
as $\mathcal{U}=\\{u_{1},u_{2},\cdots,u_{n}\\}$ and
$\mathcal{I}=\\{i_{1},i_{2},\cdots,i_{m}\\}$, respectively. We use
$\mathbf{M}$ to denote the rating-score matrix which has $n$ rows and $m$
columns, where a row corresponds to a user and a column corresponds to an
item. Essentially, the rating-score matrix $\mathbf{M}$ captures the users’
interests towards different items. In particular, an entry $\mathbf{M}_{ui}$
represents the rating score that the user $u$ gave to the item $i$. For
instance, the rating score could be an integer in the range $[1,5]$, where $1$
is the lowest rating score and denotes that the item does not attract the
user’s interest, and $5$ is the largest rating score and denotes that the item
attracts the user’s interest substantially. We note that our method is
applicable to any type of rating scores, e.g., binary, integer-valued, and
continuous. $\mathbf{M}_{ui}=0$ means that the user $u$ has not rated the item
$i$ yet. For convenience, we denote by $\mathcal{R}$ the domain of a rating
score including 0, i.e., $\mathbf{M}_{ui}\in\mathcal{R}$.

Top-$N$ recommended items: A recommender system aims to help users discover
new items that may arouse his/her interests. A recommender system algorithm
takes the rating-score matrix $\mathbf{M}$ as input and recommends top-$N$
items to each user that he/she has not rated yet but is potentially interested
in. For simplicity, we use $\mathcal{A}$ to denote a recommender system
algorithm. Moreover, we use $\mathcal{A}(\mathbf{M},u)$ to denote the set of
top-$N$ items recommended to user $u$ when the recommender system is built by
$\mathcal{A}$ on $\mathbf{M}$.

Recommender system algorithms: Many algorithms have been proposed to build
recommender systems such as Item-based Recommendation (IR) [31, 24, 3],
Bayesian Personalized Ranking (BPR) [29], Matrix Factorization [21], Neural
Collaborative Filtering (NCF) [16], and LightGCN [15]. For instance, IR
calculates the similarities between different items based on their rating
scores, predicts users’ missing rating scores using such similarities, and
recommends a user the $N$ items that the user has not rated yet but have the
largest predicted rating scores. Due to its scalability, IR has been widely
deployed in industry, e.g., Amazon [24]. According to recent benchmarks
released by Microsoft [2], BPR achieves state-of-the-art performance, e.g.,
BPR even outperforms more complex algorithms such as NCF [16] and LightGCN
[15].

###  2.2 Data Poisoning Attacks

Many studies [22, 27, 23, 42, 12, 11, 18] showed that recommender systems are
not robust to data poisoning attacks (Section 6 discusses more details). In a
data poisoning attack, an attacker creates fake users in a recommender system
and assigns carefully crafted rating scores to them, such that the recommender
system, which is built based on the rating scores of genuine and fake users,
makes attacker-desired, arbitrary recommendations. For instance, a data
poisoning attack could substantially degrade the performance of a recommender
system; and a data poisoning attack could promote certain items (e.g., videos
on YouTube and products on Amazon) via spoofing a recommender system to
recommend them to many genuine users. Figure 1 illustrates data poisoning
attacks.

We denote by $\mathbf{M}^{\prime}$ the _poisoned-rating-score matrix_. A data
poisoning attack aims to reduce the intersection between
$\mathcal{A}(\mathbf{M},u)$ and $\mathcal{A}(\mathbf{M}^{\prime},u)$ via
carefully designing the rating scores of the fake users. Different attacks
essentially assign different rating scores to the fake users.

##  3 Problem Formulation

Threat model: We assume an attacker can inject fake users into a recommender
system via registering and maintaining fake accounts [36]. We consider an
attacker can inject at most $e$ fake users into a recommender system, e.g.,
because of limited resources to register and maintain fake accounts. However,
we assume each fake user can arbitrarily rate as many items as the attacker
desires. Moreover, we assume the attacker has whitebox access to the
recommender system, e.g., the attacker has access to the rating scores of all
genuine users as well as the recommender system algorithm and its parameters.
In other words, we consider strong attackers, who can perform any data
poisoning attacks.

A poisoned-rating-score matrix $\mathbf{M}^{\prime}$ extends the rating-score
matrix $\mathbf{M}$ by at most $e$ rows, which correspond to the rating scores
of the at most $e$ fake users. Different data poisoning attacks essentially
select different rating scores for the fake users and result in different
poisoned-rating-score matrix $\mathbf{M}^{\prime}$. We use
$\mathcal{L}(\mathbf{M},e)$ to denote the set of all possible poisoned-rating-
score matrices when the clean rating-score matrix is $\mathbf{M}$ and the
number of fake users is at most $e$. $\mathcal{L}(\mathbf{M},e)$ essentially
denotes all possible data poisoning attacks with at most $e$ fake users.
Formally, we define $\mathcal{L}(\mathbf{M},e)$ as follows:

$\displaystyle\mathcal{L}(\mathbf{M},e)=\\{\mathbf{M}^{\prime}|\mathbf{M}^{\prime}_{ui}=\mathbf{M}_{ui}\text{
and }\mathbf{M}^{\prime}_{vi}\in\mathcal{R},$ $\displaystyle\forall
u\in\mathcal{U},v\in\mathcal{V},i\in\mathcal{I}\\},$ (1)

where $\mathcal{R}$ is the domain of a rating score, $\mathcal{U}$ is the set
of genuine users, $\mathcal{V}$ is the set of at most $e$ fake users (i.e.,
$|\mathcal{V}|\leq e$), and $\mathcal{I}$ is the set of items.

Figure 2: Robustness of our ensemble recommender system against data poisoning
attacks.

Provably robust recommender system algorithm: We say a recommender system
algorithm is provably robust against data poisoning attacks if a certain
number of its recommended top-$N$ items for a user are provably unaffected by
any data poisoning attacks. Specifically, given a set of items
$\mathcal{I}_{u}$, we say a recommender system algorithm $\mathcal{A}$ is
provably robust for a user $u$ if it satisfies the following property:

$\displaystyle\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}|\mathcal{I}_{u}\cap\mathcal{A}(\mathbf{M}^{\prime},u)|\geq
r,$ (2)

where $\mathcal{L}(\mathbf{M},e)$ is the set of all possible poisoned-rating-
score matrices (i.e., all possible data poisoning attacks with at most $e$
fake users), $|\mathcal{I}_{u}\cap\mathcal{A}(\mathbf{M}^{\prime},u)|$ is the
size of the intersection between $\mathcal{I}_{u}$ and the top-$N$ items
recommended to $u$ by $\mathcal{A}$ under attacks, and $r$ is called
_certified intersection size_. Note that $r$ may depend on the user $u$ and
the number of fake users $e$, but we omit its explicit dependency on $u$ and
$e$ for simplicity.

When $\mathcal{I}_{u}$ is the set of top-$N$ items recommended to user $u$ by
$\mathcal{A}$ under no attacks, i.e.,
$\mathcal{I}_{u}=\mathcal{A}(\mathbf{M},u)$, our provable robustness means
that at least $r$ of the $N$ items in $\mathcal{A}(\mathbf{M},u)$ are still
recommended to $u$ under any attacks with at most $e$ fake users. When
$\mathcal{I}_{u}$ is the set of ground truth test items for $u$ (i.e., the set
of items that $u$ is indeed interested in), our provable robustness means that
at least $r$ of the ground truth test items are recommended to $u$ under
attacks. As we will discuss more details in experiments, $r$ in the latter
case can be used to derive a lower bound of recommendation performance such as
Precision@$N$, Recall@$N$, and F1-Score@$N$ under any data poisoning attacks.
We formally define a provably robust recommender system algorithm as follows:

######  Definition 1 ($(e,r)$-Provably Robust Recommender System).

Suppose the number of fake users is at most $e$ and a data poisoning attack
can arbitrarily craft the rating scores for the fake users. We say a
recommender system algorithm $\mathcal{A}$ is $(e,r)$-provably robust for a
user $u$ if its certified intersection size for $u$ is at least $r$, i.e., if
Equation (2) is satisfied.

##  4 Our PORE

We first give an overview of our PORE, then define our ensemble recommender
system and show it is $(e,r)$-provably robust, and finally describe our
algorithm to compute the certified intersection size $r$ for each user.

###  4.1 Overview

Our key intuition is that, when the number of fake users is bounded, a random
subset of a small number of users is likely to only include genuine users.
Therefore, a recommender system built using the rating scores of such a random
subset of users is not affected by fake users. Based on the intuition, PORE
builds multiple recommender systems using random subsets of users and takes
majority vote among them to recommend items for users.

Specifically, we create multiple submatrices from a rating-score matrix, where
each submatrix contains the rating scores of $s$ different randomly selected
users, i.e., $s$ rows randomly selected from the rating-score matrix. Then, we
use an arbitrary base algorithm to build a recommender system (called _base
recommender system_) on each submatrix and use it to recommend items for
users. Finally, we build an _ensemble recommender system_ , which takes a
majority vote among the base recommender systems as the final recommended
items for each user. Figure 2 shows our ensemble recommender system and its
robustness against data poisoning attacks.

Next, we first formally define our ensemble recommender system in PORE. Then,
we show PORE is provably robust against data poisoning attacks. In particular,
given an arbitrary set of items $\mathcal{I}_{u}$ for a user $u$, we prove
that at least $r$ of the top-$N$ items recommended to $u$ by PORE are
guaranteed to be among $\mathcal{I}_{u}$ under any data poisoning attacks.
Moreover, we derive the certified intersection size $r$. Finally, we design an
algorithm to compute the certified intersection sizes $r$ for all users
simultaneously.

###  4.2 Our Ensemble Recommender System

Item probability $p_{i}$: Given a rating-score matrix $\mathbf{M}$, we
randomly sample a submatrix with $s$ rows of $\mathbf{M}$, i.e., the submatrix
consists of the rating scores of $s$ different randomly selected users. For
convenience, we denote by $\mathbf{X}$ the sampled submatrix. Then, we use an
arbitrary base algorithm $\mathcal{A}$ to build a base recommender system on
the sampled submatrix $\mathbf{X}$. We use the base recommender system to
recommend top-$N^{\prime}$ items (denoted as $\mathcal{A}(\mathbf{X},u)$) to
each user $u$ in the sampled submatrix. Since the submatrix is randomly
sampled, the recommended top-$N^{\prime}$ items are also random. To consider
such randomness, we denote by $p_{i}$ the probability that item $i$ is
recommended to a user $u$. Formally, we define $p_{i}$ as follows:
$p_{i}=\text{Pr}(i\in\mathcal{A}(\mathbf{X},u))$. We call $p_{i}$ _item
probability_.

Note that we consider $\mathcal{A}(\mathbf{X},u)$ is an empty set when $u$ is
not in the sampled submatrix $\mathbf{X}$, as many recommender systems make
recommendations for users in the rating-score matrix that was used to build
the recommender systems. Since a base recommender system is built using $s$
rows of the rating-score matrix $\mathbf{M}$, we can build ${n\choose s}$ base
recommender systems in total, where $n$ is the total number of users/rows in
$\mathbf{M}$. Essentially, our item probability $p_{i}$ is the fraction of the
${n\choose s}$ base recommender systems that recommend item $i$ to the user
$u$.

Poisoned item probability $p_{i}^{\prime}$: Under data poisoning attacks, the
rating-score matrix $\mathbf{M}$ becomes a poisoned version
$\mathbf{M}^{\prime}$. We denote by $\mathbf{Y}$ a random submatrix with $s$
rows sampled from $\mathbf{M}^{\prime}$. Moreover, we define _poisoned item
probability_ $p_{i}^{\prime}=\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))$, i.e.,
$p_{i}^{\prime}$ is the probability that the item $i$ is in the
top-$N^{\prime}$ items recommended to $u$ when the base recommender system is
built based on $\mathbf{Y}$.

Our ensemble recommender system $\mathcal{T}$: Our ensemble recommender system
(denoted as $\mathcal{T}$) recommends the top-$N$ items with the largest item
probabilities $p_{i}$’s for a user $u$. Essentially, our ensemble recommender
system takes a majority vote among the ${n\choose s}$ base recommender
systems. In particular, our ensemble recommender system essentially recommends
the top-$N$ items that are the most frequently recommended by the ${n\choose
s}$ base recommender systems to a user. For simplicity, we use
$\mathcal{T}(\mathbf{M},u)$ to denote the set of top-$N$ items recommended to
the user $u$ by our ensemble recommender system $\mathcal{T}$ when the rating-
score matrix is $\mathbf{M}$. Note that $N^{\prime}$ and $N$ are different
parameters, i.e., $N^{\prime}$ is the number of items recommended to a user by
a base recommender system while $N$ is the number of items recommended to a
user by our ensemble recommender system. We will explore their impact on our
ensemble recommender system in experiments.

Under data poisoning attacks, our ensemble recommender system $\mathcal{T}$
uses the poisoned item probabilities to make recommendations. Specifically,
$\mathcal{T}(\mathbf{M}^{\prime},u)$ is the set of top-$N$ items with the
largest poisoned item probabilities $p_{i}^{\prime}$’s that are recommended to
$u$ by $\mathcal{T}$ under attacks.

###  4.3 Deriving the Certified Intersection Size

We show that our ensemble recommender system algorithm $\mathcal{T}$ is
$(e,r)$-provably robust. In particular, for any given number of fake users
$e$, we can derive the certified intersection size $r$ of $\mathcal{T}$ for
any user $u$. Specifically, given an arbitrary set of items $\mathcal{I}_{u}$,
we show that at least $r$ of the recommended top-$N$ items
$\mathcal{T}(\mathbf{M}^{\prime},u)$ are in $\mathcal{I}_{u}$ when there are
at most $e$ fake users, no matter what rating scores they use. Later, we can
replace $\mathcal{I}_{u}$ as our desired sets of items. Formally, we aim to
show the following:
$\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|\geq
r$, where $\mathcal{L}(\mathbf{M},e)$ is the set of all possible poisoned-
rating-score matrices and denotes all data poisoning attacks with at most $e$
fake users. Next, we first overview our main idea and then show our theorem.

Overview of our derivation: Our proof is based on the _law of contraposition_.
Suppose we have a statement: $U\longrightarrow V$, whose contraposition is
$\neg V\longrightarrow\neg U$. The law of contraposition means that a
statement is true if and only if its contraposition is true. We define a
predicate $V$ as
$V:|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|\geq r$. The
predicate $V$ is true if at least $r$ of the top-$N$ items recommended by
$\mathcal{T}$ for $u$ are in $\mathcal{I}_{u}$ when the poisoned-rating-score
matrix is a given $\mathbf{M}^{\prime}$. Then, we derive a necessary condition
(denoted as $\neg U$) for $\neg V$ to be true, i.e., we have $\neg
V\longrightarrow\neg U$. By the law of contraposition, we know that $V$ is
true if $U$ is true. Roughly speaking, $U$ means that the $r$th largest
poisoned item probability for items in $\mathcal{I}_{u}$ is larger than the
$(N-r+1)$th largest poisoned item probability for items in
$\mathcal{I}\setminus\mathcal{I}_{u}$, when the poisoned-rating-score matrix
is $\mathbf{M}^{\prime}$.

The challenge in deriving the condition for $U$ to be true is that it is hard
to compute the poisoned item probabilities $p_{i}^{\prime}$’s due to the
complexity of recommender system. To address the challenge, we resort to
derive a lower bound of $p_{i}^{\prime}$ for each $i\in\mathcal{I}_{u}$ and an
upper bound of $p_{j}^{\prime}$ for each
$j\in\mathcal{I}\setminus\mathcal{I}_{u}$. In particular, we derive the
lower/upper bounds of poisoned item probabilities using lower/upper bounds of
item probabilities. We consider lower/upper bounds of item probabilities
instead of their exact values, because it is challenging to compute them
exactly. Suppose we have a lower bound $\underline{p_{i}}$ of $p_{i}$ for each
$i\in\mathcal{I}_{u}$ and an upper bound $\overline{p}_{j}$ of $p_{j}$ for
each $j\in\mathcal{I}\setminus\mathcal{I}_{u}$, i.e., we have the following:

$\displaystyle p_{i}\geq\underline{p_{i}}\text{ and
}p_{j}\leq\overline{p}_{j},$ (3)

where $i\in\mathcal{I}_{u}$ and $j\in\mathcal{I}\setminus\mathcal{I}_{u}$. In
the next section, we design an algorithm to estimate such lower/upper bounds
of item probabilities. Given the lower/upper bounds $\underline{p_{i}}$ and
$\overline{p}_{j}$, we derive a lower bound of $p_{i}^{\prime}$ for each
$i\in\mathcal{I}_{u}$ and an upper bound of $p_{j}^{\prime}$ for each
$j\in\mathcal{I}\setminus\mathcal{I}_{u}$ via a variant Neyman-Pearson Lemma
[28] that we develop. Our variant is applicable to multiple functions, while
the standard Neyman-Pearson Lemma is only applicable to one function.

Next, we show our intuition to derive the upper and lower bounds (please refer
to the proof of Theorem 1 for formal analysis) of the poisoned item
probabilities. We denote by $\Phi$ the union of the domain spaces of
$\mathbf{X}$ and $\mathbf{Y}$, i.e., each element in $\Phi$ is a submatrix
with $s$ rows sampled from $\mathbf{M}$ or $\mathbf{M}^{\prime}$. Our idea is
to find subsets in $\Phi$ such that we can apply our variant of the Neyman-
Pearson Lemma to derive the upper/lower bounds of the poisoned item
probabilities. Moreover, the upper/lower bounds are related to the
probabilities that the random submatrices $\mathbf{X}$ and $\mathbf{Y}$ are in
the subsets, which can be easily computed. We denote by $P$ (or $A$) the set
of submatrices sampled from $\mathbf{M}$ (or $\mathbf{M}^{\prime}$) that
include the user $u$.

Deriving a lower bound of $p_{i}^{\prime}$, $i\in\mathcal{I}_{u}$: We can find
a subset $C_{i}\subseteq P$ such that we have $\text{Pr}(\mathbf{X}\in
C_{i})=p_{i}^{*}\triangleq\frac{\lfloor\underline{p_{i}}\cdot{n\choose
s}\rfloor}{{n\choose s}}$. Note that we can find such a subset because
$p_{i}^{*}$ is an integer multiple of $1/{n\choose s}$. Then, via our variant
of the Neyman-Pearson Lemma, we can derive a lower bound of $p_{i}^{\prime}$
using the probability that the random submatrix $\mathbf{Y}$ is in the subset
$C_{i}$, i.e., we have: $p_{i}^{\prime}\geq\text{Pr}(\mathbf{Y}\in C_{i}),\
\forall i\in\mathcal{I}_{u}$.

Deriving an upper bound of $p_{j}^{\prime}$,
$j\in\mathcal{I}\setminus\mathcal{I}_{u}$: We first find a subset
$C_{j}^{\prime}\subseteq P$ such that we have the following:
$\text{Pr}(\mathbf{X}\in
C_{j}^{\prime})=\overline{p}^{*}_{j}=\frac{\lceil\overline{p}_{j}\cdot{n\choose
s}\rceil}{{n\choose s}}$. Given the subset $C_{j}^{\prime}$, we further define
a subset $C_{j}=C_{j}^{\prime}\cup(A\setminus P)$. Then, based on our variant
of the Neyman-Pearson Lemma, we derive an upper bound of $p_{j}^{\prime}$
using the probability that the random submatrix $\mathbf{Y}$ is in the subset
$C_{j}$, i.e., we have:

$\displaystyle p_{j}^{\prime}\leq\text{Pr}(\mathbf{Y}\in C_{j}).$ (4)

In our derivation, we further improve the upper bound via jointly considering
multiple items in $\mathcal{I}\setminus\mathcal{I}_{u}$. Suppose
$\mathcal{H}_{c}\subseteq\mathcal{I}\setminus\mathcal{I}_{u}$ is a set of $c$
items. We denote
$\overline{p}_{\mathcal{H}_{c}}=\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j}$.
Then, we can find a subset $C_{\mathcal{H}_{c}}^{\prime}$ such that we have
the following: $\text{Pr}(\mathbf{X}\in
C^{\prime}_{\mathcal{H}_{c}})=\overline{p}^{*}_{\mathcal{H}_{c}}\triangleq\frac{\lceil(\overline{p}_{\mathcal{H}_{c}}/N^{\prime})\cdot{n\choose
s}\rceil}{{n\choose s}}$. Given the subset $C_{\mathcal{H}_{c}}^{\prime}$, we
further define a subset
$C_{\mathcal{H}_{c}}=C_{\mathcal{H}_{c}}^{\prime}\cup(A\setminus P)$. Then, we
have the following upper bound for the smallest poisoned item probability in
the set $\\{p_{j}^{\prime}|j\in\mathcal{H}_{c}\\}$:

$\displaystyle\min_{j\in\mathcal{H}_{c}}p_{j}^{\prime}\leq\frac{N^{\prime}\cdot\text{Pr}(\mathbf{Y}\in
C_{\mathcal{H}_{c}})}{c}.$ (5)

Finally, we can combine the upper bounds in Equation (4) and (5) to derive an
upper bound of the $(N-r+1)$th largest poisoned item probability in
$\mathcal{I}\setminus\mathcal{I}_{u}$. Note that we don’t jointly consider
multiple items in $\mathcal{I}_{u}$ when deriving the lower bounds for
poisoned item probabilities in $\mathcal{I}_{u}$ because it does not improve
the lower bounds.

Formally, we have the following theorem:

######  Theorem 1.

Suppose we have a rating-score matrix $\mathbf{M}$, a user $u$, and an
arbitrary set of $k$ items
$\mathcal{I}_{u}=\\{\mu_{1},\mu_{2},\cdots,\mu_{k}\\}$. Furthermore, we have a
lower bound $\underline{p_{i}}$ for each $i\in\mathcal{I}_{u}$ and an upper
bound $\overline{p}_{j}$ for each $j\in\mathcal{I}\setminus\mathcal{I}_{u}$
that satisfy Equation (3). Without loss of generality, we assume
$\underline{p_{\mu_{1}}}\geq\underline{p_{\mu_{2}}}\geq\cdots\geq\underline{p_{\mu_{k}}}$.
Under any data poisoning attacks with at most $e$ fake users, we have the
following guarantee:
$\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|\geq
r$, where $r$ is the solution to the following optimization problem or $0$ if
it does not have a solution:

$\displaystyle r$
$\displaystyle=\operatornamewithlimits{argmax}_{r^{\prime}\in\\{1,2,\cdots,\min(k,N)\\}}r^{\prime}$
s.t.
$\displaystyle\underline{p^{*}_{\mu_{r^{\prime}}}}>\min(\min_{c=1}^{N-r^{\prime}+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}+\sigma)}{c},\overline{p}^{*}_{v_{1}}+\sigma),$
(6)

where $n^{\prime}=n+e$,
$\sigma=\frac{s}{n^{\prime}}\cdot\frac{{n^{\prime}\choose s}}{{n\choose
s}}-\frac{s}{n}$ ,
$\underline{p^{*}_{\mu_{r^{\prime}}}}=\frac{\lfloor\underline{p_{\mu_{r^{\prime}}}}\cdot{n\choose
s}\rfloor}{{n\choose s}}$, $\mathcal{H}_{c}=\\{v_{1},v_{2},\cdots,v_{c}\\}$ is
the set of $c$ items that have the smallest item-probability upper bounds
among the $N-r^{\prime}+1$ items with the largest item-probability upper
bounds in $\mathcal{I}\setminus\mathcal{I}_{u}$, $v_{1}$ is the item in
$\mathcal{H}_{1}$,
$\overline{p}_{\mathcal{H}_{c}}=\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j}$,
$\overline{p}^{*}_{\mathcal{H}_{c}}=\frac{\lceil(\overline{p}_{\mathcal{H}_{c}}/N^{\prime})\cdot{n\choose
s}\rceil}{{n\choose s}}$, and
$\overline{p}^{*}_{v_{1}}=\frac{\lceil\overline{p}_{v_{1}}\cdot{n\choose
s}\rceil}{{n\choose s}}$.

###### Proof.

See Appendix A. ∎

###  4.4 Computing the Certified Intersection Size

Given a base algorithm $\mathcal{A}$, a rating-score matrix $\mathbf{M}$, a
set of genuine users $\mathcal{U}=\\{u_{1},u_{2},\cdots,u_{n}\\}$, a set of
items $\mathcal{I}_{u}$ for each genuine user $u$, the maximum number of fake
users $e$, and a sampling size $s$, we aim to compute the certified
intersection size of our ensemble recommender system for each user in
$\mathcal{U}$. The key to compute the certified intersection size is to solve
$r$ in the optimization problem in Equation (1). Specifically, given a user
$u$, the key challenge to solve the optimization problem in Equation (1) is
how to estimate the item-probability lower bounds $\underline{p_{i}}$ for
$\forall i\in\mathcal{I}_{u}$ and upper bounds $\overline{p}_{j}$ for $\forall
j\in\mathcal{I}\setminus\mathcal{I}_{u}$. One naive way is to build ${n\choose
s}$ base recommender systems and compute the exact item probabilities.
However, such approach is computationally infeasible as ${n\choose s}$ is
huge. To address the challenge, we design an algorithm to estimate lower/upper
bounds of item probabilities via building $T<<{n\choose s}$ base recommender
systems. Next, we introduce estimating the lower/upper bounds of the item
probabilities, solving $r$ using the estimated item-probability bounds, and
our complete algorithm.

Estimating the item-probability lower/upper bounds: We randomly sample $T$
submatrices from $\mathbf{M}$, where each submatrix contains $s$ rows of
$\mathbf{M}$. For simplicity, we denote them as
$\Gamma_{1},\Gamma_{2},\cdots,\Gamma_{T}$. Then, we build a base recommender
system for each submatrix $\Gamma_{t}$ using the base algorithm $\mathcal{A}$,
where $t=1,2,\cdots,T$. Given a user $u$, we use each base recommender system
to recommend top-$N^{\prime}$ items for the user. We denote by
$\mathcal{A}(\Gamma_{t},u)$ the set of top-$N^{\prime}$ items recommended to
the user $u$ by the base recommender system built on the submatrix
$\Gamma_{t}$. Note that $\mathcal{A}(\Gamma_{t},u)$ is empty if the user $u$
is not in the submatrix $\Gamma_{t}$. We denote by $T_{i}$ the frequency of an
item $i$ among the recommended top-$N^{\prime}$ items of the $T$ base
recommender systems, i.e., $T_{i}$ is the number of base recommender systems
whose top-$N^{\prime}$ recommended items for $u$ include $i$. Based on the
definition of item probability $p_{i}$, the frequency $T_{i}$ follows a
binomial distribution with parameters $T$ and $p_{i}$, i.e., we have the
following: $\text{Pr}(T_{i}=t)={T\choose t}\cdot
p_{i}^{t}\cdot(1-p_{i})^{T-t}$, where $t=0,1,\cdots,T$. Our goal is to
estimate a lower or upper bound of $p_{i}$ given $T_{i}$ and $T$. This is
essentially a _binomial proportion confidence interval_ estimation problem.
Therefore, we can leverage the standard Clopper-Pearson method [10] to
estimate a lower or upper bound of $p_{i}$ from a given $T_{i}$ and $T$.
Formally, we have the following:

$\displaystyle\underline{p_{i}}$
$\displaystyle=\text{Beta}(\frac{\alpha_{u}}{m};T_{i},T-T_{i}+1),i\in\mathcal{I}_{u},$
(7) $\displaystyle\overline{p}_{j}$
$\displaystyle=\text{Beta}(1-\frac{\alpha_{u}}{m};T_{j},T-T_{j}+1),j\in\mathcal{I}\setminus\mathcal{I}_{u},$
(8)

where $1-\alpha_{u}/m$ is the confidence level for estimating the lower/upper
bound of one item probability, $m$ is the total number of items, and
$\text{Beta}(\beta;\varsigma,\vartheta)$ is the $\beta$th quantile of the Beta
distribution with shape parameters $\varsigma$ and $\vartheta$. Based on
_Bonferroni correction_ in statistics, the _simultaneous confidence level_ of
estimating the lower/upper bounds of the $m$ item probabilities is at least
$1-\alpha_{u}$. Given an item set $\mathcal{H}_{c}$ defined in Theorem 1, we
can estimate $\overline{p}_{\mathcal{H}_{c}}$ as
$\overline{p}_{\mathcal{H}_{c}}=\min(\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j},N^{\prime}-\sum_{i\in\mathcal{I}_{u}}\underline{p_{i}})$,
where both $\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j}$ and
$N^{\prime}-\sum_{i\in\mathcal{I}_{u}}\underline{p_{i}}$ are upper bounds of
${p}_{\mathcal{H}_{c}}$, and we use the smaller one.

Input: $e$, $s$, $N^{\prime}$, $N$,
$\mathcal{I}_{u},\\{\underline{p_{i}}|i\in\mathcal{I}_{u}\\}$, and
$\\{\overline{p}_{j}|j\in\mathcal{I}\setminus\mathcal{I}_{u}\\}$

1 Output: $r_{u}$

2$low,high\leftarrow 1,\min(|\mathcal{I}_{u}|,N)$

while $low<high$ do

3 $r^{\prime}=\lceil(low+high)/2\rceil$

if
VerifyConstraint($r^{\prime},e,s,N^{\prime},N,\mathcal{I}_{u},\\{\underline{p_{i}}|i\in\mathcal{I}_{u}\\},\\{\overline{p}_{j}|j\in\mathcal{I}\setminus\mathcal{I}_{u}\\}$)
$==1$ then

4 $low\leftarrow r^{\prime}$

else

5 $high\leftarrow r^{\prime}-1$

end if

end while

if
VerifyConstraint($r^{\prime},e,s,N^{\prime},N,\mathcal{I}_{u},\\{\underline{p_{i}}|i\in\mathcal{I}_{u}\\},\\{\overline{p}_{j}|j\in\mathcal{I}\setminus\mathcal{I}_{u}\\}$)
$==1$ then

6 return $r^{\prime}$

else

7 return $0$

end if

Algorithm 1 BinarySearch

Solving the optimization problem: We note that Equation (1) has the following
property: its left-hand side and right-hand side respectively decreases and
increases as $r^{\prime}$ increases. Thus, given the estimated item-
probability bounds, we can efficiently solve the optimization problem in
Equation (1) via binary search to obtain $r_{u}$ for each user $u$. Algorithm
1 shows our BinarySearch algorithm. The function VerifyConstraint verifies
whether the constraint in Equation (1) is satisfied for a given $r^{\prime}$
and returns 1 if so.

Input: $\mathbf{M}$, $s$, $T$, $\mathcal{A}$, $N^{\prime}$, $\alpha$, $e$,
$N$, $\mathcal{U}$, and $\\{\mathcal{I}_{u}|u\in\mathcal{U}\\}$

1 Output: $r_{u}$ for each user $u\in\mathcal{U}$

2$\Gamma_{1},\Gamma_{2},\cdots,\Gamma_{T}\leftarrow\textsc{RandomSample}(\mathbf{M},s)$

for $u$ in $\mathcal{U}$ do

3
counts$[i]\leftarrow\sum_{t=1}^{T}\mathbb{I}(i\in\mathcal{A}(\Gamma_{t},u)),i\in\\{1,2,\cdots,m\\}$

4
$\underline{p_{i}},\overline{p}_{j}\leftarrow\textsc{BoundEst}(\text{counts},\frac{\alpha}{n}),i\in\mathcal{I}_{u},j\in\mathcal{I}\setminus\mathcal{I}_{u}$

$r_{u}=\textsc{BinarySearch}(e,s,N^{\prime},N,\mathcal{I}_{u},\\{\underline{p_{i}}|i\in\mathcal{I}_{u}\\},\\{\overline{p}_{j}|j\in\mathcal{I}\setminus\mathcal{I}_{u}\\})$

end for

return $\\{r_{u}|u\in\mathcal{U}\\}$

Algorithm 2 Compute $r$

Complete algorithm: Algorithm 2 shows our complete algorithm to compute the
certified intersection size $r_{u}$ for each user
$u\in\mathcal{U}=\\{u_{1},u_{2},\cdots,u_{n}\\}$. The function RandomSample
randomly samples $T$ submatrices, each of which contains $s$ rows sampled from
$\mathbf{M}$ uniformly at random. BoundEst estimates the item-probability
bounds with a confidence level $1-\frac{\alpha}{n}$, i.e.,
$\alpha_{u}=\frac{\alpha}{n}$, for each user $u\in\mathcal{U}$, based on
Equation (7) - (8). BinarySearch solves the optimization problem in Equation
(1) via binary search to obtain $r_{u}$ for $u$ based on the estimated item-
probability bounds. Note that Algorithm 2 requires a clean rating-score matrix
$\mathbf{M}$, which may be sampled from the clean data distribution.

Due to randomness, the estimated item-probability bounds may be incorrect,
e.g., an estimated item-probability lower bound is larger than the true item
probability for some item and some user or an estimated item-probability upper
bound is smaller than the true item probability for some item and some user.
When such estimation error happens for a user $u$, the solved certified
intersection size $r_{u}$ is incorrect for $u$. Since the simultaneous
confidence level of estimating the item-probability bounds in our algorithm is
at least $1-\frac{\alpha}{n}$ for any user $u\in\mathcal{U}$, the probability
of having at least one incorrectly estimated item-probability bound for any
user $u\in\mathcal{U}$ is at most $\frac{\alpha}{n}$. Moreover, our following
theorem shows that the probability of having an incorrect certified
intersection size $r_{u}$ for at least one user in $\mathcal{U}$ is bounded by
$\alpha$:

######  Theorem 2.

The probability that our Algorithm 2 returns an incorrect $r_{u}$ for at least
one user in $\mathcal{U}$ is at most $\alpha$.

###### Proof.

See Appendix B. ∎

##  5 Evaluation

###  5.1 Experimental Setup

Datasets: We mainly evaluate PORE on MovieLens-100k and MovieLens-1M benchmark
datasets [1, 14], which consist of around $100,000$ and $1,000,000$ rating
scores, respectively. Specifically, MovieLens-100k contains $943$ users and
$1,682$ items, where each user rated $106$ items on average. MovieLens-1M
contains $6,040$ users and $3,952$ items, where each user on average rated
$166$ items. Following [3], for each user, we sample $75\%$ of its rating
scores as training data and treat its remaining rated items as test items. The
users’ training data form the rating-score matrix and are used to build
recommender systems, while their test items are used to evaluate the
performance of the recommended top-$N$ items.

Base algorithms: PORE is applicable to any base algorithm. To show such
generality, we evaluate two base algorithms, i.e., Item-based Recommendation
(IR) [3] and Bayesian Personalized Ranking (BPR) [29]. We adopt their public
implementations [3]. We adopt IR because it has been widely deployed in
industry [24]. We adopt BPR because it achieves state-of-the-art performance
according to recent benchmarks released by Microsoft [2].

Figure 3: Our PORE outperforms bagging when extended from classifiers to
recommender systems on MovieLens-100k (left three) and MovieLens-1M (right
three), where $N=10$ and base algorithm is IR.

Figure 4: Impact of $N^{\prime}$ on the certified Precision@$N$, certified
Recall@$N$, and certified F1-Score@$N$ of ensemble IR for MovieLens-100k (left
three) and MovieLens-1M (right three), where $N=10$.

Evaluation metrics: When there are no data poisoning attacks, _Precision@
$N$_, _Recall@ $N$_, and _F1-Score@ $N$_ are standard metrics to evaluate the
performance of a recommender system. We denote by $\mathcal{E}_{u}$ the set of
test items for a user $u$. Precision@$N$ for a user $u$ is the fraction of the
top-$N$ items recommended for $u$ that are in $\mathcal{E}_{u}$, Recall@$N$
for $u$ is the fraction of the items in $\mathcal{E}_{u}$ that are in the
top-$N$ items recommended for $u$, while F1-Score@$N$ for a user $u$ is the
harmonic mean of the user’s Precision@$N$ and Recall@$N$. The Precision@$N$
(or Recall@$N$ or F1-Score@$N$) of a recommender system algorithm is the
users’ average Precision@$N$ (or Recall@$N$ or F1-Score@$N$).

Under data poisoning attacks, Precision@$N$, Recall@$N$, and F1-Score@$N$ are
insufficient to evaluate a recommender system algorithm. This is because they
may be different under different data poisoning attacks, and it is infeasible
to enumerate all possible attacks. To address the challenge, we propose to
evaluate a recommender system algorithm using _certified Precision@ $N$_,
_certified Recall@ $N$_, and _certified F1-Score@ $N$_ under attacks. Like the
standard Precision@$N$ (or Recall@$N$ or F1-Score@$N$), calculating our
certified Precision@$N$, certified Recall@$N$, and certified F1-Score@$N$ also
only requires a clean rating-score matrix and thus does not depend on any
specific data poisoning attack. Certified Precision@$N$ (or certified
Recall@$N$ or certified F1-Score@$N$) is a _lower bound_ of Precision@$N$ (or
Recall@$N$ or F1-Score@$N$) under any data poisoning attacks with at most $e$
fake users. For instance, a certified Precision@$N$ of 0.3 means that a
recommender system achieves at least Precision@$N$ of 0.3 when the number of
fake users is at most $e$, no matter what rating scores they use.
Specifically, our certified Precision@$N$ for a user $u$ is the least fraction
of the top-$N$ recommended items for $u$ that are guaranteed to be in
$\mathcal{E}_{u}$ when there are at most $e$ fake users; our certified
Recall@$N$ for $u$ is the least fraction of $u$’s test items $\mathcal{E}_{u}$
that are guaranteed to be in the top-$N$ recommended items; while certified
F1-Score@$N$ for a user is the harmonic mean of the user’s certified
Precision@$N$ and certified Recall@$N$. Formally, we have the following for a
user $u$:

$\displaystyle\text{Certified
Precision@}N=\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}\frac{|\mathcal{E}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|}{N},$
(9) $\displaystyle\text{Certified
Recall@}N=\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}\frac{|\mathcal{E}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|}{|\mathcal{E}_{u}|},$
(10) $\displaystyle\text{Certified
F1-Score@}N=\min_{\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)}\frac{2\cdot|\mathcal{E}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|}{|\mathcal{E}_{u}|+N},$
(11)

where $|\cdot|$ is the size of a set. We can compute the certified
Precision@$N$, certified Recall@$N$, and certified F1-Score@$N$ for each user
by Algorithm 2. In particular, we can compute certified intersection size
$r_{u}$ for each user $u$ using Algorithm 2 by letting
$\mathcal{I}_{u}=\mathcal{E}_{u}$. Given $r_{u}$, the certified Precision@$N$,
certified Recall@$N$, and certified F1-Score@$N$ for a user $u$ are at least
$\frac{r_{u}}{N}$, $\frac{r_{u}}{|\mathcal{E}_{u}|}$, and
$\frac{2r_{u}}{|\mathcal{E}_{u}|+N}$, respectively. A recommender system
algorithm’s certified Precision@$N$ (or Recall@$N$ or F1-Score@$N$) is the
average of the _genuine users’_ certified Precision@$N$ (or Recall@$N$ or
F1-Score@$N$).

Compared methods: We note that PORE is the first provably robust recommender
system algorithm against data poisoning attacks. Therefore, there are no prior
recommender system algorithms we can compare with in terms of _certified_
Precision@$N$, Recall@$N$, and F1-Score@$N$. However, Jia et al. [19] showed
that bagging can be used to build provably robust defense against data
poisoning attacks for _machine learning classifiers_ , which we extend to
recommender systems and compare with our PORE. Roughly speaking, given a
training dataset, bagging trains multiple base classifiers, each of which is
trained on a random subset of training examples in the training dataset. Given
a testing input, bagging uses each base classifier to predict its label and
takes a majority vote among the predicted labels as the final predicted label
for the testing input. Jia et al. showed that bagging can guarantee that the
predicted label for an input is provably unaffected by a bounded number of
fake training examples injected into the training dataset.

We generalize their provable guarantee to derive certified intersection size
for each genuine user in recommender systems, which can be then used to
compute certified Precision@$N$, Recall@$N$, and F1-Score@$N$ for bagging.
Specifically, we treat a user as a testing input, an item as a label, and a
base recommender system as a base classifier in the terminology of bagging.
Like our PORE, the generalized bagging builds $T$ base recommender systems and
takes majority vote among them to recommend top-$N$ items to each user. Note
that since a base classifier predicts one label for a testing input, we set
$N^{\prime}=1$, i.e., a base recommender system (i.e., a base classifier)
recommends top-1 item (i.e., predicts one label) for a user (i.e., a testing
input). Finally, for each user, bagging recommends him/her the $N$ items with
the largest (poisoned) item probabilities. Given a set of items
$\mathcal{I}_{u}$ for a user $u$, we denote by $\underline{p_{i}}$ a lower
bound of item probability $p_{i}$ of item $i\in\mathcal{I}_{u}$. We use
$\overline{p}_{l}$ to denote the largest upper bound of item probabilities of
items in $\mathcal{I}\setminus\mathcal{I}_{u}$, i.e.,
$\overline{p}_{l}=\max_{j\in\mathcal{I}\setminus\mathcal{I}_{u}}\overline{p}_{j}$.
We can estimate these item-probability bounds using our method in Equation 7
and 8. Given $\underline{p_{i}}$ and $\overline{p}_{l}$, we can compute an
integer $Z_{i}$ based on Theorem 1 in bagging [19]. Roughly speaking, bagging
can guarantee the poisoned item probability $p_{i}^{\prime}$ is larger than
$p_{l}^{\prime}$ under any data poisoning attacks with at most $Z_{i}$ fake
users. Therefore, given at most $e$ fake users, the certified intersection
size of bagging for a user $u$ can be computed as
$\min\\{\sum_{i\in\mathcal{I}_{u}}\mathbb{I}(Z_{i}\geq e),N\\}$, where
$\mathbb{I}$ is an indicator function.

We note that when bagging is extended to recommender systems, both
$N^{\prime}$ and $N$ can only be 1 when using the techniques in [19] to derive
its provable robustness guarantees. PORE can be viewed as an extension of
bagging to recommender systems, but $N^{\prime}$ and $N$ can be arbitrary
positive integers. Due to such differences, we propose new techniques to
derive the robustness guarantee of PORE. Our major technical contribution is
to derive a better guarantee for bagging applied to recommender systems.

Figure 5: Impact of $N$ on the certified Precision@$N$, certified Recall@$N$,
and certified F1-Score@$N$ of ensemble IR for MovieLens-100k (left three) and
MovieLens-1M (right three).

Figure 6: Impact of $s$ on the certified Precision@$N$, certified Recall@$N$,
and certified F1-Score@$N$ of ensemble IR for MovieLens-100k (left three) and
MovieLens-1M (right three), where $N=10$.

Parameter setting: PORE has the following parameters: $N^{\prime}$ is the
number of items recommended by a base recommender system for a user, $N$ is
the number of items recommended by our ensemble recommender system for a user,
$T$ is the number of base recommender systems, $1-\alpha$ is the confidence
score, and $s$ is the number of rows sampled from the rating-score matrix in
each submatrix. Unless otherwise mentioned, we adopt the following default
parameter settings: $N^{\prime}=1$, $N=10$, $T=100,000$, $\alpha=0.001$,
$s=200$ for MovieLens-100k, and $s=500$ for MovieLens-1M. We will study the
impact of each parameter on the certified Precision@$N$, certified Recall@$N$,
and certified F1-Score@$N$ of PORE while fixing the remaining parameters to
their default settings. We call our ensemble recommender system _ensemble IR_
(or _ensemble BPR_) when the base algorithm is IR (or BPR). By default, we use
IR as the base algorithm because of its scalability.

###  5.2 Experimental Results

We report Precision@$N$/Recall@$N$/F1-Score@$N$ under no attacks (i.e.,
$e=0$), while we report certified Precision@$N$ /Recall@$N$/F1-Score@$N$ under
attacks (i.e., $e\geq 1$).

Our PORE outperforms bagging [19]: Figure 3 compares our PORE with bagging on
the two datasets. We find that our PORE substantially outperforms bagging when
extended from classifiers to recommender systems. The reason is that PORE
jointly considers multiple items when deriving the certified intersection
size. In contrast, bagging can only consider each item independently when
extended to recommender systems, and thus achieve a suboptimal certified
intersection size.

Impact of $N^{\prime}$: Figure 4 shows the impact of $N^{\prime}$. We have two
observations. First, our method has similar
Precision@$N$/Recall@$N$/F1-Score@$N$ for different $N^{\prime}$ when there
are no attacks (i.e., $e=0$). Second, a smaller $N^{\prime}$ achieves a lower
certified Precision@$N$, certified Recall@$N$, or certified F1-Score@$N$ when
$e$ is small (e.g., $e=1$), but the curve has a longer tail. In other words, a
smaller $N^{\prime}$ is more robust against data poisoning attacks as the
number of fake users $e$ increases. The reason is that an attack has a smaller
manipulation space when $N^{\prime}$ is smaller. This observation is also
consistent with our theoretical result in Equation (1). Specifically, given
the same item-probability lower/upper bounds, a smaller $N^{\prime}$ may lead
to a larger certified intersection size. Therefore, we set $N^{\prime}$ to be
$1$ by default in our experiments.

Table 1: Precision@$10$, Recall@$10$, and F1-Score@$10$ of IR, Ensemble IR,
BPR, and Ensemble BPR under no attacks.

Algorithm | Precision@10 | Recall@10 | F1-Score@10
---|---|---|---
IR | 0.330753 | 0.176385 | 0.193783
Ensemble IR | 0.332556 | 0.178293 | 0.195624
BPR | 0.349841 | 0.181807 | 0.199426
Ensemble BPR | 0.352280 | 0.173296 | 0.193362
(a) MovieLens-100k

Algorithm | Precision@10 | Recall@10 | F1-Score@10
---|---|---|---
IR | 0.270116 | 0.104350 | 0.127704
Ensemble IR | 0.262616 | 0.103638 | 0.126191
BPR | 0.324449 | 0.118385 | 0.144765
Ensemble BPR | 0.362945 | 0.119441 | 0.151509
(b) MovieLens-1M

Figure 7: Impact of $T$ on the certified Precision@$N$, certified Recall@$N$,
and certified F1-Score@$N$ of ensemble IR for MovieLens-100k (left three) and
MovieLens-1M (right three), where $N=10$.

Figure 8: Impact of $\alpha$ on the certified Precision@$N$, certified
Recall@$N$, and certified F1-Score@$N$ of ensemble IR for MovieLens-100k (left
three) and MovieLens-1M (right three), where $N=10$.

Figure 9: Comparing the certified Precision@$N$, certified Recall@$N$, and
certified F1-Score@$N$ of ensemble IR and ensemble BPR for MovieLens-100k
(left three) and MovieLens-1M (right three), where $N=10$.

Impact of $N$: Figure 5 shows the impact of $N$. The results show that $N$
achieves a tradeoff between Precision@$N$ under no attacks (i.e., $e=0$) and
robustness under attacks. Specifically, a smaller $N$ achieves a higher
Precision@$N$ under no attacks but the certified Precision@$N$ decreases more
quickly as $e$ increases. The certified Recall@$N$ increases as $N$ increases.
The reason is that more items are recommended to each user as $N$ increases.
The certified F1-Score@$N$ drops more quickly as $e$ increases when $N$ is
smaller, because the certified Recall@$N$ drops more quickly.

Impact of $s$: Figure 6 shows the impact of $s$. We have two observations.
First, our method achieves similar Precision@$N$, Recall@$N$, and F1-Score@$N$
for different $s$ when there are no attacks (i.e., $e=0$). Second, a larger
$s$ achieves a larger certified Precision@$N$, certified Recall@$N$, or
certified F1-Score@$N$ when $e$ is small, but they decrease more quickly as
$e$ increases. This is because it’s more likely to sample fake users in a
submatrix when $s$ is larger.

Impact of $T$ and $\alpha$: Figure 7 and 8 show the impact of $T$ and
$\alpha$, respectively. We have the following observations. First,
Precision@$N$, Recall@$N$, or F1-Score@$N$ is similar for different $T$ when
there are no attacks. In other words, a small $T$ is enough for our ensemble
recommender system to achieve good recommendation performance when there are
no attacks. Second, certified Precision@$N$, certified Recall@$N$, or
certified F1-Score@$N$ increases as $T$ or $\alpha$ increases. The reason is
that a larger $T$ or $\alpha$ can produce tighter estimated item-probability
lower/upper bounds, based on which we may compute larger certified
intersection sizes $r$ in our Algorithm 2. Therefore, we use a larger $T$ by
default in our experiments to better show the certified Precision@$N$,
certified Recall@$N$, and certified F1-Score@$N$ of PORE. We also observe that
the certified Precision@$N$, certified Recall@$N$, and certified F1-Score@$N$
are insensitive to $\alpha$ once it is small enough.

Ensemble IR vs. ensemble BPR: Figure 9 compares ensemble IR and ensemble BPR.
The results show that they achieve similar certified
Precision@$N$/Recall@$N$/F1-Score@$N$. One exception is that ensemble BPR
achieves higher certified Precision@$N$ on MovieLens-1M dataset.

Standard recommender system vs. ensemble recommender system under no attacks:
Table 1b compares standard recommender systems and our ensemble recommender
systems with respect to the standard Precision@$N$, Recall@$N$, and
F1-Score@$N$ when there are no attacks, where $s=300$ for MovieLens-100k and
$s=1,000$ for MovieLens-1M. A standard recommender system leverages IR (or
BPR) to train a single recommender system on the entire rating-score matrix.
The results show that our ensemble recommender system achieves comparable
performance with a standard recommender system when there are no attacks.
Ensemble BPR achieves higher Precision@N than ensemble IR on both datasets.
The reason is that BPR achieves higher precision than IR at training the base
recommender systems.

Figure 10: Training time of PORE as a function of $s$ on MovieLens-100k (left)
and MovieLens-1M (right).

Figure 11: Training time of PORE as a function of $T$ on MovieLens-100k (left)
and MovieLens-1M (right).

Training time of ensemble IR and BPR: PORE trains $T$ base recommender
systems, each of which is trained using rating scores of $s$ users. Figure 10
shows the training time of ensemble IR/BPR as a function of $s$, while Figure
11 shows the impact of $T$ on the training time of ensemble IR/BPR. As
expected, the training time of ensemble IR/BPR increases linearly as $s$ or
$T$ increases. This is because a larger $s$ means each base recommender system
is trained using more data, while a larger $T$ means more base recommender
systems are trained. Ensemble IR is more efficient than ensemble BPR because
IR is more efficient than BPR.

Figure 12: Comparing certified F1-Score@$N$ of sampling with and without
replacement for ensemble IR on MovieLens-100k, where $N=10$. Figure 13:
Certified Precision@$N$, certified Recall@$N$, and certified F1-Score@$N$ of
ensemble IR for MovieLens-10M, where $N=10$.

Sampling with vs. without replacement: PORE randomly samples a submatrix
without replacement, i.e., the sampled $s$ users are different in a submatrix.
Sampling with replacement means that the $s$ users may have duplicates, i.e.,
a submatrix may include rating scores of less than $s$ unique users. We can
extend our theoretical guarantees to sampling with replacement. The
theoretical analysis is similar to sampling without replacement, so we omit it
for simplicity. Figure 12 compares the certified F1-Score@$N$ of sampling with
and without replacement for ensemble IR on MovieLens-100k dataset. Our results
show that sampling with and without replacement achieves comparable certified
F1-Score@$N$. They also achieve comparable certified Precision@$N$ and
certified Recall@$N$, which we omit for simplicity.

Evaluation on a large dataset: We also evaluate PORE on MovieLens-10M [1],
which consists of around $10,000,000$ rating scores. We set $s=5,000$,
$T=1,000$, and IR as the base recommender system algorithm, and we adopt the
default settings for other parameters. We set a smaller $T$ than our previous
experiments because it is more expensive to train each base recommender system
on MovieLens-10M. Figure 13 shows the results. Our results indicate that our
method is applicable to a large dataset and can derive certified performance
guarantees against data poisoning attacks. We note that the certified
Precision@$N$/Recall@$N$/F1-Score@$N$ of bagging also reduces to 0 with just 1
fake user.

##  6 Related Work

Data poisoning attacks to recommender systems: Many data poisoning attacks to
recommender systems [22, 6, 27, 32, 23, 42, 12, 9, 45, 11, 33, 38, 34, 18, 46,
39] have been proposed. Early attacks are algorithm-agnostic, i.e., the
crafted rating scores of fake users do not depend on the recommender system
algorithm [22, 6, 27]. Recently, more advanced data poisoning attacks [23, 42,
12, 11, 33, 18, 46, 39] have been optimized for specific recommender system
algorithms. For instance, Yang et al. [42] proposed to inject fake co-
visitations to poison association rule based recommender systems, Fang et al.
proposed optimized data poisoning attacks to graph based recommender systems
[12] and matrix factorization based recommender systems [11], and Huang et al.
[18] proposed data poisoning attacks optimized to deep learning based
recommender systems.

Empirical defenses against data poisoning attacks to recommender systems: One
family of defenses [7, 47, 41, 44, 12] aim to detect fake users via analyzing
their abnormal rating score patterns. The key assumption is that the rating
scores of fake users and genuine users have different patterns. Fo instance,
Burke [7] extracted features from each user’s rating scores and trained a
classifier to predict whether a user is fake or not. Another family of
defenses [30, 26, 35, 8, 43, 25, 17] try to train more robust recommender
systems. For instance, adversarial training [13], which was developed to train
robust machine learning classifiers, has been extended to train robust
recommender systems by multiple work [35, 43]. However, none of the above
defenses provides provable robustness guarantees. In particular, they cannot
derive certified Precision@$N$, certified Recall@$N$, and certified
F1-Score@$N$. As a result, they can still be attacked by adaptive attacks.

Ensemble recommender systems: Ensemble methods have been explored to improve
the empirical performance of recommender systems [4, 37, 40]. For instance,
around a decade ago, the winning teams [4, 37] in the well-known Netflix
competition on predicting user rating scores for movies blended multiple base
recommender systems built by different base algorithms. However, these studies
are different from ours. The key difference is that they didn’t derive the
provable robustness guarantees for their ensemble recommender systems.
Moreover, they use different ways to aggregate the base recommender systems,
e.g., they aggregated the rating scores predicted by the base recommender
systems.

Provably robust classifiers against data poisoning attacks: Several works [19,
20] proposed certified defenses against data poisoning attacks for machine
learning classifiers. The key difference between classifiers and recommender
systems is that an input has a single ground-truth label in a classifier while
a user has multiple ground-truth items in a recommender system. As a result,
these methods achieve sub-optimal certified robustness guarantees when
generalized to recommender systems as shown in our experimental results.

##  7 Discussion and Limitations

Theoretical guarantees: For any given number of fake users, our method can
derive a certified intersection size $r$ for each user. Note that our
theoretical guarantee still holds even if fake users rate new items. However,
when the fraction of fake users is large (e.g., 49%), the derived $r$ and the
corresponding certified Precision@$N$/Recall@$N$/F1-Score@$N$ may reduce to 0.
As the first step on provably robust recommender systems, our method can
derive a non-zero $r$ against a moderate number of fake users. It is still an
open challenge to derive a non-trivial $r$ for a large fraction of fake users.
Essentially, there is a trade-off between performance without attack and
robustness, which is controlled by $s$ (number of users in each submatrix).
When the fraction of fake users is large, using a small $s$ makes the ensemble
recommender system more robust but less accurate.

There are several directions to further improve the theoretical guarantees,
i.e., derive a larger $r$ for a given fraction of fake users. First, we
considered a very strong threat model, where each fake user can arbitrarily
rate all items. For instance, in MovieLens-100k, each fake user can rate up to
1,682 items, which accounts for 1.7% of the rating scores from all genuine
users. Fake users that rate a large number of items can be easily detected, as
genuine users often rate a small number of items. Therefore, one way to
further improve theoretical guarantee is to consider fake users that rate a
bounded number of items. Second, PORE is applicable to any base recommender
system algorithm without considering the knowledge of the base algorithm.
Therefore, the second possible way to derive better theoretical guarantees is
to consider the domain knowledge of a specific base algorithm.

Base algorithms and voting mechanisms: We focus on using the same base
algorithm to train each base recommender system in this work. We note that the
base recommender systems can be trained using different base algorithms. In
particular, our theoretical guarantee holds for any (randomized) base
algorithm. Therefore, given a set of base algorithms, we can randomly pick one
to train a base recommender system. Moreover, we can view each base
recommender system is trained using a randomized base algorithm sampled from
the set of base algorithms. PORE uses hard voting when aggregating the items
recommended by the base recommender systems. Hard voting has to be used to
derive the theoretical guarantee of the ensemble recommender system.

Targeted data poisoning attacks: In this work, we focus on untargeted data
poisoning attacks, which aim to reduce the overall performance of a
recommender system. Our method can guarantee a lower bound of recommendation
performance against any untargeted data poisoning attacks. Targeted data
poisoning attacks aim to promote specific attacker-chosen items (called
_target items_) [42]. It is an interesting future work to derive provable
robustness guarantees against such attacks. Specifically, given a fraction of
fake users, we aim to derive an upper bound of the number of genuine users, to
which the target items are recommended.

##  8 Conclusion and Future Work

In this work, we show that PORE can turn an arbitrary base recommender system
algorithm to be provably robust against data poisoning attacks via ensembling
multiple base recommender systems built by the base algorithm on random
subsamples of the rating-score matrix. Our ensemble recommender system
guarantees a certain fraction of its top-$N$ items recommended to a user is
unaffected by fake users no matter how the attacker crafts their rating
scores. Our empirical evaluation confirms that our ensemble recommender system
provides provable robustness guarantees. Interesting future work includes
deriving better provable robustness guarantees by bounding the number of items
that fake users can rate and incorporating the knowledge of the base
recommender system algorithm as well as deriving provable robustness
guarantees against targeted data poisoning attacks.

## Acknowledgements

We thank the anonymous reviewers and shepherd for their constructive comments.
This work was supported by NSF under grant No. 2131859, 2112562, 2131859,
1937786, and 1937787, as well as ARO grant No. W911NF2110182.

## References

  * [1] MovieLens Datasets.  https://grouplens.org/datasets/movielens/.
  * [2] Recommenders.  https://github.com/microsoft/recommenders.
  * [3] Andreas Argyriou, Miguel González-Fierro, and Le Zhang.  Microsoft recommenders: Best practices for production-ready recommendation systems.  In WWW, 2020.
  * [4] Robert M Bell, Yehuda Koren, and Chris Volinsky.  The bellkor 2008 solution to the netflix prize.  Statistics Research Department at AT&T Research, 1, 2008.
  * [5] Leo Breiman.  Bagging predictors.  Machine learning, 24(2):123–140, 1996.
  * [6] Robin Burke, Bamshad Mobasher, Runa Bhaumik, and Chad Williams.  Segment-based injection attacks against collaborative filtering recommender systems.  In ICDM, 2005.
  * [7] Robin Burke, Bamshad Mobasher, Chad Williams, and Runa Bhaumik.  Classification features for attack detection in collaborative recommender systems.  In KDD, 2006.
  * [8] Huiyuan Chen and Jing Li.  Adversarial tensor factorization for context-aware recommendation.  In RecSys, 2019.
  * [9] Konstantina Christakopoulou and Arindam Banerjee.  Adversarial attacks on an oblivious recommender.  In RecSys, 2019.
  * [10] Charles J Clopper and Egon S Pearson.  The use of confidence or fiducial limits illustrated in the case of the binomial.  Biometrika, 26(4), 1934.
  * [11] Minghong Fang, Neil Zhenqiang Gong, and Jia Liu.  Influence function based data poisoning attacks to top-n recommender systems.  In WWW, 2020.
  * [12] Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, and Jia Liu.  Poisoning attacks to graph-based recommender systems.  In ACSAC, 2018.
  * [13] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In ICLR, 2015.
  * [14] F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  ACM TIIS, 5(4), 2015.
  * [15] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In SIGIR, 2020.
  * [16] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua.  Neural collaborative filtering.  In WWW, 2017.
  * [17] Seira Hidano and Shinsaku Kiyomoto.  Recommender systems robust to data poisoning using trim learning.  In ICISSP, 2020.
  * [18] Hai Huang, Jiaming Mu, Neil Zhenqiang Gong, Qi Li, Bin Liu, and Mingwei Xu.  Data poisoning attacks to deep learning based recommender systems.  In NDSS, 2021.
  * [19] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong.  Intrinsic certified robustness of bagging against data poisoning attacks.  In AAAI, 2021.
  * [20] Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong.  Certified robustness of nearest neighbors against data poisoning and backdoor attacks.  In AAAI, 2022.
  * [21] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  Computer, 42(8), 2009.
  * [22] Shyong K Lam and John Riedl.  Shilling recommender systems for fun and profit.  In WWW, 2004.
  * [23] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik.  Data poisoning attacks on factorization-based collaborative filtering.  In NeurIPS, 2016.
  * [24] Greg Linden, Brent Smith, and Jeremy York.  Amazon. com recommendations: Item-to-item collaborative filtering.  IEEE Internet computing, 7(1), 2003.
  * [25] Yang Liu, Xianzhuo Xia, Liang Chen, Xiangnan He, Carl Yang, and Zibin Zheng.  Certifiable robustness to discrete adversarial perturbations for factorization machines.  In SIGIR, 2020.
  * [26] Bhaskar Mehta, Thomas Hofmann, and Wolfgang Nejdl.  Robust collaborative filtering.  In RecSys, 2007.
  * [27] Bamshad Mobasher, Robin Burke, Runa Bhaumik, and Chad Williams.  Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness.  TOIT, 7(4), 2007.
  * [28] Jerzy Neyman and Egon Sharpe Pearson.  Ix. on the problem of the most efficient tests of statistical hypotheses.  Philosophical Transactions of the Royal Society of London., 1933\.
  * [29] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme.  Bpr: Bayesian personalized ranking from implicit feedback.  arXiv:1205.2618, 2012.
  * [30] Jeff J Sandvig, Bamshad Mobasher, and Robin Burke.  Robustness of collaborative recommendation based on association rule mining.  In RecSys, 2007.
  * [31] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl.  Item-based collaborative filtering recommendation algorithms.  In WWW, 2001.
  * [32] Carlos E Seminario and David C Wilson.  Attacking item-based recommender systems with power items.  In RecSys, 2014.
  * [33] Junshuai Song, Zhao Li, Zehong Hu, Yucheng Wu, Zhenpeng Li, Jian Li, and Jun Gao.  Poisonrec: An adaptive data poisoning framework for attacking black-box recommender systems.  In ICDE, 2020.
  * [34] Jiaxi Tang, Hongyi Wen, and Ke Wang.  Revisiting adversarially learned injection attacks against recommender systems.  In RecSys, 2020.
  * [35] Jinhui Tang, Xiaoyu Du, Xiangnan He, Fajie Yuan, Qi Tian, and Tat-Seng Chua.  Adversarial training towards robust multimedia recommender system.  TKDE, 32(5), 2019.
  * [36] Kurt Thomas, Damon McCoy, Chris Grier, Alek Kolcz, and Vern Paxson.  Trafficking fraudulent accounts: The role of the underground market in twitter spam and abuse.  In USENIX Security Symposium, 2013.
  * [37] Andreas Töscher, Michael Jahrer, and Robert M Bell.  The bigchaos solution to the netflix grand prize.  Netflix prize documentation, 2009.
  * [38] Soumya Wadhwa, Saurabh Agrawal, Harsh Chaudhari, Deepthi Sharma, and Kannan Achan.  Data poisoning attacks against differentially private recommender systems.  In SIGIR, 2020.
  * [39] Chenwang Wu, Defu Lian, Yong Ge, Zhihao Zhu, and Enhong Chen.  Triple adversarial learning for influence based poisoning attack in recommender systems.  In KDD, 2021.
  * [40] Mingrui Wu.  Collaborative filtering via ensembles of matrix factorizations.  In KDD Cup and Workshop 2007, 2007.
  * [41] Zhiang Wu, Junjie Wu, Jie Cao, and Dacheng Tao.  Hysad: A semi-supervised hybrid shilling attack detector for trustworthy product recommendation.  In KDD, 2012.
  * [42] Guolei Yang, Neil Zhenqiang Gong, and Ying Cai.  Fake co-visitation injection attacks to recommender systems.  In NDSS, 2017.
  * [43] Feng Yuan, Lina Yao, and Boualem Benatallah.  Adversarial collaborative neural network for robust recommendation.  In SIGIR, 2019.
  * [44] Fuzhi Zhang and Quanqiang Zhou.  Hht–svm: An online method for detecting profile injection attacks in collaborative recommender systems.  Knowledge-Based Systems, 2014.
  * [45] Hengtong Zhang, Yaliang Li, Bolin Ding, and Jing Gao.  Practical data poisoning attack against next-item recommendation.  In WWW, 2020.
  * [46] Hengtong Zhang, Changxin Tian, Yaliang Li, Lu Su, Nan Yang, Wayne Xin Zhao, and Jing Gao.  Data poisoning attack against recommender system using incomplete and perturbed data.  In KDD, 2021.
  * [47] Sheng Zhang, Amit Chakrabarti, James Ford, and Fillia Makedon.  Attack detection in time series for recommender systems.  In KDD, 2006.

##  Appendix A Proof of Theorem 3.1

Recall that, given a rating-score matrix $\mathbf{M}$ and its poisoned version
$\mathbf{M}^{\prime}$, $\mathbf{X}$ and $\mathbf{Y}$ are respectively two
submatrices with $s$ rows randomly sampled from $\mathbf{M}$ and
$\mathbf{M}^{\prime}$ without replacement. We use $\Phi$ to denote the domain
space of $\mathbf{Y}$, i.e., each element in $\Phi$ is a submatrix with $s$
rows sampled from $\mathbf{M}^{\prime}$. Note that since $\mathbf{M}$ is a
submatrix of $\mathbf{M}^{\prime}$, the domain space of $\mathbf{X}$ is a
subset of $\Phi$. For simplicity, we define the following notations. Suppose
we have $\mathbf{Z}\in\Phi$ and another rating-score matrix $\mathbf{W}$, we
say $\mathbf{Z}\prec\mathbf{W}$ (or $\mathbf{Z}\nprec\mathbf{W}$) if
$\mathbf{Z}$ is (or is not) in the domain space created by sampling $s$ rows
from $\mathbf{W}$. We have $\mathbf{X}\prec\mathbf{M}$ and
$\mathbf{Y}\prec\mathbf{M}^{\prime}$ based on our defined notations.
Similarly, give a user $u$ and $\mathbf{Z}\in\Phi$, we say $u\vdash\mathbf{Z}$
if $\mathbf{Z}$ contains rating scores of user $u$. We say
$u\nvdash\mathbf{Z}$ if $\mathbf{Z}$ does not contain user $u$’s rating
scores.

The following lemma generalizes the Neyman-Pearson Lemma [28] to multiple
functions:

######  Lemma 1.

Let $\mathbf{X}$, $\mathbf{Y}$ be two random variables with probability
densities $\text{Pr}(\mathbf{X}=\mathbf{Z})$ and
$\text{Pr}(\mathbf{Y}=\mathbf{Z})$, where $\mathbf{Z}\in\Phi$. Let
$g_{1},g_{2},\cdots,g_{\gamma}:\Phi\xrightarrow{}\\{0,1\\}$ be $\gamma$ random
or deterministic functions. Let $\eta$ be an integer such that:
$\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})\leq\eta,\forall\mathbf{Z}\in\Phi,$
where $g_{l}(1|\mathbf{Z})$ denotes the probability that
$g_{l}(\mathbf{Z})=1$. Similarly, we use $g_{l}(0|\mathbf{Z})$ to denote the
probability that $g_{l}(\mathbf{Z})=0$. Then, we have the following:

(1) If
$\Phi^{\prime}\subseteq\\{\mathbf{Z}\in\Phi:g_{1}(1|\mathbf{Z})=g_{2}(1|\mathbf{Z})=\cdots=g_{\gamma}(1|\mathbf{Z})=0\\}$,
$O_{1}=\\{\mathbf{Z}\in\Phi\setminus\Phi^{\prime}:\text{Pr}(\mathbf{Y}=\mathbf{Z})<\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})\\}$
and
$O_{2}=\\{\mathbf{Z}\in\Phi\setminus\Phi^{\prime}:\text{Pr}(\mathbf{Y}=\mathbf{Z})=\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})\\}$
for some $\rho>0$. Assuming we have $O_{3}\subseteq O_{2}$, and $O=O_{1}\cup
O_{3}$. Then, if we have
$\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{X})=1)}{\eta}\geq\text{Pr}(\mathbf{X}\in
O)$, then
$\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{Y})=1)}{\eta}\geq\text{Pr}(\mathbf{Y}\in
O)$.

(2) If
$\Phi^{\prime}\subseteq\\{\mathbf{Z}\in\Phi:g_{1}(1|\mathbf{Z})=g_{2}(1|\mathbf{Z})=\cdots=g_{\gamma}(1|\mathbf{Z})=0\\}$,
$O_{1}=\\{\mathbf{Z}\in\Phi:\text{Pr}(\mathbf{Y}=\mathbf{Z})>\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})\\}$
and
$O_{2}=\\{\mathbf{Z}\in\Phi:\text{Pr}(\mathbf{Y}=\mathbf{Z})=\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})\\}$
for some $\rho>0$. Assuming we have $O_{3}\subseteq O_{2}$, and $O=O_{1}\cup
O_{3}$. Then, if we have
$\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{X})=1)}{\eta}\leq\text{Pr}(\mathbf{X}\in
O)$, then
$\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{Y})=1)}{\eta}\leq\text{Pr}(\mathbf{Y}\in
O)$.

###### Proof.

We first prove part (1). For convenience, we denote the complement of $O$ as
$O^{c}$. Then, we have the following:

$\displaystyle\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{Y})=1)}{\eta}-\text{Pr}(\mathbf{Y}\in
O)$ (12) $\displaystyle=$
$\displaystyle\int_{\Phi}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}-\int_{O}\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
(13) $\displaystyle=$
$\displaystyle\int_{O^{c}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
$\displaystyle+\int_{O}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}-\int_{O}\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
(14) $\displaystyle=$
$\displaystyle\int_{O^{c}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
$\displaystyle-\int_{O}(1-\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta})\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
(15) $\displaystyle=$
$\displaystyle\int_{O^{c}\setminus\Phi^{\prime}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}+\int_{\Phi^{\prime}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}$
$\displaystyle\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}-\int_{O}(1-\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta})\cdot\text{Pr}(\mathbf{Y}=\mathbf{Z})d\mathbf{Z}$
(16) $\displaystyle\geq$
$\displaystyle\rho\cdot[\int_{O^{c}\setminus\Phi^{\prime}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}+\int_{\Phi^{\prime}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}$
$\displaystyle\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}-\int_{O}(1-\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta})\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}]$
(17) $\displaystyle=$
$\displaystyle\rho\cdot[\int_{O^{c}}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}$
$\displaystyle+\int_{O}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}-\int_{O}\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}]$
(18) $\displaystyle=$
$\displaystyle\rho\cdot[\int_{\Phi}\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}-\int_{O}\text{Pr}(\mathbf{X}=\mathbf{Z})d\mathbf{Z}]$
(19) $\displaystyle=$
$\displaystyle\rho\cdot[\frac{\sum_{l=1}^{\gamma}\text{Pr}(g_{l}(\mathbf{X})=1)}{\eta}-\text{Pr}(\mathbf{X}\in
O)]$ (20) $\displaystyle\geq$ $\displaystyle 0.$ (21)

Figure 14: Illustration of subset $P$, $Q$, $A$, and $B$.

We have Equation (17) from (16) due to the fact that $\forall\mathbf{Z}\in
O^{c}\setminus\Phi^{\prime},\text{Pr}(\mathbf{Y}=\mathbf{Z}\geq\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z})$,
$\forall\mathbf{Z}\in\Phi^{\prime},g_{1}(1|\mathbf{Z})=g_{2}(1|\mathbf{Z})=\cdots=g_{\gamma}(1|\mathbf{Z})=0$,
$1-\frac{\sum_{l=1}^{\gamma}g_{l}(1|\mathbf{Z})}{\eta}\geq 0$, and
$\text{Pr}(\mathbf{Y}=\mathbf{Z})\leq\rho\cdot\text{Pr}(\mathbf{X}=\mathbf{Z}),\forall\mathbf{Z}\in
O$. Similarly, we can prove the part (2). We omit the details for simplicity.
∎

Given a user $u$ and $\Phi$, we define the following subsets:

$\displaystyle
P=\\{\mathbf{Z}\in\Phi|\mathbf{Z}\prec\mathbf{M},u\vdash\mathbf{Z}\\},Q=\\{\mathbf{Z}\in\Phi|\mathbf{Z}\prec\mathbf{M},u\nvdash\mathbf{Z}\\}$
(22) $\displaystyle
A=\\{\mathbf{Z}\in\Phi|\mathbf{Z}\prec\mathbf{M}^{\prime},u\vdash\mathbf{Z}\\},B=\\{\mathbf{Z}\in\Phi|\mathbf{Z}\prec\mathbf{M}^{\prime},u\nvdash\mathbf{Z}\\}$
(23)

It is easy to verify that $P\cap Q=\emptyset$ and $A\cap B=\emptyset$.
Moreover, since $M^{\prime}$ contains rating scores for all the user in
$\mathbf{M}$, we have $P\subseteq A$ and $Q\subseteq B$. Figure 14 shows an
illustration of these four subsets. Based on our sampling without replacement,
we have the following probability mass functions for $\mathbf{X}$ and
$\mathbf{Y}$ in $\Phi$:

$\displaystyle\text{Pr}(\mathbf{X}=\mathbf{Z})=\begin{cases}\frac{1}{{n\choose
s}},&\text{ if }\mathbf{Z}\in P\cup Q,\\\ 0,&\text{ otherwise}.\end{cases}$
(24)
$\displaystyle\text{Pr}(\mathbf{Y}=\mathbf{Z})=\begin{cases}\frac{1}{{n^{\prime}\choose
s}},&\text{ if }\mathbf{Z}\in A\cup B,\\\ 0,&\text{ otherwise}.\end{cases}$
(25)

Given the probability mass functions, we have the following probabilities:

$\displaystyle\text{Pr}(\mathbf{X}\in P)=1-{n-1\choose
s}\cdot\frac{1}{{n\choose s}}=\frac{s}{n},$
$\displaystyle\text{Pr}(\mathbf{X}\in A)=\frac{s}{n},$ (26)
$\displaystyle\text{Pr}(\mathbf{Y}\in P)=\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}},$ $\displaystyle\text{Pr}(\mathbf{Y}\in
A)=\frac{s}{n^{\prime}}.$ (27)

We have $\text{Pr}(\mathbf{X}\notin P)={n-1\choose s}\cdot\frac{1}{{n\choose
s}}$ because there are overall ${n-1\choose s}$ possible submatrices if the
user $u$ is not sampled from $\mathbf{M}$. Then, we can compute
$\text{Pr}(\mathbf{X}\in P)$ based on the fact that $\text{Pr}(\mathbf{X}\in
P)+\text{Pr}(\mathbf{X}\notin P)=1$. We obtain $\text{Pr}(\mathbf{X}\in A)$
based on the fact that $P\subseteq A$ and $A\cap B=\emptyset$. Similarly, we
can compute the probability of $\mathbf{Y}$ in these subsets.

We will leverage the law of contraposition to prove our theorem. Suppose we
have a statement: $U\longrightarrow V$, then, its contraposition is $\neg
V\longrightarrow\neg U$. The law of contraposition tells us that a statement
is true if and only if its contraposition is true. We define the following two
predicates:

$\displaystyle U:$
$\displaystyle~{}\underline{p^{*}_{\mu_{r}}}>\min(\min_{c=1}^{N-r+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}+\sigma)}{c},\overline{p}^{*}_{v_{1}}+\sigma)$
(28) $\displaystyle\text{ and }1\leq r\leq\min(k,N),$ $\displaystyle V:$
$\displaystyle~{}|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|\geq
r,$ (29)

where $\sigma=\frac{s}{n^{\prime}}\cdot\frac{{n^{\prime}\choose s}}{{n\choose
s}}-\frac{s}{n}$ .

Deriving the necessary condition: We assume $\neg V$ is true, i.e.,
$|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|<r$. If $r=0$ or
$r>\min(k,N)$, then, $\neg U$ is true. Next, we consider $1\leq
r\leq\min(k,N)$ and we will show
$\underline{p^{*}_{\mu_{r}}}\leq\min(\min_{c=1}^{N-r+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}+\sigma)}{c},\overline{p}^{*}_{v_{1}}+\sigma)$
is true. If $|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|<r$, then,
there exist at least $k-r+1$ items in $\mathcal{I}_{u}$ that are not
recommended to the user $u$ by our ensemble recommender system when taking
$\mathbf{M}^{\prime}$ as input. In other words, there exist at least $N-r+1$
items in $\mathcal{I}\setminus\mathcal{I}_{u}$ appears in the recommended item
set $\mathcal{T}(\mathbf{M}^{\prime},u)$. For simplicity, we use
$\mathcal{D}_{r}$ and $\mathcal{V}_{r}$ to denote subsets of $k-r+1$ items in
$\mathcal{I}_{u}$ and $N-r+1$ items in $\mathcal{I}\setminus\mathcal{I}_{u}$,
respectively. Formally, we have the following:

$\displaystyle\exists\mathcal{D}_{r},\mathcal{V}_{r},\text{ s.t.
}\mathcal{D}_{r}\cap\mathcal{T}(\mathbf{M}^{\prime},u)=\emptyset,\mathcal{V}_{r}\subseteq\mathcal{T}(\mathbf{M}^{\prime},u),$
(30)

The above equation means that the poisoned item probabilities of the items in
$\mathcal{V}_{r}$ are no smaller than the poisoned item probabilities of the
items in $\mathcal{D}_{r}$. In other words, we have the following for
$\mathcal{D}_{r}$ and $\mathcal{V}_{r}$:

$\displaystyle\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))\leq\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u)).$
(31)

Moreover, since there exist $\mathcal{D}_{r}$ and $\mathcal{V}_{r}$, we have
the following necessary condition if
$|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|<r$ and $1\leq
r\leq\min(k,N)$:

$\displaystyle\min_{\mathcal{D}_{r}}\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))\leq\max_{\mathcal{V}_{r}}\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u)).$
(32)

Next, we will derive the lower bound of left-hand side and the upper bound of
the right-hand side for the above equation.

Deriving a lower bound of
$\min_{\mathcal{D}_{r}}\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))$:
For $\forall i\in\mathcal{D}_{r}$, based on Equation (3), we have the
following:

$\displaystyle\underline{p^{*}_{i}}\triangleq\frac{\lfloor\underline{p_{i}}\cdot{n\choose
s}\rfloor}{{n\choose
s}}\leq\underline{p_{i}}\leq\text{Pr}(i\in\mathcal{A}(\mathbf{X},u))$ (33)

Based on the definition of $\mathbf{X}$, we have:

$\displaystyle\text{Pr}(i\in\mathcal{A}(\mathbf{X},u))\geq\underline{p^{*}_{i}}.$
(34)

For $\forall i\in\mathcal{D}_{r}$, we define the function
$g_{i}(\mathbf{Z})=\mathbb{I}(i\in\mathcal{A}(\mathbf{Z},u))$, where
$\mathbb{I}$ is an indicator function. Specifically, we have
$g_{i}(\mathbf{Z})=0$ for $\forall\mathbf{Z}\in B$ based on the definition of
$B$ in Equation (23), which will be used when we leverage Lemma 1 to derive
the lower bound of $\text{Pr}(g_{i}(\mathbf{Y})=1)$. We have
$\text{Pr}(g_{i}(\mathbf{X})=1)\geq\underline{p^{*}_{i}}$ based on Equation
(34) and the definition of $g_{i}$. For $\forall i\in\mathcal{D}_{r}$, we can
find $C_{i}\subseteq P$ such that we have the following:

$\displaystyle\text{Pr}(\mathbf{X}\in C_{i})=\underline{p^{*}_{i}}.$ (35)

Note that we can find such a subset because $\underline{p^{*}_{i}}$ is an
integer multiple of $\frac{1}{{n\choose s}}$. Then, we have the following:

$\displaystyle\text{Pr}(g_{i}(\mathbf{X})=1)\geq\text{Pr}(\mathbf{X}\in
C_{i}).$ (36)

For simplicity, we define the following quantity:

$\displaystyle\tau={n\choose s}/{n^{\prime}\choose s}.$ (37)

Next, we will apply Lemma 1 to obtain the lower bound of
$\text{Pr}(g_{i}(\mathbf{Y})=1)$. In particular, we let $\Phi^{\prime}=B$
since we have $g_{i}(\mathbf{Z})=0$ for $\forall\mathbf{Z}\in B$. Note that we
omit $Q$ since we have $Q\subseteq B$. Then, we have
$A=\Phi\setminus\Phi^{\prime}$. Based on Equation (24) - (25), we have
$\text{Pr}(\mathbf{Y}=\mathbf{Z})=\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in P$ and
$\text{Pr}(\mathbf{Y}=\mathbf{Z})>\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in A\setminus P$. We let $O_{1}=\emptyset$ since there is no
subset that satisfies
$\text{Pr}(\mathbf{Y}=\mathbf{Z})<\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$.
Furthermore, we let $O_{2}=P$, $O_{3}=C_{i}\subseteq O_{2}$, $\eta=1$, and
$\gamma=1$. Finally, we let $O=O_{1}\cup O_{3}=C_{i}$. We can apply Lemma 1
based on the condition in Equation (36) and we have the following:

$\displaystyle\text{Pr}(g_{i}(\mathbf{Y})=1)\geq\text{Pr}(\mathbf{Y}\in
C_{i}).$ (38)

Based on the definition of $g_{i}$, we have the following:

$\displaystyle\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))$ (39) $\displaystyle=$
$\displaystyle\text{Pr}(g_{i}(\mathbf{Y})=1)$ (40) $\displaystyle\geq$
$\displaystyle\text{Pr}(\mathbf{Y}\in C_{i})$ (41) $\displaystyle=$
$\displaystyle\text{Pr}(\mathbf{X}\in C_{i})\cdot\tau$ (42) $\displaystyle=$
$\displaystyle\underline{p^{*}_{i}}\cdot\tau.$ (43)

For simplicity, we denote
$\mathcal{D}_{r}=\\{d^{\prime}_{1},d^{\prime}_{2},\cdots,d^{\prime}_{z}\\}$,
where $z=k-r+1$. Without loss of generality, we assume
$\underline{p_{d^{\prime}_{1}}}\geq\cdots\geq\underline{p_{d^{\prime}_{z}}}$.
We have the following:

$\displaystyle\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))\geq\max_{i\in\mathcal{D}_{r}}\underline{p^{*}_{i}}\cdot\tau=\underline{p^{*}_{d^{\prime}_{1}}}\cdot\tau.$
(44)

Then, we have the following:

$\displaystyle\min_{\mathcal{D}_{r}}\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))=\min_{\mathcal{D}_{r}}\underline{p^{*}_{d^{\prime}_{1}}}\cdot\tau$
(45)

Therefore, when $\mathcal{D}_{r}=\\{\mu_{r},\mu_{r+1},\cdots,\mu_{k}\\}$,
$\underline{p^{*}_{d^{\prime}_{1}}}\cdot\tau$ reaches the minimal value which
is $\underline{p^{*}_{\mu_{r}}}\cdot\tau$. In other words, we have the
following:

$\displaystyle\min_{\mathcal{D}_{r}}\max_{i\in\mathcal{D}_{r}}\text{Pr}(i\in\mathcal{A}(\mathbf{Y},u))\geq\underline{p^{*}_{\mu_{r}}}\cdot\tau.$
(46)

Deriving an upper bound of
$\max_{\mathcal{V}_{r}}\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$:
For $\forall j\in\mathcal{V}_{r}$, given Equation (3), we have the following:

$\displaystyle\overline{p}^{*}_{j}=\frac{\lceil\overline{p}_{j}\cdot{n\choose
s}\rceil}{{n\choose
s}}\geq\overline{p}_{j}\geq\text{Pr}(j\in\mathcal{A}(\mathbf{X},u)).$ (47)

Suppose we have
$\mathcal{V}_{r}=\\{v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{w}\\}$,
where $w=N-r+1$. Without loss of generality, we assume the following:

$\displaystyle\overline{p}_{v^{\prime}_{1}}\leq\overline{p}_{v^{\prime}_{2}}\leq\cdots\leq\overline{p}_{v^{\prime}_{w}}.$
(48)

We first derive an upper bound of $\min_{j\in\mathcal{V}_{r}}$
$\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$. Given an arbitrary item
$j\in\mathcal{V}_{r}$, we have the following inequality based on Equation (47)
and our definition of $\mathbf{X}$:

$\displaystyle\text{Pr}(j\in\mathcal{A}(\mathbf{X},u))\leq\overline{p}^{*}_{j}.$
(49)

Given an item $j\in\mathcal{V}_{r}$, we define the function
$g_{j}(\mathbf{Z})=\mathbb{I}(j\in\mathcal{A}(\mathbf{Z},u))$. We have
$\text{Pr}(g_{j}(\mathbf{X})=1)\leq\overline{p}^{*}_{j}$ based on Equation
(49) and the definition of $g_{j}$. Then, we can leverage Lemma 1 to derive an
upper bound for $\text{Pr}(g_{j}(\mathbf{X})=1)$. In particular, we can find
$C^{\prime}_{j}\subseteq P$ such that we have the following:

$\displaystyle\text{Pr}(\mathbf{X}\in C^{\prime}_{j})=\overline{p}^{*}_{j}.$
(50)

We let $C_{j}=C^{\prime}_{j}\cup(A\setminus P)$. Since we have
$\text{Pr}(\mathbf{X}\in A\setminus P)=\text{Pr}(\mathbf{X}\in
A)-\text{Pr}(\mathbf{X}\in P)=0$, we have the following:

$\displaystyle\text{Pr}(\mathbf{X}\in C_{j})=\text{Pr}(\mathbf{X}\in
C^{\prime}_{j})+\text{Pr}(\mathbf{X}\in A\setminus P)=\overline{p}^{*}_{j}.$
(51)

Based on $\text{Pr}(g_{j}(\mathbf{X})=1)\leq\overline{p}^{*}_{j}$, we have the
following:

$\displaystyle\text{Pr}(g_{j}(\mathbf{X})=1)\leq\text{Pr}(\mathbf{X}\in
C_{j}).$ (52)

Next, we will apply Lemma 1 to obtain the upper bound of
$\text{Pr}(g_{j}(Y)=1)$. In particular, we let $\Phi^{\prime}=B$ since we have
$g_{j}(\mathbf{Z})=0$ for $\forall\mathbf{Z}\in B$. Then, we have
$A=\Phi\setminus\Phi^{\prime}$. Based on Equation (24) - (25), we have
$\text{Pr}(\mathbf{Y}=\mathbf{Z})=\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in P$ and
$\text{Pr}(\mathbf{Y}=\mathbf{Z})>\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in A\setminus P$. We let $O_{1}=A\setminus P$, $O_{2}=P$,
$O_{3}=C^{\prime}_{j}\subseteq O_{2}$, $\eta=1$, and $\gamma=1$. Finally, we
let $O=O_{1}\cup O_{3}=C_{j}$. We can apply Lemma 1 based on the condition in
Equation (52) and we have the following:

$\displaystyle\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$ (53) $\displaystyle=$
$\displaystyle\text{Pr}(g_{j}(\mathbf{Y})=1)$ (54) $\displaystyle\leq$
$\displaystyle\text{Pr}(\mathbf{Y}\in C_{j})$ (55) $\displaystyle=$
$\displaystyle\text{Pr}(\mathbf{Y}\in C^{\prime}_{j})+\text{Pr}(\mathbf{Y}\in
A\setminus P)$ (56) $\displaystyle=$ $\displaystyle\text{Pr}(\mathbf{X}\in
C^{\prime}_{j})\cdot\tau+\text{Pr}(\mathbf{Y}\in A)-\text{Pr}(\mathbf{Y}\in
P)$ (57) $\displaystyle=$
$\displaystyle\overline{p}^{*}_{j}\cdot\frac{{n\choose s}}{{n^{\prime}\choose
s}}+\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}.$ (58)

Given Equation (48), we have the following:

$\displaystyle\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))\leq\overline{p}^{*}_{v^{\prime}_{1}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}.$ (59)

Therefore, when $\mathcal{V}_{r}$ contains the set of items in
$\mathcal{I}\setminus\mathcal{I}_{u}$ that have the largest probability
bounds, which we denote as $\mathcal{V}_{r}=\\{v_{1},v_{2},\cdots,v_{w}\\}$
where
$\overline{p}_{v_{1}}\leq\overline{p}_{v_{2}}\leq\cdots\leq\overline{p}_{v}$,
the upper bound of $\max_{\mathcal{V}_{r}}\min_{j\in\mathcal{V}_{r}}$
$\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$ reaches the maximum value.
Formally, we have the following:

$\displaystyle\max_{\mathcal{V}_{r}}\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))\leq\overline{p}^{*}_{v_{1}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}.$ (60)

Next, we will derive another upper bound for $\text{Pr}(g_{j}(Y)=1)$ via
jointly considering multiple items. In particular, we use $\mathcal{H}_{c}$ to
denote an arbitrary subset of $\mathcal{V}_{r}$ that contains $c$ items, i.e.,
$\mathcal{H}_{c}\subseteq\mathcal{V}_{r}$. We denote
$\overline{p}_{\mathcal{H}_{c}}=\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j}$,
i.e., the summation of probability upper bounds for the items in
$\mathcal{H}_{c}$. Then, for each item $j\in\mathcal{H}_{c}$, we define
$g_{j}(\mathbf{Z})=\mathbb{I}(j\in\mathcal{A}(\mathbf{Z},u))$. Given a
positive integer $\eta$, we define the following quantity:

$\displaystyle\overline{p}^{*}_{\mathcal{H}_{c}}=\frac{\lceil(\overline{p}_{\mathcal{H}_{c}}/\eta)\cdot{n\choose
s}\rceil}{{n\choose s}}.$ (61)

We can find $C^{\prime}_{\mathcal{H}_{c}}\subseteq P$ such that we have the
following:

$\displaystyle\text{Pr}(\mathbf{X}\in
C^{\prime}_{\mathcal{H}_{c}})=\overline{p}^{*}_{\mathcal{H}_{c}}.$ (62)

Then, we define
$C_{\mathcal{H}_{c}}=C^{\prime}_{\mathcal{H}_{c}}\cup(A\setminus P)$ and we
have the following:

$\displaystyle\text{Pr}(\mathbf{X}\in
C_{\mathcal{H}_{c}})=\text{Pr}(\mathbf{X}\in
C^{\prime}_{\mathcal{H}_{c}})+\text{Pr}(\mathbf{X}\in A\setminus
P)=\overline{p}^{*}_{\mathcal{H}_{c}}.$ (63)

Based on the definition of $g_{j}(\mathbf{Z})$, we have the following:

$\displaystyle\frac{\sum_{j\in\mathcal{H}_{c}}\text{Pr}(g_{j}(X)=1)}{\eta}\leq\frac{\sum_{j\in\mathcal{H}_{c}}\overline{p}_{j}}{\eta}\leq\overline{p}^{*}_{\mathcal{H}_{c}}=\text{Pr}(\mathbf{X}\in
C_{\mathcal{H}_{c}}).$ (64)

Next, we will leverage Lemma 1 to derive an upper bound for
$\sum_{j\in\mathcal{H}_{c}}\text{Pr}(g_{j}(\mathbf{Y})=1)$. Given a rating-
score matrix $\mathbf{Z}$ as input, the recommender system algorithm
$\mathcal{A}$ recommends $N^{\prime}$ items to a user. Therefore, we have
$\sum_{j\in\mathcal{H}_{c}}\mathbb{I}(j\in\mathcal{A}(\mathbf{Z},u))\leq
N^{\prime}$, i.e., $\sum_{j\in\mathcal{H}_{c}}g_{j}(\mathbf{Z})\leq
N^{\prime}$. Based on this, we let $\eta=N^{\prime}$. Since there are $c$
items in $\mathcal{H}_{c}$, we let $\gamma=c$. We let $\Phi^{\prime}=B$ since
we have $g_{j}(\mathbf{Z})=0$ for $\forall\mathbf{Z}\in B$. Then, we have
$A=\Phi\setminus\Phi^{\prime}$. Based on Equation (24) - (25), we have
$\text{Pr}(\mathbf{Y}=\mathbf{Z})=\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in P$ and
$\text{Pr}(\mathbf{Y}=\mathbf{Z})>\tau\cdot\text{Pr}(\mathbf{X}=\mathbf{\mathbf{Z}})$
if $\mathbf{Z}\in A\setminus P$. We let $O_{1}=A\setminus P$, $O_{2}=P$, and
$O_{3}=C^{\prime}_{\mathcal{H}_{c}}\subseteq O_{2}$. Finally, we let
$O=O_{1}\cup O_{3}=C_{\mathcal{H}_{c}}$. We can apply Lemma 1 based on the
condition in Equation (64) and we have the following:

$\displaystyle\sum_{j\in\mathcal{H}_{c}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
(65) $\displaystyle=$
$\displaystyle\sum_{j\in\mathcal{H}_{c}}\text{Pr}(g_{j}(\mathbf{Y})=1)$ (66)
$\displaystyle\leq$ $\displaystyle N^{\prime}\cdot\text{Pr}(\mathbf{Y}\in
C_{\mathcal{H}_{c}})$ (67) $\displaystyle=$ $\displaystyle
N^{\prime}\cdot(\text{Pr}(\mathbf{Y}\in
C^{\prime}_{\mathcal{H}_{c}})+\text{Pr}(\mathbf{Y}\in A\setminus P))$ (68)
$\displaystyle=$ $\displaystyle N^{\prime}\cdot(\text{Pr}(\mathbf{X}\in
C^{\prime}_{\mathcal{H}_{c}})\cdot\tau+\text{Pr}(\mathbf{Y}\in
A)-\text{Pr}(\mathbf{Y}\in P))$ (69) $\displaystyle=$ $\displaystyle
N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+(\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}})).$ (70)

Then, we have the following:

$\displaystyle\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
(71) $\displaystyle\leq$
$\displaystyle\min_{j\in\mathcal{H}_{c}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
(72) $\displaystyle\leq$
$\displaystyle\frac{\sum_{j\in\mathcal{H}_{c}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))}{c}$
(73) $\displaystyle\leq$ $\displaystyle
N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+(\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}))/c.$ (74)

We have Equation (72) from (71) because
$\mathcal{H}_{c}\subseteq\mathcal{V}_{r}$ and Equation (73) from (72) because
the smallest value is no larger than the average value in a set. We note that
the upper bound of
$\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$ is non-
decreasing as $\overline{p}_{\mathcal{H}_{c}}$ increases. Based on Equation
(48), the upper bounds reaches the minimal value when
$\mathcal{H}_{c}=\\{v^{\prime}_{1},v^{\prime}_{2},$
$\cdots,v^{\prime}_{c}\\}$. Taking all possible $c$ into consideration, we
have the following:

$\displaystyle\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
(75) $\displaystyle\leq$
$\displaystyle\min_{c=1}^{N-r+1}N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+(\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}))/c,$

where
$\mathcal{H}_{c}=\\{v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{c}\\}$.
Similarly, the upper bound of $\max_{\mathcal{V}_{r}}$
$\min_{j\in\mathcal{V}_{r}}$ $\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
reaches the maximum value when $\mathcal{V}_{r}$ contains the $N-r+1$ items
among all items in $\mathcal{I}\setminus\mathcal{I}_{u}$ that have the largest
probability upper bounds, which we denote as
$\mathcal{V}_{r}=\\{v_{1},v_{2},\cdots,v_{w}\\}$, where
$\overline{p}_{v_{1}}\leq\overline{p}_{v_{2}}\leq\cdots\leq\overline{p}_{v_{w}}$
and $w=N-r+1$. Formally, we have the following:

$\displaystyle\max_{\mathcal{V}_{r}}\min_{j\in\mathcal{V}_{r}}\text{Pr}(j\in\mathcal{A}(\mathbf{Y},u))$
(76) $\displaystyle\leq$
$\displaystyle\min_{c=1}^{N-r+1}N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+(\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}))/c,$ (77)

where $\mathcal{H}_{c}=\\{v_{1},v_{2},\cdots,v_{c}\\}$. Since we have Equation
(32) when $\neg U$ is true and $1\leq r\leq\min(k,N)$, we have the following:

$\displaystyle\underline{p^{*}_{\mu_{r}}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}\leq$
$\displaystyle\min(\min_{c=1}^{N-r+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+(\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}))}{c},$
$\displaystyle\overline{p}^{*}_{v_{1}}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose
s}}+\frac{s}{n^{\prime}}-\frac{s}{n}\cdot\frac{{n\choose
s}}{{n^{\prime}\choose s}}).$ (78)

where $\mathcal{V}_{r}=\\{v_{1},v_{2},\cdots,v_{N-r+1}\\}$ and
$\mathcal{H}_{c}=\\{v_{1},v_{2},\cdots,v_{c}\\}$. The Equation (A) is
equivalent to the following:

$\displaystyle\underline{p^{*}_{\mu_{r}}}\leq\min(\min_{c=1}^{N-r+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}+\sigma)}{c},\overline{p}^{*}_{v_{1}}+\sigma),$
(79)

where $\sigma=\frac{s}{n^{\prime}}\cdot\frac{{n^{\prime}\choose s}}{{n\choose
s}}-\frac{s}{n}$ .

Applying the law of contraposition: We leverage the law of contraposition and
we have the following: if we have $1\leq r\leq\min(k,N)$ and the following:

$\displaystyle\underline{p^{*}_{\mu_{r}}}>\min(\min_{c=1}^{N-r+1}\frac{N^{\prime}\cdot(\overline{p}^{*}_{\mathcal{H}_{c}}+\sigma)}{c},\overline{p}^{*}_{v_{1}}+\sigma),$
(80)

where $\sigma=\frac{s}{n^{\prime}}\cdot\frac{{n^{\prime}\choose s}}{{n\choose
s}}-\frac{s}{n}$. Then, we have
$|\mathcal{I}_{u}\cap\mathcal{T}(\mathbf{M}^{\prime},u)|\geq r$. The Equation
(80) is satisfied for
$\forall\mathbf{M}^{\prime}\in\mathcal{L}(\mathbf{M},e)$. We can find the
maximum value of $r$, where $1\leq r\leq\min(k,N)$, that satisfies the
Equation (80), which is essentially the optimization problem in the Equation
(1). We reach the conclusion.

##  Appendix B Proof of Theorem 3.2

Based on Equation (7) - (8) and Boole’s inequality in probability theory, we
have the following probability:

$\displaystyle\text{Pr}((p_{i}\geq\underline{p_{i}},\forall
i\in\mathcal{I}_{u})\wedge(p_{j}\leq\overline{p}_{j},\forall
j\in\mathcal{I}\setminus\mathcal{I}_{u}))\geq 1-\alpha_{u},$ (81)

where $R\wedge S$ is true if and only if $R$ is true and $S$ is true. Note
that there is no randomness in our optimization problem in Equation (1).
Therefore, the probability that our Algorithm 2 computes an incorrect $r_{u}$
for the user $u$ is at most $\alpha_{u}$. Recall that we set
$\alpha_{u}=\frac{\alpha}{n}$ in our Algorithm 2. Based on the Boole’s
inequality, we know the probability that our Algorithm 2 computes an incorrect
$r_{u}$ for at least one user among all users in $\mathcal{U}$ is at most
$\alpha$.