「微软」局部图协同过滤缓解数据稀疏问题
关注我们，一起学习~
title：Localized Graph Collaborative Filtering link：https://arxiv.53yu.com/pdf/2108.04475.pdf from：SDM 2022
1. 导读
本文是针对图神经网络在推荐系统中的应用提出的相关方法LGCF，对于用户-商品交互数据稀疏的情况下，无法得到较好的embedding来计算偏好。LGCF不需要为每个用户和商品学习embedding，旨在将有用的 CF 信息编码到局部图中，并基于该图进行推荐。
2. 定义
用户-商品二分图表示为G=(U, I, E)，
表示n个用户，
表示m个商品，
表示用户和商品的历史交互，
。模型的目标是学习一个函数映射f，计算用户u和候选商品i的偏好分数，
3. 方法
LGCF主要包含两个方面：局部结构的提取来构造局部图；从局部图中捕获相关的模式。如图所示为整体框架图。
- 首先LGCF构建以目标用户和目标商品为中心的局部化图。作者设计一种局部图构建方法将具有丰富 CF 信息的边保留到本地化图中。
- 之后，LGCF根据相对于目标节点的拓扑位置标记局部图中的节点。
- 然后一个基于 GNN 的图表征学习模块将嵌入高阶连接以及节点位置注释。通过这个过程，LGCF 消除了传统的基于embedding的策略，并有效地捕获了关键的 CF 相关模式。
- 计算用户和商品的偏好分数。
简而言之：
- 局部化图构建模块，用于提取覆盖与给定用户-商品对相关的大多数边的局部化图；
- 局部化图表征学习模块，从局部化图中学习推荐相关的表征；
- 评分函数模块，根据学习到的图表征计算偏好分数。
3.1 局部图构建
局部化图构建模块旨在提取覆盖给定用户-商品对的最重要边（即协同过滤信息）的局部图。需要在训练过程和推理过程中为每个用户-商品对提取一个局部图，因此目标是在考虑可扩展性的情况下让每一个用户-商品对包含最具代表性的边。 简单来说就是通过RWR提取包含目标用户-目标商品对的子图。
如图所示为局部图提取的框架图，分为以下步骤：
- 随机游走：采用具有重启的随机游走RWR采样用户和商品节点的邻居节点。对于(u, i)在图G上分别从u节点和i节点开始，使用RWR采样。通过RWR可以得到两个路径（traces）
和
，每条路径包含了节点的子集
,
。
- 路径联合：将两个子集V求并集得到
。
- 图提取：从提取的节点集合
中，可以基于原图G构造子图。节点采用V_ui中的，节点之间的边根据原图G中的关系得到，构造的子图表示为
。
简单的分析Q&A
- Q：什么是重要的边？
- A：靠近目标商品和目标用户的边或者说是节点周围的边，他们能更多的反应用户和商品的CF信息
- Q：RWR是什么？
- A：RWR，Random Walk with Restart。从原始节点开始，每次移动以均匀的概率迭代地到达其中一个连接的节点。此外，每一步都有一个预定义的概率返回到起始节点（这就是restart）。这样，可以将更多的相邻节点包含在游走中。
3.2 局部图表征学习
这部分
- 使用图神经网络对从局部图中得到CF信息进行编码，将 CF 信息以及与用户-商品对相关的高阶连接性编码到表征中，因为它可以自然地捕获结构信息并将高阶连通性显式编码到表征中。
- 此外，为了进一步编码拓扑信息，采用节点标记方法根据每个节点与用户-商品对的距离为每个节点生成位置标签，其中节点标签被视为输入图节点属性。
3.2.1 节点标记方法
所采用的标记方式需要达到以下三点：
- 能够将目标用户和商品节点在子图中与其他节点，使得模型能够感知到子图中的目标用户-商品对；
- 除了目标节点对之外的其他节点，每个节点的作用也是不同的，因此根据节点与目标节点对的相对位置关系来生成标记；
- 为了一致性，距离目标节点对越近的节点的标签和目标节点对的标签应该越相似。
因此，通过双半径节点标注（DRNL）根据节点到用户-商品对的距离为每个节点生成一个标签，并将生成的节点标签作为输入节点GNN 模型的属性。
- 首先将标签 1 分配给目标用户节点和目标商品节点，以将它们与其他节点区分开来。
- 接下来，根据提取的局部图上与两个目标节点的最小距离为其他节点分配标签。对于图上的节点 x，通过将其与这两个节点的最小距离相加来评估其与目标用户和目标商品的距离。由于将目标用户和目标物品的标签设置为 1，因此将为这些附近的节点标签分配较小的值。
含义解释：给定节点 x 和 y，如果 x 与目标节点之间的距离小于 y 的距离，则 x 的标签值应该小于 y 的标签值。如果距离相同，则与目标用户或目标项目的最小距离较小的节点应具有较小值的标签。 DRNL 采用满足上述标准的散列函数 fl() 来计算节点标签。每个节点 x 的节点标记函数 fl(x) 总结如下，其中
,
表示节点到目标用户节点和目标商品节点的最小距离，d=d_u+d_i。
3.2.2 GNN模型
对于局部图
，其中A表示邻接矩阵，X为生成的标签属性。本节采用GCN加池化来得到表征，具体如下，其中
表示经过l层GNN后的节点表征，W为可学习参数，
，
表示度矩阵，池化采用求和，即将所有层的表征求和得到最终表征。
3.3 得分函数
分数越高，说明用户越偏好这个商品，通过单层网络得到最终分数，具体如下，其中w是可学习参数，σ为sigmoid函数。
3.4 模型优化
这里采用BPR损失函数，公式如下，正样本为图中存在的交互行为，负样本为未交互的通过负采样得到。
3.5 与基于embedding的方法结合
像lightgcn和ngcf都是在全图上得到embedding，然后进行偏好分数计算的；而lgcf从另一个角度，从局部图上计算分数，将两者结合可以进行信息互补。这里采用两种结合方式：LGCF-emb和LGCF-ens。以lightgcn为例，令
，
分别表示lightgcn从全图上学得的商品和用户的表征,
表示LGCF从局部图中学习到的用户-商品对的表征。
3.5.1 LGCF-emb
将表征进行拼接，公式如下，其中*表示逐元素相乘，将得到的新表征送入得分函数计算得分。
3.5.2 LGCF-ens
采用集成的方式，公式如下，其中λ表示超参数或者可学习参数。将两个分数相加得到最终分数。
4. 实验结果
在稀疏数据上的实验结果。
常规场景下的实验结果
5. 总结
本文所述的不需要为每个节点学习embedding的意思是，在为用户u计算推荐的商品偏好时，不需要计算整个图，从而可以不用计算所有节点的embedding。