Edge-Level Rewards for Graph Generation from a Contrastive Judge

Many systems now train a language model to turn text or images into a graph, for example a knowledge graph whose edges are (subject, relation, object) facts, or a scene graph of objects and how they interact. They train it with reinforcement learning (RL), meaning the model is rewarded for good finished outputs instead of being shown the correct output token by token. The reward is the weak point. It comes either from gold reference graphs, which rarely exist, or from how well a downstream question-answering system performs with the graph. The second kind of reward never checks whether any single edge is true. The edges are also exactly where models fail. They can list the entities in a passage, but they confuse who acts on whom: "cat on the mat" versus "mat on the cat."

We propose to score every generated edge separately, using a language model as a judge, and with no reference graph. The judge does not just ask whether an edge is supported by the source. It must also reject a minimally corrupted version of the same edge, either with subject and object swapped or with the relation replaced by a confusable one. An edge earns reward only if the judge tells it apart from its corruption. Edge-level credit addresses the sparse-reward problem of graph RL. The contrastive test targets the specific relational failure, and it denies the judge its easiest shortcut, which is rubber-stamping any fluent triple.

Core Claim

A reference-free reward assigned per edge, built from a judge's discrimination between an edge and its minimal relational corruption, will train graph generators whose edge precision approaches that of reference-supervised RL. It will also beat both holistic judge scores and downstream-task rewards on edge correctness, and it does so without gold graphs or gold answers. The contrastive term is the claimed active ingredient. Plain per-edge entailment scoring should be measurably worse specifically on direction and relation errors. If it is not, the claim fails, and the experiments are designed to show that.

Prior Work and Where This Sits

The closest RL work is AutoGraph-R1 and R1-SGG. AutoGraph-R1 trains a language model with Group Relative Policy Optimization (GRPO), an RL method that scores each sample against the other samples drawn for the same input. The model builds knowledge graphs, and its reward is whether a frozen retrieval-augmented QA system can answer multi-hop questions from them. This needs gold QA labels and never validates individual edges. It also risks fitting the graph to one retriever's quirks. Compile Scene Graphs with Reinforcement Learning uses GRPO with recall rewards against gold VG150/PSG scene graphs, so it cannot run where gold graphs are absent.

Scene Graph Thinking motivates this proposal most directly. Its authors deliberately rewarded only nodes, through what they call "Node-as-Proxy" rewards, because edge rewards seemed too ambiguous. As a result, relational edges are left to supervised fine-tuning alone. Our proposal is a direct attempt to make edge rewards unambiguous enough to use.

Evidence for the relational gap comes from several sources. EEE-Bench finds that over half of GPT-4o's circuit errors are reasoning failures rather than perception failures. Nouns, Not Modifiers shows a vision-language-action model parsing objects correctly but failing on spatial relations. The relational-network line, including Relation Networks, supplies the design principle we reuse: score each pair independently and sum, so the total does not depend on edge order or graph size. Our reward is a sum of independent per-edge judgments for the same reason.

Three findings constrain the design. JudgeBench shows judges near chance on subtle errors (GPT-4o at 50.86% with vanilla prompting), with judging ability tied to solving ability. We respond by giving the judge the easiest possible task: one triple, one short source span, one corruption. LLMs as Narcissistic Evaluators shows that judges favor their own model family, and more so without references. We therefore use a judge from a different family than the policy and measure self-bias directly. CALVER shows that symbolic checks beat neural judges when formal axioms exist. Our setting has no such axioms, so the contrastive test is our substitute for a hard check.

Two lines of work supply method. Step-level judging in AgentEval and Graph of Verification shows that local, node-by-node judgments beat holistic verdicts: failure recall rises from 0.41 to 0.89 in AgentEval. Both evaluate fixed traces and never train a generator. PARENTing shows that rewards grounded in the source rather than in references reduce hallucination in RL, but its grounding is n-gram overlap, which cannot detect a swapped subject and object.

Research Program

The policy is an instruction-tuned language model that reads a passage $x$ and emits a graph $G$ as a list of triples. For each emitted edge $e=(s,p,o)$ we build corruptions $\tilde e$: the inverted edge $(o,p,s)$, and edges with $p$ replaced by relations a judge rates as confusable. Corruptions the judge says are also supported by the source are dropped; symmetric relations are an example. The judge $J$, from a different model family than the policy, returns the probability that an edge is supported by $x$. We read this from the "yes" token, in the style of UniEval and G-Eval's probability weighting. The edge's verified score is

$$v(e)=J(e\mid x)\,\big(1-\max_{\tilde e} J(\tilde e\mid x)\big),$$

so an edge scores high only if the judge supports it and rejects every corruption.

Precision-only rewards invite a policy that emits a few safe edges. We therefore add a reference-free coverage term $c(G)$: the fraction of source sentences for which the judge answers yes to "does some edge in the graph express this sentence's main relation." The graph reward is

$$R(G)=\frac{1}{|E|}\sum_{e\in E} v(e)\;+\;\lambda\, c(G),$$

where $\lambda$ trades precision against coverage. Credit is assigned per edge. Each edge's tokens receive their own advantage from $v(e)$, centered across the GRPO group, while $c(G)$ is shared across the whole graph. This is how the method attacks the credit-assignment problem that graph-level rewards leave open.

Before any training, a judge-audit phase measures how reliable $J$ is on corrupted edges. We use gold WebNLG triples paired with their texts, and for VG150, gold relations rendered with object crops. The measure is how often the judge accepts the true edge and rejects its inversion. If no affordable judge passes this audit well above chance, the method has no footing and we stop.

Baselines

The naive reference point is the supervised fine-tuned policy with no RL, trained on the same seed extraction data. It shows what RL adds at all. Compile Scene Graphs with Reinforcement Learning reports that supervised fine-tuning alone gives a 39.54% structural failure rate on VG150, so we also report format failures.

The strongest reference-free competitor on knowledge graphs is AutoGraph-R1's knowledge-carrying reward, which we rerun on HotpotQA, 2WikiMultihopQA and Musique. Its reported number is an average QA F1 gain of +4.39 for Qwen-3B (AutoGraph-R1). It uses gold QA labels, which our method does not. It is the strongest because it is the established RL method for this exact task. We will run it with the same policy size, rollout count, GRPO hyperparameter search and number of training steps. Beating it means equal or better downstream QA F1 together with clearly higher judged-and-human edge precision. A version that matches QA F1 while improving edge precision also counts, since our method uses no labels.

The strongest reference-supervised comparison is R1-SGG on VG150, which reports Recall@50 of 19.47% and mean Recall of 11.43% with gold-graph rewards (Compile Scene Graphs with Reinforcement Learning). This is an upper bound rather than a competitor. Recovering most of that recall without gold graphs would be the result. Beating it is not expected.

Two simpler judge-based rewards serve as baselines, both using the same judge model and the same judge-call budget per rollout. The first is a holistic G-Eval–style score for the whole graph (G-Eval). The second is per-edge entailment without corruptions, which is our reward with the contrastive factor removed. The second is the ablation that isolates the key ingredient. A further ablation keeps per-edge rewards but averages them into one graph-level scalar, which separates the value of edge-level credit from the value of edge-level scoring.

Why not just…?

Why not just score the whole graph with a strong judge? This is the cheapest option. JudgeBench and Graph of Verification both indicate that holistic verdicts degrade as the number of items to check grows: Graph of Verification reports holistic F1 falling from 99% to 49% on Number Triangle as depth increases, and AgentEval reports a step-level recall advantage. Our holistic-reward baseline tests whether this degradation carries over to graph rewards. We expect the gap to widen with graph size, and we report results binned by edge count.

Why not just use per-triple entailment scoring like UniEval? This is the real threat. Per-edge entailment already provides local credit, and it may be enough if judges handle direction well. Our hypothesis is that entailment judges accept inverted or relation-swapped triples whose words overlap with the source, much as PARENT's n-gram grounding would. The judge audit measures this directly. The RL ablation then shows whether removing corruptions raises the rate of direction and relation errors in trained graphs. If it does not, we will report that the contrastive term is unnecessary and the contribution reduces to edge-level judge rewards.

Why not just use downstream QA reward as AutoGraph-R1 does? That reward is useful but indirect. A graph can support the benchmark's questions while containing wrong edges the questions never touch, and the reward needs labeled questions. We test both points. First, we measure edge precision of AutoGraph-R1-trained graphs. Second, we swap the frozen retriever at test time, which exposes retriever-specific fitting that our retriever-independent reward should not show.

Why not just distill a teacher's graphs with supervised fine-tuning? Supervised fine-tuning copies the teacher's errors and, per R1-SGG, struggles with format. It is included as a baseline using graphs from the same model used as our judge, which also tests whether the judge's knowledge is better transferred by imitation or by discrimination.

Proposed Experiments

The primary testbed is text-to-knowledge-graph construction. WebNLG serves as the measuring stick: its gold RDF triples are hidden during training and used only for evaluation. We report triple precision and recall, and separately the rate of inverted-direction and wrong-relation errors. The multi-hop RAG corpora from AutoGraph-R1 serve for downstream utility. We found no reported text-to-triple extraction result on WebNLG on Lacuna, so that comparison is internal across our baselines. The secondary testbed is VG150 scene graphs, comparing against the R1-SGG numbers above.

Human annotators label a stratified sample of edges from every system for support and direction. These labels decide outcomes where judged and human scores disagree.

The decisive checks fall into three groups. The first concerns the judge. It must pass the audit, accepting the true edge and rejecting its inversion well above chance. Its scores must agree with the human edge labels, measured by Cohen's κ.

The second concerns the reward. The contrastive reward must cut direction and relation errors relative to plain per-edge entailment at matched coverage. Its policy must match or beat AutoGraph-R1 on QA F1 while having higher human-rated edge precision. Holistic-reward policies should lose ground as graphs grow.

The third concerns robustness. Replacing the judge with one from the policy's own family should inflate judged scores, following the narcissism finding, but not human-rated scores. A gap between judged and human edge precision on held-out data is our measure of reward hacking. We also watch whether the policy drifts toward emitting symmetric or trivially true relations to dodge corruptions, which we track by the distribution of relation types.

If these checks pass, edges, the part of the graph the relational gap is about, become something RL can optimize directly without references. If the ablation shows the contrastive term adds nothing, the field still learns that the edge-reward ambiguity Scene Graph Thinking avoided is tractable with plain per-edge judging.