Question

1. 推荐系统在现代无处不在，并且已经广泛应用于推荐音乐、书籍、电影等 item 的服务。真实世界的推荐系统包括很多有利于推荐的 user-item 交互，包括播放时间、喜欢、分享、以及贴标签 tag 。协同过滤collaborative filtering: CF 通常用于利用这种交互数据进行推荐，因为CF 在各种推荐策略之间性能表现较好，并且不需要领域知识domain knowledge 。

   有两种主流的 CF 模型：潜在因子模型latent factor model 和基于图的模型graph-based model 。

   • 潜在因子模型通过分解 user-item 矩阵来发现 user-item 交互背后的共享潜在因子shared latent factor 。矩阵分解matrix factorization: MF 是此类方法的典型代表。

     此外，最近的文献更多地关注从隐式数据优化 item 排序，而不是预测显式的item score 。大多数此类方法假设用户对未观察到的 item 不太感兴趣，因此这些方法旨在区分观察到的item （positive）和未观察到的 item （negative）。

     总而言之，潜在因子模型通过分解观察到的用户和 item 之间的直接交互来捕获用户偏好。

   • 基于图的模型探索了由用户、item、及其交互构建的简单 user-item 二部图bipartite graph 中固有的inherent 、顶点之间的高阶邻近性high-order proximity 。

     在某种程度上，这种基于图的方法放松了基于因子分解的模型所做出的假设（即：假设用户对未观察到的 item 不太感兴趣），因为它们显式地对user-item 交互二部图中的用户和 item 之间的高阶邻近性进行建模。

     总而言之，基于图的模型从由 user-item 交互构建的图中捕获用户间接偏好。

   在论文 《HOP-Rec: High-Order Proximity for Implicit Recommendation》中，作者提出了高阶临近性增强推荐模型 high-order proximity augmented recommendation: HOP-Rec，这是一个结合了这两种隐式推荐方法（潜在因子模型和基于图的模型）的、统一而有效的方法。HOP-Rec 通过在user-item 二部图上进行随机游走，从而为每个用户发现邻域item 的高阶间接信息high-order indirect information 。通过对游走路径中不同阶数使用置信参数confidence parameter，HOP-Rec 在分解用户偏好的潜在因子时同时考虑item 的不同阶数。

   下图说明了在观察到的交互中对用户和 item 之间的高阶邻近性建模的思想。

   • 图(a) 表示由观察到的 user-item 交互构建的二部图。
   • 图 (b) 给出了一条从源顶点 $ u_1 $ 到目标顶点 $ i_4 $ 的路径。
   • 图 (c) 以矩阵的形式记录了用户和 item 之间的直接交互（一阶邻近性）。
   • 图 (d) 以矩阵的形式显示了用户和 item 之间的高阶关系（高阶邻近性）。

   具体而言，用户 $ u_1 $ 的潜在偏好item 按照它们在图 (b) 中的路径中出现的阶数进行排序。例如，观察到的item $ i_2 $ 和用户 $ u_1 $ 具有一阶关系，未观察到的 item $ i_3 $ 和用户 $ u_1 $ 具有二阶关系。HOP-Rec 显式地建模这种高阶间接偏好信息high-order indirect preference information 。

   

   在真实世界四个大规模数据集上的实验结果表明，HOP-Rec 显著优于几种state-of-the-art 的推荐算法，并表明将高阶邻近性和因子分解模型相结合对于一般的 top-N 隐式推荐问题很有帮助。

15.1 模型

15.1.1 因子分解模型和图模型

1. 交互图Interaction Graph 的定义：user-item 交互由一个二元邻接矩阵 $ \mathbf A=(a_{i,j})\in \mathbb R^{|\mathcal U|\times |\mathcal I|} $ 来表示，二部交互图bipartite interaction graph $ G=(\mathcal V,\mathcal E) $ 基于二元邻接矩阵 $ \mathbf A $ 来构建。其中：

   • $ \mathcal U $ 为用户集合， $ \mathcal I $ 为 item 集合， $ \mathcal V=\mathcal U\cup\mathcal I $ 为顶点集合。
   • $ a_{i,j}\in \{0,1\} $ 表示是否存在交互，边集合 $ \mathcal E=\{e_{i,j}\mid a_{i,j}=1\} $ 。

2. k 阶邻近性k-order Proximity 的定义：给定一个交互图 $ G=(\mathcal V,\mathcal E) $ ，顶点 $ (u,i) $ 之间的k 阶邻近性由它们在图上随机游走生成的序列中的转移概率来定义，其中 $ u\in \mathcal U,i\in \mathcal I,k\in \mathbb N^+ $ 。

   具体而言，令 $ \mathcal S_u=(u,i_1,u_1,\cdots,u_{k-1},i_k,\cdots) $ 表示从源顶点 $ u $ 开始的随机游走序列，其中 $ u_k $ 和 $ i_k $ 分别表示顶点 $ u $ 的第 $ k $ 个邻居用户和第 $ k $ 个邻居item 。源顶点 $ u $ 与其第 $ k $ 个邻居item 之间的 k 阶邻近性定义为 $ p_u^{}(i_k)\times C(k) $ ，其中：

   • $ p_u^{}(i_k) $ 表示从 $ u $ 到 $ i_k $ 的 k 阶转移概率。
   • $ C(k) $ 是k 阶衰减因子decay factor。例如 $ C(k) = 1/k $ 。

   如果从 $ u $ 到 $ i_k $ 不存在可行的路径，则 k 阶邻近性为零。

3. Factorization Model: FM 模型：因子分解模型的目标是估计以下两个潜在因子集合： $ \Theta_U,\Theta_I\sube\Theta $ ，其中：

   • $ \Theta_U\in \mathbb R^{|\mathcal U|\times d} $ 为用户潜在因子集合， $ \Theta_I\in \mathbb R^{|\mathcal I|\times d} $ 为 item 潜在因子集合， $ d $ 为潜在因子空间的维度。
   • $ \Theta $ 为 $ \Theta_U,\Theta_I $ 的超集，由我们模型中的所有参数组成。

   令 $ \vec\theta_u\in \mathbb R^d $ 表示用户 $ u $ 在 $ \Theta_U $ 中的行向量， $ \vec\theta_i\in \mathbb R^d $ 表示 item $ i $ 在 $ \Theta_I $ 中的行向量，则 MF 针对隐式反馈数据集的目标函数为：

   $ \mathcal L_{\text{MF}} = \sum_{u,i}c_{u,i}\left(a_{u,i} -\vec\theta_u^\top\vec\theta_i\right) + \lambda_\Theta \|\Theta\|_2^2 $

   其中：

   • $ u\in \mathcal U,i\in \mathcal I $ ， $ c_{u,i} $ 为置信度水平confidence level。通常选择 $ c_{u,i} = 1+\alpha\times a_{u,i} $ ，即观察到交互的 user-item 置信度高于未观察到交互的 user-item 。
   • $ a_{u,i} $ 为二元变量表示在邻接矩阵 $ \mathbf A $ 中观察到的用户 $ u $ 和 item $ i $ 是否有交互。
   • 正则化参数 $ \lambda_\Theta $ 是防止观测值过拟合的超参数。

   在各种基于因子分解的模型中，基于排序ranking-based 的模型在top-N 推荐问题中表现突出。基于排序的模型如 BPR 和 WARP 已经从传统的point-wise 方法（绝对关系）转变为 pairwise 方法（相对关系），其中排序损失ranking loss 可以定义为：

   $ \mathcal L_{\text{rank}} = \sum_{u,(i,i^\prime)} \mathcal F\left(\vec\theta_u^\top\vec\theta_{i},\vec\theta_u^\top\vec\theta_{i^\prime}\right)+\lambda_\Theta\|\Theta\|_2^2 $

   其中：

   • $ i\in \mathcal I $ 表示用户 $ u $ 观察到的item （positive）， $ i^\prime\in \mathcal I $ 表示用户 $ u $ 未观察到的 item （negative）， $ u\in \mathcal U $ 。
   • 函数 $ \mathcal F(\cdot) $ 表示item 排序问题的通用目标函数。具体而言，在 BPR 中， $ \mathcal F $ 是由logistic sigmoid 函数、对数函数、示性函数组成的排序函数。在 WARP 中， $ \mathcal F $ 由权重近似的排序函数和一个示性函数组成。

   基于排序的模型假设用户更喜欢观察到的 item 而不是未观察到的 item，因此其目标是从每对item pair 中区分出偏好的 item。

4. Graph Model 模型：除了通常研究的基于因子分解的模型之外，人们还提出了几个基于图的模型，这些模型利用随机游走来对推荐的 item 进行排序。具体而言，这类模型的主要思想是将 user-item 交互矩阵 $ \mathbf A $ 视为交互图，并在图上使用随机游走从而引入间接偏好信息来提供推荐。

15.1.2 HOP-Rec 模型

1. 尽管基于因子分解的模型隐式地推断用户对未观测item 的偏好，但是最近的研究表明显式地建模此类潜在偏好potential preference 可以提高推荐系统的性能。受到因子分解模型和图模型的启发，我们提出了 HOP-Rec。这是一个统一的框架：

   • HOP-Rec 在给定的 user-item 交互矩阵中捕获高阶偏好信息。
   • HOP-Rec 通过在相应的交互图上使用随机游走来扩展scale 到大规模的真实世界数据集。

2. HOP-Rec 的目标函数定义为：

   $ \mathcal L_{\text{HOP}} = \sum_{1\le k\le K\\u,(i,i^\prime)}\underbrace{C(k)\mathbb E_{i\sim P_u^{}\\ i^\prime\sim P_N}}_{\text{graph model}}\underbrace{\left[\mathcal F\left(\vec\theta_u^\top\vec\theta_{i},\vec\theta_u^\top\vec\theta_{i ^\prime}\right)\right]}_{\text{factorization model}}+\lambda_\Theta\|\Theta\|_2^2 $

   其中：

   • $ P_u^{}(\cdot) $ 表示从随机游走序列 $ \mathcal S_u $ 中采样item 的 k 阶概率分布（即前面定义的 $ p_u^{}(i_k) $ ）。
   • $ P_N(\cdot) $ 表示从所有item 的集合中采样 item 的均匀分布。
   • $ K $ 表示在我们的方法中建模的最大阶数。

   上述物理含义是：以概率 $ P_u^{}(\cdot) $ 随机采样 $ u $ 的 k 阶邻居item 作为正样本、以均匀随机采样item 作为负样本，然后对它们的 pairwise loss 进行衰减降权（由 $ C(k) $ 指定衰减因子）。注意：每个正样本采样 $ N $ 个负样本， $ N $ 为超参数。

   从另一个角度来看，我们通过从 user-item 交互中推断高阶邻近性来丰富最初的稀疏图。

   它的本质是：数据集增强技术。即利用二部图来增强正样本（同时对每个正样本负采样 $ N $ 个负样本），另外对增强的样本赋予一个小于 1 的权重。

3. HOP-Rec 方法背后的主要思想是：通过随机游走来近似高阶概率矩阵分解，其中随机游走具有一个置信权重confidence weighting $ C(k) $ 的衰减因子， $ 0\lt C(k)\le 1 $ 。引入置信度加权参数 $ C(k) $ 来区分不同邻近性之间的强度。具体而言，我们选择 $ C(k) = 1/k $ 作为衰减因子。

   注意，我们没有通过矩阵运算直接分解转移概率矩阵矩阵，这对于大规模数据集是不可行的。而随机游走近似矩阵分解已经被证明是有效和准确的。

   通过这种方式，我们不仅通过引入高阶偏好信息来平滑观察的item 和未观察的 item 之间的严格边界（“非此即彼”的边界），而且使得我们的方法可以扩展到大规模的现实世界数据集。

   具体而言，我们首先引入随机游走从而为每个用户 $ u $ 在交互图上探索。给定从 $ u $ 开始的随机游走序列 $ \mathcal S_u=(u,i_1,u_1,\cdots,u_{k-1},i_k,\cdots) $ ，我们采样用户 $ u $ 的k 阶潜在偏好的 item $ i_k $ （即用户 $ u $ 的 k 阶邻居item ）。

   此外，在现实世界的数据集中，用户集合 $ \mathcal U $ 和 item 集合 $ \mathcal I $ 的 degree 分布通常呈现幂律分布power-law distribution 。如果我们使用均匀采样，那么大多数采样路径都是低 degree 的用户顶点和 item 顶点。考虑到这一点，我们在随机游走过程中使用了 degree 采样，即：对于随机游走采样的每一个step，我们分别以正比于 deg(u) 的概率对用户 $ u $ 采样、以正比于 deg(i) 的概率对item $ i $ 采样。

   如何采样正样本很关键，不同的采样方式产生不同的结果。

4. 我们定义 $ \mathcal F(\cdot,\cdot) $ 函数为：

   $ \mathcal F\left(\vec\theta_u^\top\vec\theta_{i},\vec\theta_u^\top\vec\theta_{i ^\prime}\right) = \mathbb I_{\vec\theta_u^\top\vec\theta_{i^\prime}-\vec\theta_u^\top\vec\theta_{i}\gt \epsilon_k}\times \log \left[\sigma\left(\vec \theta_u^\top\vec \theta_{i^\prime}-\vec \theta_u^\top\vec \theta_{i }\right)\right] $

   其中：

   • $ \mathbb I_{B} $ 为示性函数，当条件 B 为真时返回 1、为假时返回 0。上式中仅当 $ \vec\theta_u^\top\vec\theta_{i^\prime}-\vec\theta_u^\top\vec\theta_{i}\gt \epsilon_k $ 才考虑损失（即负样本的偏好分更高）。
   • $ \epsilon_k $ 为阶数相关的阈值参数，设置为 $ \epsilon/k $ 。这是因为阶数越高， $ u $ 和 $ i $ 的偏好分越低，则阈值也需要越小。

   注意，item $ i^\prime $ 是从所有 item 的集合中均匀采样的，因为我们对用户不喜欢的 item 采用假设的均匀分布 $ P_N $ 。这个假设是合理的，因为在很多真实场景中，对每个用户来讲，喜欢的item（观察到的 item）通常远远少于不喜欢的 item （未观察到的 item）。

5. HOP-Rec 模型的目标函数可以通过异步随机梯度下降 asynchronous stochastic gradient descent: ASGD 来优化。

15.2 实验

1. 数据集：为了验证 HOP-Rec 的能力和可扩展性，我们在四个公共数据集上进行了实验，这些数据集在领域domain、规模、稀疏性方面各不相同，如下表所示。

   对于每个数据集，我们丢弃那些交互少于5 个的用户和 item。此外，我们对每个数据集的交互记录进行预处理，从而模拟用户的隐式二元反馈：

   • 对于包含显式评分记录的Amazon-book 和 MovieLens 数据集，我们将所有>=4 分的评分记录转换为 label = 1、将<4分的评分记录转换为 label = 0 。
   • 对于 CiteUlike 数据集，不进行任何转换，因为它本身就是一个二元偏好数据集。

   

2. baseline 方法：

   • 矩阵分解 Matrix Factorization: MF：MF 是一种成熟且常用的 user-item 推荐技术。在实验中我们使用implicit library，它用交替最小二乘法alternating least-square: ALS 实现了 MF。

   • 贝叶斯个性化排序Bayesian Personalized Ranking: BPR：BPR 扩展了MF 的 pointwise 方法，并引入 pairwise ranking loss 来进行个性化推荐。

   • Weighted Approximate-Rank Pairwise: WARP 损失：WARP 是一种有效估计排序函数的近似方法，其主要思想是根据它们在排序列表中的位置来加权 pairwise 违规violation 。

   • K-Order Statistic: K-OS 损失：K-OS 通过在优化过程中考虑正样本集合来扩展 WARP，其中 K 表示考虑的正样本数量。注意，当 K=1 时 K-OS 退化为 WARP。

     对于BPR, WARP, K-OS 三种方法，我们使用 lightfm library 进行实验。

   • Popularity-based Re-ranking: RP3(β)：该方法作为各种graph-based 方法的一个强基线。该方法通过调节热门 item 的权重重新加权 ranking score，这个 ranking score 是基于随机游走而得到。该方法的评估时用原始作者提供的 library 进行的。

3. 实验配置：

   • 对于 top-N 推荐，我们使用了以下三个常见的评估指标：precision@N、recall@N、MAP@N。
   • 对于每个数据集，我们将二元交互矩阵随机分为两个部分：80% 作为训练集、20% 作为测试集。报告的性能取20 次实验的测试集均值。
   • 所有基于分解的方法以及提出的 HOP-Rec 都使用两个潜在因子的内积作为评分函数。
   • 除了 RP3(β) 这种以转移概率为排序分的纯图方法之外，其它方法的潜在因子 $ d $ 的维度固定为 120 。除了 $ d $ 之外，所有其它超参数都是在第一次评估时使用网格搜索和测试集基于 MAP 来选择。
   • 对于 HOP-Rec，我们搜索了从 1 ~3 的最佳阶数 K，以及针对不同规模数据集的采样倍数 N （对于 CiteUlike/MovieLens- 1M/MovieLens-20M/Amazon-Book 数据集，最佳采样倍数分别为 90/60/300/800）。
   • 对于 HOP-Rec， $ \vec\theta_u,\vec\theta_i $ 都是在 $ \pm 0.5/d $ 范围内随机均匀初始化，并且 $ \epsilon = 1 $ 。

4. HOP-Rec 和其它五种 baseline 方法的性能比较如下表所示，其中： * 表示相对于所有 baseline 方法在 $ p\lt 0.01 $ （成对 t 检验）时的统计显著性；%Improv 表示相对于最佳baseline 的性能提升比例。注意，原始library 的资源限制阻碍了我们在 Amazon-Book 上进行 PR3(β) 实验。

   可以看到：

   • WARP,K-OS,PR3(β) 是很强的 baseline 方法，因为它们和其它两种方法 MF,BPR 之间存在显著的性能差距。
   • HOP-Rec 通常产生优于或者相当与五种 baseline 方法的性能。

   

5. 为进一步检查 HOP-Rec 中建模高阶邻近性的有效性，我们评估了关于参数 K 的性能，结果如下图所示。可以看到：融合高阶邻近性可以提升 HOP-Rec 的性能，但是对于最大的数据集 Amazon-Book，当 K=3 时性能下降。