FlowNeg: GFlowNet-Guided Diverse Hard Negative Sampling for Knowledge Graph Embedding

# GFlowNet-Guided Diverse Hard Negative Samplingfor Knowledge Graph Embedding
Source: [https://arxiv.org/html/2608.23849](https://arxiv.org/html/2608.23849)
Naoshin Anzum HridiAffiliation:Department of Computer Science and Engineering, BRAC University, BangladeshJoyanta Jyoti MondalAffiliation:Department of Computer and Information Sciences, University of Delaware, USACorrespondence:[ishihab@iastate\.edu](mailto:[email protected])

###### Abstract

Negative sampling determines whether a knowledge graph embedding \(KGE\) model learns from informative counterexamples or wastes updates on implausible corruptions\. Uniform negatives are diverse but easy, whereas hard\-negative miners concentrate on few entities and collide more with held\-out positives\. We introduce FlowNeg, a context\-conditioned hierarchical generative flow network that amortizes reward\-proportional sampling without normalizing a composite reward over the entity set: given a positive triple and corruption side, it selects a type, then an entity\. Its terminal reward combines bounded model\-based hardness with a training\-only structural score for held\-out\-positive collision, over a relation\-specific type\-compatible support\. We derive the reward, specialize standard trajectory balance, and bound multiplicatively how residual imbalance perturbs terminal and mode probability\. Across a descriptive five\-seed grid of five architectures and five benchmarks, FlowNeg has higher mean MRR than EMU and than IF\-NS in 24 of 25 cells \(\+0\.0172\+0\.0172and\+0\.0160\+0\.0160on average\)\. A separate 15\-seed FB15k\-237/RotatE control fixing negative count, diagnostic budget, and compute gives FlowNeg0\.359±0\.0010\.359\\pm 0\.001MRR against0\.346±0\.0020\.346\\pm 0\.002for EMU, with near\-uniform fixed\-partition diversity, high gradient informativeness, and low collision\. The evidence supports mode\-covering negative generation without treating structural similarity as an open\-world truth oracle\.

## 1Introduction

A knowledge graph records observed facts as triples\(h,r,t\)\(h,r,t\)but rarely records explicit falsehoods\. Knowledge graph embedding therefore depends on generated negatives: a model learns to score an observed triple above corruptions that replace its head or tail\. Easy negatives quickly yield negligible gradients, whereas extremely hard negatives can be true facts omitted from an incomplete graph\. A useful sampler must find candidates hard enough to train on, broad enough to represent different regions of the entity space, and conservative enough not to treat every plausible unobserved triple as false\.

Current approaches occupy different parts of this trade\-off\. Uniform corruption\([Bordes et al\., 2013](https://arxiv.org/html/2608.23849#bib.bib5)\)covers the entity set but becomes uninformative as training progresses\([Yang et al\., 2024](https://arxiv.org/html/2608.23849#bib.bib32)\)\. Self\-adversarial weighting\([Sun et al\., 2019](https://arxiv.org/html/2608.23849#bib.bib28)\), caches\([Zhang et al\., 2019](https://arxiv.org/html/2608.23849#bib.bib33)\), structural pools\([Ahrabian et al\., 2020](https://arxiv.org/html/2608.23849#bib.bib1)\), and influence\-based selection\([Cai et al\., 2025](https://arxiv.org/html/2608.23849#bib.bib19)\)improve hardness, yet their probability mass can narrow around candidates the model already prefers\. Adversarial and mutation\-based generators\([Cai and Wang, 2018](https://arxiv.org/html/2608.23849#bib.bib7);[Takamoto et al\., 2025](https://arxiv.org/html/2608.23849#bib.bib13)\)likewise target difficulty without explicitly preserving several high\-value regions or discounting likely contamination\. The problem is therefore distributional: training needs useful mass across many hard candidates, not repeated access to a single maximizer\.

Generative flow networks \(GFlowNets\) suit this distributional objective: given a non\-negative reward, a well\-trained GFlowNet targets terminal probability proportional to reward\([Bengio et al\., 2021](https://arxiv.org/html/2608.23849#bib.bib3);[Malkin et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib24)\), so raising one candidate’s reward need not drive every other informative candidate to zero probability\. Constructing this target directly would require repeatedly normalizing the composite reward over the entity set\. FlowNeg instead amortizes it from sampled terminal rewards and a learned context\-dependent normalizer, using a hierarchical policy that selects a relation\-compatible type and then an entity within it\. The terminal reward is

R⁡\(e^∣𝒙\)=\\displaystyle R\(\\hat\{e\}\\mid\\bm\{x\}\)=\{\}aθ​\(e^∣𝒙\)\\displaystyle a\_\{\\theta\}\(\\hat\{e\}\\mid\\bm\{x\}\)\(1\)×\(1−c^HPC​\(e^∣𝒙\)\)​c​\(e^,r,s\),\\displaystyle\\times\\left\(1\-\\widehat\{c\}\_\{\\mathrm\{HPC\}\}\(\\hat\{e\}\\mid\\bm\{x\}\)\\right\)c\(\\hat\{e\},r,s\),where𝒙=\(h,r,t,s\)\\bm\{x\}=\(h,r,t,s\)is the positive triple with corruption sidess; the first two factors encode bounded hardness and structural collision risk, whileccrestricts the terminal support to role\-compatible types rather than reweighting candidates within it\. Full\-context conditioning is essential because the collision score changes with the observed entity being replaced\. FlowNeg alternates sampler updates with ordinary KGE optimization and retains a small uniform component for exploration\.

The paper makes three connected contributions\. Methodologically, it turns negative selection into context\-conditioned reward\-proportional generation with a common proposal interface for embedding models and SimKGC\([Wang et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib31)\)\. Analytically, it derives Equation \([1](https://arxiv.org/html/2608.23849#S1.E1)\) as a conditional open\-world surrogate, separates exact trajectory balance from its approximate\-balance implication, and limits the coverage interpretation to a declared fixed partition\. Empirically, it separates a descriptive five\-seed grid, a 15\-seed matched\-kkmechanism study, and a pre\-specified 15\-seed FlowNeg–Uniform analysis, exposing two small counterexamples while showing that the controlled gain over EMU persists at equal negative count and equal wall\-clock checkpoints\.

## 2Background and Related Work

### 2\.1Negative sampling in KGE

Uniform and type\-constrained corruption\([Bordes et al\., 2013](https://arxiv.org/html/2608.23849#bib.bib5);[Krompass et al\., 2015](https://arxiv.org/html/2608.23849#bib.bib20)\)are inexpensive and diverse but allocate most samples to candidates the model already rejects\. Self\-adversarial training\([Sun et al\., 2019](https://arxiv.org/html/2608.23849#bib.bib28)\)reweights a uniform pool by current scores; NSCaching\([Zhang et al\., 2019](https://arxiv.org/html/2608.23849#bib.bib33)\)and TuckerDNCaching\([Madushanka and Ichise, 2023](https://arxiv.org/html/2608.23849#bib.bib22)\)maintain high\-scoring caches; SANS\([Ahrabian et al\., 2020](https://arxiv.org/html/2608.23849#bib.bib1)\)restricts sampling to graph neighborhoods\. All increase informativeness without controlling how many distinct semantic regions remain represented\.

Learned samplers address hardness more directly\. KBGAN\([Cai and Wang, 2018](https://arxiv.org/html/2608.23849#bib.bib7)\)trains a second KGE model as a generator, inheriting the difficulties of adversarial optimization\([Goodfellow et al\., 2014](https://arxiv.org/html/2608.23849#bib.bib14)\); EMU\([Takamoto et al\., 2025](https://arxiv.org/html/2608.23849#bib.bib13)\)mutates entity embeddings toward a theoretically motivated condition; IF\-NS\([Cai et al\., 2025](https://arxiv.org/html/2608.23849#bib.bib19)\)uses influence estimates to retain useful candidates; Ne\_AnKGE\([Li et al\., 2025](https://arxiv.org/html/2608.23849#bib.bib21)\)uses analogical reasoning\. Negative\-free objectives\([Bahaj and Ghogho, 2024](https://arxiv.org/html/2608.23849#bib.bib2);[Zhang et al\., 2024](https://arxiv.org/html/2608.23849#bib.bib17)\)avoid explicit sampling but treat unobserved triples differently from the open\-world sampling question studied here\. FlowNeg’s distinct choice is to learn a distribution whose mass follows a composite reward rather than to cache, filter, or maximize individual candidates; Appendix[B](https://arxiv.org/html/2608.23849#A2)gives a mechanism\-level comparison\.

### 2\.2Reward\-proportional generation

GFlowNets learn stochastic construction policies for discrete objects with terminal probability proportional to a non\-negative reward\([Bengio et al\., 2021](https://arxiv.org/html/2608.23849#bib.bib3);[Bengio et al\., 2023](https://arxiv.org/html/2608.23849#bib.bib4)\); objectives include flow matching, detailed balance, and trajectory balance\([Malkin et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib24)\), with applications in molecular design, causal discovery, and discrete probabilistic modeling\([Deleu et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib10);[Deleu et al\., 2023](https://arxiv.org/html/2608.23849#bib.bib11);[Zhang et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib34);[Zhang et al\., 2023](https://arxiv.org/html/2608.23849#bib.bib35)\)\. Their relevance here is narrower than a general claim that GFlowNets prevent collapse: if trajectory balance is learned accurately and several regions carry reward mass, the target preserves those regions\. In FlowNeg’s two\-stage tree the benefit over direct reward normalization is amortization, since policies are updated from sampled terminal rewards without rescoring the composite reward for every entity on every KGE step\. This complements work on negative quality in contrastive representation learning\([Chen et al\., 2020](https://arxiv.org/html/2608.23849#bib.bib8);[He et al\., 2020](https://arxiv.org/html/2608.23849#bib.bib15);[Chuang et al\., 2020](https://arxiv.org/html/2608.23849#bib.bib9);[Robinson et al\., 2021](https://arxiv.org/html/2608.23849#bib.bib26)\), where candidate objects and supervision structure differ from discrete KGE corruption\.

## 3FlowNeg

Let𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\)be a knowledge graph with training triples𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}, and letfθ​\(h,r,t\)f\_\{\\theta\}\(h,r,t\)be any differentiable KGE score\. A relation\-specific Bernoulli rule chooses the corruption sides∈\{𝚑𝚎𝚊𝚍,𝚝𝚊𝚒𝚕\}s\\in\\\{\\mathtt\{head\},\\mathtt\{tail\}\\\}; training then sampleskkreplacements from a proposalqqand minimizes, for tail corruption,

ℒKGE​\(𝜽,q\)=\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{KGE\}\}\(\\bm\{\\theta\};q\)=\{\}−log⁡σ⁡\(fθ​\(h,r,t\)\)\\displaystyle\-\\log\\sigma\(f\_\{\\theta\}\(h,r,t\)\)\(2\)−1k∑i=1klogσ\(−fθ\(h,r,e^i\)\)\.\\displaystyle\-\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\log\\sigma\(\-f\_\{\\theta\}\(h,r,\\hat\{e\}\_\{i\}\)\)\.withe^i∼q\(⋅∣𝒙\)\\hat\{e\}\_\{i\}\\sim q\(\\cdot\\mid\\bm\{x\}\)and𝒙=\(h,r,t,s\)\\bm\{x\}=\(h,r,t,s\)the full positive context\. Head corruption replacesfθ​\(h,r,e^i\)f\_\{\\theta\}\(h,r,\\hat\{e\}\_\{i\}\)byfθ​\(e^i,r,t\)f\_\{\\theta\}\(\\hat\{e\}\_\{i\},r,t\)\. FlowNeg changes only this proposal; the score, loss, and side\-selection rule are unchanged\.

positive context𝒙=\(h,r,t,s\)\\bm\{x\}=\(h,r,t,s\)type policyPF​\(τ∣𝒙\)P\_\{F\}\(\\tau\\mid\\bm\{x\}\)entity policyPF​\(e^∣τ,𝒙\)P\_\{F\}\(\\hat\{e\}\\mid\\tau,\\bm\{x\}\)mixed proposal\(1−α\)​πϕ\+α​qunif\(1\-\\alpha\)\\pi\_\{\\phi\}\+\\alpha q\_\{\\mathrm\{unif\}\}KGE updateEquation \([2](https://arxiv.org/html/2608.23849#S3.E2)\)terminal rewardhardness×\\timescollision discount×\\timestype

Figure 1:FlowNeg’s training loop\. Both policies and the learned normalizer condition on the full context𝒙\\bm\{x\}; the sampler chooses a type, then an entity, and generated entities are mixed withα=0\.1\\alpha=0\.1uniform exploration\. The KGE is updated every step, whereas the GFlowNet is updated once perm=5m=5KGE steps after aW=50W=50epoch warm\-up\.### 3\.1Hierarchical generation

Direct normalization of the composite reward over all entities would require repeatedly scoring every replacement\. FlowNeg instead decomposes a draw into two learned decisions\. Let𝒛𝒙=\[𝒆h;𝒆r;𝒆t;𝒆s\]\\bm\{z\}\_\{\\bm\{x\}\}=\[\\bm\{e\}\_\{h\};\\bm\{e\}\_\{r\};\\bm\{e\}\_\{t\};\\bm\{e\}\_\{s\}\], where𝒆s\\bm\{e\}\_\{s\}is a learned corruption\-side embedding\. A type policy first selects a role\-compatible partitionτ\\tau: a two\-layer network maps𝒛𝒙\\bm\{z\}\_\{\\bm\{x\}\}to type logits, andPF​\(τ∣𝒙\)P\_\{F\}\(\\tau\\mid\\bm\{x\}\)is their softmax restricted to𝒜rs\\mathcal\{A\}\_\{r\}^\{s\}, the partitions observed in the corresponding domain or range of relationrrin𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}\(Appendix[A](https://arxiv.org/html/2608.23849#A1)\)\. Conditioned onτ\\tau, a cross\-attention policy selects an entity fromℰτ\\mathcal\{E\}\_\{\\tau\}:

𝒒𝒙\\displaystyle\\bm\{q\}\_\{\\bm\{x\}\}=𝑾q​𝒛𝒙,\\displaystyle=\\bm\{W\}\_\{q\}\\bm\{z\}\_\{\\bm\{x\}\},𝒌e\\displaystyle\\bm\{k\}\_\{e\}=𝑾k​𝒆e,\\displaystyle=\\bm\{W\}\_\{k\}\\bm\{e\}\_\{e\},\(3\)ae\\displaystyle a\_\{e\}=𝒒𝒙⊤​𝒌e/dk,\\displaystyle=\\bm\{q\}\_\{\\bm\{x\}\}^\{\\top\}\\bm\{k\}\_\{e\}/\\sqrt\{d\_\{k\}\},PF​\(e^∣τ,𝒙\)\\displaystyle P\_\{F\}\(\\hat\{e\}\\mid\\tau,\\bm\{x\}\)=exp⁡\(ae^\)∑e∈ℰτexp⁡\(ae\)\.\\displaystyle=\\frac\{\\exp\(a\_\{\\hat\{e\}\}\)\}\{\\sum\_\{e\\in\\mathcal\{E\}\_\{\\tau\}\}\\exp\(a\_\{e\}\)\}\.Schema types are used when available; otherwise entities are partitioned once bykk\-means intoK=50K=50types over embeddings trained only on𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}, and the partition and sets𝒜rs\\mathcal\{A\}\_\{r\}^\{s\}are then frozen\. Each entity has one parent partition, so its backward path is deterministic\. An optional Stage 3 refinement for coarse types \(Appendix[A](https://arxiv.org/html/2608.23849#A1)\) is not used in the headline experiments\.

The hierarchy reduces reward enumeration rather than making selection constant time: Equation \([3](https://arxiv.org/html/2608.23849#S3.E3)\) still normalizes logits within the selected partition\. Unlike direct reward matching, it evaluates the changing KGE and structural reward only at sampled terminals and learns the context\-dependent partition functionZϕ​\(𝒙\)Z\_\{\\phi\}\(\\bm\{x\}\)\.

For SimKGC, FlowNeg reads the cached entity table already consumed by the scoring module and substitutes a sampled identifier for a uniformly proposed one in the existing contrastive objective\. Neither the language encoder nor the scoring architecture changes: the cross\-architecture claim concerns a shared proposal interface\.

### 3\.2Hardness, collision discount, and type support

The hardness factor is a bounded score, not a calibrated truth probability:aθ​\(e^∣𝒙\)=σ⁡\(fθ​\(h,r,e^\)\)a\_\{\\theta\}\(\\hat\{e\}\\mid\\bm\{x\}\)=\\sigma\(f\_\{\\theta\}\(h,r,\\hat\{e\}\)\)for tail corruption andσ⁡\(fθ​\(e^,r,t\)\)\\sigma\(f\_\{\\theta\}\(\\hat\{e\},r,t\)\)for head corruption\. The collision score uses role\-conditioned neighborhoods built only from training triples,𝒩r𝚝𝚊𝚒𝚕​\(e\)=\{h′:\(h′,r,e\)∈𝒯tr\}\\mathcal\{N\}\_\{r\}^\{\\mathtt\{tail\}\}\(e\)=\\\{h^\{\\prime\}:\(h^\{\\prime\},r,e\)\\in\\mathcal\{T\}\_\{\\mathrm\{tr\}\}\\\}and𝒩r𝚑𝚎𝚊𝚍​\(e\)=\{t′:\(e,r,t′\)∈𝒯tr\}\\mathcal\{N\}\_\{r\}^\{\\mathtt\{head\}\}\(e\)=\\\{t^\{\\prime\}:\(e,r,t^\{\\prime\}\)\\in\\mathcal\{T\}\_\{\\mathrm\{tr\}\}\\\}\. Writingy𝚝𝚊𝚒𝚕=ty\_\{\\mathtt\{tail\}\}=tandy𝚑𝚎𝚊𝚍=hy\_\{\\mathtt\{head\}\}=h, FlowNeg computes

c^HPC​\(e^∣𝒙\)=\|𝒩rs​\(e^\)∩𝒩rs​\(ys\)\|\|𝒩rs​\(e^\)∪𝒩rs​\(ys\)\|\+ϵ\.\\widehat\{c\}\_\{\\mathrm\{HPC\}\}\(\\hat\{e\}\\mid\\bm\{x\}\)=\\frac\{\|\\mathcal\{N\}\_\{r\}^\{s\}\(\\hat\{e\}\)\\cap\\mathcal\{N\}\_\{r\}^\{s\}\(y\_\{s\}\)\|\}\{\|\\mathcal\{N\}\_\{r\}^\{s\}\(\\hat\{e\}\)\\cup\\mathcal\{N\}\_\{r\}^\{s\}\(y\_\{s\}\)\|\+\\epsilon\}\.\(4\)This Jaccard score discounts candidates structurally similar to the observed entity in the same relation role\. It is evaluated only as a predictor of collision with known validation or test positives, not as a probability that every unobserved triple is true\. Finally,c\(e^,r,s\)=𝟏\[τ\(e^\)∈𝒜rs\]c\(\\hat\{e\},r,s\)=\\mathbf\{1\}\[\\tau\(\\hat\{e\}\)\\in\\mathcal\{A\}\_\{r\}^\{s\}\]records role\-specific support; type\-invalid candidates are never traversed, soc=1c=1at every sampled terminal\. The additiveϵ\\epsilonkeepsc^HPC<1\\widehat\{c\}\_\{\\mathrm\{HPC\}\}<1and the sigmoid keeps hardness positive, so the logarithm in trajectory balance is well defined\. An exponential moving average rescales rewards without changing their within\-context proportions\.

### 3\.3Alternating optimization

For a complete trajectoryτ=\(s0,…,e^\)\\tau=\(s\_\{0\},\\ldots,\\hat\{e\}\)under context𝒙\\bm\{x\}, FlowNeg uses trajectory balance\([Malkin et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib24)\):

ℒTB​\(τ\)=\[log⁡Zϕ​\(𝒙\)​∏ℓPF​\(sℓ∣sℓ−1,𝒙;ϕ\)R⁡\(e^∣𝒙\)​∏ℓPB​\(sℓ−1∣sℓ,𝒙;ϕ\)\]2\.\\mathcal\{L\}\_\{\\mathrm\{TB\}\}\(\\tau\)=\\left\[\\log\\frac\{Z\_\{\\phi\}\(\\bm\{x\}\)\\prod\_\{\\ell\}P\_\{F\}\(s\_\{\\ell\}\\mid s\_\{\\ell\-1\},\\bm\{x\};\\phi\)\}\{R\(\\hat\{e\}\\mid\\bm\{x\}\)\\prod\_\{\\ell\}P\_\{B\}\(s\_\{\\ell\-1\}\\mid s\_\{\\ell\},\\bm\{x\};\\phi\)\}\\right\]^\{2\}\.\(5\)The context\-dependent normalizer is necessary because hardness and collision discount both change across positive triples\. AfterW=50W=50warm\-up epochs with uniform negatives, joint training drawsk=256k=256final negatives per positive fromqmix=\(1−α\)​πϕ\+α​qunifq\_\{\\mathrm\{mix\}\}=\(1\-\\alpha\)\\pi\_\{\\phi\}\+\\alpha q\_\{\\mathrm\{unif\}\}withα=0\.1\\alpha=0\.1and updates the GFlowNet once everym=5m=5KGE steps; trajectory\-balance gradients stop at the KGE scores\. Herequnifq\_\{\\mathrm\{unif\}\}is uniform over type\-valid entities, not over all ofℰ\\mathcal\{E\}as in the Uniform baseline\. Appendix[A](https://arxiv.org/html/2608.23849#A1)gives the complete procedure and per\-step complexity\.

## 4Analysis and Scope

The analysis has a deliberately limited purpose: it makes the reward and intended sampling behavior auditable\. It does not establish global convergence for a neural GFlowNet, nor turn the neighborhood proxy into an oracle for open\-world truth\.

#### Full\-context conditioning is implemented, not just notated\.

Both policies and the learned normalizer consume one immutable context record𝒙=\(h,r,t,s\)\\bm\{x\}=\(h,r,t,s\)with𝒛𝒙=\[𝒆h;𝒆r;𝒆t;𝒆s\]\\bm\{z\}\_\{\\bm\{x\}\}=\[\\bm\{e\}\_\{h\};\\bm\{e\}\_\{r\};\\bm\{e\}\_\{t\};\\bm\{e\}\_\{s\}\], and every sampler cache is keyed by the same four\-tuple; nothing is cached under\(h,r\)\(h,r\)alone\. This matters whenever a relation admits several observed heads or tails, since the collision discount \(and hence the reward\) changes with the entity being replaced\. An automated audit over10,00010\{,\}000context pairs and1,0001\{,\}000batches confirms full reachability, nonzero trajectory\-balance gradients at all four embeddings, zero cache aliasing, and zero validation/test leakage\. A negative control that omits the replaced entity from the policies andZϕZ\_\{\\phi\}raises the held\-out mean\|δTB\|\|\\delta\_\{\\mathrm\{TB\}\}\|from0\.0610\.061to0\.1940\.194and drops MRR from0\.3590\.359to0\.3510\.351on FB15k\-237/RotatE\. Held\-out residuals are small across datasets, a diagnostic of approximate balance rather than a certificate of the uniform residual condition in Corollary[4\.3](https://arxiv.org/html/2608.23849#S4.Thmtheorem3)\. Appendix[F](https://arxiv.org/html/2608.23849#A6)gives the audit counts, output\-sensitivity rates, residual quantiles, and negative\-control table\.

###### Proposition 4\.1\(Reward\-design surrogate\)\.

Fix a context𝐱\\bm\{x\}and its type\-compatible candidates\. Under bounded candidate\-level gradient\-norm variation, first\-order informativeness taken proportional toaθ​\(e∣𝐱\)a\_\{\\theta\}\(e\\mid\\bm\{x\}\), and no useful contribution from a candidate that is a true but unobserved fact, an event of probabilityptrue​\(e∣𝐱\)p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)\(assumptions \(A1\)–\(A3\), Appendix[C](https://arxiv.org/html/2608.23849#A3)\), the expected useful candidate score iss⁡\(e∣𝐱\)∝aθ​\(e∣𝐱\)​\(1−ptrue​\(e∣𝐱\)\)s\(e\\mid\\bm\{x\}\)\\propto a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\\bigl\(1\-p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)\\bigr\)\. Substituting the structural collision scorec^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}for the unavailable truth probability and restricting support withc⁡\(e,r,s\)c\(e,r,s\)yields Equation \([1](https://arxiv.org/html/2608.23849#S1.E1)\)\.

Assumption \(A2\) is a modeling choice, not a derived fact: a merely monotone relationship would leave the reward undetermined\. The result is a transparent design criterion, not an unconditional variance\-optimal proposal and not evidence thatc^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}is an open\-world probability\. Once the reward is fixed, the target distribution follows from a standard GFlowNet result rather than a new KGE\-specific theorem\.

###### Proposition 4\.2\(Trajectory\-balance target\)\.

For a fixed context𝐱\\bm\{x\}, if the forward and backward policies satisfy trajectory balance exactly for every complete trajectory ending atee, thenπϕ​\(e∣𝐱\)=ρR​\(e∣𝐱\):=R⁡\(e∣𝐱\)/∑e′R⁡\(e′∣𝐱\)\\pi\_\{\\phi\}\(e\\mid\\bm\{x\}\)=\\rho\_\{R\}\(e\\mid\\bm\{x\}\):=R\(e\\mid\\bm\{x\}\)/\\sum\_\{e^\{\\prime\}\}R\(e^\{\\prime\}\\mid\\bm\{x\}\)over the type\-compatible terminal support\.

Exact balance is an idealization, so the useful question is how residual error propagates\. In the unique\-path two\-stage DAG, suppose the terminal log\-balance residual satisfies\|log⁡\(Zϕ​\(𝒙\)​πϕ​\(e∣𝒙\)/R⁡\(e∣𝒙\)\)\|≤ε\\bigl\|\\log\\bigl\(Z\_\{\\phi\}\(\\bm\{x\}\)\\pi\_\{\\phi\}\(e\\mid\\bm\{x\}\)/R\(e\\mid\\bm\{x\}\)\\bigr\)\\bigr\|\\leq\\varepsilonfor allee\. Normalization then gives a direct robustness statement\.

###### Corollary 4\.3\(Approximate reward tracking\)\.

Under the residual condition above,

e−2​ε≤πϕ​\(e∣𝒙\)ρR​\(e∣𝒙\)≤e2​ε\.e^\{\-2\\varepsilon\}\\leq\\frac\{\\pi\_\{\\phi\}\(e\\mid\\bm\{x\}\)\}\{\\rho\_\{R\}\(e\\mid\\bm\{x\}\)\}\\leq e^\{2\\varepsilon\}\.\(6\)The same multiplicative bounds hold after summing over any fixed mode, andTV⁡\(πϕ,ρR\)≤min⁡\{1,\(e2​ε−1\)/2\}\\operatorname\{TV\}\(\\pi\_\{\\phi\},\\rho\_\{R\}\)\\leq\\min\\\{1,\(e^\{2\\varepsilon\}\-1\)/2\\\}\.

This corollary supplies an audit condition rather than asserting that neural training achieves a small uniform residual\. It characterizesπϕ\\pi\_\{\\phi\}, whereas negatives are drawn fromqmixq\_\{\\mathrm\{mix\}\}; the two differ by at most the mixture rate, sinceTV⁡\(qmix,πϕ\)=α​TV⁡\(qunif,πϕ\)≤α\\operatorname\{TV\}\(q\_\{\\mathrm\{mix\}\},\\pi\_\{\\phi\}\)=\\alpha\\operatorname\{TV\}\(q\_\{\\mathrm\{unif\}\},\\pi\_\{\\phi\}\)\\leq\\alpha\. Its proof is in Appendix[D](https://arxiv.org/html/2608.23849#A4)\.

To describe mode coverage without conflating it with link\-prediction risk, fix a partitionℳ=\{M1,…,MJ\}\\mathcal\{M\}=\\\{M\_\{1\},\\ldots,M\_\{J\}\\\}, letq⁡\(Mj\)=∑e∈Mjq⁡\(e\)q\(M\_\{j\}\)=\\sum\_\{e\\in M\_\{j\}\}q\(e\), and define the mode entropyHℳ\(q\)=−∑j=1Jq\(Mj\)logq\(Mj\)H\_\{\\mathcal\{M\}\}\(q\)=\-\\sum\_\{j=1\}^\{J\}q\(M\_\{j\}\)\\log q\(M\_\{j\}\)and the negative diversity scoreNDS⁡\(q\)=exp⁡\(Hℳ​\(q\)\)\\operatorname\{NDS\}\(q\)=\\exp\(H\_\{\\mathcal\{M\}\}\(q\)\), which ranges from one occupied mode toJJequally weighted modes\. In every comparisonℳ\\mathcal\{M\}is the same training\-only partition, frozen before sampler training and shared by all methods\. NDS constrains only across\-mode spread: a sampler may concentrate arbitrarily within a mode and still score nearJJ, so high NDS is compatible with high per\-candidate hardness\. Because FlowNeg also traverses this hierarchy, NDS measures its intended fixed\-partition behavior, not partition\-independent semantic diversity; entity\-level concentration is reported separately in Appendix[L](https://arxiv.org/html/2608.23849#A12)\.

Two standard consequences follow, both stated in Appendix[D](https://arxiv.org/html/2608.23849#A4)\. Under the exact target, mode mass equals normalized reward mass, so bounded per\-mode reward gives every mode a probability floor degrading only bye−2​εe^\{\-2\\varepsilon\}under Corollary[4\.3](https://arxiv.org/html/2608.23849#S4.Thmtheorem3)\(Lemma[D\.1](https://arxiv.org/html/2608.23849#A4.Thmtheorem1)\)\. A within\-mode Hoeffding union bound \(Remark[D\.2](https://arxiv.org/html/2608.23849#A4.Thmtheorem2)\) explains why tiny mode counts are undesirable, but is not a guarantee for adaptive joint training, does not identify its mode weights with test\-time link\-prediction risk, and does not imply that larger NDS improves MRR\.

The empirical burden is therefore twofold: the sampler should preserve fixed\-partition reward mass at fixed reward and architecture, and this should coincide with better link prediction\. Sections[6\.1](https://arxiv.org/html/2608.23849#S6.SS1)and[6\.3](https://arxiv.org/html/2608.23849#S6.SS3)test these separately; neither NDS nor the concentration argument alone establishes a causal link to MRR\.

## 5Experimental Design

### 5\.1Scope and controlled comparisons

We cross five architectures \(TransE\([Bordes et al\., 2013](https://arxiv.org/html/2608.23849#bib.bib5)\), RotatE\([Sun et al\., 2019](https://arxiv.org/html/2608.23849#bib.bib28)\), ComplEx\([Trouillon et al\., 2016](https://arxiv.org/html/2608.23849#bib.bib30)\), ConvE\([Dettmers et al\., 2018](https://arxiv.org/html/2608.23849#bib.bib12)\), and SimKGC\([Wang et al\., 2022](https://arxiv.org/html/2608.23849#bib.bib31)\)\) with FB15k\-237\([Toutanova and Chen, 2015](https://arxiv.org/html/2608.23849#bib.bib29)\), WN18RR\([Dettmers et al\., 2018](https://arxiv.org/html/2608.23849#bib.bib12)\), YAGO3\-10\([Mahdisoltani et al\., 2015](https://arxiv.org/html/2608.23849#bib.bib23)\), CoDEx\-L\([Safavi and Koutra, 2020](https://arxiv.org/html/2608.23849#bib.bib27)\), and Hetionet\([Himmelstein et al\., 2017](https://arxiv.org/html/2608.23849#bib.bib16)\)\. This grid crosses model with dataset, not sampler with model with dataset; every cell contains FlowNeg, EMU, and IF\-NS\. A controlled FB15k\-237/RotatE study additionally includes Uniform, Self\-Adv, KBGAN, NSCaching, and SANS\.

The matched\-kkstudy makes every method supplyk=256k=256final negatives per positive; methods starting from a larger pool use 1,024 candidates and return 256 outputs, and pool size is not counted as finalkk\. The RotatE architecture, optimizer family, batch construction, maximum epoch, split, evaluator, hardware, software, and 15 evaluation seeds are common across methods\. Each sampler keeps its method\-native configuration, selected by validation MRR on tuning seeds disjoint from the evaluation seeds and frozen before test evaluation; Appendix[G](https://arxiv.org/html/2608.23849#A7)reports the tuning counts\.

All structures FlowNeg uses \(role\-conditioned neighborhoods, type partitions, and relation\-compatible type sets\) and training\-time rejection are computed from𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}alone; validation and test triples enter neither reward construction nor negative generation\. Filtered validation and test ranking removes every known train, validation, or test positive\. A numerical divergence stays attached to its original seed; only a verified infrastructure failure occurring before any validation or test metric is observed is rerun\.

### 5\.2Inference and diagnostics

The broad grid reports mean and standard deviation over five paired seeds and is descriptive: no significance stars, no strongest\-baseline inferential claims, since an exact paired sign\-flip test over five seeds has only252^\{5\}assignments and cannot support the previously statedp<0\.01p<0\.01threshold\. A separate pre\-specified 15\-seed FlowNeg–Uniform check over all 25 cells \(Appendix[J](https://arxiv.org/html/2608.23849#A10)\) is reported as robustness, not as a substitute for inference against EMU or IF\-NS\. The matched\-kkstudy uses 15 paired seeds for every method and exports 256 diagnostic negatives per filtered test query from each frozen final checkpoint\.

Filtered MRR and Hits@\{1,3,10\}\\\{1,3,10\\\}measure link prediction\. NDS is computed per frozen test query from the empirical mode frequencies of that query’sD=256D=256exported replacements, then averaged over common queries and seeds, so unrelated queries cannot create the appearance of within\-query diversity\. The partition is frozen and shared but, as Section[4](https://arxiv.org/html/2608.23849#S4)notes, is not independent of FlowNeg’s hierarchy\.

Held\-out\-positive collision \(HPC\) is the percentage of exported corrupted triples found in𝒯val∪𝒯test\\mathcal\{T\}\_\{\\mathrm\{val\}\}\\cup\\mathcal\{T\}\_\{\\mathrm\{test\}\}, computed after training so it cannot affect optimization; it is a conservative observed\-collision rate, not an estimate of the open\-world false\-negative rate\. Gradient informativeness \(GI\) is the meanℓ2\\ell\_\{2\}norm of the per\-negative loss gradient under frozen RotatE parameters, so it is used only inside the common\-model control\. None of the three substitutes for link\-prediction performance\.

## 6Results

### 6\.1Breadth across models and datasets

Each cell of Table[1](https://arxiv.org/html/2608.23849#S6.T1)reports FlowNeg, EMU, and IF\-NS under the same split, five evaluation seeds, tuning protocol, and checkpoint rule, replacing comparison against a drifting set of printed baselines\.

Table 1:Descriptive test MRR over five paired seeds in the unified model–dataset grid\. Each cell is FlowNeg / EMU / IF\-NS; complete standard deviations and ranking metrics are in Appendix[H](https://arxiv.org/html/2608.23849#A8)\.FlowNeg exceeds EMU in 24 of 25 cells \(mean\+0\.0172\+0\.0172, median\+0\.0180\+0\.0180, range−0\.002\-0\.002to\+0\.028\+0\.028\), the exception being ComplEx/WN18RR, where EMU is higher by0\.0020\.002\. Against IF\-NS it is higher in 24 of 25 cells \(mean\+0\.0160\+0\.0160, median\+0\.0170\+0\.0170, range−0\.001\-0\.001to\+0\.024\+0\.024\), the exception being SimKGC/YAGO3\-10, where IF\-NS is higher by0\.0010\.001\. Reporting these counterexamples matters: the evidence supports broad consistency, not uniform dominance\.

In the separate 15\-seed FlowNeg–Uniform analysis all 25 cell\-level mean differences are positive \(mean\+0\.0395\+0\.0395, median\+0\.0418\+0\.0418, range\+0\.0178\+0\.0178to\+0\.0582\+0\.0582\) and 23 survive Holm correction\. SimKGC/WN18RR and RotatE/WN18RR do not, retaining positive means with unadjusted paired bootstrap intervals that include zero\. Appendix[J](https://arxiv.org/html/2608.23849#A10)records the pre\-specified estimand and decision rule\.

### 6\.215\-seed inference against EMU and IF\-NS

Because the five\-seed grid cannot support inference, we ran a nine\-setting confirmatory panel with1515paired evaluation seeds per setting, disjoint tuning seeds, and1818paired contrasts \(FlowNeg versus EMU and versus IF\-NS in each setting\), using exact two\-sided sign\-flip tests with Holm correction across all1818\. It was fixed before its outcomes were inspected, covers every model family, and deliberately retains both original counterexamples, so it cannot be accused of selecting only favorable cells\.

FlowNeg has a higher mean than EMU in8/98/9settings and than IF\-NS in8/98/9\(one exact tie\), and1616of1818contrasts are positive and Holm\-significant \(Table[2](https://arxiv.org/html/2608.23849#S6.T2)\); all1616sit at the tied minimum attainable value,2/215=0\.0000612/2^\{15\}=0\.000061raw and0\.00110\.0011adjusted\. The two non\-rejections preserve the original counterexamples rather than hiding them: ComplEx/WN18RR is indistinguishable from EMU \(Δ=−0\.001\\Delta=\-0\.001,95%95\\%CI\[−0\.002,\+0\.001\]\[\-0\.002,\+0\.001\]\) and SimKGC/YAGO3\-10 is tied with IF\-NS \(Δ=0\.000\\Delta=0\.000,\[−0\.001,\+0\.001\]\[\-0\.001,\+0\.001\]\)\. Setting\-level mean advantages are\+0\.0171\+0\.0171MRR over EMU and\+0\.0152\+0\.0152over IF\-NS, descriptive summaries of the declared settings rather than averages over exchangeable samples\. Appendix[I](https://arxiv.org/html/2608.23849#A9)gives full per\-setting MRR and paired statistics\.

Table 2:Nine\-setting1515\-seed paired inference;Δ\\DeltaMRR is FlowNeg minus baseline, with wins W out of 15\. The1616contrasts not marked†\\daggerall attain the tied minimum Holm\-adjustedp=0\.0011p=0\.0011\. The two disclosed non\-rejections \(†\\dagger\) are ComplEx/WN18RR versus EMU \(p=0\.292p=0\.292\) and SimKGC/YAGO3\-10 versus IF\-NS \(p=0\.781p=0\.781\)\.
### 6\.3Matched negative count and mechanism

The broad grid establishes scope but cannot attribute the gain to proportional sampling\. Table[3](https://arxiv.org/html/2608.23849#S6.T3)therefore fixes base model, data,k=256k=256, diagnostic export, hardware and software stack, and 15 paired seeds, reporting final\-budget checkpoints rather than the best test result during training\.

Table 3:Matched\-kkFB15k\-237/RotatE control, 15 paired seeds \(mean±\\pms\.d\.\)\. Every method returns 256 training negatives per positive and 256 diagnostic draws per filtered test query\.Against EMU the mean paired MRR difference is\+0\.013\+0\.013with FlowNeg winning all 15 seed pairs, a paired bootstrap 95% interval of\[\+0\.012,\+0\.014\]\[\+0\.012,\+0\.014\], and an exact two\-sided sign\-flip value of2/215=6\.1×10−52/2^\{15\}=6\.1\\times 10^\{\-5\}\. Uniform is marginally more diverse under the fixed partition and collides less, but its GI is0\.130\.13; EMU and IF\-NS are informative but substantially less diverse and collide more often with held\-out positives\. FlowNeg combines NDS45\.745\.7, HPC0\.5%0\.5\\%, and GI0\.900\.90, making the intended trade\-off visible without treating any single diagnostic as sufficient for accuracy\.

The direct intervention replaces trajectory\-balance training with reward\-maximizing RL at fixed reward, architecture, data,kk, and diagnostic budget: MRR falls from0\.3590\.359to0\.3400\.340, NDS from45\.745\.7to9\.89\.8, and HPC rises from0\.5%0\.5\\%to1\.7%1\.7\\%, while GI moves only from0\.900\.90to0\.910\.91\. Because measured hardness is effectively unchanged, this isolates the sampling objective more closely than any cross\-method comparison\. Appendix[K](https://arxiv.org/html/2608.23849#A11)places it beside the reward and architecture interventions from the original five\-seed profile, whose0\.3570\.357FlowNeg reference and the0\.3590\.359controlled result are different declared profiles\.

Removing the collision discount raises HPC by2\.22\.2percentage points while leaving GI high; removing type compatibility reduces fixed\-partition coverage; removing hardness cuts GI from0\.890\.89to0\.180\.18; flat entity selection retains the reward but lowers NDS to31\.231\.2; the candidate\-pool Boltzmann policy is less collapsed than reward\-maximizing RL yet stays below FlowNeg in NDS and MRR\. These interventions do not prove that NDS causes accuracy, but they show that the objective, reward factors, and hierarchy make distinguishable contributions\.

#### Diversity without FlowNeg’s own hierarchy\.

Because NDS reuses the frozen partition that FlowNeg traverses, we repeat the coverage comparison with measures using neither that hierarchy nor its reward \(Appendix[L](https://arxiv.org/html/2608.23849#A12)\)\. On FB15k\-237/RotatE, FlowNeg reaches independent NDS43\.843\.8, unique\-entity ratio0\.7920\.792, and entity effective support173\.6173\.6, versus20\.6/0\.384/73\.820\.6/0\.384/73\.8for EMU and24\.2/0\.428/84\.924\.2/0\.428/84\.9for IF\-NS, with Uniform most diverse at46\.9/0\.887/204\.846\.9/0\.887/204\.8, exactly as expected\. The same ordering holds in all nine confirmatory settings\. This removes the principal circularity in the original NDS analysis, but does not establish that coverage*causes*the MRR improvement\.

#### The collision score ranks well but is not calibrated\.

Ten\-bin absolute calibration error against the declared observable, collision with known held\-out positives, is0\.0180\.018–0\.0310\.031across the five datasets and0\.0230\.023on FB15k\-237 in the matched\-kkrerun\. A larger study \(2\.562\.56M draws per dataset\) separates discrimination from magnitude: collision is rare \(prevalence0\.350\.35–0\.85%0\.85\\%\), yet the score ranks it well \(AUROC0\.8410\.841–0\.9020\.902, AUPRC14\.814\.8–16\.9×16\.9\\timesthe prevalence baseline\), while the raw Jaccard value systematically*over*predicts, so raw Brier is slightly worse than a prevalence\-only predictor\. We therefore treatc^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}as a conservative training\-time collision\-risk score, not a calibrated open\-world truth probability\. Appendices[M](https://arxiv.org/html/2608.23849#A13)and[N](https://arxiv.org/html/2608.23849#A14)give the binning definition, prevalence, AUROC/AUPRC, Brier/ECE, and the full reliability bins\.

### 6\.4Equal wall\-clock checkpoints

Raw run time alone does not say whether a more expensive sampler produces a better model at the same deadline\. Timing starts before method\-specific initialization and covers candidate construction, negative generation, sampler updates, KGE optimization, scheduled validation, and checkpoint I/O; at each budget we evaluate the latest complete checkpoint written by that time, without interpolation or extrapolation\.

On FB15k\-237/RotatE over 15 paired seeds, FlowNeg’s final\-checkpoint MRR at 2\.1, 3\.4, and 4\.2 hours is0\.3370\.337,0\.3530\.353, and0\.3590\.359, ahead of the strongest baseline checkpoint available at each budget by\+0\.004\+0\.004,\+0\.008\+0\.008, and\+0\.013\+0\.013MRR; that baseline is Self\-Adv at 2\.1 hours \(0\.3330\.333\) and EMU at 3\.4 and 4\.2 hours \(0\.3450\.345and0\.3460\.346\)\. This does not mean FlowNeg is faster per optimizer step, only that it reaches the highest MRR at the declared equal\-time checkpoints\. At 4\.2 hours its mean validation\-selected and final\-budget MRR are both0\.3590\.359, an average selection uplift of0\.0000\.000\. Appendix[O](https://arxiv.org/html/2608.23849#A15)gives the full per\-method table at each budget, both final and validation\-selected, together with direct time/VRAM profiles and without aΔ\\DeltaMRR\-per\-hour headline\.

## 7Conclusion

FlowNeg learns a context\-specific distribution over negatives rather than repeatedly searching for an argmax\. Its hierarchy reduces the cost of exploring large entity spaces, its reward exposes the intended balance among hardness, observed collision risk, and type support, and trajectory balance amortizes sampling toward the resulting reward distribution\. The evidence is correspondingly scoped: the five\-seed grid shows broad gains with two disclosed exceptions, the 15\-seed matched\-kkstudy rules out a larger final negative count as the sole explanation, and the GFlowNet\-to\-RL intervention changes fixed\-partition coverage sharply while leaving gradient informativeness nearly constant\. These results support reward\-proportional generation as a practical KGE sampler while leaving open how best to estimate validity in genuinely incomplete graphs and how well the benefit transfers beyond the strongest controlled setting\.

## 8Limitations

FlowNeg adds sampler parameters and computation\. Its structural collision score can fail when relation\-role neighborhoods are sparse or when semantically related entities share no observed edges\. Low HPC cannot prove that generated triples are false, and ECE against held\-out positives can look small when collisions are rare; open\-world validity would require independently verified labels\. The hierarchy depends on schema information or a training\-only embedding partition, so poorly formed clusters can restrict useful candidates\. NDS uses that same frozen partition for every sampler and therefore measures the intended hierarchy\-aligned coverage, not partition\-independent semantic diversity\.

The theoretical statements condition on a fixed context, reward, or partition, whereas the KGE and GFlowNet co\-evolve\. Corollary[4\.3](https://arxiv.org/html/2608.23849#S4.Thmtheorem3)requires a uniform balance\-residual bound; held\-out residual summaries can diagnose but cannot certify that condition\. The tracking discussion in Appendix[E](https://arxiv.org/html/2608.23849#A5)records sufficient local regularity conditions rather than global convergence of a neural GFlowNet\. The candidate\-pool Boltzmann control avoids full reward enumeration but is not an oracle that normalizes the reward over all entities\. Finally, the strongest controlled attribution is on FB15k\-237/RotatE\. The broader grid is descriptive, uses five seeds, and does not reinstate the withdrawn strongest\-baseline significance claim\.

## 9Ethical Considerations

Knowledge graph completion can propagate omissions and biases already present in a graph, especially when generated links are consumed as facts\. FlowNeg should therefore be used as a training sampler rather than as a truth\-verification mechanism\. Biomedical or person\-centric predictions require downstream validation, provenance, and uncertainty\-aware review\. The experiments use established benchmark splits and do not involve human participants or newly collected personal data\.

## References

- Ahrabianet al\.\(2020\)K\. Ahrabian, A\. Feizi, Y\. Sber, F\. Morstatter, and A\. GalstyanStructure aware negative sampling in knowledge graphs\.InEMNLP,Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.6.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1)\.
- Bahaj and Ghogho \(2024\)A\. Bahaj and M\. GhoghoNegative\-sample\-free knowledge graph embedding\.Data Mining and Knowledge Discovery38,pp\. 3590–3620\.Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Bengioet al\.\(2021\)E\. Bengio, M\. Jain, M\. Korablyov, D\. Precup, and Y\. BengioFlow network based generative models for non\-iterative diverse candidate generation\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2608.23849#S1.p3.2),[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Bengioet al\.\(2023\)Y\. Bengio, S\. Lahlou, T\. Deleu, E\. J\. Hu, M\. Tiwari, and E\. BengioGFlowNet foundations\.JMLR24\(210\),pp\. 1–55\.Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Bordeset al\.\(2013\)A\. Bordes, N\. Usunier, A\. Garcia\-Duran, J\. Weston, and O\. YakhnenkoTranslating embeddings for modeling multi\-relational data\.InNeurIPS,Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.2.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Boucheronet al\.\(2013\)S\. Boucheron, G\. Lugosi, and P\. MassartConcentration inequalities: a nonasymptotic theory of independence\.Oxford University Press\.Cited by:[Appendix D](https://arxiv.org/html/2608.23849#A4.p5.1)\.
- Cai and Wang \(2018\)L\. Cai and W\. Y\. WangKBGAN: adversarial learning for knowledge graph embeddings\.InNAACL\-HLT,Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.4.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Caiet al\.\(2025\)M\. Cai, Z\. Deng, and C\. XiongIF\-NS: a new negative sampling framework for knowledge graph embedding using influence function\.Knowledge\-Based Systems315,pp\. 113258\.External Links:[Document](https://dx.doi.org/10.1016/j.knosys.2025.113258)Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.8.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Chenet al\.\(2020\)T\. Chen, S\. Kornblith, M\. Norouzi, and G\. HintonA simple framework for contrastive learning of visual representations\.InICML,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Chuanget al\.\(2020\)C\. Chuang, J\. Robinson, Y\. Lin, A\. Torralba, and S\. JegelkaDebiased contrastive learning\.InNeurIPS,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Deleuet al\.\(2022\)T\. Deleu, A\. Góis, C\. Emezue, M\. Rankawat, S\. Lacoste\-Julien, S\. Bauer, and Y\. BengioBayesian structure learning with generative flow networks\.InUAI,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Deleuet al\.\(2023\)T\. Deleu, M\. Nishikawa\-Toomey, J\. Subramanian, N\. Malkin, L\. Charlin, and Y\. BengioJoint Bayesian inference of graphical structure and parameters with a single generative flow network\.InNeurIPS,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Dettmerset al\.\(2018\)T\. Dettmers, P\. Minervini, P\. Stenetorp, and S\. RiedelConvolutional 2D knowledge graph embeddings\.InAAAI,Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Goodfellowet al\.\(2014\)I\. Goodfellow, J\. Pouget\-Abadie, M\. Mirza, B\. Xu, D\. Warde\-Farley, S\. Ozair, A\. Courville, and Y\. BengioGenerative adversarial nets\.InNeurIPS,Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Heet al\.\(2020\)K\. He, H\. Fan, Y\. Wu, S\. Xie, and R\. GirshickMomentum contrast for unsupervised visual representation learning\.InCVPR,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Himmelsteinet al\.\(2017\)D\. S\. Himmelstein, A\. Lizee, C\. Hessler, L\. Brueggeman, S\. L\. Chen, D\. Hadley, A\. Green, P\. Khankhanian, and S\. E\. BaranziniSystematic integration of biomedical knowledge prioritizes drugs for repurposing\.eLife6,pp\. e26726\.Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Honget al\.\(2023\)M\. Hong, H\. Wai, Z\. Wang, and Z\. YangA two\-timescale stochastic algorithm framework for bilevel optimization: complexity analysis and application to actor\-critic\.SIAM Journal on Optimization33\(1\),pp\. 147–180\.Cited by:[Remark E\.1](https://arxiv.org/html/2608.23849#A5.Thmtheorem1.p1.1)\.
- Krompasset al\.\(2015\)D\. Krompass, S\. Baier, and V\. TrespType\-constrained representation learning in knowledge graphs\.InISWC,Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1)\.
- Liet al\.\(2025\)H\. Li, Y\. Tao, D\. Chen, Y\. Tang, J\. Wang, and L\. XueAn enhanced framework for knowledge graph embedding based on negative sample analogical reasoning\.Scientific Reports15,pp\. 14086\.Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Madushanka and Ichise \(2023\)T\. Madushanka and R\. IchiseTuckerDNCaching: high\-quality negative sampling with Tucker decomposition\.Journal of Intelligent Information Systems61\(3\),pp\. 739–763\.Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1)\.
- Mahdisoltaniet al\.\(2015\)F\. Mahdisoltani, J\. Biega, and F\. M\. SuchanekYAGO3: a knowledge base from multilingual Wikipedias\.InCIDR,Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Malkinet al\.\(2022\)N\. Malkin, M\. Jain, E\. Bengio, C\. Sun, and Y\. BengioTrajectory balance: improved credit assignment in GFlowNets\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2608.23849#S1.p3.2),[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1),[§3\.3](https://arxiv.org/html/2608.23849#S3.SS3.p1.1)\.
- Owen \(2013\)A\. B\. OwenMonte carlo theory, methods and examples\.Stanford University\.Cited by:[Appendix C](https://arxiv.org/html/2608.23849#A3.p2.3)\.
- Robinsonet al\.\(2021\)J\. Robinson, C\. Chuang, S\. Sra, and S\. JegelkaContrastive learning with hard negative samples\.InICLR,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Safavi and Koutra \(2020\)T\. Safavi and D\. KoutraCoDEx: a comprehensive knowledge graph completion benchmark\.InEMNLP,Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Sunet al\.\(2019\)Z\. Sun, Z\. Deng, J\. Nie, and J\. TangRotatE: knowledge graph embedding by relational rotation in complex space\.InICLR,Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.3.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Takamotoet al\.\(2025\)M\. Takamoto, D\. Onoro Rubio, W\. Ben Rim, T\. Maruyama, and B\. KotnisOptimal embedding guided negative sample generation for knowledge graph link prediction\.Transactions on Machine Learning Research\.External Links:[Link](https://openreview.net/forum?id=B4SyciDyIh)Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.7.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Toutanova and Chen \(2015\)K\. Toutanova and D\. ChenObserved versus latent features for knowledge base and text inference\.In3rd Workshop on Continuous Vector Space Models and their Compositionality,Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Trouillonet al\.\(2016\)T\. Trouillon, J\. Welbl, S\. Riedel, É\. Gaussier, and G\. BouchardComplex embeddings for simple link prediction\.InICML,Cited by:[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Wanget al\.\(2022\)L\. Wang, W\. Zhao, Z\. Wei, and J\. LiuSimKGC: simple contrastive knowledge graph completion with pre\-trained language models\.InACL,Cited by:[§1](https://arxiv.org/html/2608.23849#S1.p4.1),[§5\.1](https://arxiv.org/html/2608.23849#S5.SS1.p1.1)\.
- Yanget al\.\(2024\)Z\. Yang, M\. Ding, T\. Huang, Y\. Cen, J\. Song, B\. Xu, Y\. Dong, and J\. TangDoes negative sampling matter? a review with insights into its theory and applications\.IEEE Trans\. PAMI46\(8\),pp\. 5692–5711\.Cited by:[§1](https://arxiv.org/html/2608.23849#S1.p2.1)\.
- Zhanget al\.\(2022\)D\. Zhang, N\. Malkin, Z\. Liu, A\. Volokhova, A\. Courville, and Y\. BengioGenerative flow networks for discrete probabilistic modeling\.InICML,Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Zhanget al\.\(2023\)D\. Zhang, L\. Pan, R\. T\. Q\. Chen, A\. Courville, and Y\. BengioDistributional GFlowNets with quantile flows\.Transactions on Machine Learning Research\.Cited by:[§2\.2](https://arxiv.org/html/2608.23849#S2.SS2.p1.1)\.
- Zhanget al\.\(2024\)P\. Zhang, H\. Peng, Y\. Fang, Z\. Yang, Y\. Hu, Z\. Tan, and W\. XiaoUniversal knowledge graph embedding framework based on high\-quality negative sampling and weighting\.Mathematics12\(22\),pp\. 3489\.External Links:[Document](https://dx.doi.org/10.3390/math12223489)Cited by:[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p2.1)\.
- Zhanget al\.\(2019\)Y\. Zhang, Q\. Yao, Y\. Shao, and L\. ChenNSCaching: simple and efficient negative sampling for knowledge graph embedding\.InICDE,Cited by:[Table 6](https://arxiv.org/html/2608.23849#A2.T6.2.5.1),[§1](https://arxiv.org/html/2608.23849#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.23849#S2.SS1.p1.1)\.

## Appendix ANotation and Implementation

Table 4:Notation used in the method and analysis\.The Stage 1 type policy referenced in Section[3](https://arxiv.org/html/2608.23849#S3)is a two\-layer network over the context encoding𝒛𝒙=\[𝒆h;𝒆r;𝒆t;𝒆s\]\\bm\{z\}\_\{\\bm\{x\}\}=\[\\bm\{e\}\_\{h\};\\bm\{e\}\_\{r\};\\bm\{e\}\_\{t\};\\bm\{e\}\_\{s\}\]:

𝒖𝒙\\displaystyle\\bm\{u\}\_\{\\bm\{x\}\}=ReLU⁡\(𝑾\(0\)​𝒛𝒙\+𝒃\(0\)\),\\displaystyle=\\operatorname\{ReLU\}\\\!\\left\(\\bm\{W\}^\{\(0\)\}\\bm\{z\}\_\{\\bm\{x\}\}\+\\bm\{b\}^\{\(0\)\}\\right\),\(7\)PF​\(τ∣𝒙\)\\displaystyle P\_\{F\}\(\\tau\\mid\\bm\{x\}\)=softmaxτ∈𝒜rs⁡\(𝑾\(1\)​𝒖𝒙\+𝒃\(1\)\)τ\.\\displaystyle=\\softmax\_\{\\tau\\in\\mathcal\{A\}\_\{r\}^\{s\}\}\\\!\\left\(\\bm\{W\}^\{\(1\)\}\\bm\{u\}\_\{\\bm\{x\}\}\+\\bm\{b\}^\{\(1\)\}\\right\)\_\{\\tau\}\.The softmax is restricted to𝒜rs\\mathcal\{A\}\_\{r\}^\{s\}, the partitions observed in the corresponding domain or range of relationrrin𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}, so type\-invalid partitions carry no forward mass\.

Algorithm[5](https://arxiv.org/html/2608.23849#A1.T5)spells out the alternation summarized in Figure[1](https://arxiv.org/html/2608.23849#S3.F1)\. Candidate rewards for sampler training are computed after the associated KGE update; gradients from the trajectory\-balance loss do not propagate through the KGE parameters\.

Table 5:FlowNeg joint training\. Indentation indicates loop scope\.When schema types are unavailable,kk\-means withK=50K=50is run once on TransE entity embeddings fitted to𝒯tr\\mathcal\{T\}\_\{\\mathrm\{tr\}\}\. Schema\-derived types use the finest available category, with types containing fewer than ten entities merged into their parent category\. For tail corruption,𝒜r𝚝𝚊𝚒𝚕\\mathcal\{A\}\_\{r\}^\{\\mathtt\{tail\}\}contains partitions represented among training tails ofrr;𝒜r𝚑𝚎𝚊𝚍\\mathcal\{A\}\_\{r\}^\{\\mathtt\{head\}\}is defined analogously from training heads\. This “observed at least once” rule introduces no validation/test information and avoids an unreported frequency threshold\. The main experiments useK=50K=50\. The validation sweep is stable overK∈\[20,100\]K\\in\[20,100\]and selects 50; very smallKKremoves much of the hierarchical benefit, whereas very largeKKfragments the support\.

The optional refinement stage aggregates a selected entity’s neighborhood and modulates its terminal score:

R~​\(e^\)=MLP⁡\(𝒆e^;1\|𝒩⁡\(e^\)\|​∑\(e′,r′\)∈𝒩⁡\(e^\)𝑾r′​𝒆e′\)\.\\widetilde\{R\}\(\\hat\{e\}\)=\\operatorname\{MLP\}\\\!\\left\(\\bm\{e\}\_\{\\hat\{e\}\};\\frac\{1\}\{\|\\mathcal\{N\}\(\\hat\{e\}\)\|\}\\sum\_\{\(e^\{\\prime\},r^\{\\prime\}\)\\in\\mathcal\{N\}\(\\hat\{e\}\)\}\\bm\{W\}\_\{r^\{\\prime\}\}\\bm\{e\}\_\{e^\{\\prime\}\}\\right\)\.\(8\)It is intended for coarse partitions, typicallyK≤20K\\leq 20\. It is disabled for all headlineK=50K=50results\.

The chosen update ratio ism=5m=5\. Updating the sampler on every KGE step made its target change too quickly, whilem\>20m\>20produced stale negatives\. Warm\-upW=50W=50avoids constructing rewards from an untrained scorer;W=0W=0lowers MRR by0\.0110\.011, whereasW\>100W\>100spends additional epochs on uniform sampling\. The mixture rateα=0\.1\\alpha=0\.1preserves exploration;α=0\\alpha=0lowers MRR by0\.0050\.005, andα\>0\.3\\alpha\>0\.3dilutes the learned proposal\. The main final negative count isk=256k=256\.

###### Proposition A\.1\(Per\-step sampling cost\)\.

For a mini\-batch ofBBtriples withkknegatives each, exact type\-conditioned entity selection has cost

O⁡\(B​k​\[dh\+maxτ⁡\|ℰτ\|​dk\+dscore\]\+B​km​dh2\),O\\\!\\left\(Bk\\left\[d\_\{h\}\+\\max\_\{\\tau\}\|\\mathcal\{E\}\_\{\\tau\}\|d\_\{k\}\+d\_\{\\mathrm\{score\}\}\\right\]\+\\frac\{Bk\}\{m\}d\_\{h\}^\{2\}\\right\),\(9\)wheredhd\_\{h\}is the type\-policy hidden dimension,dkd\_\{k\}is the attention\-key dimension, anddscored\_\{\\mathrm\{score\}\}is the base\-model scoring cost\.

The Stage 2 term depends on the largest partition rather than\|ℰ\|\|\\mathcal\{E\}\|\. Cached keys avoid recomputing entity projections within a sampler update\. For SimKGC, those keys are obtained from its cached or projected entity representations; sampled identifiers are then passed to the unchanged contrastive loss\.

## Appendix BMechanism Comparison

Table[6](https://arxiv.org/html/2608.23849#A2.T6)summarizes which part of the negative\-sampling trade\-off each mechanism addresses explicitly\. The entries describe design mechanisms rather than guarantees: for example, type filtering can reduce implausible corruptions but does not certify that an unobserved triple is false\.

Table 6:Mechanism\-level comparison\. H, D, C, and G denote explicit support for hardness, diversity, collision control, and learned generation\. A circle denotes indirect or partial support\.
## Appendix CDerivation of the Reward Surrogate

Proposition[4\.1](https://arxiv.org/html/2608.23849#S4.Thmtheorem1)conditions on three assumptions, stated here in full\. \(A1\) Candidate\-level gradient\-norm variation is bounded, or absorbed into a hardness score\. \(A2\) A first\-order measure of negative informativeness is proportional toaθ​\(e∣𝒙\)a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\. This is a modeling choice rather than a derived fact: under a merely monotone relationship any increasingggwould yield a different scoreg⁡\(aθ​\(e∣𝒙\)\)​\(1−ptrue​\(e∣𝒙\)\)g\(a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\)\(1\-p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)\), so proportionality is what pins the reward down\. \(A3\) A candidate is a true but unobserved fact with probabilityptrue​\(e∣𝒙\)p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)and contributes nothing useful in that event\.

Fix𝒙\\bm\{x\}and writeae=aθ​\(e∣𝒙\)\>0a\_\{e\}=a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\>0andqe=q⁡\(e∣𝒙\)q\_\{e\}=q\(e\\mid\\bm\{x\}\)\. Ifysy\_\{s\}denotes the observed entity in the corrupted role, a schematic NCE objective over an unnormalized model score can be written as

𝒥NCE\(θ;q\)=𝔼\[\\displaystyle\\mathcal\{J\}\_\{\\mathrm\{NCE\}\}\(\\theta;q\)=\\mathbb\{E\}\\Bigg\[log⁡aysays\+k​qys\\displaystyle\\log\\frac\{a\_\{y\_\{s\}\}\}\{a\_\{y\_\{s\}\}\+kq\_\{y\_\{s\}\}\}\(10\)\+k𝔼e^∼qlogk​qe^ae^\+k​qe^\]\.\\displaystyle\+k\\mathbb\{E\}\_\{\\hat\{e\}\\sim q\}\\log\\frac\{kq\_\{\\hat\{e\}\}\}\{a\_\{\\hat\{e\}\}\+kq\_\{\\hat\{e\}\}\}\\Bigg\]\.This expression is used only to expose how proposal\-dependent negative terms weight candidate gradients; Equation \([2](https://arxiv.org/html/2608.23849#S3.E2)\) remains the implemented KGE loss\. We do not appeal to importance\-sampling optimality here: Equation \([2](https://arxiv.org/html/2608.23849#S3.E2)\) averages overqqwithout importance weights\([Owen, 2013](https://arxiv.org/html/2608.23849#bib.bib25)\), so changingqqchanges the objective itself rather than reducing the variance of a fixed estimator\. The reward is instead stated as a design criterion, namely to place mass on candidates that are informative under \(A1\)–\(A2\) and unlikely to be unobserved positives under \(A3\)\. The expected useful magnitude of a candidate is consequently proportional to

aθ​\(e∣𝒙\)−aθ​\(e∣𝒙\)​ptrue​\(e∣𝒙\)\\displaystyle a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\-a\_\{\\theta\}\(e\\mid\\bm\{x\}\)p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)\(11\)=aθ​\(e∣𝒙\)​\(1−ptrue​\(e∣𝒙\)\)\.\\displaystyle=a\_\{\\theta\}\(e\\mid\\bm\{x\}\)\\bigl\(1\-p\_\{\\mathrm\{true\}\}\(e\\mid\\bm\{x\}\)\\bigr\)\.Replacing the unknown truth probability by Equation \([4](https://arxiv.org/html/2608.23849#S3.E4)\) and restricting to role\-compatible entities yields Equation \([1](https://arxiv.org/html/2608.23849#S1.E1)\)\. The substitution is a modeling decision:c^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}is observed structural similarity, not a statistically consistent estimator of open\-world truth\. The argument motivates a transparent score but does not solve the unrestricted variance\-optimal proposal, whose form would also depend on exact gradient norms, importance weights, and the chosen KGE objective\.

## Appendix DTrajectory Balance and Coverage

Fix a context𝒙\\bm\{x\}\. For any terminal entityee, exact trajectory balance equates its forward flow to its terminal reward flow\. In the main two\-stage DAG, an entity has one parent type and the type has the source as its only parent\. HencePB​\(τ∣e,𝒙\)=1P\_\{B\}\(\\tau\\mid e,\\bm\{x\}\)=1for the assigned type andPB​\(s0∣τ,𝒙\)=1P\_\{B\}\(s\_\{0\}\\mid\\tau,\\bm\{x\}\)=1\. The trajectory identity givesπϕ​\(e∣𝒙\)=R⁡\(e∣𝒙\)/Zϕ​\(𝒙\)\\pi\_\{\\phi\}\(e\\mid\\bm\{x\}\)=R\(e\\mid\\bm\{x\}\)/Z\_\{\\phi\}\(\\bm\{x\}\)\. Normalizing over terminals givesZϕ​\(𝒙\)=∑e′R⁡\(e′∣𝒙\)Z\_\{\\phi\}\(\\bm\{x\}\)=\\sum\_\{e^\{\\prime\}\}R\(e^\{\\prime\}\\mid\\bm\{x\}\)and proves Proposition[4\.2](https://arxiv.org/html/2608.23849#S4.Thmtheorem2)\. This proof also shows why a single globalZϕZ\_\{\\phi\}would be insufficient when rewards change with the positive triple\. BecausePB≡1P\_\{B\}\\equiv 1, Equation \([5](https://arxiv.org/html/2608.23849#S3.E5)\) reduces here to least\-squares regression oflog⁡πϕ\+log⁡Zϕ\\log\\pi\_\{\\phi\}\+\\log Z\_\{\\phi\}ontolog⁡R\\log R, with no flow aggregated over multiple paths\.

For Corollary[4\.3](https://arxiv.org/html/2608.23849#S4.Thmtheorem3), exponentiating the residual condition gives

e−ε​R⁡\(e∣𝒙\)Zϕ​\(𝒙\)≤πϕ​\(e∣𝒙\)≤eε​R⁡\(e∣𝒙\)Zϕ​\(𝒙\)\.e^\{\-\\varepsilon\}\\frac\{R\(e\\mid\\bm\{x\}\)\}\{Z\_\{\\phi\}\(\\bm\{x\}\)\}\\leq\\pi\_\{\\phi\}\(e\\mid\\bm\{x\}\)\\leq e^\{\\varepsilon\}\\frac\{R\(e\\mid\\bm\{x\}\)\}\{Z\_\{\\phi\}\(\\bm\{x\}\)\}\.\(12\)Summing overeeshowse−ε≤Zϕ​\(𝒙\)/∑e′R⁡\(e′∣𝒙\)≤eεe^\{\-\\varepsilon\}\\leq Z\_\{\\phi\}\(\\bm\{x\}\)/\\sum\_\{e^\{\\prime\}\}R\(e^\{\\prime\}\\mid\\bm\{x\}\)\\leq e^\{\\varepsilon\}\. Combining the two displays yields the factore±2​εe^\{\\pm 2\\varepsilon\}relative toρR\\rho\_\{R\}\. Summing the pointwise inequalities overMjM\_\{j\}gives the same mode\-mass bounds\. Finally,

TV⁡\(πϕ,ρR\)\\displaystyle\\operatorname\{TV\}\(\\pi\_\{\\phi\},\\rho\_\{R\}\)=12​∑e\|πϕ​\(e\)−ρR​\(e\)\|\\displaystyle=\\frac\{1\}\{2\}\\sum\_\{e\}\|\\pi\_\{\\phi\}\(e\)\-\\rho\_\{R\}\(e\)\|\(13\)≤12​\(e2​ε−1\)​∑eρR​\(e\),\\displaystyle\\leq\\frac\{1\}\{2\}\(e^\{2\\varepsilon\}\-1\)\\sum\_\{e\}\\rho\_\{R\}\(e\),with the trivial cap at one\.

The two coverage statements summarized in Section[4](https://arxiv.org/html/2608.23849#S4)are as follows\.

###### Lemma D\.1\(Reward\-mass identity\)\.

LetSj=∑e∈MjR⁡\(e∣𝐱\)S\_\{j\}=\\sum\_\{e\\in M\_\{j\}\}R\(e\\mid\\bm\{x\}\)\. Under the exact target in Proposition[4\.2](https://arxiv.org/html/2608.23849#S4.Thmtheorem2),πϕ​\(Mj∣𝐱\)=Sj/∑ℓSℓ\\pi\_\{\\phi\}\(M\_\{j\}\\mid\\bm\{x\}\)=S\_\{j\}/\\sum\_\{\\ell\}S\_\{\\ell\}\. If0<Smin≤Sj≤Smax0<S\_\{\\min\}\\leq S\_\{j\}\\leq S\_\{\\max\}, every mode receives probability at leastSmin/\(J​Smax\)S\_\{\\min\}/\(JS\_\{\\max\}\)\. Under Corollary[4\.3](https://arxiv.org/html/2608.23849#S4.Thmtheorem3), the lower bound is multiplied bye−2​εe^\{\-2\\varepsilon\}\.

Summingπ⁡\(e∣𝒙\)=R⁡\(e∣𝒙\)/∑e′R⁡\(e′∣𝒙\)\\pi\(e\\mid\\bm\{x\}\)=R\(e\\mid\\bm\{x\}\)/\\sum\_\{e^\{\\prime\}\}R\(e^\{\\prime\}\\mid\\bm\{x\}\)overe∈Mje\\in M\_\{j\}givesπ⁡\(Mj∣𝒙\)=Sj/∑ℓSℓ\\pi\(M\_\{j\}\\mid\\bm\{x\}\)=S\_\{j\}/\\sum\_\{\\ell\}S\_\{\\ell\}\. SinceSj≥SminS\_\{j\}\\geq S\_\{\\min\}and∑ℓSℓ≤J​Smax\\sum\_\{\\ell\}S\_\{\\ell\}\\leq JS\_\{\\max\}, the exact lower bound follows; the approximate version follows from the mode\-mass inequality above\.

Hoeffding’s inequality within a fixed mode\([Boucheron et al\., 2013](https://arxiv.org/html/2608.23849#bib.bib6)\)gives

Pr⁡\(\|L^j−Lj\|≥εj\)≤2​exp⁡\(−2​nj​εj2\)\.\\Pr\\left\(\|\\widehat\{L\}\_\{j\}\-L\_\{j\}\|\\geq\\varepsilon\_\{j\}\\right\)\\leq 2\\exp\(\-2n\_\{j\}\\varepsilon\_\{j\}^\{2\}\)\.\(15\)A union bound overJJmodes yields simultaneous deviations\|L^j−Lj\|≤log⁡\(2​J/δ\)/\(2​nj\)\|\\widehat\{L\}\_\{j\}\-L\_\{j\}\|\\leq\\sqrt\{\\log\(2J/\\delta\)/\(2n\_\{j\}\)\}\. CombiningL=∑jpj​LjL=\\sum\_\{j\}p\_\{j\}L\_\{j\}with the triangle inequality gives Equation \([14](https://arxiv.org/html/2608.23849#A4.E14)\)\. If some relevantnjn\_\{j\}is zero, this fixed\-stratum estimate is unavailable\. The uniform component in FlowNeg reduces that risk, but neither reward proportionality nor high NDS determines the evaluation weightspjp\_\{j\}\.

## Appendix ELocal Conditional Tracking Conditions

The reward changes with the KGE model\. Standard stochastic approximation describes an ideal asymptotic regime, not a guarantee for the finite constant\-ratio schedule used in the experiments\.

To see the dependence, write

θt\+1=θt−ηθ,t​\(∇θF​\(θt,ϕt\)\+ξt\)\\theta\_\{t\+1\}=\\theta\_\{t\}\-\\eta\_\{\\theta,t\}\(\\nabla\_\{\\theta\}F\(\\theta\_\{t\},\\phi\_\{t\}\)\+\\xi\_\{t\}\)\(16\)and, on sampler\-update steps,

ϕt\+1=ϕt−ηϕ,t​\(∇ϕG​\(θt,ϕt\)\+ζt\)\.\\phi\_\{t\+1\}=\\phi\_\{t\}\-\\eta\_\{\\phi,t\}\(\\nabla\_\{\\phi\}G\(\\theta\_\{t\},\\phi\_\{t\}\)\+\\zeta\_\{t\}\)\.\(17\)Local PL contraction controls‖ϕt−ϕ∗​\(θt\)‖\\\|\\phi\_\{t\}\-\\phi^\{\*\}\(\\theta\_\{t\}\)\\\|, while Lipschitz dependence ofϕ∗\\phi^\{\*\}adds drift proportional to‖θt\+1−θt‖\\\|\\theta\_\{t\+1\}\-\\theta\_\{t\}\\\|\. The outer gradient bias can then be bounded by the tracking error\. The implemented schedule instead uses finite training, constant optimizer settings, and one sampler update perm=5m=5KGE steps; the paper does not claim that this schedule verifies the asymptotic conditions above\. Neural trajectory\-balance objectives also need not satisfy a PL condition globally\. The remark is therefore a map of sufficient local assumptions, not an explanation of the dataset\-level gains\.

## Appendix FFull\-Context Conditioning Audit

The implementation builds one immutable context record𝒙=\(h,r,t,s\)\\bm\{x\}=\(h,r,t,s\)with concatenated representation𝒛𝒙=\[𝒆h;𝒆r;𝒆t;𝒆s\]\\bm\{z\}\_\{\\bm\{x\}\}=\[\\bm\{e\}\_\{h\};\\bm\{e\}\_\{r\};\\bm\{e\}\_\{t\};\\bm\{e\}\_\{s\}\], passed to the type policyPF​\(τ∣𝒙\)P\_\{F\}\(\\tau\\mid\\bm\{x\}\), the entity policyPF​\(e^∣τ,𝒙\)P\_\{F\}\(\\hat\{e\}\\mid\\tau,\\bm\{x\}\), the log\-normalizerlog⁡Zϕ​\(𝒙\)\\log Z\_\{\\phi\}\(\\bm\{x\}\), the hardness and collision scores, the reward, and the cache key\(h,r,t,s\)\(h,r,t,s\)\. A minimal auditable forward path computes the context encoding once and reuses it for all three heads and the reward; the two\-stage DAG has a deterministic backward path \(backward log\-probability zero\), and an optional refinement stage, when enabled, receives the same record\. Table[7](https://arxiv.org/html/2608.23849#A6.T7)reports the automated graph, gradient, and cache tests; Table[8](https://arxiv.org/html/2608.23849#A6.T8)the held\-out trajectory\-balance residuals; and Table[9](https://arxiv.org/html/2608.23849#A6.T9)the context\-conditioning negative controls\.

Table 7:Unit and integration audit over10,00010\{,\}000constructed context pairs and1,0001\{,\}000training batches\.Output sensitivity is a secondary diagnostic: for\(h,r\)\(h,r\)\-matched pairs differing intt, the final model changes type logits in99\.84%99\.84\\%, entity logits in99\.99%99\.99\\%, andlog⁡Zϕ\\log Z\_\{\\phi\}in99\.76%99\.76\\%of pairs\. Identical outputs in a small fraction of cases are possible even with a correct code path; the graph and gradient tests above are decisive\.

Table 8:Held\-out trajectory\-balance residualsδTB\\delta\_\{\\mathrm\{TB\}\}on final checkpoints \(contexts not used for sampler updates\)\. Diagnostics of approximate balance, not a certificate\.Table 9:Context\-conditioning negative controls on the1515\-seed FB15k\-237/RotatE protocol\.
## Appendix GDatasets and Experimental Protocol

Table 10:Benchmark statistics\. Validation and test sizes refer to the standard splits used for filtered evaluation\.The controlled protocol holds the RotatE architecture, embedding dimension, optimizer family, batch construction, maximum training budget, filtered evaluator, hardware, software, and seeds fixed\. Each method receives its validation\-selected, method\-native sampler configuration, but every pipeline returns exactly 256 final negatives\. Table[11](https://arxiv.org/html/2608.23849#A7.T11)records the selected negative\-generation settings and the number of validation configurations evaluated\. The complete run manifest additionally associates each configuration with its checkpoint and run identifier\.

Table 11:Negative\-generation settings for the controlled FB15k\-237/RotatE study\. Pool sizes describe internal candidate construction; the final count is 256 for every method\.The mean validation\-selected epochs in the controlled runs are 274, 269, 286, 278, 271, 283, 281, and 276 for Uniform, Self\-Adv, KBGAN, NSCaching, SANS, EMU, IF\-NS, and FlowNeg, respectively; every final\-budget checkpoint is at epoch 300\. Reporting both definitions prevents validation selection from being silently mixed with final\-budget evaluation\.

The three diagnostics summarized in Section[5](https://arxiv.org/html/2608.23849#S5)are computed as follows\. For each frozen filtered test query a method exportsD=256D=256replacements; their empirical mode frequenciesq^𝒙​\(Mj\)\\widehat\{q\}\_\{\\bm\{x\}\}\(M\_\{j\}\)over the shared frozen partition are substituted into the NDS definition of Section[4](https://arxiv.org/html/2608.23849#S4), computed per query and then averaged over the queries common to all methods and over seeds\. Gradient informativeness is the meanℓ2\\ell\_\{2\}norm of the per\-negative loss gradient with respect to the frozen RotatE parameters, taken*before*batch reduction so that averaging does not mask per\-candidate variation; because model parameterizations change gradient scale, it is compared only within the common\-model control\. Held\-out\-positive collision is evaluated on the same exported draws after training has finished\.

## Appendix HDetailed Unified\-Grid Results

Table[12](https://arxiv.org/html/2608.23849#A8.T12)expands the compact main\-text grid with standard deviations\. These are five\-seed descriptive results, so the table contains no significance markers\.

Table 12:Unified\-grid test MRR, mean±\\pmstandard deviation over five paired seeds\.Tables[13](https://arxiv.org/html/2608.23849#A8.T13)and[14](https://arxiv.org/html/2608.23849#A8.T14)preserve the additional filtered ranking metrics from the five\-seed profile\. Their baseline rows expose the original measurements, but all cross\-cell EMU and IF\-NS conclusions are based on Table[12](https://arxiv.org/html/2608.23849#A8.T12), where the comparison set is fixed\.

Table 13:Filtered ranking metrics on FB15k\-237 and WN18RR, mean±\\pmstandard deviation over five seeds\.Table 14:Filtered MRR and Hits@10 on YAGO3\-10, CoDEx\-L, and Hetionet, mean±\\pmstandard deviation over five seeds\.
## Appendix INine\-Setting Paired Inference

The confirmatory panel uses1515paired evaluation seeds per setting, hyperparameters frozen on disjoint tuning seeds, exact two\-sided sign\-flip tests,95%95\\%paired bootstrap intervals over seed pairs, and Holm correction over all1818FlowNeg–baseline contrasts\. Table[15](https://arxiv.org/html/2608.23849#A9.T15)gives final\-budget MRR for all three samplers\. The paired contrasts, CIs, wins, and adjustedpp\-values are summarized in Table[2](https://arxiv.org/html/2608.23849#S6.T2)of the main text; both disclosed non\-rejections \(ComplEx/WN18RR vs\. EMU; SimKGC/YAGO3\-10 vs\. IF\-NS\) are retained\. The two panel\-level means \(\+0\.0171\+0\.0171vs\. EMU,\+0\.0152\+0\.0152vs\. IF\-NS\) are descriptive summaries of the declared settings, not an average over exchangeable samples\.

Table 15:Final\-budget MRR \(mean±\\pmsd over1515paired seeds\) in the nine\-setting panel\.
## Appendix JSeed\-Level and Secondary Statistical Reporting

The original five\-seed significance markers were removed because the claimed threshold was mathematically unattainable under the stated exact test\. For paired differencesd1,…,d5d\_\{1\},\\ldots,d\_\{5\}, an exact sign\-flip test enumerates only25=322^\{5\}=32assignments\. The unified EMU and IF\-NS tables are therefore descriptive\. Table[16](https://arxiv.org/html/2608.23849#A10.T16)supplies the 15 controlled seed records most relevant to the matched\-kkclaim\.

Table 16:Seed\-level FB15k\-237/RotatE MRR in the controlled study\. Selected epoch applies to the validation\-selected FlowNeg checkpoint; final MRR uses epoch 300\.The secondary confirmatory design was fixed before its additional runs\. Its contrast is FlowNeg minus Uniform in each of the 25 model–dataset cells; its estimand is the mean paired MRR difference over retraining randomness; and it uses 15 paired seeds, an exact two\-sided sign\-flip test, Holm adjustment across the 25 tests, and a 95% paired bootstrap interval obtained by resampling seed pairs\. Mean and median paired differences, paired standard deviations, intervals, win counts, rawpp\-values, and adjustedpp\-values are all reported\. No significance statement is made unless the Holm\-adjusted value is at most0\.050\.05\.

Table 17:Summary of the pre\-specified 15\-seed FlowNeg–Uniform analysis\.The two non\-rejections are SimKGC/WN18RR and RotatE/WN18RR\. Their positive means remain part of the descriptive summary, but neither is called significant\. This secondary contrast does not restore or replace inference against EMU or IF\-NS\.

## Appendix KAblations and Mechanism Diagnostics

Table[18](https://arxiv.org/html/2608.23849#A11.T18)gives the complete component study summarized in Section[6\.3](https://arxiv.org/html/2608.23849#S6.SS3), from the five\-seed FB15k\-237/RotatE profile\. It is separate from the 15\-seed controlled rerun in Table[3](https://arxiv.org/html/2608.23849#S6.T3); this distinction explains the0\.3570\.357and0\.3590\.359FlowNeg reference values\.

Table 18:Five\-seed FlowNeg ablation on FB15k\-237/RotatE\. One reward factor or architectural component changes in each row\. This profile is distinct from the 15\-seed control in Table[3](https://arxiv.org/html/2608.23849#S6.T3)\.Removing the collision discount preserves high GI but raises HPC by 2\.2 percentage points\. Removing type compatibility reduces coverage, while removing hardness reduces GI to0\.180\.18\. Flat selection retains the same reward but lowers NDS to31\.231\.2, showing that the hierarchy contributes beyond reward design\. The Boltzmann control uses the same 1,024\-candidate pool and hierarchy, with temperature selected on validation data, but normalizesexp⁡\(R/T\)\\exp\(R/T\)only within the realized pool\. It is therefore a practical pool\-normalized comparator, not exact all\-entity reward matching\. The controlled 15\-seed GFlowNet\-to\-RL rerun gives FlowNeg/RL MRR0\.359/0\.3400\.359/0\.340, NDS45\.7/9\.845\.7/9\.8, HPC0\.5/1\.7%0\.5/1\.7\\%, and GI0\.90/0\.910\.90/0\.91\. Thus, the large coverage difference is not explained by a weaker measured gradient signal\.

The validation traces show the same temporal pattern\. Until epoch 50, all FlowNeg runs use uniform warm\-up\. Once the learned sampler activates, validation MRR separates from Uniform and EMU while NDS remains near the broad\-coverage regime; the RL replacement instead converges toward approximately nine effective modes\. The source bundle includes the epoch\-level values used to generate these traces rather than embedding a second, visually redundant plot in the paper\.

## Appendix LPartition\-Independent Diversity

To break the circularity of an NDS that reuses FlowNeg’s own hierarchy, we add measures using neither that hierarchy nor its reward: \(1\)*independent NDS*from a separately trained Uniform–ComplEx model \(K=50K=50kk\-means, ten fixed clustering seeds, never used by FlowNeg\); \(2\) unique\-entity ratio overD=256D=256draws; \(3\) inverse\-Simpson entity effective support\(∑eq^​\(e\)2\)−1\(\\sum\_\{e\}\\widehat\{q\}\(e\)^\{2\}\)^\{\-1\}\(max256256\); \(4\) top\-1010entity mass \(smaller is more diverse\); and \(5\) mean pairwise cosine distance in the independent space\. All are computed within query, then averaged over paired seeds\. Table[19](https://arxiv.org/html/2608.23849#A12.T19)gives the primary controlled setting and Table[20](https://arxiv.org/html/2608.23849#A12.T20)the nine\-setting consistency check\. Uniform remains most diverse, as expected; FlowNeg retains substantially more independent and entity\-level coverage than every hard\-negative baseline\. These diagnostics remove the circularity but do not establish that coverage causes higher MRR\.

Table 19:Independent diversity on the1515\-seed FB15k\-237/RotatE protocol\. NDSind, unique\-entity ratio \(UER\), inverse\-Simpson support \(ESS\), top\-1010mass \(T10↓\\downarrow\), independent pairwise distance \(IPD\)\.Table 20:Consistency of independent NDS / unique\-entity ratio over the nine\-setting panel\.FlowNeg exceeds both EMU and IF\-NS on independent NDS and unique\-entity ratio in all nine settings, so the coverage advantage is not an artifact of scoring samples with the hierarchy used to generate them\.

## Appendix MCalibration and Diagnostics

Within each dataset, exported diagnostic candidates are pooled across the declared queries and seeds and sorted byc^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}into ten equal\-frequency bins\. For binbb, letc¯b\\overline\{c\}\_\{b\}be the mean structural score and letHPCb\\operatorname\{HPC\}\_\{b\}be the observed fraction colliding with held\-out positives\. We report

ECEHPC=∑b\|ℬb\|N​\|HPCb−c¯b\|\.\\operatorname\{ECE\}\_\{\\mathrm\{HPC\}\}=\\sum\_\{b\}\\frac\{\|\\mathcal\{B\}\_\{b\}\|\}\{N\}\\left\|\\operatorname\{HPC\}\_\{b\}\-\\overline\{c\}\_\{b\}\\right\|\.\(18\)
Table 21:Ten\-bin calibration error for predicting held\-out\-positive collision\.This diagnostic asks whether the score agrees numerically with known held\-out collision frequency\. It neither labels all unobserved triples nor measures probability calibration against an unavailable open\-world truth set\. ECE alone also does not establish discrimination and should be interpreted alongside the bin records and collision prevalence in the supplied material\. The controlled FB15k\-237 rerun gives0\.0230\.023, close to the corresponding five\-seed profile\.

On FB15k\-237/RotatE, gains vary with relation structure\. The many\-to\-many film–actor–film relation gains3\.8%3\.8\\%MRR, and person–nationality, which has many type\-compatible candidates, gains12\.3%12\.3\\%\. The gain is1\.2%1\.2\\%for the small\-candidate person–gender relation and2\.1%2\.1\\%for symmetric relations\. These observations are descriptive and do not invoke the fixed\-partition concentration remark as a causal explanation\.

## Appendix NHeld\-out\-Positive Collision Diagnostics

For each dataset we freeze2,0002\{,\}000filtered test queries, draw256256candidates per query at each of five final checkpoints \(2\.562\.56M draws per dataset\), retain repeated draws because the target is the sampler distribution, and labely=1y=1iff the corruption occurs in𝒯val∪𝒯test\\mathcal\{T\}\_\{\\mathrm\{val\}\}\\cup\\mathcal\{T\}\_\{\\mathrm\{test\}\}\. Uncertainty is resampled over queries and seeds, not individual draws, since candidates from one query are dependent\. AUROC measures ranking, AUPRC is read against prevalence, and Brier/ECE treat the raw Jaccard value numerically only for diagnosis; none identifies true\-but\-unrecorded facts\. Table[22](https://arxiv.org/html/2608.23849#A14.T22)gives prevalence, discrimination, and calibration; the raw Brier is slightly worse than a prevalence\-only predictor because the score overpredicts the rare collision rate, while a validation\-only monotone map lowers Brier without changing rankings\. The1515\-seed FB15k\-237/RotatE matched\-kkrun reproduces the profile \(0\.50%0\.50\\%prevalence, AUROC0\.8890\.889, AUPRC0\.0830\.083, raw Brier0\.00600\.0060, ECE0\.0230\.023\)\.

Table 22:Collision prevalence, discrimination, and calibration \(mean±\\pmcluster\-bootstrap sd\)\.Ten equal\-frequency reliability bins \(Table[23](https://arxiv.org/html/2608.23849#A14.T23); each cell is mean raw score / observed collision rate, in percentage points,≈256,000\\approx 256\{,\}000draws per decile before cluster resampling\) reproduce the ECE values up to rounding and expose the point hidden by ECE alone: observed collision rises monotonically with the score, but the raw score is conservative in magnitude\. Accordingly we callc^HPC\\widehat\{c\}\_\{\\mathrm\{HPC\}\}a structural collision\-risk score, not a calibrated probability\.

Table 23:Ten equal\-frequency reliability bins: mean raw score / observed collision rate \(%\)\.
## Appendix OEfficiency and Checkpoints

Table[24](https://arxiv.org/html/2608.23849#A15.T24)preserves the direct, method\-profiled full\-run measurements from the original experiment\. These profiles are not a matched\-kkor matched\-wall\-clock comparison and are not used for inference\. In particular, their MRR values should not be mixed with the controlled rerun in Table[3](https://arxiv.org/html/2608.23849#S6.T3)\.

Table 24:Method\-profiled full runs on FB15k\-237/RotatE using four NVIDIA A100 80GB GPUs\.Table[25](https://arxiv.org/html/2608.23849#A15.T25)gives the full equal\-wall\-clock comparison summarized in Section[6\.4](https://arxiv.org/html/2608.23849#S6.SS4): for each budget, both the latest complete checkpoint written by that deadline and the best validation\-selected checkpoint available by it\. Selection uses validation MRR only; the test set is evaluated after the checkpoint has been chosen\.

Table 25:Test MRR at equal wall\-clock budgets on FB15k\-237/RotatE \(15 paired seeds\): the final complete checkpoint written by each deadline, and the best validation\-selected checkpoint available by that deadline\.The equal\-time experiment evaluates the latest fully written checkpoint at or before a budget\. Timing includes setup, candidate construction, negative generation, sampler learning, base\-model optimization, scheduled validation, and checkpoint I/O\. This definition prevents a method from receiving uncounted initialization time or an interpolated checkpoint\.

## Appendix PReproducibility and Artifact Provenance

The reported grid contains one record for every model–dataset–sampler–seed tuple, rather than inferring coverage from a subset of printed rows\. Each record links a frozen configuration, split hash, run identifier, selected checkpoint, final checkpoint, and metric file\. The supplied material contains training and evaluation code, all negative\-sampling implementations, clustering and calibration scripts, raw seed metrics, per\-bin collision records, wall\-clock logs, GPU and software versions, preprocessing scripts, and a dataset and code\-license summary\.

The evidence files preserve the distinctions used in the paper\. Five\-seed unified\-grid results, 15\-seed matched\-kkresults, and 15\-seed FlowNeg–Uniform confirmatory results have separate manifests\. Validation\-selected and final\-budget checkpoints are retained together\. A run is replaced only for a verified infrastructure failure before any validation or test metric is observed; numerical divergence or method instability remains under its original seed\. Figure[1](https://arxiv.org/html/2608.23849#S3.F1), Tables[1](https://arxiv.org/html/2608.23849#S6.T1)–[25](https://arxiv.org/html/2608.23849#A15.T25), and all appendix summaries can therefore be traced to a declared profile without combining incompatible runs\.