  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 a 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.
