PaperlayerView exact revision on arXiv

Source-linked AI summary

HyperGraphRAG: Retrieval-Augmented Generation via Hypergraph-Structured Knowledge Representation

Haoran Luo, Haihong E, Guanting Chen, Yandan Zheng, Xiaobao Wu, Yikai Guo, Qika Lin, Yu Feng, Zemin Kuang, Meina Song, Yifan Zhu, Luu Anh Tuan

arXiv:2503.21322v3cs.AI

TL;DR

Existing graph-based RAG methods are limited to binary relations, whereas real-world knowledge often contains n-ary relations. HyperGraphRAG constructs and retrieves hypergraph-structured facts and combines them with chunk-based passages for generation, outperforming standard and graph-based RAG methods across four domains.

  • Problem

    Existing graph-based RAG methods are restricted to binary relations, limiting representation of n-ary relations among more than two entities in real-world knowledge.

  • Method

    HyperGraphRAG constructs a knowledge hypergraph with n-ary relational extraction, retrieves entities and hyperedges, and combines retrieved n-ary facts with chunk-based RAG passages.

  • Results

    HyperGraphRAG consistently outperforms standard RAG and previous graph-based RAG methods in answer accuracy, retrieval relevance or efficiency, and generation quality across medicine, agriculture, computer science, and law.

  • Takeaways & Limitations

    Hypergraph-guided retrieval and generation provide a knowledge representation that captures n-ary relational structures and shows consistent effectiveness across diverse domains.

Abstract

from arXiv · show

Standard Retrieval-Augmented Generation (RAG) relies on chunk-based retrieval, whereas GraphRAG advances this approach by graph-based knowledge representation. However, existing graph-based RAG approaches are constrained by binary relations, as each edge in an ordinary graph connects only two entities, limiting their ability to represent the n-ary relations (n >= 2) in real-world knowledge. In this work, we propose HyperGraphRAG, a novel hypergraph-based RAG method that represents n-ary relational facts via hyperedges, and consists of knowledge hypergraph construction, retrieval, and generation. Experiments across medicine, agriculture, computer science, and law demonstrate that HyperGraphRAG outperforms both standard RAG and previous graph-based RAG methods in answer accuracy, retrieval efficiency, and generation quality. Our data and code are publicly available at https://github.com/LHRLAB/HyperGraphRAG.

1 Introduction

Standard RAG retrieves fixed-length chunks, while GraphRAG represents binary entity relations; HyperGraphRAG uses hyperedges to model n-ary relational facts and combines structured retrieval with generation. Experiments across four domains report improvements in answer accuracy, retrieval efficiency, and generation quality.

  • Existing graph-based RAG methods are restricted to binary relations because ordinary graph edges connect only two entities.This limits representation of n-ary relations common in real-world domain knowledge.
  • Decomposing an n-ary medical fact into binary triples can produce representation sparsity.The example separates patient attributes and diagnosis into multiple triples rather than preserving the complete fact.
  • HyperGraphRAG represents n-ary relational facts with hyperedges connecting n entities, where each hyperedge has a natural-language description.The proposed representation is intended to preserve knowledge completeness, structural expressiveness, and inferential capability.
  • HyperGraphRAG constructs a knowledge hypergraph, retrieves relevant n-ary facts, and combines them with chunk-based RAG passages for generation.Its construction uses LLM-based n-ary relation extraction and stores the resulting hypergraph for efficient retrieval.
  • HyperGraphRAG outperforms standard RAG and previous graph-based RAG methods in answer accuracy, retrieval efficiency, and generation quality across medicine, agriculture, computer science, and law.The experiments cover multiple knowledge-intensive domains.

2 Related Work

Prior graph-based RAG methods improve retrieval through graph representations and specialized indexing or path-based techniques, but they rely on binary relations. HyperGraphRAG extends this line of work with hypergraph-structured knowledge representation.

  • GraphRAG introduced graph-based retrieval for improving LLM generation, followed by methods targeting different applications and retrieval strategies.LightRAG emphasizes graph indexing and updates, while PathRAG and HippoRAG2 use path pruning or Personalized PageRank.
  • Existing graph-based RAG methods rely on binary relations, limiting knowledge expressiveness.HyperGraphRAG is presented as the first graph-based RAG method using hypergraph-structured knowledge representation.
  • Hypergraph representation research has developed embeddings, GNNs, and attention methods for n-ary entities, mainly targeting link prediction.The paper positions hypergraphs as a way to extend knowledge representation in graph-based RAG.

3 Preliminaries

The preliminaries define standard RAG as retrieving relevant document fragments before generation, graph-based RAG as retrieval over entity-relation graphs, and hypergraphs as structures whose hyperedges connect at least two entities.

  • Standard RAG selects relevant document fragments d from domain knowledge K using question q, then generates answer y from q and d.
  • Graph-based RAG represents knowledge as G = (V, E), with entities V and relationships E, then retrieves graph-structured facts for a question.Facts are represented using a relation and its connected entity set.
  • A hypergraph GH = (V, EH) contains an entity set V and hyperedge set EH, with each hyperedge connecting two or more entities.Unlike ordinary binary graphs, hypergraphs model n-ary relational facts.

4 Method: HyperGraphRAG

HyperGraphRAG constructs and stores a knowledge hypergraph, retrieves entities and hyperedges by vector similarity, expands retrieved structure into complete n-ary facts, and fuses it with chunk-based retrieval for generation.

  • Knowledge Hypergraph Construction: HyperGraphRAG constructs a knowledge hypergraph through n-ary relation extraction, bipartite storage, and vector representation storage.
  • N-ary Relation Extraction: Natural-language documents are parsed into independent knowledge fragments, each treated as a hyperedge with a description and confidence score.Entity recognition then extracts the entities associated with each hyperedge.
  • N-ary Relation Extraction: LLM-based extraction converts documents into n-ary relational facts containing hyperedges and their associated entity sets.This forms the complete knowledge hypergraph GH.
  • Bipartite Hypergraph Storage: The hypergraph is transformed into a bipartite graph whose nodes merge entities and hyperedges, while edges connect each hyperedge to its associated entities.This representation supports querying all entities for a hyperedge or all hyperedges linked to an entity while preserving the hypergraph structure.
  • Vector Representation Storage: Entities and hyperedges are embedded with the same model into vector bases to support semantic retrieval.
  • Hypergraph Retrieval Strategy: Entity retrieval extracts question entities and matches them against hypergraph entities using cosine similarity and relevance scores.Retrieved entities are constrained by a threshold and a limit on the number selected.
  • Hypergraph Retrieval Strategy: Hyperedge retrieval expands the search to complete n-ary relations by matching the question with embedded hyperedges using similarity and relevance scores.A threshold and retrieval limit control the selected hyperedges.
  • Hypergraph Knowledge Fusion: Bidirectional expansion retrieves hyperedges from entities and entities from hyperedges, then merges them into a comprehensive n-ary fact set.The resulting knowledge is used for reasoning and generation.

5 Experiments

Experiments evaluate HyperGraphRAG across multiple domains, baselines, retrieval settings, ablations, representation analyses, generation quality, and computational costs. Across these evaluations, HyperGraphRAG consistently improves performance while retaining efficient retrieval and balanced construction and generation costs.

  • Experimental Setup: Experiments cover five domains, six baselines, and three metrics measuring answer accuracy, retrieval similarity, and generation quality.The domains are Agriculture, Computer Science, Legal, Mix, and Medicine; the baselines include NaiveGeneration, StandardRAG, GraphRAG, LightRAG, PathRAG, and HippoRAG2.
  • Main Results: HyperGraphRAG improves F1, R-S, and G-E by +8.6, +8.8, and +4.4 on Binary Source, and +5.3, +6.4, and +2.9 on N-ary Source.The reported gains support robustness across both source types.
  • Ablation Study: Removing hyperedge retrieval lowers F1 from 35.4 to 26.4, while removing entity retrieval lowers it to 29.8 and removing chunk fusion lowers it to 29.2.The ablation study evaluates entity retrieval, hyperedge retrieval, chunk retrieval fusion, and their combinations in Medicine.
  • Knowledge Representation: HyperGraphRAG represents multiple entities through hyperedges and constructs 26,902 hyperedges in CS, compared with 930 GraphRAG communities and 5,632 LightRAG relations.The representation analysis reports richer interconnected structures and stronger capacity for capturing knowledge.
  • Retrieval Efficiency: Retrieval performance saturates around k = 60, and HyperGraphRAG outperforms binary graph-based methods under retrieval-length limits.Increasing retrieved hyperedges raises performance and token count before saturation, while constrained retrieval still favors n-ary representations.
  • Generation Quality: HyperGraphRAG achieves an Overall generation score of 61.5, with Correctness 64.8, Relevance 66.0, Factuality 64.2, and Diversity 47.0.It exceeds all baselines on these reported dimensions, including Diversity despite its relatively lower score.
  • Time and Cost: Construction costs 3.084 seconds and $0.0063 per 1k tokens, while generation costs 0.256 seconds and $3.184 per 1k queries.Construction is faster than GraphRAG but slower than HippoRAG2; generation is slower and more expensive than StandardRAG but cheaper than PathRAG and LightRAG.

6 Conclusion

The conclusion presents HyperGraphRAG as a hypergraph-based RAG framework for n-ary relational knowledge, with construction, retrieval, and generation components. Its prompts extract structured relations and query entities, while a unified generation prompt supports evaluation across methods.

  • Conclusion: HyperGraphRAG models knowledge as hypergraphs to capture n-ary relational structures and addresses limitations of binary graph-based RAG.The conclusion reports consistent improvements in answer accuracy, retrieval relevance, and generation quality across diverse domains.
  • Relation Extraction: The relation-extraction prompt segments text into knowledge fragments, assigns completeness scores, and identifies entities with types, descriptions, and importance scores.The prompt is designed to extract structured n-ary relational facts from raw text.
  • Entity Extraction: The query-entity prompt returns concise JSON entities aligned with the input language to support entity-level hypergraph retrieval.This prompt is used for extracting key entities from user queries.
  • Evaluation: A unified Chain-of-Thought generation prompt is used for all RAG baselines to ensure fair comparison.The prompt is presented with the evaluation approach in Appendix E.

B.1 Proof of Proposition 1

Hypergraph representation preserves n-ary facts injectively, whereas pairwise binary projection can merge distinct fact sets and lose information. An incidence bipartite encoding retains the hypergraph structure and supports equivalent queries.

  • Representation: A hyperedge represents each n-ary fact directly, while binary projection connects every co-occurring entity pair within a clique.The binary representation is defined by all pairwise edges activated by the fact set.
  • Information loss: Distinct fact sets containing an n-ary fact can activate identical binary edges through merge-split transformations.Thus, the binary representation is not injective when facts of arity n ≥3 exist.
  • Information loss: H(X | ϕB(X)) > 0 and I(X; ϕB(X)) < H(X), showing that binary representation is lossy.Hypergraph encoding instead satisfies H(X | ϕH(X)) = 0 and preserves all information.
  • Boundary case: When all facts are binary, binary representation becomes injective and equivalent to hypergraph representation, with no information loss.The information-preservation distinction therefore requires at least one fact with arity three or higher.
  • Conclusion: If the knowledge base contains a fact of arity three or higher, hypergraph representation preserves more information than binary representation.The proposition characterizes hypergraph representation as more comprehensive in the information-theoretic sense.
  • Bipartite encoding: The bipartite representation therefore preserves and queries a knowledge hypergraph without structural information loss.Adjacency and path-based reasoning encode entity–hyperedge membership.
  • Bipartite encoding: A bipartite graph formed by adding one node per hyperedge is bijective with the original hypergraph and preserves equivalent membership and co-occurrence queries.These operations run in O(|EB|), matching equivalent queries over the knowledge hypergraph.

B.3 Proof of Proposition 3

The proof models hypergraph and binary encodings as information channels and shows that hypergraph retrieval is more information-efficient when high-arity facts exist. Under a fixed retrieval budget, this yields strictly higher generation quality, while the all-binary case is equal.

  • Encoding model: Hypergraph encoding maps each fact to one hyperedge, whereas binary encoding expands an n-ary fact into all pairwise edges.The resulting encoded knowledge sets are treated as random variables for information analysis.
  • Information preservation: I(X; YH) = H(X), while I(X; YB) < H(X) whenever facts with arity n ≥3 occur.Binary encoding becomes non-injective because distinct inputs can produce the same pairwise representation.
  • Information efficiency: Hypergraph representation transmits more effective information per bit because it preserves all source information while binary representation has a larger outcome space.The proof defines information efficiency as effective information transmitted per bit.
  • Retrieval coverage: Under a fixed retrieval budget L, higher hypergraph information density provides at least as much coverage as binary encoding, with strict improvement when high-arity facts exist.The coverage comparison is strict on intervals where the measure of facts with size at least three is positive.
  • Generation quality: The total generation-quality difference increases with retrieval budget unless all facts are binary.Equation 42 gives a strictly positive derivative under the presence of at least one fact with arity n ≥3.
  • Conclusion: With at least one n-ary fact, hypergraph encoding strictly exceeds binary encoding in generation quality under any fixed retrieval budget; otherwise, the encodings are equal.This is the stated conclusion of the proposition.
  • System pipeline: HyperGraphRAG constructs hypergraphs from LLM-extracted n-ary facts, stores them bipartitely, and precomputes entity and hyperedge embeddings.The construction pipeline supports indexing and retrieval over both entities and hyperedges.
  • System pipeline: For a query, HyperGraphRAG retrieves entity and hyperedge candidates, expands neighborhoods, optionally adds chunks, and generates the final answer.Retrieval uses top-k similarity search followed by knowledge assembly.

D Dataset Construction

The evaluation benchmark spans five domains and balances binary and n-ary knowledge sources with matched traversal depths. Questions and golden answers are generated and manually verified for factual accuracy, relevance, diversity, and fairness.

  • Domains: The benchmark covers medicine, agriculture, computer science, law, and a fifth domain identified in the dataset description.Medicine uses international hypertension guidelines; agriculture and computer science use UltraDomain, while legal data also comes from UltraDomain.
  • Sampling: Each domain contributes 512 questions, divided equally between binary and n-ary sources.The two sources each contain 256 sampled facts across 1-hop, 2-hop, and 3-hop traversals.
  • Sampling: Binary-source samples contain pairwise entity connections, whereas n-ary-source samples contain multi-entity relational structures with n ≥3.Both source types use the same 128/64/64 allocation across traversal depths.
  • Quality control: GPT generates a question and golden answer for each sampled fact, followed by independent manual verification in every domain.Review checks factual accuracy, relevance, diversity, annotated-answer accuracy, and evaluation fairness.

E Evaluation Details

The evaluation standardizes generation prompts, token budgets, hyperparameters, and retrieval conditions across methods. It compares retrieval-free, chunk-based, and binary graph-based baselines using metrics for factual alignment, retrieval quality, and fluency.

  • Generation protocol: All methods insert retrieved knowledge into one fixed prompt that elicits reasoning in <think> and the answer in <answer>.This preserves zero-shot chain-of-thought benefits while keeping generation consistent across retrieval strategies.
  • Metrics: Performance is assessed along factual alignment, retrieval quality, and generation fluency.These are the three complementary evaluation dimensions described for retrieval-augmented generation.
  • Metrics: Word-level F1 compares generated answers with ground-truth references and averages the scores across questions.The metric is used to capture factual alignment with expected answers.
  • Metrics: Figure 12 organizes generation quality into seven evaluation dimensions.The figure caption identifies the number of dimensions but does not specify their individual encodings.
  • Baselines: The comparison includes retrieval-free, chunk-based, and binary graph-based RAG paradigms.The six baselines are NaiveGeneration, StandardRAG, GraphRAG, LightRAG, PathRAG, and HippoRAG2.
  • Fair comparison: Baselines use the same generation prompt, equivalent token budgets, identical evaluation conditions, and unified hyperparameters.Chunk-based methods retrieve top-5 chunks, while graph-based methods retrieve top-60 relevant elements according to their strategies.

H Case Study

The case study evaluates RAG methods on a complex medical question requiring clinical-evidence synthesis and modality discrimination. HyperGraphRAG produces the most accurate and comprehensive response, while baselines show ambiguity or imprecision.

  • Case-study question: The case study asks which renal-denervation type demonstrates BP-lowering efficacy over 24 hours in randomized, sham-controlled trials for resistant hypertension.The question requires synthesizing clinical evidence and distinguishing ultrasound from catheter-based techniques.
  • HyperGraphRAG result: HyperGraphRAG identifies ultrasound renal denervation and provides domain-relevant reasoning with structured knowledge.The reported response describes ultrasound renal denervation as the answer.
  • HyperGraphRAG result: HyperGraphRAG achieves Correctness 10.00, Factuality 9.50, Knowledgeability 10.00, and an overall G-E score of 92.86.These are the reported scores for this specific case study.
  • Baseline comparison: NaiveGeneration and StandardRAG produce factually plausible but imprecise or overly generic answers, including radiofrequency denervation.Their lower scores are particularly evident in Correctness and Factuality.
  • Baseline comparison: GraphRAG, LightRAG, and PathRAG improve coherence but remain less domain-specific, while HippoRAG2 does not precisely isolate the correct answer.The comparison also describes reduced clarity and comprehensiveness for the strongest baseline.
  • Future directions: The framework focuses on textual knowledge, whereas real-world information also includes images, tables, and structured metadata.The authors propose multimodal hypergraphs integrating textual and non-textual entities as future work.
  • Future directions: The authors propose reinforcement learning to replace fixed similarity metrics with retrieval and generation policies optimized using long-term rewards.The proposed rewards include factuality, coherence, and user feedback.

I.5 Scaling to Harder Tasks and Broader Applications

The authors plan to evaluate HyperGraphRAG on harder reasoning tasks and broader real-world applications. Planned settings include multi-hop question answering, legal argument generation, complex scientific synthesis, and domains such as policy analysis, education, and open-domain dialogue.

  • Harder tasks: Future evaluations will test HyperGraphRAG on deeper compositional reasoning tasks, including multi-hop question answering, legal argument generation, and complex scientific synthesis.These tasks are intended to assess the framework in more challenging settings.
  • Broader applications: The authors plan to extend evaluation beyond current benchmarks to policy analysis, education, and open-domain dialogue.These applications are intended to test generalization across broader domains.
Loading 2503.21322v3…