Predicting Missing Links in Incomplete Knowledge Graphs

390 concepts331 papers1 proposal

Knowledge graphs (KGs) represent real-world facts as a network of entities (nodes) connected by directed, labeled relationships (edges). A typical fact is structured as a triplet: $(\text{head}, \text{relation}, \text{tail})$, or $(h, r, t)$—for example, $(\text{Paris}, \text{capital\_of}, \text{France})$.

However, whether curated by human experts or extracted automatically from text, large-scale knowledge graphs are notoriously incomplete. Missing edges are the rule rather than the exception. If a graph lacks the explicit edge connecting $\text{Paris}$ to $\text{France}$ via $\text{capital\_of}$, traditional symbolic database queries fail completely; they cannot retrieve what is not explicitly written.

To overcome this limitation, researchers developed Knowledge Graph Completion (KGC), also known as link prediction. The core intuition behind KGC is to transition from discrete, rigid symbolic structures to continuous latent spaces. By embedding entities and relations into continuous vector spaces, we can use geometric and algebraic operations to infer unobserved connections based on the global patterns of the existing graph.


Geometric Translations in Latent Space

The foundational breakthrough in continuous knowledge graph reasoning came from treating relations as geometric translations. In Translating Embeddings for Modeling Multi-relational Data, Antoine Bordes et al. introduced TransE, a model operating on a simple principle: if a factual triplet $(h, r, t)$ holds true, the embedding of the tail entity $\mathbf{t}$ should be close to the embedding of the head entity $\mathbf{h}$ plus the relation vector $\mathbf{r}$.

$$\mathbf{h} + \mathbf{r} \approx \mathbf{t}$$

  h (Paris) + r (capital_of) -------> t_predicted
                                         |
                                         v (minimize distance)
                                      t (France)

To train such a model, the system minimizes a distance-based score function $f_r(h,t) = \|\mathbf{h} + \mathbf{r} - \mathbf{t}\|$ for true facts, while maximizing it for corrupted, false triplets (e.g., replacing $\text{France}$ with $\text{Mars}$).

Why does this work? It forces the latent space to organize itself logically. If the graph contains $(\text{London}, \text{capital\_of}, \text{UK})$ and $(\text{Tokyo}, \text{capital\_of}, \text{Japan})$, the relation vector $\mathbf{r}_{\text{capital\_of}}$ learns a universal spatial shift. If the edge $(\text{Berlin}, \text{capital\_of}, \text{Germany})$ is missing from the database, the model can infer it because the vector sum $\mathbf{h}_{\text{Berlin}} + \mathbf{r}_{\text{capital\_of}}$ lands closest to $\mathbf{t}_{\text{Germany}}$ in the continuous space.


Capturing Complex Relations via Rotations

While translational models are highly scalable, they struggle with complex relational patterns like symmetry or inversion. For instance, if a relation is symmetric (such as $\text{is\_married\_to}$), then $\mathbf{h} + \mathbf{r} = \mathbf{t}$ and $\mathbf{t} + \mathbf{r} = \mathbf{h}$ implies that $\mathbf{r} = 0$, which collapses the representation.

To resolve this, Zhiqing Sun et al. proposed RotatE in RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. Instead of moving entities linearly, RotatE maps entities into a complex vector space and treats relations as rotations.

$$\mathbf{t} = \mathbf{h} \circ \mathbf{r}$$

where $\circ$ denotes the element-wise Hadamared product, and each coordinate of the relation vector $\mathbf{r}$ is a complex number with a modulus of 1 ($|r_i| = 1$). Geometrically, each relation rotates the head entity by a specific angle $\theta_i$ in the complex plane to reach the tail entity.

This formulation naturally accommodates diverse logical patterns:

  • Symmetry: A rotation of $180^\circ$ ($\pi$ radians) means rotating from $\mathbf{h}$ to $\mathbf{t}$ is identical to rotating from $\mathbf{t}$ to $\mathbf{h}$.
  • Inversion: If $r_1$ is $\text{parent\_of}$ and $r_2$ is $\text{child\_of}$, then $r_2$ simply learns an equal and opposite rotation angle to $r_1$.
  • Composition: If $r_1$ is $\text{mother\_of}$ and $r_2$ is $\text{husband\_of}$, the composite relation $\text{father\_of}$ is modeled by adding their rotation angles together.

Alternatively, models can leverage tensor factorization to capture these interactions. In TuckER: Tensor Factorization for Knowledge Graph Completion, Ivana Balazevic et al. demonstrated that link prediction can be framed as decomposing a binary tensor of graph connections. By utilizing a three-way Tucker decomposition, they learn a core tensor that explicitly models the degree of interaction between every dimension of the entity and relation spaces, providing a mathematically unified framework that encompasses many earlier linear embedding models.


Aggregating Neighborhood Context

Pure embedding models inspect triplets in isolation, ignoring the broader topological context surrounding an entity. Modern approaches bridge this gap by combining latent embeddings with Graph Neural Networks (GNNs) to aggregate multi-hop neighborhood information.

The intuition here is that a missing link between two entities is often signaled by the paths connecting them elsewhere in the graph. For example, if $A$ is a professor at university $B$, and university $B$ is located in city $C$, there is a high probability of a missing link stating $A$ lives in city $C$.

In Knowledge Graph Reasoning with Relational Digraph (OpenReview 2024), Yongqi Zhang introduces RED-GNN, a framework that utilizes relational digraphs (r-digraphs) to recursively track local evidence. Instead of computing expensive over-extended subgraphs, the model uses dynamic programming to propagate attention along relational paths. By conditioning the representation of an entity on its multi-hop neighborhood, the system learns to recognize structural patterns of evidence, allowing it to predict missing links with both higher accuracy and explicit, path-based interpretability.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_knowledge_graph_incompleteness_knowledge_18ee6ef2,
  title = {knowledge graph incompleteness (knowledge graph completion)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/knowledge-graph-incompleteness-knowledge-graph-completion/rdr_18ee6ef25ab14a8cbd7b14c4f8264853},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_knowledge_graph_incompleteness_knowledge_18ee6ef2_v1,
  title = {knowledge graph incompleteness (knowledge graph completion)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/knowledge-graph-incompleteness-knowledge-graph-completion/rdr_18ee6ef25ab14a8cbd7b14c4f8264853/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake