论文浅尝 | 让“演进知识图谱”带你“瞻前顾后”看世界

2019 年 6 月 9 日 开放知识图谱

本文转载自公众号：爱思美谱。

指导老师 | 傅洛伊王新兵

核心技术成员 | 刘佳琪

导读

在前面几期的内容中，小编已经为大家介绍了知识图谱的产生历史和基本概念。相信大家已经对知识图谱强大的信息结构化能力有所了解。但是，目前的大部分知识图谱均有一个特点——仅刻画了静态知识信息。在现实世界中，知识往往是带有时间标签的，且会随时间发生显著变化。例如，乔布斯于2010年发布IPhone4。这一条内容如果在传统知识图谱中进行表征，会被表示为一个三元组（乔布斯，发布，IPhone4），其中主语实体（subjectentity）为“乔布斯”，宾语实体（objectentity）为“IPhone4”，关系（relation）为“发布”。

细心的读者想必已经发现了，这条内容的一个关键信息——时间，即2010年，没有被整合进知识图谱。这就造成了信息的遗漏和损失，会对后续的知识提取和挖掘产生负面影响。另外，从时间维度上考虑知识，我们会发现很多不同时间段之间的知识存在着“因果联系”，或者至少存在一定的相关性。举个例子，这里有两个事件，分别为，“Bob于2017年到访美国”和“Bob于2018年到访加拿大”，这两个事件之间是否存在某种联系呢？答案是很有可能！！我们可以猜测，Bob可能在2017年前往美国后，与北美地区的一些商家建立了合作关系，才会在2018年前往北美的另外一个国家——加拿大。从上面两个例子我们可以总结出：

知识往往是带有时间标签的
时间靠前的知识可能会对时间靠后的知识产生影响

因此，一个更完善的知识图谱需要充分体现时间的作用，能够在刻画实体对象的关系时，既“瞻前”又“顾后”，这样才能更深入地了解事件发展的来龙去脉！图1是一个演进知识图谱的示意。目前，学术界对于演进知识图谱的研究尚处于起步阶段，仅有少数几篇工作对这个新概念进行了研究和探讨。接下来我们以发表于2019 IEEE INFOCOM 会议上的文章“Evolving Bipartite Graph”为基础，为大家介绍“演进知识图谱”这个概念。下面的内容会以研究思想为主，不涉及太多数学实现细节，感兴趣的读者可以自行查阅论文来获得更加详细的实现信息。

（原文详细信息：Jiaqi Liu, Qin Zhang, Luoyi Fu,Xinbing Wang and Songwu Lu, "Evolving Knowledge Graphs", in IEEE INFOCOM 2019, Paris, France.)

图1 演进知识图谱示例

演进知识图谱的该如何表示？

传统知识图谱的三元组结构没有涵盖时间信息，那么，时间信息该如何进行表示呢？一个最简单的方法就是采用四元组，在保证原三元组基本信息，即，主语实体、关系、宾语实体不变的情况下，引入第四维参量——时间。

图2 从“三元组”到“四元组”

知识的跨时间影响（cross-time influence）如何体现？

在引入四元组的前提下，“EvolvingBipartite Graph”这篇文章对知识的跨时间影响进行了讨论。主要研究问题包含以下两个方面：

模型刻画：知识演进具有哪些典型特征？如何通过数学手段对这些特征进行刻画？
算法实现：在已有知识基础的上，如何设计算法来对新产生的知识进行预测？

通过我们之前的描述想必大家也已经发现，新知识的产生过程往往会受到已有知识的影响，且受到所有其相关行为的影响。比如，在刚刚给出的例子中，Bob在2018年到访加拿大这个事件的产生，除了受其2017年到访美国这个历史事件的影响，还可能受其其他历史访问记录的影响（这些其他访问历史记录并未在前面的例子中具体给出）。另外，历史事件对于当前事件的影响还往往具有时效性。也就是说，当我们试图预测Bob在2019年的到访情况时，他在2018年的到访情况显然比他在2000年的到访情况具有更大的影响力。后面这一条性质也可以总结为——影响力随时间衰减。通过上述两个方面的基本观察，我们可以将历史事件对当前事件的影响力建模为如下形式

这里I__f表示某个历史事件对于当前时间产生概率的影响比重。在实际场景中，不同事件间的影响力各有差异。回到我们刚刚给出的例子，在讨论历史事件对于Bob在2019年的访问行为的影响时，一般情况下“Bob于2010年到访美国”这类重大事件的影响力大于“Bob于2010年到访上海闵行”这类一般事件的影响力。但是，在我们所讨论的这篇文章中，作者为了简便起见将所有不同事件的影响力均设置为一（这个设置大大简化了运算，但是在刻画真实影响力方面略显不足，是后期研究可以继续提升的方向之一）。这里f(t_i)表示在历史时刻t_i产生的知识对于当前时刻t新知识产生的影响，这个函数是一个递减函数，实质上反映了历史事件对于当前事件的影响力随时间衰减这一特性。该论文指出，除了衰减特性，衰减函数f(t_i)还需要满足一致性等其他约束条件，这些条件将在后面为大家进行详细介绍。最后，表达式中的求和项是对所有相关历史事件的影响力进行求和，这里求和顺序不是按照事件来进行排序的，而是按照使劲顺序进行的，因此求和项是从起始时刻0到当前时刻t，表示对起始时刻至当前时刻这个时间段间的所有历史事件影响力进行求和。

衰减函数f(t_i)的一些性质

如前所述，衰减函数是需要满足一定的约束条件的。使用符号表示主语实体，表示宾语实体，表示关系，表示时间，则演进知识图谱中的四元组可以表示为，这是一个带有时间戳的事件信息。使用符号表示事件的发生概率。这篇论文假设衰减函数需要满足以下两个方面的条件：

一致性：如果时刻至时刻之间无新事件产生，

衰减性：记时刻至时刻之间发生的事件集合为，则

R1：当时，

R2：当时，

R3：当,,时，

这里“一致性”的实际含义是，如果一段时间内无新的历史事件产生，则当前事件发生的概率不变。举个例子，如果Bob在2017年到访美国，基于这个历史事件我们得到Bob在2018年1月到访美国的概率P，如果1月到5月之间无新的历史事件产生（Bob没有任何新的访问行为，美国方面也没有重大的状态变化，如更改政策法规等），那么Bob在2018年5月到访美国的概率仍然为P。这个结论还是比较符合人们的常理认知的，因为人们行为的改变是由一些自身，或者行为对象的改变导致的，当没有这种改变时，人们的行为也就不会发生变化。通常情况下，由于新知识的产生是频繁地，时间间隔都是比较小的值，如例子中给出的4个月。而“衰减性”约束条件和我们之前的讨论结果相近，该论文将其细化成为了三个更加具体的约束条件，它们的实际含义分别为：发生了相关事件(R1)、发生的相关事件越多（R2）以及发生的相关事件时间越靠后（R3），新的相关事件发生的概率越大。同样举个例子，如果Bob曾经去过北美国家（R1），去过的次数较多（R2）或者去北美国家的时间距离现在较近（R3），则可以预测他接下来会去北美国家的概率较大。这三条约束条件实质上都反映了历史事件对当前事件的影响力是随时间递减的。

经过一定的数学推导，该文章指出当衰减函数的形式为时，上述所有约束条件都可以得到满足。上式中的表示历史事件的发生时刻，表示当前时刻，为参数，用来调节衰减速率。在这篇文章中，作者从数学角度证明了上述表达式可以满足前面给出的所有约束条件。

EvolveKG框架：一种新的知识演进处理框架

基于上述性质，论文提出了一种全新的知识演进处理框架——EvolveKG。该框架的一个结构示例如下图

图3 EvolveKG框架图

EvolveKG分为两个步骤。第一步首先将演进知识图谱转化为导图（DerivativeGraph）。这里的导图是该论文提出的一个全新概念，其数学定义为

这个定义为我们展现了演进知识图谱向导图进行转换的具体过程。通过这个定义我们可以看到，某个演进知识图谱的导图与原本的知识图谱具有相同的拓扑结构，最大的区别在于原知识图谱为一个有向无权图，而其对应导图为一个有向加权图，这里每一条边的权重对应为该边以及其所连接的主语实体和宾语实体所对应的事件目前的有效影响力。在图3中的Step1我们可以看到，左侧所示是一个包含四条基础事件的演进图谱，这四个事件的产生时间分别为t1，t2，t3和t4。右侧所示即为该演进知识图谱对应的导图，导图与t时刻的演进知识图谱拓扑结构一致，但是每条边拥有一个对应的权重。这里每条边的权重反映了对应事件对当前新知识产生的影响力，或者也可以叫做该历史事件的有效性。因此，导图实质上刻画了整个演进知识图谱在当前时刻的全网有效性。之所以称其为导图，是因为它的获取方式就好比对函数进行求导，相当于是一个函数与其导函数的关系，由此得名。

接下来是第二步：对导图中包含的数据进行有偏训练。这里的“有偏”指的是各条数据的重要性程度有所差异。而在该论文所研究的问题中，数据的重要性程度体现为它们对当前知识的影响力，也就是根据衰减函数计算得到的值。那么这种“偏移”该如何实现呢？该论文提出可以分别从数据端或者损失端来刻画这种偏移程度。下图所示是一个普通的训练过程框架图

图4 一般训练过程框架

该图表示系统包含m个训练数据，根据所设计的损失函数可以得到每一条数据所对应的损失l_i，将它们相加后可以得到最终的总损失L，最后通过相应的优化函数迭代地减小总损失值。该论文提出，数据的“偏移”可以分别在数据端或者损失端进行实现。数据端指的是提高重要数据（影响力较大的数据）的采样率，而损失端指的是根据每个数据的重要程度为其对应损失乘上一个权重系数，这样不同数据在总损失中的占比权重可以方便的进行调整。论文采用的训练方法为后者，具体的实验过程如图3中Step2所示。

基于上述框架，论文对衰减函数的正确性，以及导图有效信息量随时间的变化规律进行了数学分析与证明。由于涉及量数学推导过程，我们在这里不再继续深入，感兴趣的读者可以查看该论文来获得更加详细的信息。但是这里值得一提的是，我们通过导图得了三种不同量级的知识演化速度，使得知识变化与事件发展之间建立了一个可以相互解释、相互支撑的桥梁!下面放上我们的主要定理（证明可以具体参见原文）

实验验证

文中基于两个大规模数据集对所提出算法的有效性进行了验证。这里的算法目标是——以历史数据为训练数据集，通过对其进行学习来预测当前时刻新知识的产生情况。两个数据集分别为ICEWS和GDELT，数据集的统计特性如下

另外，论文添加了两个对比算法，定义分别为

UTF（Uniform Training with the Full historical facts）：使用全部历史数据进行训练，并对所有历史数据赋予相等的权重；
UTR（Uniform Training with only Recent historical facts）：仅适用近期历史数据进行训练。

通过将所提出的算法与UTR进行对比，可以获知历史数据是否对当前知识的产生具有影响（若无影响，则UTF的性能应与所提出算法相近）；而通过与UTF的对比，可以获知历史数据对于当前知识的影响是否是均匀的还是递减的。

论文分别采用MeanRank和Hits@10作为评价指标，这两个指标被普遍用于知识图谱预测准确度的衡量中。其具体定义在这里不进行详述，感兴趣的读者可以上网查找相关资料。MeanRank越低，或者Hits@10越低时，预测准确度越高。预测结果如下图所示

图5 MeanRank指标

图6 Hits@10指标

从上图中可以看出，论文所提出的EvolveKG算法在MeanRank指标和Hits@10指标上均优于两种对比算法，这说明论文之前的假设（历史知识对于当前知识的产生具有影响，且该影响力随时间递减）是正确的。

未来展望

虽然这篇推文中我们仅以文章“Evolving Knowledge Graph”为例为大家介绍了演进知识图谱的概念，但是演进知识图谱的探索之路刚开始，可以挖掘的内容远远不止这些。举些例子，这篇论文里将时间维度转换为了图中边的权重，那么是否可以效仿实体和关系，将时间维度也映射到一个特定的向量空间呢？再如，如何更加全面有效地刻画跨时间影响，挖掘时间维度上知识演进带来的额外信息，都是未来可以继续研究的方向。

OpenKG

开放知识图谱（简称 OpenKG）旨在促进中文知识图谱数据的开放与互联，促进知识图谱和语义技术的普及和广泛应用。