PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V. Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, Bryan Hooi

arXiv:2402.07630v3cs.LG

TL;DR

Existing graph-LLM methods provide limited support for complex questions over real-world textual graphs. This paper introduces a GraphQA benchmark and G-Retriever, which uses graph-specific retrieval with soft prompting; experiments report stronger multi-domain performance, scalability, and hallucination resistance. The method’s retrieval component is currently static.

  • Problem

    Existing approaches mostly address conventional graph tasks or simple queries on small or synthetic graphs, while comprehensive benchmarks for complex real-world graph question answering are lacking.

  • Method

    G-Retriever combines GNNs, LLMs, soft prompting, and graph RAG that retrieves relevant subgraphs for textual-graph question answering.

  • Results

    G-Retriever surpasses baselines on textual graph tasks across multiple domains, scales effectively with larger graphs, and demonstrates resistance to hallucination.

  • Takeaways & Limitations

    The framework supports conversational interaction with complex textual graphs while selectively retrieving graph information for answering questions.

  • Takeaways & Limitations

    G-Retriever currently employs a static retrieval component; future work could investigate trainable retrieval.

Abstract

from arXiv · show

Given a graph with textual attributes, we enable users to `chat with their graph': that is, to ask questions about the graph using a conversational interface. In response to a user's questions, our method provides textual replies and highlights the relevant parts of the graph. While existing works integrate large language models (LLMs) and graph neural networks (GNNs) in various ways, they mostly focus on either conventional graph tasks (such as node, edge, and graph classification), or on answering simple graph queries on small or synthetic graphs. In contrast, we develop a flexible question-answering framework targeting real-world textual graphs, applicable to multiple applications including scene graph understanding, common sense reasoning, and knowledge graph reasoning. Toward this goal, we first develop a Graph Question Answering (GraphQA) benchmark with data collected from different tasks. Then, we propose our G-Retriever method, introducing the first retrieval-augmented generation (RAG) approach for general textual graphs, which can be fine-tuned to enhance graph understanding via soft prompting. To resist hallucination and to allow for textual graphs that greatly exceed the LLM's context window size, G-Retriever performs RAG over a graph by formulating this task as a Prize-Collecting Steiner Tree optimization problem. Empirical evaluations show that our method outperforms baselines on textual graph tasks from multiple domains, scales well with larger graph sizes, and mitigates hallucination.~\footnote{Our codes and datasets are available at: \url{https://github.com/XiaoxinHe/G-Retriever}}

1 Introduction

The paper targets complex, real-world textual graph question answering through a conversational framework, benchmark, and graph-specific retrieval architecture. G-Retriever addresses scalability and hallucination while supporting diverse graph applications.

  • Existing graph-LLM work largely targets conventional graph classification or simple queries on small or synthetic graphs.
  • The authors introduce a GraphQA benchmark covering common sense reasoning, scene understanding, and knowledge graph reasoning.It is designed to measure progress on complex, real-world graph questions.
  • G-Retriever combines GNNs, LLMs, and RAG to support question answering on large textual graphs.Its conversational interface enables users to interact with graph data through natural-language questions.
  • Selective retrieval addresses token-limit and information-loss problems that arise when large graphs are flattened into text or truncated.
  • Graph-specific retrieval formulates subgraph selection as a Prize-Collecting Steiner Tree optimization problem, incorporating neighborhood information and improving explainability.
  • The paper reports effectiveness across multiple domains, improved scalability, and reduced hallucination in graph question answering.

2 Related Work

Related work spans graph-LLM architectures, graph reasoning and classification, knowledge-graph applications, retrieval-augmented generation, and parameter-efficient fine-tuning. The paper positions general textual-graph retrieval as comparatively underexplored.

  • Graph-LLM research covers general graph models, multimodal architectures, graph reasoning, node classification, graph classification or regression, and knowledge-graph tasks.
  • RAG is used to mitigate hallucination and improve trustworthiness and explainability, but retrieval for general graph tasks remains largely unexplored.
  • Existing graph-oriented retrieval work focuses primarily on knowledge graphs, whereas this paper applies retrieval to general graph tasks.
  • Parameter-efficient fine-tuning includes prompt tuning, prefix tuning, LoRA, and related methods used in multimodal and graph-LLM systems.

3 Formalization

The formalization defines textual graphs, language-model text encoding, LLM prompting, and soft prompt tuning. These components provide the representation and adaptation basis for graph question answering.

  • Textual Graphs: A textual graph contains nodes and edges with textual attributes, represented as G = (V, E, {x_n}, {x_e}).Node and edge texts are sequences drawn from a vocabulary.
  • Language Models for Text Encoding: Language models encode node and edge text attributes into semantic representations for use with textual graphs.For a node, the language model output is z_n, with d denoting the output-vector dimension.
  • Large Language Models and Prompt Tuning: LLMs receive a token sequence and prompt, then generate an output sequence conditioned on the concatenated prompt and input.
  • Large Language Models and Prompt Tuning: Soft prompt tuning learns prompt parameters while keeping the LLM weights fixed.Embedded input tokens and learned prompt embeddings are concatenated before processing by the LLM.

4 Proposed GraphQA Benchmark

GraphQA is a comprehensive benchmark for answering diverse questions about textual graphs, standardizing datasets from commonsense reasoning, scene understanding, and knowledge graph QA.

  • Data Format: GraphQA contains textual graphs, graph-related questions, and one or more corresponding answers.
  • Data Format: Questions target graph elements or relationships, and answers often require multi-hop reasoning to identify information in node or edge attributes.
  • Description of Datasets: The benchmark integrates ExplaGraphs, SceneGraphs, and WebQSP into a uniform data format for graph question answering.These datasets cover commonsense reasoning, visual scene understanding, and multi-hop knowledge graph QA.
  • Description of Datasets: SceneGraphs provides 100,000 scene graphs describing objects, attributes, and image relations for spatial and multi-step question answering.
  • Description of Datasets: WebQSP contains 4,737 multi-hop knowledge graph questions and evaluates the precision of the top returned answer with hit@1.

5 G-Retriever

G-Retriever combines graph retrieval, connected subgraph construction, graph encoding, textualization, and soft-prompted LLM generation for scalable graph question answering.

  • Architecture: G-Retriever indexes graph information, retrieves query-relevant nodes and edges, constructs a manageable connected subgraph, and generates an answer.The framework combines GNNs, LLMs, and retrieval-augmented generation while freezing the LLM for efficient fine-tuning.
  • Indexing and Retrieval: A pretrained language model embeds nodes, edges, and the query, after which nearest-neighbor retrieval selects the most similar graph elements using cosine similarity.
  • Subgraph Construction: Prize-Collecting Steiner Tree retrieval selects a connected subgraph by maximizing relevant node and edge prizes while minimizing edge costs.Higher prizes are assigned to elements more relevant to the query; the edge cost controls the resulting subgraph size.
  • Graph Encoding: A graph attention network encodes the retrieved subgraph, mean pooling produces a graph representation, and an MLP projects it into the LLM hidden space.
  • Answer Generation: The retrieved subgraph is textualized and concatenated with the query, while the projected graph token acts as a trainable soft prompt for a frozen LLM.Gradients update the graph encoder and projection layer through the graph token, while the LLM parameters remain frozen.

6 Experiments

Experiments evaluate G-Retriever across multiple datasets, configurations, efficiency, hallucination, and component ablations. Results show stronger performance, substantial resource reductions, fewer hallucinations, and complementary contributions from retrieval, graph encoding, and textualization.

  • Implementation Settings: The experiments use SentenceBert for indexing node and edge attributes, Llama2-7b for generation, and a Graph Transformer as graph encoder.These implementation choices support the reported experimental configurations.
  • Main Results: G-Retriever outperforms baselines across three datasets and configurations, achieving the best performance when the LLM is tuned with LoRA.With frozen prompt tuning, it improves average performance by 40.6% over traditional prompt tuning and 30.8% over GraphToken.
  • Efficiency Evaluation: 83% fewer tokens, 74% fewer nodes, and 29% less training time are reported for SceneGraphs with graph-based retrieval.For WebQSP, reductions reach 99% in tokens, 99% in nodes, and 67% in training time.
  • Mitigation of Hallucination: G-Retriever reduces hallucinations by 54% versus an LLM with graph prompt tuning when answers must identify supporting graph nodes or edges.The evaluation manually reviews 100 responses from each method and verifies referenced graph elements against the actual graph.
  • Ablation Study: Removing the graph encoder or textualized graph causes performance declines of 22.51% and 19.19%, while graph retrieval also contributes to overall performance.The ablation supports complementary graph representations in embedded and textual formats.

7 Conclusion

The paper introduces a real-world GraphQA benchmark and G-Retriever for complex textual-graph questions. Experiments report stronger cross-domain task performance, scalability, and resistance to hallucination, while future work is needed for trainable retrieval.

  • Conclusion: G-Retriever surpasses baselines on textual graph tasks across multiple domains, scales with larger graph sizes, and demonstrates resistance to hallucination.These results summarize the paper’s reported experimental outcomes.
  • Conclusion: The paper’s GraphQA benchmark targets real-world graph question answering, while G-Retriever supports complex and creative queries.The benchmark and architecture are presented as the work’s central contributions.
  • Limitations and Future Work: G-Retriever currently uses a static retrieval component, motivating future investigation of more sophisticated trainable retrieval.This is the stated limitation and future-work direction.
  • Conclusion: The work aims to improve graph interaction while resisting hallucination and enhancing explainability through retrieved subgraphs and conversational interfaces.The paper connects graph retrieval with graph highlighting and conversational interaction.

B.1 Implementation Settings

The implementation evaluates inference-only, frozen-LLM prompt tuning, and LoRA-tuned configurations using graph encoders, textualized graphs, retrieval, and ablations. Additional studies examine encoder robustness and the effect of LLM scale.

  • Model Configurations: The inference-only configuration gives a frozen LLM the textual graph and question for direct question answering.This configuration corresponds to Figure 4.
  • Model Configurations: Prompt-tuning experiments include soft prompt tuning, GraphToken, and G-Retriever with the LLM parameters frozen.These configurations correspond to Figure 5.
  • Model Configurations: LoRA-tuned experiments compare standard LLM fine-tuning with G-Retriever using LoRA.These configurations correspond to Figure 6.
  • Ablation Study: Ablations remove or replace the graph encoder, projection layer, and textualized graph to assess individual pipeline components.The ablation configurations are summarized in Figure 7.
  • Additional Studies: GraphTransformer, GAT, and GCN provide closely aligned WebQSP results, while GraphTransformer reaches 0.8516 Hit@1 on ExplaGraphs.The reported WebQSP Hit@1 scores are 70.70, 70.27, and 70.49 for GCN, GAT, and GraphTransformer, respectively.
  • Additional Studies: Using Llama2-13b instead of Llama2-7b improves G-Retriever effectiveness, indicating benefits from increased LLM scale.The comparison is reported on WebQSP.

C GraphQA Benchmark

GraphQA standardizes data from ExplaGraphs, SceneGraphs, and WebQSP into a unified graph-question-answering format. Processing converts original triplet or JSON representations and applies dataset-specific preparation steps.

  • Benchmark Construction: The benchmark integrates ExplaGraphs, SceneGraphs, and WebQSP after standardizing them into a uniform data format.These datasets are reused with a graph question answering focus.
  • ExplaGraphs: ExplaGraphs triplets are converted so each head and tail becomes a node and each relation becomes an edge.Because test labels were unavailable, training and validation data were repartitioned into training, validation, and test subsets.
  • SceneGraphs: SceneGraphs uses scene graphs from GQA rather than image counterparts and converts JSON descriptions into standardized graph representations.The source dataset contains 108k images associated with scene graphs, while this benchmark focuses on graph question answering.
  • WebQSP: WebQSP triplet lists are transformed into the unified graph format using preprocessing steps from RoG3.The dataset processing also lowercases words and preserves the original dataset split.

D.1 Comparison with Existing GraphRAG Methods

G-Retriever retrieves connected subgraphs for general textual graphs, unlike prior triple-level GraphRAG methods. Its PCST-based retrieval accounts for graph structure and supports efficient, query-relevant context selection.

  • Retrieval comparison: G-Retriever targets general textual graphs and returns query-related subgraphs rather than isolated top-k triples.This preserves neighborhood information that triple-based retrieval may miss.
  • Retrieval comparison: Small k values can omit relevant information, whereas large k values may distract the model with excessive context.The experiments vary k across 3, 5, 10, and 20.
  • Retrieval comparison: Hit@1 rises initially with k, peaks, and then declines as k becomes large.The text recommends selecting k through validation techniques such as cross-validation.
  • Retrieval comparison: Cosine similarity is used for fast retrieval as a general and representative vector-similarity measure.The authors acknowledge that cosine similarity may not be optimal.
  • Retrieval comparison: PCST-based retrieval is more accurate than KAPING’s triple-based retrieval because it selects connected subgraphs with bridge elements.Graph RAG can also eliminate 99% of WebQSP nodes, reducing runtime from 18.7 to 6.2 min/epoch.

E.2 Computational Resources

The experiments use two 80GB A100 GPUs to evaluate Llama2-7b on WebQSP. Graph RAG substantially reduces graph size and lowers training time.

  • Computational resources: Experiments use two A100 GPUs with 80GB of memory each, Llama2-7b, WebQSP, batch size 16 for training, and 32 for evaluation.These settings define the reported computational environment.
  • Computational resources: Graph RAG improves efficiency by substantially reducing the graph size before processing.On WebQSP, it eliminates 99% of nodes.

F Hallucination in Graph LLMs

The hallucination study evaluates whether graph elements cited in answers are valid. G-Retriever substantially improves node, edge, and complete-graph citation validity over graph prompt tuning across graph-questioning examples.

  • Experimental setup: The baseline adapts MiniGPT-4 by pairing a frozen LLM with a trainable GNN that encodes graph data as a soft prompt.Graph-to-text conversion is avoided because textual graph representations exceed LLM input limits.
  • Experimental setup: Faithfulness is measured by valid-node, valid-edge, and fully valid graph rates.The fully valid measure requires the entire cited node-edge set to be valid.
  • Hallucination results: 77% node validity, 76% edge validity, and 62% overall cited-set validity are achieved by G-Retriever.The comparison is reported as a substantial reduction in hallucinations when citing both nodes and edges.
  • Demonstrations: Creative interactions are demonstrated on ExplaGraphs, SceneGraphs, and WebQSP through tables and graph visualizations.The examples include open-ended requests such as argument writing and image-assisted scene-graph visualization.
Loading 2402.07630v3…