Message Passing Query Embedding

Daniel Daza, Michael Cochez

Abstract

Recent works on representation learning for Knowledge Graphs have moved beyond the problem of link prediction, to answering queries of an arbitrary structure. Existing methods are based on ad-hoc mechanisms that require training with a diverse set of query structures. We propose a more general architecture that employs a graph neural network to encode a graph representation of the query, where nodes correspond to entities and variables. The generality of our method allows it to encode a more diverse set of query types in comparison to previous work. Our method shows competitive performance against previous models for complex queries, and in contrast with these models, it can answer complex queries when trained for link prediction only. We show that the model learns entity embeddings that capture the notion of entity type without explicit supervision.

Introduction

Knowledge Graphs (KGs) are essential for representing real-world facts, yet they are inherently incomplete. Traditional database queries fail when a single link is missing. Query Embedding methods address this by mapping queries and entities into a continuous vector space, where proximity indicates a likely answer. However, current state-of-the-art approaches, such as GQE, rely on ad-hoc geometric operators (e.g., specific intersection functions) for different query structures. This dependency necessitates training on a wide array of complex query shapes and often leads to failure when encountering unseen structures.

The MPQE Framework

Message Passing Query Embedding (MPQE) addresses these limitations by treating logical queries as small graphs and utilizing a general Graph Neural Network (GNN) for encoding.

The MPQE architecture: A query graph is processed by an R-GCN to produce node representations, which are then aggregated into a final query embedding vector.

The MPQE process involves three primary stages:

  1. Query Graph Representation: Logical queries are modeled as graphs where nodes represent known entities or variables, and edges represent relations.
  2. Relational Message Passing: A Relational Graph Convolutional Network (R-GCN) facilitates information flow across the query graph. Each node updates its state based on its neighbors and the specific relation types connecting them.
  3. Aggregation: Node representations are combined into a single query embedding vector $\mathbf{q}$. The authors explored several strategies, including simple pooling (Fixed), multi-layer concatenation (CMLP), and Target Message (TM), which focuses on the representation of the target variable node.

Experimental Evaluation

The model was benchmarked on four diverse Knowledge Graph datasets: AIFB (academic metadata), MUTAG (molecular properties), AM (museum artifacts), and Bio (biological interactions). Evaluation covered seven distinct query structures, ranging from simple chains to complex intersections.

MPQE demonstrated competitive performance, often surpassing baselines. For instance, on the AIFB dataset, the MPQE-CMLP variant achieved an AUC of 86.3%, compared to 83.4% for GQE-Bilinear.

Key Findings and Qualitative Analysis

A defining characteristic of MPQE is its structural inductive bias. By leveraging a GNN, the model inherently understands graph topology, allowing it to handle complex constraints like intersections through natural message-passing flow rather than specialized operators.

This generality enables zero-shot generalization. MPQE can be trained exclusively on simple 1-hop link predictions and still perform effectively on complex, multi-step queries at test time—a scenario where previous models typically fail. Furthermore, performance peaks when the number of GNN layers matches the query graph's diameter, confirming the importance of complete information propagation.

t-SNE visualization of entity embeddings. The right panel shows how MPQE learns to cluster entities by type without explicit supervision, compared to a baseline on the left.

Qualitatively, MPQE learns a highly structured embedding space. As shown in the t-SNE visualizations, the model discovers entity types without explicit supervision, resulting in clear clusters for different categories of entities.

Conclusion and Future Directions

MPQE provides a robust and generalizable framework for complex query answering on Knowledge Graphs. While highly effective, challenges remain in handling "hard negative" samples in complex intersections. Future work may explore more expressive geometries, such as Box Embeddings, or incorporate attention mechanisms to further refine the message-passing process for increasingly large and intricate queries.

Summary updated

Abstract

Recent works on representation learning for Knowledge Graphs have moved beyond the problem of link prediction, to answering queries of an arbitrary structure. Existing methods are based on ad-hoc mechanisms that require training with a diverse set of query structures. We propose a more general architecture that employs a graph neural network to encode a graph representation of the query, where nodes correspond to entities and variables. The generality of our method allows it to encode a more diverse set of query types in comparison to previous work. Our method shows competitive performance against previous models for complex queries, and in contrast with these models, it can answer complex queries when trained for link prediction only. We show that the model learns entity embeddings that capture the notion of entity type without explicit supervision.
BibTeX
@misc{daza2020message,
  author = {Daniel Daza and Michael Cochez},
  title = {{Message Passing Query Embedding}},
  year = {2020},
  eprint = {2002.02406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.02406},
}
Figure