Graph RAG 서베이 (2024) 논문 리뷰

논문의 제목은 Graph Retrieval-Augmented Generation: A Survey다. (링크)

 

저자는 Boci Peng, Yun Zhu, Yongchao Liu, Xiaohe Bo, Haizhou Shi, Chuntao Hong, Yan Zhang, Siliang Tang다.

 

Github: 링크

 

그래프 RAG를 다룬 서베이 논문으로, 제목 그대로 그래프 구조의 데이터를 통해서 RAG를 수행하는 방법들을 다루고 있다. 

 

Abstract

최근 Retrieval-Augmented Generation (RAG)는 retaining이 없이 LLM의 문제들의 해결에 있어서 눈에 띄는 성과를 달성했다. External knowledge 외부 지식을 참조함으로써, hallucination 환각, 도메인 특화 지식 부족, 그리고 오래된 정보 등의 문제를 효과적으로 완화시켰다. 하지만 데이터베이스 상의 다양한 entities 엔티티 간의 복잡한 구조를 RAG 시스템에 도전과제로 남아있다. 그에 대한 해답으로, GraphRAG는 엔티티에 걸쳐있는 구조적 정보를 활용하여 보다 엄밀하고 포괄적인 retrieval을 가능하게 하며, 관계적 지식을 포착하고 이를 더 정확하고 컨텍스트를 이해하는 답변 생성에 활용한다. GrapgRAG의 novelity와 가능성이 주어진 상태에서 체계적인 리뷰는 반드시 해야하는 사항이다. 본 논문에서는 우선 GraphRAG의 방법론에 대한 포괄적인 개요를 소개한다. GraphRAG의 워크플로우를 형식화하는데, 이는 Graph-based Indexing, Graph-Guided Retrieval, Graph-Enhanced Generation을 포괄한다. 그 다음 핵심 기술과 학습 방법을 각각의 단계에서 윤곽을 그린다. 추가적으로 다운스트림 태스크, 응용 도메인, 평가방법, 산업에서의 실제 사용 예시 역시 살펴본다. 최종적으로 앞으로의 연구와 실무에서의 발전 방향에 대한 미래의 연구 방향에 대해서 다룬다. 

 

 

1. Introduction

 

GraphRAG 과정을 다음의 3가지 카테고리로 분류한다.

 

Graph-Based Indexing (G-Indexing)

Graph-Guided Retreival (G-Retrieval)

Graph-Enhanced Generation (G-Geneeration)

 

이는 각각 섹션 5, 6, 7에서 자세히 다룬다.

 

 

2. Comparison with Related Techniques and Surveys

 

 

 

GraphRAG와 유사한 기술과 서베이를 다루는데, RAG, 그래프 데이터 상에서의 LLM, Knowledge Base Question Answering (KBQA)를 포함한다.

 

2.1. RAG

 

2.2. LLMs on Graphs

 

 

2.3. KBQA

 

KBQA는 nlp의 중요한 태스크로 external knowledge bases 외부 지식 베이스에 기반해서 유저의 쿼리에 대한 답변을 생성하고자 한다. 크게 2가지 유형으로 나눌 수 있는데, Information Retrieval (IR) 베이스 방법과 Semantic Parsing (SP) 기반 방법이다. IR은 KG (Knowlege Graph)로 부터 유저의 쿼리와 관련있는 정보를 검색하는 방법이다. SP는 개별 쿼리에 대한 logical form (LF)를 생성해서 knowledge base에 실행하고 답변을 얻는 방법이다. 

 

GraphRAG와 KBQA는 서로 밀접한 관련이 있다. 

 

 

3. Preliminaries

 

저자들은 서베이 논문의 이해를 돕기 위해서, GraphRAG의 배경지식을 설명한다. 첫째로, Text-Attributed Graphs라는 보편적이고 일반적인 형태의 그래프 데이터를 소개한다. 이는 GraphRAG에서 쓰이는 그래프 데이터다. 그 다음에 Graph Neural Networks와 Language Models 두 가지 모델을 소개하는데, retrieval (검색)과 generation (생성) 단계에서 쓰이는 두 가지 형태들이다. 

 

3.1. Text-Attributed Graphs

 

GraphRAG에서 쓰이는 그래프 데이터 중 텍스트 형태의 attributes (속성)을 가지는 노드와 엣지들을 지니는 Text-Attributed Graphs (TAGs)라고 한다. $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathcal{A}, \{ \mathbf{x}_v \}_{v \in \mathcal{V}}, \{ \mathbf{e}_{i, j} \}_{i, j \in \mathcal{E}} )$ where $\mathcal{V}$은 노드들의 집합이고, $\mathcal{E} \supset \mathcal{V} \times \mathcal{V}$은 엣지들의 집합이고, $\mathcal{A} \in \{ 0, 1 \}^{|\mathcal{V}| \times |\mathcal{V}|}$인 adjacent matrix 인접행렬이다. 추가적으로, $\{ \mathbf{x}_v \}$은 노드의 텍스트 속성이고, $\{ \mathbf{e}_{i, j} \}$은 엣지의 텍스트 속성이다. TAG의 가장 전형적인 종류는 Knowledge Graphs (KGs)다. 

 

3.2. Graph Neural Networks

 

Graph Neural Network는 그래프 데이터를 모델링하는 딥러닝 프레임워크다. 전통적인 GNN은 GCN, GAT, GraphSAGE 등이 있다. 노드 representations 얻기 위해서 message-passing 방법을 사용한다. $l$번째 레이어의 $i$ 노드 표현은 $h_{i}^{(l-1)}$으로 표기하며, 인접한 노드와 엣지들의 정보를 aggregating하면서 업데이트한다.  

 

$h_{i}^{(l)}$ = $UPD(h_{i}^{(l-1)}, AGG_{j \in N(i)}, MSG( h_{i}^{(l-1)}, h_{j}^{(l-1)}, e_{i, j}^{(l-1)} )$),

 

$N(i)$는 노드 $i$의 이웃 노드들을 나타낸다. MSG는 메시지 함수이며 노드, 이웃 노드, 엣지 간의 메시지를 계산한다. AGG는 aggregation 함수로 받은 메시지들을 mean, sum, max 등으로 혼합한다. UPD는 업데이트 함수로 aggragated 메시지들을 기반으로 개별 노드들의 속성들을 업데이트한다. 

 

그 다음에, readout 판독 함수는 mean, sum, max pooling으로 global-level representation을 얻기 위해서 활용되는 함수다. GraphRAG에서 GNN은 retreival 단계에서 사용할 표현을 얻기 위해 쓰며, 그래프 구조를 얻기 위해서도 쓴다.

 

4. Overview of GraphRAG

 

 

 

 

Figure 2에 묘사되었듯이, GraphRAG는 외부의 구조적인 지식 그래프 (structured KG)를 이용하여 언어모델들의 컨텍스트 이해를 개선한다. GraphRAG의 목표는 데이터베이스로부터 가장 연관있는 지식들의 검색이다. 이를 통해서 다운스트림 태스크들의 답변을 향상시킨다. 이는 다음처럼 정의할 수 있다.

 

$a^* = arg \underset{a \in A}{max} \, p(a | q, \mathcal{G})$

 

주어진 쿼리 $q$와 TAG $\mathcal{G}$에 대한 최적의 답변이 $a^*$다. 그리고 $A$는 가능한 모든 답변의 집합이다. 

 

Target distiribution인 $p(a | q, \mathcal{G})$와 graph retriever인 $p_{\theta}(G | q, \mathcal{G})$, 그리고 answer generator인 $p_{\phi}(a | q, \mathcal{G})$를 동시에 학습시킨다. 이때, ${\theta}, {\phi}$는 학습가능한 파라미터다. total probability formula를 통해서 $p(a | q, \mathcal{G})$를 다음처럼 분해할 수 있다.

 

$p(a | q, \mathcal{G})$ = $\sum_{G \subseteq \mathcal{G}}  p_{\phi}(a | q, \mathcal{G}) p_{\theta}(G | q, \mathcal{G}) $ 

$\approx p_{\phi}(a | q, \mathcal{G}^*) p_{\theta}(G^* | q, \mathcal{G}) $ ... (4)

 

이때, $\mathcal{G}^*$은 optimal subgraph다. 그래프의 크기가 커질수록 가능한 서브그래프의 수가 기하급수적으로 증가하기 때문에 효율적인 근사 방법이 필요하다. (4) 식의 첫 줄은 두 번째 줄로 근사할 수 있다. 구체적으로 말하면, graph retriever가 최적의 서브그래프를 추출하는데 쓰인다. 이렇게 추출된 서브그래프를 토대로 답변을 생성하게 된다.  

 

 그러므로 본 논문에서 저자들은 GraphRAG의 전체 과정을 3가지 단계로 분해한다. Graph-Based Indexing, Graph-Guided Retireval, Graph-Enhanced Generation의 세 단계다. 전반적인 워크플로우는 Figure 2에 그려져있다. 

 

 

Graph-Based Indexing (G-Indexing)

Graph Database인 $\mathcal{G}$를 정의하거나 구축하는 단계로 GraphRAG의 첫 단계다. 그래프 DB는 공개된 지식 그래프나 그래프 데이터 혹은 텍스트나 다른 형태의 데이터를 토대로 만들어진다. 

 

Graph-Guided Retrieval (G-Retrieval)

Graph DB에서 관계있는 정보를 검색하서 추출하는 단계다. 구체적으로는 자연어로 주어진 유저의 쿼리 $q$에 기반해서, 지식 그래프로부터 관련된 elements (e.g., entities, paths, subgraphs)들을 추출한다. 

 

$G^*$ = G-Retriever($q, \mathcal{G}$

= $arg \underset{G \in \mathcal{R}(\mathcal{G})}{max} \, p(G | q, \mathcal{G})$

= $arg \underset{G \in \mathcal{R}(\mathcal{G})}{max} \, Sim( q, \mathcal{G})$

 

$G^*$는 optimal retrieved graph elements, Sim($\cdot, \cdot$)은 유저 쿼리와 그래프 요소들의 의미적 유사성을 측정하는 함수다. $\mathcal{R}$은 서브그래프들의 검색 범위를 줄여나가는 함수로 효율성을 고려한다. 

 

 

Graph-Enhanced Generation (G-Generation)

검색한 그래프 데이터를 토대로 유의미한 결과나 응답을 생성하는 단계다. 검색된 그래프 데이터를 토대로 유의미한 출력이나 답변을 생성한다.

 

$a^*$ = G-Generator($q, G^*)$

= $arg \underset{a \in A}{max} \, p_{\phi}(a | q, G^*)$

= $arg \underset{a \in A}{max} \, p_{\phi}(a | \mathcal{F} (q, G^*)$

 

 

$\mathcal{F}(\cdot, \cdot)$은 그래프 데이터를 generator가 사용할 수 있도록 가공하는 함수다. 

 

 

5. Graph-Based Indexing

 

 

 

 

그래프 DB의 구축과 indexing 인덱싱은  그래프 RAG의 성능에 직접적인 영향을 미친다. 그래프 데이터와 다양한 인덱싱 방법들을 선택하고 구축하는 방법을 범주화하고 요약한다. 

 

5.1. Graph Data

Open Knowledge Graphs와 Self-Constructed Graph Data라는 두 가지 범주로 나누었다. 

 

5.1.1. Open Knolwedge Graphs

 

(1) General Knowledge Graphs

국제적인 커뮤니티에서 모은 일반적인 데이터로 포괄적이고 지속적으로 갱신되는 데이터들이다. Encyclopedic knowledge graph 백과사전식 지식 그래프는 전형적인 일반적인 지식 그래프로, 사람 전문가와 백과사전으로 부터 모은 대규모의 현실 지식을 담고있다. 

 

Wikipedia, Wikivoyage, Wikitionary, Freebase, DBpedia, YAHO 등이 이에 해당한다. 

 

Typical Commonesense Knolwedge Graphs: CoceptNet and ATOMIC models

 

 

(2) Domain Knowledge Graphs

 

특정 도메인, 전문 영역에 국한된 데이터로 Biomedical, 영화, 전자상거래, 문학, 헬스케어, 법 등 다양한 영역의 데이터가 이에 포함된다. 

 

특정 도메인 영역을 다루는 KG는 다음과 같다.

 

CMeKG, CPubMed-KGm, Wiki-Movies, GR-Bench, ExplaGraphs, SceneGraphs, WebQSP, GraphQA 

 

 

5.1.2. Self-Constructred Graph Data

그래프 데이터가 본질적으로 포함되지 않은 다운스트림 작업의 경우 연구자들이 직접 그래프를 설계하고 구축한다. 문서, 표, 기타 DB 등의 여러 출처로 부터 그래프를 구축한다. 

일반적으로 이러한 자가 구축 그래프는 특정 방법의 설계와 밀접하게 연관되어 있으며, 앞서 언급한 개방 도메인 그래프 데이터와는 구별된다.

문서 간의 구조적 관계를 모델링하기 위해 Munikoti  et al은 co-citation, co-topic, co-venue 등 다양한 문서 수준의 관계를 포착하는 heterogeneous 문서 그래프를 구축할 것을 제안했다. Li et al과 Wang et al은 공유 키워드를 기준으로 문단 간의 관계를 설정한다. 문서 내 개체 entity 간의 관계를 포착하기 위해 Delile et al, Edge et al, Gutiérrez et al, Li  et al은 개체명 인식(NER) 도구를 사용해 문서에서 개체를 추출하고, LM을 활용해 개체 간 관계를 추가로 추출한다. 이렇게 검색된 개체와 관계는 이후 지식 그래프를 형성한다.

또한 일부 다운스트림 작업의 경우, 태스크 자체의 특성에 맞추어 설계된 매핑 방법이 필요하다. 예를 들어 특허 구문 Patent phrase 유사도 추론 태스크를 해결하기 위해 Peng과 Yang은 특허 데이터베이스를 Patent-phrase graph 특허–구문 그래프로 변환한다. 구문이 특허에 등장할 경우 특허 노드와 구문 노드 간에 연결을 설정하며, 특허 노드 간의 연결은 인용 관계를 기반으로 한다. 고객 서비스 기술 지원 시나리오를 대상으로 Xu et al은 과거 이슈를 지식 그래프(KG)로 모델링할 것을 제안하며, intra-issue relations 이슈 내의 관계들을 유지하는 트리로 표현한다.  Semantic similarity 의미적 유사도를 활용하고 inter-issue relations 이슈 간의 관계를 유지한다. 

 

 

 

5.2. Indexing

그래프 기반의 인덱싱은 쿼리 작업의 효율성과 속도의 향상에 있어서 아주 중요한 역할을 한다. 

 

5.2.1. Graph Indexing

그래프 인덱싱은 가장 보편적인 접근 방법으로 그래프의 전체 구조를 보존한다. 어떠한 노드든 간에 모든 엣지와 이웃 노드들에 쉽게 접근할 수 있다. 이어지는 검색 단계에서, BFS나 Shortest Path Algorithms 같은 전통적인 서치 알고리즘을 적용할 수 있다. 

 

5.2.2. Text Indexing

검색 과정의 최적화를 위해서 그래프 데이터를 텍스트 설명으로 전환하는 과정을 포함한다. 텍스트 코퍼스에 이 설명들이 저장되며, sparse retrieval이나 dense retrieval의 텍스트 기반 검색에 사용된다. 사전에 정의된 규칙이나 템플릿에 의해서 지식 그래프를 사람이 읽을 수 있는 텍스트로 변환하는 방법도 있다. 

 

 

5.2.3. Vector Indexing

벡터 인덱싱은 그래프 데이터를 벡터 표현으로 변환하는 작업으로 검색의 효율성을 향상시켜 빠른 검색과 효율적인 쿼리 처리를 촉진한다. 예를 들어서 entity linking은 쿼리 임베딩과 Locality Sensitive Hashing (LSH) 같은 효율적인 벡터 검색 알고리즘을 통해서 효율적으로 활용된다. G-Retriever은 언어모델로 그래프 안에 있는 노드 및 엣지와 관련된 텍스트 정보를 인코딩한다. 반면에 GRAG는 언어 모델을 활용해서 k-hop ego networks를 그래프 임베딩으로 변환하며, 더 나은 구조적 정보를 보존할 수 있다. 

 

이때, k-hop ego network는 그래프에서 특정 노드 하나(ego)를 중심으로, k번 이내의 edge를 따라 도달 가능한 모든 노드와 그 사이의 연결로 이루어진 서브그래프다. 

 

5.2.4. Hybrid Indexing

위 3가지 방법은 각기 장점이 다르기 때문에 섞어서 쓴다. 예를 들어서, HybridRAG는 벡터와 그래프 데이터를 동시에 활용하며,  EWEK-QA는 텍스트와 지식 그래프를 모두 사용한다. 

 

 

6. Graph-Guided Retreival

 

 

 

그래프 데이터 검색에서의 주된 문제점은 2가지다. (1) Explosive Candidate Subgraph, 그래프의 사이즈가 커질수록 후보가 되는 서브그래프의 숫자가 기하급수적으로 증가한다. (2) Insufficient Similarity Measurement로 텍스트로 된 쿼리와 그래프 데이터 사이의 유사도를 정확히 측정하는 방법이 필요하다. 이 유사도는 텍스트의 정보와 그래프의 구조적 정보를 모두 충실하게 이해하고 있어야 한다. 

 

 

6.1. Retriever

 

검색 태스크의 서로 다른 측면의 해결에 강점을 지니는 여러가지 검색 방법들이 있다. 저자들은 이를, 기반이 되는 모델에 따라서 3가지로 분류했는데 각각 Non-parametric Retriever, LM-based Retriever, and GNN-based Retriever다. 한 가지 중요한 점은, 쿼리 인코딩이나 엔티티 링킹 같은 전처리 과정에서 사용된 모델은 여기서 고려되지 않는다는 사실이다. 

 

6.1.1. Non-parameteric Retriever

휴리스틱 규칙이나 전통적인 그래프 서치 알고리즘에 기반한 비모수 검색은 딥러닝 모델에 기반하지 않기 때문에 높은 검색 효율성을 지닌다. 각각의 질문-선택 쌍의 주제를 담은 k-hop paths를 검색하는 방법이 이에 해당한다. G-Retriever는 기존의 Prize-Collecting Steiner Tree (PCST) algorithm를 edge prices와 함께 사용하여 관련된 서브그래프 추출의 최적화에 사용했다. Delile et al. 그리고 Mavromatis and Karypis는 먼저 쿼리에 언급된 엔티티들을 추출한 다음, 가장 짧은 거리를 가지는 관련된 엔티티들을 검색한다. 이러한 방법들은 흔히 엔티티 링킹이라는 전처리 과정을 통해서 그래프 검색 전에 노드를 확인한다. 

 

 

6.1.2. LM-based Retriever

LMs를 그래프 RAG에서 검색기로 쓰는데 이는 강력한 자연어 이해 능력에 기반한다. 폭 넓은 자연어 쿼리를 처리하고 해석하여 그래프 베이스 프레임워크의 폭 넓고 다양한 검색 태스크에 활용이 가능하다. 저자들은 LMs를 크게 2가지 종류인 discriminative와 generative
language models로 분류한다. 

Subgraph Retriever는 RoBERTa를 retriever로 학습시켰다. 주제 엔티티로 부터 관련된 paths를 찾는 연속적인 결정 과정이다. KG-GPT는 특정 엔티티와 관계가 있는 top-𝐾 을 생성하는데 LLM을 사용한다.  Wold et al은 GPT-2를 파인튜닝하여 
 reasoning paths를 생성한다. StructGPT는 사전에 정의된 몇가지 함수들을 LLMs가 자동으로 활용하도록 만들었으며, 이를 통해서 관련된 지식을 검색하고 추가적인 추론을 위해 사용된다. 

 

6.1.3. GNN-based Retriever

GNN은 복잡한 그래프 구조를 활용하고 이해하는데 능숙하다. GNN 베이스 검색기들은 그래프 데이터를 인코딩하고 서로 다른 retrieval granularities, 검색 단위에 점수를 매기는데 이는 쿼리와의 유사도에 기반한다. 예를 들어서 GNN-RAG는 그래프를 인코딩하고, 각각의 엔티티에 점수를 매긴다음, 쿼리에 기반한 임계점을 넘는 관련된 엔티티들을 선택한다. EtD는 관련된 paths를 검색하기 위해서 여러번 반복한다. 매 반복 마다 LLaMA2를 사용해서 현재 노드와 연결된 엣지들을 선택하고 GNN에 적용해서 임베딩을 얻는다.  이 임베딩은 LLM이 선택할 다음 라운드의 새로운 레이어의 임베딩으로 사용된다. 

 

6.1.4 Discussion

검색 과정에서 비모수적 방법은 효율성에서 강점이 있지만 다운스트림 태스크에서의 학습 부족으로 부정확할 수 있다. 반면에 LM-based와 GNN-based는 검색 정확도가 높지만 상당한 계산적인 오버헤드를 요구한다. 이러한 상호보완성 때문에 많은 방법들은 효율성과 정확성 모두를 향상시키기 위한 하이브리드 방법을 사용한다. 많은 방법들이 멀티 스트에지 검색 전략을 사용하는데, 매 스테이지 마다 다른 방법을 적용한다. 예를 들어 RoG는 처음에는 LLM으로 planning paths를 생성하고, KG로 부터 planning paths임을 만족하는 경로들만 추출한다. GenTKGQA는 LLM을 사용해서, 쿼리로 부터 중요한 관계들과 제약을 추론한다. 그리고 이러한 제약에 따른 triplets를 추출한다. 

 

 

6.2. Retrieval Paradigm

GraphRAG에서는 다양한 검색 패러다임이 존재하는데 once retrieval 단일 검색, iterative retrieval 반복 검색, and
multi-stage retrieval 다단계 검색을 포함한다. 검색 패러다임은 검색된 정보의 관련성과 깊이에 중요한 역할을 한다. 

 

단일 검색은 한 번의 동작으로 모든 관련된 정보를 수집하는 것을 목표로 한다. 반복 검색은 이전의 검색 정보를 토대로 추가적인 검색을 수행하여 가장 관련있는 결과들을 범위를 좁히면서 찾아 나간다. 저자들은 반복 검색을 다시 적응형과 비적응형으로 구분하는데 검색 중단의 모델에 의하느냐 아니냐가 기준이다. 또 다른 검색 패러다임은 다단계 검색으로 검색이 여러 단계로 나뉜 것을 의미한다. 각 단계마다 서로 다른 종류의 검색기가 적용되어 보다 정확하고 다양한 결과를 얻고자 한다. 

 

6.2.1. Once Retrieval

단일 검색은 모든 관련된 정보를 하나의 쿼리로 얻고자 한다.  하나의 방법으로는 임베딩 유사도를 통해서 가장 관련있는 정보를 뽑는게 있다. 다른 방법으로는 사전에 정의된 규칙이나 패턴을 설계하여 특정한 triplets, paths, subgraphs를 그래프 데이터베이스로 부터 추출하는 방법이 있다. 예를 들어, G-Retriever는 확장된 PCST 알고리즘으로  관련된 서브그래프를 뽑는다. KagNet는 𝑘를 넘지 않는 길이를 가진 모든 주제 페어들의 경로들을 추출한다.  Yasunaga et al과 Taunk et al 는 2-hop 네이버인 모든 주제 엔티티들을 포함안 서브그래프를 뽑는다.

 추가적으로, 서로 분리된 독립적인 검색기들이 병렬적으로 계산되고 단 한번씩만 실행되는 경우도 포함했다. 예를 들어서,  Luo et al. 과 Cheng et al 논문에서는 맨 처음에 LLMs에 여러가지 reasoning 경로를 지시하고, BFS 검색기를 활용하여 각각의 경로에 부합하는 KG 내의 서브그래프를 순차적으로 탐색하는 방법을 사용한다. KG-GPT는 원본 쿼리를 여러개의 서브 쿼리로 분해해서, 개별 서브 쿼리 마다 독립적으로 검색을 수행한다. 

 

 

6.2.2. Iterative Retireval

반복 검색에서는, 여러 단계의 검색이 수행되며, 이전 단계의 검색 결과에 다음 단계의 검색이 의존한다. 이러한 방법들은 연속적인 반복을 통하여 검색된 정보의 완전성 혹은 이해도를 심화시키는게 목적이다. 저자들은 이 과정을 (1) non-adaptive와 (2) adaptive으로 분류했다.

(1) Non-Adaptive Retrieval. 비적응형 검색.

 

비적응형 검색은 고정된 길이의 검색을 따르며, 최대 시간이나 임계점에 의해서 종료가 결정된다. 예를 들어, PullNet은 문제와 관련된 서브그래프들을 𝑇번 반복해서 검색한다. 매 반복마다 검색된 엔티티들의 부분집합을 선택하는 규칙을 설계하고, 이를 KG의 관계가 있는 엣지들의 검색으로 확장한다. 각각의 반복에서 KGP는 처음에, 그래프 내의 노드들과 컨텍스트 간의 유사도에 기반한 시드 노드를 선택한다. 다음 단계로 LLM을 사용해서 요약하고, 시드 노드의 이웃 노드들의 컨텍스트로 업데이트한다. 업데이트 된 내용은 다음번 반복 때 활용한다. 

 

(2) Adaptive Retrieval. 적응형 검색.

 

적응형 검색의 특징은 모델들이 알아서 최적의 검색 종료 시점을 자동으로 선택한다는 점이다. 예를 들어, 언어모델의 hop 예측을 활용해서 검색의 중단 지점을 나타내는데 사용할 수 있다. 모델이 특정한 토큰이나 텍스트를 생성해서 종료 신호로 활용하는 방법도 있다. 예를 들어, ToG는 LLM 에이전트에게 현재 reasoning path에 기반하여 답변을 얻을 수 있다고 판단할 때까지 여러 reasoning paths를 탐색하라고 프롬프트를 작성한다. RoBERTa를 학습해서 주제 엔티티로 부터 경로를 확장하는 방법도 있다. 이 과정에서 “[END]”라는 가상의 단계를 도입해서, 검색을 종료한다. 또 다른 흔한 접근방법은 대규모 모델을 에이전트로 설정하여 질문에 대한 답변을 직접 생성하게 함으로써, 매 반복의 종료 신호로 사용하는 것이다. 그래프 상에서 추론을 수행하는 LLM 기반 에이전트를 제안하는 논문들이 다수 있다. 이러한 에이전트들은 검색할 정보를 자율적으로 결정하고, 사전에 정의된 검색 도구를 호출하며, 검색된 정보를 바탕으로 검색 과정을 종료할 수 있다. 

 

 

6.2.3. Multi-Stage Retrieval

다단계 검색은 검색 과정을 선형적인 여러 단계로 분할하는 방법이다. 검색 향상이나 단계들 사이의 생성 과정 같은 추가적인 단계로 포함한다. 다단계 검색에서 서로 다른 단계들은 다양한 검색기를 사용함으로써, 쿼리의 여러 측면들에 맞춘 검색 기법들을 통합할 수 있다. 예를 들어 Wang et al.은 처음에는 비모수적 검색기로 쿼리의 리즈닝 체인에서 엔티티들의 𝑛-hop paths을 추출하고, 다음 단계인 pruning 가지치기 스테이지를 거치고, pruned subgraph를 기반으로 one-hop 네이버를 한 번 더 검색한다. OpenCSR은 검색을 2단계로 나눈다. 첫 번째 단계에서는 주제 엔티티의 모든 1-hop neighbors를 검색한다. 두 번째 단계에서는 이웃 노드들과 다른 노드들간의 유사도를 모두 비교해서, 유사도가 가장 높은 top-𝑘 nodes를 뽑는다. GNN-RAG에서는 처음에, GNN으로 정답일 것 같은 top-𝑘 nodes를 뽑고, 이어서 쿼리 엔티티들과 정답 엔티티들의 쌍을 놓고 가장 짧은 경로들을 검색한다. 

 

6.2.4 Discussion. 

 

단일 검색은 낮은 복잡도와 빠른 응답 시간으로, 실시간 응답을 요구할 때 적합하다. 반대로, 반복 검색은 더 많은 시간 복잡도를 지니지만, 특히 LLM을 검색기로 쓰는 경우, 더 긴 처리시간을 잠재적으로 요구한다. 하지만 이 방법은 보다 높은 검색 정확성을 산출할 수 있으며 이는, 검색된 정보와 생성된 답변에 대한 반복적인 정제로 가능하다. 따라서, 검색 패러다임의 선택은 특별한 유즈 케이스와 요구사항에 따른 정확도와 시간 복잡도 사이의 균형에 대한 선택이다. 

 

 

 

6.3. Retireval Granularity

 

다른 태스크 시나리오와 인덱싱 타입에 따라서, 연구자들은 구별되는 granularities (i.e., the form of related knowledge retrieved from graph data)를 설계했으며, 이는 nodes, triplets, paths, and subgraphs로 나눌 수 있다. 각각의 검색 단위는 고유한 장점을 지니며, 서로 다른 실전 시나리오에 따라 어울린다. 위 단위들을 아래 섹션에서 소개한다. 

 

6.3.1. Nodes

노드는 그래프 내의 개별 요소에 집중한 정확한 검색을 가능하게 한다. 특정한 정보 추출이나 목표로 한 쿼리에 이상적이다. 일반적으로, KG에서 노드들은 엔티티다. 텍스트 속성을 지닌 그래프의 경우, 노드는 노드의 속성을 묘사하는 테긋트 정보를 포함할 수 있다. 그래프의 노드를 검색함으로써, 그래프 RAG 시스템은 노드들이 지닌 고유의 속성들, 관계들, 그리고 맥락적인 정보에 대한 상세한 통찰력을 제공한다. 문서 그래프를 구축하고 관련된 문단 노드들을 검색하는 경우도 있다.  

 

 

 

6.3.2. Triplets

일반적으로 트리플렛은 주어-술어-목적어(subject-predicate-object) 튜플 형태의 엔티티와 그 관계들로 구성되며, 그래프 내의  관계를 구조적으로 표현한다. 트리플렛의 구조적인 형태는 분명하고 정리된 데이터 검색을 가능하게 한다. 3개의 논문에서는 아래의 방법을 사용했다. 우선, 그래프 데이터의 트리플렛을 사전에 정의된 템플릿을 사용해서 문장으로 만든 다음, 텍스트 검색기로 관련된 트리플렛들을 뽑는다. 하지만 그래프 데이터로 부터 직접 트리플렛을 뽑는 것은 맥락적인 너비와 깊이가 부족하므로 reasoning chains와 간접적인 관계들을 포착하지 못할 수도 있다. 이러한 난점을 해결하기 위해서 원본 질문에 근거한 논리적인 연쇄를 생성하거나 각각의 논리 연쇄의 관련된 트리플렛을 검색하는 방법을 제안하기도 했다. 

 

 

 

6.3.3. Paths

경로 단위의 검색은 엔티티들 간의 관계에 대한 연속적 배열을 포착할 수 있으며, 이는 맥락적인 이해와 추론 능력을 향상시킬 수 있다. GraphRAG에서 경로 검색은 복잡한 관계와 맥락적인 의존성을 포착하는데 있어서 독보적인 장점을 지닌다. 하지만 그래프 크기가 커질수록, 계산 복잡도가 지수적으로 커지는 문제점이 있다. 이런 문제점을 해결하기 위해서 사전에 결정된 규칙에 기반한 연관있는 경로들을 검색하는 방법들이 있다. Wang et al.와 Lo and Lim 방법에서는 쿼리에 있는 엔티티 쌍을 선택하고, 𝑛-hop 내의 모든 경로들을 순회한다.  HyKGE는 처음에는 path, co-ancestor chain, and co-occurrence chain 세 종류의 경로를 정의하고, 각각의 경로를 검색하기 위한 규칙을 활용한다. 그래프 상의 경로 탐색을 위해서 모델을 사용하는 경우도 있다. ToG는 LLM 에이전트에게 프롬프트로 명령을 시켜서 KGs 상에서의 빔 서치를 수행하고, 문제에 대한 답변에 도움을 줄 수 있는 다양한 가능한 추론 경로들을 찾는다. Luo et al. , Wu et al.  and Guo et al. 는 우선 모델을 활용해서 믿을만한 추론 계획들을 생성하고, 계획에 기반하여 관련된 경로들을 검색한다. GNN-RAG는 처음에는 질문에 있는 엔티티들을 식별하고, 특정한 길이를 만족하는 관계들을 지닌 모든 엔티티 쌍들의 경로들을 추출한다.  

 

 

6.3.4. Subgraphs

 

서브그래프 검색은 그래프 내부의 포괄적인 관계적 맥락을 포착에 분명한 장점이 있다. 이 검색 단위는 GraphRAG가 거대한 구조 내부의 복잡한 패턴, 시퀀스, 그리고 의존성들을 추출하고 분석하는걸 가능하게 하며,  의미론적 연결에 대한 보다 미묘한 차이의 이해와 더 깊은 통찰력을 가능하게 한다. 검색의 효율성과 완전성 모두를 보장하기 위해서, 몇몇 방법들은 초기에 규칙에 기반한 후보 서브그래프들을 검색하고, 그 뒤에 정제하거나 과정을 이어나가는걸 제시한다. Yasunaga et al. , Feng et al. and Taunk et al.은 처음에 주제 엔티티들과  two-hop 네이버들이라는 노드 집합을 선택한다. 그 다음 서브그래프 내의 노드 집합들로 부터 헤드와 테일 엔티티들에 대한 엣지들을 선택한다. 뿐만 아니라 임베딩 기반의 서브 그래프 검색 방법들도 있다, 예를 들어서 Hu et al.의 경우  그래프 DB의 모든 𝑘-hop ego networks들을 인코딩 한 다음, 임베딩 사이의 유사도에 기반하여 쿼리와 관련된 서브그래프들을 검색한다. Wen et al.과 Li et al.은 두 종류의 그래프를 뽑는데, 사전정의된 규칙에 따라서 Path evidence subgraphs and Neighbor evidence subgraphs를 뽑는다. OpenCSR은 처음 몇개의 시드 노드부터 시작에서 점진적으로 새로운 노드로 확장하면서 서프그래프를 형성한다. 앞서 언급한 직접적인 서브그래프 검색 방법 외에, 몇가지 작업들은 우선 관련된 경로를 검색한 다음 관련된 서브그래프를 구성하기도 한다. Zhang et al.은 RoBERTa 모델을 이용해서 몇가지 추론 경로를 여러 단계의 결정 과정을 통해 확인한 다음, 서로 다른 경로의 동일한 엔티티들을 통합하여 최종 서브그래프를 도출한다. 

 

 

6.3.5. Hybrid Granularities

앞서 언급된 여러가지 검색 단위의 장점과 단점을 고려하여, 여러 연구자들은 하이브리드 단위를 제시하는데 그래프 데이터로 부터 여러 단위를 사용해서 관련된 정보들을 검색한다. 디테일한 관계들과 보다 넓은 범위의 맥락적 이해 양쪽을 포착하기 위해서다. 여러 논문들은 LLM 에이전트에 기반해서 적응적으로 nodes, triplets, paths, and subgraphs를 검색 단위로 선택하는 방법을 제시한다. 

 

 

 

6.3.6 Discussion. 

(1) 실제 세계에서의 적용해서는 명확한 검색 단위가 없다. 왜냐면 서브그래프가 다양한 경로들과 트리플렛에 의해서 형성되기 때문이다. 

(2) 다양한 검색 단위는 서로 다른 장점을 지닌다. 검색 컨텐츠와 효율성 사이의 균형을 잡기 위해서는 검색 단위를 특정한 태스크의 맥락에 맞게 선택하는 일이 매우 중요하다. 반면에 복잡한 시나리오일 경우 하이브리드 방법이 더 낫다. 따라서, GraphRAG는 다양한 도메인에서 필요한 다양한 정보에 맞게 효율적으로 검색 단위를 선택해야 한다. 

 

 

 

6.4. Retrieval Enhancement

 

검색의 질을 담보하기 위해서, 연구자들은 유저의 쿼리와 검색된 지식을 향상시키는 테크닉들을 제시한다. 여기서는 query enhancement 쿼리 향상을 query expansion 쿼리 확장과 query decomposition 쿼리 분해로 쪼개고, knowledge enhancement 지식 향상을 merging 병합과 pruning 가지치기로 나눈다. 이 전략들은 집단적으로 사용해서 검색 과정을 최적화한다. 또 다른 방법으로는 RAG에서 흔히 쓰는 query rewriting이 있다. 저자들은 RAG에서는 많이 사용되지만, GraphRAG에서는 드물게 쓰이는 쿼리 재작성을 깊게 파지 않았으나, 앞으로 적용할 가능성은 알고 있다. 

 

 

6.4.1. Query Enhancement

쿼리에 사용되는 전략들은 보통 전처리 기술들을 포함한다. 이 기술들은 더 나은 검색을 위해 정보를 더 풍부하게 한다. 이는 쿼리 확장이나 쿼리 분해를 포함한다. 

(1) Query Expansion. 쿼리 확장. 

 

일반적으로 쿼리는 길이가 짧으며 정보량이 제한적이기 때문에, 쿼리 확장은 추가적인 용어나 개념을 정제하거나 보충해서 결과를 향상시키고자 한다. Luo et al은 KG에 기반한 relation paths를 LLM으로 생성하여 검색 쿼리를 더 낫게 한다. Cheng et al은 SPARQL을 채택하여 Wikidata로 부터 관련된 모든 쿼리 엔티티를 가져와서 동일한 엔티티에 대한 여러 어휘들을 포착한다. Huang et al은 다음의 방법을 제안하는데, 우선 의미론적으로 관련 있는 쿼리들을 찾은 다음 오리지널 쿼리를 다시 가중치를 매겨서 검색 성능을 향상시킨다. HyKGE는 large model로 hypothesis output 가설 출력을 만든다. 이 출력과 원래 쿼리를 concat해서 검색기에 입력으로 넣는다. Golden-Retriever는 쿼리에 있는 jargon 용어를 우선 인식한 다음, jargon의 설명을 받아와서 쿼리의 보충물로 사용한다.

 

 

(2) Query Decomposition. 쿼리 분해. 

 

쿼리 분해는 원래 쿼리를 더 작은 서브 쿼리로 쪼개는 작업을 의미한다. 각각의 서브쿼리는 원본 쿼리의 특정한 면이나 요소를 판영하며, 언어 쿼리가 지니는 애매모호함을 성공적으로 완화한다. 

 

6.4.2. Knowledge Enhancement

처음 검색 결과를 얻은 다음 이를 정제하거나 향상시키는 전략이 knowledge enhancement다. Knowledge merging과 knowledge pruning을 포함하며, 포괄적일 뿐만 아니라 유저가 필요한 정보의 검색 결과를 도출하는게 목적이다. 

 

(1) Knowledge Merging. 지식 통합  

 

검색된 정보의 지식 통합은 정보의 압축과 종합을 가능하게 하며, 다양한 소스의 세부 정보들을 통합하여 보다 포괄적인 관점을 얻는데 도움을 준다. 이러한 작업은 정보의 완전성과 일관성을 향상시킬 뿐만 아니라, 모델에서의 입력 길이 제한과 관련된 이슈도 완화한다. KnowledgeNavigator는 노드들을 통합하고, triple aggregation을 통해 검색된 서브그래프들을 압축하여 추론 효율성을 향상시킨다. Subgraph Retrievel에서는 하나의 서브그래프에 속한 개별 토픽 엔티티에 대해서 top-𝑘 paths를 검색한 다음, 다양한 서브그래프로 부터의 동일한 엔티티들을 통합하여 최종 서브그래프를 형성한다. Wen et al.과 Li et al.은 relations에 기반한 검색된 서브그래프들을 통합하는데, 이는 헤드 엔티티와 테일 엔티티들의 결합이며, 동일한 관계를 지니는 서로 다른 엔티티 집합으로 결합하고 이를 토대로 relation paths를 형성한다.  

 

(2) Knowledge Pruning. 지식 프루닝

 

Knowledge pruning은 보다 관련이 없거나 불필요한 정보들을 거름으로써 결과를 정제한다. 기존의 방법들은 크게 2가지 범주가 있는데 (re)-ranking-based approaches와 LLM-based approaches다. (Re)-ranking methods은 잘 짜여진 메트릭이나 기준을 토대로 검색된 정보의 우선순위와 순서를 재정립하는 방법이다. Triplets을 re-rank하거나, FlagEmbedding에서처럼 bge_reranker_large 모델을 통해서 텍스트를 인코딩하고  top-k documents에 대해 re-rank를 수행하기도 한다. PLM을 학습해서 쿼리와 검색된 정보 사이의 ranking을 다시 매기기도 한다. 쿼리와 서브 그래프 간의 re-rank, KG entity nodes와 question context 사이의 relevance score에 기반한 서브그래프 검색, Personalized PageRank 사용 등 다양한 방법들이 있다. 

 

 

7. Graph-Enhanced Generation

 

 

 

생성 단계는 GraphRAG에서 매우 중요하며, 쿼리와 검색된 그래프 데이터를 통합함으로써 응답의 질을 높이는게 목적이다. 이 단계에서는 반드시, 다운스트림 태스크에 적합한 생성 모델을 선택해야 한다. 검색된 그래프 데이터는 생성기에 호환되는 형태로 변환해야 한다. 생성기는 쿼리와 변환된 그래프 데이터 모두를 입력으로 받아서 최종 응답을 생성한다. 이러한 근본적인 과정 외에도 출력을 향상하기 위한 생성 향상 기법들이 있다. 자세한 과정들은 Figure 5에 묘사되어 있다. 

 

 

7.1. Generators

생성기의 선택은 수행해야 하는 다운스트림 태스크의 종류에 따라 달라진다. Discrimi-
native tasks (e.g., multi-choice question answering) 판별형 작업이나 discriminative tasks (e.g., KBQA)로 구성될 수 있는 generative 작업들은 GNNs나 discriminative language models로 데이터의 표현을 학습할 수 있다. 서로 다른 정답 옵션들과 관련된 로짓에 매핑되어 응답을 제공할 수 있다. 다른 방법으로는, 생성형 언어 모델을 이용해서 직접 답을 생성할 수 있다. 하지만 GNNs와  discriminative language models로는 충분하지 않으며, 텍스트의 생성과 이를 위한 디코더의 적용이 필요하다. 

 

7.1.1. GNNs

GNN은 그래프 데이터를 직접 인코딩하기 때문에 그래프에 내재된 복잡한 구조와 관계들을 포착할 수 있으며, 따라서 강력한 표현 능력을 지니고 있기 때문에 discriminative tasks에 효과적이다. 이 인코딩된 데이터를 Multi-Layer Perceptron (MLP)에 보내서 예측 결과를 생성한다. 이런 접근 방식은 GCN, GAT, GraphSAGE, GraphTransformers 등의 기존 GNN 모델들을 그대로 사용하거나 다운스트림 작업에 맞게 수정해서 사용한다. HamQA는 hyperbloic GNN을 설계하여 검색된 그래프 데이터와 쿼리 간의 상호 계층적인 정보를 학습한다.  Sun et al.은 PageRank로 message-passing 메시지 전달 중에 인접 노드에 대한 점수를 계산하고, 이를 가중치로 부여해서 집계한다. 중앙 노드가 가장 관련 있는 이웃 노드들로 부터의 정보를 통화하는 능력을 향상시킨다.  Mavromatis and Karypis는 쿼리를 여러가지 벡터 (지시들)로 디코딩하고, GNN은 사용해서 BFS를 에뮬레이션하여 지시 실행을 개선하고, KG-aware 정보로 지시를 업데이트함으로써 명령 디코딩과 효과적인 추론을 가능하게 한다. 

 

 

7.1.2. LMs

언어모델들은 텍스트 이해에 능력이 강력하므로, 생성기로 기능할 수 있다. 언어모델들을 그래프 데이터와 통합하는 맥락에서, 우선 검색된 그래프 데이터를 특정한 그래프 포맷으로 변경해야 한다. 자세한 형식에 대한 내용은 7.2 섹션에서 설명될것이며 그래프 데이터의 관계 밎 계측적 구조를 보존하는게 중요하다. 이는 모델의 복잡한 데이터 유형 해석 능력과 관련있다. 그래프 데이터가 형식화되면 쿼리와 결합되어 언어모델의 입력이 된다. BERT나 RoBERTa 등의 인코더 모델들은 주로 판별 작업에 사용된다. GNN처럼 입력 텍스트를 인코딩한 다음 MLP를 통해 answer sapce 정답 공간으로 매핑된다. 반면에 인코더-디코더나 디코더 모델, T5, GPT-4, LLaMa의 경우 판별과 생성 태스크 모두 가능하기 때문에, 텍스트 이해, 생성, 추론에 탁월하여 직접 처리하고 텍스트 응답을 생성할 수 있다. 

 

 

7.1.3. Hybrid Models

GNN의 그래프 구조 표현이라는 장점과 LM의 텍스트 이해에 대한 강점을 모두 살리기 위해서, 하이브리드 생성 방법이 제시된다. 각각은 Cascaded 패러다임과 Parallel 패러다임이다. 

(1) Cascaded Paradigm. 

 

캐스케이디드에서는 한 모델의 출력이 다음 모델의 입력이 되는 순차적인 상호작용이 이루어진다. 구체적으로는, GNN이 그래프 데이터를 처리하여 구조적 정보와 관계적 정보를 언어모델이 이해할 수 있는 형태로 가공한다. 이를 토대로 언어모델이 텍스트 기반 답변을 생성한다. 

(2) Parallel Paradigm. 

 

반면에, 병렬 패러다임은 GNN와 언어모델이 초기 입력을 받아서, 동시에 각각이 독립적으로 응답을 생성한다. 응답들을 모아서 특정한 규칙이나 다른 모델에 의해서 병합되고 통합된 응답을 생성한다.  GreaseLM, ENGINE의 G-Laddder 등이 이에 속한다. 

 

 

7.2. Graph Formats

GNN과 달리, 언어모델을 생성기로 사용할 경우 그래프 데이터를 직접 인코딩 할 수 없다. 이는 그래프 데이터가 비유클리드적이기 때문인데 이를 해결하기 위해서 그래프 변환기로 언어모델과 호환될 수 있도록 형식을 변환해야 한다. 본 연구에서는 graph language과 graph embedding이라는 두 가지 형식을 간력하게 소개하며, Figure 6에는 그림으로 예시가 소개되어 있다. 

 

7.2.1. Graph Language

 

 

그래프 서술 언어는 그래프 데이터를 특징짓고 표현하기 위해 특별히 고안된 방법이다. 그래프 내의 구성 요소와 상호 연결을 설명하는 균일한  syntax 구문과 semantic framework 의미론적 틀을 규정한다. 이러한 언어를 통해 사용자는 기계가 이해할 수 있는 형식으로 그래프 데이터를 일관되게 생성, 조작 및 해석할 수 있습니다.

 

그래프 서술 언어는 그래프 아키텍처 정의, 노드와 엣지에 대한 속성 지정, 그리고 그래프 구조에 대한 연산 및 쿼리 구현을 가능하게 한다. 다음으로, 인접/엣지 테이블, 자연어, 코드, 구문 트리, 노드 시퀀스의 다섯 가지 유형의 그래프 언어를 각각 소개한다.

 

 

(1) Adjacency / Edge Table.

 

인접 테이블과 엣지 테이블은 그래프 구조를 설명하는데 널리 사용된다. 인접 테이블은 각 노드의 바로 인접한 이웃들을 열거하여 희소 그래프에서의 연결들을 간결하게 표현한다. 예를 들어서, Kg-GPT에서는 검색된 서브 그래프의 트리플을 선형화한 다음 LLM에 입력한다.

반대로, 엣지 테이블은 그래프 내의 모든 엣지들을 자세히 보여주며 특히 선형 형식의 그래프를 처리하고 분석하는데 유용한 직관을 제공한다. 두 방법 모두 간결하며 이해하기 쉽고 직관적이다. 

 

(2) Natural Language. 

 

주어진 사용자 쿼리느 보통 자연어로 표현되며, 언어모델들이 자연어 이해 능력이 뛰어남을 고려할 때 검색된 그래프 데이터를 자연어로 설명하는 것은 설득력있는 접근이다. 예를 들어서, 일부 연구자들은 각 엣지 유형에 대한 자연어 템플릿을 미리 정의하고, 각 엣지의 끝점을 유형에 따라 템플릿을 채워넣는 방식을 제안한다. 자연어를 사용하여 중앙 노드의 1-hop과 2-hop 인접 노드들의 정보를 설명하는 방법도 있다. 감지된 그래프 커뮤니티에 대한 보고서 형식의 요약을 활용하거나, 서브그래프의 엣지 테이블을 작성하고 자연어로 설명하거나, 노드와 엣지의 다양한 표현이 연구되기도 했다. 

 

(3) Code-Like Forms. 

 

자연어 설명은 1-D 시퀀스나 그래프 데이터의 2-D 구조를 직접 표현하기에는 근본적으로 부적절하며, 언어모델의 강력한 코드 이해 기능을 고려하여 연구자들은 코드와 유사한 형식으로 그래프 구조를 표현하는 방법을 탐구했다. 예를 들어서, Guo et al.은 Graph Modeling
Language (GML)과 Graph Markup Language (GraphML)의 사용을 검토했다. 이러한 표준화된 언어들은 그래프 데이터를 위해 특별하게 설계되었으며, 노드, 엣지, 그리고 상호관계를 포괄하는 설명을 제공한다. 

 

 

(4) Syntax Tree. 

 

직접 그래프를 평면화하는 방법과 비교해서, 일부 연구에서는 syntax tree 구문트리와 유사한 구조로의 변환을 제시한다. 구문 트리는 계층적 구조를 가지며, topological graphs 위상 그래프이므로 topological order 위상 순서도 유지한다. 이 방법은 더 많은 구조적 정보를 보존하며 그래프의 내재적인 속성의 이해와 분석을 향상시킨다. 서로 다른 그래프 요소들 간의 관계적 역학을 보존할뿐만 아니라 더 정교한 그래프 분석과 처리 알고리즘을 가능하게 한다. GRAPHTEXT는 중심 노드의 에고 네트워크를 그래프-구문 트리 형식으로 변환하는 방법을 제안한다.  구조적 정보를 캡슐화할 뿐만 아니라 노드의 특징도 통합한다. 이 구문 트리를 탐색함으로써 위상 순서와 계층적 구조를 모두 유지하는 노드 시퀀스를 얻을 수 있다.

 

(5) Node Sequence. 

 

일부 연구들은 사전에 정의된 규칙에 의한 노드 시퀀스를 통해서 그래프를 표현하는 방법을 제시한다. 자연어 설명과 비교했을 때, 노드 시퀀스는 더 간결하며 사전 지식 특히 규칙이 강조하는 구조적 정보를 통합한다. Luo et al.과 Sun et al.은 검색된 경로를 노드 시퀀스로 변환하여 LLM에 입력함으로써 작업 성능을 향상시킨다. LLaGA는 그래프를 노드 시퀀스로 변환할 수 있는 두 가지 템플릿을 제안한다. 첫 번째 템플릿인 Neighborhood Detail Template은 중심 노드와 그 주변 영역에 대한 자세한 분석을 제공한다. 두 번째 템플릿인 Hop-Field Overview Template은 노드 주변 영역에 대한 요약된 관점을 제공하며, 더 넓은 영역을 포함하도록 확장할 수 있다. GNN-RAG는 검색된 추론 경로를 노드 시퀀스 형태로 LM에 입력하여 프롬프트로 사용한다.

 

Discussion. 

 

좋은 그래프 언어는 완전하고 간결하며 이해하기 쉬워야 한다. 완전성이란 그래프 구조 내의 모든 필수 정보를 포착하여 중요한 세부 사항이 누락되지 않도록 하는 것을 의미한다. 간결성은 텍스트 설명을 간결하게 유지하여 "lost in the middle 중간에서 길을 잃는 현상"을 방지하거나 언어모델의 길이 제한을 초과하지 않게 하기 위해 필요하다. 긴 입력은 언어모델의 처리 능력을 저해하여 맥락 손실이나 데이터 해석의 불완전성을 초래할 수 있다. 이해하기 쉬움은 사용된 언어가 LLM이 쉽게 이해될 수 있도록 보장하여, 그래프 구조의 정확한 표현을 용이하게 한다. 다양한 그래프 언어의 특성으로 인해, 언어 선택은 다운스트림 작업의 성능에 상당한 영향을 미칠 수 있다.

 

 

7.2.2. Graph Embeddings

위 그래프 언어 방법들은 그래프 데이터를 텍스트 시퀀스로 변환하는 작업으로, 지나치게 긴 컨텍스트가 생성되어 높은 계산 비용이 발생하고, 잠재적으로 LLM의 처리 한계를 초과할 수 있다. 또한 LLM은 그래프 언어를 사용하더라도 그래프 구조를 완전히 이해하는데 어려움을 겪고 있기 때문에, GNN으로 그래프를 임베딩으로 표현하는 것은 유망한 대안이다. 핵심은 그래프 임베딩과 텍스트 표현을 통합된 의미 공간으로 임베딩하는 것이다. 그래프 데이터를 텍스트로 변환하고, LM 기반 인코더로 인코딩하고 디코더에 입력하는 FiD (Fusion-in-Decoder) 방법들도 소개되었다. 특히 그래프 표현을 LM에 입력하는 일은 오픈소스에서만 가능하며, GPT-4 같은 클로즈드 모델에서는 불가능하다. 그래프 임베딩은 긴 텍스트 입력의 처리는 피하지만 특정 엔티티 이름과 같은 정확한 정보의 보존에는 어려움이 있으며, 일반화 성능이 떨어지는 다른 문제가 있다. 

 

 

7.3. Generation Enhancement

생성 단계에서는, 검색된 그래프 데이터를 생성기가 허용하는 형식으로 변환하고 쿼리와 함께 입력하여 최종 응답을 생성하는 것 외에도,
많은 연구자들이 출력 응답의 품질을 향상시키기 위해 다양한 생성 향상 기법을 연구했다.
이러한 기법들은 적용 단계에 따라 pre-generation enhancement 생성 전 향상, mid-generation enhancement 생성 중간 향상, post-generation enhancement 생성 후 향상의 세 가지 범주로 분류할 수 있다.

 

 

7.3.1. Pre-Generation Enhancement

생성 전 향상 기법은 생성기에 입력하기 전에 입력 데이터 또는 표현의 품질을 개선하는 데 중점을 둔다. 실제로 생성 전 향상과 검색 사이에는 명확한 경계가 없다. 본 논문에서는 검색 단계를 원본 그래프에서 지식을 검색하는 과정과 검색된 지식을 병합 및 가지치기하는 과정으로 분류합니다. 이후의 작업은 생성 전 향상으로 간주한다.

 

% 검색 (지식 검색, 검색 된 지식 후처리) -> 생성 전 항샹 

 

일반적인 생성 전 향상 방법은, 검색된 그래프를 의미론적으로 풍부하게 만들어서 그래프 데이터와 텍스트 쿼리 사이의 통합을 더 단단하게 만드는게 목적이다. 그래프 데이터를 더 자연스럽고 풍부한 자연어로 변환한다. 반대로 DALK 방법은 검색된 그래프 데이터를 사용해서 쿼리를 재작성한다. 그래프 데이터 외의 추가 정보를 통합하는 방법들도 있는데, PullNet은 엔티티와 관련된 문서들을 통합하고, MVP-Tuninbg은 다른 관련 질문을 검색한다.  

 

7.3.2. Mid-Generation Enhancement

중간 생성 향상은 생성 과정 중에 적용되는 기법들을 포함한다. 일반적으로 중간 결과 또는 문맥적 단서를 기반으로 생성 전략을 조정한다. TIARA는 출력 공간을 제어하고 생성 오류를 줄이기 위해서 제한된 디코딩을 도입한다. Logical forms 논리 형식을 생성할 때, 제약 조건 디코더가 현재 패턴 항목을 생성하고 있음을 감지하면 다음에 생성되는 토큰을 KB 클래스와 관계를 포함하는 시도에 존재하는 옵션으로 제한한다. Beam search와 비교하였을 때, 이 방법론은 KG에 존재하는 패턴이 생성되도록 조절함으로써 생성 오류를 줄인다. 다단계 추론을 달성하기 위해서, LLM의 프롬프트를 조정하는 방법들도 있다. MindMap의 경우 답변과 추론 과정 모두를 생성한다. 

 

 

 

7.3.3. Post-Generation Enhancement

생성 후 향상은 초기 응답이 생성된 다음에 이루어진다. 생성 후 개선의 주된 방법은 여러개의 생성된 응답들을 통합하여 최종 답변을 생성하는 방법들이다. 일부 방법들은 서로 다른 조건이나 입력에서 동일한 생성기의 출력을 통합하는데 집중한다. Edge et al.을 예로 들면, 각 그래프 커뮤니티에 대한 요약을 생성한 다음, 요약을 기반으로 쿼리에 대한 응답을 생성하고 LLM으로 응답마다 점수를 매긴다. 궁극적으로 응답은 점수에 따라 내림차순으로 정렬되고 토큰 제한에 걸릴 때 까지 프롬프트에 통합한다. 그 다음 LLM이 최종 응답을 생성한다.

 

 

먼저 쿼리를 여러 하위 질문으로 분해한 다음, 각 하위 질문에 대한 답변을 생성하고 마지막으로 모든 하위 질문에 대한 답변을 병합하여 최종 답변을 얻는 방법들도 있다. 또 다른 방법에서는 서로 다른 모델에서 생성된 응답들을 결합하거나 선택한다. UniOQA, Cypher Query Language(CQL), EmbedKGQA, KALMV 등의 다양한 방법들이 있다. KALMV는 여러 응답의 통합 외에도 생성된 답변이 올바른지 판단하는 검증기를 학습시키고, 올바르지 않은 경우 오류가 생성 때문인지 검색 때문인지 추가로 판단한다.

 

 

 

8. Training

 

 

 

 

이 섹션에서 저자들은 검색기, 생성기의 개별적 학습과 joint training 공동 학습을 요약한다. 이 작업을  Training-Free and Training-Based으로 범주화하는데, 이는 explicit training이 요구 되느냐 아니냐에 따라 결정된다. Training-Free는 보통 GPT-4 같은 클로즈드 소스 LLM에 사용되며, 조심스럽게 구성된 프롬프트를 통해서 LLM의 검색과 생성 능력을 조절한다. LLM은 강력한 텍스트 이해와 추론 능력이 있지만, 특정 다운스트림 작업에서의 최적화의 부족으로 최적이 아닌 결과를 낼 수 있다. 

 반대로, Training-Based는 지도 학습 신호를 활용한 학습과 파인 튜닝을 포함한다. 특정한 작업의 목적에 맞준 성능 향상을 통해서 검색 혹은 생성된 컨텐츠의 퀄리티를 잠재적으로 개선할 수 있다. 

 공동 학습은 검색기와 생성기의 시너지를 도모하는 방법으로, 두 구성 요소의 상호 보완을 강조한다. 

 

 

8.1. Training Strategies of Retriever

8.1.1. Training-Free

크게 두 가지 유형이 있는데, 첫 번째 유형은 비매개변수  non-parametric 검색기로 특정 모델이 아닌 미리 정의된 규칙이나
기존의 그래프 검색 알고리즘에 의존한다. 두 번째 유형은 사전 학습된 언어 모델을 검색기로 활용한다. 사전 학습된 임베딩 모델을 사용하여 쿼리를 인코딩하고 쿼리와 그래프 요소 간의 유사성을 기반으로 직접 검색을 수행한다. 또 다른 방법으로는 생성형 언어 모델을 사용하여 학습 없는 검색을 수행한다. 엔티티, 트리플, 경로 또는 서브그래프와 같은 후보 그래프 요소는 LLM에 쓸 프롬프트 입력의 일부로 포함된다. LLM은 의미적 연관성을 활용하여 제공된 프롬프트에 따라 적절한 그래프 요소를 선택하며, 이는 LLM의 강력한 의미 이해 기능에 의한 것이며, 명시적인 학습 없이 관련 그래프 요소를 검색한다.

 

8.1.2. Training-Based 

검색 단위가 노드 또는 트리플렛인 경우, 많은 방법들이 검색 정답과 쿼리 간의 유사성을 최대화하도록 검색기를 훈련시킨다. 예를 들어,
MemNNs는 메트릭 학습을 활용하여 의미 공간에서 정답을 쿼리와 밀접하게 정렬하는 동시에 쿼리와 관련 없는 사실을 구분한다. 반대로, 검색 단위가 경로인 경우, 검색기 훈련은 종종 autoregressive 자기회귀적 접근 방식을 채택하는데, 이 방식에서는 이전 관계 경로가 쿼리의 끝에 연결된다. 그런 다음 모델은 연결된 입력을 기반으로 다음 관계를 예측한다.

 그러나 대부분의 데이터 세트에서 검색 콘텐츠에 대한 정답이 부족하여 상당한 어려움이 발생한다. 이 문제를 해결하기 위해 많은 방법들이 distant supervision을 기반으로 추론 경로를 구성하여 검색기 훈련으로 안내하려고 시도한다. 예를 들어, Zhang et al., Feng
et al. 및 Luo et al. 은 쿼리의 엔티티와 답변의 엔티티 간의 모든 경로 (또는 최단 경로)를 추출하여 이를 검색기의 훈련 데이터로 사용한다.

 또한 Zhang et al. 은 비지도 학습 환경에서 distant supervision을 위해 관계 추출 데이터셋을 사용한다.

 

 또 다른 범주의 방법은 implicit intermediate supervision signals를 활용하여 검색기를 훈련한다. 예를 들어, NSM은 양방향 검색 전략을 사용하는데, 두 검색기는 각각 헤드 엔티티와 테일 엔티티에서 검색을 시작한다. 지도 학습의 목표는 두 검색기가 검색한 경로가 가능한 한 가깝게 수렴하도록 하는 것입니다. KnowGPT 및 MINERVA는 경로 또는 부분 그래프를 구축하기 위한 인접 노드 선택을 마르코프 프로세스로 처리한다. 검색된 정보에 답변이 포함되는 것을 중심으로 보상 함수를 설계하고, 폴리시 그라디언트 같은 강화 학습 방법을 채택하여 검색기를 최적화한다.

 
 일부 방법에서는 distant supervision signals 또는 implicit intermediate supervision signals에 상당한 노이즈가 포함될 수 있어 효과적인 검색기를 훈련하기 어렵다고 주장한다. 따라서 검색기의 사전 훈련을 위해 self-supervised methods의 사용을 제시한다. SKP는 DPR(Dense Passage Retrieval) 모델을 사전 훈련한다. 먼저, 서브그래프에 대한 무작위 샘플링을 수행하고 샘플링된 서브그래프를 passage로 변환한다. 그 다음 passage를 무작위로 마스킹하고, Masked Language Model MLM을 사용하여 모델을 훈련하고, 마스킹된 passage와 원본 패시지를 비교를 위한 positive pairs로 처리하여 contrastive learning을 수행한다.

 

 

8.2. Training of Generator

8.2.1. Training-Free

학습이 없는 생성기는 클로즈드 LLM이나 높은 학습 비용을 피해야하는 시나리오에 적합하다. 검색된 그래프 데이터가 쿼리와 함께 LLM에 입력으로 들어가며, 프롬프트에 제공된 작업 설명을 바탕으로 응답을 생성하는데 쿼리와 그래프 데이터를 모두 이해하는 고유의 능력에 강하게 의존한다. 

 

8.2.2. Training-Based 

생성기 학습은 다운스트림 작업의 지도학습 신호를 직접적으로 받는다. Supervised fine-tuning (SFT)를 통해서 생성형 LLM의 파인튜닝을 달성할 수 있는데, 이때 작업 설명, 쿼리, 그리고 그래프 데이터가 입력으로 들어가며 출력 결과는 그라운드 트루스와 비교된다. 반면에 GNN이나 discriminative 모델이 생성기로 작동하는 경우, 다운스트림 태스크에 맞추어 조정된 특수한 loss functions에 맞추어 모델을 효과적으로 학습할 수 있다. 

 

8.3. Joint Training 

공동 학습은 검색기와 생성기를 한 번에 학습하는 방법이다. 일반적으로는 LLM과 같은 단일 모델로 통합하고 검색과 생성 목적 함수들을 동시에 훈련한다. 이는 단일 프레임워크에서 일관된 응답을 생성하게 한다. 다른 방법론으로는 검색기과 생성기를 별도로 훈련한 다음 , 파인튜닝을 공동으로 훈련하는 방법이 있다. Subgraph Retriever는 alternating training paradigm을 제시하는데, 검색기의 파라미터를 고정하고 생성기를 훈련한다. 생성기 파라미터를 고정하고 생성기를 훈련한다. 이런 반복으로 두 구성 요소를 모두 파인튜닝한다.  

 

9. Applications and Evaluation

아래의 Table 1에서는 GraphRAG를 downstream tasks, benchmarks, methods, and evaluation metrics 등으로 분류해서 정리했다. 

 

9.1. Downstream Tasks

9.1.1. Question Answering

KBQA - Knowledge Base Question Answering

CSQA - CommonSense Question Answering

 

9.1.2. Information Retrieval

Entity Linking - NLP에서 중요한 작업으로, 텍스트에서 언급된 엔티티를 판별하고 KG에서 연관된 엔티티에 연결하는 작업이다.

Relation Extraction - 엔티티 간의 의미론적 관계를 밝히고 분류하는 작업이다. 

 

9.1.3. Others

 

Fact Verification

Link Prediction

Dialogue Systems

Recommendation

 

 

9.2. Application Domains

9.2.1. E-Commerce

 

• 사용자–상품 상호작용을 그래프로 표현 가능
• 대규모 데이터 환경에서 중요 서브그래프 추출이 핵심
• 활용 사례:
  • 사용자 행동 예측
  • 고객 서비스 QA 성능 향상 (유사 과거 이슈 그래프 검색)

9.2.2. Biomedical

 

• 질병–증상–약물 관계를 그래프로 구조화
• 의료 QA 및 의사결정 지원에 활용
• 특징:
  • 비모수 검색 → 재정렬(re-ranking)
  • 검색 결과를 활용한 입력 재작성으로 생성 성능 향상
  • 오픈소스 KG(CMeKG, PubMed 기반 KG 등) 활용

9.2.3. Academic

• 논문, 저자, 기관, 연구 분야 간 관계를 그래프로 구성
• 활용:
  • 잠재적 공동 연구자 추천
  • 연구 분야 트렌드 분석

9.2.4. Literature

 

• 책, 저자, 출판사, 시리즈 간 관계 그래프
• 활용:
  • 스마트 도서관
  • 문학 정보 탐색 및 추천

9.2.5. Legal

• 판례 및 법원 문서 간 인용 관계가 자연스럽게 그래프 형성
• 활용:
  • 판례 분석
  • 법률 상담 및 리서치 지원

9.2.6. Others

정보 분석 및 이해가 중요한 다양한 분야에 적용

• 정보 보고서 생성
• 특허 문구 유사도 판단
• 소프트웨어 의존성 분석 및 QA

 

9.3. Benchmarks and Metrics

9.3.1. Benchmarks

GraphRAG 성능 평가는 두 가지 유형의 벤치마크로 나뉜다.

(1) 다운스트림 태스크 기반 벤치마크

기존 태스크(KBQA, CSQA 등)에 사용되는 데이터셋 활용
GraphRAG가 실제 문제 해결 성능을 얼마나 개선하는지 평가

 

 

(2) GraphRAG 전용 벤치마크

여러 도메인을 포괄해 종합적인 GraphRAG 성능 평가 목적

대표 사례:
- STARK: 반정형 지식 기반 LLM Retrieval 평가
(상품 검색, 학술 검색, 정밀 의료)

- GraphQA: 실제 텍스트 그래프 대상 QA 벤치마크
(장면 그래프, 상식 추론, KG 추론)

- GRBENCH: 10개 도메인 그래프 기반 1,740개 질의
→ LLM + Graph 결합 추론 평가

- CRAG: 구조화 질의 + mock KG API 제공
→ 공정한 GraphRAG 비교 가능

 

9.3.2. Metrics

 

GraphRAG 평가는 생성 품질과 검색 품질 두 축으로 이루어진다.

(1) 다운스트림 태스크 평가 (Generation Quality)

주요 평가 기준:
- KBQA: Exact Match (EM), F1
- CSQA: Accuracy

의미적 동등성 보완:
- BERTScore, GPT4Score 활용 (정답과 의미는 같지만 표기가 다른 경우 보정)

생성형 태스크:
- BLEU, ROUGE-L, METEOR 등 텍스트 생성 품질 지표 사용

(2) 검색 품질 평가 (Retrieval Quality)

검색 결과를 직접 평가하기 어렵기 때문에 간접 지표 활용

주요 지표:

- Answer Coverage / Subgraph Size 비율: 적은 그래프로 얼마나 많은 정답을 포함하는지
- Query Relevance: 질의와 검색 결과의 관련성
- Diversity: 검색된 정보의 다양성
- Faithfulness: 검색 정보의 신뢰도 및 정확성

 

 

 

9.4. GraphRAG in Industry

산업용 GraphRAG 시스템 요약

산업용 GraphRAG 시스템은 산업용 그래프 DB를 기반으로 하거나 대규모 그래프 데이터 처리에 초점을 둔 것이 특징이다.

1. Microsoft GraphRAG

- LLM으로 엔티티 기반 지식 그래프 자동 구축
- 엔티티 커뮤니티 단위 사전 요약(community summary) 생성
- 문서 전체의 로컬·글로벌 관계를 동시에 포착
- Query-Focused Summarization(QFS) 성능 향상
- LlamaIndex, LangChain 등 오픈소스 RAG 툴킷과 연동 가능

2. NebulaGraph GraphRAG

- 최초의 산업용 GraphRAG 시스템
- NebulaGraph DB에 LLM을 직접 통합
- 목표: 정확하고 지능적인 대규모 그래프 검색

3. Ant Group GraphRAG

- DB-GPT, OpenSPG, TuGraph 기반의 종합 프레임워크
- 파이프라인:
  1. LLM으로 문서에서 트리플 추출
  2. 그래프 DB에 저장
  3. 질의에서 키워드 추출 후 관련 노드 탐색
  4. BFS/DFS로 서브그래프 검색
  5. 서브그래프를 텍스트화하여 LLM 생성에 활용
- 전형적인 end-to-end GraphRAG 구조

4. NaLLM (Neo4j)

- Neo4j 그래프 DB + LLM 통합 프레임워크
- 주요 활용 사례:
  - 자연어 → 지식 그래프 질의 인터페이스
  - 비정형 데이터로부터 KG 생성
  - 그래프 데이터 + LLM 기반 리포트 생성

5. LLM Graph Builder (Neo4j)

- GraphRAG의 그래프 구축·인덱싱 단계에 특화
- LLM으로 비정형 데이터에서
  - 노드
  - 관계
  - 속성 자동 추출
- LangChain 기반으로 구조화된 KG 자동 생성

 

 

 

 

여담:

 

9. Applications and Evaluation은 ChatGPT로 정리해봤는데 개조식으로 잘 정리해준다. 

 

LLM에게 정리를 시키면 편할테지만, 직접 번역 그게 아니라면 최소한 구그 번역이나 LLM 번역을 자기식으로 리프레이징해서 다시 적어야 머리에 남는것 같다.  

 

 

 

References:

https://meaningful96.github.io/gr/IDGNN/

https://groups.google.com/g/gremlin-users/c/5-ui5yKjdxg?pli=1

http://www.analytictech.com/networks/egonet.htm

https://faculty.ucr.edu/~hanneman/nettext/C9_Ego_networks.html