A knowledge graph embedding model learns to score facts such as (Mona Lisa, exhibitedIn, Louvre). To learn this, it must also be shown false facts, called negatives. The usual recipe swaps in a random entity, which gives facts like (Mona Lisa, exhibitedIn, Submarine). These are so obviously false that the model stops learning from them. Adversarial negative sampling fixes this by preferring the negatives the current model finds most believable. The fix creates a new problem. Knowledge graphs are incomplete, so the most believable "false" facts are often true facts nobody recorded. An adversary that chases the highest-scoring negatives will therefore punish the model for correct predictions.
This proposal keeps the adversary but limits how much weight it can put on any one negative. The limit shrinks as the estimated chance that the negative is actually true grows. That chance is estimated from something we can observe: we hide a small set of real training facts, then watch where the model ranks these hidden truths among its candidate negatives. The same hidden set also lets us audit, for every sampler, how much training signal is spent on true facts. That measurement is what lets us ask whether adversarial gains come from hardness or from something else.
Core Claim
Self-adversarial negative sampling, introduced with RotatE, draws $\nu$ candidate negatives uniformly and weights them by a softmax over the model's own scores $f$ at temperature $\alpha$. This weighting is exactly the solution of a small worst-case problem. For a query, let $\ell_j$ be the loss on candidate negative $j$ and $w$ a weighting over candidates. Then
$$ w^\star = \arg\max_{w \in \Delta_\nu} \; \sum_{j=1}^{\nu} w_j \ell_j \;-\; \tfrac{1}{\alpha}\,\mathrm{KL}\!\left(w \,\|\, \tfrac{1}{\nu}\mathbf{1}\right), $$
where $\Delta_\nu$ is the set of weightings that are non-negative and sum to one. The solution is $w_j \propto \exp(\alpha \ell_j)$, which is SANS, because $\ell_j$ increases with the score $f$ of the negative. The same observation underlies the distributionally robust reading of AdvInfoNCE, a collaborative-filtering loss that frames negative weighting as a minimax game with a KL constraint.
Seen this way, the false-negative problem has a clean cause: nothing stops the adversary from placing almost all its mass on one candidate that happens to be a true fact. We add a per-candidate cap:
$$ w_j \;\le\; \frac{\kappa}{\nu}\,\bigl(1 - \hat\pi_r(q_j)\bigr). $$
Here $q_j$ is candidate $j$'s rank among the $\nu$ candidates, expressed as a quantile, and $\hat\pi_r(q)$ is the estimated probability that a candidate at quantile $q$ is actually true for relation $r$. The constant $\kappa \ge 1$ sets the overall budget. The capped problem is still a small convex program. It is solved by clipping the softmax weights at their caps and passing the excess mass to the uncapped candidates in proportion to their softmax weights, which costs a sort per query.
The claim is two-sided. The capped adversary should match or beat SANS on standard filtered ranking. More importantly, it should put measurably less training weight on true unobserved facts. If the audit shows that SANS already spends little weight on true facts, the premise is wrong, and the project reports that negative result.
Estimating False-Negative Risk from Hidden Facts
The estimator $\hat\pi_r$ is the new ingredient. Before training, we hide a random 5% of training triples; these are "planted" facts. The model never trains on them, so it scores them the way it scores any unrecorded true fact.
During training, at a fixed interval, we score each planted fact's query against its own $\nu$ candidates and record the quantile where the planted answer lands. Pooling per relation gives the density $g_r(q)$ of hidden truths across quantiles. Let $\rho_r$ be the unknown rate at which random candidates for relation $r$ are true. Bayes' rule then gives
$$ \hat\pi_r(q) \approx \min\{1,\ \rho_r\, g_r(q)\}. $$
We set $\rho_r$ as one global scale shared across relations and tune it on validation MRR; per-relation scales are left for later. Relations with few planted facts share a pooled curve. This is a positive-unlabeled estimate: it uses the only truths we know to be missing to model the ones we don't know.
Its cost is one extra scoring pass over 5% of the data every few epochs. That is small next to the candidate scoring SANS already does, which matters because the computational overhead of dynamic candidate evaluation is a known limitation (Cornell et al.). For the final model, planted facts are returned to the training set for a short last phase, and the curve is frozen at its last estimate. Every baseline receives the same schedule, so no method sees more data.
Relation to Prior Work
Four lines of prior work play different roles. KBGAN motivates the problem: it trains a separate generator with policy gradients to pick hard negatives. It showed that hardness helps, raising TransE on WN18RR from 0.186 to 0.213 MRR, but it paid for this with high reward variance and never addressed false negatives. SANS removed the second player, and our method keeps that choice. The cap is the only change.
Kamigaito and Hayashi constrain the design and supply a warning. They prove that SANS behaves like ordinary negative sampling as $\nu$ grows. They also show that margin and subsampling choices alone can move RESCAL's FB15k-237 MRR from 17.2 to 26.6. Any claimed gain from adversarial weighting must therefore survive a matched margin and subsampling sweep. Feng et al. likewise recast SANS as score smoothing and add triple-level smoothing (TANS); we treat that as a competing explanation of where SANS gains come from.
Don't Mess with Mister-in-Between motivates the false-negative concern directly. Its authors mine hard negatives lexically, topologically and from model predictions, and report that removing false negatives with an oracle gives substantial gains. We replace that oracle with an estimate. AdvInfoNCE and DeMix supply the closest method-level ideas. AdvInfoNCE learns per-negative hardness shifts that may go negative for suspected false negatives, but only for user-item graphs. DeMix flags pseudo-negatives with a margin threshold and mixes them with other samples. Neither estimates false-negative risk from held-out truths, and neither caps an adversary's mass.
EMU synthesizes continuous negatives by mutating embeddings and sidesteps discrete search. It is an orthogonal competitor rather than an ingredient.
Research Program
We implement the capped adversary as a drop-in replacement for the SANS weighting in a standard knowledge graph embedding codebase. We test it on one distance-based model (RotatE), where margin effects matter, and one inner-product model (DistMult or ComplEx), where they do not. This split follows the reachability result of Kamigaito and Hayashi.
The analysis has three parts. First, a planted-fact audit. For each sampler, we measure the share of total negative weight that lands on hidden true facts over training, alongside the gradient norm on negatives. The gradient norm shows whether the cap brings back the vanishing-gradient behavior of easy negatives. Second, a hardness-versus-smoothing test. Each query keeps its SANS weight values, but they are randomly permuted across candidates. This preserves how uneven the weights are while destroying which candidate gets them. If this does as well as SANS, the gains in RotatE come from smoothing, not from targeting hard negatives. Third, the main comparison on link prediction.
Baselines
The naive reference point is uniform negative sampling with the same model, $\nu$, and a tuned margin and subsampling method ("Freq"/"Uniq"). The tuning follows Kamigaito and Hayashi and uses the same budget as every other method. This separates what careful loss tuning achieves without any hardness.
The strongest existing competitor is RotatE with SANS. It is the adversarial method with the least instability, it shares our model and code path, and the reported numbers are MRR 0.338 on FB15k-237 and 0.476 on WN18RR (RotatE). We rerun it in our codebase with the same number of negatives, epochs, and hyperparameter trials: temperature, margin, and learning rate, with 30 trials per method. We report both our rerun and the published figure. Beating it means a mean filtered-MRR gain over five seeds that exceeds the seed standard deviation on at least two of FB15k-237, WN18RR and YAGO3-10. It also means a clear drop in the share of weight on planted true facts. An MRR tie with a large drop in that share would still support the mechanism but would not be a performance claim.
TANS (Feng et al.) is run under the same budget. It is the strongest smoothing-based explanation of SANS gains.
KBGAN with a TransE target (KBGAN; WN18RR MRR 0.213 reported) represents explicit two-player adversaries. It is included mainly for the audit, since a separately learned generator may concentrate on true facts more than SANS does.
EMU with DistMult (EMU; FB15k-237 MRR 0.329 at dimension 200 reported) represents non-adversarial continuous negatives. It is run at a matched embedding dimension.
DeMix (DeMix) represents threshold-based denoising. The file gives only a relative gain of 7.8% MRR for TransE on FB15k-237, with no absolute value.
For the rank-truncation heuristic in the spirit of Don't Mess with Mister-in-Between, no reported result was found on Lacuna for the embedding models we use. We implement it as SANS with the top-$k$ candidates removed, with $k$ tuned.
Two ablations isolate the key ingredient. In the flat-cap ablation, $\hat\pi_r \equiv 0$, so only $\kappa$ limits mass. This tests whether any cap helps, regardless of estimated risk. In the shuffled-curve ablation, $\hat\pi_r$ is borrowed from a random other relation. This tests whether relation-specific risk estimates matter.
Why not just…?
Why not just tune the SANS temperature and margin? A lower temperature flattens the weights and puts less mass on the top candidate. That is the main threat, since Kamigaito and Hayashi show that tuning alone can deliver large gains. A lower temperature, however, flattens weights for all candidates, including hard true negatives. The cap removes mass only where hidden truths are estimated to lie. The flat-cap and matched-temperature comparisons settle this directly. If a tuned temperature reaches the same MRR with the same planted-fact weight share, the calibrated cap is unnecessary, and we will say so.
Why not just drop the top-$k$ candidates? Truncation assumes the false-negative risk sits at a fixed rank for every relation. For one-to-many relations such as nationality or genre, many top candidates may be true. For functional relations, almost none are. The planted-fact curves $g_r$ measure this directly. If they turn out nearly identical across relations, truncation with a tuned $k$ is essentially our method, and the shuffled-curve ablation will show no loss.
Why not just filter candidates by schema types, as CAKE's commonsense sampling does? CAKE restricts negatives to entities of the valid type and reports an 11.5% MRR gain on FB15k-237. Type filtering removes easy negatives, but it keeps and even concentrates false negatives, because true unrecorded facts pass every type check. Filtering and capping are therefore complementary. We run a type-filtered candidate pool under both SANS and the capped adversary to test whether the gains add up.
Why not port AdvInfoNCE directly? AdvInfoNCE learns its per-negative shifts adversarially from the model's own scores, so a confidently scored false negative looks just like a hard negative. Our risk signal comes from held-out truths the model never trained on. Adapting AdvInfoNCE to relational queries is feasible and would be a useful extra baseline. We treat it as an optional baseline if its training schedule proves stable within the budget.
Proposed Experiments
The main runs cover FB15k-237, WN18RR and YAGO3-10 with filtered MRR and Hits@1/10 over five seeds. A scale check uses ogbl-wikikg2 with the sampled-candidate protocol of Cornell et al., who report that easy-negative evaluation can inflate MRR by up to 40 points. There we additionally evaluate against type-matched hard candidates, so that no method benefits from easy evaluation negatives.
Three checks decide the outcome. First, the planted-fact audit must show that SANS and KBGAN put substantially more weight on hidden truths than uniform sampling does. If they do not, the false-negative motivation fails for embedding models. Second, the capped adversary must reduce that share while keeping negative-gradient norms near SANS levels, so that the fix does not bring back easy negatives. Third, the calibrated cap must beat the flat-cap ablation and truncation on relations whose planted-fact curves differ most. If the permuted-weight SANS matches real SANS, we also have a clear answer to the open question of whether self-adversarial gains come from hardness or from smoothing.
References
- RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
- Empowering Collaborative Filtering with Principled Adversarial Contrastive Loss
- Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors
- KBGAN: Adversarial Learning for Knowledge Graph Embeddings
- Comprehensive Analysis of Negative Sampling in Knowledge Graph Representation Learning
- Unified Interpretation of Smoothing Methods for Negative Sampling Loss Functions in Knowledge Graph Embedding
- Don't Mess with Mister-in-Between: Improved Negative Search for Knowledge Graph Completion
- Negative Sampling with Adaptive Denoising Mixup for Knowledge Graph Embedding
- Optimal Embedding Guided Negative Sample Generation for Knowledge Graph Link Prediction
- CAKE: A Scalable Commonsense-Aware Framework For Multi-View Knowledge Graph Completion