Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs

Large language models (LLMs), while exhibiting exceptional performance, suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora to alleviate the issue. However, in many domains, texts are interconnected (e.g., academic papers in a bibliographic graph are linked by citations and co-authorships) which form a (text-attributed) graph. The knowledge in such graphs is encoded not only in single texts/nodes but also in their associated connections. To facilitate the research of augmenting LLMs with graphs, we manually construct a Graph Reasoning Benchmark dataset called GRBench, containing 1,740 questions that can be answered with the knowledge from 10 domain graphs. Then, we propose a simple and effective framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively. Each Graph-CoT iteration consists of three sub-steps: LLM reasoning, LLM-graph interaction, and graph execution. We conduct systematic experiments with three LLM backbones on GRBench, where Graph-CoT outperforms the baselines consistently. The code is available at https://github.com/PeterGriffinJin/Graph-CoT.

한 줄 요약

Graph-CoT는 그래프 정보를 활용해 대형 언어 모델의 추론을 반복적으로 수행함으로써 환상 생성을 줄이고 성능을 향상시키는 프레임워크이다.

핵심 기여도

GRBench라는 10개 도메인 그래프와 1,740개 질문을 포함한 그래프 추론 벤치마크 데이터셋을 수작업으로 구성.
Graph Chain-of-thought (Graph-CoT)라는 반복적 그래프 추론 프레임워크를 제안.
Graph-CoT는 LLM reasoning, LLM-graph interaction, graph execution의 3단계로 구성.
3개의 LLM 백본 모델을 사용한 GRBench 실험에서 기존 기법 대비 일관된 성능 개선을 보임.

핵심 아이디어

기존 연구는 단일 텍스트 단위로 외부 지식을 확장하지만, 실제 도메인에서는 텍스트가 연결되어 그래프 구조를 형성한다. 예를 들어, 학술 논문은 인용과 공동 저자 관계로 연결되며, 이 관계 자체에 중요한 지식이 포함되어 있다. 따라서 단일 텍스트 기반의 Retrieval-Augmentation은 그래프 구조에 내재된 지식을 포착하지 못하며, 그래프의 크기 증가로 인해 LLM의 입력 길이 제한에 도달할 수 있다. 이에 따라, Graph-CoT는 LLM이 그래프를 단계적으로 탐색하며 필요한 정보를 추출하도록 유도하는 반복적 추론 프레임워크를 제안한다. 이는 기존 방식과 달리 전체 서브그래프를 입력으로 주입하는 대신, 그래프를 탐색하는 과정을 반복적으로 수행함으로써 정확도를 높이고 불필요한 정보를 줄인다.

기술적 접근법

**Graph-CoT 프레임워크**: 3단계 반복 구조로 구성됨.

1. **LLM reasoning**: 현재 정보로 도출 가능한 결론과 추가로 필요한 정보를 제시.
2. **LLM-graph interaction**: 그래프에서 정보를 가져오기 위한 요청 생성 (예: 노드 찾기, 이웃 확인).
3. **Graph execution**: 요청 실행 후 정보 반환.

**GRBench 데이터셋**: 5개 도메인(학술, 이커머스, 문학, 의료, 법률)의 10개 그래프와 1,740개 질문 포함.
**실험 설정**: 3개의 LLM 백본 모델을 사용하여 GRBench에서 실험 수행.
**평가 지표**: Rouge-L과 GPT-4 기반 정확도(GPT4score) 사용.

주요 결과

GRBench 데이터셋에서 Graph-CoT는 기존 기법 대비 일관된 성능 개선을 보임.
GPT4score 기준, Graph-CoT는 기존 기법 대비 +12.3%의 정확도 향상을 기록.
질문 난이도(단일-다중-유도적 추론)에 따라 성능 차이가 있으나, Graph-CoT는 모든 범주에서 상위 성능을 유지.
특히, 다중-홉 추론 질문에서 기존 기법 대비 +15.8%의 성능 향상.

의의 및 한계

Graph-CoT는 LLM이 그래프 구조를 활용한 반복적 추론을 가능하게 하여, 단일 텍스트 기반의 RAG 방식의 한계를 극복한다. 이는 특히 지식 집약적 작업에서 LLM의 환상 생성 문제를 줄이는 데 기여할 수 있다. GRBench는 그래프 기반 LLM 확장 연구를 위한 첫 번째 벤치마크로, 다양한 도메인과 질문 유형을 포함하여 연구의 재현성과 비교성을 높인다. 그러나 Graph-CoT는 그래프 탐색 과정에서 오류가 누적될 수 있으며, 복잡한 그래프 구조에 대한 LLM의 이해도가 낮아지는 한계가 있다.

실용적 활용

Graph-CoT는 학술 연구, 법률 판단, 의료 진단, 이커머스 추천 시스템 등 그래프 구조가 중요한 역할을 하는 분야에서 LLM의 정확도와 신뢰도를 높이는 데 활용될 수 있다. 특히, 인용 관계나 법적 판례 연결 등 구조화된 정보가 포함된 도메인에서 효과적이다.