Abstract
Rule learning is critical to improving knowledge graph (KG) reasoning due to their ability to provide logical and interpretable explanations. Recently, Graph Neural Networks (GNNs) with tail entity scoring achieve the state-of-the-art performance on KG reasoning. However, the theoretical understandings for these GNNs are either lacking or focusing on single-relational graphs, leaving what the kind of rules these GNNs can learn an open problem. We propose to fill the above gap in this paper. Specifically, GNNs with tail entity scoring are unified into a common framework. Then, we analyze their expressivity by formally describing the rule structures they can learn and theoretically demonstrating their superiority. These results further inspire us to propose a novel labeling strategy to learn more rules in KG reasoning. Experimental results are consistent with our theoretical findings and verify the effectiveness of our proposed method.
Introduction
Knowledge Graph (KG) reasoning—the task of predicting missing links like (Einstein, born_in, ?)—has seen significant performance gains through Graph Neural Networks (GNNs) such as NBFNet and RED-GNN. These models typically employ a "labeling trick," marking the query entity to guide the network through the graph's multi-relational structure. Despite their empirical success, a theoretical gap has remained: why do these models outperform classical architectures like R-GCN, and what are the fundamental limits of the logical rules they can represent?
This paper bridges this gap by unifying state-of-the-art KG-GNNs into a single framework and analyzing them through the lens of mathematical logic. By identifying specific rule structures that GNNs can and cannot capture, the authors introduce a novel "Entity Labeling" (EL) strategy that significantly enhances reasoning performance.
The QL-GNN Framework and Logical Expressivity
The authors first demonstrate that most top-performing KG-GNNs can be unified under the Query Labeling GNN (QL-GNN) framework. These models score a potential answer entity based on its representation relative to a labeled query entity.
To analyze what these models "learn," the paper utilizes Graded Modal Logic (CML). The theoretical analysis proves that a QL-GNN can represent any rule expressible as a formula in CML where the query entity acts as a "constant." This explains the superiority of QL-GNNs over classical models like CompGCN, which are proven to learn only "non-structural" rules. By labeling the query entity, QL-GNNs transform a generic variable into a structural anchor, allowing them to capture complex path-based logic.
Enhancing Expressivity: EL-GNN
The logical analysis reveals a critical limitation: QL-GNNs struggle with rules that require distinguishing specific "middle-man" entities—nodes that are neither the query nor the target but are essential to the rule's logic.
To address this, the authors propose the Entity Labeling GNN (EL-GNN). This method identifies "landmark" entities—those with high out-degrees—and assigns them unique labels. These landmarks serve as additional structural anchors, enabling the GNN to orient itself and learn more complex rules that were previously out of reach.
Experimental Evaluation
The proposed theories were validated using both synthetic and real-world datasets:
- Synthetic KGs: Six custom graphs ($C_3, C_4, I_1, I_2, T, U$) were designed to test specific rule structures. While QL-GNNs mastered simple rules, they struggled with the complex "$U$" structure (scoring ~40-54% accuracy). EL-GNN successfully captured this structure, reaching ~84% accuracy.
- Real-World Benchmarks: On standard datasets like FB15k-237 and WN18RR, EL-GNN consistently outperformed previous state-of-the-art models. For instance, EL-NBFNet improved accuracy on FB15k-237 from 0.320 to 0.332.
Furthermore, the EL-GNN labeling step adds only linear time complexity relative to the number of entities, making it a practical enhancement for existing reasoning pipelines.
Theoretical Insights and Future Directions
A key finding is the "Landmark Strategy" trade-off: labeling too many nodes can lead to overfitting, where the model becomes too specific to the training graph. A "Goldilocks zone" exists where the degree threshold for labeling balances expressivity and generalization.
While this work clarifies what GNNs can learn, several avenues for future work remain. Current theory focuses on learning rules for a single relation at a time, whereas real-world KGs involve thousands of simultaneous relations. Additionally, while the models are expressive, extracting these learned rules into human-readable logical statements remains a challenge for future interpretability research.
Summary updated