PaperlayerView exact revision on arXiv

Source-linked AI summary

Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation

Mufei Li, Siqi Miao, Pan Li

arXiv:2410.20724v4cs.CLcs.IRcs.LG

TL;DR

KG-based RAG aims to ground LLM answers in graph knowledge, but effective retrieval must find relevant multi-hop evidence efficiently and fit within LLM context limits. SubgraphRAG retrieves adjustable subgraphs with a lightweight MLP and parallel triple scoring, then prompts unfine-tuned LLMs to reason over them. The authors report competitive results from smaller models and state-of-the-art results from larger models, alongside reduced hallucination through grounded answers and explanations.

  • Problem

    KG-based RAG must efficiently retrieve relevant, multi-hop graph evidence while keeping retrieved context within LLM reasoning capacity.

    Source: §1 · p. 2

  • Method

    SubgraphRAG uses a lightweight MLP with parallel triple scoring and structural-distance features to retrieve adjustable subgraphs for unfine-tuned LLM reasoning.

    Source: §1 · p. 3

  • Results

    SubgraphRAG achieves competitive performance with Llama3.1-8B-Instruct and state-of-the-art results with GPT-4o without fine-tuning on WebQSP and CWQ.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors report robust multi-hop reasoning, cross-dataset generalization despite domain shifts, and reduced hallucination through knowledge-grounded answers and explanations.

    Source: §1 · p. 3

    Iterating the process for questions too challenging for the approach is beyond the scope of this work.

    Source: §1 · p. 3

Abstract

from arXiv · show

Large Language Models (LLMs) demonstrate strong reasoning abilities but face limitations such as hallucinations and outdated knowledge. Knowledge Graph (KG)-based Retrieval-Augmented Generation (RAG) addresses these issues by grounding LLM outputs in structured external knowledge from KGs. However, current KG-based RAG frameworks still struggle to optimize the trade-off between retrieval effectiveness and efficiency in identifying a suitable amount of relevant graph information for the LLM to digest. We introduce SubgraphRAG, extending the KG-based RAG framework that retrieves subgraphs and leverages LLMs for reasoning and answer prediction. Our approach innovatively integrates a lightweight multilayer perceptron with a parallel triple-scoring mechanism for efficient and flexible subgraph retrieval while encoding directional structural distances to enhance retrieval effectiveness. The size of retrieved subgraphs can be flexibly adjusted to match the query's need and the downstream LLM's capabilities. This design strikes a balance between model complexity and reasoning power, enabling scalable and generalizable retrieval processes. Notably, based on our retrieved subgraphs, smaller LLMs like Llama3.1-8B-Instruct deliver competitive results with explainable reasoning, while larger models like GPT-4o achieve state-of-the-art accuracy compared with previous baselines -- all without fine-tuning. Extensive evaluations on the WebQSP and CWQ benchmarks highlight SubgraphRAG's strengths in efficiency, accuracy, and reliability by reducing hallucinations and improving response grounding.

1 INTRODUCTION

KG-based RAG can ground LLM answers, but retrieving useful graph evidence is difficult when queries require multi-hop reasoning, retrieval must be efficient, and LLM context is limited. SubgraphRAG uses a lightweight retriever to select flexible, adjustable subgraphs for LLM reasoning; the authors report competitive performance from smaller models and state-of-the-art results from larger models without fine-tuning.

1 INTRODUCTION

  • LLMs can hallucinate, rely on outdated knowledge, or lack domain expertise, while RAG seeks to ground their outputs in external knowledge.The cited motivation presents RAG as a strategy for mitigating these trustworthiness concerns.Source: §1 · p. 1
  • KG retrieval must find nonlocal entities connected by multi-hop, semantically relevant relations, since complex questions can require reasoning beyond entities named in the query.Subgraphs can represent this evidence for downstream reasoning.Source: §1 · p. 2
  • Practical KG-based RAG must efficiently retrieve relevant structure for online queries and dynamic KG updates while meeting latency requirements.Approximate nearest-neighbor methods are not suitable for structure extraction.Source: §1 · p. 2
  • Retrieved evidence must cover what answers require while fitting LLM reasoning capacity; oversized contexts can add irrelevant information and degrade performance.The passage links this risk to the “lost in the middle” phenomenon and argues for pruning redundant structure.Source: §1 · p. 2
  • Existing KG-based RAG approaches can trade off complexity, retrieval coverage, and reasoning ability, while fixed-form subgraphs may restrict evidence coverage.Some approaches use multiple LLM calls for iterative search; lighter retrieval-and-reasoning models are more efficient but have inferior reasoning capabilities.Source: §1 · p. 2
  • For questions too challenging for the described process, iteration is proposed as a possible extension but is outside this work’s scope.The authors frame lightweight retrieval and LLM reasoning as a division of labor that balances model complexity with reasoning capability.Source: §1 · pp. 2–3
  • SubgraphRAG pairs a lightweight MLP and parallel triple scoring with structural distances from query topic entities, then lets unfine-tuned LLMs reason over adjustable subgraphs.The framework is intended to balance retrieval efficiency and effectiveness while accommodating different LLM capacities.Source: §1 · p. 3
  • SubgraphRAG is evaluated on WebQSP and CWQ, where Llama3.1-8B-Instruct is competitive and GPT-4o achieves state-of-the-art results without fine-tuning.The authors also report robust multi-hop reasoning, cross-dataset generalization despite domain shifts, and reduced hallucination through knowledge-grounded answers and explanations.Source: §1 · p. 3

2 PRELIMINARIES

A knowledge graph represents facts as directed triples, and KG-based RAG retrieves relevant triples for an LLM to answer a query. In KG question answering, complex questions require multiple triples as evidence and therefore multi-hop reasoning.

2 PRELIMINARIES

  • A knowledge graph is a set of directed triples (head, relation, tail), whose entities and relations may have text surface forms for LLM reasoning.The head and tail are entities, and the relation expresses a directed fact between them.Source: §2 · p. 3
  • KG-based RAG gives LLMs access to relevant KG triples, with the challenge of finding them efficiently in a large graph and reasoning accurately.The query is denoted q in the passage.Source: §2 · p. 3
  • Entity linking identifies query-involved topic entities, which guide retrieval because relevant triples are often nearby in the graph.The topic entities are denoted Tq.Source: §2 · p. 3
  • In KGQA, complex questions require multiple KG triples as evidence to identify answer entities, unlike single-hop questions.KGQA questions impose constraints that candidate answers must satisfy.Source: §2 · p. 3

3 THE SUBGRAPHRAG FRAMEWORK

SubgraphRAG retrieves a size-adjustable subgraph before asking an LLM to reason over it. Its retrieval design combines triple-wise scoring with directional structural information, while prompting grounds answers and explanations in the retrieved evidence.

3 THE SUBGRAPHRAG FRAMEWORK

  • SubgraphRAG extracts a query-relevant subgraph within an adjustable size constraint, then prompts an LLM to reason over it and produce a grounded answer with explanations.The size can be selected to match the downstream LLM's capacity.Source: §3 · p. 3, §3.2 · pp. 5–6

3.1 EFFICIENT, FLEXIBLE AND EXPRESSIVE SUBGRAPH RETRIEVAL

  • Training on heuristic surrogate subgraphs lets the retriever learn from question-answer pairs without requiring the computationally hard optimal subgraph.Shortest paths between topic and answer entities are one example of surrogate evidence; the learned distribution factorizes over triples, allowing flexible subgraph forms and sizes.Source: §3.1 · p. 4
  • Directional Distance Encoding represents structural relationships between triples and topic entities, with entity encodings concatenated into triple encodings for retrieval.The encoding uses feature propagation in both graph directions; the paper reports DDE performing best among compared encoding options.Source: §3.1 · p. 5
  • A lightweight MLP scores triples using question and entity-relation text embeddings together with their structural encodings.Precomputed text embeddings are stored in a vector database, while the MLP classifies concatenated semantic and structural inputs.Source: §3.1 · p. 5

3.2 PROMPTING-BASED LLM REASONING

  • In-context prompt demonstrations guide the LLM to reason over retrieved triples and generate explanations, without fine-tuning the LLM.The appropriate retrieval size depends on the LLM's context window and ability to reason over long contexts.Source: §3.2 · pp. 5–6

4 EXPERIMENTS

SubgraphRAG is evaluated on WebQSP and CWQ for retrieval and KGQA, including retrieval-size, structural-design, and reasoning-capacity analyses. It performs strongly across benchmarks, with results varying by dataset, LLM, and retrieval setting.

4 EXPERIMENTS

  • The evaluation covers WebQSP and CWQ, both based on Freebase, and measures retrieval recall and wall-clock time alongside KGQA performance and truth-grounding.The sub-benchmarks remove samples whose answer entities are absent from the KG; retrieval-time measurements exclude KG query time.Source: §4 · p. 6, §4.1 · p. 7, §4.2 · p. 8

4.1 EVALUATION FOR RETRIEVAL (Q1 & Q2)

  • SubgraphRAG consistently outperforms other retrieval approaches, while RoG’s recall on GPT-4o-labeled triples drops by 45.6% on WebQSP and 52.2% on CWQ.SubgraphRAG’s recall changes by only -2.0% on WebQSP and +3.6% on CWQ; it is slightly slower than cosine similarity on WebQSP and one to two orders of magnitude faster than other baselines.Source: §4.1 · p. 7
  • On CWQ, larger retrieval sizes uniformly improve recall across variants, while DDE-equipped SubgraphRAG outperforms other variants even at smaller baseline-sized retrieval budgets.Topic-entity indicators improve results, GNN variants often underperform their MLP counterparts, and PPR does not reliably improve performance; WebQSP results are reported as consistent.Source: §4.1 · pp. 7–8, Figure 4 · p. 8
  • SubgraphRAG consistently outperforms other methods on WebQSP and achieves the best overall CWQ performance, with advantages on multi-hop and multi-topic questions.The cosine-similarity baseline and RoG perform competitively on single-hop questions but degrade significantly on multi-hop questions; SubgraphRAG is superior across single-topic and multi-topic CWQ metrics.Source: §4.1 · p. 8

4.2 KGQA RESULTS (Q3 & Q4)

  • SubgraphRAG achieves state-of-the-art results on WebQSP and WebQSP-sub; with GPT-4o, it ranks second only to ToG on CWQ, while CWQ-sub gains reach ≤9% Macro-F1 and ≤11% Hit.Source: §4.2 · p. 9
  • Across-dataset evaluation shows moderate performance decay that can largely be mitigated by retrieving more triples, with decay generally more pronounced on CWQ and CWQ-sub.The authors suggest greater label leakage from the WebQSP test set into CWQ training as a possible reason for the larger decay.Source: §4.2 · p. 9
  • Replacing baseline retrievers with SubgraphRAG’s retriever improves performance on all reported metrics and datasets under the same prompts and LLM reasoners.For some baselines, the evaluation uses all retrieved triples; other cases use 100 triples.Source: §4.2 · p. 10, Table 6 · p. 10
  • More retrieved triples significantly reduce Llama 3.1 8B performance but improve GPT-4o-mini performance, indicating that retrieval size should match the reasoner and available inference budget.The reported upper bound treats an answer as correct if its entity appears among retrieved results.Source: Figure 4 · p. 8, §4.2 · p. 10

5 CONCLUSION

SubgraphRAG pairs flexible subgraph retrieval with unfine-tuned LLM reasoning and is reported to perform better or comparably to existing approaches in accuracy, efficiency, and explainability. The related work discusses directional distance encoding and contrasts SubgraphRAG with earlier KGQA and subgraph-retrieval approaches.

5 CONCLUSION

  • SubgraphRAG performs better or comparably to existing approaches in accuracy, efficiency, and explainability while prompting unfine-tuned LLMs over retrieved subgraphs.Source: §5 · p. 10

A DIRECTIONAL DISTANCE ENCODING (DDE)

B ADDITIONAL RELATED WORK

  • Earlier KGQA methods used PLMs, GNNs, LSTMs, or LLMs translating questions to SPARQL; later work used LLMs for KG retrieval and reasoning, often with multiple calls.Source: B ADDITIONAL RELATED WORK · p. 18
  • Subgraph-reasoning approaches use varied retrieval strategies, while SubgraphRAG claims advantages in retrieval efficiency, adjustable subgraph sizes, and flexible subgraph types.Source: B ADDITIONAL RELATED WORK · pp. 18–19

C.1 ADDITIONAL IMPLEMENTATION AND EVALUATION DETAILS

The implementation details describe baseline handling, a shared rough-subgraph setup for several methods, and a GraphSAGE extension for node and edge attributes.

  • RoG was retrained separately for WebQSP and CWQ to address training-set label leakage; G-Retriever was adapted for CWQ, while SR+NSM evaluation there could not be run.Source: §C.1 · p. 19
  • RoG, G-Retriever, cosine similarity, GNN-RAG, and SubgraphRAG variants retrieved from identical rough subgraphs, whereas Retrieve-Rewrite-Answer queried the raw KG.Source: §C.1 · p. 19
  • The GraphSAGE extension handles node and edge attributes, and empirically the one-layer version performed best.Source: §C.1 · p. 19

C.2 IMPLEMENTATION DEPENDENCIES

The implementation uses standard machine-learning, transformer, graph, and network-analysis packages.

  • The implementation uses PyTorch, Transformers, xFormers, NetworkX, and PyTorch Geometric, including NetworkX's built-in PPR implementation.Source: §C.2 · p. 19

C.3 ADDITIONAL EXPERIMENT RESULTS FOR VARYING K IN TOP-K TRIPLE RETRIEVAL

Figure 6 shows SubgraphRAG variant performance on WebQSP across top-K triple-retrieval settings, with observations consistent with CWQ.

  • Figure 6 presents WebQSP performance for SubgraphRAG variants across top-K triple-retrieval values, with observations consistent with CWQ.Source: §C.3 · p. 19

D SUPPLEMENTARY KGQA RESULTS

The supplementary results analyze truth-grounded answers and retrieval size, describe the evaluation prompts, and provide examples of explainable responses.

D SUPPLEMENTARY KGQA RESULTS

  • Figure 6 plots WebQSP retrieval effectiveness across top-K values, while Table 7 breaks down CWQ recall by topic-entity count.The supplied captions identify the comparisons but do not provide specific plotted values.Source: Figure 6 · p. 20, Table 7 · p. 20
  • The truth-grounded QA score aggregates per-sample answer outcomes, penalizing hallucinated answers and favoring missing answers over incorrect ones.The scoring assigns different values according to whether answers are correct, absent, or unsupported by retrieved triples, then uses min-max normalization from 0 to 100.Source: D SUPPLEMENTARY KGQA RESULTS · p. 20
  • SubgraphRAG’s retriever consistently outperforms RoG’s even when RoG retrieves more triples, although increasing RoG’s beam-search size substantially raises computational costs.Figure 7 presents the retriever and retrieval-size ablations using un-fine-tuned LLM reasoners.Source: D SUPPLEMENTARY KGQA RESULTS · p. 20, Figure 7 · p. 21
  • On CWQ-sub, over 10% of RoG’s correct answers are not retrieved, compared with 1% for SubgraphRAG; its refusal rates also rise when KG evidence is absent.For questions lacking KG-supported answers, SubgraphRAG’s refusal rates increase from 2% to 19% on WebQSP and from 7% to 29% on CWQ, compared with questions with KG-supported answers.Source: D SUPPLEMENTARY KGQA RESULTS · p. 20, Table 8 · p. 21

E PROMPT TEMPLATES

F EXPLAINABLITY EXAMPLES

  • The explainability examples cover responses involving different reasoning-hop counts and logic chains, alongside examples of refusing to answer when information is insufficient.The refusal examples are in Appendix F.2.Source: F EXPLAINABLITY EXAMPLES · p. 23

F.1 LLM RESPONSES WITH EXPLAINABLE REASONING

The examples show LLM responses using retrieved triples to answer questions through relation chaining, multi-hop reasoning, and multi-answer retrieval.

F.1 LLM RESPONSES WITH EXPLAINABLE REASONING

  • For a question about Nord-Ouest Department, the response first identifies Haiti and then returns Haitian Creole and French as languages spoken there.The retrieved triples connect the department to Haiti and list both languages.Source: §F.1 · p. 23
  • The Tom Hicks example links his owned teams to American League West membership and identifies the Texas Rangers as the matching team.The response distinguishes the Rangers from the Dallas Stars by following the retrieved ownership and league triples.Source: §F.1 · p. 24
  • The Winged Monkey #7 example chains character-to-film and film-to-actor triples to answer Judy Garland.The response identifies The Wizard of Oz as the film and Judy Garland as the actor who played Dorothy.Source: §F.1 · p. 25
  • The response to the Angelina Jolie and Erwin Stoff query intersects their retrieved film lists and selects Unbroken.The example frames the answer as the common film directed by Jolie and produced by Stoff.Source: §F.1 · p. 25
  • The Bristol Palin example returns three schools by following her education triples, matching all three listed ground-truth answers.The schools are Wasilla High School, Juneau-Douglas High School, and West Anchorage High School.Source: §F.1 · p. 26

F.2 LLM REFUSAL TO ANSWER DUE TO INSUFFICIENT INFORMATION

The examples include answers withheld when retrieved triples lack the requested information, as well as cases where the response does not match the listed ground truth.

F.2 LLM REFUSAL TO ANSWER DUE TO INSUFFICIENT INFORMATION

  • For Lake Merritt’s depth, the response says the retrieved triples provide no direct depth information and returns no answer.It notes location and landmark facts but says these do not establish the lake’s depth.Source: §F.2 · p. 28
  • For Jeremy Shockey’s 2012 team, the response reports insufficient evidence and returns unavailable, while the listed ground truth is Carolina Panthers.The response lists team years through 2007 but no 2012 team.Source: §F.2 · p. 28
  • In the Logan Lerman query, the response fails to find a matching film in the two retrieved lists but then invokes a related Fury title; the listed ground truth is What Women Want.The response itself says Fury was not among the films edited by Thomas J. Nordberg before asserting a related-film connection.Source: §F.2 · p. 29
  • For the 1808 position and 2011 Ohio governor query, the response says the answer is unavailable, although the listed ground truth is Return J. Meigs, Jr.The response says the retrieved triples provide no person matching the date and governorship.Source: §F.2 · p. 29

Related papers

Loading 2410.20724v4…