TL;DR
This paper introduces a novel data poisoning attack for matrix factorization-based Top-N recommender systems. By strategically injecting fake user data, attackers can manipulate recommendations to promote a target item to a wider audience. The key innovation lies in using influence functions to identify influential users, making the attack more effective and efficient.
What Problem Does This Paper Address?
Recommender systems are ubiquitous, helping users discover new products, movies, and content. They typically work by learning user preferences from interaction data (like ratings) and then recommending the "top-N" items that best match those preferences. However, this reliance on user data makes them vulnerable to "data poisoning" attacks. Attackers can inject malicious data to trick the system into making undesirable recommendations. While data poisoning attacks have been studied for various machine learning models, a specific, optimized attack for matrix factorization-based Top-N recommender systems remained an open challenge. This paper aims to fill that gap by developing an attack that can effectively manipulate these systems to promote a chosen target item to as many users as possible.
Methods
The core of the paper's contribution is an optimized data poisoning attack, dubbed the "S-attack," for matrix factorization-based Top-N recommender systems. The attack involves injecting fake users who provide carefully crafted ratings.
Here's a breakdown of their approach:
- Problem Formulation: The attack is framed as an optimization problem: maximize the number of normal users who receive a specific target item in their top-N recommendations, given constraints on the number of fake users and the items they can rate.
- Approximation Techniques: Since the direct optimization problem is NP-hard (a non-convex integer programming problem), the authors employ several techniques to approximate a solution:
- Relaxing Ratings: Discrete rating scores are relaxed to continuous values to enable gradient-based optimization.
- Differentiable Loss Function: The hit ratio (the metric to maximize) is approximated by a differentiable loss function, allowing for gradient descent.
- Influence Function for User Selection: This is the paper's key innovation. Instead of considering all normal users, they use influence functions (borrowed from interpretable machine learning) to identify a subset of "influential" users whose ratings most significantly impact the recommendation of the target item. This significantly reduces the computational burden and improves attack effectiveness. They prove that the influence function exhibits submodular properties, allowing for an efficient greedy algorithm to select these influential users.
- Gradient-Based Optimization: A gradient-based method is used to determine the optimal rating scores for the fake users, considering the influential user subset.
- Stealthy Rating Generation: To make the attack less detectable, fake users' ratings for "filler" items (items other than the target) are generated to mimic the statistical properties (mean and variance) of normal users' ratings for those items.
Datasets
The authors evaluate their proposed attack on two publicly available, real-world datasets:
- Amazon Digital Music (Music): Contains user ratings for music albums.
- Yelp: Contains user ratings for businesses.
These datasets are standard benchmarks for recommender system research. The paper does not introduce new datasets.
Key Insights and Ideas
- Influence Functions for Attack Optimization: The most significant insight is the application of influence functions to identify influential users for data poisoning attacks. This dramatically improves efficiency and effectiveness by focusing the attack on the most critical parts of the user-item interaction data.
- Submodularity for Efficient Selection: Proving that the influence function is submodular is crucial. It guarantees that a simple greedy selection algorithm can find a near-optimal set of influential users, making the attack practical.
- Targeted vs. General Attacks: The paper highlights that attacks specifically targeting Top-N recommendations are more effective than those aiming to manipulate all missing entries in the rating matrix. This is because Top-N recommendations are often driven by a smaller, more sensitive subset of user preferences.
- Attack Effectiveness Against Detection: The S-attack demonstrates resilience against fake-user detection mechanisms. Even when detectors are in place, the influence-function-based attack remains effective because it's designed to be stealthy and targets influential users, making it harder for detectors to flag the malicious activity.
Key Results
- High Effectiveness: The S-attack significantly increases the "hit ratio" (the percentage of users who receive the target item in their top-N recommendations). For instance, on the Yelp dataset, injecting just 0.5% fake users increased the hit ratio by 150 times compared to the non-attack setting.
- Outperforms Baselines: The proposed S-attack (specifically S-TNA-Inf) consistently outperforms existing baseline attacks (like PGA and SGLD) across both datasets and various attack sizes.
- Influence Function Advantage: The S-TNA-Inf variant, which uses influence functions to select influential users, performs better than variants that use all users (U-TNA) or randomly selected users (S-TNA-Rand). This validates the core idea of focusing on influential users.
- Partial Knowledge Robustness: The attack remains effective even when the attacker has only partial knowledge of the recommender system's parameters (e.g., not knowing the latent factor dimension
d). - Weighting Users Enhances Attack: The paper also explores an alternative approach where normal users are weighted based on their influence, rather than being discarded. This method further improves attack effectiveness, especially when computational resources are not a bottleneck.
Limitations and Future Work
- Computational Cost: While the influence function significantly reduces computation compared to using all users, the process of calculating influence functions and solving the optimization problem for each fake user can still be computationally intensive, especially with a large number of fake users (
m). - Assumptions: The attack assumes knowledge of the recommender system's architecture (matrix factorization) and potentially some parameters. The effectiveness might vary for other recommender system types.
- Future Work: The authors suggest extending their influence function approach to graph-based recommender systems and exploring the weighting of normal users as a more computationally intensive but potentially more effective attack strategy. They also implicitly suggest further research into robust recommender systems that can defend against such sophisticated attacks.
Summary updated