Differentiable Reasoning about Knowledge Graphs with Region-based Graph Neural Networks

Aleksandar Pavlovic, Emanuel Sallinger, Steven Schockaert

TL;DR

This paper introduces RESHUFFLE, a novel knowledge graph embedding model that uses ordering constraints on reshuffled entity embeddings to faithfully capture a broader range of logical rules than previous region-based methods. By leveraging Graph Neural Networks (GNNs), RESHUFFLE offers a differentiable approach to rule learning that can be efficiently updated with new knowledge.

What Problem Does This Paper Address?

Knowledge graph (KG) embedding methods aim to represent entities and relations geometrically to infer missing facts. A key challenge is understanding which logical rules these embeddings can capture. While region-based models offer more transparency by representing relations as geometric regions, existing methods are limited to simple rules due to their reliance on coordinate-wise comparisons. This paper addresses the need for KG embedding models that can faithfully capture a wider variety of logical rules, particularly complex rule bases, while remaining computationally efficient and amenable to learning via GNNs.

Methods

The core innovation is the RESHUFFLE model, which moves beyond coordinate-wise comparisons. Instead, it defines relation embeddings as regions based on ordering constraints between reshuffled entity embeddings. This means that for a relation $r$, its region $\eta(r)$ is defined by conditions like $e_i \le f_j$ for specific indices $i$ and $j$, where $e$ and $f$ are entity embeddings. This allows for more complex interactions than simple coordinate-wise checks.

Entity embeddings are learned using a Graph Neural Network (GNN). This GNN acts as a differentiable approximation of a rule base, taking randomly initialized entity embeddings and propagating information through the graph structure to enforce rule consequences. This GNN-based approach enables inductive KG completion and allows for theoretical analysis of bounded reasoning. The paper also introduces the concept of "rule graphs" as an abstraction to formally connect rule bases to RESHUFFLE's parameters.

Datasets

The authors evaluate RESHUFFLE on inductive knowledge graph completion benchmarks derived from:

  • FB15k-237
  • WN18RR
  • NELL-995

Each of these datasets is further split into four versions (v1-v4), resulting in a total of twelve datasets for evaluation.

Key Insights and Ideas

  • Beyond Coordinate-Wise: The fundamental insight is that moving beyond simple coordinate-wise comparisons in region-based embeddings (e.g., checking $e_i \le f_i$ for each dimension $i$) is crucial for capturing more complex logical rules. RESHUFFLE achieves this by "reshuffling" embeddings, allowing for cross-dimensional dependencies.
  • GNNs as Differentiable Rule Bases: Using a GNN to learn entity embeddings transforms the model into a differentiable rule learner. This is powerful because it allows for end-to-end training and efficient updates when new knowledge is added.
  • Faithful Rule Capture: The paper rigorously defines what it means for a model to "faithfully capture" a rule base, ensuring that all entailed facts are captured and no spurious facts are inferred. RESHUFFLE is shown to be more expressive than prior region-based models in this regard.
  • Bounded Reasoning: The GNN formulation naturally leads to the concept of bounded inference, where reasoning is limited to a fixed number of steps. RESHUFFLE is proven to faithfully capture arbitrary sets of closed path rules within this bounded setting.

Key Results

  • Expressiveness: RESHUFFLE demonstrates superior expressiveness compared to existing region-based models, particularly in capturing closed path rules.
  • Empirical Performance: RESHUFFLE consistently outperforms differentiable rule learners like DRUM and Neural-LP on inductive KG completion tasks, often by a significant margin. It also performs competitively with GNN-based methods like COMPILE and GraIL on FB15k-237 and NELL-995.
  • Ablation Studies: Experiments show that the core RESHUFFLE model (with specific constraints) performs better than variants that relax these constraints, suggesting the importance of the proposed parameterization for avoiding overfitting.
  • State-of-the-Art Comparison: While RESHUFFLE is competitive with differentiable rule learners, it does not reach state-of-the-art performance on KGC benchmarks, which the authors attribute to the inherent limitations of rule-based reasoning when dealing with noisy evidence.

Limitations and Future Work

  • Non-Monotonic Reasoning: RESHUFFLE, like other rule-based methods, struggles with non-monotonic reasoning (revising beliefs when new evidence emerges). Developing models that can handle this remains an open challenge.
  • Inverse and Symmetric Relations: The basic RESHUFFLE formulation doesn't directly handle inverse or symmetric relations, though these can be incorporated by adding inverse triples and constraints.
  • Disjointness Constraints: Capturing disjointness constraints (where two relations cannot co-occur) is not directly supported.
  • Higher Arity Relations: The current work focuses on binary relations. Extending the model to handle relations with higher arity is a promising direction for future work.

Summary updated

Abstract

Methods for knowledge graph (KG) completion need to capture semantic regularities and use these regularities to infer plausible knowledge that is not explicitly stated. Most embedding-based methods are opaque in the kinds of regularities they can capture, although region-based KG embedding models have emerged as a more transparent alternative. By modeling relations as geometric regions in high-dimensional vector spaces, such models can explicitly capture semantic regularities in terms of the spatial arrangement of these regions. Unfortunately, existing region-based approaches are severely limited in the kinds of rules they can capture. We argue that this limitation arises because the considered regions are defined as the Cartesian product of two-dimensional regions. As an alternative, in this paper, we propose RESHUFFLE, a simple model based on ordering constraints that can faithfully capture a much larger class of rule bases than existing approaches. Moreover, the embeddings in our framework can be learned by a monotonic Graph Neural Network (GNN), which effectively acts as a differentiable rule base. This approach has the important advantage that embeddings can be easily updated as new knowledge is added to the KG. At the same time, since the resulting representations can be used similarly to standard KG embeddings, our approach is significantly more efficient than existing approaches to differentiable reasoning.
BibTeX
@misc{pavlovic2024differentiable,
  author = {Aleksandar Pavlovic and Emanuel Sallinger and Steven Schockaert},
  title = {{Differentiable Reasoning about Knowledge Graphs with Region-based Graph Neural Networks}},
  year = {2024},
  eprint = {2406.09529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.09529},
}
Figure