SparseTransX: Efficient Training of Translation-Based Knowledge Graph Embeddings Using Sparse Matrix Operations

Md Saidul Hoque Anik, Ariful Azad

TL;DR

This paper introduces SparseTransX, a novel framework that significantly speeds up the training of knowledge graph embeddings by replacing traditional dense matrix operations with efficient sparse matrix multiplications (SpMM). This approach reduces both training time and memory usage, enabling larger-scale KG learning.

What Problem Does This Paper Address?

Training knowledge graph embeddings (KGEs), especially for large knowledge graphs (KGs), is computationally intensive and memory-hungry. A major bottleneck identified by the authors is the gradient computation during the embedding extraction process, which often involves numerous fine-grained scatter-gather operations. These operations lead to irregular memory access patterns, increased backpropagation costs, and substantial memory demands for dense matrices, hindering the scalability of KGE models.

Methods

The core innovation of SparseTransX is the reformulation of KGE training, particularly for translation-based models, to leverage sparse matrix operations. Instead of directly gathering entity and relation embeddings and performing element-wise operations, the authors construct a sparse incidence matrix representing the KG triplets. This sparse matrix is then multiplied with the dense embedding matrix using optimized Sparse-Dense Matrix Multiplication (SpMM) kernels. This approach unifies multiple scatter-gather operations into a single, efficient SpMM operation for both forward and backward passes. The framework is designed to be general and can accommodate various translation-based models (TransE, TransR, TransH, TorusE) and is extensible to non-translational models. They also developed a library implementing these sparse formulations with various optimization techniques.

Datasets

The paper evaluates their approach on seven standard knowledge graph datasets:

  • FB15K
  • FB15K237
  • WN18
  • WN18RR
  • FB13
  • YAGO3-10
  • BioKG

Key Insights and Ideas

  • Gradient computation is the bottleneck: The paper highlights that gradient computation for embeddings is a dominant factor in training time for many KGE models, not just the forward pass.
  • SpMM as a unifying operation: By representing the KG as a sparse incidence matrix, the scatter-gather operations for embedding lookups and gradient updates can be unified into efficient SpMM operations.
  • Memory efficiency through sparsity: Replacing dense operations with sparse ones significantly reduces the memory footprint, allowing for larger batch sizes and potentially larger KGs to be processed.
  • Generalizability: The sparse formulation is not limited to a single model but can be applied to a family of translation-based models and extended to other KGE paradigms.

Key Results

  • Significant Speedup: SparseTransX achieves up to 5.3x speedup on CPU and 4.2x speedup on GPU compared to established frameworks like TorchKGE, DGL-KE, and PyG. These speedups are consistent across various datasets and models.
  • Reduced GPU Memory Usage: The framework demonstrates significantly lower CUDA memory allocation, with some models being up to 11x more efficient than TorchKGE.
  • Comparable Accuracy: The sparse approach does not negatively impact model accuracy. The paper shows that SpTransX achieves comparable or better Hits@10 accuracy than TorchKGE.
  • Efficient Large-Batch Training: The reduced memory requirements enable larger batch sizes, which in turn leads to faster training times.

Limitations and Future Work

  • Model-Specific Bottlenecks: While SpMM provides significant speedups, for models like TorusE, the dissimilarity function can become a bottleneck, limiting the overall speedup. Similarly, for TransH, the impact of SpMM is less pronounced due to a more complex computational graph.
  • Distributed Training: The paper mentions that the framework is designed to potentially support distributed training using PyTorch's DDP and FSDP wrappers, and a preliminary experiment on scaling with DDP is shown. However, a full investigation into distributed training performance and communication bottlenecks at extreme scales is left for future work.
  • Extensibility: While the paper discusses extending the approach to non-translational models like DistMult, ComplEx, and RotatE, further implementation and evaluation of these extensions would be valuable.
  • Dataset Size: The paper focuses on single-GPU/CPU experiments for clarity, but the true benefit of sparse operations might be more pronounced on even larger, more challenging datasets, which would require extensive distributed training.

Summary updated

Abstract

Knowledge graph (KG) learning offers a powerful framework for generating new knowledge and making inferences. Training KG embedding can take a significantly long time, especially for larger datasets. Our analysis shows that the gradient computation of embedding is one of the dominant functions in the translation-based KG embedding training loop. We address this issue by replacing the core embedding computation with SpMM (Sparse-Dense Matrix Multiplication) kernels. This allows us to unify multiple scatter (and gather) operations as a single operation, reducing training time and memory usage. We create a general framework for training KG models using sparse kernels and implement four models, namely TransE, TransR, TransH, and TorusE. Our sparse implementations exhibit up to 5.3x speedup on the CPU and up to 4.2x speedup on the GPU with a significantly low GPU memory footprint. The speedups are consistent across large and small datasets for a given model. Our proposed sparse approach can be extended to accelerate other translation-based (such as TransC, TransM, etc.) and non-translational (such as DistMult, ComplEx, RotatE, etc.) models as well. An implementation of the SpTransX framework is publicly available as a Python package in https://github.com/HipGraph/SpTransX.
BibTeX
@misc{anik2025sparsetransx,
  author = {Md Saidul Hoque Anik and Ariful Azad},
  title = {{SparseTransX: Efficient Training of Translation-Based Knowledge Graph Embeddings Using Sparse Matrix Operations}},
  year = {2025},
  eprint = {2502.16949},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.16949},
}
Figure