Differentially private recommender systems: building privacy into the net

ABSTRACT

We consider the problem of producing recommendations from collective user behavior while simultaneously providing guarantees of privacy for these users. Specifically, we consider the Netflix Prize data set, and its leading algorithms, adapted to the framework of differential privacy.

Unlike prior privacy work concerned with cryptographically securing the computation of recommendations, differential privacy constrains a computation in a way that precludes any inference about the underlying records from its output. Such algorithms necessarily introduce uncertainty--i.e., noise--to computations, trading accuracy for privacy.

We find that several of the leading approaches in the Netflix Prize competition can be adapted to provide differential privacy, without significantly degrading their accuracy. To adapt these algorithms, we explicitly factor them into two parts, an aggregation/learning phase that can be performed with differential privacy guarantees, and an individual recommendation phase that uses the learned correlations and an individual's data to provide personalized recommendations. The adaptations are non-trivial, and involve both careful analysis of the per-record sensitivity of the algorithms to calibrate noise, as well as new post-processing steps to mitigate the impact of this noise.

We measure the empirical trade-off between accuracy and privacy in these adaptations, and find that we can provide non-trivial formal privacy guarantees while still outperforming the Cinematch baseline Netflix provides.

REFERENCES

• 1: Charu C. Aggarwal, On k-anonymity and the curse of dimensionality, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Esma Aïmeur , Gilles Brassard , José M. Fernandez , Flavien Serge Mani Onana, Alambic: a privacy-preserving recommender system for electronic commerce, International Journal of Information Security, v.7 n.5, p.307-334, September 2008 [doi>10.1007/s10207-007-0049-3]
• 3: Esma Aimeur , Gilles Brassard , Jose M. Fernandez , Flavien Serge Mani Onana , Zbigniew Rakowski, Experimental Demonstration of a Hybrid Privacy-Preserving Recommender System, Proceedings of the 2008 Third International Conference on Availability, Reliability and Security, p.161-170, March 04-07, 2008 [doi>10.1109/ARES.2008.193]
• 4: Robert M. Bell , Yehuda Koren, Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.43-52, October 28-31, 2007 [doi>10.1109/ICDM.2007.90]
• 5: R. M. Bell, Y. Koren, and C. Volinsky. The BellKor solution to the Netflix Prize. Available from http://www.netflixprize.com, 2007.
• 6: R. M. Bell, Y. Koren, and C. Volinsky. The BellKor 2008 solution to the Netflix Prize. Available from http://www.netflixprize.com, 2008.
• 7: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 8: Justin Brickell , Vitaly Shmatikov, The cost of privacy: destruction of data-mining utility in anonymized data publishing, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401904]
• 9: J. Calandrino, A. Narayanan, E. Felten, and V. Shmatikov. Don't review that book: Privacy risks of collaborative filtering. Manuscript, 2009.
• 10: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 11: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 12: Anirban Dasgupta , John E. Hopcroft , Frank McSherry, Spectral Analysis of Random Graphs with Skewed Degree Distributions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.602-610, October 17-19, 2004 [doi>10.1109/FOCS.2004.61]
• 13: C. Dwork. Differential privacy. Invited talk. In Automata, Languages and Programming--ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 1--12. Springer, 2006.
• 14: C. Dwork. An ad omnia approach to defining and achieving private data analysis. In F. Bonchi, E. Ferrari, B. Malin, and Y. Saygin, editors, PinKDD, volume 4890 of Lecture Notes in Computer Science, pages 1--13. Springer, 2007.
• 15: C. Dwork. Differential privacy: A survey of results. In M. Agrawal, D.-Z. Du, Z. Duan, and A. Li, editors, Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 1--19. Springer, 2008.
• 16: C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In S. Vaudenay, editor, Advances in Cryptology--EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 486--503. Springer, May 2006.
• 17: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, Theory of Cryptography Conference--TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 265--284. Springer, 2006.
• 18: Srivatsava Ranjit Ganta , Shiva Prasad Kasiviswanathan , Adam Smith, Composition attacks and auxiliary information in data privacy, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401926]
• 19: Yehuda Koren, Factorization meets the neighborhood: a multifaceted collaborative filtering model, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401944]
• 20: Y. Li, B. Liu, and S. Sarawagi, editors. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, August 24-27, 2008. ACM, 2008.
• 21: Ashwin Machanavajjhala , Daniel Kifer , John Abowd , Johannes Gehrke , Lars Vilhuber, Privacy: Theory meets Practice on the Map, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.277-286, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497436]
• 22: Arvind Narayanan , Vitaly Shmatikov, Robust De-anonymization of Large Sparse Datasets, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.111-125, May 18-21, 2008 [doi>10.1109/SP.2008.33]
• 23: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Algorithms, Security, Theory

Keywords:
Netflix, differential privacy, recommender systems