Geometric Algebra Based Embeddings for Static and Temporal Knowledge Graph Completion

Chengjin Xu, Mojtaba Nayyeri, Yung-Yu Chen, Jens Lehmann

TL;DR

This paper introduces GeomE and TGeomE, novel methods for Knowledge Graph Embedding (KGE) that leverage geometric algebra. By representing entities and relations as multivectors, these models achieve state-of-the-art performance on both static and temporal link prediction tasks, offering a more expressive and unified framework than existing approaches.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful tools for organizing information, but they are often incomplete. Knowledge Graph Completion (KGC) aims to fill these gaps, with link prediction being a key task. Traditional KGE methods embed entities and relations into vector spaces, but struggle to capture complex relational patterns and temporal dynamics. Temporal KGs, which include time-varying facts, present an even greater challenge. Existing methods often rely on complex or hypercomplex spaces, but this paper proposes a more general and flexible approach using geometric algebra.

Methods

The core innovation is the use of geometric algebra for KGE.

  • GeomE (Static KGs): This model represents entities and relations as multivectors in a geometric algebra space (specifically G² and G³). The geometric product is used to score triples. GeomE is designed to subsume existing models like ComplEx, QuatE, and RotatE, offering greater expressiveness.
  • TGeomE (Temporal KGs): This extends GeomE to handle temporal KGs by representing time steps as multivectors as well. It formulates temporal KGC as a 4-way tensor factorization problem and introduces a novel linear temporal regularizer to better capture temporal dynamics.

Datasets

The authors evaluated their models on several standard benchmarks:

  • Static KGs: FB15k, WN18, FB15k-237, WN18RR.
  • Temporal KGs: ICEWS14, ICEWS05-15, YAGO11k, Wikidata12k.

Key Insights and Ideas

  • Geometric Algebra's Expressiveness: Geometric algebra, with its multivectors and geometric product, provides a more unified and expressive framework for modeling complex relational patterns (like symmetry, inversion, and composition) compared to traditional complex or hypercomplex embeddings.
  • Subsumption of Existing Models: GeomE and TGeomE are designed to generalize and subsume many popular KGE and TKGE models, demonstrating their versatility.
  • Linear Temporal Regularizer: The proposed linear temporal regularizer is shown to be more effective than other temporal regularization techniques, leading to better performance and more meaningful time embeddings.
  • Time Granularity Matters: The choice of time granularity significantly impacts the performance of temporal KGE models, especially for datasets with long-tail time distributions.

Key Results

  • State-of-the-Art Performance: GeomE and TGeomE achieved state-of-the-art results on most static and temporal KG link prediction benchmarks across various metrics (MRR, Hits@K).
  • GeomE vs. QuatE2: GeomE models (especially GeomE+ and GeomE++) outperformed QuatE2, a strong hypercomplex baseline, on static KGs.
  • TGeomE vs. TKGE Baselines: TGeomE models showed significant improvements over existing TKGE models on temporal KGs, particularly on ICEWS datasets.
  • Linear Regularizer Superiority: The linear temporal regularizer consistently outperformed smoothing, rotational, and autoregressive temporal regularizers.

Limitations and Future Work

  • Computational Cost: While geometric algebra offers expressiveness, higher grades and embedding dimensions can increase computational complexity and memory usage. The paper notes that 2-grade multivector embeddings are often optimal.
  • Future Directions: The authors suggest exploring distance-based embedding models or neural network-based models using multivectors. They also plan to incorporate additional information like logic rules or temporal rules into their framework and investigate new ways to model time-aware facts involving time spans.

Summary updated

Abstract

Recent years, Knowledge Graph Embeddings (KGEs) have shown promising performance on link prediction tasks by mapping the entities and relations from a Knowledge Graph (KG) into a geometric space and thus have gained increasing attentions. In addition, many recent Knowledge Graphs involve evolving data, e.g., the fact (\textit{Obama}, \textit{PresidentOf}, \textit{USA}) is valid only from 2009 to 2017. This introduces important challenges for knowledge representation learning since such temporal KGs change over time. In this work, we strive to move beyond the complex or hypercomplex space for KGE and propose a novel geometric algebra based embedding approach, GeomE, which uses multivector representations and the geometric product to model entities and relations. GeomE subsumes several state-of-the-art KGE models and is able to model diverse relations patterns. On top of this, we extend GeomE to TGeomE for temporal KGE, which performs 4th-order tensor factorization of a temporal KG and devises a new linear temporal regularization for time representation learning. Moreover, we study the effect of time granularity on the performance of TGeomE models. Experimental results show that our proposed models achieve the state-of-the-art performances on link prediction over four commonly-used static KG datasets and four well-established temporal KG datasets across various metrics.
BibTeX
@article{xu2023geometric,
  author = {Chengjin Xu and Mojtaba Nayyeri and Yung-Yu Chen and Jens Lehmann},
  title = {{Geometric Algebra Based Embeddings for Static and Temporal Knowledge Graph Completion}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  doi = {10.1109/tkde.2022.3151435},
}
Figure