More Web Proxy on the site http://driver.im/

research-article

Incorporating Multi-Level Sampling with Adaptive Aggregation for Inductive Knowledge Graph Completion

Authors:

Baocai YinAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data, Volume 18, Issue 5

Article No.: 128, Pages 1 - 16

https://doi.org/10.1145/3644822

Published: 26 March 2024 Publication History

Abstract

In recent years, Graph Neural Networks (GNNs) have achieved unprecedented success in handling graph-structured data, thereby driving the development of numerous GNN-oriented techniques for inductive knowledge graph completion (KGC). A key limitation of existing methods, however, is their dependence on pre-defined aggregation functions, which lack the adaptability to diverse data, resulting in suboptimal performance on established benchmarks. Another challenge arises from the exponential increase in irrelated entities as the reasoning path lengthens, introducing unwarranted noise and consequently diminishing the model’s generalization capabilities. To surmount these obstacles, we design an innovative framework that synergizes Multi-Level Sampling with an Adaptive Aggregation mechanism (MLSAA). Distinctively, our model couples GNNs with enhanced set transformers, enabling dynamic selection of the most appropriate aggregation function tailored to specific datasets and tasks. This adaptability significantly boosts both the model’s flexibility and its expressive capacity. Additionally, we unveil a unique sampling strategy designed to selectively filter irrelevant entities, while retaining potentially beneficial targets throughout the reasoning process. We undertake an exhaustive evaluation of our novel inductive KGC method across three pivotal benchmark datasets and the experimental results corroborate the efficacy of MLSAA.

References

[1]

Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. arXiv:1607.06450. Retrieved from https://arxiv.org/abs/1607.06450

[2]

Jinheon Baek, Minki Kang, and Sung Ju Hwang. 2021. Accurate learning of graph representations with graph multiset pooling. In Proceedings of the 9th International Conference on Learning Representations.

[3]

Muhammed Fatih Balin and Ümit V. Çatalyürek. 2022. (LA)yer-neigh(BOR) sampling: Defusing neighborhood explosion in GNNs. abs/2210.13339. Retrieved from https://arxiv.org/abs/2210.13339

[4]

Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew M. Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. 2018. Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261. Retrieved from https://arxiv.org/abs/1806.01261

[5]

Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. 2787–2795.

[6]

Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the 6th International Conference on Learning Representations.

[7]

Ling Chen, Xing Tang, Weiqi Chen, Yuntao Qian, Yansheng Li, and Yongjun Zhang. 2022. DACHA: A dual graph convolution based temporal knowledge graph representation learning method using historical relation. ACM Transactions on Knowledge Discovery from Data 16, 3 (2022), 46:1–46:18.

Digital Library

[8]

Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 2019. Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 257–266.

Digital Library

[9]

Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. 2022. You are AllSet: A multiset function framework for hypergraph neural networks. In Proceedings of the 10th International Conference on Learning Representations..

[10]

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2D knowledge graph embeddings. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 1811–1818.

[11]

Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek. 2015. Fast rule mining in ontological knowledge bases with AMIE+. The VLDB Journal 24, 6 (2015), 707–730.

Digital Library

[12]

Alberto García-Durán, Mathias Niepert, and Heiner Stuckenschmidt. 2017. Kern: Kernel embeddings of categorical data. In Proceedings of the International Semantic Web Conference. Springer, 210–218.

[13]

Marta Garnelo, Dan Rosenbaum, Christopher Maddison, Tiago Ramalho, David Saxton, Murray Shanahan, Yee Whye Teh, Danilo Jimenez Rezende, and S. M. Ali Eslami. 2018. Conditional neural processes. In Proceedings of the 35th International Conference on Machine Learning. 1690–1699.

[14]

Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning. 1263–1272.

Digital Library

[15]

William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 1024–1034.

[16]

Vinh Thinh Ho, Daria Stepanova, Mohamed H. Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. 2018. Rule learning from knowledge graphs guided by embedding models. In Proceedings of the Semantic Web - ISWC 2018-17th International Semantic Web Conference. 72–90.

Digital Library

[17]

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. In Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6–12, 2020, virtual.

[18]

Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018. Adaptive sampling towards fast graph representation learning. In Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3–8, 2018, Montréal, Canada. 4563–4572.

[19]

Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7–9, 2015, Conference Track Proceedings.

[20]

Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations.

[21]

Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018. Canonical tensor decomposition for knowledge base completion. In Proceedings of the 35th International Conference on Machine Learning. 2869–2878.

[22]

Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. 2019. Set transformer: A framework for attention-based permutation-invariant neural networks. In Proceedings of the 36th International Conference on Machine Learning. 3744–3753.

[23]

David Lopez-Paz, Robert Nishihara, Soumith Chintala, Bernhard Schölkopf, and Léon Bottou. 2017. Discovering causal signals in images. In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. 58–66.

[24]

Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. 2018. Fine-grained evaluation of rule- and embedding-based systems for knowledge graph completion. In Proceedings of the Semantic Web - ISWC 2018-17th International Semantic Web Conference. 3–20.

Digital Library

[25]

Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. 2019. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. In Proceedings of the 7th International Conference on Learning Representations.

[26]

Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. 2019. Learning attention-based embeddings for relation prediction in knowledge graphs. In Proceedings of the 57th Conference of the Association for Computational Linguistics. 4710–4723.

[27]

Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. 2015. Compositional vector space models for knowledge base completion. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing. 156–166.

[28]

Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic differentiation in pytorch. In Proceedings of the Neural Information Processing Systems.

[29]

Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. 2017. PointNet: Deep learning on point sets for 3D classification and segmentation. In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. 77–85.

[30]

Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. 2019. DRUM: End-to-end differentiable rule mining on knowledge graphs. In Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019. 15321–15331.

[31]

Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In Proceedings of the Semantic Web - 15th International Conference. 593–607.

Digital Library

[32]

Zhihao Shi, Xize Liang, and Jie Wang. 2023. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In Proceedings of the 11th International Conference on Learning Representations.

[33]

Jake Snell, Kevin Swersky, and Richard S. Zemel. 2017. Prototypical networks for few-shot learning. In Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 4077–4087.

[34]

Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. 2013. Reasoning with neural tensor networks for knowledge base completion. In Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. 926–934.

[35]

Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. RotatE: Knowledge graph embedding by relational rotation in complex space. In Proceedings of the 7th International Conference on Learning Representations.

[36]

Komal K. Teru, Etienne G. Denis, and William L. Hamilton. 2020. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning. 9448–9457.

Digital Library

[37]

Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality. 57–66.

[38]

Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. 2015. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. 1499–1509.

[39]

Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha P. Talukdar. 2020. Composition-based multi-relational graph convolutional networks. In Proceedings of the 8th International Conference on Learning Representations.

[40]

Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. 2019. On the limitations of representing functions on sets. In Proceedings of the 36th International Conference on Machine Learning. 6487–6494.

[41]

Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. 2018. RippleNet: Propagating user preferences on the knowledge graph for recommender systems. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 417–426.

Digital Library

[42]

Jiapu Wang, Boyue Wang, Junbin Gao, Simin Hu, Yongli Hu, and Baocai Yin. 2024. Multi-level interaction based knowledge graph completion. IEEE/ACM Transactions on Audio, Speech, and Language Processing 32 (2024), 386–396.

Digital Library

[43]

Jiapu Wang, Boyue Wang, Junbin Gao, Yongli Hu, and Baocai Yin. 2023. Multi-concept representation learning for knowledge graph completion. ACM Transactions on Knowledge Discovery from Data 17, 1 (2023), 11:1–11:19.

Digital Library

[44]

Jiapu Wang, Boyue Wang, Junbin Gao, Xiaoyan Li, Yongli Hu, and Baocai Yin. 2023. TDN: Triplet distributor network for knowledge graph completion. IEEE Transactions on Knowledge and Data Engineering 35, 12 (2023), 13002–13014.

Digital Library

[45]

Jiapu Wang, Boyue Wang, Meikang Qiu, Shirui Pan, Bo Xiong, Heng Liu, Linhao Luo, Tengfei Liu, Yongli Hu, Baocai Yin, and Wen Gao. 2023. A survey on temporal knowledge graph completion: Taxonomy, progress, and prospects. arXiv:2308.02457. Retrieved from https://arxiv.org/abs/2308.02457

[46]

Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. 2019. KGAT: Knowledge graph attention network for recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 950–958.

Digital Library

[47]

Yashen Wang, Xiaoye Ouyang, Dayu Guo, and Xiaoling Zhu. 2024. MEGA: Meta-graph augmented pre-training model for knowledge graph completion. ACM Transactions on Knowledge Discovery from Data 18, 1 (2024), 30:1–30:24.

Digital Library

[48]

Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. 564–573.

[49]

Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the 3rd International Conference on Learning Representations.

[50]

Fan Yang, Zhilin Yang, and William W. Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. In Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 2319–2328.

[51]

Minji Yoon, Théophile Gervet, Baoxu Shi, Sufeng Niu, Qi He, and Jaewon Yang. 2021. Performance-adaptive sampling strategy towards fast and accurate graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2021. 2046–2056.

Digital Library

[52]

Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander AJ Smola. 2017. Deep sets. In Proceedings of the Advances in Neural Information Processing Systems. 3391–3401.

[53]

Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor K. Prasanna, Long Jin, and Ren Chen. 2021. Decoupling the depth and scope of graph neural networks. In Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021. 19665–19679.

[54]

Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. 2020. GraphSAINT: Graph sampling based inductive learning method. In Proceedings of the 8th International Conference on Learning Representations.

[55]

Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J. Smola, and Le Song. 2018. Variational reasoning for question answering with knowledge graph. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 6069–6076.

[56]

Yuxuan Zhang, Yuanxiang Li, Yini Zhang, Yilin Wang, Yongshen Yang, Xian Wei, and Jianhua Luo. 2023. Missing-edge aware knowledge graph inductive inference through dual graph learning and traversing. Expert Systems with Applications 213, Part B (2023), 118969.

Digital Library

[57]

Yongqi Zhang and Quanming Yao. 2022. Knowledge graph reasoning with relational digraph. In Proceedings of the ACM Web Conference 2022. 912–924.

Digital Library

[58]

Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. 2019. ERNIE: Enhanced language representation with informative entities. In Proceedings of the 57th Conference of the Association for Computational Linguistics. 1441–1451.

[59]

Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang. 2021. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021. 29476–29490.

[60]

Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019. 11247–11256.

Cited By

Wang YZhu XChen TZhang Y(2024)An Aggregation Procedure Optimization Method by Leveraging Neighboring Prompt for GCN-based Knowledge Graph Completion Model2024 IEEE 9th International Conference on Data Science in Cyberspace (DSC)10.1109/DSC63484.2024.00042(263-270)Online publication date: 23-Aug-2024
https://doi.org/10.1109/DSC63484.2024.00042
Sun KJiang HHu YYin B(2024)Generating Graph-Based Rules for Enhancing Logical ReasoningAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5615-5_12(143-156)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5615-5_12

Index Terms

Incorporating Multi-Level Sampling with Adaptive Aggregation for Inductive Knowledge Graph Completion
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Embedded systems
    2. Robotics
2. Networks
  1. Network properties
    1. Network reliability

Recommendations

A versatile adaptive aggregation framework for spatially large discrete location-allocation problems

An adaptive aggregation framework for discrete location-allocation problems is proposed.The mechanism relies on the adjustment of data aggregation to high quality solutions.Adaptive aggregation is more beneficial than the elimination of aggregation ...
Multilevel Adaptive Aggregation for Markov Chains, with Application to Web Ranking

A multilevel adaptive aggregation method for calculating the stationary probability vector of an irreducible stochastic matrix is described. The method is a special case of the adaptive smoothed aggregation and adaptive algebraic multigrid methods for ...
Logic attention based neighborhood aggregation for inductive knowledge graph embedding
AAAI'19/IAAI'19/EAAI'19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence

Knowledge graph embedding aims at modeling entities and relations with low-dimensional vectors. Most previous methods require that all entities should be seen during training, which is unpractical for real-world knowledge graphs with new entities emerging ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 18, Issue 5

June 2024

699 pages

EISSN:1556-472X

DOI:10.1145/3613659

Editor:
Jian Pei
Duke University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2024

Online AM: 07 February 2024

Accepted: 29 January 2024

Received: 16 October 2023

Published in TKDD Volume 18, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Key R&D Program of China
National Natural Science Foundation of China
R&D Program of Beijing Municipal Education Commission
Beijing Natural Science Foundation
Engineering Research Center of Intelligent Perception and Autonomous Control, Ministry of Education

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
459
Total Downloads

Downloads (Last 12 months)379
Downloads (Last 6 weeks)28

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang YZhu XChen TZhang Y(2024)An Aggregation Procedure Optimization Method by Leveraging Neighboring Prompt for GCN-based Knowledge Graph Completion Model2024 IEEE 9th International Conference on Data Science in Cyberspace (DSC)10.1109/DSC63484.2024.00042(263-270)Online publication date: 23-Aug-2024
https://doi.org/10.1109/DSC63484.2024.00042
Sun KJiang HHu YYin B(2024)Generating Graph-Based Rules for Enhancing Logical ReasoningAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5615-5_12(143-156)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5615-5_12

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents