Multi-trends Enhanced Dynamic Micro-video Recommendation

The methods for recommendation can be generally classified into two categories. Early algebraic approaches adopted collaborative filtering (Konstan et al., 1997; Ding and Li, 2005; He et al., 2017b; Sarwar et al., 2001) or model-based methods (Rendle et al., 2010; Deshpande and Karypis, 2004; Wang et al., 2015; Kim and Shim, 2014) to estimate user-item correlations and make predictions about users’ future interests. Collaborative filtering (CF) assumes that users sharing the same opinion on one issue tend to have more similar opinions on other issues (Koren and Bell, 2015), and thus it makes predictions specific to each user through information gleaned from other users (Terveen and Hill, 2001). Due to the extreme high computational complexity and data sparsity in traditional CF (Deshpande and Karypis, 2004; Papagelis et al., 2005), model-based methods alleviate this overhead by mapping user-item interactions into matrix entries, then apply factorization to the characteristic matrix to build nonlinear models that estimate correlations (i.e. preferences) between every pair of user and item and employ Hidden Markov models (HMM) to capture temporal trends of preferences (Rendle et al., 2010).

Recently, as the major advances in deep learning techniques, a wealth of research has sprung up on incorporating them into recommender systems. Most of work reformulated traditional estimation problem as learning task based on deep neural networks (Fan et al., 2019; Smirnova and Vasile, 2017; He et al., 2018). In the field of video recommendation, representative work focuses on content-based learning (Covington et al., 2016; Wang et al., 2019b; Wei et al., 2019a; Deldjoo et al., 2016), in which features of videos are extracted into embedding vectors and then matched with user representations that indicate individual preference. To name a few, Chen et al. (2017) tackled the item- and component-level implicit feedback issue in multimedia recommendation by learning independent video and users characteristics in a unified hierarchical attention network and then reckoning pair-wise scores as a measure of user preference. Although these works improve the accuracy of user modeling, they lack a clear partition of history and future for the given dataset and hence may encounter prediction bias due to mixing the two parts together. Our work adopts a multi-step time partition and similarity matching approach to alleviate this issue.

Modeling latent user interest from historical behaviors is commonly used in recommender systems. In the past two decades, a variety of approaches have been proposed, ranging from Markov chains (Shani et al., 2005; Rendle et al., 2010; He et al., 2016; He and McAuley, 2016; Norris and Norris, 1998) and traditional collaborative filtering (Koren, 2009; Ding and Li, 2005; Salakhutdinov and Mnih, 2008) to deep representation learning (Qu et al., 2016; Zhou et al., 2018). The approaches based on Markov decision processes implicitly track user state dynamics to predict future behaviors. For example, Rendle et al. (2010) captured long-term user interest via personalized transition graphs over underlying Markov chains. He and McAuley (2016) integrated similarity-based methods with Markov chains smoothly in personalized sequential recommender systems. Besides, temporal collaborative filtering is proposed to deal with the drifting user preferences. Koren (2009) offered a paradigm that tracks time changing behaviors throughout the life span of the data.

With the development of deep learning, more and more researchers adopted deep neural networks (DNN) to model the user dynamics in recommender systems. Particularly, Hidasi et al. (2015) applied recurrent neural networks (RNN) to model the whole session and introduced a new ranking loss function to make recommendations more accurate. Tang and Wang (2018b) utilized convolutional filters to embed a sequence of recent items into an ”image” in the time and latent spaces as well as learn sequential patterns as local features of the image. Wu et al. (2019b) considered session sequences as graph structured data and used graph neural networks (GNN) to capture complex transitions of items. Recently, self-attention mechanism (Vaswani et al., 2017) has been widely employed in recommender systems(Kang and McAuley, 2018a). For instance, Wu et al. (2020) proposed a Contextualized Temporal Attention Mechanism to weigh historical actions’ influence on not only what action it is, but also when and how the action took place.

However, previous work does not consider the influence of future information when modeling user behaviors in history sequences. In this work, we constructed a user-item heterogeneous graph to capture future interactions of each user with items.

In a typical micro-video recommendation scenario, we have a set of users and a set of micro-videos, which can be denoted as ${U=\{u_{1},u_{2},u_{3},...,u_{|U|}\}}$ and ${V=\{v_{1},v_{2},v_{3},...,v_{|V|}\}}$ respectively. Let ${I_{u}=\{x_{1}^{u},x_{2}^{u},...,I_{|I_{u}|}^{u}\}}$ represent the sequence of interacted micro-videos ${x\in I_{u}}$ of user ${u\in U}$, which is sorted in a chronological order according to the timestamp of each interaction, and ${x_{t}^{u}}$ denote the micro-video that the user ${u}$ has interacted with at timestamp ${t}$. The interaction sequence ${I_{u}}$ is split into ${I_{+}}$ and ${I_{-}}$ which represent the micro-videos clicked by the user and the ones not clicked respectively. Given the user’s historical micro-video interaction behaviors, the investigated goal of the micro-video recommendation task in this paper is to predict the probability that the new candidate micro-video will be clicked by user ${u}$. Notations are summarized in Table 1.

Specifically, each instance is represented by a tuple ${(I_{u},A_{i})}$, where ${I_{u}}$ denotes the set of items interacted by user ${u}$, ${A_{i}}$ the features of target item ${i}$ including the information of interaction timestamp and micro-video embeddings. Through implicit user network module, we extract relative future sequence of user ${u}$ based on ${I_{u}}$ and their similar users’ historical interaction ${I_{u^{\prime}},u^{\prime}\in U}$. The detail will be illustrated in Section 3.3.

To model diverse user preferences dynamically, DMR learns a function ${f}$ for mapping history trend set ${T_{u}^{h}}$ and future trend set ${T_{u}^{f}}$ into user representations, which can be formulated as:

where ${\overrightarrow{e_{u}}\in\mathbb{R}^{d\times 1}}$ denotes the representation vector of user ${u}$, ${d}$ the dimension. Besides, the representation vector of target micro-video ${i}$ is obtained by an embedding function ${g}$ as:

where ${\overrightarrow{e_{i}}\in\mathbb{R}^{d\times 1}}$ denotes the representation vector of target micro-video ${i}$.

Based on the learned user representation vector and micro-video representation vector, the probability of candidate micro-video is calculated using the likelihood function ${P}$ as:

where ${\overrightarrow{e_{i}}}$ is the embedding of target item ${i}$ from set of micro-videos ${V}$. Our framework outputs the click probabilities of the candidate micro-video to rank the personalized recommendation list. Then the system provide precise and diversified recommendation for each user, which entails potential preference of the specific user as they are most likely to interact with the recommended micro-videos.

The objective function for training our model is described in Section 3.6 We use the Adam optimizer to train our method.

The overall structure of our proposed framework DMR is illustrated in Figure 1, which is composed of an implicit user network module, a multi-trend routing module, a multi-level time-aware attention module and a prediction layer. As the relative future sequence for current user is actually the history sequence for the neighbors, the multi-trend routing algorithm is applied on both the future and history sequences using shared parameters in parallel. The framework takes the user historical interactions set ${X}$ as input. We use ${X^{u}_{1,N-K}}$ and ${X^{u}_{N-K+1,N}}$ to represent training and testing data of interactions sequence of user ${u}$ respectively. ${N}$ and ${K}$ denotes the selected total length of interaction sequence of each user ${u}$ and the length of training sequence respectively. For micro-videos from the set of ${X^{u}_{1,N-K}}$, embeddings are presented as ${\overrightarrow{e}_{X^{u}_{1,N-K}}}$.

The implicit user network module constructs neighbors set for each user by selecting the users that have similar micro-video preference as indicated in their past behaviors, and then extract the relative future sequences from each neighbor. The query items can be selected from the user historical interaction ${I_{u}}$, for simplicity, we solely choose the last one in the list, which can be both efficient and effective as demonstrated in the empirical analysis. The relative future behaviors are defined as the interacted items following the query item in the chronological order, aiming at representing dynamic preference of the user. The intuition in behind is that the user tend to have similar preference trend as users with similar historical behaviors, and that the user can have diverse and dynamic trends of preferences.

The multi-trend routing module is developed to obtain the neighbor centroids according to diverse motivation behind specific interactions with the micro-videos. Then we learn future-aware diverse trends based on history and future sequence jointly. Furthermore, the future sequence evolved user representation acquired by time-aware attention layer is concatenated with the historical behavior evolved user representation to generate the dynamic user preference representation vector. Finally we compute the user’s preferences over different micro-videos from the pool by the prediction decoder. Each part will be elaborated in the following sections.

As shown in Figure 2 ,the implicit user network is constructed based on user-item heterogeneous graph, which contains both the user nodes and item nodes. An edge in the graph represents the interaction between the user and the item. The weight of the edge indicates the temporal weight of each interacted item in a chronological order. The query items are selected in a multi-hop manner. The user nodes connected to the selected query items are considered as the candidate neighbor nodes of the current user.

Inspired by some works (Guo et al., 2016; Felicio et al., 2016), which extract social relationships in absence of explicit social networks (Mukherjee and Guennemann, 2019) , we construct the user network from user-item correlation implicitly.

Specifically, we compare the similarity among users via collaborative filtering implicitly based on the historical interactions with micro-videos. As the Pearson Correlation Coefficient(PCC) is a widely used similarity measure, we adopt Pearson Correlation Coefficient (Breese et al., 2013) to compute a linear correlation between the user and each candidate neighbor as:

where ${I(i)}$ is a set of micro-videos user ${i}$ interacted with, ${r_{ik}}$ and ${\overline{r}_{i}}$ represents the level (click or not click) of interaction of user ${i}$ over micro-video ${k}$ and the average level of action of user ${i}$. The user similarity $s_{i}$ is ranging from ${[-1,1]}$, and the similarity between users ${i}$ and ${j}$ is proportional to the value according to this definition. Following (Ma, 2013), we employ a mapping function ${f(x)=(x+1)/2}$ to bound the range of PCC similarities into ${[0,1]}$.

In the case of users with only one common micro-video in history, PCC similarity gets $1$ when the users’ preferences over the common micro-video are similar and $-1$ when not, which encourages diversity of neighbors while damaging the fairness of similarity calculation. To tackle this issue, we only kept less than ${20\%}$ of such neighbor nodes to seek the balance.

In addition to the PCC method, we also design a filter with simple schema to extract similar users. For each user, if the historical interactions ${I_{u}}$ is split into two pieces, ${I^{u}_{1:t_{1}}}$ for training data, and ${I^{u}_{t_{1}:t_{2}}}$ for testing data, the item ${\hat{I}^{u}_{k}}$ is defined as the last ${k}$ micro-videos, ${k}$ could be any value less than or equal to ${|I^{u}|}$, while in practice ${k=1}$ can achieve good enough performance with simplicity. We extracted a list of neighbors ${N=\{n_{1},n_{2},...,n_{|N|}\}}$ according to the query item. The detail of this process is described in Algorithm 1. Furthermore, we constructed the future sequence of user ${u}$ as:

where Timestamp is denoted as ${TI}$ and the query item is denoted as ${I_{|I_{u}|-k}}$. ${I_{n}}$ represents the interaction set of neighbor ${n}$

To capture the trend information lies in both history sequence and future sequence, we devised a multi-trend routing module into a two-stage manner to generate trend represent parallelly. Specifically, we group each micro-video from both the user’s historical sequence and extracted relative future sequence into diverse trends in the first stage. The micro-videos that are grouped into the same trend are considered to be similar according to users’ interactions over them and their own basic features. In the second stage, the micro-videos from historical sequence and relative future sequence are utilized to generate the representation of history and future trend group in parallel.

Based on the positive historical interaction sequence ${I_{+}}$ of user ${u}$, we represent each micro-video ${x}$ in ${I_{+}}$ as an embedding vector ${\overrightarrow{x}\in\mathbb{R}^{d}}$, where ${d}$ is the embedding size. And we initialize positive history trend group as ${T_{u}^{h}\in\mathbb{R}^{s\times d}}$ for user ${u}$, where ${s}$ denotes the number of trend groups indicated from historical sequence and ${d}$ denotes the embedding dimension of each history trend. Specifically, each trend embedding is represented as ${\overrightarrow{t}\in\mathbb{R}^{d}}$.

Similarly, based on the extracted future sequence ${F_{+}}$ from the implicit user network. The positive future trend group is denoted as ${T_{u}^{f}\in\mathbb{R}^{s\times d}}$ for user ${u}$, where ${s}$ denotes the number of trend groups indicated from future sequence and ${d}$ denotes the embedding dimension of each future trend.

In order to fine-tune the representation of each trend, we apply attention mechanism over each micro-video and the initialized trend group. Given the micro-video embedding ${\overrightarrow{x}\in\mathbb{R}^{d}}$ and the trend embedding ${\overrightarrow{t}\in\mathbb{R}^{d}}$, we calculate the weight between the micro-video and the trend based on a co-attention memory matrix. The micro-video from the history sequence and the future sequence are put into history trend and future trend separately. As the history sequence and future sequence is processed separately, our module is capable of capturing timeliness of trends which indicates evolved user interest.

As for the item-level, we use the weighted sum of historical micro-video features to obtain the current micro-video representation. Finally, we get the representation of each trend by attention mechanism on each micro-video in the trend group. As for the trend-level, we utilize the time-aware attention to activate the weight of diverse trends to capture the timeliness of each trend. Specifically, the attention function takes the interaction time of item ${i}$, the interaction time of trends and trend embeddings as the query, key and value respectively. We compute the final representation of trend representation future sequence of user ${u}$ as:

where Attention denotes the attention function, ${TI_{i}}$ represents the interaction time of micro-video ${i}$, ${TI_{tr}}$ represents the average interaction time of micro-videos related to the trend group, ${\overrightarrow{t_{u}}}$ represents the embedding of the specific trend group.

The trend group generated from the user’s historical sequence and future sequence are then eventually updated by adding the corresponding trend group in ${T_{u}^{h}}$ and ${T_{u}^{f}}$ with the aggregation of history trend and future trend representation respectively.

After computing the trend embeddings from activated trends through time-aware attention layer, we apply sumpooling to both history and future trend representations.

And then we concatenate the history trend representation vector ${e_{u}^{h}}$ and future trend representation vector ${e_{u}^{f}}$ to form a user preference embedding ${\overrightarrow{e_{u}}}$ as:

Given a training sample ${u,i}$ with the user preference embedding ${\overrightarrow{e_{u}}}$ and micro-video embedding ${\overrightarrow{e_{i}}}$ as well as the micro-video set ${V}$, we can predict the possibility of the user interacting with the micro-video as

In the same way, we calculate the prediction score ${P(x|H_{-})}$ based on the negative interaction sequence, which aims to maximize the distance between the new micro-video embedding and user’s negative trend embeddings.

The final recommendation probability ${\hat{p}_{ij}}$ is represented by the linear combination of ${p(x|H_{+})}$ and ${p(x|H_{-})}$. And the objective function of our model is as follows:

where ${\hat{p}_{ui}}$ denotes the prediction score of micro-video ${i}$ for user ${u}$, ${\sigma}$ represents the sigmoid activation function.

MicroVideo-1.7M and KuaiShou were used as micro-video benchmark datasets in our experiments. Micro-video data and user-video interaction information can be found in each of these datasets. Each micro-video is represented by its features in these two datasets, and each interaction record includes the userID, micro-video ID, visited timestamp, and whether the user clicked the video. The two datasets’ statistics are shown in Table 2.

• •

  MicroVideo-1.7M(Chen et al., 2018a): This dataset comes from real data of micro-video sharing service in China which contains 1.7 million micro-videos.

• •

  KuaiShou: This dataset is released by the Kuaishou Competition in China MM 2018 conference.

  Dataset	users	items	interactions	train	test
  MicroVideo-1.7M	10,986	1,704,880	12,737,619	8,970,310	3,767,309
  KuaiShou	10,000	3,239,534	13,661,383	10,931,092	2,730,291

We used TensorFlow on four Tesla P40 GPUs to train our model with Adam optimizer. The following are the hyper-parameters: The micro-video embedding is 512-dimensional vectors, while the user embedding is 128-dimensional vectors. The batch size was set to 32, the optimizer was Adam, the learning rate was set to 0.001, and the regularization factor was set to 0.0001.

To find the user’s similar neighbors, we used the Pearson Correlation Coefficient (PCC) described earlier. In the ablation analysis, we set neighbor numbers as 5, 20, and 50. As for the  future sequences, we cut off each neighbor’s at most 100 interacted micro-videos after the current user’s query items.

To compare the performance of different models,we use Precision@N, Recall@N, F1-score@N and AUC, where N is set to 50 as metrics for evaluation.

• •

  Precision: Number of correctly predicted positive observations divided by the total number of predicted positive observations.

  (11)

  $$Precision@N=\frac{1}{|U|}\sum\limits_{u\in U}\frac{|\hat{I}_{u,N}\cap I_{r}|}{|I_{r}|}$$

  where ${\hat{I}_{u,N}}$ denotes the set of top-N recommended micro-videos for user u and ${I_{r}}$ is the total recommendation list for user u.

• •

  Recall: Number of corrected recommended micro-videos divided by the total number of all recommended micro-videos.

  (12)

  $$Recall@N=\frac{1}{|U|}\sum\limits_{u\in U}\frac{|\hat{I}_{u,N}\cap I_{u}|}{|I_{u}|}$$

  where ${\hat{I}_{u,N}}$ denotes the set of top-N recommended micro-videos for user u and ${I_{u}}$ is the set of testing micro-videos for user u.

• •

  F1-score: F1 Score is the weighted average of Precision and Recall. It’s used to balance between Presicion and Recall.

  (13)

  $$F1-score=2*\frac{Precision*Recall}{Precision+Recall}$$

• •

  AUC: AUC (Area Under the ROC Curve) is used in classification analysis to determine the quality of classifiers.

To validate the effectiveness of our proposed DMR framework, we conducted experiments on two publicly available real-world datasets. The comparision to other state-of-the-art micro-video recommenders are summarized in Table 3.

• •

  BPR(Rendle et al., 2012): Trained on pairwise items, the Bayesian personalized ranking(BPR) maximize the difference between positive and negative items of each user in Bayesian approach.

• •

  LSTM(Zhang et al., 2014): Long short-term memory(LSTM) is a sequence model. Hidden states of each unit are aggregated to form user interest representation.

• •

  CNN: The convolutional neural network (CNN) can be utilized to generate user interest representations based on the inter- action sequence. The max pooling layer and MLP layers are used for user interest extraction and prediction.

• •

  NCF(He et al., 2017a): As a collaborative filtering based model, NCF learns user embedding and item embedding with a shallow network and a deep network, which is able to learn an arbitrary function from data.

• •

  ATRank(Zhou et al., 2018): ATRank is an attention-based behavior modeling framework, which can model with heterogeneous user behaviors using only the attention model. It utilizes self-attention in multiple semantic spaces to capture behaviors interactions. The model is capable of predicting all types of user actions in a multi-task manner, which shows effectiveness over the highly optimized individual models.

• •

  THACIL(Chen et al., 2018a): THACIL achieved the click-through prediction for micro-videos by modeling user’s historical behaviors. The proposed recommendation algorithm characterizes both short-term and long-term correlation within user behaviors. It also profiles user interests at both coarse and fine granularities.

• •

  ALPINE(Li et al., 2019c): To intelligently route micro videos to target users, ALPINE proposed an LSTM model based on a temporal graph, which is encoded by user’s historical interaction sequence. The model captures the complex and diverse interests of users via a multi-level interest modeling layer. Moreover, the model achieves better performance by utilizing true negative samles, which indicates uninterested information.

• •

  MTIN(Jiang et al., 2020b): This model is a multi-scale time-aware user interest modeling framework, which learns user interests from fine-grained interest groups. MTIN incorporates the interest group routing unit to generate user interest groups based on the interaction sequence and leverages fine-grained interest groups via item-level and group-level interest extraction unit. The distilled user interest representation is used to predict the click probabilities of micro-video candidates.

The model performance on the two datasets is summarized in Table 3. We run experiments to dissect the effectiveness of our recommendation model. We compare the performance of DMR with several commonly used and state-of-the-art models: BPR, LSTM, CNN, NCF, ATRank, THACIL, ALPINE and MTIN. All these models are running on the two datasets introduced above: MicroVideo-1.7M and KuaiShou-Dataset. According to the results shown in Table 3, our model DMR achieve better performance on precision over KuaiShou dataset and performs better in terms of AUC, Recall and F1-score over MicroVideo-1.7M dataset.

Table 4 compares the result of different neighbor number setting of 5, 20 and 50. Considering more neighbors could result in more diversity, but too many neighbors would dilute interest trends’ embedding. Our model achieves improvements on neighbor number equals 20 over 5. Besides, it shows reduction if setting neighbor number from 20 to 50. This means the number of neighbors also play a crucial part in model performance.

The computational complexity of sequence layer modeling user and neighbors is $O(knd^{2})$, where $k$ denotes the number of extracted neighbors, $n$ denotes the average sequence length and $d$ denotes the dimension of item’s representation. Capsule layer’s computational complexity depends on kernel size and number of trends. Average time complexity of capsule layer scales $O(nTr^{2})$, where $r$ denotes kernel size of capsule layer and $T$ denotes the number of trends. For large-scale applications, our proposed model could reduce computational complexity by two measures: (1)encode neighbors with a momentum encoder(He et al., 2019).(2)adopt a light-weight Capsule network.

Aside from achieving high recommendation accuracy, diversity is also essential for the user experience. With little information of historical interactions between the users and the micro-videos, recommendation systems learned to assist users in selecting micro-videos that would be of interest to them. Recommender systems keep track of how users interacted with the micro-videos they’ve chosen.

Many research works (Adomavicius and Kwon, 2012; Boim et al., 2011; Di Noia et al., 2014; Premchaiswadi et al., 2013) have been undertaken to propose novel diversification algorithms. Our proposed module can learn the diverse trends of user preference and provide recommendation with diversity. We define the individual diversity as below:

where ${CATE}$ represents the category of the item. ${\hat{i}_{u}}$ denotes item recommended for user ${u}$, ${j}$ and ${k}$ represents the order of the recommended items. ${\delta(\cdot)}$ is an indicator function.

Table 5 presents comparisons with THACIL and MTIN over the recommendation diversity metric on Micro-video dataset, which provides category infromation of micro-videos. We adopt the setting of six historical trend and six future trend evolved from 5 neighbors for our model. From the table, our module DMR achieve the optimum diversity metric indicating the recommendation it provide can effectively take neighbors’ interests into account.