부분 그래프를 골라 답하기

핵심 개념

그래프 전체를 텍스트로 바꿔 LLM에 넣으면 컨텍스트가 넘치고, 점수가 높은 노드만 골라 넣으면 서로 끊긴 사실 조각이 들어가 LLM이 관계를 잘못 이을 수 있습니다. 그래서 질문에 맞는 작은 부분 그래프를 고르는 방법이 연구되었습니다. G-Retriever(He et al. 2024)는 노드·엣지에 텍스트가 붙은 그래프(textual graph)에 대화식으로 질문하는 문제를 다루며, 상식 추론·장면 그래프·KG 질의응답 데이터셋(ExplaGraphs, SceneGraphs, WebQSP)을 묶은 GraphQA 벤치마크를 제안했습니다.

G-Retriever는 질문과 코사인 유사도가 높은 상위 k개 노드에 k, k−1, …, 1의 상(prize)을 주고 나머지는 0으로 둡니다(엣지도 같은 방식). 그리고 상금 수집 슈타이너 트리(Prize-Collecting Steiner Tree, PCST) 문제로, 연결된 부분 그래프 가운데 ‘노드 상 + 엣지 상 − 엣지 수 × 엣지 비용 Ce’가 가장 큰 것을 고릅니다. Ce를 키우면 작은 그래프가 됩니다. 고른 부분 그래프는 GNN으로 인코딩해 소프트 프롬프트로 넣고, 동시에 텍스트로 풀어 질문과 함께 LLM에 넣습니다. 논문은 이 검색이 환각을 줄이고 큰 그래프로 확장된다고 주장합니다.

Think-on-Graph(ToG, Sun et al. 2024)는 LLM을 KG 위의 에이전트로 씁니다(LLM ⊗ KG). 질문의 주제 엔티티에서 시작해 관계 탐색(후보 관계를 찾고 LLM이 상위 N개로 가지치기)과 엔티티 탐색(후보 엔티티를 찾고 가지치기)을 반복하며 상위 N개 경로를 유지하는 빔 탐색을 합니다. 단계마다 LLM이 현재 경로로 답할 수 있는지 판단하고, 아니면 최대 깊이 D까지 계속합니다. 최대 LLM 호출 수는 2ND + D + 1로, N=3·D=3이면 22회입니다. 남은 경로가 근거가 되므로 추적과 수정이 가능합니다.

두 방법은 비용을 쓰는 곳이 다릅니다. G-Retriever는 한 번에 부분 그래프를 고르지만 그래프 인코더와 투영층을 학습해야 하고, ToG는 학습 없이 여러 번 LLM을 호출합니다. 둘 다 KG에 없는 사실은 찾지 못합니다. ToG는 최대 깊이까지 답을 찾지 못하면 LLM 내부 지식만으로 답한다고 논문이 밝히므로, 그런 답에는 그래프 근거가 없다는 표시가 필요합니다.

작은 예제로 따라가기

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.