Neural Logical Index for Fast Knowledge Graph Complex Query Answering

Authors: Weizhi Fei, Zihao Wang, Hang Yin, Shukai Zhao, Wei Zhang, Hanghang Tong, Yangqiu Song
Primary area: learning on graphs and other geometries & topologies
Keywords: complex logical query, knowledge graph, query embedding, neural link predictor

Abstract:
Complex query answering (CQA) over knowledge graphs is a crucial multi-hop reasoning task aimed at addressing first-order logical queries within large and incomplete knowledge graphs. Direct traversal search methods rely solely on graph topology and often miss answers due to the incompleteness of the graph, thus neural models have been proposed to generalize the neglected answers from observed facts. There are primarily two lines of research tackling the challenges of CQA. Query embedding models learn representations for complex queries, offering fast speed but often providing only generic performance. In contrast,  neural symbolic search methods deliver better performance, although they tend to be computationally more expensive. In this paper, we propose an efficient and scalable search framework that combines the precision of symbolic methods with the speed of embedding techniques. Our model utilizes embedding methods to compute Neural Logical Indices (NLI) to reduce the search domain for each variable in advance, followed by an approximate symbolic search for fine ranking. The search is precise for tree-structured queries and approximates cyclic queries (which are NP-complete) in quadratic complexity concerning the search domain, matching the complexity of tree-form queries. Experiments on various CQA benchmarks show that our framework reduces computation by 90% with a minimal performance loss, alleviating both efficiency and scalability issues.

Decision: reject
Reviewer scores: 8, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1730653660537

thread_type:
official_review

<thread_object>
creator: reviewer_ecua

<content>
summary:
The paper addresses the challenge of efficiently answering complex queries over large and incomplete knowledge graphs (KGs). The authors propose a novel framework that combines the speed of embedding methods with the precision of symbolic search approaches. Their method introduces Neural Logical Indices (NLI) to preemptively reduce the search domain using embedding-based techniques. The framework approximates cyclic queries in quadratic complexity, achieving significant efficiency gains with minimal performance loss. Experiments across multiple benchmarks demonstrate the scalability and performance of their approach.

strengths:
1. The method reduces computation costs by 90%, significantly improving efficiency with minimal performance loss.
2. It is scalable to larger knowledge graphs, handling orders of magnitude more entities than traditional methods.
3. The introduction of Neural Logical Indices effectively narrows the search domain, making symbolic computation more feasible.
4. It achieves a good balance between the precision of symbolic search and the speed of embedding methods for tree-form queries.

weaknesses:
1. 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.
2. 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.
3. The integration of local and global constraints in the framework adds a layer of implementation complexity. This could present challenges during practical deployment, requiring sophisticated engineering and optimization efforts to ensure seamless functionality.
4. While the framework achieves competitive results, it still falls short of the performance of state-of-the-art models in certain scenarios. This performance gap indicates room for further refinement, particularly in enhancing the handling of complex and cyclic queries to match or surpass the best-performing methods available.

questions:
See the Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730702966398

thread_type:
official_review

<thread_object>
creator: reviewer_bmby

<content>
summary:
This paper addresses the limitations of current approaches to complex query answering, particularly query embedding and neural symbolic search methods. While query embedding methods offer speed, they often suffer from lower performance. Conversely, neural symbolic search methods achieve strong performance but are computationally demanding.
The proposed approach seeks to combine the strengths of both methods, aiming to provide high performance with efficiency. It does this by leveraging surrounding constraints for each query variable to reduce the search space. In one strategy, termed local constraints, embedding models determine constraints via relation tail prediction, based on the variable's connection to the relation. In another strategy, called global constraints, a broader set of constraints is applied across the entire query to further limit the domain.
The resulting framework, Neural Logical Index for Search Approximately (NLISA), can handle both tree and cyclic queries in a scalable way. Extensive experiments across multiple CQA datasets demonstrate NLISA's effectiveness and efficiency compared to several baseline models.

strengths:
– The problem targeted in this paper (enhance the scalability of CQA methods while obtaining a good performance) is a valid and an important ongoing problem existing in the literature of CQAs. 

– the paper is well written in terms of motivation and problem statement.

– The proposed approach can handle several query types including cyclic ones where many previous works did not handle.

weaknesses:
– 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. 

– 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.

– Scalability remains a significant challenge in the embedding and complex query answering (CQA) domains. Even studies that claim to improve scalability often use only small datasets for evaluation. Given years of advancements in model development, it is expected that models claiming improved scalability would be trained and tested on large-scale datasets. However, most datasets used in this field are quite small. In this paper, even the largest dataset, used to demonstrate model scalability, contains only 400,000 entities—far fewer than real-world knowledge graphs, which often have over 90 million entities.

questions:
Why GNN-QE is not included in table 1?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720475747

thread_type:
official_review

<thread_object>
creator: reviewer_p8gq

<content>
summary:
This paper introduces a new knowledge graph complex query answering method called NLISA, featured by computationally fast. It is a neural-symbolic framework with local and global constraints. Experiments on the benchmarks show that the NLISA framework could reduce computation by 90% with a minimal performance loss.

strengths:
1. This paper studies an important problem of fast knowledge graph complex query answering, which could benefit the development of the knowledge graph complex query answering methods. 
2. The proposed fast knowledge graph complex query answering method is efficient that could reduce the computation by 90%.

weaknesses:
1. The main method is hard to understand. After reading, I find it is not clear how the neural logical indices are achieved. 
2. Some method and experiment details are missing(refer to question 3 and 4 ). 
3. 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.

questions:
1. 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. 
2. The $\top$ in Equation (3) and (4) is hard to understand. Does the $\top$ represents operations between the truth values?  How should we interpret the Equation (3) and (4)? 
3. What are the entity embedding and relation embedding from equation in line 244 from? is it pre-trained by some methods? 
4. How the hyper-network are train? What data are used for the training?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745007716

thread_type:
official_review

<thread_object>
creator: reviewer_fobd

<content>
summary:
This paper proposes a novel framework called Neural Logical Index for Search Approximately (NLISA) to tackle the problem of complex query answering over large and incomplete knowledge graphs. The framework leverages the speed of embedding-based methods and the precision of symbolic search methods by reducing the search domain using neural logical indices computed via embedding techniques. This allows for an efficient and scalable approximate search mechanism, particularly for cyclic queries which are traditionally NP-complete. Experiments on various benchmarks demonstrate that the proposed method achieves significant computation reduction with minimal performance loss.

strengths:
1. The combination of embedding-based and symbolic search methods in a novel framework that reduces the search domain using neural logical indices is a creative approach to the existing challenges in complex query answering.
2. The method is well-designed with details on how the neural logical indices are computed using local and global constraints strategies. The framework is theoretically grounded and empirically evaluated on multiple benchmarks.
3. The paper is well-structured and clearly explains the motivation, approach, and results. Definitions, figures, and tables are used effectively to aid comprehension.
4. The proposed method addresses the critical issues of efficiency and scalability in symbolic search methods, demonstrating its potential for real-world applications involving large knowledge graphs.

weaknesses:
This work is solid. 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.

questions:
Section 3.2 Why to choose hypernetwork? How sensitive are the results to the choice of embedding model used for computing the neural logical indices? Would different embedding techniques lead to significant variations in performance? The embedding model seems to be related to the caching issue.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732094968261

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
First General Response to All Reviews

comment:
We would like to thank the reviewers for their insightful comments. We believe your suggestions have improved our paper. In the following, we present the changes made to the revision which are marked in Brown. We have also clarified some misunderstandings regarding common questions. 
1. We corrected `the typos of the AVG(P) result for NLISA (local) in FB15K`, as discussed below.
2. We rewrote part of Section 3 to `clarify the definition and computation of neural logical indices`.
3. We updated Fig. 2 to enhance the clarity of our examples.
4. We provide `details about the hypernet in Appendix E`, including its rationale for usage and training process.
5. We updated the details of the functions in the search algorithms in Appendix C, which helps the reader learn the algorithm.
6. We revised the details regarding the computation of truth values in the symbolic representation construction in Appendix D.


Additionally, we identified some misunderstandings that we would like to clarify regarding common questions. We address  `the typos in Table 2 of the main text ` that many reviewers have pointed out. We also provide  `details about the hypernet `, including its usage rationale and training process. 


## Typos in Table 2 of the main text
  
We apologize for the typos in reporting the AVG(P) result for NLISA (local) on positive queries in FB15K, which mistakenly included the average of all query types, including negation queries. The correct result is `63.4, not 55`, and we have verified that there are no other similar mistakes.  In fact, only this AVG(P) was incorrect, while the results for the other query types remain unchanged. Additionally, our code is available in the abstract, allowing for the results to be reproduced. We hope this correction addresses your concerns regarding NLISA (local).
  
## Why Use Hypernet?
Relation tail prediction is fundamentally similar to knowledge graph completion (KGC) tasks, as both involve inferring missing tails from a knowledge graph. In KGC, the query is presented in the form of (h, r, ?), to predict the tail t. In contrast, relation tail prediction aims to predict the tail t given the relation r. This similarity makes the embedding methods used in KGC equally applicable to relation tail prediction.
  
Hypernet[1] is employed to dynamically generate weights, allowing the model to automatically adjust representations for new tasks. This facilitates the sharing and adaptation of weights across different tasks. By adopting the embeddings [2] from KGC, Hypernet enhances the utilization of existing knowledge and enables quicker adaptation to relation tail prediction. Additionally, Hypernet requires only a few parameters, improving performance while reducing training costs and storage needs.
  
## How Is Hypernet Trained?
  
The training process is similar to that of KGC, with the exception that each triple (h,r,t) is replaced with (r,t). This requires only minor modifications compared to the existing KGC framework[3].

[1] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference on machine learning, pp.2071–2080. PMLR, 2016.

[2] Yihong Chen, Pasquale Minervini, Sebastian Riedel, and Pontus Stenetorp. Relation prediction as an auxiliary training objective for improving multi-relational graph representations. In 3rd Conference on Automated Knowledge Base Construction, 2021. URL https://openreview.net/forum?id=Qa3uS3H7-Le.

[3] David Ha, Andrew M. Dai, and Quoc V. Le. Hypernetworks. ArXiv, abs/1609.09106, 2016. URLhttps://api.semanticscholar.org/CorpusID:208981547.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a framework called Neural Logical Index for Search Approximately (NLISA) to tackle the problem of complex query answering over large and incomplete knowledge graphs. It utilizes embedding methods to compute Neural Logical Indices (NLI) to reduce the search domain for each variable in advance, followed by an approximate symbolic search for fine ranking.

While the reviewers see some merits in the work (e.g., an important problem and the computational efficiency of the proposed method), some critical issues should be addressed. The initial submission contained too many typos, errors, and unclear explanations, which led to substantial updates during the discussion phase. Clarifying the details seems to require several more rounds. Also, the authors should include larger datasets than those used in the current manuscript. Finally, performance is being sacrificed by improving efficiency. There should be a better balance between efficiency and performance.