Efficient Learning of Entity and Predicate Embeddings for Link Prediction in Knowledge Graphs

Pasquale Minervini, Claudia d'Amato, Nicola Fanizzi, Floriana EspositoURSW@ISWC 2015 · OpenReview

TL;DR

This paper tackles the computationally expensive training of knowledge graph embedding models, which are crucial for predicting missing links. They introduce adaptive learning rates and novel embedding models that significantly reduce training time by an order of magnitude while achieving state-of-the-art link prediction accuracy.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful structures for representing factual knowledge, but they are often incomplete. Predicting missing links (link prediction) is essential for discovering new facts. Recent advances use representation learning to embed entities and predicates into continuous vector spaces, achieving impressive results. However, a major bottleneck is the training process itself, which can take days for large KGs due to the need to learn optimal embeddings for all entities and predicates. This paper aims to drastically speed up this training process without sacrificing accuracy, making these powerful models more practical for large-scale applications.

Methods

The core contribution is a method for reducing training time by leveraging adaptive per-parameter learning rates. Instead of using a single global learning rate for all parameters (like in standard Stochastic Gradient Descent - SGD), they propose using methods like the Momentum Method and AdaGrad. These techniques adjust learning rates for individual parameters, allowing for faster convergence, especially for parameters that are updated less frequently.

In addition to the training efficiency improvements, the paper also introduces novel embedding models inspired by the successful TransE model. These include:

  • TransE+: Extends TransE by also translating the object embedding vector.
  • ScalE: Replaces the translation operation in TransE with a scaling operation, where predicates weight entity embeddings.
  • ScalE+: Combines the scaling operation with the translation of both subject and object embeddings.

These new models aim to preserve the scalability of TransE while potentially offering improved performance.

Datasets

The paper evaluates its methods on two widely used benchmark datasets for link prediction:

  • WORDNET (WN18)
  • FREEBASE (FB15K)

These datasets are standard for evaluating KG embedding models and contain a large number of entities, predicates, and triples.

Key Insights and Ideas

  • Adaptive learning rates are key to efficiency: The paper demonstrates that by adapting learning rates per parameter, training time can be dramatically reduced. This is particularly impactful for large KGs where some entities/predicates are updated much less frequently than others.
  • Novel embedding models offer competitive performance: The proposed TransE+, ScalE, and ScalE+ models, when trained with adaptive learning rates, achieve state-of-the-art results, sometimes even surpassing existing models despite significantly shorter training times.
  • Simplicity and scalability can be powerful: The proposed models, like TransE, maintain a linear scaling of parameters with the number of entities and predicates, making them suitable for very large KGs.
  • Trade-off between model complexity and underfitting: The paper suggests that simpler models (like TransE and its variants) might be less prone to underfitting on large datasets compared to more complex models, leading to better performance in certain scenarios.

Key Results

  • Significant Speedup: The proposed method using adaptive learning rates (specifically AdaGrad) reduces training time by an order of magnitude. For example, training that previously took days (reported in [10]) can now be done in minutes (e.g., ~30 minutes on FREEBASE for 100 epochs).
  • State-of-the-Art Accuracy: The proposed models (ScalE and ScalE+) trained with AdaGrad achieve record-breaking results on WORDNET (95.5% HITS@10) and FREEBASE (73.0% HITS@10), outperforming previous state-of-the-art methods.
  • Improved Accuracy with Less Training: Even with significantly fewer training epochs (100 vs. 1000 in prior work), the models trained with AdaGrad show improved accuracy (lower MEAN RANK, higher HITS@10) compared to models trained with SGD for longer.

Limitations and Future Work

  • Hyperparameter Tuning: While adaptive learning rates help, selecting the optimal hyperparameter settings for these methods still requires careful tuning, though the reduced training time makes this more feasible.
  • Model Capacity: The paper notes that simpler models might be less prone to underfitting but could potentially underperform if the underlying data structure is very complex and requires a more expressive model.
  • Future Work: The authors suggest that their work improves the effectiveness and applicability of embedding models for large and Web-scale KGs, implying that further exploration of these efficient training methods and novel model architectures is warranted. The availability of source code and datasets suggests a path for further research and validation.

Summary updated

BibTeX
@inproceedings{minervini2015efficient,
  author = {Pasquale Minervini and Claudia d'Amato and Nicola Fanizzi and Floriana Esposito},
  title = {{Efficient Learning of Entity and Predicate Embeddings for Link Prediction in Knowledge Graphs}},
  booktitle = {URSW@ISWC},
  year = {2015},
  url = {https://openreview.net/forum?id=Q0xQxMUMva2},
}
Figure