# GCoder: Improving Large Language Model for Generalized Graph Problem Solving

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

## Key facts

- Cited by 11 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 29 of its 51 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Placed in

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

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning](https://mlsanity.com/paper/2309.05653/) (2023)
- [Augmented Language Models: a Survey](https://mlsanity.com/paper/2302.07842/) (2023)
- [Enhancing Retrieval-Augmented Large Language Models with Iterative Retrieval-Generation Synergy](https://mlsanity.com/paper/2305.15294/) (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)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [OpenGraph: Towards Open Graph Foundation Models](https://mlsanity.com/paper/2403.01121/) (2024)
- [Label-free Node Classification on Graphs with Large Language Models (LLMS)](https://mlsanity.com/paper/2310.04668/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment](https://mlsanity.com/paper/2402.08785/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [MATHSENSEI: A Tool-Augmented Large Language Model for Mathematical Reasoning](https://mlsanity.com/paper/2402.17231/) (2024)
- [GraphWiz: An Instruction-Following Language Model for Graph Problems](https://mlsanity.com/paper/2402.16029/) (2024)
- [VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context](https://mlsanity.com/paper/2405.04950/) (2024)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [Prompt-based Node Feature Extractor for Few-shot Learning on Text-Attributed Graphs](https://mlsanity.com/paper/2309.02848/) (2023)
- [Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models](https://mlsanity.com/paper/2409.19667/) (2024)
- [A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment](https://mlsanity.com/paper/2305.06574/) (2023)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)
- [Link Recommendation to Augment Influence Diffusion with Provable Guarantees](https://mlsanity.com/paper/2402.19189/) (2024)
- [Finding Densest Subgraphs with Edge-Color Constraints](https://mlsanity.com/paper/2402.09124/) (2024)
- [Local Centrality Minimization with Quality Guarantees](https://mlsanity.com/paper/2402.07718/) (2024)

## Built on by (most cited first, 11 of 11)

- [ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation](https://mlsanity.com/paper/2502.09891/) (2025)
- [Graph is a Substrate Across Data Modalities](https://mlsanity.com/paper/2601.22384/) (2026)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [Rethinking and Benchmarking Large Language Models for Graph Reasoning](https://mlsanity.com/paper/2509.24260/) (2025)
- [DynamicGTR: Leveraging Graph Topology Representation Preferences to Boost VLM Capabilities on Graph QAs](https://mlsanity.com/paper/2602.21864/) (2026)
- [MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications](https://mlsanity.com/paper/2502.18540/) (2025)
- [Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems](https://mlsanity.com/paper/2602.06319/) (2026)
- [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)
- [GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL](https://mlsanity.com/paper/2608.27142/) (2026)
- [GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics](https://mlsanity.com/paper/2609.38798/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated strong reasoning abilities, making them suitable for complex tasks such as graph computation. Traditional reasoning steps paradigm for graph problems is hindered by unverifiable steps, limited long-term reasoning, and poor generalization to graph variations. To overcome these limitations, we introduce GCoder, a code-based LLM designed to enhance problem-solving in generalized graph computation problems. Our method involves constructing an extensive training dataset, GraphWild, featuring diverse graph formats and algorithms. We employ a multi-stage training process, including Supervised Fine-Tuning (SFT) and Reinforcement Learning from Compiler Feedback (RLCF), to refine model capabilities. For unseen tasks, a hybrid retrieval technique is used to augment performance. Experiments demonstrate that GCoder outperforms GPT-4o, with an average accuracy improvement of 16.42% across various graph computational problems. Furthermore, GCoder efficiently manages large-scale graphs with millions of nodes and diverse input formats, overcoming the limitations of previous models focused on the reasoning steps paradigm. This advancement paves the way for more intuitive and effective graph problem-solving using LLMs. Code and data are available at here: https://github.com/Bklight999/WWW25-GCoder/tree/master.