[논문리뷰] GNN-RAG : Graph Neural Retrieval for Large Language Model Reasoning

Abstract

• Knowledge Graphs (KGs)는 (head, relation, tail) 형태의 triplet
• Graph Neural Networks (GNNs)는 KG에 저장된 복잡한 그래프 정보를 처리할 수 있어 KGQuestioning Anaswering Task에서 널리 사용
• GNN-RAG를 소개 : RAG 방식으로 LLM의 언어 이해 능력과 GNN의 추론 능력을 결합하는 새로운 방법
  • 첫째, GNN이 주어진 질문에 대한 답변 후보를 찾기 위해 dense KG subgraph에 대해 추론을 수행
  • 둘째, KG 내에서 질문 엔티티와 답변 후보를 연결하는 최단 경로를 추출하여 KG 추론 경로를 표현
    • 추출된 경로는 자연어로 변환되어 LLM의 RAG 추론을 위한 입력으로 제공
  •  GNN-RAG 프레임워크에서 GNN은 유용한 그래프 정보를 추출하는 dense subgraph reasoner로 작동하고, LLM은 궁극적인 KGQA를 위한 자연어 처리 역량을 씀.
•  GNN-RAG와 함께 KGQA 성능을 더욱 향상시키기 위한 retrieval augmentation (RA) 기술을 개발
• 실험 결과
  • 최고 성능을 달성
  • 7B tuned LLM으로 GPT-4의 성능을 능가하거나 비슷함.
  • GNN-RAG는 multi-hop 및 multi-entity 질문에서 뛰어남

1 Introduction

• LLM의 특성과 한계
  • LLM은 자연어 이해에 뛰어나며 많은 NLP 태스크에서 최고 성능을 보임
  • 이러한 능력은 대규모 텍스트 데이터에 대한 사전학습에서 비롯됨
  • 하지만 사전학습이 비용과 시간이 많이 들기 때문에:
    • 새로운 지식이나 도메인별 지식에 쉽게 적응하지 못함
    • Hallucination(환각, 잘못된 정보 생성) 문제가 있음
• Knowledge Graphs (KGs)의 특성
  • 구조화된 형태로 정보를 저장하는 데이터베이스
  • 정보는 triplet 형태로 저장 (예: <Jamaica → language_spoken → English>)
  • 장점:
    • 쉽게 업데이트 가능
    • 복잡한 상호작용(예: multi-hop relations) 표현 가능
    • 지식 집약적 태스크(예: QA)에 널리 사용됨
• Retrieval-augmented generation (RAG)
  • LLM의 hallucination을 줄이기 위한 프레임워크
  • KG에서 얻은 최신의 정확한 정보로 입력 컨텍스트를 보강
  •  예시:
    • 입력: "Knowledge: Jamaica → language_spoken → English"
    • 질문: "Which language do Jamaican people speak?"
  •  하지만 RAG의 성능은 검색된 KG 품질에 크게 의존함
• 현재 검색 방법의 문제점
  • KG는 수백만 개의 사실을 포함하는 복잡한 그래프 정보 저장
  • 올바른 정보 검색이 어려움
  • 부적절한 정보 검색은 LLM의 KGQA 추론을 방해할 수 있음
  • 기존 LLM 기반 검색 방법의 한계:
    • 복잡한 그래프 정보 처리 능력 부족
    • Multi-hop KGQA에서 성능 저하
    • 누락된 정보를 보완하기 위해 GPT-4와 같은 대형 LLM에 의존
      (누락한 정보는 LLM의 Reasoning성능으로 대체)
• GNN-RAG의 제안
  • GNN의 그래프 처리 능력과 LLM의 자연어 이해 능력을 결합
  • 주요 프로세스:
    • GNN이 dense KG subgraph에서 답변 후보 검색
    • 질문 엔티티와 GNN 기반 답변을 연결하는 최단 경로 추출
    • 추출된 경로를 자연어로 변환하여 LLM에 입력
• 논문의 주요 기여
  • Framework: GNN-RAG 개발 및 retrieval augmentation 기술
  • Effectiveness & Faithfulness: 최신 성능 달성, 특히 복잡한 질문에서 우수
  • Efficiency: 추가 LLM 호출 없이 성능 향상, 7B LLM으로 GPT-4 수준 달성

 

2 Related Work

2.1 KGQA Methods (지식 그래프 질의응답 방법)

• A) Semantic Parsing (SP) 방법:
  • 작동 방식: 자연어 질문을 논리적 형태(예: SPARQL 쿼리)의 쿼리로 변환, 변환된 쿼리를 KG에서 실행하여 답변 획득
  • 한계점:
    • 학습을 위해 ground-truth 논리적 쿼리가 필요함
    • 이러한 데이터는 실제로 만들기 어려움
    • 구문이나 의미 오류로 인해 실행 불가능한 쿼리가 생성될 수 있음
• B) Information Retrieval (IR) 방법:
  • 특징: 작은양의-supervised KGQA 설정에 중점, 학습을 위해 질문-답변 쌍만 필요
  • 작동 방식:
    • KG 정보 검색(예: KG subgraph) : query에 들어있는 entity기반으로 KG에서 entity search. search된 entity의 relation들을 살펴봄.
    • 검색된 정보를 KGQA 추론의 입력으로 사용

2.2 Graph-Augmented LM

• A) Latent Graph Information을 활용한 방법:
  • GNN으로 얻은 잠재 그래프 정보로 LM 강화
  • 한계점 : 언어와 그래프 간의 모달리티 불일치 문제, 지식 집약적 태스크에서 성능 저하
• B) Verbalized Graph Information을 활용한 방법:
  • RAG와 유사하게 자연어로 변환된 그래프 정보를 입력으로 사용
  • 한계점: 그래프가 큰 경우 노이즈가 있는 정보를 가져올 수 있음 -> 이는 LM의 추론 능력을 저하시킬 수 있음

 

3. Problem Statement & Background

• KGQA : (v, r, v') 표현되는 KG(G)가 주어진다
  - G와 자연어 질문 q가 주어졌을 때, KGQA의 태스크는 q에 정확하게 답하는 엔티티 집합 {a} ∈ G를 추출하는 것
  - 학습을 위해 질문-답변 쌍은 주어지지만, 답변으로 이어지는 ground-truth 경로는 주어지지 않음.
  • v : head entity
  • v' : tail entity
  • r : 두 엔티티의 관계
• Retrieval & Reasoning
  • KG는 보통 수백만 개의 노드를 포함하기 때문에, 질문 q에 대해 특정 서브그래프 $G_q$가 검색된다(예: entity linking과 neighbor extraction을 통해).
  • 이상적으로는, 질문에 대한 모든 정확한 답변이 검색된 서브그래프에 포함되어 있어야 한다. ({a} ∈ $G_q$).
  • 검색된 서브그래프 $G_q$와 질문 q는 추론모델(GNN, LLM)의 입력으로 사용되어 정확한 답변을 출력
• GNNs:
  • KGQA는 KG 엔티티들을 주어진 질문에 대한 답변과 비답변으로 분류하는 노드 분류 문제로 볼 수 있다.
    (연관이 있는지 없는지)
  • GNN은 노드 분류와 같은 태스크에 강함.
  • GNN은 각 이웃 v'로부터의 메시지 $m^{(l)}_{vv'}$를 집계하여 layer l에서 노드 v의 표현 $h^{(l)}_v$를 업데이트.
  • Eq1 : $h^{(l)}v = \psi(h^{(l-1)}v, \sum{v' \in N_v} \omega(q,r) \cdot m^{(l)}{vv'})$
    • 여기서:
      • 함수 ω(·)는 fact (v, r, v')의 관계 r이 질문 q와 얼마나 관련있는지를 측정
        (잘 보면 가중합)
      • 이웃 메시지 $m^{(l)}_{vv'}$는 GNN에서 일반적으로 사용되는 sum-operator Σ로 집계)(정보를 섞음)
      • 함수 ψ(·)는 연속된 GNN 레이어의 표현을 결합(NeuralNet)
• LLMs:
  • LLM은 KG 정보를 사용하여 RAG 수행
    • 검색된 서브그래프는 LLM이 처리할 수 있도록 자연어로 변환
    • LLM에 주어지는 입력은 KG 정보와 함께 질문과 프롬프트를 포함
    • 예를 들어, 입력은 다음과 같다:
      "Knowledge: Jamaica → language_spoken → English
      "Question: Which language do Jamaican people speak?"

• Landscape of KGQA method(Figure 2)
  • Figure 2는 KG 검색과 추론 측면에서 현재 존재하는 KGQA 방법론들의 현황 보여줌
  • GNN 기반 방법: GraftNet, NSM, ReaRev와 같은 GNN 기반 방법들은 복잡한 그래프 정보를 처리할 수 있는 GNN의 능력을 활용하여 dense KG subgraph에서 추론을 수행
  • LLM 기반 방법: 최근의 LLM 기반 방법들은 검색과 추론 모두에 LLM의 능력을 활용:
    - ToG: LLM을 사용하여 hop-by-hop으로 관련 사실들을 검색
    - RoG: LLM을 사용하여 가능성 있는 관계 경로를 생성하고, 이를 KG에 매핑하여 관련 정보를 검색
• LLM-based Retriever.
  • RoG의 예시 :
    1. 학습을 위한 질문-답변 쌍이 주어졌을 때, RoG는 retriever를 fine-tuning하기 위해 question 엔티티에서 시작하여 답변으로 이어지는 최단 경로를 추출.
    2. 추출된 경로를 기반으로, LLM(LLaMA2-Chat-7B)은 질문 q가 주어졌을 때 추론 경로를 생성하도록 fine-tuning
    Eq2 : LLM(prompt, q) ⇒ {r₁ → ··· → rₜ}ᵏ
    - 여기서 프롬프트는 "Please generate a valid relation path that can be helpful for answering the following question: {Question}" 이다.
    - 더 나은 답변 커버리지를 위해 beam-search 디코딩을 사용하여 k개의 다양한 추론 경로 집합을 생성
  • 생성된 경로는 질문 엔티티에서 시작하여 KG에 매핑되어 RAG를 위한 중간 엔티티들을 검색
    예: <Jamaica → language_spoken → English>

4. GNN-RAG

RAG 방식으로 LLM의 언어 이해 능력과 GNN의 추론 능력을 결합하는 방법인 GNN-RAG를 제안.

• 첫째, GNN이 주어진 질문에 대한 답변 후보를 검색하기 위해 dense KG subgraph에 대해 추론 수행
• 둘째, 질문의 엔티티와 GNN 기반 답변을 연결하는 KG 내의 최단 경로를 추출하여 유용한 KG 추론 경로를 표현
  • 추출된 경로는 자연어로 변환되어 LLM의 RAG 추론을 위한 입력으로 제공.
  • GNN-RAG 프레임워크에서
    • GNN : 유용한 그래프 정보를 추출하는 dense subgraph reasoner로 작동
    • LLM : 자연어 처리 능력을 활용하여 최종 KGQA를 수행

4.1 GNN

• embedding 방법 대신 GNN을 선호하는 이유는
• 복잡한 그래프 상호작용을 처리하고 multi-hop 질문에 답할 수 있는 능력 때문
  (multi-hop : 여러 단계의 추론이 필요한 경우)
  
  • GNN은 다양한 추론 경로를 탐색하는 구조적 이점으로 인해 높은 answer recall을 달성하여 검색에 적합한 후보가 된다
  • GNN 추론이 완료되면(Equation 1을 통한 L번의 GNN 업데이트), 서브그래프의 모든 노드는 최종 GNN 표현 $h^{(L)}_v$를 기반으로 답변과 비답변으로 점수가 매겨지고, softmax(·) 연산이 뒤따른다. GNN 파라미터는 학습 질문-답변 쌍을 사용하여 노드 분류(답변 vs. 비답변)를 통해 최적화됨
  • 결론 : GNN Neural Network를 학습하여, 해당 노드의 정보가 유용한지 안한지 판단.
  • 추론 시
    • 임계값보다 높은 확률 점수를 가진 노드들이 후보 답변으로 반환, 질문 엔티티와 후보 답변을 연결하는 최단 경로(추론 경로)도 함께 반환. 검색된 추론 경로는 LLM 기반 RAG의 입력으로 사용
    • 서로 다른 GNN은 RAG를 위해 서로 다른 추론 경로를 가져올 수 있다. Equation 3에서 보여지듯이, GNN 추론은 question-relation matching 연산 ω(q, r)에 의존
      • Eq3 : $q^{(k)} = γ_k(LM(q))$, $r = γ_c(LM(r))$
      • ω : question-relation matching function(0~1 사이 값)
      • r : KG의 관계를 벡터 형태로 표현한 것
      • ω(q, r) : query와 r의 관계를 계산
      • γ_k : attention-based pooling
        -> Query : What language are spoken in Jamaica?
        -> Attention을 기반으로 하여, Embedding 가중치를 주어 Query를 Embedding함.
        -> 학습 가능한 파라미터를 포함한 동적 pooling
        -> 질문의 다양한 의미적 측면을 포착
      • γ_c : [CLS]  token pooling
        -> 관계를 단일 벡터로 압축.
        -> 고정된 위치의 토큰을 사용하는 단순 pooling
        -> 관계의 전체적인 의미를 효율적으로 표현
    •  ω(q, r)의 일반적인 구현은 ϕ(q^(k) ⊙ r) : query가 k개의 layer를 통과한 뒤의 hidden state과 relation의 원소 곱을하고, ϕ(신경망)으로 score계산
  • Appendix B에서 우리는 GNN의 출력이 question-relation matching 연산 ω(q, r)에 의존한다는 것을 보여주는 정리함, 
• 서로 다른 GNN 아키텍처를 시도하는 대신, 서로 다른 출력 노드 표현을 결과로 내는 서로 다른 LM을 Equation 3에서 사용.
  구체적으로, 두 개의 별도 GNN 모델을 학습 : 
  • SBERT와 같은 사전학습된 LM을 사용하는 모델
  • KG에서의 question-relation matching을 위해 사전학습된 LM_SR(GNN Pretrained Model)을 사용하는 모델
•  다른 GNN들이 서로 다른 KG 정보를 검색하지만, 둘 다 RAG 기반 KGQA를 개선한다는 것을 보여줌.

4.2 LLM

GNN-RAG로부터 추론 경로를 얻은 후, 자연어로 변환하여 ChatGPT나 LLaMA와 같은 downstream LLM에 입력으로 제공

• 하지만 LLM은 입력 프롬프트 템플릿과 그래프 정보가 자연어로 변환되는 방식에 민감
  • 학습이 가능한 LLM에 대해 RAG 프롬프트 튜닝을 진행(LLaMA2-Chat-7B 모델)
  • 다음과 같은 프롬프트가 주어졌을 때 정확한 답변 목록을 생성하도록 학습 질문-답변 쌍을 기반으로 fine-tuning :
    • "Based on the reasoning paths, please answer the given question.
      Reasoning Paths: {Reasoning Paths}
      Question: {Question}"
    • 예) 
      입력 예시:
        "Based on the reasoning paths, please answer the given question. Reasoning Paths:
          Jamaica → language_spoken → English Jamaica → official_language → English
      Question: Which language do Jamaican people speak?"
        목표 출력: "English"
      
    • 추론 경로는 다음과 같이 자연어로 변환:
      "{question entity} → {relation} → {entity} → ··· → {relation} → {answer entity} \n" (Figure 3 참조)
  • 학습 중에는 추론 경로가 질문 엔티티에서 답변 엔티티로 이어지는 최단 경로.
    추론 시에는 추론 경로가 GNN-RAG를 통해 얻어짐

4.3 Retrieval Analysis: Why GNNs & Their Limitations

GNN은 그래프 구조를 활용하여 multi-hop 정보를 포함하는 KG의 관련 부분을 검색

GNN이 multi-hop KGQA를 위한 좋은 retriever인 이유에 대한 실험적 증거 제시.

- 두 개의 서로 다른 GNN, 즉 deep GNN(L = 3)과 shallow GNN(L = 1)을 학습하고 이들의 검색 능력을 측정

- 평가지표 : 'Answer Coverage' 메트릭(retriever가 RAG를 위해 최소한 하나의 정확한 답변을 가져올 수 있는지)

   (KGQA 성능이 아닌 retriever가 관련 KG 정보를 가져오는지를 측정)

 

실험 결과 : 

Multi-hop 질문에서:

• Deep GNN(L=3)이 가장 우수한 성능
• LLM과 Shallow GNN보다 효과적(높은 Answer Coverage)
• 더 효율적(적은 Input Tokens)

GNN의 한계점:

• Single-hop(간단한) 질문에서는 성능이 떨어짐
• 이유: 깊은 그래프 탐색보다 질문-관계 매칭의 정확도가 더 중요
• 이런 경우에는 자연어 이해가 뛰어난 LLM retriever가 더 효과적

GNN이 복잡한 multi-hop 질문에서는 뛰어나지만, 단순한 질문에서는 LLM이 더 효과적이라는 것을 실험적으로 입증
-> GNN-RAG + RA를 제안하는 근거가 됨

 

4.4 Retrieval Augmentation (RA)

4.3의 결과에 인사이트를 얻어, 우리는 GNN retriever를 LLM 기반 retriever와 결합하는 (GNN-RGA+RA) 제시

A. GNN-RAG+RA (GNN과 LLM 결합):

• GNN retriever: multi-hop 질문에 강점
• LLM retriever: single-hop 질문에 강점
• 작동방식: 두 retriever의 추론 경로를 합집합으로 결합

B. GNN-RAG+Ensemble (서로 다른 GNN 결합):

• GNN+SBERT
• GNN+LM_SR
• 작동방식: 두 GNN의 검색 경로를 합집합으로 결합

 

그래서 어떻게 GNN에서 Retrieve하는 거지?

# 논문에서 언급된 구현 세부사항:

1. 초기 subgraph 추출

- Entity Linking을 통해 질문에서 언급된 엔티티들을 KG의 엔티티와 매핑

- PageRank Nibble (PRN) 알고리즘을 사용하여 링크된 엔티티에서 시작

     시작점 : 링크된 엔티티들
     목표 : top-m 엔티티 선택하여 subgraph구성

- Top-m개(m = 2,000)의 엔티티를 포함하는 서브그래프 선택 - 2000개의 score를 계산.

 

2. Query-graph matching : 

- Equation 3에 의해, query와 relation을 embedding변환

- 질문과 관계 간의 점수 계산 : ω(q, r) = ϕ(q^(k) ⊙ r) 

 

3. GNN을 통한 정보 전파 :
- Equation 1에 의해, GNN업데이트

 

4. 답변 후보 선택:

- 모든 노드에 대해 softmax를 통해 답변 확률 계산

- 확률이 임계값 보다 높은 노드들을 후보로 선택

- 선택된 후보 노드들까지의 최단 경로 추출

 

 

5. Experiment Setup 생략

6. Results 생략

7. Conclusion 생략