LHRM: A LBS based Heterogeneous Relations Model for User Cold Start Recommendation in Online Travel Platform

Most current recommender systems used the historical behaviour data of user to predict user' preference. However, it is difficult to recommend items to new users accurately. To alleviate this problem, existing user cold start methods either apply deep learning to build a cross-domain recommender system or map user attributes into the space of user behaviour. These methods are more challenging when applied to online travel platform (e.g., Fliggy), because it is hard to find a cross-domain that user has similar behaviour with travel scenarios and the Location Based Services (LBS) information of users have not been paid sufficient attention. In this work, we propose a LBS-based Heterogeneous Relations Model (LHRM) for user cold start recommendation, which utilizes user's LBS information and behaviour information in related domains and user's behaviour information in travel platforms (e.g., Fliggy) to construct the heterogeneous relations between users and items. Moreover, an attention-based multi-layer perceptron is applied to extract latent factors of users and items. Through this way, LHRM has better generalization performance than existing methods. Experimental results on real data from Fliggy's offline log illustrate the effectiveness of LHRM.

forms: (1) new user cold start problem (2) new item cold start problem [7]. In new user cold start problem, a new user has just registered to the system and RS has no behaviour information about the user except some basic attributes [15]. In new item cold start problem, a new item is presently added to the online recommendation platform and RS has no ratings on it [15]. Compared with new item cold start problem, the new user cold start problem is more difficult and has been attracting greater interest [1]. In this paper, we focus on user cold start problem. Existing methods, including cross-domain recommendation algorithms [17,20,6,9,19], Lowrank Linear Auto-Encoder (LLAE) [11] have been proposed and achieved great success for user cold start problem.
User cold start recommendation over online travel platforms (e.g., Fliggy) are more challenging, thus existing methods cannot work well. LLAE [11] can reconstruct user behavior from user attributes, but even for active user, travel is a low-frequency demand and user behaviour is quite sparse. Therefore, the generalization performance of LLAE is limited by the sparse behaviour of users. Cross-domain algorithms try to utilize explicit or implicit feedbacks from multiple auxiliary domains to improve the recommendation performance in the target domain [6]. Unfortunately, it is hard to find a cross-domain that user has similar behaviour with travel scenarios and the LBS information of users have not been paid sufficient attention. Unconditional fuse the user behaviour information from other domains may introduce much noise. More importantly, user's travel intention is strongly related to user' LBS information. The intuition is that, users who are geographical situation closer may have similar travel intention.
To alleviate the user cold start problem in travel scenarios, we propose a LBS based Heterogeneous Relations Model (LHRM) for user cold start recommendation in online travel platform. LHRM firstly constructs heterogeneous relations between users and items and then apply an attention-based multi-layer perceptron to learn the latent factors of users and items. Heterogeneous relations is proposed in [2], which include user-user couplings, item-item couplings, and user-item couplings. It is increasingly recognized that modeling such multiple heterogeneous relations is essential for understanding the non-IID nature and characteristics of RSs [2,3]. In order to relieve the problem of data-sparse, user behaviour information in a specific category of items in related domains is used to learn the embedding representation of user. The background is that, more than 80% of Fliggy users have Taobao platform account 1 , and most of them are cold start users in Fliggy, but they have rich behaviours on Taobao. Then LBS information and user behaviour information in a specific category of items in Taobao domain are concatenated to construct the heterogeneous relations between users. User behaviour information in Fliggy domain is used to construct the heterogeneous relations between items. Meanwhile, user attributes are mapped into the space of user behaviour in Fliggy domain. After obtaining the side information and the embedding representation of user and items, an attention-based multi-layer perceptron is applied to extract higher level features and make the recommendation results more accurately for cold start user in Fliggy.
In summary, the contributions of this paper are multi-fold: -We propose a LBS-based Heterogeneous Relations Model (LHRM) for user cold start recommendation in travel scenarios, which utilize the LBS information and fuses user behaviour information in specific category in Taobao domain to improve the recommendation performance. -A new heterogeneous relations between users and items is proposed in LHRM, which can represent the relationship between users who with similar preference better. -Comprehensive experimental results on real data demonstrate the effectiveness of the proposed LHRM model.
The rest of this paper is organized as follows: Section 2 review the related work. Section 3 describe the proposed model in detail. Section 4 focus on the experimental results about the proposed model, including performance evaluation on real data from Fliggy's offline log. At last, we conclude the paper in Section 5.

Related Work
The main issue of the cold start problem is that, there is no available information can be required for making recommendations [7]. There has been extensive research on cold start problem in recommender systems. In the section, we mainly review the related work about user cold start problem.
Cross domain [6,17,9,8,5,19] recommendation algorithms have attracted much attention in recent years, which utilize explicit or implicit feedbacks from multiple auxiliary domains to improve the recommendation performance in the target domain. [6] proposed a Review and Content based Deep Fusion Model (RC-DFM), which contains four major steps: vectorization of reviews and item contents, generation of latent factors, mapping of user latent factors and crossdomain recommendation. Through this way, the learned user and item latent factors can preserve more semantic information. [8] proposed the collaborative cross networks (CoNet), which can learn complex user-item interaction relationships and enable dual knowledge transfer across domains by introducing cross connections from one base network to another and vice versa. [19] combine an online shopping domain with information from an ad platform, and then apply deep learning to build a cross-domain recommender system based on shared users of these two domains, to alleviate the user cold start problem. Servel recent works model the relationship between user attributes and user behaviour. With the assumption that people with the similar preferences would have the similar consuming behavior, [11] proposed a Zero-Shot Learning (ZSL) method for user cold start recommendation. Low-rank Linear Auto-Encoder (LLAE) consists of two parts, a low-rank encoder maps user behavior into user attributes and a symmetric decoder reconstructs user behavior from user attributes. LLAE takes the efficiency into account, so that it suits large-scale problem.
A non-personalized recommendation algorithm is proposed in [16]. The authos hypothesize that combining distinct non-personalized RSs can be better to conquer the most first-time users than traditional ones. [16] proposed two RSs to balance the recommendations along the profile-oriented dimensions. Max-Coverage and Category-Exploration aims to explore user coverage to diversify the items recommended and conquer more first-time users.

Problem Statement
Most current Recommender Systems (RSs) based on the intuition that users' interests can be inferred from their historical behaviours (such as purchase and click history) or other users with similar preference. However, it is difficult to recommend items to new users accurately. User cold start problem is a longstanding problem in recommender systems. In this work, we define the cold start user as the user who have not any behaviours on Fliggy in the past one month. Specifically, more than 20% of users are cold start users in Fliggy everyday and the optimization task of user cold start is becoming very important in Fliggy. The problem can be summarized as follows: Problem: Given a target domain D t , and a source domain D s , user u is new for D t , but it has interactions in D s , recommend top k items for u in D t .

Notations
In this paper, we use lowercase and uppercase letters to represent vector and matrix, respectively. We denote active users in two domain intersection as the target users {u t }. For every target u t , we denote the basic attributes as x ut = {x 1 , x 2 , x 3 , ..., x k }, the heterogeneous relation of user-user as E ug = {e u1 , e u2 , e u3 , ..., e un ; e ut }, each e un is the representation vector of u n . We denote the items that target users have interacted as the target items {i t }. For every target i t , we denote the basic attributes as .., e im ; e it }, each e im is the representation vector of i m . We use U to denote the target user matrix, and I to denote the target item matrix, Y ∈ {0, 1} |U| * |I| be the relationship matrix between U and I, where Y u,i = 1 means u n clicked i m .

Geohash Algorithm
In order to map user' LBS information (such as latitude and longitude) to a range, we use the Geohash algorithm [18]. Geohash is a public domain geocode system invented in 2008 by Gustavo Niemeyer and G.M. Morton, which encodes a geographic location into a short string of letters and digits (e.g., geo-hash6(31.1932993, 121.4396019) = wtw37q). Length of different Geohash strings represent different area of region, for example, geohash5 means a square area of about 10 square kilometers.

LBS based Heterogeneous Relations Model
It is worth noting that users' interests can be inferred from historical behaviours or other users with similar preference and benefited from heterogeneous relations. Moreover, user's travel intention is strongly related to user' LBS information (such as latitude and longitude), which based on the intuition that users who are geographical situation closer may have similar travel intention. To active this, we propose LBS based Heterogeneous Relations Model (LHRM), in which LBS information is used to construct the heterogeneous relation between users. The framework of LHRM illustrated in Fig.1. LHRM contains two modules: heterogeneous relations construction module and representation learning module.  Heterogeneous relations construction module The detailed process of constructing the heterogeneous relations between users and items is shown in Fig.2. We can see that user's historical behaviours sequence and LBS sequence in Taobao domain are concatenated and input into a embedding layer, which pretrained by skip-gram algorithm [13]. Specifically, items not related to travel are filtered out and user's latitude and longitude information is mapped to a string with the length of 5 by the geohash5 algorithm. After the embedding layer, we adopt average-pooling to generate the corresponding vector representation of user. In order to generate different user groups, we utilize K-means algorithm to cluster users according to their representation vectors. For each user group, any user can be regarded as the target user, and the other users are regarded as the friends of the target user.
User behaviour sequence in Taobao domain ...

Embedding Layer
User embedding  Each item that the target user has interacted in Fliggy domain is regarded as the target item. The whole candidate items set contains two part: items recalled by target item through item-item (i2i) and items interacted by all users in user group. Finally, the items in candidate set are filtered according to the topic of the target item and generate the item group. In this way, all items in item group are more related, and which can be represented by a pre-trained item embedding vector in Fliggy domain.
Representation learning module An attention-based multi-layer perceptron is used to learn the latent factors of users and items. After the process of heterogeneous relations construction, E ug and E ig are generated. Then we adopt an attention layer to focus on the relevant parts of E ug and E ig . The implementation of attention for sequence-to-one networks on E ug is shown in Eq.(1) and Eq. (2): where: W a is the learnable parameters in attention layer, and the output of attention layer is computed as Eq. (3): Similarly, attention layer is implemented on E ig , and the output is a i . The MultiLayer Perceptron (MLP) layer is a feed-forward neural network, which can generalize better to unseen feature combinations through low-dimensional dense embeddings learned for the sparse features [4]. We denote the input of MLP layer as v u and v i , the output of MLP layer as s u and The output of LHRM is the preference score of u t for i t , we denoteŷ as the output of dot layer.ŷ is computed as Eq. (4): y is binary labels with y = 1 or y = 0 indicating whether click or not. The logistic loss of LHRM is shown in Eq. (5): For clarity, we show the key steps of our algorithm in Algorithm 1.

Experiment
In this section, we conduct experiments on Fliggy and Taobao's offline log dataset to evaluate the performance of LHRM and some baseline models.

Algorithm 1 LBS based Heterogeneous Relations Model
Input: User's behaviour sequence in Taobao domain ST , user's LBS sequence in Taobao domain LT , user's behaviour sequence in Fliggy domain SF , user attributes Xu, item attributes Xi Output: Latent factors of users Su, latent factors of items Si 1: ST and LT are used to construct heterogeneous relation between users by K-means, and output Eu g 2: SF is used to construct heterogeneous relation between items, and output Ei g 3: Eu g and Ei g are input into attention layer, and output au, ai 4: the concatenation vector of [au, xu t ] and [ai, xi t ] are input into MLP layer, and output su, si 5: su, si are input into dot layer, and outputŷ 6: update all parameters according to L(y, y) = −ylog( y) − (1 − y)log(1 − y) 7: Cold start: 8:ŷnew = su new · si 9: Recommendation: 10: Computing the similarity score between the new user and all candidate items, and recommend the top-k items

Compared Methods
In the experiments, we compare the following methods.
-Hot: Hot is a non-personalized recommendation algorithm, which recommends items to new users according to the popularity score of item in Fliggy domain.

-HERS: Heterogeneous relations-Embedded Recommender System (HERS)
is proposed in [9], which based on ICAUs to model and interpret the underlying motivation of user-item interactions by considering user-user and item-item influences and can handle the cold start problem effectively. -MaxCov: Max-Coverage (MaxCov) [16] is a non-personalized recommendation algorithm, which aims to explore user coverage to diversify the items recommended and conquer more first-time users. -LHRM: Lbs based heterogeneous relations model proposed in this paper.
Popularity score of items is very important factor in cold start recommendation, therefore, when implementing LHRM and HERS in experiments, we fuse the popularity score of items with the score of LHRM and HERS's output. Then, final preference score of u t for i t calculated in Eq. (6):

Implementation Details
We set the maximum length of user group and item group to 10. The number of cluster center is set to 1000. The dimension of latent factors of user and item is a hyper parameter, we set it to 32, 64, 128 and 256 in the experiments. In order to evaluate the performance of proposed methods, we adopt two evaluation metrics, i.e., Hit Rate (HR@30,@50,@100,@200), Normalized Discounted Cumulative Gain (NDCG@30,@50,@100,@200). HR is a metric of shotting accurately at target items. NDCG is a cumulative measure of ranking quality, which is more sensitive to the relevance of higher ranked items.

Datasets
During our survey, no public datasets for user cold start recommendation in travel scenarios. To evaluate the proposed approach, we collect the offline log data from Fliggy and Taobao domain in the past one month as the dataset. Generally, impression and click sample as positive samples, impression but not click samples as negative samples. All the data have been de-identified, and the algorithm training and application related to cold start do not involve the identification of users, so as to fully protect the privacy of users. The statics of dataset is illustrated in table 1.

Results
We show the experimental results of different models in Table 2. Among all methods, LHRM achieves the best performance in terms of all metrics. Specifically, when the dimension of latent factors of user and item is set to 32, the HR and NDCG are the highest. Table 2 shows the HR and NDCG on target items, and all existing methods did not work well on cold start users. Generally, in practical applications, we not only care whether the recommended items will be clicked, but also whether the recommended items are related to the target items. Therefore, we evaluate the hit rate of different models under different degree of relevance with target items. Experimental results are shown in Fig.3. We can see that, LHRM-32 is very competitive, MaxCov performs best when calculating hit rate according to whether the destination same as the target items.

Conclusion
In this paper, we point out two challenges of user cold start recommendation in travel platform: i) it is hard to find a cross-domain that user has similar behaviour with travel scenarios ii) LBS information of users have not been paid sufficient attention. To address this problem, we propose LBS based heterogeneous relations model. LHRM utilizes user's LBS information and behaviour information in Taobao domain and user's behaviour information in Fliggy domain to construct the heterogeneous relations between users and items. Moreover, an attentionbased multi-layer perceptron is applied to extract latent factors of users and items. Experimental results on real data from Fliggy's offline log illustrate the effectiveness of LHRM.