An Accuracy-Assured Privacy-Preserving Recommender System for Internet Commerce

Zhigang Lu, Hong Shen

Introduction

Modern e-commerce platforms rely heavily on neighborhood-based collaborative filtering to provide personalized recommendations. By identifying a set of $k$ "neighbors"—users with similar historical preferences—these systems can predict a target user's interest in new products. However, this reliance on user similarity creates a significant privacy vulnerability known as the $k$NN attack. In such an attack, a malicious actor creates fake accounts to mimic a target user, forcing the system to identify the target as a neighbor and subsequently leaking their private data through recommendation outputs.

While Differential Privacy (DP) has been proposed as a solution, traditional methods often introduce "global randomness" that degrades recommendation accuracy to the point of obsolescence. This paper introduces Partitioned Probabilistic Neighbour Selection (PPNS), a novel framework designed to resolve the long-standing conflict between user privacy and system utility.

The Problem: The $k$NN Attack and Utility Loss

In a standard $k$NN attack, an attacker with partial knowledge of a user's ratings can inject $k$ sybil profiles into the system. Because these profiles are designed to be the target's closest neighbors, the system’s output becomes a direct reflection of the target's private ratings.

Existing defenses typically apply noise to the entire user pool. While this provides formal privacy guarantees, it often results in the selection of neighbors with low similarity to the target, causing the Mean Absolute Error (MAE) of recommendations to spike. The authors identify a critical gap in the literature: a lack of mechanisms that provide a guaranteed level of data utility while maintaining robust privacy.

The PPNS Framework

PPNS addresses this gap by replacing global randomness with a structured, partitioned selection process. The method follows four primary steps:

  1. Partitioning: The system sorts all potential neighbors by their similarity to the target user and divides them into exclusive partitions, each of size $k$.
  2. Geometric Selection: Instead of picking neighbors uniformly, the system uses a geometric distribution (governed by a parameter $p$) to select which partitions to draw neighbors from. This ensures that the majority of neighbors are selected from the most similar partitions, preserving accuracy.
  3. Intra-Partition Differential Privacy: Within each selected partition, the exponential mechanism is used to select specific users. This ensures that the selection process within the group meets formal differential privacy requirements.
  4. The "Last Neighbor" Logic: To satisfy the mathematical requirements of absolute differential privacy—where every user must have a non-zero probability of being selected—the final neighbor is drawn from all remaining unvisited partitions.

Quantifying the Trade-off

To manage the balance between security and accuracy, the authors define two key metrics:

  • Accuracy Metric ($\alpha$): The expected sum of similarities of the selected neighbors. This allows administrators to set a target utility level.
  • Security Metric ($\beta$): The number of partitions across which the $k$ neighbors are distributed. This represents the "fraud cost" for an attacker, as they would need to compromise multiple partitions to succeed.

Experimental Evaluation

The researchers evaluated PPNS using the MovieLens 100k dataset, a benchmark containing 100,000 ratings from 943 users. Performance was measured using Mean Absolute Error (MAE) against existing Private Neighbour Collaborative Filtering (PNCF) methods.

Key Results

  • Superior Accuracy: PPNS consistently achieved lower MAE than previous probabilistic methods. By confining randomness to partitions, the system keeps high-quality neighbors at the top of the selection list.
  • Tunability: When the selection parameter $p$ is high (approaching 1), the system’s accuracy is nearly indistinguishable from a non-private $k$NN system, while still providing a baseline of security against $k$NN attacks.
  • Stability: Unlike competing methods that see performance plummet as privacy constraints tighten, PPNS maintains a steady performance curve, making it more reliable for commercial deployment.

Discussion and Insights

The core innovation of PPNS is the shift from global to local randomness. By partitioning the user space, the system prevents an attacker from "trapping" a target user in a single neighborhood without significantly diluting the quality of the recommendations. Furthermore, the authors generalized the standard $k$NN attack into a $\beta$-$k$NN attack, demonstrating that PPNS makes such attacks economically unfeasible by requiring an attacker to create a prohibitively large number of fake accounts.

Conclusion and Future Work

PPNS provides a mathematically grounded approach to privacy that does not sacrifice the commercial viability of recommender systems. While the current study focuses on user-based collaborative filtering using the MovieLens dataset, the underlying logic of partitioned selection is theoretically applicable to item-based filtering as well. Future research may explore the computational overhead of real-time partitioning in large-scale systems with millions of users and further refine the "last neighbor" selection logic to optimize the tail-end of the differential privacy distribution.

Summary updated

Abstract

Recommender systems, tool for predicting users’ potential preferences by computing history data and users’ interests, show an increasing importance in various Internet applications such as online shopping. As a well-known recommendation method, neighbourhood-based collaborative filtering has attracted considerable attentions recently. The risk of revealing users’ private information during the process of filtering has attracted noticeable research interests. Among the current solutions, the probabilistic techniques have shown a powerful privacy preserving effect. The existing methods deploying probabilistic methods are in three categories, one [19] adds differential privacy noises in the covariance matrix; one [1] introduces the randomisation in the neighbour selection process; the other [29] applies differential privacy in both the neighbour selection process and covariance matrix. When facing the k Nearest Neighbour (kNN) attack, all the existing methods provide no data utility guarantee, for the introduction of global randomness. In this paper, to overcome the problem of recommendation accuracy loss, we propose a novel approach, Partitioned Probabilistic Neighbour Selection, to ensure a required prediction accuracy while maintaining high security against the kNN attack. We define the sum of k neighbours’ similarity as the accuracy metric α, the number of user partitions, across which we select the k neighbours, as the security metric β. We generalise the k Nearest Neighbour attack to the βk Nearest Neighbours attack. Differing from the existing approach that selects neighbours across the entire candidate list randomly, our method selects neighbours from each exclusive partition of size k with a decreasing probability. Theoretical and experimental analysis show that to provide an accuracy-assured recommendation, our Partitioned Probabilistic Neighbour Selection method yields a better trade-off between the recommendation accuracy and system security.
BibTeX
@inproceedings{lu2015accuracy,
  author = {Zhigang Lu and Hong Shen},
  title = {{An Accuracy-Assured Privacy-Preserving Recommender System for Internet Commerce}},
  booktitle = {Comput. Sci. Inf. Syst},
  year = {2015},
  url = {https://openreview.net/forum?id=LH_PjZY9re},
}
Figure