一、SR-GNN [2019]

《Session-Based Recommendation with Graph Neural Networks》

1. 随着互联网上信息数量的快速增长，在许多互联网应用中（如搜索、电商、流媒体网站），推荐系统成为帮助用户缓解信息过载问题并选择有趣信息的基础。大多数现有的推荐系统都假设 user profile 和历史行为都被持续地记录。然而，在许多服务中，user id 可能是未知的，并且只有正在进行的 session 期间的用户行为历史可用。因此，建模在一个 session 中有限的行为并生成推荐是非常重要的。相反，在这种情况下，依赖于充足的 user-item 交互的传统推荐方法无法实现很好的推荐。

   这里的 user profile 指的是用户历史行为记录，而不是指的是年龄性别等用户画像。

   由于具备很高的实用价值，人们对这个问题的研究兴趣越来越大，并且已经开发了多种 session-based 的推荐方法。基于马尔科夫链，一些工作根据前一个行为来预测用户的 next action 。在强独立性假设下，历史行为的独立组合（independent combination）限制了预测准确性。

   近年来，大多数研究将 Recurrent Neural Network: RNN 应用于 session-based 的推荐系统，并获得了有前景的结果。

   • 《Session-based recommendations with recurrent neural networks》 首先提出了一种 RNN 方法，然后通过数据增强和考虑用户行为的时间漂移（temporal shift）来增强模型。

   • 最近，NARM 设计了一个全局 RNN 和局部 RNN 推荐器，来同时捕获用户的序列行为（sequential behavior）和主要意图（main purpose）。

   • 类似于 NARM，STAMP 也通过使用简单的 MLP 网络和注意力网络来捕获用户的通用兴趣（general interest）和当前兴趣（current interest）。

   尽管上述方法取得了令人满意的结果并成为 SOTA 的技术，但是它们仍然存在一些局限性。

   • 首先，如果在一个 session 中没有足够的用户行为，那么这些方法难以估计 user representation。

     通常，这些 RNN 方法的 hidden vector被视为 user representation ，然后可以基于这些 representation 来生成推荐，例如，NARM 的全局推荐器。然而，在 session-based 的推荐系统中，session 大多是匿名的而且数量非常多，并且 session 点击中涉及的用户行为通常是有限的。因此很难从每个 session 中准确估计每个用户的 representation 。

   • 其次，之前的工作表明（NARM 和 STAMP ），item transition的模式很重要，可以用作 session-based 推荐中的局部因子，但是这些方法总是建模连续 item 之间的单向转移（singleway transition），而忽略了上下文之间的转移，即 session 中的其它 item。因此，这些方法经常忽略远距离 item 之间的复杂转移。

     RNN 网络仅建模单向转移，而 attention 机制建模全局相关性而忽略了 item 之间的关系。

   为了克服上述限制，论文 《Session-Based Recommendation with Graph Neural Networks》提出了一种新的 Session-based Recommendation with Graph Neural Network: SR-GNN 方法，从而探索 item 之间的丰富转移并生成准确的 item 潜在向量。Graph Neural Network: GNN 被设计用于生成图的 representation。

   最近，GNN 被广泛用于为 natural language processing: NLP 和 computer vision: CV 的应用构建图结构依赖关系，如脚本事件（script event）预测、情景识别（situation recognition）、图像分类。

   对于 session-based 推荐，论文首先从历史 session 序列构建有向图。基于 session graph，GNN 能够捕获 item 的转移并相应地生成准确的 item embedding 向量，这是传统的序列方法（如 MC-based 方法和 RNN-based 方法）所难以揭示的。基于准确的 item embedding 向量，SR-GNN 构造了可靠的 session representation ，并可以推断出 next-click item 。

   SR-GNN 的核心在于 item embedding 的生成。传统的 session-based 推荐方法中，item embedding 是自由变量并随机初始化。在 SR-GNN 推荐方法中，item embedding 是根据 GNN 计算得到的，因此包含了 item 之间的转移关系。

   能否仅仅依赖于 GNN 来建模 session-based 推荐？读者认为是不可行的。因为 GNN 无法建模序列信息，而序列信息（尤其是 last click item）对于 session-based 推荐至关重要。

   下图说明了所提出的 SR-GNN 方法的工作流程。

   • 首先，所有 session序列都被建模为有向的 session graph，其中每个 session 序列都可以视为一个子图。

     也可以将所有 session 序列建模为一张大的图，而不是每个 session 一个 session graph。但是论文在实验部分对比了这两种方式的效果，实验表明：每个 session 一个 session graph 的效果更好。因为前者（建模为一张大图）会显著影响当前 session 的完整性。

   • 然后，每个 session graph 依次被处理，并且可以通过 gated graph neural network: GGNN 来获得每个子图中涉及的所有节点的潜在向量。

   • 之后，我们将每个 session 表达为该 session 中该用户的全局偏好（global preference）和当前兴趣 （current interest）的组合，其中这些全局 session embedding 向量和局部 session embedding 向量都由节点的潜在向量组成。

     session embedding 的计算方式类似于 STAMP ，其中全局 session embedding 向量通过注意力机制计算得到，局部session embedding 向量就是 last click item 的 embedding 向量。

   • 最后，对于每个 session，我们预测每个 item 成为 next click 的概率。

   

   论文在真实世界的代表性数据集上进行了大量实验，实验结果证明了所提出方法的有效性并达到了 SOTA。

   论文主要贡献总结如下：

   • 论文将独立的 session 序列建模为图结构化数据，并使用 GNN 来捕获复杂的 item transistion。据作者所知，该方法提出了在 session-based 推荐场景中建模的新视角。

   • 为了生成 session-based 推荐，论文不依赖于 user representation 而是使用 session representation，它可以仅基于每个单一 session 中涉及的 item 的潜在向量来获得。

   • 在真实世界数据集上进行的大量实验表明，SR-GNN 显著优于 SOTA 的方法。

2. 相关工作：这里我们回顾了 session-based 推荐系统的一些相关工作，包括：传统方法、基于马尔科夫链的序列方法、RNN-based 方法。然后我们介绍了图上的神经网络。

   • 传统的推荐方法：

     • 矩阵分解是推荐系统的一种通用方法。矩阵分解的基本目标是将 user-item 评分矩阵分解为两个低秩矩阵，每个矩阵代表用户潜在因子或 item 潜在因子。它不太适合 session-based 推荐，因为用户偏好仅由一些 positive 点击来提供。

     • item-based 邻域方法是一种自然的解决方案，其中 item 相似性是根据同一 session 中的 item co-occurrence 来计算的。这些方法难以考虑 item 的顺序，并且仅基于 the last click 来生成预测。

     • 然后人们提出了基于马尔科夫链的序列推荐方法，该方法根据用户的前一个行为来预测 next action 。

       • 《An mdp-based recommender system》 将推荐生成视为序列优化问题，并采用马尔科夫决策过程（Markov decision process: MDP）来解决该问题。

       • 通过对用户的个性化概率转移矩阵进行分解，FPMC 对每两次相邻点击之间的序列行为进行建模，并为每个序列提供更准确的预测。

       然而，基于马尔科夫链的模型的主要缺点是：它们独立地组合了历史行为（ combine past components independently）。这种独立性假设太强，从而限制了预测的准确性。

   • 基于深度学习的方法：最近，一些基于神经网络的预测模型，尤其是 language model 被人们提出。在众多 language model 中，recurrent neural network: RNN 在句子建模方面是最成功的模型，并且已被广泛应用于各种自然语言处理任务，例如机器翻译、对话机器人（conversation machine）、图像字幕生成（image caption）。RNN 也成功应用于许多 application，例如序列点击预测、位置预测（location prediction）、以及 next basket 推荐。

     对于 session-based 推荐，《Session-based recommendations with recurrent neural networks》 提出了 RNN 的方法，然后《Parallel recurrent neural network architectures for feature-rich session-based recommendations》扩展到具有并行 RNN 的架构，该架构可以根据被点击的 item 及其特征来建模 session 。此后，人们基于这些 RNN 方法提出了一些工作。

     • 《Improved recurrent neural networks for session-based recommendations》 通过使用适当的数据增强技术并考虑用户行为的时间漂移（temporal shift）来提高 RNN 模型的性能。

     • 《When recurrent neural networks meet the neighborhood for session-based recommendation》 将 RNN 方法和 neighborhood-based 方法结合起来，从而混合序列模式和共现信号（ co-occurrence signal ）。

     • 《3d convolutional networks for session-based recommendation with content features》 将 session 点击与 item 描述和 item 类别等内容特征相结合，通过使用三维卷积神经网络生成推荐。

     • 此外，《Session-aware information embedding for e-commerce product recommendation》 通过 list-wise 的深度神经网络来建模每个 session 内的有限用户行为，并使用一个 list-wise 的 ranking model 来为每个 session 生成推荐。

     • 此外，具有一个 encoder-decoder 架构的神经注意力推荐机（neural attentive recommendation machine: NARM） 采用 RNN 上的注意力机制来捕获用户的序列行为特征和主要意图。

     • 然后，《Stamp:Short-term attention/memory priority model for session-based recommendation》 提出了一种使用简单 MLP 网络和注意力网络的 short-term attention priority model ，即 STAMP ，从而有效地捕获用户的通用兴趣和当前兴趣。

   • 图上的神经网络：如今，神经网络已被用于生成图结构化数据（如社交网络、知识图谱）的 representation。

     扩展自word2vec 的无监督算法 DeepWalk 旨在基于随机游走来学习图节点的 representation。继 DeepWalk 之后，无监督网络嵌入算法 LINE 和 node2vec 是最具代表性的方法。

     另一方面，经典的神经网络 CNN 和 RNN 也部署在图结构数据上。

     • 《Convolutional networks on graphs for learning molecular fingerprints》 引入了一个卷积神经网络，它直接对任意大小和形状的图进行操作。

     • 《Semi-supervised classification with graph convolutional networks》 是一种可扩展的方法，通过谱图卷积的局部近似来选择卷积架构。它是一种有效的变体，也可以直接对图进行操作。

     但是，这些方法仅能在无向图上实现。

     先前，人们提出了 《The graph neural network model》来操作有向图。作为 GNN 的修改，《Gatedgraph sequence neural networks》 提出了gated GNN 来使用 GRU 并采用 back-propagation through time: BPTT 来计算梯度。

     最近，GNN 被广泛应用于不同的任务，例如脚本事件预测、情景识别、图像分类。

1.1 模型

1. 在这里我们介绍了所提出的 SR-GNN，它将图神经网络应用于 session-based 的推荐。我们首先形式化问题，然后解释如何从 session 构建图，最后描述 SR-GNN 方法。

2. 形式化问题：session-based 推荐旨在预测用户接下来会点击哪个 item，仅仅基于用户当前的序列 session 数据，而无需访问用户的长期历史行为数据。这里我们给出该问题的形式化（formulation）如下。

   在 session-based 的推荐中，令 $\mathcal{V}=\{v_1,v_2,\cdots ,v_m\}$$\mathcal V=\{v_1,v_2,\cdots,v_m\}$ 表示由所有 session 中涉及的所有 unique item 组成的集合。一个匿名 session 序列 $s$$s$ 可以表述为根据时间戳排序的一个列表 $s=[v_{s_1},v_{s_2},\cdots ,v_{s_n}]$$s=[v_{s_1},v_{s_2},\cdots,v_{s_n}]$ ，其中 $v_{s_i}\in \mathcal{V}$$v_{s_i}\in \mathcal V$ 表示用户在 session $s$$s$ 中点击的第 $i$$i$ 个 item 。session-based 推荐的目标是预测 next click ，即针对 session $s$$s$ 预测 sequence label $v_{s_{n+1}}$$v_{s_{n+1}}$ 。

   在 session-based 的推荐模型下，对于 session $s$$s$ ，我们输出所有可能 item 的概率 $\widehat{\overrightarrow{\mathbf{y}}}$$\hat{\mathbf{\vec y}}$ ，其中 $\widehat{\overrightarrow{\mathbf{y}}}$$\hat{\mathbf{\vec y}}$ 的元素值是相应 item 的推荐分。 $\widehat{\overrightarrow{\mathbf{y}}}$$\hat{\mathbf{\vec y}}$ 中的 top-K 取值的 item 就是被推荐的候选 item 。

3. 构建 session graph：每个 session 序列 $s$$s$ 可以建模为有向图 ${\mathcal{G}}_s=({\mathcal{V}}_s,{\mathcal{E}}_s)$$\mathcal G_s = (\mathcal V_s,\mathcal E_s)$ 。在这个 session graph 中，每个节点代表一个 item $v_{s_i}\in \mathcal{V}$$v_{s_i}\in \mathcal V$ 。每条边 $(v_{s_{i-1}},v_{s_i})\in {\mathcal{E}}_s$$(v_{s_{i-1}},v_{s_i}) \in \mathcal E_s$ 意味着用户在 session $s$$s$ 中点击item $v_{s_{i-1}}$$v_{s_{i-1}}$ 之后紧接着点击了 item $v_{s_i}$$v_{s_i}$ 。

   由于序列中可能重复出现多个 item，我们为每条边分配一个归一化的权重，权重的计算方法是：边的出现次数除以该边的起始节点的出度（ out degree）。

   我们将每个 item $v\in \mathcal{V}$$v \in \mathcal V$ 嵌入到一个统一的 embedding 空间中，节点向量 $\overrightarrow{\mathbf{v}}\in {\mathbb{R}}^d$$\mathbf{\vec v}\in \mathbb R^d$ 表示通过 GNN 学到的 item $v$$v$ 的潜在向量，其中 $d$$d$ 是维度。基于节点向量，每个 session $s$$s$ 可以由一个 embedding 向量 $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ 表达，其中该向量由该图中使用的节点向量来生成。

1.1.1 学习 Item Embedding

1. 然后我们介绍了如何通过 GNN 获得节点的潜在向量。普通的 GNN 由《The graph neural network model》 提出，它扩展了神经网络方法从而用于处理图结构数据。《Gated graph sequence neural networks》 进一步引入门控循环单元（gated recurrent unit）并提出 gated GNN 。GNN 非常适合 session-based 的推荐，因为它可以在考虑丰富的节点链接的情况下自动抽取 session graph 的特征。

2. 我们首先演示 session graph 中节点向量的学习过程。形式上，对于图 ${\mathcal{G}}_s$$\mathcal G_s$ 的节点 $v_{s_i}$$v_{s_i}$ ，更新函数为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{a}}}_{s_i}^{(t)}={\mathbf{A}}_{s,i:}{[{\overrightarrow{\mathbf{v}}}_{s_1}^{(t-1)},\cdots ,{\overrightarrow{\mathbf{v}}}_{s_n}^{(t-1)}]}^{\mathrm{\top }}\mathbf{H}+\overrightarrow{\mathbf{b}}\in {\mathbb{R}}^d\\ {\overrightarrow{\mathbf{z}}}_{s_i}^{(t)}=\sigma ({\mathbf{W}}_z{\overrightarrow{\mathbf{a}}}_{s_i}^{(t)}+{\mathbf{U}}_z{\overrightarrow{\mathbf{v}}}_{s_i}^{(t-1)})\in {\mathbb{R}}^d\\ {\overrightarrow{\mathbf{r}}}_{s_i}^{(t)}=\sigma ({\mathbf{W}}_r{\overrightarrow{\mathbf{a}}}_{s_i}^{(t)}+{\mathbf{U}}_r{\overrightarrow{\mathbf{v}}}_{s_i}^{(t-1)})\in {\mathbb{R}}^d\\ {\widetilde{\overrightarrow{\mathbf{v}}}}_{s_i}^{(t)}=\tanh ({\mathbf{W}}_o{\overrightarrow{\mathbf{a}}}_{s_i}^{(t)}+{\mathbf{U}}_o({\overrightarrow{\mathbf{r}}}_{s_i}^{(t)}\odot {\overrightarrow{\mathbf{v}}}_{s_i}^{(t-1)}))\in {\mathbb{R}}^d\\ {\overrightarrow{\mathbf{v}}}_{s_i}^{(t)}=(1-{\overrightarrow{\mathbf{z}}}_{s_i}^{(t)})\odot {\overrightarrow{\mathbf{v}}}_{s_i}^{(t-1)}+{\overrightarrow{\mathbf{z}}}_{s_i}^{(t)}\odot {\widetilde{\overrightarrow{\mathbf{v}}}}_{s_i}^{(t)}\in {\mathbb{R}}^d\end{array}$$

   其中：

   • $[{\overrightarrow{\mathbf{v}}}_{s_1}^{(t-1)},\cdots ,{\overrightarrow{\mathbf{v}}}_{s_n}^{(t-1)}]\in {\mathbb{R}}^{d\times n}$$\left[\mathbf{\vec v}_{s_1}^{(t-1)},\cdots,\mathbf{\vec v}_{s_n}^{(t-1)}\right]\in \mathbb R^{d\times n}$ 为 session $s$$s$ 中所有节点的 node vector 。

   • ${\mathbf{A}}_s\in {\mathbb{R}}^{n\times 2n}$$\mathbf A_s\in \mathbb R^{n\times 2n}$ 为 session graph 的connection matrix ，它决定了 graph 中节点之间如何相互通信。${\mathbf{A}}_{s,i:}\in {\mathbb{R}}^{1\times 2n}$$\mathbf A_{s,i:}\in \mathbb R^{1\times 2n}$ 为 ${\mathbf{A}}_s$$\mathbf A_s$ 中对应于节点 $v_{s,i}$$v_{s,i}$ 的那一行。

   • $\mathbf{H}\in {\mathbb{R}}^{2d\times d}$$\mathbf H\in \mathbb R^{2d\times d}$ 为投影矩阵，$\overrightarrow{\mathbf{b}}\in {\mathbb{R}}^d$$\mathbf{\vec b}\in \mathbb R^d$ 为偏置向量。

   • ${\overrightarrow{\mathbf{z}}}_{s_i}\in {\mathbb{R}}^d$$\mathbf{\vec z}_{s_i}\in \mathbb R^d$ 为复位门 （reset gate），${\overrightarrow{\mathbf{r}}}_{s_i}\in {\mathbb{R}}^d$$\mathbf{\vec r}_{s_i} \in \mathbb R^d$ 为更新门 （update gate），${\overrightarrow{\mathbf{v}}}_{s_i}\in {\mathbb{R}}^d$$\mathbf{\vec v}_{s_i}\in \mathbb R^d$ 为节点 $v_{s_i}$$v_{s_i}$ 的潜在向量。

   • ${\mathbf{W}}_z,{\mathbf{U}}_z,{\mathbf{W}}_r,{\mathbf{U}}_r,{\mathbf{W}}_o,{\mathbf{U}}_o\in {\mathbb{R}}^{d\times d}$$\mathbf W_z,\mathbf U_z,\mathbf W_r,\mathbf U_r,\mathbf W_o,\mathbf U_o\in \mathbb R^{d\times d}$ 为投影矩阵。

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数，$\odot$$\odot$ 为 逐元素乘法。

   这里 ${\mathbf{A}}_s$$\mathbf A_s$ 定义为两个邻接矩阵 ${\mathbf{A}}_s^{\text{(out)}}$$\mathbf A_s^\text{(out)}$ 和 ${\mathbf{A}}_s^{\text{(in)}}$$\mathbf A_s^\text{(in)}$ ，分别对应于 session graph 中出边（ outgoing edge ）的邻接矩阵和入边 （incoming edge）的邻接矩阵。例如，考虑一个 session $s=[v_1,v_2,v_3,v_2,v_4]$$s=[v_1,v_2,v_3,v_2,v_4]$ ，对应的图 ${\mathcal{G}}_s$$\mathcal G_s$ 和矩阵如下图所示。

   对于矩阵 $\mathbf{B}\in {\mathbb{R}}^{n\times d}$$\mathbf B\in \mathbb R^{n\times d}$，${\mathbf{A}}_s\mathbf{B}$$\mathbf A_s \mathbf B$ 的矩阵乘法其实等价于：${\mathbf{A}}_s\mathbf{B}=[{\mathbf{A}}_s^{\text{(out)}}\mathbf{B},{\mathbf{A}}_s^{\text{(in)}}\mathbf{B}]\in {\mathbb{R}}^{n\times 2d}$$\mathbf A_s\mathbf B = \left[\mathbf A_s^\text{(out)} \mathbf B,\mathbf A_s^\text{(in)}\mathbf B\right]\in \mathbb R^{n\times 2d}$ 。

   

   注意， SR-GNN 可以为各种类型的 session graph 支持不同的connection matrix ${\mathbf{A}}_s$$\mathbf A_s$ 。如果使用不同的 session graph 的构建策略，那么connection matrix ${\mathbf{A}}_s$$\mathbf A_s$ 将会相应改变。此外，当存在节点的内容特征，如描述信息和类别（categorical）信息时，该方法可以进一步推广。具体而言，我们可以将节点的内容特征和节点向量拼接起来从而处理这些内容特征信息。

3. 对于每个 session graph ${\mathcal{G}}_s$$\mathcal G_s$ ，GGNN 同时处理所有节点。${\overrightarrow{\mathbf{a}}}_{s_i}^{(t)}$$\mathbf{\vec a}_{s_i}^{(t)}$ 用于在矩阵 ${\mathbf{A}}_s$$\mathbf A_s$ 给出的限制之下，不同节点之间的信息传播。具体而言：

   • 首先，它抽取邻域的潜在向量并将它们作为 input 馈入到 GNN 中。

   • 然后，更新门和复位门分别决定保留哪些信息、丢弃哪些信息。

   • 之后，我们通过前一个状态、当前状态、复位门来构造候选状态。

   • 最后，在更新门的控制下，final state 是前一个隐状态和当前候选状态的组合。

   在更新 session graph 中的所有节点直到收敛之后，我们可以获得 final 的节点向量。

   这里需要迭代 session graph 直到达到不动点 fixed point。然而，可以采用 GraphSage, Semi-GCN 等方法，这些方法无需达到不动点，只需要迭代 $K$$K$ 次，$K$$K$ 为一个超参数。

1.1.2 生成 Session Embedding

1. 之前的 session-based 的推荐方法总是假设每个 session 存在用户的 distinct latent representation 。相反， SR-GNN 方法不对该向量做任何假设。在 SR-GNN 中，session 直接由该 session 中涉及的节点来表达。为了更好地预测用户的 next click ，SR-GNN 将 session 的长期偏好和当前兴趣相结合，并将这种组合的 embedding 作为 session embedding 。

   引入 user embedding 需要直到 user id。而在 session-based 推荐场景之下，通常是不知道 user id 的，即匿名 session 。

2. 在将所有 session graph 输入 GGNN 之后，我们获得了所有节点的向量。然后，为了将每个 session 表达为一个 embedding 向量 $\overrightarrow{\mathbf{s}}\in {\mathbb{R}}^d$$\mathbf{\vec s}\in \mathbb R^d$ ：

   • 我们首先考虑 session $s$$s$ 的局部 embedding ${\overrightarrow{\mathbf{s}}}_l$$\mathbf{\vec s}_l$ 。对于 session $s=[v_{s_1},v_{s_2},\cdots ,v_{s_n}]$$s=[v_{s_1},v_{s_2},\cdots,v_{s_n}]$ ，局部 embedding 可以简单地定义为 last-clicked item 的 embedding ，即：${\overrightarrow{\mathbf{s}}}_l={\overrightarrow{\mathbf{v}}}_{s_n}$$\mathbf{\vec s}_l = \mathbf{\vec v}_{s_n}$ 。

   • 然后，我们通过聚合所有节点向量来考虑 session graph ${\mathcal{G}}_s$$\mathcal G_s$ 的全局 embedding ${\overrightarrow{\mathbf{s}}}_g$$\mathbf{\vec s}_g$ 。考虑到这些 embedding 中的信息可能具有不同 level 的优先级，我们进一步采用 soft-attention 机制来更好地表达全局 session 偏（ global session preference）：

     $$\begin{array}{c}{\alpha }_i={\overrightarrow{\mathbf{q}}}^{\mathrm{\top }}\sigma ({\mathbf{W}}_1{\overrightarrow{\mathbf{v}}}_{s_n}+{\mathbf{W}}_2{\overrightarrow{\mathbf{v}}}_{s_i}+\overrightarrow{\mathbf{c}})\\ {\overrightarrow{\mathbf{s}}}_g=\sum _{i=1}^n{\alpha }_i{\overrightarrow{\mathbf{v}}}_{s_i}\end{array}$$

     其中：

     • $\overrightarrow{\mathbf{q}}\in {\mathbb{R}}^d$$\mathbf{\vec q}\in \mathbb R^d$ 为 attention 的参数向量。

     • ${\mathbf{W}}_1,{\mathbf{W}}_2\in {\mathbb{R}}^{d\times d}$$\mathbf W_1,\mathbf W_2\in \mathbb R^{d\times d}$ 为投影矩阵，$\overrightarrow{\mathbf{c}}\in {\mathbb{R}}^d$$\mathbf{\vec c}\in \mathbb R^d$ 为偏置向量。

     这里将局部 embedding ${\overrightarrow{\mathbf{s}}}_l$$\mathbf{\vec s}_l$ 作为注意力机制的 query 向量。

   • 最后，我们通过对局部 embedding 向量和全局 embedding 向量拼接之后的线性变换来计算混合 embedding 向量 ${\overrightarrow{\mathbf{s}}}_h$$\mathbf{\vec s}_h$：

     $${\overrightarrow{\mathbf{s}}}_h={\mathbf{W}}_3[{\overrightarrow{\mathbf{s}}}_l,{\overrightarrow{\mathbf{s}}}_g]$$

     其中：${\mathbf{W}}_3\in {\mathbb{R}}^{d\times 2d}$$\mathbf W_3\in \mathbb R^{d\times 2d}$ 为投影矩阵。

     这里对局部 embedding 向量和全局 embedding 向量进行线性组合，组合权重由模型自动学到。

1.1.3 生成推荐以及模型训练

1. 在获得每个 session 的 embedding 之后，对于每个候选 item $v_i\in \mathcal{V}$$v_i\in \mathcal V$ ，我们将其 embeddign ${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec v}_i\in \mathbb R^d$ 乘以 session representation ${\overrightarrow{\mathbf{s}}}_h$$\mathbf{\vec s}_h$ 从而得到候选 item $v_i$$v_i$ 的推荐分，即：

   $${\hat{z}}_i={\overrightarrow{\mathbf{s}}}_h^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_i$$

   然后我们应用一个 softmax 函数来得到模型的输出向量 $\widehat{\overrightarrow{\mathbf{y}}}$$\hat{\mathbf{\vec y}}$：

   $$\widehat{\overrightarrow{\mathbf{y}}}=\text{softmax}\left(\widehat{\overrightarrow{\mathbf{z}}}\right)$$

   其中：$\widehat{\overrightarrow{\mathbf{z}}}\in {\mathbb{R}}^m$$\hat{\mathbf{\vec z}}\in \mathbb R^m$ 表示所有候选 item 的推荐分，$\widehat{\overrightarrow{\mathbf{y}}}\in {\mathbb{R}}^m$$\hat{\mathbf{\vec y}}\in \mathbb R^m$ 表示这些候选 item 作为 session $s$$s$ 的 next click 的概率。

2. 对于每个 session graph，损失函数定义为预测值和 ground truth 的交叉熵。即：

   $$\mathcal{L}\left(\widehat{\overrightarrow{\mathbf{y}}}\right)=-\sum _{i=1}^m[y_i\log {\hat{y}}_i+(1-y_i)\log (1-{\hat{y}}_i)]$$

   其中：$\overrightarrow{\mathbf{y}}$$\mathbf{\vec y}$ 为 ground truth，$y_i$$y_i$ 为 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 的第 $i$$i$ 个元素。

   最后，我们使用时间反向传播 Back-Propagation Through Time: BPTT 算法来训练所提出的 SR-GNN 模型。注意。在 session-based 的推荐场景中，大多数 session 的长度相对较短。因此，建议选择相对较少的训练 step 从而防止过拟合。

1.2 实验

1. 数据集：

   • Yoochoose：来自 RecSys Challenge 2015 ，包含一个电商网站 6 个月内的用户点击流（ stream of user clicks）。

   • Diginetica：来自于 CIKM Cup 2016 ，这里仅使用交易数据。

   为了公平比较，遵从 NARM 和 STAMP，我们过滤掉所有长度为 1 的 session 以及出现频次少于 5 次的 item 。Yoochoose 数据集剩下 7981580 个 session 和 37483 个 item，而 Diginetica 数据集剩下 204771 个 session 和 43097 个 item 。

   对于 Yoochoose我们将最后几天的 session 设为测试集，对于 Diginetiva 我们将最后几周的 session 设为测试集。遵从NARM 和 STAMP，我们还使用了 Yoochoose 训练序列的最近 1/64 和 1/4 。

   此外，类似于 《Improved recurrent neural networks for session-based recommendations》，我们通过拆分 input 序列来生成序列和对应的 label 。具体而言，对于 session 序列 $s=[v_{s_1},v_{s_2},\cdots ,v_{s_n}]$$s=[v_{s_1},v_{s_2},\cdots,v_{s_n}]$ ，我们生成 input 和相应的 label 为：$(\{v_{s_1}\},v_{s_2}),(\{v_{s_1},v_{s_2}\},v_{s_3}),\cdots ,(\{v_{s_1},v_{s_2},\cdots ,v_{s_{n-1}}\},v_{s_n})$$(\{v_{s_1}\},v_{s_2}),(\{v_{s_1},v_{s_2}\},v_{s_3}),\cdots,(\{v_{s_1},v_{s_2},\cdots,v_{s_{n-1}}\},v_{s_n})$ 用于训练和测试。

   数据集的统计数据如下表所示。

   

2. baseline 方法：

   • POP 和 S-POP：分别推荐训练集和当前 session 中的 top-N 流行的 item 。

   • Item-KNN：推荐与 session 中先前点击的 item 相似的 item ，其中相似性定义为 session 向量之间的余弦相似度。

     session 向量：一个 $N$$N$ 维向量，$N$$N$ 为 session 数量。如果 item 在第 $i$$i$ 个 session 中出现，那么该向量的第 $i$$i$ 个元素为 1，否则为 0 。

   • BPR-MF：通过随机梯度下降优化 pairwise 的排序目标函数。

   • FPMC：一种基于马尔科夫链的序列预测方法。

   • GRU4REC：使用 RNN 为 session-based 推荐来建模用户序列。

   • NARM：采用带注意力机制的 RNN 来捕获用户的主要意图和序列行为。

   • STAMP：捕获用户对当前 session 的通用兴趣（ general interest）、以及 last click 的当前兴趣（ current interest）。

3. 评估指标：

   • P@20 （Precision)）：一个广泛应用的准确性指标，它代表了 top 20 个 item 中，正确推荐 item 的比例。

   • MRR@20 （Mean Reciprocal Rank）：是正确推荐的 item 的排名倒数（reciprocal rank ）的均值。当排名差于 20 时，排名倒数置为零。MRR 指标考虑推荐的 order，其中 MRR 值大则表示正确的推荐排在 ranking list 的头部。

4. 实验配置：

   • 遵从之前的方法（NARM 和 STAMP），我们将两个数据集上的潜在向量维度设置为 $d=100$$d=100$ 。

   • 此外，我们在验证集上选择其它超参数，其中验证集是训练集的随机 10% 子集。

   • 所有参数均使用均值为零、标准差为 0.1 的高斯分布进行初始化。

   • 我们使用 mini-batch 的 Adam 优化器，其中学习率设置为 0.001 ，每 3 个 epoch 之后将衰减 0.1 。

   • 此外，mini-batch size 设为 100，L2 正则化系数设为 ${10}^{-5}$$10^{-5}$ 。

5. 和 baseline 的比较：为了展示所提出模型的整体性能，我们将SR-GNN 与其它 SOTA 的 session-based 的推荐方法进行比较，比较结果如下表所示，其中最佳结果以粗体突出显示。注意，与《Neural attentive session-based recommendation》 一样，由于初始化 FPMC 的内存不足，这里没有报告 Yoochoose 1/4 上的性能。

   • SR-GNN 将分离（separated）的 session 序列聚合为图结构数据。在这个模型中，我们共同考虑全局 session 偏好以及局部兴趣。根据实验，很明显，所提出的 SR-GNN 方法在 P@20 和 MRR@20 指标上在所有三个数据集上都实现了最佳性能。这验证了 SR-GNN 的有效性。

   • POP, S-POP 等传统算法的性能相对较差。这种简单的模型仅基于重复的共现 item、或者连续 item 进行推荐，这在 session-based 推荐场景中是有问题的。

     即便如此，S-POP 的表现仍然优于 POP, BPR-MF, FPMC 等竞争对手，这证明了 session 上下文信息（session contextual information）的重要性。

     Item-KNN 比基于马尔科夫链的 FPMC 取得了更好的结果。注意，Item-KNN 仅利用 item 之间的相似性，而不考虑序列信息。这表明传统的基于马尔科夫链的方法主要依赖的假设是不现实的，这个假设是：successive items 的独立性。

   • 基于神经网络的方法（如 NARM 和 STAMP）优于传统方法，这展示了在推荐领域应用深度学习的能力。短期/长期记忆模型，如 GRU4REC 和 NARM，使用循环单元来捕获用户的通用兴趣（general interest），而 STAMP 通过利用 last-click item 来改善短期记忆（short-term memory）。这些方法显式地建模用户的全局行为偏好，并考虑用户的 previous actions 和 next click 之间的转移（transition），从而获得优于传统方法的性能。

     但是，它们的性能仍然不如SR-GNN 。与 NARM 和 STAMP 等 SOTA方法相比，SR-GNN 进一步考虑了 session 中 item 之间的转移，从而将每个 session 建模为一个 graph，这个 graph 可以捕获用户点击之间更复杂、更隐式的链接。而在 NARM 和 GRU4REC 中，它们显式地建模每个用户，并通过separated 的 session 序列来获得 user representation，忽略了 item 之间可能的交互关系。因此，SR-GNN 对 session 行为的建模能力更强大。

     RNN 网络显式建模单向转移，而 attention 机制显式建模全局相关性而忽略了 item 之间的关系。相比之下，SR-GNN 建模了 item 之间更复杂、更隐式的关系（如一阶邻近性、高阶邻近性）。

   • 此外，SR-GNN 采用 soft-attention 机制生成 session representation，这可以自动选择最重要的 item 转移，并忽略当前 session 中噪音（noisy）的、无效的用户 action 。相反，STAMP 仅使用 last click item 和 previous actions 之间的转移，这可能还不够。

     SR-GNN 在 soft-attention 机制中，也使用 last click item 和 previous actions 之间的关系。但是在 SR-GNN 中，每个 item embedding 考虑了 session graph 中更复杂的、更隐式的转移。

     其它 RNN 模型，如 GRU4REC 和 NARM，在传播过程中也无法选择有影响力的信息。它们使用所有 previous items 来获得代表用户通用兴趣的向量。当用户的行为是漫无目的、或者用户的兴趣在当前 session 中快速漂移时，传统模型无法有效地处理噪音的 session 。

     NARM 在通过局部编码器计算当前 session 的主要意图时，也使用注意力机制来自适应地关注更重要的 item 。因此作者这里表述有误。

   

6. 各种链接方案的比较：所提出的 SR-GNN 方法可以灵活地构建 graph 中 item 之间的链接关系。我们展示了另外两个链接变体，从而评估每个 session graph 中 item 之间的不同方式的关系。

   • 变体一：我们将所有 session graph 聚合在一起，并将它们建模为一个有向的、整体的 item graph，称之为 global graph 。在 global graph 中，每个节点表示一个 unique item，每条边表示从一个 item 到另一个 item 的有向转移。

     我们使用从 global graph 中提取的边权重代替 connection matrix ，称之为：具有归一化的全局链接（normalized global connection）的 SR-GNN （SR-GNNNGC）。

   • 变体二：我们将一个 session 中 item 之间的所有高阶关系显式建模为直接链接。我们使用布尔权重表示所有高阶关系，并将其对应的 connection matrix 附加到 SR-GNN 的 connection matrix ，称之为：具有全连接的 SR-GNN（SR-GNN-FC）。

   不同链接方案的结果如下图所示，可以看到：

   • 所有三种链接方案都实现了与 SOTA 的 STAMP 和 NARM 方法更好或几乎相同的性能，证明了将 session 建模为 graph 的有用性。

   • 与 SR-GNN 相比，对于每个 session，SR-GNNNGC 除了考虑当前 session 中的 item 之外，还考虑了其它 session 的影响，从而减少了当前 session graph 中 high degree 节点对应的边的影响。这种融合方法会显著影响当前 session 的完整性，尤其是当 graph 中边的权重差异较大时，从而导致模型性能下降。

     此外，SR-GNNGC 需要构建一张大的 global graph，当节点数量非常多（如数十亿），此时对内存也是一个挑战。而 session graph 小得多，也更容易处理。

     此外，即使 session graph 之间相互独立，但是 item embedding 是共享的，因此每个 item 可以从所有的 session graph 中学习各种转移模式。

   • 对于 SR-GNN 和 SR-GNN-FC，前者仅对连续 item 之间的确切关系进行建模，后者进一步显式地将所有高阶关系视为直接链接。结果表明，SR-GNN-FC 的性能要比 SR-GNN 更差，尽管两种方法的实验结果差别不大。

     如此小的结果差异表明，在大多数推荐场景中，并非每个高阶转移都可以直接转换为直接链接，高阶 item 之间的 intermediate stage 仍然是必需的。例如，考虑到用户在浏览一个网站时浏览了以下网页：A -> B -> C，不适合直接在 A 之后推荐网页 C 而没有中间网页 B，因为 A 和 C 之间没有直接的联系。

   

7. 不同 Session Embedding 的比较：我们将SR-GNN 的 session embedding 生成策略与以下三种方法进行比较：

   • 仅 local embedding （SR-GNNL）：即，仅考虑 last-clicked item 的 embedding 。

   • 仅具有均值池化的 global embedding（SR-GNNAVG）：即，仅考虑 global embedding 并且 ${\overrightarrow{\mathbf{s}}}_g=\sum _{i=1}^n\frac{1}{n}{\overrightarrow{\mathbf{v}}}_{s_i}$$\mathbf{\vec s}_g = \sum_{i=1}^n \frac{1}{n}\mathbf{\vec v}_{s_i}$ 。

   • 仅具有注意力机制的 global embedding （SR-GNN-ATT） ：即，仅考虑 global embedding 。

   下图给出了三种不同 embedding 策略的方法的结果。可以看到：

   • 原始的 SR-GNN 在所有三个数据集上都取得了最佳结果，这验证了显式结合当前 session 兴趣和长期偏好的重要性。

   • 此外，SR-GNN-ATT 在三个数据集上的 性能优于 SR-GNN-AVG。这表明 session 可能包含一些噪音的行为。此外，结果表明，注意力机制有助于从 session 数据中抽取重要行为从而构建长期偏好。

   • 注意，SR-GNN 的降级版本 SR-GNN-L 仍然优于 SR-GNN-AVG，并达到与 SR-GNN-ATT 几乎相同的性能，这表明：当前 session 兴趣和长期偏好对于 session-based 推荐都是至关重要的。

     仅使用 last-clicked item 的 embedding 效果就很好，那么是否可以丢弃所有 previous 行为而仅保留 last-clicked item？如果可以的话，那么会极大地简化推荐算法。

     读者认为是不可以的，因为还依赖于 session graph 来生成 last-clicked item 的 embedding 。

   

8. session 序列长度分析：我们进一步分析了不同模型处理不同长度 session 的能力。为了比较，我们将 Yoochoose 1/64 和 Diginetica 分为两组，其中： Short 组表示 session 的长度小于或等于 5 个，Long 组表示 session 的长度超过 5 个。之所以选择数字 5 ，是因为所有数据集中 session 的平均长度最接近整数 5 。Yoochoose 数据集上的 session 中，属于 Short 组和 Long 组的比例分别为 0.701 和 0.299 ，而 Diginetica 数据集则为 0.764 和 0.236 。对于每种方法，我们在下表中报告了 P@20 的指标。可以看到

   • 我们的 SR-GNN 及其变体在两个数据集上具有不同 session 长度时表现稳定。这证明了 SR-GNN 的优越性能、以及 GNN 在 session-based 推荐中的适应性（ adaptability ）。

   • 相反，NARM 和 STAMP 的性能在 Short 组和 Long 组的性能变化很大。

     STAMP 解释这样的差异归因于重复的动作（replicated actions）：这可能是因为重复点击可能会强调不重要item 的一些无效信息，并使其难以捕获到 next action 相关的用户兴趣。

     与 STAMP 类似，NARM 在 Short 组上获得了良好的性能，但是随着 session 长度的增加，性能迅速下降。部分原因是 RNN 模型难以处理长的序列。

   然后我们分析了 SR-GNN-L, SR-GNN-ATT, SR-GNN 在不同 session 长度下的性能：

   • 与 STAMP 和 NARM 相比，这三种方法取得了有前景的结果。这可能是因为基于 GNN 的学习框架，我们的方法可以获得更准确的节点向量。这种 node embedding 不仅可以捕获节点的潜在特征，还可以全局地建模节点链接。

   • 此外，SR-GNN 的性能是最稳定的，而 SR-GNN-L, SR-GNN-ATT 的性能在 Short 组和 Long 组上波动很大。

     结论不成立，SR-GNN-ATT 的波动与 SR-GNN 一样都很小。

   • 此外，SR-GNN-L 也可以取得良好的结果，尽管该变体仅使用 local session embedding vector 。这可能是因为建模 local session embedding vector 时还隐式地考虑了 session graph 中一阶节点和高阶节点的属性。