【论文阅读】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^-)$ 。