Graph Contextualized Self-Attention Network for Session-based Recommendation

1 Introduction

Recommender systems play an important role in helping users alleviate the problem of information overload and select interesting contents in many applications domains, e.g., ecommerce, music, and social media. Most of existing recommender systems are based on user historical interactions. However, in many application scenarios, user identification may be unknown and there are only user historical actions during an ongoing session. To solve this problem, sessionbased recommendation is proposed to predict the next action (e.g., click on an item) that a user may take based on the sequence of the user's previous behaviors in the current session.

∗ Pengpeng Zhao is the corresponding author. And his email is ppzhao@suda.edu.cn.

Due to its highly practical value, many kinds of approaches for session-based recommendation have been proposed. Markov Chain (MC) is a classic example, which assumes that the next action is based on the previous ones [Rendle et al., 2010]. With such a strong assumption, an independent combination of the past interactions may limit the accuracy of recommendation. Recent studies have highlighted the importance of using recurrent neural network (RNN) in session-based recommender systems and obtained promising results [Zhao et al., 2019]. For instance, Hidasi et al. [Hidasi et al., 2016] proposed to model short-term preferences with GRU (a variant of RNN), and then an improved version [Tan et al., 2016] is proposed to further boost its recommendation performance. Recently, NARM [Li et al., 2017] is designed to capture the user's sequential pattern and main purpose simultaneously by employing a global and local RNN. However, the existing methods usually model single-way transitions between consecutive items and neglect complex transitions among the entire session sequence.

More recently, a new sequential model, Transformer [Vaswani et al., 2017], has achieved state-of-the-art performance and efficiency in various translation tasks. Instead of using recurrence or convolution, Transformer utilizes an encoder-decoder structure composed of stacked self-attention network to draw global dependencies between input and output. Self-attention, as a special attention mechanism, has been widely used to model the sequential data and achieved remarkable results in many applications, e.g., machine translation [Vaswani et al., 2017], sentiment analysis [Lin et al., 2017], and sequential recommendation [Kang and McAuley, 2018; Zhou et al., 2018]. The success of the Transformer model can be attributed to its self-attention network, which takes full account of all signals with a weighted averaging operation. Despite its success, such an operation disperses the distribution of attention, which results in lacking local dependencies over adjacent items and limiting its capacity for learning contextualized representations of items [Liu et al., 2019]. While the local contextual information of adjacent items has been shown that it can enhance the ability of modeling dependencies among neural representations, especially for the attention models [Yang et al., 2018; Liu et al., 2019].

In this work, we propose to strengthen self-attention network through graph neural network (GNN). On the one hand, the strength of self-attention is to capture long-range dependencies by explicitly attending to all the positions. On the other hand, GNN is capable of providing rich local contextual information by encoding edge or node attribute features [Battaglia et al., 2018]. Specifically, we introduce a graph contextual self-attention network, named GC-SAN, for session-based recommendation, which benefits from the complementary strengths of GNN and self-attention. We first construct a directed graph from all historical session sequences. Based on the session graph, GC-SAN is able to capture transitions of neighbor items and generate the latent vectors for all nodes involved in the graph correspondingly. Then we apply the self-attention mechanism to model longrange dependencies regardless of the distance, where session embedding vectors are composed by the latent vectors of all nodes in the graph. Finally, we use the linear weighted sum of the user's global interests and his/her local interests in that session as the embedding vector to predict the probability of clicking on the next item.

The main contributions of this work are summarized as follows.

• To improve the representation of session sequences, we present a novel graph contextual self-attention model based on graph neural network (GC-SAN). GC-SAN utilizes the complementarity between self-attention network and graph neural network to enhance the recommendation performance.
• Graph neural network is used to model local graphstructured dependencies of separated session sequences, while multi-layer self-attention network is designed to obtain contextualized non-local representations.
• We conduct extensive experiments on two benchmark datasets. Our experimental results show the effectiveness and superiority of GC-SAN, comparing with the state-of-the-art methods via comprehensive analysis.

2 RelatedWork

Session-based recommendation is a typical application of recommender systems based on implicit feedback, where users' identifications are unknown, and no explicit preferences (e.g., ratings) but only positive observations (e.g., purchases or clicks) are provided [He et al., 2016]. These positive observations are usually in the form of sequential data obtained by passively tracking users' records over a sequence of time. In this setting, classical CF methods (e.g., matrix factorization) break down because no user profile can be constructed from anonymous history interactions. A natural solution to this problem is the item-to-item recommendation approaches [He et al., 2018]. In the session-based setting, an item-to-item similarity matrix is pre-computed for the available session data using simple item co-occurrence (frequent) patterns [Bonnin and Jannach, 2015]. Sarwar et al. [Sarwar et al., 2001] analyzed different item-based recommendation generation techniques and compared their results with basic k-nearest neighbor approaches. Moreover, to model the sequence relationship between two adjacent actions, Rendle et al. [Rendle et al., 2010] proposed to combine the power of MF and Markov Chain (MC) for next-basket recommendation. Though these methods are proved to be effective and widely employed, they only take into account the most recent click of the session, ignoring the global information of the whole click sequence.

Recently, researchers turn to neural networks and attention-based models for session-based recommender system. For instance, Hidasi et al. [Hidasi et al., 2016] were among the first to explore Gated Recurrent Unit (GRU) as a special form of RNN for the prediction of the next action in a session, and later an improved version [Tan et al., 2016] is proposed to boost its recommendation performance further. Nowadays, Graph Neural Network (GNN) has been proposed to learn the representation for graph structured data [Scarselli et al., 2009; Wang et al., 2019] in the form of RNN, which is broadly applied for the different tasks, e.g., image classification [Marino et al., 2017], script event prediction [Li et al., 2018] and recommender systems [Wu et al., 2018].

On the other hand, several attention-based mechanisms have been introduced across various applications, e.g. natural language processing and computer vision. Standard vanilla attention mechanism has been incorporated into recommender systems [Li et al., 2017; Liu et al., 2018]. More recently, Vaswani et al. [Vaswani et al., 2017] proposed to model the dependencies between words based entirely on self-attention without any recurrence or convolution, which has achieved state-of-the-art performance on machine translation task. Based on the simple and parallelized self-attention mechanism, Kang et al. [Kang and McAuley, 2018] proposed a self-attention based sequential model, which outperforms MC/RNN/RNN-based sequential recommendation methods. Huang et al. [Huang et al., 2018] proposed a unified contextual self-attention network at feature level to capture the polysemy of heterogeneous user behaviors for sequential recommendation.

Most existing sequential recommendation models utilize the self-attention mechanism to capture distant item-item transitions in a sequence and have achieved state-of-the-art performance. However, it is still challenging for establishing complex contextual information between adjacent items. In this paper, we strengthen the self-attention network through graph neural network and meanwhile maintain the model's simplicity and flexibility. To the best of our knowledge, this is the first attempt to complement SAN and GNN for sessionbased recommendation, in which the first one can model the global item-item information of a session and the latter is capable of learning local contextual information by encoding attribute features of constructing graphs.

3 Graph Contextualized Self-Attention Network

In this section, we introduce the proposed contextualized selfattention recommendation model based on graph neural network (GC-SAN). We first formulate the problem of sessionbased recommendation, and then describe the architecture of our model in detail (As shown in Figure 1).

3.1 Problem Statement

Session-based recommendation aims to predict which item a user would like to click next, only based upon his/her current interaction sequence. Here we give a formulation of the session-based recommendation problem as below.

Let V = {v1, v2, ..., v|V |} denote a set of all unique items involved in all sessions. For each anonymous session, a sequence of clicked actions by the user are denoted as S = {s1, s2, ..., sn} in time order, where st ∈ V represents a clicked item of the user at time step t. Formally, our model aims to predict the next possible click (i.e., st+1) for a given prefix of the action sequence truncated at time t, St = {s1, s2, ..., st-1, st} (1 ≤ t < n). To be exact, our model generates a ranking list over all candidate items that may occur in that session. ˆy = {ˆ y1, ˆ y2, ..., y|V |} denotes the output probability for all items, where ˆ yi corresponds to the recommendation score of item vi. Since a recommender typically makes more than one recommendation for the user, thus we choose the top-N items from ˆy for recommendation.

3.2 Dynamic Graph Structure

Graph Construction. The first part of GNN is to a construct meaningful graph from all sessions. Given a session S = {s1, s2, ..., sn}, we treat each item si as a node and (si-1, si) as an edge which represents a user clicks item si after si-1 in the session S. Therefore, each session sequence can be modeled as a directed graph. The graph structure is updated by promoting communication between different nodes. Specifically, let MI ,MO ∈ Rn×n denote weighted connections of outgoing and incoming edges in the session graph, respectively. For example, considering a session S = {s1, s3, s2, s4, s3}, the corresponding graph and the matrix (i.e.,MI and MO ) are shown in Figure2. Since several items may appear in the session sequence repeatedly, we assign each edge with normalized weight, which is calculated as the occurrence of the edge divided by the outdegree of that edge's start node. Note that our model can support various strategies of constructing session graph and generate the corresponding connection matrices. Then we can apply the two weighted connection matrices with graph neural network to capture the local information of the session sequence.

Node Vectors Updating. Next, we present how to obtain latent feature vectors of nodes via graph neural network. We first convert every item v ∈ V into an unified lowdimension latent space and the node vector s ∈ Rd denotes a d-dimensional real-valued latent vector of item v. For each node st at time t in the graph session, given by the connection matricesMI andMO , the information propagation between different nodes can be formalized as:

where WIa , WOa ∈ Rd×d are the parameter matrices. bI , bO ∈ Rd are the bias vectors. MIt ,MOt ∈ R1×n are tth row of each matrix corresponding to node st, respectively. at extracts the contextual information of neighborhoods for node st. Then we take them and the previous state st-1 as input and feed into the graph neural network. Thus, the final output ht of GNN layer is computed as follows.

where Wz,Wr,Wh ∈ R2d×d , Pz, Pr, Ph ∈ Rd×d , are learnable parameters. σ(·) represents the logistic sigmoid function and ⊙ denotes element-wise multiplication. zt, rt are update gate and reset gate, which decide what information to be preserved and discarded, respectively.

3.3 Self-Attention Layers

Self-attention is a special case of the attention mechanism and has been successfully applied in lots of research topics including NLP [Vaswani et al., 2017] and QA [Li et al., 2019]. The self-attention mechanism can draw global dependencies between input and output, and capture item-item transitions across the entire input and output sequence itself without regard to their distances.

Self-Attention Layer. After feeding a session sequence into the graph neural network, we can obtain the latent vectors of all nodes involved in the session graph, i.e., H = [h1, h2, ..., hn]. Next, we feed them into the self-attention layer to better capture the global session preference.

where the projection matrices WQ,WK ,WV ∈ R2d×d .

Point-Wise Feed-Forward Network. After that, we apply two linear transformations with a ReLU activation function to endow the model with nonlinearity and consider interactions between different latent dimensions. However, transmission loss may occur in self-attention operations. Thus we add a residual connection after the feed-forward network, which makes the model much easier to leverage low-layer information inspired by [Vaswani et al., 2017].

where W1 and W2 are d × d matrices, b1 and b2 are ddimensional bias vectors. Moreover, to alleviate overfitting problems in deep neural networks, we apply "Dropout" regularization techniques during training. For simplicity, we define the above whole self-attention mechanism as:

Multi-layer Self-Attention. Recent work shows that different layers capture different types of features. In this work, we investigate which levels of layers benefit most from the features modeling to learn more complex item transitions. The 1-st layer is defined as E(1) = E. The k-th (k > 1) self-attention layer is defined as:

where E(k) ∈ Rn×d is the final output of the multi-layer selfattention network.

3.4 Prediction Layer

After several self-attention blocks that adaptively extract sequential information of sessions, we achieve the long-term self-attentive representation E(k) . To better predict the user's next clicks, we combine the long-term preference and the current interest of the session, and then use this combined embedding as the session representation. For a session S = {s1, s2, ..., sn}, we take the last dimensions of E(k) as the global embedding following [Kang and McAuley, 2018]. The local embedding can be simply defined as the last clicked-item vector, i.e., hn. Then we weight them together as the final session embedding.

where E(k) n ∈ Rd represent n-th row of the matrix. Finally, we predict the next click for each candidate item vi ∈ V given session embedding Sf as follows:

where ˆyi denotes the recommendation probability of item vi to be the next click in session S. Finally, we train our model by minimizing the following objective function:

where y denotes the one-hot encoding vector of the ground truth item, θ is the set of all learnable parameters.

4 Experiments and Analysis

In this section, we first set up the experiment. And then we conduct experiments to answer the following questions:

RQ1: Does the proposed graph contextualized self-attention session-based recommendation model (GC-SAN) achieve state-of-the-art performance?

RQ2: How do the key hyper-parameters affect model performance, such as the weight factor and embedding size ?

4.1 Experimental Setup

Datasets. We study the effectiveness of our proposed approach GC-SAN on two real-world datasets, i.e., Diginetica1 and Retailrocket2 . Diginetica dataset comes from CIKM Cup 2016, where only the transactional data is used in this study. Retailrocket dataset is published by a personalized e-commerce company, which contains six months of user browsing activities. To filter noisy data, we filter out items appearing less than 5 times and then remove all sessions with fewer than 2 items on both datasets. Furthermore, for session-based recommendation, we set the sessions data of last week as the test data, and the remaining for training. Similar to [Tan et al., 2016; Yuan et al., 2019], for a session sequence S = {s1, s2, ..., sn}, we generate the input and corresponding labels ({s1}, s2), ({s1, s2}, s3)...({s1, ..., s(n-1)}, sn) for training and testing on both datasets. After preprocessing, the statistics of the datasets are shown in Table 2.

1 http://cikm2016.cs.iupui.edu/cikm-cup/

2 https://www.kaggle.com/retailrocket/ecommerce-dataset

EvaluationMetrics. To evaluate the recommendation performance of all models, we adopt three common metrics, i.e., Hit Rate (HR@N), Mean Reciprocal Rank (MRR@N) and Normalized Discounted Cumulative Gain (NDCG@N). The former one is an evaluation of unranked retrieval results, while the latter two are evaluations of ranked lists. Here, we consider Top-N (N = {5, 10}) for recommendation.

4.2 Baselines

We consider the following compared methods for performance comparisons:

• Pop is a simple baseline that recommends top rank items based on popularity in training data.
• BPR-MF [Rendle et al., 2009] is the state-of-the-art method for non-sequential recommendation, which optimizes matrix factorization using a pairwise ranking loss.
• IKNN [Sarwar et al., 2001] is a traditional item-to-item model, which recommends items similar to the candidate item within the session based on cosine similarity.
• FPMC 3 [Rendle et al., 2010] is a classic hybrid model combing matrix factorization and first-order Markov chain for next-basket recommendation. Note that in our recommendation problem, each basket is a session.
• GRU4Rec 4 [Hidasi et al., 2016] is a RNN-based deep learning model for session-based recommendation. It utilizes a session-parallel mini-batch training process to model user action sequences.
• STAMP [Liu et al., 2018] is a novel short-termmemory priority model to capture the user's long-term preference from previous clicks and the current interest of the lastclicks in a session.
• SR-GNN 5 [Wu et al., 2018] is recently proposed session-based recommendation model with graph neural

3 http://github.com/khesui/FPMC

4 http://github.com/hidasib/GRU4Rec

5 http://github.com/CRIPAC-DIG/SR-GNN

network, which applies GNN to generate latent vectors of items and then represent each session through traditional attention network.

4.3 Comparisons of Performance

To demonstrate the recommendation performance of our model GC-SAN, we compare it with other state-of-the-art methods (RQ1). The experimental results of all methods on Diginetica and Retailrocket datasets are illustrated in Table1, and we have the following observations.

The non-personalized Popularity-based methods (i.e., Pop) has the most unfavorable performance on both datasets. By profiling users individually and optimizing the pairwise ranking loss function, BPR-MF performs better than Pop. This suggests the importance of personalization in recommendation tasks. IKNN and FPMC achieve better performance than BPR-MF on Diginetica dataset, while BPR-MF outperforms IKNN and FPMC on Retailrocket dataset. In fact, IKNN utilizes the similarity between items in the session and FPMC is based on first-order Markov Chain.

All of the neural network methods, such as GRU4Rec and STAMP, outperform the traditional baselines (e.g., FPMC and IKNN) in nearly all the cases, which verifies the power of deep learning technology in this field. GRU4Rec leverages the recurrent structure with GRU as a special form of RNN to capture the user's general preference, while STAMP improves the short-term memory through the last clicked item. Unsurprisingly, STAMP performs better than GRU4Rec, which indicates the effectiveness of short-term behavior for predicting the next item problem. On the other hand, by modeling every session as a graph and applying graph neural network and the attention mechanism, SR-GNN outperforms all other baselines on both datasets. This further proves the power of neural network in recommender systems.

Compared to SR-GNN, our approach GC-SAN adopts the self-attention mechanism to adaptively assign weights to previous items regardless of their distances in the current session and captures long-range dependencies between items of a session. We combine the long-range self-attention representation and the short-term interest of the last-click in a linear way to generate the final session representation. As we can see, our method achieves the best performance among all the methods on both datasets in terms of HR, MRR, and NDCG. These results demonstrate the efficacy and validity of GCSAN for session-based recommendation.

4.4 Model Analysis and Discussion

In this subsection, we take an in-depth model analysis study, aiming to further understand the framework of GC-SAN (RQ2). Due to the space limit, we only show the analysis results in terms of HR@10 and NDCG@10. We have obtained similar experimental results in terms of other metrics.

Impact of graph neural network. Although we can infer the effectiveness of graph neural network implicitly from Table 1, we would like to verify the contribution of graph neural network in GC-SAN. We remove the graph neural network module from GC-SAN, replace it with a randomly initialized item embedding, and feed into the self-attention layer. Table 3 displays the comparisons between with and without GNN. From Table 1 and Table 3, we find that even without GNN, GC-SAN can still outperform STAMP on Retailrocket dataset, while it was beaten by GRU4Rec on Diginetica dataset. In fact, the maximum session length of Retailrocket dataset is almost four times that of Diginetica dataset. A possible reason is that short sequence lengths can construct more dense session graphs that provide richer contextual information, while the self-attention mechanism performs better with long sequence lengths. This further demonstrates that the self-attention mechanism and graph neural network play important roles in improving recommendation performance.

Impact of weight factor ω. The weight parameter ω controls the contribution of self-attention representation and the last-clicked action. Observing from Figure 3(a), taking only global self-attention dependencies (ω = 1.0) as final session embedding usually achieves a better performance than considering only current interests (ω = 0). Setting ω to a value from 0.4 to 0.8 is more desirable. This indicates that while the self-attention mechanism with graph neural network can adaptively assign weights to focus on long-range dependencies or more recent actions, the short-term interest is also indispensable for improving the recommendation performance.

Impact of the number of self-attention blocks k. As aforementioned, we investigate which levels of self-attention layers benefit most from GC-SAN. Figure 3(b) displays the experimental results of applying different self-attention blocks with k varying from 1 to 6. On both datasets, we can observe that increasing k can boost the performance of GCSAN. However, it achieves the best performance when k is chosen properly and gets worse for a larger k. This may be because using more blocks (k ≥ 4) would make GC-SAN easier to lose low-layer information.

Impact of the embedding size d. In Figure 4, we investigate the effectiveness of the embedding size d ranging from 10 to 120 on both datasets. Among all the baselines, STAMP and SR-GNN perform well and stable. Hence, we use STAMP and SR-GNN as two baselines for ease of comparisons. From figure 4, we can observe that our model GCSAN consistently outperforms STAMP on all latent dimensions. When d is less than a certain value, SR-GNN performs better than GC-SAN. Once this value is exceeded, the performance of GC-SAN still grows and eventually stabilizes with d ≥ 100, while the performance of SR-GNN slightly reduces. This may be because that a relatively small d limits GC-SAN to capture complex transitions between item latent factors, while SR-GNN may suffer from overfitting with a larger d.

5 Conclusion

In this paper, we proposed a graph contextualized selfattention network (GC-SAN) based on graph neural network for session-based recommendation. Specifically, we first constructed directed graphs from anonymous session records and then applied graph neural network to generate new latent vectors for all items, which contained local contextual information of sequences. Next, we used the self-attention network to capture global dependencies between distant position. Finally, we combined the local short-term dynamics (i.e., the last-clicked item) and global self-attended dependencies to represent session sequences in a linear way. Extensive experimental analysis verified that our proposed model GC-SAN consistently outperformed the state-of-the-art methods.

Acknowledgments

This research was partially supported by NSFC (No. 61876117, 61876217, 61872258, 61728205), Major Project of Zhejiang Lab (No. 2019DH0ZX01), Open Program of Key Lab of IIP of CAS (No. IIP2019-1) and PAPD.