Poisoning Attacks to Graph-Based Recommender Systems

2018·Arxiv

ABSTRACT

ABSTRACT

Recommender system is an important component of many web services to help users locate items that match their interests. Several studies showed that recommender systems are vulnerable to poisoning atacks, in which an atacker injects fake data to a recommender system such that the system makes recommendations as the atacker desires. However, these poisoning atacks are either agnostic to recommendation algorithms or optimized to recommender systems (e.g., association-rule-based or matrix-factorization-based recommender systems) that are not graph-based. Like association-rule-based and matrix-factorization-based recommender systems, graph-based recommender system is also deployed in practice, e.g., eBay, Huawei App Store (a big app store in China). However, how to design optimized poisoning atacks for graph-based recommender systems is still an open problem.

In this work, we perform a systematic study on poisoning atacks to graph-based recommender systems. We consider an atacker’s goal is to promote a target item to be recommended to as many users as possible. To achieve this goal, our atacks inject fake users with carefully crafed rating scores to the recommender system. Due to limited resources and to avoid detection, we assume the number of fake users that can be injected into the system is bounded. Te key challenge is how to assign rating scores to the fake users such that the target item is recommended to as many normal users as possible. To address the challenge, we formulate the poisoning atacks as an optimization problem, solving which determines the rating scores for the fake users. We also propose techniques to solve the optimization problem. We evaluate our atacks and compare them with existing atacks under white-box (recommendation algorithm and its parameters are known), gray-box (recommendation algorithm is known but its parameters are unknown), and black-box (recommendation algorithm is unknown) setings using two real-world datasets. Our results show that our atack is efective and outperforms existing atacks for graph-based recommender systems. For instance, when 1% of users are injected fake users, our atack can make a target item recommended to 580 times more normal users in certain scenarios.

CCS CONCEPTS

Security and privacy Web application security;

KEYWORDS

Adversarial recommender systems, poisoning atacks, adversarial machine learning.

ACM Reference format:

Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, and Jia Liu. 2018. Poisoning Atacks to Graph-Based Recommender Systems. In Proceedings of

1 INTRODUCTION

In the era of big data, a fundamental challenge is to locate the data that are relevant to a particular user. Recommender systems aim to address this challenge: given a user’s historical behavior and social data, a recommender system fnds the data that match the user’s preference. Indeed, recommender systems are widely deployed by web services (e.g., YouTube, Amazon, and Google News) to recommend users relevant items such as products, videos, and news. In particular, collaborative fltering based recommender systems, which analyze the correlations between users’ historical behavior data for making recommendations, are widely deployed due to their efectiveness and generality. Depending on the techniques used to capture the correlations between users’ behavior data, collaborative fltering based recommender systems can further include matrix-factorization-based [17], association-rule-based [6, 22], and graph-based [7] recommender systems. For instance, matrix-factorization-based recommender systems are deployed by Netfix to recommend movies, association-rule-based recommender systems are deployed by YouTube to recommend videos [6], and graph-based recommender systems are deployed by eBay [25, 26] and Huawei App Store (a big app store in China) [12, 13].

It is commonly believed that recommender systems recommend users items that match their personal interests. However, several studies [19–21, 24, 35] have demonstrated that recommender systems are vulnerable to poisoning atacks, which inject fake data to a recommender system such that the recommender system makes recommendations as an atacker desires. For instance, an atacker can inject fake users with carefully crafed fake rating scores to a recommender system such that a target item is recommended to as many users as possible. Conventional poisoning atacks [19, 21, 24] (also known as shilling atacks) are agnostic to recommendation algorithms, i.e., they are not optimized to a certain type of recommender systems. Terefore, such atacks ofen achieve suboptimal performance when the recommendation algorithm is known. To address this limitation, recent studies [20, 35] proposed poisoning atacks that were optimized for a particular type of recommender systems. For instance, Li et al. [20] proposed poisoning atacks optimized for matrix-factorization-based recommender systems, while Yang et al. [35] proposed poisoning atacks optimized for association-rule-based recommender systems. However, how to design optimized poisoning atacks to graph-based recommender systems is still an open problem.

In this work, we aim to design poisoning atacks for graph-based recommender systems [7, 12, 13, 25, 26]. A graph-based recommender system uses a user preference graph to represent users’ rating scores to items. In the graph, a node is a user or an item, an edge between a user and an item means that the user rated the item, and the edge weight is the corresponding rating score. To make recommendations to a user, the recommender system performs a random walk in the user preference graph, where the random walk starts from the user and jumps back to the user with a certain probability (called restart probability) in each step. Afer the random walk converges, each item has a stationary probability that essentially characterizes the closeness between the item and the user. Finally, the system recommends the items that have the largest stationary probabilities to the user.

In our poisoning atacks, an atacker’s goal is to promote a target item, i.e., making a graph-based recommender system recommend the target item to as many users as possible. Like most existing poisoning atacks to recommender systems [19–21, 24], our atacks inject fake users with carefully crafed rating scores to the target recommender system to achieve the atack goal. Due to limited resources and to avoid detection, we assume an atacker can inject m fake users at most and each fake user rates n items at most. For convenience, we call the items, which a fake user rates, the user’s fller items. Te key challenge is to determine the fller items and their rating scores for each fake user. To address the challenge, we formulate poisoning atacks to graph-based recommender systems as an optimization problem, whose objective function is the hit ratio of the target item (i.e., the fraction of normal users whose recommended items include the target item) and whose constraints are that at most m fake users with at most n fller items can be injected. Solving this optimization problem produces m fake users that maximize the hit ratio of the target item.

However, this optimization problem is computationally intractable because 1) the hit ratio is related to the fake users’ rating scores in a very complex way, and 2) the rating scores are integer variables. To address the computational challenge, we propose several techniques to solve the optimization problem approximately. Specifcally, we approximate the hit ratio using the items’ stationary probabilities, which are used to make recommendations in graph-based recommender systems. Moreover, we relax the fake users’ rating scores as continuous variables, solve the optimization problem, and then generate fller items and their integer rating scores based on the continuous variables. Finally, we propose a projected gradient descent based method to solve the optimization problem with an approximate hit ratio and relaxed continuous variables.

We evaluate our poisoning atacks and compare them with several existing atacks using two real-world datasets. First, we evaluate the atacks under the white-box seting, i.e., the graph-based recommendation algorithm and its parameter (i.e., restart probability) are known to the atacker. We fnd that our atack can efectively enhance the hit ratio of a target item. For instance, when the system recommends 10 items to each user and the number of injected fake users is 1% of the number of normal users, our attack could improve the hit ratio of an unpopular target item by around 580 times. Moreover, our atack is signifcantly more efective than existing atacks for graph-based recommender systems. For instance, compared to the poisoning atack proposed by Yang et al. [35], our atack can improve the hit ratio from 0.0% to 0.4% for an unpopular target item. Te reason is that existing atacks are not optimized for graph-based recommender systems. Second, we evaluate the atacks under gray-box seting (the graph-based recommendation algorithm is known but its parameter is unknown) and black-box seting (the recommendation algorithm is unknown). We fnd that, in the gray-box seting, even if the atacker does not know the restart probability, our atack can still substantially improve the hit ratios of target items. In the black-box seting, we assume an atacker generates fake users based on a graph-based recommender system, while the target recommender system is based on matrix factorization. Our results show that our atacks can also transfer to matrix factorization based recommender systems.

We also study detecting fake users via supervised machine learning techniques and their impact on the efectiveness of poisoning atacks. Intuitively, the rating scores of fake users are generated in specifc ways, and thus it could be possible to distinguish between normal users and fake users using their rating scores. Specifcally, we extract features from a user’s rating scores and learn a binary classifer using a training dataset that includes both normal users and fake users. Te binary classifer is then used to predict a user to be normal or fake. We fnd that a small fraction of normal users are falsely predicted to be fake, while a large fraction (20%fake users are falsely predicted to be normal. Te service provider could deploy such a detector to predict fake users and exclude the predicted fake users from the recommender system. We evaluate our poisoning atacks and existing atacks under such scenario. We fnd that the poisoning atacks are still efective when such a detector is deployed, and our atack is still more efective than existing atacks. Te reason is that a large fraction of fake users are not detected.

In summary, our contributions are as follows:

• We provide the frst systematic study on poisoning atacks to graph-based recommender systems. We formulate poisoning atacks as an optimization problem and propose techniques to solve the optimization problem approximately.

• We extensively evaluate our atacks and compare them with existing atacks using two real-world datasets.

• We study detecting fake users using their rating scores and evaluate the efectiveness of poisoning atacks when such a detector is deployed.

2 BACKGROUND AND RELATED WORK

2.1 Collaborative Filtering

Collaborative fltering based recommender systems have been widely deployed in various web services such as Amazon, YouTube, Netfix, and Google Play. Suppose we are given a user-item rating score matrix, where the entry is the rating score that user u gave to item i, e.g., a product on Amazon, a video on YouTube, a movie on Netfix, and an app on Google Play. For instance, a rating score can be 0, 1, 2, 3, 4, or 5, where =0 indicates that u did not rate the item i, 1 means the most negative rating score, and 5 means the most positive rating score. Te goal of collaborative fltering is to recommend each user in the user-item rating score matrix N items that the user did not rate before but the user may have interests in, via analyzing the rating score matrix. Depending on the techniques that are used to analyze the rating score matrix, collaborative fltering can be roughly classifed to 4 categories, i.e., neighborhood-based, association-rule-based, matrix-factorization-based, and graph-based.

torization-based recommender systems: Neighborhood-based recommender systems [27] fnd neighbors of a user or neighbors of an item in order to recommend items to a user. For instance, to recommend a user items, the methods can frst fnd the nearestneighbors of the user, predict the user’s rating scores to items based on the rating scores of the nearest neighbors, and recommend the N items that have the highest predicted rating scores to the user. Association-rule-based recommender systems [6, 22] aim to identify frequent co-occurrence between items in user reviews. For instance, if many users give high rating scores to both item A and item B, then there is a certain association between the two items. For a user who gave a high rating score to item A, item B is recommended to the user. Matrix-factorization-based recommender systems [17] assume that the user-item rating score matrix can be explained by a small number of latent factors. Based on the assumption, they use a low-rank matrix to approximate the user-item rating score matrix. Te low-rank matrix predicts missing values in the user-item rating score matrix, i.e., for each user, the low-rank matrix predicts rating scores to all items that the user did not rate before; and the N items that have the highest predicted rating scores are recommended to the user. Graph-based recommender systems: In this work, we focus on graph-based recommender systems [7]. Graph-based recommender systems were deployed by several popular web services such as eBay [25, 26] and Huawei App Store [12, 13] in China. Te key idea of graph-based recommender system is to model users’ preference for items as a weighted bipartite graph G = (U , I, E), namely user preference graph. Te two sets of vertex U and I represent the user set and the item set, respectively; an edge (u,i) between a user and an item represents that the user rated the item; and the weight of an edge (u,i) is the rating score that the user gave to the item. Figure 1 illustrates a user preference graph with an example of 3 users and 3 items.

To generate the top-N recommendation list for a user, the recommender system performs a random walk in the graph, where the random walk starts from the user and jumps back to the user with a probability in each step, where is called restart probability. Te stationary probability distribution of the random walk is used

Figure 1: An illustration of user preference graph

to rank items and make recommendations. We denote by the stationary probability distribution of the random walk that starts from the user u. Ten, the stationary probability distribution is a solution of the following linear system:

where is a unit vector whose uth entry is 1 and all other entries are 0, and the matrix Q is called transition matrix, which is defned as follows:

where is the set of neighbors of node x. More specifcally, for a user node is the set of items that were rated by x; for an item node is the set of users that rated from a random probability distribution and then iteratively update as until convergence. Ten, we rank the items that were not rated by the user u with respect to their stationary probabilities. Te top-N items with the largest stationary probabilities are recommended to the user u.

2.2 Attacks to Recommender Systems

2.2.1 Security Atacks. Tese atacks aim to spoof a recommender system such that a target item is recommended to as many or few users as possible. Specifcally, poisoning atacks (also known as shilling atacks) [19, 21, 24] aim to inject fake users with fake rating scores to the system such that a bad recommender system is learnt from the user-item rating score matrix. Profle pollution atacks [34] aim to pollute the rating behavior of normal users to manipulate the recommendations to them. By analogy to adversarial machine learning, poisoning atacks are to manipulate recommender systems at “training time”, while profle pollution atacks are to manipulate recommender systems at “testing time”.

Poisoning attacks: Poisoning atacks were frst studied more than a decade ago [19, 21, 24]. However, these atacks are heuristicsdriven and are not optimized to a particular type of recommender systems. For instance, in random atacks [19], given the number of fake users an atacker can inject into the system, the atacker randomly selects some items for each fake user and then generates a rating score for each selected item from a normal distribution, whose mean and variance are calculated from the rating scores in the entire user-item rating score matrix. In average atacks [19], the atacker generates a rating score for a selected item from a normal distribution, whose mean and variance are computed from the rating scores to the selected item in the user-item rating score matrix.

More recent poisoning atacks [20, 35] generate fake rating scores or behavior that are optimized to a particular type of recommender systems. Specifcally, Li et al. [20] proposed poisoning atacks to matrix-factorization-based recommender systems. Yang et al. [35] proposed poisoning atacks (they called them fake co-visitation injection atacks) to association-rule-based recommender systems, in which each user injects fake co-visitations between items instead of fake rating scores to items. We aim to study optimized poisoning atacks to graph-based recommender systems.

Profle pollution attacks: Xing et al. [34] proposed profle pollution atacks to recommender systems and other personalized services, e.g., web search. Teir atacks aim to pollute a user’s profle, e.g., browsing history, via cross-site request forgery (CSRF) [37]. With a polluted user profle, the atacker can recommend arbitrary items to the user. Tey showed that popular web services including YouTube, Amazon, and Google search are vulnerable to the atacks. However, the limitation of these atacks is that they rely on CSRF, which makes it hard to perform the atacks at a large scale.

2.2.2 Privacy Atacks. Two atacks, i.e., item inference atacks

and atribute inference atacks, were proposed to compromise user privacy in recommender systems.

Item inference attacks: Calandrino et al. [4] proposed privacy attacks to infer the items that a target user has rated before, e.g., such items could be products that the target user purchased on Amazon, music the target user liked on Last.fm, and books the target user read on LibraryTing. Te key intuition of their atacks is that a collaborative fltering recommender system makes recommendations based on users’ past behavior. Terefore, the recommendations made by a recommender system include information about users’ past behavior. Via tracking and analyzing the publicly available recommendations over time, an atacker could infer a target user’s past behavior, e.g., the items the user rated.

Attribute inference attacks: A user’s rating behavior (e.g., rating scores to items, page likes on Facebook) is essentially statistically correlated to the user’s atributes (e.g., gender, political view, sexual orientation, interests, and location). Terefore, an atacker could infer a user’s private atributes based on its rating behavior via machine learning techniques, which capture the statistical correlations between rating behavior and atributes. Such atacks are called atribute inference atacks [9] and have been demonstrated to be feasible by multiple studies [9–11, 16, 18, 33]. In particular, given a set of users whose rating behavior and atributes are known to an atacker, the atacker learns a machine learning classifer which takes a user’s rating behavior as an input and predicts the user’s attributes. Ten, the atacker applies this classifer to infer atributes of the users who did not disclose their atributes. A notable example of real-world atribute inference atacks is that Cambridge Analytica leveraged Facebook users’ rating behavior (e.g., page likes) to infer users’ atributes, based on which targeted advertisements are delivered to users [1]. Jia and Gong [15] recently proposed a practical defense against atribute inference atacks via adversarial machine learning. Te key idea is to add carefully crafed noise to a user’s rating behavior data such that the atacker’s classifer is very likely to make incorrect predictions.

3 PROBLEM FORMULATION

3.1 Treat Model

Attack goal: We consider an atacker’s goal is to promote a target item t to as many users as possible. Suppose the system recommends N items to each user. We denote by h(t) the fraction of normal users whose top-N recommendations include the target item afer the atack. h(t) is called hit ratio of the target item t. Te atacker’s goal is to maximize the hit ratio. We note that an atacker could also demote a target item, i.e., minimize the hit ratio of the target item. However, demotion is a special case of promotion [21, 35]. Specifcally, an atacker can promote other items such that the target item is demoted in recommendation lists. Terefore, we will focus on promotion atacks in this work.

Attack approach: Te atacker uses data poisoning atacks to achieve the atack goal. In particular, the atacker injects some fake users to the system. Each fake user gives a high rating score to the target item and well-crafed rating scores to certain selected items, which we call fller items. A key challenge for the atacker is to determine the fller items and their rating scores for each fake user. Since normal users ofen rate a small number of items, we assume the number of fller items for each fake user is at most n, to avoid being detected simply based on the number of rated items.

an atacker has the following background knowledge: 1) the recommendation algorithm used by the given recommender system; and 2) the user-item rating score matrix, which is usually publicly available and can be collected by the atacker. We note that the atacker could also collect a partial user-item rating score matrix for a subset of users and subset of items, and design atacks based on the partial matrix. Our threat model is also known as white-box seting. In our experiments, we will demonstrate that our atacks can also be transferred between recommender systems under the grey-box seting (i.e., the atacker does not know the parameters of the recommendation algorithm) or the black-box seting (i.e., the atacker does not know the recommendation algorithm).

In practice, an atacker ofen has limited resources so the atacker can only inject a bounded number of fake users into the system, though the bounded number could still be large. For instance, an atacker could leverage compromised machines to register and maintain fake users. Detecting such fake users is also known as Sybil detection, and many methods (e.g., [8, 28, 32]) have been developed to detect fake users. For instance, the service provider could analyze the IP addresses of the users to detect fake ones. To avoid such IP-based detection, an atacker ofen registers a small number of fake users on a compromised machine. Indeed, Tomas et al. [29] found that a half of compromised machines under an atacker’s control maintain less than 10 fake users in online social networks. More formally, we assume the atacker can inject m fake users into the recommender system.

3.2 Attacks as an Optimization Problem

We formulate poisoning atacks as an optimization problem, solving which maximizes the hit ratio of the target item. Let be the rating score vector of a fake user is the rating score that the fake user v gives to the item i. We consider a rating score is in the set of integers is the maximum rating score. For instance, in many recommender systems, 5. A rating score of 0 means that the user did not rate the corresponding item. Essentially, we aim to fnd the rating score vector for each fake user that maximizes the hit ratio of the target item. Specifcally, we fnd the rating score vectors via solving the following optimization problem:

where is the set of m fake users, is the number of non-zero entries in the rating score vector , and n is the maximum number of fller items (the fller items do not include the target item). Te hit ratio h(t), which is the fraction of normal users whose top-N recommended items include the target item t, is computed by a recommender system on the entire user-item rating score matrix that includes the m fake users. We note that our formulation in Equation 3 is applicable to data poisoning attacks to any recommender system. In this work, we will focus on graph-based recommender systems.

4 OUR POISONING ATTACKS

4.1 Overview

A solution to the optimization problem in Equation 3 is a data poisoning atack. However, fnding the exact optimal solution to the optimization problem in Equation 3 is computationally intractable (i.e., NP-hard) because 1) the objective function h(t) is related to the rating score variables ) in a very complex way, and 2) the variables are integer variables. Terefore, we propose techniques to fnd approximate solutions to the optimization problem.

Specifcally, to address the computational challenge, we propose several approximation techniques. First, instead of optimizing the rating scores for the m fake users simultaneously, we optimize their rating scores one by one. In particular, given the normal users and fake users we have added so far, we fnd the rating scores for the next fake user to optimize the hit ratio of the target item. Second, we approximate the hit ratio h(t) in the objective function using some function that is easier to optimize. Specifcally, since graph-based recommender systems leverage the stationary probabilities of items to make recommendations, our approximate objective function roughly requires that the stationary probabilities of the target item are high for many users. Tird, we relax the rating scores to be continuous variables in the range [0, ] and then transform them to integer rating scores afer solving the optimization problem. We propose a projected gradient descent based method to solve the optimization problem with the approximate objective function and relaxed continuous variables.

4.2 Approximating the Optimization Problem

Suppose t is the target item that the atacker aims to promote. We add fake users to the recommender system one by one. Assume G = (U , I, E) is the current user preference graph which includes rating scores for both normal users and fake users added so far. S is the set of normal users who have not rated the target item t. We denote the set of top-N recommended items for a user

Relaxing rating scores to be continuous variables: We add a fake user v to the user preference graph is the rating score that the fake user gives to item i. We model as the weight of the edge (v,i). For simplicity, we denote by the vector of weights of edges that connect the fake user v and all items. Our goal is to fnd the edge weights that optimize the hit ratio of the target item. Since rating scores are integers, integer variables whose values could be 0. However, such integer variables make the optimization problem intractable. Terefore, we relax the variables as continuous variables whose values are in the range [0, ], solve the optimization problem using the continuous variables, and transform them to integer rating scores. Note that is diferent from . Specifcally, is a continuous variable we use to model a rating score, while is the fnal integer rating score that user v gives to item i.

Approximating the hit ratio: Since the hit ratio is related to the edge weights in a very complex way, which makes the optimization problem intractable, we approximate the hit ratio using the stationary probabilities of random walks, which are used to generate the top-N recommended items in graph-based recommender systems. In the user preference graph with the new fake user v, to make recommendations for a normal user u, we frst perform a random walk fromu and compute its stationary probability distribution , where is the stationary probability for item i. Specifcally, the stationary probability distribution is computed according to Equation 1, where the transition matrix Q is a function of the edge weights . Te recommendation list consists of the N items that 1) u has not rated yet and 2) have the largest stationary probabilities. Te target item t hits the user u if t is among the recommendation list for a certain item i in the recommendation list , otherwise the target item does not hit the user u.

1) Loss function for one user. To approximate the hit ratio, we leverage a over the stationary probability distribution for each user u. We aim to design a loss function that satisfes two goals: 1) for each item (i.e., the target item ranks before the item i), then the loss for item i is smaller, and 2) the loss is smaller if the target item ranks higher in the recommendation list . To achieve these goals, we adopt the following loss

function:

where is called the Wilcoxon-Mann-Whitney loss function [3] and b is a parameter called width. In the machine learning community, the Wilcoxon-Mann-Whitney loss function is known to optimize the ranking performance [3], i.e., the loss is smaller when the target item ranks higher in the recommendation list in our case.

2) Loss function for all normal users. Our goal is to recommend the target item to as many normal users as possible. Terefore, we sum the loss of all normal users as follows:

where S is the set of normal users who have not rated the target item yet.

3) Approximate optimization problem. Recall that, in our threat model, each fake user rates at most n items to avoid detection, which essentially constrains the values of . Considering this constraint, we propose to solve the following optimization problem:

where regularizes and is used to model the constraint that each fake user can rate a small number of items, while balances the regularization term and the loss function.

4.3 Solving the Optimization Problem

We solve the optimization problem in Equation 6 using projected gradient descent. Specifcally, in each iteration, we compute the gradient of with respect toa small step towards the inverse direction of the gradient, and project each back to the range . We can compute the gradient of as

Table 1: Dataset statistics.

follows:

where Te key challenge of computing the gradient is to compute the gradient for each normal user u. From Equation 1, we have:

Furthermore, according to Equation 2, we have:

where is the discrete rating score that user x gave to the item y when x is not the new fake user, and is the continuous edge weight to be optimized when x is the new fake user. Terefore, Equation 8 is a linear system of equations with respect to

iteratively solve the linear system to obtain . Afer solving

4.4 Generating Rating Scores

Afer solving the weights , we generate rating scores for the fake user v. First, we assume the fake user gives the maximum rating score to the target item. Second, we rank the items according to the weights and select the n items with the highest weights as the fller items. Te fake user only generates rating scores for the fller items. Tird, for each fller item, we sample a number from a normal distribution that is fted to the rating scores that all normal users gave to the item, and then discretize the number to an integer rating score. We only use the weights to select fller items instead of assigning their rating scores, because the weights are approximate values. We generate rating scores for the fller items from such a normal distribution so that the fake user is likely to be similar to more normal users, which makes it more likely to recommend the target item to more normal users.

Algorithm 1 summarizes our poisoning atacks. We generate fake users one by one. For each fake user, we use projected gradient descent to solve the optimization problem in Equation 6 with the current rating score matrix (i.e., the current user preference graph). Afer solving the weights, we generate rating scores. Specifcally, at Line 9 is the normal distribution with mean and variance that are fted using the rating scores that normal users gave to the item j.

5 EXPERIMENTS

5.1 Experimental Setup

5.1.1 Datasets. We perform experiments using two real-world datasets, which are widely used for evaluating recommender systems in the data mining community. Te frst dataset is MovieLens 100K (Movie) [23]. Tis dataset consists of 943 users, 1,682 movies, and 100,000 ratings. Te second dataset is Amazon Instant Video (Video) [2], which includes 5,073 users, 10,843 items, and 48,843 ratings. We defne the sparsity of a dataset as follows:

As we will show, the atack performance is related to the sparsity of a recommender system. Table 1 shows the dataset statistics.

5.1.2 Compared Atacks. We compare our poisoning atacks to several poisoning atacks. In all these atacks, an atacker injects m fake users to the recommender system. Each fake user gives the maximum rating score to the target item and gives certain rating scores to n selected items (called fller items). Diferent atacks use diferent strategies to select the fller items and generate rating scores for them.

Random attack [19]: In this atack, the atacker frst fts a normal distribution for the rating scores in the entire user-item rating score matrix. For each fake user, the atacker selects n items as the fller items uniformly at random. Ten, for each fller item, the atacker samples a number from the normal distribution and discretizes it to be a rating score.

Average attack [19]: In this atack, the atacker fts a normal distribution for the rating scores of each item. Like the random atack, average atack also samples n items as fller items uniformly at random. However, for each fller item, the atacker generates a rating score from the normal distribution fted for the item. Te intuition is that generating rating scores around the average rating scores of fller items could enable the fake users to be more similar to normal users, and thus have a larger efect on the recommendations.

Bandwagon attack [21]: Tis atack considers item popularity when selecting fller items. We implement a variant of bandwagon atack as follows: for each fake user, the atacker selects 10% items whose average rating scores are high (e.g., 5 in our experiments) and selects 90% items uniformly at random as fller items. For each fller item, the atacker generates a rating score from the normal distribution fted for the entire user-item rating score matrix (like the random atack). Te intuition is that the atacker aims to recommend the target item to users who rated the popular items.

Co-visitation attack [35]: Tis atack was designed for association-rule-based recommender systems. We note that in the original atack, the atacker does not necessarily need to register fake users, because some association-rule-based recommender systems consider visitations from any visitors to make recommendations. In our work, we focus on recommender systems using rating scores and only registered users can provide rating scores. Terefore, the atacker injects fake users to the system. Moreover, if a user rates both items i and j, then we say i and j are co-visited by the user.

Terefore, the atack technique developed by Yang et al. [35] essentially fnds the fller items for each fake user. For each fller item of each fake user, we generate a rating score from the normal distribution fted for the item (like the average atack).

Items). We consider two types of target items. First, an atacker aims to promote a random target item. Specifcally, in our experiments, we sample an item uniformly at random and treat it as the target item. Second, an atacker could also promote an unpopular item (e.g., a new item that belongs to the atacker). To simulate this atacker, we sample an item that has 5 ratings at most uniformly at random and treat it as the target item.

5.1.4 Evaluation Metric (HR@N). We use the hit ratio (HR@N) as our evaluation metric. Suppose the recommender system recommends N items for each user. Given a target item, HR@N is the fraction of normal users whose N recommended items include the target item. For both random target items and unpopular target items, we compute the hit ratio averaged over 10 target items.

5.1.5 Parameter Seting. Without otherwise mentioned, we use the following default parameter seting: the restart probability graph-based recommender systems is set to be 0.3, 0.01, N = 10, and n = 10. Moreover, the number of fake users (i.e., atack size) is 3% of the normal users in the recommender system. By default, we assume graph-based recommender system is used.

5.2 Attacking Graph-based Systems

We frst consider the white-box seting, i.e., the graph-based recommender system and its restart probability are known to the atacker. Impact of attack size: Table 2 shows the results for the compared poisoning atacks with diferent atack sizes. Te atack size means that the number of fake users is a certain fraction of the normal users, e.g., 1% atack size means that the number of fake users is 1% of the number of normal users. Te row in “None” means the hit ratios without any atacks. First, our atack can efectively promote target items. For instance, in the Video dataset, when injecting 1% fake users, the hit ratio of a random target item increases by around 33 times, while the hit ratio of an unpopular target item increases by around 580 times. Second, our atack is signifcantly more efective than existing atacks. For instance, in the Movie dataset, when injecting 1% fake users, our atack improves the hit ratio upon the best compared atack by 2.3 times for a random target item, while our atack improves the hit ratio from 0 to 0.0042 for an unpopular target item. Te reason is that random atack, average atack, and bandwagon atack are agnostic to recommender systems, while the co-visitation atack was specifcally designed for association-rule-based recommender systems.

Tird, the hit ratio gain is more signifcant for unpopular target items than random target items. For instance, our atack improves the hit ratio by 96 times and 1700 times for a random target item and an unpopular target item respectively, when injecting 3% fake users into the Video dataset. Fourth, all atacks are more efective on the Video dataset than the Movie dataset. We speculate the reason is that Video is more sparse, and thus is easier to atack. More specifcally, when the dataset is more sparse, it is easier to inject fake users that are similar to a large number of normal users.

Table 2: HR@10 for diferent attacks with diferent attack sizes.

Table 3: HR@N for diferent N.

Impact of the number of recommended items: Table 3 shows the hit ratios for diferent atacks when the recommender system recommends diferent numbers (i.e., N) of items to users, where random target items are used and the atack size is fxed to be 3%. First, we observe that our atack is efective and is more efective than the existing atacks for diferent values of N. Second, when N is smaller, the hit ratio gains of our atack over existing atacks are more signifcant. For instance, when N = 20 and N = 5, our atack’s hit ratios improve upon the best existing atacks by twice and by 9.5 times in the Movie dataset, respectively. Tis indicates that our atack ranks the target item higher in the recommendation lists than existing atacks. Te reason is that the Wilcoxon-Mann-Whitney loss function [3] adopted by our atacks aims to optimize the ranking performance of the target item.

Impact of the number of fller items: Figure 2 shows the impact of the number of fller items on our atacks for random target items. On the Movie dataset, the hit ratio decreases as the atacker uses more fller items. However, on the Video dataset, the hit ratio

Figure 2: Impact of the number of fller items.

increases and fuctuates as more fller items are used. Terefore, the relationship between the hit ratio and the number of fller items heavily depends on datasets. We note that Mobasher et al. [21] had similar observations for the average and bandwagon atacks. Intuitively, an atacker should be more powerful and achieve beter hit ratios when using more fller items. Our results and previous study [21] show that this intuition does not hold. Understanding such phenomena theoretically is an interesting future work.

5.3 Transferring to Other Systems

In the previous section, we assume that the atacker has a white-box access to the target recommender system. In this section, we consider an atacker has a gray-box and black-box access to the recommender system. In particular, in the gray-box seting, the recommender system is still graph-based recommender system, but the key parameter is unknown to the atacker. In the black-box seting, the atacker does not know the target recommender system algorithm. To simulate such black-box seting, we assume the atacker generates fake users based on a graph-based recommender system, while the target recommender system uses matrix factorization.

Gray-box setting: Te atacker uses a restart probability graph-based recommender system to generate fake users. Figure 3 shows the hit ratios for random target items of our atacks when

Figure 3: Hit ratio of our attack as a function of the restart probability of the target graph-based recommender system under the gray-box setting.

the target graph-based recommender system uses diferent restart probabilities. We observe that the hit ratio reaches the maximum when the restart probability is 0.3. Te reason is that the atacker also sets the restart probability to be 0.3, which essentially reduces to a white-box atack. When the target recommender system uses a restart probability other than 0.3, our atack is less efective. However, our atack is still much more efective than existing atacks (please refer to Table 2).

Black-box setting: We assume the atacker generates fake users using a graph-based recommender system, while the target recommender system uses matrix factorization. In particular, we use the popular matrix factorization technique proposed in [17] to implement the target recommender system. Table 4 shows the hit ratios of our atacks and existing atacks for random target items. First, all compared atacks can transfer to matrix factorization based recommender systems, especially on the Video dataset. Specifcally, all atacks signifcantly improve the hit ratios of target items upon no atacks on the Video dataset. However, the hit ratio gains on the Movie dataset is less signifcant. We suspect the reason is that the Movie dataset is denser and is harder to atack.

Second, the diferences between our atack and the existing atacks are small, which means that diferent atacks have similar transferability to matrix factorization based recommender systems. Tird, the hit ratio gains of all atacks are less (or more) signifcant in the black-box seting than in the white-box seting on the Movie (or Video) dataset (comparing Table 2 and Table 4). For instance, on the Movie dataset, our atack improves the hit ratio over no atacks by 3 times and by 20% in the white-box seting and black-box seting, respectively, when the atack size is 1%. However, on the Video dataset, our atack improves the hit ratio over no atacks by 33 times and 4000 times in the white-box seting and black-box seting, respectively, when the atack size is 1%. Tis is because matrix factorization is known to achieve beter hit ratios when the dataset is denser [17]. For instance, matrix factorization achieves lower hit ratios than the graph-based recommender system on the

Table 4: HR@10 under the black-box setting, where the attacker generates fake users using a graph-based recommender system while the target recommender system uses matrix factorization.

Video dataset when there are no atacks. Afer the atacker adds fake users, the target item has dense rating scores and thus it is recommended to many users by matrix factorization. As a result, the poisoning atacks have even more signifcant hit ratio gains over no atacks in the black-box seting than in the white-box seting.

6 DETECTING FAKE USERS

Detecting fake users is closely related to Sybil detection in social networks. Many methods have been developed for Sybil detection. Tese methods leverage IP addresses (e.g., [28]), user behavior (e.g., [32]), or social relationships between users (e.g., [8, 30, 31]). Since we do not have access to IP addresses nor social relationships of users, we explore a behavior based method. In particular, we extract a set of features from a user’s rating scores and train a binary classifer to classify users to be normal or fake. We will also study the efectiveness of the poisoning atacks when the recommender system has deployed such a detector to predict fake users and has excluded the predicted fake users from the recommender system.

Rating scores based detection: Intuitively, the fake users’ rating scores are generated in specifc ways, and thus it may be possible to distinguish between normal users and fake users using their rating scores. Indeed, previous studies [5, 21] extracted several features from rating scores to train a binary classifer to distinguish between normal users and fake users. We adopt these features in our work. Specifcally, the features are as follows.

• Rating Deviation from Mean Agreement (RDMA) [5]: Tis feature measures the average deviation of a user’s rating scores to the mean rating scores of the corresponding items. Formally, for a user u, RDMA is computed as follows:

where is the set of items that user u has rated, number of items in is the rating score that u gave

Table 5: Detection results for diferent attacks.

Table 6: HR@10 for diferent attacks when the service provider deploys a classifer to predict fake users and excludes the predicted fake users from the system.

to item is the average rating score for item the total number of ratings for item i.

• Weighted Degree of Agreement (WDA) [21]: Tis feature is simply the numerator of the RDMA feature, i.e., this feature is computed as follows:

• Weighted Deviation from Mean Agreement (WDMA) [21]: Tis feature is also based on RDMA, but it puts higher weights on rating deviations for items that have less ratings. Te WDMA feature for a user u is calculated as follows:

• Mean Variance (MeanVar) [21]: Tis feature measures the average variance of a user’s rating scores to the mean rating scores of the corresponding items. Specifcally, the

• Filler Mean Target Diference (FMTD) [21]: Tis feature measures the divergence between a user’s rating scores, and it is computed as follows:

where is the set of items in gave the maximum rating score and includes all other items in

For each poisoning atack, the service provider generates some fake users using the atack and labels some normal users as a training dataset. In our experiments, we generate 150 fake users (these fake users could be diferent from the fake users an atacker synthesizes when performing atacks) and sample 150 normal users as the training dataset. Ten, using the above features, the service provider learns a KNN classifer, where K is determined via cross-validation in the training dataset.

Results of detecting fake users: We apply the classifers to detect fake users generated by diferent poisoning atacks. We use False Positive Rate (FPR) and False Negative Rate (FNR) to measure the detection performance. Specifcally, FPR is the fraction of normal users that are predicted to be fake, while FNR is the fraction of fake users that are predicted to be normal.

Table 5 shows the FPR and FNR when detecting the fake users generated in our experiments in Section 5 under the default parameter seting. We observe that a small fraction of normal users are predicted to be fake. When the service provider excludes the predicted fake users from the recommender system, these normal users won’t receive personalized recommendations from the recommender system. Te service provider could leverage other methods to recommend items for such users, e.g., the service provider always recommends popular items to them (such recommendation is not personalized). Moreover, the detector misses a large fraction of fake users, i.e., FNR is large. Moreover, the FNR tends to increase as the atacker injects more fake users. A possible reason is that

more fake users have more diverse paterns, and thus it is harder to detect them. Attack efectiveness when detector is deployed: Suppose the service provider deploys the classifer to detect fake users. In particular, the service provider excludes the predicted fake users from the recommender system. Note that a small fraction of normal users will be excluded from the recommender system, while a large fraction of fake users will still be included in the recommender system. We re-compute the recommended items for each remaining user afer excluding the predicted fake users from the recommender system and re-compute the hit ratios of the target items. Te hit ratio of a target item is the fraction of the remaining normal users whose recommended items include the target item.

Table 6 shows the hit ratios of random target items for the compared poisoning atacks under the white-box seting. First, we observe that these atacks are still efective in many cases. Tis is because a large fraction of fake users are not detected. Second, compared to the case where the service provider does not detect fake users, the hit ratios are smaller (comparing Table 6 with Table 2). Te reason is that a large fraction of fake users are detected and excluded from the recommender system. Tird, our atack still substantially outperforms existing atacks.

7 CONCLUSION AND FUTURE WORK

In this work, we propose optimized poisoning atacks to graph-based recommender systems. We show that poisoning atacks to graph-based recommender systems can be formulated as an optimization problem and the optimization problem can be approximately solved by a projected gradient descent method. Via evaluations on real-world datasets, we fnd that our atacks can make a target item recommended to substantially more users. Moreover, our atacks are more efective than existing atacks for manipulating graph-based recommender systems. Te reason is that existing atacks are not optimized for graph-based recommender systems, while our atacks are. Our atacks can also transfer to other recommender systems under the gray-box and black-box setings. Te service provider can detect a large fraction of fake users but also falsely predict a small fraction of normal users to be fake, via using supervised machine learning techniques to analyze the users’ rating scores. Moreover, our atacks are still efective when the service provider deploys such a detector and excludes the predicted fake users from the recommender system.

Interesting future works include 1) evaluating our poisoning atacks on real-world graph-based recommender systems, 2) designing optimized poisoning atacks to other graph-based recommender systems (e.g., graph convolutional neural network based recommender systems [36]), 3) designing optimized poisoning atacks to neural network based recommender systems (e.g., [14]), and 4) designing defenses against poisoning atacks.

ACKNOWLEDGEMENTS

We thank the anonymous reviewers for their insightful feedback. Tis work is supported by the National Science Foundation under Grants No. CNS-1750198 and CNS-1801584. Any opinions, fndings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily refect the views of the funding agencies.

REFERENCES

[1] 2018. Cambridge Analytica. htps://www.theguardian.com/technology/2018/ mar/17/facebook-cambridge-analytica-kogan-data-algorithm

[2] Amazon Instant Video Dataset. 2018. htp://jmcauley.ucsd.edu/data/amazon/

[3] Lars Backstrom and Jure Leskovec. 2011. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining. ACM, 635–644.

[4] Joseph A. Calandrino, Ann Kilzer, Arvind Narayanan, Edward W. Felten, and Vitaly Shmatikov. 2011. “You Might Also Like:” Privacy Risks of Collaborative Filtering. In IEEE Symposium on Security and Privacy.

[5] Paul-Alexandru Chirita, Wolfgang Nejdl, and Cristian Zamfr. 2005. Preventing shilling atacks in online recommender systems. In Proceedings of the 7th annual ACM international workshop on Web information and data management. ACM, 67–74.

[6] James Davidson, Benjamin Liebald, Junning Liu, Palash Nandy, Taylor Van Vleet, Ullas Gargi, Sujoy Gupta, Yu He, Mike Lambert, Blake Livingston, et al. 2010. Te YouTube video recommendation system. In ACM conference on Recommender systems. ACM, 293–296.

[7] Francois Fouss, Alain Pirote, Jean-Michel Renders, and Marco Saerens. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on knowledge and data engineering 19, 3 (2007), 355–369.

[8] Neil Zhenqiang Gong, Mario Frank, and Prateek Mital. 2014. SybilBelief: A Semi-supervised Learning Approach for Structure-based Sybil Detection. IEEE Transactions on Information Forensics and Security 9, 6 (2014), 976 – 987.

[9] Neil Zhenqiang Gong and Bin Liu. 2016. You are Who You Know and How You Behave: Atribute Inference Atacks via Users’ Social Friends and Behaviors. In USENIX Security Symposium.

[10] Neil Zhenqiang Gong and Bin Liu. 2018. Atribute Inference Atacks in Online Social Networks. ACM Transactions on Privacy and Security (TOPS) 21, 1 (2018).

[11] Neil Zhenqiang Gong, Ameet Talwalkar, Lester Mackey, Ling Huang, Eui Chul Richard Shin, Emil Stefanov, Elaine(Runting) Shi, and Dawn Song. 2014. Joint Link Prediction and Atribute Inference using a Social-Atribute Network. ACM TIST 5, 2 (2014).

[12] Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. A Graph-based Push Service Platform. In DASFAA.

[13] Xiuqiang He, Wenyuan Dai, Guoxiang Cao, Ruiming Tang, Mingxuan Yuan, and Qiang Yang. 2015. Mining target users for online marketing based on App Store data. In IEEE International Conference on Big Data.

[14] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017. Neural Collaborative Filtering. In WWW.

[15] Jinyuan Jia and Neil Zhenqiang Gong. 2018. AtriGuard: A Practical Defense Against Atribute Inference Atacks via Adversarial Machine Learning. In USENIX Security Symposium.

[16] Jinyuan Jia, Binghui Wang, Le Zhang, and Neil Zhenqiang Gong. 2017. AtriInfer: Inferring User Atributes in Online Social Networks Using Markov Random Fields. In WWW.

[17] Y Koren, R Bell, and C Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 8 (2009), 30–37.

[18] Michal Kosinski, David Stillwell, and Tore Graepel. 2013. Private traits and atributes are predictable from digital records of human behavior. PNAS (2013).

[19] Shyong K Lam and John Riedl. 2004. Shilling recommender systems for fun and proft. In WWW.

[20] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. 2016. Data Poisoning Atacks on Factorization-Based Collaborative Filtering. In NIPS.

[21] Bamshad Mobasher, Robin Burke, Runa Bhaumik, and Chad Williams. 2007. Toward trustworthy recommender systems: An analysis of atack models and algorithm robustness. ACM Transactions on Internet Technology 7, 4 (2007), 23.

[22] Bamshad Mobasher, Robert Cooley, and Jaideep Srivastava. 2000. Automatic personalization based on web usage mining. Commun. ACM 43, 8 (2000), 142– 151.

[23] MovieLens Dataset. 2018. htps://grouplens.org/datasets/movielens/

[24] M. O’Mahony, N. Hurley, N. Kushmerick, and G. Silvestre. 2004. Collaborative Recommendation: A Robustness Analysis. ACM Transactions on Internet Technology 4, 4 (2004), 344–377.

[25] Tomas Pinckney. 2013a. Graph-based Recommendation Systems at eBay. htps: //www.youtube.com/watch?t=2400&v=Tg3dP2fZGSM

[26] Tomas Pinckney. 2013b. Planet Cassandra: Graph Based Recommendation Systems at eBay. htp://www.slideshare.net/planetcassandra/e-bay-nyc

[27] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based collaborative fltering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web. ACM, 285–295.

[28] Gianluca Stringhini, Pierre Mourlanne, Gregoire Jacob, Manuel Egele, Christopher Kruegel, and Giovanni Vigna. 2015. EVILCOHORT: Detecting Communities of Malicious Accounts on Online Services. In Usenix Security.

[29] Kurt Tomas, Damon McCoy, Chris Grier, Alek Kolcz, and Vern Paxson. 2013. Trafcking Fraudulent Accounts: Te Role of the Underground Market in Twiter Spam and Abuse. In USENIX Security Symposium.

[30] Binghui Wang, Neil Zhenqiang Gong, and Hao Fu. 2017. GANG: Detecting Fraudulent Users in Online Social Networks via Guilt-by-Association on Directed Graphs. In IEEE ICDM.

[31] Binghui Wang, Jinyuan Jia, Le Zhang, and Neil Zhenqiang Gong. 2018. Structurebased Sybil Detection in Social Networks via Local Rule-based Propagation. IEEE TNSE (2018).

[32] Gang Wang, Tristan Konolige, Christo Wilson, and Xiao Wang. 2013. You are How You Click: Clickstream Analysis for Sybil Detection. In Usenix Security.

[33] Udi Weinsberg, Smriti Bhagat, Stratis Ioannidis, and Nina Taf. 2012. BlurMe: Inferring and obfuscating user gender based on ratings. In RecSys.

[34] Xinyu Xing, Wei Meng, Dan Doozan, Alex C Snoeren, Nick Feamster, and Wenke Lee. 2013. Take Tis Personally: Pollution Atacks on Personalized Services. In USENIX Security. 671–686.

[35] Guolei Yang, Neil Zhenqiang Gong, and Ying Cai. 2017. Fake Co-visitation Injection Atacks to Recommender Systems. In NDSS.

[36] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In KDD.

[37] William Zeller and Edward W. Felten. 2008. Cross-Site Request Forgeries: Exploitation and Prevention. Technical Report. Princeton University.

designed for accessibility and to further open science