Novel Collaborative Filtering Recommender Friendly to Privacy Protection

1 Introduction

Recommender system is one of the most frequently used machine learning technologies in many different applications. Both academia and industry have spent a lot of efforts in designing and implementing new recommendation algorithms. These efforts have largely focused on improving the recommendation accuracy, while some efforts have also been dedicated to other useful properties such as explanability. Today, many state-of-the-art recommendation algorithms are very sophisticated, due to the aim for higher accuracy. Fed with a very large dataset, most of them face an efficiency bottleneck, i.e., it takes huge amount of computing resources to train a recommender model. We argue that, although there is a proliferation of recommendation algorithms including deep learning based ones [Zhang et al., 2017], designing simple and efficient recommendation algorithms with good accuracy performance is still an interesting research question.

∗Contact Author

In parallel, with the ever-increasing personal data abuse and new privacy regulations, privacy issues in recommender systems has become a hot topic, even though the issues have been mentioned many years ago, e.g., [Ramakrishnan et al., 2001]. So far, a number of privacy-preserving recommender solutions have been proposed. Differentialprivacy based solutions (e.g., [McSherry and Ilya, 2009; Berlioz et al., 2015]) often require the users to trust the service provider and downgrade the accuracy. Cryptographic solutions can allow users to protect their data without affecting accuracy, but they are often too complex to be practical. Representative cryptographic solutions, such as Nikolaenko et al. [Nikolaenko et al., 2013] and Kim et al. [Kim et al., 2016], introduce third-party crypto service providers to improve efficiency, nevertheless their performance is still far from practical and moreover the third party is difficult to be instantiated in practice. From the privacy perspective, it is also an interesting research question to design simple and efficient recommendation algorithms that facilitate privacy protection.

1.1 Our Contribution

In this paper, we propose a new recommender, named CryptoRec, which aims to facilitate privacy protection while still achieving state-of-the-art accuracy. CryptoRec decouples user features from the model parameter space, allowing a service provider to estimate a new user's preferences by directly using a model pre-learned from an expert dataset (e.g., the massive user data collected from the internet or a company's business can be used to construct such a dataset). It only relies on additions and multiplications, simplifying the execution on encrypted data. Inspired by [Han et al., 2015], we propose a new model compression strategy, named SparseQuantization-Reuse, to reduce response latency without affecting accuracy. We evaluate the accuracy of CryptoRec with three real-world datasets and show that it is competitive with state-of-the-art recommenders. In addition, we demonstrate CryptoRec also has a nice transferability property.

Different from existing model-based algorithms, in CryptoRec, the new user's data is not required in the recommendation model training process. This is a crucial property for efficient privacy protection, because the complexity of existing solutions such as [Nikolaenko et al., 2013; Kim et al., 2016] mainly comes from the requirement that the user's data need to be used to train the model! We introduce two privacy-preserving protocols to compute predictions for privacy-savvy users with CryptoRec: the first one uses a pre-learned CryptoRec model to compute recommendations directly; the second one allows us to fine-tune the model parameters based on privacy-savvy user's data to further improve accuracy. Our results show that our first protocol (i.e., without fine-tuning) allows securely computing predictions of thousands of items within a few seconds on a single PC, significantly outperforming existing solutions which are also far more inefficient than the second protocol.

2 Preliminaries

In this section, we introduce collaborative filtering based recommenders and our major privacy protection building block, namely homomorphic encryption.

2.1 Collaborative Filtering (CF)

Collaborative filtering (CF) is a state-of-the-art technique for building recommender systems [Zhang et al., 2017]. Below, we briefly review three representative types of CF algorithms.

Neighborhood-Based Method (NBM). The neighborhood based method estimates a user's rating on a targeted item by taking the weighted average of a certain number of ratings of the user or of the item. A typical item-based NBM (I-NBM) is defined as ˆ rui = ¯ ri + ∑j∈Nu(i) sij(ruj-¯ rj ) ∑j∈Nu(i) |sij| , where ¯ ri is the mean rating of item i, ruj is the rating user u gave to item j. sij ∈ Sm×m is the similarity between item i and j, m is the number of items, Nu(i) denotes a set of items rated by user u that are the most similar to item i. Cosine and Pearson correlation are widely used similarity metrics. User-based NBM is the symmetric counterpart of I-NBM, while I-NBM is more accurate [Su and Khoshgoftaar, 2009].

Matrix Factorization (MF). Let Rn×m be a sparse rating matrix formed by n users and m items, in which each user rated a small number of the m items, and the missing values are marked with zero. Matrix factorization (MF) decomposes the rating matrix R into two low-rank and dense feature matrices [Koren et al., 2009]: R ≈ PQT , where P ∈ Rn×d is the user feature space, Q ∈ Rm×d is the item feature space and d ∈ N+ is the dimension of user and item features. To predict how user u would rate item i, we compute ˆ rui = puqTi , where p1×d u ⊂ P and q1×d i ⊂ Q denote the learned features vectors of user u and item i, respectively. A standard way of optimizing P and Q is to minimize the regularized squared objective function using only observed ratings ({rui > 0}(u,i)∈R)

by using the stochastic gradient descent method (SGD) [Koren et al., 2009].The constant λ is a regularization factor.

Neural Network Approach. AutoRec [Sedhain et al., 2015] is a notable example of neural network based recommenders, built on top of Autoencoders. Item-based AutoRec (I-AutoRec) reconstructs the inputs ri by computing ˆri = f(W· g(Vri +b(1) )+b(2) ), where g(·) and f(·) are activation functions, e.g., the Sigmoid function ( 1 1+e-x ). Nonlinear activation functions are crucial to the success of neural networks. Model parameters W ∈ Rn×d , V ∈ Rd×n , b(1) ∈ Rd×1 and b(2) ∈ Rn×1 are learned by minimizing the regularized square objective function

where using only observed ratings. The user-based AutoRec (U-AutoRec) is defined symmetrically in the obvious way, which is not as accurate as I-AutoRec [Sedhain et al., 2015].

2.2 Homomorphic Encryption (HE)

Homomorphic encryption (HE) is a form of encryption that allows computations to be carried over ciphertexts without decryption. The result, after decryption, is the same as if the operations had been performed on the plaintexts [Gentry, 2009]. Consider two plaintexts x1 and x2 and their corresponding ciphertexts Jx1K ← HE.Enc(x1, pk) and Jx2K ← HE.Enc(x2, pk). An encryption scheme is additively homomorphic if it satisfies x1 + x2 = HE.Dec(Jx1K ⊕ Jx2K, sk) or multiplicatively homomorphic if we have x1 × x2 = HE.Dec(Jx1K⊗Jx2K, sk), where ⊕ and ⊗ represent the homomorphic additive and multiplicative operators, respectively. In addition to the homomorphic properties of ciphertexts, HE schemes also allow additions (⊕) and multiplications (⊙) between a ciphertext and a plaintext, i.e., x1 + x2 = HE.Dec(Jx1K⊕x2, sk) and x1×x2 = HE.Dec(Jx1K⊙x2, sk).

3 Encryption-aware CryptoRec Recommender

In this section, we first present the new CryptoRec recommender which is HE-friendly; then we introduce a SparseQuantization-Reuse method for further improving efficiency; lastly, we describe the transferability property of CryptoRec.

3.1 Description of CryptoRec Recommender

In CryptoRec, a user is profiled by items that the user has consumed and, likewise, an item is essentially identified by the ratings received from users. Therefore, it is possible to learn item features from massive user data collected by the server. Correspondingly, we can also construct user features by aggregating the pre-learned item features according to a user's ratings history. Suppose the server has already learned the item features Q = {qi }mi=1 from its database, we define the user features as follows,

where φu = {φui}mi=1 and (ru - ¯ ru) · φu denotes {(rui - ¯ ru)φui}mi=1 . If user u rated item i, then φui = 1, otherwise, we let φui = 0 and rui = 0. To approximate an observed rating rui, we follow matrix factorization [Koren et al., 2009], performing a dot production between user and item features,

Real-world datasets often exhibit large systematic tendencies for some users to give higher ratings than others, and for some items to receive higher ratings than others. This fact may prevent the model (Eq. (4)) from precisely modeling user preferences. A common solution is to model the biases of individual users or items, subjecting only the true user-item interactions to the factor machine [Koren et al., 2009]. Follow this, we separate the user preference estimation into the biases approximator and user-item interaction approximator,

where µ is the global rating average. bu = ¯ ru - µ and bi = ¯ ri - µ approximate user and item individual biases, respectively. As such, only the true user-item interaction is modeled by the factor machine (i.e., Eq.(4)).

The accuracy of user-item interaction modeling only relies on the item feature Q, which may limit the model expressiveness. So that we relax the item features which were used to construct user features P, and redefine Eq. (5) as,

Note that A ∈ Rm×d is a new item feature space, which will be optimized independently.

Model Training. The model Θ = {A,Q} can be learned by minimizing the regularized square objective function,

Using the back-propagation method, we have the gradient of each model parameter of CryptoRec as follows,

where eui = ˆ rui - rui, eu = {eui}mi=1 , ei = {eui}nu=1 , and eu · φu = {eui · φui}mi=1 . ⊛ denotes outer product. In the training phase, we compute the gradient for each randomlydivided batch. Algorithm 1 outlines the training procedure.

Prediction Computation. Suppose a server has trained the parameters {A,Q} on its dataset, then it can predict a new client ratings for the unrated items by Eq. (6). We stress that the client's rating vector is not necessarily involved in training the model. This is different from existing collaborative filtering approaches, e.g., those from Section 2.1. We refer this to be the fast-mode prediction, denoted as CryptoRec-f .

Even CryptoRec-f can provide very good accuracy, we can still fine-tune the pre-learned parameters Θ = {A,Q}

Algorithm 1 CryptoRec training procedure T

with a new client v's rating vector to achieve better recommendation accuracy for this client. The fine-tuning process is identical to Algorithm 1, where the inputs become rv, φv ,¯rv and Θ = {A,Q}. Note that rv, φv ,¯rv are possessed by the client v and Θ is possessed by the server. We refer this to be the accurate-mode prediction, denoted as CryptoRec-a.

3.2 Sparse-Quantization-Reuse Method

When we apply homomorphic encryption (HE) to protect privacy in computing predictions, shown in Section 5, the multiplications in the user-item interaction estimation (i.e., ((ru - ¯ ru)A)QT ) will dominate the runtime.

To minimize the number of multiplications on encrypted data, we introduce a sparse-quantization-reuse method. We first sparsify a pre-learned CryptoRec model Θ = {A, Q} by removing parameters which don't contribute to final predictions, without losing accuracy. Specifically, we remove all weights whose absolute values (θ ∈ Θ) fall below a threshold (e.g., |θ| < 1.0 × 10-3 ). Next, we quantify the weights to enforce more weights to share the same values. Following the method in [Han et al., 2015], we classify each feature matrix Q and A into 512 clusters (i.e., each feature contains 512 shared weights), without affecting the accuracy. Lastly, we reuse the shared multiplicative results if possible, illustrated in Figure 1.

In Section 4.2, we will show this method can greatly improve the efficiency in privacy-preserving protocols. Besides facilitating privacy protection, together with data compression [Van Leeuwen, 1976], the sparse-quantization step can reduce the model size significantly. This will facilitate the deployment of recommendation services on mobile devices subjecting to limited network bandwidth and storage resources.

3.3 Transferability Property of CryptoRec

In recommender systems, transferring the knowledge learned from a source domain to a target domain to improve accuracy and mitigate the notorious cold start problem is a challenging task [Cantador et al., 2015]. CryptoRec naturally achieves transferability if two datasets share the same item entries, improving both efficiency and accuracy ( Section 4.3).

4 Evaluation of CryptoRec Recommender

We test CryptoRec on three movie rating datasets (Table 1): netflix [Netflix, 2010], ml1m [Grouplens, 2010], yahoo [Yahoo!, 2010]. The testbed is a PC with 8 Intel Xeon(R) processors (3.5 GHz, 16 GB RAM), using Ubuntu 16.04.

The baseline models include item-based NBM (INBM) [Desrosiers and Karypis, 2011], matrix factorization (BiasedMF) [Koren et al., 2009], user-based AutoRec (UAutoRec) and item-based AutoRec (I-AutoRec) [Sedhain et al., 2015]. To train the CryptoRec model, we choose η = 0.0002, λ = 0.00002 and the dimension d = 500. To train the baseline models, we perform a grid search around the suggested settings given in their original papers. For each dataset, we randomly split all the users into a training set (80%) and a validation set (20%), then we randomly divide each user vector of the validation set into a feeding set (90%, simulating the client's data) and a testing set (10%, denote as D). For all the models, we repeat the accuracy experiments five times on each dataset. The root mean square error (RMSE) is adopted as the accuracy metric, RMSE = √∑(u,i)∈D (ˆ rui-rui)2 .

4.1 Accuracy Evaluation

With respect to the accurate-mode algorithmCryptoRec-a, we observed that the first several iterations contribute the most to the accuracy increase. Particularly, the accuracy is asymptotically close to the best performance within 3 to 5 iterations. This means that we can adopt an early-stop strategy to halt the fine-tuning, when applying privacy protection mechanism (i.e., HE) in which case the outputs cannot be monitored by the server to determine convergence. In the following discussions, CryptoRec-a(1) means fine-tuning in one iteration and CryptoRec-a(n) represents fine-tuning until convergence. Figure 2 shows the accuracy loss (i.e., RMSE increase), where I-AutoRec serves as the benchmark. Compared to the best accuracy (i.e., I-AutoRec), CryptoRec loses accuracy at most 4.6% and 1.8% on the fast-mode and accurate-mode, respectively. All baseline models are trained with all the user data from scratch, while CryptoRec-f is only based on a pre-trained model (the client's data is excluded from the training process), and CryptoRec-a is finetuned with only the client's data.

4.2 Sparse-Quantization-Reuse Evaluation

We first prune the parameters (i.e., A, Q) of which the weights are in the range of (-5.0×10-4 , 5.0×10-4 ), without affecting the accuracy. Then, we use k-means clustering (k=512, in this paper) to identify the shared values of each feature, so that all the parameters that fall into the same cluster share the same value. To reduce the latency, the server should perform the two steps offline. Lastly, we reuse the shared multiplication results when computing pu ← ruA and ˆru ← puQT in prediction computation.

As shown in Table 2, the server can remove more than 90% of computations, resulting in a 10× better efficiency. The pruning ratio is defined as # of pruned parameter # of all the parameter . The reuse ratio is defined as 1 - ∑i sharedi ∑i alli , where sharedi (resp. alli) indicates the number of shared values (resp. all the non-zero values) at i-th row of a feature matrix.

4.3 Transferability Evaluation

To evaluate the transferability of CryptoRec, we constructed two datasets pairs (ml1 (from ml1m) and yah (from yahoo); ml2 (from ml1m) and net (from netflix)), and each pair share the same item entries. Details are summarized in Table 3.

For knowledge transferring, we use the model trained on the source (src) dataset to initialize the training on the target (tgt) dataset. As shown in Table 4, the transferred knowledge improves both the accuracy and efficiency (reducing training iterations (iter#)). Especially, when transferring the knowledge learned from a relatively dense dataset to a sparse dataset, the improvement is more significant.

5 Privacy-preserving CryptoRec Protocols

In this section, for convenience, we simplify the definition of CryptoRec (Eq. (6)) as ˆ rui = µ + bu + bi + (ruA)qTi , and denote the client as v. In all protocols, the client generates a public/private homomorphic encryption (HE) key pair and shares the public key with the server.

5.1 Fast-Mode Prediction Protocol

As shown in Figure 3, the protocol runs in three stages. First, the client v sends her encrypted rating vector JrvK and J¯ rv K to the server; Then, the server executes the prediction process P (Algorithm 2 which converts Eq. (6) into an HE domain) and returns the encrypted results ˆrv. Lastly, the client postprocesses the predictions after decryption, such as clamping the predictions into a proper range or selecting favorite items.

ˆrv ← HE.Dec(JˆrvK, sk)

Figure 3: Privacy-preserving Fast-Mode Protocol

Algorithm 2 CryptoRec prediction procedure P

Input: ratings JrvK, J¯

rvK ; Θ = {A, Q, µ, ¯ri}

Output: predictions JˆrvK

1: procedure P({JrvK, J¯ rv K}, Θ) 2: Jpv K ← JrvKA ▷ HE dot-product using ⊙ and ⊕ 3: for i ← [1, 2, · · · ,m] do 4: Jˆ rviK ← bi ⊕ J¯ rv K ⊕ Jpv KqTi ▷ bi = ¯ ri - µ 5: JˆrvK[i] ← Jˆ rviK 6: return JˆrvK

For the sake of succinctness, we do not explicitly describe the sparse-quantization-reuse in Algorithm 2 (at line 2, 4).

5.2 Accurate-Mode Prediction Protocol (full)

In this protocol, shown in Figure 4, the server needs to finetune the pre-learned model (using the client's encrypted data) before computing predictions. The fine-tuning process is identical to the regular training process (T , Algorithm 1). Since the training process only contains additions and multiplications, we can also convert it into an HE space easily.

Different from the fast-mode protocol, the client v also has to send an encrypted indication vector JφvK to the server, completing the objective function computation. In contrast to the fast-mode protocol in Algorithm 2, after the fine-tuning process, the model Θ becomes encrypted. So the related operations in P (Algorithm 2) should be updated to their corresponding homomorphic operations.

ˆrv ←$ HE.Dec(JˆrvK, sk)

Figure 4: Privacy-preserving Accurate-Mode Protocol

5.3 Accurate-Mode Prediction Protocol (simp)

Performing the fine-tuning process on encrypted data is challenging, due to the prohibitive cost in ciphertext-only computation and corresponding storage, see the Section 5.4. Though it is not infeasible for a commercial server, it is too expensive to respond to a single query while the accuracy improvement is limited. Fortunately, as shown in Figure 2, the first finetuning iteration moves a big step towards the convergence. Combining together this fact and software engineering, we can achieve better accuracy with a modest increase of computation cost. Briefly, in the forward pass of the first iteration, we can apply the sparse-quantization-reuse method from Section 3.2 to accelerate the computation. In the backward pass, we immediately release the model parameters which will not be used in the future. Algorithm 3 details the first-iteration fine-tuning and prediction computation process.

Algorithm 3 CryptoRec-a(1): one-iteration fine-tuning

5.4 Asymptotic Performance Analysis

The complexity of each HE operation type is different. Generally, ⊗ is higher than ⊙, which in turn higher than ⊕. Nonlinear operations are not compatible with HE schemes, and incur much higher complexity. I-NBM, I-AutoRec and UAutoRec contain non-linear operations. BiasedMF has to be trained on the whole dataset. In contrast, CryptoRec-f needs only ⊙,⊕ and CryptoRec-a only relies on the client's data, resulting in a significant advantage in efficiency. Detailed complexity information appear in Table 5.

5.5 Experimental Performance Analysis

We implement the fast-mode prediction protocol (which needs ⊕,⊙) with an efficient additive HE scheme, Paillier cryptosystem [Paillier, 1999] supported by the library pythonpaillier [CSIRO, 2018]. The secret key size is 2048. In this setting, the size of each encrypted message is 0.5KB.

For accurate-mode prediction protocol (which needs ⊕,⊙,⊗), we adopt a ring-based somewhat (fully) HE scheme, the Fan-Vercauteren scheme [Fan and Vercauteren, 2012] supported by the SEAL library [Chen et al., 2017]. We let the polynomial degree be 4096, the plaintext module be 65537. To encode real numbers, we reserve 1024 coefficients of the polynomial for the integral part and expand the fractional part to 16 digits of precision. For more detail on this configuration, we refer interested readers to [Chen et al., 2017]. In this setting, the size of a ciphertext is 96 KB. However, the item features often contain millions of parameters. Take the CryptoRec-a(n > 1) on dataset ml1m as an example, the features JA3952×500 K and JQ3952×500 K has around 4 million parameters, which requires 360GB RAM. In the experiment, we implemented the one-iteration fine-tuning (Algorithm 3), which only needs less than 2GB RAM.

Table 6 describes the running time and communication cost on each dataset. Compared to the fast-mode implementation, though the time cost of the accurate-mode implementation is significantly increased, the server can amortize the cost by packing multiple user data into one message similar to [GiladBachrach et al., 2016].

As far as we know, CryptoRec is the first solution allowing online recommendation services in real-time, while preserving the privacy. Using existing recommenders (e.g., MF), before computing recommendations, the server often has to train the model with the client's encrypted data and its database. Recent advances in devising secure frameworks to execute existing recommenders come from GraphSC [Nayak et al., 2015], in which a single training iteration of MF took 13 hours to run on 128 processors. On the ml1m dataset, about 20 iterations are necessary for convergence.

6 RelatedWork

Canny et al. [Canny, 2002] introduced a distributed solutions to factor the Singular Value Decomposition securely, based on HE schemes. To further improve the efficiency, Nayak et al. [Nayak et al., 2015] brought parallelism to the execution of the oblivious version of graph-based algorithms (e.g., MF). Shmueli and Tassa [Shmueli and Tassa, 2017] presented a solution for securely learning neighborhood-based models, by assuming a semi-honest mediator which computes and distributes intermediate values to each party. Technically, these solutions can be adjusted for providing online recommendation services. But the computation latency would prevent the use of the services in the real world.

Recent solutions for privacy-preserving Machine Learning as a Service often assume the server has a pre-learned machine learning model [Gilad-Bachrach et al., 2016; Liu et al., 2017; Zhang et al., 2018], separating the training process from machine learning services. Most efforts have been focused on efficiently computing non-linear operations. GiladBachrach et al. [Gilad-Bachrach et al., 2016] substituted nonlinear activation functions with a square function. However, this approach often leads to a significant accuracy loss [Liu et al., 2017; Rouhani et al., 2017; Zhang et al., 2018]. To preserve accuracy, Liu et al. [Liu et al., 2017] and Rouhani et al. [Rouhani et al., 2017] proposed to evaluate neural networks using secure multiparty computation schemes, but requiring the server and client to be online constantly.

7 Conclusions

In this paper, we proposed an encryption-aware recommender, CryptoRec, which can provide privacy-preserving recommendation services with high throughput, while being competitive with state-of-the-art accuracy performance.

Acknowledgments

This work is supported by the Fonds National de la Recherche, Luxembourg (project code: C13/IS/5856658).