Cited by 28Privacy-Preserving Technologies in DataRecommender Systems and TechniquesPrivacy, Security, and Data Protection

ReuseKNN: Neighborhood Reuse for Differentially Private KNN-Based Recommendations

Open access
Müllner, Peter, Lex, Elisabeth, Schedl, Markus, Kowald, Dominik·2023·ACM Transactions on Intelligent Systems and Technology

Abstract

User-based KNN recommender systems ( UserKNN ) utilize the rating data of a target user’s k nearest neighbors in the recommendation process. This, however, increases the privacy risk of the neighbors, since the recommendations could expose the neighbors’ rating data to other users or malicious parties. To reduce this risk, existing work applies differential privacy by adding randomness to the neighbors’ ratings, which unfortunately reduces the accuracy of UserKNN . In this work, we introduce ReuseKNN , a novel differentially private KNN-based recommender system. The main idea is to identify small but highly reusable neighborhoods so that (i) only a minimal set of users requires protection with differential privacy and (ii) most users do not need to be protected with differential privacy since they are only rarely exploited as neighbors. In our experiments on five diverse datasets, we make two key observations. Firstly, ReuseKNN requires significantly smaller neighborhoods and, thus, fewer neighbors need to be protected with differential privacy compared with traditional UserKNN . Secondly, despite the small neighborhoods, ReuseKNN outperforms UserKNN and a fully differentially private approach in terms of accuracy. Overall, ReuseKNN leads to significantly less privacy risk for users than in the case of UserKNN .

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3608481

Cites

31 of 31 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • To achieve privacy protection, centralized RS typically uses non-cryptographic techniques due to their ease of application and low computational complexity.

    “To achieve privacy protection, centralized RS typically uses non-cryptographic techniques due to their ease of application and low computational complexity [8, 123-125].”

    From A Deep Dive into Fairness, Bias, Threats, and Privacy in Recommender Systems: Insights and Future Research (2024) · cites this paper as [124]

    Section 2.2 (page unavailable) says differential privacy has been used in collaborative-filtering recommender systems and that homomorphic encryption has high computational complexity. It does not say centralized recommender systems typically prefer non-cryptographic techniques, or that ease of application and low computational complexity explain such a preference. (LLM, conf=0.82)

    Experimental — accuracy not yet measured
  • In a centralized setup, the system is a trusted server responsible for maintaining data privacy.

    “In a centralized setup, the system is a trusted server responsible for maintaining data privacy [99, 123-126].”

    From A Deep Dive into Fairness, Bias, Threats, and Privacy in Recommender Systems: Insights and Future Research (2024) · cites this paper as [124]

    The Introduction says the recommender-system provider specifies which users need privacy protection, supporting the idea that the system operator has a role in protecting data. It does not describe a centralized setup or characterize the server as trusted; searches for “trusted server” and “centralized” found no such description in the paper’s discussion. (LLM, conf=0.78)

    Experimental — accuracy not yet measured
  • DP noise can be introduced at various stages: on the input data, the model parameters, or the final recommendations.

    “This carefully calibrated noise can be introduced at various stages: on the input data [14, 124, 138, 172], the model parameters [101, 171, 173], or the final recommendations [172].”

    From A Deep Dive into Fairness, Bias, Threats, and Privacy in Recommender Systems: Insights and Future Research (2024) · cites this paper as [124]

    Section 5.2.2 says ReuseKNN applies DP by adding noise to neighbors’ rating values, supporting the input-data part of the claim. Appendix B evaluates the resulting top-N recommendations, but does not say noise is added to the final recommendations themselves. The model-parameters clause cites other sources, not this paper. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

1 of the 32 references couldn’t be matched to a known paper.

Research works printed but not linked: 35

  1. Himan Abdollahpouri, Masoud Mansoury, Robin Burke, and Bamshad Mobasher. 2019. The unfairness of popularity bias in recommendation. In Proc. of the RMSE'19 Workshop, in Conjunction with ACM RecSys'19.
  2. Vito Walter Anelli, Yashar Deldjoo, Tommaso Di Noia, Antonio Ferrara, and Fedelucio Narducci. 2021. How to put users in control of their data in federated top-N recommendation with learning to rank. In Proc. of SAC'21.
  3. Michael Buckland and Fredric Gey. 1994. The relationship between recall and precision. Journal of the American Society for Information Science 45, 1 (1994), 12-19.
  4. Joseph A. Calandrino, Ann Kilzer, Arvind Narayanan, Edward W. Felten, and Vitaly Shmatikov. 2011. "You might also like:" Privacy risks of collaborative filtering. In Proc. of S&P'11. IEEE, 231-246.
  5. Chaochao Chen, Huiwen Wu, Jiajie Su, Lingjuan Lyu, Xiaolin Zheng, and Li Wang. 2022. Differential private knowl- edge transfer for privacy-preserving cross-domain recommendation. In Proc. of ACM WWW'22.
  6. Ziqian Chen, Fei Sun, Yifan Tang, Haokun Chen, Jinyang Gao, and Bolin Ding. 2022. Studying the impact of data disclosure mechanism in recommender systems via simulation. ACM Transactions on Information Systems (2022).
  7. Josep Domingo-Ferrer. 2010. Rational privacy disclosure in social networks. In Proc. of MDAI'10. Springer, 255-265.
  8. Cynthia Dwork. 2008. Differential privacy: A survey of results. In Proc. of TAMC'08. Springer, 1-19.
  9. Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Proc. of ITCS'12. 214-226.
  10. Michael D. Ekstrand, Rezvan Joshaghani, and Hoda Mehrpouyan. 2018. Privacy for all: Ensuring fair and equitable privacy protections. In Proc. of FAccT'18. PMLR, 35-47.
  11. Chen Gao, Chao Huang, Dongsheng Lin, Depeng Jin, and Yong Li. 2020. DPLCF: Differentially private local collabo- rative filtering. In Proc. of SIGIR'20. 961-970.
  12. Guibing Guo, Jie Zhang, Daniel Thalmann, and Neil Yorke-Smith. 2014. ETAF: An extended trust antecedents frame- work for trust prediction. In Proc. of ASONAM'14.
  13. Jialiang Han, Yun Ma, Qiaozhu Mei, and Xuanzhe Liu. 2021. DeepRec: On-device deep learning for privacy-preserving sequential recommendation in mobile commerce. In Proc. of WWW'21. 900-911.
  14. Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017. Neural collaborative filtering. In Proc. of WWW'17. 173-182.
  15. Jonathan L. Herlocker, Joseph A. Konstan, A. l. Borchers, and John Riedl. 1999. An algorithmic framework for per- forming collaborative filtering. In Proc. of SIGIR'99. 230-237.
  16. Longke Hu, Aixin Sun, and Yong Liu. 2014. Your neighbors affect your ratings: On geographical neighborhood influ- ence to rating prediction. In Proc. of SIGIR'14.
  17. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proc. of ICLR'15.
  18. Dominik Kowald, Markus Schedl, and Elisabeth Lex. 2020. The unfairness of popularity bias in music recommendation: A reproducibility study. In Proc. of ECIR'20.
  19. Emanuel Lacic, Dominik Kowald, Matthias Traub, Granit Luzhnica, Jörg Peter Simon, and Elisabeth Lex. 2015. Tackling cold-start users in recommender systems with indoor positioning systems. In Proc. of ACM RecSys'15. ACM.
  20. Yujie Lin, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Dongxiao Yu, Jun Ma, Maarten de Rijke, and Xiuzhen Cheng. 2020. Meta matrix factorization for federated rating predictions. In Proc. of SIGIR'20.
  21. Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin Burke. 2020. Feedback loop and bias amplification in recommender systems. In Proc. of CIKM'20.
  22. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication- efficient learning of deep networks from decentralized data. In Proc. of AISTATS'17. PMLR, 1273-1282.
  23. A. K. M. Nuhil Mehdy, Michael D. Ekstrand, Bart P. Knijnenburg, and Hoda Mehrpouyan. 2021. Privacy as a planned behavior: Effects of situational factors on privacy perceptions and plans. In Proc. of UMAP'21.
  24. Peter Muellner, Dominik Kowald, and Elisabeth Lex. 2021. Robustness of meta matrix factorization against strict privacy constraints. In Proc. of ECIR'21.
  25. Milad Nasr, Reza Shokri, and Amir Houmansadr. 2019. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In Proc. of S&P'19. IEEE.
  26. Alan Said and Alejandro Bellogín. 2014. Comparative recommender system evaluation: benchmarking recommenda- tion frameworks. In Proc. of ACM RecSys'14. 129-136.
  27. Martin Saveski and Amin Mantrach. 2014. Item cold-start recommendations: Learning local collective embeddings. In Proc. of ACM RecSys'14. 89-96.
  28. Agrima Srivastava and G. Geethakumari. 2013. Measuring privacy leaks in online social networks. In Proc. of ICACCI'13. IEEE, 2095-2100.
  29. Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019. BERT4Rec: Sequential recom- mendation with bidirectional encoder representations from Transformer. In Proc. of CIKM'19. 1441-1450.
  30. Mengting Wan and Julian J. McAuley. 2018. Item recommendation on monotonic behavior chains. In Proc. of ACM RecSys'18. 86-94.
  31. Mengting Wan, Rishabh Misra, Ndapa Nakashole, and Julian J. McAuley. 2019. Fine-grained spoiler detection from large-scale review corpora. In Proc. of ACL'19. Association for Computational Linguistics, 2605-2610.
  32. Yu Xin and Tommi Jaakkola. 2014. Controlling privacy in recommender systems. In Proc. of NIPS'14. 2618-2626.
  33. Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013. Learning fair representations. In Proc. of ICML'13. PMLR, 325-333.
  34. Minxing Zhang, Zhaochun Ren, Zihan Wang, Pengjie Ren, Zhunmin Chen, Pengfei Hu, and Yang Zhang. 2021. Mem- bership inference attacks against recommender systems. In Proc. of ACM SIGSAC'21. 864-879.
  35. Tianqing Zhu, Gang Li, Yongli Ren, Wanlei Zhou, and Ping Xiong. 2013. Differential privacy for neighborhood-based collaborative filtering. In Proc. of IEEE/ACM ASONAM'13. 752-759.

Cited by

Sorted by citations

Authors
Müllner, P., Lex, E., Schedl, M., & Kowald, D.
Affiliations
  • Graz University of Technology (AT)
  • Johannes Kepler University of Linz (AT)
Venue
ACM Transactions on Intelligent Systems and Technology
Published
2023-08-11
Volume
14
Issue
5
Pages
1-29
ISSN
  • 2157-6904 (ISSN-L)
  • 2157-6912
OpenAlex
W4384201236
Cited by
27
References
32
Citations by year
2026: 3 · 2025: 8 · 2024: 12 · 2023: 4
FWCI
2.39
Type
journal article
Language
en
Open access
Locations
  • ACM Transactions on Intelligent Systems and Technology (publishedVersion, other-oa)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • DDAI
  • COMET Module within the COMET — Competence Centers for Excellent Technologies Programme
  • Austrian Federal Ministry for Transport, Innovation and Technology
  • Austrian Federal Ministry for Digital and Economic Affairs
  • Austrian Research Promotion Agency
  • TU Graz Open Access Publishing Fund, the Austrian Science Fund (P33526 and DFH-23)
  • State of Upper Austria and the Federal Ministry of Education, Science, and Research (LIT-2020-9-SEE-113)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
  • Social Sciences › Sociology and Political Science › Privacy, Security, and Data Protection
Keywords
differential privacy, k-nearest neighbors, recommender systems, user-based recommendation, privacy risks, privacy-utility trade-off

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review