[ RAG ] From Local to Global: A GraphRAG Approach to Query-Focused Summarization

들어가며

Talky를 만드는데, 내가 아는 RAG라고는 VectorDB에서 가져오는 RAG밖에 없었다. 이 방식은 한계가 너무 많았다.

예를 들면 Multi Hop 어려움 (예를들어 사용자의 관심사의 관계 파악)의 문제가 있다.

 

이는 내가 RAG에 대해서 아직 많은 것을 모르고 단순하게 VectorDB를 구성하고 Retrieve하는 것만 알고 있기 때문일 수도 있다고 생각하여 다양한 RAG에 대해 조사를 했었다.

 

이때, MS에서 발표한 GraphRAG를 접하게 되었고, GraphRAG에 대해 공부해보면 Talky 개발에 도움이 될 것 같고, 또 다른 새로운 아이디어를 내는데에 도움이 될 것 같아 논문을 읽게 되었는데, 블로그에도 정리해두고자 한다.

 

MS에서 발표한 자료와 논문은 이곳에 있다.

Welcome - GraphRAG

---

0. Abstract

Abstract에서는 일반적 논문처럼 문제, 제안, 설명, 기여를 말하고 있다. 각 내용은 아래와 같다.

• 문제
  • RAG는 "이 데이터셋의 메인 테마가 무엇?"'과 같은 전체 데이터를 파악해야 하는 QFS (Query-Focused Summarization)task에서 실패하는 문제가 있다.
  • Existing QFS Method는 일반적인 RAG System이 indexing하는 large text에 대해 확장이 되지 않는다.
• 제안 
  • RAG와 QFS는 상반되는 성격이 존재함. 이 상반되는 두 방법론의 장점을 결합한 GraphRAG을 제안한다.
  • GraphRAG는
    1. 일반적 질문도 처리할 수 있도록 확장이 가능하다.
       • RAG의 경우, 지엽적인 질문만 처리 가능하였으나, GraphRAG에서는 조금 더 추상적/포괄적 질문을 처리할 수 있고 sensemaking 질문 또한 처리가 된다.
    2. 처리할 수 있는 Source Text의 양이 확장 가능해진다.
       • QFS method의 경우 작은 규모의 text에서만 동작했으나, GraphRAG에서는 큰 규모에서도 동작한다.
• 설명
  • GraphRAG는 두 가지 방식으로 동작한다.
    1. Source Document로부터 Entity Knowledge Graph를 도출한다.
       • Source Text에서 Entity들을 추출하고, 관계를 추출하는 등의 작업을 통해 Graph를 도출하는 과정이다.
    2. Closely Related Entity들의 그룹에 대해서 Community Summaries를 사전 생성한다.
       • 1 단계에서 추출된 Entity들에 대해 Leiden Algorithm으로 Group화하는 단계이다. Cluster 이름 짓기 정도로 생각하면 쉽다.
• 기여
  • GraphRAG는 comprehensiveness와 생성된 응답의 다양성 모두에서 conventional RAG baseline을 넘어서는 상당한 향상을 만들어냈다.

---

1. Introduction

Introduction도 동일하게 세 가지 파트(소개 및 문제, 제안, 기여(실험))로 나누어서 전개된다. 

• 소개 및 문제
  • RAG는 LLM의 context window를 넘어서는 data를 기반으로 대답하기 위하여 LLM을 사용하는 방법론이다.
  • 표준 RAG setup에선, system은 text records의 대용량 외부 데이터에 접근하고, query와 관련된 record subset을 검색한다음 결과를 모으는 것이다.
  • LLM은 query를 기반으로 응답을 생성하고 record를 검색하는데 이러한 conventional approach(vectorRAG)에는 문제가 존재한다. 지역적인 질문에 대답만 잘하고 sensemaking queries에는 잘 대답하지 못한다는 것이다. (이는 위에서 말한 문제와 동일하다.)
  • sensemaking query와 연결된 개념 집합이 주어지면 LLM은 응답을 잘 생성할 수 있지만, vector RAG는 corpus에 의미를 부여할 수 없기 때문에 문제다.
• 제안
  • 그래서, 위 문제를 해결하고자 graph-based RAG approach(GraphRAG)를 제안한다.
  • 이 IDEA는 2가지 방식으로 동작한다.
    1. 먼저, LLM을 사용하여 knowledge graph를 구성한다. (node들은 corpus의 key entity, edge들은 entity사이의 관계)
    2. 다음으로 관련된 entity들의 community 계층으로 분할한다. 
    3. 이제 bottom-up 방식으로 추출된 community들을 따라가며 community 요약을 생성하고, high-level의 요약은 lower-level의 요약을 포함한다.
       • 이러한 community summaries가 corpus에 대해 description과 insight를 제공함.
    4. 마지막으로 GraphRAG는 map-reduce process를 통해 답변한다.
       • map : summaries는 독립적이고 병렬적으로 query에 대해 partial answer 제공하는데 사용됨
       • reduce : map단계에서 생성한 partial answer를 결합하고 final global answer를 생성
• 기여
  • GraphRAG Method와 그 성능을 보이기 위해 LLM-as-a-judge technique의 novel application 개발
    • 이 방식은 LLM을 사용하여 corpus-specific use case를 기반으로 global sensemaking 질문 set를 생성
    • 다음 answer 평가 LLM이 predefined criteria를 사용하여 두 RAG system을 평가
    • real-world text dataset에 대해 GraphRAG,VectorRAG를 비교함. (GraphRAG이 GPT-4쓸 때 매우 압도)
• GraphRAG는 opensource로 여기 링크에 있다.

GitHub - microsoft/graphrag: A modular graph-based Retrieval-Augmented Generation (RAG) system

---

2. Background

여기선 논문을 이해하는데 필요한 배경 지식을 설명하고 있다. 나도 RAG에 대하여 많이 알지 못하고 대부분 나와 비슷할 가능성이 높기에 이 부분도 정리하도록 한다.

 

2.1 RAG Approaches and Systems

• 일반적으로 RAG는 외부 data로부터 관련 정보를 검색하는데 user query를 사용하는 시스템을 말함
  • 이 정보로 응답을 생성함
• RAG는 data source가 context window를 넘어갈 정도로 많은 경우에 사용하기 이상적이다.
• 보편적인 RAG approaches에서 retrieval process는 query와 의미적으로 유사한 record set을 return하고 그 정보들로 정답 생성한다.
  
  • RAG는 text embedding을 사용하여 vector space에서 query와 가장 가까운 record를 가져온다.
• 일부 RAG approach들은 다른 retrieval mechanism을 사용하지만, 본 논문에선 이 모든 것들을 그냥 vector RAG라고 한다.
• GraphRAG는 vectorRAG와 global sensemaking이 요구되는 answer 능력에서 차이가 있다.
• GraphRAG는 self-memory의 형태로 datasource의 큰 부분 위에서 요약을 다룬다.
  • 여기서 요약은 이전 논문의 기법과 비슷하게 parallel and iteratively
• 특히, GraphRAG는 요약을 생성하기 위한 계층적 인덱싱을 사용하는 방법들과 유사하지만, source data로부터 graph index를 생성한다음 graph based community detection을 적용하여 데이터의 thematic partitioning을 생성한다는 점에서 차이가 있다.

---

2.2 Using Knowledge Graphs with LLMs and RAG

• natural language text corpora에서 knowledge graph extraction을 위한 방법은 아래를 포함한다.
  • rule-matching
  • statistical pattern recognition
  • clustering
  • embeddings
• GraphRAG는 knowledge graph extraction을 위해 LLM을 사용하는 최신 연구에 속한다. 또한, knowledge graph를 index로 사용하는 접근이 점점 늘고 있다.
  • 기존의 연구들에 대해 정리한다.
    • 일부 기법은 subgraph, elements of the graph, properties of the graph structure를 prompt에 직접 사용하거나 생성된 출력에 대한 사실적인 근거(factual grounding)으로 사용한다.
    • 다른 기법들은 knowledge graph를 retrieval을 향상시키기 위해 사용한다. 
  • GraphRAG는 위에 나온 접근들과 다르다.
    • 이전에 탐색하지 않은 graph의 특성에 초점을 맞춘다. (modularity, graph를 근접한 관계의 노드들의 nested modular communities 로 분할하는 능력)
    • 특히 GraphRAG는 global summaries를 만들기 위해 LLM을 사용함

---

2.3 Adaptive benchmarking for RAG Evaluation

• 평가를 위한 open-domain QA benchmark가 많이 존재한다.
  • HotPotQA
  • MultiHop-RAG
  • MT-Bench
• 하지만, 이러한 벤치마크들은 vector RAG performance에 치중되어 있다. (explicit fact retrieval)
• 그래서 본 논문에서는 corpus 전체에 대해 global sensemaking 평가를 위한 질문 셋을 만드는 접근을 제안한다.
  • 이 방식은 LLM Method와 관련이 있지만, 공정한 평가를 위해 corpus로부터 직접적으로 생성하지 않는다.
• Adaptive benchmarking은 specific domain/use case에 맞춘 평가 벤치마크를 동적으로 생성하는 process를 말한다.
  • 아니 이거 내가 오픈소스로 개발해볼까 생각했던건데 좀만 더 빨리 해볼걸...
  • Adaptive benchmakring
    • LLM based persona generation 연구를 기반으로 제작되었다.
      • LLM based persona generation -> LLM이 다양하고 authentic한 persona set를 만드는 분야
    • persona generation으로 현실의 RAG system 사용을 나타내는 query를 만든다. (현실성이 있는 평가다)

---

2.4 RAG evaluation criteria

• 본 논문의 평가 시스템은 LLM에 의존적인데, 기존 연구에서 LLM이 good evaluator라는 것을 보여왔다는 것을 언급하며 잘 선택했음을 말한다.
• 이전의 몇몇 연구들은 fluency와 같은 생성된 text의 품질을 정량화하기 위한 기준을 제안해왔는데, 이러한 기준들은 vector RAG system에 일반적이나, global sensemaking과는 관련이 없다.
• 그래서 본 논문에서는 glboal sensemaking question에 대답을 평가하기 위한 기준을 design한다.

---

3. Method

3.1 GraphRAG Workflow

Figure 1 GraphRAG Approach와 pipeline의 high-level data flow

---

3.1.1 Source Documents -> Text Chunks

Source Documents를 text chunks로 나누는 시작 단계로 LLM은 각 chunk에서 정보를 추출한다. 

 

여기서 chunk size 결정이 필요한데, longer chunks는 LLM call 횟수를 줄인다는 장점이 존재(비용 절감)하지만, chunk 초기에 나타나는 정보의 기억력 저하 문제가 나타난다.

---

3.1.2 Text Chunks -> Entities & Relationships

해당 단계에서는 LLM을 사용하여 주요 entity들과 entity와 chunk사이의 relationships를 추출하고, entity들과 relationships에 대한 짧은 설명을 생성한다.

 

예시를 들어보겠다. 아래와 같은 청크가 존재할때,

NeoChip’s (NC) shares surged in their first week of trading on the NewTech Exchange. However, market analysts caution that the chipmaker’s public debut may not reflect trends for other technology IPOs. NeoChip, previously a private entity, was acquired by Quantum Systems in 2016. The innovative semiconductor firm specializes in low-power processors for wearables and IoT devices.

LLM은 아래와 같이 추출한다.

The entity NeoChip, with description “NeoChip is a publicly traded company specializing in low-power processors for wearables and IoT devices.”

The entity Quantum Systems, with description “Quantum Systems is a firm that previously owned NeoChip.”

A relationship between NeoChip and Quantum Systems, with description “Quantum Systems owned NeoChip from 2016 until NeoChip became publicly traded.”

 

이를 생성하는 prompt는 적절한 few-shot exemplar들을 선택하여 domain에 맞춰 잘 생성하도록 할 수 있다.

 

일반적인 사람, 장소 같은 named entities를 추출하는 것은 그냥 해도 되지만, science, medicine, law같은 specialized knowledge에서는 few-shot examplars를 활용하여 domain에 맞출 수 있다는 말이다.

 

LLM은 또한, 아래와 같이 entities에 대해 중요한 사실 진술인 claims를 추출한다. (dates, evenets, 다른 entities와의 interactions 등)

NeoChip’s shares surged during their first week of trading on the NewTech Exchange.

NeoChip debuted as a publicly listed company on the NewTech Exchange.

Quantum Systems acquired NeoChip in 2016 and held ownership until NeoChip went public.

 

이 두 링크(Default Graph Extraction Prompt, Claim Extraction Prompt)에 논문 실험에 사용한 Prompt가 있다.

---

3.1.3 Entities & Relationships -> Knowledge Graph

위에서 Entity/Relationships/Claims를 추출했고 이제는 이를 엮어서 하나의 Graph로 만든다. 

 

Entities 인스턴스와 relationships 인스턴스들은 개별적인 node와 edge가 되고, Entity description은 각 node/edge에 대해 집계되고 요약된다.

 

Relationships는 graph edge로 집계되어, 중복된 수가 edge weight로 들어간다. Claim도 유사하게 동작한다.

 

Entity는 어떻게 할까?

본 논문에서 entity 매칭을 위해 exact string matching을 사용하나, prompt나 code를 약간 조정하여 softer matching approach로 도 사용할 수 있다.

 

GraphRAG는 중복된 enitities가 clustering되기에 상관없어서 exact string matching을 사용하는 것으로 보인다.

---

3.1.4 Knowledge Graph -> Graph Communities

이제 만든 Graph들을 communities로 나누는 작업을 진행한다.

 

많은 방법들이 존재하는데 본 논문에서는 Leiden community detection을 계층적 방식으로 사용하였다고 한다.

계층적 방식이란 더이상 나눠지지 않을때까지 반복적으로 각 community에서 sub communities를 detecting하는 것이다. 

 

이 계층의 각 단계는 graph의 노드들을 cover하는 community partition을 제공하여 divide-and-conquer global summarization을 가능하게 한다.

 

example dataset에서 계층적 partitioning 예시

---

3.1.5 Graph Communities -> Community Summaries

이제 우리는 Graph Communities까지 제작했다.

다음 단계는 Community를 설명하는 Community Summaries를 작성하는 과정이다.

 

이 단계에서는 very large dataset으로 확장하기 위해 design된 방법을 사용하여 report같은 summaries를 생성한다.

 

여기서 생성하는 Summaries는 global structure와 dataset의 의미를 이해하는데 유용하고, 구체적인 query 없이도, corpus의 이해를 돕는데 사용된다.

 

예를 들어 user는 관심있는 일반적인 주제를 찾기 위해 한 level의 community summaries를 scan하고 관련된 report들을 읽을 수 있다. 하지만, GraphRAG에서 이 기능은 global queries에 답변하는데 사용되는 graph-based index의 부분에 집중한다.

 

GraphRAG는 다양한 element의 summaries를 추가함으로써 community summaries를 생성한다. 

하위 community의 summaries는 상위 community의 summaries를 생성하는데 사용된다. 

Leaf-level communities : The element summaries of a leaf-level community are prioritized and then iteratively added to the LLM context window until the token limit is reached. The prioritization is as follows: for each community edge in decreasing order of combined source and target node degree (i.e., overall prominence), add descriptions of the source node, target node, the edge itself, and related claims.

Higher-level communities : If all element summaries fit within the token limit of the context window, proceed as for leaf-level communities and summarize all element summaries within the community. Otherwise, rank sub-communities in decreasing order of element summary tokens and iteratively substitute sub-community summaries (shorter) for their associated element summaries (longer) until they fit within the context window.

---

3.1.6 Community Summaries -> Community Answers -> Global Answer

이전 단계에서 생성한 Community Summaries를 이용하여 multi-stage process로 final answer를 생성할 것이다.

 

community structure의 계층적인 구조는 다른 level의 community summaries를 사용하여 답변될 수 있음을 의미하고, 특정 level에서 summary detail과 scope의 황밸을 제공하는지에 대해 질문을 제기한다. (이에 대한 평가는 아래 Analysis에서 진행한다.)

 

어떠한 user query에 대한 global answer는 아래 단계에 따라 생성된다.

1. Prepare community summaries : Community Summaries는 랜덤하게 섞이고 특정한 사이즈로 chunking하여 관련된 정보가 chunk들에 분산되도록 한다.
2. Map community answers : 중간 단계 답변은 병렬적으로 생성된다. 이때 LLM은 답변이 얼마나 도움이 되는지 나타내는 score를 생성하고, 0점이면 filtered out한다.
3. Reduce to global answer : 2단계에서 scoring한 답변을 내림차순 정렬하고 context window가 한계에 도달할 때까지 반복적으로 새로운 context window에 추가한다. 마지막 context는 global answer를 생성하는데 사용된다.

---

3.2 Global Sensemaking Question Generation

RAG system의 유효성을 평가하기 위해 위에서 LLM-as-a-judge를 사용한 방식을 제안한다고 언급하였다.

 

본 논문에서는 평가에 사용될 질문을 생성하기 위해 LLM을 사용하여 specific low-level facts를 검색할 필요 없이 주어진 corpus의 high-level understanding을 평가하도록 design된 corpus-question set를 생성하도록 한다.

 

대신에 high-level description과 목적이 주어지면 LLM은 RAG system을 사용할 가상의 사용자를 생성한다. 이 가상의 사용자들에 대해 LLM은 user가 RAG system으로 완료하고자하는 task를 생성하도록 한다.

 

이제 그럼 우리는 user-task set를 갖게 된다. user-task set 각각에 대해 LLM은 전체 corpus 이해가 필요한 질문(sensemaking question)을 생성한다. 아래는 이를 나타낸 알고리즘이다.

알고리즘은 아래와 같이 진행된다.

• Input : corpus 설명, user의 수(K), user당 task 수(N), user-task 조합 당 question 수(M)
• Output : K*M*N 개의 high-level question(sensemaking question)
• Procedure : 질문 생성
  • corpus 설명을 기반으로 LLM에 요청한다.
    • 이 데이터셋의 K개의 잠재적인 user의 persona를 설명하라.
    • (각 유저에 대해 반복)user와 관련된 N개의 task를 identify하라.
    • (user-task 쌍에 대해 반복) M개의 high-level question을 생성하라.
      • 전체 corpus의 이해를 요구하는 질문이어야 한다.
      • 낮은 수준의 사실 검색을 요구하면 안된다. (허접 질문 XX)
  • 생성된 질문을 Collect
• 끝!

본 논문의 평가에서는 K=N=M=5로 진행하여, 125개의 질문을 얻을 수 있었다. 아래는 두 평가 세트의 예시 질문이다.

---

3.3 Criteria for Evaluating Global Sensemaking

위에서 질문을 생성했으니, 이제 평가를 진행해야 한다.

 

LLM-as-a-judge를 사용하여 특정한 기준에 따라 상대적 우위를 평가하는 방식인 head-to-head comparison을 적용(like chatbot arena)한다. 

본 논문에서는 이 평가를 위해 아래의 global sensemaking activities에 적합한 target criteria를 design했다.

• Comprehensiveness : How much detail does the answer provide to cover all aspects and details of the question?  
• Diversity : How varied and rich is the answer in providing different perspectives and insights on the question?  
• Empowerment : How well does the answer help the reader understand and make informed judgments about the topic?

각 기준에 대한 자세한 prompt를 확인하면 아래와 같다. 

평가 Prompt

위의 prompt를 이용해 평가된 결과는 아래와 같이 나오게 된다.

 

평가 결과

---

4. Analysis

4.1 Experiment 1

4.1.1 Datasets

본 논문에서는 1M token 양의 2개의 데이터셋을 사용했다. Podcast, News articles

---

4.1.2 Conditions

총 6개의 조건을 비교했다.

• C0,C1,C2,C3 4개의 다른 graph communitiy level에서의 GraphRAG
  • C0 : root-level community summaries(가장 적음)
  • C1 : high-level community summaries. C0의 sub-communities가 존재하는 경우, 만약 없다면, C0를 그대로 사용 (projected downwards)
  • C2 : intermediate-level community summaries. (C2-C1 관계는 C1-C0 관계와 동일)
  • C3 : low-level community summaries(가장 많음). (C3-C2 관계는 C2-C1 관계와 동일)
• source texts에 직접 map-reduce를 적용한 text summarization method
  • TS : 3.1.6에서 사용한 것과 동일한 방식, source texts는 map-reduce 단계에서 shuffle되고 chunk됨
• vectorRAG로 semantic search approach
  • SS : vector RAG이용 ( context window에 들어갈 수 있는 최대 용량의 document를 검색하여 넣음)

동등한 비교를 위해 context window size와 prompt는 모두 동일하게 설정했다. (각 방법에 따른 약간의 수정사항은 존재)

---

4.1.3 Configuration

• context window size : 8K token
• Graph indexing : 600 token 
• virtual machine : 16GB RAM, Intel(R) Xeon(R) Platinum 8171M CPU @ 2.60GHz
• LLM : GPT-4-turbo(2M TPM, 10k RPM)
• Algorithm : Leiden community detection (graspologic library)
• prompt : Appendix E,F에 공개되어 있어서 첨부할라했는데 너무 길어서 패스 (논문에 있음)
• full statistical analysis 

---

4.2 Experiment 2

comprehensiveness와 diversity를 평가하기 위해 claim based measure를 구현했다고 한다.

 

여기서 Claim이라는 것은 "a statement that explicitly presents some verifiable facts."이다.

 

이 factual claims를 추출하기 위해, LLM을 이용하여 적어도 한개의 Claim을 포함하는 답변을 식별하는 방식인 Claimify 를 사용했다고 한다.

 

논문에서는 Experiment1에서 조건하에 생성된 answer에 Claimify를 적용했고, 각 답변에 중복된 claim을 제거한 후, 47075개의 unique claim을 추출했다고 한다. (이는 평균적으로 답변 당 31개의 claim이라 한다.)

 

Experiment 2에서 metric은 아래와 같이 두개이다.

1. Comprehensiveness : Measured as the average number of claims extracted from the answers generated under each condition.  
2. Diversity : Measured by clustering the claims for each answer and calculating the average number of clusters.

Clustering에서 Scikit learn의 agglomerative clustering을 사용한 방식을 이용했다.

 

이 방식은 Cluster의 가장 먼 point들 사이의 거리가 threshold 이하일 때, 둘을 결합하는 방식이다. distance는 1-ROUGE-L을 사용한다. 

이때, distance threshold가 cluster의 숫자에 영향을 주기 때문에, threshold에 따른 결과들을 같이 공유한다. (Result에서 서술)

---

5. Results

5.1 Experiment 1

Global approaches vs. vector RAG

아래의 결과(Figure2,Table6)를 보게되면, global approach(GraphRAG)가 vector RAG의 결과를 Comprehensive/Diversity에서 outperform함을 확인할 수 있다. 그러나 Empowerment에서는 압도적이진 못했고, 섞인듯한 결과가 나왔다. 이는 Tuning element extraction prompt를 이용하여 개선할 수 있다고 한다.

 

---

Community summaries vs. source texts

위에서 vector RAG와 비교했으니 이번에는 Community summaries와 source text를 비교한다. (Figure 2참고)

 

먼저 comprehensive win-rate을 비교한다.

Podcast dataset(Intermediate)에서 commutnity summaries가 57%의 win-rate, News Dataset(low-level)에서 64% winrate을 달성한다.

다음으로 Diversity win-rate은 community summaries가 57%, 60%를 달성한다.

 

아래의 Table 2는 GraphRAG의 scalability를 TS(source text)와 비교하여 설명한다.

C3(low-level community summaries)에선 GraphRAG가 26~33% 낮은 context token을 요구하고 C0(root-level)에선 97% 이상의 token을 적게 요구한다.

이렇게 낮은 token을 요구하는 C0에선 성능이 약간 하락하나 쓸만하다고 하고, iterative QA에서 높은 효율성을 제공한다고 한다.

---

5.2 Experiment2

아래의 Table3는 추출된 claim의 평균 개수를 보여준다. 모든 Global Search와 TS가 VectorRAG보다 0.05 이상 나은 것을 보여준다.

Table4는 cluster의 평균 개수를 나타낸다. 이 또한, 위의 LLM win-rate 결과와 일치하는 성능을 보였다. 

측정은 claim들을 유사도별로 clustering한 평균 cluster의 개수를 측정한 것이고, distance threshold는 0.5~0.8까지 다양하게 측정했다.

 

둘 모두에서 모든 distance threshold에서 SS대비 우수한 성능을 보였다.

---

나가며

이렇게 GraphRAG에 대한 방식을 정리해보았다.

 

모든 문제 해결에는 적합한 기술이 따로 존재한다는걸 다시 한 번 느끼게 되었다. 이를 가장 잘하기 위해서는 꾸준히 기술을 학습하고 익혀두는게 중요할 것 같다.