Predicting Temporal Sets with Deep Neural Networks

Most of the existing temporal sets prediction methods have two main components: set embedding and temporal dependency learning, where set embedding turns the temporal sets prediction problem into a conventional predictive modelling problem. However, the set embedding step suffers from information loss problem caused by the pooling operation, which reduces the final prediction accuracy.

In order to leverage the useful information in element relationship as much as possible, this paper founds on element representation according to set-level relationship learning. In particular, we propose a weighted graph convolutional network on dynamic graphs, which first constructs weighted graphs based on the co-occurrence of elements and then propagates information between elements in each graph. Let $\bm{E}\in\mathbb{R}^{m\times F}$ denote the embedding matrix of all elements ¹¹1The embedding matrix $\bm{E}$ is initialized from the standard normal distribution., where $F$ is the dimension of element representation. Then we learn the relationships of elements by the following two steps.

Weighted Graphs Construction. The process of constructing weighted graphs is shown in Figure 3.

For $S_{i}^{t}\in\mathbb{S}_{i}$, the $t$-th set of user $u_{i}$, we first generate the pairs of every two elements in $S_{i}^{t}$ and each pair denotes a co-occurrence relationship of two elements in $S_{i}^{t}$. For example, let $S_{i}^{1}=\{v_{i,1},v_{i,2},v_{i,3}\}$ and the generated pairs are $(v_{i,1},v_{i,2})$, $(v_{i,2},v_{i,1})$, $(v_{i,1},v_{i,3})$, $(v_{i,3},v_{i,1})$, $(v_{i,2},v_{i,3})$ and $(v_{i,3},v_{i,2})$, see Figure 3(a). After generating pairs of elements for each set in $\mathbb{S}_{i}$, we could obtain a collection of all pairs. Then we select all unique pairs and assign value to each pair based on its appearing frequency. We add self-connection for each element appearing in $\mathbb{S}_{i}$ by treating its appearing frequency as 1, which is used to reduce the information loss for rarely appearing elements in the sequence as the information of such elements would decrease dramatically in long sequences without the self-connection during the following convolutional operations, see Figure 3(b). After that, we normalize the value of each pair between 0 and 1 to denote the weights among different elements as shown in Figure 3(c). Finally, we construct the graph for each set based on the calculated weights and assign representation to each element by its corresponding representation in $\bm{E}$, see Figure 3(d). Following the above steps, we could construct $T$ weighted dynamic graphs $\mathbb{G}_{i}=\left\{\mathcal{G}_{i}^{1},\mathcal{G}_{i}^{2},\cdots,\mathcal{G}_{i}^{T}\right\}$. The $t$-th graph $\mathcal{G}_{i}^{t}=(\mathcal{V}_{i},\mathcal{E}_{i}^{t})$ is a weighted undirected graph with a weighted matrix $\bm{A}_{i}^{t}\in\mathbb{R}^{|\mathcal{V}_{i}|\times|\mathcal{V}_{i}|}$, where $\mathcal{V}_{i}$ denotes the set of appearing elements in $\mathbb{S}_{i}$ and $\mathcal{E}_{i}^{t}$ denotes the set of edges in $\mathcal{G}_{i}^{t}$. In the following parts, we use $\bm{e}_{i,j}^{t}\in\mathbb{R}^{F}$ to denote the representation of element $v_{i,j}\in\mathcal{V}_{i}$ at time $t$.

Weighted Convolutions on Dynamic Graphs. This paper designs a novel module to perform weighted convolutions on the constructed dynamic graphs. The input of this module is a sequence of dynamic graphs $\mathbb{G}_{i}=\left\{\mathcal{G}_{i}^{1},\mathcal{G}_{i}^{2},\cdots,\mathcal{G}_{i}^{T}\right\}$, where graph $\mathcal{G}_{i}^{t}\in\mathbb{G}_{i}$ has a sequence of elements represented as $\left\{\bm{e}_{i,j}^{t}\in\mathbb{R}^{F},\forall v_{i,j}\in\mathcal{V}_{i}\right\}$. For graph $\mathcal{G}_{i}^{t}$, the output of this module is a new sequence of element representation, which could be denoted as $\left\{\bm{c}_{i,j}^{t}\in\mathbb{R}^{F^{\prime}},\forall v_{i,j}\in\mathcal{V}_{i}\right\}$, where each element is denoted with $F^{\prime}$ dimensions.

The weighted convolutions are implemented by propagating information of elements in each dynamic graph as follows. Take graph $\mathcal{G}_{i}^{t}$ as an instance,

where $\bm{A}_{i}^{t}[j,k]$ represents the item at the $j$-th row and $k$-th column of matrix $\bm{A}_{i}^{t}$, which is the edge weight of $v_{i,j}$ and $v_{i,k}$ in graph $\mathcal{G}_{i}^{t}$, $\bm{W}^{t,l}\in\mathbb{R}^{F^{l}\times F^{l-1}}$ and $\bm{b}^{t,l}\in\mathbb{R}^{F^{l}}$ are trainable parameters of the $l$-th convolutional layer at time $t$, and $\bm{c}_{i,j}^{t,l}$ denotes the representation of $v_{i,j}\in\mathcal{V}_{i}$ in the $l$-th layer at time $t$. $F^{l}$ denotes the output dimension of the $l$-th layer and $F^{0}$ is equal to $F$. $\mathcal{N}_{i,j}^{t}$ are neighbors’ indices of the $j$-th element in graph $\mathcal{G}_{i}^{t}$. To reduce the parameter scale and also make our method flexible to deal with sequences with variable lengths, a parameter sharing strategy is adopted, Equation (1) is rewritten as

which means that we utilize shared parameters for convolutional layers across different timestamps. In the first layer, $\bm{c}_{i,j}^{t,0}$ is initialized from the standard normal distribution, which is actually the representation of $v_{i,j}$ in $\bm{E}$. The output dimension of the last layer is set to $F^{\prime}$. Due to the weighted convolutions on dynamic graphs, each element in the graphs could not only receive the information from itself, but also receive the information from its neighbours. The representation of each element is updated by all the received information. After the information propagating thoroughly, we achieve a stable representation of each element, which comprehensively considers the relationships of all elements in the graphs. Formally, we use $C_{i,j}=\left\{\bm{c}_{i,j}^{1},\bm{c}_{i,j}^{2},\cdots,\bm{c}_{i,j}^{T}\right\}$ to denote the sequence of $v_{i,j}$, where $\bm{c}_{i,j}^{t}\in\mathbb{R}^{F^{\prime}}$ is the output of the last convolutional layer.

For the studied problem, it has been reported that some elements appear quite frequently and regularly in a sequence, while the other elements appear irregularly and occasionally (Hu and He, 2019), which makes the temporal dependency among a sequence dynamic and complicated. Traditional RNNs fail to handle such temporal dependency, even some gated model have been proposed (e.g. LSTM (Hochreiter and Schmidhuber, 1997), GRU (Chung et al., 2014)). The reason is that RNNs only propagate information sequentially, which limits the perception field of temporal dependency learning (Khandelwal et al., 2018). Different from the RNNs, the self-attention mechanism could provide a model with the ability to capture the temporal dependency without such limitation (Vaswani et al., 2017; Sankar et al., 2018). In our model, we extend the self-attention mechanism to capture temporal dependency.

To learn the dynamic and evolutionary patterns in sequences, a temporal dependency learning component is proposed in this paper. The inputs of this component are the sequences of all elements’ representations in $\mathcal{V}_{i}$, which could be denoted as $\mathbb{C}_{i}=\left\{C_{i,1},C_{i,2},\cdots,C_{i,|\mathcal{V}_{i}|}\right\}$, where $C_{i,j}=\left\{\bm{c}_{i,j}^{1},\bm{c}_{i,j}^{2},\cdots,\bm{c}_{i,j}^{T}\right\}$ are the representations of element $v_{i,j}$ over time. We use $\bm{C}_{i,j}\in\mathbb{R}^{T\times F^{\prime}}$ to denote the stacked matrix representation of $C_{i,j}$, where the $t$-th row of $\bm{C}_{i,j}$ is $\bm{c}_{i,j}^{t}$. The outputs of this component are aggregated and compact representations of elements in $\mathcal{V}_{i}$, that is, $\mathbb{Z}_{i}=\{\bm{z}_{i,1},\bm{z}_{i,2},\cdots,\bm{z}_{i,|\mathcal{V}_{i}|}\}$, where $\bm{z}_{i,j}\in\mathbb{R}^{F^{\prime\prime}}$ denotes the representation of element $v_{i,j}\in\mathcal{V}_{i}$. This subsection first introduces how to aggregate the stacked representations $\bm{C}_{i,j}$ into new representations $\bm{Z}_{i,j}$ with consideration of temporal dependency, and then discusses how to compress the new representations into a compact representation of $v_{i,j}$, denoted as $\bm{z}_{i,j}$.

The self-attention is used to learn temporal dependency of the stacked representations for each element. The new representations with consideration of temporal dependency are computed as

where $\bm{W}_{q}\in\mathbb{R}^{F^{\prime}\times F^{\prime\prime}}$, $\bm{W}_{k}\in\mathbb{R}^{F^{\prime}\times F^{\prime\prime}}$, $\bm{W}_{v}\in\mathbb{R}^{F^{\prime}\times F^{\prime\prime}}$ are trainable parameters to calculate queries, keys and values for elements in the sequence, $\bm{Z}_{i,j}\in\mathbb{R}^{T\times F^{\prime\prime}}$ is the stacked representation of $v_{i,j}$’s sequence. $\bm{M}_{i}\in\mathbb{R}^{T\times T}$ is a masked matrix, which is used to avoid the future information leakage and guarantee that the state of each timestamp is only affected by its previous states. It is defined as

Then we aggregate the sequential information into a vectorized representation by the following weighted aggregation equation,

where $\bm{w}_{agg}\in\mathbb{R}^{F^{\prime\prime}}$ is a trainable parameter to learn the importance of different timestamps adaptively. $\bm{z}_{i,j}\in\mathbb{R}^{F^{\prime\prime}}$ is a compact representation for element $v_{i,j}$ that considers all the possible temporal dependencies. In this paper, we set $F^{\prime\prime}=F$ to make the calculation in the following part more convenient.

Our model predicts the subsequent set based solely on the historical behaviors, without using any other auxiliary information (e.g. the attributes of users). This indicates that different users may share the same patterns in their sequential behaviors. Mining the shared patterns could not only make our method suitable for sparse data but also improve the robustness of the prediction result.

To discover the shared hidden patterns and also to combine the static and dynamic information together, A gated information fusing component is provided here. The input of this component has two parts: the shared element representation matrix $\bm{E}$ and the compact representations of elements w.r.t. user $u_{i}$, $\mathbb{Z}_{i}=\{\bm{z}_{i,1},\bm{z}_{i,2},\cdots,\bm{z}_{i,|\mathcal{V}_{i}|}\}$. The first part $\bm{E}$ could be treated as the static representations of elements as it is shared by all the users. The second part $\mathbb{Z}_{i}$ could be seen as the dynamic representations of elements appearing in $\mathcal{V}_{i}$ because it considers both the co-occurrence relationships and the temporal dependency of the elements. We use $\bm{E}_{i}$ to denote the hidden state of user $i$, which is initialized as $\bm{E}$. The most recent state $\bm{E}_{i,I(j)}^{update}$ is achieved by updating the user state $\bm{E}_{i}$ iteratively as follows,

where $I(\cdot)$ is a function that maps element $v_{i,j}$ to its corresponding index in $\bm{E}_{i}$, $\beta_{i,j}$ and $\gamma_{j}$ are the $j$-th dimension of $\bm{\beta}_{i}$ and $\bm{\gamma}$. $\bm{\beta}_{i}\in\mathbb{R}^{m}$ is a indicator vector composed of 0 or 1, where the entry with value 1 means the corresponding element is in $\mathcal{V}_{i}$. $\bm{\gamma}\in\mathbb{R}^{m}$ is the trainable parameter of an updating gate which controls the importance of the static and dynamic representations. In Equation (5), the representations of elements appearing in $\mathcal{V}_{i}$ are updated according to both the static and dynamic information. For the other elements, we just maintain its original static representations.

Finally, the possibilities of all elements appearing in the next-period set could be computed according to the user’s current state,

where $\bm{w}_{o}\in\mathbb{R}^{F}$ and $b_{o}\in\mathbb{R}$ are trainable parameters to provide the final prediction result.

To construct our temporal sets prediction model, we first stack multiple weighted convolutional layers with shared parameters and propagate information of elements on the dynamic graphs to learn set-level element relationship. Then we provide an attention-based temporal dependency learning module to learn the temporal dependency with a complete receptive field, and aggregate the temporal information into a latent representation for each element using the weighted aggregation. In order to enhance the learning capacity of this component, we use multiple heads to identify the most influencing modes, and concatenate the representations of different heads to get a joint representation. Moreover, we employ the gated information fusing component to take in the output of temporal dependency learning module and the embedding matrix to explore the shared patterns in different sequences. Finally, the prediction layer provides the final result.

In the training process, predicting next-period set could be treated as a multi-label learning problem, so we adopt the loss function with $L_{2}$ regularization technique as follows,

where $\bm{W}$ denotes all the trainable parameters in our model, $N$ is the number of training samples, $\lambda$ is a hyperparameter to control the importance of $L_{2}$ regularization, $y_{i,j}$ and $\hat{y}_{i,j}$ denote the $j$-th dimension of the ground truth and the predicted appearing possibility of $j$-th element in the next set of user $u_{i}$. We optimize the proposed model by minimizing Equation (7) until convergence.

We conduct experiments on four real-world datesets:

• •

  TaFeng ²²2https://www.kaggle.com/chiranjivdas09/ta-feng-grocery-dataset: TaFeng is a public dataset which contains four months of shopping transactions at a Chinese grocery store. This dataset was recorded at day-level, and we treat products purchased in the same day by the same customer as a set.

• •

  Dunnhumby-Carbo (DC) ³³3https://www.dunnhumby.com/careers/engineering/sourcefiles: DC contains two years of transactions from households at a retailer which could be available online. Products purchased in the same transaction are treated as a set. We select the transactions during the first two months to conduct experiments because it’s costly to train on the original dataset due to its large scale.

• •

  TaoBao ⁴⁴4https://tianchi.aliyun.com/dataset/dataDetail?dataId=649: TaoBao contains lots of users who have four types of behaviors including clicking, purchasing, adding products to shopping carts and marking products as favor online. We select all purchasing behaviors and treat products bought in the same transaction as a set.

• •

  Tags-Math-Sx (TMS) ⁵⁵5https://math.stackexchange.com: TMS dataset contains the whole history of users in Mathematics Stack Exchange, a stack exchange for mathematics questions. We use the TMS dataset preprocessed by Benson et al. (2018) to do experiments.

For simplicity, we select frequent elements which cover 80% records in each dataset to conduct experiments. Too short sequences are dropped and too long sequences are subtracted. More details about the datasets are summarized in Table 1, where #E/S denotes the average number of elements in each set, #S/U represents the average number of sets for each user.

We compare our model with the following baselines, including both classical and the state-of-the-art methods:

• •

  TOP: It uses the most popular elements appearing in the training set as the prediction for users in the test set.

• •

  PersonalTOP: It sorts the most popular elements that appear in historical sets of a given user, and then recommends them to the user as the prediction result.

• •

  ElementTransfer: ElementTransfer first learns transfer relationships between elements based on adjacent behaviors of a given user. Then it provides elements which are more likely to appear in the next-period based on the last status of the user using the learned transfer relationships.

• •

  DREAM: This method considers both dynamic representations of users and global interactions among sets based on neural networks for next-basket recommendation (Yu et al., 2016). DREAM uses max pooling operations to generate representations of baskets. Then the sequence of baskets is fed into an RNN structure which predicts the next-period basket.

• •

  Sets2Sets: Sets2Sets (Hu and He, 2019) uses the average pooling operation to map sets into structured vectors and designs an encoder-decoder framework to complete multi-period sets prediction based on the attention mechanism. It also takes the repeated patterns in user behaviors into consideration.

To get a comprehensive evaluation of the proposed method, three metrics: Recall, Normalized Discounted Cumulative Gain (NDCG) and Personal Hit Ratio (PHR) are adopted as evaluation metrics.

Recall is widely used in estimating model performance which measures the model’s ability to find all relevant elements. For user $u_{i}$, Recall is calculated by

where $\hat{S}_{i}$ and $S_{i}$ are the predicted top-K elements and the ground truth of user $u_{i}$ respectively, $|S|$ denotes the size of set $S$. We adopt the average recall of all users as a metric.

NDCG is a measure of ranking quality which considers the order of elements in a list. For user $u_{i}$, NDCG is calculated by

where $\delta\left(v,S\right)$ returns 1 when the element $v$ is in the set $S$, otherwise 0. The average NDCG of all users is adopted as another metric.

PHR pays attention to the performance at user level which represents the ratio of users whose predicted sets contain the elements appearing in the ground truth. PHR is calculated by

where $N^{\prime}$ denotes the number of testing samples, $\mathds{1}\left(x\right)$ is an indicator function which returns 1 when $x\geq 0$, otherwise 0.

For evaluation, we generate a ranking list of top-K elements from the output and K is set to 10, 20, 30 and 40 respectively. We divide each dataset into train, validation and test set across users with the ratios of 70%, 10% and 20% to do experiments. After partitioning the data, we train our model on the training data for a fix number of epochs (e.g. 100 epochs), and choose the model which achieves the best performance on the validation set for testing. Adam (Kingma and Ba, 2014) is adopted as the optimizer in our experiment. We utilize batch normalization (Ioffe and Szegedy, 2015) technique between weighted convolutional layers to accelerate the training speed. The learning rate on TaFeng, TaoBao and TMS datasets is set to 0.001, and it is set to 0.005 on DC dataset. We stack 2 weighted convolutional layers and employ 4 attention heads on all four datasets. The hidden dimension $F$ and batch size are set to 32 and 64 respectively. The model is implemented with the PyTorch framework. We make the code and data publicly available on GitHub platform ⁶⁶6Code and data are available at https://github.com/yule-BUAA/DNNTSP..

The comparisons of DNNTSP with other methods on Top-K performance are reported in Table 2. By analyzing the results, some conclusions could be summarized.

Firstly, PersonalTOP achieves competitive or even better performance than other baselines in some cases although it does not consider the temporal dependency. This is because that users tend to interact with some elements repeatedly due to their preferences, which are not affected by the time. PersonalTOP performs better than TOP because it could provide personalized results for different users. TOP gets worse metrics as it always provides the same elements for all users.

Secondly, ElementTransfer performs worse than DREAM as it only considers adjacent temporal dependency, while DREAM focuses on the whole sequence due to RNN structures. It indicates that users’ behaviors are temporally dependent. So learning the temporal dependency from the whole sequence of the users could obtain better prediction performance.

Thirdly, Sets2Sets achieves better performance than other baselines in most cases because it learns temporal dependency by RNNs combined with the attention mechanism, which helps to select the most useful temporal dependencies in the sequence. What’s more, it considers the frequent behaviors of users by modelling the repeated patterns, which also improves the prediction performance.

Finally, the proposed DNNTSP outperforms all other methods significantly in most cases. Compared with TOP and PersonalTOP, DNNTSP learns dynamic temporal dependency in users’ sequential behaviors. Compared with ElementTransfer and DREAM, DNNTSP focuses on the temporal dependency of the whole sequence and leverages attention mechanism to adaptively select the most important temporal dependencies. Compared with Sets2Sets, DNNTSP learns set-level element relationship, which could maintain useful information as much as possible. What’s more, DNNTSP learns the interactions of elements from a global perspective by mining shared patterns in different sequences. We also observe that DNNTSP could not outperform Sets2Sets completely in TMS dataset, especially on the NDCG metric. We infer that the repeated behaviors in TMS dataset are more obvious than that in other datasets, which result in a higher ranking quality. We will investigate this phenomenon in a further step in Section 4.8.

In order to compare our method with baselines more comprehensively, we also show the performance of the proposed model when top-K varies in consecutive values. Due to space limitations, we just show the results on TaFeng dataset. As shown in Figure 4, we can see that DNNTSP outperforms other baselines consistently when the value of K changes from 1 to 40. This indicates that our method could provide more precise predictions without the influence of the capacity of predicted sets.

To investigate the effects of element relationship learning and temporal dependency learning components, we conduct the ablation study by removing the two components manually and comparing the performance with the original DNNTSP.

Specifically, three-fold ablation experiments have been implemented: 1) We remove the Element Relationship Learning component by stacking the representations of appearing elements in the sequence based on the sequence’s length (denoted as DNNTSP w/o ERL), which means that we ignore the relationships between elements and and do not propagate information among elements. 2) We replace the Temporal Dependency Learning component by simply aggregating the sequence of each appearing element using average pooling (denoted as DNNTSP w/o TDL), which means that we do not consider the evolutionary pattern in the sequence and lose some temporal information. 3) Moreover, we remove both the two components simultaneously (denoted as DNNTSP w/o both) to conduct experiments. Experimental results on TaFeng dataset are shown in Figure 5.

From the results, we could conclude that the performance of DNNTSP decreases when any component is abandoned, because the ERL component takes element relationship into consideration and the TDL module learns dynamic temporal dependency from the whole sequence and selects the most important dependencies adaptively. DNNTSP w/o ERL ignores the element relationship and DNNTSP w/o TDL omits the evolution of dynamic changes in the sequence, so they both obtain worse performance. DNNTSP (w/o both) achieves the worst results as it does not consider either the element relationship or temporal dependency in the sequence.

To demonstrate the effectiveness of the gated information fusing component, we train our model on training set with varying sizes. Specifically, we randomly choose data in the original training set by changing the ratio from 10% to 100% with 10% increment each time. Finally, we could generate 10 training sets with different sizes and train the model on each dataset.

Experimental results on TaFeng dataset are shown in Figure 6. From the results, we could observe that our model performs better when the size of training data increases. More importantly, our model is able to achieve competitive performance when it is trained with only forty percent of the training data. This proves that the gated information fusing component helps our model discover the shared patterns in different sequences, and therefore our model could get satisfactory results with only a portion of the training data. The results illustrate that our model is applicable to the scenarios with sparse data.

Since our model could not outperform Sets2Sets in some metrics on the TMS dataset, we conclude that the repeated behaviors have a greater impact on the TMS dataset and the component of modelling such behaviors in Sets2Sets helps Sets2Sets achieve better performance. So we study the effects of modelling the repeated behaviors in temporal sets prediction and use the TMS dataset to conduct experiments. Specifically, we first remove the repeated behaviors modelling component in Sets2Sets and denote the model as Sets2Sets-. Then we incorporate this component into our DNNTSP and denote it as DNNTSP+. Experimental results of the modified models are shown in Table 3.

From the results, we could conclude that in the same condition, the proposed DNNTSP performs better than Sets2Sets. On the one hand, without modelling repeated behaviors, DNNTSP achieves better results than Sets2Sets-, which shows the superiority of DNNTSP over Sets2Sets in temporal sets prediction when no empirical information is added. On the other hand, DNNTSP+ also outperforms Sets2Sets, which proves the effectiveness of modelling the repeated behaviors in temporal sets prediction and also demonstrates that our model is able to achieve the best performance by incorporating the repeated behaviors modelling component.