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

arXiv: https://arxiv.org/abs/2404.07103 · HTML: https://mlsanity.com/paper/2404.07103/

## Key facts

- Cited by 119 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 10 Apr 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 30 of 30)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Retrieval Augmentation Reduces Hallucination in Conversation](https://mlsanity.com/paper/2104.07567/) (2021)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Persistent Anti-Muslim Bias in Large Language Models](https://mlsanity.com/paper/2101.05783/) (2021)
- [A Survey of Hallucination in Large Foundation Models](https://mlsanity.com/paper/2309.05922/) (2023)
- [Towards Understanding and Mitigating Social Biases in Language Models](https://mlsanity.com/paper/2106.13219/) (2021)
- [RAGTruth: A Hallucination Corpus for Developing Trustworthy Retrieval-Augmented Language Models](https://mlsanity.com/paper/2401.00396/) (2023)
- [ToolQA: A Dataset for LLM Question Answering with External Tools](https://mlsanity.com/paper/2306.13304/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Learning on Large-scale Text-attributed Graphs via Variational Inference](https://mlsanity.com/paper/2210.14709/) (2022)
- [GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](https://mlsanity.com/paper/2105.02605/) (2021)
- [Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction](https://mlsanity.com/paper/2111.00064/) (2021)
- [Large Language Models Can Learn Temporal Reasoning](https://mlsanity.com/paper/2401.06853/) (2024)
- [SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning](https://mlsanity.com/paper/2308.02565/) (2023)
- [Heterformer: Transformer-based Deep Node Representation Learning on Heterogeneous Text-Rich Networks](https://mlsanity.com/paper/2205.10282/) (2022)
- [Scientific Paper Recommendation: A Survey](https://mlsanity.com/paper/2008.13538/) (2020)
- [The Effect of Metadata on Scientific Literature Tagging: A Cross-Field Cross-Model Study](https://mlsanity.com/paper/2302.03341/) (2023)

## Built on by (most cited first, 30 of 119)

- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [A Comprehensive Survey of Scientific Large Language Models and Their Applications in Scientific Discovery](https://mlsanity.com/paper/2406.10833/) (2024)
- [RepoGraph: Enhancing AI Software Engineering with Repository-level Code Graph](https://mlsanity.com/paper/2410.14684/) (2024)
- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [Beyond Chain-of-Thought: A Survey of Chain-of-X Paradigms for LLMs](https://mlsanity.com/paper/2404.15676/) (2024)
- [Towards Agentic RAG with Deep Reasoning: A Survey of RAG-Reasoning Systems in LLMs](https://mlsanity.com/paper/2507.09477/) (2025)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [AgentRouter: A Knowledge-Graph-Guided LLM Router for Collaborative Multi-Agent Question Answering](https://mlsanity.com/paper/2510.05445/) (2025)
- [Towards Trustworthy Retrieval Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2502.06872/) (2025)
- [HybGRAG: Hybrid Retrieval-Augmented Generation on Textual and Relational Knowledge Bases](https://mlsanity.com/paper/2412.16311/) (2024)
- [KET-RAG: A Cost-Efficient Multi-Granular Indexing Framework for Graph-RAG](https://mlsanity.com/paper/2502.09304/) (2025)
- [From Single to Multi-Granularity: Toward Long-Term Memory Association and Selection of Conversational Agents](https://mlsanity.com/paper/2505.19549/) (2025)
- [ViCrit: A Verifiable Reinforcement Learning Proxy Task for Visual Perception in VLMs](https://mlsanity.com/paper/2506.10128/) (2025)
- [MemSim: A Bayesian Simulator for Evaluating Memory of LLM-based Personal Assistants](https://mlsanity.com/paper/2409.20163/) (2024)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [STEP: Enhancing Video-LLMs' Compositional Reasoning by Spatio-Temporal Graph-guided Self-Training](https://mlsanity.com/paper/2412.00161/) (2024)
- [Let's Ask GNN: Empowering Large Language Model for Graph In-Context Learning](https://mlsanity.com/paper/2410.07074/) (2024)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [OnePiece: Bringing Context Engineering and Reasoning to Industrial Cascade Ranking System](https://mlsanity.com/paper/2509.18091/) (2025)
- [GRAPHGPT-O: Synergistic Multimodal Comprehension and Generation on Graphs](https://mlsanity.com/paper/2502.11925/) (2025)
- [Causal Sufficiency and Necessity Improves Chain-of-Thought Reasoning](https://mlsanity.com/paper/2506.09853/) (2025)
- [medIKAL: Integrating Knowledge Graphs as Assistants of LLMs for Enhanced Clinical Diagnosis on EMRs](https://mlsanity.com/paper/2406.14326/) (2024)
- [Domain-Specific Retrieval-Augmented Generation Using Vector Stores, Knowledge Graphs, and Tensor Factorization](https://mlsanity.com/paper/2410.02721/) (2024)
- [Graph RAG-Tool Fusion](https://mlsanity.com/paper/2502.07223/) (2025)
- [Tool-to-Agent Retrieval: Bridging Tools and Agents for Scalable LLM Multi-Agent Systems](https://mlsanity.com/paper/2511.01854/) (2025)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)

## Abstract (arXiv)

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.