Binarized Collaborative Filtering with Distilling Graph Convolutional Network

1 Introduction

Nowadays, recommender systerms are widely used in people's daily life [Liu et al., 2011; Lian et al., 2016; Li et al., 2018a], but a growing scale of users and products renders recommendation challenging. Because implicit feedback is more common and easier to collect than explicit feedback, we concentrate on how to accelerate top-K recommendation based on implicit feedback. However, there are two challengings to address. Firstly, compared with explicit feedback, implicit feedback is more difficult to utilize because of the lack of negative samples [Pan et al., 2008]. Secondly, generating top-k preferred items for each user is extremely timeconsuming.

For the first problem, recently, SpectralCF [Zheng et al., 2018] combined collaborative filtering model with graph convolutional network [Henaff et al., 2015] to mine hidden interactions between users and items from spectral domain, which showed enormous potential for implicit feedback problem [Zheng et al., 2018]. However, SpectralCF ignores highorder feature interaction.

∗Corresponding author

For the second problem, for extracting top-K preferred items for each user, the time complexity of recommendation is O(MND + MNlogK) when there are M users, N items and D dimensions in the latent space. Therefore, this is a critical efficiency bottleneck. However, it is necessary to timely update recommendation algorithms and the recommendation list because user interest evolves frequently. Fortunately, hash technique, encoding real-valued vectors/matrices into binary codes(e.g., {0, 1}, {-1, 1}), is promising to address this challenge because inner product can be efficiently computed between binary codes via bit operation. Finding approximate top-K items can be even finished in sublinear or logarithmic time [Wang et al., 2012; Muja and Lowe, 2009] by making use of index technique.

Several methods applied hash techniques to recommendation. Some two-stage approximation methods like BCCF [Zhou and Zha, 2012], PPH [Zhang et al., 2014], CH [Liu et al., 2014] incur large quantization loss [Zhang et al., 2016], and a direct optimization model DCF [Zhang et al., 2016] is easy to fall into a local optimum because it is based on local search. To this end, to improve the accuracy of hashing-based recommender systems for implicit feedback, we propose a binarized collaborative filtering framework with distilling graph convolutional network. In the framework, we firstly train a CF-based GCN model (GCN-CF) which can capture high-order feature interaction via cross operation. Following that, we distill the ranking information from the trained GCN-CF model into a binarized model (DGCNBinCF) with knowledge distillation technique (KD [Hinton et al., 2015]). To be more specific, we introduce a novel distillation loss, which penalizes not only the discrepancy between distributions of positive items defined by GCN-CF and that defined by Bin-CF, but also the the discrepancy between distributions of sampled negative items. Noting that learning hash codes is generally NP-hard [H˚astad, 2001], approximation methods are appropriate choices but it may incur the loss of information during the training process. To this end, inspired by [Dai et al., 2016], we transform the binary optimization problem to an equivalent continuous optimization problem by imposing a stochastic penalty term. Therefore, any gradient-based solver can optimize the overall loss with ranking-based loss with knowledge distillation loss.

Our contributions are summarized as follows:

• We propose a novel framework DGCN-BinCF to distill the ranking information from the proposed GCN-CF model into the binary model. To the best of our knowledge, DGCN-BinCF is the first model utilizing knowledge distilling to improve the performance of binarized model. We also improve GCN via adding a cross operation to aggregate users and items' own high-order features.
• We propose a generic method to relax the binary constraint problem to an equivalent bound-constrained continuous optimization problem. Hence, we can optimize the original problem by popular solvers directly.
• Through extensive experiments performed on three realworld datasets, we show the superiority of the proposed framework to the state-of-the-art baselines.

2 RelatedWork

In this section, we review several works related to our task including GCN for recommender systems, recent hashingbased collaborative filtering methods and distilling knowledge techniques for ranking.

2.1 GCN for Recommender Systems

How to take advantage of the rich linkage information from the user-item bipartite graph is crucial for implicit feedback. Some work used GCN to solve it such as SpectralCF [Zheng et al., 2018], GCMC [Berg et al., 2017], RMGCNN [Monti et al., 2017], GCNWSRS [Ying et al., 2018], LGCN [Gao et al., 2018], etc. (1)SpectralCF was the first model to learn from the Spectral domain of the user-item bipartite graph directly based on collaborative filtering. Because it could discover deep connections between users and items, it may alleviate cold-start problem. (2)GCMC combined GCN model with a graph auto-encoder to learn users' and items' latent factors. (3)RMGCNN proposed a matrix completion architecture combining a multi-graph convolutional neural network with a recurrent neural network. (4)GCNWSRS focused on how to apply GCN model for web-scale recommendation tasks effectively, like billion of items and hundreds of millions of users. (5)LGCN proposed a sub-graph training strategy to save memory and computational resource requirements greatly. Its experiments showed it was more efficient as compared to prior approaches.

2.2 Discrete Hashing for Collaborative Filtering

A pioneer work was to exploit Locality-Sensitive Hashing [Datar et al., 2004] to generate binary codes for Google News readers according to their click history [Das et al., 2007]. Then [Karatzoglou et al., 2010] proposed a method mapping users and items' latent factors into Hamming space to obtain binary representation. Later, following this, some two stage methods [Zhou and Zha, 2012; Zhang et al., 2014] which relaxed binary constraints at first and then quantified binary codes. Nonetheless, [Zhang et al., 2016] proposed that those two-stage methods suffered from large quantization loss. Therefore, DCF proposed a method which could optimize binary codes directly. However, DCF optimizes binary codes via searching neighborhoods with the distance one. So it is easy to fall into local optima.

2.3 Distilling Knowledge for Ranking

[Hinton et al., 2015] was the first one that proposed method "Knowledge Distilling", which trained a complex neural network firstly and then transferred the complex model to a small model. The role of the complex model is similar to a teacher, and the role of the small model is similar to a student. Following this, DarkRank [Chen et al., 2018] proposed a method combining deep metric learning and "Learning to rank" technique with KD to solve pedestrian re-identification, image retrieval and image clustering tasks. In addition, [Tang and Wang, 2018] applied KD with point-wise ranking on recommendation task. Unfortunately, it did not focus on implicit feedback problem and how to transfer unobserved interaction information.

3 Definitions and Preliminaries

Throughout the paper, we denote vectors by boldfaced lowercase letters and matrices by boldfaced uppercase letters. All vectors are considered as column vectors. Next, we define the following definitions in this paper:

Definition 1 (Bipartite Graph)A user-item bipartite graph with M + N vertices and E edges is defined as G = {U, I, E}, where U and I are two disjoint vertex sets of user and item, and M = |U|, N = |I|. For each edge e ∈ E, it has the form that e = (u, i), where u ∈ U and i ∈ I, which shows that there exists an interaction between user u and item i in the training set.

Definition 2 (LaplacianMatrix)Given a bipartite graph with M+N vertices and E edges, the laplacian matrix L is defined as L = D-1/2AD-1/2 , where A is the adjacent matrix and D is the (M + N) × (M + N) diagonal degree matrix defined as Dnn = ∑j Anj .

Our work focuses on recommendation based on implicit feedback, where we only observe whether a user has viewed or clicked an item. We denote I + i as the set of all items clicked by user i and denote I - i as the set of remaining items.

3.1 Binary Collaborative Filtering

Matrix factorization maps users and items onto a joint Ddimensional latent space, where user embedding matrix is represented by P = [p1 , · · · , pM ]′ ∈ RM×D and item embedding matrix is represented by Q = [q1 , · · · , qN ]′ ∈ RN×D . However, binary collaborative filtering (Bin-CF) maps users and items onto a joint D-dimensional Hamming space. Denoting Φ = [φ1, · · · ,φM]′ ∈ {-1, 1}M×D and Ψ = [ψ1, · · · ,ψM]′ ∈ {-1, 1}N×D as user and item's binary codes respectively, for implicit feedback, the Bin-CF

problem is formulated as follows:

3.2 Binary-Continuous Equivalent Transformation

Let us consider the following generic binary program firstly,

and a transformed problem,

where g(·):Rd → R is a penalty term for f(x) and β is its penalty coefficient. [Giannessi and Tardella, 1998; Lucidi and Rinaldi, 2010] show that the above two problems are equivalent when certain conditions hold.

Lemma 1 Denote || · || be a chosen norm. Suppose the following conditions hold:

1. When x ∈ [-1, 1]d , f(x) is bounded. In addition, there exists an open set A ⊃ {-1, 1}d and real positive number η, such that for ∀x1, x2 ∈ A, the following H¨ older condition is satisfied:

1. g(·) satisfies:
2. (a) g(·) is continuous on [-1, 1]d
3. (b) ∀x ∈ {-1, 1}d , g(x) = 0; ∀x ∈ (-1, 1)d , g(x) > 0
4. (c) ∀y ∈ {-1, 1}d , there exits a neighborhood S(y) of y and a real positive number ϵ(y), such that:

Then there exits a real value η0, such that ∀η > η0, problem 2 and problem 3 are equivalent.

It can be verified that g(x) = |||x| - 1||2F satisfies above conditions, and we adopt it as the penalty term.

4 Binarized Collaborative Filtering with Distilling Graph Convolutional Network

For binarized collaborative filtering for implicit feedback problem as shown in Eqn.1, there are three problems to solve. Firstly, the interaction information between users and items is extremely sparse. Secondly, a lot of information is lost during learning binary codes. Thirdly, binary optimization is general NP-hard, so we must adopt an efficient approximate method to solve it. We propose a novel framework-Binarized Collaborative Filtering with Distilling Graph Convolutional Network to deal with the aforementioned problems. Because GCN model can mine hidden connection information between users and items in user-item graph spectral domain, we train a GCN-based collaborative filtering model (GCNCF) to solve the first problem. Then we utilize knowledge distillation to transfer the ranking information fromGCN-CF into the binary model to make up for information loss. Finally, we propose a method to transform the binary optimization to a continuous optimization problem to solve the binary optimization problem.

4.1 GCN-based Collaborative Filtering

Following SpectralCF, our graph convolutional operation is shown as the following:

where L is the Laplacian matrix of the bipartite graph G. IM+N is an identity matrix, ρ(·) is an activation function and Θ(k) is a layer-specific trainable filter parameter. The proposed convolution operation as shown in Eqn. (6) is denoted as sp(X; L,Θ).In this model, we set it as a two-layer GCN. According to Eqn. (1), similarity to matrix factorization (MF) methods, it does not take advantage of the user's own and the item's own high-order interaction, which limits the performance of GCN. Inspired by CrossNet [Wang et al., 2017], we define the cross operation(cross op) to fix the problem. The cross operation can be formulated as

where xk is a user or item's embedding vector and wk is a parameter vector. The term xkwTk xk takes the place of the term x0wTk xk in CrossNet, which leads to obtaining higher-order interactions than CrossNet when setting the same iterations. In addition, the time complexity of the proposed cross operation is still the same as CrossNet's. The improved GCN model can be vectorized as follows:

where "◦" represents Hadamard product, "1" is a column vector whose elements are all 1 and W1,W2 ∈ R(M+N)×D are weight matrices. Moreover, we add batch normalization [Ioffe and Szegedy, 2015] before Eqn.8 and Eqn.11.

In order to make full use of features from every layer of GCN, we follow SpectralCF and concatenate them into the final latent factors of users and items as:

In terms of the loss function, we employ the popular and effective BPR loss [Rendle et al., 2009]. In particular, given a user matrix U and an item matrix V as shown in Eqn.12 and Eqn.13, the loss function of GCN-CF is given as

where ui and vj denote ith and jth rows of U and V respectively; λ is the regularization coefficient. Negative sample j ′ is sampled from I - i randomly and the training data D is generated as D = {(i, j, j ′ )|i ∈ U ∧ j ∈ I + i ∧ j ′ ∈ I - i }.

Distilling GCN into Binarized Collaborative Filtering

In this model, we distill the ranking information in GCN-CF model and transfer it to a simple binary collaborative filtering model via a mixed objective function. The model is denoted by DGCN-BinCF for short. The key motivation of the distillation in DGCN-BinCF is two-fold. On one hand, we consider the distribution of positive (negative) samples in the binary model should be close to that in the GCN-CF. On the other hand, the differences between positive and negative samples should become far enough in DGCN-BinCF. However, because the BPR model can guarantee that positive samples have higher scores than negative samples', negative samples are assigned much lower probability than positive samples' if we consider the distribution of both positive and negative samples at the same time. Thus, we consider positive and negative samples in GCN-CF separately.

Specifically, to distill the ranking information in GCN-CF, we hope the positive (negative) items of one user have the approximately same order in binary model and continuous model. For instance, if user u's preference for the three items i, j, k is ranked as [i, j, k] in GCN-CF model, we hope that the rank keeps [i, j, k] in the binary model. According to ListNet [Cao et al., 2007], we can characterize sorting information in the following ways

where D+ = {(i, j)|i ∈ U ∧ j ∈ I + i }, D- = {(i, j ′ )|i ∈ U ∧j ′ ∈ I - i } and T is the temperature parameter. In Eqn.15, we convert the items' score list to probability distributions via softmax function, and utilize cross entropy for penalizing the discrepancy. According to [Hinton et al., 2015], combining LBin-CF with Lrank as a multi-task learing problem can transfer the ranking knowledge to the binary model. It's worth mentioning that since the magnitudes of the gradients produced by the Lrank scale as 1/T 2 , it is necessary to multiply them by T 2 when mixing Lrank and LBin-CF . So the loss function of DGCN-BinCF is formulated as

Algorithm 1: DGCN-BinCF Algorithm

Input: Bipartite graph:G;dimension of latent factor in GCN-CF:D;dimension of latent factor in DGCN-BinCF:d = 3D;Laplacian

• matrix:L;temperature:T, τ ;coefficient:λ, α, η, ν 1 Initialize GCN-CF model;

2 repeat

• 3 Randomly sampling from unobserved items to generate training set D;
• 4 Forward propagation according to Eqn.8 ∼ 11;
• 5 Concatenate U and V via Eqn.12 and 13;
• 6 Update parameters of GCN-CF model by Adam optimization;
• 7 until Convergence;
• 8 Initialize DGCN-BinCF model;

9 repeat

• 10 Randomly sampling from unobserved items to generate training set D;
• 11 Forward propagation according to Eqn.18;
• 12 Update parameters of DGCN-BinCF model by Adam optimization;
• 13 until Convergence;

LDGCN-BinCF is denoted as L(P,Q;U, V, α, T) for short. P and Q are user and item embedding matrices in DGCNBinCF respectively, and U, V are trained user and item embedding matrices of GCN-CF. The loss Lrank encodes the first motivation and the loss LBin-CF encodes the second motivation.

For the binary optimization problem, it is a direct method to use tanh(x/t) to approximate sign function, where t is a small temperature. But [Li et al., 2018b] points that setting a small temperature will harm the optimization process. [Courbariaux et al., 2015] mentions that generating binary codes stochastically is a finer and more correct averaging process than generating binary codes via sign function. Hence, we generate binary codes via sampling from the Bernoulli distribution. More specifically, given x ∈ (-1, 1)d , its corresponding binary code is ˜x = x + ε, where ε is a random variable which only can be 1 - x and -1 - x, and P (εi = 1 - xi) = sigmoid(xi/τ ), P (εi = -1-xi) = 1-sigmoid(xi/τ ). Here, τ is temperature parameter. To force the noise to be small, we add the expectation of noise as a penalty term. Therefore, the DGCN-BinCF can be transformed into the following optimization problem:

where (εP)ij ∼ Bernoulli(tanh(Pij)), (εQ)ij ∼ Bernoulli(tanh(Qij )). We use the tanh function to bound the value of P, Q between -1 and 1.

According to Lemma 1, Eqn 17 can be rewritten as

Here we adopt g(pi ) = |||pi | - 1||22 which can be validated satisfying the conditions as the penalty term. Eqn.18 can be optimized by any gradient-based optimization methods directly. The whole training processing is summarized in Algorithm1.

5 Experiments

In this section, we evaluate our proposed DGCN-BinCF framework with the aim of answering the following research questions.

1. Does the recommendation performance of the proposed DGCN-BinCF framework outperforms the state-of-theart hashing-based recommendation methods?
2. Whether our proposed GCN-CF is effective?
3. Whether distilling ranking information helps learning binary model?
4. Whether this proposed framework can converge well?

We introduce the experimental settings firstly and then answer the above questions in following sections.

5.1 Experiment Settings

Dataset

We use three public real datasets including MovieLens1M, MovieLens10M and Yelp to evaluate the proposed algorithm. Because the three datasets are explicit feedback data, to convert them into implicit feedback data, we set all ratings as positive samples. In addition, due to the extreme sparsity of them, we then filter users who have less than 20 ratings and remove items that are rated by less than 20 users. Table 1 summaries the filtered datasets. For each user, we sampled randomly 50% positive samples as training and the remaining as test. We repeated five random splits and reported the averaged results.

Comparison Methods

To evaluate the performance of DGCN-BinCF for hashingbased recommender systems, we compare DGCN-BinCF with 3 very popular and state-of-art methods: DCF, BCCF and PPH. DCF solves the binary optimization problem directly via bit-wise optimization. BCCF and PPH are twostage methods.

To measure the effectiveness of the improved GCN model, we compare GCN-CF with SpectralCF. And we compare DGCN-BinCF with the binary model LBin-CF . To show the role of KD loss in binary optimization, LBin-CF is optimized by our proposed relaxation method as well.

Evaluation Metric

To evaluate the recommendation system performance, we choose four widely used ranking-based metric: (1) NDCG (Normalized Discounted Cumulative Gain), (2) Recall, , and (3) MAP (Mean Average Precision). We predicted the top-K preferred items from test set for each user in our experiments.

Parameter Settings

In our experiments, we set the regularization coefficient λ = 0.001 in GCN-CF in all dataset. For DGCN-BinCF, we set temperature T = 1, τ = 0.2, the weight α = 10, and the penalty coefficients β = 0.001, ν = 0.001 in the three datasets. In addition, we set the dimension of users and items' latent factor of GCN-CF 16 in MovieLens10M and 64 in the other two datasets. The learned matrices U ,V in GCN-CF are used as the initialization of P ,Q in DGCN-BinCF. All parameters of SpectralCF are set according to [Zheng et al., 2018].

Besides, for DCF, BCCF and PPH, we held-out evaluation means on splits of training data randomly to tune the optimal hyper-parmenters via grid search. α and β in DCF are tuned among the set {1e-4, 1e-3, · · · , 1e1}. λ in BCCF is tuned among the set {0.01, 0.03, · · · , 0.09} and λ in PPH is tuned among the set {0.01, 0.5, 1, 2, 4, 8, 16}.

5.2 Comparison with Baselines

Although hashing-based recommendation has significant advantages of both time and storage, it often incurs low accuracy recommendation because binary codes have limited representation ability and lose a lot of information compared with real-valued recommender systems. DGCN-BinCF is to improve the accuracy of recommendation.

In this part we will answer the first question. We compare the recommendation accuracy of DGCN-BinCF with three state-of-art binary recommendation methods including DCF, BCCF and PPH on the three datasets. Table 2, Table 3 and Table 4 summary the results.

The three tables show that DGCN-BinCF has much better performance than all baselines on the three datasets. This is because we train the improved GCN model GCN-CF firstly to discover the deep interactions between users and items and then transfer the ranking information to a binary model, DGCN-BinCF loses less information than baseline models. In addition, the binary optimization problem is optimized directly by the proposed penalty terms, which leads to less quantization loss. Therefore, DGCN-BinCF has great advantages over DCF, BCCF and PPH.

5.3 The Effectiveness of GCN-CF

It is mentioned that SpectralCF did not consider aggregating users and items' own high-order feature, which may limit its representation ability. In this part, we will answer the second question.

We implement the experiment in MovieLens1M dataset. We utilize three metrics to evaluate the performance of SpectralCF and GCN-CF respectively. Figure 1 shows the results. In two histograms, the orange column is the performance of GCN-CF and the blue one represents the results of SpectralCF. From the histograms, it is clear to observe that GCN-CF has great improvement (over 20%) for every metric compared with SpectralCF, which shows the effectiveness of GCN-CF.

5.4 The Effectiveness of Distillation

Because lots of useful information loses during learning the binary representation, it is vital to utilize the ranking information from the trained GCN-CF model as supplements for learning discrete codes. In this part, we investigate the role of ranking information for binary optimization. To implement the experiment, we consider optimizing Eqn.1 directly by adding the proposed penalty term. In the other word, we set α = 0 in LDGCN-BinCF , and compare its results with DGCN-BinCF. We test the two methods in the MovieLens1M dataset and evaluate them via the four ranking metrics.

Figure 2 reports the comparison results. The blue bar represents BinCF and the orange bar means DGCN-BinCF model. The two histograms show that for all evaluation indicators, DGCN-BinCF outperforms BinCF by 10%. Thus we conclude that the distillation method helps the model learn high quality binary representation.

5.5 Convergence

In this section, we will answer the forth question. Because deep models and discrete optimization may diverge, we test the convergence of GCN-CF and DGCN-BinCF model.

To test the convergence of our proposed model GCN-CF and DGCN-BinCF, we implement the experiment on MovieLens1M. We record the value of Eqn.14 and Eqn.18 with the change of epoch respectively. In this experiment, we set the maximum number of iterations 200. Figure 3 shows the convergence of two models. It is observed that loss value of GCN-CF decreases and the DGCN-BinCF converges greatly.

6 Conclusion

In this paper, we propose a hash-based method DGCN-BinCF to accelerate implicit feedback recommendation. Because implicit feedback lacks negative samples and learning binary codes loses a lot of information, we train the model GCN-CF, which aggregates users' and items' own high-order feature, to mine rich connection information, and then distill the ranking information from GCN-CF into the binary model. In addition, we propose a method utilizing penalty terms to learning binary codes based on gradient descent directly. The experiments on three real-world datasets show the great superiority of our framework.

Acknowledgements

The work was supported in part by grants from the National Natural Science Foundation of China (Grant No. U1605251, 61832017, 61631005 and 61502077).