根据阅读进度，时不时会更新

[toc]

HIP Network

HIP Network: Historical Information Passing Network for Extrapolation Reasoning on Temporal Knowledge Graph,IJCAI2021

结构+时间

主要模型分为三个部分，每个部分各有一个损失函数。

SIP

SIP的全称是structural information passing，功能是获取在时间\(t\)的时候的图中的结构信息，具体来说就是对每个\(s\)进行编码（\(s_{s,t-1}\)），在这个模块使用的方法基于CompGCN，通过分解的方法有选择性的传递结构性知识。\(s\)在时间\(t-1\)时的分解化（disentangled）embedding为\(x_{s,t-1}\)，将\(x_{s,t-1}\)投影到\(K\)个空间：

\[h_{s,t}=U_s^Tx_{s,t-1},U_k \in R^{d_{in}\times \frac{d_{in}}{K}}\]

由此，得到此时的\(K\)个embedding，\(h_s=\{h_{s,1},h_{s,2},\dots,h_{s,k},\dots,h_{s,K}\}\)。

与很多以往做法不同的是，CompGCN不使用基于度量的方法直接计算\(r\)，而是去将\(r\)的embedding在进行节点更新时进行隐式的计算。令\(\phi(x_r,x_o)\)为分解操作（composition operation，例如减法、乘法和循环表示），将分解的结果同样投影到\(K\)个空间：

\[c_{o,k}=V_k^T\phi(x_{r,t-1},x_{o,t-1}),V_k\in R^{d_{in}\times \frac{d_{in}}{K}}\]

设置\(K\)个注意力权重，\(\alpha_k\)表示了消息\(\phi(x_r,x_o)\)与第\(k\)个\(s\)的组成部分的相关性： \(\alpha_k=\frac{\exp({\rm ReLU}(W[c_{o,k};h_{s,k}]))}{\sum_{k^\prime}\exp({\rm ReLU}(W[c_{o,k^\prime};h_{s,k^\prime}]))},W\in R^{1\times \frac{2d_{in}}{K}}\)

在固定\(s,r\)情况下，根据不同的\(o\)的权重进行加权求和，最终得到\(t\)时刻的\(s\)的编码： \(x_{s,k}^l=\sum_{(r,o^\prime)\in \mathcal{N}(s)}\alpha_kW_{\lambda(r)}^{l,k}c_{o^\prime,k}^{l-1},W_{\lambda(r)}^{l,k}\in R^{\frac{out}{K}\times \frac{in}{K}}\)

其中\(W_{\lambda(r)}^{l,k}\)是与关系类型有关的参数，CompGCN将关系分为了原始（original）、反向（inverse）和自循环（self-loop）。将最后一层所有的\(x_{s,k}^L\)拼接得到\(x_{r,t}\)。

TIP

TIP的全称是temporal information passing，功能是对实体对之间的事件演化模式进行建模，并跨时间集成信息，以生成实体和关系的时态embedding。对于一个实体\(s\)，可以通过SIP得到一系列embedding：\(\{x_{s,t-m+1},x_{s,t-m+2},\dots,x_{s,t} \}\)，其中\(m\)是时间窗口。文章中使用了一个时序自注意力层（temporal self-attention layer）去整合时间维度中实体的表示，并且将\(s\)的输出定义为：\(\{z_{s,t-m+1},z_{s,t-m+2},\dots,z_{s,t} \}\)。在每个时间步的输入上使用缩放点积注意力（scaled dot-product）去生成时间依赖的embedding：

\[e_{ij}=\frac{((XW_q)(XW_k)^T)_{ij}}{\sqrt{d}}+M_{ij},X\in R^{m\times d},W_q\in R^{d\times d}, W_k \in R^{d\times d}\\ \beta_{ij}=\frac{\exp (e_{ij})}{\sum_{j^\prime}^m \exp(e_{ij^\prime})},\beta\in R^{m\times m}\\ Z=\beta(XW_v),Z\in R^{m\times d}，W_v\in R^{d\times d}\]

其中，\(X\)是输入，\(Z\)是输出，\(\beta\)是注意力权重矩阵，\(W_q,W_k,W_v\)对应queries，keys，values的线性度量。为了确保未来的信息不被暴露，文中使用了掩码矩阵\(M\in R^{m\times m}\): \(M_{ij}=\left\{ \begin{aligned} & 0, & i\leq j \\ & -\infty, & otherwise \end{aligned} \right.\)

History Forward Module

通过SIP得到图谱结构的表示，通过TIP得到图谱时序的表示，论文设计了三种loss函数。

（1）temporal scoring function：\(I_t\)

\(I_t(s,r,o,t)=softmax(W_t[z_{s,t};z_{so,t};z_{o,t]}])_r,W_t\in R^{p\times 3d}\)，其中\(p\)是关系类型的数量。\(I_t\)使用了TIP的输出作为输入，这样就可以关注特定实体对之间事件的时间演化，从而预测下一个事件。

（2）structural scoring function：\(I_s\)

借用DistMult作为衡量函数：\(I_s(s,r,o,t)=\sigma(<x_{s,t},x_{r,t},x_{o,t}>)\)，其中\(<\cdot>\)表示点积。

（3）repetitive history scoring function：\(I_h\)

考虑到实体和关系在时序图谱中都是时间敏感的，这可能导致一些实体在时间窗口中可用的信息减少。根据观察到的许多事实沿着历史反复发生，可以从历史事件中选择性地生成新的事件来解决这个问题，在本文中，对每个实体和关系使用历史词汇（historical vocabulary），对应一个四元组\((s,r,?,t)\)，使用下列式子计算重复历史分数：

\[I_h(s,r,o,t)=softmax(W_h[e_{s,t};e_{r,t}]+V_t^{(s,r)})_o,W_h\in R^{q\times2d};e_{s,t},e_{r,t}\in R^d\\ V_t^{(s,r)}=v_1^{s,r}+v_2^{s,r}+\dots +v_{t-1}^{s,r}\]

其中\(q\)是实体个数，\(e_{s,t},e_{r,t}\)分别是实体和关系对于历史表现的建模（与时间和结构无关），\(v_{t^-}^{(s,r)}\)是与\(s\)和\(r\)相关的\(q\)维multi-hot indicator vector，若\(o\)为1，则表示四元组\((s,r,o,t^-)\)在图\(\mathcal G^{(t^-)}\)中存在。

最终的损失函数为将三种损失函数合并：

\[\mathcal L=\sum_{(s,o,r,t)\in \mathcal G^{(t)}}\sum_{*}-\log(I_{*}(s,r,o,t))\]

算法流程图：

CyGNet

Learning from History: Modeling Temporal Knowledge Graphs with Sequential Copy-Generation Networks, AAAI 2021

时间编码

模型分为两个部分，一个是复制模式（copy mode）和生成模式（generate mode）。在数据处理阶段，生成一个历史字典（historical vocabulary）：\(\{ h_{t_1}^{(s,p)}, h_{t_2}^{(s,p)}, \dots, h_{t_T}^{(s,p)}\}\)，其中\(h_{t_k}^{(s,p)}\)是一个N维的多热编码，表示头实体\(s\)和关系\(p\)对应的尾实体\(o\)出现在快照\(\mathcal G_{t_k}\)，将他们加起来得到： \(H_{t_K}^{(s,p)}=h_{t_1}^{(s,p)}+h_{t_2}^{(s,p)}+\dots+h_{t_{k-1}}^{(s,p)}\)

此时，\(H_{t_K}^{(s,p)}\)也为多热编码。

复制模式

对于任务\((s,p,?,t_k)\)的历史字典\(H_{t_K}^{(s,p)}\)中出现过的尾实体给予更大的权重。复制模式先生成一个index向量\(v_q\)： \(v_q=\tanh(W_c[s,p,t_k]+b_c)\)

根据\(H_{t_K}^{(s,p)}\)生成\(\dot H_{t_K}^{(s,p)}\)，将没有在之前出现过的实体对应的index给予一个小的负值（降低权重）: \(c_q=v_q+\dot H_{t_K}^{(s,p)},\\ p(c)=softmax(c_q)\) 生成模式

相对于复制模式，生成模式去掉了历史字典，直接使用embedding进行预测： \(g_q=W_g[s,p,t_k]+b_g,\\ p(g)=softmax(g_q)\)

最终结果将两种模式加权在一起： \(p(o\vert s,p,t)=\alpha * p(c)+ (1-\alpha)* p(g)\)

CluSTeR

Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs, IJCNLP2021

强化学习

论文通过强化学习进行时序知识图谱的学习，分为两个阶段

阶段一：搜寻线索

强化学习中的几个模块，对于任务\((e_s,r_q,?,t_s)\)

States：状态表示为\(s_i=(e_i,t_i,e_s,r_q,t_s)\in S\)，其中\(e_i(e_0=e_s)\)表示在时间步\(i\)搜索到的实体，\(t_i(t_0=t_s)\)表示在上一步采取决策（action）时的时间，\(e_s,r_q,t_s\)是被所有状态共享的。

Time-constrained Actions：设置最大搜索间隔时间\(\Delta\)，对于第\(i\)步的行为\(A_i\in \mathcal A\)： \(A_I=\{(r^\prime,e^\prime,t^\prime)\vert(e_i,r^\prime,e^\prime,t^\prime)\in \\ \mathcal G_{o:t_s-1}, \vert t^\prime-t_i\vert \leq \Delta, t_s-t^\prime \leq m \}\)

Transition：转移方程记为：\(\delta: S\times A \to S\)。

Rewards：反馈分为两个部分，双值反馈（binary reward）和实值反馈（real value reward），双值反馈指找到结果了就为1，否则为0，实值反馈由阶段二给出。

决策过程：

对于一个搜索路径\(h_i=(e_s,a_0, \dots,a_{i-1}),a_i=(r_{i+1},e_{i+1},t_{i+1})\)，称为线索路径（clue path），对每一个动作的编码为\(\mathbf a_i=r_{i+1} \oplus e_{i+1}\)，此时在路径中已不包含时间要素，使用一个LSTM进行编码： \(\mathbf h_i = LSTM(\mathbf h_{i-1},\mathbf a_{i-1})\)

给出决策公式： \(\pi(a_i\vert s_i;\Theta)=\eta(A_iW_2f(W_1[e_i\oplus h_i \oplus r_q]))\)

其中\(A_i\)是所有\(a_i\)堆叠而成的矩阵，\(\eta(\cdot)\)是softmax函数，\(f(\cdot)\)是ReLU函数。

具体的搜索方法使用Randomized Beam Search。

阶段二：时序推理

对于每个快照使用RGCN进行建模，将输出结果输入到GRU中： \(H_j=GRU([\hat{e}_s\oplus \hat{g}_j \oplus \hat{r}_q], H_{j-1})\\ p(e\vert e_s, r_q, t_s)=\sigma (H^T_{t_s-1}\cdot W_{mlp})\\ \hat{r}=p(e_I)\)

最后的结果\(\hat{r}\)作为实值反馈返回到阶段一。

TITer

TimeTraveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting, EMNLP2021

强化学习

强化学习中的几个模块，对于任务\((e_q,r_q,?,t_q)\)：

States：状态表示为\(s_l=(e_l,t_l,e_q,t_q,r_q)\in S\)，其中\((e_l,t_l)\)是在时间步\(l\)路径上的节点，\((e_q,t_q,r_q)\)是不变的。

Actions：\(\mathcal A_l =\{(r^\prime,e^\prime,t^\prime)\vert(e_l,r^\prime,e^\prime,t^\prime)\in \mathcal F, t^\prime \leq t_l, t^\prime < t_q \}\)。

Transition：转移方程记为：\(\delta: S\times A \to S\)。

Reward：初始的Reward函数\(R(s_L)\)，因为时间的稀疏性和变化性，可以将已知的结果作为一种先验知识（结果按时间具有一定的分布）来指导强化学习，具体为： \(\tilde R(s_L)=(1+p_{\Delta t_L})R(s_L),\\ \Delta t_L = t_q-tL,\\ (p_1,\dots,p_K)\sim Dirichlet(\alpha_{r_q})\)

由此可以取样: \(D=\{x_1,\dots,x_N \}\\ p(D\vert a_{r_q})=\prod_i p(x_i\vert a_{r_q})\)

决策过程：

对每个关系给予一个向量\(\mathbf r \in \mathbb R^{d_r}\)，论文使用一个动态嵌入表示\(\mathcal G_t\)中的每个节点\(e_i^t=(e_i,t)\)，并使用\(\mathbf e \in \mathbb R^{d_r}\)来表示实体不变的部分。对于时间，使用相对时间的编码方程： \(\Phi(\Delta t)\in \mathbb R^{d_t}\\ \Phi(\Delta t)=\sigma(w\Delta t + b)\\ e_i^t = [e_i;\Phi(\Delta t)]\)

使用LSTM对路径进行编码： \(h_l=LSTM(h_{l-1},[r_{l-1};e_{l-1}^{t_l-1}])\)

决策分数为： \(\phi(a_n,s_l)=\beta_n<\tilde e, e_n^{t_n}>+(1-\beta_n)<\tilde r,r_n>,\\ \tilde e = W_ef(W_1[h_l;e_q^{t_q};r_q]),\\ \tilde r = W_rf(W_1[h_l;e_q^{t_q};r_q]),\\ \beta_n = \sigma(w_\beta[h_l;e_q^{t_q};r_q;e_n^{t_n};r_n])\)

TARGCN

A Simple But Powerful Graph Encoder for Temporal Knowledge Graph Completion, Arxiv2021

基于时间取样

对于任务\((s_q,r_q,?,t_q)\)

时间邻居子图取样

论文首先基于时序上的邻居对\(s_q\)构建一个子图，\((s_q,t_q)\)是在\(t_q\)时刻的\(s_q\)的表示，寻找所有\((s_q,t_q)\)在时间上的邻居，定义如下： \(\mathcal N_{s_q,t_q}=\{(e,t)\vert (e,r,s_q,t)\in \mathcal G;e \in \mathcal E, t\in \mathcal T, r\in \mathcal R \}\)

对所有的邻居使用以下的加权机制进行取样： \(\frac{\exp(-\vert t_q-t\vert)}{\sum_{e,t^\prime\in \mathcal N_{s_q,t_q}}\exp(-\vert t_q-t^\prime\vert)}\)

时间感知关系聚合（Time-aware）

在完成取样之后，基于这些邻居节点进行上下文表示，时间感知的节点表示计算方法为： \(h_{(e,t)}=f(h_e\Vert \mathcal K(t,t_q))\)

其中\(h_e\)是与时间无关的实体表示，\(\mathcal K(\cdot,\cdot)\)将\(t-t_q\)映射到向量空间，使用下面的公式将邻居节点聚合： \(h_{s_q,t_q}=\frac{1}{\vert \mathcal N(s_q,t_q)\vert}\sum_{e,t\in \mathcal N_{s_q,t_q}}W(h_{(e,t)}\Vert h_r)\)

论文中假设关系是与时间无关的。

解码器使用DistMult，因为不需要额外的参数。值得注意的是，在数据集GDELT上，该模型表现得结果很好。

RE-GCN

Temporal Knowledge Graph Reasoning Based on Evolutional Representation Learning , SIGIR2021

之前的方法3个主要的限制：

1. 主要关注给定四元组的实体和关系，而忽视了每一个时间戳中的KG所有事件的结构依赖
2. 对每个历史四元组单独编码的效率较低
3. 忽视了一些实体的静态特征，如实体类型等

RE-GCN将KG中每个时间戳的结构信息、时序中相邻事实的序列信息和实体中的静态属性通过进化表示（evolutional representation）进行聚合。

进化单元（The Evolution Unit）

共现事实的结构依赖。使用一个w层的RGCN去对结构依赖建模。

跨时间相邻事实的序列模式。对于一个实体，它的序列模式通过历史事实进行反映，为尽量包含尽可能多的历史事实，模型需要考虑一个实体的所有相邻时间信息。 之前的结构依赖已经建模了每个时间快照内的结构信息，一种直接的方法是使用t-1时间的输出作为t时间的输入，但是这会带来over-smoothing的问题，即相同的一对实体之间如果有重复的关系，那么实体向量会收敛到同样的值，并且随着KG序列长度的增长，GCN的堆叠也会出现梯度消失的问题，所以文中使用了一种门机制来减轻以上问题（剑杪按：通常这些问题通过门机制解决比较有用）： \(\mathrm{H}_t=\mathrm{U}_t \otimes \mathrm{H}_t^\omega+\left(1-\mathrm{U}_t\right) \otimes \mathrm{H}_{t-1}\\ \mathrm{U}_t=\sigma\left(\mathrm{W}_4 \mathrm{H}_{t-1}+\mathrm{b}\right)\) 对于关系的嵌入，文中认为会受到当前时间快照中与该关系相关的实体的影响，即： \(\mathcal{V}_{r, t}=\left\{i \mid(i, r, o, t) \text { or }(s, r, i, t) \in \mathcal{E}_t\right.\) 将t-1时的实体嵌入和当前时间与关系相关的实体嵌入做池化操作，然后与关系的原始嵌入拼接，使用GRU去建模关系的序列模式： \(\vec{r}_t^{\prime}=\left[\text { pooling }\left(\mathrm{H}_{t-1, \mathcal{V}_{r, t}}\right) ; \vec{r}\right]\\ \mathrm{R}_t=GRU(\mathrm{R}_{t-1},\mathrm{R}^\prime_t)\) 静态属性

通过给KG增加新的边的方式来增加静态属性，例如实体A为“Police（Australia）”，可以构造为\((A,isA, Police)\)和\((A,country,Australia)\)。对于静态属性，同样使用RGCN（此处去除了self-loop）进行编码，文中使用一个角度限制来限制时序实体的编码与静态编码，即这两个编码之间的最大偏差不应该超过90°： \(\theta_x=min(\gamma x,90^\degree)\)

##