GRAG Graph Retrieval-Augmented Generation

1. Introduction

Naive RAG는 query와 유사한 개별 문서를 검색하는 방식으로 설계되었으며, 문서 간 연결 구조를 고려하지 않음. 반면, 현실 세계의 문서들은 일반적으로 독립적이지 않고, textual graph 형태로 상호 연결됨. 대표적인 예로는:

소셜 미디어 게시물 간의 social interaction
연구 논문 간의 citation graph
지식 그래프 내 entity relation
제품 리뷰와 구매 이력 간의 purchase linkage 등이 존재함

이러한 networked document 구조는 적절한 retrieval과 LLM 기반 generation을 위한 핵심 정보로 작용함. 예를 들어, 태양 플레어 예측 분야의 최신 기술 동향을 파악하고자 하는 연구자는 관련 논문 간의 mutual referencing link를 따라가며 기술 진화의 흐름을 파악하고, comprehensive한 retrieval coverage를 달성할 필요가 있음. 이는 주제적으로 연관된 entity들이 연결될 경우, subgraph 단위의 retrieval을 통해 정밀도와 견고성이 향상된다는 점을 시사함.

이러한 배경을 바탕으로, GRAG 프레임워크가 제안됨. GRAG는 전통적인 RAG 방식과 달리, document 간의 연결 구조를 retrieval 및 generation의 전 과정에 통합함. 이를 통해 다음 두 가지 근본적인 문제를 해결하고자 함:

Textual Subgraph Retrieval high-dimensional textual features를 가지는 node 및 edge로 구성된 textual graph에서, query에 관련된 subgraph를 효율적으로 검색하는 문제. 이 문제는 combinatorial explosion과 embedding space의 복잡성으로 인해 NP-hard한 최적화 과제로 정의됨.
Textual Subgraph Integration into LLMs 검색된 textual subgraph의 textual 및 topological information을 LLM에 효과적으로 전달하여, 양자 간의 interdependence를 보존한 채 generation을 수행하는 문제.

이러한 과제를 해결하기 위해, GRAG는 다음과 같은 computational framework를 제안함:

Divide-and-Conquer 기반 서브그래프 검색 전체 subgraph search space는 2^|V|+|E|로 NP-hard함. 이를 회피하기 위해, GRAG는 먼저 query-relevant한 ego-graphs를 탐색하고, 이후 soft pruning 메커니즘을 통해 noise가 포함된 node와 edge를 제거함으로써 최적에 가까운 subgraph 구조를 구성함.
Dual-Prompt Strategy: Text View + Graph View
- Text View (Hard Prompt): 검색된 textual subgraph를 계층적 서술 구조로 변환하여, topological information을 포함한 text tokens 형태로 LLM에 입력함. 이 변환 과정은 저자들이 제안한 알고리즘에 기반함.
- Graph View (Soft Prompt): textual subgraph를 graph encoder (= GNN)를 통해 임베딩하고, node/edge의 텍스트 속성을 포함한 soft tokens로 변환함. 이는 LLM의 embedding space와 aligned되어, 구조적 문맥을 보완함.

이러한 이중 프롬프트 구조는 LLM이 textual graph 내 entity 간 관계와 문맥 흐름을 보다 깊이 이해할 수 있도록 함. 결과적으로, 생성된 응답은 query와 graph context 모두에 정합적인 형태를 띠게 됨.

실험 결과, GRAG는 multi-hop graph reasoning을 요구하는 다양한 benchmark 과제에서 기존 RAG 기반 retriever 및 LLM 단독 모델보다 우수한 성능을 보임. 특히, fine-tuning 없이 GRAG만을 적용한 frozen LLM이, fine-tuned LLM을 모든 task에서 일관되게 능가함.

Main Contributions

Graph Retrieval-Augmented Generation(GRAG) 문제를 정식화하고, textual graph 문맥을 통합하는 효율적인 computational framework를 제안함
textual graphs를 hierarchical text descriptions로 변환하여 topological structure를 보존하는 hard prompt generation 기법을 제안함
relevant textual subgraph를 효율적으로 추출하기 위한 divide-and-conquer 기반 근사 최적화 전략을 제안함
multi-hop graph reasoning benchmark에서 기존 SOTA RAG 방법들을 상회하는 성능을 실험적으로 입증함

2.1 Prompt Tuning

전통적인 fine-tuning 기법은 모델의 내부 파라미터를 업데이트하는 방식으로 동작하며, 대표적으로 LoRA가 있음. 이에 비해 prompt tuning은 모델 파라미터를 변경하지 않고, 입력 자체를 조정하여 모델 출력을 유도하는 방식임.

AutoPrompt (Shin et al., 2020), Prompt Tuning (Lester et al., 2021) 등의 기법은 수작업 없이 효과적인 prompt를 자동으로 생성하는 방식으로 제안되었으며, 특히 Lester et al.은 soft prompt를 임베딩으로 학습하여 태스크에 특화된 조정을 가능하게 하면서도 모델의 본래 파라미터는 유지할 수 있도록 함.

이러한 기반 위에서 최근 연구들은 multi-modal context에 soft prompt embedding을 확장하는 방법들을 다루고 있음. 이를 통해 LLM을 다양한 도메인에 유연하게 통합할 수 있는 메커니즘이 제공됨.

LLM은 graph-related task에서도 다양한 방식으로 활용되고 있음. LLM의 text embedding 능력을 활용하여, node 및 edge의 textual attribute를 임베딩함으로써 graph classification 및 knowledge graph 생성에 활용됨. 다른 한편으로는 LLM의 context reasoning 능력이 graph reasoning 및 zero-shot graph QA 에서 유용하게 작용함. 하지만, 대규모 text corpus로 사전 학습된 LLM은 단순한 그래프 구조에 대해 언어적 이해는 갖추었지만, explicit topological structure를 내재하지 않는 텍스트 기반 훈련만으로는 복잡한 graph 구조에 대한 reasoning에는 한계가 존재함.

이에 따라 최근에는 graph prompt tuning이 LLM이 그래프의 구조적 정보를 처리하고 이해하는 데 유용한 도구로 부각.

2.3 Retrieval on Graphs

그래프 기반 정보 검색 분야에서는 다양한 접근이 제안되어 왔음. Yasunaga et al.은 질의 응답(QA) 컨텍스트와 관련 노드를 포함하는 joint graph를 구성하기 위해 관련 노드를 검색하는 방식을 제안함. Kang et al. 및 Kim et al.은 개별 노드/엣지가 아닌 triples 단위로 retrieval을 수행하여, 더 복잡한 관계 구조를 포착함.

일부 검색 문제는 reasoning chain의 형태로 단순화할 수 있으며, 이는 question과 target entity 사이의 path를 retrieval하는 것으로 환원 가능함.

Edge et al.은 community detection algorithm을 이용해 그래프를 커뮤니티 단위로 분할한 뒤, 관련 커뮤니티를 retrieval하고 aggregation하여 최종 응답을 생성함. Li et al.은 textual 정보와 topological 정보 양쪽을 모두 통합함으로써 retrieval 정확도를 개선하고, graph 내 구조적 관계를 보다 정밀하게 반영하는 retrieval 방식을 제안함.

3. Problem Formalization

3.1 Textual Graph

Textual Graph는 자연어 속성을 가지는 노드와 엣지로 구성된 그래프로, 다음과 같이 정의됨:

G = (V, E, {Tn}{n∈V}, {Te}{e∈E})

V: 노드 집합
E: 엣지 집합
Tn: 각 노드 n ∈ V에 대응하는 자연어 속성
Te: 각 엣지 e ∈ E에 대응하는 자연어 속성

즉, textual graph는 구조적 연결성과 더불어 자연어 기반의 풍부한 의미 정보를 포함하는 복합 정보 구조임.

3.2 Textual Subgraph

Textual Subgraph는 textual graph G의 부분 구조로, 유한한 노드 집합과 엣지 집합으로 구성됨. 다음과 같이 정의됨:

S(G) = {g = (V′, E′, {Tn}{n∈V′}, {Te}{e∈E′}) | V′ ∈ P(V), E′ ∈ P(E)}

P(V), P(E): 각각 V와 E의 power set (모든 부분집합들의 집합)
S(G): 그래프 G로부터 파생 가능한 모든 서브그래프의 집합

3.3 GRAG Problem Definition

GRAG의 목적은 textual graph G에 대해 주어진 query q로부터 최적의 subgraph를 검색하고, 이를 LLM에 통합함으로써 더욱 정합적이고 정보에 부합하는 응답을 생성하는 것임.

보다 구체적으로, GRAG는 다음을 목표로 함:

질의 q에 대해 가장 관련성이 높은 subgraph ĝ ∈ S(G)를 효율적으로 검색하는 것
이 subgraph ĝ를 LLM θ (parameterized by θ)의 입력으로 통합하여 생성 품질을 향상시키는 것

3.4 Output Probability Distribution Definition

GRAG의 최종 출력 시퀀스 Y는 다음의 조건부 확률 분포로 정의됨:

y<i: i번째 토큰 이전까지의 prefix 시퀀스
[q, ĝ]: 질의 q와 최적 subgraph ĝ의 결합 입력

LLM이 query와 해당 graph context를 바탕으로 token-by-token 방식으로 응답을 생성하는 과정을 나타냄.

4. Methodology

4.1 Overview

Text Subgraph Retrieval Problem

텍스트 서브그래프 검색의 계산 복잡도 문제를 해결하기 위해, divide-and-conquer 전략을 제안함. 이 접근은 "중요한 서브그래프는 중요한 노드들과 그 이웃 일부로 구성된다"는 가정에 기반함.

구체적인 과정은 다음과 같음:

전체 그래프 G에서 중요 ego-graph를 식별
relevance 점수를 기준으로 상위 N개의 ego-graph를 선택
이들을 병합한 후 soft pruning을 수행하여 중복 노드 및 엣지를 제거

이 과정을 통해 최적에 가까운 subgraph 구조를 근사적으로 도출함.

기존의 direct subgraph search는 탐색 공간이 **2^(|V|+|E|)**으로 매우 비효율적이나, GRAG의 retrieval-then-pruning 방식은 탐색 공간을 **|V|**개의 ego-graph로 제한하여 효율성을 보장함.

그래프 정보의 보존 및 LLM 통합

텍스트 및 토폴로지 정보를 LLM에 효과적으로 전달하기 위해 두 가지 complementary한 관점을 제안함:

Graph View of Textual Graphs
- 텍스트 그래프의 구조적 연결성을 soft prompt 형태로 학습
- 각 노드/엣지의 관계성과 연결성을 보존
- soft prompt는 LLM 내부 latent space에 주입됨
Text View of Textual Graphs
- 텍스트 그래프를 계층적 자연어 기술(hierarchical text description)로 변환
- 연결 구조를 설명하는 문장 기반으로 구성
- hard prompt 형태로 LLM 입력에 포함됨

이러한 dual-view 설계를 통해 textual graph의 구조적 의미와 서술적 맥락을 동시에 보존하며 LLM에 통합 가능함.

4.1 Textual Subgraph Retrieval

텍스트 그래프 G가 주어졌을 때, GRAG의 목적은 생성 품질을 극대화할 수 있는 최적의 textual subgraph ĝ ∈ S(G)를 검색하는 것임. 이를 수식으로 표현하면 다음과 같음:

목표: max_ĝ f(ĝ) (여기서 f(·)는 subgraph에 기반한 generation quality를 측정하는 함수)

이 문제는 NP-hard이므로, 직접적인 최적화 대신 다음과 같은 대체 접근을 사용함.

Alternative Understanding: Neighborhood Union of Key Nodes

retrieved subgraph는 여러 중요 노드들과 그 이웃들의 (부분적인) 합집합으로 간주할 수 있음. 이를 통해 원래의 최적화 문제는 다음과 같이 근사화됨:

여기서:

G[N*_K(v)]: 노드 v와 선택된 K-hop 이웃들로 구성된 subgraph
N*_K(v) ⊆ N_K(v): 전체 K-hop 이웃 중 선택된 subset
V_key: 서브그래프 ĝ의 중추를 구성하는 핵심 노드 집합

Divide-and-Conquer 기반 근사 전략

원문 문제를 tractable하게 만들기 위해 다음의 근사식을 활용함:

즉, 전체 subgraph의 품질을 직접 측정하는 대신, 각 핵심 노드의 주변 subgraph 품질을 개별적으로 평가하여 전체 구조를 구성하는 방식임.

효율적 검색을 위한 두 단계 처리

Offline Encoding
- 각 노드의 K-hop neighborhood G[N_K(v)]를 미리 인코딩
- 전체 그래프의 candidate subgraph pool {G[N_K(v)]} 생성
Online Selection & Pruning
- relevance 기반으로 상위 subgraph들을 인덱싱하여 선택
- learnable pruner를 통해 query와 관련성 높은 이웃들만 남겨 {G[N*_K(v)]} 구성

이러한 전략은 복잡한 조합 최적화 문제를 선형 시간 내에 해결 가능한 구조로 환원하며, 중요 노드 기반의 국소적 탐색을 통해 전체 그래프 탐색 효율을 극대화함.

Textual Subgraph Indexing

각 노드 v에 대해, G[N_K(v)]는 해당 노드를 중심으로 한 K-hop ego-graph와 동일하며, 각 ego-graph는 고유한 식별자와 함께 그래프 임베딩으로 인덱싱됨.

각 subgraph g ∈ S(G)에 대해 다음과 같이 그래프 임베딩 z_g ∈ R^d를 생성:
- (여기서 {T_n}은 노드 텍스트, {T_e}는 엣지 텍스트)
PLM은 사전학습된 언어모델(Pre-trained Language Model)이며, 이로부터 얻은 노드 및 엣지 임베딩에 대해 mean pooling을 적용하여 z_g 생성
모든 서브그래프 임베딩은 이후 검색 과정을 위해 저장됨

Textual Subgraph Ranking

쿼리 q는 동일한 PLM 인코더로 다음과 같이 임베딩됨:

이후, 모든 K-hop ego-graph 임베딩과 z_q 간의 코사인 유사도를 계산하여 쿼리에 가장 관련 있는 상위 N개의 subgraph를 선택:

여기서 cos(·,·)는 cosine similarity 함수이며, S_N(G)는 쿼리와 의미적으로 가장 관련 높은 N개의 subgraph 집합을 의미함.

Textual Subgraph Soft Pruning

S_N(G)로부터 검색된 서브그래프에는 여전히 불필요하거나 노이즈성 노드 및 엣지가 포함될 수 있음. 이러한 요소들이 LLM의 응답 생성 품질에 부정적 영향을 미치므로, soft pruning 기법을 적용하여 관련성이 낮은 구성 요소를 제거함.

각 노드/엣지의 PLM 임베딩과 쿼리 임베딩 간의 차이를 입력으로 하여 scaling factor를 학습:
- (⊖는 element-wise 차이 연산자)
MLP는 노드/엣지의 중요도를 0~1 사이의 스칼라로 출력하며, 이 값을 바탕으로 비관련 노드/엣지에 대해 마스킹 효과를 유도함
쿼리로부터 거리가 먼 노드일수록 α값이 0에 가까워지며, 이는 해당 노드/엣지의 soft 제거에 해당
최종적으로, soft pruning된 서브그래프들을 병합하여 쿼리에 최적화된 subgraph ĝ를 선형 시간 복잡도로 도출함

4.2 Textual Graph Augmented Generation

GRAG는 텍스트 그래프에 대해 LLM에 두 가지 상호보완적인 시각 (Text View & Graph View)을 제공함으로써, 토폴로지 정보를 보존한 상태에서 효과적인 응답 생성을 가능하게 함.

4.2.1 Text View of Textual Graphs

핵심 아이디어 LLM은 트리와 같은 계층 구조로 조직된 텍스트에 대해 강한 추론 능력을 보이며, 이러한 구조를 활용하면 토폴로지 정보를 보존하면서 텍스트 그래프를 효과적으로 해석할 수 있음. 따라서, GRAG는 검색된 textual subgraph를 계층적(hierarchical) 텍스트 서술로 변환하여 hard prompt로 제공하는 방식을 채택함.

Challenge ego-graph는 일반적인 트리 구조와 달리 같은 레벨 또는 교차 레벨 간의 엣지를 포함하는 복잡한 구조를 가짐. 따라서 단순히 트리로 변환하는 것으로는 토폴로지 정보를 완전히 반영할 수 없음. 이를 해결하기 위한 자동화된 구조 변환 알고리즘이 필요함.

변환 알고리즘 절차

ego-graph 분해
- ego-graph g를 다음과 같이 분할:
  - T_g: ego 노드를 루트로 하는 트리 형태의 부분 그래프 (부분 순서 집합)
  - E_g: T_g에 포함되지 않은 잔여 엣지 집합 → g = T_g ∪ E_g
트리 구조 추출
- 각 ego-graph에 대해 BFS를 수행하여 T_g를 추출함
- 이후 E_g는 T_g에 포함되지 않은 엣지를 수집하여 구성
계층적 서술 구성
- T_g에 대해 pre-order traversal 수행
- 방문한 노드 및 엣지의 텍스트를 relation template에 따라 연결하여 서술을 구성
- 이후 E_g에 포함된 triple 형태의 텍스트를 적절한 위치에 삽입하여 보완
최종 출력
- 이 과정을 통해 생성된 계층적 텍스트 서술을 D_g로 정의
- D_g는 텍스트 정보와 토폴로지 정보를 모두 보존하는 구조
- Appendix A.1에서는 K-hop ego-graph ↔ 계층적 텍스트 간 무손실 변환 사례 제시

LLM 입력 구성

최종적으로, 질의 q와 변환된 계층 텍스트 D_g를 연결하여 hard prompt로 LLM에 입력함:
- Hard Prompt = [q, D_g]

Text View는 ego-graph의 구조적 정보를 텍스트 기반으로 보존하며, LLM이 구조 인지 기반 추론을 수행할 수 있도록 설계됨. 이 구조는 그래프 기반 질의 응답에서 하드 프롬프트로 활용됨.

4.2.2 Graph View of Textual Graphs

핵심 아이디어 텍스트 그래프의 구조 정보를 LLM에 전달하기 위해, GRAG는 soft pruned subgraph를 입력으로 **Graph Neural Network (GNN)**를 활용하고, 이를 통해 생성된 임베딩을 soft prompt로 사용함. 이 접근은 LLM이 구조적 맥락을 인지한 상태에서 텍스트 생성을 수행할 수 있도록 유도함.

소프트 프롬프트를 위한 GNN 인코딩

GNN_Φ는 노드 및 엣지의 query 관련도에 따라 message passing 강도를 조절함으로써, 관련성이 높은 정보에 집중할 수 있도록 함.
이 때, relevance scaling factor α를 통해 노드 및 엣지의 중요도를 반영함:
- u ∈ {N(v) ∪ v} : v의 이웃 노드 또는 v 자신
- h_u^(l−1): 이전 layer의 노드 u의 hidden feature
- e_uv = z_uv: u와 v 사이 엣지의 임베딩
- α_u, α_uv: query와의 relevance를 반영한 스케일링 계수
- m_u^(l): 현재 layer에서 node u로 들어오는 메시지
노드 초기 feature h_u^(0)은 PLM으로부터 생성된 임베딩 zn
relevance scaling factor는 앞서 soft pruning 단계에서 학습된 α 사용

4.2.3 Generation Phase

핵심 아이디어 최종 생성 단계에서는 질의 q와 그에 대해 검색된 textual subgraph ĝ의 정보를 바탕으로 텍스트 생성을 수행함. 이때, text view와 graph view에서 각각 추출한 정보를 LLM의 입력 공간에 align하고, 이를 동시 활용하여 보다 구조적으로 정합성 높은 응답을 생성함.

모달리티 불일치 문제 해결

text view에서 생성된 hard prompt ([q, D_g])는 자연어 기반 텍스트 구조
graph view에서 생성된 soft prompt는 GNN 임베딩 기반 구조 정보
이 둘은 서로 다른 representation space(modality)을 갖기 때문에, graph 임베딩을 LLM의 임베딩 공간에 맞춰 정렬해야 함

정렬 방법

graph 임베딩은 **GNN_Φ(ĝ)**를 통해 얻어진 후, MLP_ϕ3를 통해 LLM의 임베딩 차원으로 projection:
- d_LLM: LLM의 입력 토큰 임베딩 차원
- h_ĝ: 구조 정보를 내포한 soft prompt 임베딩

하드 프롬프트 처리

질의 q와 텍스트 서술 D_g를 연결한 hard prompt ([q, D_g])는 LLM의 텍스트 임베더를 통해 임베딩됨:
- h_T = TextEmbedder_LLM([q, D_g])

최종 생성 확률 정의

위에서 얻어진 h_ĝ (graph view)와 h_T (text view)를 연결하여 LLM_θ의 입력으로 사용:
- [· ; ·]: 임베딩 연결(concatenation)
- y_<i: 생성된 토큰 시퀀스의 prefix
- 최종적으로 transformer 입력으로 주어짐

요약

GRAG는 hard prompt와 soft prompt를 결합한 이중 프롬프트 방식으로 입력됨
soft prompt(h_ĝ)는 구조 정보를, hard prompt(h_T)는 자연어 기반 문맥 정보를 제공
이를 통해 LLM은 문맥적 정확도와 구조적 정합성을 동시에 고려한 응답을 생성할 수 있음

5 Experiments

실험 목적 GRAG의 실제 성능을 평가하기 위해 Graph QA 시나리오에서 기존 RAG 및 LLM 기반 접근들과 비교 실험을 수행.

5.1 Experiment Setup

Datasets

GraphQA Benchmark (He et al., 2024)
- 그래프 문맥 이해가 필요한 QA 문제를 포함한 벤치마크 데이터셋
- 각 textual graph는 최소 하나의 질의-응답 쌍과 연결됨
WebQSP (Yih et al., 2016; Luo et al., 2023)
- 대규모 multi-hop knowledge graph 질의응답 데이터셋
- 복잡한 추론 경로와 질의-타겟 엔티티 간 다단계 연결 필요
ExplaGraphs (Saha et al., 2021)
- 상식 기반 추론 데이터셋
- 논쟁에서의 입장 예측(task of predicting stance positions)을 주요 과제로 포함

Evaluation Metrics

WebQSP: F1 Score, Hit@1, Recall
ExplaGraphs: Accuracy

Comparison Methods

GRAG의 효과를 검증하기 위해, 다음과 같은 다양한 RAG 및 LLM 기반 접근 방식과 비교:

LLM Baselines (retrieval 미사용)
1. Frozen LLM: 외부 지식 없이 고정된 사전학습 모델 사용
2. Fine-tuned LLM (LoRA 기반): RAG 없이 LoRA를 이용한 파인튜닝 수행
사용된 LLM 모델
- Llama2-7b

전체 실험 설정 및 학습 파라미터는 Appendix A.3에 명시됨

5.2 Main Results

주요 성능 결과

1. GRAG는 RAG 및 LLM 베이스라인보다 일관되게 우수한 성능을 달성함

GRAG는 사전학습된 LLM을 별도의 fine-tuning 없이도 모든 지표에서 fine-tuned LLM을 능가함
WebQSP에서 fine-tuned LLM의 Hit@1은 0.7236 → 0.7275로 소폭 상승하는 데 그침
- 이는 GRAG 적용 시 fine-tuning의 추가 효과가 제한적임을 시사
GRAG는 단순 파인튜닝보다 훨씬 효과적인 그래프 추론 강화 전략으로 작용
- 결과적으로, 그래프 QA와 같은 과제에 대해 LLM 학습 비용을 절감할 수 있는 잠재력 보유

2. Soft Pruning은 그래프 기반 작업에서 LLM 성능을 유의미하게 향상시킴

그래프의 모든 텍스트 정보를 하드 프롬프트에 통합할 경우, LLM은 성능 저하를 보임
- 특히 ExplaGraphs와 같이 그래프 크기가 작은 경우에도 성능이 저조함
이는 retrieval과 soft pruning이 중복 정보 제거에 필수적임을 강조
예시:
- ExplaGraphs에서 fine-tuning 없이: Accuracy 33.94%
- GRAG + fine-tuning 적용 후: Accuracy 89.27%
그러나 그래프 크기가 커질수록 fine-tuning의 이점은 감소
- WebQSP에서 Hit@1: 0.4148 → 0.6186 (상대적 증가폭 감소)

3. GRAG는 학습된 텍스트 그래프 인코딩 능력을 다른 데이터셋에 효과적으로 전이함

대규모 데이터셋(WebQSP)에서 학습한 GRAG는 소규모 데이터셋(ExplaGraphs)에도 효과적으로 적용됨
예시: WebQSP에서 학습한 GRAG를 ExplaGraphs에 적용 → Accuracy 33.77% 향상

4. Retrieval이 없는 상황에서는 LLM 크기 증가가 성능 향상으로 이어지지 않음

Retrieval을 사용하지 않을 경우, 13B LLM은 오히려 7B 모델보다 성능이 낮음
- ExplaGraphs Accuracy:
  - Llama2-7b-chat-hf: 33.94%
  - Llama2-13b-chat-hf: 33.57%
- WebQSP Hit@1:
  - 7B: 0.4148
  - 13B: 0.4112
이는 LLM 스케일업만으로는 복잡한 그래프 문맥 이해에 한계가 있음을 보여줌

요약 GRAG는 단순 LLM 파인튜닝이나 대규모 모델 사용보다 훨씬 효과적인 방식으로 그래프 기반 질의응답 문제를 해결함. Retrieval + Soft Prompt + Structured Graph Encoding의 조합은 그래프 구조를 정밀하게 반영하며, 다양한 조건에서도 일관된 성능 향상을 이끌어냄.

5.3 Discussion

Subgraph 크기 K의 영향

GRAG의 검색 효율성은 탐색 공간을 |V|개의 K-hop ego-graph로 제한함으로써 유지됨
그러나 K가 커질수록 더 넓은 그래프 문맥이 생성 과정에 통합되어 훈련/추론 시간이 증가함
특히 3-hop 이상의 서브그래프는 임베딩이 oversmoothing 현상을 겪기 쉬워, 검색 구분력이 약화될 수 있음
K 값 선택은 성능과 효율성 간 트레이드오프를 고려해 조정해야 함
동일 개수의 ego-graph를 사용할 경우, 2-hop ego-graph가 1-hop보다 성능이 항상 우수함
그러나 ego-graph 수가 너무 많아질 경우, 불필요한 정보 증가로 인해 성능이 감소함
- 예: ego-graph 수가 15 → 20으로 증가할 때 성능 하락
한편, retrieved subgraph 수가 증가하면 생성 결과의 표준편차가 감소 → 생성 일관성 향상

Hallucination 평가

WebQSP 및 ExplaGraphs에서 100개 샘플을 무작위로 선택하여 수작업으로 hallucination 평가 수행
방법: LLM이 생성한 답변과 함께 참조된 노드 및 엣지를 제공 → 실제 그래프에 존재하는지 검증
평가 기준: Menick et al., He et al. 방식에 따라 응답의 합리성과 근거의 정당성을 측정
결과:
- GRAG: 유효 엔티티 참조율 79%
- G-Retriever: 71%
- MiniLM-L12-v2: 62%
→ GRAG는 가장 높은 정확도로 실제 그래프에 존재하는 엔티티 기반의 응답 생성 가능

RAG 방식과의 정성적 비교

대부분의 retriever들은 text-only embedding을 기반으로 하며, 그래프 구조는 검색에 반영되지 않음
고급 retriever들은 더 많은 훈련 데이터와 높은 차원의 임베딩을 사용하지만, 여전히 토폴로지 정보가 누락됨
Table 2에 따르면, 그래프 구조를 무시할 경우 retriever 간 성능 차이는 매우 작음 → 성능 병목
G-Retriever는 soft prompt 형태로 그래프 정보를 통합하므로 다른 retriever보다 우수하나, retrieval 자체는 여전히 토폴로지 무시
GRAG는 다음의 두 가지 점에서 차별화됨:
1. 개별 엔티티가 아닌 subgraph 단위로 검색
2. topology-aware retrieval + topology-aware generation을 모두 적용
이러한 접근으로 두 데이터셋 모두에서 최적 성능 달성

요약

K-hop 크기와 subgraph 수의 선택은 성능과 효율성에 결정적 영향
GRAG는 hallucination 방지 측면에서 탁월하며, 기존 retriever 대비 실질적 graph 이해능력이 뛰어남
단순 text-only 기반의 retriever는 구조적 한계를 가지며, GRAG는 이를 극복하여 그래프 기반 QA의 새로운 기준을 제시함

5.4 Ablation Study

실험 설정

다음 네 가지 ablated variant를 구성하여 비교:

w/o Retrieval: 서브그래프 retrieval 없이 전체 그래프를 직접 입력
w/o Graph Encoder: retrieval된 서브그래프의 텍스트만 사용하고, graph encoder 없이 graph token은 생성하지 않음
w/o Soft Pruning: 서브그래프 내 불필요한 엔티티를 pruning하지 않고 graph token 생성
w/o Graph Description: 서브그래프의 hierarchical text description을 제거한 채 학습

주요 결과 및 분석

‌

1. 그래프 컨텍스트의 중요성

w/o Graph Encoder: Hit@1 성능이 0.7275 → 0.5835로 크게 하락
단순히 텍스트로 노드 간 관계를 설명하는 것은 LLM의 그래프 구조 이해에 불충분
Graph embedding은 더 깊이 있는 구조적 정보 학습을 가능케 함

2. Soft Pruning의 영향

w/o Soft Pruning: 성능이 w/o Retrieval 및 w/o Graph Encoder보다 낮음
특히 복잡한 그래프 구조에서는 불필요한 정보의 부정적 영향이 큼
Pruning은 고품질 graph token 생성에 필수적인 전처리 과정

3. 텍스트 속성의 중요성

w/o Graph Description: soft token만으로는 성능을 향상시키지 못함
- Hit@1 = 0.4496 → Retrieval 제거보다도 낮음
이는 노드 및 엣지의 텍스트 속성 자체가 generation 성능에 중요한 피처임을 시사
Soft token은 이 정보를 압축 표현하지만, 텍스트 자체의 직접적 주입이 효과적

요약

Variant	주요 결함	Hit@1 변화	시사점
w/o Retrieval	Retrieval 제거	성능 저하	Retrieval 구조가 필요
w/o Graph Encoder	구조적 임베딩 미사용	-20%↓	Graph Encoder 필수
w/o Soft Pruning	Pruning 부재	추가 성능 저하	Pruning의 정제 효과
w/o Graph Description	Text prompt 부재	-38.2%↓	텍스트 정보 중요성

→ GRAG의 성능은 텍스트 정보 + 토폴로지 정보의 결합, 그리고 Pruning을 통한 선택적 정보 입력에 크게 의존함

6 Conclusion

제안 방법

GRAG는 LLM의 생성 성능을 향상시키기 위해 질의에 연관된 텍스트 서브그래프를 검색하여 활용하는 구조를 가짐
서브그래프 검색의 효율성 확보를 위해, K-hop ego-graphs 기반 divide-and-conquer 전략과 soft pruning 기법을 조합하여 최적 서브그래프를 근사
생성 단계에서는 LLM에 **그래프 뷰(graph view)**와 텍스트 뷰(text view) 두 가지 상보적 관점을 제공함으로써 텍스트 그래프 문맥을 정교하게 이해하도록 설계

실험적 성과 및 의의

제안된 GRAG는 multi-hop reasoning이 요구되는 복잡한 그래프 질의 환경에서 기존 LLM 및 RAG 대비 우수한 성능을 달성
특히, fine-tuning 없이도 frozen LLM에 GRAG를 적용하면 fine-tuned LLM보다 더 나은 성능을 보임
- → 훈련 비용 감소와 성능 향상을 동시에 달성하는 전략으로서 유효함
NP-hard한 서브그래프 탐색 문제에 대해 현실적인 근사를 제공함으로써 실용적인 구현 가능성 확보

GRAG는 RAG의 텍스트 기반 retrieval 한계를 극복하며, 텍스트-그래프 융합 기반 생성 기술의 새로운 가능성을 제시함. 향후 연구는 이 프레임워크를 멀티모달, 실시간 동적 그래프 환경으로 확장할 수 있는 방향에서 이루어질 수 있음.

Appendix

A.1 Hierarchical Description

구조적 특징

계층 구조의 각 단계는 그래프 내에서의 거리(level)에 대응되며, 이는 노드 간의 연결 관계를 그대로 유지함
각 노드는 관련된 제목 또는 설명 텍스트를 포함하고 있으며, 논문의 제목이나 키워드와 같은 정보가 함께 제공됨
들여쓰기(indentation)와 중첩(nesting)을 통해 상위 노드와 하위 노드 간의 연결성을 표현하고, 원래 그래프의 위계적 연결 구조를 직관적으로 보여줌

표현 방식의 이점

원래 그래프에서의 노드 간 **토폴로지 관계(topological relationship)**를 손실 없이 보존
트리 구조로 정렬된 텍스트 표현은 LLM이 이해하기에 적합한 **선형 순차적 형식(linearized hierarchical form)**으로 제공됨
이 구조는 추론 과정에서의 **관계 명시성(explicitness of relationships)**을 강화하며, 각 노드의 부모-자식 관계가 명확히 드러남

적용 예시

인용관계 그래프에서는, 루트 노드(예: 특정 논문)로부터 시작하여 인용된 논문들과 그 인용들의 인용 등으로 이어지는 **참조 계층(reference hierarchy)**이 구성됨
각 서브노드는 해당 노드의 식별자 및 요약 문장과 함께 제공되며, 텍스트 기반 reasoning을 지원함

이 계층형 서술 방식은 ego-graph의 텍스트화(textualization)를 통해 LLM의 그래프 구조 이해도를 향상시키는 핵심 요소로 작용함.

A.2 Comparison Retrievers

BM25 (Robertson et al., 2009)

통계 기반 모델
쿼리와 문서 간의 관련성을 용어 빈도(TF), 역문서 빈도(IDF), 문서 길이를 기준으로 확률적으로 평가
전통적인 IR(Information Retrieval)에서 널리 사용되는 방식

MiniLM-L12-v2 (Reimers and Gurevych, 2019)

SentenceTransformer 기반의 경량 모델
군집화(clustering) 및 **의미 기반 검색(semantic search)**에 자주 사용
Bi-encoder 구조를 활용하여 쿼리와 문서를 독립적으로 임베딩

LaBSE (Feng et al., 2022)

다국어 cross-lingual 검색을 위한 BERT 기반 모델
Dual-encoder 구조를 사용해 문장 간 유사도를 계산
다국어 문장 임베딩을 학습하여 의미적 대응을 유도

mContriever (Izacard et al., 2021)

Contrastive Learning 기반의 bi-encoder 모델
쿼리와 문서를 독립적으로 인코딩하고, 관련 문서 쌍 간의 유사도 최적화
in-batch negative sampling을 활용해 비관련 문서들과의 구별을 학습

E5 (Wang et al., 2022)

대규모 contrastive pre-training을 수행한 bi-encoder 기반 모델
관련된 쿼리-문서 쌍의 유사도를 극대화하고, 비관련 쌍과의 유사도는 최소화
mContriever와 유사한 프레임워크이나 더 광범위한 사전학습을 수행

G-Retriever (He et al., 2024)

그래프에서 관련된 노드 및 엣지를 검색한 후, 이를 바탕으로 Prize-Collecting Steiner Tree 알고리즘을 사용하여 관련 서브그래프 구성
텍스트 기반이 아닌 구조적 그래프 정보를 활용함으로써 그래프-기반 추론에 적합

위의 리트리버들은 대부분 텍스트 기반의 Bi-Encoder 구조를 중심으로 설계되어 있으며, GRAG과는 달리 그래프 토폴로지 정보의 활용이 제한적이라는 한계를 지님.

A.3 Implementation

데이터 분할

ExplaGraphs: Train/Validation/Test = 60% / 20% / 20%
WebQSP: Train/Validation/Test = 60% / 5% / 35%

하드웨어 및 환경

운영체제: Linux 기반 서버
GPU: NVIDIA A10G GPU × 4대

텍스트 임베딩 및 리트리버 구성

텍스트 및 질문 임베딩: SentenceBERT (Reimers and Gurevych, 2019)
검색 단계에서 사용되는 텍스트 벡터를 생성

그래프 인코더

GAT (Graph Attention Network) 사용 (Veličković et al., 2018)
- num_layer: 4
- num_head: 4 (per layer)
- hiddent_dim: 1024

언어 모델 설정

LLM Backbone: Llama-2-7b-hf
LLM-only 설정 시 사용된 모델: Llama-2-7b-chat-hf

Finetuning: LoRA 설정 (Hu et al., 2021)

rank: 8
scaling_factor: 16
dropout: 0.05
Optimizer: AdamW
learning rate: 1e-5
weight decay: 0.05
epohcs: max 10
batch_size: 2

Retriever 실험 구성

ExplaGraphs:
- 실험을 3회 반복
- 각각 다른 top-k 설정 적용: top-3, top-5, top-10
WebQSP:
- 실험을 5회 반복
- 각각 다른 top-k 설정 적용: top-3, top-5, top-10, top-15, top-20
- 여기서 top-k는 가장 관련도 높은 노드 k개와 엣지 k개를 검색하여 생성에 활용

GRAG 전용 설정 사항

ExplaGraphs의 경우, 각 그래프가 단순한 트리플 체인으로 구성되어 노드 수가 적음
이에 따라, 전체 그래프를 LLM에 입력하여 처리

A.4 Experiment