EvolveKG: a general framework to learn evolving knowledge graphs

doi:10.1007/s11704-022-2467-9

Front. Comput. Sci.

2024, Vol. 18

Issue (3) : 183309 https://doi.org/10.1007/s11704-022-2467-9

RESEARCH ARTICLE

EvolveKG: a general framework to learn evolving knowledge graphs

Jiaqi LIU¹, Zhiwen YU¹(

), Bin GUO¹, Cheng DENG², Luoyi FU², Xinbing WANG², Chenghu ZHOU³

¹. School of Computer Science, Northwestern Polytechnical University, Xi’an 710129, China
². Department of Computer Science, Shanghai Jiao Tong University, Shanghai 200240, China
³. Institute of Geographical Science and Natural Resources Research, Chinese Academy of Sciences, Bejjing 100864, China

Download: PDF(15563 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

A great many practical applications have observed knowledge evolution, i.e., continuous born of new knowledge, with its formation influenced by the structure of historical knowledge. This observation gives rise to evolving knowledge graphs whose structure temporally grows over time. However, both the modal characterization and the algorithmic implementation of evolving knowledge graphs remain unexplored. To this end, we propose EvolveKG – a general framework that enables algorithms in the static knowledge graphs to learn the evolving ones. EvolveKG quantifies the influence of a historical fact on a current one, called the effectiveness of the fact, and makes knowledge prediction by leveraging all the cross-time knowledge interaction. The novelty of EvolveKG lies in Derivative Graph – a weighted snapshot of evolution at a certain time. Particularly, each weight quantifies knowledge effectiveness through a temporarily decaying function of consistency and attenuation, two proposed factors depicting whether or not the effectiveness of a fact fades away with time. Besides, considering both knowledge creation and loss, we obtain higher prediction accuracy when the effectiveness of all the facts increases with time or remains unchanged. Under four real datasets, the superiority of EvolveKG is confirmed in prediction accuracy.

Keywords knowledge graph evolution modal characterization algorithmic implementation

Corresponding Author(s): Zhiwen YU

Just Accepted Date: 21 December 2022 Issue Date: 21 April 2023

Cite this article:

Jiaqi LIU,Zhiwen YU,Bin GUO, et al. EvolveKG: a general framework to learn evolving knowledge graphs[J]. Front. Comput. Sci., 2024, 18(3): 183309.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2467-9
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I3/183309

Fig.1 An example of evolving knowledge graphs, where the fact happened more recently is represented by the line with a larger width

Notation	Definition
$G (V, E)$	Knowledge graph with entity set $V$ and relation set $E$ .
$G ~ (V ′, E ′)$	Derivative Graph of $G (V, E)$ .
$e v s$	Subject entity $v$ .
$e v o$	Object entity $v$ .
$(e v s, r, e u o, t)$	Fact where relation $r$ occurs between subject entity $e v s$ and object entity $e u o$ at time $t$ .
$d v s (t)$	Subject degree of entity $v$ at time $t$ .
$d v o (t)$	Object degree of entity $v$ at time $t$ .
$d^v s (t)$	Weighted subject degree of entity $v$ at time $t$ .
$d^v o (t)$	Weighted object degree of entity $v$ at time $t$ .
$e^(t)$	Average weighted number of edges in $G ~ (V ′, E ′)$ .
$λ$	Parameter of the attenuation function.
$s (t)$	Speed function of $G (V, E)$ .
$s^(t)$	Effective speed function of $G (V, E)$ .
$l (t)$	Loss rate of knowledge in $G (V, E)$ .

Tab.1 Notations and definitions

Fig.2 An illustration on the proposed framework – EvolveKG

Tab.2 Statistical properties of datasets.

Fig.3 Evaluation on MeanRank - TransE. (a) GDELT; (b) ICEWS; (c) WIKI; (d) YAGO

Fig.4 Evaluation on Hit@10 - TransE. (a) GDELT; (b) ICEWS; (c) WIK; (d) YAGO

Fig.5 Evaluation on MeanRank - TransH. (a) GDELT; (b) ICEWS; (c) WIKI; (d) YAGO

Fig.6 Evaluation on Hit@10 - TransH. (a) GDELT; (b) ICEWS; (c) WIKI; (d) YAGO

Fig.7 Evaluation on MeanRank - TransD. (a) GDELT; (b) ICEWS; (c) WIKI; (d) YAGO

Fig.8 Evaluation on Hit@10 - TransD. (a) GDELT; (b) ICEWS; (c) WIKI; (d) YAGO

Fig.9 MeanRank with varying time ranges of historical knowledge

Fig.10 Hits@10 with varying time ranges of historical knowledge

Tab.3 Running time pre epoch

1	A, Bordes N, Usunier A, Garcia-Durán J, Weston O Yakhnenko . Translating embeddings for modeling multi-relational data. In: Proceedings of the 26th International Conference on Neural Information Processing System. 2013, 2787−2795
2	Z, Wang J, Zhang J, Feng Z Chen . Knowledge graph embedding by translating on hyperplanes. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2014, 1112−1119
3	Y, Lin Z, Liu M, Sun Y, Liu X Zhu . Learning entity and relation embeddings for knowledge graph completion. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 2181−2187
4	G, Ji S, He L, Xu K, Liu J Zhao . Knowledge graph embedding via dynamic mapping matrix. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing. 2015, 687−696
5	M, Li Y, Xing F, Kong G Zhou . Towards better entity linking. Frontiers of Computer Science, 2022, 16( 2): 162308
6	C, Shi J, Ding X, Cao L, Hu B, Wu X Li . Entity set expansion in knowledge graph: a heterogeneous information network perspective. Frontiers of Computer Science, 2021, 15( 1): 151307
7	K, Bollacker C, Evans P, Paritosh T, Sturge J Taylor . Freebase: a collaboratively created graph database for structuring human knowledge. In: Proceedings of 2008 ACM SIGMOD International Conference on Management of Data. 2008, 1247−1250
8	J, Lehmann R, Isele M, Jakob A, Jentzsch D, Kontokostas P N, Mendes S, Hellmann M, Morsey Kleef P, Van S, Auer C Bizer . DBpedia−a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web, 2015, 6( 2): 167–195
9	F M, Suchanek G, Kasneci G Weikum . Yago: a core of semantic knowledge. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 697−706
10	D, Lukovnikov A, Fischer J, Lehmann S Auer . Neural network-based question answering over knowledge graphs on word and character level. In: Proceedings of the 26th International Conference on World Wide Web. 2017, 1211−1220
11	W T, Yih M, Richardson C, Meek M W, Chang J Suh . The value of semantic parse labeling for knowledge base question answering. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. 2016, 201−206
12	R, Hoffmann C, Zhang X, Ling L, Zettlemoyer D S Weld . Knowledge-based weak supervision for information extraction of overlapping relations. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. 2011, 541−550
13	J, Daiber M, Jakob C, Hokamp P N Mendes . Improving efficiency and accuracy in multilingual entity extraction. In: Proceedings of the 9th International Conference on Semantic Systems. 2013, 121−124
14	D, Damljanovic K Bontcheva . Named entity disambiguation using linked data. In: Proceedings of the 9th Extended Semantic Web Conference. 2012, 231−240
15	Z, Zheng X, Si F, Li E Y, Chang X Zhu . Entity disambiguation with freebase. In: Proceedings of 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology. 2012, 82−89
16	J, Berant A, Chou R, Frostig P Liang . Semantic parsing on freebase from question-answer pairs. In: Proceedings of 2013 Conference on Empirical Methods in Natural Language Processing. 2013, 1533−1544
17	L P, Heck D, Hakkani-Tür G Tür . Leveraging knowledge graphs for web-scale unsupervised semantic parsing. In: Proceedings of the 14th Annual Conference of the International Speech Communication Association. 2013, 1594−1598
18	J, Fen M, Huang M, Wang M, Zhou Y, Hao X Zhu . Knowledge graph embedding by flexible translation. In: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning. 2016, 557−560
19	S, Yang J, Tian H, Zhang J, Yan H, He Y Jin . TransMS: knowledge graph embedding for complex relations by multidirectional semantics. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 1935−1942
20	F, Ren J, Li H, Zhang X Yang . TransP: a new knowledge graph embedding model by translating on positions. In: Proceedings of 2020 IEEE International Conference on Knowledge Graph (ICKG). 2020, 344−351
21	S, Vashishth S, Sanyal V, Nitin N, Agrawal P Talukdar . InteractE: improving convolution-based knowledge graph embeddings by increasing feature interactions. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34( 3): 3009–3016
22	Z, Cao Q, Xu Z, Yang Z, Yang X, Cao Q Huang . Dual quaternion knowledge graph embeddings. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35( 8): 6894–6902
23	C, Chung J J Whang . Knowledge graph embedding via metagraph learning. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021, 2212−2216
24	A, Sadeghian M, Armandpour A, Colas D Z Wang . ChronoR: rotation based temporal knowledge graph embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35( 7): 6471–6479
25	J, Wu Y, Xu Y, Zhang C, Ma M, Coates J C K Cheung . TIE: a framework for embedding-based incremental temporal knowledge graph completion. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021, 428−437
26	R, Trivedi H, Dai Y, Wang L Song . Know-evolve: deep temporal reasoning for dynamic knowledge graphs. In: Proceedings of the 34th International Conference on Machine Learning. 2017, 3462−3471
27	S, Deng H, Rangwala Y Ning . Dynamic knowledge graph based multi-event forecasting. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020, 1585−1595
28	Z, Li X, Jin W, Li S, Guan J, Guo W, Shen Y, Wang X Cheng . Temporal knowledge graph reasoning based on evolutional representation learning. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021, 408−417
29	M E J Newman . Clustering and preferential attachment in growing networks. Physical Review E, 2001, 64( 2): 025102(R)
30	S, Bamberg I, Ajzen P Schmidt . Choice of travel mode in the theory of planned behavior: the roles of past behavior, habit, and reasoned action. Basic and Applied Social Psychology, 2003, 25( 3): 175–187
31	C, Pinder J, Vermeulen B R, Cowan R Beale . Digital behaviour change interventions to break and form habits. ACM Transactions on Computer-Human Interaction, 2018, 25( 3): 15
32	L, Carden W Wood . Habit formation and change. Current Opinion in Behavioral Sciences, 2018, 20: 117–122
33	S, Consolvo D W, McDonald J A Landay . Theory-driven design strategies for technologies that support behavior change in everyday life. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. 2009, 405−414
34	E B, Hekler P, Klasnja J E, Froehlich M P Buman . Mind the theoretical gap: interpreting, using, and developing behavioral theory in HCI research. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. 2013, 3307−3316
35	C H Papadimitriou . Computational Complexity. Chichester: John Wiley and Sons Ltd., 2003
36	S, Boyd L Vandenberghe . Convex Optimization. Cambridge: Cambridge University Press, 2004
37	K, Leetaru P A Schrodt . GDELT: global data on events, location and tone, 1979-2012. In: Proceedings of ISA Annual Convention. 2013, 1−49
38	E, Boschee J, Lautenschlager S, Brien S, Shellman J, Starz M Ward . ICEWS coded event data. Harvard Dataverse. 2015, 15
39	J, Leblay M W Chekol . Deriving validity time in knowledge graph. In: Proceedings of the The Web Conference. 2018, 1771−1776
40	F, Mahdisoltani J, Biega F M Suchanek . YAGO3: a knowledge base from multilingual wikipedias. In: Proceedings of the 7th Biennial Conference on Innovative Data Systems Research. 2005
41	X, Han S, Cao L, Xin Y, Lin Z, Liu M, Sun J Li . OpenKE: an open toolkit for knowledge embedding. In: Proceedings of 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. 2018, 139−144
42	W, Jin M, Qu X, Jin X Ren . Recurrent event network: autoregressive structure inference over temporal knowledge graphs. 2019, arXiv preprint arXiv: 1904.05530

[1]

FCS-22467-OF-JL_suppl_1

Download

[1]	Miao ZHANG, Tingting HE, Ming DONG. Meta-path reasoning of knowledge graph for commonsense question answering[J]. Front. Comput. Sci., 2024, 18(1): 181303-.
[2]	Shiwei PAN, Yiming MA, Yiyuan WANG, Zhiguo ZHOU, Jinchao JI, Minghao YIN, Shuli HU. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem[J]. Front. Comput. Sci., 2023, 17(4): 174326-.
[3]	Yongchun ZHU, Fuzhen ZHUANG, Xiangliang ZHANG, Zhiyuan QI, Zhiping SHI, Juan CAO, Qing HE. Combat data shift in few-shot learning with knowledge graph[J]. Front. Comput. Sci., 2023, 17(1): 171305-.
[4]	Yunhao SUN, Guanyu LI, Jingjing DU, Bo NING, Heng CHEN. A subgraph matching algorithm based on subgraph index for knowledge graph[J]. Front. Comput. Sci., 2022, 16(3): 163606-.
[5]	Hong QIAN, Yang YU. Derivative-free reinforcement learning: a review[J]. Front. Comput. Sci., 2021, 15(6): 156336-.
[6]	Peng YANG, Qi YANG, Ke TANG, Xin YAO. Parallel exploration via negatively correlated search[J]. Front. Comput. Sci., 2021, 15(5): 155333-.
[7]	Ibrahim ALSEADOON, Aakash AHMAD, Adel ALKHALIL, Khalid SULTAN. Migration of existing software systems to mobile computing platforms: a systematic mapping study[J]. Front. Comput. Sci., 2021, 15(2): 152204-.
[8]	Jianpeng HU, Linpeng HUANG, Tianqi SUN, Ying FAN, Wenqiang HU, Hao ZHONG. Proactive planning of bandwidth resource using simulation-based what-if predictions forWeb services in the cloud[J]. Front. Comput. Sci., 2021, 15(1): 151201-.
[9]	Chuan SHI, Jiayu DING, Xiaohuan CAO, Linmei HU, Bin WU, Xiaoli LI. Entity set expansion in knowledge graph: a heterogeneous information network perspective[J]. Front. Comput. Sci., 2021, 15(1): 151307-.
[10]	Yihui LIANG, Han HUANG, Zhaoquan CAI. PSO-ACSC: a large-scale evolutionary algorithm for image matting[J]. Front. Comput. Sci., 2020, 14(6): 146321-.
[11]	Yaopeng LIU, Hao PENG, Jianxin LI, Yangqiu SONG, Xiong LI. Event detection and evolution in multi-lingual social streams[J]. Front. Comput. Sci., 2020, 14(5): 145612-.
[12]	Munish SAINI, Kuljit Kaur CHAHAL. Change profile analysis of open-source software systems to understand their evolutionary behavior[J]. Front. Comput. Sci., 2018, 12(6): 1105-1124.
[13]	Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.
[14]	Bo SUN, Haiyan CHEN, Jiandong WANG, Hua XIE. Evolutionary under-sampling based bagging ensemble method for imbalanced data classification[J]. Front. Comput. Sci., 2018, 12(2): 331-350.
[15]	Jayanthi MANICASSAMY, Dinesh KARUNANIDHI, Sujatha POTHULA, Vengattaraman THIRUMAL, Dhavachelvan PONNURANGAM, Subramanian RAMALINGAM. GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems[J]. Front. Comput. Sci., 2018, 12(1): 101-121.

Viewed

Full text

Abstract

Cited

Shared

Discussed