时态知识图谱补全的方法及其进展
Temporal knowledge graph completion:methods and progress
通讯作者: 申宇铭,ymshen2002@163.com
网络出版日期: 2021-05-15
基金资助: |
|
Online: 2021-05-15
Fund supported: |
|
作者简介 About authors
申宇铭(1976-),男,博士,广东外语外贸大学教授,主要研究方向为知识表示与推理、知识图谱。主持或参与多项国家自然科学基金和省部级项目。近年来在《计算机学报》《软件学报》等国内重要期刊,以及国际重要期刊和国际会议上发表论文20余篇。担任CCKS、AAAI、EMNLP等国内外重要学术会议的程序委员会委员。
杜剑峰(1976-),男,博士,广东外语外贸大学教授,中国中文信息学会语言与知识计算专业委员会委员,主要研究方向为知识表示与推理、数据挖掘和自然语言处理。在AAAI、WWW、ISWC、CIKM和KAIS等学术会议上发表数十篇文章,获得多项国家自然科学基金项目资助。担任JournalofWebSemantics编委,长期担任CCKS、CSWS、IJCAI、AAAI、ISWC、JIST等学术会议的程序委员会成员,曾担任CSWS2014程序委员会主席。
时态知识图谱是将时间信息添加到传统的知识图谱而得到的。近年来,时态知识图谱补全受到了学术界的高度关注,并成为研究热点之一。总结了目前时态知识图谱补全的两大类方法,即基于符号逻辑的方法和基于知识表示学习的方法,比较分析了两类方法的优缺点,展望了未来时态补全方法的发展方向,还总结了7个用于时态知识图谱补全的基准数据集和若干代表性模型在基准数据集上的评测结果。
关键词:
Temporal knowledge graph (TKG) are obtained by adding the time information of real-world knowledge to classical knowledge graphs.Recently, TKG completion has drawn much attention and become a hot topic in research.Two main methodologies for TKG completion were summarized, one based on symbolic logic whereas and the other based on knowledge representation learning.The pros and cons of these two different methodologies were discussed, highlighting some directions for enhancing TKG completion in future research.Also, seven benchmark datasets for TKG completion and evaluation results of several typical models on the benchmark datasets were introduced.
Keywords:
本文引用格式
申宇铭, 杜剑峰.
SHEN Yuming, DU Jianfeng.
1 引言
在人工智能飞速发展的背景下,知识图谱(knowledge graph)被普遍地认为是人工智能技术和系统中的重要组成部分,在智能搜索、网络安全、金融风险控制及电子商务等诸多领域得到了广泛应用。传统的知识图谱以(实体,关系,实体)或(实体,属性,属性值)三元组集合的方式来表达现实世界的概念、实体、事件及三者之间的关系。比如,三元组(姚明,身高,2.26米)和(姚明,国籍,中国)。2012年5月,谷歌公司发布了谷歌知识图谱(Google knowledge graph),宣布以此为基础构建下一代智能化搜索引擎。这是知识图谱名称的由来,也标志着大规模知识图谱在语义搜索中的成功应用。事实上知识图谱技术渊源已久——从20世纪70年代的专家系统(expert system),到万维网之父Tim BernersLee提出的语义网(semantic web),再到他后来提出的链接数据(linked data),都是知识图谱的前身。可以说,知识图谱的升温是人工智能对数据处理与理解需求逐日增加而导致的必然结果。
图1
与传统的静态知识图谱相似,时态知识图谱中的知识也是不完备的,为了实现最大价值,其需要不断地消化吸收新数据,以完善知识体系。近年来,时态知识图谱补全(temporal knowledge graph completion)方法应运而生,受到了学术界的高度关注,并成为研究热点之一[3]。这类方法基于时态知识图谱的现有四元组数据,建模预测真实存在的新四元组。这些预测得到的四元组经过验证后,可被添加到时态知识图谱中,作为其演化的结果。时态知识图谱补全的方法在构建大规模知识图谱、相似度计算、关系抽取,以及基于知识图谱问答等任务方面展现出巨大的应用潜力。
为了能够及时追踪到补全方法在时态知识图谱上的发展和应用,本文首先给出时态知识图谱补全的问题定义,回顾代表性的时态知识图谱补全方法,然后对不同类别的方法进行对比分析,给出可能的结合途径,最后总结当前时态知识图谱评测的7个基准数据集,并且给出几个代表性的补全模型在其中3个基准数据集上的评测结果。
2 问题定义
本节给出时态知识图谱及其补全过程的定义,并介绍相关的评测任务。
定义2.1 时态知识图谱。一个时态知识图谱是一个四元组的集合。形式地说,任意给定实体集合E、关系集合R、有穷时间戳集合T,时态知识图谱G是笛卡儿积E×R×E×T的一个子集。
比如,事件“2016—2020年期间,特朗普是美国总统”可以表达为四元组(美国,总统,特朗普,[2016,2020])。类似地,事件“拜登于2021年当选美国总统”可以表达为四元组(美国,总统,拜登, 2021)。
定义2.2 时态知识图谱补全。令E× R×E×T的一个子集W表达现实世界中所有成立的事实,G为W的一个真子集。时态知识图谱的补全是指:由G出发,推理出不属于G但是属于W的事实。
例1 假设W={(a,签订合同,b,t1),(a,履行合同,b,t1+1),(a,签订合同,c,t2),(a,履行合同,c,t2+1)},且G={(a,签订合同,b,t1),(a,履行合同,c,t2+1)},则需要从G出发推理出事实(a,履行合同,b,t1+1)和(a,签订合同,c,t2)。
时态知识图谱的补全评测任务主要有两个:
● 给定头实体a、关系r和时间戳t,补全尾实体,即(a,r,?,t);
● 给定尾实体b、关系r和时间戳t,补全头实体,即(?,r,b,t)。
与传统的知识图谱补全问题不同,时态知识图谱的补全更加强调事实成立的时效性,比如,四元组(特朗普,当选,美国总统,2016)和(特朗普,卸任,美国总统,2015),第一个四元组是真实事实,而第二个四元组是虚假事实,去掉时间戳后,所得的两个三元组(特朗普,当选,美国总统)和(特朗普,卸任,美国总统)都是真实事实。因此,如何将事实成立的时效性信息融入传统的补全模型是亟待解决的问题。
3 时态知识图谱补全方法
目前,依据对符号处理的不同方式,时态知识图谱的补全方法主要分为两大类:一类是基于符号逻辑的方法,此类方法通过构建领域本体,运用饱和度技术,推理出隐含存在的真实四元组;另一类是基于知识表示学习(knowledge representation learning)的方法,此类方法将符号映射到实值空间,采用数值运算评估四元组的真实程度。
3.1 基于符号逻辑的方法
基于符号逻辑的时态数据查询回答(logic-based temporal query answering)方法又分为两类:一类以领域为中心,另一类以时间为中心。
以时间为中心的方法假定本体的构建语言为时态描述逻辑,查询语句为包含时态算子(next-time,previous-time,sincetime,until-time,future-time)的一阶时态逻辑公式。以此为基础,Artale A等人[7]设计了一种时态描述逻辑语言TQL,其包含past-time和future-time两个一元时态算子,并在限定时态概念只出现在术语公理左侧的情形下,证明了该逻辑语言支持时态查询的一阶重写。GutiérrezBasulto V等人[8]在限定时态查询语言为时态原子语句的情形下,证明了时态本体EL-LTL的查询问题是不可判定的,继而通过引入若干语法上的限制条件识别出EL-LTL的若干可判定子片段,并证明了在某些子片段上的时态查询回答是多项式时间可以完成的。Artale A等人[9]全面研究了时态DL-Lite-LTL族下时态查询的一阶重写问题,较完整地分析了时态查询问题的计算复杂性。
例2 假设本体只包括一条规则“对所有x,y,t: R(x,y,t)→Q(x,y,t+1)”,其中谓词R、Q分别表示签订合同和履行合同,考虑到例1中集合G={(a,签订合同,b,t1),(a,履行合同,c,t2+1)},由上述规则可以推理出隐含事实(a,履行合同,b,t1+1)。对于时态查询q=(a,履行合同,?,t1+1),隐含的事实 (a,履行合同,b,t1+1) 满足该时态查询q。
对比两类方法,以领域为中心的方法在查询语言的表达能力上要强于以时间为中心的方法,而以时间为中心的方法在本体的表达能力上要强于以领域为中心的方法。同时,基于符号逻辑的方法在实际应用中难以覆盖大量真实的四元组,召回率较低,而且构建本体时也要付出较高的人工成本。
3.2 基于知识表示学习的方法
本节先简要回顾针对传统知识图谱的表示学习代表性方法,再以此为基础,综述针对时态知识图谱的表示学习方法。知识表示学习方法的基本原理是将给定的三元组数据映射到低维、高密度的数值空间,通过数值运算评估未知三元组的真实程度。依据三元组评分函数的不同类型,传统知识图谱的表示学习方法大致分为3类:第一类是基于平移距离模型的方法,第二类是基于矩阵分解模型的方法,第三类是基于神经网络模型的方法。
基于矩阵分解模型的方法采用
基于神经网络模型的知识表示学习方法采用神经网络形式的评分函数来评估三元组的真实程度。Bordes A等人[23]提出了语义匹配能量(semantic matching energy,SME)模型,该模型将头实体与关系的交互模型和尾实体与关系的交互模型作为第一层网络,再将两个交互模型的输出组合起来构成第二层网络。Socher R等人[24]提出了神经张量网络(neural tensor network,NTN)模型,该模型采用头尾实体各自的线性变换模型以及它们之间交互的线性变换模型来构造神经网络,其中所有线性变换模型都使用不同的关系依赖矩阵。Dong X等人[25]提出了多层感知器(multi-layer perceptron,MLP)模型,该模型采用关系和头尾实体各自的线性变换模型共3个线性变换模型来构造神经网络,3个线性变换模型中使用的变换矩阵都不依赖于关系。
除了这3类方法,还有文献讨论了利用知识图谱外部信息的知识表示学习方法,包括结合实体描述信息的方法、结合实体类型信息的方法、结合关系路径信息的方法、结合逻辑规则的方法等。更多的传统知识图谱的表示学习方法参见参考文献[3]。
传统知识图谱中的知识在大多数情况下只在特定的时间内有效,而一些事实(如演化的事件)往往出现在一个时间序列中。为了对时间序列中的事实进行表示学习,近年来涌现了不少针对时态知识图谱的补全方法。依据对时间戳的处理方式,这些方法可以大致分为两类:第一类是时间戳单独编码方法,第二类是基于序列学习的方法。
在图2中,r1是先于r2的时态关系,根据评分函数有
在图3中,关系“bornIn”与日期“1986”经过LSTM模型后形成了融合时间信息的关系表示向量
图2
图3
4 两类方法的比较
基于符号逻辑的方法可以从已有的知识图谱出发,结合本体中的规则,推理出新的实体间关系;同时,还可以对演化后的知识图谱进行逻辑一致性检查,使得推理结果具备透明、可靠及可解释性强等特点。为了表达时态的知识,这一类方法通常需要引入时态算子来提升本体的表达能力,而表达能力的提升通常会导致如下两种局限性。
● 不可判定性:即不存在有限时间可终止的算法,使得该算法能够判定相关的推理问题是否可证。比如,在描述逻辑EL中,引入时态算子到本体中会导致其时态查询回答是不可判定的[8]。
● 高计算复杂性:比如,在描述逻辑EL中,交查询的回答是多项式时间的,但引入时态算子到查询语言后,时态交查询回答却是NP难的[5]。
由此可见,基于符号逻辑的方法在推理效率方面难以满足日益增长的数据需求。
基于知识表示学习的方法将研究对象的语义信息表示为低维稠密的实值向量。在低维向量空间中能够高效地计算实体和关系的语义关系,显著地提高推理性能。但是,此类方法的推理过程不透明,推理结果的可解释性低。此外,大多数表示学习模型的表达能力有限。比如,参考文献[39]指出数值嵌入模型不能表达本体中的存在规则(existential rule),而这类规则恰好对应于轻量级描述逻辑EL或DL-Lite族的术语或角色公理;进一步地,参考文献[40]指出,就算表示学习模型能够区分所有真实的三元组和错误的三元组,也不能确保正确区分出本体中的上下位关系。由此可见,基于知识表示学习的推理不能完全替代基于符号逻辑的推理。
从推理的方式来看,基于符号逻辑的推理属于演绎推理,而基于表示学习的推理属于不完全归纳推理,两种推理方式各有各的优缺点,但最终的目的都是将不完备的知识库(incomplete knowledge base)演化为完备的知识库(complete knowledge base)。为了发挥两种推理方式的优势,未来的知识图谱补全研究方向可以聚焦于解决表示学习模型无法习得存在规则逻辑的结论的问题。在这一方向上,Du J F等人[41]提出了逻辑背景预完备技术来融入关系特征定义,并提出了区分头尾实体的投影函数来解决关系表示向量不可区分的问题;进一步地,参考文献[42]引入了逻辑一致性规则预完备技术,解决了部分排位靠前的三元组与逻辑一致性规则相违背的问题。
5 基准测试数据集
当前,时态知识图谱补全研究领域有7个基准测试数据集,它们是在Wikidata、YAGO、GDELT和综合早期危机预警系统(integrated crisis early warning system, ICEWS)4个数据库上构建的。这7个数据集分别是GDELT-500、ICEWS14、ICEWS05-15、YAGO15k、Wikidata11k、YAGO11k和Wikidata12k,其中YAGO和Wikidata中的事实是基于时间区间的,而GDELT和ICEWS中的事实是基于时间点的。
● GDELT:GDELT数据库记录了从1969年至今,每个国家大约100多种语言的新闻媒体中印刷、广播和We b形式的新闻,并且每隔15 min更新一次数据。GDELT主要包含两大数据库,即事件数据库(event database)和全球知识图谱 (global knowledge graph)。目前,用于时态知识图谱补全研究的数据集是GDELT-500。
● ICEWS:ICEWS数据库涵盖了100多个数据源以及250个国家和区域的政治事件,并且每天更新一次数据。用于时态知识图谱补全研究的数据集是ICEWS14和ICEWS05-15。
● Wikidata:Wikidata是维基媒体基金会主持的一个自由的协作式多语言辅助知识库,旨在为维基百科、维基共享资源以及其他的维基媒体项目提供支持。目前,用于时态知识图谱补全研究的数据集是Wikidata11k和Wikidata12k。
● YAGO:YAGO是由德国马克斯·普朗克研究所研制的链接数据库。该数据库主要集成了Wikipedia、WordNet和GeoNames 3个来源的数据。YAGO将WordNet的词汇定义与Wikipedia的分类体系进行了融合集成,使得YAGO具有更加丰富的实体分类体系。YAGO还考虑了时间和空间知识,为很多知识条目增加了时间和空间维度的属性描述。目前,用于时态知识图谱补全研究的数据集是YAGO11k和YAGO15k。上述7个数据集的统计结果见表1。
表1 基准数据集的统计结果
数据集 | 实体数/个 | 关系数/条 | 时间跨度 | 更新时间间隔 |
GDELT-500 | 500 | 20 | 2015—2016年 | 15 min |
ICEWS14 | 7 128/6 869 | 230 | 2014年 | 每天 |
ICEWS05-15 | 10 094 | 251 | 2005—2015年 | 每天 |
Wikidata11k | 11 134 | 95 | 25—2020年 | 每年 |
Wikidata12k | 12 554 | 24 | 1479—2018年 | 每年 |
YAGO11k | 10 623 | 10 | 公元前453—2844年 | 每年 |
YAGO15k | 15 403 | 34 | 1513—2017年 | 每年 |
表2 若干代表性补全模型的评测结果
模型 | ICEWS14 | ICEWS05-15 | Wikidata11k | ||||||||
MRR | Hit@1 | Hit@10 | MRR | Hit@1 | Hit@10 | MRR | Hit@1 | Hit@10 | |||
TransE* | 0.280 | 9.4 | 63.7 | 0.294 | 9.0 | 66.3 | 0.316 | 18.1 | 65.9 | ||
DistMult* | 0.439 | 32.3 | 67.2 | 0.456 | 33.7 | 69.1 | 0.316 | 18.1 | 66.1 | ||
ConT+ | 0.185 | 11.7 | 31.5 | 0.163 | 10.5 | 27.2 | - | - | - | ||
TTransE* | 0.255 | 7.4 | 60.1 | 0.271 | 8.4 | 61.6 | 0.488 | 33.9 | 80.6 | ||
HyTE+ | 0.297 | 10.8 | 65.5 | 0.316 | 11.6 | 68.1 | - | - | - | ||
TA-TransE* | 0.275 | 9.5 | 62.5 | 0.299 | 9.6 | 66.8 | 0.484 | 32.9 | 80.7 | ||
TA-DistMult* | 0.477 | 36.3 | 68.6 | 0.474 | 34.6 | 72.8 | 0.700 | 65.2 | 78.5 | ||
DE-SimplE+ | 0.526 | 41.8 | 72.5 | 0.513 | 39.2 | 74.8 | 0.310 | 18.4 | 62.5 | ||
TComplEx# | 0.560 | 47.0 | 73.0 | 0.580 | 49.0 | 76.0 | 0.731 | 67.3 | 84.5 | ||
TNTComplEx# | 0.560 | 46.0 | 74.0 | 0.600 | 50.0 | 78.0 | 0.718 | 65.4 | 85.6 |
6 结束语
给定某个时间区间[t0,t1]及其对应的时态知识图谱G,补全任务是针对某个时刻t (t0≤t≤t1)的推理任务。比如,在例2中,可以由(a,履行合同,c,t2+1)补全出(a,签订合同,c,t2)。与补全任务相对的另一个任务是时态知识图谱的预测任务。即给定某个时间区间[t0,t1]及其对应的时态知识图谱G,预测出t>t1时刻图谱G的演化结果。相比而言,时态知识图谱的预测任务比补全任务更具有挑战性。限于文章的篇幅,请读者阅读参考文献[3]了解预测任务的解决方案和相关技术。
综合考虑时态知识图谱的补全方法不难发现,基于知识表示学习的方法是目前的主流方法。这类方法具有计算效率高和召回率高的特点,但是在表达能力上还存在弱点。因此,未来的研究工作可以关注如下两个可能的完善方向:①融合本体推理,运用基于符号逻辑的推理弥补知识表示学习在表达能力上的不足,完成知识表示学习模型的精准训练;②设计表达能力更强的神经网络模型,用于表达本体中所有可能的规则。
参考文献
GDELT:global data on events,location and tone,19792012
[C]//
Representation learning for dynamic graphs:a survey
[J]. ,
Temporal query entailment in the description logic SHQ
[J]. ,
Temporal conjunctive query answering in the extended DL-Lite family
[J]. ,
Temporal query answering in the description logic EL
[C]//
Temporal description logic for ontologybased data access
[C]//
Lightweight temporal description logics with rigid roles and restricted TBoxes
[C]//
First-order rewritability of ontology-mediated queries in linear temporal logic
[J]. ,
Translating embeddings for modeling multi-relational data
[C]//
Knowledge graph embedding by translating on hyperplanes
[C]//
Learning entity and relation embeddings for knowledge graph completion
[C]//
Knowledge graph embedding via dynamic mapping matrix
[C]//
TransG:a generative model for knowledge graph embedding
[C]//
RotatE:knowledge graph embedding by relational rotation in complex space
[C]//
A three-way model for collective learning on multi-relational data
[C]//
Holographic embeddings of knowledge graphs
[C]//
Embedding entities and relations for learning and inference in knowledge bases
[C]//
Complex embeddings for simple link prediction
[C]//
Analogical inference for multi-relational embeddings
[C]//
Simple embedding for link prediction in knowledge graphs
[C]//
Tucker:tensor factorization for knowledge graph completion
[C]//
A semantic matching energy function for learning with multi-relational data - application to word-sense disambiguation
[J]. ,
Reasoning with neural tensor networks for knowledge base completion
[C]//
Knowledge vault:a web-scale approach to probabilistic knowledge fusion
[C]//
Towards time-aware knowledge graph completion
[C]//
HyTE:hyperplane-based temporally aware knowledge graph embedding
[C]//
Embedding models for episodic knowledge graphs
[J]. ,
Tensor decompositions for temporal knowledge base completion
[C]//
Temporal knowledge base completion:new algorithms and evaluation protocols
[C]//
TeRo:a time-aware knowledge graph embedding via temporal rotation
[C]//
Learning sequence encoders for temporal knowledge graph completion
[C]//
Diachronic embedding for temporal knowledge graph completion
[C]//
TeMP:temporal message passing for temporal knowledge graph completion
[C]//
T-GAP:learning to walk across time for temporal knowledge graph completion
[J]. ,
RTFE:a recursive temporal fact embedding framework for temporal knowledge graph completion
[J]. ,
Temporal knowledge graph completion based on time series gaussian embedding
[C]//
DyERNIE:dynamic evolution of Riemannian manifold embeddings for temporal knowledge graph completion
[C]//
From knowledge graph embedding to ontology embedding? An analysis of the compatibility between vector space representations and rules
[C]//
Improved knowledge graph embedding using background taxonomic information
[C]//
Enhancing knowledge graph embedding from a logical perspective
[C]//
Knowledge graph embedding with logical consistency
[C]//
/
〈 | 〉 |