MQ uin E : a Cure for “ Z -paradox” in Knowledge Graph Embedding (2024)

Abstract: Knowledge graph embedding (KGE) models achieved state-of-the-art results on many knowledge graph tasks including link prediction and information retrieval. Despite the superior performance of KGE models in practice, we discover a deficiency in the expressiveness of some popular existing KGE models called Z-paradox . Motivated by the existence of Z-paradox, we propose a new KGE model called MQuinE that does not suffer from Z-paradox while preserves strong expressiveness to model various relation patterns including symmetric/asymmetric, inverse, 1-N/N-1/N-N, and composition relations with theoretical justification. Experiments on real-world knowledge bases indicate that Z-paradox indeed degrades the performance of existing KGE models, and can cause more than 20% accuracy drop on some challenging test samples. Our experiments further demonstrate that MQuinE can mitigate the negative impact of Z-paradox and outperform existing KGE models by a visible margin on link prediction tasks.

## introduction knowledge graphs (kgs) consist of many facts that connect real-world entities (e.g., humans, events, words, etc.) with various relations. each fact in a knowledge graph is usually represented as a triplet (h, r, t), where h, t are respectively the head and tail entities and r is the relation; the triplet (h, r, t) indicates that the head entity h has the relation r to the tail entity t. due to the prevalence of relational data in practice, kg has a wide range of applications including recommendation systems @xcite @xcite , natural language processing (nlp) @xcite , question answering (qa) @xcite and querying @xcite . embedding-based models @xcite have revolutionized certain fields of machine learning including kg in the past two decades. simply speaking, knowledge graph embedding (kge) models map each entity and relation into a vector or matrix and calculate the probability of a fact triple through some score functions. kge models are space and time efficient. more importantly, kge models such as transe @xcite , rotate @xcite , ote @xcite , etc., are quite expressive; it was shown that kge models if designed carefully, can capture various relation patterns including symmetry/asymmetry, inversion, composition, injective and non-injective relations. due to the efficiency and expressiveness of kge models, embeddingbased models have achieved state-of-the-art performance on many kg applications and are widely deployed in practice. despite the popularity of kge models on various kg applications, in this work, we discover a bottleneck, termed as "z-paradox", of the expressiveness of some existing kge models. below we give a short description and illustration of zparadox and present its formal definition and some related properties in section 3. ## related works we summarize some popular kge models in table c.2. we go through some existing kge methods and discuss how they relate to our work. translation distance based methods. translation distance based approaches evaluate the plausibility of fact triples by comparing the distances between the head and tail entity embeddings after some relation transformations. inspired by word2vec @xcite , @xcite first introduced the idea of translation invariance into the knowledge graph embedding domain and proposed the transe model. @xcite proposed rotate and characterized relations as rotations between the head and tail entities in complex space; it was shown that many desirable properties, such as symmetry/asymmetry, inversion, and abelian composition, can be achieved by rotate. @xcite extended rotate from the 2-dimensional complex domain to high-dimensional space. @xcite proposed dense to better model the complex composition relation patterns. bilinear semantic matching methods. @xcite first introduced the idea of tensor decomposition to model triple-relational data. @xcite later proposed a simple and effective bilinear model called dismult and achieved promising empirical results. subsequent works such as complex @xcite , tucker @xcite , dihedral @xcite , quate @xcite and seek @xcite adopted more complicated bilinear operations to either improve the expressiveness of dis-mult or decrease the model complexity. deep learning methods. vashishth et al. (2020) proposed compgcn to incorporate multirelational information into graph convolutional networks which leverages a variety of composition operations from knowledge graph embedding techniques to embed both nodes and relations in a graph jointly. dettmers et al. (2018) proposed conve and used convolutional neural networks to model multi-relational data. subsequent works (nathani et al., 2019; vashishth et al., 2020) brought more advanced neural network architectures such as graph convolutional networks and graph attention networks. more recently, wang et al. (2021) proposed m 2 gnn and embeds entities and relations into the mixed-curvature space with trainable heterogeneous curvatures. zhou et al. (2022) proposed jointe and adopted both 1-dimensional and 2-dimensional convolution operations to capture the latent knowledge more carefully. consider a kge model that suffers from zparadox. if e 1 → e 2 , e 3 → e 2 , e 3 → e 4 , i.e., (1) holds, then e 1 → e 4 must holds regardless the fact is true or not. it is obvious that a kge model that suffers from z-paradox has an inherent deficiency in its expressiveness, and a good kge model should be able to circumvent z-paradox. next, we show that a wide range of existing kge models indeed suffer from z-paradox and therefore have limited expressiveness. if s(h, r, t) can be expressed as for some functions f (•) and g(•), and s * := inf @xmath0, then the kge model suffers from z-paradox. proof. first, we notice that s(h, r, t remark 3.1. proposition 3.1 indicates that all existing translation-based kge models suffer from z-paradox, including transe @xcite , rotate @xcite , ote @xcite and mquade @xcite , etc. remark 3.2. kge models with bilinear score functions may also suffer from z-paradox under certain conditions. this is because bilinear score functions can be transformed into distance-based score functions. for example, we have when h, t both have fixed norms and r is an orthogonal matrix, then maximizing h t rt is equivalent to minimizing ∥rt -h∥ 2 . setting s(h, r, t) = ∥rt -h∥ 2 , by proposition 3.1, the model suffers from z-paradox provided that inf @xmath1. the above procedure can be applied to other bilinear kge models including dismult @xcite , complexex @xcite , dihedral @xcite , quate @xcite , seek @xcite , tucker @xcite . ## learning of mquine parameterization and regularization. we constrain the entity embedding matrices to be symmetric and parameterize each entity matrix e by a lower triangular matrix a and its transpose, i.e.,@xmath2. we use the frobenius norm of entity and relation embedding matrices as regularization. z-sampling. the negative sampling technique plays an important role in the training of kge models. classic negative sampling first sample a batch of observed facts. then for each fact (h, r, t) in the batch, fix the head entity h and relation r and sample m tail entities {t i } m lastly, the z-sampling uniform randomly samples k facts from s z and treats them as positive facts. the detailed algorithm of z-sampling is given in algorithm 1. z-sampling explicitly tries to minimize the score of positive facts in the z-pattern and maximize the score of negative facts simultaneously. experiments on kg benchmark datasets demonstrate the effectiveness of z-sampling; see section 5.6 for details. note that algorithm 1 can also be applied to ranking the head entity h (fixing r, t) with minor modifications, we omit the details. objective function. the loss function l (h,r,t) with respect to an observed fact (h, r, t) is ## experiments we conduct experiments to demonstrate the impact of z-paradox for existing kge models on kg benchmark datasets and evaluate the performance of mquine. first, we introduce the experimental setup in section 5.1, including the description of benchmark datasets, evaluation tasks, evaluation metrics and baseline methods. in section 5.3, we propose a metric called z-value to quantify the number of z-patterns related to a given fact and gather statistics of z-values to quantify the effect of z-patterns for our experimental datasets. for each dataset, we divide their test samples into easy, neutral, and hard cases according to their z-value. in section 5.4, we evaluate the performance of mquine against other competitive baseline methods on the easy, neutral, and hard cases respectively; we also report the overall improvement of mquine in section 5.5. lastly, we conduct an ablation study to evaluate the effectiveness of z-sampling with different kge models in section 5.6. ## conclusion in this paper, we introduce a phenomenon called z-paradox and show that many existing kge models suffer from it both theoretically and empirically. to overcome z-paradox, we propose a new kge model mquine that can circumvent z-paradox while maintaining strong expressiveness. experiments on real-world knowledge bases suggests that the z-paradox indeed degrades the performance of existing kge models and strongly support the effectiveness of mquine. limitations. there are a few limitations for mquine. z-paradox holds for translation-distance based score function and apply to bilinear and deep learning based kge models under some certain conditions.