# GraphWiz: An Instruction-Following Language Model for Graph Problems

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

## Key facts

- Cited by 32 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 48 of its 62 references that are in the map.
- First posted on arXiv 25 Feb 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning](https://mlsanity.com/paper/2309.05653/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)

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

- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [A Survey of Large Language Models for Graphs](https://mlsanity.com/paper/2405.08011/) (2024)
- [Parameter-Efficient Fine-Tuning with Discrete Fourier Transform](https://mlsanity.com/paper/2405.03003/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [GLBench: A Comprehensive Benchmark for Graph with Large Language Models](https://mlsanity.com/paper/2407.07457/) (2024)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [GRAPHGPT-O: Synergistic Multimodal Comprehension and Generation on Graphs](https://mlsanity.com/paper/2502.11925/) (2025)
- [LangGFM: A Large Language Model Alone Can be a Powerful Graph Foundation Model](https://mlsanity.com/paper/2410.14961/) (2024)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [A Survey on Self-Supervised Graph Foundation Models: Knowledge-Based Perspective](https://mlsanity.com/paper/2403.16137/) (2024)
- [PortLLM: Personalizing Evolving Large Language Models with Training-Free and Portable Model Patches](https://mlsanity.com/paper/2410.10870/) (2024)
- [CodeGraph: Enhancing Graph Reasoning of LLMs with Code](https://mlsanity.com/paper/2408.13863/) (2024)
- [Graph-KV: Breaking Sequence via Injecting Structural Biases into Large Language Models](https://mlsanity.com/paper/2506.07334/) (2025)
- [Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applications](https://mlsanity.com/paper/2510.21131/) (2025)
- [GUNDAM: Aligning Large Language Models with Graph Understanding](https://mlsanity.com/paper/2409.20053/) (2024)
- [NPG-Muse: Scaling Long Chain-of-Thought Reasoning with NP-Hard Graph Problems](https://mlsanity.com/paper/2508.20373/) (2025)
- [GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining](https://mlsanity.com/paper/2511.00457/) (2025)
- [Chain of Execution Supervision Promotes General Reasoning in Large Language Models](https://mlsanity.com/paper/2510.23629/) (2025)
- [DynamicGTR: Leveraging Graph Topology Representation Preferences to Boost VLM Capabilities on Graph QAs](https://mlsanity.com/paper/2602.21864/) (2026)
- [A Hierarchical Language Model For Interpretable Graph Reasoning](https://mlsanity.com/paper/2410.22372/) (2024)
- [Integrating Structural and Semantic Signals in Text-Attributed Graphs with BiGTex](https://mlsanity.com/paper/2504.12474/) (2025)
- [Joint Embeddings for Graph Instruction Tuning](https://mlsanity.com/paper/2405.20684/) (2024)
- [Improving LLMs' Generalized Reasoning Abilities by Graph Problems](https://mlsanity.com/paper/2507.17168/) (2025)
- [Harnessing Adaptive Topology Representations for Zero-Shot Graph Question Answering](https://mlsanity.com/paper/2508.06345/) (2025)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [GFMate: Empowering Graph Foundation Models with Test-time Prompt Tuning](https://mlsanity.com/paper/2605.14809/) (2026)
- [PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization](https://mlsanity.com/paper/2507.06127/) (2025)

## Abstract (arXiv)

Large language models (LLMs) have achieved impressive success across several fields, but their proficiency in understanding and resolving complex graph problems is less explored. To bridge this gap, we introduce GraphInstruct, a novel and comprehensive instruction-tuning dataset designed to equip language models with the ability to tackle a broad spectrum of graph problems using explicit reasoning paths. Utilizing GraphInstruct, we build GraphWiz, an open-source language model capable of resolving various graph problem types while generating clear reasoning processes. To enhance the model's capability and reliability, we incorporate the Direct Preference Optimization (DPO) framework into the graph problem-solving context. The enhanced model, GraphWiz-DPO, achieves an average accuracy of 65% across nine tasks with different complexity levels, surpassing GPT-4 which has an average accuracy of 43.8%. Moreover, our research delves into the delicate balance between training data volume and model performance, highlighting the potential for overfitting with increased data. We also explore the transferability of the model's reasoning ability across different graph tasks, indicating the model's adaptability and practical application potential. Our investigation offers a new blueprint and valuable insights for developing LLMs specialized in graph reasoning and problem-solving.