Neural Logical Index for Fast Knowledge Graph Complex Query Answering

Dear reviewer, we really appreciate your thorough and constructive feedback. We believe your suggestions have improved our paper. We first want to address your weakness for improvement and then answer your question.

The following are the rebuttals to your weakness.

In general, the local version of the model obtain lower performance than state of the art models. For example, on FB15K, the results are very low (approx 55) comparing to other models which obtain approx 72. Thus the scalability is obtained with the cost of substantial performance loss for local model.

We apologize for the typos regarding the AVG(P) results on the FB15K dataset of BetaE benchmark. The actual result is 63.4, not 55, as previously stated in the first general response. NLISA is a general framework that can flexibly extract the subgraph structure surrounding the variables and estimate their domains. Though NLISA (local) only considers the neighbor, it offers advantages in efficiency, deployment, and scalability.

NLISA (local) utilizes relational constraints from first-order neighbor subgraphs, eliminating the need to train query embedding models. Both knowledge graph embeddings and hypernetworks required for NLISA (local) can be easily trained using well-established knowledge graph embedding frameworks. This framework only requires relation facts in the knowledge graph for pre-training, making it significantly more efficient than the query embedding framework, which necessitates sampling queries along with positive and negative answers as training data. Additionally, NLISA provides an ablation study on the considered query structures, highlighting the importance of subgraph selection.

while the paper is written well in terms of problem statement and motivation, the technical details of the approach requires further and better explanation. Moreover, some acronyms should be defined before the first usage to improve the clarity of the paper, e.g., EFO1.

Thank you for your kind reminder. We have included the full name of EFO1 at its first mention in line 74, and we will ensure to avoid similar issues in the future. We have rewritten part of Section 3 to clarify the definition and computation of neural logical indices, presenting an example of the local version constraints in Figure 2. Additionally, we provided further details on the neural logical indices used in REMOVECONSTNODE and REMOVELEAFNODE in Appendix C. Additionally, we have provided further details on the computation of truth values, and implementation in Appendices D and E. We hope these updates enhance the clarity of our method.

We thank you for your time and review. However, there seem to be some core misunderstandings about our presentation that we would like to clarify.

The following are the rebuttals to your weakness.

The main method is hard to understand. After reading, I find it is not clear how the neural logical indices are achieved.

We apologize for any misunderstandings regarding the main methods. We have rewritten part of Section 3 to clarify the definition and computation of neural logical indices, presenting an example of the local version constraints in Figure 2. Additionally, we provided further details on the neural logical indices used in REMOVECONSTNODE and REMOVELEAFNODE functions in Appendix C. We hope these updates enhance the clarity of our method.

Some method and experiment details are missing(refer to question 3 and 4 ).

We provide our response to the below rebuttal to questions 3 and 4.

Though the NLISA is efficient but the complex query answering performances of NLISA are suboptimal. Table 1 shows the NLISA(local) is more efficient that achieves the best efficiency results. But most of the task performance of NLISA(local) in Table 2 are worse than FIT method. Especially the AVG(P) results on FB15k datasets is significantly worse.

We apologize for the typos regarding the AVG(P) results on the FB15K dataset. The actual result is 63.4, not 55, as previously stated in the first general response.

NLISA is a general framework that can flexibly extract the subgraph structure surrounding the variables and estimate their domains. Though NLISA (local) only considers the neighbor, it offers advantages in efficiency, deployment, and scalability.

NLISA (local) utilizes relational constraints from first-order neighbor subgraphs, eliminating the need to train query embedding models. Both knowledge graph embeddings and hypernetworks required for NLISA (local) can be easily trained using well-established knowledge graph embedding frameworks. This framework only requires relation facts in the knowledge graph for pre-training, making it significantly more efficient than the query embedding framework, which necessitates sampling queries along with positive and negative answers as training data. Additionally, NLISA provides an ablation study on the considered query structures, highlighting the importance of subgraph selection.

The following are the rebuttals to your questions.

In Figure2, should the query graph represent the query “Fine someone who is married to a person who graduated from the same institution”? Since the in the triples (x1, Graduate, y) and (x1, Graduate, x2), the head entity refers to the same variable x1.

The triple (x1, Graduate, y) has the negation, thus the query is “Fine someone who is married to a person who graduated from the same institution”? We updated Fig 2 to change the Graudate with not Graudate in the figures. We hope this change can clear the presentation of examples.

The ⊤ in Equation (3) and (4) is hard to understand. Does the ⊤represents operations between the truth values? How should we interpret the Equation (3) and (4)?

Yes, ⊤ represents fuzzy logical operations between truth values, with a detailed definition provided in Line 186 and Appendix G. Equation (3) rewrites the logical query from Boolean variables to truth values, allowing logical queries to be addressed using knowledge graph embeddings rather than searching over a discrete knowledge graph. By leveraging knowledge graph embeddings to compute symbolic representations, it becomes possible to find difficult answers. Equation (4) presents the cut domain version of Equation (3).

What are the entity embedding and relation embedding from equation in line 244 from? is it pre-trained by some methods?

We feel sorry for this misunderstanding. The entity embedding and relation embedding from the equation in line 244 are reused from the embedding of query embedding models, where the resume refers to the introduction in hypernet. We have updated the statement in Lines 246-248.

How the hyper-network are train? What data are used for the training?

Thank you for your question, we present the details in a first general response to all reviews and also present the details in Appendix E.

We thank you for your time and review. We believe your suggestions have improved our paper. However, there seem to be some core misunderstandings about our major claim that we would like to clarify.

The following are the rebuttals to your questions.

Even with the efficiency improvements, the framework incurs some performance loss when handling more complex cyclic queries. This limitation could affect use cases where high accuracy on intricate query patterns is essential.

Thank you for raising the dicussion of complex cyclic queries. Our contribution, in comparison to FIT, lies in developing efficient algorithms while maintaining comparable performance, which improves the QPS of cyclic queries by nearly 35-40 times, as shown in the following table.

FIT should be regarded as the upper bound of our framework since its search algorithms are optimal for the perfect symbolic representation. However, FIT suffers from significant complexity issues, particularly with exponential complexity in cyclic queries. As shown in the QPS results for FB15k-237 in Table 1, cyclic queries (3c and 3cm) are nearly 30 times slower than other types, and this issue worsens as the size of the knowledge graph increases, resulting great scalability trouble. Thus, our framework was proposed to address efficiency and scalability, as demonstrated in the table below, which shows that our framework reduces the QPS of cyclic queries by nearly 35-40 times, making their QPS comparable to that of other query types. To ensure a fair comparison, we utilize the same pre-trained model with identical checkpoints. Given the same symbolic representation capabilities, it is overly ambitious to expect an approximate solving algorithm to outperform FIT on cyclic queries while achieving a tenfold reduction in the search domain. Attaining 95% performance is already a satisfactory result.

Table 1: Queries Per Second on the Real EFO1 Benchmark (FB15K-237)

Overall, regarding cyclic queries, our framework achieves a 35-40 times improvement in QPS while maintaining 95% performance compared to FIT. We believe that the considerations of efficiency and scalability discussed in our paper offer valuable insights for the development of CQA models.

The method’s dependency on embedding-based approaches may limit its adaptability and generalizability across different query types or diverse knowledge graph structures. Variability in embedding quality could impact overall performance and effectiveness.

During the execution of query embedding methods, we will project unseen query types into tree-form queries that have been thoroughly trained for query embedding.

When applying query embedding to address unseen query types, our framework first constructs an approximated operator tree by removing certain edges from the original query graph to simplify it into a tree-form query. The modified query is then transformed into this approximated operator tree. The original answers are included in the approximated operator tree because they satisfy the simplified constraints. As a result, query embedding models encode the approximated operator tree instead of directly encoding the unseen query types, demonstrating robustness across different query types. You can review the results of the query embedding models for ten unseen query types in Table 3 of the main text.

The query embedding is just used for the rough rank and just needs to recall the answers in the search domain where the search domain is not small; thus, the requirements for query embedding methods are minimal. Additionally, the strong performance of NLISA (global) on the real EFO1 datasets, as shown in Table 3, supports these arguments, given that the ten query types are new to the query embedding models used.

Thank you for the feedback.

However, there are some misunderstanding regarding of FIT.

For CQA tasks, FIT-like CQA methods already reduce processing time significantly compared to traditional query methods because of the embedding characteristic.

FIT is NOT an embedding method; rather, it is a symbolic method that does not reduce processing time but significantly rise processing time compared to query embedding. We list the complexity of each operation for different models in the below Tab.1, which shows that FIT have much more time complexity than query embedding methods like ConE/BetaE and that's the reason why FIT can perform better than query embedding. Furthermore, the number of operation executions for cyclic queries grows exponentially, which causes significant challenges. Overall, FIT suffers from significant efficiency issues and face OOM trouble in below Tab.2. Our method address the efficiency issues and support the KG with 400,000 entities, which show our scalability.

Table 1 Time complexity of each set operation and answer retrieval. We denote E and R as the number of entities and relations, the embedding dimension and hidden dimension of MLPs as $d$, number of layers of MLPs/GNNs as $l$, number of branches in an intersection operation as $i$, the beam size as $k$, number of branches in a union operation as $u$.

Table 2 Averaged MRR results(%) on large KG with 400,000 entities of different methods.

Thank you for your valuable feedback!

First, the SOTA symbolic search method, FIT, suffers from significant efficiency issues. Its query complexity for cyclic queries is exponential, while its data complexity is quadratic relative to the number of entities in the knowledge graph. Additionally, FIT results in very slow processing times for cyclic queries due to this high complexity and cannot process cyclic queries in parallel. When handling 60,000 entities, it have to use float16 to reduce memory usage even for a 32GB GPU, which leads to substantial scalability challenges. Therefore, it is essential to develop efficient symbolic methods to address these efficiency and scalability concerns. Our method achieves a 35-fold improvement in efficiency metrics for cyclic queries on FB15k-237 and can scale to knowledge graphs with 400,000 entities. Our framework supports larger knowledge graphs, and the efficiency improvements for cyclic queries can be further enhanced when handling larger datasets.

Second, the performance of current SOTA symbolic search methods, such as FIT, is not poor. These symbolic search methods enhance the quality of pre-trained knowledge graph embedding models [1] and calibration strategies [2], with QTO [1] and CKGR [2] achieving a 25% improvement over Avg.(P) on FB15k-237. We utilize older knowledge graph embedding models solely for fairness in evaluation. Furthermore, the current evaluation is undervalued because the evaluated "hard answers" do not encompass all the “hard answers” in true real-world situation. Research [3] conducted under the open-world assumption demonstrates that the mean reciprocal rank (MRR) metric performs better than traditional evaluations. In this context, the open-world assumption means that unknown triplets are considered to include many missing facts that are not present in the training or test sets, resulting in a more realistic setting.

[1] Bai, Y., Lv, X., Li, J., & Hou, L. (2023, July). Answering complex logical queries on knowledge graphs via query computation tree optimization. In International Conference on Machine Learning (pp. 1472-1491). PMLR.

[2] Xiao C, Cao Y. Complex Logical Query Answering by Calibrating Knowledge Graph Completion Models[J]. arXiv preprint arXiv:2410.07165, 2024.

[3] Yang H, Lin Z, Zhang M. Rethinking knowledge graph evaluation under the open-world assumption[J]. Advances in Neural Information Processing Systems, 2022, 35: 8374-8385.

Thank you for your response. Query Embedding essentially addresses the efficiency of regular graph query searches using vector representations. However, its performance remains poor, generally below 50%. Therefore, improving its performance is more critical than further reducing its efficiency.

Dear reviewer, we would like to express our gratitude for your time and valuable feedback. Below is our point-by-point response to your questions.

Maybe the authors could discuss more about the caching issue mentioned in appendix line 797, which is suggested to be presented in the main body of the paper if the issue really exists.

Regarding your concerns about the caching issue, we complemented more details in Appendix D, where introduce how caching is used and why caching works. Since the page limit of the main body of the paper, we present the details in the Appendix and provide a reference to the main body.

Section 3.2 Why to choose hypernetwork?

Regarding your questions about hypernet, please refer to the first general response to all reviews and we also present it in Appendix E.

How sensitive are the results to the choice of embedding model used for computing the neural logical indices?

The neural logical indices are not sensitive to the choice of embedding model because the domain size is sufficiently large. We will include an ablation study on the choice of embedding models in the revised paper.

Would different embedding techniques lead to significant variations in performance?

In our approach, the local version uses knowledge graph embeddings to compute the neural logical indices, while the global version adapts the query embeddings. You can refer to the comparison between the local and global versions for insights into performance variations. The results indicate that the global version achieves better overall performance, while the local version demonstrates better efficacy. This demonstrates that our framework can benefit from the development of embedding models.

The embedding model seems to be related to the caching issue.

The caching issue arises from the construction of the symbolic representation. We have provided further details in Appendix D.

Recent discussion raise the concerns regarding to the efficiency trouble and we want to classify its existence and importance.

We first present the complexity of each operation for different methods in Table 1. The table demonstrates that the state-of-the-art symbolic search method, FIT, requires significantly more computation than embedding methods like ConE and BetaE. Furthermore, FIT suffers from exponential complexity $O(E^q)$ for cyclic queries, where $E$ is the entities number and $q$ is the size of query graph.

We then illustrate the efficiency challenges with detailed examples. Table 2 shows that FIT processes cyclic queries 30 times slower than other query types, while our method reduces the processing time for cyclic queries by a factor of 35. Additionally, Table 3 highlights FIT's struggles with out-of-memory issues, whereas our method performs well with a knowledge graph containing 400,000 entities.

Table 1 Time complexity of each set operation and answer retrieval. We denote E and R as the number of entities and relations, the embedding dimension and hidden dimension of MLPs as $d$, number of layers of MLPs/GNNs as $l$, number of branches in an intersection operation as $i$, the beam size as $k$, number of branches in a union operation as $u$.

Table 2 Averaged MRR results(%) on large KG with 400,000 entities of different methods.

Table 3 Averaged QPS results on FB15k-237 with 14,000 entities.