Source-linked AI summary
Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs
Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng, Jiawei Han
TL;DR
LLMs hallucinate on knowledge-intensive tasks, and text-only retrieval does not capture knowledge encoded in graph connections. The paper constructs GRBENCH and proposes GRAPH-COT, an iterative reasoning framework whose experiments show consistent baseline improvements, while identifying graph-understanding and training limitations.
Problem
Existing retrieval augmentation treats individual texts as knowledge units, but interconnected graphs also encode knowledge in their structure.
Method
The paper constructs GRBENCH and uses GRAPH-COT to iteratively combine LLM reasoning, graph interaction, and graph execution.
Results
GRAPH-COT consistently and significantly outperforms all baselines on GRBENCH, although its absolute score remains not high.
Takeaways & Limitations
The benchmark and framework support evaluating and augmenting LLMs through iterative reasoning over external graphs.
Takeaways & Limitations
GRBENCH questions are mostly manually designed, and the API-based LLM backbone cannot be readily fine-tuned.
Abstract
from arXiv · showhide
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.
1 Introduction
LLMs can hallucinate because they lack concrete knowledge sources, while text-attributed graphs encode knowledge in both texts and their connections. The paper introduces GRBENCH and GRAPH-COT to support and perform iterative graph reasoning.
- LLMs may generate plausible but ungrounded content because they memorize knowledge parametrically without consulting concrete sources.
- Interconnected texts encode knowledge through relationships such as citations, enabling graph traversal to trace research directions or verify legal judgments.
- Text retrieval augmentation overlooks graph structure, while local-subgraph contexts can grow exponentially and exceed LLM context limits.
- GRBENCH contains manually designed questions across ten real-world graphs and five domains, spanning single-hop, multi-hop, and inductive reasoning.
- GRAPH-COT iteratively combines LLM reasoning, graph interaction, and graph execution until the LLM concludes an answer.
- The paper reports extensive experiments analyzing GRAPH-COT across demonstration settings, backbone LLMs, and question difficulties.
2 Preliminaries
The paper models a graph as nodes and edges, with node-associated features represented as text in a text-attributed graph.
- A graph is denoted G = (V, E), where V and E are the node and edge sets, and each node may have associated feature information.
3 GRBENCH Dataset
GRBENCH is built from real-world domain graphs, manually designed question templates, GPT-4 paraphrases, and graph-derived ground-truth answers. Its questions cover progressively harder graph reasoning requirements.
- Dataset Overview: GRBENCH evaluates graph interaction using question-answer samples from ten graphs spanning academia, e-commerce, literature, healthcare, and legal domains.
- Dataset Overview: The dataset construction collects reference graphs, manually designs templates, generates paraphrases with GPT-4, and automatically derives answers from graphs.
- Domain Graphs: The five domains include academic graphs of papers, authors, and venues connected by citation, authorship, and venue relations.
- Domain Graphs: E-commerce graphs connect items and brands through relationships such as also-viewed and also-bought.
- Domain Graphs: Literature, healthcare, and legal graphs connect books, medical entities, and legal opinions through domain-specific relations.
- Question Templates: Easy questions require at most one-hop lookup, medium questions require multi-hop reasoning, and hard questions use graphs as informative context for answers not directly stored in them.
- Question Expression: Templates are instantiated with graph values, while GPT-4 paraphrases each template into five expressions to increase question diversity.
- Question Expression: Using identical expressions for samples from one template initially limited diversity and could make evaluation only partially comprehensive.
4 Graph Chain-of-Thought
GRAPH-COT addresses graph reasoning by iteratively deciding what information is needed, converting that decision into graph operations, and executing them to obtain new context.
- GRAPH-COT is an iterative framework with reasoning, interaction, and execution steps in each iteration.
- During reasoning, the LLM determines what external graph information is needed or whether the current context suffices.
- During interaction, the LLM selects graph operations that retrieve semantic or structural information.
- During execution, graph functions run the requested operations and return information for the next reasoning iteration.
- The framework can be viewed as an agent setup in which LLMs act as agents, graphs act as environments, and predefined functions mediate question answering.
5 Experiments
Experiments compare GRAPH-COT with standard, text-retrieval, and graph-retrieval baselines across multiple backbones and evaluation settings. GRAPH-COT performs best overall, but performance depends on demonstrations, backbone capability, question difficulty, and accurate graph interaction.
- Overall Performance: Graph RAG usually outperforms Text RAG because its context includes structure-aware subgraphs rather than only retrieved text.The main Graph RAG result uses 1-hop ego-graphs linearized into text sequences.
- Overall Performance: GRAPH-COT outperforms standard LLMs, Text RAG, and Graph RAG consistently and significantly on GRBENCH.The evaluation uses Rouge-L and GPT4score, with GPT-3.5-turbo as the GRAPH-COT backbone in the main results.
- Ablation Study: Without reasoning demonstrations, GRAPH-COT achieves nearly 0 performance across datasets, whereas cross-domain demonstrations remain generally robust.The ablation studies indicate that in-context demonstrations teach the key steps of graph chain-reasoning, even when demonstration domains differ.
- Ablation Study: GPT-4 performs better than weaker backbones in GRAPH-COT, showing that instruction-following and reasoning ability affect results.The backbone comparison includes LLaMA-2-13b-chat, Mixtral-8x7b-Instruct, GPT-3.5-turbo, and GPT-4.
- RAG vs GRAPH-COT: 1-hop ego-graph retrieval performs best among retrieval settings but still underperforms GRAPH-COT, while larger-hop contexts risk excessive length and lost information.The authors attribute this limitation to the exponential growth of nodes and texts as hop number increases.
- Question Difficulty: GRAPH-COT performs relatively well on easy questions but worse on medium and hard questions requiring complex or inductive reasoning.The benchmark also includes manually designed questions spanning three difficulty levels.
6 Related Work
Prior work uses LLMs for graph-related tasks either as feature extractors or predictors, while retrieval augmentation supplies external text contexts. This paper addresses the less explored problem of augmenting LLMs with graph-structured knowledge.
- Existing graph-LLM methods use LLMs as feature extractors or final predictors for graph tasks.Examples include LLM-GNN cascades, sequence-based structure encoding, and graph-empowered language-model architectures.
- Most prior graph-LLM work focuses on traditional tasks such as node classification and link prediction.
- Retrieval-augmented generation retrieves external text units as LLM context to improve factuality and reduce hallucination.
- Unlike this work, most retrieval-augmentation methods are designed for external text corpora rather than graph knowledge.
7 Conclusions
The paper studies graph-based augmentation of LLMs, introduces GRBENCH and GRAPH-COT, and evaluates GRAPH-COT on the benchmark with multiple backbone models.
- GRBENCH contains 1,740 questions and 10 graphs from 5 domains, with each question answerable from graph knowledge.
- GRAPH-COT augments LLMs by conducting iterative reasoning on graphs through reasoning, interaction, and execution.
- Experiments with three backbone LLMs on GRBENCH demonstrate the effectiveness of GRAPH-COT.
- The paper identifies future directions involving better graph understanding and more complex reasoning by LLMs.
Limitations
The study’s benchmark construction and model-training setup impose scope boundaries on evaluation and future development.
- GRBENCH question templates are mostly manually designed, leaving room to improve question diversity and difficulty.
- GRAPH-COT uses an API LLM that cannot be fine-tuned or is very costly to fine-tune.
- Future methods may need to train LLMs explicitly to navigate graphs.
Ethics Statement
The paper motivates graph augmentation partly by LLM hallucinations and proposes external graphs as knowledge sources. It frames this integration as a potential way to reduce bias and misinformation.
- LLMs demonstrate strong language processing and generation but can propagate false information.
- The study integrates external graphs as knowledge sources to enhance LLMs.
- The paper presents graph integration as a potential solution for reducing bias and eradicating misinformation.
A Dataset
GRBENCH spans heterogeneous domain graphs whose nodes carry domain-specific features and whose edges encode meaningful relations. The dataset includes academic, healthcare, e-commerce, legal, and literature graph structures.
- Academic Graphs: Academic graphs contain paper, author, and venue nodes with feature and neighboring information.Paper, author, and venue examples illustrate the graph’s node attributes and connections.
- E-commerce Graphs: E-commerce graphs contain item and brand nodes connected through viewing, purchasing, and co-purchase relations.The graph includes also-viewed, also-bought, bought-together, and buy-after-viewing item relations.
- Literature Graphs: Literature graphs contain book, author, publisher, and series nodes, with book attributes including publication year and popular shelves.The graph represents bibliographic entities and their associated metadata.
- Healthcare Graphs: Healthcare graphs contain eleven node types, including anatomy, gene, disease, compound, pathway, and symptom.The graph includes biologically and medically distinct node categories connected by typed relations.
- Healthcare Graphs: Healthcare relations include gene participation, compound effects, disease associations, anatomical regulation, and symptom presentation.Examples include Compound-causes-Side Effect, Disease-associates-Gene, and Gene-participates-Biological Process.
- Legal Graphs: Legal graphs contain opinion, opinion cluster, docket, and court nodes with attributes such as case identifiers and citation strings.Examples include opinion clusters, PACER case IDs, and citation strings.
B Question Templates
GRBENCH question templates span easy, medium, and hard graph reasoning tasks across academic, legal, e-commerce, literature, and healthcare domains. They range from direct attribute lookup to multi-hop retrieval, counting, comparison, recommendation, and synthesis.
- B Question Templates: The benchmark organizes questions into easy, medium, and hard templates.The templates are intended to structure graph questions by reasoning difficulty.
- B Question Templates: Academic templates ask about authorship, collaboration, venues, citations, research interests, and paper recommendation.Examples include finding coauthors, counting papers, identifying venues, and selecting a recommended paper from candidates.
- B Question Templates: E-commerce templates cover item attributes, brand membership, interaction counts, shared neighbors, prices, categories, and recommendations.The questions use co-viewed, bought-together, buy-after-viewing, and also-bought relations for counting and comparison.
- B Question Templates: Literature templates query book metadata, authors, publishers, series, genres, languages, publication years, and recommendations.They also ask for shared-author or shared-publisher books, earliest works, and aggregate genre or language properties.
- B Question Templates: Harder templates require multi-hop counting, intersection, correlation, or majority-style reasoning across graph relations.Examples ask for shared biological processes, diseases with matching symptoms, correlated entities, and cellular components or pathways reached through filtered genes.
- B Question Templates: Legal templates ask for court dates, citation strings, docket identifiers, attorneys, judges, opinion clusters, and case support.These questions combine node-feature lookup with relations among opinions, dockets, courts, and clusters.
- C Question Template Paraphrase Prompt: Templates are paraphrased into four alternative question forms while preserving names and the question-answer format.The paraphrase prompt instructs generation without apostrophes in questions and with unchanged names in quotation marks.
D Programmatic Automatic Answer Generation Examples
The examples programmatically generate graph question-answer pairs by traversing typed one-hop neighborhoods, formatting node features and neighbors, and embedding the resulting examples in Graph-CoT prompts. The prompt interleaves reasoning, graph interaction, and graph feedback.
- Programmatic Answer Generation: The one_hop function defines graph traversal over a center node type, neighbor node type, edge type, and output limit k.It accepts graph and feature-key arguments and returns generated examples for a specified relation.
- Programmatic Answer Generation: Center nodes are shuffled, iterated, and read by their feature names before neighbor lookup.The code randomizes center IDs, loops through them, and extracts each center node’s name.
- Programmatic Answer Generation: The generator skips centers lacking the requested edge and retrieves neighbor IDs and names from the selected relation.Neighbor names are assembled from the graph’s typed adjacency structure.
- Programmatic Answer Generation: Neighbor lists longer than five entries are truncated before examples are stored.The generation routine checks the neighbor count and limits the displayed neighborhood.
- Programmatic Answer Generation: A healthcare example asks for compound side effects and generates answers through the Compound-causes-Side Effect relation.The generated question uses a compound name, while the answer is populated from the corresponding side effects.
- Graph-CoT Prompt: The Graph-CoT prompt contains graph descriptions, interaction-function descriptions, and demonstrations.These three components are inserted into a final prompt template.
- Graph-CoT Prompt: Graph-CoT interleaves Thought, Interaction with Graph, and Feedback from Graph steps, using four graph interaction functions.The prompt permits as many reasoning and interaction steps as necessary and requests answers by node features rather than IDs.