[논문 리뷰] From Local to Global: A Graph RAG Approach to Query-Focused Summarization

핵심 개념

• Graph RAG (Retrieval-Augmented Generation)
  대규모 언어 모델(LLM)이 전체 문서 집합에 대한 질문에 답변하기 위해, 지식 그래프를 생성하고 이를 활용해 질의 중심 요약(Query-Focused Summarization)을 수행하는 새로운 접근법
• 기존 RAG의 한계
  지역적 텍스트 추출은 전체 문서 요약을 다루기에 충분하지 않음
  LLM의 컨텍스트 윈도우 크기 제한으로 인해 텍스트의 중요한 정보 손실
• 제안된 해결책
  그래프 기반 지식 인덱스를 생성하고 커뮤니티 탐지 알고리즘(Leiden)을 적용해 효율적이고 종합적인 응답 제공

---

• 문제 의식
  기존 RAG는 Chunk 단위로 전체 맥락을 가져오기 때문에, 전체 맥락을 가져오지 못 할 수도 있고, 전체 코퍼스에 대한 질의 중심의 추상적인 요약이 어려움(QFS -Query-Focused Summarization)
• 제안 방법
  

  

Graph RAG는 (1) document에서 entity를 추출해서 (2) 유사 entities끼리 community를 만들고, (3) 이러한 community(local단위)끼리 summarization을 한 뒤, (4) 이것들을 모아서 global summarization을 하는 일종의 'map reduce' 방식임

단위별로 쪼개서 요약을 진행하는 이유는 LLM의 input length의 제한이 있으며, 한번에 처리했을 때 정보가 소실될 수 있기 때문이다.

 

1. Source Documents -> Text Chunks

 

retrieve를 할 문서에서 chunking을 진행하는 단계이다. chunk의 사이즈가 크면 클 수록 entity를 추출하는 횟수가 줄어들지만, recall 성능이 저하된다고 한다.

즉 600 토큰의 청크 크기를 사용하면 2400의 청크 크기를 사용할 때보다 거의 두 배나 많은 entity가 추출

2. Text Chunks -> Element Instances

이 단계에서는 chunk에서 entity를 추출하는데, 이때 LLM에 few-shot example을 넣은 prompt를 활용한다. 우선적으로 각 entity를 판별하는데, 이때의 entity는 people, places, organizations 등이 되는데, 도메인에 따라 세부적으로 분류할 수 있다.

자세한 설명은 코드 참고 → 링크

3. Element Instaces -> Element Summaries

이 단계에서는 이전에 추출된 entity, relationships, claims에 대해서 이미 작성된 추상적인 description을 기반으로 summarize를 진행한다. 각 인스턴스 레벨의 요약글을 하나의 single-blocks 요약으로 추가적인 요약을 하는 것이다.

이때의 bottle neck은 '동일한 entity명에 대해서 항상 같은 description이 적히지 않아서 중복이 발생할 수 있다는 것'이다.

4. Element Summaries -> Graph Communities

인덱싱이 다 된 객체들을 Leiden 알고리즘으로 그래프를 커뮤니티로 분할

Leiden 알고리즘 - 위키피디아
클러스터링 알고리즘 종류로 커뮤니티 탐지 알고리즘입니다 . 이 알고리즘은 루뱅 방법 을 수정하여 개발되었습니다. 루뱅 방법과 마찬가지로 라이덴 알고리즘은 네트워크에서 커뮤니티를 추출할 때 모듈성을 최적화하려고 시도 하지만 루뱅 방법에서 나타나는 주요 문제, 즉 연결성이 낮은 커뮤니티와 모듈성의 해상도 한계를 해결합니다.

5. Graph Communities -> Community Summaries

커뮤니티 내 주요 entity와 관계를 요약

• leaf-level community
  리프 수준 커뮤니티(노드, 에지, 공변량)의 요소 요약에 우선순위가 부여된 다음 토큰 제한에 도달할 때까지 LLM 컨텍스트 창에 반복적으로 추가. 우선 순위는 source node와 target node의 결합 정도(예: 전체 중요도)가 감소하는 순서로 각 커뮤니티 가장자리에 대해 source node, target node, linked covariate, edge 자체에 대한 설명을 추가
• higher-level community
  모든 element 요약이 컨텍스트 창의 토큰 제한 내에 맞는 경우 리프 수준 커뮤니티와 마찬가지로 진행하고 커뮤니티 내의 모든 element 요약을 요약함. 컨텐스트의 길이가 긴 경우, element 요약 토큰의 내림차순으로 하위 커뮤니티의 순위를 지정하고 컨텍스트 창에 맞을 때까지 관련 element 요약(더 긴)을 하위 커뮤니티 요약(더 짧은)으로 반복적으로 대체함

6. Community Summaries -> Community Answers -> Global Answer

사용자의 query가 들어왔을 때, 앞에서 생성된 community summarization은 retrieve chunk로써 사용될 수 있다. 특정 community 수준에서 사용자의 query에 대한 전체 답변은 다음과 같이 생성됨

• Prepare community summaries
  커뮤니티 요약은 무작위로 섞이고 미리 지정된 토큰 크기의 덩어리로 나뉜다. 이를 통해 관련 정보가 단일 컨텍스트 창에 집중(및 잠재적으로 손실될 수 있음)하는 대신 여러 청크로 분산된다.
• Map community answers(map)
  각 청크마다 하나씩 중간 답변을 병렬로 생성한다. LLM은 또한 생성된 답변이 목표 질문에 답변하는 데 얼마나 도움이 되는지 나타내는 0-100 사이의 점수를 생성하도록 요청받는다. 점수가 0인 답변은 필터링된다.
• Reduce to global answer(reduce)
  중간 커뮤니티 답변은 유용성 점수의 내림차순으로 정렬되고 토큰 제한에 도달할 때까지 새 컨텍스트 창에 반복적으로 추가된다. 이 최종 컨텍스트는 사용자에게 반환되는 전역 응답을 생성하는 데 사용된다.

---

평가 결과

• 데이터셋
  Podcast 대본 (약 100만 토큰)
  뉴스 기사 (약 170만 토큰)
• 메트릭
  종합성(comprehensiveness), 다양성(diversity), 사용성(empowerment), 명확성(directness)
• 비교 조건
  전통적인 RAG와 그래프 없는 Map-Reduce 요약과 비교
  그래프 기반 요약(C0, C1, C2, C3) 수준에 따라 성능 분석
  • C0: 루트 수준 커뮤니티 요약을 사용하여 질문에 답변. 매우 광범위한 내용을 포괄
    C1: 상위 수준 커뮤니티 요약을 사용하여 질문에 답변.C0의 하위 커뮤니티들로 구성
    C2: 중간 수준 커뮤니티 요약을 사용하여 질문에 답변. C1의 하위 커뮤니티들로 구성
    C3: 하위 수준 커뮤니티 요약을 사용하여 질문에 답변. C2의 하위 커뮤니티들로 구성
• 결과
  그래프 RAG는 전통적인 RAG보다 종합성과 다양성이 높음
  중간 수준의 커뮤니티 요약(C1, C2)은 최상의 성능을 제공
  루트 수준 커뮤니티 요약(C0)은 최소한의 토큰 사용으로 효율

---

 

QnA
여기서 설명하는 Entity란?
사람(Person), 장소(Location), 조직(Organization) 등 명명된 개체(Named Entity)를 포함하며, 관계(Relation)와 주장(Claim)과 함께 지식 그래프(Knowledge Graph)를 구성하는 기본 요소입니다.

예제 문서:
"Albert Einstein developed the Theory of Relativity, which transformed physics. He worked closely with the Swiss Patent Office in Bern. Later, his work was recognized by organizations like the Nobel Prize committee."

엔티티 추출 결과:
Person: "Albert Einstein"
Concept: "Theory of Relativity", "Physics"
Organization: "Swiss Patent Office", "Nobel Prize committee"
Location: "Bern"

 

어떻게 커뮤니티 레벨을 분류하는지? 

논문에서는 커뮤니티를 탐지하기 위해 Leiden 알고리즘을 이용하여 4단계의 레벨을 사용합니다.

https://github.com/microsoft/graphrag/blob/e6de713f25eb9299cd9ad7530156044cbb1de37f/graphrag/model/community.py#L16

이러한 계층적 분류는 데이터의 복잡성과 자연스러운 클러스터링 구조에 의해 결정되며, 사용자가 별도로 지정이 가능합니다.

 

Task마다 작업 단계가 달라지나? 

Graph RAG의 작업 단계는 Task의 목적과 요구사항에 따라 달라질 수 있을거 같습니다.

 

graph rag를 만들 때 사용한 모델은?

GPT-4 Turbo 입니다. Welcome - GraphRAG

 

graph는 어떻게 저장되냐?

해당 연구에서는 Neo4j에 저장됩니다. 추가로 Milvus 에서도 저장이 가능합니다.

 

---

참고자료

From Local to Global: A Graph RAG Approach to Query-Focused Summarization

graphrag/graphrag/prompts/index/claim_extraction.py at c1c09bab8078bc279722e3237f18dd5bd100d512 · microsoft/graphrag

[논문 리뷰] From Local to Global: A Graph RAG Approach to Query-Focused Summarization