Source-linked AI summary
Data Poisoning Attacks on Factorization-Based Collaborative Filtering
Bo Li, Yining Wang, Aarti Singh, Yevgeniy Vorobeychik
TL;DR
Recommendation systems can be compromised by data poisoning that degrades availability or manipulates item-specific recommendations. The paper develops near-optimal, full-knowledge attacks for two factorization-based methods, while also synthesizing malicious users that mimic normal behavior. Experiments on real-world data show effective availability and integrity manipulation, and the paper discusses detection and ensemble-based defenses.
Problem
Recommendation systems are susceptible to malicious data poisoning that can degrade system effectiveness or credibility and manipulate targeted item popularity.
Method
The paper develops constrained, near-optimal poisoning attacks using gradient computations for alternating minimization and nuclear norm minimization, with stochastic gradient Langevin dynamics to mimic normal users.
Results
Targeted attacks using PGA and SGLD are more effective at manipulating specific-item ratings, while experiments also evaluate RMSE effects for alternating minimization and nuclear norm minimization.
Takeaways & Limitations
Tracking feature-correlation deviations and accuracy metrics, along with combinational models or sampling such as bagging, are proposed as potential defenses.
Takeaways & Limitations
The analysis assumes an attacker can add αm malicious users under per-user rating-count and rating-magnitude constraints, and relies on approximate low-rank structure for matrix completion.
Abstract
from arXiv · showhide
Recommendation and collaborative filtering systems are important in modern information and e-commerce applications. As these systems are becoming increasingly popular in the industry, their outputs could affect business decision making, introducing incentives for an adversarial party to compromise the availability or integrity of such systems. We introduce a data poisoning attack on collaborative filtering systems. We demonstrate how a powerful attacker with full knowledge of the learner can generate malicious data so as to maximize his/her malicious objectives, while at the same time mimicking normal user behavior to avoid being detected. While the complete knowledge assumption seems extreme, it enables a robust assessment of the vulnerability of collaborative filtering schemes to highly motivated attacks. We present efficient solutions for two popular factorization-based collaborative filtering algorithms: the \emph{alternative minimization} formulation and the \emph{nuclear norm minimization} method. Finally, we test the effectiveness of our proposed algorithms on real-world data and discuss potential defensive strategies.
1 Introduction
Collaborative filtering systems are vulnerable to data poisoning attacks that can degrade recommendations or manipulate item popularity. The paper addresses limitations of prior informal attacks by developing systematic, near-optimal attacks against factorization-based algorithms under a full-knowledge adversary model.
- Motivation: Data poisoning creates malicious users with chosen preferences to degrade recommendation effectiveness or manipulate specific item popularity.Examples include making recommendations differ from normal outputs or changing the popularity of a targeted movie or product.
- Research gap: Existing random and random product push/nuke attacks are not formally analyzed or optimized for specific collaborative filtering algorithms.Knowing the defender’s algorithm or parameter settings can otherwise lead to underestimating attacker ability.
- Contribution: The paper computes near-optimal poisoning attacks for alternating minimization and nuclear norm minimization.The attacker is assumed to know the learner’s algorithms and parameters following the Kerckhoffs’ principle.
- Contribution: The work characterizes availability and integrity attacker utilities within a unified optimization framework.Availability attacks increase prediction error, whereas integrity attacks pursue item-specific objectives.
- Related work: The study extends data-poisoning analysis to factorization-based collaborative filtering while building on prior gradient-based attacks and robust matrix-completion research.Prior work analyzed security attacks broadly and alternating-minimization stability under malicious manipulation, but assumed globally optimal alternating-minimization solutions.
2 Preliminaries
Collaborative filtering formulates recommendation as completing a sparsely observed user-by-item matrix. Because arbitrary partial matrices cannot generally be completed, the paper assumes approximate low rank and uses alternating minimization or nuclear norm minimization.
- Problem formulation: Collaborative filtering seeks to recover a complete user-by-item matrix from relatively few observed ratings.The matrix contains users as rows, items as columns, and observed entries indexed by Ω.
- Low-rank assumption: Matrix completion is ill-posed for arbitrary matrices, motivating the assumption that the data matrix is close to rank k with k ≪ min(m, n).The low-rank assumption supplies structure needed for recovery from partial observations.
- Recovery objective: The basic recovery objective minimizes observed-entry reconstruction error subject to a rank constraint.The feasible set is non-convex, making direct optimization difficult.
- Alternating minimization: Alternating minimization factorizes the completed matrix into user and item factors and alternates optimization over those factors.Small positive regularization parameters can avoid large completed entries and improve convergence.
- Nuclear norm minimization: Nuclear norm minimization replaces rank with a convex surrogate and can be solved using iterative singular value thresholding.Both approaches are stated to provably approximate the underlying matrix under certain conditions.
3 The Attack Model
The attack model adds constrained malicious users whose ratings are optimized to divert collaborative-filtering predictions. It supports availability, integrity, and hybrid objectives, including attacks that seek a lighter detectable trace.
- Attack constraints: The attacker adds αm malicious users, each rating at most B items with preferences bounded in [−Λ, Λ].These constraints define the feasible poisoning data.
- Poisoned learner: The poisoned learner jointly estimates latent factors for normal and malicious users, or a completed matrix under nuclear norm minimization.The resulting model determines predictions after malicious data are added.
- Attacker objective: The attacker optimizes a utility over feasible malicious data to divert predictions on the original dataset.The framework represents the attack as choosing malicious users while respecting sparsity and rating bounds.
- Availability attack: Availability attacks maximize prediction perturbation on unseen entries to increase system error and potentially render the system useless.The utility compares predictions before and after poisoning over unobserved entries Ω^C.
- Integrity attack: Integrity attacks boost or reduce ratings for a selected subset of items using attacker-specified weights.The objective targets item-specific popularity rather than overall prediction error.
- Hybrid attack: Hybrid objectives trade off availability and integrity, and a negative availability coefficient can model a light-trace attack.Such an attack seeks to affect target-item popularity while reducing broader system perturbation.
4 Computing Optimal Attack Strategies
The paper computes near-optimal poisoning strategies by differentiating attack utility through factorization-based learning procedures, then optimizing malicious profiles under feasibility or detection-avoidance constraints.
- Alternating minimization: Projected gradient ascent updates malicious profiles using utility gradients for alternating minimization, then projects them back into the feasible attack set.The feasible set limits rated items and rating magnitudes; projection truncates ratings to ±Λ.
- Gradient computation: The attack gradient is decomposed by the chain rule into model sensitivity to malicious data and utility sensitivity to model parameters.The model-sensitivity term is approximated using first-order KKT conditions.
- Gradient computation: For alternating minimization, factor rows are differentiated as functions of original and malicious data to obtain the required model sensitivity.The derivation treats the learned factor variables as data-dependent quantities.
- Nuclear norm minimization: The nuclear norm formulation extends projected gradient ascent while obtaining its convex model solution with proximal gradient descent or singular value thresholding.The resulting estimate is low rank, and KKT conditions support differentiating the solution with respect to malicious data.
- Mimicking normal user behaviors: A Bayesian detection-avoidance strategy samples malicious profiles from a posterior combining attack utility with a normal-user prior.SGLD approximately samples the intractable posterior, then selects B items and truncates ratings to ±Λ.
- Mimicking normal user behaviors: The parameter β controls the attack–detection trade-off: smaller β favors harder-to-detect but less effective attacks, and vice versa.The posterior shifts toward the normal-user prior as β decreases.
5 Experimental Results
Experiments on MovieLens evaluate poisoning against alternating and nuclear norm minimization using availability and integrity objectives. Targeted attacks manipulate item ratings effectively, while detection-avoiding attacks trade some utility for profiles harder to distinguish from normal users.
- Dataset and metrics: MovieLens experiments use 20 million ratings from 138,000 users and evaluate poisoning with RMSE and average ratings after restricting users to at least 20 rated movies.Ratings are shifted to [−2, 2], and the nuclear norm experiments use a smaller subset because of higher computational cost.
- Availability attacks: When µ1 = 1, µ2 = 0, the attacker targets increased RMSE; when µ1 = 1, µ2 = −1, it also pushes a specific item’s rating downward.The latter setting produces slightly lower RMSE than targeting availability alone.
- Detection avoidance: PGA generates the largest RMSE, but its uniformly sampled rated items fail a paired t-test against normal-user profiles with p < 0.05.SGLD has slightly worse attacker utility but produces malicious users that are harder to distinguish from normal users.
- Integrity attacks: For integrity settings µ1 = 0, µ2 = 1 and µ1 = −1, µ2 = 1, targeted PGA and SGLD attacks more effectively manipulate ratings of specified items.The second setting additionally seeks to reduce the poisoning impact on the entire system.
- Nuclear norm minimization: Nuclear norm minimization shows generally similar RMSE and average-rating behavior to alternating minimization across the different attack settings.These experiments use 1,000 users and 1,700 items because nuclear norm minimization is more computationally expensive.
6 Discussion and Concluding Remarks
The paper uses adversarial-behavior analysis to motivate defenses against poisoning attacks. It suggests monitoring feature-correlation deviations and accuracy metrics, alongside combinational models or sampling strategies such as bagging.
- Feature-correlation deviations and other accuracy metrics are proposed as potential signals for detecting poisoning attacks.
- Combinational models or sampling strategies, including bagging, are suggested to reduce poisoning attacks’ influence.
C Additional experimental results
Additional experiments examine how β and attacker objectives affect poisoning outcomes for alternating minimization and nuclear norm minimization. Increasing β lowers P-values while increasing RMSE and average ratings, whereas competing objectives constrain item manipulation.
- Increasing β decreases P-values while increasing RMSE and average per-item ratings when B = 25.
- With µ1 = 0 and µ2 = −1, alternating minimization lowers an item’s predicted average rating from 0.8 to around -0.3.
- With µ1 = −1 and µ2 = −1, the same item’s average rating decreases to about -0.1 while the attacker also reduces whole-system availability error.
- Figures 3 and 4 plot P-values, RMSE, and average ratings against β for four µ1, µ2 settings.
- Figures 5 and 6 plot average ratings of selected items under two attacker-objective settings for alternating minimization and nuclear norm minimization.