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:
- Partitioning: The system sorts all potential neighbors by their similarity to the target user and divides them into exclusive partitions, each of size $k$.
- 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.
- 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.
- 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