Abstract
Nowadays, recommender system is an indispensable tool in many information services, and a large number of algorithms have been designed and implemented. However, fed with very large datasets, state-of-the-art recommendation algorithms often face an efficiency bottleneck, i.e., it takes huge amount of computing resources to train a recommendation model. In order to satisfy the needs of privacy-savvy users who do not want to disclose their information to the service provider, the complexity of most existing solutions becomes prohibitive. As such, it is an interesting research question to design simple and efficient recommendation algorithms that achieve reasonable accuracy and facilitate privacy protection at the same time. In this paper, we propose an efficient recommendation algorithm, named CryptoRec, which has two nice properties: (1) can estimate a new user's preferences by directly using a model pre-learned from an expert dataset, and the new user's data is not required to train the model; (2) can compute recommendations with only addition and multiplication operations. As to the evaluation, we first test the recommendation accuracy on three real-world datasets and show that CryptoRec is competitive with state-of-the-art recommenders. Then, we evaluate the performance of the privacy-preserving variants of CryptoRec and show that predictions can be computed in seconds on a PC. In contrast, existing solutions will need tens or hundreds of hours on more powerful computers.
Introduction
Recommender systems face a fundamental tension between utility and privacy. To provide high-quality suggestions, service providers typically require access to raw user data (ratings, clicks, etc.) to train their models. Existing privacy-preserving solutions generally fall into two categories, both with significant drawbacks. Differential Privacy (DP) adds noise to data, which is fast but degrades accuracy. Cryptographic solutions, such as Homomorphic Encryption (HE), are mathematically secure but computationally intensive, struggling with non-linear operations (like Sigmoid functions) and the massive number of multiplications required for large datasets.
CryptoRec aims to bridge this gap by creating a recommender that is "HE-friendly"—relying only on simple additions and multiplications—and efficient enough to run on a standard PC.
Methods
CryptoRec departs from standard Matrix Factorization (MF) through several key innovations:
- Decoupled Feature Estimation: Instead of requiring a user's data to be part of the initial model training, CryptoRec uses a model pre-learned from an "expert dataset" (massive public or historical data). It estimates a new user’s preferences by aggregating these pre-learned item features based on the user's encrypted rating history.
- HE-Friendly Architecture: The algorithm avoids non-linear activation functions, relying instead on dot products that translate efficiently into the additive and multiplicative operations supported by HE schemes like Paillier and Fan-Vercauteren.
- Sparse-Quantization-Reuse: To overcome efficiency bottlenecks, the authors implement three optimizations: sparsification (pruning near-zero weights), quantization (clustering weights to share values), and reuse.
By reusing the results of multiplications for identical weights, the system reduces the computational load by over 90%, resulting in a 10x efficiency gain.
Key Results
The model was evaluated using three well-known movie rating benchmarks: Netflix, MovieLens 1M (ml1m), and Yahoo! Movies. The system offers two modes: CryptoRec-f (Fast-mode, using pre-trained parameters) and CryptoRec-a (Accurate-mode, which allows for iterations of fine-tuning).
As shown in the results, CryptoRec is highly competitive. Compared to the state-of-the-art (I-AutoRec), the "Fast" mode only loses about 4.6% accuracy, while the "Accurate" mode (with fine-tuning) narrows that gap to just 1.8%. Notably, on the Yahoo dataset, CryptoRec-a(n) even shows a slight improvement over the baseline (negative accuracy loss).
In terms of performance, the Fast-mode allows predictions for thousands of items to be computed in seconds on a standard PC. This is a significant improvement over previous cryptographic solutions that required tens or hundreds of hours on powerful clusters.
Conclusion
CryptoRec demonstrates that it is possible to achieve near-state-of-the-art recommendation accuracy while maintaining strict user privacy through Homomorphic Encryption. By decoupling feature estimation and utilizing a Sparse-Quantization-Reuse strategy, the framework provides a practical, efficient solution for privacy-conscious recommendation services. Future work will focus on reducing the latency of the fine-tuning process in the Accurate-mode to make it more suitable for real-time applications.
Summary updated