Link Prediction using Embedded Knowledge Graphs

Abstract: Recent studies on knowledge base completion, the task of recovering missing facts based on observed facts, demonstrate the importance of learning embeddings from multi-step relations. Due to the size of knowledge bases, previous works manually design relation paths of observed triplets in symbolic space (e.g. random walk) to learn multi-step relations during training. However, these approaches suffer some limitations as most paths are not informative, and it is prohibitively expensive to consider all possible paths. To address the limitations, we propose learning to traverse in vector space directly without the need of symbolic space guidance. To remember the connections between related observed triplets and be able to adaptively change relation paths in vector space, we propose Implicit ReasoNets (IRNs), that is composed of a global memory and a controller module to learn multi-step relation paths in vector space and infer missing facts jointly without any human-designed procedure. Without using any axillary information, our proposed model achieves state-of-the-art results on popular knowledge base completion benchmarks.

We thank Scott Wen-Tau Yih, Kristina Toutanova, Jian Tang, Greg Yang, Adith Swaminathan, Xiaodong He, and Zachary Lipton for their thoughtful feedback and discussions.
 Inference Steps in KBC Analysis: Applying IRNs to a Shortest Path Synthesis Task 

Figure and table captions:
Figure 1: An overview of the IRN for KBC tasks.
Figure 2: A running example of the IRN architecture. Given the input (Obama, CITIZENSHIP,?), the model iteratively reformulates the input vector via the current input vector and the attention vector over the shared memory, and determines to stop when an answer is found.
Table 1: The knowledge base completion (link prediction) results on WN18 and FB15k.
Table 2: The performance of IRNs with different memory sizes and inference steps on FB15k, where |M | and Tmax represent the number of memory vectors and the maximum inference step, respectively.
Table 3: Hits@10 (%) in the relation category on FB15k. (M stands for Many)
Table 4: Interpret the state st in each step via finding the closest (entity, relation) tuple, and the corresponding the top-3 predictions and termination probability. “Rank” stands for the rank of the target entity and “Term. Prob.” stands for termination probability.
Table 5: Shared memory visualization in an IRN trained on FB15k, where we show the top 8 relations, ranked by the average attention scores, of some memory cells. The first row in each column represents the interpreted relation.
Figure 3: An example of the shortest path synthesis dataset, given an input “215 ; 493” (Answer: 215→ 101→ 493). Note that we only show the nodes that are related to this example here. The corresponding termination probability and prediction results are shown in the table. The model terminates at step 5.

Questions about this paper:
What datasets are used to evaluate the model?

Answers:
WN18 and FB15k