Quaternion Collaborative Filtering for Recommendation

1 Introduction

With the significant rise in the amount of information and number of users on the internet, it is becoming important for companies to provide personalized recommendations. As such, recommendation engine becomes an indispensable component to modern e-commerce. To this end, an effective recommendation model can not only significantly boost revenues, but also improve the overall user experience by ameliorating the prevalent and intrinsic problem of over-choice.

Learning a matching function between user and item lives at the heart of modern methods for recommender systems research. More concretely, factorization-based methods [Koren, 2008; He et al., 2017], metric learning methods [Hsieh et al., 2017; Tay et al., 2018a] and/or neural network models [Zhang et al., 2017a; He et al., 2017] have all recently demonstrated good progress and performance on the task at hand. All in all, joint representation learning techniques forms the crux of this paradigm and investigating novel methods for this purpose remains highly interesting and relevant.

∗Contact Author

A key observation is that most work in this area has been primarily focused on real-valued representations R, ignoring the rich potential of alternative spaces such as complex C and/or hypercomplex spaces H. This work investigates the notion of complex algebra and quaternion algebra which are well-developed in the area of mathematics. The intuition is clear. Complex and hypercomplex representation learning methods are not only concerned with expanding the vector space (i.e., merely composing multiple spaces together) but have tight links with associative retrieval, asymmetry and learning latent inter-dependencies between components via multiplication of complex numbers and/or Hamilton products. The associative nature of complex representations going beyond multi-view representations is well-established in the literature [Hayashi and Shimbo, 2017; Danihelka et al., 2016]. Moreover, the asymmetry of simple inner products in hypercomplex space [Trouillon et al., 2016; Tay et al., 2018b] provides a strong inductive bias for reflecting the asymmetrical problem of user-itemmatching, i.e., user and item embeddings fundamentally belong to a separate class of entities.

To this end, Quaternion representations are hypercomplex numbers with three imaginary numbers. There have been recent surge in interest, showing promise in real world applications such as signal processing [Witten and Shragge, 2006], image processing [Parcollet et al., 2018a], and speech recognition [Parcollet et al., 2018b; Trabelsi et al., 2017]. This is in similar spirit to multi-view representations, although the latent components are connected via the complex-number system. Moreover, the Hamilton product encodes interactions between imaginary and real components, enabling an expressive blend of components that forms the final representation. Given the interaction function lies fundamental to recommender system research, it is intuitive that Hamilton products are suitable choices for user-item representation learning.

Our Contributions Overall, the prime contributions of this paper can be summarized as follows:

• We propose recommender systems in non-real spaces, leveraging rich and expressive complex number multiplication and Hamilton products to compose user-item pairs. Our proposed approaches, Complex collaborative filtering and Quaternion collaborative filtering (QCF), opens up a new distinct direction for collaborativebased/neural recommendation in non-real spaces.

• We conduct extensive experiments on a wide range of large diverse real-world datasets. Our results demonstrate that QCF achieves state-of-the-art performance.
• We thoroughly investigate and control for parameters, demonstrating that the power of QCF lies not in its expanded representation capability but its expressiveness. When controlling for parameters, QCF outperforms MF significantly. Ablative experiments that control for latent dimensions prove the efficacy of our approach.

2 RelatedWork

In this section, we identify and review former studies that are relevant to our work.

Firstly, our work is concerned with collaborative filtering, in which matrix factorization [Koren et al., 2009] remains a competitive baseline. A wide spectrum of variants have been proposed based on it. For example, timeSVD++ [Koren, 2008] takes temporal dynamics and implicit feedback into account and achieves good performance on rating prediction. BPR [Rendle et al., 2009] is a pairwise learning personalized ranking method with matrix factorization. [He et al., 2016] proposed an efficient matrix factorization based recommendation model with a non-uniform weight strategy, just to name a few. Recent years have witnessed a shift from traditional collaborative filtering to neural networks approaches, with exponentially increase in the amount of publications on this topic [Zhang et al., 2017a]. The achievements are inspiring and enlightening. Many of the well-established neural networks can be applied to recommender systems. For instance, We can add nonlinear transformations into collaborative filtering with multilayer perceptron [Dziugaite and Roy, 2015; He et al., 2017], use autoencoder or convolutional neural networks to learn richer feature representations from user/item auxiliary information (e.g., profiles, images, video abstract, reviews, etc.) [Sedhain et al., 2015; Van den Oord et al., 2013; Chen et al., 2017], and utilize recurrent neural networks to model the sequential patterns in user behaviours to make session-aware recommendation [Hidasi et al., 2015; Wu et al., 2017].

Secondly, our work is inspired by the widespread success of complex and Quaternion number across a myriad of domains. [Trabelsi et al., 2017] devised some atomic components for complex-valued deep neural networks and built a complex-valued convolutional neural network for several computer vision and speech processing tasks. [Gaudet and Maida, 2018; Parcollet et al., ] proposed the building blocks for Quaternion convolution and tested it on image classification tasks. [Parcollet et al., 2019] generalized Quaternion into recurrent neural networks and showed better performances than RNN/LSTM on a realistic application of automatic speech recognition. In addition, Quaternion MLP [Parcollet et al., 2016] also achieved promising results on spoken language understanding. Former studies suggest that complex and Quaternion have a richer representational capacity, and enjoy higher flexibility/generalization than real-valued based methods.

3 Preliminaries

In this section, we give a brief introduction to complex and Quaternion algebra which lie at the centre of the proposed method.

3.1 Complex Algebra

A complex number is a number that can be written as a + bi, where i is the imaginary unit, and a and b are the real numbers. The backbone of the complex algebra is the imaginary unit which is the solution of x2 = -1.

The multiplication of complex number follows the general rule that each part of the first complex number gets multiplied by each part of the second complex number. Thus we have:

The multiplication of complex number occurs in a twodimensional space and obeys the commutative law and the result is still a complex number.

3.2 Quaternion Algebra

Quaternion is an extension of complex number that operates on four-dimensional space. It consists of one real part and three imaginary parts. In this work, we mainly focus on the Hamilton's Quaternion which is defined as:

where a is the real component and i, j, and k satisfy the relations:

Such a definition can be used to describe spatial rotations.

The Hamilton product of two Quaternions is determined by the products of the basis elements and the distributive law. Suppose that we have two Quaternions H1 = a1 + b1i + c1j +d1k and H2 = a2 + b2i + c2j +d2k, the Hamilton product of them is defined as follows:

Multiplication of Quaternions is associative and distributes over vector addition, but it is not commutative.

4 The Proposed Approach

In this section, we propose applying complex and Quaternion number to recommendation models.

Suppose that we have N items and M users, user's preferences over items formulate a user-item interaction matrix Y ∈ RM×N . Our task is concerned with learning personalized ranking list with implicit interactions, e.g., click, like, check-in, watch, purchase, rate, etc. We set Yui to 1 if user u has interacted with item i and Yui = 0 indicates that the user dislikes or does not know the existence of item i. Let Y + denote the user-item set with Yui = 1 and Y - denote the set with Yui = 0. The aim is to fill in the missing values in the interaction matrix.

4.1 Collaborative Filtering with Complex Embedding

In classic matrix factorization [Koren et al., 2009], each user is represented by a latent vector of dimension d and each item is also allocated with a vector with the same dimension. In the complex number system, we embed users and items with complex vectors. Formally, we define each user with a complex vector Cu = Uu+Vui with Uu, Vu ∈ Rd . Similarly, each item is represented with a complex vector Ci = Pi +Qii with Pi,Qi ∈ Rd .

Different from traditional matrix factorization where dot product is usually used, we model the interaction between users and items with complex number multiplication, which gives the following expression:

where dot product "·" is used in order to get a scalar output but it will not change the multiplication rule. For simplicity, we define by the real part of the above expression with a and the imagery coefficient with b. Following [Parcollet et al., 2019], we apply split activation functions (specifically, sigmoid) to the above result and get:

We use split activation because it can lead to better stability and simpler computation [Parcollet et al., 2019; Gaudet and Maida, 2018].

4.2 Collaborative Filtering with Quaternion Embedding

Similar to complex number, we embed users and items with Quaternion representations. In formal, let Hu = Uu + Vui + Xuj + Yuk denote each user and Hi = Pi + Qii + Sij + Tik denote each item, where Uu, Vu, Xu, Yu, Pi, Qi, Si, Ti ∈ Rd . We model the user item relationship with the well-defined Hamilton product and obtain:

Note that dot product "·" is also used to get a scalar result. As can be seen, Hamilton product enables interactions between different components, thus, leading to more powerful modelling capability. Additionally, the noncommutative property also enables the recommender systems to model both symmetrical (when all imaginary parts are zero) and asymmetrical collaborative effects. Moreover, Hypercomplex spaces enable spatial transformations (and smooth rotations), as compared to real space products. This enables the model to be more numerically stable and expressive.

Similar to complex collaborative filtering, we use a, b, c, d to represent the real and imaginary components of expression (7). Split sigmoid activation function is also employed over the result. Thus, we have:

With complex or Quaternion embedding, we could not only model the internal interactions between user and item latent factors, but also external relations of different latent vectors. Intuitively, Quaternion Hamilton product is able to capture more intricate relations than complex number multiplication.

4.3 Model Learning and Inference

Following [Parcollet et al., 2019; Gaudet and Maida, 2018], we train our model with classic cross-entropy loss in a component-wise manner. Here, we give the loss function for complex collaborative filtering. Loss function of Quaternion collaborative filtering can be easily derived as follows.

Where Y + ∈ Y + and Y - is sampled from Y -. Negative sampling is conducted during each training epoch with controlled sampling ratio. Same as NeuMF, we solve the personalized ranking task with implicit feedback from the classification perspective. ℓ2 norm is used to regularize the model parameters. Note that pairwise Bayesian log loss [Rendle et al., 2009] is also viable for our model. Finally, the model can be optimized with standard gradient descent algorithms such as SGD or Adam optimizer [Ruder, 2016].

During the inference stage, we take the average of all the components as the final recommendation score. So the ranking score for complex collaborative filtering is:

Similarly, the ranking score of Quaternion collaborative filtering is the mean of one real and three imaginary coefficients (with sigmoid applied).

With the mean aggregation, our approach ensembles predictions from different parts and, as a result, could reduce biases and variations, leading to a more robust estimation.

To accelerate the convergence and training efficiency, we follow the parameter initialization principle of [Gaudet and Maida, 2018] which is tailored for Quaternions to initialize the proposed model.

4.4 Quaternion Neural Network?

Here, we give a brief discussion on Quaternion neural networks. Considering that our model follows the basic patterns (e.g., split activation function, component-wise loss, etc.) of Quaternion neural networks, it is easy to add some Quaternion feed-forward layers into our model [Gaudet and Maida, 2018; Parcollet et al., ]. In Quaternion neural networks, the weights are also represented with Quaternions and transformation is performed with Hamilton product. The model learning and inference procedure remain unchanged. Complex neural networks share the same pattern as Quaternion ones. We omit details on this topic but will discuss it in Section 5.

5 Experiments

In this section, we present our experimental setup and evaluation results. Our experiments are designed to answer the following research questions:

1. Does the proposed model outperform matrix factorization approach? How much is the improvement?
2. Can our model beat recent neural network based model?
3. How does the proposed model behave? For instance, where is the improvement from? What is the impact of hyper-parameters?

5.1 Dataset Description

We conduct evaluation across a wide spectrum of datasets with diverse domains and densities. A concise summary is shown in Table 1.

• Movielens HetRec. It is a widely used benchmark dataset for recommendation model evaluations provided by GroupLens research 1 . We use the version HetRec.
• LastFM. This dataset is collected from the last.fm online music system 2 . It contains music listening information of the website users.
• Foursquare. This is a location check-in dataset which records the digital footprints of users from the Foursquare application 3 .
• Amazon Datasets 4 . This repository contains Amazon product ratings for a variety of categories. Due to limited space, we adopted three subcategories including: video games, digital music and office products.

For all datasets, we converted all interactions into binary values and ensured that each user has at least five interactions since cold-start problem is usually investigated separately [Zhou et al., 2011].

5.2 Evaluation Setup andMetrics

To evaluate the performance of the proposed approach, we adopted hit ratio (HR) and normalized discounted cumulative gain (NDCG) with top k list. HR measures the accuracy of the recommendation model with definition HR@k = #Hit #Users . NDCG assesses the ranking quality of the recommendation list as, in practice, to make the items that interest target users rank higher will enhance the quality of recommendation lists. For each metric, we report the results with three different k value, namely, top-5, top-10 and top-20. We report the average scores of both evaluation metrics. The higher both metrics are, the better recommendation performance is.

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

2 http://www.last.fm

3 https://foursquare.com/

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

Following [He et al., 2017], we use the leave-one-out protocol to study the model behaviour. We hold out one interaction (the latest interaction if time-stamp is available) of each user as test and use the remaining data for training. During test step, we pair each test item with sampled 200 (negative) items that the user have not interacted with. Then, we rank those 201 items and report the evaluation results with the above metrics.

5.3 Baselines

To verify the performance of the proposed approach, we compare it with the following baselines.

• Generalized Matrix Factorization(GMF) [He et al., 2017]. It is a generalized version of matrix factorization and a special case of neural collaborative filtering framework. GMF learns its parameters by minimizing the cross-entropy loss.
• Multilayer Perceptron (MLP). It captures user and item relations with multilayered feedfoward networks. A three-layer MLP with pyramid structure is adopted.
• Joint Representation Learning (JRL) [Zhang et al., 2017b]. JRL passes the element-wise product of user and item latent vectors into a tower-structured multilayered perceptron.
• Neural Collaborative Filtering (NCF or NeuMF) [He et al., 2017]. NeuMF is an ensemble of MLP and GMF. MLP could help introduce non-linearity while GMF retains the advantages of matrix factorization. The whole framework is trained in an end-to-end manner with cross-entropy loss.

We denote by CCF the complex collaborative filtering and QCF the Quaternion collaborative filtering. Models such as ItemPOP and BPR are not further reported since they are outperformed by the above baselines [He et al., 2017].

5.4 Implementation Details

All the above baselines and the proposed approaches are implemented with Tensorflow 5 . We tested all models on a Titan Xp GPU. For fair comparison, pre-training is not used in the experiments. The regulariztion is tuned amongst {0.001, 0.005, 0.01, 0.05, 0.1}. The learning rate is selected from {0.001, 0.005, 0, 01, 0.05}. The activation function α is set to sigmoid function. We set latent vector dimension d to the same value for all models for fair comparison. The batch size is fixed to 256 in the experiment.

5.5 Experimental Results

The experimental results on six benchmark datasets are reported in Table 2. The relative improvement of CCF and QCF against the strongest baseline is also provided in the table.

5 https://www.tensorflow.org/

80

Several observations can be made from the results. Firstly, the proposed QCF outperforms all other baselines. The performance gain is large over the strongest baseline. On average, QCF improves the score of the strongest baseline by approximately 5.46%. It can not only get higher hit accuracy but also gain superior ranking quality. Secondly, we observe that there is no clear winner between CCF and the best baseline, but outperforms GMF in general. That is, CCF can achieve comparable performance to NeuMF even that it has simpler structures. Thirdly, CCF achieves slightly better performance than QCF on Foursquare, but fails on other five datasets with poorest performance on Video Game. In total, CCF is weaker compared with QCF. This is reasonable as Quaternion has better representational capability than complex number. Fourthly, the hit ratio and NDCG usually show consistent patterns in terms of varying cut-off values.

In summary, the proposed approaches can outperform both matrix factorization and neural networks based recommendation models, which clearly answers research question one and two.

5.6 Model Analysis

To answer the research question three, we conduct model analysis to get a better understanding towards the proposed approaches. We mainly focus upon analyzing QCF since it usually performs the best.

Where Does the Improvement Come From?

As we can see from Eq.(7), each user/item has four latent embedding vectors. It is natural to assume that it is the increase of latent embedding vectors that leads to the performance improvement. In order to study the effect of the increase of embedding vectors, we devised an extension of GMF by using four embedding vectors for each user and item. For simplicity, we reuse the notations in Section 4.2 and use Uu, Vu,Xu, Yu ∈ Rd to represent the user latent vectors and Pi, Qi, Si, Ti ∈ Rd to denote item latent vectors. The prediction function for this model is formulated as:

We train the model following the settings (e.g., loss function, optimization algorithm, etc.) of generalized matrix factorization and name it "MMF" (multiple matrix factorization).

The comparison results is shown in Table 3. At this point, we make an interesting observation - simply increasing the embedding vectors does not necessarily lead to substantial improvement and can even cause accuracy decrease. We can see that the improvement of MMF over GMF is trivial. We also found that it took longer time for MMF to converge than GMF. The second observation is that QCF usually outperforms MMF by a large margin, which also ascertains the reasonableness of using Quaternion for recommender systems. Compared with the simple combination in MMF, Quaternion collaborative filtering enables more complicated interactions and is less likely to cause over-fitting.

Does Quaternion Neural Networks Help?

Here, we study the impact of Quaternion neural networks. We add one Quaternion neural layer in QCF and coin it QCF+. The results are shown in Table 4. Unfortunately, there is no sign of considerable improvement with Quaternion neural networks. The increase in terms of hit ratio and NDCG is very limited. One possible explanation is that the increased amount of parameters may cause side effects to the model performance.

Impact of Embedding Dimension d

Figure 1 (a) and (b) show the effect of hyper-parameter d on the performance of QCF and NeuMF. Evidently, the embedding dimension has a big effect on the model performance. We make two observations. On the one hand, our model consistently outperforms NeuMF by varying the embedding size.

On the other hand, both small or large embedding dimension can pose side effects on the results. Setting d to a value between 15 to 45 is usually preferable. The performances of both models increase largely by moving d from 5 to 15. From then on, the performance of NeuMF fluctuates a lot while QCF maintains increasing or stable results.

Comparison on Runtime

Figure 1 (c) reports the runtime of all models on datasets Video Game. The runtime includes the training time of each epoch plus the test time. As can be seen, model JRL has the highest model complexity. Our model QCF only incurs a small computational cost over the neural networks based model NeuMF. Also, the difference in runtime between CCF and GMF is insignificant. Overall, the proposed approaches are very efficient and scalable.

6 Conclusion

In this paper, we presented a straightforward yet effective collaborative filtering model for recommendation. We move beyond real number space and explored the effectiveness of complex and quaternion representations for recommendation tasks. Extensive experiments on six real world datasets show that our model achieves very promising results without incurring additional cost. For future work, we will investigate more advanced hypercomplex systems such as Octonion [Baez, 2002] on the recommendation tasks.