Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders

Frank McSherry, Ilya MironovKDD 2009 · DOI

TL;DR

This paper introduces a method to build differentially private recommender systems, specifically adapting algorithms from the Netflix Prize competition. They demonstrate that it's possible to achieve strong privacy guarantees without significantly sacrificing recommendation accuracy, outperforming Netflix's own baseline.

What Problem Does This Paper Address?

Recommender systems, like those used by Netflix, are incredibly useful for discovering new content. They work by analyzing the preferences of many users to predict what an individual might like. However, this process inherently involves handling sensitive user data. Even with robust security measures, there's a risk that a user's input could be inferred from the system's output, especially if an adversary can manipulate their own input and observe the system's responses. This is a significant privacy concern, as even seemingly innocuous data can reveal sensitive information when aggregated. Traditional anonymization techniques often degrade data utility too much for effective machine learning.

Methods

The authors adapt leading Netflix Prize algorithms (factor models and neighborhood models) to the framework of differential privacy. Their core strategy is to separate the recommender system into two phases:

  1. Privately Computable Aggregation/Learning Phase: This phase involves computing global statistics (like movie averages, user averages, and the covariance matrix) from the entire dataset. Crucially, noise is added to these computations according to differential privacy principles (using Laplace or Gaussian noise). This ensures that the output of this phase doesn't reveal information about any single user's contribution.
  2. Individual Recommendation Phase: This phase uses the "learned" correlations from the private aggregation phase and the individual user's own data to generate personalized recommendations. This phase is performed locally by the user, thus not requiring privacy guarantees for its execution.

They meticulously analyze the "sensitivity" of each computation (how much a single record can change the output) to determine the appropriate amount of noise needed for differential privacy. They also introduce "cleaning" steps, like shrinking the covariance matrix towards an average and performing low-rank approximations, to mitigate the noise introduced for privacy.

Datasets

  • Netflix Prize Dataset: Used for both training and evaluation. This dataset contains approximately 100 million ratings from 480,000 users on 17,770 movies.

Key Insights and Ideas

  • Privacy Doesn't Necessarily Mean Huge Accuracy Loss: The paper's central finding is that strong differential privacy guarantees can be achieved with only a modest impact on recommendation accuracy, especially when compared to the baseline.
  • Covariance Matrix is Key for Privacy: While adding noise to the raw data matrix is problematic due to its size and the number of users, adding noise to the covariance matrix is more manageable. The noise added scales with the number of movies, not the number of users, making it more feasible for large datasets.
  • Two-Phase Approach is Crucial: Separating the privacy-sensitive global learning from the user-specific prediction is essential for building practical, private recommender systems.
  • "Cleaning" the Noise: Techniques like matrix shrinking and low-rank approximation are vital for recovering accuracy after noise has been added for privacy.

Key Results

  • The proposed differentially private algorithms (both kNN and SVD-based) can match or outperform Netflix's Cinematch baseline at a specific privacy parameter setting (θ ≈ 0.15).
  • As the privacy parameter (θ, inversely related to noise) increases, accuracy generally decreases, but the trade-off is shown to be manageable.
  • The accuracy loss due to privacy decreases as more data becomes available, suggesting that privacy-preserving systems become more efficient with scale.

Limitations and Future Work

  • Parameter Optimization: The authors fixed several parameters (like dimensionality k=20, shrinking parameters βm=15, βp=20) and suggest that further experimentation could lead to improved prediction accuracy.
  • Cleansing Parameter Sensitivity: The "cleansing" step's parameters were optimized for a specific privacy level (θ=0.15), and it's noted that this might impair performance at other privacy levels. More delicate post-processing could potentially accommodate both regimes.
  • More Advanced Algorithms: Future work could explore privacy-preserving methods for more complex collaborative filtering techniques that don't easily factorize into two phases.
  • User-Level Privacy: While the paper discusses per-user privacy, it notes that stronger guarantees come at a higher accuracy cost. Further research could explore better trade-offs.

Summary updated

BibTeX
@inproceedings{mcsherry2009differentially,
  author = {Frank McSherry and Ilya Mironov},
  title = {{Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2009},
  doi = {10.1145/1557019.1557090},
}
Figure