Source-linked AI summary
Influence Function based Data Poisoning Attacks to Top-N Recommender Systems
Minghong Fang, Neil Zhenqiang Gong, Jia Liu
TL;DR
Recommender systems can be manipulated by injecting fake users with crafted ratings to promote a target item, but optimizing those ratings is difficult. The paper uses influence functions and approximate optimization for matrix-factorization-based top-N systems, and reports that its attacks outperform existing methods, including under partial knowledge and detection.
Problem
The paper addresses the open question of designing customized poisoning attacks for widely deployed matrix-factorization-based top-N recommenders.
Method
The paper formulates fake-user rating design as non-convex integer optimization and approximately solves it using influence-based user selection, continuous relaxation, and gradient-based optimization.
Results
The proposed attacks outperform existing methods and remain effective with partial system knowledge and fake-user detection; on Yelp, 0.5% fake users yielded 150 times more target-item appearances.
Takeaways & Limitations
Influence functions can enhance poisoning attacks for matrix-factorization-based and graph-based top-N recommender systems, although weighting all users sacrifices computational efficiency.
Takeaways & Limitations
The attack formulation is an integer program that is NP-hard in general, so the paper relies on approximate solutions.
Abstract
from arXiv · showhide
Recommender system is an essential component of web services to engage users. Popular recommender systems model user preferences and item properties using a large amount of crowdsourced user-item interaction data, e.g., rating scores; then top-$N$ items that match the best with a user's preference are recommended to the user. In this work, we show that an attacker can launch a data poisoning attack to a recommender system to make recommendations as the attacker desires via injecting fake users with carefully crafted user-item interaction data. Specifically, an attacker can trick a recommender system to recommend a target item to as many normal users as possible. We focus on matrix factorization based recommender systems because they have been widely deployed in industry. Given the number of fake users the attacker can inject, we formulate the crafting of rating scores for the fake users as an optimization problem. However, this optimization problem is challenging to solve as it is a non-convex integer programming problem. To address the challenge, we develop several techniques to approximately solve the optimization problem. For instance, we leverage influence function to select a subset of normal users who are influential to the recommendations and solve our formulated optimization problem based on these influential users. Our results show that our attacks are effective and outperform existing methods.
1 INTRODUCTION
The paper studies poisoning attacks that inject fake users to promote a chosen item in matrix-factorization-based top-N recommenders. It develops influence-function-based optimization techniques and reports strong effectiveness, including under limited system knowledge and detection.
- Recommender systems learn user preferences and item features from user-item interactions, then recommend each user the top-N best-matching items.
- The paper formulates fake-user rating design as an attack that maximizes recommendations of an attacker-chosen target item.The attacker selects filler items and rating scores for injected fake users.
- Influence functions identify influential normal users, while continuous relaxation, greedy selection, and gradient-based optimization approximately solve the difficult rating-design problem.The influential-user selection subproblem has a submodular property with a (1 − 1/e) approximation guarantee.
- The attack is evaluated against multiple baselines on Yelp and Amazon Digital Music benchmark datasets.The experiments assess target-item promotion in matrix-factorization-based top-N recommenders.
- 150 times more normal users saw a randomly selected target item in their top-N lists when only 0.5% fake users were injected on Yelp.The attack outperformed baselines and remained effective without knowing the target recommender’s parameters.
- Influence-function weighting also improves attack effectiveness and extends the approach to graph-based top-N recommenders, at the cost of computational efficiency.
2 RELATED WORK
Prior work established recommender-system poisoning across several architectures, but earlier system-agnostic attacks were unsatisfactory and matrix-factorization attacks did not target top-N lists.
- Data poisoning attacks manipulate recommender-system training interactions to alter recommendations, and earlier random or average attacks achieved unsatisfactory performance.
- Recent attacks are tailored to association-rule-based, graph-based, and matrix-factorization-based recommender systems.
- Graph-based attacks inject crafted ratings to promote a target item by optimizing fake-user ratings.
- Matrix-factorization poisoning previously manipulated predictions for all missing rating entries rather than top-N recommendation lists.
- Data poisoning research also covers anomaly detectors, spam filters, SVMs, regression, graph-based methods, neural networks, and federated learning.Existing studies report attacks that significantly affect these systems’ performance.
3 PROBLEM FORMULATION
The paper defines matrix-factorization recommendations, the attacker’s threat model, and a hit-ratio maximization problem for selecting ratings of injected fake users. The resulting integer program is NP-hard, motivating approximate solution methods.
- 3.1 Matrix-Factorization-Based Recommender Systems: A Primer: Matrix factorization represents users and items as latent factor vectors and stores observed ratings in a user-item rating matrix.
- 3.1 Matrix-Factorization-Based Recommender Systems: A Primer: Predicted ratings equal x_u^T y_i, and the system recommends the N unseen items with highest predicted scores.
- 3.2 Threat Model: The attacker seeks to maximize the hit ratio h(t), the fraction of normal users whose top-N lists contain target item t.
- 3.2 Threat Model: The attacker may know all ratings and the recommendation algorithm or only have access to some ratings.The paper states that its attacks remain effective with partial knowledge.
- 3.3 Attack Strategy: Each fake user rates target item t and at most n filler items using integer scores from 0 through r_max.The attacker can inject m fake users, and each fake user rates at most n+1 items including the target.
- 3.3 Attack Strategy: The optimization chooses each fake user’s rated-item set and scores to maximize h(t), with nonzero entries representing rated items.
- 3.3 Attack Strategy: Rating scores are constrained to integer values in {0, 1, · · ·, r_max}.
- 3.3 Attack Strategy: HRM is an integer programming problem and is NP-hard in general, so the paper develops approximate solution techniques.
4 OUR SOLUTION
The solution approximately optimizes fake-user ratings and uses influence functions to select influential normal users for target-item promotion. It derives influence estimates for matrix-factorization recommenders and exploits submodularity for greedy selection with an approximation guarantee.
- Solving Rating Scores for a Fake User: The attack optimizes fake users’ rating scores one at a time, relaxing discrete ratings to continuous variables before converting them back to discrete values.The relaxed variables support gradient-based optimization, while the final ratings satisfy the discrete rating constraints.
- Solving Rating Scores for a Fake User: A loss function approximates target-item recommendation counts by penalizing cases where other recommended items outrank the target.Its ℓ1 regularizer encourages each fake user to rate only a limited number of filler items.
- Determining the Set of Influential Users: The S-attack restricts optimization to influential users who are most responsible for the target item’s predictions before the attack.The influential set S contains users selected to focus the optimization on users whose recommendations are most affected by the attack.
- Influence Function for Matrix-factorization-based Recommender Systems: Influence measures the change in the target item’s predicted rating caused by removing users, user-item edges, or user sets.The approach computes user influence from edge-level influence and uses an influence function to approximate the effect of removing an edge without retraining from scratch.
- Influence Function for Matrix-factorization-based Recommender Systems: The edge-removal influence approximation uses the model gradient and the inverse Hessian at the optimum to estimate prediction changes.The relevant perturbed parameter represents the optimum after removing an edge, while the Hessian comes from the training objective.
- Determining the Set of Influential Users: Because influence is monotone and submodular, a greedy algorithm repeatedly selects the remaining user with the largest influence for a set of ∆ users.The selection problem is NP-hard, but submodularity yields an approximation-ratio guarantee for the greedy solution.
- Solving Rating Scores for a Fake User: The rating-score optimization assumes the optimality conditions remain valid under an infinitesimal change of the fake user’s rating weights.Under this assumption, differentiating the stationary conditions enables computation of the required Jacobians for the projected subgradient method.
5 EXPERIMENTS
The experiments evaluate S-attack variants and baselines on Music and Yelp under full- and partial-knowledge settings. S-attack effectively promotes target items, often outperforming baselines and remaining effective without knowing the recommender dimension.
- Experimental setup: Experiments use Amazon Digital Music and Yelp datasets to compare three S-attack variants with PGA and SGLD baselines.The variants differ in whether they optimize over all users, randomly selected users, or influential users.
- Experimental setup: The default evaluation averages HR@N over 10 randomly selected target items, with N = 10 and 3% fake users unless otherwise stated.The default filler-item count is n = 20, and the recommender dimension is d = 64.
- Full-knowledge attack: 150 times: on Yelp, S-TNA-Inf improves the hit ratio for a random target item with only 0.5% fake users versus no attack.The variants outperform baseline attacks in most cases, which target missing rating-matrix entries rather than top-N lists.
- Full-knowledge attack: S-TNA-Inf outperforms U-TNA, showing that excluding users not influential to the target recommendation can improve attack effectiveness.The full-knowledge setting gives the attacker the recommender type, all ratings, and parameters such as d and λ.
- Partial-knowledge attack: Attack performance improves as the attacker observes more normal-user ratings, while the attack remains effective when the attacker does not know d.The observed ratings are selected by increasing distance from the target item in the user-item bipartite graph, and the attack outperforms SGLD in this setting.
6 DETECTING FAKE USERS
The paper evaluates whether fake-user detection weakens the attack. It finds that detection misses a large fraction of fake users, allowing the proposed attacks to remain effective after predicted fake users are removed.
- Detection setup: The evaluation extracts six rating-based features and trains binary SVM classifiers to distinguish fake users from normal users.The features are RDMA, WDMA, WDA, TMF, FMTD, and MeanVar.
- Detection results: PGA is most likely to be detected because its fake users choose filler items unlike normal users’ behavior.Figure 2 reports false negative rate, the fraction of fake users predicted to be normal.
- Detection results: A large fraction of fake users are not detected by the trained classifiers.This leaves many injected users in the recommender system under the evaluated attack settings.
- Fake-user-aware recommender systems: After predicted fake users are removed, the proposed attacks remain effective and outperform baselines because the detectors miss many fake users.PGA performs worst after removal because it is most likely to be detected.
7 DISCUSSION
The discussion extends influence-function-based poisoning beyond matrix factorization to graph-based recommenders and to weighting all users by influence. These extensions improve effectiveness, with weighting trading computational efficiency for stronger attacks.
- Influence function for graph-based recommender systems: The influence-function approach extends data-poisoning attacks to graph-based top-N recommender systems by selecting influential normal users.The graph recommender models ratings as a weighted user-item bipartite graph and uses random walks with restart.
- Influence function for graph-based recommender systems: In the graph-based model, stationary random-walk probabilities determine recommendations, and influence measures how removing an edge changes the target-item prediction.The stationary distribution satisfies pu = (1 − α) · Q · pu + α · eu.
- Influence function for graph-based recommender systems: S-Graph optimizes the graph attack over 400 influential users and outperforms existing graph-based attacks.The influential set is approximately selected using the influence function and Algorithm 1.
- Influence-based weighting: Weighting every normal user by influence improves attack performance over selecting a subset, but sacrifices computational efficiency.The weights are computed from each user’s influence on the target item and incorporated into the attack objective.
8 CONCLUSION
The paper introduces the first data poisoning attack for matrix-factorization-based top-N recommender systems and identifies influential users for targeting. Experiments show that the proposed attacks outperform existing methods.
- The paper proposes the first data poisoning attack for matrix-factorization-based top-N recommender systems.
- An influence function based method efficiently determines the influential user set for a specific target item.
- Extensive experiments demonstrate the efficacy of the proposed attacks.
- The proposed attacks outperform existing ones.