GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics

GraphCert, a post-training method from researchers behind the arXiv paper 2609.38798v1, bootstraps agentic graph reasoning by generating graph-grounded QA pairs and certifying supporting evidence into rubrics that reward evidence alignment alongside answer correctness during GRPO training. Experiments across five graph reasoning domains in GRBENCH show GraphCert consistently outperforms substantially larger LLM agents and post-training methods, with the learned policy transferring robustly across heterogeneous graph domains. The authors state the code will be made publicly available.

arXiv:2609.38798v1 Announce Type: new Abstract: 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.