PaperlayerView exact revision on arXiv

Source-linked AI summary

Poisoning Attacks to Graph-Based Recommender Systems

Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, Jia Liu

arXiv:1809.04127v1cs.IRcs.CRcs.LGstat.ML

TL;DR

The paper addresses the open problem of optimizing poisoning attacks for graph-based recommender systems, where prior attacks were algorithm-agnostic or targeted other recommender types. It formulates bounded fake-user injection as an optimization problem, develops approximate solution techniques, and evaluates the attacks across white-, gray-, and black-box settings. On two real-world datasets, the attacks outperform existing methods for graph-based systems; with 1% fake users, one scenario produced an approximately 580-fold hit-ratio improvement for an unpopular target item.

  • Problem

    Graph-based recommender systems lack optimized poisoning attacks, while prior attacks are algorithm-agnostic or target matrix-factorization- and association-rule-based systems.

  • Method

    The paper formulates bounded fake-user injection as an optimization problem that maximizes the target item’s hit ratio and develops approximate solution techniques.

  • Results

    The attacks outperformed existing attacks for graph-based recommenders; with 1% fake users, an unpopular target’s hit ratio improved by around 580 times in one white-box scenario.

  • Takeaways & Limitations

    Optimizing poisoning attacks for graph-based recommenders enables substantially more effective target-item manipulation than existing attacks in the evaluated settings.

  • Takeaways & Limitations

    Future work includes evaluating the attacks on real-world graph-based recommender systems and designing defenses against poisoning attacks.

Abstract

from arXiv · show

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 attacks, in which an attacker injects fake data to a given system such that the system makes recommendations as the attacker desires. However, these poisoning attacks are either agnostic to recommendation algorithms or optimized to 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. However, how to design optimized poisoning attacks for graph-based recommender systems is still an open problem. In this work, we perform a systematic study on poisoning attacks to graph-based recommender systems. Due to limited resources and to avoid detection, we assume the number of fake users that can be injected into the system is bounded. The 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 attacks 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 attacks and compare them with existing attacks 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) settings using two real-world datasets. Our results show that our attack is effective and outperforms existing attacks for graph-based recommender systems. For instance, when 1% fake users are injected, our attack can make a target item recommended to 580 times more normal users in certain scenarios.

1 INTRODUCTION

The paper studies poisoning attacks against graph-based recommender systems, where optimized fake-user ratings aim to promote a target item under bounded injection constraints. It formulates the attack as an optimization problem, develops approximate solution techniques, and evaluates effectiveness across attacker-knowledge settings.

  • Existing poisoning attacks are algorithm-agnostic or optimized for matrix-factorization- and association-rule-based systems, leaving graph-based systems insufficiently addressed.
  • Graph-based recommenders represent ratings as a user preference graph and rank unrated items using stationary probabilities from a restart-based random walk.
  • The attacker injects at most m fake users, each rating at most n filler items, to maximize the target item’s hit ratio among normal users.
  • The attack optimization is computationally intractable, so the paper approximates hit ratio, relaxes integer ratings to continuous variables, and applies projected gradient descent.
  • With 1% fake users and 10 recommendations per user, the attack improved an unpopular target’s hit ratio by around 580 times in the white-box setting.
  • The study evaluates attacks against existing methods on two real-world datasets and examines fake-user detection, finding 20%–50% of fake users falsely predicted as normal.

2 BACKGROUND AND RELATED WORK

The background describes collaborative filtering and graph-based recommendation, then situates poisoning, profile-pollution, and privacy attacks within recommender-system security research.

  • 2.1 Collaborative Filtering: Collaborative filtering analyzes user–item rating matrices to recommend previously unrated items, and includes neighborhood-, association-rule-, matrix-factorization-, and graph-based approaches.
  • 2.1 Collaborative Filtering: A user preference graph uses user and item nodes, rating edges, and edge weights equal to the corresponding rating scores.
  • 2.1 Collaborative Filtering: Graph-based recommendation performs a user-rooted random walk with restart probability α and ranks unrated items by their converged stationary probabilities.
  • 2.2 Attacks to Recommender Systems: Poisoning attacks inject fake users and ratings during training to manipulate recommendations, whereas profile-pollution attacks alter normal users’ profiles during testing.
  • 2.2 Attacks to Recommender Systems: Earlier poisoning attacks were heuristic and algorithm-agnostic, while later work optimized attacks for matrix-factorization- and association-rule-based recommenders.
  • 2.2 Attacks to Recommender Systems: Profile-pollution attacks can manipulate browsing histories through CSRF, while item- and attribute-inference attacks target users’ privacy.

3 PROBLEM FORMULATION

The threat model targets promotion of an item through bounded fake-user injection, assuming substantial knowledge in the white-box setting. The attack is formulated as constrained rating optimization.

  • 3.1 Treat Model: The attacker promotes target item t by maximizing h(t), the fraction of normal users whose top-N recommendations include t.
  • 3.1 Treat Model: Demoting an item is treated as a special case of promotion because promoting other items can reduce its presence in recommendation lists.
  • 3.1 Treat Model: Each fake user rates the target highly and assigns crafted scores to at most n filler items, limiting profile size to reduce detection based on rated-item counts.
  • 3.1 Treat Model: The white-box threat model assumes knowledge of the recommendation algorithm and the user–item rating matrix, though attacks may use partial matrices.
  • 3.1 Treat Model: Resource constraints bound the number of injectable fake users, while Sybil-detection methods can use signals such as users’ IP addresses.
  • 3.2 Attacks as an Optimization Problem: The optimization searches for integer rating vectors for m fake users, with each vector containing at most n+1 nonzero entries including the target item.
  • 3.2 Attacks as an Optimization Problem: The objective computes the target item’s hit ratio on the full rating matrix after adding the fake users.

4 OUR POISONING ATTACKS

The paper approximates an intractable poisoning objective for graph-based recommenders by optimizing fake-user edge weights and converting them into constrained rating profiles. It uses stationary probabilities, continuous relaxation, projected gradient descent, and sequential fake-user injection.

  • Overview: The exact poisoning optimization is NP-hard because the hit ratio depends complexly on integer fake-user rating variables.The paper therefore seeks approximate solutions rather than exact optima.
  • Algorithm: Each fake user is optimized sequentially, using the current graph and rating matrix before adding the next fake user.This decomposes joint optimization into one-fake-user-at-a-time updates.
  • Solving the Optimization Problem: Projected gradient descent optimizes continuous edge weights in [0,rmax], after which the weights are transformed into integer rating scores.The gradient is computed with respect to the fake user’s edge-weight vector and projected back into the permitted range.
  • Approximating the Optimization Problem: The approximate objective uses stationary probabilities because graph-based recommenders use them to generate top-N recommendations.The loss is constructed over each normal user’s recommendation list and summed across users.
  • Approximating the Optimization Problem: The Wilcoxon-Mann-Whitney loss is used to optimize ranking performance, becoming smaller when the target item ranks higher.The aggregate objective sums losses over normal users who have not rated the target item.
  • Algorithm: The generated fake user assigns the maximum rating to the target item and selects the n highest-weight items as filler items.Filler-item ratings are sampled from item-specific normal distributions fitted to normal users’ ratings.

5.1 Experimental Setup

The experimental setup evaluates poisoning attacks on two real-world recommender datasets, against several baselines, for random and unpopular target items using HR@N. The default setting uses graph-based recommendation with a 3% attack size.

  • Datasets: The experiments use MovieLens 100K and Amazon Instant Video, containing 943 users and 1,682 movies, and 5,073 users and 10,843 items, respectively.MovieLens has 100,000 ratings, while Amazon Instant Video has 48,843 ratings.
  • Baselines: The study compares its attacks with random, average, bandwagon, and co-visitation attacks using the same fake-user and filler-item limits.The baselines differ in filler-item selection and rating-score generation strategies.
  • Target Items: Target items are sampled either uniformly at random or uniformly from items with at most 5 ratings.The second protocol represents promotion of an unpopular item, such as a new attacker-owned item.
  • Evaluation Metric: HR@N is the fraction of normal users whose N recommended items include the target item, averaged over 10 target items.The metric is computed for both random and unpopular target items.
  • Default Parameters: The default configuration sets α = 0.3, λ = 0.01, b = 0.01, N = 10, n = 10, and attack size to 3% of normal users.The default recommender is graph-based.

5.2 Attacking Graph-based Systems

In white-box evaluations, the attack effectively promotes target items and outperforms existing attacks, with gains varying by target popularity, dataset, recommendation-list length, and filler-item count.

  • Impact of attack size: 33 times and 580 times: in the Video dataset, injecting 1% fake users increases hit ratios for random and unpopular targets, respectively.These results are reported for the white-box setting.
  • Target and dataset effects: 96 times and 1700 times: with 3% fake users in Video, hit-ratio gains for random and unpopular targets, respectively, show larger gains for unpopular items.All attacks are reported as more effective on Video than Movie, which the authors speculate may reflect Video’s greater sparsity.
  • Number of recommended items: Twice and 9.5 times: in Movie, the attack improves upon the best existing attacks at N = 20 and N = 5, respectively.The comparison uses random target items and a fixed 3% attack size; larger gains at smaller N indicate higher target-item ranking.
  • Number of filler items: The attack’s hit-ratio relationship with filler-item count is dataset-dependent: it decreases on Movie but increases and fluctuates on Video.The authors note that this contradicts the intuition that more filler items should always improve attack power.

5.3 Transferring to Other Systems

The attacks transfer beyond their original graph-based setting: they remain effective when the target uses an unknown restart probability or matrix factorization. Transferability and gains vary across datasets and settings.

  • Gray-box setting: In the gray-box setting, the attacker generates fake users with restart probability α = 0.3 while the target system uses different restart probabilities.The attacker knows the graph-based algorithm but not the target’s restart probability.
  • Gray-box setting: The hit ratio is maximal when the target restart probability is 0.3, because the attack then effectively becomes white-box.With other restart probabilities, effectiveness decreases but remains much higher than existing attacks.
  • Black-box setting: In the black-box setting, the attacker uses a graph-based recommender to generate fake users while the target uses matrix factorization.Table 4 reports HR@10 for random target items under this cross-algorithm transfer setting.
  • Black-box setting: The attacks transfer to matrix-factorization systems, especially on the Video dataset, where all attacks significantly improve target-item hit ratios over no attacks.The differences among attacks are small, indicating similar transferability to matrix factorization.
  • Black-box setting: At 1% attack size, the attack improves hit ratio over no attacks by 3 times versus 20% on Movie and 33 times versus 4000 times on Video in white-box versus black-box settings.The larger black-box gain on Video is attributed to matrix factorization benefiting from denser rating scores after fake users are added.

6 DETECTING FAKE USERS

The paper evaluates rating-score-based detection of fake users with supervised classifiers and measures both false positives among normal users and false negatives among fake users. Detection reduces attack hit ratios, but the attack remains effective because many fake users evade detection.

  • Detection method: The detector uses rating-score features, including RDMA, WDA, WDMA, MeanVar, FMTD, and related rating-pattern measures.These features characterize deviations, agreement, variance, and differences between filler-item and target-item ratings.
  • Detection method: The service provider trains a KNN classifier using 150 generated fake users and 150 sampled normal users.The value of K is selected through cross-validation on the training dataset.
  • Detection results: Detection performance is measured with False Positive Rate (FPR) for normal users and False Negative Rate (FNR) for fake users.FPR is the fraction of normal users predicted fake, while FNR is the fraction of fake users predicted normal.
  • Detection results: A small fraction of normal users are predicted to be fake, while more diverse fake-user patterns make larger attacks harder to detect.Excluded normal users lose personalized recommendations, whereas popular-item recommendations remain possible.
  • Attack effectiveness with detection: After predicted fake users are excluded, poisoning attacks remain effective in many cases because a large fraction of fake users are not detected.Hit ratios are lower than without detection, but the proposed attack still substantially outperforms existing attacks.

7 CONCLUSION AND FUTURE WORK

The paper formulates optimized poisoning attacks for graph-based recommender systems, approximately solves them, and finds them effective against graph-based systems and transferable settings. It also identifies future evaluation, attack-design, and defense directions.

  • Conclusion: The proposed attacks formulate graph-based recommender-system poisoning as an optimization problem approximately solved with projected gradient descent.The objective is to make a target item recommended to substantially more users.
  • Conclusion: Evaluations on real-world datasets find that the attacks substantially increase target-item recommendations and outperform attacks not optimized for graph-based systems.The paper attributes this advantage to optimizing the attacks for graph-based recommender systems.
  • Conclusion: The attacks also transfer to other recommender systems under gray-box and black-box settings and remain effective when a detector excludes predicted fake users.The detector catches a large fraction of fake users but falsely predicts a small fraction of normal users as fake.
  • Future work: Future work includes evaluating attacks on real-world graph-based systems, extending them to other graph-based and neural recommenders, and designing defenses.The proposed examples include graph convolutional neural network-based recommender systems.
Loading 1809.04127v1…