GraphCert improves graph reasoning agents with self-certified evidence rubrics
GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics
Artificial Intelligence
Summary
It can be hard to train computer programs that understand and answer questions about big networks of information because it usually needs lots of examples made by people. This paper presents GraphCert, a way for these programs to teach themselves using evidence they check and approve themselves, without sharing sensitive data. The authors show that GraphCert works well across many kinds of network data and makes smaller programs just as smart as bigger ones. This method lets graph reasoning agents get better without needing lots of expensive human-made examples.
What this means in practice
- •For knowledge graph engineers: Train graph question-answering agents without exposing sensitive data by using self-certified evidence rubrics during post-training.
- •For enterprise ai developers: Develop smaller, efficient graph reasoning agents that transfer across different domains, reducing reliance on large proprietary language models.
Authors
Weiqi Jiang, Yuchen Ying, Rui Wang, Kaixuan Chen, Bingde Hu, Shunyu Liu, Yu Wang, Tongya Zheng
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.