Efficient Knowledge Graph Completion via Dual-Sampling Path Ranking Algorithm

We consider the problem of Knowledge Graph Completion (KGC) in a large-scale knowledge base containing incomplete knowledge. Path Ranking Algorithm (PRA) is a soft inference procedure based on path-constrained random walk, which has proven to be an effective method for knowledge graph completion. However, the high computational complexity of PRA limits its application, especially in large-scale knowledge graphs. In order to alleviate this problem, we propose a Dual-Sampling Path Ranking Algorithm (DSPRA). DSPRA adopts a two-layer sampling strategy and performs particle sampling at the relation layer and the node layer respectively. Experiments on 48 tasks extracted from the NELL dataset prove that DSPRA can further improve the computational efficiency of PRA, while not significantly affecting its inference accuracy.