Graph Neural Networks (GNNs) have been recently introduced to learn from knowledge graph (KG) and achieved state-of-the-art performance in KG reasoning. However, a theoretical certification for their good empirical performance is still absent. Besides, while logic in KG is important for inductive and interpretable inference, existing GNN-based methods are just designed to fit data distributions with limited knowledge of their logical expressiveness. We propose to fill the above gap in this paper. Specifically, we theoretically analyze GNN from logical expressiveness and find out what kind of logical rules can be captured from KG. Our results first show that GNN can capture logical rules from graded modal logic, providing a new theoretical tool for analyzing the expressiveness of GNN for KG reasoning; and a query labeling trick makes it easier for GNN to capture logical rules, explaining why SOTA methods are mainly based on labeling trick. Finally, insights from our theory motivate the development of an entity labeling method for capturing difficult logical rules. Experimental results are consistent with our theoretical results and verify the effectiveness of our proposed method.
翻译:图神经网络(GNN)最近被引入知识图谱(KG)中进行学习,并在KG推理中取得了最先进的性能。然而,它们良好的经验表现的理论证明仍然缺失。此外,虽然KG中的逻辑对于归纳和可解释的推理非常重要,但现有的基于GNN的方法仅仅是为了拟合具有有限逻辑表达能力的数据分布而设计的。我们在本文中提出了填补上述空白的方案。具体地,我们从逻辑表达能力的角度理论分析GNN,并找出KG中可以捕获的逻辑规则的类型。我们的结果首次表明,GNN可以从分级模态逻辑中捕获逻辑规则,为分析GNN在KG推理中的表达能力提供了一个新的理论工具。查询标记技巧使GNN更容易捕获逻辑规则,解释了为什么SOTA方法主要基于标记技巧。最后,我们理论上的见解激励了开发一个实体标记方法,以捕获难以理解的逻辑规则。实验结果与我们的理论结果一致,并验证了我们提出的方法的有效性。