HCFRec: Hash Collaborative Filtering via Normalized Flow with Structural Consensus for Efficient Recommendation

1 Introduction

Recommender System (RS) has recently become a crucial tool to alleviate information overload in many areas with rich data, including but not limited to e-commerce, education, finance, and health [Zhu et al., 2021]. As a pivotal technology of RS, Collaborative Filtering (CF) has received thrilling success owing to its inherent domain-independent and easy-toexplain properties. Specifically, CF attempts to learn representations of users and items from their interactive information for the subsequent user preference prediction and item recommendation[Chen et al., 2022]. However, with the explosive growth of users and items, CF based recommendation methods often suffer from high time and space costs [Qi et al., 2021a].

∗Corresponding author

Fortunately, hash-based CF (Hash-CF) approaches [Chen et al., 2018] have been proven to have a good ability to compress data and accelerate computation for recommendations with billion-scale users and items [Shan et al., 2018]. In large-scale recommendation scenarios, Hash-CF takes effect by encoding high dimensional real-valued vectors into compact one-hot codes (hash representations), such that: (1) bitwise operations (e.g., XOR) instead of real-valued calculations for preference inference can dramatically accelerate recommendations; (2) bit-wise representations often achieve a 64× storage compression rate compared to real-valued representations. Therefore, Hash-CF enables a lighter and more efficient recommendation model even massive data are involved in decision-makings.

However, existing Hash-CF approaches often face two challenges existing in the learned hash representations. Firstly, CH1: how to implement optimization on discrete hash representations? The hash representation is usually obtained through the sign function, and optimizing such a representation will lead to a challenging mixed-binary-integer optimization problem [Wang et al., 2018], which is NP-hard. A promising solution is to replace the sign function with a continuous relaxation (e.g., tanh function) to learn deterministic hash representations in an end-to-end manner, which, however, is not robust due to a lack of noise tolerance consideration. Fortunately, Variational Autoencoder (VAE) [Kingma and Welling, 2014] with its probabilistic nature can model features as distributions to accommodate much uncertainty or noisy in data, so as to implement robust recommendation [Liang et al., 2018]. However, for the Hash-CF task, features need to be modeled as latent discrete Bernoulli distributions to generate hash representations. Such distributions with discrete nature make the optimization on hash representations more difficult. Secondly, CH2: how to preserve semantic information in discrete representations?A hash representation has intrinsically limited representation ability, as it carries less semantic information than a real-valued representation. Although the existing Hash-CF approaches [Zhang et al., 2016] try to control quantization loss to reduce the difference between real-valued and hash representations, they fail to preserve the semantic structure consistency between them. The two representations without structural consensus drop much semantic information that is crucial to accurate recommendations.

In light of the above two challenges, we propose a novel Hash-CF recommendation approach, i.e., HCFRec, which generates compact yet informative hash representations for effective and efficient recommendations. The proposal is comprised of two major components based on VAE framework for robust generalization capability. Specifically, for CH1, hash representation generation component first models user (item) features as user (item) real-valued representations that obey a simple prior normal distribution. Considering the difficulty in optimizing a discrete distribution, we innovatively propose an approximate mixture multivariate normal distribution, a continuous but approximately discrete distribution, and introduce normalized flow [Rezende and Mohamed, 2015] to deploy reversible transformation functions from the simple normal distribution to the complex and approximately discrete distribution. Normalized flow can efficiently implement reversible distribution transformation from a simple continuous distribution to any complex continuous distribution with same dimensions. To our best knowledge, this is the first attempt to introduce normalized flow for binary optimization. Finally, hash representations are generated by binarization operations. For CH2, cluster consistency preserving component first respectively clusters the real-valued representations and the hash distribution both generated in the first component. Subsequently, a loss function is designed for the two representations to alternately learn semantic information with structural consensus.

We summarize our main contributions as follows: (1) We propose a novel Hash-CF approach implemented on a variational framework for effective and efficient recommendation. (2) Normalized flow is first introduced to learn the optimal hash codes by efficiently fitting our proposed approximate mixture multivariate normal distribution, which makes it possible for efficient optimization on discrete distribution. (3) We innovatively develop a cluster structure preserving mechanism to retain cluster consensus between real-valued and hash representations for more accurate recommendations. (4) Extensive experiments conducted on six real-world datasets demonstrate the superiority of our HCFRec approaches over state-of-the-art competitive ones.

2 RelatedWork

2.1 Hash-CFMethods

Due to the intrinsic characteristics of high efficiency and low storage cost, Hash-CF has recently gained ever-increasing attentions of researchers, including two kinds of approaches. First, the "two-stage" approaches learn hash representations through a continuous representation learning stage followed by a binary quantization stage [Karatzoglou et al., 2010; Zhang et al., 2014; Zhang et al., 2017b], which, however, produces considerable quantization errors. Second, the "endto-end" approaches try to optimize hash representations directly. Some researchers model user and item features as deterministic representations [Zhang et al., 2016][Zhang et al., 2017a][Liu et al., 2019]. However, these approaches lack noise tolerance. For more generalization, some researchers recruit probability-based VAE to model user/item features as discrete Bernoulli distributions [Hansen et al., 2020]. However, discrete latent space makes it challenging for hash codes to be optimized effectively and efficiently.

2.2 VAE-based CFMethods

VAE has recently achieved strong performance improvements on CF [Liang et al., 2018]. VAE's strong generative ability even in sparse settings is mainly because it can model representations as a distribution rather than a deterministic vector to account for much uncertainty in the latent space. [Lee et al., 2017] incorporates auxiliary information into VAE for CF. [Karamanolakis et al., 2018] also takes side information into account, which learns user representations in multimodal latent space for better recommendation. RecVAE [Karamanolakis et al., 2018] introduces some regularization techniques into VAE to improve recommendation performance. However, despite remarkable improvements are achieve in these works, they only learn user representations but ignore valuable item information. In this situation, [Truong et al., 2021] models a Bilateral VAE framework to learn both user and item representations for more robust recommendation.

3 Methodology

The data we intend to learn from is a user-item interaction matrix R ∈ RNU×NV , where NU and NV denote the number of users and items, respectively. The i-th row of R is formulated as ri,∗ ∈ RNV while the j-th column of R is formulated as r∗,j ∈ RNU , representing user feature and item feature, respectively. Moreover, EU and EV are respectively user encoder and item encoder, bU ∈ {-1, 1}D and bV ∈ {-1, 1}D respectively indicate user hash representations and item hash representations. The main problem we need to solve is: Given ri,∗ and r∗,j from matrix R, a model is needed to learn hash representations bU and bV for effective and efficient recommendations.

3.1 Overview of HCFRec

Our HCFRec model is mainly based on a dual VAE framework comprised of hash representation generation component and cluster consistency preserving component, as illustrated in Figure 1. Details of each component are as follows:

(1) Hash Representation Generation Component. Due to the close correlation with the VAE framework, this component is embedded into the VAE for introduction here. Concretely, we first employ VAE framework to model user (item) features as real-valued representations that obey prior normal distribution. Normalized flow is subsequently deployed to achieve pre-hash representation that obeys a continuous but approximately discrete distribution. Finally, sign function on this distribution is recruited to output hash representations.

(2) Cluster Consistency Preserving Component. We cluster the embedded real-valued representations and the generated hash representations, and alternately learn clusterconsistent semantic information from each other to ensure the semantic structure restoration ability of hash representations. Finally, HCFRec uses the enhanced hash representations for recommendations.

3.2 Hash Representation Generation Component

Modelling. For a recommendation task, the objective we seek to maximize is the likelihood of a rating, i.e., p(ri,j). Formally, we determine the likelihood p(ri,j) in Eq.(1) by introducing binary latent representations bU and bV as conditions.

However, such maximization is intractable, thus we need to introduce variational inference [Jordan et al., 1999]. Variational inference devotes to approximate both posteriors qφ(bUi |ri,∗) and qψ(bVj |r∗,j) to surrogate the true intractable posterior p(bUi |ri,∗) and p(bVj |r∗,j), where φ and ψ are parameters on neural networks respectively for user and item. Formally, variational inference in this work seeks to simultaneously minimize the KL divergence KL(qφ(bUi |ri,∗)‖p(bUi |ri,∗) and KL(qψ(bVj |r∗,j‖p(bVj |r∗,j) to achieve the optimal φ and ψ. During the learning process with the above variational inference, an Evidence Lower BOund can be drawn in Eq.(2). Therefore, we can use ELBO maximization as a proxy to indirectly maximize the log-likelihood function.

where the first term in ELBO indicates the reconstruction error that measures the likelihood of reconstructing the observed rating data, the two KL terms are regularizers that constrain the form of the two approximate posteriors.

Calculation. In this part, user side and item side are treated symmetrically. Due to the limited space, this part only takes user side as a specific example for illustration. Firstly, we adopt EU to generate user mean and variance as [µUi , (σU i )2 ] = EU(ri∗). Then we adopt the reparametric method to obtain the user real-valued representation as zU i,0 = µUi + ϵUi σU i where zU i,0 is a D-dimensional vector.

In order to enhance the model generalization, we align the real-valued latent space to the standard normal distribution N(0, I) with the KL-divergence constraint as:

After that we adopt the normalized flow to generate the zU i,T through several layers with probability estimation as:

where zU i,t + uUt χ ((wU t )⊤zU i,t +aUt ) = zU i,t+1 ∈ RD and χ(·) denotes the sigmoid activation function. uUt , wU t andaUt are the trainable network parameters at the t-th layer. Here, it is worth noting that the reversible distribution transformation in Eq.(4) is only deployed on the d-th dimension of the entire D-dimensional representation. Finally, we adopt sign(·) to achieve the user hash representation as:

Meanwhile we prefer that the latent hash representation conforms to the Bernoulli distribution as p(bi|d = 1) = p(bi|d = -1) = 12 on the d-th dimension. However, the Bernoulli distribution is discrete which makes it much more difficult to be optimized. Therefore, we first innovatively propose the approximate mixture multivariate normal distribution represented as:

where Σ(bi|d) = γI denotes the covariance matrix of corresponding normal distribution. Here, γ is set to 0.015 in our experiments. Therefore, we define the loss function corresponding to the KL term in Eq. (2) as:

Here, since p(bUi ) is approximately surrogated by an approximate mixture multivariate normal distribution in Eq.(6), the KL term is also be approximated in Eq.(7).

Next, we infer the reconstruction loss corresponding to the likelihood Lrecon = -p(ri,j|bUi , bVj ) in Eq.(2). In this paper, we assume that the observed rating data obey the Poission distribution, such that:

where sB(bUi , bVj ) = (bUi )T bVj +K 2K Considering the equivalence of inner product and Hamming distance, hash representations can be optimized directly by optimizing Eq.(8).

Finally, fusing both user side and item side information, the loss function for the optimal hash representations can be defined as:

It is worth noting that, in Eq.(5), bUi (bVj ) is achieved by sign(·), a non-smooth function that makes the gradient of all inputs to zero during backward propagation. Thus, we adopt an identify function f(·) to surrogate sign(·), such that f(·) achieves unit gradient in the backward pass.

3.3 Cluster Consistency Preserving Component

To further enhance the quality of both real-valued representations and hash representations, we push them to reach structural consensus. In other words, neighbors generated by realvalued representations and hash representations are expected to be same, such that semantic cluster structure [Liu et al., 2021] can be preserved.

Neighbor Aggregation. In this part, since user side and item side can work in the same way, thus, for concise illustration, we employ user side as a specific example for illustration. Firstly, we aggregate neighbors into different clusters respectively with real-valued representations and hash representations. Due to the characteristics of data independence and time-efficiency, Locality Sensitivity Hashing (LSH) has been proven a powerful approach for approximate nearest neighbor (ANN) search [Qi et al., 2021b]. Thus, we resort to LSH for neighbor aggregation. Concretely, since the intrinsic continuity of real-valued representations and the discreteness of hash representations, the hash functions of the two representations are respectively for Euclidean distance and Hamming distance. Formally, for the real-valued side, we recruit hash functions as:

where a ∼ N(0, I) is a K-dimentional random vector, c ∼ U(0, w) is a random real value, and w ∈ R+ is a hyperparameter. Since LSH is a probability-based approach, we perform the above hash process L rounds to ensure credibility. Then, the final hash value can be calculated by:

where B is a constant, and h(l) i is the hash function employed in round l with independently sampled random variables a and c. Then, users with the same hash values will be projected into an identical bucket. We regard neighbors in the same bucket as a cluster. From the obtained cluster structure, we can obtain the similarity matrix A ∈ {1, 0}NU×NU corresponding to real-valued latent representations as:

where 1 indicates "similar", 0 indicates not. Likewise, for hash representations, we perform the hash functions for Hamming distance L rounds and calculate the final hash values by Eq.(13).

where h′ (l) i denotes hash functions, H′ i (bUi ) denotes final hash values, b(d) i indicates the binary value of the d-th dimension in D-dimensional hash representation bi. Users (items) with the same hash values are projected into an identical bucket and regarded as a cluster. With the obtained cluster structure, the similarity matrix A′ ∈ {1, 0}NU×NU corresponding to hash representations can also be obtained.

Consistency Learning. Till now, joining both user side and item side, the optimization objective of cluster consistency can be defined by:

where, for the user side, the first term indicates that similar users' hash representations require smaller Euclidean distances for users' real-valued representations, while the second term indicates that similar users' real-valued representations require smaller Hamming distances for users' hash representations, which is likewise for the item side.

3.4 Combined Loss Function

Next, we put the two components together and get a fused loss function of HCFRec defined as:

where λ is a hyper-parameter that balances the loss of two components, Lrating is the loss of the first component obtained in Eq.(9), and Lcons is the loss of the second component obtained in Eq.(14).

4 Experiments and Evaluation

We conduct extensive experiments to answer the following questions: Q1: How does HCFRec compare with the stateof-art approaches in terms of recommendation accuracy (see subsection 4.3)? Q2: How does Hamming distance outperform real-valued inner product in terms of computational efficiency and storage costs (see subsection 4.4)? Q3: How does HCFRec perform on parameter sensitivity (see subsection 4.5)?

4.1 Data Preparation

We adopt two well-known datasets, MovieLens 1 and Amazon 2 for experimental evaluations: (1) MovieLens collects user ratings for movies, ranging from 1 (worst) to 5 (best). We evaluate recommendation performance in terms of different data scale, i.e., ML-100K, ML-1M, ML-10M. (2) Amazon [He and McAuley, 2016] covers ratings (with the range of 1 to 5) for up to 24 product categories. We evaluate recommendation performance on its 3 product categories, i.e., Clothing, Shoes and Jewelry, Office Products, and Toys and Games.

We preprocess the data following [Hansen et al., 2020] and [Lian et al., 2017] to filter users and items with less than 20 ratings. Moreover, only the last rating is reserved if a user has rated an itemmultiple times. We sort the ratings in ascending order according to the feedback time, and divide all datasets into training set, validation set, and test set according to 5:2:3. We summarize the dataset information with Table 1.

4.2 Experimental Settings

Comparison Methods. Five baselines classified into two groups and two versions of our proposed approaches, i.e., HCFRec/no.C and HCFRec, are compared in our experiments, where HCFRec/no.C is the version of HCFRec without cluster consistency preserving component.

(1) Classical real-valued CF approaches: BPR: A classical recommendation framework maximizing posterior estimator to create a personalized ranking list for a group of items [Rendle et al., 2009]. BiVAE: A state-of-the-art bilateral VAE that learns user real-valued representations and item real-valued representations for CF [Truong et al., 2021] 3 .

(2) Hash-CF approaches: DCF: An explicit feedbackbased Hash-CF method that learns balanced and uncorrelated hash codes for recommendation task [Zhang et al., 2016] 4 . DPR: A Hash-CF method tha learns hash codes based on personalized ranking objective instead of rating prediction objective in DCF [Zhang et al., 2017a] 5 . BiVAEB: A version directly binarizing the real-valued representations in BiVAE for recommendation task, which is a baseline indicating the quantization loss from real values to binary representations.

Evaluation Metrics. We focus on the item positions in recommendation lists to evaluate the accuracy of the above competitive methods. In concrete, we adopt the following two metrics: mean Average Precision (mAP) and normalized Discounted Cumulatiive Gain (nDCG).

1 https://grouplens.org/datasets/movielens

2 http://jmcauley.ucsd.edu/data/amazon/

3 https://github.com/PreferredAI/bi-vae

4 https://github.com/hanwangzhang/Discrete-CollaborativeFiltering

Parameter Setting. We conduct our experiments on an NVIDIA RTX 3090 GPU by PyTorch. We adopt Adam optimizer with learning rate 0.015 for training. Moreover, the mini-batch SGD with the fixed batch size 128 is employed for optimization. As the introduced hyper-parameters in our model, we set γ in Eq. (6) as 0.015 and λ = 0.3 in Eq.(15). Following [Zheng et al., 2020], we set ω = 8 in Eq.(10) and B = 4 in Eq(11). Moreover, we set L = 1 in both Eq (11) and Eq (13), because multiple rounds of training have replaced L to make the obtained hash values confident.

4.3 Performance Comparison (for Q1)

We report the recommendation accuracy in terms of nDCG and mAP respectively in Table 2 and Table 3. Moreover, we evaluate the performance on all methods with both 16dimensional and 64-bit representations. To illustrate the performance intuitively, we boldly mark the best performance among all Hash-CF methods in each column.

As Table 2 and Table 3 show, HCFRec achieves superior performance over other Hash-CF baselines with improvements of at least 7.18% in terms of nDCG and at leat 20.75% in terms of mAP. Moreover, on Amazon-Clothing and Amazon-Toys datasets (two extremely sparse settings), HCFRec also achieves higher robustness of recommendations over other Hash-CF baselines, which demonstrates a better generalization ability of VAE framework. Furthermore, considering the performance gap between HCFRec/no.C and HCFRec, we find that semantic information takes effect for more informative hash codes.

In addition to Hash-CF approaches, the state-of-the-art real-valued CF (BPR and BiVAE) are also employed for experimental evaluation. As expected, the two real-valued CF methods perform better on all datasets since they leverage more informative representations than Hash-CF methods. However, we can observe that the performance gap becomes smaller when dimension increases. This is because even in low-dimensional scenarios, real-valued CF can still collect rich information for recommendations. In this situation, higher dimensions often bring a limited performance improvement. As a contrast, more dimensions of hash code often result in a higher ability of information representation for better recommendation performances.

4.4 Efficiency and Storage (for Q2)

(b) storage cost

Figure 2: Comparisons of real-valued representations and hash representations in terms of efficiency and storage.

Recall that one of the major motivations of our proposal is to recruit hash representation for more efficient computation and lighter storage. In this subsection, we respectively investigate computational efficiency and storage cost as follows.

Computational Efficiency. We fix the user size to 100,000 and change the item size NV from 100 to 200,000. The 64dimensional representations of real-value and hash codes are randomly generated. The evaluation results are illustrated in Figure 2(a): computational time of real-valued representations grows exponentially as item scale increases; as a contrast, the time cost of hash representations achieves a speedup factor of 40-50. This observation demonstrates the efficiency benefit of Hash-CF for large-scale recommendation.

Storage Costs. We compare the storage costs in Figure 2(b) with item sizes from 1 million to 1 billion. As expected, storing real-valued representations consumes more space than hash codes. This is because one dimension of real-valued representation often needs 64 bits, while one dimension of hash code needs only 1 bit. This fact highlights the space thrift of Hash-CF for large-scale recommendation.

4.5 Parameter Sensitivity (for Q3)

We investigate the recommendation performances influenced by hyper-parameters γ and λ in Figure 3, during which the 64-dimensional hash representations are adopted and the top-10 items are returned for evaluation nDCG performance on the two sparsest datasets, i.e., Amazon-Clothing and Amazon-Toys. With fixed λ = 0.3, we vary γ from 0.010 to 0.030. Figure 3(a) shows that our model achieves the best performance when γ = 0.015. This is because a continuous distribution extremely close to a discrete distribution (with γ smaller than 0.015) is too complex to learn. As a contrast, the much smoother distribution (with γ larger than 0.015) leads to more quantization errors in the latter quantization step, so as to dampen the recommendation performance. Furthermore, we fix γ = 0.015 and evaluate nDCG@10 with λ verying from 0.01 to 0.5. Figure 3(b) shows that the performances are not sensitive to λ. Therefore, we set γ = 0.015 and λ = 0.3.

5 Conclusion

In the big data environment, Hash-CF has been proven a promising technique to accelerate recommendation efficiency by learning an optimal hash representation. However, traditional Hash-CF often falls short in the optimization on discrete hash representations and the preservation of semantic information. To tackle these issues, we introduce normalized flow to learn the optimal hash code and deploy a cluster consistency preserving mechanism to preserve the semantic structure in representations. Extensive experiments conducted on six real-world datasets reveal the superiority of our proposal in terms of accuracy and efficiency.

Acknowledgments

This work was supported in part by the National Key R&D Program of China (No.2018YFB1403001), the National Natural Science Foundation of China (No.62172362 and No.72192823) and Leading Expert of "Ten Thousands Talent Program" of Zhejiang Province (No.2021R52001).