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