【论文阅读】05-TimeTraveler：Reinforcement Learning for Temporal Knowledge Graph Forecasting

Abstract（摘要）

• 提出目的：

  • 大多数现有的方法都主要集中在历史时刻的时间推理上。
  • 少数研究工作是基于现有的知识图谱（TKG）进行推断。
  • 目前有2个挑战：
    • 如何有效地建模时间信息来处理未来的时间戳？
    • 如何通过归纳推理来处理随时间出现的新实体？

• 解决方式： * 智能体利用历史知识图谱快照检索答案 * 该方法旨在通过相对时间编码函数捕获时间跨度信息，并基于Dirichlet分布设计了一种时间形奖励机制来指导模型学习 * 开发出一种隐含实体的表现形式以显著提升模型在归纳和推理方面的性能

• 实验结果： * 我们将在未来的某个时间点评估我们的方法用于此链接预测任务

• 在四个基准数据集上进行了系统性的测试表明, 相比现有的先进模型, 该方法不仅提升了模型性能, 还具备更高的可解释性. 此外, 该模型在计算负担方面表现更为优秀, 同时减少了所需的模型参数数量.

1 Introduction（引言）

• 基于三元组的知识图谱（KGs）使用数学表达式(e_s,r,e_o)进行表示 ，其中每个三元组(e_s,r,e_o)代表多关系有向图中的标记边。
  • 通常情况下 ，知识抽取（Knowledge Extraction, KE）将三张量知识图谱（Tri-Partite KG, TKG）建模为一系列静态的知识图谱快照。

基于现有事实进行新事实的推断过程主要包含内插与外推两大类。
其中内插是指利用推理机制补充历史时间点缺失的事实内容。
而外推侧重于未来事件的可能性预测。
通过构建未来时间节点的路径预测模型来深入分析这种可能性。

• 外推面临着两大主要问题 * 不可见的时间戳标记：待预测事件的时间戳在训练集中缺失

• 未识别的对象：随着数据不断积累，新实体可能随之出现而这些待预测事件可能涉及之前未识别的对象

• 当前流行的外推技术 * RE-NET （Jin et al, 2020） 利用递归神经网络（RNN）提取前后时间段的事实数据，并以此预测未来的时间序列数据。

• CyGNet （Zhu et al., 2021） 则侧重于分析历史数据中的重复现象，并通过统计方法揭示事件发生的规律性。

• 这些方法本身
• 这些方法仅通过随机向量来表征未曾见过的实体，并将链路预测任务归类为一个多类分类问题。
• 此外，在预测过程中也未能明确地指出历史事实对预测结果的影响。

对于静态的知识图谱（KG），我们提出了一种新的基于时间路径的强化学习（Reinforcement Learning, RL）模型，并命名为"Time Travel Erver"（TITer），其主要功能是进行"知识图谱外推推理"（TKG extrapolation）。该模型从查询主题节点出发，在与当前节点相关的时间事实序列中逐步转移至新节点，并最终停靠在答案节点上。
基于历史 KG 快照来进行未来查询结果预测的方法较为有限，在现有技术中尚属首次实现这一目标。

• 一种专为外推TKG推理设计的强化学习模型被首次提出，并基于可解释性原则实现了对不可见时间节点及实体特征的有效处理。
• 我们提出了一种创新的时间信息建模方法。通过相对时间编码函数捕获智能体的时间信息，并通过时间形奖励引导模型的学习过程。
• 我们开发了一种新的不可见实体表示机制。该机制通过结合查询与训练实体嵌入生成潜在实体向量，在不影响计算效率的前提下显著提升了归纳推理的效果。
• 经过大量实验验证，我们的模型在计算资源与参数数量上均远超现有技术。

2 Related Work（相关工作）

2.1 Static Knowledge Graph Reasoning（静态知识图谱推理）

可参考我之前写的论文阅读综述部分

基于嵌入的方法中 ，空间的表示有很多，如：

Euclidean 空间 、复数向量空间 以及最新的流形空间*通过基于 entity 和 relation 的候选事实评估来推导缺失事实

其他的方法使用深度学习模型对嵌入进行编码 ，如：

• 卷积神经网络（CNN） 用于提取图像数据中的抽象且深入的理解能力。
• 图神经网络（GNN） 捕获或学习不同层次的空间关系和连接模式。

基于路径的方法也主要应用于知识图谱推理领域 * Lin等人（2015）与Guo等人（2019）通过递归神经网络整合了路径意义* * 强化学习框架（Xiong等, 2017;Das等, 2018;Lin等, 2018）将这一任务建模为以马尔可夫决策过程的形式描述了实体对之间的关系路径, 并且相较于基于向量表示的方法具有更高的可解释性*

2.2 Temporal Knowledge Graph Reasoning（时间知识图谱推理）

• 基于时间属性的扩展：一部分人通过赋予静态知识图谱的时间维度而实现了动态特性建模。他们对嵌入机制与评分函数进行了相应优化（Jiang et al ., 2016b；Dasgupta等人，2018；Goel et al, 2020；Lacroix et al, 2020；Han et al ., 2020a）。
  • 研究者们发展出消息传递网络以捕捉图快照中的邻域特征（Wu et al ., 2020；Jung et al, 2020）。
  • 这些方法被成功应用于内插任务中。

• 在外推场景中

• Know-Evolve （Trivedi等人, 2017）与GHNN （Han等人, 2020b）采用了时间点过程来模拟连续时域中的演化情况；而Tango则通过基于常微分方程的方法构建了连续时间模型。

• RE-NET提取快照图中的多步关系信息，并通过递归神经网络分析不同时间节点上的实体互动模式。

• CyGNet发现许多事实往往呈现出重复模式并参考历史数据作为建模依据。

• 这些方法无法解释其预测结果也无法处理新出现的实体。

• 基于子图采样技术构建推理图的该模型xERTE。

• 尽管GraphSAGE（Hamilton等人，2017）的方法允许处理不可见节点的可能性得以实现，并且随着推理图的持续扩展导致了推理速度显著下降。

3 Methodology（方法论）

• 与之前关于KGs的研究沿用相同的思路（Das等人, 2018），我们将RL公式构建为时间图上的"基于行走的查询-问答"方案：
  • Agent系统性地从源节点出发进行路径探索，在每个步骤中选择出边逐步遍历至新的节点直至抵达目标。
  • 在本节中首先定义了任务。
  • 接下来详细描述了强化学习框架并阐述了如何将时间信息整合到策略强化学习模型中。
  • 最后提出了优化策略并设计了针对先前未识别实体的有效归纳均值表示方法。
  • 图2展示了模型的整体架构。

3.1 Task Definition（任务定义）

• 基本概念

• 一个事实在知识图谱增量式抽取（TKG）中可以被表示为一个四元组quadruple（start实体, 关系, 结束实体, 时间戳）

• 在时间点t时, 关系r描述了start实体到结束实体之间的一条有向边

• 可以通过时序演变的图结构来描述知识图谱增量式抽取的过程

• 具体而言, G_{(1,T)}= \{ G_1, G_2, ..., G_T \}, 其中每个时间点t对应一个快照模型G_t=\{E_t,R,F_t\}, 这里E_t和F_t分别代表实体集合和事实集合在时间t的状态

• 通过设置每个图节点为包含实体及其时间戳的一对：e^t_i = (e_i, t)。

• 然而一个事实（ e_s,r,e_o,t）能够被视为从源节点 e^t_s 到目标节点 e^t_o 有一条类型 r 的边。

• 外推KG推理旨在模拟知识图谱随时间演变的过程，在未来时间段内进行链路预测。这种方法还能够预判不久之后即将发生的事件。
• 给定查询 （e_q,r_q,?,t_q）或者（?,r_q,e_q,t_q），我们有一组事实{(e_{si},r_q,e_{oi},t_i|t_i＜t_q)}
• 基于现有事实构建现有的TKG知识图谱后，则我们的目标是推测查询中的缺失实体或关键实体。

3.2 Reinforcement Learning Framework（强化学习框架）

• 由于典型的TKG快照缺乏明确的界限，在这样的情况下，并不存在任何一种方法可以让Agent跨越两个快照进行信息传递。因此，在这样的情况下，并不存在任何一种方法可以让Agent跨越两个快照进行信息传递。
  所以按照需求依次增加三种类型的边
  • 反向边 ：
    • 对于四元组（ e_s, r, e_o, t ），生成相应的反向边 (e_o, r^{-1}, e_s, t) ，从而确保这种关系在反转后依然成立。
    • 推理 ( ?, r, e_q, t ) 和推理 ( e_q, r^{-1}, ?, t ) 的过程是相同的。

自环边：
该机制允许Agent在一个特定位置上停留，并在该Agent在其搜索范围内展开固定数量的步骤后作为终止操作。

• 时间边界：
• 当存在（ e_s, r, e_o, t_i ）且 t_j 位于 t_i 和 t_q 之间时，则 Agent 可通过关系 r 连接节点 e_s^{t_j} 和节点 $ e_o^{t_i} 。这种结构的时间边界有助于表征实体随时间的变化情况。
• 图1展示了具有时间边的图表。

图1：带颞边的TKG示意图。为了确保图形呈现的清晰度，在绘制过程中省略了自反边和逆向边。虚线标记为时间边

通过五元组来进行表示：States * S由五元组进行表示：s_l = (e_l, t_l, e_q, t_q, r_q)
*e_l, t_l：在第l步被访问的那个节点；它表征当前信息。
*e_q, t_q, r_q：在查询过程中所涉及的元素；它们表征全局信息。

• Agent从查询的源节点出发，则其初始状态s_0 = (e_s, t_s, e_t, t_t, r_t)

Action * A_l由第l步可选动作构成
* A_l∈A定义于节点e^{tl}_l的出边构成的集合中
* 具体来说，集合 A_l 应该是\{(r{'}, e', t{'}) | (e_l, r{'}, e', t{'})\}的形式，并且满足t' ≤ t_lt' ≤ t_q * 然而一个实体通常会积累大量相关历史事实这将产生大量可选操作 * 因此得出最终一组可选动作 A = {a | a ∈ A_{out}(e)}$是通过从上述边集采样获得的

Transition * 环境状态经由Agent选择的边传输至新节点

• 该函数体是状态S与动作A共同作用的结果。

Rewards

• 当状态变量s_L满足特定条件时，在最终State中到达目标实体位置可以获得成功 rewards 值1；否则，在非目标位置获得失败 rewards 值0
• 当状态变量s_L满足特定条件时，在最终State中到达目标实体位置可以获得成功 rewards 值1；否则，在非目标位置获得失败 rewards 值0

通常情况下，在特定时间段内具有相同实体的四重组会导致时间和空间上的多样性以及时间间隔的稀疏性；由于这种特性（或性质），在查询结果中出现的答案实体会随着时间呈现分布特征；我们可以通过将这种先验知识融入奖励函数来指导智能体进行学习。

时间形奖励可以让Agent知道哪个快照更有可能找到答案

基于训练集，我们估计每个关系的狄利克雷分布

然后，我们用狄利克雷分布来塑造原始奖励式子2

α_{r_q} 是关系r_q的狄利克雷分布的参数向量，可以从训练集中估计出

在训练集中的每个与r_q相关的四元组中，请统计该对象实体在历史快照中的出现频率。由此生成一个包含多项式特征的集合D={x₁,…,x_N}。

使其尽可能最大化 式子3 。这样就是评估α_{r_q}

最大值可以通过不动点迭代计算，并进行更多的计算附录A.5

由于Dirichlet分布具有共轭先验特性，在获取更多的观测数据用于模型训练时，能够方便地进行更新

3.3 Policy Network（策略网络）

• 设计一个策略网络表示智能体在连续空间中建模，其中个和为模型参数。
• 策略网络由以下三个模块组成

• dynamic embeddings are employed to assign dense vector representations r∈{\mathbb{R^{d_r}}} to each relationship r∈R

• The entity attributes undergo temporal evolution, prompting the adoption of a relative time encoding strategy

• Through dynamic embeddings, nodes in the graph structure at time step t, denoted as e^t_i = (e_i, t), are represented

• By mapping entities to e∈{\mathbb{R^{d_t}}}, their inherently stable characteristics are captured

• A relative time encoding function \Phi(\Delta t) ∈ {\mathbb{R^{d_t}}} is constructed to encode temporal information

• Where \Delta t = t_q - t, and \Phi(\Delta t) refers to equation (4). Herein, w and b denote learnable parameter vectors, while \sigma represents an activation function.

  • d_r,d_e,d_t表示嵌入的维度
  • 我们可以将节点e^t_i，表示为e^t_i=[e_i;\Phi(\Delta t)]

• 路径编码技术 * 搜索历史记录信息 h_l = ((e_q, t_q), r_1, (e_1, t_1), \dots, r_l, (e_l, t_l)) 是所采取的一系列行动的顺序，并且 Agent 对所采取的历史行动进行编码；使用 LSTM 网络进行建模。
  式子5中的变量 r_0 被定义为初始关系，在模型训练过程中起着重要的初始作用；当最后一个执行动作形成自循环结构时（即最后一个动作是自循环时），我们选择性地保持 LSTM 状态不变以避免状态信息过早丢失。

• 动作评估 * 为每一个可选动作赋值并计算状态转移的可能性
• a_n表示步骤中的一个可选动作
• 未来的事件往往是不确定的，并且在某些查询中缺乏明确的因果关系链；因此，在这些情况下，实体与查询之间的相关性往往显得更为关键
• 通过加权的动作评估机制来指导智能体更加关注目标节点的属性或边的信息
• 使用两个多层感知机（MLP）对状态信息进行编码处理
• 通过计算相似度指标获得候选动作的目标节点评分以及出边评分
• 代理将两个分数进行加权汇总后得出最终候选动作评分, 表达式6

在公式6、7、8中，
W_1、W_e、W_r、W_β各自代表可学习的矩阵。
在对所有候选动作进行评估时，在第l步的策略阶段，可以通过softmax函数激活。

3.4 Optimization and Training（优化与训练）

我们将在搜索路径长度被设置为L之后，在策略网络中生成一个长度为L的轨迹。
策略网络将以最大化所有训练样本的期望奖励为目标进行训练。
接着采用策略梯度方法进行优化。
强化算法（Williams, 1992）通过迭代 F_{train} 中的所有四组，并利用随机梯度更新 \theta`式子10。

图2:TITer的概述。对于给定的一个查询(e_q, r_q, ?(e_{gt}), t_q)，TITer从节点e_q^{{t_q}出发。在每一阶段中，在当前节点处基于策略网络Π_θ探索到一个新的节点。我们以搜索过程的最后一阶段为例：设当前节点为e_l}{t_l}。政策网络则用于评估候选操作（r₁,e₁,t₁）的价值并生成相应的评分机制。基于所有候选操作分数计算得到的动作转移概率分布后会随机选择一条出边执行对应的行为动作。当搜索完成时时间形奖励函数将根据估计的Dir(α_rq)给予agent一个奖励。

3.5 Inductive Mean Representation（归纳平均表示）

随着新实体随着时间不断涌现出现我们提出了一种新的实体表示方法用于表征那些以往从未被观察到的存在
先前的研究(Bhowmik和de Melo 2020 Han等人 2021)通过邻居信息聚合的方式实现了对看不见实体的表现
然而新出现的实体通常仅有少量链接导致获取的信息十分有限
例如对于问题(Evan_Mobley plays_for ? 2022) 在以往的时间中不存在Evan_Mobley这一实体但我们仍能推断出其身份并为其分配一个更为合理的初始嵌入以便于后续推理过程
我们提出了另一种方法即通过融合查询信息与训练样本中的嵌入向量来表征未曾见过的新实体该方法被称为归纳平均(IM)如图3所示

图3：IM机制的说明

• 对于一个隐藏的实体e_q"，“t_q−3"：r₁, r₃"表明该实体在时间点t_q−3"处具有r₁", r₃"两种属性间的关联关系，并基于属性对应的特征矩阵进行更新操作后得到$t_{q}-1"时刻的IM表示。
• 然后，在回答查询($e_q.r₂",?.t_q")时我们则基于属性E_r₂进行预测偏移。

• G(t_j, t_q-1)代表测试集中的一个快照片段，在此期间查询实体e_q首次出现于时间戳t_j所对应的图中，并初始化了一个随机向量。
  • 如果存在包含(e_q, r)的关系四元组，则称r为实体e_q在其生命周期内的共现关系。
  • 需要指出的是，在时间维度上，实体间的关系会随着演进而发生变化。
  • 我们将这种随时间变化的关系集合称为\mathcal{R}_t(e_q)。
  • 对于具有共现关系r, 我们定义集合\mathcal{E}_r, 其包含所有与$r`具有该关系的所有训练实体。
  • 进而得到具有相同共现关系$r`的所有实例及其归纳平均表示（如式（11）所示）。

• 基于具有相同共现关系r的实体具有相似特征这一事实，在信息抽取（IM）中可以通过时间流逐步更新q_{}向量的状态表示。
• 0≤μ≤1作为一个超参数，在该模型中我们可以得到相应的公式推导结果。
• 通过关系r_{q}的学习过程，在后续推理阶段将能够有效提升实体表达的相关性。
• 为了处理(e_{q}, r_{q}, t_{q})这一查询请求，在模型构建阶段需要综合考虑多个时间点的信息特征。

4 Experiments（实验）

4.1 Experimental Setup（实验设置）

• 数据集
  • ICEWS：综合危机预警系统（ICEWS）是一个事件数据集。ICEWS14和ICEWS18是2014年和2018年ICEWS事件的两个子集，时间粒度为天
  • WIKI、YAGO：是两个包含带有时间信息的事实的知识库，我们使用时间粒度为年的子集