[논문리뷰]Explore then Determine: A GNN-LLM Synergy Framework for Reasoning over Knowledge Graph

Guangyi Liu, Yongqi Zhang, Yong Li, and Quanming Yao. 2024. Explore then determine: A gnn-llm synergy framework for reasoning over knowledge graph.

Problem Statement

Limitations of Prior Studies

1. 대형 언어 모델(LLM)의 지식 부족: LLM은 자연어 처리에서 강력한 성능을 보이지만, KGQA 작업에서는 사실적 지식의 부족과 환각 문제로 인해 어려움을 겪고 있다. 기존의 LLM 기반 추론 방법들은 질문과 관련된 정확한 지식을 추출하는 데 중요한 지식 그래프(Knowledge Graph, KG)에서의 구성적 학습(compositional learning)을 간과하고 있다는 점이 문제로 지적되고 있다.

2. 비효율성과 높은 비용: 현재의 많은 KGQA 방법들은 LLM의 미세 조정이나 빈번한 상호작용을 필요로 하는데, 이는 특히 대규모 지식 그래프에서 다중 단계 추론을 수행할 때 시간과 자원이 많이 소요되어 비효율적이다.

Method

Model Overview

Knowledege Graph(KG)는 헤드 엔티티(= head entity), 릴레이션(= 릴레이션), 테일 엔티티(= tail entity)로 이루어진 트리플을 지식의 기본 단위로 저장하고 있다. 헤드, 릴레이션, 테일은 각각 주체(= subject), 술어(= predicate), 객체(= object)라고도 불린다.

• Notation
  • 트리플(Triple): {\((e_s, r, e_o)\)}
  • Knowledge Graph: \(\mathcal{G} = \{(e_s, r, e_o) \mid e_s, e_o \in V, r \in R \}\)
  • 엔티티 집합: \(V\)
  • 릴레이션 집합: \(R\)
  • 질문: \(q\)

KGQA 문제는 질문 \(q\)와 그래프 \(\mathcal{G}\)가 주어졌을 때, 답변 엔티티 \(e_a \in V\)를 KG에서 찾아내는 것이다. 이를 함수로 \(F(q, G)\)와 같이 표현할 수 있다. KGQA는 질문과 관련된 구성적 지식(Compositional Knowledge)을 KG에서 정확하게 탐색해야 하며, 질문과 KG 내 엔티티 간의 텍스트 이해 및 매칭 능력을 요구하는 어려운 작업이다. 그리고 LLM은 여전히 멀티 홉 추론을 함에 있어서 유망한 후보를 제대로 추출하지 못한다.

Figure 1. Explore-then-Determine(EtD) Framework

본 논문에서는 인간이 어려운 과제를 마주할 때 여러 가능한 대안을 식별한 후 최적의 선택을 하는 방식에서 영감을 받아, 멀티 홉 추론을 위한 Explore-then-Determine(EtD) 프레임워크를 제안한다. LLM에 유망한 후보와 세부 지식을 제공하기 위한 탐색 모듈을 채택하고, LLM이 최종 답변을 생성하도록 안내하는 결정 모듈을 사용한다.

Figure 1은 EtD 프레임워크를 나타내며, 그림에서와 같이 두 가지 구성 요소로 이루어져 있다. 각각 (1)의미를 인식하고 유망한 후보 엔티티를 추출하는 그래프 탐색(Explore); (2)LLM을 통해 후보들을 활용해 답변 결정(Determine)이다. 첫 번째 부분에서는 그래프에서 질문과 관련된 구성적 지식을 정확하게 파악하기 위해, LLM이 강화된 GNN 모듈을 설계하여 주어진 질문과 관련된 후보와 관련 지식을 KG에서 탐색한다. 즉, (\(\mathcal{C_q}, \mathcal{K_q}\)) = \(f_{exp}(q, \mathcal{G})\)이다. 두 번째 부분에서는 첫 번째 단계에서 탐색된 정보를 효과적으로 활용하기 위해, 지식이 강화된 다중 선택 프롬프트를 신중하게 설계하여, LLM이 KG의 명시적 지식과 LLM 내부의 암묵적 지식을 바탕으로 최종 답변을 결정하도록 안내한다, 즉, \(e_a = g_{det}(q, \mathcal{C_q}, \mathcal{K_q})\)이다.

Semantic-Aware Graph Exploration

Figure 2. Semantic-Aware Graph Exploration의 진행 과정

Semantic-Aware Graph Exploration은 주어진 질문에 대해 지식 그래프(KG)에서 의미적으로 관련 있는 후보 엔티티와 세부 지식을 탐색하기 위해 설계된 과정이다. 이 과정은 크게 두 가지 주요 단계, Semantic-aware pruning과 GNN encoding through propagation으로 나누어진다.

1) Semantic-Aware Pruning

Semantic-aware pruning 단계에서는 주어진 질문 \(q\)에 대해 지식 그래프 \(\mathcal{G}\)에서 의미적으로 관련이 있는 후보 엔티티를 선택하고, 불필요한 정보를 걸러내는 과정을 수행한다. 이 과정은 다음과 같은 절차로 이루어진다.

1. 초기화
질문 \(q\)와 관련된 토픽 엔티티 \(e_q\)를 초기 후보 집합 \(\mathcal{C_0}^q\)로 설정한다. 토픽 엔티티 \(e_q\)의 초기 임베딩 표현(representation) \(h_{e_q}^0\)은 질문 \(q\)의 임베딩 \(h_q\)로 초기화된다. 이 질문의 임베딩 표현은 사전학습된 LLM 의 출력 임베딩을 사용하며, 논문에서는 Llama2-13B를 사용하였다.

$$h_{e_q}^0 = h_q = W_L \cdot \text{LLM}(q)$$

위의 수식이 질문 임베딩, 토픽 엔티티의 초기 표현값을 나타내며, \(W_L\)은 학습 가능한 가중치 행렬이다.

2. 후보 집합 확장 및 중요도 계산
다음으로, \(\ell\) 번째 단계에서 현재 후보 집합 \(C_{\ell-1}^q\)을 사용하여 후보 엔티티 집합을 확장한다.

$$C_{\ell}^q = \{e_o : (e_s, r, e_o) \in G, e_s \in C_{\ell-1}^q \}$$

여기서 \(e_s\)는 현재 후보 엔티티, \(e_o\)는 새로운 후보 엔티티, 그리고 \(r\)는 두 엔티티 사이의 릴레이션이다. 각 후보 엔티티 간의 엣지에 대해 중요도 \(\alpha_{\ell}^{q \vert sr}\)를 계산한다:

$$\alpha_{\ell}^{q \vert sr} = \sigma \left( W_{\ell}^{(s)} h_{s}^{\ell-1} + W_{\ell}^{(r)} h_r + W_{\ell}^{(q)} h_q + W_{\ell}^{(qr)} (h_r \odot h_q) \right)$$

여기서 \(\sigma\)는 시그모이드(Sigmoid) 함수, \((W_{\ell}\)은 학습 가능한 가중치 행렬들, \(h_r\)는 릴레이션 \(r\)의 표현, \(\odot\)는 하다마드 곱(Hadamard product)이다. 하다마드 곱은 Element-wise product이다. 중요도 기반 필터링 단계에서는 각 엣지의 중요도 \(\alpha_{\ell}^{q \vert sr}\)를 바탕으로, 중요도가 높은 상위 K개의 엣지를 남기고 나머지는 필터링하여 새로운 후보 집합 \(\tilde{C}_{\ell}^q\)을 만든다. 이 과정은 관련성이 낮은 엔티티와 릴레이션을 제거하여 후보 엔티티 수의 폭발적 증가를 방지한다.

2) GNN encoding through propagation

Semantic-aware pruning에서 필터링된 후보 엔티티들을 바탕으로, GNN을 사용하여 각 엔티티의 표현을 학습하고, 질문과 관련된 의미적 정보를 그래프 구조를 통해 전파(propagation)하는 과정이다.

1. 후보 엔티티 표현 업데이트
GNN을 사용하여 현재 후보 엔티티 \(\tilde{C_{\ell}}^q\)에서 이전 단계의 후보 엔티티 \(\tilde{C}_{\ell-1}^q\)로부터 정보를 전파한다.

$$h_{o}^{\ell} = \delta \left( \sum_{(e_s, r, e_o) \in \tilde{N}_{e_o}^{\ell}} \alpha_{\ell}^{q|sr} W_{\ell} \left( h_{s}^{\ell-1} \odot h_r \right) \right)$$

여기서 \(\delta\)는 활성화 함수, \(\tilde{N}_{e_o}^{\ell}\)는 \(e_o\)의 남아있는 이웃 엣지 집합, \(h_{s}^{\ell-1}\)은 이전 단계에서의 후보 엔티티 \(e_s\)의 표현이다. L번의 전파 과정을 거친 후, 최종 후보 집합 \(C_q = \tilde{C}_0^q \cup \tilde{C}_1^q \cup \ldots \cup \tilde{C}_L^q\)과 각 엔티티의 최종 표현 \(h_e^L\)을 얻는다.

Semantic-Aware Graph Exploration은 주어진 질문에 대해 지식 그래프에서 의미적으로 관련 있는 후보 엔티티와 세부 지식을 탐색하고, 이를 통해 효율적이고 신뢰할 수 있는 질의응답을 가능하게 하는 과정이다. 이 과정은 의미적 관련성을 바탕으로 후보 엔티티와 관계를 필터링하는 Semantic-aware pruning과, 필터링된 엔티티 간의 정보를 전파하여 의미적 표현을 학습하는 GNN encoding through propagation을 결합하여, 최종적으로 가장 유망한 후보와 그와 관련된 세부 지식을 도출하는 역할을 한다.

Knowledge-Enhanced Answer Determination

Knowledge-Enhanced Answer Determination 단계에서는 탐색 단계에서 획득한 후보 엔티티와 관련 지식을 활용하여, LLM이 최종 답을 결정할 수 있도록 돕는다. 이 과정은 주어진 후보들 간의 비교를 통해 최적의 답변을 선택하는 데 중점을 둔다. 이를 위해 지식이 강화된 다중 선택 프롬프트를 설계하여, LLM이 보다 정확하고 신뢰할 수 있는 답변을 생성하도록 유도한다.

1. Multiple-choice prompt 설계
이 단계에서는 탐색 단계에서 얻은 후보 엔티티 집합 \(\mathcal{C_q}\)를 기반으로 LLM을 위한 다중 선택 형식의 프롬프트를 구성한다. 프롬프트는 다음과 같은 요소들로 구성된다.

• 문제 설명(Task Description): 질문에 대한 설명과 기대되는 출력 형식을 명시한다.
• 질문(Question): 주어진 질문 \(q\)을 그대로 포함한다.
• 참조 답변(Reference Answers): 탐색 단계에서 가장 높은 확률을 얻은 상위 \(N\)개의 후보 엔티티를 참조 답변으로 제공한다. 각 참조 답변에는 해당 후보의 올바른 확률과 함께 탐색된 관련 경로(세부 지식)가 포함된다.

[프롬프트 예시]

<Task Description>
<Question>  
<Reference Answers>:
A. 후보 1 (올바른 확률) {증거 체인} 
B. 후보 2 (올바른 확률) {증거 체인} 
...

2. 증거 추출 (Evidence Extraction)
LM이 보다 신뢰할 수 있는 답변을 생성할 수 있도록, 각 참조 답변에 대한 증거 체인을 제공한다. 증거 체인은 후보 엔티티가 주제 엔티티와 어떻게 연결되는지를 설명하는 경로를 의미한다. 이를 추출하기 위해 그리디 알고리즘을 사용하여, 각 후보 답변에서 시작하여 역방향으로 탐색하여 초기 주제 엔티티 \(e_q\)까지의 경로를 추적한다.

• 예시
  • 질문: “Birdy의 작가가 작성한 영화가 언제 개봉되었나요?”
  • Evidence Chain
    • (Birdy, written_by, William Wharton) -> (Dad, written_by, William Wharton) -> (Dad, release_year, 1989)

Training Strategy

EtD는 LLM을 튜닝하지 않곡 비용을 줄이기 위해, LLM 자체는 훈련시키지 않고 대신 탐색 모듈과 결정 모듈만 학습한다.

1. 탐색 모듈의 학습
탐색 모듈은 GNN과 MLP로 구성되어 있으며, 주어진 질문-답변 쌍을 사용하여 지도 학습된다. 이때의 손실 함수는 Cross-Entropy 손실로 정의된다.

$$L = \displaystyle\sum_{(q, e_a) \in F_{tra}} -\log (p(q, e_a))$$

위 손실함수 식에서 \(F_{tra}\)는 training set, \(p(q, e_a)\)는 질문 \(q\)에 대한 정답 엔티티 \(e_a\)의 확률이다.

2. LLM을 frozen하고 결정 모듈을 활용
논문에서는 LLM을 frozen하여, 추가적인 훈련 없이 결정 모듈에서 활용한다. 이는 시간과 자원의 비용을 줄이기 위한 것으로, 결정 모듈이 탐색 모듈에서 추출된 정보와 LLM의 내재된 지식을 결합하여 최종 답변을 도출한다. 이 방법은 기존 LLM의 성능을 유지하면서도, 효율적인 질의응답 시스템을 구성할 수 있도록 한다.

Experiments

Main Result

실험에서는 WebQSP, CWQ, MetaQA 데이터셋이 사용되었다. 위의 표는 성능 비교를 위한 main result를 보여준다. EtD는 SOTA를 달성하였으며 특히 frozen LLM으로 ChatGPT를 사용했을때 매우 높은 성능을 보여주었다. RoG-ChatGPT와 비교했을때, 특히 CWQ에서 높은 성능을 보여주었다. 하지만 추론시에만 LLM을 사용하므로 LLM을 어떤 걸로 사용하느냐에 따라 성능 차이가 심하다. Llama2-13B를 사용했을대 WebQSP와 CWQ에서 성능 차이가 많이 난다.

Extra Experiment

Table 3. 추론 시간 비교
Table 3에서는 RoG, StructGPT, ToG, 그리고 EtD 방법들이 각 질문에 대해 LLM(Llama2-13B)과 상호작용하는 횟수와 추론 시간(inference time)을 비교하고 있다. 실험 결과, EtD 방법은 가장 적은 상호작용 횟수(1회)와 가장 짧은 추론 시간(1.29초/1.99초)을 기록하여, 다른 방법들보다 효율적으로 작동함을 보여준다. 반면, ToG 방법은 가장 많은 상호작용(15회/22회)과 가장 긴 추론 시간(16.7초/20.5초)을 보여주어 상대적으로 비효율적이다. 이 결과는 EtD 방법이 계산 비용 측면에서 매우 효율적임을 나타낸다.

Table 4. Ablation Study1: Llama2-13B에서 서로 다른 varients에 따른 성능 비교
Table 4에서는 EtD 방법의 다양한 변형들이 WebQSP와 CWQ 데이터셋에서 정확도(Hits@1)를 비교하고 있다. 표에 따르면, 기본 EtD 방법이 WebQSP와 CWQ 데이터셋에서 각각 77.4%와 57.7%의 정확도를 기록하며 가장 높은 성능을 보여준다. 반면, 여러 구성 요소를 제거한 변형들(예: w.o.-mcp, w.o.-cand, w.o.-prob, w.o.-path)은 성능이 감소하였다. 특히, w.o.-mcp와 w.o.-prob 변형은 정확도가 크게 떨어져, 다중 선택 프롬프트(mcp)와 올바른 확률(prob)의 제공이 LLM의 최종 답변 결정에 중요한 역할을 한다는 것을 시사한다.

• w.o.-mcp (without multi-choice prompt)
  • 다중 선택 프롬프트를 제외한 변형이다. 이 구성 요소는 탐색된 후보 엔티티들에 대한 다중 선택 형식의 프롬프트를 제공하여 LLM이 최종 답변을 결정하는 데 도움을 준다. 이 프롬프트가 제거되면, LLM은 후보 엔티티들 간의 비교나 선택을 할 수 없게 되며, 그 결과 성능이 감소할 수 있다.
• w.o.-cand (without candidate filtering)
  • 후보 필터링을 제외한 변형이다. 이 구성 요소는 탐색 단계에서 의미적으로 관련성이 낮은 후보 엔티티들을 필터링하여, LLM이 보다 적절한 후보들만을 고려할 수 있도록 한다. 이 필터링이 제거되면, LLM은 관련성이 낮은 후보들도 고려하게 되어 성능이 저하될 수 있다.
• w.o.-prob (without probability-based ranking)
  • 확률 기반 랭킹을 제외한 변형이다. 이 구성 요소는 후보 엔티티들 사이에서 최종 답변을 결정할 때, 각 후보의 신뢰도를 확률로 평가하여 랭킹을 매긴다. 이 랭킹이 제거되면, LLM은 후보들 간의 확률적 차이를 고려하지 않고 답변을 선택하게 되어 정확도가 떨어질 수 있다.
• w.o.-path (without path backtracking)
  • 경로 추적을 제외한 변형이다. 이 구성 요소는 후보 엔티티와 주제 엔티티 사이의 경로를 추적하여 LLM에 증거 체인을 제공한다. 이 과정이 제거되면, LLM은 후보 엔티티의 신뢰성을 판단할 수 있는 중요한 맥락 정보를 잃게 되어 성능이 저하될 수 있다.

Table 5. Ablation Study2: EtD의 서로 다른 varients에 따른 성능 비교
Table 5에서는 UniKGQA, EtD-w.o.-AD, EtD-Llama2-13B, EtD-ChatGPT 방법들이 다양한 데이터셋에서 기록한 정확도(Hits@1)를 비교하고 있다. 표에 따르면, EtD 방법들은 UniKGQA보다 전반적으로 높은 정확도를 기록하고 있으며, 특히 EtD-ChatGPT가 모든 데이터셋에서 가장 높은 성능을 보이고 있다. EtD-w.o.-AD는 LLM을 사용하지 않고 GNN만으로 탐색한 결과(GNN으로 탐색을 통한 후보 엔티티 추출뿐만 아니라, 정답 엔티티까지 찾음음)를 보여주는데, 이는 LLM을 활용한 결정 단계가 성능을 크게 향상시킴을 나타낸다. EtD-Llama2-13B와 EtD-ChatGPT는 각각 Llama2와 ChatGPT를 활용한 버전으로, LLM의 성능에 따라 결과가 달라짐을 알 수 있다. ChatGPT를 사용한 버전이 더 높은 정확도를 기록하여, LLM의 선택이 성능에 중요한 영향을 미친다는 것을 알 수 있다.

Limitations and Contributions

• Limitations
  • Frozen LLM을 사용하기 때문에 backbone에 따른 성능 차이가 발생.
  • RoG의 후속 모델인 GNN-RAG에 비해 Llama2에서 성능이 밀림.
  • Candidate Filtering이 과연 GNN을 사용하는 것이 좋은지 의문이다.
• Contribution
  • LLM과 GNN의 시너지 활용.
  • GNN을 활용한 탐색 단계와 동결된 LLM을 사용한 결정 단계를 도입하여, 효율적이고 계산 비용이 적은 질의응답 시스템을 구현함.
  • 탐색 단계에서 수집된 지식을 활용하여 지식이 강화된 다중 선택 프롬프트를 설계하고, 이를 통해 LLM이 최적의 답변을 생성함.

NR 카테고리 내 다른 글 보러가기