Skip to content

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

Conference: NeurIPS 2025 arXiv: 2503.21322 Code: GitHub Area: LLM / RAG / Knowledge Graph Keywords: Retrieval-Augmented Generation, Hypergraph, Knowledge Representation, N-ary Relations, Graph Retrieval

TL;DR

This paper proposes HyperGraphRAG, the first RAG method based on hypergraph structure, which models n-ary relations (\(n \geq 2\)) via hyperedges. It overcomes the binary-relation bottleneck of existing graph-based RAG methods, achieving comprehensive improvements over StandardRAG and the GraphRAG family on question-answering tasks across medical, agricultural, computer science, and legal domains.

Background & Motivation

Standard RAG relies on vector retrieval over text chunks, ignoring inter-entity relations. While GraphRAG and its successors (LightRAG, PathRAG, HippoRAG2) introduce graph structures to capture entity relationships, all existing methods are confined to binary relations—each edge in an ordinary graph connects exactly two entities.

Real-world knowledge, however, frequently involves n-ary relations (\(n > 2\)). For example, in the medical domain, the statement "male hypertensive patients with serum creatinine levels between 115–133 μmol/L are diagnosed with mild serum creatinine elevation" involves a relation among four entities. Forcing such knowledge into binary triples (e.g., "gender:(hypertensive patient, male)", "diagnosed as:(hypertensive patient, mild serum creatinine elevation)") leads to sparsification of knowledge representation and information loss.

Method

Overall Architecture

HyperGraphRAG consists of three core steps: knowledge hypergraph construction, hypergraph retrieval strategy, and hypergraph-guided generation.

Key Designs

1. Knowledge Hypergraph Construction

Core Idea: An LLM extracts n-ary relational facts from text; hyperedges connect multiple entities; natural language descriptions replace structured relation types.

  • Hyperedge Extraction: Input text is parsed into independent knowledge segments, each represented as a hyperedge \(e_i = (e_i^{text}, e_i^{score})\), comprising a natural language description and a confidence score \(e_i^{score} \in (0, 10]\).
  • Entity Recognition: Entity extraction is performed for each hyperedge; each entity \(v_j = (v_j^{name}, v_j^{type}, v_j^{explain}, v_j^{score})\) includes name, type, explanation, and confidence score.
  • End-to-End LLM Extraction: A dedicated prompt \(p_{ext}\) drives the LLM to perform both knowledge segment segmentation and entity recognition.

Bipartite Graph Storage: The hypergraph \(G_H = (V, E_H)\) is stored as a bipartite graph \(G_B = (V_B, E_B)\) via a transformation function \(\Phi\), where \(V_B = V \cup E_H\) and \(E_B = \{(e_H, v) \mid v \in V_{e_H}\}\). This design leverages the query optimization capabilities of standard graph databases while losslessly preserving hypergraph structure and supporting incremental updates.

Vector Storage: The same embedding model \(f\) maps both hyperedges and entities into a shared vector space, stored in two separate vector databases \(\mathcal{E}_H\) and \(\mathcal{E}_V\).

2. Hypergraph Retrieval Strategy

A dual-channel parallel retrieval scheme is adopted:

  • Entity Retrieval \(\mathcal{R}_V(q)\): Key entities \(V_q\) are extracted from query \(q\); the most relevant entities are retrieved via cosine similarity weighted by entity confidence score \(v^{score}\), with threshold \(\tau_V\) and upper bound \(k_V\).
  • Hyperedge Retrieval \(\mathcal{R}_H(q)\): The query vector is directly compared against hyperedge vectors; relevant hyperedges are retrieved weighted by \(e_H^{score}\), with threshold \(\tau_H\) and upper bound \(k_H\).

3. Hypergraph-Guided Generation

Hypergraph Knowledge Fusion: Retrieved results are expanded via a bidirectional strategy: - From retrieved entities, all associated hyperedges and their linked entities are looked up → \(\mathcal{F}_V^*\) - From retrieved hyperedges, all connected entities are obtained → \(\mathcal{F}_H^*\) - These are merged into a complete n-ary relational fact set \(K_H = \mathcal{F}_V^* \cup \mathcal{F}_H^*\)

Hybrid RAG Fusion: Hypergraph knowledge \(K_H\) is combined with conventional chunk retrieval results \(K_{chunk}\) to form the final knowledge input \(K^* = K_H \cup K_{chunk}\), which is fed to the LLM for answer generation.

Loss & Training

HyperGraphRAG does not involve end-to-end training. The construction phase uses an LLM (GPT-4o-mini) for n-ary relation extraction; the generation phase uses an LLM for question answering. Key hyperparameters: entity retrieval \(k_V = 60\), \(\tau_V = 50\); hyperedge retrieval \(k_H = 60\), \(\tau_H = 5\); chunk retrieval \(k_C = 5\), \(\tau_C = 0.5\).

Key Experimental Results

Main Results

Evaluation is conducted on QA datasets across medical, agricultural, CS, legal, and mixed domains, compared against 6 baseline methods. Metrics: F1 (answer token-level similarity), R-S (retrieval semantic similarity), G-E (LLM-as-judge generation quality, averaged over 7 dimensions).

Method Medicine F1 Medicine R-S Agriculture F1 CS F1 Legal F1 Mix F1
NaiveGeneration 12.89 0.00 12.74 18.65 21.64 16.93
StandardRAG 27.90 62.57 27.43 28.93 37.34 43.20
GraphRAG 17.60 55.89 21.28 23.33 30.11 19.27
LightRAG 12.79 53.52 18.24 22.72 31.64 27.03
PathRAG 14.94 53.19 21.30 26.73 31.29 37.07
HippoRAG2 21.34 59.52 12.63 17.34 18.53 21.53
HyperGraphRAG 35.35 70.19 33.89 31.30 43.81 48.71

Compared to StandardRAG, HyperGraphRAG achieves overall gains of +7.45 F1, +7.62 R-S, and +3.69 G-E. Notably, existing graph-based RAG methods underperform StandardRAG in most settings, owing to knowledge fragmentation introduced by binary-relation graphs.

Ablation Study

Module removal effects evaluated on the Medicine domain:

Configuration F1 R-S G-E
Full HyperGraphRAG 35.4 70.2 59.4
w/o Entity Retrieval 29.8 — —
w/o Hyperedge Retrieval 26.4 — —
w/o Chunk Retrieval Fusion 29.2 — —
w/o ER & HR & CR Lowest — —

Every module is indispensable; removing hyperedge retrieval causes the largest drop (F1 −9.0), confirming that n-ary relation capture is the core contribution.

Time and Cost Analysis

Method Build TP1kT (s) Build CP1kT ($) Gen TPQ (s) Gen CP1kQ ($)
StandardRAG 0 0 0.147 1.016
GraphRAG 9.272 0.0058 0.221 1.836
LightRAG 5.168 0.0081 0.359 3.359
PathRAG 5.168 0.0081 0.436 3.496
HippoRAG2 2.758 0.0056 0.240 3.438
HyperGraphRAG 3.084 0.0063 0.256 3.184

HyperGraphRAG achieves moderate construction efficiency (3.1 s/1k tokens); its generation cost is lower than LightRAG and PathRAG, striking a favorable balance between efficiency and quality.

Key Findings

  1. Counter-intuitive behavior of existing GraphRAG methods: GraphRAG and LightRAG underperform StandardRAG in most domains, exposing the knowledge fragmentation and retrieval sparsification caused by binary-relation modeling.
  2. N-ary Source vs. Binary Source: HyperGraphRAG's advantage is more pronounced on N-ary Source questions (+5.3 F1), validating the effectiveness of hypergraph modeling for n-ary relations.
  3. Richness of hypergraph construction: In the CS domain, HyperGraphRAG constructs 26,902 hyperedges and 19,913 entities, far exceeding LightRAG's 5,632 relations and GraphRAG's 930 communities.
  4. Retrieval efficiency: Under constrained retrieval budgets, HyperGraphRAG still outperforms all binary-graph methods, indicating higher information density in n-ary representations.
  5. Generation quality: Among 7 evaluation dimensions, Correctness (64.8), Relevance (66.0), and Factuality (64.2) all achieve the best scores.

Highlights & Insights

  • First introduction of hypergraph structure into RAG: The concept is straightforward yet effective, directly targeting the core bottleneck of existing methods (the limitation of binary relations).
  • Natural language descriptions for hyperedges: Compared to traditional hyper-relational representations (e.g., m-TransH, HINGE), this design is more flexible and directly compatible with LLM generation capabilities.
  • Bipartite graph storage scheme: Hypergraph structure is elegantly stored using standard graph databases, avoiding the complexity of dedicated hypergraph databases while fully preserving hypergraph semantics.
  • Comprehensive experimental design: Performance is evaluated across answer accuracy, retrieval efficiency, generation quality, time cost, and ablation analysis.

Limitations & Future Work

  1. LLM dependence: N-ary relation extraction relies entirely on LLM capability; extraction quality is constrained by prompt design and the LLM's domain knowledge.
  2. Construction cost: While per-instance cost is manageable, full-scale construction of large knowledge bases still requires substantial API calls.
  3. Hyperedge granularity control: Determining appropriate knowledge segment granularity remains an open question—overly coarse segmentation yields vague relations, while overly fine segmentation degenerates toward binary relations.
  4. Confidence score calibration: Confidence scores for entities and hyperedges are directly output by the LLM, lacking an objective calibration standard.
  5. Cross-domain adaptability: Although validated across 4 domains, the hypergraph advantage may diminish for less structured knowledge (e.g., literature, philosophy).
  6. Larger-scale validation: The knowledge scale (up to 940k tokens) remains modest compared to industrial-grade RAG systems.
  • Exposing the failure modes of the GraphRAG family: HyperGraphRAG's experiments reveal the failure patterns of GraphRAG, LightRAG, PathRAG, and HippoRAG2 when they underperform StandardRAG—specifically, knowledge fragmentation from binary relations.
  • Knowledge representation theory: Inspiration is drawn from n-ary relation modeling in the knowledge graph literature (m-TransH, HINGE), but structured representations are replaced with natural language, better suited to the LLM era.
  • Hypergraph success in other domains: Hypergraphs have demonstrated their ability to model higher-order relations in recommendation systems and social network analysis; their introduction into RAG is a natural extension.
  • Implications for future RAG systems: The expressiveness of knowledge structure directly affects retrieval quality and generation performance; improving knowledge representation is more impactful than refining retrieval algorithms alone.

Rating

  • Novelty: ⭐⭐⭐⭐ — Introducing hypergraphs into RAG is a meaningful first work, though the core idea is relatively straightforward.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ — 5 domains × 6 baselines × multi-dimensional evaluation, with comprehensive ablation, efficiency, and generation quality analysis.
  • Writing Quality: ⭐⭐⭐⭐ — Clear framework, rich figures and tables; theoretical proofs are concise but adequate.
  • Value: ⭐⭐⭐⭐ — Identifies a critical deficiency in existing GraphRAG methods and provides an effective solution.