research-article

Message Function Search for Knowledge Graph Embedding

Authors:

Lei ChenAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 2633 - 2644

https://doi.org/10.1145/3543507.3583546

Published: 30 April 2023 Publication History

Abstract

Recently, many promising embedding models have been proposed to embed knowledge graphs (KGs) and their more general forms, such as n-ary relational data (NRD) and hyper-relational KG (HKG). To promote the data adaptability and performance of embedding models, KG searching methods propose to search for suitable models for a given KG data set. But they are restricted to a single KG form, and the searched models are restricted to a single type of embedding model. To tackle such issues, we propose to build a search space for the message function in graph neural networks (GNNs). However, it is a non-trivial task. Existing message function designs fix the structures and operators, which makes them difficult to handle different KG forms and data sets. Therefore, we first design a novel message function space, which enables both structures and operators to be searched for the given KG form (including KG, NRD, and HKG) and data. The proposed space can flexibly take different KG forms as inputs and is expressive to search for different types of embedding models. Especially, some existing message function designs and some classic KG embedding models can be instantiated as special cases of our space. We empirically show that the searched message functions are data-dependent, and can achieve leading performance on benchmark KGs, NRD, and HKGs.

References

[1]

Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. 2019. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICML.

[2]

Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007. Dbpedia: A nucleus for a web of open data. In The Semantic Web. Springer, 722–735.

Digital Library

[3]

I. Balazevic, C. Allen, and T. Hospedales. 2019. TuckER: Tensor Factorization for Knowledge Graph Completion. In EMNLP. 5188–5197.

[4]

J. Bergstra, D. Yamins, and D. D. Cox. 2013. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. (2013).

[5]

Max Berrendorf, Evgeniy Faerman, Laurent Vermue, and Volker Tresp. 2020. On the ambiguity of rank-based evaluation of entity alignment or link prediction methods. arXiv preprint arXiv:2002.06914 (2020).

[6]

Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD. 1247–1250.

[7]

A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In NIPS. 2787–2795.

[8]

Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. 2019. Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences. In WWW. 151–161.

[9]

Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. 2020. Fair darts: Eliminating unfair advantages in differentiable architecture search. In ECCV. Springer, 465–480.

[10]

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2D knowledge graph embeddings. In AAAI.

[11]

Shimin Di, Quanming Yao, and Lei Chen. 2021. Searching to Sparsify Tensor Decomposition for N-ary Relational Data. In Webconf. 4043–4054.

[12]

Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, 2019. Neural architecture search: A survey.J. Mach. Learn. Res. 20, 55 (2019), 1–21.

[13]

Stefan Falkner, Aaron Klein, and Frank Hutter. 2018. BOHB: Robust and efficient hyperparameter optimization at scale. In ICML. PMLR, 1437–1446.

[14]

Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. 2020. Knowledge hypergraphs: Prediction beyond binary relations. (2020).

[15]

Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. 2020. Message Passing for Hyper-Relational Knowledge Graphs. In EMNLP.

[16]

Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. 2020. Graph neural architecture search. In IJCAI, Vol. 20. 1403–1409.

[17]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In ICML. PMLR, 1263–1272.

[18]

Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. 2020. Neuinfer: Knowledge inference on n-ary facts. In ACL. 6141–6151.

[19]

Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. 2019. Link prediction on n-ary relational data. In WWW. 583–593.

[20]

William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS. 1025–1035.

[21]

Frank L Hitchcock. 1927. The expression of a tensor or a polyadic as a sum of products. Journal of Mathematics and Physics 6, 1-4 (1927), 164–189.

[22]

F. Hutter, L. Kotthoff, and J. Vanschoren. 2018. Automated Machine Learning: Methods, Systems, Challenges. Springer.

[23]

Eric Jang, Shixiang Gu, and Ben Poole. 2016. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv:1611.01144 (2016).

[24]

Shengli Jiang and Prasanna Balaprakash. 2020. Graph Neural Network Architecture Search for Molecular Property Prediction. In IEEE Big Data. IEEE, 1346–1353.

[25]

S. Kazemi and D. Poole. 2018. Simple embedding for link prediction in knowledge graphs. In NeurIPS. 4284–4295.

[26]

D.P. Kingma and J. Ba. 2014. Adam: A method for stochastic optimization. In ICLR.

[27]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. In ICLR.

[28]

T. Lacroix, N. Usunier, and G. Obozinski. 2018. Canonical Tensor Decomposition for Knowledge Base Completion. In ICML. 2863–2872.

[29]

Haoyang Li, Shimin Di, Zijian Li, Lei Chen, and Jiannong Cao. 2022. Black-box Adversarial Attack and Defense on Graph Neural Networks. In ICDE. IEEE, 1017–1030.

[30]

H. Liu, K. Simonyan, and Y. Yang. 2018. DARTS: Differentiable architecture search. In ICLR.

[31]

Yu Liu, Quanming Yao, and Yong Li. 2020. Generalizing Tensor Decomposition for N-ary Relational Knowledge Bases. In WebConf. 1104–1114.

[32]

Yu Liu, Quanming Yao, and Yong Li. 2021. Role-Aware Modeling for N-ary Relational Knowledge Bases. In WebConf 2021. 2660–2671.

Digital Library

[33]

Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. 2017. Neural network-based question answering over knowledge graphs on word and character level. In WWW. 1211–1220.

[34]

Chris J Maddison, Andriy Mnih, and Yee Whye Teh. 2017. The concrete distribution: A continuous relaxation of discrete random variables. ICLR (2017).

[35]

Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. 2015. A review of relational machine learning for knowledge graphs. Proc. IEEE 104, 1 (2015), 11–33.

[36]

Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. 2016. Holographic embeddings of knowledge graphs. In AAAI.

[37]

A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, 2019. PyTorch: An imperative style, high-performance deep learning library. In NeurIPS. 8024–8035.

[38]

H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean. 2018. Efficient Neural Architecture Search via Parameter Sharing. In ICML. 4092–4101.

[39]

Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. 2021. Knowledge graph embedding for link prediction: A comparative analysis. TKDD 15, 2 (2021), 1–49.

[40]

Paolo Rosso, Dingqi Yang, and Philippe Cudré-Mauroux. 2020. Beyond triplets: hyper-relational knowledge graph embedding for link prediction. In WebConf. 1885–1896.

[41]

Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In ESWC. Springer, 593–607.

[42]

DI Shimin, YAO Quanming, Yongqi ZHANG, and CHEN Lei. 2021. Efficient Relation-aware Scoring Function Search for Knowledge Graph Embedding. In ICDE. IEEE, 1104–1115.

[43]

Z. Sun, Z. Deng, J. Nie, and J. Tang. 2019. RotatE: Knowledge graph embedding by relational rotation in complex space. In ICLR.

[44]

Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2018. RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In ICLR.

[45]

Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. 2020. A Re-evaluation of Knowledge Graph Completion Methods. In ACL. 5516–5522.

[46]

K. Toutanova and D. Chen. 2015. Observed versus latent features for knowledge base and text inference. In Workshop on CVSMC. 57–66.

[47]

T. Trouillon, Christopher R., É. Gaussier, J. Welbl, S. Riedel, and G. Bouchard. 2017. Knowledge graph completion via complex tensor factorization. JMLR 18, 1 (2017), 4735–4772.

Digital Library

[48]

Ledyard R Tucker. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika 31, 3 (1966), 279–311.

[49]

Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2019. Composition-based Multi-Relational Graph Convolutional Networks. In ICLR.

[50]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In NeurIPS. 5998–6008.

[51]

Ellen Voorhees. 1999. The TREC-8 question answering track report. In TREC, Vol. 99. 77–82.

[52]

Hongwei Wang, Hongyu Ren, and Jure Leskovec. 2020. Entity context and relational paths for knowledge graph completion. arXiv:2002.06757 (2020), 47.

[53]

Q. Wang, Z. Mao, B. Wang, and L. Guo. 2017. Knowledge graph embedding: A survey of approaches and applications. TKDE 29, 12 (2017), 2724–2743.

[54]

Zhili Wang, Shimin Di, and Lei Chen. 2021. AutoGEL: An Automated Graph Neural Network with Explicit Link Information. Advances in Neural Information Processing Systems 34 (2021), 24509–24522.

[55]

Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge graph embedding by translating on hyperplanes. In AAAI.

[56]

Lanning Wei, Huan Zhao, and Zhiqiang He. 2022. Designing the topology of graph neural networks: A novel feature fusion perspective. In Proceedings of the ACM Web Conference 2022. 1381–1391.

Digital Library

[57]

Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. 2021. Pooling architecture search for graph classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2091–2100.

Digital Library

[58]

Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang. 2016. On the representation and embedding of knowledge bases beyond binary relations. In IJCAI.

[59]

Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. 2018. SNAS: stochastic neural architecture search. arXiv preprint arXiv:1812.09926 (2018).

[60]

Naganand Yadati. 2020. Neural Message Passing for Multi-Relational Ordered and Recursive Hypergraphs. NeurIPS 33 (2020).

[61]

B. Yang, W. Yih, X. He, J. Gao, and L. Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In ICLR.

[62]

Quanming Yao and Mengshuo Wang. 2018. Taking human out of learning applications: A survey on automated machine learning. (2018).

[63]

Jiaxuan You, Zhitao Ying, and Jure Leskovec. 2020. Design space for graph neural networks. NeurIPS 33 (2020).

[64]

Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. 2019. Understanding and robustifying differentiable architecture search. arXiv preprint arXiv:1909.09656 (2019).

[65]

Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. 2018. Scalable instance reconstruction in knowledge bases via relatedness affiliated embedding. In WWW. 1185–1194.

[66]

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

Digital Library

[67]

Yongqi Zhang, Quanming Yao, and Lei Chen. 2020. Interstellar: Searching recurrent architecture for knowledge graph embedding. Advances in Neural Information Processing Systems 33 (2020), 10030–10040.

[68]

Yongqi Zhang, Quanming Yao, Wenyuan Dai, and Lei Chen. 2020. AutoSF: Searching Scoring Functions for Knowledge Graph Embedding. In ICDE. 433–444.

[69]

Ziwei Zhang, Xin Wang, and Wenwu Zhu. 2021. Automated Machine Learning on Graphs: A Survey. arXiv preprint arXiv:2103.00742 (2021).

[70]

Huan Zhao, Quanming Yao, and Weiwei Tu. 2021. Search to aggregate neighborhood for graph neural network. arXiv preprint arXiv:2104.06608 (2021).

[71]

Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. 2019. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv:1909.03184 (2019).

[72]

Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. 2021. Neural bellman-ford networks: A general graph neural network framework for link prediction. NeurIPS 34 (2021), 29476–29490.

Cited By

Li HDi SLi CChen LZhou X(2024)Fight Fire with Fire: Towards Robust Graph Neural Networks on Dynamic Graphs via Actively DefenseProceedings of the VLDB Endowment10.14778/3659437.365945717:8(2050-2063)Online publication date: 31-May-2024
https://dl.acm.org/doi/10.14778/3659437.3659457
Liu YDi SChen LZhou XLin FSerra ESpezzano F(2024)A Universal and Interpretable Method for Enhancing Stock Price PredictionProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679731(1533-1543)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679731
WANG ZDI SCHEN LZHOU X(2024)Search to Fine-Tune Pre-Trained Graph Neural Networks for Graph-Level Tasks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00219(2805-2819)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00219
Show More Cited By

Index Terms

Message Function Search for Knowledge Graph Embedding
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
  2. Machine learning
    1. Machine learning algorithms
2. Information systems
  1. World Wide Web
    1. Web searching and information discovery

Recommendations

Embedding based Link Prediction for Knowledge Graph Completion
CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge Management

Knowledge Graphs (KGs) have recently gained attention for representing knowledge about a particular domain. Since its advent, the Linked Open Data (LOD) cloud has constantly been growing containing many KGs about many different domains such as ...
Embedding-Based Entity Alignment of Cross-Lingual Temporal Knowledge Graphs
Abstract
Entity alignment aims to construct a complete knowledge graph (KG) by matching the same entities in multi-source KGs. Existing researches on entity alignment mainly focuses on static multi-relational data in knowledge graphs. However, the ...
Relation-based multi-type aware knowledge graph embedding
Abstract
Knowledge graph (KG) embedding projects the graph into a low-dimensional space and preserves the graph information. An essential part of a KG is the ontology, which always is organized as a taxonomy tree, depicting the type (or multiple types) of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 ACM.

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].

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

RIF Project
Guangdong Basic and Applied Basic Research Foundation
National Science Foundation of China
Hong Kong ITC ITF grant
National Key Research and Development Program of China Grant
Theme-based project
AOE Project
Hong Kong RGC GRF Project

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
435
Total Downloads

Downloads (Last 12 months)190
Downloads (Last 6 weeks)14

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li HDi SLi CChen LZhou X(2024)Fight Fire with Fire: Towards Robust Graph Neural Networks on Dynamic Graphs via Actively DefenseProceedings of the VLDB Endowment10.14778/3659437.365945717:8(2050-2063)Online publication date: 31-May-2024
https://dl.acm.org/doi/10.14778/3659437.3659457
Liu YDi SChen LZhou XLin FSerra ESpezzano F(2024)A Universal and Interpretable Method for Enhancing Stock Price PredictionProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679731(1533-1543)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679731
WANG ZDI SCHEN LZHOU X(2024)Search to Fine-Tune Pre-Trained Graph Neural Networks for Graph-Level Tasks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00219(2805-2819)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00219
LIU HDI SLI HLI SCHEN LZHOU X(2024)Effective Data Selection and Replay for Unsupervised Continual Learning2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00119(1449-1463)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00119
Li RDi SChen LZhou X(2024)GradGCL: Gradient Graph Contrastive Learning2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00095(1171-1184)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00095
Li HDi SChen LZhou X(2024) E 2 GCL: Efficient and Expressive Contrastive Learning on Graph Neural Networks 2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00071(859-873)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00071
Wang ZDi SChen LSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)A Message Passing Neural Network Space for Better Capturing Data-dependent Receptive FieldsProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599243(2489-2501)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599243

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents