EvolveKG: a general framework to learn evolving knowledge graphs

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.

Graphical abstract

Keywords

knowledge graph / evolution / modal characterization / algorithmic implementation

Jiaqi Liu received her BE degree in Electronic Engineering from Shanghai Jiao Tong University, China in 2014, and PhD degree in the same major and the same university in 2019. She is currently an Associate Professor in School of Computer Science in Northwestern Polytechnical University, China. Her research of interests are in the area of social networks and social computing

Zhiwen Yu received the PhD degree of engineering in computer science and technology from Northwestern Polytechnical University, China in 2005. He is currently a professor at Northwestern Polytechnical University, China. He has worked as a research fellow at the Academic Center for Computing and Media Studies, Kyoto University, Japan from February 2007 to January 2009, and a postdoctoral researcher at the Information Technology Center, Nagoya University, Japan in 2006−2007. He has been an Alexander von Humboldt fellow at Mannheim University, Germany from November 2009 to October 2010. His research interests include pervasive computing, con- text-aware systems, humancomputer interaction, mobile social networks, and personalization

Bin Guo received the PhD degree in computer science from Keio University, Japan in 2009. He was a postdoc researcher with Institut Telecom SudParis, France. He is currently a professor at Northwestern Polytechnical University, China. His research interests include ubiquitous computing, mobile crowd sensing, and HCI

Cheng Deng received his BE degree in Computer Science from Hunan University, China in 2019. He is pursuing the PhD degree in Computer Science in Shanghai Jiao Tong University, China. His research of interests are in the area of knowledge graph, social networks and data mining

Luoyi Fu received her BE degree in Electronic Engineering in 2009 and PhD degree in Computer Science and Engineering from Shanghai Jiao Tong University, China in 2015. She is currently an assistant professor in Department of Computer Science and Engineering in Shanghai Jiao Tong University, China. Her research of interests are in the area of social networking and big data, scaling laws analysis in wireless networks, connectivity analysis and random graphs. She has been a member of the Technical Program Committees of several conferences including ACM MobiHoc 2018–2020, IEEE INFOCOM 2018–2020

Xinbing Wang received the BS degree (Hons.) from the Department of Automation, Shanghai Jiao Tong University, China in 1998, the MS degree from the Department of Computer Science and Technology, Tsinghua University, China in 2001, and the PhD degree, majoring in the electrical and computer engineering and minoring in mathematics, from North Carolina State University, USA in 2006. He is currently a professor with the Department of Electronic Engineering, Shanghai Jiao Tong University, China. He has been an Associate Editor for the IEEE/ACM Transactions on Networking and the IEEE Transactions on Mobile Computing, and a member of the Technical Program Committees of several conferences including the ACM MobiCom 2012, the ACM MobiHoc 2012–2014, and the IEEE INFOCOM 2009–2017

Chenghu Zhou received the BS degree in geography from Nanjing University, China in 1984, and the MS and PhD degrees in geographic information system from the Chinese Academy of Sciences (CAS), China in 1987 and 1992, respectively. He is currently an academician with CAS, where he is also a research professor with the Institute of Geographical Sciences and Natural Resources Research, China and a professor with the School of Geography and Ocean Science, Nanjing University, China. His research interests include spatial and temporal data mining, geographic modeling, hydrology and water resources, and geographic information systems and remote sensing applications

References

[1] Bordes A, Usunier N, Garcia-Durán A, Weston J, Yakhnenko O. Translating embeddings for modeling multi-relational data. In: Proceedings of the 26th International Conference on Neural Information Processing System. 2013, 2787−2795

[2] Wang Z, Zhang J, Feng J, Chen Z. Knowledge graph embedding by translating on hyperplanes. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2014, 1112−1119

[3] Lin Y, Liu Z, Sun M, Liu Y, Zhu X. Learning entity and relation embeddings for knowledge graph completion. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 2181−2187

[4] Ji G, He S, Xu L, Liu K, Zhao J. 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] Li M, Xing Y, Kong F, Zhou G . Towards better entity linking. Frontiers of Computer Science, 2022, 16( 2): 162308

[6] Shi C, Ding J, Cao X, Hu L, Wu B, Li X . Entity set expansion in knowledge graph: a heterogeneous information network perspective. Frontiers of Computer Science, 2021, 15( 1): 151307

[7] Bollacker K, Evans C, Paritosh P, Sturge T, Taylor J. 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] Lehmann J, Isele R, Jakob M, Jentzsch A, Kontokostas D, Mendes P N, Hellmann S, Morsey M, Van Kleef P, Auer S, Bizer C . DBpedia−a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web, 2015, 6( 2): 167–195

[9] Suchanek F M, Kasneci G, Weikum G. Yago: a core of semantic knowledge. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 697−706

[10] Lukovnikov D, Fischer A, Lehmann J, Auer S. 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] Yih W T, Richardson M, Meek C, Chang M W, Suh J. 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] Hoffmann R, Zhang C, Ling X, Zettlemoyer L, Weld D S. 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] Daiber J, Jakob M, Hokamp C, Mendes P N. Improving efficiency and accuracy in multilingual entity extraction. In: Proceedings of the 9th International Conference on Semantic Systems. 2013, 121−124

[14] Damljanovic D, Bontcheva K. Named entity disambiguation using linked data. In: Proceedings of the 9th Extended Semantic Web Conference. 2012, 231−240

[15] Zheng Z, Si X, Li F, Chang E Y, Zhu X. Entity disambiguation with freebase. In: Proceedings of 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology. 2012, 82−89

[16] Berant J, Chou A, Frostig R, Liang P. Semantic parsing on freebase from question-answer pairs. In: Proceedings of 2013 Conference on Empirical Methods in Natural Language Processing. 2013, 1533−1544

[17] Heck L P, Hakkani-Tür D, Tür G. 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] Fen J, Huang M, Wang M, Zhou M, Hao Y, Zhu X. Knowledge graph embedding by flexible translation. In: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning. 2016, 557−560

[19] Yang S, Tian J, Zhang H, Yan J, He H, Jin Y. 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] Ren F, Li J, Zhang H, Yang X. 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] Vashishth S, Sanyal S, Nitin V, Agrawal N, Talukdar P . 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] Cao Z, Xu Q, Yang Z, Yang Z, Cao X, Huang Q . Dual quaternion knowledge graph embeddings. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35( 8): 6894–6902

[23] Chung C, Whang J J. 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] Sadeghian A, Armandpour M, Colas A, Wang D Z . ChronoR: rotation based temporal knowledge graph embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35( 7): 6471–6479

[25] Wu J, Xu Y, Zhang Y, Ma C, Coates M, Cheung J C K. 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] Trivedi R, Dai H, Wang Y, Song L. Know-evolve: deep temporal reasoning for dynamic knowledge graphs. In: Proceedings of the 34th International Conference on Machine Learning. 2017, 3462−3471

[27] Deng S, Rangwala H, Ning Y. 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] Li Z, Jin X, Li W, Guan S, Guo J, Shen W, Wang Y, Cheng X. 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] Newman M E J . Clustering and preferential attachment in growing networks. Physical Review E, 2001, 64( 2): 025102(R)

[30] Bamberg S, Ajzen I, Schmidt P . 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] Pinder C, Vermeulen J, Cowan B R, Beale R . Digital behaviour change interventions to break and form habits. ACM Transactions on Computer-Human Interaction, 2018, 25( 3): 15

[32] Carden L, Wood W . Habit formation and change. Current Opinion in Behavioral Sciences, 2018, 20: 117–122

[33] Consolvo S, McDonald D W, Landay J A. 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] Hekler E B, Klasnja P, Froehlich J E, Buman M P. 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] Papadimitriou C H. Computational Complexity. Chichester: John Wiley and Sons Ltd., 2003

[36] Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004

[37] Leetaru K, Schrodt P A. GDELT: global data on events, location and tone, 1979-2012. In: Proceedings of ISA Annual Convention. 2013, 1−49

[38] Boschee E, Lautenschlager J, Brien S, Shellman S, Starz J, Ward M. ICEWS coded event data. Harvard Dataverse. 2015, 15

[39] Leblay J, Chekol M W. Deriving validity time in knowledge graph. In: Proceedings of the The Web Conference. 2018, 1771−1776

[40] Mahdisoltani F, Biega J, Suchanek F M. YAGO3: a knowledge base from multilingual wikipedias. In: Proceedings of the 7th Biennial Conference on Innovative Data Systems Research. 2005

[41] Han X, Cao S, Xin L, Lin Y, Liu Z, Sun M, Li J. 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] Jin W, Qu M, Jin X, Ren X. Recurrent event network: autoregressive structure inference over temporal knowledge graphs. 2019, arXiv preprint arXiv: 1904.05530

Acknowledgements

This work was supported in part by the National Key R&D Program of China (No. 2021ZD0113305), the National Natural Science Foundation of China (Grant Nos. 61960206008, 62002292, 42050105, 62020106005, 62061146002, 61960206002), the National Science Fund for Distinguished Young Scholars (No. 61725205), and Shanghai Pilot Program for Basic Research - Shanghai Jiao Tong University.

RIGHTS & PERMISSIONS

2024 Higher Education Press