PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics

Weiqi Jiang, Yuchen Ying, Rui Wang, Kaixuan Chen, Bingde Hu, Shunyu Liu, Yu Wang, Tongya Zheng

arXiv:2609.38798v1cs.AI

TL;DR

Graph-reasoning training often relies on costly human-authored supervision or proprietary LLM-generated data. GraphCert bootstraps training with certified evidence rubrics; across five GRBENCH domains, it consistently outperforms strong prompting-based and self-training baselines, with an 8.2% average relative F1 gain over each domain’s strongest baseline.

  • Problem

    Existing graph-reasoning training often relies on human-authored supervision or powerful proprietary LLMs, introducing annotation cost, deployment overhead, and privacy concerns.

    Source: Introduction · p. 2

  • Method

    GraphCert uses executable self-training to generate graph-grounded QA pairs, certify supporting evidence, and train compact LLMs with certified evidence rubrics.

    Source: Introduction · p. 2

  • Results

    Across five GRBENCH domains, GraphCert consistently outperforms strong prompting-based and self-training baselines, with an 8.2% average relative F1 gain over each domain’s strongest baseline.

    Source: Introduction · p. 2, Conclusion · p. 7

  • Takeaways & Limitations

    GraphCert provides an effective approach to training compact graph agents without external teacher models.

    Source: Conclusion · p. 8

    Accepted certificates do not establish an error-free Judge, formally proven causal lineage, unique query solutions, or invariance to future graph snapshots.

    Source: Semantic Curation Protocol · p. 12

Abstract

from arXiv · show

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.

Introduction

GraphCert tackles the difficulty of training compact LLMs for transferable graph reasoning by generating graph-grounded supervision, certifying its evidence, and using certified rubrics to guide Solver training.

Motivation

  • Existing graph-reasoning approaches can lose structural information, compound multi-hop errors, or miss schema semantics, while training often depends on costly human supervision or powerful external LLMs.These dependencies also introduce deployment overhead and privacy concerns.Source: Introduction · pp. 1–2
  • Certification rejects over one third of Quizzer candidates in Healthcare and Literature, including hard failures affecting 21.2% and 14.4%, respectively, underscoring the need to verify and curate locally generated supervision.Hard failures include schema-direction errors, answer–evidence inconsistencies, incomplete evidence, and execution failures; semantic curation filters additional candidates.Source: Introduction · pp. 1–2

GraphCert

  • GraphCert treats Quizzer-generated QA pairs and supporting evidence as candidate certificates, then uses execution certification and semantic curation to create rubrics for evidence-alignment rewards during GRPO training.The Solver independently explores the graph, predicts answers, and records evidence; its evidence is compared with hidden certified rubrics alongside answer correctness.Source: Introduction · p. 2

Results

  • On GRBENCH, GraphCert gains an average relative 8.2% in F1 over the strongest baseline on each domain and transfers robustly across heterogeneous domains.The experiments also show that it improves the compact base model and outperforms larger or teacher-dependent graph agents.Source: Introduction · p. 2

Related Work

Prior work applies LLMs to graph reasoning as feature extractors or direct reasoners, while agentic graph post-training targets structural exploration and multi-step interaction. Existing supervision often depends on predefined paths, teacher-generated trajectories, task-specific QA, or proprietary LLMs.

LLMs for Graph Reasoning

Post-Training for Agentic Graph Reasoning

  • Post-training studies use synthetic verifiable graph problems, optimize iterative GraphRAG retrieval and answers, or train knowledge graph agents with paths, trajectories, and outcome- or process-level rewards (Guo et al. 2025; Luo et al. 2025; Yu et al. 2026; Park et al. 2026; Luo et al. 2024a; Liu 2025; Bai et al. 2026).General-purpose LLMs often remain limited in structural exploration and multi-step interaction, motivating task-specific post-training.Source: Related Work · p. 2
  • Prior knowledge graph agent methods typically depend on predefined paths, teacher-generated trajectories, or task-specific QA, while GraphScout generates graph-grounded QA with proprietary LLMs that may raise privacy and inference-cost concerns (Luo et al. 2024a; Liu 2025; Bai et al. 2026; Ying et al. 2026b).In contrast, GraphCert enables compact open-source LLMs to generate executable supervision and improve through self-training as a more private, cost-effective solution.Source: Related Work · p. 2

Methodology

GraphCert bootstraps graph-agent training by generating graph-grounded QA candidates, certifying their evidence, and using canonical evidence rubrics to supervise Solver post-training alongside answer correctness. Its pipeline combines Quizzer generation, evidence certification, independent Solver exploration, and GRPO optimization.

Methodology

  • GraphCert generates graph-grounded QA candidates, certifies their evidence, and uses canonical evidence rubrics to augment Solver training alongside answer correctness.The pipeline comprises a Bootstrapped Graph Quizzer, Executable Verification, and evidence-derived Solver training; generation rubrics guide Quizzer exploration, while certified rubrics evaluate Solver evidence.Source: Methodology · pp. 2–3, Figure 1 · p. 3

Problem Formulation

  • The problem is question answering over a labeled property graph, with the Solver policy producing a multi-turn interaction trace and an answer grounded against an execution reference.The graph schema specifies node and edge labels, properties, directions, and endpoint constraints.Source: Problem Formulation · p. 3

Bootstrapped Graph Quizzer

  • The Quizzer uses soft generation controls to create diverse QA pairs, records executed Cypher support, and marks evidence for certification.Controls specify answer type, difficulty, question structure, match family, and return family; the Quizzer uses schema inspection and read-only querying, while its candidate certificate records query provenance and must match the execution-grounded answer. The approach follows GraphScout (Ying et al. 2026b) and uses CypherBench-inspired (Feng, Papicchio, and Rahman 2025) controls.Source: Bootstrapped Graph Quizzer · p. 3

Certified Evidence Rubrics

  • Candidates enter the certified training set only after execution checks and semantic review; accepted evidence is canonicalized into executable rubrics for Solver supervision.Execution certification replays marked queries and checks provenance, schema use, safety, and answer grounding; a rubric-guided local-model judge reviews whether evidence semantically supports the QA pair.Source: Certified Evidence Rubrics · pp. 3–4

Graph Solver with Recorded Evidence

  • The Solver independently explores the graph, predicts an answer, and marks supporting results without access to the Quizzer’s gold evidence or certified rubric.Its marked evidence is converted to the same canonical rubric representation, enabling structural comparison with the certified rubric.Source: Graph Solver with Recorded Evidence · p. 4

Certified Rubric-Augmented Reward

  • The rollout reward combines answer F1 with weighted evidence alignment, while answer correctness remains primary and a fully correct answer receives reward 1 regardless of evidence.Evidence can provide additional training signal for incorrect answers, but the evidence weight bounds the reward obtainable from evidence alone.Source: Certified Rubric-Augmented Reward · pp. 4–5
  • Evidence alignment compares canonical query structures through weighted structural scores and one-to-one query matching, while pooled feature coverage can credit equivalent query decompositions.Structural comparisons cover graph shape, return contract, operations, and match/return families; pooled coverage tolerates one-to-many or many-to-one decompositions.Source: Certified Rubric-Augmented Reward · p. 4

GRPO Optimization

  • GRPO trains on certified examples by group-normalizing trajectory rewards, applying clipped policy updates, and adding reference-policy KL regularization.The group-normalized trajectory advantage is broadcast across valid response tokens.Source: GRPO Optimization · p. 5

Experiments

The experiments assess GraphCert’s overall effectiveness, its certification and rubric-guided reward mechanisms, and compact-Quizzer training and cross-domain transfer.

Experimental Setup

  • GRBENCH contains 1,740 questions across five domains and ten graphs ranging from approximately 47K to 84M nodes, evaluated with token-level F1 and QwenScore.Qwen3-4B-Instruct-2507 served as both Quizzer and Solver initialization; training used GRPO for up to 400 steps.Source: Experimental Setup · p. 5

RQ2: Certification and Reward Effectiveness

  • Certification rejects 36.03% of Healthcare candidates and 35.40% of Literature candidates, with schema-direction errors dominating Healthcare failures and answer-evidence inconsistencies dominating Literature failures.It identifies 662 of 3,126 Healthcare candidates and 446 of 3,096 Literature candidates as hard failures, exposing substantial noise in compact-Quizzer supervision.Source: RQ2: Certification and Reward… · pp. 5–6, Table 2 · p. 6

RQ1: Overall Effectiveness

  • GraphCert achieves the best F1 in all five domains and the best QwenScore in four, outperforming larger prompting systems and matched GraphScout(4B).On Academic, its QwenScore is 0.006 below DeepSeek-V3.2-based GraphCounselor while its F1 remains highest; it also improves both metrics over its untrained Solver in every domain.Source: RQ1: Overall Effectiveness · p. 5, Table 1 · p. 6

RQ2: Certification and Reward Effectiveness

  • 32.0–44.0 percentage-point gains across QA-quality dimensions raised strict grounding from 36.7% to 71.0% for GraphCert-retained examples.A blinded judge assessed execution-trace support, evidence sufficiency, and question consistency; the authors note its conservative criteria may reject some valid examples, while applying the same criteria to both methods.Source: RQ2: Certification and Reward… · p. 6, Table 3 · p. 6
  • Removing certification degraded F1 across Healthcare and Literature, while removing evidence-based rewards also reduced performance, particularly on Healthcare.The controlled variants used the same training-data size and optimization budget; the findings indicate that verified supervision and evidence rewards each contribute to Solver performance.Source: Table 4 · p. 6, RQ2: Certification and Reward… · p. 7

RQ3: Compact Self-Training and Transfer

  • With the same Qwen3-4B Quizzer, GraphCert outperforms GraphScout(4B) and even strong-Quizzer GraphScout on both Literature and E-Commerce.Replacing DeepSeek-V3.2 with Qwen3-4B as GraphScout’s Quizzer consistently degrades its performance, indicating greater sensitivity to supervision-generator capability than GraphCert.Source: RQ3: Compact Self-Training and Transfer · p. 7, Table 5 · p. 7
  • GraphCert’s policy transfers across all five domains, though performance varies by domain pair; scaling to Qwen3-8B improves Literature slightly but degrades Healthcare.Strong off-domain results across training domains suggest reusable graph-reasoning behaviors rather than reliance on a single schema, while the scaling comparison uses the full certified method.Source: RQ3: Compact Self-Training and Transfer · p. 7, Table 6 · p. 7, Table 7 · p. 7

Conclusion

GraphCert trains compact graph agents to generate graph-grounded QA pairs, certify evidence, and derive Solver-supervision rubrics. Across five GRBENCH domains, it outperforms prompting-based and self-training baselines, with studies confirming benefits from certification, rubric-augmented rewards, and cross-domain generalization.

Conclusion

  • Across five GRBENCH domains, GraphCert consistently outperforms strong prompting-based and self-training baselines.The conclusion presents GraphCert as an effective approach to training compact graph agents without external teacher models.Source: Conclusion · pp. 7–8
  • GraphCert enables compact LLMs to generate graph-grounded QA pairs, certify supporting evidence, and derive evidence rubrics for Solver supervision.Source: Conclusion · p. 7
  • Ablation and transfer studies confirm the benefits of certification, rubric-augmented reward, and cross-domain generalization.Source: Conclusion · p. 8

Quizzer Exploration Settings

The Quizzer uses five complementary controls to guide diverse graph-grounded task generation, while compatibility constraints and certification determine which candidates are retained.

Quizzer Exploration Settings

  • Quizzer exploration and initial candidate generation use temperature 0.7, while evidence-code retries and evidence-grounded QA regeneration are ordinary agent self-correction.Source: Quizzer Exploration Settings · p. 9
  • Candidates are discarded if any entity in their question, answer, or marked evidence appears in an official test question, preventing test-set leakage.Source: Quizzer Exploration Settings · p. 9
  • Five complementary controls specify answer type, query pattern, difficulty, match family, and return family, drawing on GraphScout (Ying etal. 2026b) and CypherBench (Feng, Papicchio, and Rahman 2025).Answer type constrains return family, query pattern constrains match family, and difficulty constrains both; controls guide generation but are not verified labels.Source: Quizzer Exploration Settings · p. 9
  • Valid settings intersect query-pattern and difficulty constraints on match families, and answer-type and difficulty constraints on return families, preventing incompatible combinations.For example, the construction avoids assigning a shortest-path objective to a simple entity lookup or requesting a Boolean return for a set-valued answer.Source: Quizzer Exploration Settings · p. 9
  • Sampled controls are soft generation targets: candidates adapt to local graph context but are retained only after marked Cypher evidence passes execution certification and semantic curation.The controls do not themselves verify the finished question, answer, or evidence.Source: Quizzer Exploration Settings · p. 9

Data Backend, Prompts, and Tool Interfaces

The section specifies a graph-preserving Neo4j backend and separate Quizzer and Solver protocols, with typed graph access and explicit evidence-marking constraints.

Dataset Definition and Preprocessing

  • The original GRBENCH graphs are imported into Neo4j with their semantics, identifiers, typed directed schemas, constraints, properties, and domain labels preserved.Schema and property metadata support Cypher access and textual entity retrieval; preprocessing changes access, not graph facts or benchmark questions.Source: Dataset Definition and Preprocessing · p. 9

Quizzer Protocol

  • Quizzer prompts combine an invariant interaction protocol with runtime guidance for sampled controls and domain terminology, plus a seed node, its neighborhood, schema, and round budget.Graph-specific entities and relations enter through runtime context rather than fixed few-shot examples.Source: Quizzer Protocol · p. 9
  • Quizzer’s five soft generation controls specify answer form, question structure, graph-access structure, return semantics, and intended complexity.They are generation targets, not verified labels.Source: Table 8 · p. 10
  • Quizzer fixes a candidate QA before marking only direct traced query results, checks answer agreement and complete marking, and allows one repair-and-re-execution opportunity.Each exploration turn invokes exactly one schema-selection or code action; failed turns are rolled back.Source: Quizzer Protocol · p. 10
  • Quizzer exploration probes are not automatically gold evidence, and prompts withhold test-side answers and templates as well as downstream verifier, Judge, Solver, and reward information.Evidence marking becomes available only after the candidate QA is fixed.Source: Quizzer Protocol · p. 10

Solver Protocol

  • Solver resolves ambiguous mentions with node retrieval, queries the typed graph through sandboxed code, marks direct TracedResults, and submits an answer in the required format.Its schema-derived prompt supplies tool signatures and answer rules but withholds Quizzer evidence, the certified rubric, reference answer, verifier status, and reward.Source: Solver Protocol · p. 11

Certification and Semantic Curation

GraphCert treats generated QA pairs and marked support as candidate certificates, not trusted supervision: deterministic execution certification and rubric-guided semantic curation are required before admission to Dcert.

Certification and Semantic Curation

Certificate Format

  • Only immutable traced query results can be marked as evidence, and certification requires synchronized artifact, query, and evidence identities plus a recoverable execution-grounded answer.Marked queries retain at most 200 rows; truncated results cannot certify complete sets, exact counts, or other full-result claims.Source: Certificate Format · p. 11

Execution Certification Rules

  • Execution certification checks format, provenance, and safety; schema and Cypher validity; independent query replay; and answer grounding and evidence completeness.Replay or execution errors, timeouts, hash or truncation mismatches, unsafe queries, and invalid provenance are hard failures.Source: Execution Certification Rules · pp. 11–12

Program-Level Certification Outcomes

  • Certification yields strict, partial, or hard-failure statuses: partial preserves all hard gates but leaves allowlisted uncertainty, and neither judgeable status bypasses semantic curation.Strict requires established evidence completeness and direct grounding; hard failures include execution, safety, provenance, or answer-evidence violations.Source: Program-Level Certification Outcomes · p. 12

Semantic Curation Protocol

  • A local model performs two-stage rubric-guided semantic review without human admission review, and only an accept verdict enters the certified training set.Review audits evidence sufficiency and claim coverage, specificity, modifiers, relation verbalization, quantifier scope, entity and path grounding, answer scope, and unsupported claims; uncertain infrastructure failures are excluded from the rejection count.Source: Semantic Curation Protocol · p. 12

Evidence-Score Component Definitions

This section defines reproducible evidence-score components, including multiplicity-aware feature matching, weighted pairwise and aggregate coverage, and fixed implementation settings.

Multiplicity-aware feature F1

  • MF1 counts overlapping feature multiplicities, is invariant to ordering under deterministic serialization, equals 1 for two empty multisets, and is 0 when only one is empty.Overlap sums the smaller multiplicity of each feature in the two multisets.Source: Evidence-Score Component Definitions · p. 12

Pair-score components

  • Pair scores weight graph shape 0.55, return contract 0.25, active operations 0.15, and match/return families 0.05; directed patterns and participating nodes contribute 0.44 and 0.11.All components lie in [0, 1], and a failed or empty static derivation sets the complete pair score to zero.Source: Evidence-Score Component Definitions · p. 13

Aggregate-score components

  • Aggregate coverage weights relation types 0.25, directed patterns 0.35, pooled node/property coverage 0.20, and return requirements 0.20.Pooled node/property coverage weights nodes 0.60 and properties 0.40; failed derivations are excluded, and either side lacking a valid derivation yields zero.Source: Evidence-Score Component Definitions · p. 13

Implementation settings

  • Implementation fixes η = 0.70 and λ = 0.10, uses maximum-weight one-to-one matching, and scores only explicitly marked queries.An empty marked query set makes the evidence score zero; an unparseable final answer makes the rollout reward zero.Source: Evidence-Score Component Definitions · p. 13

Experimental Details and Additional Analyses

The section specifies GraphCert’s training and comparison setup, then analyzes token use, difficulty-stratified performance, partial-certificate coverage, and Healthcare benchmark sensitivity.

GRPO Hyperparameters

  • Each domain-specific model trains on 2,000 certified examples for 400 steps, sampling eight Solver trajectories per prompt at temperature 1.0.GRPO is implemented with verl, with evidence mixture weight η=0.70 and reward weight λ=0.10; training also uses gradient checkpointing, padding removal, sample packing, dynamic batching, and Flash Attention.Source: GRPO Hyperparameters · p. 13

Computational Resources

  • Domain-specific training and evaluation use the 4B server configuration unless otherwise specified; the 8B configuration is reserved for model-scaling experiments.The experiments use separate Linux-server configurations for 4B and 8B models.Source: Computational Resources · p. 13, Table 10 · p. 13

Baseline Details

  • The baseline suite spans parametric-only answering, passive text retrieval, two-hop graph retrieval, and executable Cypher queries.BaseLLM receives only the question; TextRAG (Gao et al. 2024) retrieves linearized text chunks, GraphRAG (Ye et al. 2024) expands two-hop neighborhoods, and Cypher generates and executes a graph query for answer synthesis.Source: Baseline Details · p. 14
  • Other baselines use iterative traversal, adaptive graph exploration, multi-agent collaboration, or graph-grounded post-training.GraphCoT (Jin et al. 2024) interleaves reasoning with graph operations; PolyG (Liu et al. 2025) adapts traversal paths; GraphCounselor (Gao et al. 2025) coordinates planning, execution, and reflection. GraphScout (Ying et al. 2026b) trains with answer-based reward; its 4B controlled variant uses Qwen3-4B-Instruct-2507 for both Quizzer and Solver, while specified published comparisons were not rerun.Source: Baseline Details · p. 14

Token Efficiency

  • GraphCert stays in the same low-token regime as GraphScout(4B) while using substantially fewer tokens than other active graph-reasoning baselines.The comparison covers Healthcare and Literature; its performance therefore does not rely on longer inference traces.Source: Figure 2 · p. 14, Token Efficiency · p. 14

Performance by Question Difficulty

  • GraphCert leads on Easy Literature and Medium Healthcare, is comparable to GraphScout(4B) on Medium Literature, and all methods score zero on Hard Literature.Hard is omitted because Healthcare has no Hard questions; many Hard Literature questions emphasize recommendation-style reasoning and external-world knowledge rather than graph traversal, making that split less diagnostic of graph exploration.Source: Performance by Question Difficulty · p. 14, Figure 3 · p. 15

Accepted Partial Certificates and Coverage

  • Adding accepted partial certificates more than doubled biomedical pair coverage, from 18 to 39, while broadening question-pattern and match-family coverage.The added coverage chiefly recovered comparison, set-equivalence, conjunction, shared-intermediate, Boolean, and multi-query problems; the gain persisted under sample-size matching and a target-aligned-only comparison. Retained partials passed replay and semantic curation, but their Python-composition lineage was not statically proven.Source: Accepted Partial Certificates and… · p. 15, Figure 4 · p. 15, Figure 5 · p. 15

Healthcare Benchmark Sensitivity

  • A schema-grounded review flagged 56 of 270 Healthcare questions, mostly for reversing directed relations or equating symptom sets where the reference uses containment.Excluding them changes GraphCert from 0.744/0.722 to 0.835/0.802 QwenScore/F1 on 214 questions; this score is not used for ranking because baselines were not reevaluated.Source: Healthcare Benchmark Sensitivity · p. 15
Loading 2609.38798v1…