Paper Reading AI Learner

Logical Expressiveness of Graph Neural Network for Knowledge Graph Reasoning

2023-03-22 04:49:00
Haiquan Qiu, Yongqi Zhang, Yong Li, Quanming Yao

Abstract

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.

Abstract (translated)

Graph Neural Networks (GNNs) 引入以来,从知识图(KG)学习并在KG推理中取得了最先进的性能。然而,缺乏对其良好经验表现的理论证明。此外,尽管KG的逻辑对于归纳和可解释推理非常重要,但现有的GNN-based方法只是设计以适应数据分布,对其逻辑表达能力的有限知识进行适应。我们建议在这篇论文中填补这些差距。具体而言,我们从理论上分析GNN的逻辑表达能力,并找出可以从KG捕获的逻辑规则的种类。我们的结果显示,GNN可以从等级模态逻辑捕获逻辑规则,为分析GNN在KG推理中表达能力提供了新的理论工具;查询标签技巧使GNN更容易捕获逻辑规则,解释了为什么SOTA方法主要基于标签技巧。最后,我们的理论见解激励开发用于捕获困难逻辑规则实体标签方法。实验结果与我们的理论结果一致,并验证了我们提出的方法的有效性。

URL

https://arxiv.org/abs/2303.12306

PDF

https://arxiv.org/pdf/2303.12306.pdf


Tags
3D Action Action_Localization Action_Recognition Activity Adversarial Agent Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot