Incorporating Graph Attention Mechanism into Knowledge Graph Reasoning Based on Deep Reinforcement Learning

摘要

知识图(KG)推理的目的是寻找关系的推理路径，以解决KG中的不完全性问题。以前的许多基于路径的方法，如PRA和DeepPath，要么缺乏记忆部件，要么在训练中卡住。因此，他们的表现总是依赖于良好的训练。本文提出了一种基于AttnPath的深度强化学习模型，该模型将LSTM和图注意机制作为记忆组件。我们定义了平均选择率(MSR)和平均替换率(MRR)两个指标来定量衡量查询关系的学习难度，并利用它们在强化学习框架下对模型进行微调。同时，提出了一种新的增强学习机制，使agent每一步都向前走，以避免agent在同一实体节点上不断陷入停滞。在此基础上，该模型不仅可以摆脱训练前的训练过程，而且与其他模型相比，可以达到最先进的性能。我们使用不同的任务在FB15K-237和NELL- 995数据集上测试我们的模型。大量的实验表明，该模型与现有的许多最先进的方法相比是有效的和有竞争力的，并且在实践中表现良好。

介绍

• 推理的方法

  • 基于规则
  • 基于路径
  • 基于嵌入
    同时，它提供了一个新的视角，将深度强化学习(Deep Reinforcement Learning, DRL)引入到预测缺失环节的任务中，如DeepPath (Xiong et al.， 2017)，这是一种基于路径的方法。DeepPath是第一个将DRL整合到KG推理中的作品。与PRA相比，它取得了显著的改进，但仍然存在一些缺点。首先，它缺少记忆部件，因此需要预先培训。训练前的操作需要为模型训练提供许多已知(或存在)的路径。这种蛮力操作可能会使模型在预先训练的给定路径上过度拟合。其次，在训练时对KG中不同的关系设置相同的超参数是不合适的，忽略了实体之间连接的多样性。最后，当代理选择了一个无效的路径时，它会停止并重新选择，这会导致不断地选择这个无效的路径，最后卡在一个节点上。因此，本文针对上述不足，提出了一种新的深度强化学习模型和算法。该模型也属于基于路径的框架。我们的贡献可以总结如下

• DRL的缺陷

  • 缺少记忆部件，需要预先训练
    • 训练前的操作需要为模型训练提供许多已知(或存在)的路径–》过拟合
  • 不同关系超参数不同，忽略了实体之间连接的多样性
  • 当代理选择了一个无效的路径时，它会停止并重新选择–卡住

• 本文的贡献

  • LSTM+图attention作为记忆组件，不用再预训练了
  • 定义了两个度量标准(MSR和MRR)，以定量地度量学习关系的可替换路径的难度，这些可替换路径用于对模型进行微调。
  • 提出了一种新的增强学习机制，通过强制agent每一步都向前走来避免agent在同一实体节点上不断陷入停滞。

相关工作

到目前为止，已经有许多工作被提出来解决KG不完全的问题。

• 基于规则的方法，如
  • ProPPR (Wang and Cohen, 2016)和Neural LP (Yang et al.， 2017)，通过人工或数学逻辑规则生成推理规则，然后根据现有的三元组将其应用于填补缺失的环节。虽然这类方法有坚实的数学背景，但它们很难扩展到大型的kg，因为它们直接操作符号，而可能的推理路径的数量与实体的数量呈指数关系。
• 基于嵌入的方法，如
  • TransE (Bordes et al.， 2013)和TransR (Lin et al.， 2015)，将实体和关系映射到低维连续的向量空间中，获取实体和关系之间的距离特征。然后，通过比较两个训练实体嵌入和查询关系嵌入之间的距离来判断查询关系是否存在。这种方法需要KG中的所有三元组都参与训练，只适用于单跳推理。
• 基于路径的，如
  • PRA (Lao et al.， 2011)和DeepPath (Xiong et al.， 2017)，训练一个agent在一个KG上导航，找到某个关系的可替换路径，然后将其作为下游任务的特征。路径排序算法(PRA)是第一个基于路径的推理方法。
  • Neelakantan等人开发了一个基于RNN的组合模型，该模型非原子性地组合了一条路径的含义和多跳关系连接的原因(Neelakantan et al.， 2015)。
  • Guu等人提出了一种软边遍历算子，该算子可以递归地应用于预测路径，减少TransE和TransR等单跳KG完井方法面临的级联传播误差(Guu et al.， 2015)。
  • Toutanova等人提出了一种动态规划算法，该算法将所有有界长度的关系路径合并到一个KG中，并对组合路径表示中的关系和中间节点进行建模(Toutanova等人，2016)。这样的表示可以帮助生成更多高质量的推理路径。
  • Das等人将DeepPath (Xiong等，2017)改进为MINERVA (Das等，2018)，后者从QA s的角度看待KG。它去掉了预训练，引入LSTM来记忆以前走过的路径，并训练一个代理在某个实体上运行，如果它相信这个实体是正确的答案。
  • Lin等人通过引入奖励形成和行动退出来改进这两种方法(Lin et al.， 2018)。奖励塑造用动态惩罚代替无用选择的固定惩罚，既可以基于基于边缘的预训练嵌入，如TransE，也可以基于基于概率的嵌入，如ConvE (Dettmers et al.， 2018)。而action dropout则随机地掩盖了一定比例的有效action，以减少查询关系的不相关路径。
  • DIVA (Chen et al.， 2018)将路径作为潜在变量，将关系作为观测变量，建立变量推理模型，完成KG推理任务。它还使用波束搜索来扩大搜索范围。
  • M-Walk (Shen et al.， 2018)利用另一种称为蒙特卡罗树搜索(Monte Carlo Tree Search, MCTS)的RL算法来解决稀疏奖励问题。注意机制首次被引入多跳KG推理中(Wang et al.， 2018)。但是，它只计算查询嵌入的注意权重和所有找到的路径嵌入。它们被用来帮助判断vanilla模型找到的答案是否正确。

方法

• 由于我们使用强化学习(RL)作为序列决策模型的训练算法，我们首先在KG推理中引入RL框架的基本元素，包括环境、状态、动作和奖励。

• 环境:在本任务中，环境指的是整个KG，不包括查询关系及其逆。整个培训过程环境保持一致

• 状态:agent的状态由三个部分连接:

  • 嵌入部分、
    • deepPath中用了TransE,这里用TransD（映射到关系所带的向量空间中
    • $e'=(r_pe_p'+I)e\\m_t=(e'_t,e'_{target}-e_t')$e′=(rp​ep′​+I)emt​=(et′​,etarget′​−et′​)
  • LSTM部分
    • $h_t=LSTM(h_{t-1},m_t)$ht​=LSTM(ht−1​,mt​)
  • 图形注意部分

• 动作：选哪个关系（边）走

  • 有关系-有效边
  • 无关系-无效边

• 奖励

  • 一步的无效操作：-1
  • 可以获得全局解的（一整条路径）：convE(a series of actions can lead to ground truth)
  • 奖励是全局精度、路径效率和路径多样性的加权和。根据约定，全局精度设置为1，路径效率为路径长度的倒数，因为我们鼓励代理尽可能少的步进。(和DeepPath一样）

• 使用注意力机制Graph Attention mechanism (GAT)

  • self-attention在实体层
  • attention权重用一层前馈神经网络训练
  • $\alpha_{ij}=LeakyReLU(a^T(W_{ei'},W_{ej'}）\\只计算它和它的邻居，j是与i相邻的节点，然后normalize\\\alpha_{ij}=\frac{\alpha_{ij}}{\Sigma_{k\in N_i} \alpha_{ik}}\\a_i=\Sigma_{k\in N_i}\alpha_{ik}W_{e_k}\\s_{i,t}=[m_{i,t};h_t;a_t]$αij​=LeakyReLU(aT(Wei′​,Wej′​）只计算它和它的邻居，j是与i相邻的节点，然后normalizeαij​=Σk∈Ni​​αik​αij​​ai​=Σk∈Ni​​αik​Wek​​si,t​=[mi,t​;ht​;at​]
  • 然后输入一个三层前馈神经网络，其最终输出是一个长度等于所有关系的数量(以KG为单位)的Softmax概率。代理选择一个动作并获得奖励。当它成功到达尾部实体或在指定次数内没有到达时，整个事件的奖励将用于更新所有参数。
    
    

Mean Selection Rate (MSR) and Mean Replacement Rate (MRR

对于不同的查询关系，需要为每个查询关系训练不同的模型。而在实践中，每个关系的难度值都是不同的。某些关系可能具有更多的替换关系，这表明agent可以很容易地选择从head实体到tail的替换路径。因此，我们发明了两个指标，平均选择率(MSR)和平均替代率。在这里，定量地测量每个关系的不同值。

较低的MSR表示学习r比较困难，因为与关系r相关的实体可能有更多方面。

较高的MRR表示一个关系可能有更多的替换关系，因此更容易学习，因为代理可以直接选择一个替代关系来到达目的地。在我们的模型中，我们有三种方法来防止过度拟合:L2正则化、dropout和action dropout。然而，对于比较容易学习的关系(高MSR和MRR)，我们希望实施更多的正规化，以鼓励代理寻找更多样化的路径，而不是过度拟合立即成功。否则，对于较难学习的关系(MSR和MRR较低)，我们最好关注路径找到的成功率，因此我们应该减少正规化。
为简单起见，我们使用指数来计算关系r的难度系数。它被定义为exp(MSR®+MRR®)，并分别乘以三种正则化方法的基本速率。正则化方法的基本速率是基于KG的，在相同KG中的所有关系之间共享。

在此基础上，我们提出了一种新的训练算法，如算法1所示。在我们的算法中，我们的贡献之一是，**当代理选择了一个无效路径时，我们的模型不仅惩罚了它，而且还迫使它选择一个有效的关系来前进。**神经网络的概率在所有有效关系上被归一化，这些有效关系反过来又决定了强制动作的概率。初始化之后，第6行根据网络的输出对操作进行采样。当代理选择了一个无效的操作时，第7行10被执行，第9行10强制代理前进。当代理选择一个有效的操作时，执行第12行。22和25行19日更新参数无效的行为,有效的行动成功的事件,和有效的行动在一个不成功的事件,分别与奖赏-1，Rtotal Rshaping。