From Translations to Boxes: Convexifying Knowledge Graph Embedding Approaches, TransE and BoxE

Abstract

Knowledge graphs (KGs) are often incomplete due to the inherent challenges in data curation. To address this issue, a variety of knowledge graph completion approaches have been proposed, among which Knowledge Graph Embedding (KGE) methods are particularly prominent. These approaches embed entities and relations into a latent space and learn to infer missing links. However, most existing KGE models rely on stochastic gradient descent (SGD), which lacks strong theoretical guarantees, particularly with respect to convergence and consistency. In contrast, convex optimization offers desirable properties, including global optimality guarantees, efficient solvers, and transparent formulations through explicit constraints. In this thesis, we leverage these advantages and introduce two of the first convex formulations of KGE models: convex TransE and convex BoxE. These models are derived from their SGD-based counterparts, TransE, a functional model based on vector translations, and BoxE, a spatial model representing relations as hyperrectangles. We present the convex formulations of these models and discuss the challenges that arise when adapting inherently non-convex components, such as negative sampling, into a convex framework. Furthermore, we empirically evaluate the proposed models and analyze their predictive performance relative to existing approaches. Our results highlight both the potential and the limitations of convex formulations for KGE, providing a foundation for future research in integrating optimization theory with representation learning.