Reasoning on the knowledge graph (KG) aims to infer new facts from existing ones. Methods based on the relational path have shown strong, interpretable, and transferable reasoning ability. However, paths are naturally limited in capturing local evidence in graphs. In this paper, we introduce a novel relational structure, i.e., relational directed graph (r-digraph), which is composed of overlapped relational paths, to capture the KG's local evidence. Since the r- digraphs are more complex than paths, how to efficiently construct and effectively learn from them are challenging. Directly encoding the r-digraphs cannot scale well and capturing query-dependent information is hard in r-digraphs. We propose a variant of graph neural network, i.e., RED-GNN, to address the above challenges. Specifically, RED-GNN makes use of dynamic programming to recursively encodes multiple r-digraphs with shared edges, and utilizes a query-dependent attention mechanism to select the strongly correlated edges. We demonstrate that RED-GNN is not only efficient but also can achieve significant performance gains in both inductive and transductive reasoning tasks over existing methods. Besides, the learned attention weights in RED-GNN can exhibit interpretable evidence for KG reasoning.
翻译:以知识图(KG)为根据来推断现有事实。基于关系路径的方法已经显示出强大的、可解释的和可转移的推理能力。然而,路径自然有限,难以在图表中捕捉当地证据。在本文中,我们引入了一种新的关系结构,即由关系路径重叠组成的关系定向图(r-digraph),以捕捉KG的当地证据。由于r-digraph比路径复杂得多,如何有效地构建和有效地从中吸取教训是具有挑战性的。直接将r-digraph系统编码成正比,而获取依赖查询的信息在r-digraph系统中是很难做到的。我们提出了一个图形神经网络的变式,即RED-GNN,以应对上述挑战。具体地说,RED-GNNN利用动态编程来将具有共同边缘的多重rdigraph系统重新编码,并使用一个依赖查询的注意机制来选择高度关联的边缘。我们证明RED-GNN不只是效率高尺度的,而且还可以使G在现有的推理学上获得重大的成绩。