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

Abstract: 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/.

## introduction large language models (llms) @xcite have demonstrated their exceptional language understanding and text generation capability in real-world scenarios @xcite . however, llms suffer from hallucination problems and sometimes tend to generate content that appears plausible but is ungrounded @xcite . this is because they memorize world knowledge parametrically and fail to refer to concrete knowledge sources @xcite . to alleviate the hallucination issues, existing works propose to augment llms with external text corpora as knowledge sources @xcite and treat every single document as a knowledge unit. retrieval augmentation (rag) @xcite is then proposed to enable llms to interact with external knowledge sources, where relevant texts are retrieved and serve as contexts to improve the factuality of llms (shown in figure 1 (a) ). however, retrieval augmentation assumes that knowledge is well represented in individual text units and ignores the correlations among multiple text units. in real-world scenarios, text units are generally interconnected, forming a (text-attributed) graph. the knowledge of such graphs is reflected not only in the form of texts but also in the structure of their connections. for example, academic papers in a bibliographic graph are linked by citation links @xcite . we can trace the source of a research direction @xcite by traversing such a graph. cases and opinions in a legal graph are interconnected by reference edges @xcite . we can verify the judgment for a case by looking up its citations on such a graph @xcite . although widely used for text corpora as external knowledge sources, retrieval-augmentation cannot be readily used to augment llms with graphs for two reasons: 1) structure context: retrieval augmentation can find individual nodes/texts from the graphs which can serve as context to augment the llms. however, knowledge on the graph also lies in the structure which can not be captured by single nodes/texts. 2) graph size explosion: although it is feasible to convert local subgraph structures into text descriptions as the input contexts to llms, the size of the local subgraph increases exponentially as the hop number increases, resulting in an excessively long context sequence. this could cause llms to be lost in the middle (liu et al., 2023) given a plethora of irrelevant information in the context. in addition, the long sequence could potentially exceed the input length limitations of llms @xcite . therefore, it is an important research topic to augment llms with such graph information. unfortunately, there has been a lack of benchmark datasets to support the development of methodology and facilitate the evaluation of the proposed models. to this end, we first construct a graph reasoning benchmark dataset called gr-bench. grbench includes ten real-world graphs that can serve as external knowledge sources for llms from five domains including academic, ecommerce, literature, healthcare, and legal domains. each sample in grbench consists of a manually designed question and an answer, which can be directly answered by referring to the graphs or retrieving the information from the graphs as context. to make the dataset comprehensive, we include samples of different difficulty levels: easy questions (which can be answered with single-hop reasoning on graphs), medium questions (which necessitate multi-hop reasoning on graphs), and hard questions (which call for inductive reasoning with information on graphs as context). we propose a simple and effective framework called graph chain-of-thought (graph-cot). the main idea is to enable llms to traverse the graph step-by-step to figure out the key information needed, rather than directly feeding the whole subgraph as context into the llms (shown in figure 1 (b) ). graph-cot is an iterative framework, where one iteration corresponds to one step on the graph. each iteration in graph-cot consists of three sub-steps: 1) reasoning: llms propose what conclusion we can make with the current information and what further information is needed from the graph; 2) interaction: llms generate the interactions needed to fetch information from the graph (e.g., finding the nodes, checking the neighbors, etc); 3) execution: the requests from the interaction step are executed on the graph and the corresponding information is returned. in this way, llms can conduct chain-based reasoning on the graph and find the key information on the graph. this process will be iterated until llms conclude the final answer in the reasoning sub-step. in summary, our contributions are as follows: • we propose the problem of augmenting llms with external graphs and introduce a comprehensive benchmark dataset called grbench. definition 2.1. graph. a graph can be denoted as @xmath0, e), where v and e are node set and edge set, respectively. each v @xmath1. for example, in an e-commerce item graph, @xmath2, @xmath3, and x v include features such as item title, description, price, and category. in this work, we formulate all the features as texts and the graph is also called a text-attributed graph. definition 2.2. neighbors and degree. the neighbors of a node v i refer to nodes which are linked to v i on the graph, denoted as n ( ## graph chain-of-thought the straightforward solution to let llms interact with the graph is through retrieval-augmentation generation (rag) @xcite , where a retriever fetches related information from graphs as context for llm generation. however, different from text corpus as the external knowledge source, the information in graphs also lies in the complex interconnection between the text units, which poses a potential requirement for traversing and reasoning on graphs. to enable llms to reason, chain-of-thought @xcite is proposed to encourage llms to decompose complex tasks into several steps. however, it is designed for reasoning on texts and leaves reasoning on graphs with llms an open question. to this end, we design a simple solution named graph chain-of-thought (graph-cot) to tackle the complex graph reasoning problem with llms (shown in figure 2 ). graph-cot is an iterative framework, with three steps in each iteration: reasoning, interaction, and execution. we delve into each step as follows: reasoning with llms. given the question or the previous iteration context, the first step is to let the llms conduct reasoning on what further external information from graphs is needed to answer the question, or if the question is answerable with the current contexts from graphs. for example, given the question "who are the authors of language models are unsupervised multitask learners?". the llms are expected to reason "we need to first find the paper node {language models are unsupervised multitask learners} on the graph." interaction between llms and graphs. based on the output results from the previous llm reasoning step, the next step is to let llms know how to interact with the graphs and fetch relevant information from the graphs. inspired by @xcite , we pre-define four graph functions to cover both the semantic information and structure information on the graphs: external graph who develops both resnet and mae? question whole process llm reasoning graph execution llm reasoning graph execution ## conclusions in this work, we study the problem of augmenting llms with (text-attributed) graphs as external knowledge sources. we first manually construct a benchmark dataset called grbench, which contains 1,740 questions and 10 graphs from 5 domains. each question in grbench can be answered by referring to the graphs. we further propose a simple and effective framework called graph-cot, which can augment llms with graphs by letting llms conduct iterative reasoning on graphs. graph-cot contains three sub-steps in each iteration: llm reasoning, llm-graph interaction, and graph execution. we then conduct experiments with three backbone llms on grbench and demonstrate the effectiveness of graph-cot. future works can explore how to let llms better understand the graphs and how to let llms conduct more complex reasoning.