Knowledge graph completion

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 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, ?) 2303.13948 §5.3. Human supervision is named as the gold-standard way to check the added facts 2303.13948 §5.3. One large benchmark for the task is WikiKG90M, with about 87 million entities 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 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 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% 2303.13948 tab. 3. Card: Knowledge Graphs: Opportunities and Challenges.

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% 2303.13948 tab. 3. The survey names TransH and TransR as extensions but does not give their distance or loss functions 2303.13948 §5.1.2. Same card as above.

Neural network-based

SME, ConvKB and R-GCN score triples with small neural models 2303.13948 §5.1.3. Reported Hits@10: SME 41.3% on FB15K, R-GCN 84.2% on FB15K, ConvKB 52.5% on WN18RR 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 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 1911.06962 §1 §4.1. Training uses a margin ranking loss with one uniformly corrupted negative per positive 1911.06962 §3.2. Inductive runs use 3 hops and 3 GNN layers, 32-dimensional states, and 5 averaged runs 1911.06962 §4.1. Card: Inductive Relation Prediction by Subgraph Reasoning.

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 1911.06962 tab. 1. Its Hits@10 is best in 10 of 12 columns 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 1911.06962 §4.2 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 2210.09338 §2.3. The main model scores edges with DistMult; an ablation on the QA benchmarks also tries TransE and RotatE 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 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 2210.09338 tab. 1. Card: Deep Bidirectional Language-Knowledge Graph Pretraining.

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 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 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 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 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 2103.09430 §2.2. The ranking of candidates by training frequency alone reaches 0.75 validation MRR 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 2103.09430 app. C. The text reports 0.1833 MRR for ComplEx-Concat on v2 2103.09430 §3. Card: OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs.

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 2303.13948 §5.1.4. The constraints below come from the cards.

Implementation sketch

The survey gives no code and no training details. The sketch below shows only the completion loop from 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 1911.06962 §3.1.

# 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 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 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 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 2303.13948 §5.1.4. GraIL uses no entity features and is reported best on its inductive splits 1911.06962 tab. 1 tab. 2, but it is not the strongest transductive model alone and its transductive ensembles give small gains 1911.06962 §4.2.
• Datasets and metrics. The survey's top FB15K Hits@10 figure, QuatE at 90% 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 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 2303.13948 §5.1.4. Its own table compares these numbers across FB15K, WN18, WN18RR and WN11, and mixes Hits@10 with classification accuracy 2303.13948 tab. 3.
• Hit@3 against Hits@10. DRAGON's ConceptNet figures use Hit@3 and a model that also reads text 2210.09338 app. C tab. 9. The survey's table and GraIL's tables use Hits@10 on other datasets 2303.13948 tab. 3 1911.06962 §4.1. None of these numbers is comparable to another.
• Sampled negatives and metrics. GraIL reports Hits@10 against 50 sampled negatives 1911.06962 §4.1. OGB-LSC reports MRR against 1,000 sampled tails, with no credit beyond rank 10 2103.09430 §2.2. The survey's table reports Hits@10 under filtered link prediction 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 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: 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: 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: 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: 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.