Distributional Negative Sampling for Knowledge Base Completion

Alfio Gliozzo; Sarthak Dash

REVIEW 4 major objections 5 minor 2 cited by

Distributional Negative Sampling for Knowledge Base Completion

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Training knowledge-base models on plausible false statements instead of random negatives improves link prediction accuracy.

desk verdict The DNS negative-sampling trick is clever and plausibly useful, but the paper's own Table 2 contradicts its universal improvement claim and the baselines are not controlled. read the letter →

arxiv 1908.06178 v1 pith:UUES6BPF submitted 2019-08-16 cs.LG cs.AIstat.ML

Sarthak Dash , Alfio Gliozzo This is my paper · ORCID

classification cs.LGcs.AIstat.ML

keywords knowledgebasecompletionnegativesamplinglinkpredictiondistributionalsimilaritygraphembeddingsTransERESCALmeanreciprocalrank

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that random negative sampling in knowledge base completion generates mostly nonsensical assertions that give the model little to learn from, and proposes Distributional Negative Sampling (DNS) to replace it. DNS corrupts a triple by replacing an entity with another entity whose learned embedding is similar, so the resulting negative is a plausible but false statement. The authors claim that using DNS in place of random sampling improves Mean Reciprocal Rank and Hits@1 for two KBC models, TransE and RESCAL, across three benchmarks, and that training converges in fewer epochs. A sympathetic reader would care because this is a drop-in change to the training loop that needs no extra supervision and makes better use of the model's own learned representations.

What carries the argument

The load-bearing mechanism is Algorithm 1. For each training triple, DNS picks whether to corrupt the head or tail entity by a Bernoulli draw, then computes the cosine similarity between the chosen entity and every other entity in the KB. For each candidate entity, it accepts the candidate as a negative with probability max(0, cosine similarity), skipping any candidate that would form a true triple already in the training set. Because the acceptance probability is proportional to similarity, the negative set concentrates on plausible alternatives; because the step is stochastic, there remains a small chance of sampling unrelated entities, which preserves exploration. The same network's embeddings are reused to compute similarity, so the sampler sharpens as training proceeds, and the number of negatives per positive emerges automatically from the accept-reject step instead of being a tuned hyperparameter.

What would settle it

Measure, at an early and a late epoch, the fraction of DNS-generated negatives that actually occur as true triples in the validation or test set, and compare that fraction with the same fraction for random negatives. DNS's argument predicts this fraction is low; if DNS negatives are true triples as often as or more often than random ones, then the sampler is not producing 'highly likely false' statements and the reported gains must come from some other effect.

Watch

Extended reading notes

Core claim

The paper's central claim is that meaningful negatives, meaning plausible false assertions produced by substituting an entity with a distributionally similar one, provide a stronger training signal than random negatives, and that the similarity signal can be read off from the entity embeddings the KBC model is already learning. DNS therefore creates a positive feedback loop: better embeddings make similar entities more likely to be sampled as negatives, and training on those harder negatives makes the embeddings better. The paper reports that DNS beats random sampling on nearly every metric in five of the six algorithm-dataset settings, with the largest gains in Hits@1, and that DNS reaches a given filtered MRR in fewer epochs.

Load-bearing premise

The method assumes that cosine similarity between the KBC model's own entity embeddings is a reliable measure of whether two entities would make a plausible false statement, even in the early epochs when those embeddings are barely trained.

Editorial extensions

If this is right

If DNS is correct, any embedding-based KBC model can be improved by swapping the negative sampler, with no architectural change and no new labels.
DNS should reduce the number of training epochs needed to reach a given accuracy, since hard negatives continue to contribute nonzero gradient when random negatives would already satisfy the margin.
DNS removes the need to cross-validate the number of negative samples per positive, because the accept-reject mechanism sets it automatically.
Because the paper reports the largest Hits@1 gains, DNS most helps applications that need the top-ranked prediction to be right, not just a high rank among ten.
The paper explicitly suggests that the same sampling idea could transfer to other tasks that corrupt units into negatives, such as relation extraction, where random corruption currently dominates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural stress test is to split negatives by relation type: DNS's similarity ignores the relation of the triple being corrupted, so for relations where similar entities are often valid alternatives, DNS may push down true facts; conditioning similarity on the relation is a testable extension.
The reported convergence speedup may be larger on datasets with many entities per type, where random sampling is most likely to produce nonsense; on small or sparse KBs the benefit could shrink.
The accept-reject idea could be applied to any task that builds negatives by corrupting discrete units, but the cosine-similarity proxy would need to be replaced by a unit-level similarity appropriate to that task.
DNS's gains are measured only on two model families; the same sampler might behave differently on models with very different embedding geometries, such as those that use complex-valued or graph-neural representations.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

I'll cut to the chase: the paper has a genuinely neat idea—DNS, sampling negatives by cosine similarity using the very model being trained—but it hurts its own case. Its own Table 2 shows TransE with DNS underperforming TransE with random sampling on FB15k (MRR 43.0 vs 46.3, Hits@10 63.9 vs 74.9), while Section 4 claims DNS wins everywhere. That's not a minor blemish; it directly contradicts the abstract's 'significant improvement.'

DNS is new, as far as I can tell: stochastic, self-referential, no external type data, no pre-trained selector. That alone is worth something. The intuition—hard negatives that are plausible but false—is sensible, and the convergence plots on WN18RR (Figure 2) suggest it can help RESCAL. The idea deserves follow-up.

The problems are all in the evidence. RNS baselines for TransE and RESCAL are borrowed from Nickel et al. (2016b) rather than re-run with the same code, hyperparameters, and early stopping; the WN18RR TransE RNS row is missing MRR and Hits@1; there are no error bars; and unresolved citation placeholders (for the GAN and Fast-TransX) make reproducibility harder. The reader's circularity worry doesn't land—the test triples are held out, so the success metric isn't circular—but the universal claim is overreach even with footnote 5. A controlled comparison would settle whether DNS is actually better, not just different.

This is for someone working on negative sampling or contrastive learning who wants a simple trick to try. It's not a paper to trust for benchmarks. If I were the editor, I wouldn't desk reject it—the idea is plausible and fixable—but I'd send it to a referee with instructions to demand a same-code RNS baseline, complete results, and a rewritten abstract. As is, it's a workshop-level draft.

Referee Report

4 major / 5 minor

Summary. The paper proposes Distributional Negative Sampling (DNS), a training-time negative sampler for knowledge base completion. Instead of corrupting a positive triple with a uniformly random entity, DNS computes cosine similarities between the entity being replaced and all other entities using the model's current embeddings, and accepts each candidate entity as a negative with probability equal to its (clamped) cosine similarity. The authors evaluate DNS against random negative sampling (RNS) for TransE and RESCAL on FB15k, FB15k-237, and WN18RR, reporting filtered MRR, Hits@10, and Hits@1. They claim in the abstract and Section 4 that DNS gives significant improvements over RNS, and in Section 5 they argue qualitatively that DNS converges faster and produces more meaningful negatives.

Significance. If the central claim were established, DNS would be a simple and appealing drop-in replacement for random negative sampling in embedding-based KBC, with no additional data or supervision required. The idea is intuitive and the qualitative example in Table 3 is instructive. The paper also has the merit of explicitly acknowledging one counterexample to its own headline claim. However, the evaluation is not controlled: RNS baselines are borrowed from a different paper, one baseline row is incomplete, no variance or significance information is reported, and the method's own table contradicts the universal improvement claim. The distributional hypothesis underlying the sampler is plausible, but the evidence offered is anecdotal and limited to a single query entity. Because the central empirical claim fails on the paper's own numbers, the contribution as stated is not established.

major comments (4)

[Section 4, Table 2] The statement in Section 4 that 'DNS outperforms RNS on all the considered KBC algorithms and across all benchmarks and evaluation metrics' is directly contradicted by Table 2. On FB15k, TransE(DNS) achieves MRR 43.0 and Hits@10 63.9, while TransE(RNS) achieves MRR 46.3 and Hits@10 74.9. Footnote 5 acknowledges this exception but does not investigate it, and the abstract's claim of a 'significant improvement' in MRR is therefore unsupported for this setting. The paper should either restrict its claim to the settings where DNS wins, or explain why the FB15k TransE result does not undermine the general claim.
[Section 4, Table 2] The RNS baselines for TransE and RESCAL are borrowed from Nickel et al. (2016b) rather than produced with the same code, hyperparameters, and experimental pipeline as the DNS runs. In addition, the WN18RR TransE(RNS) row reports only Hits@10 and lacks MRR and Hits@1. With no error bars, no multiple-seed runs, and no same-code controlled baseline, it is impossible to determine whether the differences in Table 2 are due to the sampling strategy or to implementation details, hyperparameter choices, or randomness. A controlled comparison under identical training conditions is essential to support the paper's central claim.
[Section 3, Algorithm 1 and Section 5] DNS uses the model's own embeddings, at the current training state, to select negatives for that same model. The paper asserts that this creates a 'virtuous circle' and that the similarity signal becomes meaningful over time, but the only supporting evidence is Table 3, which shows nearest neighbors of a single entity (DVD) on one dataset (FB15k-237). No quantitative measure is given of how well embedding similarity tracks type similarity, or of how the sampler behaves in the first epochs when embeddings are not yet informative. The possibility that DNS could amplify early embedding errors is not addressed. The faster-convergence claim in Section 5 is based on one figure for RESCAL on WN18RR over the first 50 epochs; more systematic evidence is needed.
[Section 3, Equation (1) and Algorithm 1] The number of negative samples per positive triple is an uncontrolled variable between DNS and RNS. RNS is described in Section 3 as using a fixed number C of negatives, whereas Algorithm 1 accepts each candidate entity with probability max(0, cosine similarity). The expected number of DNS negatives therefore varies with the similarity distribution and changes during training. If the DNS runs effectively use a different negatives-to-positives ratio than the RNS runs, the comparison in Table 2 is confounded. The paper should either match the number of negatives across conditions, or report the actual number of negatives generated per triple and analyze sensitivity to C for both samplers.

minor comments (5)

[Related Work and Table 2] The GAN-based negative sampling reference in Section 2 appears as '?' and the Fast-TransX implementation in Table 2 has no citation; these references need to be completed.
[Abstract and Introduction] The Introduction states that DNS gives 'consistent and significant improvement in five out of six settings', while Section 4 claims it outperforms RNS in all settings. The paper should state the claim consistently and precisely, acknowledging the FB15k TransE exception.
[Section 5, Table 3] The caption and text of Table 3 are ambiguous about whether the numbers shown are cosine similarities or softmax probabilities. The text later computes the 'odds' of VHS via a softmax, but the table values appear to be raw similarities; please clarify.
[Section 5] The sentence 'as per LCWA this assertion is counted as less positive' should read 'counted as negative' or 'counted as unseen', since the Local Closed World Assumption treats unobserved triples as negative.
[Algorithm 1, line 4] The comment 'Use bernoulli sampling to conclude that t should be corrupted' is implementation-specific and appears inside the pseudocode; the Bernoulli choice of whether to corrupt the head or tail should be described in the text rather than embedded as a code comment.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: DNS's self-referential negative sampling is a training-feedback mechanism, and the claimed gains are measured on held-out test triples independent of the sampler.

full rationale

The paper's derivation chain is not circular. DNS alters negative-sampling during training by using cosine similarity over the current entity embeddings to choose corrupted entities, and those embeddings are themselves updated with DNS-generated negatives. This is a feedback loop, but the central claim is that DNS improves final link-prediction accuracy over RNS, measured on held-out test triples by filtered MRR, Hits@10, and Hits@1. At evaluation time the DNS sampler plays no role; the model ranks all entities for each test triple. Therefore the reported improvement is not equivalent by construction to the sampler's inputs. Algorithm 1's acceptance probability max(0, cosine similarity) is a stated heuristic assumption, not a quantity fitted to the evaluation metric. RNS baselines are borrowed from Nickel et al. (2016b), an external reference rather than a self-citation, and no load-bearing argument reduces to a self-citation chain. The paper's own Footnote 5 and Table 2 reveal an exception to the universal claim (TransE DNS underperforms TransE RNS on FB15k MRR and Hits@10), but that is an internal-consistency or evidence-quality issue, not circularity. The 'virtuous circle' language in Sections 1 and 5 is an empirical convergence argument supported by Figure 2 and Table 3, not a definitional identity. No equation is shown to be equal to its own input, and no fitted parameter is renamed as a prediction. Hence there is no specific circular step to quote.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The method rests on standard LCWA and the distributional hypothesis, and on the ad hoc assumption that cosine similarity of the model's own embeddings is a reliable guide for negative selection during training. Hyperparameters were tuned on validation data. No new entities, forces, or dimensions are introduced.

free parameters (5)

margin gamma = 10.0 for TransE, 5.0 for RESCAL
Tuned by grid search on the validation set; affects the ranking loss and thus the comparison.
embedding dimension = 100 (TransE), 200 (RESCAL)
Tuned by grid search; larger dimensions generally improve capacity.
early-stopping patience = 20 epochs
Chosen on validation filtered MRR; affects number of training epochs and final model.
max epochs = 1000
Cap on training; early stopping may stop earlier.
batch size = not stated
Batch size is an input to Algorithm 1 but its value is not reported, affecting the sampling dynamics.

assumptions (4)

domain assumption Local Closed World Assumption (LCWA)
Used to generate negatives by corrupting true triples; any unseen triple is treated as negative. Introduced in Section 3.
domain assumption Distributional hypothesis: entities sharing many relations tend to have the same type
Basis for using distributional similarity to generate meaningful negatives; cited from Harris 1954 in Section 3.
domain assumption Cosine similarity of model embeddings is a valid proxy for semantic relatedness
Central to Algorithm 1; asserted in Section 3 with no formal justification beyond intuition.
ad hoc to paper The model's own embeddings are informative enough for negative selection throughout training
The paper relies on the 'virtuous circle' that DNS improves embeddings and better embeddings improve DNS; Table 3 shows early epochs yield noisy similarities, so this premise is not guaranteed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributional Negative Sampling for Knowledge Base Completion." pith.science (2026). https://pith.science/paper/UUES6BPF

@misc{pith2026190806178,
  author       = {Pith},
  title        = {Pith review of: Distributional Negative Sampling for Knowledge Base Completion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UUES6BPF}},
  note         = {Machine review of arXiv:1908.06178}
}

read the original abstract

State-of-the-art approaches for Knowledge Base Completion (KBC) exploit deep neural networks trained with both false and true assertions: positive assertions are explicitly taken from the knowledge base, whereas negative ones are generated by random sampling of entities. In this paper, we argue that random sampling is not a good training strategy since it is highly likely to generate a huge number of nonsensical assertions during training, which does not provide relevant training signal to the system. Hence, it slows down the learning process and decreases accuracy. To address this issue, we propose an alternative approach called Distributional Negative Sampling that generates meaningful negative examples which are highly likely to be false. Our approach achieves a significant improvement in Mean Reciprocal Rank values amongst two different KBC algorithms in three standard academic benchmarks.

Figures

Figures reproduced from arXiv: 1908.06178 by the authors.

**Figure 1.** Our intuition is that the entity vectors trained by KBC deep networks represent well the distributional properties of entities in the original KB. Therefore, cosine similarity between those vectors can be used as a proxy for the semantic relatedness. This enables us to define the DNS algorithm as described by Algorithm 1 below. Let us see in detail what’s happening in Algorithm [1] below. Let P denote all negative t… view at source ↗

**Figure 1.** DNS Architecture using an off-the-shelf KBC model. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** The left column represents Filtered MRR vs. Number of epochs, whereas the right column represents [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Enhancing PyKEEN with Multiple Negative Sampling Solutions for Knowledge Graph Embedding Models
cs.LG 2025-08 conditional novelty 4.0 of 10

A PyKEEN extension integrates seven known negative sampling strategies; experiments on FB15K and WN18 show pool sizes shrink sharply and random fallback often dominates at high sample counts.
A Survey of Task-Oriented Knowledge Graph Reasoning: Status, Applications, and Prospects
cs.AI 2025-04 conditional novelty 4.0 of 10

A task-oriented survey of knowledge graph reasoning, covering six task categories, benchmark datasets, downstream applications, and future challenges.

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages · cited by 2 Pith papers

[1]

Freebase: a collaboratively created graph database for structuring human knowledge

Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages 1247--1250. AcM, 2008

work page 2008
[2]

Learning structured embeddings of knowledge bases

Antoine Bordes, Jason Weston, Ronan Collobert, Yoshua Bengio, et al. Learning structured embeddings of knowledge bases. In AAAI , volume 6, page 6, 2011

work page 2011
[3]

Translating embeddings for modeling multi-relational data

Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems , pages 2787--2795, 2013

2013
[4]

Special issue on learning from imbalanced data sets

Nitesh V Chawla, Nathalie Japkowicz, and Aleksander Kotcz. Special issue on learning from imbalanced data sets. ACM Sigkdd Explorations Newsletter , 6(1):1--6, 2004

work page 2004
[5]

Convolutional 2d knowledge graph embeddings

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. arXiv preprint arXiv:1707.01476 , 2017

arXiv 2017
[6]

Distributional structure

Zellig S Harris. Distributional structure. Word , 10(2-3):146--162, 1954

work page 1954
[7]

Adam: A method for stochastic optimization

Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014

arXiv 2014
[8]

Analysis of the impact of negative sampling on link prediction in knowledge graphs

Bhushan Kotnis and Vivi Nastase. Analysis of the impact of negative sampling on link prediction in knowledge graphs. arXiv preprint arXiv:1708.06816 , 2017

arXiv 2017

Show all 19 references

[9]

Modeling relation paths for representation learning of knowledge bases

Yankai Lin, Zhiyuan Liu, Huanbo Luan, Maosong Sun, Siwei Rao, and Song Liu. Modeling relation paths for representation learning of knowledge bases. arXiv preprint arXiv:1506.00379 , 2015

2015 arXiv
[10]

Wordnet: a lexical database for english

George A Miller. Wordnet: a lexical database for english. Communications of the ACM , 38(11):39--41, 1995

1995
[11]

A three-way model for collective learning on multi-relational data

Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In ICML , volume 11, pages 809--816, 2011

2011
[12]

A review of relational machine learning for knowledge graphs

Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE , 104(1):11--33, 2016

2016
[13]

Holographic embeddings of knowledge graphs

Maximilian Nickel, Lorenzo Rosasco, Tomaso A Poggio, et al. Holographic embeddings of knowledge graphs. In AAAI , pages 1955--1961, 2016

1955
[14]

Proje: Embedding projection for knowledge graph completion

Baoxu Shi and Tim Weninger. Proje: Embedding projection for knowledge graph completion. In AAAI , pages 1236--1242, 2017

2017
[15]

Reasoning with neural tensor networks for knowledge base completion

Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in neural information processing systems , pages 926--934, 2013

2013
[16]

Observed versus latent features for knowledge base and text inference

Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality , pages 57--66, 2015

2015
[17]

Complex embeddings for simple link prediction

Th \'e o Trouillon, Johannes Welbl, Sebastian Riedel, \'E ric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference on Machine Learning , pages 2071--2080, 2016

2016
[18]

Knowledge graph embedding by translating on hyperplanes

Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In AAAI , pages 1112--1119, 2014

2014
[19]

An interpretable knowledge transfer model for knowledge base completion

Qizhe Xie, Xuezhe Ma, Zihang Dai, and Eduard Hovy. An interpretable knowledge transfer model for knowledge base completion. arXiv preprint arXiv:1704.05908 , 2017

2017 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Freebase: a collaboratively created graph database for structuring human knowledge

Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages 1247--1250. AcM, 2008

work page 2008

[2] [2]

Learning structured embeddings of knowledge bases

Antoine Bordes, Jason Weston, Ronan Collobert, Yoshua Bengio, et al. Learning structured embeddings of knowledge bases. In AAAI , volume 6, page 6, 2011

work page 2011

[3] [3]

Translating embeddings for modeling multi-relational data

Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems , pages 2787--2795, 2013

2013

[4] [4]

Special issue on learning from imbalanced data sets

Nitesh V Chawla, Nathalie Japkowicz, and Aleksander Kotcz. Special issue on learning from imbalanced data sets. ACM Sigkdd Explorations Newsletter , 6(1):1--6, 2004

work page 2004

[5] [5]

Convolutional 2d knowledge graph embeddings

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. arXiv preprint arXiv:1707.01476 , 2017

arXiv 2017

[6] [6]

Distributional structure

Zellig S Harris. Distributional structure. Word , 10(2-3):146--162, 1954

work page 1954

[7] [7]

Adam: A method for stochastic optimization

Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014

arXiv 2014

[8] [8]

Analysis of the impact of negative sampling on link prediction in knowledge graphs

Bhushan Kotnis and Vivi Nastase. Analysis of the impact of negative sampling on link prediction in knowledge graphs. arXiv preprint arXiv:1708.06816 , 2017

arXiv 2017