The information cost of manipulation-resistance in recommender systems

ABSTRACT

Attackers may seek to manipulate recommender systems in order to promote or suppress certain items. Existing defenses based on analysis of ratings also discard useful information from honest raters. In this paper, we show that this is unavoidable and provide a lower bound on how much information must be discarded. We use an information-theoretic framework to exhibit a fundamental tradeoff between manipulation-resistance and optimal use of genuine ratings in recommender systems. We define a recommender system to be (n, c)-robust if an attacker with n sybil identities cannot cause more than a limited amount c units of damage to predictions. We prove that any robust recommender system must also discard Ω(log (n/c)) units of useful information from each genuine rater.

REFERENCES

• 1: B. Awerbuch and R. D. Kleinberg. Competitive collaborative learning. In 18th Annual Conference on Learning Theory (COLT 2005), volume 3559 of LNAI, pages 233--248. Springer, 2005.
• 2: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 3: Paul-Alexandru Chirita , Wolfgang Nejdl , Cristian Zamfir, Preventing shilling attacks in online recommender systems, Proceedings of the 7th annual ACM international workshop on Web information and data management, November 04-04, 2005, Bremen, Germany [doi>10.1145/1097047.1097061]
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: E. Friedman and P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173--199, 2001.
• 6: Shyong K. Lam , John Riedl, Shilling recommender systems for fun and profit, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988726]
• 7: Bhaskar Mehta , Thomas Hofmann , Peter Fankhauser, Lies and propaganda: detecting spam users in collaborative filtering, Proceedings of the 12th international conference on Intelligent user interfaces, January 28-31, 2007, Honolulu, Hawaii, USA [doi>10.1145/1216295.1216307]
• 8: Bhaskar Mehta , Wolfgang Nejdl, Attack resistant collaborative filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390350]
• 9: Bamshad Mobasher , Robin Burke , Runa Bhaumik , Chad Williams, Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness, ACM Transactions on Internet Technology (TOIT), v.7 n.4, p.23-es, October 2007 [doi>10.1145/1278366.1278372]
• 10: J. O'Donovan and B. Smyth. Trust no one: Evaluating trust-based filtering for recommenders. In Proceedings of IJCAI'05, 2005.
• 11: Michael P. O'Mahony , Neil Hurley , Guenole C. M. Silvestre, Promoting Recommendations: An Attack on Collaborative Filtering, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.494-503, September 02-06, 2002
• 12: Michael P. O'Mahony , Neil J. Hurley , Guénolé C.M. Silvestre, Detecting noise in recommender system databases, Proceedings of the 11th international conference on Intelligent user interfaces, January 29-February 01, 2006, Sydney, Australia [doi>10.1145/1111449.1111477]
• 13: A. M. Rashid, G. Karypis, and J. Riedl. Influence in ratings-based recommender systems: An algorithm-independent approach. In Proceedings of the SIAM International Conference on Data Mining, 2005.
• 14: Paul Resnick , Rahul Sami, The influence limiter: provably manipulation-resistant recommender systems, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA [doi>10.1145/1297231.1297236]
• 15: J. J. Sandvig , Bamshad Mobasher , Robin Burke, Robustness of collaborative recommendation based on association rule mining, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA [doi>10.1145/1297231.1297249]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Reliability

Keywords:
information loss, manipulation-resistance, recommender systems, shilling