Logical Expressiveness of Graph Neural Network for Knowledge Graph Reasoning

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.

Introduction

Knowledge Graph (KG) reasoning—the task of predicting missing facts such as (Einstein, born_in, ?)—has seen significant performance gains from Graph Neural Networks (GNNs) like NBFNet and RED-GNN. Despite their success, these models are often built on heuristics, leaving a fundamental question unanswered: What kind of logical rules are these GNNs actually learning?

While traditional GNN theory focuses on graph isomorphism, this work shifts the focus to logical expressivity: the ability of a GNN to represent and learn specific multi-relational rule structures. By unifying state-of-the-art models into a single framework and mapping them to formal logic, this paper provides a rigorous foundation for KG reasoning.

Overview of Knowledge Graph reasoning, rule structures, and the expressivity of QL-GNN versus EL-GNN.

Theoretical Framework: QL-GNN and Graded Modal Logic

The authors unify top-performing models into the Query Labeling (QL) GNN framework. The core of these models is the "labeling trick," which assigns a unique starting feature to the query entity (the "head" of the triplet).

The paper proves that QL-GNNs are logically equivalent to Graded Modal Logic (CML). In this mapping, every message-passing step in the GNN corresponds to a specific logical operation, such as "there exist at least $N$ neighbors with property $X$." This explains why GNNs naturally act as counting engines, implementing counting quantifiers essential for relational reasoning.

Advancing Expressivity: The EL-GNN Method

Despite the power of QL-GNNs, the authors identify a bottleneck: these models struggle with complex, non-chain-like rules. For example, in "U-shaped" structures where a path splits and merges, standard GNNs lose track of node identities.

To solve this, the authors propose Entity Labeling GNN (EL-GNN). Instead of labeling only the query entity, EL-GNN labels all entities with an out-degree higher than a threshold $d$. These high-traffic nodes act as "anchors" or logical constants, allowing the GNN to learn much more complex rule structures that were previously inaccessible.

Comparison of chain rule (C3) and intersection rule (I1) structures and their corresponding logical formulas.

Experimental Validation

The theory was tested using both synthetic and real-world datasets:

  • Synthetic Benchmarks: Six custom KGs ($C_3, C_4, I_1, I_2, T, U$) were designed to test specific rule structures. While QL-GNNs achieved 100% accuracy on simple chain rules ($C_3, C_4$), they struggled on the complex "U" rule (scoring as low as 40%). EL-GNN boosted this performance to over 80%.
  • Real-World Datasets: On standard benchmarks like FB15k-237 and WN18RR, EL-GNN consistently outperformed previous state-of-the-art models. For instance, on FB15k-237, EL-NBFNet achieved an accuracy of 0.332, surpassing the standard NBFNet's 0.320.

Conclusion

This work provides a theoretical bridge between GNN architectures and logical reasoning in KGs. By identifying the limits of current query-labeling methods and introducing the entity-labeling trick, the authors provide both a deeper understanding of why GNNs work and a practical path toward more expressive models. Future work remains to optimize the degree threshold $d$ and explore expressivity in highly incomplete or noisy knowledge graphs.

Summary updated

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.
BibTeX
@inproceedings{qiu2024logical,
  author = {Haiquan Qiu and Yongqi Zhang and Yong Li and Quanming Yao},
  title = {{Logical Expressiveness of Graph Neural Network for Knowledge Graph Reasoning}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=43cYe4oogi},
}
Figure