二十八、LESSR [2020]

发布于 2023-07-17 23:38:23 字数 107173 浏览 0 评论 0 收藏 0

在许多在线服务中，用户的行为天然地是按时间排序的。为了预测用户未来的行为，next-item 推荐系统通过从用户的历史行为中挖掘序列模式sequential pattern来学习用户的偏好。session-based 推荐是 next-item 推荐的一个特例。与使用固定数量的 previous action 来预测 next action 的通用 next-item 推荐系统不同，session-based 推荐系统将 user action 分组到不相交的 session 中，并使用当前 session 中的 previous action 来进行推荐。这里，session 是在时间上非常接近的 item 的一个序列。
session-based 推荐的思想来自于这样的一个观察：intra-session 的依赖关系对 next item 的影响，要比 inter-session 的依赖关系更大。具体而言，同一个 session 中的用户行为通常具有一个共同的目标（如，购买一些手机配件），而不同 session 中的用户行为的相关性较弱。用户可能在一个 session 中购买手机配件，但是在另一个 session 中购买与手机配件关系不大的商品，如衣服。因此，通用的 next-item 推荐系统可能会遇到组合不相关的 session、以及抽取不完整的 session 这两个问题。session-based 推荐系统不存在这些问题，因此它可以做出更准确的推荐，并部署在许多在线服务中。
由于具有很高的实用价值，session-based 推荐引起了研究人员的高度重视，并在过去几年中开发了许多有效的方法。之前提出的大多数方法都是基于马尔科夫链或 RNN。最近，GNN 变得越来越流行，并在许多任务中实现了 state-of-the-art 的性能。也有一些工作尝试将 GNN 应用于 session-based 推荐。尽管这些 GNN-based 方法取得了令人振奋的结果，并为 session-based 推荐提供了一个新的和有前途的方向，但是我们观察到这些方法中存在两个信息丢失问题information loss problem。
- 现有的 GNN-based 方法中的第一个信息丢失问题称作有损lossy的 session encoding 问题。这是由于它们将 session 转换为 graph 的有损编码方案 lossy encoding scheme 。要使用 GNN 处理 session，需要首先将 session 转换为 graph 。在这些方法中，每个 session 都将被转换为一个有向图，边是 item 之间的转移 transition 。边可以加权或不加权。
  例如，session $[v_{1}, v_{2}, v_{3}, v_{3}, v_{2}, v_{2}, v_{4}]$ $ [v_1,v_2,v_3,v_3,v_2,v_2,v_4] $ 被转换为如下图所示的 graph。但是，这种转换是有损操作，因为它不是一一映射。不同的 session $[v_{1}, v_{2}, v_{2}, v_{3}, v_{3}, v_{2}, v_{4}]$ $ [v_1,v_2,v_2,v_3,v_3,v_2,v_4] $ 也被转换为相同的 graph，因此我们无法在给定 graph 的情况下重建原始 session 。尽管在特定数据集中，这两个 session 可能产生相同的 next item。但是也可能存在一个数据集，其中这两个 session 产生不同的 next item。在后一种情况下，这些 GNN 模型不可能为这两个 session 都作出正确的推荐。因此，这些模型的建模能力有限。
  本质上这两个 session 是不同的，而 GNN-based 会为这两个 session 作出相同的推荐，因为这两个 session 转换后的 graph 是相同的。
- 第二个信息丢失问题称为无效的远程依赖捕获问题 ineffective long-range dependency capturing problem ，即，这些 GNN-based 方法无法有效地捕获所有远程依赖。在 GNN 模型的每一层中，节点携带的信息沿着边传播一个 step ，因此每一层只能捕获 1-hop 关系。通过堆叠多个层，GNN 模型可以捕获多达 L-hop 关系，其中 L 等于层数。由于过拟合 overfitting 和过度平滑 over-smoothing 问题，堆叠更多层不一定会提高性能，因此这些 GNN 模型的最佳层数通常不大于 3 。因此，模型只能捕获 3-hop 关系。
  然而，在实际应用中，session 长度很容易大于 3 。因此，很可能存在一些重要的、长度大于 3 的序列模式sequential pattern 。然而，由于网络结构的限制，这些 GNN-based 模型无法捕获此类信息。
为了解决上述问题，论文 《Handling Information Loss of Graph Neural Networks for Session-based Recommendation》提出了一种新的 GNN 模型，称作 Lossless Edge-order preserving aggregation and Shortcut graph attention for Session-based Recommendation: LESSR 。下图说明了 LESSR 的工作流程：
- 首先，将给定的 input session 转换为一个无损编码图（称作 edge-order preserving: EOP 的 multigraph），以及一个 shortcut graph 。
  EOP multigraph 可以解决 lossy session encoding 问题，shortcut graph 可以解决无效的远程依赖捕获问题。
- 然后，这些 graph 和 item embedding 一起被传递给 multiple edge-order preserving aggregation: EOPA 层和 shortcut graph attention: SGAT 层，从而生成所有节点的 latent feature 。
  EOPA 层使用 EOP multigraph 来捕获局部上下文信息，SGAT 层使用 shortcut graph 有效地捕获远程依赖关系。
- 然后，模型应用带注意力机制的 readout 函数从所有的 node embedding 中生成 graph-level embedding 。
- 最后，模型将 graph-level embedding 与用户最近的兴趣相结合从而生成推荐。
论文的贡献总结如下：
- 论文首先确定了用于 session-based 推荐的 GNN-based 方法的两个信息丢失问题，包括有损的 session encoding 问题、以及无效的远程依赖捕获问题。
- 为了解决有损的 session encoding 问题，论文提出了一种将 session 转换为有向 multigraph 的无损编码方案，以及一个使用 GRU 来聚合所传播的信息的 EOPA 层。
- 为了解决无效的远程依赖捕获问题，作者提出了一个 SGAT 层，该层使用注意力机制沿着 shortcut connection 有效地传播信息。
- 通过结合这两种解决方案，作者构建了一个 GNN 模型，该模型没有信息丢失问题并且在三个公共数据中优于现有的方法。
相关工作：
- 受到邻域模型在传统推荐任务中流行的启发，其中在传统推荐任务中 user id 可用，早期的 session-based 推荐的研究工作大多基于最近邻nearest neighbor 。这些方法需要一个相似度函数来衡量 item 或 session 之间的相似度。
  - 《The YouTube Video Recommendation System》 提出了一种方法，该方法根据 item 的共现模式co-occurrence pattern 来计算 item 相似度，并推荐最可能与当前 session 中的任何 item 共现的 item 。
  - 《Session-based Collaborative Filtering for Predicting the Next Song》 提出了一种模型，该模型首先将每个 session 转换为一个向量，然后测量 session 向量之间的余弦相似度。
  - 基于《Session-based Collaborative Filtering for Predicting the Next Song》 的工作，《Improving Music Recommendation in Session-based Collaborative Filtering by Using Temporal Context》 提出在计算余弦相似度之前使用聚类方法，将稀疏的 session 向量转换为稠密向量。
  虽然简单有效，但是 neighborhood-based 方法存在稀疏性问题，并且未考虑 session 中 item 的相对顺序。
- 为了更好地捕获序列属性，人们采用了基于马尔科夫链的方法。
  - 最简单的基于马尔科夫链的方法使用训练集中的转移概率来启发式地计算转移矩阵transition matrix （《An MDP-Based Recommender System》）。但是，该方法无法处理未观察到的转移模式。
  - 一种解决方案是 《Factorizing Personalized Markov Chains for Next-basket Recommendation》 中提出的 FPMC 方法，该方法使用张量分解技术来分解个性化的转移矩阵。
  - 另一种解决方案称作潜在马尔科夫 embedding （《Playlist Prediction via Metric Embedding》），它将 item 嵌入到欧氏空间，并通过 embedding 的欧氏距离来估计 item 之间的转移概率。
  当考虑更多 previous items 时状态空间的规模很快就变得难以管理，因此大多数基于马尔科夫链的方法仅使用一阶转移来构建转移矩阵，这使得它们无法捕获更复杂的高阶序列模式。
- 由于强大的序列建模能力，RNN 是对上述基于马尔科夫链方法的限制的自然解决方案。
  - GRU4Rec 是第一个 RNN-based 的 session-based 推荐方法，它简单地堆叠了多个 GRU layer。
  - 受计算机视觉和自然语言处理中注意力机制成功的启发，NARM 采用带注意力机制的混合编码器来建模用户的序列行为和主要意图。结果证明这是学习 session representation 的有效方法。
  - 遵从 NARM 工作，几乎所有后续的 RNN-based 方法都包含了注意力机制（LINet、RepeatNet、ISLF）。
- 卷积神经网络也是强大的序列建模工具。
  - 《Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding》 提出了一种基于 CNN 的方法（即，Caser），该方法将 item 序列嵌入到二维潜在矩阵中，并对矩阵进行水平卷积和垂直卷积从而抽取 sequence representation 。
  - 《A Simple Convolutional Generative Network for Next Item Recommendation》 提出使用空洞卷积层dilated convolutional layer来有效地增加感受野，而不依赖于有损的池化操作，从而使模型与 GRU4Rec 和 Caser 相比更能捕获远程依赖关系。
- 在过去的几年里，GNN 越来越受欢迎，并在许多任务中取得了 state-of-the-art 的性能。有一些工作将 GNN 应用于 session-based 推荐。
  - SR-GNN 首先将 session 编码为无权有向图，其中边表示 session 中的 item 转移。然后使用gated GNN: GGNN 在节点之间沿着边的两个方向传播信息。
  - 基于 SR-GNN，《Graph Contextualized Self-Attention Network for Session-based Recommendation》 提出了一种方法，该方法使用 GGNN 来提取局部上下文信息，并使用 self-attention network: SAN 来捕获远距离位置之间的全局依赖关系。
  - FGNN 将 session 转换为加权有向图，其中边的权重是 item 转移的计数。它使用一个适配的multi-layered graph attention network 来抽取 item 特征，并使用一个修改过的 Set2Set 池化算子来生成 session representation 。
  这些 GNN-based 方法为 session-based 推荐展示了一个新的和有前景的方向。然而，正如我们即将讨论的那样，这些方法在代表了 session 有损编码的图上操作，并且它们无法有效地捕获长期依赖关系。

28.1 模型

GNN 是直接对 graph 数据进行操作的神经网络。它们用于学习诸如图分类、节点分类、链接预测等问题的任务。这里我们仅关注图分类问题，因为 session-based 推荐可以被表述为图分类问题。
给定图 $G = (V, E)$ $ G=(V,E) $ ，其中 $V$ $ V $ 为节点集合， $E$ $ E $ 为边集合。每个节点 $v_{i} \in V$ $ v_i\in V $ 关联一个节点特征向量 ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ ，该特征向量作为初始的 node representation 传递给 GNN 的第一层。大多数 GNN 可以从消息传递的角度来理解。在 GNN 的每一层中，node representation 通过沿着边来传递消息从而得到更新。该过程可以表述为：
$\begin{matrix} {\vec{x}}_{i}^{(l + 1)} = f_{upd}^{(l)} ({\vec{x}}_{i}^{(l)}, {agg}_{i}^{(l)}) \\ {agg}_{i}^{(l)} = f_{agg}^{(l)} ({f_{msg}^{(l)} ({\vec{x}}_{i}^{(l)}, {\vec{x}}_{j}^{(l)}) : (v_{j}, v_{i}) \in E_{in} (v_{i})}) \end{matrix}$
其中：
- ${\vec{x}}_{i}^{(l)}$ $ \mathbf{\vec x}_i^{(l)} $ 表示节点 $v_{i}$ $ v_i $ 在第 $l$ $ l $ 层的 node representation 。
- $E_{in} (v_{i})$ $ E_\text{in}(v_i) $ 表示节点 $v_{i}$ $ v_i $ 的入边 incoming edge 集合。
- $f_{msg}^{(l)} (\cdot)$ $ f^{(l)}_\text{msg}(\cdot) $ 为消息函数 message function，它计算要从相邻节点 $v_{j}$ $ v_j $ 传播到目标节点 $v_{i}$ $ v_i $ 的消息。
- $f_{agg}^{(l)} (\cdot)$ $ f_\text{agg}^{(l)}(\cdot) $ 为聚合函数 aggregation function ，它聚合传递给目标节点 $v_{i}$ $ v_i $ 的所有信息。
- $f_{upd}^{(l)} (\cdot)$ $ f_\text{upd}^{(l)}(\cdot) $ 为更新函数 update function，它根据原始的 node representation 和聚合后的信息来计算新的 node representation 。
  这里的消息函数、聚合函数、更新函数都与 layer-specific 的。如果层之间共享，那么这三个函数可以表示为： $f_{msg} (\cdot), f_{agg} (\cdot), f_{upd} (\cdot)$ $ f_\text{msg}(\cdot),f_\text{agg}(\cdot),f_\text{upd}(\cdot) $ ，即移除了上标 $(l)$ $ (l) $ 。
令 $L$ $ L $ 为 GNN 的层数。经过 $L$ $ L $ 层 GNN 的 $L$ $ L $ 步消息传递之后，final node representation 捕获了 L-hop community 内的有关图结构和节点特征的信息。
对于图分类任务，readout function $f_{out} (\cdot)$ $ f_\text{out}(\cdot) $ 用于通过聚合最后一层中所有节点的 representation 来生成 graph level representation ${\vec{h}}_{G}$ $ \mathbf{\vec h}_G $ ：
${\vec{h}}_{G} = f_{out} ({{\vec{x}}_{i}^{(L)} : v_{i} \in V})$
session-based 推荐的目标是给定当前 session 的一个 item 序列（历史点击的 item ），预测用户最有可能点击的 next item 。
正式地，令 $I = {v_{1}, v_{2}, \dots, v_{| I |}}$ $ \mathcal I = \{v_1,v_2,\cdots,v_{|\mathcal I|}\} $ 为所有 item 的集合。一个 session $s_{i} = [s_{i, 1}, s_{i, 2}, \dots, s_{i, l_{i}}]$ $ \mathbf s_i = [s_{i,1},s_{i,2},\cdots,s_{i,l_i}] $ 是根据时间排序的 item 序列，其中 $s_{i, t} \in I$ $ s_{i,t}\in \mathcal I $ 为 time step $t$ $ t $ 的 item ， $l_{i}$ $ l_i $ 为 $s_{i}$ $ \mathbf s_i $ 的长度。模型的目标是预测 next item $s_{i, l_{i + 1}}$ $ s_{i,l_{i+1}} $ 。一个典型的 session-based 推荐系统会生成 next item 的一个概率分布，即 $p (s_{i, l_{i} + 1} ∣ s_{i})$ $ p(s_{i,l_i+1}\mid \mathbf s_i) $ 。具有top 概率的一批 item 将作为候选集合用于推荐。
遵从之前的工作，我们在本文中不考虑额外的上下文信息，如 user ID 和 item 属性。item ID 被嵌入在 $d$ $ d $ 维空间中，并作为模型中的初始的 item feature 。这是 session-based 推荐的文献中的常见做法。
然而，很容易调整我们的方法来考虑额外的上下文信息。例如：
- user ID embedding 可以作为 graph-level 的属性，并且可以附加到每一层中的 item ID embedding 。
- item 特征可以与 item ID emebdding 相结合，或者直接替换后者。

28.1.1 Session 到 Graph 的转换

要使用 GNN 处理 session，必须首先将 session 转换为图。这里我们首先介绍一种叫做 S2MG 的方法，该方法将 session 转换为 EOP multigraph 。然后我们介绍另一种叫做 S2SG 的方法，该方法将 session 转换为 shortcut graph 。

a. S2MG: Session to EOP Multigraph

在 session-based 推荐的文献中，有两种常用的方法可以将 session 转换为图。
- 第一种方法由 SR-GNN 提出，它将 session 转换为无权有向图 $G = (V, E)$ $ G=(V,E) $ ，其中节点集合 $V$ $ V $ 由 session 中的 unique item 组成，边集合 $E$ $ E $ 包含所有的边 $(u, v)$ $ (u,v) $ 如果 $u = s_{i, t}, v = s_{i, t + 1}, 1 \leq t \leq l_{i}$ $ u=s_{i,t},v=s_{i,t+1}, 1\le t\le l_i $ 。
- 第二种方法由 FGNN 提出。与第一种方法不同，该方法转换后的图是加权的，其中边 $(u, v)$ $ (u,v) $ 的权重是转移 $u \to v$ $ u\rightarrow v $ 在当前 session 中出现的频次。
在接下来的内容中，我们称第一种方法为 Session-to-Graph: S2G，第二种方法为 Session-to-Weighted-Graph: S2WG 。
我们声称 S2G 和 S2WG 都是有损的转换方法，因为在给定转换后的图的情况下，并不总是可以重建原始的 session 。为了证明这一点，我们只需要证明 S2WG 是有损的，因为它比 S2G 捕获更多的信息，即 item transition 的出现次数。因此，S2WG is lossy 意味着 S2G is lossy 。
为了了解为什么 S2WG 是有损的，我们举一个反例如下。给定两个不同的 session：
$\begin{matrix} s_{1} = [v_{1}, v_{2}, v_{3}, v_{3}, v_{2}, v_{2}, v_{4}] \\ s_{2} = [v_{1}, v_{2}, v_{2}, v_{3}, v_{3}, v_{2}, v_{4}] \end{matrix}$
S2WG 将这两个session 转换为相同的图，如下图 (a) 所示。注意，我们省略了边的权重，因为它们都是 1 。因此，给定下图 (a) 中的转换后的图，我们不清楚 $s_{1}$ $ \mathbf s_1 $ 和 $s_{2}$ $ \mathbf s_2 $ 中的哪一个才是原始的 session 。
有损转换可能会出现问题，因为被忽略的信息对于确定 next item 可能很重要。我们应该让模型自动学习决定哪些信息可以被忽略，而不是使用有损转换方法 “盲目地” 作出决定。否则，该模型不够灵活，无法适应复杂的数据集，因为模型的建模能力受到有损转换方法的限制。
为了解决这个问题，我们提出了一种叫做 session to EOP multigraph: S2MG 的方法，该方法将 session 转换为保留了边顺序的有向 multigraph 。
- 对于原始 session 中的每个转移 $u \to v$ $ u\rightarrow v $ ，我们创建一条边 $(u, v)$ $ (u,v) $ 。该图是一个 multigraph ，因为如果存在从 $u$ $ u $ 到 $v$ $ v $ 的多个转移，我们将创建从 $u$ $ u $ 到 $v$ $ v $ 的多条边。
- 然后，对于每个节点 $v$ $ v $ ， $E_{in} (v)$ $ E_\text{in}(v) $ 中的边可以根据它们在 session 中出现的时间来排序。我们通过给 $E_{in} (v)$ $ E_\text{in}(v) $ 中的每条边一个整数属性来记录顺序，该属性值指示该条边在 $E_{in} (v)$ $ E_\text{in}(v) $ 中的所有边之间的相对顺序。
  首先出现在 $E_{in} (v)$ $ E_\text{in}(v) $ 中的边，其属性值为 1 。接下来出现的边，其属性值为 2 。以此类推。
例如，session $s_{1} = [v_{1}, v_{2}, v_{3}, v_{3}, v_{2}, v_{2}, v_{4}]$ $ \mathbf s_1 = [v_1,v_2,v_3,v_3,v_2,v_2,v_4] $ 被转换为上图 (b) 中的图，用 ${MG}_{s_{1}}$ $ \text{MG}_{\mathbf s_1} $ 表示。为了使得转换真正无损，我们还标记了 last item，即session $s_{1}$ $ \mathbf s_1 $ 中的节点 $v_{4}$ $ v_4 $ ，由虚线圆圈来表示。我们将这个结果图称作给定 session 的 edge-order preserving: EOP 的 multigraph 。
现在，我们通过展示如何在给定一个 EOP multigraph （即，使用 S2MG 转换得到的图）的情况下重建原始的 session 来证明 S2MG 是一种从 session 到 graph 的无损转换方法。基本思想是：按照 item 在 session 中出现的相反顺序来恢复 item 。
我们以 ${MG}_{s_{1}}$ $ \text{MG}_{\mathbf s_1} $ 为例。 last item 是被标记的节点 $v_{4}$ $ v_4 $ 。
- 由于我们知道 last item，并且我们知道 $v_{4}$ $ v_4 $ 的入边的顺序，我们可以确定 last edge 是 $(v_{2}, v_{4})$ $ (v_2,v_4) $ 。
- 倒数第二个 item 就是 last edge 的源节点，即 $v_{2}$ $ v_2 $ 。
- 然后我们可以迭代地执行该操作并确定倒数第三个 item，以此类推。
通过这种方式，我们可以从图 ${MG}_{s_{1}}$ $ \text{MG}_{\mathbf s_1} $ 中恢复 session $s_{1}$ $ \mathbf s_1 $ 。给定任何的 graph，可以应用相同的过程来重建原始的 session 。因此，S2MG 是一种从 session 到图的无损转换方法。

b. S2SG: Session to Shortcut Graph

为了处理现有的 GNN-based 的 session-based 推荐模型中无效的远程依赖问题，我们提出了 shortcut graph attention: SGAT 层（见后面的内容描述）。SGAT layer 需要一个不同于上述 EOP multigraph 的输入图。这个输入图采用称作 session to shortcut graph: S2SG 的方法从 input session 中转换而来。
给定一个 session $s_{i}$ $ \mathbf s_i $ ，我们创建一个图，其中节点是 $s_{i}$ $ \mathbf s_i $ 中的 unique item 。对于每对有序的节点 pair $(u, v)$ $ (u,v) $ ，当且仅当存在一个 pair $(s_{i, t_{1}}, s_{i, t_{2}})$ $ (s_{i,t_1},s_{i,t_2}) $ 使得 $s_{i, t_{1}} = u, s_{i, t_{2}} = v, t_{1} < t_{2}$ $ s_{i,t_1}=u,s_{i,t_2}=v, t_1\lt t_2 $ 的时候，我们创建从 $u$ $ u $ 到 $v$ $ v $ 的一条边。该图被称作 shortcut graph，因为它连接了一对 item 而不经过中间的 item 。
我们还在图中添加了 self-loop，以便稍后在 SGAT 层执行消息传递时，可以组合 update function 和 aggregate function ，这是 GAT 模型中的常见做法。
采用了 self-loop 之后，更新函数和聚合函数可以用一个统一的函数来替代。
因此，session $s_{1} = [v_{1}, v_{2}, v_{3}, v_{3}, v_{2}, v_{2}, v_{4}]$ $ \mathbf s_1 = [v_1,v_2,v_3,v_3,v_2,v_2,v_4] $ 的shortcut graph 如下图 (c) 所示。
在接下来的内容中，我们展示了 SGAT 层如何通过在 shortcut graph 上执行消息传递从而解决无效的远程依赖问题。

28.1.2 LESSR

LESSR 的整体框架如下图所示。首先我们介绍 EOPA layer，然后我们介绍 SGAT layer，接下来我们描述如何堆叠这两种类型的层，然后我们展示如何获取 session embedding 。最后，我们给出了我们如何进行预测和训练。

a. EOPA layer

给定从 session 无损转换的 EOP multigraph ，GNN 仍然需要正确地处理图，以便可以将不同的 session 映射到不同的 representation 。这在现有的 GNN-based 的 session-based 推荐模型中是不可能的，因为它们使用排列不变permutation-invariant的聚合函数，忽略了边的相对顺序。因此，这些模型仅适用于边之间的排序信息不重要的数据集，这意味着这些模型的建模能力存在限制。
因为 EOP multigraph 中，每条边有一个整数属性值来保留边的相对顺序，那么将这个属性值作为聚合函数的特征（比如，position embedding ），是否就可以保留边之间的排序信息？
为了填补这个 gap，我们提出了 edge-order preserving aggregation: EOPA 层，该层使用 GRU 来聚合从相邻节点传递的信息。具体而言，令 $O E_{in} (v_{i}) = [(v_{j_{1}}, v_{i}), (v_{j_{2}}, v_{i}), \dots, (v_{j_{d_{i}}}, v_{i})]$ $ OE_\text{in}(v_i) = [(v_{j_1},v_i),(v_{j_2},v_i),\cdots,(v_{j_{d_i}},v_i)] $ 为边集合 $E_{in} (v_{i})$ $ E_\text{in}(v_i) $ 的有序列表，其中 $d_{i}$ $ d_i $ 为节点 $v_{i}$ $ v_i $ 的 degree 。 $O E_{in} (v_{i})$ $ OE_\text{in}(v_i) $ 可以使用 EOP multigraph 中边的整数属性从 $E_{in} (v_{i})$ $ E_\text{in}(v_i) $ 来获得。来自邻居的聚合信息定义如下：
$\begin{matrix} {agg}_{i}^{(l)} = {\vec{h}}_{d_{i}}^{(l)} \\ {\vec{h}}_{k}^{(l)} = {GRU}^{(l)} (f_{msg}^{(l)} ({\vec{x}}_{i}^{(l)}, {\vec{x}}_{j_{k}}^{(l)}), {\vec{h}}_{k - 1}^{(l)}) \end{matrix}$
其中：
- ${{\vec{h}}_{k}^{(l)} : 0 \leq k \leq d_{i}}$ $ \left\{\mathbf{\vec h}_k^{(l)}:0\le k\le d_i\right\} $ 为 GRU 的 hidden state 。初始的状态 ${\vec{h}}_{0}^{(l)}$ $ \mathbf{\vec h}_0^{(l)} $ 可以为零向量。
- $f_{msg}^{(l)} (\cdot)$ $ f_\text{msg}^{(l)}(\cdot) $ 可以是计算从节点 $v_{j_{k}}$ $ v_{j_k} $ 传递到节点 $v_{i}$ $ v_i $ 的消息的任意有效消息函数。
  消息函数的结果作为 GRU 的输入。
GRU 聚合器是一种 RNN 聚合器。我们选择 GRU 而不是 LSTM，因为已经有工作表明：在 session-based 推荐任务中GRU 优于 LSTM 。尽管在现有工作中人们已经提出了 RNN 聚合器，如GraphSAGE 中提出了 LSTM 聚合器，但是应该注意到这些 RNN 聚合器的工作方式与我们的不同。
具体而言，现有的 RNN 聚合器通过对这些边的随机排列执行聚合来故意忽略入边 incoming edge 的相对顺序，而我们的 GRU 聚合器以固定的顺序执行聚合。这是因为在 session-based 推荐设置中，边自然是按时间排序的。
但是，我们要强调的是，GRU 聚合器并不是我们的主要贡献。我们的主要贡献是应用 GRU 聚合器来解决前面描述的信息丢失问题。
来自已有 GNN 模型的消息函数和更新函数可以与 GRU 聚合器一起使用，但是考虑到 GRU 强大的表达能力，我们简单地对消息函数和更新函数使用线性变换。因此，将所有内容放在一起，我们模型的 EOPA 层定义为：
$\begin{matrix} {\vec{x}}_{i}^{(l + 1)} = W_{upd}^{(l)} ({\vec{x}}_{i}^{(l)} | | {\vec{h}}_{d_{i}}^{(l)}) \\ {\vec{h}}_{k}^{(l)} = {GRU}^{(l)} (W_{msg}^{(l)} {\vec{x}}_{j_{k}}^{(l)}, {\vec{h}}_{k - 1}^{(l)}) \end{matrix}$
其中： $W_{upd}^{(l)} \in R^{d \times (2 d)}, W_{msg}^{(l)} \in R^{d \times d}$ $ \mathbf W^{(l)}_\text{upd}\in \mathbb R^{d\times (2d)},\mathbf W_\text{msg}^{(l)}\in \mathbb R^{d\times d} $ 为待学习的参数， $| |$ $ || $ 表示向量拼接。
这里消息函数 $f_{msg}^{(l)} ({\vec{x}}_{i}^{(l)}, {\vec{x}}_{j_{k}}^{(l)}) = W_{msg}^{(l)} {\vec{x}}_{j_{k}}^{(l)}$ $ f_\text{msg}^{(l)}\left(\mathbf{\vec x}_i^{(l)},\mathbf{\vec x}_{j_k}^{(l)}\right) = \mathbf W_\text{msg}^{(l)}\mathbf{\vec x}_{j_k}^{(l)} $ ，更新函数 $f_{upd}^{(l)} ({\vec{x}}_{i}^{(l)}, {agg}_{i}^{(l)}) = W_{upd}^{(l)} ({\vec{x}}_{i}^{(l)} | | {\vec{h}}_{d_{i}}^{(l)})$ $ f_\text{upd}^{(l)}\left(\mathbf{\vec x}_i^{(l)},\text{agg}_i^{(l)}\right)= \mathbf W_\text{upd}^{(l)}\left(\mathbf{\vec x}_i^{(l)}|| \mathbf{\vec h}_{d_i}^{(l)}\right) $ 。
至于最后一个节点的信息，将在后面描述的 readout 函数中使用，以便将不同的 session 映射到不同的 representation 。

b. SGAT layer

一般而言，每一层都传播一个 step 的信息，因此一层只能捕获节点之间的 1-hop 关系。为了捕获 multi-hop 关系，可以堆叠多个 GNN 层。不幸的是，这会引入过度平滑问题over-smooth problem，即，node representation 收敛到相同的值。由于过度平滑问题通常发生在层数大于 3 时，因此堆叠多个层并不是捕获 multi-hop 关系的好方法。
此外，即使可以堆叠多个层，GNN 也只能捕获最多 k-hop 关系，其中 $k$ $ k $ 等于层数。但是，在电商网站等现实世界的 application 中，session 长度大于 $k$ $ k $ 是很常见的。因此，现有的 session-based 推荐的 GNN 模型无法有效地捕获 very long range 内的依赖关系。
为了解决这个问题，我们提出了 shortcut graph attention: SGAT 层，它本质上是利用 S2SG 得到的 shortcut graph 中的边来进行快速的消息传播。
具体而言，SGAT 层使用以下注意力机制沿着 shortcut graph 中的边来传播信息：
$\begin{matrix} {\vec{x}}_{i}^{(l + 1)} = \sum_{(v_{j}, v_{i}) \in E_{in} (v_{i})} α_{i, j}^{(l)} W_{val}^{(l)} {\vec{x}}_{j}^{(l)} \\ α_{i, j}^{(l)} = softmax (e_{i, j}^{(l)}) = \frac{\exp (e_{i, j}^{(l)})}{\sum_{j^{'}} \exp (e_{i, j^{'}}^{(l)})} \\ e_{i, j}^{(l)} = {\vec{p}}^{(l)} \cdot σ (W_{key}^{(l)} {\vec{x}}_{i}^{(l)} + W_{qry}^{(l)} {\vec{x}}_{j}^{(l)} + {\vec{b}}^{(l)}) \end{matrix}$
其中：
- $E_{in} (v_{i})$ $ E_\text{in}(v_i) $ 是节点 $v_{i}$ $ v_i $ 在 shortcut graph 中的入边 incoming edge 集合。
- ${\vec{p}}^{(l)}, {\vec{b}}^{(l)} \in R^{d}, W_{key}^{(l)}, W_{qry}^{(l)}, W_{val}^{(l)} \in R^{d \times d}$ $ \mathbf{\vec p}^{(l)},\mathbf{\vec b}^{(l)}\in \mathbb R^d, \mathbf W_\text{key}^{(l)},\mathbf W_\text{qry}^{(l)},\mathbf W_\text{val}^{(l)}\in \mathbb R^{d\times d} $ 为待学习的参数。
shortcut graph 中的边直接将每个 item 连接到其所有后续 item，而无需经过中间的 item 。因此，shortcut graph中的边可以看做是 item 之间的 shortcut connection 。
SGAT 层可以有效地捕获任意长度的长期依赖关系，因为它在一个 step 中沿着 item 之间的 shortcut connection 传播信息，而无需经过中间的 item 。它可以与现有的 GNN-based 方法中的原始层相结合，从而提高 GNN-based 方法捕获远程依赖关系的能力。
如何与现有的 GNN-based 方法中的原始层相结合？可以参考本文中的 “堆叠多层” 部分。

c. 堆叠多层

EOPA 层和 SGAT 层用于解决之前 GNN-based 的 session-based 推荐方法的两个信息丢失问题。为了构建没有信息丢失问题的 GNN 模型，我们堆叠了许多 EOPA 层和 SGAT 层。我们没有将所有 EOPA 层放在所有 SGAT 层之后，也没有将所有的 SGAT 层放在 EOPA 层之后。我们将 EOPA 层与 SGAT 层交错，原因如下：
- shortcut graph 是原始 session 的有损转换，因此不断堆叠多个 SGAT 层会引入有损 session encoding 问题。SGAT 层越多，问题就越严重，因为信息丢失量会累积。
  通过交错 EOPA 层和 SGAT 层，丢失的信息可以保留在后续的 EOPA 层中，SGAT 层可以仅专注于捕获远程依赖关系。
- 交错两种层的另一个优点是：每种层都可以有效地利用另一种层捕获的特征。由于 EOPA 层更能捕获局部上下文信息，而 SGAT 层更能捕获全局依赖关系，将这两种层交错可以有效地结合两者的优点，提高模型学习更复杂依赖关系的能力。
为了进一步促进特征重用 feature reuse，我们引入 DenseNet 中提出的稠密连接。每层的输入由所有 previous layers 的输出特征组成。具体而言：
- 第 $l$ $ l $ 层的原始输入为： ${{\vec{x}}_{i}^{(l - 1)} : v_{i} \in V}$ $ \left\{\mathbf{\vec x}_i^{(l-1)}:v_i\in V\right\} $ 。
- 采用稠密连接之后，第 $l$ $ l $ 层的输入为： ${{\vec{x}}_{i}^{(0)} | | {\vec{x}}_{i}^{(1)} | | \dots | | {\vec{x}}_{i}^{(l - 1)} : v_{i} \in V}$ $ \left\{\mathbf{\vec x}_i^{(0)}||\mathbf{\vec x}_i^{(1)}||\cdots||\mathbf{\vec x}_i^{(l-1)}:v_i\in V\right\} $ ，它就是所有 previous layers 输出的拼接。
结果表明：具有稠密连接的深度学习模型的参数效率更高，即，用更少的参数实现相同的性能，因为每个较高的层不仅可以使用它的前一层的抽象特征，还可以使用更低层的 low-level feature 。

d. 生成 Session Embedding

在所有层的消息传递完成之后，我们得到所有节点的 final representation。为了将当前 session 表示为 embedding 向量，我们应用了SR-GNN 中提出的 readout 函数，该函数通过注意力机制聚合 node representation 来计算 graph-level representation 。
令 ${\vec{x}}_{last}^{(L)}$ $ \mathbf{\vec x}_\text{last}^{(L)} $ 为session 中 last item 的 final node representation 。graph-level representation ${\vec{h}}_{G}$ $ \mathbf{\vec h}_G $ 定义如下：
$\begin{matrix} {\vec{h}}_{G} = \sum_{v_{i} \in V} β_{i} {\vec{x}}_{i}^{(L)} \\ β_{i} = softmax (ϵ_{i}) = \frac{\exp (ϵ_{i})}{\sum_{j} \exp (ϵ_{j})} \\ ϵ_{i} = \vec{q} \cdot σ (W_{1} {\vec{x}}_{i}^{(L)} + W_{2} {\vec{x}}_{last}^{(L)} + \vec{r}) \end{matrix}$
其中： $\vec{q}, \vec{r} \in R^{d}, W_{1}, W_{2} \in R^{d \times d}$ $ \mathbf{\vec q},\mathbf{\vec r}\in \mathbb R^d, \mathbf W_1,\mathbf W_2\in \mathbb R^{d\times d} $ 为待学习的参数。
$V$ $ V $ 为当前 session 转换后的图的节点集合，它的规模远远小于全量 item 集合 $I$ $ \mathcal I $ ，即 $V \subseteq I$ $ V\sube \mathcal I $ 。
graph-level representation 捕获当前 session 的全局偏好，记做 ${\vec{s}}_{g} = {\vec{h}}_{G}$ $ \mathbf{\vec s}_g = \mathbf{\vec h}_G $ 。由于之前的研究表明：显式考虑用户最近的兴趣也很重要，因此我们定义了一个局部偏好向量local preference vector ，记做 ${\vec{s}}_{l} = {\vec{x}}_{last}^{(L)}$ $ \mathbf{\vec s}_l = \mathbf{\vec x}_\text{last}^{(L)} $ 。
然后，我们将 session embedding 计算为全局偏好和局部偏好的线性变换：
${\vec{s}}_{h} = W_{h} ({\vec{s}}_{g} | | {\vec{s}}_{l})$
其中： $W_{h} \in R^{d \times 2 d}$ $ \mathbf W_h\in \mathbb R^{d\times 2d} $ 为一个待学习的参数。

e. 预测和训练

在获得 session embedding 之后，我们可以使用它来计算 next item 的概率分布从而进行推荐。
对于每个 item $v_{i} \in I$ $ v_i\in \mathcal I $ ，我们首先使用其 embedding ${\vec{v}}_{i}$ $ \mathbf{\vec v}_i $ 以及 session embedding 来计算一个分数：
$z_{i} = {\vec{s}}_{h} \cdot {\vec{v}}_{i}$
实际上 ${\vec{v}}_{i}$ $ \mathbf{\vec v}_i $ 就是节点特征向量 ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ 。
然后，next item 是 item $v_{i}$ $ v_i $ 的预测概率为：
${\hat{y}}_{i} = \frac{\exp (z_{i})}{\sum_{v_{j} \in I} \exp (z_{j})}$
对于 top-K 推荐，我们可以仅推荐概率最高的 $K$ $ K $ 个 ietm 。
令 $\vec{y}$ $ \mathbf{\vec y} $ 为 next item 的真实概率分布，它是一个 one-hot 向量。损失函数被定义为预测分布和真实分布的交叉熵：
$L (\vec{y}, \hat{\vec{y}}) = - \sum_{i} (y_{i} \log {\hat{y}}_{i} + (1 - y_{i}) \log (1 - {\hat{y}}_{i}))$
然后，所有参数以及 item embedding 都被随机初始化，并通过端到端的反向传播来联合学习。

28.2 实验

数据集：
- Diginetica 数据集：来自 CIKM Cup 2016 。我们使用它的交易数据来进行 session-based 推荐。遵从之前的工作（NARM, STAMP, RepeatNet, SR-GNN），我们使用最近一周的 session 作为测试集。
- Gowalla 数据集：是一个广泛用于 point-of-interest: POI 推荐的 check-in 数据集。遵从之前的工作（《Streaming Session-based Recommendation》,Caser），我们保留了 top 30000 个最受欢迎的 location ，并通过 1 天的时间间隔来拆分用户的 check-in 记录从而将这些记录分组到不相交的 session 中。最近的 20% 的 session 用作测试集。
- Last.fm 数据集：是一个广泛用于许多推荐任务的数据集。我们将该数据集用于音乐艺术家推荐。遵从之前的工作（《Streaming Session-based Recommendation》, RepeatNet），我们保留了 top 40000 名最受欢迎的艺术家，并将拆分间隔设置为 8 小时。与 Gowalla 类似，最近的 20% 的 session 用作测试集。
遵从之前的工作（NARM, STAMP, FGNN, RepeatNet, SR-GNN），我们首先过滤了短的 session 和低频的 item，然后应用了NARM, STAMP, SR-GNN 中描述的数据增强技术。预处理后数据集的一些统计数据如下表所示：
baseline 方法：
- Item-KNN：一种邻域方法，它推荐与当前 session 中的 previous items 相似的 item，其中两个 item 之间的相似度由它们的 session 余弦相似度所定义。
- FPMC：一种用于 next-basket 推荐的基于马尔科夫链的方法。为了适配 session-based 推荐，我们将 next item 视为 next-basket 。
- NARM：使用 RNN 来捕获用户的主要意图和序列行为。
- NextItNet：一种用于 next-item 推荐的 CNN-based 方法。它使用空洞卷积来增加感受野，而且不使用有损的池化操作。
- SR-GNN：将 session 转换为有向无权图，并通过 GNN 来沿边的两个方向传播信息从而提取 item 特征。
- FGNN：将 session 转换为有向加权图，并使用适配的 GAT 来学习 item representation 。
- GC-SAN：首先使用 GGNN 来抽取局部上下文信息，然后使用 self-attention network: SAN 来捕获全局依赖关系。
配置：遵从 STAMP 和Caser 之后，对于每种方法，我们应用网格搜索并使用训练集的最后 20% 作为验证集从而找到最佳超参数。超参数的范围是：
- embedding 维度 $d$ $ d $ 的范围 ${16, 32, 64, 96, 128}$ $ \{16,32,64,96,128\} $ 。
- 学习率 $η$ $ \eta $ 的范围 ${10^{- 4}, 10^{- 3}, \dots, 10^{- 1}}$ $ \{10^{-4},10^{-3},\cdots,10^{-1}\} $ 。
- 对于 GNN-based 方法，我们也搜索层数 $L$ $ L $ ，其范围是 ${1, 2, 3, 4, 5}$ $ \{1,2,3,4,5\} $ 。
我们使用 Adam 优化器来训练模型，batch size 设置为 512 。我们报告每个模型在其最佳超参数配置下的结果。
评估指标：Hit Rate: HR@20、Mean Reciprocal Rank: MRR@20 。
所有方法的实验结果如下表所示，可以看到：
- 包括 Item-KNN 和 FPMC 在内的传统方法的性能没有竞争力。这些方法仅基于 item 的相似性、或者仅基于 item 转移进行推荐，而不考虑其它重要的序列信息，如，当前 session 中 previous items 之间的相对次序。
- 所有基于神经网络的模型都大大优于传统方法，证明了深度学习技术在 session-based 推荐中的有效性。基于神经网络的模型能够捕获复杂的序列模式从而进行推荐。
  然而，它们的序列建模能力并非同样地强大。
  - CNN-based 的方法 NextItNet 的性能低于其它 RNN-based 和 GNN-based 方法。一个可能的原因是：CNN 仅擅长捕获连续的序列模式，而不擅长捕获长期依赖。
  - NARM 取得了具有竞争力的性能，因为它使用 RNN 来捕获序列行为以及使用注意力机制来捕获全局偏好。
- GNN-based 方法通常优于其它方法，这表明 GNN 为 session-based 推荐提供了一个有前途的方法。
  - 虽然 FGNN 使用的转换方法 conversion method 比 SR-GNN 使用的方法捕获更多的信息，但是 FGNN 的性能并不优于 SR-GNN，这表明选择强大的消息传递方案的重要性。
  - GC-SAN 优于 SR-GNN，因为它使用 SAN 来捕获远距离 item 之间的全局依赖关系，展示出显式考虑长期依赖关系的有效性。
  - LESSR 使用强大的 EOPA 来抽取局部上下文，并使用 SGAT 来捕获任意长度的远程依赖关系，因此它可以显著优于所有的 baseline 方法，证明了所提出方法的效果。
    在三个数据集中，LESSR 在 Last.fm 数据集上获得了最大的性能提升，因为这个数据集的平均长度最大，所以 LESSR 从保留边次序edge order 和捕获长期依赖关系中获益最多。
消融研究：
- EOPA Layer 的有效性：为了评估 EOPA 层的有效性，我们将它与来自其它 GNN-based 方法的 message passing: MP 层进行比较，包括：来自 SR-GNN 的 GGNN、来自 FGNN 的 WGAT、来自 GC-SAN 的 SAN。
  我们使用前述描述的相同的 readout 函数。embedding size 设置为 96，因为大多数模型在这个 embedding size 下实现了最佳性能。
  - 对于 GGNN 和 WGAT，层数设置为 1 ，并与具有一个 EOPA 层的模型进行比较。
  - 为了展示 EOPA 的重要性，我们还将 EOPA 层与其修改后的变体进行了比较，该变体对入边 incoming edge 的随机排列执行聚合。换句话讲，修改后的 EOPA 层忽略了 EOP multigraph 中边的顺序属性。我们用变体 EOPA(rand) 来表示。
  - 对于 SAN，由于它是为与 GGNN 一起工作而设计的，因此我们比较了由 GGNN 和 SAN 组成的模型，以及由 GGNN 和 EOPA 组成的模型。
  结果如下表所示。每个模型都由其包含的 MP layer 的名称来表示。可以看到：
  - EOPA 始终优于所有其它类型的 MP layer，证明了 EOPA 的有效性。
  - 其它类型的 MP layer 表现更差，因为它们使用有损编码方案将 session 转换为图，并且它们的聚合方案不考虑边的相对顺序。
  - 注意，尽管 EOPA 和 EOPA(rand) 使用相同的编码方案，即 S2MG，但是 EOPA 优于 EOPA(rand)，因为 EOPA(rand) 在执行聚合时会随机排列入边 incoming edge 。因此，仅保留边顺序的转换方案是不够的。聚合方案还需要保留边顺序。
- SGAT Layer 的有效性：为了展示 SGAT 的有效性，我们将每个现有的 GNN-based 方法的最后一个 MP layer 替换为 SGAT layer，并检查是否替换后是否提高了性能。
  - 由于 SR-GNN 和 FGNN 只有一种 MP layer，因此将层数设置为 2，以便修改后的模型有一个原始 MP layer、有一个是 SGAT layer。
  - 对于 GC-SAN，层数设为 3，因为它有两种 MP layer 。
  - 对于 LESSR，我们比较了一个具有两层 EOPA layer 的模型，以及一个具有一层 EOPA layer 和一层 SGAT layer 的模型。
  emebdding size 设为 96。由于篇幅有限，我们仅报告了 Diginetica 数据集上的 HR@20 的性能，因为它更常用于 session-based 的推荐。结果如下表所示。可以看到：替换有助于提高模型性能。这是因为原始层仅擅长捕获局部上下文信息，而不是复杂的远程依赖关系。通过 SGAT layer 替换原始层，模型捕获远程依赖关系的能力得到提升。
  GC-SAN 中的 SAN 层也能够捕获远程节点之间的全局依赖关系。但是，它们在每对节点之间传播信息，这完全丢弃了原始 session中的连接信息。相反，我们的 SGAT 层仅当 $u$ $ u $ 出现在 $v$ $ v $ 之前时，才会将信息从 $u$ $ u $ 传播到 $v$ $ v $ ，这保留了一些连接信息。因此，当 SAN layer 替换为我们的 SGAT layer 时，模型的性能提升是可以理解的。
- EOPA 层和 SGAT 层的顺序：为了展示层顺序的优势，我们比较了四种模型，包括：EESS, SSEE, ESES, SESE。每个模型包含两个 EOPA layer 和两个 SGAT layer ，其中 E 代表 EOPA layer，S 代表 SGAT layer ，字符的顺序代表层之间的顺序。例如，EESS 有两个 EOPA layer，后面跟着两个 SGAT layer 。
  embedding size 设置为 96 ，并使用残差连接。下表展示了实验结果。可以看到：
  - SSEE 表现最差，因为它不能利用任何一种层的优点。
  - SESE 和 EESS 具有相似的性能，这表明交错两种层、或者将 EOPA 层放在 SGAT 层之前的好处。
  - ESES 优于所有其它模型，证明该顺序是利用这两种层的优势的最有效方式。
超参数调优：这里我们研究 embedding size 和层数如何影响所提出方法的性能。由于篇幅有限，这里我们仅给出 HR@20 的结果，如下图所示。可以看到：
- 增加 embedding size 或层数并不总是会带来更好的性能。
  - 对于较小的数据集 Diginetica，最佳的 embedding size 为 32。当 embedding size 超过该最佳值时，性能会迅速下降，因为模型过拟合。
  - 对于另外两个较大的数据集，增加 embedding size 通常会提高性能，因为较大的 embedding size 会增加模型的学习能力。
- 如果 embedding size 小于最优值，那么随着层数的增加，模型性能先提高后下降。这是因为随着层数变大，模型的学习能力会增加。但是过多的层数也无济于事，因为会出现过度平滑的问题，即使模型没有过拟合。
  因此，堆叠更多的层并不是捕获远程依赖的有效方法，而采用替代方法（如 SGAT layer）来提高模型捕获远程依赖的能力是有意义的。