research-article

The information cost of manipulation-resistance in recommender systems

Authors:

Rahul SamiAuthors Info & Claims

RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems

Pages 147 - 154

https://doi.org/10.1145/1454008.1454033

Published: 23 October 2008 Publication History

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.

Digital Library

[2]

N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.

Digital Library

[3]

P.-A. Chirita, W. Nejdl, and C. Zamfir. Preventing shilling attacks in online recommender systems. In WIDM 05, pages 67--74, 2005.

Digital Library

[4]

T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New York, 1991.

Digital Library

[5]

E. Friedman and P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173--199, 2001.

[6]

S. K. Lam and J. Riedl. Shilling recommender systems for fun and profit. In Proceedings of WWW '04., pages 393--402, 2004.

Digital Library

[7]

B. Mehta, T. Hoffman, and P. Fankhauser. Lies and propaganda:detecting spam users in collaborative filtering. In Proceedings of IUI'07, 2007.

Digital Library

[8]

B. Mehta and W. Nejdl. Attack resistant collaborative filtering. In Proceedings of ACM SIGIR 2008 (to appear), 2008.

Digital Library

[9]

B. Mobasher, R. Burke, R. Bhaumik, and C. Williams. Towards trustworthy recommender systems: An analysis of attack models and algorithm robustness. ACM Transactions on Internet Technology, 7(2):1--40, 2007.

Digital Library

[10]

J. O'Donovan and B. Smyth. Trust no one: Evaluating trust-based filtering for recommenders. In Proceedings of IJCAI'05, 2005.

Digital Library

[11]

M. O'Mahony, N. Hurley, and G. Silvestre. Promoting recommendations: An attack on collaborative filtering. In Proceedings of the 13th International Conference on Database and Expert System Applications, pages 494--503. Springer-Verlag, 2002.

Digital Library

[12]

M. P. O'Mahony, N. J. Hurley, and G. C. M. Silvestre. Detecting noise in recommender system databases. In Proceedings of the 2006 International Conference on Intelligent User Interfaces, pages 109--115, 2006.

Digital Library

[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]

P. Resnick and R. Sami. The influence limiter: Provably manipulation-resistant recommender systems. In Proceedings of the ACM Recommender Systems Conference (RecSys07), 2007.

Digital Library

[15]

J. Sandvig, B. Mobasher, and R. Burke. Robustness of collaborative recommendation based on association rule mining. In Proceedings of the 2007 ACM Conference on Recommender Systems, 2007.

Digital Library

Cited By

Matias J(2023)Influencing recommendation algorithms to reduce the spread of unreliable news by encouraging humans to fact-check articles, in a field experimentScientific Reports10.1038/s41598-023-38277-513:1Online publication date: 20-Jul-2023
https://doi.org/10.1038/s41598-023-38277-5
Ozarko KChelombytko V(2022)Peculiarities of the Use of the Scrum Approach in the Management System of Information Activities of the EnterpriseEconomic Herald of the Donbas10.12958/1817-3772-2022-3(69)-59-65(59-65)Online publication date: 2022
https://doi.org/10.12958/1817-3772-2022-3(69)-59-65
Himeur YSayed AAlsalemi ABensaali FAmira AVarlamis IEirinaki MSardianos CDimitrakopoulos G(2022)Blockchain-based recommender systemsComputer Science Review10.1016/j.cosrev.2021.10043943:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100439
Show More Cited By

Index Terms

The information cost of manipulation-resistance in recommender systems
1. Computing methodologies
  1. Machine learning

Recommendations

Shilling recommender systems for fun and profit
WWW '04: Proceedings of the 13th international conference on World Wide Web

Recommender systems have emerged in the past several years as an effective way to help people cope with the problem of information overload. One application in which they have become particularly common is in e-commerce, where recommendation of items ...
Acquiring User Information Needs for Recommender Systems
WI-IAT '13: Proceedings of the 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) - Volume 03

Most recommender systems attempt to use collaborative filtering, content-based filtering or hybrid approach to recommend items to new users. Collaborative filtering recommends items to new users based on their similar neighbours, and content-based ...
Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness

Publicly accessible adaptive systems such as collaborative recommender systems present a security problem. Attackers, who cannot be readily distinguished from ordinary users, may inject biased profiles in an attempt to force a system to “adapt” in a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems

October 2008

348 pages

ISBN:9781605580937

DOI:10.1145/1454008

General Chair:
Pearl Pu
Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
,
Program Chairs:
Derek Bridge
University College Cork, Ireland
,
Bamshad Mobasher
DePaul University, USA
,
Francesco Ricci
Free University Bozen-Bolzano, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

RecSys08

Sponsor:

RecSys08: ACM Conference on Recommender Systems

October 23 - 25, 2008

Lausanne, Switzerland

Acceptance Rates

Overall Acceptance Rate 254 of 1,295 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
987
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Matias J(2023)Influencing recommendation algorithms to reduce the spread of unreliable news by encouraging humans to fact-check articles, in a field experimentScientific Reports10.1038/s41598-023-38277-513:1Online publication date: 20-Jul-2023
https://doi.org/10.1038/s41598-023-38277-5
Ozarko KChelombytko V(2022)Peculiarities of the Use of the Scrum Approach in the Management System of Information Activities of the EnterpriseEconomic Herald of the Donbas10.12958/1817-3772-2022-3(69)-59-65(59-65)Online publication date: 2022
https://doi.org/10.12958/1817-3772-2022-3(69)-59-65
Himeur YSayed AAlsalemi ABensaali FAmira AVarlamis IEirinaki MSardianos CDimitrakopoulos G(2022)Blockchain-based recommender systemsComputer Science Review10.1016/j.cosrev.2021.10043943:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100439
Tran TFelfernig ALe VAtas MStettinger MSamer RPapadopoulos GSamaras GWeibelzahl SJannach DSantos O(2019)User Interfaces for Counteracting Decision Manipulation in Group Recommender SystemsAdjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization10.1145/3314183.3324977(93-98)Online publication date: 6-Jun-2019
https://dl.acm.org/doi/10.1145/3314183.3324977
Truong AEtesami SEtesami JKiyavash N(2018)Optimal Attack Strategies Against Predictors - Learning From Expert AdviceIEEE Transactions on Information Forensics and Security10.1109/TIFS.2017.271848813:1(6-19)Online publication date: Jan-2018
https://doi.org/10.1109/TIFS.2017.2718488
Truong AKiyavash NRasoul Etesami S(2018)Adversarial Machine Learning: The Case of Recommendation Systems2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)10.1109/SPAWC.2018.8445767(1-5)Online publication date: Jun-2018
https://doi.org/10.1109/SPAWC.2018.8445767
Zhai ELi ZLi ZWu FChen G(2016)Resisting tag spam by leveraging implicit user behaviorsProceedings of the VLDB Endowment10.14778/3021924.302193910:3(241-252)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.14778/3021924.3021939
Jannach DResnick PTuzhilin AZanker M(2016)Recommender systems — beyond matrix completionCommunications of the ACM10.1145/289140659:11(94-102)Online publication date: 28-Oct-2016
https://dl.acm.org/doi/10.1145/2891406
Aggarwal CAggarwal C(2016)Attack-Resistant Recommender SystemsRecommender Systems10.1007/978-3-319-29659-3_12(385-410)Online publication date: 29-Mar-2016
https://doi.org/10.1007/978-3-319-29659-3_12
Johnson BVang MVan Der Heide B(2015)Show Me The GoodsJournal of Media Psychology10.1027/1864-1105/a00012627:1(3-10)Online publication date: 1-Jan-2015
https://doi.org/10.1027/1864-1105/a000126
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents