Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models

Authors: LINHAO LUO, Zicheng Zhao, Gholamreza Haffari, Chen Gong, Shirui Pan
Primary area: foundation or frontier models, including LLMs
Keywords: large language models, knowledge graphs, reasoning

Abstract:
Large language models (LLMs) have demonstrated impressive reasoning abilities, but they still struggle with faithful reasoning due to knowledge gaps and hallucinations. To address these issues, knowledge graphs (KGs) have been utilized to enhance LLM reasoning through their structured knowledge. However, existing KG-enhanced methods, either retrieval-based or agent-based, encounter difficulties in accurately retrieving knowledge and efficiently traversing KGs at scale. In this work, we introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs. To eliminate hallucinations, GCR ensures faithful KG-grounded reasoning by integrating KG structure into the LLM decoding process through KG-Trie, a trie-based index that encodes KG reasoning paths. KG-Trie constrains the decoding process, allowing LLMs to directly reason on graphs and generate faithful reasoning paths grounded in KGs. Additionally, GCR leverages a lightweight KG-specialized LLM for graph-constrained reasoning alongside a powerful general LLM for inductive reasoning over multiple reasoning paths, resulting in accurate reasoning with zero reasoning hallucination. Extensive experiments on several KGQA benchmarks demonstrate that GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training.

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

Reviews and discussion:
<thread>
creation date:
1729172987006

thread_type:
official_review

<thread_object>
creator: reviewer_spbz

<content>
summary:
This paper proposes a graph-constrained reasoning (GCR) framework to enable LLMs to produce faithful reasoning and reduce hallucinations. The key idea of GCR is to convert vanilla KG into a KG-trie and enable LLMs to perform graph-constrained decoding. Experiments on various KGQA reasoning benchmarks and several LLMs demonstrate the effectiveness of the proposed GCR.

strengths:
1. The conversion of a KG into KG-trie and the introduction of graph-constrained decoding are reasonable.

2. Extensive experiments on the various KGQA benchmarks demonstrate the effectiveness of GCR.

3. The results of zero-shot generalizability for reasoning on unseen KGs are interesting.

weaknesses:
1. What is the time cost of the construction of a KG-trie? Furthermore, since the construction of a KG-trie is query-dependent, the offline pre-constructed KG-trie strategy may not be effective when a new input query is introduced. Additionally, the beam search method for constructing a KG-trie may be time-consuming.

2. Real-world KGs are often incomplete and contaminated. Therefore, when entities are absent from the KG or when the reasoning paths generated by Figure 3 (Lines 220-228) contain unreliable logical pathways, how does GCR work? Will GCR still contribute positively to the results under these circumstances?

3. The results of the zero-shot generalizability improvement in Table 6 for MedQA are not particularly significant. I am curious about the additional time cost associated with implementing GCR compared to vanilla ChatGPT and GPT-4o-mini.

4. The authors may want to discuss or summarize more KG-enhanced methods for reducing knowledge  hallucinations including [A, B].

[A] Chain-of-Verification Reduces Hallucination in Large Language Models. ACL 2024 Findings.

[B] Coarse-to-Fine Highlighting: Reducing Knowledge Hallucination in Large Language Models. ICML2024.

questions:
1. The reasoning path in a KG-trie may consist of multiple paths. In cases where several valid reasoning paths exist within the KG-trie, how does GCR operate?

2. Given that the knowledge stored in KGs often exhibits redundancy, can we ensure that all generated reasoning paths are strongly relevant to the question posed? Is there a risk of introducing irrelevant information?

3. In line 917, the beam size is set to 10 for graph-constrained decoding. Is the beam size sensitive to graph-constrained reasoning, and if so, what aspects of GCR are influenced by the beam size?

4. If a KG is temporal and dynamic, how can the pre-constructed KG-trie strategy be effectively employed?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730448383179

thread_type:
official_review

<thread_object>
creator: reviewer_hr19

<content>
summary:
This paper introduces Graph-Constrained Reasoning (GCR) that stores KG paths in a Trie structure as constraints to guide the decoding process of LLMs and only generates reasoning paths that are valid in KGs. GCR combines a lightweight KG-specialized LLM for graph-constrained reasoning with a powerful general LLM for inductive reasoning, achieving good performance and zero-shot generalization on various KGQA benchmarks.

strengths:
1. The motivation is clear and the proposed method is technically sound.

2. The manuscript is well-organized and easy to follow.

3. Extensive experiments have verified the effectiveness of the proposed method.

weaknesses:
1. Preprocessing all paths appears to be both costly and potentially redundant. Could you discuss the space complexity involved in this process? Additionally, how do you plan to control the length of the reasoning paths to optimize efficiency?

2. Instead of using a Trie to constrain the LLM step by step, what are the implications of performing a post-validation with graph querying for the beam-search paths? How do these two approaches differ in terms of time and space complexity?

3. Given that the proposed method has achieved zero reasoning hallucination, analysing the error cases would provide deeper insights and make the results more convincing. Could you include such an analysis in the discussion?

questions:
Please refer to Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730654876493

thread_type:
official_review

<thread_object>
creator: reviewer_rwhg

<content>
summary:
The paper introduces graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs. To eliminate hallucinations, GCR ensures faithful KG-grounded reasoning by integrating KG structure into the LLM decoding process through KG-Trie, a trie-based index that encodes KG reasoning paths.

strengths:
The approach is interesting. 
The experiments show strong results. The paper is well written though the organization of the approach description can be improved.

weaknesses:
1. The authors should give some cases in which GCR has a Faithful Reasoning Path and RoG does not. The key reason that GCR outperforms RoG was not fully explained. RoG seems a simplified version of GCR.

2. The tokenizer-level decoding method may lead to entities or relationships that cannot be recognized in KGs, which in turn invalidates the model. Meanwhile, the tokenizer-level decoding will remarkably 
 increase the runtime compared to the methods of the same type (see Table2).

3. Is the definition of faithful reasoning in section 5.2 sound? This definition is a bit broad since some wrong paths can also lead to right answers as many papers point out. 


4. The construction of KG-trie is still time-consuming and takes up space if you want to cover all the questions.

questions:
1. The motivation for using BFS and Tokenizer in E.4 is not clear. Can use DFS and word-level Tokenizer work?

2. The authors used simple scenarios in their experiments, but is the model as efficient as it claims when there are many candidate paths and it takes multiple hops to reach the target entity?

3. Can the author analyze the reasons for unfaithful reasoning in GCR and give some examples?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730690449464

thread_type:
official_review

<thread_object>
creator: reviewer_thqb

<content>
summary:
This paper proposes graph-constrained reasoning (GCR). GCR integrates KG structure into the LLM decoding process through KG-Trie, a trie-based index that encodes KG reasoning paths. It leverages a lightweight KG specialized LLM for graph constrained reasoning alongside a powerful general LLM for inductive reasoning over multiple reasoning paths.

strengths:
1, The proposed method achieves the 100% faithful reasoning. All the supporting reasoning paths can be found on KGs as shown in Figure 5.

2, The proposed method requires less average LLM tokens and small numbers of LLM calls during inference as shown in Table 2.

weaknesses:
1, The construction of KG-Trie may be computationally expensive in the pre-processing. Although the inference of the proposed method is efficient, the overhead of the preprocessing seems time-consuming. The BFS in formula 3 extract all 
-length edges around the 
 in the preprocessing stage. In a large graph with millions of entities and edges, this will be expensive. These steps (formula 3-5) need to be done for every entity since we do not know the query entity in advance. In this paper authors choose 
. In multi-hop reasoning on KGs a larger 
 is needed which brings more preprocessing overhead. Can the authors explain the time complexity of preprocessing with both theoretical analysis and empirical results?

2, Missing graph reasoning baselines. In the experiments in Table 1 the graph reasoning baselines are included. However, some SOTA link prediction GNN methods like NBFNet[1] and ULTRA[2] are not in the table. These methods can be applied on Freebase and ConceptNet and should be included.

3, Experiments on more datasets are needed to show the superiority of the proposed method. In Table 1 only two datasets WebQSP and CWQ are included. On CWQ, GCR performs well. However on WebQSP, GCR only shows a small margin over GNN-RAG + RA. In Table 6 only two datasets CSQA and MedQA are includes. And the improvements on MedQA is not signifcant. More experiments on more datasets will make the proposed method more convincing.

[1] Zhu, Zhaocheng, et al. "Neural bellman-ford networks: A general graph neural network framework for link prediction." Advances in Neural Information Processing Systems 34 (2021): 29476-29490. 

[2] Galkin, Mikhail, et al. "Towards foundation models for knowledge graph reasoning." arXiv preprint arXiv:2310.04562 (2023).

questions:
Please refer to the questions mentioned in the Weaknesses part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731887503443

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General reply to all reviewers about the efficiency of KG-Trie construction: Part 1

comment:
We sincerely appreciate your thorough reviews and valuable feedback on our submission. We have noted your primary concerns regarding the efficiency and preprocessing overhead of constructing the KG-Trie. Below, we provide a comprehensive response to address these points and clarify our approach. Specifically, we first analyze the time and space complexity of KG-Trie construction. Then, we introduce several strategies to further improve efficiency and support real-world billion-scale KGs.

## Motivations of KG-Trie construction

Large language models (LLMs) have demonstrated remarkable reasoning capabilities through token-by-token decoding. However, the unstructured nature of LLMs poses challenges for conducting efficient reasoning over structured knowledge graphs (KGs). The KG-Trie addresses this challenge by converting KG structures into the format that LLMs can handle. It has been incorporated into the LLM decoding process as constraints, allowing for faithful reasoning paths that align with the graph’s structure.

## KG-Trie Construction Strategies

**We want to clarify that there is no need to build a KG-Trie for all entities in KGs.** The KG-Trie can be either pre-computed for fast inference or constructed on-demand to minimize pre-processing time. Users can choose to build the KG-Trie offline, allowing them to be used during inference at no additional cost. Alternatively, **we can only retrieve the question-related subgraphs around the question entities and construct a question-specific KG-Trie on-demand.** In experiments, we only construct the KG-Trie for entities mentioned in questions. Users can also develop their own strategies (e.g. dynamic cache) to balance pre-processing and inference overhead.  We have clarified our discussion about KG-Trie construction in Section 4.2 and Section 5.1 of the revision, and present a framework of cache-based KG-Trie construction in Appendix B.

## Time and Space Complexity of KG-Trie Construction

As discussed, it is not necessary to construct KG-Trie for all entities in KGs. Thus, we want to highlight that the time and space complexity for KG-Trie construction is affordable and can be easily improved in industry-level applications to support billions of scale graphs. To support this, we provide detailed theoretical analysis and empirical evidence.

**Theoretical Analysis**

* **Time Complexity**: Constructing the KG-Trie involves a BFS traversal to explore paths up to a maximum length of $L$ starting from certain entities. The time complexity of this traversal is $O(E^{L})$, where $E$ is the average number of edges per entity, and $L$ is the maximum path length. BFS ensures that all reachable paths up to length $L$ are considered. However, BFS can be replaced with other efficient graph-traversing algorithms, such as random walk \[1\] to further improve efficiency.  
* **Space Complexity:** The space complexity of the KG-Trie depends on the number of unique paths and their tokenized representations. In the worst case, the space complexity is $O(E^L \\times T)$, where $T$ represents the average number of tokens per path. Trie structures are efficient for storing shared prefixes, which reduces redundancy and optimizes memory usage. Moreover, it supports efficient traversal of reasoning paths in constant time.

**Empirical Analysis**

We have provided the average BFS running time and space consumption of the KG-Trie construction to demonstrate its efficiency. 

System settings:

- CPU: Intel(R) Xeon(R) Silver 4214R CPU @ 2.40GHz.  
- Memory: 32G.  
- BFS implementation: Virtuoso SPARQL  
- Space storage: Pickle

In the experiment, we build the KG-Trie for all question entities of WebQSP dataset and measure the average running time and space consumption. The BFS is executed on the Freebase KG stored in a Virtuoso database. We retrieve the $L$-hop paths, then save the constructed KG-Trie with Pickle. The statistics show that both running time and space usage are acceptable, which highlights efficiency in KG-Trie construction. The results are also presented in Table 7 of Appendix B.2.2 in the revision.

Although a larger hop can lead to better coverage of the possible answer, it would significantly increase the time and space complexity. Thus, we set hops to 2 or 3 in experiments to balance between efficiency and effectiveness. Notably, time can be further reduced by utilizing multi-threading. Space consumption can be optimized by storing data in a database.

Average running time and space utilization of the KG-Trie construction.

| Hop | Avg. Running Time (s) | Space (Mb) |
| :---- | :---- | :---- |
| L=1 | 0.0058 | 0.4 |
| L=2 | 0.0133 | 0.5 |
| L=3 | 0.0219 | 2.5 |

\[1\] Xia, Feng, et al. "Random walks: A review of algorithms and applications." IEEE Transactions on Emerging Topics in Computational Intelligence 4.2 (2019): 95-107.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731890698507

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers

comment:
We appreciate the detailed feedback from all reviewers. We have revised the paper accordingly, with edits highlighted in **BLUE**, and included detailed responses below. Here, we summarize the major revisions and address each comment. We hope our responses address your concerns.

1. To address the concerns of all reviewers regarding KG-Trie construction efficiency, we have carefully clarified our discussion in Sections 4.2 and 5.1 of the revision. We also presented a detailed complexity analysis, empirical studies, and a framework of cache-based KG-Trie construction in Appendix B.
2. To address reviewer tHQb's comments, we have revised the experiment results in Table 1 by adding more GNN-based graph reasoning baselines.
3. To address reviewer tHQb's comments, we have revised the zero-shot experiments in Table 6 of Section 5.4 by extending them to additional datasets: FreebaseQA.
4. To address the comments of reviewers rwhg and SPbz, we have added analyses about the performance of GCR under multi-path explorations and multi-hop reasoning in Appendix F.2 and F.3, respectively.
5. To address the comments of reviewers rwhg, hR19, and SPbz, we have added analyses about the failure cases predicted by GCR in Appendix F.4 to further discuss the limitations and future directions.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Graph-constrained reasoning (GCR) is introduced to integrate knowledge graph (KG) structure into the LLM decoding process. It leverages a KG-specialized LLM for graph-constrained reasoning and a general LLM for inductive reasoning over multiple reasoning paths. To alleviate hallucinations, GCR utilizes KG-grounded reasoning by imposing KG structure into the LLM decoding process through KG-Trie, a trie-based index encoding KG reasoning paths.

While some reviewers acknowledged that the paper is well-written and the approach is reasonable, there are shared concerns about the paper:\
(1) The KG-trie construction process is inefficient and time-consuming.\
(2) The proposed method's advantages are not significantly distinct from other retrieval-based methods.\
(3) It is hard to ensure that all generated reasoning paths are strongly relevant to the question. There can be a risk of introducing irrelevant information.\
(4) Given that real-world KGs are often incomplete and contaminated, a more elaborated method should be presented to show how the proposed method works when entities are absent from the KG or when the reasoning paths generated contain unreliable logical pathways.

Additional Comments:\
The authors claimed, "To eliminate hallucinations, GCR ensures faithful KG-grounded reasoning." On the other hand, the authors also argue that "Thus, based on the internal knowledge of powerful LLMs, we can filter out the irrelevant path." This sounds like the authors are only taking upsides of KGs and LLMs, which is too optimistic; the authors say KGs are used to eliminate LLMs' hallucinations, while LLMs filter out irrelevant paths on KGs. What happens if KG's irrelevant paths fail to eliminate hallucinations and LLMs' hallucinations fail to filter out irrelevant paths on KGs?