# GraphSearch: Agentic Search-Augmented Reasoning for Zero-Shot Graph Learning

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

## Key facts

- Cited by 7 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 22 of its 36 references that are in the map.
- First posted on arXiv 13 Jan 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

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

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.05592/) (2025)
- [LightRAG: Simple and Fast Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.05779/) (2024)
- [From RAG to Memory: Non-Parametric Continual Learning for Large Language Models](https://mlsanity.com/paper/2502.14802/) (2025)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.19470/) (2025)
- [Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning](https://mlsanity.com/paper/2305.19523/) (2023)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?](https://mlsanity.com/paper/2309.16595/) (2023)
- [R1-Searcher++: Incentivizing the Dynamic Knowledge Acquisition of LLMs via Reinforcement Learning](https://mlsanity.com/paper/2505.17005/) (2025)
- [RAGraph: A General Retrieval-Augmented Graph Learning Framework](https://mlsanity.com/paper/2410.23855/) (2024)
- [Let's Ask GNN: Empowering Large Language Model for Graph In-Context Learning](https://mlsanity.com/paper/2410.07074/) (2024)
- [GraphICL: Unlocking Graph Learning Potential in LLMs through Structured Prompt Design](https://mlsanity.com/paper/2501.15755/) (2025)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)

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

- [AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning](https://mlsanity.com/paper/2604.05846/) (2026)
- [GraphVLM: Benchmarking Vision Language Models for Multimodal Graph Learning](https://mlsanity.com/paper/2603.13370/) (2026)
- [Do We Still Need GraphRAG? Benchmarking RAG and GraphRAG for Agentic Search Systems](https://mlsanity.com/paper/2604.09666/) (2026)
- [FT-RAG: A Fine-grained Retrieval-Augmented Generation Framework for Complex Table Reasoning](https://mlsanity.com/paper/2605.01495/) (2026)
- [Agentic Graph Token Reasoning](https://mlsanity.com/paper/2608.00542/) (2026)
- [OpenMAS-GCom. A Diagnostic Benchmark for Graph-enhanced Multi-Agent Systems](https://mlsanity.com/paper/2609.21527/) (2026)
- [GraphMAS: A Systematic Benchmark of Multi-Agent Coordination for Graph Learning](https://mlsanity.com/paper/2609.39777/) (2026)

## Abstract (arXiv)

Recent advances in search-augmented large reasoning models (LRMs) enable the retrieval of external knowledge to reduce hallucinations in multistep reasoning. However, their ability to operate on graph-structured data, prevalent in domains such as e-commerce, social networks, and scientific citations, remains underexplored. Unlike plain text corpora, graphs encode rich topological signals that connect related entities and can serve as valuable priors for retrieval, enabling more targeted search and improved reasoning efficiency. Yet, effectively leveraging such structure poses unique challenges, including the difficulty of generating graph-expressive queries and ensuring reliable retrieval that balances structural and semantic relevance. To address this gap, we introduce GraphSearch, the first framework that extends search-augmented reasoning to graph learning, enabling zero-shot graph learning without task-specific fine-tuning. GraphSearch combines a Graph-aware Query Planner, which disentangles search space (e.g., 1-hop, multi-hop, or global neighbors) from semantic queries, with a Graph-aware Retriever, which constructs candidate sets based on topology and ranks them using a hybrid scoring function. We further instantiate two traversal modes: GraphSearch-R, which recursively expands neighborhoods hop by hop, and GraphSearch-F, which flexibly retrieves across local and global neighborhoods without hop constraints. Extensive experiments across diverse benchmarks show that GraphSearch achieves competitive or even superior performance compared to supervised graph learning methods, setting state-of-the-art results in zero-shot node classification and link prediction. These findings position GraphSearch as a flexible and generalizable paradigm for agentic reasoning over graphs.