ReGraphRAG: Reorganizing Fragmented Knowledge Graphs for Multi-Perspective Retrieval-Augmented Generation

Soohyeong Kim, Seok Jun Hwang, JungHyoun Kim, Jeonghyeon Park, Yong Suk ChoiEMNLP 2025

TL;DR

This paper introduces ReGraphRAG, a novel framework that tackles the issue of fragmented knowledge graphs in retrieval-augmented generation (RAG) systems. By reorganizing these fragmented graphs and expanding the query's perspective, ReGraphRAG significantly improves the coherence and diversity of generated responses, outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Large Language Models (LLMs) are powerful but often struggle with queries requiring up-to-date, domain-specific, or nuanced information due to their reliance on static, pre-trained knowledge. Retrieval-Augmented Generation (RAG) aims to solve this by dynamically incorporating external knowledge. Graph-based RAG further enhances this by organizing retrieved information into structured knowledge graphs, enabling multi-hop reasoning. However, a significant challenge arises when these knowledge graphs are constructed from unstructured documents using LLMs: they often become fragmented, with disconnected subgraphs. This fragmentation hinders inferential coherence and limits the benefits of graph-based retrieval. ReGraphRAG directly addresses this problem by reconstructing and enriching these fragmented knowledge graphs.

Methods

ReGraphRAG is built upon three core components:

  1. Perspective Expansion: The original query is decomposed into multiple interpretive angles. For each angle, the system generates several sub-queries using chain-of-thought prompting. This allows for the retrieval of a broader range of semantically relevant information from the knowledge graph, addressing the query from diverse viewpoints.
  2. Graph Reorganization: This is a two-step process to connect fragmented subgraphs.
  3. Dijkstra-based Shortest Path: It first connects subgraphs that are already linked in the original knowledge graph by finding shortest paths between them. This fills in missing connections and introduces new edges to support coherent reasoning.
  4. Cosine Similarity-based Path Generation: For subgraphs that remain disconnected, new edges are established based on the semantic similarity of their node embeddings. This ensures that all retrieved subgraphs are merged into a single, connected graph structure.
  5. Query-aware Reranking: The reorganized graph is converted into triplets (<node, edge, node>). These triplets are then reranked based on their semantic similarity to the original query. This prioritizes the most relevant information for the LLM's generation process.

Finally, the reorganized and reranked graph is transformed into a structured prompt for the LLM.

Datasets

The paper uses the Ultradomain dataset, which is a collection of QA datasets derived from college textbooks across 18 domains. For their experiments, they specifically selected four datasets: Agriculture, Computer Science, Legal, and a Mix domain. This dataset has been used in previous graph-based RAG studies, including LightRAG, ensuring a fair comparison.

Key Insights and Ideas

  • Fragmentation is a major bottleneck: The paper highlights that fragmented knowledge graphs, a common issue with LLM-based construction, severely limit the effectiveness of graph-based RAG.
  • Multi-perspective querying is crucial: Decomposing a query into multiple interpretive angles (Perspective Expansion) significantly boosts the diversity and comprehensiveness of retrieved information.
  • Reorganization bridges the gap: The Graph Reorganization component is vital for transforming disconnected fragments into a coherent structure, which is essential for multi-hop reasoning and improving answer clarity (Empowerment).
  • Diversity vs. Coherence trade-off: While increasing diversity is beneficial, it can sometimes lead to less coherent answers. Graph Reorganization helps mitigate this by ensuring a structured flow of information.
  • Prompting matters for reranking: The paper notes that the effectiveness of Query-aware Reranking might be influenced by how the graph structure is presented in the prompt, suggesting an area for future research.

Key Results

  • ReGraphRAG consistently outperforms strong baselines (NaïveRAG, HyDE, GraphRAG, LightRAG) across four evaluation dimensions: Comprehensiveness, Diversity, Empowerment, and Overall quality.
  • The system achieves an average diversity win rate of over 80% against baselines.
  • Ablation studies show that Perspective Expansion has the largest impact, especially on Diversity, while Graph Reorganization significantly improves Empowerment by enhancing logical coherence.
  • Computational efficiency: While the full ReGraphRAG with multi-perspective expansion has a higher time cost (19.8 sec in a sequential setup), it uses significantly fewer tokens (18,000) compared to GraphRAG (360,000 tokens), indicating more efficient use of prompt resources.

Limitations and Future Work

  • Query-aware Reranking Effectiveness: The paper notes that removing the reranking step occasionally led to better performance, suggesting that the current cosine similarity-based reranking might not fully capture multi-hop reasoning potential. The interplay between graph-structured prompts and reranking is underexplored.
  • Computational Overhead: The multi-perspective expansion strategy increases retrieval and inference time, potentially limiting its practicality in real-time applications.
  • Future Work: The authors suggest exploring adaptive perspective selection or budget-aware expansion for better efficiency. Further research into the interaction between graph-structured prompt design and reranking is also recommended.

Summary updated

BibTeX
@inproceedings{kim2025regraphrag,
  author = {Soohyeong Kim and Seok Jun Hwang and JungHyoun Kim and Jeonghyeon Park and Yong Suk Choi},
  title = {{ReGraphRAG: Reorganizing Fragmented Knowledge Graphs for Multi-Perspective Retrieval-Augmented Generation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure