Exploiting Cross-Session Information for Session-based Recommendation with Graph Neural Networks

The most popular method in recent years for the general recommender system is collaborative filtering (CF), which represents the user interest based on the whole history. For example, the famous shallow method, Matrix Factorization (MF) (Koren et al., 2009) factorizes the whole user-item interaction matrix with latent representation for every user and item. With the prevalence of deep learning, neural networks are widely used. Neural collaborative filtering (NCF) (He et al., 2017; Chen et al., 2019a) proposes to use the multilayer perceptron to approximate the matrix factorization process. More subsequent work extends the incorporation of different deep learning tools, for instance, convolutional neural networks (He et al., 2018), knowledge graph (Wang et al., 2019) and zero-shot learning and domain adaptation (Li et al., 2019b, c). To make use of the text information, Guan et al. (Guan et al., 2019) proposed to use the attention to learn the relative importance of the reviews. These methods all depend on the identification of users and the whole record of interactions for every user. However, for many modern commercial online systems, the user information is anonymous, which leads to the failure of these CF-based algorithms.

The research on the session-based recommender system (SBRS) is a sub-field of RS. Compared with RS, SBRS takes the user’s recent user-item interactions into consideration rather than requiring all historical actions. SBRS is based on the assumption that the recent choice of items can be viewed as the recent preference of a user.

Sequential recommendation is based on the Markov chain model (Shani et al., 2002; Zimdars et al., 2001; Wang et al., 2018b; Chen et al., 2020), which learns the dependency of items of a sequence data to predict the next click. Using probabilistic decision-tree models, Zimdars et al. (Zimdars et al., 2001) proposed to encode the state of the dependency relationships of the item sequential dependency. Shani et al. (Shani et al., 2002) made use of a Markov Decision Process (MDP) to compute the probability of recommendation with the dependency probability between items.

Deep learning models are popular recently with the boom of recurrent neural networks (Hochreiter and Schmidhuber, 1997; Chung et al., 2014; Chen et al., 2019b; Wang et al., 2016; Sun et al., 2019, 2020), which is naturally designed for processing sequential data. Hidasi et al. (Hidasi et al., 2016) proposed the GRU4REC, which applies a multi-layer GRU (Chung et al., 2014) to simply treat the data as time series. Based on the RNN model, some work makes improvements on the architectural choice and the objective function design (Hidasi and Karatzoglou, 2018; Tan et al., 2016). In addition to RNN, Jannach and Ludewig (Jannach and Ludewig, 2017) proposed to use the neighborhood-based method to capture co-occurrence signals. Incorporating content features of items, Tuan and Phuong (Tuan and Phuong, 2017) utilized 3D convolutional neural networks to learn more accurate representations. Wu et al. (Wu and Yan, 2017) propose a list-wise deep neural network model to train a ranking model. Some recent work uses the attention mechanism to avoid the time order. NARM (Li et al., 2017) stacks GRU as the encoder to extract information and then a self-attention layer to assign a weight to each hidden state to sum up as the session embedding. To further alleviate the bias introduced by time series, STAMP (Liu et al., 2018) entirely replaces the recurrent encoder with an attention layer. SR-GNN (Wu et al., 2019) applies a gated graph network (Li et al., 2016) as the item feature encoder and a self-attention layer to aggregate item features together as the session feature. FWSBR (Hwangbo and Kim, 2019) is proposed to integrate the fashion feature to make sustainable session-based recommendation. SSRM (Guo et al., 2019) considers a specific user’s historical sessions and applies the attention mechanism to combine them. Although the attention mechanism can proactively ignore the bias introduced by the time order of interactions, it considers the session as a totally random set.

Cross-session information is considered in SBRS when the user ID is available (Wang et al., 2015; Yu et al., 2016; Bai et al., 2018; Hu et al., 2018; Quadrana et al., 2017). All these methods require the identified user to build connections between sessions. Quadrana et al. (Quadrana et al., 2017) proposed HRNN to apply a recurrent architecture to aggregate the average feature of all sessions from the user’s history. Bai et al. (Bai et al., 2018) proposed ANAM, which uses an attention model to combine different sessions. The user ID is the only linkage between different sessions in these methods. However, there is no record of user ID in many online systems, which makes it impossible to access to other sessions in this way.

In recent years, GNN attracts much interest in the deep learning community. Inspired by the embedding learning method Word2Vec (Mikolov et al., 2013), DeepWalk (Perozzi et al., 2014) learns node embeddings by randomly sampling neighboring nodes and predicting the joint probabilities of these neighbors. With different learning objective functions and sampling strategies, LINE (Tang et al., 2015) and Node2Vec (Grover and Leskovec, 2016) are the most representative algorithms of the unsupervised learning on the graph. Initially, GNN is applied to the simple situation on directed graphs (Gori et al., 2005; Scarselli et al., 2009). In recent years, many GNN methods (Kipf and Welling, 2017; Velickovic et al., 2018; Hamilton et al., 2017; Li et al., 2016; Xu et al., 2019) work under the mechanism that is similar to message passing network (Gilmer et al., 2017) to compute the information flow between nodes via edges. Additionally, the graph level feature representation learning is essential for graph level tasks, for example, graph classification and graph isomorphism (Xu et al., 2019; Li et al., 2019a). Set2Set (Vinyals et al., 2016) assigns each node in the graph a descriptor as the order feature and uses this re-defined order to process all nodes. SortPool (Zhang et al., 2018) sorts the nodes based on their learned feature and uses a normal neural network layer to process the sorted nodes. DiffPool (Ying et al., 2018) designs two sets of GNN for every layer to learn a new dense adjacent matrix for a smaller size of the densely connected graph.

The purpose of an SBRS is to predict the next item that matches the current anonymous user’s preference based on the interactions within the session. In the following, we give out the definition of the SBRS problem.

In an SBRS, there is an item set $\mathcal{V}=\{v_{1},v_{2},v_{3},\ldots,v_{m}\}$, where all items are unique and $m$ denotes the number of items. A session sequence from an anonymous user is defined as an order list $\mathcal{S}=[v_{s,1},v_{s,2},v_{s,3},\ldots,v_{s,n}]$, $v_{s,*}\in\mathcal{V}$. $n$ is the length of the session $\mathcal{S}$, which may contain duplicated items, $v_{s,p}=v_{s,q}$, $p,q<n$. The goal of our model is to take an anonymous session $\mathcal{S}$ and the cross-session information as input, and predict the next item $v_{s,n+1}$ that matches the current anonymous user’s preference.

After obtaining the session graph, a GNN is needed to learn embeddings for nodes in a graph, which is the $\text{WGAT}\times L$ part in Fig. 2. In recent years, some baseline methods on GNN, for example, GCN (Kipf and Welling, 2017) and GAT (Velickovic et al., 2018), are demonstrated to be capable of extracting features of the graph. However, most of them are only well-suited for unweighted and undirected graphs. For the session graph, weighted and directed, these baseline methods cannot be directly applied without losing the information carried by the weighted directed edges. Therefore, a suitable graph convolutional layer is needed to effectively convey information between the nodes in the graph.

In this paper, we propose a weighted graph attentional layer (WGAT), which simultaneously incorporates the edge weight when performing the attention aggregation on neighboring nodes. We describe the forward propagation of WGAT in the following. The information propagation procedures are shown in Fig. 5. Fig. 5(b) shows an example of how a two-layer GNN calculates the final representation of the node $v_{6}$.

The input to a WGAT is a set of node initial features, the item embeddings, $\bm{x}=\{\bm{x}_{0},\bm{x}_{1},\bm{x}_{2},\ldots\bm{x}_{n-1}\}$, $\bm{x}_{i}\in\mathbb{R}^{d}$, where $n$ is the number of nodes in the graph, and $d$ is the dimension of the embedding $\bm{x}_{i}$. After applying the WGAT, a new set of node features, $\bm{x}^{\prime}=\{\bm{x}^{\prime}_{0},\bm{x}^{\prime}_{1},\bm{x}^{\prime}_{2},\ldots\bm{x}^{\prime}_{n-1}\}$, $\bm{x}^{\prime}_{i}\in\mathbb{R}^{d^{\prime}}$, will be given out as the output. Specifically, the input feature vectors $\bm{x}^{0}_{i}$ of the first WGAT layer are generated from an embedding layer, whose input is the one-hot encoding of items,

where Embed is the embedding layer.

To learn the node representation via the complicated item dependency relationships within the graph structure, a self-attention mechanism for every node $i$ is used to aggregate information from its neighboring nodes $\mathcal{N}(i)$, which is defined as the nodes with edges towards the node $i$ (may contain $i$ itself if there is a self-loop edge). Because the size of the session graph is not huge, we can take the entire neighborhood of a node into consideration without any sampling. At the first stage, a self-attention coefficient $e_{ij}$ to determine how importantly the node $j$ will influence the node $i$ is calculated based on $\bm{x}_{i}$, $\bm{x}_{j}$ and $w_{ij}$,

where Att is a mapping $\text{Att}:\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}^{1}\to\mathbb{R}^{1}$ and $\bm{W}$ is a shared parameter which performs linear mapping across all nodes. As a matter of fact, the attention of a node $i$ can extend to every node, which is a special case the same as how STAMP makes the attention of the last node of the sequence. Here we restrict the range of the attention within the first order neighbors of the node $i$ to make use of the inherent structure of the session graph $S$. To compare the importance of different nodes directly, a softmax function is applied to convert the coefficient into a probability form across the neighbors and itself,

The choice of $att$ can be diversified. In our experiments, we use an MLP layer with the parameter $\bm{W}_{att}\in\mathbb{R}^{2d+1}$, followed by a LeakyRelu non-linearity unit with negative input slope $\alpha=0.2$

where $||$ means concatenation of two vectors.

For every node $i$ in $G_{s}$, in a WGAT layer, all attention coefficients of their neighbors can be computed as (6). To utilize these attention coefficients, a linear combination for the corresponding neighbors is applied to update the features of the nodes.

where $\sigma$ is a non-linearity unit and in our experiments, we use the ReLU (Nair and Hinton, 2010).

As suggested in previous work (Velickovic et al., 2018; Vaswani et al., 2017), the multi-head attention can help to stabilize the training of the self-attention layers. Therefore, we apply the multi-head setting for our WGAT.

where $K$ is the number of heads and for every head, there is a different set of parameters. $\Arrowvert$ in (8) stands for the concatenation of all heads. As a result, after the calculation of (8), $\bm{x}^{\prime}_{i}\in\mathbb{R}^{K{d^{\prime}}}$.

Specifically, if we stack multiple WGAT layers, the final nodes feature will be shaped as $\mathbb{R}^{K{d^{\prime}}}$ as well. However, what we expect is $\mathbb{R}^{d^{\prime}}$. Consequently, we calculate the mean over all the heads of the attention results.

Once the forward propagation of multiple WGAT layers has finished, we obtain the final feature vectors of all nodes, which is the item level embeddings. These embeddings will serve as the input of the session embedding computation stage that we detail below.

The purpose of the Mask-Readout function is to generate a representation of the updated BCS graph based on the node features after the forward computation of the GNN layers. The Mask-Readout needs to learn the description of the item dependency relationships to avoid the bias of the time order and the inaccuracy of the self-attention on the last input item. For the convenience, some algorithms use simple permutation invariant operations, for example, $Mean,Max$ or $Sum$ over all node features. Although it is clear that these methods are simple and not going to violate the constraints of the permutation invariance, they can not provide a sufficient model capacity for learning a representative session embedding for the BCS graph. In contrast, Set2Set (Vinyals et al., 2016) is a graph level feature extractor that learns a query vector indicating the order of reading from the memory for an undirected graph. We develop our basic Readout function by modifying this method to suit the setting of the BCS graphs. The computation procedures are as follows:

where $i$ indexes node $i$ in the session graph $G_{s}$, $\bm{q}_{t}$, $\bm{q}_{t}\in\mathbb{R}^{d}$, is a query vector which can be seen as the order to read $\bm{r}_{t}\in\mathbb{R}^{d}$ from the memory and GRU is the gated recurrent unit, which at the first step takes no inputs and at the following steps, takes the former output $\bm{q}^{*}_{t-1}\in\mathbb{R}^{2d}$. $f$ calculates the attention coefficient $e_{i,t}$ between the embedding of every node $\bm{x}_{i}$ and the query vector $\bm{q}_{t}$. $a_{i,t}$ is the probabilistic form of $e_{i,t}$ after applying a softmax function over $e_{i,t}$, which is then used to a linear combination on the node embeddings $\bm{x}_{i}$. The final output $\bm{q}^{*}_{t}$ of one forward computation of the Readout function is the concatenation of $\bm{q}_{t}$ and $\bm{r}_{t}$.

Based on all node embeddings for a session graph, we follow Equation 10$\sim$14 to obtain a graph level embedding that contains a query vector $\bm{q}_{t}$ in addition to the semantic embedding vector $\bm{r}_{t}$. The query vector $\bm{q}_{t}$ controls what to read from the node embeddings, which actually provides an order to process all nodes if we recursively apply the Readout function.

Generally, there is no restriction for the Readout function to calculate over all nodes in the BCS graph. However, based on the purpose of the SBRS, the current session is delegated to reflect the user’s most recent preference rather than sessions from previous time or other users. Therefore, it is necessary to preserve the original session information within the BCS graph when generating the graph embedding. To achieve this goal, the Mask-Readout masks out all nodes out of the range of $G_{\text{BCS}-0}$.

As shown in Fig. 6, the BCS session graph can vary in size with a different choice of the neighborhood. Under this situation, the basic Readout function calculates the session embedding based on all the nodes in the BCS graph, which fails to preserve the relative importance of the current session and other sessions. Therefore, the Mask-Readout function masks all the nodes out of the range of $G_{\text{BCS}-0}$ in the BCS graph to generate a precise session embedding.

Once the graph level embedding $\bm{q}^{*}_{t}$ is obtained, we can use it to make a recommendation by computing a score vector $\hat{\bm{z}}$ for every item over the whole item set $\mathcal{V}$ with their initial embeddings in the matrix form,

where $\bm{W}_{out}\in\mathbb{R}^{d\times 2d}$ is a parameter that performs a linear mapping on the graph embedding $\bm{q}^{*}_{t}$, the $T$ means the transformation on a matrix, and $\bm{X}^{0}$ is from the Equation 3.

For every item in the item set $\mathcal{V}$, we can calculate a recommendation score and combine them together, we obtain a score vector $\hat{\bm{z}}$. Furthermore, we apply a softmax function over $\hat{\bm{z}}$ to transform it into the probability distribution form $\hat{\bm{y}}$,

For the top-K recommendation, it is simple to choose the highest K probabilities over all items based on $\hat{\bm{y}}$.

Since we already have the recommendation probability of a session, we can use the label item $v_{label}$ to train our model with the supervised learning method.

As mentioned above, we formulate the recommendation as a graph level classification problem. Consequently, we apply the multi-class cross entropy loss between $\hat{\bm{y}}$ and the one-hot encoding of $v_{label}$ as the objective function. For a batch of training sessions, we can have

where $l$ is the batch size we use in the optimizer.

In the end, we use the Back-Propagation Through Time (BPTT) algorithm to train the whole FGNN model.

We follow the previous version to choose two representative real world e-commerce datasets i.e., Yoochoose²²2https://2015.recsyschallenge.com/challenge.html and Diginetica, to evaluate our model.

• •

  Yoochoose is used as a challenge dataset for RecSys Challenge 2015. It is obtained by recording click-streams from an e-commerce website within 6 months.

• •

  Diginetica is used as a challenge dataset for CIKM cup 2016. It contains the transaction data which is suitable for session-based recommendation.

For the fairness and the convenience of comparison, we follow (Li et al., 2017; Liu et al., 2018; Wu et al., 2019) to filter out sessions of length 1 and items which occur less than 5 times in each dataset respectively. After the preprocessing step, there are 7,981,580 sessions and 37,483 items remaining in Yoochoose dataset, while 204,771 sessions and 43097 items in Diginetica dataset. Similar to (Wu et al., 2019; Tan et al., 2016), we split a session of length $n$ into $n-1$ partial sessions of length ranging from $2$ to $n$ to augment the datasets. For the partial session of length $i$ in the session $S$, it is defined as $[v_{s,0},\ldots,v_{s,i-1}]$ with the last item $v_{s,i-1}$ as $v_{label}$. Following (Li et al., 2017; Liu et al., 2018; Wu et al., 2019), for Yoochoose dataset, the most recent portions $1/64$ and $1/4$ of the training sequence are used as two split datasets respectively.

In order to prove the advantage of our proposed FGNN model, we compare FGNN with the following representative methods:

• •

  POP always recommends the most popular items in the whole training set, which serves as a strong baseline in some situations although it is simple.

• •

  S-POP always recommends the most popular items for the individual session.

• •

  Item-KNN (Sarwar et al., 2001) computes the similarity of items by the cosine distance of two item vectors in sessions. Regularization is also introduced to avoid the rare high similarities for unvisited items.

• •

  BPR-MF (Rendle et al., 2009) proposes a BPR objective function which utilizes a pairwise ranking loss to train the ranking model. Following (Li et al., 2017), Matrix Factorization is modified to session-based recommendation by using mean latent vectors of items in a session.

• •

  FPMC (Rendle et al., 2010) is a hybrid model for the next-basket recommendation and it achieves state-of-the-art results. For anonymous session-based recommendation, following (Li et al., 2017), we omit the user feature directly because of the unavailability.

• •

  GRU4REC (Hidasi et al., 2016) stacks multiple GRU layers to encode the session sequence into a final state. It also applies a ranking loss to train the model.

• •

  NARM (Li et al., 2017) extends to use an attention layer to combine all of the encoded states of RNN, which enables the model to explicitly emphasize on the more important parts of the input.

• •

  STAMP (Liu et al., 2018) uses attention layers to replace all RNN encoders in previous work to even make the model more powerful by fully relying on the self-attention of the last item in a sequence.

• •

  SR-GNN (Wu et al., 2019) applies a gated graph convolutional layer (Li et al., 2016) to obtain item embeddings, followed by a self-attention of the last item as STAMP does to compute the sequence level embeddings.

For each time, a recommender system can give out a few recommended items and a user would choose the first few of them. To keep the same setting as previous baselines, we mainly choose to use top-20 items to evaluate a recommender system and specifically, two metrics, i.e., R@20 and MRR@20. For more detailed comparison, top-5 and top-10 results are considered as well.

• •

  R@K (Recall calculated over top-K items). The R@K score is the metric that calculates the proportion of test cases which recommends the correct items in a top K position in a ranking list,

  (18)

  $$\text{R@K}=\frac{n_{hit}}{N},$$

  where $N$ represents the number of test sequences $S_{test}$ in the dataset and $n_{hit}$ counts the number that the desired items are in the top K position in the ranking list, which is named the $hit$. R@K is also known as the hit ratio.

• •

  MRR@K (Mean Reciprocal Rank calculated over top-K items). The reciprocal is set to $0$ when the desired items are not in the top K position and the calculation is as follows,

  (19)

  $$\text{MRR@K}=\frac{1}{N}\sum\limits_{v_{label}\in S_{test}}\frac{1}{Rank(v_{label})}.$$

  The MRR is a normalized ranking of $hit$, the higher the score, the better the quality of the recommendation because it indicates a higher ranking position of the desired item.

In the experiments, there are two types of building methods of the session graph. For the basic session graph, we directly make use of all nodes in the session to build the corresponding session graph. On the other hand, for the BCS graph, we sample the neighboring nodes according to the edge weight by restricting the number of a node’s neighbors to 5 in our default setting. The neighboring sample rate will be discussed in Section 5.6. We apply a three-layer WGAT and each with eight heads as our node representation encoder and three processing steps of our Readout function. The size of the feature vector of the item is set to 100 for every layer including the initial embedding layer. All parameters of the FGNN are initialized using a Gaussian distribution with a mean of 0 and a standard deviation of 0.1 except for the GRU unit in the Readout function, which is initialized using the orthogonal initialization (Saxe et al., 2014) because of its performance on RNN-like units. We use the Adam optimizer with the initial learning rate $1e-3$ and the linear schedule decay rate 0.1 for every 3 epochs. The batch size for mini-batch optimization is 100 and we set an L2 regularization to $1e-5$ to avoid overfitting.

To demonstrate the overall performance of FGNN, we compare it with the baseline methods mentioned in Section 5.2 by evaluating their scores of R@20 and MRR@20. The overall results are presented in Table 2 with respect to all baseline methods and our proposed FGNN model. Due to the insufficient memory of hardware, we can not initialize FPMC on Yoochoose1/4 as (Li et al., 2017), which is not reported in Table 2. For more detailed comparisons, in Table 3, we present the results of the most recent state-of-the-art methods for the dataset Yoochoose1/64 when $K=5$ and $10$.

Different methods of generating a graph for model forward computation can result in different levels of cross-session information incorporation. Basically, we can build a session graph for each session graph without any cross-session information. We refer to this setting as FGNN-SG. For the BCS graph setting, we can obtain $0$-hop neighbor situation $G_{\text{BCS}-0}$ with the same structure as the basic session graph but different edge weights. We refer to this setting as FGNN-BCS-0. Similarly, we also have comparisons between different $n$-hop neighbors. Therefore, we conduct experiments with FGNN-BCS-1, FGNN-BCS-2 and FGNN-BCS-3 as well.

To efficiently convey information between items in a session graph, we propose to use WGAT, which suits the situation of the session better. As mentioned above, there are many different GNN layers that can be used to generate node embeddings, e.g., GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018) and gated graph networks (Li et al., 2016; Wu et al., 2019). To prove the usefulness of WGAT, we substitute all three WGAT layers with GCN, GAT and gated graph networks respectively in our model. For GCN and GAT, they both initially work for the unweighted and undirected graph, which is not the same setting as the proposed session graph. To make both of them work on the session graph, we directly convert the session graph into undirected by replacing the originally directed edges with undirected ones, i.e., reverse the source and target nodes of edges. And we simply omit the original weight of edges and set all connections between nodes with the same weight 1. For the other one, Gated graph networks, it can work with the session graph setting in its original form without any modification on the session graph.

Different approaches for generating the session embedding after obtaining the node embeddings stand for different emphasis of the input items. The Readout function proposed in this work learns an inherent order of the nodes by the query vector, which indicates the relatively different impact on the user’s preference along with the item dependency. To prove the superiority of our Readout function, we replace the Readout function with other session embedding generators:

• •

  FGNN-SG-ATT We apply the widely-used self-attention of the last input item. It directly considers the last input item as the short-term reference and all other items as the long-term reference.

• •

  FGNN-SG-GRU To compare the inherent order learned by our Readout function, we use GRU to directly make use of the input session sequence order.

• •

  FGNN-SG-SortPool SortPooling is introduced by Zhang et al. (Zhang et al., 2018) to perform a pooling on graph level by sorting the features of nodes. This sorting can be viewed as a kind of order as well.

In this section, we conduct experiments using the BCS graph setting and compare the experimental results with Mask-Readout or Readout. When the session is converted into a basic session graph or a BCS-$0$ graph, there will be no difference between Mask-Readout and Readout because the choices of nodes are the same for both of them. Overall, the experiments are conducted on BCS-$1$,-$2$ and -$3$ graphs. We use FGNN-BCS-$n$-Readout ($n$ indicates different neighbors) to denote the methods which use the previous Readout function and FGNN-BCS-$n$ to denote the methods which use Mask-Readout.

Fig. 12(a) and 12(b) demonstrate the result of how different graph representation extraction methods perform on all three datasets with the metrics of R@20 and MRR@20. According to the results, it is clear that Mask-Readout outperforms the previous Readout in all situations, which means that Mask-Readout is more suitable for the BCS graph. Compared with Readout, Mask-Readout only cares about the nodes that are in the individual session rather than other sessions. Consequently, Cent-Read prevents the model from losing the session information, which becomes back to the simple dependency information when processing with Readout. Overall, Mask-Readout helps the model to balance the cross-session information and the individual session information.

Take a deeper look at Fig. 12(a) and 12(b), when the Readout is applied, as the neighbors in the BCS graph grow, the performance generally becomes worse. This situation indicates that the more cross-session information is incorporated, the more easily our model will be distracted from the individual session. But when Mask-Readout is used instead of Readout, this phenomenon weakens.