PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ibne Farabi Shihab, Naoshin Anzum Hridi, Joyanta Jyoti Mondal

arXiv:2608.23849v1cs.LG

TL;DR

Knowledge graph negative sampling must balance informative hardness, entity-space coverage, and caution about unobserved true facts. FlowNeg uses hierarchical reward-proportional generation, and controlled evidence shows gains over EMU alongside diversity, informativeness, and collision trade-offs.

  • Problem

    Knowledge graph embeddings need generated negatives that are hard enough to train on while remaining diverse and conservative about plausible unobserved facts.

  • Method

    FlowNeg amortizes context-conditioned reward-proportional negative sampling through a hierarchy that selects a relation-compatible type and then an entity.

  • Results

    FlowNeg shows broad gains with disclosed exceptions, while the matched study reports +0.013 mean paired MRR over EMU and FlowNeg combines NDS 45.7, HPC 0.5%, and GI 0.90.

  • Takeaways & Limitations

    The evidence supports reward-proportional generation as a practical KGE sampler and supports mode-covering generation without treating structural similarity as an open-world truth oracle.

  • Takeaways & Limitations

    Structural collision scores can fail in sparse relation-role neighborhoods, low collision cannot prove generated triples are false, and the theory conditions on fixed contexts or partitions while models co-evolve.

Abstract

from arXiv · show

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$ and $+0.0160$ on average). A separate 15-seed FB15k-237/RotatE control fixing negative count, diagnostic budget, and compute gives FlowNeg $0.359\pm0.001$ MRR against $0.346\pm0.002$ for 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.

1 Introduction

FlowNeg addresses the tension between easy but uninformative negatives and hard negatives that can collapse onto a narrow set or coincide with omitted positives. It uses context-conditioned hierarchical reward-proportional generation to balance hardness, coverage, and collision risk.

  • Easy negatives yield negligible gradients, while extremely hard negatives may be true facts omitted from an incomplete graph.
  • A useful sampler must produce negatives that are hard enough to train on, broad enough to cover entity regions, and conservative about unobserved triples.
  • FlowNeg uses a GFlowNet because reward-proportional terminal sampling can preserve probability across multiple informative candidates instead of collapsing onto one.
  • The sampler selects a relation-compatible type and then an entity, amortizing composite-reward normalization through sampled rewards and a learned context-dependent normalizer.
  • FlowNeg’s contributions combine a shared proposal interface, a trajectory-balance analysis, and separated descriptive, matched-k, and robustness evaluations.

2 Background and Related Work

Existing negative samplers improve hardness or diversity separately, while FlowNeg learns a reward-following distribution intended to retain both. The related-work distinction is distributional: FlowNeg follows composite reward rather than caching, filtering, or maximizing individual candidates.

  • Uniform and type-constrained corruption are inexpensive and diverse but spend most samples on candidates the model already rejects.
  • Self-adversarial weighting, caches, and structural neighborhoods increase informativeness without controlling how many distinct semantic regions remain represented.
  • Learned samplers such as KBGAN, EMU, and IF-NS target hardness through adversarial generation, embedding mutation, or influence estimates.
  • FlowNeg’s distinct choice is to learn a distribution whose mass follows a composite reward rather than cache, filter, or maximize individual candidates.
  • GFlowNets provide terminal probabilities proportional to non-negative rewards through objectives including trajectory balance, but the paper limits this relevance to reward-bearing regions rather than claiming collapse prevention generally.

3 FlowNeg

FlowNeg replaces direct entity-wide reward normalization with a two-stage, context-conditioned sampler that selects a compatible type and then an entity. Its bounded hardness and training-only structural collision signals define the terminal reward used by trajectory balance.

  • FlowNeg changes the negative proposal while retaining the KGE score, loss, and corruption-side rule.
  • Hierarchical generation: Direct reward normalization over all entities would repeatedly score every replacement, so FlowNeg decomposes sampling into type selection followed by entity selection.
  • Hierarchical generation: The type policy restricts sampling to relation-compatible partitions, after which a cross-attention policy selects an entity within the chosen partition.
  • Hierarchical generation: Schema types are used when available; otherwise FlowNeg creates K = 50 training-only k-means partitions and freezes them before sampling.
  • Hierarchical generation: The hierarchy reduces reward enumeration but still normalizes logits within the selected partition while evaluating rewards only at sampled terminals.
  • For SimKGC, FlowNeg substitutes sampled identifiers into the existing contrastive objective without changing the encoder or scoring architecture.
  • Reward design: The hardness factor is bounded and model-based, while the collision score uses role-conditioned training neighborhoods to discount structurally similar candidates.
  • Reward design: Type-invalid candidates are excluded, an additive epsilon and sigmoid keep trajectory-balance rewards valid, and exponential rescaling preserves within-context proportions.

4 Analysis and Scope

The analysis characterizes FlowNeg’s reward-tracking and fixed-partition coverage under explicit assumptions, while audits test implementation and controlled behavior. Its claims remain limited by co-evolving training, proxy validity, and hierarchy-dependent diversity measures.

  • The analysis does not establish global convergence for a neural GFlowNet or make the neighborhood proxy an oracle for open-world truth.
  • Full-context conditioning keys policies and caches by (h, r, t, s), because collision discounts change with the entity being replaced.
  • The negative control omitting the replaced entity raises mean |δTB| from 0.061 to 0.194 and lowers FB15k-237/RotatE MRR from 0.359 to 0.351.
  • Equation (1) substitutes structural collision for unavailable truth probability under an explicit modeling assumption, so it is a design criterion rather than an unconditional optimal proposal.
  • Under exact trajectory balance, terminal probability equals normalized reward over the type-compatible support.
  • Approximate balance yields multiplicative tracking bounds and a total-variation bound, but only under a uniform residual condition that diagnostics cannot certify.
  • NDS measures entropy across a shared frozen training-only partition, not partition-independent semantic diversity or within-mode concentration.
  • Neither high NDS nor the concentration argument alone establishes that greater diversity improves MRR.

5 Experimental Design

The experiments compare FlowNeg with established samplers across a broad model–dataset grid and under a controlled matched-k setting, while defining leakage-safe diagnostics and inference boundaries.

  • Evaluation scope: The grid crosses five architectures with five benchmarks, placing FlowNeg, EMU, and IF-NS in every model–dataset cell.A controlled FB15k-237/RotatE study additionally includes Uniform, Self-Adv, KBGAN, NSCaching, and SANS.
  • Controlled comparison: The matched-k study gives every method k = 256 final negatives per positive and shares the model, optimization, data, evaluation, and 15-seed setup.Larger candidate pools contribute 1,024 candidates but are not counted as final k.
  • Leakage control: All structural supports and training-time rejection use Ttr alone, excluding validation and test triples from reward construction and negative generation.Filtered ranking removes known positives from train, validation, and test sets.
  • Inference scope: The five-seed grid is descriptive because its exact paired sign-flip test has only 25 assignments, while the separate 15-seed FlowNeg–Uniform check is reported as robustness.The design distinguishes descriptive comparison from formal inference.
  • Diagnostics: NDS measures within-query diversity from empirical mode frequencies over D = 256 exported replacements, whereas HPC measures observed collisions with held-out positives.GI is the mean per-negative loss-gradient norm under frozen RotatE parameters; these diagnostics do not replace link-prediction metrics.

6 Results

FlowNeg shows broad but non-uniform MRR gains over EMU and IF-NS, with controlled evidence linking its advantage to the sampling objective and reward structure while preserving diagnostic caveats.

  • 6.1 Breadth across models and datasets: FlowNeg exceeds EMU in 24 of 25 cells with mean +0.0172 MRR, and exceeds IF-NS in 24 of 25 with mean +0.0160 MRR.The exceptions are ComplEx/WN18RR versus EMU and SimKGC/YAGO3-10 versus IF-NS.
  • 6.1 Breadth across models and datasets: All 25 FlowNeg–Uniform cell-level mean differences are positive, averaging +0.0395 MRR, and 23 survive Holm correction.This separate 15-seed analysis is reported as robustness rather than inference against EMU or IF-NS.
  • 6.2 15-seed inference against EMU and IF-NS: In the nine-setting confirmatory panel, FlowNeg has higher means in 8/9 settings against each baseline, with 16 of 18 contrasts positive and Holm-significant.The two non-rejections retain the original counterexamples.
  • 6.3 Matched negative count and mechanism: The matched-k control gives FlowNeg a +0.013 mean paired MRR difference over EMU, winning all 15 seed pairs with a 95% interval of [+0.012, +0.014].The control fixes the base model, data, negative count, diagnostics, hardware, software, and paired seeds.
  • 6.3 Matched negative count and mechanism: FlowNeg combines NDS 45.7, HPC 0.5%, and GI 0.90, exposing a diversity–collision–informativeness trade-off rather than treating one diagnostic as sufficient for accuracy.Uniform is marginally more diverse and collides less, while EMU and IF-NS are less diverse and collide more often.
  • 6.3 Matched negative count and mechanism: Replacing trajectory-balance training with reward-maximizing RL lowers MRR from 0.359 to 0.340 and NDS from 45.7 to 9.8, while HPC rises from 0.5% to 1.7%.GI changes only from 0.90 to 0.91 under fixed reward, architecture, data, negative count, and diagnostic budget.
  • 6.3 Matched negative count and mechanism: A hierarchy-independent analysis still ranks FlowNeg above EMU and IF-NS on diversity measures, but does not establish that coverage causes the MRR improvement.Uniform remains most diverse in the FB15k-237/RotatE comparison.

7 Conclusion

FlowNeg learns context-specific negative distributions through hierarchical reward-proportional generation, with matched controls indicating broad gains and distinct contributions from its objective, reward factors, and hierarchy.

  • 7 Conclusion: FlowNeg learns a context-specific negative distribution rather than repeatedly searching for an argmax.Its hierarchy reduces exploration cost in large entity spaces.
  • 7 Conclusion: The matched-k control uses 256 training negatives per positive and 256 diagnostic draws per filtered test query.This fixed budget supports the controlled comparison described in Table 3.
  • 7 Conclusion: The reward balances hardness, observed collision risk, and type support, while trajectory balance amortizes sampling toward that reward distribution.The conclusion frames these components as the intended balance of the method.
  • 7 Conclusion: The evidence supports mode-covering negative generation, while the reported intervention and diagnostics do not show that diversity causes accuracy or that structural similarity is an open-world truth oracle.The conclusion limits the interpretation to the declared experiments and observables.

8 Limitations

FlowNeg’s evidence is bounded by structural sparsity, evolving training dynamics, fixed-partition diagnostics, and descriptive broader-grid evaluation. Its sampler also adds computational cost and does not establish open-world truth.

  • FlowNeg adds sampler parameters and computation, while structural collision scores can fail in sparse or semantically disconnected relation-role neighborhoods.Low hardness–positive collision cannot prove generated triples are false.
  • NDS measures hierarchy-aligned coverage under a frozen partition, not partition-independent semantic diversity.Poorly formed schema or training-only embedding clusters can restrict useful candidates.
  • The theoretical guarantees condition on fixed contexts, rewards, or partitions, although the KGE model and GFlowNet co-evolve during training.Residual diagnostics cannot certify the uniform balance-residual condition, and the analysis does not establish global neural GFlowNet convergence.
  • The broader five-seed grid is descriptive, and the strongest controlled attribution is limited to FB15k-237 with RotatE.The withdrawn strongest-baseline significance claim is not reinstated.

9 Ethical Considerations

Knowledge-graph completion can propagate omissions and biases, so FlowNeg is intended for training rather than truth verification. Its benchmark experiments use established splits without human participants or newly collected personal data.

  • Knowledge-graph completion may propagate omissions and biases when generated links are consumed as facts.Biomedical and person-centric predictions require downstream validation, provenance, and uncertainty-aware review.
  • FlowNeg should be used as a training sampler rather than as a truth-verification mechanism.Structural similarity and low collision do not establish that an unobserved triple is false.
  • The experiments use established benchmark splits and involve neither human participants nor newly collected personal data.
  • Type filtering restricts candidates to observed relation-role partitions but does not certify unobserved triples as false.The support may instead be derived from a training-only embedding partition when schema types are unavailable.

C Derivation of the Reward Surrogate

FlowNeg defines a context-conditioned reward surrogate that balances hardness, collision risk, and type compatibility, then trains a hierarchical sampler toward that reward. The derivation explicitly treats key substitutions as modeling choices and scopes coverage claims to fixed partitions and stated assumptions.

  • Reward assumptions: The reward is a design criterion for informative candidates unlikely to be unobserved positives, under assumptions about gradient variation, informativeness, and open-world truth.Proportionality between informativeness and model hardness is a modeling choice rather than a derived fact.
  • Reward construction: Equation (1) replaces unknown truth probability with an observed structural surrogate and restricts sampling to role-compatible entities.The structural score is not a statistically consistent estimator of open-world truth.
  • Trajectory balance: Exact trajectory balance yields terminal probability proportional to reward, while the learned context-dependent normalizer accommodates rewards that change with the positive triple.In the two-stage DAG, each terminal has one type parent and deterministic backward probabilities.
  • Coverage bounds: Under approximate balance, terminal and mode probabilities receive multiplicative e^±2ε perturbation bounds; fixed-partition coverage follows reward mass rather than guaranteeing test-risk improvement.The fixed-partition bound requires nonzero mode samples and bounded losses.
  • Joint training: FlowNeg alternates sampler and KGE updates, but its finite schedule does not verify the asymptotic tracking conditions described by the local theory.The theory assumes smoothness, bounded stochastic-gradient variance, a local PL condition, and slower KGE updates.
  • Implementation audit: The implementation reuses one full context record across policies, normalizer, scores, reward, and cache, with graph and gradient audits reported separately.The audit covers 10,000 context pairs and 1,000 training batches.

G Datasets and Experimental Protocol

The experiments combine a controlled matched-k protocol with descriptive grid and confirmatory analyses across architectures and datasets. Reporting distinguishes validation-selected settings, final-budget evaluation, descriptive five-seed results, and corrected 15-seed inference.

  • Controlled protocol: Every controlled pipeline returns exactly 256 final negatives under a common RotatE protocol, while method-native sampler configurations are selected on disjoint tuning seeds.The protocol fixes architecture, optimizer family, batch construction, training budget, evaluator, hardware, software, and seeds.
  • Checkpointing: Final-budget checkpoints use epoch 300, while mean validation-selected epochs range from 269 for Self-Adv to 286 for KBGAN across the eight methods.Reporting both epoch definitions prevents validation selection from being mixed with final-budget evaluation.
  • Diagnostics: The diagnostic protocol computes NDS from 256 replacements over a shared frozen partition, alongside gradient informativeness and collision-related measurements.Diagnostics are averaged over common queries and seeds in the controlled FB15k-237/RotatE study.
  • Descriptive grid: The five-seed grid is descriptive and contains no significance markers; unified cross-cell comparisons use the fixed comparison set in Table 12.Additional filtered ranking metrics remain in Tables 13 and 14.
  • Statistical reporting: The original five-seed significance markers were removed because the stated exact sign-flip threshold was unattainable with five paired differences.The secondary panel instead uses 15 paired seeds, exact sign-flip tests, bootstrap intervals, and Holm adjustment.

K Ablations and Mechanism Diagnostics

The diagnostics separate FlowNeg’s reward components, hierarchy, diversity, collision prediction, and evaluation protocols. Together they show broad coverage and informativeness, while preserving distinctions between descriptive profiles and controlled comparisons.

  • Component ablations: Removing collision discount raises HPC by 2.2 percentage points while preserving high GI, whereas removing hardness reduces GI to 0.18.Removing type compatibility reduces coverage, and flat selection lowers NDS to 31.2 despite retaining the same reward.
  • Controlled mechanism comparison: FlowNeg/RL records MRR 0.359/0.340, NDS 45.7/9.8, HPC 0.5/1.7%, and GI 0.90/0.91 in the controlled rerun.The coverage difference is therefore not explained by a weaker measured gradient signal.
  • Validation dynamics: After uniform warm-up through epoch 50, FlowNeg separates from Uniform and EMU while NDS remains broad; RL converges toward approximately nine effective modes.The validation traces describe the temporal behavior after the learned sampler activates.
  • Partition-independent diversity: FlowNeg retains substantially more independent and entity-level coverage than every hard-negative baseline, while Uniform remains most diverse.The independent diagnostics avoid reusing FlowNeg’s own hierarchy for scoring samples.
  • Partition-independent diversity: FlowNeg exceeds EMU and IF-NS on independent NDS and unique-entity ratio in all nine settings, but coverage is not shown to cause higher MRR.This supports the robustness of the coverage comparison without establishing its causal role in performance.
  • Collision diagnostics: Observed collision rises monotonically with bcHPC, but the raw score is conservative in magnitude; the controlled rerun reports AUROC 0.889, AUPRC 0.083, raw Brier 0.0060, and ECE 0.023.The diagnostic predicts known held-out collisions without labeling all unobserved triples as true or false.
Loading 2608.23849v1…