WSDM'22「谷歌」更快，更准，更可扩展：利用随机游走做会话推荐

秋枫学习笔记

发布于 2022-09-19 11:13:23

4820

发布于 2022-09-19 11:13:23

文章被收录于专栏：秋枫学习笔记

点击关注我们，提升学习效率

title：S-Walk: Accurate and Scalable Session-based Recommendation with Random Walks
link：https://arxiv.org/pdf/2201.01091.pdf
from：WSDM 2022

1. 导读‍‍‍‍‍

本文针对基于会话的推荐而提出的相关方法S-Walk，主要针对两方面：

同时关注会话内和会话间的商品之间的关系；
所提方法具有更高的效率和更好的可扩展性。

S-Walk主要包含三个部分，分别是transition model（直译：转换模型）， teleportation model（直译：传送模型）以及具有重启的随机游走（RWR）。

通过转换模型，从会话序列中捕获商品之间的依赖关系和顺序关系
通过传送模型，从会话序列中捕获商品之间的共现关系
利用RWR，结合上面两个模型得到的图，生成最终的图，用于预测。

2. 基本概念

2.1 符号

S=\{s^{(1)},...,s^{(m)}\}

表示会话集合，每个会话s中包含一系列的交互商品，商品集合表示为

I=\{i_1,...,i_n\}

，序列s表示为

s=(s_1,...,s_{|s|})

，其中

s_i \in I

。交互的类型有很多，包括点击、购买等，这里简化为是否交互，不区分具体类型，定义一个矩阵

X \in \mathbb{R}^{m\times n}

，m是会话集合大小，n是商品集合大小，其中的元素等于1表示有交互，等于0表示没交互。

2.2 问题定义

会话推荐的目标就是，给定用户在之前的交互商品，预测下一个可能交互的商品。对于给定的

s=(s_1,...,s_j)

预测候选商品列表

(s_{j+1},...,s_{|s|})

，这相比于预测单个商品

s_{j+1}

更具一般性。

2.3 随机游走模型

随机游走的关键概念是反映商品之间的直接和传递关系。使用随机游走的传统推荐模型基于用户-商品二分图

\mathcal{G}=(\mathcal{U} \cup \mathcal{I},\mathcal{E})

，其中 U 和 I 是用户集合和商品集合。每条边 𝑒 ∈ E 代表用户和商品之间的关系。因此，随机游走模型的核心部分是确定转移概率矩阵来计算商品的邻近分数。有两种方案可以计算该分数：

可以利用随机游走者的 𝑘 步着陆概率分布。从源用户𝑢开始，所有商品的邻近分数可以计算为

uR_{(k)}

，其中u是用户向量，R是k步转移概率矩阵。但是该方法容易受流行度偏差的影响，随着k的增加，热门商品往往具有更高的分数。

计算有**重启的随机游走（RWR）**的平稳分布。他能有效捕获向量间的高阶关系，因为 RWR 除了顺序转换之外还利用了重启，它可以缓解流行度偏差的问题，集中在𝑘-step 中的中心节点。

在基于会话的推荐中采用随机游走具有以下优点：

随机游走模型利用会话之间的高阶商品相关性。由于会话本质上通常是稀疏的，因此通过捕获商品之间的深层关系来缓解数据稀疏问题很有用。
与基于 GNN 的 SR 模型相比，它是高效的，无需复杂的超参数调整。

2.4 线性item-item模型

给定会话-商品矩阵X，线性模型的目标是估计商品-商品相似度矩阵

\mathbf{B} \in \mathbb{R}^{n \times n}

。SLIM是这方面的开创新工作，它制定了一个线性模型，该模型约束 B 中的所有元素都是非负且零对角线的。公式如下，其中diag(B)表示由B的对角元素构成的向量，

\begin{gathered} \underset{\text { B }}{\operatorname{argmin}}\|\mathbf{X}-\mathbf{X} \cdot \mathbf{B}\|_{F}^{2}+\lambda_{1}\|\mathbf{B}\|_{1}+\lambda_{2}\|\mathbf{B}\|_{F}^{2} \\ \text { s.t. } \operatorname{diag}(\mathbf{B})=0, \quad \mathbf{B} \geq 0, \end{gathered}

近期提出的

EASE^R

是对上面工作的改进，只考虑零对角约束和F范数，公式如下，

\underset{\mathrm{B}}{\operatorname{argmin}}\|\mathrm{X}-\mathrm{X} \cdot \mathrm{B}\|_{F}^{2}+\lambda \cdot\|\mathrm{B}\|_{F}^{2} \text { s.t. } \operatorname{diag}(\mathrm{B})=0

通过拉格朗日乘子法，可得闭式解，其中

\hat{\mathbf{P}}=(\mathbf{X^TX}+\lambda \mathbf{I})^{-1}

，

\oslash

表示逐元素相除，diagmat(x)表示由向量x扩展而来的对角矩阵。

\hat{\mathbf{B}}=\mathbf{I}-\hat{\mathbf{P}} \cdot \operatorname{diagMat}(\mathbf{1} \oslash \operatorname{diag}(\hat{\mathbf{P}}))

note：本文后续的工作也是在该工作的基础上进行的，如果想继续深度了解这些方法可以阅读论文。

3. S-Walk

3.1 模型结构

如图所示为S-Walk的总体流程，给定会话-商品交互矩阵X，首先设计了两个模型item transition和item teleportation，以捕捉会话的不同特征。然后，用RWR构成全局商品图。

两个模型分别产生两个图

\mathcal{G}_R=(\mathcal{I},\mathcal{E}_R)

\mathcal{G}_T=(\mathcal{I},\mathcal{E}_T)

，转移矩阵 R 是 GR 的邻接矩阵，它编码会话中的顺序依赖和重复交互的商品；矩阵T是GT的邻接矩阵，捕获会话中的商品一致性。引入这两个矩阵可以捕获商品之间的不同会话内的关系，但它们没有解决会话间关系。

采用 RWR，其中随机游走者从一个节点跳到另一个节点或在任意节点上重新启动，而不管她当前的位置如何，我们打算考虑会话间关系，捕获商品之间的高阶关系，即，商品图上的多阶连接关系。从概念上讲，两个商品图 G𝑅 和 G𝑇 上的 RWR 可以被认为是抛硬币，以概率 𝛼 产生正面：

以α的概率，在矩阵R上，随机游走者从当前商品节点跳跃到另一个相邻节点；
以1-α的概率，在矩阵T上，从开始节点的其中一个相邻节点上重启

使用这两个矩阵的随机游走是一个随机过程，也可以看作是均匀离散时间上商品的马尔可夫链。RWR 公式如下，其中α就是上面的概率，

x_{(0)}^T \in \mathbb{R}^n

是初始商品向量，

x_{(k)}^T \in \mathbb{R}^n

是k步后更新的临近分数。随着k的增加，x_k收敛到一个分布。通过 RWR，可以获得随机游走者落在每个节点上的平稳概率，最后通过最终的图

\mathcal{G}_M=(\mathcal{I},\mathcal{E}_M)

生成推荐列表。

\mathbf{x}_{(k+1)}=\alpha \mathbf{x}_{(k)} \mathbf{R}+(1-\alpha) \mathbf{x}_{(0)} \mathbf{T} \text {, where } k=0, \ldots, \infty

3.1 Item Transition Model

构建线性转换模型来构建转换矩阵R，这里采用部分会话表征（ partial session representations ）。会话s被划分为两个子会话，过去（past）和未来（future）。“过去”子会话为

s_{1:t-1}=\{s_1,...,s_{t-1}\}

，“未来”子会话为

s_{t:|s|}=\{s_{t},...,s_{|s|}\}

。对于每个时间t=2,...,|s|，都生成一个“过去”和“未来”子会话，可以得到|s|-1个对。将所有会话s的|s|-1个“过去”和“未来”子会话分别堆叠后，可得两个矩阵，“过去”会话矩阵

Y \in \mathbb{R}^{m'\times n}

，“未来”会话矩阵

Z \in \mathbb{R}^{m' \times n}

，其中m'表示所有子会话的数量

m'=\sum_{i-1}^m{(|s^{(i)}|-1)}

。

考虑其中商品的时间关系，本节对矩阵Y，Z中商品的权重进行调整，通过商品之间的位置差别进行加权，权重公式如下，其中δ是超参数，控制会话中的位置衰减，p(i,s)表示商品i在会话s中的位置，商品i，j相隔越远，他们的相关性就越弱。

w_{\text {pos }}(i, j, s)=\exp \left(-\frac{|p(i, s)-p(j, s)|}{\delta_{\text {pos }}}\right)

商品转移模型可以定义为，其中B是从Y和Z中学习到的商品-商品相关矩阵。

\underset{\mathrm{B}^{\operatorname{tran}}}{\operatorname{argmin}}\left\|\mathrm{Z}-\mathrm{Y} \cdot \mathrm{B}^{\operatorname{tran}}\right\|_{F}^{2}+\lambda\left\|\mathrm{B}^{\operatorname{tran}}\right\|_{F}^{2}

B可以由下式求解得到，

\hat{\mathbf{B}}^{train}=\hat{\mathbf{P}}' \cdot (\mathbf{Y}^T \mathbf{Z})

\hat{\mathbf{P}}'=(\mathbf{Y^TY}+\lambda \mathbf{I})^{-1} \in \mathbb{R}^n

为了在随机游走中利用商品转移矩阵，每个元素应该是从一个节点到另一个节点的转移概率。也就是说，每个元素都是非负的并且总和为 1。因此，用0替换

\hat{\mathbf{B}}^{train}

中所有的负数，表示为

\hat{\mathbf{B}}^{train}_{>= 0}

，然后对其标准化，如下式，其中R是转移概率矩阵，其每一行都被标准化，1是长度为n的全为1的列向量。

\mathrm{R}=\operatorname{diagMat}\left(\hat{\mathrm{B}}_{\geq 0}^{\operatorname{tran}} \mathbf{1}\right)^{-1} \hat{\mathbf{B}}_{\geq 0}^{\operatorname{tran}}

3.3 Item Teleportation Model

该模型用于捕获商品之间的一致性，这里该模型专注于商品之间的共现关系，忽略会话中商品之间的顺序关系，构建矩阵X（“2.定义”中的X），其中重复出现多次，也当做出现一次，即出现就是1，不出现就是0。

给定矩阵 X，该模型使用与现有线性模型中使用的相同输入和输出矩阵来制定。同时，放宽了 B 的零对角约束以处理重复的物品消费。当 B 的对角元素被松散惩罚时，它允许我们重复预测与下一个商品相同的商品。其中B是反映商品一致性的商品-商品矩阵，

\xi

是超参数，对B的对角元素进行约束。

B的闭式解如下

\hat{\mathbf{B}}^{\text {tele }}=\mathbf{I}-\hat{\mathbf{P}} \cdot \operatorname{diagMat}(\gamma), \quad \gamma_{j}= \begin{cases}\lambda & \text { if } 1-\lambda P_{j j} \leq \xi \\ \frac{1-\xi}{P_{j j}} & \text { otherwise }\end{cases}

\hat{\mathbf{P}}=(\mathbf{X^TX}+\lambda \mathbf{I})^{-1}

同样，这里的B也是存在负数的，因此要采用相同的操作，用0替换负数后，对其进行标准化，公式如下，其中β是超参数，控制自循环的重要性从而使得随机游走能收敛

\mathrm{T}=\beta\left(\text { diagMat }\left(\hat{\mathbf{B}}_{\geq 0}^{\text {tele }} \mathbf{1}\right)^{-1} \hat{\mathbf{B}}_{\geq 0}^{\text {tele }}\right)+(1-\beta) \mathrm{I}

3.4 随机游走

3.4.1 训练

为了得到S-Walk的稳定分布，公式如下，其中

M=\sum_{k=0}^{\infty}{\alpha^k(1-alpha)TR^k}

为S-walk训练得到的商品-商品矩阵。

\begin{aligned} \mathbf{x}_{(\infty)} &=\alpha^{\infty} \mathbf{x}_{(0)} \mathbf{R}^{\infty}+\sum_{k=0}^{\infty} \alpha^{k}(1-\alpha) \mathbf{x}_{(0)} \mathbf{T R}^{k} \\ & \approx \mathbf{x}_{(0)} \sum_{k=0}^{\infty} \alpha^{k}(1-\alpha) \mathbf{T R}^{k}=\mathbf{x}_{(0)} \mathbf{M} . \end{aligned}

3.4.2 推理

给定一个新会话

s_{new}

，我们表示一个会话向量

x_{new}

并使用 M 计算接近分数。预测下一个商品的接近分数

x_{new}M

。在这个过程中，为了更多地依赖最近的消费，对会话中不同商品进行加权，公式如下，其中δ是超参数用于控制衰减，||表示会话长度。

w_{\text {inf }}\left(i, s_{\text {new }}\right)=\exp \left(-\frac{\left|s_{\text {new }}\right|-p\left(i, s_{\text {new }}\right)}{\delta_{\text {inf }}}\right)

4. 结果