Unified Interpretation of Softmax Cross-Entropy and Negative Sampling: With Case Study for Knowledge Graph Embedding

Hidetaka Kamigaito, Katsuhiko Hayashi

In the world of Knowledge Graph Embedding (KGE), researchers have long toggled between two primary loss functions: Softmax Cross-Entropy (SCE) and Negative Sampling (NS). While NS was originally designed as a computationally efficient approximation of SCE, the theoretical bridge between them has remained murky.

In their paper, "Unified Interpretation of Softmax Cross-Entropy and Negative Sampling: With Case Study for Knowledge Graph Embedding," Hidetaka Kamigaito and Katsuhiko Hayashi provide the missing link. By using the mathematical framework of Bregman divergence, they offer a unified perspective that explains when and why one loss function outperforms the other.

TL;DR

The authors use Bregman divergence to prove that Softmax Cross-Entropy and Negative Sampling (with uniform noise) target the same optimal distribution. However, SCE fits training data more aggressively than NS, making it superior for flexible models but prone to issues when score functions are bounded.

What Problem Does This Paper Address?

Knowledge graphs (like Freebase or WordNet) are massive networks of entities and relations. KGE models represent these as vectors to predict missing links. To train these models, you need a loss function.

The choice between SCE and NS is often treated as an empirical trial-and-error process. There was no clear theoretical basis to compare them fairly. This paper addresses that gap, providing a mathematical foundation to understand their relationship and the "objective distribution"—the ideal distribution a model tries to reach at its optimal solution.

Methods

The researchers leverage Bregman divergence, a generalized way to measure the distance between two distributions. By choosing different "generator functions" ($\Psi$), they show that both SCE and NS can be derived from the same framework.

Key methodological contributions include:

  • Objective Distribution Derivation: They mathematically define the "target" distribution for various flavors of NS and SCE.
  • Mapping Variants: They show that Self-Adversarial Negative Sampling (SANS) is theoretically similar to SCE with Label Smoothing (LS).
  • Convexity Analysis: They analyze the first and second-order derivatives of the loss functions to show that SCE is strictly convex, while NS is not, explaining why SCE "fits" data more strongly.

Datasets

The authors validated their theory using two standard KGE benchmarks:

  • FB15k-237: A subset of Freebase where inverse relations have been removed to make link prediction harder.
  • WN18RR: A subset of WordNet designed to prevent models from "cheating" via simple reciprocal relations.

They also analyzed the KL divergence between training and test sets across other datasets like YAGO3-10, Kinship, UMLS, and Nations to understand how data distribution affects overfitting.

Key Insights and Ideas

  • The "Strong Fitting" Property: SCE imposes a much higher penalty on prediction errors than NS. As seen in Figure 1, the divergence curve for SCE is much steeper than for NS. This means SCE forces the model to match the training data more precisely. Divergence comparison showing SCE's higher penalty
Figure 1: Divergence between 0.5 and p in dΨ(z) for each Ψ(z).
  • The Bounded Score Trap: Models like TransE and RotatE use score functions that are mathematically bounded (they cannot express infinitely positive values). Because SCE involves a normalization term (the "softmax"), it is very difficult for these bounded models to reach the high probability values SCE demands. This explains why NS often performs better for these specific architectures.
  • SANS as Smoothing: The popular SANS technique is effectively a form of smoothing. The authors show it behaves similarly to SCE with label smoothing, which helps explain why it improves generalization on noisy or sparse datasets.

Key Results

The theoretical findings were backed by extensive experiments across multiple KGE architectures (TuckER, RESCAL, ComplEx, DistMult, TransE, and RotatE).

  • SCE Dominance in Flexible Models: For "flexible" models like TuckER and RESCAL (which have no score bounds), SCE consistently outperformed NS. For example, on FB15k-237 with TuckER, SCE achieved an MRR of 0.338 compared to 0.257 for NS.
  • NS Resilience in Bounded Models: In models like RotatE, NS and SANS remained competitive or superior because they don't suffer from the "normalization pressure" of SCE.
  • Pre-training Success: The authors found that SANS and SCE with Label Smoothing are excellent pre-training methods, as they help the model learn a more generalized distribution before fine-tuning.

The following table summarizes their theoretical mapping between the two loss families: Summary of theoretical findings

Summary of theoretical findings

Limitations and Future Work

While the paper provides a robust framework, the authors acknowledge a few areas for further exploration:

  • SANS Approximation: The derivation for SANS is an approximation based on training dynamics, not a closed-form analytical solution.
  • Frequency-based Noise: While common in word embeddings (like word2vec), frequency-based noise (NS w/ Freq) didn't help much in KGE because it shifts the data distribution too drastically for these specific graph datasets.
  • Out-of-Domain Data: The authors suggest that future work should investigate how these loss functions behave when the test data comes from a different distribution than the training data.

Summary updated

Abstract

In knowledge graph embedding, the theoretical relationship between the softmax cross-entropy and negative sampling loss functions has not been investigated. This makes it difficult to fairly compare the results of the two different loss functions. We attempted to solve this problem by using the Bregman divergence to provide a unified interpretation of the softmax cross-entropy and negative sampling loss functions. Under this interpretation, we can derive theoretical findings for fair comparison. Experimental results on the FB15k-237 and WN18RR datasets show that the theoretical findings are valid in practical settings.
BibTeX
@inproceedings{kamigaito2021unified,
  author = {Hidetaka Kamigaito and Katsuhiko Hayashi},
  title = {{Unified Interpretation of Softmax Cross-Entropy and Negative Sampling: With Case Study for Knowledge Graph Embedding}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}

Loading related content...

Figure