GRAPH-O1: Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning

Text-attributed graphs, where nodes and edges are enriched with textual informa- tion, are widely used across various domains. A central challenge in this setting is question answering, which requires effectively integrating unstructured text with the structured relationships in the graph. Although Large Language Models (LLMs) have achieved remarkable progress in natural language understanding, their direct application to reasoning over text-attributed graphs remains limited. Existing text retrieval–augmented generation methods often treat text passages as independent units, overlooking the rich interconnections within the graph. Similarly, conven- tional graph RAG approaches that encode large subgraphs as text quickly become impractical due to LLM context-length constraints, leading to fragmented reason- ing and reduced accuracy. To address these challenges, we propose GRAPH-O1, an agentic GraphRAG framework that enables LLMs to perform stepwise, interactive reasoning over graphs. Our approach combines Monte Carlo Tree Search (MCTS) with end-to-end reinforcement learning, allowing the model to selectively explore and retrieve only the most relevant subgraph elements. The reasoning process is modeled as a multi-turn agent–environment interaction, and the agent is opti- mized via an end-to-end reward mechanism. Extensive experiments across multiple LLM backbones show that GRAPH-O1 consistently outperforms state-of-the-art baselines, delivering more accurate, reliable, and interpretable answers.