【论文阅读】HIP network: Historical information passing network for extrapolation reasoning on temporal knowledge graph Metadata authors:: Yongquan He, Peng Zhang, Luchen Liu, Qi Liang, Wenyuan Zhang, Chuang Zhang
container:: Proceedings of the thirtieth international joint conference on artificial intelligence, IJCAI-21
year:: 2021
DOI:: 10.24963/ijcai.2021/264
rating:: ⭐
share:: false
comment:: 时间知识图谱TKG，时间片上采用CompGCN，顺序关系上同时考虑时间片的顺序关系和实体对的顺序关系，并以三个得分函数为辅助进行推理。
前言 关于时间知识图谱的论文：HIP Network: Historical Information Passing Network for Extrapolation Reasoning on Temporal Knowledge Graph ，IJCAI，2021
问题描述 时间知识图谱（TKG）由一系列带有时间戳的子图组成，即
\mathcal{G}=\{\mathcal{G}^{(1)},\mathcal{G}^{(2)},\cdots,\mathcal{G}^{(T)}\} ，其中
\mathcal{G}^{(t)}=\{\mathcal{E},\mathcal{R},\mathcal{O}^t\} ，
\mathcal{E} 和
\mathcal{R} 分别表示实体和关系，
\mathcal{O}^t 表示在
t 时刻的事件集合。每个事件可以表示为
(s,r,o,t) ，其中
s,o\in\mathcal{E}, r\in\mathcal{R} 。
本文的任务是根据历史 KG 序列
\{\mathcal{G}^{(t')}\}(t'\le t) ，预测给定的 query
(s,r,?,t+\Delta t) （或者
(?,r,o,t+\Delta t) ）中的缺失实体。
OverView 本文提出了Historical Information Passing (HIP) network。在结构信息传递部分，基于CompGCN，以解构的方式更新结构表示，充分利用关系嵌入并有选择地聚合邻域信息。对于时间部分，模型为特定的实体生成关系嵌入来捕捉时间信息，并通过时间自注意力机制获得当前实体的嵌入。此外，论文从历史实体中考虑重复性信息。
本文的主要贡献如下：
论文提出了一个新的学习框架来处理TKG上的推理问题，它从时间、结构和重复性的角度传递历史信息。 论文特别考虑了信息传递过程中关系嵌入的更新，并提出了一种具有三个评分函数的多步骤推理算法，可以按顺序推断未来的事件。 HIP Network 模型架构如下图所示：
Structural Information Passing Module 首先论文根据最近的历史 KG
\mathcal{G}^{(t-1)} ，更新实体和关系的信息，来捕获邻居的相互作用。考虑到在时间知识图谱中，随着新邻居的出现 / 消失，需要更新相关的部分以保留有用的信息，因此论文使用了 CompGCN，以解构的方式更新结构表示。
具体来说，对于实体
s ，论文将它的解构表示
\boldsymbol{x}_{x,t-1} 投影到
K 个空间中：
\boldsymbol{h}_{s,k}=\boldsymbol{U}_k^T\boldsymbol{x}_{s,t-1}
其中
\boldsymbol{U}_k\in\mathbb{R}^{d_{in}\times\frac{d_{in}}{K}} 为第
k 个空间的参数，
K 为超参数。可以得到
K 个不同的分量的节点嵌入，即
\boldsymbol{h}_s = \{ \boldsymbol{h}_{s,1},\boldsymbol{h}_{s,1},\boldsymbol{h}_{s,1} \}
其中
\boldsymbol{U}_k\in\mathbb{R}^{d_{in}\times\frac{d_{in}}{K}} 为第
k 个空间的参数，
K 为超参数。可以得到
K 个不同的分量的节点嵌入，即
\boldsymbol{h}_s = \{ \boldsymbol{h}_{s,1},\boldsymbol{h}_{s,1},\boldsymbol{h}_{s,2},\cdots,\boldsymbol{h}_{s,k},\cdots,\boldsymbol{h}_{s,K}\} 。
与大多是 GNN 只对节点进行嵌入不同，CompGCN 在聚合时使用关系
\mathcal{R} 而不是矩阵，因此对于每个四元组
(s,r,o,t-1)\in\mathcal{G}^{(t-1)} ，还需要将实体 - 关系投射到
K 个空间上，如下所示：
\boldsymbol{c}_{o,k}=\boldsymbol{V}_k^T\phi(\boldsymbol{x}_{r,t-1},\boldsymbol{x}_{o,t-1})
其中
\boldsymbol{V}_k\in\mathbb{R}^{d_{in}\times\frac{d_{in}}{K}} 为第
k 个空间的参数；
\phi(\boldsymbol{x}_r, \boldsymbol{x}_o) 表示组合操作（例如加，减，循环）。
CompGCN同时生成实体和关系嵌入，而不仅仅生成实体嵌入:
接下来计算
K 个 Attetnion 权重，其中第
k 个权重
\alpha_k 表示消息
\phi(\boldsymbol{x}_r, \boldsymbol{x}_o) 与第
k 个分量
\boldsymbol{h}_{s,k} 之间的关系：
\alpha_k=\frac{\exp(\text{ReLU}(\boldsymbol{W}[\boldsymbol{c}_{o,k};\boldsymbol{h}_{s,k}]))}{\sum_{k'=1}^{K} \exp(\text{ReLU}(\boldsymbol{W}[\boldsymbol{c}_{o,k'};\boldsymbol{h}_{s,k'}]))}
其中
\boldsymbol{W}\in\mathbb{R}^{1\times\frac{2d_{in}}{K}} 为可学习的转移矩阵。结构信息的更新方程可以表示为：
\boldsymbol{x}_{s,k}^l = \sum_{(r,o')\in\mathcal{N}(s)} \alpha_k \boldsymbol{W}_{\lambda(r)}^{l,k} \boldsymbol{c}_{o',k}^{l-1}
其中
\boldsymbol{W}_{\lambda(r)}^{l,k}\in\mathbb{R}^{\frac{out}{K}\times\frac{in}{K}} 。
最后根据
K 个分量的输出
\boldsymbol{x}_{s,k}^L 可以得到实体
s 在
t 时刻的结构嵌入表示
\boldsymbol{x}_{s,t} 。由于 CompGCN 可以在聚合过程中考虑关系的嵌入，因此也可以得到关系
r 的嵌入
\boldsymbol{x}_{r,t} 。
结构模块：将实体和关系投影到K个空间，计算关系和实体的attention，使用CompGCN进行聚合。
Temporal Information Passing Module 时间模块旨在对实体对之间的事件演变模式进行建模，并整合跨时间的信息，以生成实体和关系的时间嵌入。
对每个实体
s ，它的输入为
\boldsymbol{X}=\{\boldsymbol{x}_{s,t-m+1},\boldsymbol{x}_{s,t-m+2},\cdots,\boldsymbol{x}_{s,t}\} ，
m 为时间窗口大小。论文使用时间自注意层对时间维度中实体表示进行集成，并将输出嵌入序列定义为
\boldsymbol{Z}=\{\boldsymbol{z}_{s,t-m+1},\boldsymbol{z}_{s,t-m+2},\cdots,\boldsymbol{z}_{s,t}\} ：
e_{ij} = \frac{((\boldsymbol{XW}_q)(\boldsymbol{XW}_k)^T)_{ij}}{\sqrt{d}} + \boldsymbol{M}_{ij}
\beta_{ij} = \frac{\exp(e_{ij})}{\sum_{j'=0}^{m}\exp(e_{ij'})}
\boldsymbol{Z} = \boldsymbol{\beta}(\boldsymbol{XW}_v)
其中
\boldsymbol{X},\boldsymbol{Z}\in\mathbb{R}^{m\times d} ；
\boldsymbol{\beta}\in\mathbb{R}^{m\times m} 为注意力权重矩阵；
\boldsymbol{W}_q,\boldsymbol{W}_k,\boldsymbol{W}_v\in\mathbb{R}^{d\times d} 均为可学习参数矩阵；mask 矩阵
\boldsymbol{M}\in\mathbb{R}^{m\times m} 为：
\boldsymbol{M}_{ij} =
\begin{cases}
0&, \quad i\le j, \\
-\infty&, \quad otherwise.
\end{cases}
另外一方面，由于 SIP 模块被用来模拟邻居之间的相互作用，TIP 模块更关注细粒度的变化，即在整个时间步骤中特定实体对之间发生的事件（关系）。对于每一个实体对
(s,o) ，因此论文使用关系序列
\{r_{so}^0,r_{so}^1,\cdots,r_{so}^n,\cdots,r_{so}^N\}(1\le n\le N) ，
N 为当前时间窗口的事件数，使用 GRU 来获取实体对之间的关系
(s,o) ：
\boldsymbol{z}_{so,n}=\text{GRU}(\boldsymbol{x}_{so,n}, \boldsymbol{z}_{so,n-1})
其中
\boldsymbol{x}_{so,n}\in\mathbb{R}^d 为关系
r_{so}^n 在对应时间的结构关系表示。考虑到一个实体对在同一时间可能有多个事件，这里按照原始数据集中的顺序进行操作。
时间模块：主要有两个部分：1）根据SIP的结果进行时间维度上的Attention；2）对一个时间窗口内的实体对应用GRU。
History Forward Module 在本节中，论文通过评分函数，从结构、时间和重复的角度来评估一个事件。并提出了一种多步推理算法来处理推理问题。
时间得分函数 用于预测可能发生的事件，使用来自 TIP 模块的输出：
I_t(s,r,o,t) = \text{softmax}(\boldsymbol{W}_t[\boldsymbol{z}_{s,t};\boldsymbol{z}_{so,t};\boldsymbol{z}_{o,t}])_r
其中
\boldsymbol{W}_t\in\mathbb{R}^{p\times 3d} ，
p 为关系的种类数量。论文通过这种方法关注特定实体对之间事件的时间演化来预测下一个事件。
结构得分函数 基于结构表示来评估事件，以考虑在同一时间步长中它们之间的交互作用。这里，论文使用 DistMult 来为四元组打分：
I_s(s,r,o,t) = \sigma(\langle \boldsymbol{x}_{s,t},\boldsymbol{x}_{r,t},\boldsymbol{x}_{o,t} \rangle)
其中
\sigma 为 sigmoid 激活函数，
\langle\cdot\rangle 表示点积操作。
考虑到实体和事件是对时间敏感的，这可能会导致某些实体在时间窗口中可用的信息较少。因此论文对每个实体和关系建立历史词汇表，对于 query
(s,r,?,t) ，计算 重复历史得分 ：
I_h(s,r,o,t) = \text{softmax}(\boldsymbol{W}_h[\boldsymbol{e}_{s,t};\boldsymbol{e}_{r,t}] + \boldsymbol{V}_t^{(s,r)})_o
\boldsymbol{V}_t^{(s,r)} = \boldsymbol{v}_1^{(s,r)} + \boldsymbol{v}_2^{(s,r)} + \cdots + \boldsymbol{v}_{t-1}^{(s,r)}
其中
\boldsymbol{W}_h\in\mathbb{R}^{q\times 2d} ，
q 为实体数量；
\boldsymbol{e}_{s,t},\boldsymbol{e}_{r,t}\in\mathbb{R}^d 分别表示实体和关系的嵌入；
\boldsymbol{v}_{t^-}^{(s,r)} 为实体
s 和关系
r 的多热指示向量；
o 为 1 表示
\mathcal{G}^{(t^-)} 中存在
(s,r,o,t^-) 。
Training Objective 论文的损失函数为：
\mathcal{L} = \sum_{(s,o,r,t)\in\mathcal{G}^{(t)}} \sum_{*} -\log(I_{*}(s,r,o,t))
其中
I_{*}(\cdot) 分别为之前定义的得分函数。
论文算法如下：
实验 Datasets ICEWS14，ICEWS18 GDELT WIKI YAGO Result Ablation Study Sensitivity Analysis 总结 基于时间片的时间知识图谱，以解构的方式更新表示每个时间片上的结构信息，时间维度上不仅考虑时间片之间的顺序信息，还考虑了时间窗口内的事件对顺序信息。不同维度分别配对了不同的得分函数，此外的历史重复信息也有一定的道理。
参考资料 
