Understanding Expressivity of GNN in Rule Learning

Haiquan Qiu, Yongqi Zhang, Yong Li, Quanming Yao

TL;DR

This paper bridges the gap between the empirical success of Graph Neural Networks (GNNs) in Knowledge Graph (KG) reasoning and their theoretical foundations. By unifying state-of-the-art GNNs into a framework called QL-GNN, the authors prove these models learn rules equivalent to Graded Modal Logic (CML) and introduce EL-GNN, a novel labeling strategy that expands the range of logical rules a GNN can master.

What Problem Does This Paper Address?

Knowledge Graph reasoning—the task of predicting missing facts like (Einstein, born_in, ?)—has seen a massive performance boost from GNNs. However, we haven't fully understood why they work so well or what specific logical rules they are actually learning.

Existing theoretical work often focuses on simple, single-relational graphs, which doesn't capture the complexity of KGs where edges have different types (e.g., "friend" vs. "parent"). Furthermore, while models like NBFNet and RED-GNN achieve state-of-the-art (SOTA) results, they are motivated by different heuristics (like the Bellman-Ford algorithm), making it hard to compare their fundamental "intelligence" or logical limits.

Methods

The authors first unify SOTA KG-reasoning GNNs into a common framework: Query Labeling GNN (QL-GNN). The defining feature of QL-GNNs is the "labeling trick"—assigning a unique initial representation to the query entity (the "head" of the triplet you're trying to complete).

The Logical Connection

The core contribution is analyzing QL-GNN through the lens of Graded Modal Logic (CML).

  • Expressivity: They prove that a QL-GNN can learn a rule if and only if that rule can be expressed in CML relative to the query entity.
  • Comparison: They show that classical GNNs (like R-GCN or CompGCN) are significantly weaker because they don't use the labeling trick. These older models can only learn "non-structural" rules—essentially looking at disconnected neighborhoods around the two entities rather than the path between them.

EL-GNN: Breaking the Limits

The authors identify that QL-GNNs struggle with rules involving complex, multi-connected structures (where nodes have multiple outgoing paths). To fix this, they propose Entity Labeling GNN (EL-GNN).

Overview of Knowledge Graphs, Rule Structures, and GNN Expressivity

As shown in Algorithm 1 in the paper, EL-GNN identifies "landmark" entities—those with an out-degree higher than a threshold $d$—and gives them unique labels. This effectively adds "constants" to the logic, allowing the GNN to distinguish and learn much more complex rule structures that were previously "invisible" to it.

Datasets

The researchers evaluated their theories and models on two fronts:

  1. Synthetic Datasets: Six KGs specifically designed to test different logical structures ($C_3, C_4, I_1, I_2, T, U$). These benchmarks are crucial because they isolate specific logical challenges that real-world data might obscure.
  2. Real-World Benchmarks: Standard KG datasets including Family, Kinship, UMLS, WN18RR, and FB15k-237.

Key Insights and Ideas

  • The Labeling Trick is Essential: The simple act of marking the query entity is what allows GNNs to move beyond simple neighborhood averaging and start learning actual structural paths (rules).
  • Logic as a Yardstick: By mapping GNN architectures to specific fragments of first-order logic (like CML), we get a formal way to say exactly what a model can and cannot "understand."
  • Structural Blindness: Classical GNNs are "structurally blind" in KG reasoning. Because they don't label the query entity, they can't tell if a path actually connects the query to the target.
  • Landmarks Matter: Labeling high-degree nodes acts like placing GPS beacons in the graph, helping the GNN navigate and learn rules that involve complex branching.
Examples of rule structures like chain-like (C3) and tree-like (I1) rules

Key Results

  • Synthetic Validation: On the most complex synthetic rule ($U$), vanilla QL-GNNs (like NBFNet) only achieved ~40-54% accuracy. EL-GNN boosted this to ~80-84%, confirming that the new labeling strategy successfully expanded the model's logical capacity.
  • Real-World Gains: EL-GNN consistently outperformed SOTA backbones. For example, on the FB15k-237 dataset, EL-NBFNet improved accuracy to 0.332 compared to NBFNet's 0.320.
  • Efficiency: The authors noted that while EL-GNN is more expressive, the additional computational overhead is negligible, as it only requires a single traversal of the graph to identify high-degree nodes.

Limitations and Future Work

  • Hyperparameter Sensitivity: The degree threshold $d$ for labeling entities is a sensitive hyperparameter. If $d$ is too small, too many constants are added, which can hurt the model's ability to generalize to new parts of the graph.
  • Single vs. Multiple Rules: The current theory focuses on the ability to learn a single relation/rule. In practice, GNNs learn many relations simultaneously, and understanding the capacity limits for multi-rule learning remains an open question.
  • Incomplete Data: While the theory holds for perfect graphs, real-world KGs are often missing many triplets. The authors suggest that studying expressivity on incomplete datasets is a vital next step.

Summary updated

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. The code is publicly available at https://github.com/LARS-research/Rule-learning-expressivity.
BibTeX
@inproceedings{qiu2024understanding,
  author = {Haiquan Qiu and Yongqi Zhang and Yong Li and Quanming Yao},
  title = {{Understanding Expressivity of GNN in Rule Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=43cYe4oogi},
}
Figure