Efficient Embeddings of Logical Variables for Query Answering over Incomplete Knowledge Graphs

Dingmin Wang, Yeyuan Chen, Bernardo Cuenca Grau

TL;DR

This paper introduces Var2Vec, a novel method for answering complex logical queries over incomplete knowledge graphs (KGs). Var2Vec overcomes limitations of previous approaches by efficiently handling negation, reducing inference time, and requiring only simple facts for training, unlike methods that need complex query-answer pairs.

What Problem Does This Paper Address?

Knowledge graphs (KGs) are powerful tools for representing information, but they are often incomplete, meaning many true facts are missing. A significant challenge is answering complex logical queries over these incomplete KGs. While neural link predictors can identify missing facts, they struggle with complex queries. Existing methods for complex query answering either require extensive training data (example queries and their answers) or cannot handle logical negation. This paper aims to bridge this gap by developing a method that is efficient, handles negation, and requires minimal training data.

Methods

The core of Var2Vec lies in its ability to learn vector representations for variables within logical queries. It leverages a pre-trained neural link predictor (like TransE, DistMult, or ComplEx) which provides embeddings for entities and relations.

  1. Learning a Weight Matrix (W): Var2Vec trains a weight matrix W that learns to map the embeddings of a term and its relation to the embedding of the term it relates to. This is done by minimizing a loss function on known facts, effectively teaching W how to predict the embedding of the second argument in a triple. This is a key departure from methods that require complex query training.
  2. Generating Variable Embeddings: For a given query, Var2Vec traverses its dependency graph. It starts with known entity and relation embeddings. For each existentially quantified variable, it computes its embedding by combining the embeddings of the terms it's related to via learned relations, using the trained weight matrix W. This process is iterative and handles complex query structures.
  3. Scoring for Query-Entity Pairs: Once all variables in a query have embeddings, Var2Vec uses the neural link predictor's decoding function to score each entity in the KG as a potential answer to the query. This scoring is done recursively based on the logical structure of the query (conjunction, disjunction, negation), using t-norms and t-conorms to combine scores.

Datasets

The paper evaluates Var2Vec on three standard KG benchmarks commonly used for KG completion and query answering:

  • FB15k: A widely used KG derived from Freebase.
  • FB15k-237: A subset of FB15k that removes inverse relations, making it more challenging.
  • NELL995: A subset of the Never-Ending Language Learner KG.

The benchmark also provides a set of query patterns, including those without negation (from Ren et al., 2020) and those with negation (introduced later).

Key Insights and Ideas

  • Learning Variable Embeddings from Facts: The most significant insight is that it's possible to learn effective embeddings for query variables solely from simple factual triples, without needing explicit examples of complex query answers. This dramatically reduces the training data requirements.
  • Unified Handling of Logic: Var2Vec's approach of traversing the query's dependency graph and using a learned weight matrix allows it to handle various logical constructs (conjunction, disjunction, negation, existential quantification) in a unified manner.
  • Efficiency through Embeddings: By representing queries and their components as vectors, Var2Vec transforms query answering into a scoring and ranking problem, which is significantly more efficient than methods that might materialize large parts of the KG.
  • Negation is Tractable: The paper demonstrates that logical negation can be effectively incorporated into this embedding-based framework, a limitation of many prior works.

Key Results

  • Superior Performance: Var2Vec achieves state-of-the-art or highly competitive performance across all three benchmark datasets and various query patterns, outperforming baselines like GQE, Query2Box, BetaE, ConE, MLP, and CQD.
  • Significant Speedup: Var2Vec demonstrates substantial improvements in inference times compared to CQD, being significantly faster. It also shows faster training times compared to embedding-based models.
  • Generalization: The approach shows strong generalization to query patterns not seen during training, suggesting robustness.
  • Ablation Studies: The paper confirms that using ComplexE as the link predictor yields better results than DisMult. It also shows that product t-norms and t-conorms lead to superior performance.

Limitations and Future Work

  • Link Predictor Dependency: The performance of Var2Vec is dependent on the quality of the underlying neural link predictor.
  • Computational Cost for Scoring: While inference is faster than CQD, scoring every entity in the KG for each query can still be computationally intensive for very large KGs.
  • Future Work: The authors suggest exploring more complex neural architectures for learning the weight matrix (though initial experiments showed simple matrices are effective) and potentially investigating inductive link predictors for even broader applicability.

Summary updated

Abstract

The problem of answering complex First-order Logic queries over incomplete knowledge graphs is receiving growing attention in the literature. A promising recent approach to this problem has been to exploit neural link predictors, which can be effective in identifying individual missing triples in the incomplete graph, in order to efficiently answer complex queries. A crucial advantage of this approach over other methods is that it does not require example answers to complex queries for training, as it relies only on the availability of a trained link predictor for the knowledge graph at hand. This approach, however, can be computationally expensive during inference, and cannot deal with queries involving negation. In this paper, we propose a novel approach that addresses all of these limitations. Experiments on established benchmark datasets demonstrate that our approach offers superior performance while significantly reducing inference times.
BibTeX
@inproceedings{wang2023efficient,
  author = {Dingmin Wang and Yeyuan Chen and Bernardo Cuenca Grau},
  title = {{Efficient Embeddings of Logical Variables for Query Answering over Incomplete Knowledge Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25588},
}
Figure