Graph Problem Reasoning and Large Language Models: A Comprehensive Survey

The Hong Kong University of Science and Technology (Guangzhou)

Data Science and Analytics Thrust

PhD Qualifying Examination

By Mr. ZHANG, Qifan

Abstract

The intersection of Large Language Models (LLMs) and graph problem reasoning has rapidly emerged as a vibrant research area, driven by the unique advantages of graph problems in probing, evaluating, and enhancing the complex reasoning capabilities of modern AI systems. Graph problems offer arbitrary scalability in difficulty, inherently long-context structures, deterministic verifiability, and rich cross-domain transferability—properties that make them ideal testbeds for LLM reasoning. This survey provides a comprehensive review of recent progress at this intersection, organized along two complementary trajectories: LLM for Graph, which investigates how LLMs can be applied to solve graph algorithmic problems through prompting strategies, code generation, and multi-agent collaboration; and Graph for LLM, which explores how graph problem data can serve as high-quality reasoning corpora to enhance the general reasoning abilities of LLMs via continued pretraining and fine-tuning. We systematically categorize existing benchmarks, methods, and training paradigms, critically analyze their strengths and limitations, and identify key open challenges and promising future directions in this rapidly evolving field.

PQE Committee