Unlocking Complex Query Answering: CQDA - A Parameter-Efficient Model for Knowledge Graphs

By Dr. Sampath LonkaReviewed by Susha Cheriyedath, M.Sc.Jul 14 2023

Addressing complex queries on incomplete knowledge graphs presents a significant challenge. Existing approaches often rely on resource-intensive training methods and lack interpretability.

In a recent submission to the arXiv* server, researchers proposed CQD^A, a parameter-efficient model designed to recalibrate neural link prediction scores for complex query answering (CQA). This model outperforms state-of-the-art methods by achieving higher accuracy with limited training data and supporting reasoning with negations. It also demonstrates data efficiency and robustness in out-of-domain evaluations.

*Important notice: arXiv publishes preliminary scientific reports that are not peer-reviewed and, therefore, should not be regarded as conclusive, guide clinical practice/health-related behavior, or treated as established information.

Background

Knowledge Graphs (KGs) serve as valuable representations of relationships between entities in various domains. Answering complex queries over KGs requires logical reasoning. While neural link predictors address missing edge identification, answering queries with multiple unobserved edges necessitates specialized models. Existing approaches lack interpretability and require extensive training data. In contrast, CQD provides a simple link prediction model but lacks negation support and calibrated scores. To overcome these limitations, the researchers propose CQD^A, a lightweight adaptation model that calibrates link prediction scores for CQA.

Related work

Researchers working in the field of reasoning over KGs with missing nodes have explored various approaches to link prediction. Latent feature models, including neural link predictors, graph feature models, and GNNs, have been employed for this purpose. CQA extends atomic queries using First-Order Logic (FOL) operators, and previous methods utilized embedding-based techniques, probabilistic distributions, or GNNs for answer retrieval. However, existing approaches like CQD have limitations in score calibration and handling negation. In contrast, CQD^A addresses these challenges by introducing a scalable adaptation function that calibrates link prediction scores, enabling support for a broader range of FOL queries, including atomic negation.

Methodology

To address the limitation of the CQD method in score calibration for neural link prediction, the researchers propose a method for adaptive learning of score calibration. The main issue lies in the fact that scores produced by neural link predictors are not trained to interact with each other when answering complex queries. To tackle this, the researchers introduce an adaptation function that performs an affine transformation of the scores produced by the neural link predictor.

During training, the answer scores for each candidate entity are computed, and additional parameters are optimized using gradient descent. The likelihood of the true answers is maximized based on the scores, utilizing either a 1-vs-all cross-entropy loss or a binary cross-entropy loss.

By employing this adaptive score calibration, the interaction of scores produced by the neural link predictor improves, leading to more accurate complex query answering.

Experiments

The researchers evaluated the CQD^A method using three benchmark KG datasets: FB15K, FB15K-237, and NELL995. They employed FOL query datasets proposed by Ren and Leskovec, which include various query structures and types, including atomic negations. The datasets consist of challenging tasks with hard answers and exclude queries with more than 100 answers. During the training phase, a subset of query types was utilized for the adaptation process. The evaluation followed the protocol of Ren and Leskovec, calculating the mean reciprocal rank (MRR) for non-trivial queries.

Results

The proposed CQD^A model outperforms state-of-the-art methods in CQA. It increases the MRR from 34.4 to 35.1, especially on the NELL995 dataset. The CQD^A model demonstrates its efficiency by achieving competitive results using ≤ 30% of the complex query types during training. When handling queries with negations, CQD^A shows a relative improvement of 6.8% to 37.1%.

Moreover, the adaptation process is data-efficient, as training with only 1% of the complex queries yields competitive results. CQD^A exhibits generalization capabilities, performing well on unseen query types while maintaining a fast convergence rate. The study highlights that CQD^A achieves the highest test MRR results across all query types. Fine-tuning all model parameters leads to a notable decrease in performance across all query types, affecting the pre-trained link predictor.

Conclusions

In summary, the researchers introduce CQD^A, a novel method for answering complex FOL queries over KGs. The proposed technique significantly improves the MRR compared to the previous state-of-the-art while using a small fraction of the query types during training. The data efficiency of CQD^A is demonstrated by achieving competitive results with only 1% of the training data.

Furthermore, the experiments reveal that CQD^A can generalize to new queries not seen during training while maintaining data efficiency. The results of this work highlight the compositionality and transferability of neural link predictors, opening opportunities for their application in various downstream tasks. Future research can focus on enhancing the learned representations of neural link predictors, benefiting tasks such as clustering, entity classification, and information retrieval.

*Important notice: arXiv publishes preliminary scientific reports that are not peer-reviewed and, therefore, should not be regarded as conclusive, guide clinical practice/health-related behavior, or treated as established information.