【论文阅读】Temporal knowledge graph reasoning based on evolutional representation learning

EmoryHuang

发布于 2023-04-06 09:56:47

5880

发布于 2023-04-06 09:56:47

文章被收录于专栏：EmoryHuang's BlogEmoryHuang's Blog

【论文阅读】Temporal knowledge graph reasoning based on evolutional representation learning

Metadata

authors:: Zixuan Li, Xiaolong Jin, Wei Li, Saiping Guan, Jiafeng Guo, Huawei Shen, Yuanzhuo Wang, Xueqi Cheng container:: Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval year:: 2020 DOI:: 10.1145/3404835.3462963 rating:: ⭐⭐⭐ share:: true comment:: 时间知识图谱TKG推理，时间片上采用GCN，顺序关系上采用GRU，并融合静态信息，同时预测实体和关系。

前言

这次是一篇关于时间知识图谱（TKG）的论文，现在有很多论文把知识图谱（KG）放到POI预测里，也是想了解尝试一下。

SIGIR 2021：Temporal Knowledge Graph Reasoning Based on Evolutional Representation Learning

问题描述

一个时间知识图谱TKG可以定义为带时间戳的知识图谱KGs序列，即G={G1,G2,⋯ ,Gt,⋯ }G=\{G_1,G_2,\cdots,G_t,\cdots\}G={G1,G2,⋯,Gt,⋯}。对于每个KG，Gt=(V,R,εt)G_t=(\mathcal{V},\mathcal{R},\mathcal{\varepsilon}_t)Gt=(V,R,εt)表示一个在ttt时刻的有向的多关系图，其中V\mathcal{V}V表示实体，R\mathcal{R}R表示关系，εt\mathcal{\varepsilon}_tεt表示在ttt时刻的事实集。事实集中的事实（fact）可以用四元组表示(s,r,o,t),s,o∈V,r∈R(s,r,o,t), s,o\in\mathcal{V}, r\in\mathcal{R}(s,r,o,t),s,o∈V,r∈R，在传统KG的基础上加上时间戳。此外，对于每个四元组(s,r,o,t)(s,r,o,t)(s,r,o,t)，其逆四元组(o,r−1,s,t)(o,r^{-1},s,t)(o,r−1,s,t)也加入数据集。

文中的静态图表示为Gs=(Vs,Rs,εs)G^s=(\mathcal{V}^s,\mathcal{R}^s,\mathcal{\varepsilon}^s)Gs=(Vs,Rs,εs)，对应实体集合，关系集合和事实集合。

Task 1. Entity Prediction. 给定query (s,r,?,t+1)(s,r,?,t+1)(s,r,?,t+1)，根据实体sss，关系rrr和历史KG序列Gt−m+1:tG_{t-m+1:t}Gt−m+1:t计算对象实体概率：

p⃗(o∣s,r,Gt−m+1:t)=p⃗(o∣s,r,Ht,Rt)\vec{p}(o\vert s,r,G_{t-m+1:t})=\vec{p}(o\vert s,r, \mathbf{H}_t, \mathbf{R}_t) p(o∣s,r,Gt−m+1:t)=p(o∣s,r,Ht,Rt)

Task 2. Relation Prediction. 给定query (s,?,o,t+1)(s,?,o,t+1)(s,?,o,t+1)，根据实体s,os,os,o和历史KG序列Gt−m+1:tG_{t-m+1:t}Gt−m+1:t计算关系概率：

p⃗(r∣s,o,Gt−m+1:t)=p⃗(r∣s,o,Ht,Rt)\vec{p}(r\vert s,o,G_{t-m+1:t})=\vec{p}(r\vert s,o, \mathbf{H}_t, \mathbf{R}_t) p(r∣s,o,Gt−m+1:t)=p(r∣s,o,Ht,Rt)

除了把序列关系作为一个个时间切片之外，另一种考虑序列的方式是把时间信息放到关系中表示。

OverView

论文认为现有的方法主要有三个限制：

主要关注给定查询的实体和关系，忽略每个时间戳KG中所有事实之间的结构依赖性;
为每个查询单独编码历史记录，效率低下;
忽略实体的某些静态属性（如实体类型）的作用；
现有方法仅关注实体预测，无法同时解决关系预测问题。

本文将时间知识图谱作为一个序列考虑，并通过同时建立整个序列的模型，将所有历史事实编码为实体和关系的表示。提出了GCN-based Recurrent Evolution network（RE-GCN），学习每个时间戳实体和关系的演化表示。对于每个演化单元，使用关系感知GCN来捕获KG中的结构依赖性，此外通过加入静态图约束，将实体静态属性合并进来以获得更好的实体表示。论文的主要贡献如下：

论文提出了一种演化表示学习模型 RE-GCN，用于时间推理，考虑了KG中并发事实之间的结构依赖性、时间相邻事实之间的序列模式以及实体的静态属性。
从KG序列角度描述TKG，RE-GCN有效地将TKG中的所有历史信息建模为演化表示，可同时用于实体和关系预测。

RE-GCN

模型架构如下图所示：

The Evolution Unit

演化单元由三部分组成：一个关系感知的GCN，两个门控循环组件以及一个静态图约束组件。关系感知的GCN在每个时间戳捕捉KG内部的结构性依赖关系。两个门控循环组件对历史KG序列进行回归建模，包括一个时间门控循环组件和一个GRU。静态图约束组件通过在静态嵌入和实体的演化嵌入之间添加一些约束，将静态属性集成到演化嵌入中。

具体来说，演化单元将长度为mmm的KG序列{Gt−m+1,⋯ ,Gt}\{G_{t-m+1},\cdots,G_t\}{Gt−m+1,⋯,Gt}，映射为实体序列{Ht−m+1,⋯ ,Ht}\{\mathbf{H}_{t-m+1},\cdots,\mathbf{H}_t\}{Ht−m+1,⋯,Ht}和关系序列{Rt−m+1,⋯ ,Rt}\{\mathbf{R}_{t-m+1},\cdots,\mathbf{R}_t\}{Rt−m+1,⋯,Rt}。

Structural Dependencies among Concurrent Facts

论文使用一个ω\omegaω层的关系感知的GCN来捕获结构依赖关系。具体来说，对于ttt时刻的KG，对象实体ooo通过消息传递获取主体实体以及关系的信息：

h⃗o,tl+1=f(1co∑(s,r),∃(s,r,o)∈εtW1l(h⃗s,tl+r⃗t)+W2lh⃗o,tl)\vec{h}_{o,t}^{l+1} = f \left( \frac{1}{c_o} \sum_{(s,r),\exists(s,r,o)\in\varepsilon_t} \mathbf{W}_1^l(\vec{h}_{s,t}^l + \vec{r}_t) + \mathbf{W}_2^l\vec{h}_{o,t}^l \right) ho,tl+1=f⎝⎛co1(s,r),∃(s,r,o)∈εt∑W1l(hs,tl+rt)+W2lho,tl⎠⎞

其中h⃗s,tl,h⃗o,tl,r⃗t\vec{h}_{s,t}^l, \vec{h}_{o,t}^l, \vec{r}_ths,tl,ho,tl,rt分别表示lll层ttt时刻的实体s,os,os,o和关系rrr；W1l,W2l\mathbf{W}_1^l,\mathbf{W}_2^lW1l,W2l为参数矩阵；h⃗s,tl+r⃗t\vec{h}_{s,t}^l + \vec{r}_ths,tl+rt通过向量加法连接实体和关系；coc_oco为实体ooo的入度；f(⋅)f(\cdot)f(⋅)表示RReLU激活函数。

Sequential Patterns across Temporally Adjacent Facts

对于一个实体ooo，其历史事实中所包含的顺序模式反映了其行为趋势和偏好。为了尽可能多地涵盖历史事实，论文利用了一个时间门控循环组件来缓解over-smoothing problem和vanishing gradient problem，具体来说，将实体矩阵Ht\mathbf{H}_tHt分为两部分，Htω\mathbf{H}_t^\omegaHtω和Ht−1\mathbf{H}_{t-1}Ht−1，分别表示关系感知的GCN在ttt时刻最后一层的输出和前一个时刻的信息：

Ht=Ut⊗Htω+(1−Ut)⊗Ht−1\mathbf{H}_t = \mathbf{U}_t \otimes \mathbf{H}_t^{\omega} + (1-\mathbf{U}_t)\otimes \mathbf{H}_{t-1} Ht=Ut⊗Htω+(1−Ut)⊗Ht−1

其中⊗\otimes⊗表示点乘。Ut∈Rd×d\mathbf{U}_t\in\mathbb{R}^{d\times d}Ut∈Rd×d表示为：

Ut=σ(W4Ht−1+b)\mathbf{U}_t = \sigma(\mathbf{W}_4\mathbf{H}_{t-1}+\mathbf{b}) Ut=σ(W4Ht−1+b)

其中σ(⋅)\sigma(\cdot)σ(⋅)表示sigmoid激活函数。除了实体关系之外，论文使用GRU对关系的顺序模式进行建模。GRU在ttt时刻的输入为进行平均池化后的t−1t-1t−1时刻与rrr相关的实体：

r⃗t′=[pooling(Ht−1,Vr,t);r⃗]\vec{r}_t' = [pooling(\mathbf{H}_{t-1,\mathcal{V}_{r,t}});\vec{r}] rt′=[pooling(Ht−1,Vr,t);r]

其中r⃗\vec{r}r关系rrr的embedding表示，[;][;][;]表示拼接操作。

Rt=GRU(Rt−1,Rt′)\mathbf{R}_t = GRU(\mathbf{R}_{t-1}, \mathbf{R}_t') Rt=GRU(Rt−1,Rt′)

其中Rt′∈R∣R∣×d\mathbf{R}_t'\in\mathbb{R}^{\vert\mathcal{R}\vert\times d}Rt′∈R∣R∣×d由关系r⃗t′\vec{r}_t'rt′组成。

Static Properties

除了历史KG序列中包含的信息外，实体的一些静态属性，可以看作是TKG的背景知识，可以帮助进行更准确的实体的进化表示。这里，论文使用了一个单层的R-GCN获取静态实体嵌入表示：

h⃗is=Υ(1ci∑(rs,j),∃(i,rs,j)∈εsWrsh⃗i′s(j))\vec{h}_i^s=\varUpsilon \left( \frac{1}{c_i} \sum_{(r^s,j),\exists(i,r^s,j)\in\varepsilon^s} \mathbf{W}_{r^s}\vec{h}_i'^{s}(j) \right) his=Υ⎝⎛ci1(rs,j),∃(i,rs,j)∈εs∑Wrshi′s(j)⎠⎞

其中h⃗is,h⃗j′s\vec{h}_i^s,\vec{h}_j'^{s}his,hj′s分别表示Hs\mathbf{H}^sHs和H′s\mathbf{H}'^sH′s的第iii和第jjj行；Wrs\mathbf{W}_{r^s}Wrs表示关系矩阵；Υ(⋅)\varUpsilon(\cdot)Υ(⋅)表示ReLU函数；cic_ici表示与实体iii相关的实体数量。

为了学习实体矩阵Ht−m,Ht−m+1,⋯ ,Ht\mathbf{H}_{t-m},\mathbf{H}_{t-m+1},\cdots,\mathbf{H}_tHt−m,Ht−m+1,⋯,Ht中的静态关系，论文设定了一个演化表示和静态表示之间的角度，它会随着时间的推移而增加，实体演化的允许的可变范围也不断拓展。

感觉可以理解为近期的动态偏好这种概念。

θx=min⁡(γx,90∘)\theta_x = \min(\gamma x,90^\circ) θx=min(γx,90∘)

其中γ\gammaγ表示角度增加幅度，x∈[0,1,⋯ ,m]x\in[0,1,\cdots,m]x∈[0,1,⋯,m]。两个嵌入表示的最大角度为90∘90^\circ90∘。

接着计算两个嵌入实体之间的余弦值cos⁡(h⃗is,h⃗t−m+x,i)\cos(\vec{h}_i^s, \vec{h}_{t-m+x,i})cos(his,ht−m+x,i)，可以得到ttt时刻静态图的损失函数：

Lxst=∑i=0∣V∣−1max⁡{cos⁡θx−cos⁡(h⃗is,h⃗t−m+x,i),0}L_x^{st} = \sum_{i=0}^{\vert\mathcal{V}\vert-1} \max\{\cos\theta_x - \cos(\vec{h}_i^s, \vec{h}_{t-m+x,i}),0\} Lxst=i=0∑∣V∣−1max{cosθx−cos(his,ht−m+x,i),0}

因此静态图的损失函数为：Lst=∑x=0mLxstL^{st} = \sum_{x=0}^m L_x^{st}Lst=∑x=0mLxst。

可以理解为利用余弦函数控制两个嵌入表示的比例问题。

Score Functions for Different Tasks

论文使用ConvTransE作为解码器，它包含一个一维卷积层和一个全连接层，分别得到实体和关系的概率：

p⃗(o∣s,r,Ht,Rt)=σ(HtConvTransE(s⃗t,r⃗t))\vec{p}(o\vert s,r, \mathbf{H}_t, \mathbf{R}_t) = \sigma(\mathbf{H}_t \text{ConvTransE}(\vec{s}_t,\vec{r}_t)) p(o∣s,r,Ht,Rt)=σ(HtConvTransE(st,rt))

p⃗(r∣s,o,Ht,Rt)=σ(RtConvTransE(s⃗t,o⃗t))\vec{p}(r\vert s,o, \mathbf{H}_t, \mathbf{R}_t) = \sigma(\mathbf{R}_t \text{ConvTransE}(\vec{s}_t,\vec{o}_t)) p(r∣s,o,Ht,Rt)=σ(RtConvTransE(st,ot))

其中σ(⋅)\sigma(\cdot)σ(⋅)表示sigmoid函数，ConvTransE(s⃗t,r⃗t),ConvTransE(s⃗t,o⃗t)∈Rd×1\text{ConvTransE}(\vec{s}_t,\vec{r}_t), \text{ConvTransE}(\vec{s}_t,\vec{o}_t)\in\mathbb{R}^{d\times 1}ConvTransE(st,rt),ConvTransE(st,ot)∈Rd×1。

Parameter Learning

实体预测任务和关系预测任务都可以看作是多标签学习问题，因此实体和关系的损失函数为：

Le=∑t=0T−1∑(s,r,o,t+1)∈εt+1∑i=0∣V∣−1yt+1,ielog⁡pi(o∣s,r,Ht,Rt)L^e = \sum_{t=0}^{T-1}\sum_{(s,r,o,t+1)\in\varepsilon_{t+1}}\sum_{i=0}^{\vert\mathcal{V}\vert-1} y_{t+1,i}^e \log p_i(o\vert s,r, \mathbf{H}_t, \mathbf{R}_t) Le=t=0∑T−1(s,r,o,t+1)∈εt+1∑i=0∑∣V∣−1yt+1,ielogpi(o∣s,r,Ht,Rt)

Lr=∑t=0T−1∑(s,r,o,t+1)∈εt+1∑i=0∣R∣−1yt+1,irlog⁡pi(r∣s,o,Ht,Rt)L^r = \sum_{t=0}^{T-1}\sum_{(s,r,o,t+1)\in\varepsilon_{t+1}}\sum_{i=0}^{\vert\mathcal{R}\vert-1} y_{t+1,i}^r \log p_i(r\vert s,o, \mathbf{H}_t, \mathbf{R}_t) Lr=t=0∑T−1(s,r,o,t+1)∈εt+1∑i=0∑∣R∣−1yt+1,irlogpi(r∣s,o,Ht,Rt)

最终的损失函数为：

L=λ1Le+λ2Lr+LstL = \lambda_1L^e + \lambda_2L^r + L^{st} L=λ1Le+λ2Lr+Lst

其中λ1,λ2\lambda_1,\lambda_2λ1,λ2为超参数。