SpeedE: Euclidean Geometric Knowledge Graph Embedding Strikes Back

Aleksandar Pavlovic, Emanuel SallingerNAACL 2024 · DOI

TL;DR

This paper introduces SpeedE, a novel Euclidean geometric knowledge graph embedding (gKGE) model that significantly improves efficiency without sacrificing performance. SpeedE achieves state-of-the-art results on knowledge graph completion (KGC) tasks, even outperforming existing models on challenging benchmarks, while requiring substantially less training time and fewer parameters.

What Problem Does This Paper Address?

Knowledge graph completion (KGC) aims to predict missing links (triples) in knowledge graphs (KGs). Geometric knowledge graph embedding (gKGE) models represent entities and relations as geometric shapes, offering intuitive interpretations. However, current high-performing gKGEs often require very high-dimensional embeddings and complex embedding spaces, leading to significant computational costs (time and memory). This limits their applicability in resource-constrained environments like mobile devices. While some methods have focused on simplifying embedding spaces or reducing dimensionality, few have addressed both simultaneously. This paper tackles this efficiency bottleneck by developing a lightweight gKGE that maintains strong KGC performance with low-dimensional embeddings.

Methods

SpeedE builds upon the ExpressivE model, a spatio-functional gKGE that uses hyper-parallelograms to represent relations. The authors identify that ExpressivE's efficiency is hampered by redundant parameters, particularly its relation-wise width vectors.

  1. Min_SpeedE: The first step is to simplify ExpressivE by replacing the relation-specific width vectors with a single shared width parameter. This significantly reduces the number of parameters and halves inference time while surprisingly retaining the ability to capture core inference patterns.
  2. SpeedE: To address the performance degradation on hierarchical relations caused by fixing the width, SpeedE introduces two carefully designed scalar parameters per relation: an "inside distance slope" and an "outside distance slope." These parameters allow for flexible adjustment of the distance function, crucial for representing hierarchical relationships, without compromising the efficiency gains of Min_SpeedE. The model also imposes constraints on these slopes to preserve the geometric interpretability.

Datasets

The authors evaluate SpeedE on three standard KGC benchmarks:

  • WN18RR: Extracted from WordNet, known for its many hierarchical relations.
  • FB15k-237: A subset of Freebase, containing both hierarchical and non-hierarchical relations.
  • YAGO3-10: A subset of YAGO, also featuring hierarchical and non-hierarchical relations.

Key Insights and Ideas

  • Efficiency is not a trade-off for performance: SpeedE demonstrates that it's possible to achieve high KGC performance with significantly reduced computational resources (time and memory).
  • Simplifying geometric representations works: By analyzing and simplifying the geometric components of existing models (like ExpressivE's width vectors), substantial efficiency gains can be realized without losing core capabilities.
  • Hierarchical relations are key: The performance boost of SpeedE, especially on datasets like WN18RR, is attributed to its improved ability to model hierarchical relations, a task where hyperbolic models were previously thought to excel.
  • Geometric interpretation is preserved: Even with efficiency improvements, SpeedE maintains the intuitive geometric interpretation of embeddings, which is a hallmark of gKGEs.

Key Results

  • Competitive KGC Performance: SpeedE is competitive with state-of-the-art (SotA) gKGEs on FB15k-237 and significantly outperforms them on YAGO3-10 and WN18RR, even under low-dimensional settings (d=32).
  • Efficiency Gains:
    • On WN18RR, SpeedE requires only a fourth of ExpressivE's parameters and a fifth of its training time to achieve the same KGC performance.
  • SpeedE trains approximately five times faster than ExpressivE and significantly faster than other SotA models like RotH and AttH.
  • SpeedE converges much faster than competing models, achieving a validation MRR of 0.490 in just 6 minutes, compared to 31 minutes for ExpressivE.
  • Hierarchical Relation Modeling: SpeedE significantly improves over ExpressivE and outperforms hyperbolic models like RotH on hierarchical relations, demonstrating its strength in this area.

Limitations and Future Work

  • Decoupling Entity and Relation Dimensionalities: The paper notes that both SpeedE and ExpressivE use the same dimensionality for entities and relations. Decoupling these could further improve efficiency, as entities are generally less complex than relations.
  • Automatic Pattern Mining: While gKGEs provide geometric interpretations, automatically and efficiently mining these learned patterns to make knowledge explicit remains an open challenge.
  • Novel Applications: Integrating knowledge graph embeddings with latent representations of large language models for novel practical applications is suggested as a future direction.

Summary updated

BibTeX
@inproceedings{pavlovic2024speede,
  author = {Aleksandar Pavlovic and Emanuel Sallinger},
  title = {{SpeedE: Euclidean Geometric Knowledge Graph Embedding Strikes Back}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.findings-naacl.6},
}
Figure