TL;DR
This paper bridges the theoretical gap between two common loss functions in knowledge graph embedding: Softmax Cross-Entropy (SCE) and Negative Sampling (NS). By using Bregman divergence, they show that these seemingly different losses can be unified, revealing that NS with uniform noise is equivalent to SCE, and that SCE generally fits the training data more strongly. This unified view helps in fairly comparing their performance and understanding their behavior.
What Problem Does This Paper Address?
In the field of knowledge graph embedding (KGE), models learn to represent entities and their relationships as vectors. Two popular methods for training these models are Softmax Cross-Entropy (SCE) and Negative Sampling (NS). While NS is computationally more efficient and widely used, its theoretical relationship with SCE has been unclear. This lack of understanding makes it difficult to fairly compare their performance and to choose the most appropriate loss function for a given task. The paper aims to provide a unified theoretical framework to interpret and compare these two loss functions.
Methods
The core of this paper's methodology lies in the application of Bregman divergence. Bregman divergence is a mathematical tool that measures the difference between two probability distributions. The authors use it to derive the "objective distribution" for both SCE and NS loss functions. The objective distribution represents the model's predicted probability distribution when the loss function is minimized. By analyzing these objective distributions, they can understand the theoretical relationship between the two loss functions. They also explore different types of noise distributions for NS, such as uniform noise and frequency-based noise, and analyze how these affect the objective distribution.
Datasets
The paper uses two standard benchmark datasets for knowledge graph embedding:
- FB15k-237: A widely used dataset for knowledge graph completion.
- WN18RR: Another popular dataset derived from WordNet, also used for knowledge graph completion.
Key Insights and Ideas
- Unified Interpretation: The paper successfully unifies SCE and NS loss functions under the framework of Bregman divergence, revealing their underlying theoretical connections.
- NS w/ Uniform Noise = SCE: A key finding is that Negative Sampling with a uniform noise distribution (NS w/ Uni) has the same objective distribution as Softmax Cross-Entropy (SCE). This means, in terms of what the model learns at its optimal solution, they are equivalent.
- SCE Fits Data More Strongly: The paper demonstrates that SCE generally fits the training data more strongly than NS. This is attributed to the divergence and convexity properties of the SCE loss function, which impose a larger penalty for deviations from the true distribution.
- SANS and SCE w/ LS are Similar: Self-Adversarial Negative Sampling (SANS) and SCE with Label Smoothing (SCE w/ LS) are shown to have similar objective distributions, suggesting they can offer comparable smoothing effects.
- Frequency-based Noise as Smoothing: Using frequency-based noise in NS (NS w/ Freq) acts as a smoothing mechanism for the objective distribution, potentially helping to prevent overfitting.
- Bounded Score Functions: NS is found to be more suitable for models with bounded score functions (like RotatE), which cannot express positive values, whereas SCE performs better with unbounded score functions.
Key Results
The experimental results on FB15k-237 and WN18RR datasets largely validate the theoretical findings.
- Performance Comparison: The paper shows that while SCE generally fits the training data better, the difference in performance between SCE and NS is not always significant, especially on datasets like WN18RR where the gap between training and test data is smaller.
- Pre-training Effectiveness: SANS and SCE w/ LS were found to be effective pre-training methods, improving performance on downstream KGE tasks. NS w/ Freq and SCE w/ BC showed less promising results, possibly due to the drastic change in data distribution caused by unigram noise.
- Model-Loss Interaction: The study highlights that the choice of loss function can interact with the model architecture. For instance, NS performs better with models like RotatE that have bounded score functions.
Limitations and Future Work
- Pre-training with Unigram Noise: The paper notes that while NS w/ Freq and SCE w/ BC were explored for pre-training, their effectiveness was limited. The authors suggest that the unigram noise might drastically alter the data distribution, making it unsuitable for KG datasets where the training-test data difference isn't very large.
- RotatE and SCE: For models like TransE and RotatE with bounded score functions, SCE's performance was sometimes hindered because its normalization term makes it difficult to represent values close to 1.
- Future Work: The authors suggest investigating the properties of these loss functions in "out-of-domain" data scenarios for future research.
Summary updated