Reinforced Negative Sampling over Knowledge Graph for Recommendation

Enhanced Negative Sampling within a Knowledge Graph to improve recommendation

ABSTRACT

有效的缺失数据处理在推荐系统中是一个核心问题。当前大多数研究均基于未被观测到的数据进行负采样以生成具有负面信号的推荐模型训练数据集。然而现有的负采样策略无论是静态还是自适应均无法充分生成高质量的负样本这不仅有助于提升模型性能同时也能够更好地反映用户的实际需求。
为了实现这一目标我们假设项目知识图谱（Knowledge Graph, KG）能够提供项目与KG实体之间的丰富关系从而推断出高质量的真实负面样本。
在此基础上我们开发了一种新的负采样模型——知识图谱策略网络（Knowledge Graph Policy Network, KGPolicy）。该模型作为一种强化学习智能体旨在探索高质量的负面样本空间具体而言通过设计的独特探索操作从用户与项目的正向交互中引导自身逐步接收基于知识感知的真实负面信号最终生成一个用于推荐系统的高质负面影响样本。
我们在基于KGPolicy的知识图谱分解模型上进行了实验验证并取得了预期效果。

INTRODCTION

推荐系统已广泛应用于实际应用中，以提高用户满意度和参与度。 从历史用户-项目交互中训练推荐模型，正例和负例的用户反馈，被要求以确保模型生成合理的个性化排序[13，23，33]。 然而，大多数互动都是以隐反馈的形式进行的，例如点击和购买，这只提供信号的正反馈。 这就给推荐模型学习带来了根本的挑战—如何从仅有正例数据中提取负例数据-这也被称为一类问题。
由于负面信号潜伏在未观察到的数据中，一个普遍的解决方案是执行负采样，这比将所有未观察到的相互作用视为负例更有效。 现有的负采样策略可分为三种类型：静态采样器、自适应采样器和具有额外行为的增强采样器。然而，每种方法都有一些固有的局限性。
鉴于负采样的基本作用和现有方法的局限性，我们在本工作中将重点放在负采样上，旨在通过引入其他类型的数据来提高其质量.高质量的负采样应该满足两个要求：1)信息性，这意味着目前的模型对它们的评分相对较高，因此将它们更新为负例将会我显著地改变模型参数，2)事实，这意味着它们是真正的负例，即用户以前知道它们（通过系统或其他方式暴露），但没有选择它们.由于自适应采样器可以实现对信息的要求，关键的挑战在于从缺失的数据中发现真实的负例，这些数据本质上缺乏真实性。
在这项工作中，我们假设知识图(KG)，它引入了项目和现实世界实体之间的额外关系（来自项目属性或外部知识），可以从未观察到的数据中推断真实的负例。虽然将KG纳入推荐中最近得到了广泛的研究，但这些研究只利用KG建立预测模型，以前的工作没有使用它来增强负采样器。
为此，我们提出了一种新的负采样模型KGPolicy（简称知识图策略网络），该模型采用强化学习(RL)代理来探索KG以发现高质量的负采样。核心是设计的探索操作，它从用户项正例探索，选择两个顺序邻居(例如，一个KG实体和一个项目)访问。 这样的两跳路径可以捕捉到知识感知负例。为了实现这一目标，我们设计了一个邻居注意力模块，该模块指定了以正例用户项对为条件的一跳和两跳邻居的不同重要性，以便自适应地捕获对KG实体的偏好，并产生潜在的项目。 通过递归地进行这种探索，KGPolicy学会为目标正例交互选择潜在的负例。 此外，路径历史作为支持证据，揭示了为什 所选项目被视为负实例。为了证明我们的方法，我们使用了一个简单的线性模型，矩阵分解(MF)，作为推荐者，使用KGPolicy训练该模型。
总之，这项工作作出了以下主要贡献：
1） 据我们所知，我们是第一个将知识图纳入负抽样的，目的是选择高质量的负例与正例用户项交互配对。
2） 我们开发了一种用于负采样的强化学习KGPolicy，它有效地学习了用多跳探索路径得到高质量的负例。
3） 我们对三个基准数据集进行了广泛的实验，证明了KGPolicy在抽样有效性和知识条目使用方面的优势。

TASK FORMULATION

我们首先展示交互数据与知识图谱，并设定我们的研究任务，在多跳路径中突出负样本的表现。
其中O={(u,i)|u∈U,i∈I}代表隐式反馈集，在此集合中每个(u,i)对表示用户u与正项i之间的历史交互关系；U和I分别代表用户的集合与项目的集合。
基于最近研究工作的启发，在知识图谱框架下组织项目属性与外部知识，并整合交互数据集。正如先前的研究成果表明，在项目属性与KG实体对齐的基础上构建关联关系能够提升模型性能。
在任务描述中我们通过整合用户的显性偏好信息与项目属性信息构建了一个完整的知识感知框架 以此为指导实现采样器的高效学习。

采样器fs（.）采用ΘS参数化方法。该采样器通过生成未观察项目的经验分布来推导出具有知识感知能力的负采样项目j。此外，在正例(u,i)交互中，在根节点i出发进行路径遍历直至终止于未观察到的项j时所形成的多跳连接关系有助于解释为何目标用户u对负样本j缺乏兴趣。例如，在这种情况下,j2可能是u1行为在i1与i4之间差异的一个关键因素。
为此,我们旨在探索KG中的结构信息,尤其是节点间的高阶连通性,以便发现合适的负例子集。
对于正例(u,i)交互,我们可以从根节点i出发进行路径遍历直至终止于未观察到的项j,将多跳连接视为i与j之间的关系。
然而,值得注意的是,不同路径在发现负例子的过程中具有不同的置信度水平,并非所有的路径都能有效地提取出有效的负例子信号。

具有信息性的两个Itemsi和j由于共享相同的KG实体e′而可能具备相似的表现特征。它们之间的配对比较关系在推荐参数上能够提供较为显著的梯度变化。另一方面这些关系能够反映出用户的真实偏好因为如果e′是影响u兴趣的重要因素那么通过其他途径如搜索营销或广告系统u已经接触过j这一情况则表明u对j可能并不十分感兴趣。因此(u j)被视为一个更为优质的负样本用于训练推荐模型会更加合理一些。此外如果我们认为以较低置信度标记为负样本的情况值得进一步探索那么可以从i→e→j′→e′→j这样的路径中发现新的项并赋予其较高的负置信度

METHODOLOGY

该框架由一个推荐器和一个采样器组成。 然后，详细阐述了采样器，KGPolicy，其目标是学习探索到KG上的负例。进行探索的操作分为三个步骤。
1） 图形学习模块，它预先准备节点的高质量表示。
2） 邻居注意力机制模块 它利用两个注意模型进行路径查找，并确定下一个访问哪个合适的节点。
3）neighbor pruning module 这减少了搜索空间，以解决上述模块中的计算过载。 反复进行这样的探索，KGPolicy最终能够产生一个潜在的负例项目来配对正例目标。
最后，KGPolicy和推荐被共同训练以提供推荐。

Recommender
基于实验结果表明, 我们的知识感知采样器具有良好的性能, 为此我们采用了高效的矩阵分解(MF)方法进行推荐. 具体而言, MF通过将用户与项目的ID信息转换为嵌入表示, 并利用用户与项目嵌入之间的内积关系构建预测模型, 从而估算出用户u对项目i的选择可能性.

其中，

是(u,i)相互作用的预测分数。

我们使用成对的BPR损失作为目标函数来优化和学习ΘR的参数。

衡量负样本的信息性时（即评估其重要性程度），可以关注梯度的大小（即其变化范围）。这反映了三元组(u, i, j)对提升ΘR性能的作用（具体而言是该模型在训练过程中对于这一特定关系的学习效果）。在这种情况下（即当一个低质量的负面实例被分配到比i更低的位置时），梯度幅度趋近于零，则该实例对优化问题的影响变得微乎其微。相比之下，在与正面实例进行比较时（即当一个信息丰富的负面实例被分配到与正面实例相近的位置时），两者之间的预测分数差异将较小。

Knowledge-aware Sampler
我们以KG作为取样器的环境。 这使我们能够利用项目和KG实体之间的丰富关系，特别是高阶连通性，以探索更合适的负例。 基本思想是，以目标用户为条件，从正例的项目开始，学会在KG结构上探索，然后沿着探索的路径产生可能的负例。 在大规模的KGs中，无法列举所有未观察到的项目的可能路径，因为它需要劳动密集型的特征工程，存储这些路径和消耗时间提取有用的信号，需要内存。 因此，我们设计了一种智能采样器作为强化学习(R L)，对KG进行自动探索。

引入强化学习和马尔科夫决策过程的知识

Sampling as Reinforcement Learning
我们将采样作为马尔可夫决策过程（MDP）M={S，A，P，R}， 其中A={a}是从探索路径操作导出的一组动作（action），S={s}是探索过程中抽象路径的一组状态（state），P是状态转移概率矩阵，R是奖励作用（reward）。 我们介绍了RL的KG环境（相当于environment）的关键要素如下:
Exploration Operation
为了获得知识图谱中的原子路径。 我们定义了一种新的探索操作，包括两个连续的边。比如说：

State

Action

State Transition Dynamics

Reward

Prediction Reward:

Similarity Reward ：

考虑到这两个因素，我们设计了一个奖励函数：

Objective Function
为了设计一个随机策略π以调整采样器参数ΘS，并以最大化预期的累积折扣回报为准则进行优化：

在模型中，γ被定义为衰减因子；π的期望值旨在最大化与用户相关的三元组（u,i,j）的概率。

Knowledge Graph Policy Network.
我们引入一个网络来生成策略π，以及对每一项行动（action）的置信度。 首先，我们描述了一个图形学习模块，它为每个节点生成向量表示，然后在表示上构建一个邻居注意模块，以选择一个合适的邻居作探索访问，它与邻居剪枝模块耦合，以减少探索空间。
Graph Learning Module
在最近的图神经网络(GNNs)的启发下，我们使用G上的图GraphSage和用户项二部图O，目的是嵌入用户、项目和KG实体的向量表示。
eg. 在第l个图卷积层中，以节点e为起始节点接收从其邻居传播的信息以更新其向量表示形式，如：

Neighbor Attention Module

Attentive KG Neighbors

eg.

因为注意力评分取决于关系空间中eh和et之间的距离,为了避免有的距离太大而引起的权重干扰,所以要进行归一化处理.公式如下:

Attention Item Neighbors.

基于此，在每个探索操作中生成相应的负例概率。
Neighbor Pruning Module
通过设计的邻居去核模块（Neighbor Pruning Module），搜索空间被有效限制在正例项目的多跳邻居范围内。值得注意的是，在实际应用中，某些节点的邻居数量（如流行项目或通用KGconc）往往非常庞大。这种现象进一步影响了整体的探索效率。基于上述分析，在DNS中获得了一些启发性信息后，我们提出了一种高效的剪枝策略来保留有潜力的邻居节点。