G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering

We thank the reviewer very much for the careful reading and comments regarding our work. Please, see below our answer to the raised comments/questions.

Reviewer: In Section 5.1 (Indexing), the authors use a pre-trained LM to encode the text attributes of nodes and edges into representations. However, there is no ablation study to demonstrate the importance of the node attributes or the text attributes, which leaves an unexplored gap in understanding the contribution of these features to the overall performance of the G-Retriever.

Authors: The text attributes in G-Retriever play a critical role in three main areas: (1) Retrieval: Node and edge embeddings are used to select the top-k nodes and edges based on their semantic similarity to the query embedding. (2) GNN Input: These embeddings are fed into the GNN, which processes the graph structure and refines the embeddings to capture more complex relationships within the graph. (3) LLM Input: The retrieved subgraph is textualized and used as input for the LLM to generate answer.

To address the reviewer’s concern, we have conducted an ablation study to assess the contribution of these features.

Reviewer: In Section 5.3 (Subgraph Construction), the authors use PCST to obtain a more refined subgraph. However, the motivation for selecting PCST is not clearly explained. Is PCST the optimal for this task? How the "optimally sized and relevant subgraphs" are defined? At least the authors could consider to justify this by comparing some naive approaches, such as fixed number or fixed similarity threshold.

Authors: Due to the character limit, we kindly refer the reviewer to our general response “G2: Elaboration on PCST-Based Retrieval”, where we have addressed this question in detail.

Reviewer: The claim of the new benchmark is somewhat weak, as it primarily involves the reintroduction of an existing dataset. Additionally, the contributions related to the QA formulation and graph reformatting are limited.

Authors: Due to the character limit, we kindly refer the reviewer to our general response “G1. Contribution of the GraphQA Benchmark”, where we have addressed this question in detail.

Reviewers: The evaluation of hallucinations lacks sufficient detail and requires further elaboration.

Authors: Thank you for your feedback. Due to space constraints, the detailed evaluation of hallucinations is provided in Appendix F. Here, we offer a summary:

• Experiment Design. We instructed the LLM to answer graph-related questions and list the nodes or edges in the explanation graph that support its answers. Since there are no standard answers, evaluating the LLM’s responses becomes challenging. To address this, we manually examined 100 responses generated by both our method and a baseline method (LLM with graph prompt tuning) to verify whether the referenced nodes and edges actually exist in the graph.
• Evaluation Metrics. We assessed the model’s faithfulness using three metrics: the fraction of valid nodes (Valid Nodes), the fraction of valid edges (Valid Edges), and the fraction of times the entire set of nodes and edges cited was valid (Fully Valid Graphs).
• Baseline. We adapted MiniGPT-4 [57] to graph contexts as our baseline, using a frozen LLM with a trainable GNN that encodes graph data as a soft prompt (LLM+Graph Prompt Tuning). We focused on graph prompt tuning due to the large size of the textual representation of the graph, which often exceeds the input token limits of LLMs.
• Results. As shown in Table 5, G-Retriever outperforms the baseline in reducing hallucinations. The baseline method showed only 31% valid nodes, 12% valid edges, and 8% fully valid node-edge sets. In contrast, G-Retriever achieved 77% validity in nodes, 76% in edges, and 62% overall validity in node-edge sets. These results highlight the effectiveness of G-Retriever in accurately referencing graph elements and significantly reducing hallucinations.

We will ensure that these points are clearly elaborated upon in the revised manuscript for better understanding.

Thank you very much for your time reviewing our answer.

We thank the reviewer very much for the careful reading and comments regarding our work. Please, see below our answer to the raised comments/questions.

Reviewer: The framework seems to mainly work for larger graphs. For tasks with smaller graphs, such as the ExplaGraphs dataset with an average node number of 5.17, it is unnecessary to use such a framework. The performances of G-retrieval and GraphToken are nearly the same for the ExplaGraphs dataset.

Authors: We acknowledge that G-Retriever and GraphToken demonstrate similar performance on the ExplaGraphs dataset, which consists of small graphs. As noted by the reviewer, other techniques like GraphToken can be employed effectively on this dataset. However, our aim in applying G-Retriever to ExplaGraphs dataset was to highlight the flexibility and effectiveness of the proposed technique across a wide range of graph sizes. This versatility is particularly advantageous in datasets like SceneGraphs, where graph sizes, although small (averaging 19.1 nodes) and varying significantly (ranging from 1 to 126 nodes with a standard deviation of 8.3). For these small-scale graphs, G-Retriever significantly outperforms GraphToken, achieving 0.8131 accuracy compared to 0.4903, as reported in Table 5. Additionally, G-Retriever offers extra benefits, such as a flexible conversational interface. As shown in Figure 1, G-Retriever can generate an essay based on a given explanation graph. We believe that this versatile question-answering capability adds substantial value beyond just accuracy.

Reviewer: After the subgraph is retrieved, is it possible to use neuro-symbolic methods (e.g. answer set programming or graph search) instead of using a graph encoder together with an LLM? It would be more efficient and cost much less.

Authors: Thank you for the insightful suggestion. While neuro-symbolic methods such as answer set programming or graph search can indeed offer efficiency and cost-effectiveness, they generally require a predefined specification of patterns, i.e. symbols, to guide the search process. In our graph QA scenario, the patterns are highly dependent on the query, which can vary significantly in complexity, making it challenging to effectively predefine these patterns. However, we acknowledge that for specific applications where patterns can be clearly defined, neuro-symbolic approaches could be a viable alternative and are certainly worth exploring in future work.

We wish to thank the reviewer very much for the careful reading and comments regarding our work. Please, see below our answer to the raised comments/questions.

Reviewer (W1 & Q1): Explanation on “chat with their graph”

Authors: By “chat with their graph,” we mean that users can interact with the graph through a conversational interface. Users can input a textual graph and pose natural language queries, to which G-Retriever will respond in natural language. For example, as shown in Figure 1, if a user provides a mindmap-like explanation graph and requests an argument essay, G-Retriever can generate the essay accordingly. This feature enhances human-AI interaction, making the model more intuitive and aligned with human expectations. We will clarify and elaborate on this concept in the main sections of our revised manuscript.

Reviewer (W2 & Q2): Explainability of G-Retriever

Authors: We believe G-Retriever enhances explainability in the following ways:

• Retrieved subgraph. By returning the most relevant subgraph in response to a query, users can see which parts of the graph are considered important for the answer. This helps users understand the basis of the model’s responses. For example, if users want to understand why certain information is present or absent in the LLM’s response, they can inspect the subgraph to see whether such information is present or absent in the retrieved subgraph.
• Conversational Interface. G-Retriever allows users to ask follow-up questions and receive detailed natural language explanations. For example, if a user questions the LLM’s response, they can ask, “Why do you think [xxx]? Please explain your answer.” This interactive capability enables users to explore the model’s reasoning process and gain deeper insights into how it interprets graph data.

We will include specific examples in the revised version of our manuscript to illustrate the two explainability properties mentioned above.

Reviewer (W3): Novelty of GraphQA benchmark

Authors: Due to the character limit, we kindly refer the reviewer to our general response “G1: Contribution of the GraphQA Benchmark”, where we have addressed this question in detail.

Reviewer (W4 & Q3): PCST and alternative retrieval methods

Authors: Due to the character limit, we kindly refer the reviewer to our general response “G2: Elaboration on PCST-Based Retrieval”, where we have responded to this question in detail.

Retriever (W5 & Q4): Quality of the retrieved subgraphs

Authors: We quantify the quality of our retrieval method as follows:

We examine the retrieval subgraph; if the label is contained within it, we consider it a successful retrieval. We calculate the retrieval success rate of our method and the retrieval method proposed in KAPING [1] on the WebQSP dataset. The results are as follows:

• Hit@1 accuracy for [KAPING with top-k triple retrieval] is 60.81%.
• Hit@1 accuracy for [Ours with PCST-based subgraph retrieval] is 67.87%.

This demonstrates the effectiveness of our method.

Reviewer (W6): Efficiency evaluation

Authors: We conducted additional experiments on the WebQSP dataset comparing inference times of G-Retriever with and without retrieval:

Despite additional steps, G-Retriever is faster (9.55 vs. 21.01 minutes) and more accurate (70.49% vs. 63.84%). The speedup is due to:

• PCST subgraph construction is very efficient. For instance, in the WebQSP dataset, even the largest subgraph (2,000 nodes, 6,104 edges) takes only 0.29 seconds to construct.
• PCST retrieval reduces the graph size significantly, eliminating up to 99% of nodes in the WebQSP dataset, which in turn speeds up inference time.

Reviewer (W7): Experimental details

Authors: In Table 5, we assessed the model’s faithfulness using three metrics: the fraction of valid nodes (denoted as Valid Nodes), the fraction of valid edges (denoted as Valid Edges), and the fraction of times the entire set of nodes and edges cited was valid (denoted as Fully Valid Graphs). As recommended, we will update the table captions in our revised manuscript to include this information.

Regarding the hallucination evaluation in section 6.4, the manual examination was conducted by the authors. We will develop the following points:

1. Necessity of Manual Evaluation: Since standard answers are not available for these questions, the LLM’s responses are inherently flexible. This flexibility, along with the varied output formatting, makes automatic evaluation difficult, necessitating manual review.

2. Objectivity in Determining Hallucinations: The determination of hallucinations is based on objective criteria. For example, in Table 1, in the response from “LLM w/ Graph Prompt Tuning,” it is stated: “ The animal in the bushes is a deer. Nodes: * Deer (node 1), * Bushes (node 2); Edges: * Deer → Bushes (edge 1) * Deer → Grass (edge 2) * Bushes → Grass (edge 3)”. The fraction of “valid nodes” is 1/2 = 0.5, as “Bushes” exists in the scene graph while “Deer” does not. The fraction of “valid edges” is 0/3 = 0, since none of the mentioned edges exist in the scene graph. As there are hallucinated nodes and edges, this is not a “fully valid graph.”

3. Transparency and Bias Mitigation: We recognize the importance of transparency and minimizing bias in our evaluation process. To address potential concerns, we will open-source the model outputs used for these manual checks, allowing for public scrutiny and verification.

Reviewer (W8): The texts in Figure 1 and Figure 2 are too small to read.

Authors: We will enlarge the text in Figures 1 and Figure 2 to enhance readability in our next manuscript.

We would like thank the reviewer very much for the careful reading and comments regarding our work. Please, see below our answer to the raised comments/questions.

Reviewer: I think several baselines are missing: (1) Simply feed the retrieved top-k nodes/edges (plus its neighbors) to the LLM would be able to show the effectiveness of PCST.

Authors: To demonstrate the effectiveness of PCST, we compared it to a similar baseline, KAPING [1]. KAPING retrieves the top-k triples related to the question from the graph, adds them to the input question as a prompt, and then sends this to LLMs to generate the answer. In addition to KAPING, we included the following baseline methods to address the reviewer's concern:

• Top-k nodes plus their neighbors: For each query, For each query, the top-k nodes and their one-hop neighbors are retrieved.
• Shortest path retrieval: This approach involves retrieving the top-k nodes and the shortest paths between them. For all methods, we set k = 5 and used llama2-7b-chat as the LLM. The results are presented in the table below, where we observed that our PCST-based retrieval outperforms the baseline retrieval methods, achieving an accuracy of 66.17 on the WebQSP dataset.

Reviewer: (2) It would be helpful to understand the generation model by replacing the tuned generation model to a fixed LLM like GPT4, Claude, etc.

Authors: To address this concern, we conducted additional experiments by replacing the tuned generation model with fixed LLMs on the WebQSP dataset. Specifically, we first applied the PCST retrieval to obtain the subgraph, then converted it into text and fed it into the fixed LLMs along with the query. We considered two fixed LLMs: the open-source llama2-7b-chat and the closed-source GPT-4. The results are summarized in the table below:

As the results indicate, G-Retriever outperforms both fixed LLM baselines. This demonstrates the effectiveness of our approach in the tuned generation model.

Reviewer: When encoding the nodes and edges, the context of the nodes/edges is missing, it could be beneficial to include the context (e.g., adjacent nodes)

Authors: Thank you for your observation. In our indexing step, we use a pre-trained language model (LM) to encode the text attributes associated with each node and edge into embeddings. Although we do not explicitly include the context, such as adjacent nodes, during this initial encoding, we address this in the generation step. Specifically, our framework incorporates a graph neural network (GNN) component designed to aggregate information from adjacent nodes and update the node and edge representations based on the graph context. This approach allows us to effectively capture and use the context during the generation phase. Therefore, while the context is not directly included in the initial encoding, it is integrated later in the process through the GNN, ensuring that the contextual information is considered in the overall framework.

Reviewer: Table captions should be more informative so that they are easier to understand (e.g., In Table5, what metrics are used?)

Authors: Thank you for the suggestion. In Table 5, we assessed the model’s faithfulness using three metrics: the fraction of valid nodes (denoted as Valid Nodes), the fraction of valid edges (denoted as Valid Edges), and the fraction of times the entire set of nodes and edges cited was valid (denoted as Fully Valid Graphs). As recommended, we will update the table captions in our revised manuscript to include this information.

Reference

[1] Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering, 2023.