# GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 27 of its 39 references that are in the map.
- First posted on arXiv 30 Sep 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/)
- Synthetic data and self-improvement for LLMs / [Self-evolving search agents](https://mlsanity.com/synth/self-evolving-search-agents/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models](https://mlsanity.com/paper/2512.02556/) (2025)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning](https://mlsanity.com/paper/2308.02565/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL](https://mlsanity.com/paper/2509.10446/) (2025)
- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)
- [LinkGPT: Teaching Large Language Models To Predict Missing Links](https://mlsanity.com/paper/2406.04640/) (2024)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Graph-O1 : Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning](https://mlsanity.com/paper/2512.17912/) (2025)
- [Actions Speak Louder than Prompts: A Large-Scale Study of LLMs for Graph Inference](https://mlsanity.com/paper/2509.18487/) (2025)
- [PolyG: Adaptive Graph Traversal for Diverse GraphRAG Questions](https://mlsanity.com/paper/2504.02112/) (2025)
- [HyperGraphPro: Progress-Aware Reinforcement Learning for Structure-Guided Hypergraph RAG](https://mlsanity.com/paper/2601.17755/) (2026)
- [Code-on-Graph: Iterative Programmatic Reasoning via Large Language Models on Knowledge Graphs](https://mlsanity.com/paper/2606.03705/) (2026)
- [GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning](https://mlsanity.com/paper/2603.01410/) (2026)
- [GraphDancer: Training LLMs to Explore and Reason over Graphs via Two-Stage Curriculum Post-Training](https://mlsanity.com/paper/2602.02518/) (2026)

## Abstract (arXiv)

Graph agents extend large language models (LLMs) with the ability to actively explore and reason over knowledge graphs through multi-step interactions with graph tools. However, training capable graph agents typically requires large collections of question-answer pairs and reasoning trajectories, whose manual construction is costly and difficult to scale. Moreover, employing proprietary LLMs to generate such supervision further risks exposing sensitive graph data to external services. Therefore, we propose GraphCert to bootstrap agentic graph reasoning with certified evidence rubrics during post-training. Specifically, the Bootstrapped Graph Quizzer guided by generation controls produces graph-grounded QA pairs and marks supporting evidence, which undergo execution certification and semantic curation. The accepted evidence is then canonicalized into certified evidence rubrics that later reward Graph Solver evidence alignment alongside answer correctness during GRPO training. Experiments on five graph reasoning domains in GRBENCH demonstrate that GraphCert consistently outperforms substantially larger LLM agents and post-training method. Furthermore, our analysis demonstrates that the learned policy transfers robustly across heterogeneous graph domains, suggesting that GraphCert acquires reusable graph-reasoning capabilities rather than domain-specific patterns. These results establish executable self-certification as an effective approach to self-training compact graph reasoning agents. Our code will be made publicly available.