Knowledge graph embedding

{{Short description|Dimensionality reduction of graph-based semantic data objects [machine learning task]}} thumb|Embedding of a knowledge graph. The vector representation of the entities and relations can be used for different machine learning applications. In representation learning, '''knowledge graph embedding''' ('''KGE'''), also called '''knowledge representation learning''' ('''KRL'''), or '''multi-relation learning''',<ref name=":0">{{Cite journal|last1=Ji|first1=Shaoxiong|last2=Pan|first2=Shirui|last3=Cambria|first3=Erik|last4=Marttinen|first4=Pekka|last5=Yu|first5=Philip S.|date=2021|title=A Survey on Knowledge Graphs: Representation, Acquisition, and Applications|journal=IEEE Transactions on Neural Networks and Learning Systems|volume=PP|issue=2 |pages=494–514|doi=10.1109/TNNLS.2021.3070843|pmid=33900922|arxiv=2002.00388|hdl=10072/416709 |s2cid=211010433|issn=2162-237X}}</ref> is a machine learning task of learning a low-dimensional representation of a knowledge graph's entities and relations while preserving their semantic meaning.<ref name=":0" /><ref>{{Cite journal|last1=Mohamed|first1=Sameh K|last2=Nováček|first2=Vít|last3=Nounu|first3=Aayah|date=2019-08-01|editor-last=Cowen|editor-first=Lenore|title=Discovering Protein Drug Targets Using Knowledge Graph Embeddings|url=https://academic.oup.com/bioinformatics/advance-article/doi/10.1093/bioinformatics/btz600/5542390|journal=Bioinformatics|volume=36|issue=2|language=en|pages=603–610|doi=10.1093/bioinformatics/btz600|pmid=31368482|issn=1367-4803|hdl=10379/15375|hdl-access=free}}</ref><ref name=":2">{{cite arXiv|last1=Lin|first1=Yankai|last2=Han|first2=Xu|last3=Xie|first3=Ruobing|last4=Liu|first4=Zhiyuan|last5=Sun|first5=Maosong|date=2018-12-28|title=Knowledge Representation Learning: A Quantitative Review|class=cs.CL|eprint=1812.10901}}</ref> Leveraging their embedded representation, knowledge graphs can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction.<ref name=":0" /><ref name=":32">{{Cite journal|last1=Abu-Salih|first1=Bilal|last2=Al-Tawil|first2=Marwan|last3=Aljarah|first3=Ibrahim|last4=Faris|first4=Hossam|last5=Wongthongtham|first5=Pornpit|last6=Chan|first6=Kit Yan|last7=Beheshti|first7=Amin|date=2021-05-12|title=Relational Learning Analysis of Social Politics using Knowledge Graph Embedding|url=https://doi.org/10.1007/s10618-021-00760-w|journal=Data Mining and Knowledge Discovery|volume=35|issue=4|pages=1497–1536|language=en|doi=10.1007/s10618-021-00760-w|arxiv=2006.01626|s2cid=219179556|issn=1573-756X}}</ref>

== Definition == A knowledge graph <math>\mathcal{G} = \{E, R, F\}</math> is a collection of entities <math>E </math>, relations <math>R</math>, and facts <math>F</math>.<ref name=":1">{{Cite journal|last1=Rossi|first1=Andrea|last2=Barbosa|first2=Denilson|last3=Firmani|first3=Donatella|last4=Matinata|first4=Antonio|last5=Merialdo|first5=Paolo|date=2020|title=Knowledge Graph Embedding for Link Prediction: A Comparative Analysis|url=https://dl.acm.org/doi/10.1145/3424672|journal=ACM Transactions on Knowledge Discovery from Data|language=en|volume=15|issue=2|pages=1–49|doi=10.1145/3424672|arxiv=2002.00819|hdl=11573/1638610 |s2cid=211011226|issn=1556-4681}}</ref> A ''fact'' is a triple <math>(h, r, t) \in F</math> that denotes a link <math>r \in R</math> between the head <math>h \in E</math> and the tail <math>t \in E</math> of the triple. Another notation that is often used in the literature to represent a triple (or fact) is <math>\langle \text{head}, \text{relation}, \text{tail} \rangle</math>. This notation is called the Resource Description Framework (RDF).<ref name=":0" /><ref name=":1" /> A knowledge graph represents the knowledge related to a specific domain; leveraging this structured representation, it is possible to infer a piece of new knowledge from it after some refinement steps.<ref name=":27">{{Cite journal|last=Paulheim|first=Heiko|date=2016-12-06|editor-last=Cimiano|editor-first=Philipp|title=Knowledge graph refinement: A survey of approaches and evaluation methods|url=https://www.medra.org/servlet/aliasResolver?alias=iospress&doi=10.3233/SW-160218|journal=Semantic Web|volume=8|issue=3|pages=489–508|doi=10.3233/SW-160218|s2cid=13151033 |url-access=subscription}}</ref> However, nowadays, people have to deal with the sparsity of data and the computational inefficiency to use them in a real-world application.<ref name=":2" /><ref name=":3">{{Cite journal|last1=Dai|first1=Yuanfei|last2=Wang|first2=Shiping|last3=Xiong|first3=Neal N.|last4=Guo|first4=Wenzhong|date=May 2020|title=A Survey on Knowledge Graph Embedding: Approaches, Applications and Benchmarks|journal=Electronics|language=en|volume=9|issue=5|pages=750|doi=10.3390/electronics9050750|doi-access=free}}</ref>

The embedding of a knowledge graph is a function that translates each entity and each relation into a vector of a given dimension <math>d</math>, called embedding dimension.<ref name=":3" /> It is even possible to embed the entities and relations with different dimensions.<ref name=":3" /> The embedding vectors can then be used for other tasks.

A knowledge graph embedding is characterized by four aspects:<ref name=":0" />

# Representation space: The low-dimensional space in which the entities and relations are represented.<ref name=":0" /> #Scoring function: A measure of the goodness of a triple-embedded representation.<ref name=":0" /> # Encoding models: The modality in which the embedded representation of the entities and relations interact with each other.<ref name=":0" /> # Additional information: Any additional information coming from the knowledge graph that can enrich the embedded representation.<ref name=":0" /> Usually, an ''ad hoc'' scoring function is integrated into the general scoring function for each additional piece of information.<ref name=":1" /><ref name=":0" /><ref>{{Cite book|last1=Guo|first1=Shu|last2=Wang|first2=Quan|last3=Wang|first3=Bin|last4=Wang|first4=Lihong|last5=Guo|first5=Li|title=Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) |chapter=Semantically Smooth Knowledge Graph Embedding |date=2015|chapter-url=http://aclweb.org/anthology/P15-1009 |language=en |publisher=Association for Computational Linguistics|pages=84–94|doi=10.3115/v1/P15-1009|s2cid=205692|doi-access=free}}</ref>

== Embedding procedure == All algorithms for creating a knowledge graph embedding follow the same approach.<ref name=":3" /> First, the embedding vectors are initialized to random values.<ref name=":3" /> Then, they are iteratively optimized using a training set of triples. In each iteration, a batch of size <math>b</math> triples is sampled from the training set, and a triple from it is sampled and corrupted{{emdash}}i.e., a triple that does not represent a true fact in the knowledge graph.<ref name=":3" /> The corruption of a triple involves substituting the head or the tail (or both) of the triple with another entity that makes the fact false.<ref name=":3" /> The original triple and the corrupted triple are added in the training batch, and then the embeddings are updated, optimizing a scoring function.<ref name=":1" /><ref name=":3" /> Iteration stops when a stop condition is reached.<ref name=":3" /> Usually, the stop condition depends on the overfitting of the training set.<ref name=":3" /> At the end, the learned embeddings should have extracted semantic meaning from the training triples and should correctly predict unseen true facts in the knowledge graph.<ref name=":1" />

=== Pseudocode === The following is the pseudocode for the general embedding procedure.<ref name=":9" /><ref name=":3" /> '''algorithm''' Compute entity and relation embeddings '''input:''' The training set <math>S = \{(h, r, t)\}</math>, entity set <math>E </math>, relation set <math>R</math>, embedding dimension <math>k</math> '''output:''' Entity and relation embeddings '''''initialization:''''' ''the entities'' '''<math>e</math>''' ''and relations'' '''<math>r</math>''' ''embeddings (vectors) are randomly initialized'' '''while''' stop condition '''do''' <math>S_{batch} \leftarrow sample(S, b)</math> // Sample a batch from the training set '''for each''' <math>(h, r, t)</math> '''in''' <math>S_{batch}</math> '''do''' <math>(h', r, t') \leftarrow sample(S')</math> // Sample a corrupted fact <math>T_{batch} \leftarrow T_{batch} \cup \{((h,r, t), (h', r, t')) \}</math> '''end for''' Update embeddings by minimizing the loss function '''end while'''

== Performance indicators == These indexes are often used to measure the embedding quality of a model. The simplicity of the indexes makes them very suitable for evaluating the performance of an embedding algorithm even on a large scale.<ref name=":31">{{Cite journal|last1=Chen|first1=Zhe|last2=Wang|first2=Yuehan|last3=Zhao|first3=Bin|last4=Cheng|first4=Jing|last5=Zhao|first5=Xin|last6=Duan|first6=Zongtao|date=2020|title=Knowledge Graph Completion: A Review|journal=IEEE Access|volume=8|pages=192435–192456|doi=10.1109/ACCESS.2020.3030076|s2cid=226230006|issn=2169-3536|doi-access=free|bibcode=2020IEEEA...8s2435C }}</ref> Given <chem>Q</chem> as the set of all ranked predictions of a model, it is possible to define three different performance indexes: Hits@K, MR, and MRR.<ref name=":31" />

=== Hits@K === Hits@K or in short, H@K, is a performance index that measures the probability to find the correct prediction in the first top K model predictions.<ref name=":31" /> Usually, it is used <math>k=10</math>.<ref name=":31" /> Hits@K reflects the accuracy of an embedding model to predict the relation between two given triples correctly.<ref name=":31" />

Hits@K<math>= \frac{|\{q \in Q : q < k \}|}{|Q|} \in [0, 1]</math>

Larger values mean better predictive performances.<ref name=":31" />

=== Mean rank (MR) === Mean rank is the average ranking position of the items predicted by the model among all the possible items.<ref name=":31" />

The smaller the value, the better the model.<ref name=":31" />

=== Mean reciprocal rank (MRR) === Mean reciprocal rank measures the number of triples predicted correctly.<ref name=":31" /> If the first predicted triple is correct, then 1 is added, if the second is correct <math>\frac{1}{2}</math> is summed, and so on.<ref name=":31" />

Mean reciprocal rank is generally used to quantify the effect of search algorithms.<ref name=":31" />

The larger the index, the better the model.<ref name=":31" />

== Applications == === Machine learning tasks === Knowledge graph completion (KGC) is a collection of techniques to infer knowledge from an embedded knowledge graph representation.<ref name=":35">{{cite arXiv|last1=Cai|first1=Hongyun|last2=Zheng|first2=Vincent W.|last3=Chang|first3=Kevin Chen-Chuan|date=2018-02-02|title=A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications|class=cs.AI|eprint=1709.07604}}</ref> In particular, this technique completes a triple inferring the missing entity or relation.<ref name=":35" /> The corresponding sub-tasks are named link or entity prediction (i.e., guessing an entity from the embedding given the other entity of the triple and the relation), and relation prediction (i.e., forecasting the most plausible relation that connects two entities).<ref name=":35" />

Triple Classification is a binary classification problem.<ref name=":0" /> Given a triple, the trained model evaluates the plausibility of the triple using the embedding to determine if a triple is true or false.<ref name=":35" /> The decision is made with the model score function and a given threshold.<ref name=":35" /> Clustering is another application that leverages the embedded representation of a sparse knowledge graph to condense the representation of similar semantic entities close in a 2D space.<ref name=":32" />

=== Real world applications === The use of knowledge graph embedding is increasingly pervasive in many applications. In the case of recommender systems, the use of knowledge graph embedding can overcome the limitations of the usual reinforcement learning,<ref name=":33">{{cite arXiv|last1=Zhou|first1=Sijin|last2=Dai|first2=Xinyi|last3=Chen|first3=Haokun|last4=Zhang|first4=Weinan|last5=Ren|first5=Kan|last6=Tang|first6=Ruiming|last7=He|first7=Xiuqiang|last8=Yu|first8=Yong|date=2020-06-18|title=Interactive Recommender System via Knowledge Graph-enhanced Reinforcement Learning|class=cs.IR|eprint=2006.10389}}</ref><ref>{{Cite book|last1=Liu|first1=Chan|last2=Li|first2=Lun|last3=Yao|first3=Xiaolu|last4=Tang|first4=Lin|title=2019 IEEE International Conference on Computer Science and Educational Informatization (CSEI) |chapter=A Survey of Recommendation Algorithms Based on Knowledge Graph Embedding |date=August 2019|pages=168–171|doi=10.1109/CSEI47661.2019.8938875|isbn=978-1-7281-2308-0|s2cid=209459928}}</ref> as well as limitations of the conventional collaborative filtering method.<ref name="EBBK25">{{Cite web|author = Eytan, L., Bogina, V., Ben-Gal, I., & Koenigstein, N. (2025)|title = KPAR: Knowledge-aware path-based attentive recommender with interpretability |url = https://www.iradbengal.sites.tau.ac.il/_files/ugd/901879_c776b98683fb467c839173d952810e95.pdf |publisher = ACM Transactions on Recommender Systems, 3(3), 1-23.}}</ref> Training this kind of recommender system requires a huge amount of information from the users; however, knowledge graph techniques can address this issue by using a graph already constructed over a prior knowledge of the item correlation and using the embedding to infer from it the recommendation.<ref name=":33" /> Drug repurposing is the use of an already approved drug, but for a therapeutic purpose different from the one for which it was initially designed.<ref name=":34">{{Cite journal|last1=Sosa|first1=Daniel N.|last2=Derry|first2=Alexander|last3=Guo|first3=Margaret|last4=Wei|first4=Eric|last5=Brinton|first5=Connor|last6=Altman|first6=Russ B.|date=2020|title=A Literature-Based Knowledge Graph Embedding Method for Identifying Drug Repurposing Opportunities in Rare Diseases|journal=Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing|volume=25|pages=463–474|issn=2335-6936|pmc=6937428|pmid=31797619}}</ref> It is possible to use the task of link prediction to infer a new connection between an already existing drug and a disease by using a biomedical knowledge graph built leveraging the availability of massive literature and biomedical databases.<ref name=":34" /> Knowledge graph embedding can also be used in the domain of social politics.<ref name=":32" />

== Models == thumb|Publication timeline of some knowledge graph embedding models. In red the tensor decomposition models, in blue the geometric models, and in green the deep learning models. RESCAL<ref name=":22" /> (2011) was the first modern KGE approach. In<ref>{{Cite book|last1=Nickel|first1=Maximilian|last2=Tresp|first2=Volker|last3=Kriegel|first3=Hans-Peter|title=Proceedings of the 21st international conference on World Wide Web |chapter=Factorizing YAGO |date=2012-04-16 |url=https://doi.org/10.1145/2187836.2187874 |publisher=Association for Computing Machinery|pages=271–280|doi=10.1145/2187836.2187874|isbn=978-1-4503-1229-5|s2cid=6348464}}</ref> it was applied to the YAGO knowledge graph. This was the first application of KGE to a large scale knowledge graph.|535x535px Given a collection of triples (or facts) <math>\mathcal{F} = \{ \langle \text{head}, \text{relation}, \text{tail} \rangle \}</math>, the knowledge graph embedding model produces, for each entity and relation present in the knowledge graph a continuous vector representation.<ref name=":3" /> <math>(h, r, t)</math> is the corresponding embedding of a triple with <math>h,t \in {\rm I\!R}^{d}</math> and <math>r \in {\rm I\!R}^{k}</math> , where <math>d</math> is the embedding dimension for the entities, and <math>k</math> for the relations.<ref name=":3" /> The score function of a given model is denoted by <math>\mathcal{f}_{r}(h, t) </math> and measures the distance of the embedding of the head from the embedding of tail given the embedding of the relation. In other words, it quantifies the plausibility of the embedded representation of a given fact.<ref name=":1" />

Rossi et al. propose a taxonomy of the embedding models and identifies three main families of models: tensor decomposition models, geometric models, and deep learning models.<ref name=":1" />

=== Tensor decomposition model === The tensor decomposition is a family of knowledge graph embedding models that use a multi-dimensional matrix to represent a knowledge graph,<ref name=":0" /><ref name=":1" /><ref name=":25" /> that is partially knowable due to gaps of the graph describing a particular domain thoroughly.<ref name=":1" /> In particular, these models use a third-order (3D) tensor, which is then factorized into low-dimensional vectors that are the embeddings.<ref name=":1" /><ref name=":25" /> A third-order tensor is suitable for representing a knowledge graph because it records only the existence or absence of a relation between entities,<ref name=":25" /> and so is simple, and there is no need to know ''a priori'' the network structure,<ref name=":22">{{Cite book|last1=Nickel|first1=Maximilian|last2=Tresp|first2=Volker|last3=Kriegel|first3=Hans-Peter|chapter=A three-way model for collective learning on multi-relational data |date=2011-06-28 |chapter-url=https://dl.acm.org/doi/10.5555/3104482.3104584 |title=ICML'11: Proceedings of the 28th International Conference on International Conference on Machine Learning|publisher=Omnipress|pages=809–816|doi=|isbn=978-1-4503-0619-5}}</ref> making this class of embedding models light, and easy to train even if they suffer from high-dimensionality and sparsity of data.<ref name=":1" /><ref name=":25" />

==== Bilinear models ==== This family of models uses a linear equation to embed the connection between the entities through a relation.<ref name=":0" /> In particular, the embedded representation of the relations is a bidimensional matrix.<ref name=":1" /> These models, during the embedding procedure, only use the single facts to compute the embedded representation and ignore the other associations to the same entity or relation.<ref name=":4">{{Cite journal|last1=Wang|first1=Meihong|last2=Qiu|first2=Linling|last3=Wang|first3=Xiaoli|date=2021-03-16|title=A Survey on Knowledge Graph Embeddings for Link Prediction|journal=Symmetry|language=en|volume=13|issue=3|pages=485|doi=10.3390/sym13030485|bibcode=2021Symm...13..485W|issn=2073-8994|doi-access=free}}</ref> * DistMult<ref name=":11">{{cite arXiv|last1=Yang|first1=Bishan|last2=Yih|first2=Wen-tau|last3=He|first3=Xiaodong|last4=Gao|first4=Jianfeng|last5=Deng|first5=Li|date=2015-08-29|title=Embedding Entities and Relations for Learning and Inference in Knowledge Bases|class=cs.CL|eprint=1412.6575}}</ref>''':''' Since the embedding matrix of the relation is a diagonal matrix,<ref name=":1" /> the scoring function can not distinguish asymmetric facts.<ref name=":1" /><ref name=":4" /> * ComplEx<ref name=":5">{{cite arXiv|last1=Trouillon|first1=Théo|last2=Welbl|first2=Johannes|last3=Riedel|first3=Sebastian|last4=Gaussier|first4=Éric|last5=Bouchard|first5=Guillaume|date=2016-06-20|title=Complex Embeddings for Simple Link Prediction|class=cs.AI|eprint=1606.06357}}</ref>''':''' As DistMult uses a diagonal matrix to represent the relations embedding but adds a representation in the complex vector space and the hermitian product, it can distinguish symmetric and asymmetric facts.<ref name=":1" /><ref name=":25">{{Cite journal|last1=Alshahrani|first1=Mona|last2=Thafar|first2=Maha A.|last3=Essack|first3=Magbubah|date=2021-02-18|title=Application and evaluation of knowledge graph embeddings in biomedical data|journal=PeerJ Computer Science|language=en|volume=7|article-number=e341|doi=10.7717/peerj-cs.341|issn=2376-5992|pmc=7959619|pmid=33816992 |doi-access=free }}</ref> This approach is scalable to a large knowledge graph in terms of time and space cost.<ref name=":5" /> * ANALOGY<ref name=":12">{{cite arXiv|last1=Liu|first1=Hanxiao|last2=Wu|first2=Yuexin|last3=Yang|first3=Yiming|date=2017-07-06|title=Analogical Inference for Multi-Relational Embeddings|class=cs.LG|eprint=1705.02426}}</ref>''':''' This model encodes in the embedding the analogical structure of the knowledge graph to simulate inductive reasoning.<ref name=":12" /><ref name=":1" /><ref name=":0" /> Using a differentiable objective function, ANALOGY has good theoretical generality and computational scalability.<ref name=":12" /> It is proven that the embedding produced by ANALOGY fully recovers the embedding of DistMult, ComplEx, and HolE.<ref name=":12" /> * SimplE<ref name=":13">{{cite arXiv|last1=Kazemi|first1=Seyed Mehran|last2=Poole|first2=David|date=2018-10-25|title=SimplE Embedding for Link Prediction in Knowledge Graphs|class=stat.ML|eprint=1802.04868}}</ref>''':''' This model is the improvement of canonical polyadic decomposition (CP), in which an embedding vector for the relation and two independent embedding vectors for each entity are learned, depending on whether it is a head or a tail in the knowledge graph fact.<ref name=":13" /> SimplE resolves the problem of independent learning of the two entity embeddings using an inverse relation and average the CP score of <math>(h, r, t)</math> and <math>(t, r^{-1}, h)</math>.<ref name=":3" /><ref name=":25" /> In this way, SimplE collects the relation between entities while they appear in the role of subject or object inside a fact, and it is able to embed asymmetric relations.<ref name=":1" />

==== Non-bilinear models ====

* HolE:<ref name=":14">{{cite arXiv|last1=Nickel|first1=Maximilian|last2=Rosasco|first2=Lorenzo|last3=Poggio|first3=Tomaso|date=2015-12-07|title=Holographic Embeddings of Knowledge Graphs|class=cs.AI|eprint=1510.04935}}</ref> HolE uses circular correlation to create an embedded representation of the knowledge graph,<ref name=":14" /> which can be seen as a compression of the matrix product, but is more computationally efficient and scalable while keeping the capabilities to express asymmetric relation since the circular correlation is not commutative.<ref name=":4" /> HolE links holographic and complex embeddings since, if used together with Fourier, can be seen as a special case of ComplEx.<ref name=":0" /> * TuckER:<ref name=":15">{{Cite book|last1=Balažević|first1=Ivana|last2=Allen|first2=Carl|last3=Hospedales|first3=Timothy M.|title=Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) |chapter=TuckER: Tensor Factorization for Knowledge Graph Completion |date=2019 |pages=5184–5193|doi=10.18653/v1/D19-1522|arxiv=1901.09590|s2cid=59316623}}</ref> TuckER sees the knowledge graph as a tensor that could be decomposed using the Tucker decomposition in a collection of vectors{{emdash}}i.e., the embeddings of entities and relations{{emdash}}with a shared core.<ref name=":15" /><ref name=":1" /> The weights of the core tensor are learned together with the embeddings and represent the level of interaction of the entries.<ref name=":26">{{cite journal|last1=Ali|first1=Mehdi|last2=Berrendorf|first2=Max|last3=Hoyt|first3=Charles Tapley|last4=Vermue|first4=Laurent|last5=Galkin|first5=Mikhail|last6=Sharifzadeh|first6=Sahand|last7=Fischer|first7=Asja|last8=Tresp|first8=Volker|last9=Lehmann|first9=Jens|title=Bringing Light into the Dark: A Large-scale Evaluation of Knowledge Graph Embedding Models under a Unified Framework|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|year=2021|volume=PP|issue=12 |pages=8825–8845 |doi=10.1109/TPAMI.2021.3124805|pmid=34735335|arxiv=2006.13365|s2cid=220041612}}</ref> Each entity and relation has its own embedding dimension, and the size of the core tensor is determined by the shape of the entities and relations that interact.<ref name=":1" /> The embedding of the subject and object of a fact are summed in the same way, making TuckER fully expressive, and other embedding models such as RESCAL, DistMult, ComplEx, and SimplE can be expressed as a special formulation of TuckER.<ref name=":15" /> * MEI:<ref name=":36">{{Cite book |last1=Tran |first1=Hung Nghiep |last2=Takasu |first2=Atsuhiro |title=Proceedings of the European Conference on Artificial Intelligence (ECAI 2020) |chapter=Multi-Partition Embedding Interaction with Block Term Format for Knowledge Graph Completion |date=2020 |chapter-url=https://ebooks.iospress.nl/doi/10.3233/FAIA200173 |pages=833–840 |series=Frontiers in Artificial Intelligence and Applications |volume=325|publisher=IOS Press |doi=10.3233/FAIA200173|arxiv=2006.16365 |s2cid=220265751 }}</ref> MEI introduces the multi-partition embedding interaction technique with the block term tensor format, which is a generalization of CP decomposition and Tucker decomposition. It divides the embedding vector into multiple partitions and learns the local interaction patterns from data instead of using fixed special patterns as in ComplEx or SimplE models. This enables MEI to achieve optimal efficiency—expressiveness trade-off, not just being fully expressive.<ref name=":36" /> Previous models such as TuckER, RESCAL, DistMult, ComplEx, and SimplE are suboptimal restricted special cases of MEI. * MEIM:<ref name=":37">{{Cite book |last1=Tran |first1=Hung-Nghiep |last2=Takasu |first2=Atsuhiro |title=Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence |chapter=MEIM: Multi-partition Embedding Interaction Beyond Block Term Format for Efficient and Expressive Link Prediction |date=2022-07-16 |url=https://www.ijcai.org/proceedings/2022/314 |language=en |volume=3 |pages=2262–2269 |doi=10.24963/ijcai.2022/314|isbn=978-1-956792-00-3 |s2cid=250635995 }}</ref> MEIM goes beyond the block term tensor format to introduce the independent core tensor for ensemble boosting effects and the soft orthogonality for max-rank relational mapping, in addition to multi-partition embedding interaction. MEIM generalizes several previous models such as MEI and its subsumed models, RotaE, and QuatE.<ref name=":37" /> MEIM improves expressiveness while still being highly efficient in practice, helping it achieve good results using fairly small model sizes.

=== Geometric models === The geometric space defined by this family of models encodes the relation as a geometric transformation between the head and tail of a fact.<ref name=":1" /> For this reason, to compute the embedding of the tail, it is necessary to apply a transformation <math>\tau</math> to the head embedding, and a distance function <math>\delta</math> is used to measure the goodness of the embedding or to score the reliability of a fact.<ref name=":1" />

<math>\mathcal{f}_{r}(h, t) = \delta(\tau(h, r), t) </math>

Geometric models are similar to the tensor decomposition model, but the main difference between the two is that they have to preserve the applicability of the transformation <math>\tau</math> in the geometric space in which it is defined.<ref name=":1" />

==== Pure translational models ==== This class of models is inspired by the idea of translation invariance introduced in word2vec.<ref name=":3" /> A pure translational model relies on the fact that the embedding vector of the entities are close to each other after applying a proper relational translation in the geometric space in which they are defined.<ref name=":4" /> In other words, given a fact, the embedding of the head plus the embedding of the relation should equal the embedding of the tail.<ref name=":1" /> The closeness of the entities embedding is given by some distance measure and quantifies the reliability of a fact.<ref name=":25" />thumb|TransE embedding model. The vector representation (embedding) of the head plus the vector representation of the relation should be equal to the vector representation of the tail entity.

* TransE<ref name=":9">{{Cite book|last1=Bordes|first1=Antoine|last2=Usunier|first2=Nicolas|last3=Garcia-Durán|first3=Alberto|last4=Weston|first4=Jason|last5=Yakhnenko|first5=Oksana|chapter=Translating embeddings for modeling multi-relational data |date=May 2013 |chapter-url=https://dl.acm.org/doi/10.5555/2999792.2999923 |title=NIPS'13: Proceedings of the 26th International Conference on Neural Information Processing Systems |volume=2 |publisher=Curran Associates Inc.|pages=2787–2795}}</ref>''':''' Uses a scoring function that forces the embeddings to satisfy a simple vector sum equation in each fact in which they appear: <math>h + r = t</math>.<ref name=":3" /> The embedding will be exact if each entity and relation appears in only one fact, and so in practice is poor at representing one-to-many, many-to-one, and asymmetric relations.<ref name=":1" /><ref name=":3" /> * TransH<ref name=":6">{{Cite book|last=Wang|first=Zhen|chapter=Knowledge Graph Embedding by Translating on Hyperplanes |title=Proceedings of the AAAI Conference on Artificial Intelligence |date=2014 |chapter-url=https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8531 |volume=28 |doi=10.1609/aaai.v28i1.8870 |s2cid=15027084 }}</ref>''':''' A modification of TransE for representing types of relations, by using a hyperplane as a geometric space.<ref name=":6" /> In TransH, the relation embedding is on a different hyperplane depending on the entities it interacts with.<ref name=":3" /> So, to compute, for example, the score function of a fact, the embedded representation of the head and tail need to be projected using a relational projection matrix on the correct hyperplane of the relation.<ref name=":0" /><ref name=":3" /> * TransR<ref name=":10">{{Cite book|last1=Lin|first1=Yankai|last2=Liu|first2=Zhiyuan|last3=Sun|first3=Maosong|last4=Liu|first4=Yang|last5=Zhu|first5=Xuan|title=Learning entity and relation embeddings for knowledge graph completion |date=2015-01-25 |url=https://dl.acm.org/doi/10.5555/2886521.2886624 |publisher=AAAI Press|pages=2181–2187|isbn=978-0-262-51129-2}}</ref>''':''' A modification of TransH that uses different spaces embedding entities versus relations,<ref name=":0" /><ref name=":4" /> thus separating the semantic spaces of entities and relations.<ref name=":3" /> TransR also uses a relational projection matrix to translate the embedding of the entities to the relation space.<ref name=":3" /> *TransD''':<ref name=":7">{{Cite book|last1=Ji|first1=Guoliang|last2=He|first2=Shizhu|last3=Xu|first3=Liheng|last4=Liu|first4=Kang|last5=Zhao|first5=Jun|title=Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) |chapter=Knowledge Graph Embedding via Dynamic Mapping Matrix |date=July 2015|chapter-url=https://www.aclweb.org/anthology/P15-1067 |publisher=Association for Computational Linguistics|pages=687–696|doi=10.3115/v1/P15-1067|s2cid=11202498}}</ref>''' In TransR, the head and the tail of a given fact could belong to two different types of entities. For example, in the fact<math>(\text{Obama}, \text{president of}, \text{USA})</math>, ''Obama'' is a person and ''USA'' is a country.<ref name=":7" /><ref name=":3" /> Matrix multiplication is an expensive procedure in TransR to compute the projection.<ref name=":3" /><ref name=":7" /> In this context, TransD uses two vectors for each entity-relation pair to compute a dynamic mapping that substitutes the projection matrix while reducing the dimensional complexity.<ref name=":0" /><ref name=":3" /><ref name=":7" /> The first vector is used to represent the semantic meaning of the entities and relations, the second to compute the mapping matrix.<ref name=":7" /> * TransA:<ref name=":8">{{cite arXiv|last1=Xiao|first1=Han|last2=Huang|first2=Minlie|last3=Hao|first3=Yu|last4=Zhu|first4=Xiaoyan|date=2015-09-27|title=TransA: An Adaptive Approach for Knowledge Graph Embedding|class=cs.CL|eprint=1509.05490}}</ref> All the translational models define a score function in their representation space, but they oversimplify this metric loss.<ref name=":8" /> Since the vector representation of the entities and relations is not perfect, a pure translation of <math>h + r</math> could be distant from <math>t</math>, and a spherical equipotential Euclidean distance makes it hard to distinguish which is the closest entity.<ref name=":8" /> TransA, instead, introduces an adaptive Mahalanobis distance to weights the embedding dimensions, together with elliptical surfaces to remove the ambiguity.<ref name=":0" /><ref name=":3" /><ref name=":8" />

==== Translational models with additional embeddings ==== It is possible to associate additional information to each element in the knowledge graph and their common representation facts.<ref name=":0" /> Each entity and relation can be enriched with text descriptions, weights, constraints, and others in order to improve the overall description of the domain with a knowledge graph.<ref name=":0" /> During the embedding of the knowledge graph, this information can be used to learn specialized embeddings for these characteristics together with the usual embedded representation of entities and relations, with the cost of learning a more significant number of vectors.<ref name=":1" /> * STransE:<ref name=":16">{{Cite book|last1=Nguyen|first1=Dat Quoc|last2=Sirts|first2=Kairit|last3=Qu|first3=Lizhen|last4=Johnson|first4=Mark|title=Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies |chapter=STransE: A novel embedding model of entities and relationships in knowledge bases |date=June 2016 |chapter-url=https://www.aclweb.org/anthology/N16-1054 |publisher=Association for Computational Linguistics|pages=460–466|doi=10.18653/v1/N16-1054|arxiv=1606.08140|s2cid=9884935}}</ref> This model is the result of the combination of TransE and of the structure embedding<ref name=":16" /> in such a way it is able to better represent the one-to-many, many-to-one, and many-to-many relations.<ref name=":1" /> To do so, the model involves two additional independent matrix <math>W_{r}^{h}</math> and <math>W_{r}^{t}</math> for each embedded relation <math>r</math> in the KG.<ref name=":16" /> Each additional matrix is used based on the fact the specific relation interact with the head or the tail of the fact.<ref name=":16" /> In other words, given a fact <math>(h, r, t)</math>, before applying the vector translation, the head <math>h</math> is multiplied by <math>W_{r}^{h}</math> and the tail is multiplied by <math>W_{r}^{t}</math>.<ref name=":3" /> * CrossE''''':<ref name=":17">{{Cite book|last1=Zhang|first1=Wen|last2=Paudel|first2=Bibek|last3=Zhang|first3=Wei|last4=Bernstein|first4=Abraham|last5=Chen|first5=Huajun|title=Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining |chapter=Interaction Embeddings for Prediction and Explanation in Knowledge Graphs |date=2019-01-30 |pages=96–104|doi=10.1145/3289600.3291014|arxiv=1903.04750|isbn=9781450359405|s2cid=59516071}}</ref> '''''Crossover interactions can be used for related information selection, and could be very useful for the embedding procedure.<ref name=":17" /> Crossover interactions provide two distinct contributions in the information selection: interactions from relations to entities and interactions from entities to relations.<ref name=":17" /> This means that a relation, e.g.'president_of' automatically selects the types of entities that are connecting the subject to the object of a fact.<ref name=":17" /> In a similar way, the entity of a fact inderectly determine which is inference path that has to be choose to predict the object of a related triple.<ref name=":17" /> CrossE, to do so, learns an additional interaction matrix <math>C</math>, uses the element-wise product to compute the interaction between <math>h</math> and <math>r</math>.<ref name=":1" /><ref name=":17" /> Even if, CrossE, does not rely on a neural network architecture, it is shown that this methodology can be encoded in such architecture.<ref name=":0" />

==== Roto-translational models ==== This family of models, in addition or in substitution of a translation they employ a rotation-like transformation.<ref name=":1" /> * TorusE:<ref name=":18">{{cite arXiv|last1=Ebisu|first1=Takuma|last2=Ichise|first2=Ryutaro|date=2017-11-15|title=TorusE: Knowledge Graph Embedding on a Lie Group|class=cs.AI|eprint=1711.05435}}</ref> The regularization term of TransE makes the entity embedding to build a spheric space, and consequently loses the translation properties of the geometric space.<ref name=":18" /> To address this problem, TorusE leverages the use of a compact Lie group that in this specific case is n-dimensional torus space, and avoid the use of regularization.<ref name=":0" /><ref name=":18" /> TorusE defines the distance functions to substitute the L1 and L2 norm of TransE.<ref name=":1" /> * RotatE:<ref name=":19">{{cite arXiv|last1=Sun|first1=Zhiqing|last2=Deng|first2=Zhi-Hong|last3=Nie|first3=Jian-Yun|last4=Tang|first4=Jian|date=2019-02-26|title=RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space|class=cs.LG|eprint=1902.10197}}</ref> RotatE is inspired by the Euler's identity and involves the use of Hadamard product to represent a relation <math>r</math> as a rotation from the head <math>h</math> to the tail <math>t </math> in the complex space.<ref name=":19" /> For each element of the triple, the complex part of the embedding describes a counterclockwise rotation respect to an axis, that can be describe with the Euler's identity, whereas the modulus of the relation vector is 1.<ref name=":19" /> It is shown that the model is capable of embedding symmetric, asymmetric, inversion, and composition relations from the knowledge graph.<ref name=":19" />

=== Deep learning models === This group of embedding models uses deep neural network to learn patterns from the knowledge graph that are the input data.<ref name=":1" /> These models have the generality to distinguish the type of entity and relation, temporal information, path information, underlay structured information,<ref name=":4" /> and resolve the limitations of distance-based and semantic-matching-based models in representing all the features of a knowledge graph.<ref name=":0" /> The use of deep learning for knowledge graph embedding has shown good predictive performance even if they are more expensive in the training phase, data-hungry, and often required a pre-trained embedding representation of knowledge graph coming from a different embedding model.<ref name=":0" /><ref name=":1" />

==== Convolutional neural networks ==== This family of models, instead of using fully connected layers, employs one or more convolutional layers that convolve the input data applying a low-dimensional filter capable of embedding complex structures with few parameters by learning nonlinear features.<ref name=":0" /><ref name=":1" /><ref name=":4" />

* ConvE:<ref name=":29">{{cite arXiv|last1=Dettmers|first1=Tim|last2=Minervini|first2=Pasquale|last3=Stenetorp|first3=Pontus|last4=Riedel|first4=Sebastian|date=2018-07-04|title=Convolutional 2D Knowledge Graph Embeddings|class=cs.LG|eprint=1707.01476}}</ref> ConvE is an embedding model that represents a good tradeoff expressiveness of deep learning models and computational expensiveness,<ref name=":25" /> in fact it is shown that it used 8x less parameters, when compared to DistMult.<ref name=":29"/> ConvE uses a one-dimensional <math>d</math>-sized embedding to represent the entities and relations of a knowledge graph.<ref name=":1" /><ref name=":29"/> To compute the score function of a triple, ConvE apply a simple procedure: first concatenes and merge the embeddings of the head of the triple and the relation in a single data <chem>[h; \mathcal{r}]</chem>, then this matrix is used as input for the 2D convolutional layer.<ref name=":1" /><ref name=":25" /> The result is then passed through a dense layer that apply a linear transformation parameterized by the matrix <math>\mathcal{W}</math> and at the end, with the inner product is linked to the tail triple.<ref name=":1" /><ref name=":4" /> ConvE is also particularly efficient in the evaluation procedure: using a 1-N scoring, the model matches, given a head and a relation, all the tails at the same time, saving a lot of evaluation time when compared to the 1-1 evaluation program of the other models.<ref name=":4" /> * ConvR:<ref name=":20">{{Cite book|last1=Jiang|first1=Xiaotian|last2=Wang|first2=Quan|last3=Wang|first3=Bin|title=Proceedings of the 2019 Conference of the North |chapter=Adaptive Convolution for Multi-Relational Learning |date=June 2019 |chapter-url=https://www.aclweb.org/anthology/N19-1103 |publisher=Association for Computational Linguistics|pages=978–987|doi=10.18653/v1/N19-1103|s2cid=174800352}}</ref> ConvR is an adaptive convolutional network aimed to deeply represent all the possible interactions between the entities and the relations.<ref name=":20" /> For this task, ConvR, computes convolutional filter for each relation, and, when required, applies these filters to the entity of interest to extract convoluted features.<ref name=":20" /> The procedure to compute the score of triple is the same as ConvE.<ref name=":1" /> * ConvKB:<ref name=":21">{{Cite book|last1=Nguyen|first1=Dai Quoc|last2=Nguyen|first2=Tu Dinh|last3=Nguyen|first3=Dat Quoc|last4=Phung|first4=Dinh|title=Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers) |chapter=A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network |date=2018 |pages=327–333|doi=10.18653/v1/N18-2053|arxiv=1712.02121|s2cid=3882054}}</ref> ConvKB, to compute score function of a given triple <math>(h, r, t)</math>, it produces an input <chem>[h; \mathcal{r}; t]</chem>of dimension <math>d \times 3</math> without reshaping and passes it to series of convolutional filter of size <math>1 \times 3</math>.<ref name=":21" /> This result feeds a dense layer with only one neuron that produces the final score.<ref name=":21" /> The single final neuron makes this architecture as a binary classifier in which the fact could be true or false.<ref name=":1" /> A difference with ConvE is that the dimensionality of the entities is not changed.<ref name=":25" />

==== Capsule neural networks ==== This family of models uses capsule neural networks to create a more stable representation that is able to recognize a feature in the input without losing spatial information.<ref name=":1" /> The network is composed of convolutional layers, but they are organized in capsules, and the overall result of a capsule is sent to a higher-capsule decided by a dynamic process routine.<ref name=":1" /> * CapsE:<ref name=":23">{{cite arXiv|last1=Nguyen|first1=Dai Quoc|last2=Vu|first2=Thanh|last3=Nguyen|first3=Tu Dinh|last4=Nguyen|first4=Dat Quoc|last5=Phung|first5=Dinh|date=2019-03-06|title=A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization|class=cs.CL|eprint=1808.04122}}</ref> CapsE implements a capsule network to model a fact <math>(h, r, t)</math>.<ref name=":23" /> As in ConvKB, each triple element is concatenated to build a matrix <chem>[h; \mathcal{r}; t]</chem>and is used to feed to a convolutional layer to extract the convolutional features.<ref name=":1" /><ref name=":23" /> These features are then redirected to a capsule to produce a continuous vector, more the vector is long, more the fact is true.<ref name=":23" />

==== Recurrent neural networks ==== This class of models leverages the use of recurrent neural network.<ref name=":1" /> The advantage of this architecture is to memorize a sequence of fact, rather than just elaborate single events.<ref name=":24" /> * RSN:<ref name=":24">{{cite arXiv|last1=Guo|first1=Lingbing|last2=Sun|first2=Zequn|last3=Hu|first3=Wei|date=2019-05-13|title=Learning to Exploit Long-term Relational Dependencies in Knowledge Graphs|class=cs.AI|eprint=1905.04914}}</ref> During the embedding procedure is commonly assumed that, similar entities has similar relations.<ref name=":24" /> In practice, this type of information is not leveraged, because the embedding is computed just on the undergoing fact rather than a history of facts.<ref name=":24" /> Recurrent skipping networks (RSN) uses a recurrent neural network to learn relational path using a random walk sampling.<ref name=":1" /><ref name=":24" />

== Model performance == The machine learning task for knowledge graph embedding that is more often used to evaluate the embedding accuracy of the models is the link prediction.<ref name=":0" /><ref name=":2" /><ref name=":1" /><ref name=":27" /><ref name=":3" /><ref name=":4" /> Rossi et al.<ref name=":1" /> produced an extensive benchmark of the models, but also other surveys produces similar results.<ref name=":2" /><ref name=":3" /><ref name=":4" /><ref name=":26" /> The benchmark involves five datasets FB15k,<ref name=":9" /> WN18,<ref name=":9" /> FB15k-237,<ref name=":28">{{Cite book|last1=Toutanova|first1=Kristina|last2=Chen|first2=Danqi|title=Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality |chapter=Observed versus latent features for knowledge base and text inference |date=July 2015 |chapter-url=https://www.aclweb.org/anthology/W15-4007 |publisher=Association for Computational Linguistics|pages=57–66|doi=10.18653/v1/W15-4007|s2cid=5378837|doi-access=free}}</ref> WN18RR,<ref name=":29"/> and YAGO3-10.<ref name=":30">{{Cite journal|last1=Mahdisoltani|first1=F.|last2=Biega|first2=J.|last3=Suchanek|first3=Fabian M.|date=2015|title=YAGO3: A Knowledge Base from Multilingual Wikipedias|journal=CIDR|s2cid=6611164}}</ref> More recently, it has been discussed that these datasets are far away from real-world applications, and other datasets should be integrated as a standard benchmark.<ref>{{cite arXiv|last1=Hu|first1=Weihua|last2=Fey|first2=Matthias|last3=Zitnik|first3=Marinka|last4=Dong|first4=Yuxiao|last5=Ren|first5=Hongyu|last6=Liu|first6=Bowen|last7=Catasta|first7=Michele|last8=Leskovec|first8=Jure|date=2021-02-24|title=Open Graph Benchmark: Datasets for Machine Learning on Graphs|class=cs.LG|eprint=2005.00687}}</ref>

{| class="wikitable" |+Table summary of the characteristics of the datasets used to benchmark the embedding models. !Dataset name !Number of different entities !Number of different relations !Number of triples |- |FB15k<ref name=":9" /> |14951 |1345 |584,113 |- |WN18<ref name=":9" /> |40943 |18 |151,442 |- |FB15k-237<ref name=":28" /> |14541 |237 |310,116 |- |WN18RR<ref name=":29" /> |40943 |11 |93,003 |- |YAGO3-10<ref name=":30" /> |123182 |37 |1,089,040 |} {| class="wikitable mw-collapsible" |+Table summary of the memory complexity and the link prediction accuracy of the knowledge graph embedding models according to Rossi et al.<ref name=":1" /> in terms of Hits@10, MR, and MRR. Best results on each metric for each dataset are in bold. !Model name !Memory complexity !FB15K (Hits@10) !FB15K (MR) !FB15K (MRR) !FB15K - 237 (Hits@10) !FB15K - 237 (MR) !FB15K - 237 (MRR) !WN18 (Hits@10) !WN18 (MR) !WN18 (MRR) !WN18RR (Hits@10) !WN18RR (MR) !WN18RR (MRR) !YAGO3-10 (Hits@10) !YAGO3-10 (MR) !YAGO3-10 (MRR) |- |DistMul<ref name=":11" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.863 |173 |0.784 |0.490 |199 |0.313 |0.946 |675 |0.824 |0.502 |5913 |0.433 |0.661 |1107 |0.501 |- |ComplEx<ref name=":5" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |'''0.905''' |'''34''' |'''0.848''' |0.529 |202 |0.349 |0.955 |3623 |0.949 |0.521 |4907 |0.458 |0.703 |1112 |0.576 |- |HolE<ref name=":14" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.867 |211 |0.800 |0.476 |186 |0.303 |0.949 |650 |0.938 |0.487 |8401 |0.432 |0.651 |6489 |0.502 |- |ANALOGY<ref name=":12" /> |<math>\mathcal{O}(N_{e}d+N_{r}k^{2})(d=k)</math> |0.837 |126 |0.726 |0.353 |476 |0.202 |0.944 |808 |0.934 |0.380 |9266 |0.366 |0.456 |2423 |0.283 |- |SimplE<ref name=":13" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.836 |138 |0.726 |0.343 |651 |0.179 |0.945 |759 |0.938 |0.426 |8764 |0.398 |0.631 |2849 |0.453 |- |TuckER<ref name=":15" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.888 |39 |0.788 |0.536 |162 |0.352 |0.958 |510 |'''0.951''' |0.514 |6239 |0.459 |0.680 |2417 |0.544 |- |MEI<ref name=":36" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> | | | |0.552 |145 |0.365 | | | |0.551 |3268 |0.481 |0.709 |756 |0.578 |- |MEIM<ref name=":37" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> | | | |'''0.557''' |'''137''' |'''0.369''' | | | |'''0.577''' |2434 |'''0.499''' |'''0.716''' |'''747''' |'''0.585''' |- |TransE<ref name=":9" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.847 |45 |0.628 |0.497 |209 |0.310 |0.948 |279 |0.646 |0.495 |3936 |0.206 |0.673 |1187 |0.501 |- |STransE<ref name=":16" /> |<math>\mathcal{O}(N_{e}d+N_{r}k^{2})(d=k)</math> |0.796 |69 |0.543 |0.495 |357 |0.315 |0.934 |208 |0.656 |0.422 |5172 |0.226 |0.073 |5797 |0.049 |- |CrossE<ref name=":17" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.862 |136 |0.702 |0.470 |227 |0.298 |0.950 |441 |0.834 |0.449 |5212 |0.405 |0.654 |3839 |0.446 |- |TorusE<ref name=":18" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.839 |143 |0.746 |0.447 |211 |0.281 |0.954 |525 |0.947 |0.535 |4873 |0.463 |0.474 |19455 |0.342 |- |RotatE<ref name=":19" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.881 |42 |0.791 |0.522 |178 |0.336 |'''0.960''' |274 |0.949 |0.573 |3318 |0.475 |0.570 |1827 |0.498 |- |ConvE<ref name=":29" /> |<math>\mathcal{O}(N_{e}d^{2}+N_{r}k^{2})</math> |0.849 |51 |0.688 |0.521 |281 |0.305 |0.956 |413 |0.945 |0.507 |4944 |0.427 |0.657 |2429 |0.488 |- |ConvKB<ref name=":21" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.408 |324 |0.211 |0.517 |309 |0.230 |0.948 |'''202''' |0.709 |0.525 |3429 |0.249 |0.604 |1683 |0.420 |- |ConvR<ref name=":20" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.885 |70 |0.773 |0.526 |251 |0.346 |0.958 |471 |0.950 |0.526 |5646 |0.467 |0.673 |2582 |0.527 |- |CapsE<ref name=":23" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.217 |610 |0.087 |0.356 |405 |0.160 |0.950 |233 |0.890 |0.559 |'''720''' |0.415 |0 |60676 |0.000 |- |RSN<ref name=":24" /> |<math>\mathcal{O}(N_{e}d+N_{r}k)(d=k)</math> |0.870 |51 |0.777 |0.444 |248 |0.280 |0.951 |346 |0.928 |0.483 |4210 |0.395 |0.664 |1339 |0.511 |}

== Libraries ==

* {{GitHub|https://github.com/uma-pi1/kge |KGE}} * {{GitHub|https://github.com/tranhungnghiep/MEI-KGE|MEI-KGE}} * {{GitHub|https://github.com/Sujit-O/pykg2vec |Pykg2vec}} * {{GitHub|https://github.com/awslabs/dgl-ke |DGL-KE}} * {{GitHub|https://github.com/pykeen/pykeen |PyKEEN}} * {{GitHub|https://github.com/torchkge-team/torchkge |TorchKGE}} * {{GitHub|https://github.com/Accenture/AmpliGraph |AmpliGraph}} * {{GitHub|https://github.com/thunlp/OpenKE |OpenKE}} * {{GitHub|https://github.com/mnick/scikit-kge |scikit-kge}} * {{GitHub|https://github.com/thunlp/Fast-TransX |Fast-TransX}} * {{GitHub|https://github.com/tranhungnghiep/MEIM-KGE|MEIM-KGE}} * {{GitHub|https://github.com/dice-group/dice-embeddings|DICEE}}

== References == <references />

== External links == {{Scholia|topic}} * [https://ogb.stanford.edu Open Graph Benchmark - Stanford] *[https://wordnet.princeton.edu/ WordNet - Princeton]

Category:Knowledge graphs Category:Machine learning Category:Graph algorithms Category:Information science