PaperlayerView exact revision on arXiv

Source-linked AI summary

GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning

Costas Mavromatis, George Karypis

arXiv:2405.20139v1cs.CLcs.AIcs.LG

TL;DR

KGQA needs retrieval that can handle complex KG structure without feeding LLMs irrelevant or incomplete facts. GNN-RAG uses GNN retrieval to supply reasoning paths to an LLM, achieving state-of-the-art results across WebQSP and CWQ while matching or outperforming GPT-4 with a 7B model.

  • Problem

    KGQA retrieval must handle complex multi-hop graph information, while LLM-based retrievers can underperform or require very large models to compensate for missing information.

  • Method

    GNN-RAG uses a GNN to retrieve answer candidates and shortest KG reasoning paths, verbalizes them, and supplies them to an LLM for RAG reasoning with optional retrieval augmentation.

  • Results

    GNN-RAG achieves state-of-the-art performance on WebQSP and CWQ, with 8.9–15.5% improvement on complex KGQA and performance that matches or exceeds GPT-4 using a 7B tuned LLM.

  • Takeaways & Limitations

    GNN-RAG combines GNN graph processing with LLM language understanding for effective and faithful KGQA without additional LLM calls.

  • Takeaways & Limitations

    GNN retrieval is limited on simple 1-hop questions, where accurate question–relation matching matters more than deep graph search.

Abstract

from arXiv · show

Knowledge Graphs (KGs) represent human-crafted factual knowledge in the form of triplets (head, relation, tail), which collectively form a graph. Question Answering over KGs (KGQA) is the task of answering natural questions grounding the reasoning to the information provided by the KG. Large Language Models (LLMs) are the state-of-the-art models for QA tasks due to their remarkable ability to understand natural language. On the other hand, Graph Neural Networks (GNNs) have been widely used for KGQA as they can handle the complex graph information stored in the KG. In this work, we introduce GNN-RAG, a novel method for combining language understanding abilities of LLMs with the reasoning abilities of GNNs in a retrieval-augmented generation (RAG) style. First, a GNN reasons over a dense KG subgraph to retrieve answer candidates for a given question. Second, the shortest paths in the KG that connect question entities and answer candidates are extracted to represent KG reasoning paths. The extracted paths are verbalized and given as input for LLM reasoning with RAG. In our GNN-RAG framework, the GNN acts as a dense subgraph reasoner to extract useful graph information, while the LLM leverages its natural language processing ability for ultimate KGQA. Furthermore, we develop a retrieval augmentation (RA) technique to further boost KGQA performance with GNN-RAG. Experimental results show that GNN-RAG achieves state-of-the-art performance in two widely used KGQA benchmarks (WebQSP and CWQ), outperforming or matching GPT-4 performance with a 7B tuned LLM. In addition, GNN-RAG excels on multi-hop and multi-entity questions outperforming competing approaches by 8.9--15.5% points at answer F1.

1 Introduction

GNN-RAG addresses KGQA retrieval challenges by combining GNN graph reasoning with LLM language understanding in a RAG framework. It achieves strong benchmark performance while preserving efficient retrieval and reasoning.

  • LLMs understand natural language well but struggle to adapt to new knowledge and can hallucinate because updating pretrained knowledge is costly.
  • RAG grounds KGQA answers in retrieved KG facts, but irrelevant or incomplete retrieval can confuse the LLM on complex graph questions.
  • GNN-RAG uses a GNN to retrieve answer candidates and reasoning paths, then verbalizes those paths for LLM-based RAG reasoning.
  • The framework repurposes GNNs for dense-subgraph retrieval while using the LLM for natural-language reasoning, with retrieval augmentation available to boost performance.
  • 8.9–15.5% improvement: GNN-RAG achieves state-of-the-art results on WebQSP and CWQ for complex KGQA.
  • GNN-RAG improves vanilla LLMs without additional LLM calls and outperforms or matches GPT-4 with a 7B tuned LLM.

2 Related Work

Prior KGQA methods use semantic parsing, graph reasoning, or LLM-based retrieval, but each approach has limitations in handling complex graph information or noisy verbalized context. GNN-RAG combines graph retrieval with LLM reasoning.

  • Semantic-parsing KGQA transforms questions into executable logical queries, but requires costly logical-form annotations and can produce invalid queries.
  • GNN-based methods reason over dense KG subgraphs because they handle complex and multi-hop graph information.
  • Existing work combines language models with graphs either through latent graph information or verbalized graph information inserted into the input.
  • Latent graph methods face language–graph modality mismatch, while verbalized graph methods may retrieve noisy information from large graphs.

3 Problem Statement & Background

KGQA maps a natural-language question to answer entities in a knowledge graph, using a question-specific subgraph and a reasoning model. Existing approaches differ in whether retrieval and reasoning rely on GNNs or LLMs.

  • KGQA extracts answer entities from a KG whose facts are represented as head–relation–tail triples, using question–answer pairs but not ground-truth answer paths for training.
  • Because KGs contain millions of facts, systems retrieve a smaller question-specific subgraph before applying a reasoning model.
  • GNN-based reasoning: GNNs treat KGQA as answer-versus-non-answer node classification and update entity representations by aggregating neighbor messages conditioned on the question.
  • GNN-based reasoning: The GNN update weights relation messages according to their relevance to the question, aggregates them, and combines representations across layers.
  • LLM-based reasoning: LLM-based KGQA converts retrieved graph facts into natural language and supplies them with the question as RAG input.
  • Method landscape: The KGQA landscape contrasts GNNs for dense-subgraph reasoning with LLMs that perform both retrieval and reasoning.
  • LLM-based retrieval: Existing LLM retrievers generate relation paths and map them onto the KG to retrieve intermediate entities for RAG.

4 GNN-RAG

GNN-RAG uses GNNs to retrieve answer candidates and shortest reasoning paths from dense KG subgraphs, then verbalizes those paths for LLM reasoning. Retrieval analysis motivates combining complementary retrievers through retrieval augmentation.

  • Framework: GNN-RAG retrieves answer candidates from a dense KG subgraph, extracts shortest paths from question entities, and verbalizes those paths for LLM-based RAG.
  • GNN retrieval: GNNs are selected because their graph processing and diverse path exploration support retrieval of high-recall multi-hop information.
  • GNN retrieval: After message passing, nodes receive answer probabilities; high-scoring nodes and their connecting shortest paths are returned for RAG.
  • GNN retrieval: Question–relation matching uses representations from a shared pretrained language model, with attention pooling for question representations and [CLS] pooling for relations.
  • GNN retrieval: Different matching language models can produce different retrieved paths, so the framework trains GNN variants using SBERT and LMSR.
  • LLM reasoning: The retrieved paths are verbalized and provided to a tuned LLM, whose prompt asks it to answer using those reasoning paths.
  • Retrieval analysis: Deep GNNs retrieve multi-hop information more effectively and efficiently than an LLM retriever and a shallow GNN on WebQSP.
  • Retrieval analysis: GNN retrieval is limited on simple 1-hop questions, where accurate question–relation matching matters more than deep graph search.

5 Experimental Setup

The experiments evaluate GNN-RAG on WebQSP and CWQ against GNN, LLM, embedding-based, and zero-/few-shot LLM methods. The evaluation includes overall benchmark performance, multi-hop and multi-entity subsets, and efficiency comparisons with LLM-based retrieval.

  • Datasets: WebQSP contains 4,737 questions requiring up to 2-hop reasoning, while CWQ contains 34,699 questions requiring up to 4-hop reasoning.Both benchmarks use questions answerable from a subset of the Freebase KG.
  • Implementation: Subgraph retrieval uses linked entities and PageRank to extract dense graph information, with ReaRev providing the GNN component.The default implementation combines ReaRev with SBERT as the language model in Equation 3; an LMSR variant is also evaluated.
  • Baselines: The comparison includes state-of-the-art GNN and LLM methods, earlier embedding-based methods, and zero-shot or few-shot LLMs.Semantic parsing methods are excluded because they use additional SPARQL annotation training data.
  • Evaluation: Table 2 compares different methods across the two KGQA benchmarks and marks the best and second-best methods.The evaluation reports performance for the benchmark methods included in the comparison.
  • Evaluation: Table 3 evaluates F1 on multi-hop questions with hops≥2 and multi-entity questions with entities≥2.The multi-hop and multi-entity subsets target questions with deeper reasoning or multiple question entities.
  • Evaluation: The study also compares GNN-RAG with LLM-based retrieval approaches in terms of efficiency and effectiveness.This comparison addresses both the quality and resource demands of retrieval-based KGQA systems.

6 Results

GNN-RAG achieves strong KGQA results by combining GNN-based graph retrieval with LLM reasoning, particularly on complex multi-hop and multi-entity questions. Retrieval augmentation further improves performance, while avoiding additional LLM calls and supporting efficient deployment.

  • Overall performance: GNN-RAG+RA outperforms RoG by 5.0–6.1% points at Hit and outperforms or matches ToG+GPT-4 with a 7B LLM.The authors estimate ToG+GPT-4 costs above $800, whereas GNN-RAG can run on a single 24GB GPU.
  • Complex questions: GNN-RAG outperforms RoG by 6.5–17.2% points at F1 on WebQSP and by 8.5–8.9% points at F1 on CWQ for multi-hop and multi-entity questions.GNN-RAG+RA provides an additional improvement of up to 6.5% points at F1.
  • Retrieval efficiency: GNN-based retrieval is more efficient and effective than LLM-based retrieval, especially for complex CWQ questions.The comparison uses LLM calls, input tokens, and F1 as efficiency and effectiveness measures.
  • Retrieval augmentation: Retrieval augmentation works best when combining GNN-induced and LLM-induced reasoning paths because they fetch non-overlapping KG information.The combined paths improve retrieval but increase the number of input tokens.
  • Faithfulness: GNN-RAG retrieves both facts needed for multi-hop answers, whereas the KG-RAG baseline may retrieve only one crucial fact.In a Gilfoyle example, GNN-RAG retrieves the Toronto and Ontario relations required to answer the question.

7 Conclusion

GNN-RAG combines GNN-based graph reasoning with LLM reasoning for RAG-based KGQA. It achieves strong performance while improving efficiency and matching or outperforming GPT-4 with a 7B tuned LLM.

  • Framework: GNN-RAG combines LLM and GNN reasoning in a RAG-based KGQA framework.It also uses retrieval analysis to design a retrieval augmentation technique.
  • Effectiveness & Faithfulness: GNN-RAG achieves state-of-the-art performance on two widely used KGQA benchmarks and retrieves multi-hop information for faithful reasoning.
  • Efficiency: GNN-RAG improves vanilla LLM KGQA performance without additional LLM calls and matches or outperforms GPT-4 with a 7B tuned LLM.

A Analysis

The analysis identifies retrieval quality as central to KGQA reasoning: incomplete subgraphs limit answers, while irrelevant facts must be filtered through effective semantic matching. LLM-based retrieval can trade efficiency for effectiveness when reducing search effort.

  • Analysis: A retrieved subgraph prevents effective reasoning when it lacks information necessary to answer the question.This issue can arise because LLMs are not designed to handle complex graph information.
  • Analysis: 8.3–9.9% points at answer hit are lost when LLM-based retrieval switches from beam-search decoding to greedy decoding.The result illustrates a trade-off between computational efficiency and KGQA effectiveness.
  • Analysis: GNNs require question-relevant semantic matching to filter irrelevant KG facts during reasoning.The analysis attributes this requirement to the GNN sum operator and its inability to understand textual semantics like LLMs.

B Full Theorem & Proof

The theorem analysis formalizes when a GNN can reason over a retrieved subgraph as effectively as over the ground-truth subgraph. The key condition is selective weighting of relevant facts and suppression of irrelevant ones.

  • Theorem setup: The analysis compares GNN reasoning over a retrieved subgraph with reasoning over the ground-truth reasoning subgraph.The ground-truth subgraph contains the necessary reasoning paths leading from question entities to correct answers.
  • Theorem condition: A binary relevance function assigns zero weight to question-irrelevant facts and one weight to ground-truth facts.Neighbor messages are aggregated with a sum operator, while ψ combines representations across GNN layers.
  • Conclusion: The resulting GNN reasoning process over the retrieved subgraph equals the process over the ground-truth subgraph.
  • Proof: Under the stated conditions, irrelevant nodes and relations do not contribute to the reasoning process.The proof treats separately irrelevant nodes and irrelevant relations before combining the two cases.

C Experimental Setup

The experiments evaluate KGQA methods across WebQSP, CWQ, and MetaQA-3 using dense subgraph retrieval, GNN reasoning, and LLM prompting. The setup compares embedding, GNN, LLM, KG-plus-LLM, and GNN-plus-LLM approaches.

  • KGQA Datasets: WebQSP contains 4,737 questions requiring up to 2-hop reasoning, while CWQ contains 34,689 more complex questions requiring up to 4 hops.MetaQA-3 contains more than 100k 3-hop movie-domain questions.
  • Implementation: Dense subgraphs are constructed by PageRank Nibble from linked entities, selecting the top 2,000 entities.
  • Implementation: ReaRev performs GNN reasoning, RoG performs RAG-based prompt tuning, and the methods use suggested hyperparameters without further search.
  • Retrieval: GNN inference ranks answer candidates by softmax-normalized node probabilities and retrieves shortest paths below a cumulative probability threshold of 0.95.NetworkX is used to retrieve shortest paths between question entities and answer candidates.
  • Evaluation: The evaluation covers embedding, GNN, LLM, KG+LLM, and GNN+LLM method categories.

D.1 Question Analysis

The analyses show that GNN-RAG benefits most from graph retrieval that preserves multi-hop connectivity and uses a strong GNN, while retrieval augmentation improves answer coverage and performance across settings.

  • Question complexity: 6.5–11.8% F1 points: GNN-RAG improves multi-hop questions with at least two hops over RoG.Retrieval augmentation further improves single-hop questions by 0.8–2.6% F1 points over GNN-RAG.
  • GNN retrieval: 9.2–9.8% H@1 points: weak GNN retrievers underperform ReaRev, while also trailing RoG by 5.3–5.9% points.The ablation indicates that strong GNNs are required to improve RAG for KGQA.
  • Question complexity: GNN-RAG achieves 98.6% Hit@1 on the 3-hop MetaQA-3 dataset.RoG underperforms because its LLM-based retrieval cannot effectively handle multi-hop KG information.
  • Robustness: GNN-RAG outperforms RoG across the tested input prompts and remains effective with or without KGQA-model fine-tuning.It uses the same or less retriever training data than competing methods.
  • Graph structure: Pruning irrelevant facts can reduce retrieval effectiveness when sparse subgraphs contain disconnected KG parts.In those cases, shortest-path extraction can fail and return empty KG information.

E Limitations

GNN-RAG depends on answer-containing, connected KG subgraphs; upstream linking or extraction errors can prevent correct retrieval, while disconnected graphs can yield empty reasoning paths.

  • Answer coverage: 79.3%: CWQ subgraphs contain an answer, leaving some questions without answer nodes for GNN-RAG retrieval.Entity-linking and neighborhood-extraction errors can produce subgraphs that exclude all correct answers.
  • Graph connectivity: Disconnected KG parts can cause shortest-path extraction to return empty reasoning paths.This prevents the LLM from receiving the KG information needed for faithful answering.
Loading 2405.20139v1…