Costas Mavromatis / Univiersity of Minnesota
George Karypis / University of Minnesota
LLM의 한계 :
지식 그래프(KnowledgeGraph, KG)의 역할
다중홉(multi-hop)관계는 하나의 엔티티가 여러 개의 다른 엔티티와 연결되어 있는 경우
여러 개의 관계(relation)를 거쳐야만 정답에 도달할 수 있는 질의응답 방식
📌 1-Hop (단일 홉) 질의 예시:
질문: "자메이카에서 사용되는 언어는?"
지식 그래프 정보: <Jamaica → language_spoken → English>정답: "English"
✔ 단일 관계(1-hop)만 거치면 답을 찾을 수 있음.
📌 Multi-Hop (다중 홉) 질의 예시:
질문: "자메이카에서 사용되는 언어를 공용어로 지정한 군주는 누구인가?"
필요한 지식 그래프 정보:
1. <Jamaica → language_spoken → English> 2. <Jamaica → governed_by → Queen Elizabeth II>정답: "Queen Elizabeth II"
✔ 두 개 이상의 관계(2-hop 이상)를 거쳐야 답을 찾을 수 있음.
RAG는 LLM이 신뢰할 수 있는 외부지식을 검색 후 활용하여 Hallucination 문제를 완화하는 방법이다. 하지만 RAG 성능은 검색된 KG 정보의 품질에 의해 결정된다.
GNN-RAG는 LLM의 자연어 이해력과 GNN의 그래프 처리 능력을 결합하여 기존 RAG의 한계를 극복하는 방식이다.

KGQA(지식 그래프 질의 응답)은 크게 Sementic Parsing(SP) 와 Information Retrieval(IR) 방법 두가지 방법으로 분류된다.
Semantic Parsing(SP) 방법
주어진 질문을 SPARQL 쿼리 또는 논리적 질의 (logical from query)로 변환 후, KG에서 실행하여 정답을 추출하는 방식
단점 :
Information Retrieval(IR) 방법
약한 지도 학습(Weakly Supervised Learning) 기반 KGQA 방법
학습시 정확한 논리적 질의가 필요하지 않으며 질문-정답 쌍(question-answer pairs)을 활용하여 학습 가능
주어진 질문을 기반으로 KG에서 관련 subGraph를 검색한 후 이를 입력으로 사용
단점 :
따라서, 논문에서는 GNN-RAG가 SP와 IR 방식의 장점을 결합하여 보다 효율적인 KGQA를 수행하도록 제안.
GNN을 활용한 잠재적 그래프 정보 추가 방법 (Latent Graph-Augmented LMs)
GNN을 활용하여 KG에서 잠재적(latent) 그래프 정보를 추출한 후, 이를 LLM의 내부 지식으로 보강하는 방식.
단점 :
그래프 정보를 자연어로 변환하여 입력에 추가하는 방법 (Verbalized Graph-Augmented LMs)
- 그래프에서 추출된 정보를 자연어 형태로 변환한 후, 이를 LLM 입력으로 제공하는 방식
- 예: "Knowledge: Jamaica → language_spoken → English" 를 LLM의 컨텍스트에 포함
- 단점:
- 대규모 그래프에서는 불필요한 정보(Noise)가 포함될 가능성
- LLM의 추론 과정에 방해가 될 수 있음
GNN-RAG는 두 가지 방법의 단점을 보완하기 위해 GNN을 정보 검색 단계에 활용하고, LLM이 RAG 방식으로 KGQA를 수행하도록 설계됨.
<Jamaica → language_spoken → English>검색과 추론의 두 단계로 나눠서 작업을 진행
검색 (Retrieval)
추론(Reasoning) : GNN + LLM

"Which language do Jamaican people speak?"라는 질문에 대해, LLM은 <official_language>, <language_spoken> 관계를 찾아낼 수 있습니다.| 방법 | 검색 방식 | 추론 방식 | 강점 | 약점 |
|---|---|---|---|---|
| GNN-based KGQA | GNN이 서브그래프 검색 | GNN이 답 생성 | 다중 홉 질의에 강함 | 자연어 이해가 부족 |
| ToG (LLM-based KGQA) | LLM이 관계를 하나씩 검색 | LLM이 답 생성 | 자연어 이해가 뛰어남 | KG 구조 활용이 부족 |
| RoG (LLM-based KGQA) | LLM이 관계 경로를 예측하여 검색 | LLM이 답 생성 | 유연한 검색 가능 | 환각(Hallucination) 문제 발생 가능 |
| GNN-RAG (논문 기법) | GNN이 검색, LLM이 답 생성 | LLM이 RAG로 최적화 | GNN과 LLM의 장점 결합 | - |
GNN-RAG는 LLM의 자연어 인해 능력과 GNN의 논리적 추론 능력을 결합한 새로운 RAG 방식이다.
GNN이 KG(지식 그래프)에서 관련 정보를 검색하고, LLM이 이를 활용해 답을 생성한다.
-> GNN은 KG 구조적 정보를 활용하고, LLM은 자연어 이해와 답변 생성을 담당하는 방식

Figure 3. 해당 그림은 GNN-RAG방식을 시각적으로 설명한것.
Retrieval Augmentation(RA, 검색 강화) 단계 - 1번과 동시에 검색이 이루어짐짐
GNN이 놓칠수 잇는 추가적인 정보를 보완하기 위해 LLM기반 검색을 함께 사용.
LLM이 "Generate helpful relation paths" 라는 프롬프트를 통해 추가적인 관계 경로를 생성.
이 과정에서 GNN과 LLM이 찾은 관계 경로를 Union(결합)하여 최적의 reasoning paths를 도출한다.
Reasoning(추론) 단계 :
Jamaica → official_language → English
Jamaica → language_spoken → Jamaican English
Jamaica → close_to → Haiti → official_language → French
Jamaica → located_in → Caribbean SeaLLM을 통한 최종 답변 생성(Textualize + RAG)
GNN은 복잡한 그래프 정보를 분석하여 multi-hop 질의 에서도 정확한 정보를 검색 할 수 있다는 강점이 잇다.
다른 KGQA 방법(embedding기반 방법) 보다 다양한 경로를 탐색하여 정답을 찾을 확률이 놓다.
GNN이 하는 일
따라서, GNN은 KG에서 정확한 정보를 검색하는 역할을 한다.
GNN-RAG 에서 GNN이 생성한 reasoning paths를 LLM에게 전달하여 답변을 생성
LLM이 사용하는 입력 프롬프트 예시 :
prompt = f"""
Based on the reasoning paths, please answer the given question.
Reasoning Paths : {reasoning_paths}
Question : {question}
"""
Reasoning paths 예시 :
Jamaica → offical_language → English
Jamaica → language_spoken → Jamaican English
GNN이 생성한 reasoning paths를 LLM이 해석하고, 이를 바탕으로 최종 답변을 생성하는 방식이다.
GNN과 LLM기반 검색(RoG)을 비교하여 어떤 방식이 더 효과적인지 분석
GNN은 다중 홉 질문에 강하지만, 단순한 질문 (1-hop)에서는 성능이 떨어질 수 있음.

실험 결과:
결론: GNN은 복잡한 질문에서는 우수하지만, 단순한 질문에서는 LLM 기반 검색이 더 효과적일 수 있음
GNN과 LLM 기반 검색을 결합하여 더 나은 성능을 내는 방법.
GNN이 다중 홉 검색을 담당하고, LLM(RoG)이 단순한 질문에 대한 검색을 보완하도록 설계
실험에서 GNN-RAG + RA 방식이 가장 높은 성능을 보임
결과적으로 GNN과 LLM의 장점을 모두 활용하는 최적의 검색방식이라고 할수 있다.
서브 그래프 검색 방식
사용된 GNN 및 LM 조합
LLM 기반 RAG 최적화
성능평가지표 (Evaluation Metrics)
Hit : 생성된 답변 중 정답이 포함되었는지 여부 측정 (LLM평가 시 사용)
H@1 (Hits@1): 첫번재 예측 답변이 정답인지 측정하는 Accuracy 평가.,
F1-score :
- 정답을 얼마나 많이 찾았는지(Recall)와 불필요한 답을 얼마나 줄였는지 (precision)를 모두 반영하는 점수
- LLM 및 KGQA 시스템의 성능을 종합적으로 평가하는 데 사용

Table 2. KGQA 벤치마크 성능비교 (Performance Comparison on WebQSP & CWQ)
GNN-RAG + RA 가 WebQSP와 CWQ 모두에서 최고 성능을 기록
GNN-RAG는 기존의 LLM 기반 검색 방식보다 높은 F1-score를 달성
특히 WebQSP에서는 RoG보다 3.5% 높은 F1-score를 기록

Table 3: Multi-Hop & Multi-Entity 질문 성능 분석
- Multi-hop : 정답을 찾기위해 여러개의 관계(Edge)를 거쳐야하는 질문
- Multi-Entity : 하나의 질문에 대해 여러 개의 정답 엔터티가 포함되는 질문
Table 2에서 다양한 KGQA 방법들의 성능 비교
GNN-RAG가 전반적으로 가장 높은 성능 기록 -> 최신 (SOTA) 결과 달성
GNN을 활용한 검색이 LLM기반 검색보다 추론 능력을 크게 향상시킴 (GNN+LLM vs KG+LLM)
GNN-RAG + RA vs. 기존 방법성능 비교
ToG+ChatGPT 대비 최대 14.5% 높은 Hit 성능
최고 성능을 기록한 GNN 대비 Hits@1에서 5.39.5%, F1에서 0.710.7% 성능 향상
GNN-RAG는 복잡한 그래프 검색이 중요한 KGQA에서 매우 효과적
LLM의 추론 능력을 GNN을 통해 보완하면 성능이 대폭 향상됨

다양한 검색 증강 기법을 비교.
주요 결론 :
다양한 LLM(ChatGPT, Alpaca-7B, LLaMA2-Chat 등)을 활용한 검색 성능 비교
평가지표 : Hit(%)

GNN-RAG는 다양한 LLM과 결합할 수 있으며, 추가 훈련 없이 KGQA 성능을 향상 가능
Figure 4. GNN-RAG가 LLM의 신뢰성(Faithfulness)을 어떻게 향상시키는지 보여주는 사례
GNN-RAG vs. KG-RAG :
질문 1: "In which state did fictional character Gilfoyle live?"
질문 2: "Who was the real Erin Brockovich featured in Michael Renault Mageau movie?"
결론 : GNN-RAG는 더 깊은 reasoning paths를 활용하여 LLM이 정확한 정보를 사용하도록 도와줌
Figure 5. 검색 증강(RA)이 GNN-RAG 성능을 개선하는 사례
질문: "Who made the laws in Canada?"
결론: RA를 사용하면 GNN이 놓칠 수 있는 의미적으로 중요한 KG 정보를 LLM이 보완할 수 있음
논문에서는 GNN-RAG를 KGQA(Knowledge Graph Question Answering)를 위한 새로운 RAG 방식으로 제안했으며, 주요기여는 다음과 같다.