--- kind: concept slug: knowledge-graph-completion title: Knowledge graph completion summary: >- Predicts missing facts in a knowledge graph by scoring candidate triples, then adds the high-scoring ones. Embedding models are the common choice; their evidence is a 2023 survey's table that mixes datasets and metrics. GraIL scores from the local subgraph with no entity embeddings, so it handles unseen entities (author-reported wins on 12 inductive splits). Trade-off: a subgraph per candidate. tags: [knowledge-graphs, link-prediction, graph-learning] papers: ["1911.06962", "2210.09338", "2303.13948", "2103.09430"] related: [knowledge-graph-embedding, knowledge-graph-reasoning, graph-neural-network, relational-graph-convolution, language-model-pretraining, benchmark-validity] status: draft updated_at: 2026-10-24 --- ## Overview A knowledge graph stores facts as triples (head, relation, tail). Graphs are incomplete, so completion asks which missing triples are likely true. The survey lists completion as one of five technologies whose limits block further use of knowledge graphs, next to embedding, acquisition, fusion and reasoning [arxiv:2303.13948 §2.2]. The survey describes the usual procedure: train a model on the existing graph, use it to score candidate triples, and add the high-scoring candidates back to the graph. Two tasks are named: link prediction and entity prediction. Entity prediction ranks candidate tails for a partial triple such as (Tom, friendOf, ?) [arxiv:2303.13948 §5.3]. Human supervision is named as the gold-standard way to check the added facts [arxiv:2303.13948 §5.3]. One large benchmark for the task is WikiKG90M, with about 87 million entities [arxiv:2103.09430 §2.2]. ## Variants The survey does not split completion into method families. It reports results for embedding models on link prediction, grouped by the three embedding families it describes [arxiv:2303.13948 §5.1] [tab. 3]. Each family scores a triple differently. GraIL is a fourth kind: it scores a triple from the subgraph around its two entities instead of from entity vectors. DRAGON is a fifth case: a pretraining method that uses link prediction as one of its objectives. The WikiKG90M benchmark is a setting rather than a method family, and is covered last. ### Tensor factorization The graph is stored as a binary tensor with one slice per relation, and the model learns entity and relation vectors that factor it [arxiv:2303.13948 §5.1.1]. Reported Hits@10 on FB15K: RESCAL 44.1%, HolE 73.9%, ComplEx 84%, SimplE 83.8%, RotatE 88.4%, QuatE 90% [arxiv:2303.13948 tab. 3]. Card: [Knowledge Graphs: Opportunities and Challenges](/papers/2303.13948). ### Translation-based Head plus relation should land near the tail (h + r ≈ t) [arxiv:2303.13948 §5.1.2]. Reported Hits@10 on FB15K: TransE 47.1%, TransH 64.4%, TransR 68.7%, TransD 77.3%, TransG 88.2% [arxiv:2303.13948 tab. 3]. The survey names TransH and TransR as extensions but does not give their distance or loss functions [arxiv:2303.13948 §5.1.2]. Same card as above. ### Neural network-based SME, ConvKB and R-GCN score triples with small neural models [arxiv:2303.13948 §5.1.3]. Reported Hits@10: SME 41.3% on FB15K, R-GCN 84.2% on FB15K, ConvKB 52.5% on WN18RR [arxiv:2303.13948 tab. 3]. Same card as above. ### Subgraph scoring (inductive) GraIL predicts (u, r, v) from the subgraph that connects u and v. It uses no entity embeddings and no node features; each node is labelled only by its distances to u and to v, and a relation-aware GNN with edge attention scores the subgraph [arxiv:1911.06962 §3.1]. Because nothing is tied to an entity's ID, a new entity can be scored without retraining, provided its relations occur in the training graph [arxiv:1911.06962 §1] [§4.1]. Training uses a margin ranking loss with one uniformly corrupted negative per positive [arxiv:1911.06962 §3.2]. Inductive runs use 3 hops and 3 GNN layers, 32-dimensional states, and 5 averaged runs [arxiv:1911.06962 §4.1]. Card: [Inductive Relation Prediction by Subgraph Reasoning](/papers/1911.06962). On its inductive splits (WN18RR, FB15k-237 and NELL-995, four versions each), GraIL has the best AUC-PR in all 12 columns against RuleN, Neural-LP and DRUM [arxiv:1911.06962 tab. 1]. Its Hits@10 is best in 10 of 12 columns [arxiv:1911.06962 tab. 2]. These are author-reported numbers on the authors' own splits. On the transductive benchmarks GraIL is not the strongest model alone. Averaged over the three ensembles it forms with each embedding model, the gains are 1.5% on WN18RR and 0.62% on NELL-995, and the paper reports none as significant on FB15k-237; it gives no significance test [arxiv:1911.06962 §4.2] [arxiv:1911.06962 tab. 3] [tab. 4] [tab. 5]. ### Joint text and graph pretraining DRAGON does not rank candidate triples as its main output. It pretrains one encoder on a text segment and a local subgraph of the knowledge graph. Its two self-supervised losses are masked language modeling and link prediction on held-out edges, summed with equal weight [arxiv:2210.09338 §2.3]. The main model scores edges with DistMult; an ablation on the QA benchmarks also tries TransE and RotatE [arxiv:2210.09338 tab. 5]. Its one completion-style number is ConceptNet link prediction, Hit@3 of 78.1 against 61.3 for DistMult alone. DRAGON also uses retrieved text for that number [arxiv:2210.09338 app. C] [tab. 9]. Its main results are multiple-choice QA: 76.0 on CommonsenseQA against 68.7 for a continued-pretrained RoBERTa-Large [arxiv:2210.09338 tab. 1]. Card: [Deep Bidirectional Language-Knowledge Graph Pretraining](/papers/2210.09338). ### Large-scale ranking with text encoders (WikiKG90M) The OGB-LSC link task is completion on WikiKG90M, a Wikidata snapshot of 87,143,637 entities and 504,220,369 triplets in v1 [arxiv:2103.09430 §2.2] [tab. 1]. Each entity and relation has RoBERTa features built from its title and description. The paper pairs TransE and ComplEx decoders with three encoders: shallow per-entity embeddings, an MLP over the text features, and the concatenation of both [arxiv:2103.09430 §2.2]. Under the v1 protocol, the concatenated ComplEx model has the highest single-model test MRR in the table, 0.8637. Text alone gives 0.7186 and shallow embeddings give 0.5883 [arxiv:2103.09430 tab. 5]. The shallow and concatenated rows are listed at 17.4 billion parameters, and the text-only rows at 0.3 million [arxiv:2103.09430 tab. 5]. Scoring is sampled. For each test triplet the tail is replaced by 1,000 tails that do not occur in the graph. The model returns its top 10 of the 1,001 candidates, and MRR gives no credit beyond rank 10 [arxiv:2103.09430 §2.2]. The ranking of candidates by training frequency alone reaches 0.75 validation MRR [arxiv:2103.09430 §2.2], which is a reference point under this protocol. These numbers are not directly comparable to the Hits@10 figures above. The v2 revision removes the candidate list. A model must rank about 90 million entities, and the baselines use the 20,000 most frequent tails per relation as candidates [arxiv:2103.09430 app. C]. The text reports 0.1833 MRR for ComplEx-Concat on v2 [arxiv:2103.09430 §3]. Card: [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](/papers/2103.09430). ## When to use which The survey gives no criteria for choosing a completion model, and its results table does not support a ranking. Rows compare numbers from different datasets and metrics, and the survey itself notes that methods which ignore extra information such as entity types and relation paths scored lower [arxiv:2303.13948 §5.1.4]. The constraints below come from the cards. | Situation | Use | Why | |---|---|---| | New entities appear at query time and retraining is not an option | Subgraph scoring (GraIL) | Its model has no per-entity parameters, so an unseen entity is scored from its neighbourhood [arxiv:1911.06962 §1] [§3.1] | | New relations appear at query time | Not stated for GraIL | Its inductive splits require every test relation to occur in training [arxiv:1911.06962 §4.1]; the survey gives no guidance | | Many candidates per query, tight latency | Measure first; GraIL cost is per candidate | Each candidate needs its own enclosing subgraph, and inference is dominated by shortest-path work on it [arxiv:1911.06962 §3.1] [§3.4] | | Extra information (types, relation paths) is available | Not stated by the survey | The survey ties weak results to methods that ignore it [arxiv:2303.13948 §5.1.4]; GraIL with TransE embeddings added (GraIL++) rises from 90.91 to 96.20 AUC-PR on WN18RR [arxiv:1911.06962 tab. 6] | | Graph is large | Do not start from the dense tensor view | A full binary tensor needs m² · n cells [arxiv:2303.13948 §5.1.1]; sparse storage is not discussed | | Need a comparable benchmark number | Re-run the models on one dataset and protocol | The survey's table mixes datasets and metrics [arxiv:2303.13948 tab. 3]; GraIL's own tables use other splits and sampled negatives [arxiv:1911.06962 §4.1] | | Added facts must be trusted | Plan for human review | The survey names human supervision as the gold standard [arxiv:2303.13948 §5.3] | | Texts about the entities are available and the target is a language task such as QA | Joint pretraining (DRAGON) if you can afford it | On CommonsenseQA, MLM plus link prediction gives 76.0, against 74.3 for MLM alone and 73.8 for link prediction alone [arxiv:2210.09338 tab. 5]. Pretraining took 7 days on eight A100 GPUs [arxiv:2210.09338 §3.1] | | Output must be generated text | Not DRAGON | The model is an encoder that scores answers; generation is named as future work [arxiv:2210.09338 §5] | | Each input must be linked to the graph at inference | Budget for entity linking and subgraph retrieval | Each example needs entity linking and retrieval of at most 200 nodes [arxiv:2210.09338 §3.1] [app. B.1]; fewer than 1% of inputs link no entity [app. B.2] | | Millions of entities, text on each entity, and memory is not the limit | Concatenate a text encoder with a shallow embedding (ComplEx-Concat in the paper) | Best single-model v1 MRR in the table, 0.8637, against 0.7186 for text alone and 0.5883 for shallow embeddings [arxiv:2103.09430 tab. 5]. The table lists 17.4 billion parameters for this row [tab. 5] | | Memory is tight and text is available | Text-only encoder with a decoder (ComplEx-RoBERTa) | 0.3 million parameters against 17.4 billion; v1 MRR 0.7186 [arxiv:2103.09430 tab. 5] | | Candidates are not supplied at test time (v2 setting) | Rank against a restricted candidate pool, as the baselines do | Baselines use the 20,000 most frequent tails per relation [arxiv:2103.09430 app. C]; the paper reports 0.1833 MRR for ComplEx-Concat [§3] and 0.1761 on test-dev [app. C] | | Need a number comparable to other WikiKG90M results | Use the same 1,000-tail sampled protocol | MRR is defined under that protocol [arxiv:2103.09430 §2.2]; the survey's Hits@10 is a different metric [arxiv:2303.13948 tab. 3] | ## Implementation sketch The survey gives no code and no training details. The sketch below shows only the completion loop from [arxiv:2303.13948 §5.3]. The scoring function is a placeholder for any family above. For GraIL, `model.score` is replaced by extracting the enclosing subgraph of (head, relation, candidate), labelling its nodes by distance to each end, and running the GNN [arxiv:1911.06962 §3.1]. ```pseudocode # Complete one partial triple (head, relation, ?) by ranking tails [arxiv:2303.13948 §5.3] def complete_tail(model, graph, head, relation, k): # score every entity as a candidate tail, with a trained model [arxiv:2303.13948 §5.3] scores = {t: model.score(head, relation, t) for t in graph.entities} # rank candidates; the top ones are the completion candidates [arxiv:2303.13948 §5.3] ranked = sorted(scores, key=scores.get, reverse=True) # proposals only; a human or other check decides what is added [arxiv:2303.13948 §5.3] return ranked[:k] ``` Hits@10 in [arxiv:2303.13948 tab. 3] is computed with filtered link prediction, per the table footnote. The survey does not define the filtering step, so check the original paper before comparing numbers. GraIL's Hits@10 instead ranks each positive against 50 sampled negatives per link [arxiv:1911.06962 §4.1], so its numbers depend on that sampler. For graphs at WikiKG90M scale, the loop above is too slow to score every entity for each query. The benchmark scores the true tail and 1,000 sampled tails, then keeps the top 10 [arxiv:2103.09430 §2.2]. ## Contradictions The papers' numbers are not comparable, and none of them resolves the difference. - **Extra information.** The survey says methods that ignore entity types and relation paths score lower [arxiv:2303.13948 §5.1.4]. GraIL uses no entity features and is reported best on its inductive splits [arxiv:1911.06962 tab. 1] [tab. 2], but it is not the strongest transductive model alone and its transductive ensembles give small gains [arxiv:1911.06962 §4.2]. - **Datasets and metrics.** The survey's top FB15K Hits@10 figure, QuatE at 90% [arxiv:2303.13948 tab. 3], is on FB15K. GraIL's results use WN18RR, FB15k-237 and NELL-995 splits, scored with AUC-PR and with Hits@10 under sampled negatives [arxiv:1911.06962 §4.1]. The survey does not list GraIL. - **Within the survey only:** it names QuatE (90%), RMNN (89.9%) and KBGAN (89.2%) as the strongest results [arxiv:2303.13948 §5.1.4]. Its own table compares these numbers across FB15K, WN18, WN18RR and WN11, and mixes Hits@10 with classification accuracy [arxiv:2303.13948 tab. 3]. - **Hit@3 against Hits@10.** DRAGON's ConceptNet figures use Hit@3 and a model that also reads text [arxiv:2210.09338 app. C] [tab. 9]. The survey's table and GraIL's tables use Hits@10 on other datasets [arxiv:2303.13948 tab. 3] [arxiv:1911.06962 §4.1]. None of these numbers is comparable to another. - **Sampled negatives and metrics.** GraIL reports Hits@10 against 50 sampled negatives [arxiv:1911.06962 §4.1]. OGB-LSC reports MRR against 1,000 sampled tails, with no credit beyond rank 10 [arxiv:2103.09430 §2.2]. The survey's table reports Hits@10 under filtered link prediction [arxiv:2303.13948 tab. 3]. These are three protocols with three metric definitions. - **Ensembles.** The KDD Cup winners reach 0.9727 test MRR on v1, but their scores are ensembles [arxiv:2103.09430 §2] [tab. 5]. Under the same protocol, the best single model in the table reaches 0.8637. - **WikiKG90Mv2 numbers.** The text gives 0.1833 for ComplEx-Concat, and the appendix gives 0.2048 on validation and 0.1761 on test-dev [arxiv:2103.09430 §3] [app. C]. The paper does not say which split 0.1833 refers to. ## Papers - [Knowledge Graphs: Opportunities and Challenges](/papers/2303.13948): a 2023 survey that defines triples and completion, lists embedding families with scoring functions, and tabulates literature link-prediction results. It runs no experiments. - [Inductive Relation Prediction by Subgraph Reasoning](/papers/1911.06962): GraIL, which scores triples from their enclosing subgraph with distance labels and a relation-aware GNN. It reports inductive wins on new splits and small transductive ensemble gains. - [Deep Bidirectional Language-Knowledge Graph Pretraining](/papers/2210.09338): DRAGON, an encoder pretrained on text and local graph jointly with masked language modeling and link prediction. Its evidence is QA accuracy, plus one ConceptNet link-prediction number. - [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](/papers/2103.09430): a benchmark paper whose link task is completion on WikiKG90M, scored by MRR under sampled negatives. It reports TransE and ComplEx baselines with shallow and text encoders. Its node and molecule tasks are not covered here.