Message Passing for Query Answering over Knowledge Graphs

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 powerful tools for structured information retrieval, yet they are notoriously incomplete. Traditional logical traversal often fails when edges are missing. To address this, researchers embed queries and entities into a shared vector space to find approximate answers. However, previous state-of-the-art methods like Graph Query Embedding (GQE) rely on rigid, ad-hoc neural operators (e.g., specific "projection" and "intersection" modules). These models are limited in structural flexibility and typically require training on a massive, diverse set of query structures to perform well. This paper introduces Message Passing Query Embedding (MPQE), a flexible architecture that treats the query itself as a graph and uses message passing to compute embeddings.

Methods

Instead of parsing a query into a sequence of rigid operations, MPQE treats the query as a small graph where nodes are either known entities (constants) or unknown variables. The process follows three main stages:

  1. Initialization: Constant nodes are initialized with learned entity embeddings, while variable nodes are initialized with learned "type" embeddings.
  2. Message Passing: A Relational Graph Convolutional Network (R-GCN) runs over the query graph, updating node representations based on their neighbors and the specific relation types connecting them.
  3. Aggregation: Node representations are aggregated into a single vector representing the entire query.
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.

A highly effective variant introduced is Target Message (TM). In TM, the network performs exactly $D$ steps of message passing—where $D$ is the diameter of the query graph—and uses the final representation of the target variable node as the query embedding.

Key Results and Insights

MPQE demonstrates significant advantages over previous ad-hoc architectures across standard datasets like AIFB, MUTAG, AM, and Bio:

  • Zero-Shot Structural Generalization: Because MPQE relies on standard message passing rather than hard-coded operators, it can be trained purely on simple 1-hop link prediction and still successfully answer complex multi-hop and intersection queries at test time. In contrast, GQE baselines fail completely under these conditions.
  • Query Diameter Dictates Depth: Performance results confirm that the optimal number of message-passing steps corresponds to the diameter of the query graph. Once information from the furthest constant node reaches the target variable node, performance peaks.
AUC performance as a function of GNN layers. The black circles indicate the point where the number of layers matches the query diameter, showing where performance typically plateaus.
  • Unsupervised Semantic Clustering: Qualitative analysis via t-SNE reveals that MPQE naturally clusters entities by their semantic type without explicit supervision, creating a more structured embedding space than previous methods.

Conclusion

MPQE provides a robust and general framework for query answering over incomplete KGs. By replacing rigid structural operators with general message passing, it achieves superior generalization to unseen query structures. Future work includes improving the message-passing procedure with attention mechanisms and upgrading the underlying embedding geometry to more expressive representations, such as box embeddings, to better handle complex logical boundaries.

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 for Query Answering over Knowledge Graphs}},
  year = {2020},
  eprint = {2002.02406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.02406},
}
Figure