Optimal Embedding Guided Negative Sample Generation for Knowledge Graph Link Prediction
Authors: Makoto Takamoto
Daniel Onoro Rubio
Wiem Ben Rim
Takashi Maruyama
Bhushan Kotnis
Venue: Accepted by TMLR ()

Abstract: Knowledge graph embedding (KGE) models encode the structural information of knowledge graphs to predicting new links. 
Effective training of these models requires distinguishing between positive and negative samples with high precision. 
Although prior research has shown that improving the quality of negative samples can significantly enhance model accuracy, identifying high-quality negative samples remains a challenging problem. 
This paper theoretically investigates the condition under which negative samples lead to optimal KG embedding and identifies a sufficient condition for an effective negative sample distribution. Based on this theoretical foundation, we propose \textbf{E}mbedding \textbf{MU}tation (\textsc{EMU}), a novel framework that \emph{generates} negative samples satisfying this condition, in contrast to conventional methods that focus on \emph{identifying} challenging negative samples within the training data. 
Importantly, the simplicity of \textsc{EMU} ensures seamless integration with existing KGE models and negative sampling methods. 
To evaluate its efficacy, we conducted comprehensive experiments across multiple datasets. The results consistently demonstrate significant improvements in link prediction performance across various KGE models and negative sampling methods. Notably, \textsc{EMU} enables performance improvements comparable to those achieved by models with embedding dimension five times larger. 
An implementation of the method and experiments are available at \url{https://github.com/nec-research/EMU-KG}.

Published in Transactions on Machine Learning Research (04/2025)
Optimal Embedding Guided Negative Sample Generation for Knowledge Graph Link Prediction
Makoto Takamoto
makoto, wakamoto@@eclllll
NEC Laboratories Europe, Heidelberg, Germany
Danicl Oōro-Rubio
daniel onoro @neclab.cr... eu
NEC Laboratories Europe, Heidelberg, Germany
Wiem Ben Rim
University College London, London, UK
Takashi Maruyama
NEC Laboratories Europe, Heidelberg, Germany
Bhushan Kotnis
Coresystems AG, Zurich, Switzerland
Reviewed OpenReview: https: oppnrevee/perrvveeu. net/ forum? id= B4Syyyyii
Abstract
Knowledge graph embedding (KGE) models encode the structural information of knowledge graphs to predicting new links. Effective training of these models requires distinguishing be- tween positive and negative samples with high precision. Although prior rescarch has shown that improving the quality of negative samples can significantly enhance model accuracy, identifying high-quality negative samples remains a challenging problem. This paper theoreti- cally investigates the condition under which negative samples lead to optimal KG embedding and identifies sufficient condition for effective negative sample distribution. Based on this theoretical foundation, propose Embedding MUtation (FMU), novel framework that generates negative samples satisfying this condition, in contrast to conventional methods that focus on identifying challenging nogative samples within the training data. Importantly, the simplicity of EMU ensures seamless integration with existing KGE models and negative sampling methods. To evaluate its efficacy, we conducted comprehensive experiments across multiple datasets. The results consistently demonstrate significant improvements in link prediction performance across various KGE models and negative sampling methods. Notably, EMU enables performance improvements comparable to those achieved by models with embedding dimension five times larger. An implementation of the method and experiments are available at httts://github. wwwp:ecoooooooeeeeeeeeeeeeeeeeee http://ccccreeerrrc/////-E---
1 Introduction
Knowledge Graphs (KGs) are graph databases, consisting of a collection of facts about real-world entities that are represented in the form of (head, relation, trill--ripllts. With their logical structure reflecting human knowledge, KGs have proven thenselves be a crucial component many intelligent systems that tackle
complex tasks, such question answering (Huang et. al. 2019), recommender systems (Guo et. al. 2022

---

Published in Transactions on Machine Learning Research (04/2025)
information extraction (Gashteovski et al. 2020
machine reading (Weissenborn et al. 2018 and natural
language processing, such language modeling (Yang & Mitchell 2017 7 7 Logan et al.
2019 entity linking
[Radhakrishnan et al. 2018), and question answering (Saxena et al. 2022: Popular KGs such as Freebase
Bollacker et al. 2008). YAGO (Suchanck et al.) 2007), and WordNet (Miller 1995) have been instrumental
in driving advancements both academic research and industrial applications.
One of the major challenges that KGs face is their incompleteness; there may be numerous factually correct relations between entities in the graph that are not covered. To address this issue, the task of link prediction has emerged as fundamental research topic, aimed at filling in the missing links between entities in the graph. Among the various approaches to predicting these missing links, Knowledge Graph Embedding (KGE) methods have proven to be particularly effective. KGE methods encode entities and relations information into a low- www-dimensional embedding vector space, thus enabling link prediction using neural networks (Bordes
ct al.) 2013 Yang et al., 2015 Trouillon et al., 2016 Sun al.) 2019 Zhang et al., 2020 Abboud et al. 2020
Zhu et al. 2021 Tran & Takasu 2022).
Various methods have been developed to improve the accuracy of KGE predictions. For instance, Rufineli et al. (2020) showed that using contrastive learning improves the model's prediction accuracy, irrespective of the embedding models used. However, to effectively train model with contrastive learning, it is essential to prepare hard-negative samples that are sufficiently challenging for the model to avoid penalizing true triplets. Although there has been a significant amount of research into effective negative sampling methods (Bordes
et al. 2013 Sun et al., 2019 Zhang et al.] 2019 Ahrabiin et al. 2020 Zhang et al.) 2021] Lin et al. 2023] Yao al., 2023), finding a powerful yet efficient negative sampling method remains an open problem in the research community.
In this paper, conduct a theoretical investigation into the conditions under which negative samples contribute to optimal embedding in knowledge graph embedding (KGE) models and identify sufficient condition that the negative sample distribution must satisfy. Building on this thcoretical insight, we propose Embedding MUtation (EMU), a novel approach for the generation of negative samples tailored to the KGE link prediction task. Unlike conventional methods that focus on údenlifying informative negative samples within the training dataset, EMU generates challenging negative samples for training triples by mutating their embedding vectors with components extracted from the target positive embedding vector. By manipulating the components of embedding vectors, EMU elficiently generates negalive samples that satisfy the condition for optimal embedding in KGE link prediction tasks. The simplicity of EMU facilitates seamless integration with existing KGE models and any negative sampling strategies. Through extensive experiments across various models and datasets, we demonstrate that EMU consistently delivers substantial performance improvemenss, highlighting its potential as a robust tool for link prediction. Notably, our experiments reveal that EMU enables models to achieve comparable performance to those with embedding dimensions five times larger, thereby reducing computational complexity.
In summary, our contributions are as follows:
We theoretically derive and identify condition for the negative sample distribution that leads to optimal KGE for link prediction tasks.
We introduce EMU, novel negative sample generation method that satisfies the identified condition. FMU is compatible with existing KGF models and negative sampling methods, achieving performance comparable to models with significantly larger embedding dimensions.
We perform comprehensive experiments to validate EMU, demonstrating consistent performance improvements across diverse KGE models, datascts, and negative sampling strategies.
2 Background and Notation
Background Link prediction is task that consists of finding new links among entities in a graph by leveraging existing entities and relations. Given triple (head, relation, tail), one of the elements is omitted
2

---

Published in Transactions on Machine Learning Research (04/2025)
(e.g., (head, relation, ?)), and the model is required to predict the missing element to form new valid triple KGE models have demonstrated their effectiveness for this task by learning to represent the knowledge graph structure in vector space. During training, KGE methods rely on negative sampling techniques because KGs only contain information about positive links. Negative sampling plays a critical role in embedding learning by proposing samples that represent node pairs known nol to be connected, contrasting with posilive samples, which represent connected node pairs. By incorporating negative samples, KGE models improve their ability distinguish between positive and negative links, enhancing their predictive performance in link prediction tasks. Varions techniques have been proposed to propose high-quality negative samples. One of the most widely used methods is Uniform Sampling (Bordes et al., 2013), which corrupts positive triples by replacing either the head or the tail entity with a uniformly sampled alternative from the knowledge graph. However, this approach has notable limitations, as it often produces uninformative samples, leading to limited performance gains due to the potential risk treating unknown positive samples in the KGs as negatives. To address these shortcomings, alternative negative sampling methods have been developed to propose more challenging, or 'hard,, negative samples, e.g., (Ahrabian al. 2020).
Notation We define a triplet as: x x= r,,r,t) where rh, t) denote (head, relation, and tail). These triplets often consists of discrete concepts, such as ('Joe Biden', 'president of', *USA'), or ("Tokyo', 'capital of', 'Japan'). To facilitate processing by machine learning models, they are usually mapped onto a contimuous, low-dimensional latent space z E Rd, where d is the dimensionality of the latent space. The mapping is carried out using an embedding function G. For instance, to embedding of the head entity is given by z G())0"), where 0h is the weight parameters of the embedding model. The feasibility of a triplet then evaluated using scoring function S(2) = s, where (z", zz, 22) is the latent representation of the input triple and is the computed score. The scoring function S varies across methods; For example, TransE (Bordes et al.) 2013 uses the Euclidean distance, while DistMult (Yang et al.) 2015) uses the dot-product.
Training involves minimizing a contrastive loss function that leverages the score of the positive sample s+ from the true triplet and the scores of negative samples {so, $1....} which are produced by corrupting the true triplct:
C(st, 81,-))
The loss function is designed to increase the score of the true triple while decreasing the score of negative samples. Depending on the specific method, this optimization can involve minimizing maximising distances (as in TransE) or optimizing similarities (as in DistMult).
3 Optimal Embedding for KGE and EMU
In this section, we illustrate how the negative samples generated by EMU lead to near-optimal embedding for KGE link prediction problems. First, we introduce the principle of negative sampling for graph reprosentation learning proposed by (Yang et al.] 2020), , and extend it to the KGE link prediction problems. Next, we provide a comprehensive description of EMU, Finally, we demonstrate that EMU generates negative samples that distribute isotropically around positive samples, which leads to the condition for the principle of negative sampling for KGE link prediction problems.
3.1 Optimal Embedding for KGE Representation Learning
Drawing upon the theoretical framework proposed by (Yang et al. 2020), referred to as Y20 henceforth, we posit that the target node and the positive node each characterized by their respective embedding vectors, u, v, are derived from the positive sample distribution: pa(ulp). An objective function for embedding
If either "head' 'tail' is omitted, the task is referred to as 'entity prodiction'; When the 'relation' is omitted, it is denoted as 'relation prediction'. While this paper mainly discusses the "tail" prediction scenario for simplicity, the proposed method is applicable to other cases as well.
3

---

Published in Transactions on Machine Learning Research (04/2025)
is: ((m) (e) (Bx-ppuu)) log o v) + (u'rp.(u'l)) log logo (-uo v)],
(2)
where Pr. (ulu) is the negative sample distribution and a-)) the sigmoid function, and & is numerical constant; and its corresponding empirical risk for node v is:
((0) T T
Σ log ( logo(u,
v)
Σ log o (-u' v),
(3)
where fui.-.. , are sampled from pa(ule) and fuh,.... 4ne} are sampled from Pn (u/e). We set 0 = [uo V,..., UN-1 v] as the parameters to be optimized, where {uor , are all the N nodes in the graph.
Under the assumption, Y20 derived the following equation, an empirical realization of the covariance measure proved in Y20:
1 0-) T pa(ulu)) (1)))))) 1
1 kul(ulu) 1:
(4)
Here, Or and 0* are the respective optimal parameters for J and J(v), Based on this theoretical finding, Y20 proposed principle of negative sampling which enables the optimal x(e) to converge to the optimal J(v) for graph representating alion learning. We exlend the idea to KG link prediction, assuming a KGE model 'DistMult" Yann et al. 2015) which calculate the scoring function as: SDistMult = =((² O z" o z²) where C is the element-wise multiplication. The extension is given as: Theorem 3.1. Assuming DistMult model, an empirical realization of the covariance measure can be given as,
B[] - -0) (
1
(p((z((uur) (111 - 1 + kpn (pn(z'/ohr) To
1
where vir z² o z and z², z", z' are the head, relation, and tail embedding vectors, respectively.
Proof. Equation can be derived by substituting z' and z @ z" for u, v the proof provided Y20.
3.2
EMU: Embedding MUtation
EMU is inspired from the gene 'mutation' technique utilized in evolutionary algorithms. In this study, we propose a new non-linear mixing approach that replaces a certain amount of the embedding vector components in the negative sample with the corresponding parts of the true positive vector components. This technique is simple yet effective means of enhancing the difficulty of negative samples by increasing their similarity to the true positive.
I Figure provides two-dinensional visualization of this phenomena.
The formal definition of the EMU technique is presented as follows:
žemU λEMU @ x + (1 XeMU) Oz
where λrMU E Rd is the EMU mixing vector that controls the number of embedding vector components to be mutations, which is denoted as np. λEMU a binary-valued vector whose components are generated through random sampling process that selects either zero or unity, with the probability of (1 - np /d, np ap/d). The symbol @ denotes element-wise multiplication, and z and z correspond to the positive and negative vectors to be mutated, respectively.
For the application of knowledge-bate base link prediction, we utilize Equation 6 to create the EMU negative tail sample by substituting z' (2*+, {z), zi. ... J-). We employ the generated samples as the EMU negative samples.
More concretely, the component of the vector λEMU Bd composed by np unities and up zeros whose order is randomly determined, e-g. (0, 0, For simplicity we the random sampling. The study of the better mutation vector XEMu our future work.
4

---

Published in Transactions on Machine Learning Research (04/2025)
Hard negative
True
Negative
x1
-1.0
2.0
-1.0
λEMU
+(1 λEMU)
x2
2.0
1.5
1.5
Mutation
Figure 1: EMU generates a new negative samples with embedding mutation. The figure illustrates a typical example that generate hard negative tails.
3.3 Theoretical Consideration on EMU
In the following, we demonstrate that EMU generates negative samples that are isotropically distributed around positive samples, thereby satisfying the condition necessary for achieving optimal embedding. Specifi- cally, we present the following theorems to illustrate that the negative samples produced by EMU exhibit isotropic distribution around the positive samples.
Theorem 3.2. Suppose that A and B are veclors in RN and BEMU = λEMU + B. Assuming a sufficienlly small standard deviation in the vector component of B with non-zero mean value and sufficiently large N, the angle formed between A and BEMU adheres to a Gaussian distribution whose center the angle between A and B.
The proof for this theorem can be found in Appendix C Utilizing the above theorem, we can deduce: Theorem 3.3. EMU generates negative samples isotropically around the target positive sample.
Proof. According the definition the deviation vector A can be written
žEMU z = 10--) @ Az,
(7)
where A =². Subsequently, we consider the angular distribution of (Az²) Ji=t..... Without loss of generality, we take the angle distribution of Az in terms of Aag. The cosine function between Az, and Azd can be expressed
Azd
Az,
{cos 07²} =
Az
(1
AEMUa) O Az,
A
Az
In this context, the operator (1 - \BMU,) projects Az; onto a lower-dinennionall hypersurface, and Theorem 3.2 hence shows (1 - O induces the Gaussian distribution in terms of the angle between Azd and Aze in the angle-space. This results in isotropic distribution of the EMU samples in the coordinate space, which are isotropically dispersed around the target positive tail sample.
Before proving the final theorem, we provide the following lemma. In the rest of this subsection, we will consider 7EMU, 2 Azd as independent random variables.
5

---

Published in Transactions on Machine Learning Research (04/2025)
Lemma 3.4. In the contert of EMU, (z')v( can be expressed as:
PR,EMU (2.EMU(ZENUU))) ( = A f dx'it I daad (ōD(ZEMU 2 Fiso (1Az)) 1zti+, Az)pa(zz ((/)))))]])]
(9)
where dD is the Dirac delta function, fieo is an isotropic distribution with typical decaying scalar scale A and A is an oppropriate constant.
The proof for this lemma can be found in Appendix D To finalize, conclude the following claim:
Theorem 3.5. Assuming EMU considers the embedding vector of negative samples to be muted in the neighbor of the considering positive sample, the negative sample distribution by EMU results in near-optimal embedding.
Proof. According to Lemma 3.4 fiso is a sufficiently rapidly decreasing function when | > Az. In the following, we approximate Siso by the Heaviside function: H(A: |Az^l), which does not affect the following order-of-magnitude discussion. Concretely, the variation within Az < A can be taken into account by properly renormalize the coefficient denoted as A in the following. Then, Equation 9 reduces to:
Pr.EMU(ZEMUlV")) A ddde> H(A= -AA Azrlv/r)
A // d' / dd - AzZlv²r) A' pa Pa(ZEMmc/ + +((
(10)
where A' is constant. To obtain the final line, we performed the Taylor expansion in terms of Az^ and performed the integration in terms of A= Then, by substituting the above equation, Equation reduces to:
1 T pa(z)| [ kA''
1 1- 1-0((A E2)
1111)
Ell[@r - 2z)
(11)
As in Y20, this indicates that the order of magnitude of deviation is only negatively related to for the case of EMU.
Theorem 3.5 suggests that the distribution of negative samples generated by EMU closely aligns with Equation 5 as stated in Theorem 3.1 indicating that EMU produces near-optimal negative sample distribution. Note that Theorem 3.5) also shows that the ncar-optimal embedding can be achioved when negative samples are distributed according a rapidly decreasing rspt function, Siso, around the targel positive samples. EMU facilitates the easy generation of such negative samples. Note that we have not explicitly used the fact that the objective function depends SpistMult- The logic in the above proof and Y20 be applied to more generic form of the embedding, f(z", z", z²) where is scalar function that takes zh z", z inputs. This formulation encompasses models such as the DistMult and neural networks.
3.4 Overall Loss Terms
Inspired by knowledge distillation (Hinton et al. 2015), combine the EMU loss function with the usual loss function without FMU, enabling the model to learn from the vanilla negative samplings (i.e., sampled using the existing methods) as well. The overall loss function is expressed as:
C C(st {50,EMU, $1,EMU, ... } + aC(st, {so. $1, }:;
(12)
where is contrastive loss function, i is the onc-hot label, and y a generalizod label by such a label-smoothing. The numerical coefficient a is utilized for weight balancing between the losses.

---

Published in Transactions on Machine Learning Research (04/2025)
FB15k-237
YAGO3-10
WN18rr
0.5
0.35
0.4
0.4
MRR
0.30
MRR
MRR
0.3
0.2
0.25
0.2
0.20
0.0
0.1
DM
RE
TE
DM
RE
CE
DM
RE
TE
Models
Models
Models
san
$3n_EMM
UNi
Uni BMU
san
SON_EMU
uni
UnLENUU
$an_EMU
unt BHU
Figure 2:
MRR for the datasets: FB15k-237, YAGO3-10, and WNISRR. The blue, orange, green, and red colored bars mean the result of using the following negative sampling methods: "SAN', "SAN with EMU", 'uniformm, ;
and "uniform with EMU", respectively.
4 Emperical Validation
In this section, we perform an experimental evaluation of EMU for the link prediction problem validate the effectiveness of EMU as shown in sceciin 3. To ensure thorongh evaluation, we chose commonly used
KG embedding models (ComplEX (Trouillon al. 2016 Lacroix al. 2018). DistMult (Yang et al. 2015
Salchi et al. 2018). TransE (Bordes et al. 2013). RotatE (Sun et al. 2019]), HAKE (Zhang et al. 2020
and NeF (Zhu et al. 2021) to test with EMU Although we used the Must model in section 3 the above models enable to assess the effectiveness of EMU to more generic form of operation for triplets than the inner-product type one. Furthermore, we evaluate them on three widely used knowledge graphs, namely FB15k-253 -37 (Toutanova Chen 2015), WNISRR (Dettmers al. 2018), and YAGO3-10 (Mahdisoltani et al. 2013 whose detailed statistics are provided in Appendix F
4.1
Experimental Setup
In order to enable a fair comparison between the different models and to ensure that all methods are evaluated under the same conditions, we implemented all the methods 3 Among all existing basclines, we consider vanilla uniform negative sampling (Bordes et al. 2013). SAN (Ahrabian et al.] (020)., and NScaching (Zhang et al. 2019) as the most relevant. to compare our work against. A detailed experimental setup is provided in Appendix G For the loss function in Equation 12 we consider the cross-entropy loss function with slightly modified label-smoothing as y, which is described in Appendix E
4.2
Results
This section provides a summary and discussion of the obtained results.
Figure 2 illussraaes the quantitative results in Table 8] displaying three plots for the MRR results obtained for the FB15k-237, YAGO3-10 10, and WN18rr datasets. The results of HAKE model are provided in Table 9 and the results with NScaching are provided in Table 10 Each plot includes four groups of column bars, representing the results for ComplEX (Trouillon et al. 2016: Lacroix et al. 2018) (CE), DistMult (Yang et al. 2015 Dettmers et al. 2018 Salehi et al. 2018) (DM), RotatE (Sun et al.) 2019 (RE), TransE (Bordes al. 2013) (TE). The columns are distinguished by colors that correspond to the results obtained from running the SAN (in blue), SAN EMU (i.e.: SAN negative sampling method with EMU, in orange), uniform sampling (green), and uni EMU (i.c.: simple uniform negative sampling with EMU, in red). The findings demonstrate that, in most cases, employing EMU significantly improves the scores across all embedding models. An exception is observed with the WN18rr dataset, which is further analyzed and theoretically examined in subsection 4.4
3The code to replicate our experiments be found: https://anonynnn www.e.ocoieeceee...ooo Science/r/EHU KC- GE58
*Note that the assumed loss function in sesscction 3 that sigmord-type loss lunction Eqqatton related but different
from Equation 12 which also indicates the wider applicahiiity of EMU than assumed in Section 3)
the recent-popular loss functions (Ruffinelli al. 2020 The following experimental results

---

Published in Transactions on Machine Learning Research (04/2025)
Dalaset
Model
Case
Parameter: (d. n]
MRR
HITS@10
FB15k-237
DistMult
w/t EMU
(200, 64)
0.314
0.500
w/t FMU
(1000, 64)
0.327
0.519
FMU
(200, 64)
0.329
0.514
HAKE
w/t EMU
(200, 256)
0.175
0.315
w/t EMU
(1000, 256)
0.308
0.493
EMU
(200, 256)
0.311
0.501
YAGO3-10 DistMult
w/t EMU
(100, 256)
0.345
0.538
w/t EMU
(1000, 256)
0.393
0.595
EMU
(100, 256)
0.403
0.601
HAKE
w/t EMU
(500, 256)
0.452
0.651
w/L EMU
(1000, 256)
0.482
0.665
EMU
(500, 256)
0.499
0.687
Table 1: Embedding dimension efficacy study results on FB15K-237 and YAGO3-10. (d, n) denote the embedding dimension and the negative sample number. "w/t EMU" denotes the model trained without EMU but with uniform sampling. The best performance is written in bold font and the second best performance is written with underline. The reported values are obtained by our own training of HAKE model with utilizing the official repository Zhang et al. 2020
4.3 Embedding Dimension Efficacy Study
In this subsection, we study the embedding dimension efficacy of EMU using FB15K-237 and YAGO3-10. For this study, we consider DistMult and HAKE models as classical and recent representative KGE models. To show EMU efficacy, we performed the training of the models with large embedding dimension without. EMU in comparison with the one with small embedding dimension with EMU. The result provided in Table I] which shows that EMU enables to achieve the model performance comparable to five times larger embedding dimension case. In particular, HAKE results show significant performance gain, indicating that EMU enables the recent sophisticate model with smaller size but keeping the prediction performance.
4.4 Mutation effect
In this subsection, analyze and discuss the mutation effect in terms of embedding similarity. We use DistMult as reference model and train it on FB15k-237 and WN18RR datasets. We visualize the embedding vector of the negative tail obtained with EMU to compare it with other negative sampling strategies, iee. uniform random sampling and SAN negative sampling.
Figure 3 shows the cosine similarity of negative samples provided by the three strategies. The similarity distributions of negative samples produced by the uniform and SAN methods are quite low, resulting in 'easy' negative samples. In contrast, the negative samples generated by EMU cxhibits much larger similarity, indicating that EMU generates harder negative samples than the other methods shown in Proposition B.I
Fig Figure depicts the distribution of true-tails and negative tails for two different datasets, namely FB15k-237 and WN18rr, by plotting the first and second PCA components. The left panel of each figure shows the distribution when negative tails are uniformly sampled, while the right panel depicts the distribution using EMU negative-tails. In the Figure 4 the distribution around a true tail is anisotropic for uniform-negative sampling, while EMU negative-tails show a rapidly decreasing isotropic distribution as shown in Theorem 3.3 which validates our assumption of Jino by the Heaviside function. Moreover, the distributions for FB15k-237 are quite varied in comparison to those of WN18RR, This could be explanation for the higher performance gain when using EMU for FB15k-237 (sce Table 8
TThe isotropic distribution of embedded node vectors observed in the WN18RR datasct consistent with findings from
previous studies (Sadeghi al. 2021;. highlighting the influence of node degree and centrality measures on node embeddings
Sardina et. al. 2024 el. 2022nl Shomer al. 2023 Furthermore, we note that the performance improvements of
8

---

Published in Transactions on Machine Learning Research (04/2025)
soaee samibntyy poodlea-nagehiee
17.3
SAN
16.
12.5
16.5
7.
5.
24
0.2
0.00
Figure 3: Cosine similarity between positive and negalive sample pair for DistMult trained on FB15k-237 dataset. The used negative samples are: uniform, EMU, and SAN. The larger, the more similar.
2.0
uniform
2.0
EMU
1.0
uniform
1.0
EMU
tall
1.0
genvecto
1.0
2nd eigenvecion
0.5
2nd eigenvestor
0.5
0.5
0.8
0.0
0.0
0.0
0.0
-0.5
-0.5
-0.5
-0.5
-1.5
rsellst magetivn
-1.6
-2.0
-1.0
-1.0
0
0 1st eiganvector
1st eigenvector
1st eigenvector
1st algenvector
Figure Results of the analysis of EMU of DistMult model trained on FB15k-237 (Left) and WN18rr (Right) dataset. Left: The distribution of real-tail and uniformly-sampled negative-tail in terms of the 1st and 2nd PCA components. Right: The distribution of real-tail and EMU negative-tail in terms of the 1st and 2nd PCA components.
FB15K-237
WNISRR
YAGO3-10
Model
Method
MRR.
HITS@10
MRR
HITS@10
MRR.
HITS@10
ComplEX
uni EMU
0.344
0.532
0.473
0.547
0.437
0.638
[Lacroxx al.
2018
uni MIXUP
0.324
0.517
0.470
0.547
0.418
0.605
DistMult
uni EMU
0.332
0.513
0.446
0.523
0.403
0.601
Yang et al.
2015 uni MIXUP
0.319
0.507
0.441
0.517
0.402
0.597
RotatE
uni EMU
0.329
0.514
0.453
0.525
0.365
0.555
Sum et al.
2019 uni MIXUP
0.281
0.454
0.278
0.428
0.174
0.318
TransE
uni EMU
0.323
0.503
0.216
0.493
0.255
0.436
Bordes et al. 2013
uni
MIXUP 0.269
0.421
0.050
0.139
0.063
0.102
Table 2: MRR and Hi of the results on FB15K-237, WNISRR, and YAGO3-10 datasets. 'uni EMU means the uniform negative sampling with EMU and "uni _MXUP" means the uniform negative sampling with MIXUP. The shown results are the average of three trials of the randomly determined initial weights.
4.5 Comparison to Mixup
There is well-known approach called MIXUP, which shares similar philosophy with the EMU but is based on a different theoretical background (see also seccion 5). To compare their performance, we replaced
Must and ComplEx remain significant, with gains ranging from 10%. This improvement may be attributed the ability MultMult- models better capture low-degree entities compared Trans Rossi Matinata 2020).

---

Published in Transactions on Machine Learning Research (04/2025)
the Embedding Mutation step with MIXUP and present the results in Table 2 g The findings consistently demonstrate that EMU outperforms MIXUP. We hypothesize that the linear nature of MixUP-generated examples limits the magnitude of gradients while preserving their direction, thereby restricting its effectiveness. In contrast, EMU overcomes this limitation by generating updates that can explore multiple directions, thereby enhancing model training
4.6 Application to NBFNet
In this section, we apply EMU to Neural Bellman-Ford Networks (NBFNet) (Zuu et al. 2021 one of the state-of-the-art (SOTA) models for knowledge graph tasks. The results on the FB15K-28 237 datasct are presented in Table 3 demonstrating that EMU remains effective even when applied to the latest models, achieving performance competitive with the current SOTA methods
FB15K-237 HITS@1
Model
MRR
HITS@3
HITS@10
NBFNet (reported)
0.415
0.321
0.454
0.599
NBFNet (our experiments)
0.414 + 0.003
0.321 + 0.003
0.453 + 0.003
0.596 1 0.002
NeFNet w.t. EMU
0.419 + 0.002
0.326 + 0.002
0.460 + 0.003
0.601 = 0.002
Table 3: MRR, Hit@1, @it@3, and @1 of the results of NBFNet on FB15K-237 dataset. The results are the average with the standard deviation of three trials of the randomly determined initial weights.
5
Related Work
KGE Models KGE models such as TransB et al. 2013 DistMult (Yang et al., 2015 Dettmers
ctt al.
2018
Salchi et al.) 2018), ConvE (Dettmers et al. 2018). ComplEX (Trouillon et al. 2016 Lacroix
el al. Each model implements a scoring function mapping a given triple to a real-valued number. These models
2018
RotatE (Sun et al. 2019 are commonly used when solving the knowledge base completion task.
also differ in the embedding spaces used to learn the latent embedding, for instance RotatE (Sun et al. 2019 utilizes the complex vector space. The new KGE model investigation is still actively conducted Zhang et al.
[2020]; AAboou et al. 2020); Zhu et al. (2021]; Tran & Takasu
(2022) Zhang et al. (2023 Zhu et. al. 202
Zhou et al. (2024) and more comprehensive review can be found in Ge et al. 20024
Negative sampling While training KGE model for the link prediction task, it is essential to sample high-quality negative data points adequately from the graph. Poor quality negative samples can hinder the performance of KGE models by failing to guide the model during training. With this in mind, many approaches were proposed for generating cetter-quality negative samples, ie., hard negatives. The earliest sampling method is Uniform Sampling (Bordes et al. 2013).. Another commonly used method relics on Bernoulli Sampling where the replacement of the heads or tails of the triples follows the Bernoulli distribution. (Wang et al. 2014). Newer methods that are based on Generative Adversarial Networks (GAN) are also used such as KBGAN (Cai & Wang 2018) and IGAN (Vignaud 2021 where the generator is adversarially trained for the purpose of providing better quality negative samples where KGE model is used as the discriminator. Building on this NScasching (Zhang et al. 2019) proposed a distilled version of GAN-based methods by creating custom clusters of candidates entities used for the negative samples. Structure Aware Negative Sampling (SANS) (Ahrabian et al.] 2020) leverages the graph structure the KG by selecting negative samples from a node's 's k-hop neighborhood. In addition, the subject continues to be actively studied
(Zhang et al. 2021 Islam et al.) 2022 Xu et al. 2022 Lin et al.) 2023 Yao et al. 2023 Chen et al. 2023
Qiao et al. 2023 Unlike the prior work mentioned above, EMU generates hard negative samples, distinct
from traditional approaches aimed at identifying more difficult negative samples. Furthermore, an additional
Note that this procedure already different from the original implementation of Mixur which corrupts the original data, not that of embedding dimension.
Whill the performance improvement relatively smaller compared other models, this may attributed the additional structure of NBFNet, specifically the Bellman-Fan iteration, which differs from the architectures used in other experiments.
10

---

Published in Transactions on Machine Learning Research (04/2025)
benefit of EMU is its compatibility with any of the above negative sampling methods, allowing for scamless integration.
6 Discussion and Conclusion
In the present study, we theoretically identified condition of the nice negative sample distribution leading to near-optimal embedding of KGE and identified sufficient condition for near optimal embedding. Based on the condition, we proposed EMU which aims lo generate the negalive samples following the condition easily and efficiently. Our comprehensive experimental findings also demonstrate that EMU consistently outperforms all the bascline negative sampling methods, including uniform sampling, SAN, and NSCaching almost all the KGE models and datasets. We also observed that EMU's efficacy was largely invariant across embedding models and datasets. Moreover, the experiments shows that EMU enables to achieve comparable performance to models with embedding dimensions that are five times larger. Our analysis showed that EM U generates negative samples that are closer to true samples in terms of cosine-similarity, and that the generated samples exhibit a more isotropic distribution around the true sample in the embedding space compared to other methods, which is a part of the condition for the near optimal embedding for KGE. Although EMU involves tuning few hyper-parameters, we observed that its performance is not heavily reliant on them (refer to Appendix KJ. While EMU was developed for KGE tasks, its simple structure enables its application to other tasks, such graph node classification and representation learning. Exploring these applications remains promising direction for future work.
Acknowledgements
The authors would like to thank their colleagues NEC Laboratories Europe, in particular Dr. Kiril Gashteovski, Dr. Carolin Lawrence, and Professor Mathias Niepert, for their valuable feedback and encouraging support throughout this work.
11

---

Published in Transactions on Machine Learning Research (04/2025)
7 Limitations
EMU scope is restricted to KG missing link prediction model trained using the cross-entropy loss function with negative samples. It cannot be applied to neither 1-VS-ALL method nor the other loss functions for the moment.
Potential Broader Impact and Ethical Aspects
This paper presents work whose goal is to advance the field Machine Learning, in particular, knowledge- graph link prediction. There are many potential socictal consequences of our work in the far future due the generic nature of pure science, none which we feel must be specifically highlighted here. While we do not foresee substantial ethical concern in proposed strategies, there may be side effect resulting from the feature mutation. It is thus important to monitor and evaluate potential bias that may arise during the model training process. Note that we utilized only publicly available KG datasets, and thus, there is no concerns regarding compliance with the General Data Protection Regulation (GDPR) law
References
Ralph Abboud, Ismail Ilkan Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. Boxe: A box embedding model for knowledge base completion. ArXiv, abs/2007.06220 2020. URL https://api. http://wwwooooooooo....ooooo/aaa semanticcchollr
org/Corpus ID: 220496538
Naser Ahmadi and Paolo Papotti. Wikidata logical rules and where to find them. In Companion Proceedings of the Web Conference 2021, pp. 580-581, 2021.
Kian Ahrabian, Aarash Feizi, Yasmin Salchi, William L. Hamilton, and Avishek Jocy Bosc. Structure aware negative sampling in knowledge graphs. In EMNLP, 2020.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next- generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: A collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD '08, pp. 1247 1250, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605581026. URL 1376616. 1376746)
Antoine Bordes, Nicolas Usunier, Alberto Gareía-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NewrIPS, 2013.
Liwei Cai and William Yang Wang. KBGAN: Adversarial learning for knowledge graph embeddings. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pp. 1470-1480, New Orleans, Louisiana, June 2018. Association for Computalional Linguistics. doi: 10.18633/v1/N18-11
URL
Olivier Chapelle, Jason Weston, Léon Bottou, and Vladimir Vapnik. Vicinal risk minimization. Advances in neural information processing systems, 13, 2000.
Feihu Che, Guohua Yang, Pengpeng Shao, Dawei Zhang, and Jianhua Tao. Mixkg: Mixing for harder negative samples in knowledge graph. arXiv preprint arXi::200..000 09600, 2022.
Xiangnan Chen, Wen Zhang, Zhen Yao, Mingyang Chen, and Siliang Tang. Negative sampling with adaptive denoising mixup for knowledge graph embedding. In International Semantic Web Conference, pp. 253 270. Springer, 2023.
hhttps://gápreer
12

---

Published in Transactions on Machine Learning Research (04/2025)
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Scbastian Riedel. Convolutional 2d knowledge
graph embeddingg. In AAAT, 2018.
Qingkai Fang, Rong Ye, Lei Li, Yang Feng, and Mingxuan Wang. STEMM: Self-learning with speech-text manifold mixup for speech translation. In ACI, 2022.
Kiril Gashteovski, Rainer Gemulla, Bhushan Kotnis, Sven Hertling, and Christian Meilicke. On aligning OpenIE extractions with knowledge bases: A case study. In NLP (workshop); 2020.
Xiou Ge, Yun Cheng Wang, Bin Wang, C-C Jay Kuo, et al. Knowledge graph embedding: An overview. APSIPA Transactions on Signal and Information Processing, 13(1), 2024.
Q. Guo, F. Zhuang, C. Qin, H. Zhu, X. Xie, H. Xiong, and Q He. A survey on knowledge graph-based recommender systems. IEEE Transactions on Knowledge and Data Engineering, 2022.
Haitao He, Haoran Niu, Jianzhou Feng, Junlan Nie, Yangsen Zhang, and Jiadong Ren. An embedding model for knowledge graph completion based on graph sub-hop convolutional network. Big Data Research, 30: 100351, 2022a.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In CVPR, 2022b.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprinl arXiv:1503.0955 2015.
Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. Knowledge graph embedding based question answering. 2019.
Md Kamrul Islam, Sabeur Aridhi, and Malika Smail-Tabbone Negative sampling and rule mining for explainable link prediction in knowledge graphs. Knowledge-Base Based Systems, 250:109083 2022. ISSN 0950-7051. doi:
ht0.::/)....oooss22220000000 URL http://www.cciinccirrrcccc com/
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. NeurIPS, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar e-prints, pp.
arXiv-14Hh 2014.
Timothée Lacroix, Nicolas Usunier, and Guillaune Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 3563-2872. PMTR, 2018.
Zhenzhou Lin, Zishuo Zhao, Jingyou Xie, and Ying Shen. Hierarchical type enhanced negative sampling for knowledge graph embedding. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '23, pp. 2047 2051, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394086. doi: 01445/5533618.3555 https://doi.co org 10. 1e.1111533336118 0...99991.399996 3591996
URL
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hicrarchical vision transformer using shifted windows. In ICCV, 2021.
Robert Logan, Nelson F. Liu, Matthew E. Peters, Matt Gardner, and Sameer Singh. Barack's wife hillary: Using knowledge graphs for fact-aware language modeling. In Proceedings of the 57th Annual Meeting of the Association for Compulational Linguistics, pp. 59711, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 18653866/ PP19-1598
URL
Farzanch Mahdisoltani, Joanna Biega, and Fabian M. Suchanck. YAGO3: A Knowledge Basc from Multilingual Wikipedias. In CIDR, Asilomar, United States, January 2013. URL https://hal-int: -wtps//owwwetttthha--0000667777
13

---

Published in Transactions on Machine Learning Research (04/2025)
Linghui Meng, Jin Xu, Xu Tan, Jindong Wang, Tao Qin, and Bo Xu. Mixspeech: Data augmentation for low-resource automatic speech recognition. In ICASSP, 2021.
George A. Miller. Wordnet: A lexical database for english. Commun. ACM, 38(11):39 41, November 1995. ISSN 0001-0782. URL http://teee//bo..rr//00...11////
219748
Rafael Müller, Simon Kornblith, and Geoffrey Hinton. When does label smoothing help? Advonces in neural information processing systems, 32, 2019.
Zile Qiao, Wei Ye, Dingyao Yu, Tong Mo, Weiping Li, and Shikun Zhang. Improving knowledge graph completion with generative hard negative mining. In Findings of the Association for Computational Linguisties: ACL 2023, pp. 5866 5878, 2023.
Priya Radhakrishnan, Partha Talukdar, and Vasudeva Varma, ELDEN: Improved entity linking using densified knowledge graphs. In Proceedings of the 2018 Conference of the North American Chapler of the Association for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pp. 1944-1853, New Orleans, Louisiana, June 2018. Association for Computational Linguisties. doi: 10.18653/v1/N11 URL https://aclanthhllogg.... ootp:/o/ooooooo////-111111100111
Andrea Rossi and Antonio Matinata. Knowledge graph embeddings: Are relation-lcarning modols learning
relations? In EDBT/ICDT Workshops, volune 2578, 2020.
Aniket Roy, Anshul Shah, Ketul Shah, Prithviraj Dhar, Anoop Cherian, and Rama Chellappa. Felmi Few shot learning with hard mixup. In NewrIPS, 2022.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach old dog tricks! on training knowledge graph embeddings. In International Conference on Learning Represenlations, 2020.
Afshin Sadeghi, Diego Collarana, Damien Graux, and Jens Lehmann. Embedding knowledge graphs attentive positional and centrality qualities. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 548 564. Springer, 2021.
Farnood Salchi, Robert Bamler, and Stephan Mandt. Probabilistic knowledge graph emboddings. 2018.
Jeffrey Sardina, John D Kelleher, and Declan O'Sullivan. A survey on knowledge graph structure and knowledge graph embeddings. arXiv preprint 2rXi:24422.10092 2024.
Apoorv Saxena, Adrian Kochsiek, and Rainer Gemulla. sestencc-to-sequenne knowledge graph completion and question answering. In Proceedings of the 60th Anmual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 2814 2828, Dublin, Ireland, May 2022. Association for Computational long.201. 201. URL https: battts://aclanthottt
Linguistics. doi: 10.18653/vll
.rg.e...rg//// wwtp://0./22.11111..... 201
Harry Shomer, Yao Ma, Juanhui Li, Bo Wu, Charu C Aggarwal, and Jiliang Tang. Distance-based propagation for efficient knowledge graph reasoning. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: A core of semantic knowledge. In Proceedings of the 16th International Conference on World Wide Web, WWW '07, pp. 697-706, New York, NY, USA, 2007. Association for Computing Machinery, ISBN 9781595936547, doi: 10.1145/12455721222200 URL https::/doi.
1111 11451/1421111222. 12427722
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR, 2016.
Ily O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohna Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, al. Mlp-mixer: An all-mlp architecture for vision. NewrIPS, 2021.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Alexandre Allauzen, Edward Grefenstette, Karl Moritz Hermann, Hugo Larochelle, and Scott Wen-tau Yih (eds.), CVSC, 2015.
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 14499-5509 Lisbon, Portugal, September 2015. Association for Computational Linguistics. URL
Hung Nghiep Tran and Atsuhiro Takasu. Meim: Multi-partition embedding interaction beyond block term format for efficient and expressive link prediction. In International Joint Conference on Artificial Intelligence, 2022. URL
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, 2016.
Dr. Lue Vignaud. Igan: Inferent and generative adversarial networks, 2021. URL https://axciv.org/ $109.13360
Wenhai Wang, Enze Xic, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. In ICCV, 2021.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In Proceedings of the AAAI conference on artificial intelligence, volume 28, 2014.
Dirk Weissenborn, Pasquale Minervini, Isabelle Augenstein, Johannes Welbl, Tim Rocktäschel, Matko Bošnjak, Jeff Mitchell, Thomas Demeester, Tim Dettmers, Pontus Stenetorp, and Sebastian Riedel. Jack the reader a machine reading framework. In ACL, 2018.
Wikipedia contributors. Plagiarism Wikipedia, the free encyclopedia, 2004. URL p hrrgw/indee hotg/w/indxx...
[Online; accessed 22-July-2004).
Derong Xu, Tong Xu, Shiwei Wu, Jingbo Zhou, and Enhong Chen. Relation-Enhaneee Negative Sampling for Multimodal Knowledge Graph Completion, pp. 3857-3866. Association for Computing Machinery, New York, NY, USA, 2022. ISBN 9781450392037. URL htttp:///dois 1ttp///00.115//3111111111 3548388
Bishan Yang and Tom Mitchell. Leveraging knowledge bases in LSTMs for improving machine reading. In ACL, 2017.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In Yoshua Bengio and Yann LeCun (eds.), ICLR, 2015.
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery E/ data mining, pp. 1666-1676, 2020.
Naimeng Yao, Qing Liu, Yi Yang, Weihua Li, and Quan Bai. Entity-relation distribution-awwn negative sampling for knowledge graph embedding. In International Semantic Web Conference, pp. 234-252. Springer, 2023.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE/CVE international conference on compuler vision, pp. 6023 6032, 2019.
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR, 2018.
Yongqi Zhang, Quanming Yao, Yingxia Shao, and Lei Chen. Nscaching: Simple and efficient negative sampling for knowledge graph embedding. In ICDE, 2019.
15

---

Published in Transactions on Machine Learning Research (04/2025)
Yongqi Zhang, Quanming Yao, and Lei Chen. Simple and automated negative sampling for knowledge graph embedding. The VLDB Journal, 30(2):259 285, 2021.
Yongqi Zhang, Zhanke Zhou, Quanming Yao, and Yong Li. Kgtuner: Efficient ayper-parameter search for knowledge graph learning. arXiv preprint arXin:220..0m 02460, 2022.
Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, and Bo Han. Adaprop: Learning adaptive propagation for graph neural network based knowledge graph reasoning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3446-3457, 2023.
Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. Learning hieracchy-waaee knowledge graph embeddings for link prediction. In Thirty-Fourth AAAI Conference on Artificial Intelligence, pp. 5065-3072 AAAI Press, 2020.
Zhanke Zhou, Yongqi Zhang, Jiangchao Yao, Quanming Yao, and Bo Han. Less is more: One-shot subgraph reasoning on large-scale knowledge graphs. arXiv preprint arXiv:2403. 10231, 2024.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Neural Information Processing Systems, 2021. URL hattpa///apt semanti wrtp:o/aaarrrr/roooraaaa-220000
Zhaocheng Zhu, Xinyu Yuan, Michael Galkin, Louis-Pascal Xhonneux, Ming Zhang, Maxime Gazeau, and Jian Tang. A net: scalable path-based reasoning approach for knowledge graphs. Advonces in Neural Information Processing Systems, 36, 2024.
16

---

Published in Transactions on Machine Learning Research (04/2025)
A Additional Related Work
Model Regularization Methods for Classification Tasks To obtain good representation of the embedding vector of a machine learning model, it is common to consider regularization methods. In particular, there have been several regularization techniques for better generalization power in the case of the cross entropy loss function. MIXUP (Zhang et al. 2018) is one of the most popular and powerful regularization methods, originally developed for image and speech processing. This method generates new training samples by convexly mixing two different. training data during the training, resulting a network with a better gencralization bocause of Vicinal Risk Minimization (Chapolle al. 2000). Consoquently MIXUP has gained popularity in computer vision (Liu et al. 2021; He et al. 2022b; Wang al. 2021) and voice recognition [Meng et al.
2021 Fang et al. 2022), among other fields (Tolstikhin et al.) 2021; Kalantidis et al. 2020 Roy ct al. 2022 Che ct al., 2022). CUTMIX Yun et al. (0099) is variant of MIXUP that combine two input
images as MIXUP but by cutting and pasting patches among images. Our Feature Mutation shares a similar philosophy but the crucial difference is that feature mutation combines positive and negative tails in "feature' space that has not yet been tried in any existing work as far as we know.
Label Smoothing (Szegedy et al., 2016 Müller al., 2019) is also known a very effective regularization method when combined with cross entropy loss. Label Smoothing prevents overconfident predictions from the model by artificially reducing the true labels to be less than unity.
Further Property of EMU
The following proposition describes that EMU generates more difficult negative samples than the original ones.
Proposition B.1. The generated negative samples generated by EMU are always closer to the positive samples than the original negative samples.
Proof. The Euclidean distance between a positive sample zz (2 Ji=t....d and vanilla negative sample z [2 his.....d can be written as:
d
dpN =
z )2
(13)
On the other hand, the distance between positive sample and a negative sample generated using EMU is
dEMU
(2 z,
22
(2t U1zt + (1 A,)2,
1=1
d
(z, 2, 22 S drN.
(14)
where in the last line, we assume the first components in AEMU is unity and the others are zero: XEMU = (1, 1, 1.0,... , ,0), without loss of generality.
The above equations show that EMU enables to generate hard negative samples than the original ones.
C Proof of Theorem 3.2
In the following, we provide the proof of Theorem 3.2
17

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. For simplicity, assume the first axis of the coordinate is aligned with vector A: A d1eb and we also represent B as B = (i:).=,....,' = {b + Abi)i=1,..... where b is the mean-value of the component of the vector B. Then, the angle between A and B can be written as:
A B
cos 0u =
A
B
1 (b + Ab,)
b1
N
Ab;
27
1/2
1
(15)
b/N
N
b
Likewise, the angle belween and can be writlen as:
A BEMU
b1b
COS
A BEMUl
X²(6 + Ab;)²
Dimi
b1b1
1
N
2A6
Abi
I]
1/2
+
+
(16)
Ply
i=
In the limit of Ab < b, noting that X₂ = Ass
N
OENU:
N
1
A1 V
+ +0(e)
cos Oo
nr
Th i=1
N
C
>1 nr
1
+ +02))
(17)
nr.
Here, = Ab:/b and <= >i Ase and we derived the first equation by the Taylor expansion to the first-order in According to the central limit theorem, < follows the Gaussian distribution in the case of sufficiently large N, and hence cos ÊEmU adheres to Gaussian distribution centered around / NN/n, cos fo as long as \ ل
D Proof of Lemma 3.4
Proof. First, we consider the case of the real-world data case with only limited data. According to Theorem 3.3 and |Equaion 6) the negative sample distribution can be written linear summation of an isotropic distribution as:
N Pr.EMU C.EMU(&EMU(eR (r)) Σ (Az 2²it),
+ ~ (p(zz+t(
(18)
where Pa, Pa are the expression of Pm and pa in the data space and (xly)) is isotropic function around y. Note that in the above equation, it is assumed the following relation is always satisfied: `emu z + Az* If moving back to the idealized data space, Equation 18 reduces to:
Po,EMU (ZEMUle"))
A dz fio fio (Az) 2 (a (x))))r
(19)
where is constant. Then, we obtain the Equation 3.4 explicitly demanding the relation: gEMU
f Az by considering the Dirac delta function. Note that the Equation 3.4 also assume that fis is a rapidly decaying function with typical scale Až which the scale implicitly given in Proposition B.1
18

---

Published in Transactions on Machine Learning Research (04/2025)
E
Unbounded Label Smoothing for Cross-Entrops Loss Function
Label smoothing is a well-known technique used to regularize classifier models (Szegedy et al. 2016). It. is originally proposed to address the overconfidence issue that certain classifiers such neural networks may exhibit during training. It works by smoothing the class label as follows:
YLS = y(1 BLS) + B
(20)
where ý == (1o. Vi...., .K) } is the one-hot label encoding, PLS is a label smoothing parameter that controls the model confidence, and K is the number of classes. Note that the resultant smoothed label maintains the total sum equal to unity. However, when applied to problems with a high number of classes, label smoothing leads to small values for the negative class label (or elements for the contrastive learning case), which still induces an overly strong penalty on the EMU negative samples whose vector component include the true positive sample vector that should not be penalized. To address this issue, we propose new approach called Unbounded Label Smoothing (Unbounded-LS), which is defined follows:
{1 if (+ 8
JULS,
otherwisc,
(21)
where / is the softening parameter over the negative samples. The above modification of the negative sample labels does not affect the probabilistic interpretation of the model output, it does not change the model output itself. Our unbounded LS discourages the model from penalizing the negative samples excessively.
F
Datasets
Dataset
#entities
#relations
#triples
FB15K-237
14,541
237
310,079
YAGO3-10
123,188
37
1,179,040
WN18-RR
40,943
93,003
Table 4: Knowledge Graph dataset statistics. training, validation and testing refer to the number of triples under each split.
FB15k-237 Touuanova et al. 2015 commonly used benchmark for Knowledge Graph link prediction tasks and a subset. of Freebase Knowledge Base (Bollacker et al. (2088). FB15k-237 was created as a replacement for FB15k, previous benchmark that was widely adapted until the dataset's quality came into question in subsequent work (Toutanova et al. 2015) due to excess of inverse relations.
YAGO3-10 Maahdisoltani et al. 2013) is subset of YAGO (Yet. Another Great Ontology (Suchanek et al. 2007 a large semantic knowledge base that augments WORDNET and which was derived from WIKIPEDIA Wikkiedia contributors 2004), WORDNET (Miller) 1995). WIKIDATA (Ahmadi & Papotti 2021). and other sources. Because of its origins, YAGO entities are linked to WIKIDATA and WORDNET ET entity types. The dataset contains information about individuals, such as citizenship, gender, profession, as well other entities such organizations and cities. The subset. YAGO3-10 contains triples with entities that have more than 10 relations.
WN18RR (Dettmers et al. 2018 is link prediction datasct created from WN18 [Bordes et al. 2013) which is a subset of WORDNET, popular large lexical database of English nouns, verbs, adjectives and adverbs. WORDNET contains information about relations between words, such as hyponyms, hypernyms and synonyms (Miller 1995). However, similarly the issues that occurred FB15K, many test triples WN18 are obtained by inverting triples from the training set. Therefore, WN18RR dataset was created in the same work FB15k-237, in order to make more challenging benchmark for link prediction.
19

---

Published in Transactions on Machine Learning Research (04/2025)
G Experiment Setup
Training Scttings Here we describe the general settings we used train all the models. The optimization was performed using Adam (Kingma & Ba 2014) for 10 iterations" with 256 negative sample The pperrpaaameeter tuning performed with Optuna (Akiba et al. 2019]. During the training, we monitored the loss over the validation set and selected the best model based on its performance the validation set. For models trained with SAN negative samples, we utilized the default training setup from (Ahrabian et al. 2020
Evaluation Settings To ensure that all the methods were evaluated under the same conditions, we utilized standard metrics to report results, specifically the Mcan Reciprocal Rank (MRR) and Hits at K (H@K). If multiple true tails exist for the same (head, relation)-pair, we filtered out the other true triplets at test time. To minimize model uncertainty resulting from random seeds or multi-chreading, we performed three trials for each experiment and reported the mean and standard deviation of the evaluation scores.
Basclines Among all cxisting basclines, we consider vanilla uniform negative sampling (Bordes ct al. 2013 and SAN (Ahrabian et al. 2020) as the most relevant to compare our work against. Additionally, we incl uded
NSCaching (Zang et al., 2019) as another baseline method, with its results provided in [Appendix hyper-parameters for the basclines and EMU are tuned by utilizing Optuna (Akiba et al. 2019).
The
Implementation Settings We modified the code originally developed by Ahrabian et al. (020)) to perform MIXUP and EMU with SAN. As explained in section 3] the models are trained using cross-entropp losses, incorporating one true tail sample and multiple negative samples. The optimization was performed using Adam (Kingma & Ba 2014). The L3-norm loss function is used on the embedding vectors for the models with the vanilla uniform negalive sampling and SAN. The mini-batch size is set to 1000. To compute the embedded triplets for all the KG models, we used an Embedding layer with a hidden dimension of: d 100. A more detailed syper-parameters are provided in Table 5) and [Table 6] We tuned our hyperparameters, including the learning rate and the coefficient for weight-decay for baseline scores, through 10000 iterations on the FB15K-237 validation dataset using Optuna (Akiba et al. 2019). We adopted the officially provided configuration for the HAKE model setup (Zhang et al. 2020). The hyperparameters for EMU are detailed in
Table
Computational Resources All the experiments other than HAKE were performed on one Nvidia GeForce GTX 1080 Ti GPU for each run. The experiments with HAKE were performed on one Nvidia GeForce RTX 3090 GPU for each run. The models were implemented by PyTorch 2.1.0 with CUDA1L.8. Because of the additional gradient flow through negative sample components due to mutation, the total GPU memory usage of FMU becomes around 1.5 to 2 times larger than vanilla case in the case of DistMult with (d, = (100, 256) where d, n denote embedding dimension and negative sample number. Concerning the training time, although one-step duration becomes around twice longer [2 we also found that EMU reaches its maximum performance much earlier than the case without EMU, leading to a shorter training time in the end. We emphasize that the additional computational resource allows us to achieve a comparable performance with the case using even 10 times larger embedding dimension, which requires at least 10 times larger computational resource (see also subsection 4.3). Note that EMU does not require additional computational resources during inference.
TThe total iteration number is the same as the one used in the SAN repository Ahrabian et al. 2020 to reproduce their best result.
the inffuence of the number of negative samples on the outcomes is analyzed, and it is demonstrated that EMU outperforms the uniform-sampling approach in almust all instances.
10 Appendix J
DiDuc to the inherent intricacy involved in asscssing the impact of different implemennaaiinss (specifically, SAN-based and NSCaching- based codcs) performances, we relocated he results obtained with NSCaching the Appendix.
12ehe length tends increase with model complexity and size. However, Table 1 indicates that the performance gain by
EMU also increases with the model complexity, as shown with HAKE
20

---

Published in Transactions on Machine Learning Research (04/2025)
Model
Method
Learning Rate
np/d
B
ComplEX
uni
0.1
n/a a
n/a
n/a
10-5
SAN
0.1
n/a
n/a
a
10-5
SAN EMU
0.1
0.34
0.92
0.12
0
uni EMU
0.1
0.34
0.92
0.12
0
DistMult
uni
0.1 n/a
n/a
n/a
10-5 5
SAN
0.1
n/a
n/a 0.94
n/a
10
SAN EMU
0.1
0.73
0.25
0
uni EMU
0.1
0.73
0.94
0.25
0
RotatE
uni
0.005
n/a a
n/a
n/a
10-3
SAN
0.005
n/a
n/a
n/a
10-3
SAN EMU
0.005
0.11
0.39
0.53
0
uni EMU
0.005
0.11
0.39
0.53
0
TransE
uni
0.005
n/a
n/a
n/a
10
SAN
0.005
n/a
n/a
n/a
10
SAN EMU
0.005
0.11
0.39
0.53
0
uni EMU
0.005
0.11
0.39
0.53
0
Table 5: Hyper-Paramede for FB15K-237 and WN18RR dataset. at B, 7 are the coefficient of original Loss, negative label value of Unbounded LS, and the coefficient L3-norm loss, respectively.
Model
Method
Learning Rate
a
Rp/d
7
ComplEX
uni
0.1
n/a
n/a.
n1aa
10 10-5
SAN
0.1
n/a
n/a.
n/a
10
SAN EMU
0.1
0.536
0.804
0.193
uni EMU
0.1
0.536
0.804
0.193
DistMult
uni SAN
0.1
n/a
n/a
n/a
10
0.1
n/a
n/a
n/a
10
SAN EMU
0.1
0.54
0.949
0.22
uni EMU
0.1
0.54
0.949
0.22
RotatE
uni
0.1
n/a
n/a
n/a
10-5
SAN
0.1
n/a
n/a.
n/a
10
SAN EMU
0.1
0.46
0.73
0.84
uni EMU
0.1
0.46
0.73
0.84
TransE
uni
0.1
n/a
D/a
n/a
5
10-5
SAN
0.1
n/a
n/a
n/a
5 10-5
SAN EMU
0.1
0.11
0.39
0.53
uni EMU
0.1
0.11
0.39
0.53
Table 6: Hyper-Parameters for YAGO3 dataset. a, 8 are the coefficient of original Loss, negative label value of Unbounded LS, and the coefficient of L3-norm loss, respectively.
Full Description of Main Result
In Table 8 we provide the full description of our result visualized Figure For the HAKE model, we provide the quantitative results in Table
21

---

Published in Transactions on Machine Learning Research (04/2025)
Dataset
Method
R2
Tib
Max-Step
Learning Rate
a
rpp/d
8
FB15K-237
uni
1000
256
1024
100000
5 x 10-5
n/a
n/a
n/a
uni EMU
5 10 5
0.1
0.128
0.964
WNISRR
500
1024
80000
10
n/a
n/a
n/a 0.964
uni EMU
5 10-6
0.1
0.128
YAGO3-10
uni uni EMU
500
256
1024
180000
2 10
n/a
n/a
n/a 0.964
2 10
0.1
0.128
Table 7: Hyper- Parem--arameeers of HAKE model. d, na. ny denote hidden dimension size, negative sample number, and mini batch size, respectively. a, 8 are the coefficient original Loss, negative label value of Unbounded LS, and the coefficient of L3-norm loss, respectively.
FB15K-237
WN1SRR
YAGO3-10 MRR
Model
Method
MRR
HITS$
MRR
HITS& IO
HITS 10
ComplEX
0.306+0.001
0,486 0.486-00000
U.461
U.461#00000
0.626440.002
0.39g=00000
0.605 0.605-0.000
[Lacrox
2018
SAN
0.275=0.000
0.437#00000
0.467=0.001
0.530#0.000
0.31820.002
0.496#00004
SAN EMU
0.298 0.298+0.00m 000001
0.474 +00001
0.466 0.466
0.543 0.543++00000
+00000
0.385 0.385
=0.002
0.563
uni EMU
0.344 #00001
0.532 +0.001
0.473 600063
0.547 #00000
0.437
0.638
0.638400.04
DistMult
0.200
0.476
0.428=000001
0.48g=20000z
0.345 2.345000000
0.538
Yang et al. 2015
SAN
00000
#0.000
0.425 000001
0.481 #00.002
0.251
00.002
0.428*00000
SAN EMU
0.282 20.001
0.446 L0.002
0.427
0.50640.000
0.293 2.00002
0.478
uni EMU
0.332 10.001
0.513
10.001
0.446-40.002
0.4416
40.000
0.523 400000
0.403
1.0.000..0000 004
0.601
0.000
RotatE Sun et al.
uni
0.305 000001
0.484=#0.001
0.484
4:0.001
0.458
0.0001
0.549
4:0.002
0.378
-0.003
0.569
1.569=00000
2019
SAN
0.25740.000
0.418 +..00m
0.456*00000
0.532 0.532=40.00 400.00
0,303
0.303=0.003
-00000000000
0.45g
SAN EMU
0.282 200000
0.455 20.001
00.000
0.516:20.002
0.363
0.535#0.002
uni EMU
0.329
0.514
0.453=0:000
0.525220.002
0.391 20.001
0.609#0.000
TransE
uni
0.314 20.001
0.479 20.000 0.479-20.002
0.227
0.506=0000z
0.233 20.000
0.389 0.09
Bordes et al.
2013
SAN
0. 1.299 1.299940000 20.001
0.460 000
0.237
0.518
0,222 -0 0012
0.375
SAN EMU
0.281#50
0..50tt0.00
0.202
0.493
0,221 20.2100.008 0.003
0
EMU
0.323
0.503
0.216#0.001
0.4993+0.001
0.255 00.022
0.438=#000
Table 8: MRR and Hit@10 of the results on FB11K--377, WN18RR, and YAGO3-10 datasets. "uni" means the uniform negative sampling, "SAN" means the structure aware negative sampling. The shown results are the average with the standard deviation of three trials of the randomly determined initial weights.
FB15K-237
WN1SRR
YAGO3-10 MRR
Model
Method
MRR
HITS@10 10
MRR
HITS@10
HITS@10
HAKE
uni
0.308 00.002
0.493=00000
0.436
0.487=0.008
0.452
0.651#0.004
Zhang et al. 2020
uni
EMU
0.316 0.316#0.00 #0.001
0.503
0.453 000001
0.526=0.002
0.499 0.499 000
0.687
Table 9: MRR and Hit@10 of the results of HAKE model trained on FB15K-237, WNISRR, and YAGO3-10 datasets. "uni" means the uniform negative sampling. The shown results the average with the standard deviation of three trials of the randomly determined initial weights
Results using NScaching
This section presents the results obtained with EMU and NSCaching (Zhang et al. 2019 13
We modified the official NSCaching repository to enable the use of the cross entropy loss function and EMU. We used the same hyperparameters as those provided in Section 3. mini-batch size 1000 and 256 negative samples.
We provided the results with NSCaching in the appendix rather than the main body because of differences in the implementation between the official repositories for SAN and NSCaching, which makes difficult compare those results equally.
22

---

Published in Transactions on Machine Learning Research (04/2025)
Model
Method
MRR
1it@10
ComplEX
NSCaching
0.387#0.001
0.577=0.001
NSCaching
EMU
40.944
0.585=0.005
DistMult
NSCaching
0.370
0.557=0.003
NSCaching
EMU
0.376+00002
0.565
TransE
NSCaching
0.322#0.000
0.470=0.002
NSCaching
EMU
0.323 #0.001
0.467=0.001
RotatE
NSCaching
n/a. a
n/a
NSCaching
EMU
n//..
l/a
Table 10: MRR and Hit@10 of the results with NSCaching code trained using FB15K-237. "NSCaching" mcans the NSCaching negative smapling. The shown results are the average with the standard deviation of three trials of the randomly determined initial weights. Note that the result of RotatE is omitted because RotatE is not provided in the original repository.
EMU parameters provided in Table 11 The results are provided in Table 10 which demonstrate that our EMU consistently improves the performance, even when using NSCaching 14
Model
Method uni
Learning Rate
Cr
np/d 3
?
ComplEX
3 x 10-4
n/a
n/a
n/a
10
NSCaching
3 x 10
n/a
n/a
n/a
10
NSCaching EMU
3 x 10-4
0.44
0.34
0.32
0
DistMult
uni
10
n/a
n/a
n/a
10-3
NSCaching XSCaching_EMM EMU
10
n/a
n/a
n/a
10
10
0.68
0.17
0.16
0
TransE
uni
10 10-4
n/a
n/a
n/a
10 10
NSCaching
10-4
10
n/a
n/a
n/a
10-2
10
NSCaching
EM EMU
10
0.54
0.168
0.151
0
Table 11: Hyper-Parameters of NScaching code trained using FB15K-237 dataset. 0, the coefficient of EMU Loss, negative label value of Unbounded LS, and the coefficient of L3-norm loss, respectively.
J Negative Sample Number Dependence
In the main body of this work, maintained fixed number of negative samples at 256. However, in Figure 5, we depict the relationship between the optimal MRR and the number of negative samples employed. Our experiments were conducted using the FB15K-237. Notably, EMU demonstrated superior MRR values in most cases, with a notable increase performance gains as the number of negative samples increased.
K Hyper-Parameter Dependence Study
In Table 12 illustrates the dependence of FMU performance hyper-parameters: a, a,np/d, and B. We considered the Dist.Mul as KGE model. The results indicate that the excessively large values of the cocfficient of EMU loss, a, are undesirable. Converscly, it is preferable to use a moderate value for the negative label value of Unbounded LS, B. Finally, the performance is relatively insensitive to the change of the mutation ratio, np/d, but exhibits a slight improvement as the value approaches the optimal one.
1he obtained MMR and H&10 values may appear excessively good; however, believe that this may partly due the NSCaching code implementation, although cannot confirm this with certainty.
23

---

Published in Transactions on Machine Learning Research (04/2025)
ComplEX
DistMult
0.330
uniform
0.320
uniform
EMU
EMU
0.315
0.325
0.310
0.320
0.315
0.305
0.310
0.300
0.305
0.295
0.300
0.290
0.295
0.285
016
064
256
512
016
064
256
512
Sumple Number
Bancle Namber
TransE
RotatE
0.31
uniform EMU
uniform EMU
0.30
0.30
0.28
0.29
0.26
0.28
0.24
0.27
016
064
256
512
016
064
256
512
Sample Number
Sampla Number
Figure 5: The negative sample number dependence of MRR trained FB15K-237. The right-edge of the ComplEX and DistMult of the uniform negative sampling case is the 'I VS ALL' results.
line with the above trend, for practical applications, we recommend initially testing the hyperparameters identified in this study, as outlined in Table Table 6 and Table 11 In particular, attention should be given tuning the coefficient of the EMU loss, a. computational resources permit, the use of hyperparameter optimization tools, such Optuna (Akiba et al.] 2019) and KGTumer (Zhang et al. 2022 is also advised.
(a, (a,np/d,3)
MRR
HITS@10
(0.11, 0.914, 0.53) basclinc
0.333
0.513
(0.5, 0.914, 0.53)
0.318
0.498
(0.9, 0.914, 0.53)
0.306
0.484
(0.11, 0.1, 0.53)
0.326
0.509
(0.11, 0.3, 0.53)
0.327
0.504
(0.11, 0.914, 0.1)
0.314
0.496
(0.11, 0.914, 0.9)
0.326
0.501
Table 12: Hyper-Parameter study results using FB15K-237 dataset with DistMult model. o. B, np are the coefficient EMU Loss, negative label value Unbounded LS, and the number mutation components, respectively.
24

---

Published in Transactions on Machine Learning Research (04/2025)
Model
Ablation
MRR
HITS@10
ComplEX
EMU
0.344
0.532
w/t ULS
0,252
(-0.092)
0.411 (-0.121)
w/t Eub.
0.302 (-0.042)
0.477
(-0.055)
w/t EMU
0.306
(-0.038)
0.486
(-0.046)
DistMult
EMU
0.332
0.513
w/t ULS
0.254
(-0.076)
0.415 (-0.098)
w/t Eub.
0.300
(-0.032)
0.477
(-0.036)
w/t EMU.
0.311
(-0.021)
0.489
(-0.024)
Rotat
EMU
0.329
0.514
w/t ULS
0,236 (-0.093)
0.386 (-0.128)
w/t Eub.
0.312 (-0.017)
0.496
(-0.018)
w/t EMU
0.305
(-0.024)
0.484
(-0.030)
TransE
EMU
0.323
0.503
w/t ULS
0.260
(-0.063)
0.423 (-0.080)
w/t Emb.Mut.
0.308
(-0.015)
0.491
(-0.012)
w/t EMU
0.314
(-0.009)
0.479 (-0.024)
Table 13: Ablation study results on FB15K-237. The number in the parentheses are the difference from the "EMU" results. "ULS' means Unbounded Label Smoothing, and "Emb.Mut." means Embedding Mutation.
L Ablation Study
In this subsection, we present the results of our ablation study to understand the individual contributions of the two main components of EMU, i.c. the Embedding Mutation and the Unbounded-LLS. To achieve this goal, we used the FB15k-237 dataset as a reference benchmark and performed a set of experiments by decoupling the embedding mutation from the Unbounded--LS. We trained the KGE models under three different scenarios: 1) the EMU, which represents the proposed EMU combining Embedding Mutation and Unbounded-LS; 2) the bascline without Unbounded-LS (w/t Unbounded-LS); 3) the bascline without the Embedding Mulation (w/l Bmb.Mul.), and 4) the case without EMU (w/t EMU). The aim of the experiments was to compare the performance reduction by removing one of the components, thereby gaining insights into their relative importance.
The results obtained from the ablation study are presented in Table 13 with the first two columns indicating the target model and the experiment setup, and the last two columns showing the MRR and HITS@10 results with the performance loss compared to the baseline. Our results consistently demonstrate that Unbounded-LS has strong impact all model This is quite natural because EMU without Unbounded-LS penalizes not only pure negative samples but also true sample embedding because of Embedding Mutation. We also hypothesize that the effectiveness of Unbounded-LS can also stem from its ability to effectively allow large gradient flow values from negative samples. This is altributed to the relatively large negative sample labels (typically larger than 0.1) and the tendency Embedding Mutation to create harder negatives, which results in larger loss values. The resulting gradients affect both the positive and negative sample components, ultimately leading to an improved representation of their embedding. In conclusion, Embedding Mutation combined with Unboundec-L.S consistently (FMU) improves performance of multiple and diverse models.
We also compared Unbounded-LLS and vanilla L.S (Szegedy al. 2016: in Appendix M and found that Unbounded-LLS is more effective than the usual T.S
25

---

Published in Transactions on Machine Learning Research (04/2025)
M Comparison between Vanilla LS and Unbounded LS
In this study we proposed the unbounded label-smoothing (LS) technique. To assess its efficacy, we also trained our models using vanilla LS (Szegedy et al., 2016) with a label smoothing parameter of 0.2. The result is provided in Table 14 which demonstrate the clear speriority of Unbounded LS for all cases.
Model
Ablation
MRR
HITS@10
ComplEX
Unbounded LS
0.344
0.532
Trouillon et al. 2016)
Vanilla LS (w/t ULS)
0.262
(-0.082)
0.423 (-0.109)
DistMult
Unlabeled LS
0.332
0.513
Yang et al.
2015
Vanilla LS (w/t ULS)
0.252 (-0.080)
0,410 (-0.103)
RotatE
Unbounded LS
0.329
0.514
Sun et al.
2019
Vanilla LS (w/t ULS)
0.236
(-0.093)
0.382 (-0.132)
TransE
Unbounded LS
0.322
0.503
Bordes et al.
2013
Vanilla LS (w/t ULS)
0.259
(-0.063)
0.423 (-0.080)
Table 14: A comparison between Unbounded LS and vanilla LS.
N An Brief Introduction to Mixup
In this section, we provide brief introduction of Micup technique that constructs virtual training examples as:
(Zhang et al. 2018). MIXUP is simple regularization
Zdixup = Az, + +1 A)zj.
(22)
where n,, Ii are the i-th input and label data, ~~ Beta(a, a) is a random scalar value controlling mixing ratio between the two samples, and E (0, oc). MIXUP is typically applied across the elements of given batch, and randomly produces new virtual samples by linearly mixing two classes shown in Equation 22 While MIXUP was originally proposed to address problems such as reducing memorization of corrupted labels and increasing the robustness to adversarial examples, we observed limitations to its performance when we extended it to embedding methods (refer to Table 2]. We hypothesize that the linear nature of MixUP-generated example restricts the magnitude of gradients without changing their direction, which limits its effectiveness. On the other hand, EMU overcomes this limitation by producing updates that can take multiple directions and thus, enhances model training.
For the MIXUP experiments, we simply replaced the embedding mutation into Mixup in Equation 22 For simplicity, we set À ~ Beta(a, 8) 8) Note that here we did not set as a = 3, as in the original implementation (Zhang et al. 2018). because we found that using different values of a and 3 resulted in a significantly improved accuracy. We attribute this to the skewed probabilistic distribution that arises due to the different values of a and 8, which allows for a higher ratio of negative samples than positive samples the mixed-tail embedding vectors.
0 Detailed Explanation of the Application of EMU to NBFNet
Model
α
np /
NBFNet w.t. EMU
1.0
0.94
0.25
Table 15: EMU hyper-parameter used for the experiments on NBFNet.
The experiments on Neural Bellman-Ford Networks (NBFNet) (Zhu al. 2021
described in subsection 4.6
were conducted using the official repository [6
We integrated the EMU loss function into the repository's
26

---

Published in Transactions on Machine Learning Research (04/2025)
code and executed the experiments using the default configuration. The hyperparameters for EMU are listed in Table 15 The experiments were conducted using three different. random seeds, which were consistently applied to both the baseline and EMU experiments. All experiments were performed on a single NVIDIA A100 GPU. this experiment, we used the binary cross entropy loss for EMU loss because of the usage of binary cross entropy loss for the vanilla NBFNet.
P Cosine Similarity Between Negative Samples
Figure plots the cosine similarity among negative samples for EMU-EMU, uniform-unii uniformm and uniform- EMU. The results indicate that the similarity between uniform negative samples are consistently lower than that of EMU negative samples, suggesting that EMU generates more hard negative samples.
codle civibrity chaggstheneggtheecoooo palls
unfform-2V
Figure 6: Cosine similarity of negative-negative tail pairs for DistMult with FB15k-237.
27


Reviews:
[{"review_id": "hm7IwMcMT9", "reviewer": "Reviewer_2EYK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n1. The paper provides a solid theoretical analysis, identifying a sufficient condition for an effective negative sample distribution that leads to optimal KGE.\n2. The proposed EMU framework generates negative samples by mutating embedding vectors, and is designed to be simple and compatible with existing KGE models, making it easy to integrate into current workflows. This practical aspect enhances its potential for widespread adoption.\n3. The paper includes extensive experiments across multiple datasets and KGE models, demonstrating consistent and significant improvements in link prediction performance. The results show that EMU can achieve performance comparable to models with much larger embedding dimensions, reducing computational complexity.\n4. The authors provide an implementation of EMU and the experiments, which facilitates reproducibility and further research by the community.\n\n## Weaknesses:\n1. The core of EMU is Eq.(6), which is pretty simple and straightforward. While the authors already provide a theoretical analysis on its relationship with Y20, I think their relationships are not as close as claimed in the paper, and it would be better if the authors could provide more insights on why this simple mutation strategy works well in practice. For example, what kind of information is preserved in the mutated embeddings that make them effective negative samples?\n2. Some experiments are not convincing. For example, in Table 1, the ablation study was conducted with only one dataset and two baseline models, then the authors concluded that EMU enables models with smaller embedding dimensions to achieve performance comparable to those with much larger dimensions. However, the results may not be generalizable to other datasets or models. It would be better if the authors could conduct more ablation studies on different datasets and models to validate their conclusions. Besides, larger dimensions don't always result in better performance.\n3. It's pleased to see that the authors have compared with Mixup in KGE tasks. Mixup is a general data augmentation method, and it's not specifically designed to generate negative samples in KGE tasks. Regardless of its theoretical foundation, EMU also appears to be general, but this work only discusses its application in KGE tasks. It would be better if the authors could provide more insights on how EMU could be applied to other tasks or domains.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper attempts to address the challenge of generating high-quality negative samples for training Knowledge Graph Embedding (KGE) models, which is crucial for improving link prediction performance. The authors theoretically investigate the conditions under which negative samples lead to optimal KGE and propose a novel framework called Embedding MUtation (EMU). EMU generates negative samples by mutating embedding vectors, ensuring that the generated samples satisfy the identified optimal condition. The paper demonstrates through extensive experiments that EMU significantly improves link prediction performance across various KGE models and datasets, even enabling models with smaller embedding dimensions to achieve performance comparable to those with much larger dimensions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "keaxEXYCXl", "reviewer": "Reviewer_wpzR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- I agree that negative samples are crucial for KGE training. The proposed method generates negative samples by mutating embeddings, which differs from conventional methods that corrupt positive triples. The simplicity of EMU allows for seamless integration with existing KGE models and negative sampling methods.\n\n- The paper provides a solid theoretical basis for the proposed method, identifying conditions under which negative samples lead to optimal KGE for DistMult.\n\n- The work conducts extensive experiments across multiple datasets and KGE models, demonstrating some improvements in link prediction performance.\n\nWeaknesses:\n\n- It seems that the theoretical analysis in the paper is based on DistMult. It remains to be seen whether the theory still holds when integrated with other KGE models.\n\n- In my view, achieving optimal learning objectives does not imply that the vectors are optimal, as the non-existent edges in the KG may not necessarily be incorrect. The theoretical analysis and referenced work in this paper do not take this point into consideration.\n\nTypos:\n\n- In Abstract, \"consistenly\" -> \"consistently\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a new method for improving knowledge graph embedding (KGE) models by generating high-quality negative samples. The method, called Embedding Mutation (EMU), generates negative samples by replacing a certain amount of the embedding vector components in the negative sample with the corresponding parts of the true positive vector components. The work implements the method based on DistMult and demonstrates that EMU can help DistMult achieve optimal embeddings. Experiments on benchmark datasets show that the proposed EMU method can be successfully integrated into several KGE methods to achieve performance improvements.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Discussions on whether the theory still holds when integrated with other KGE models or what the prerequisites are for the proposed theory to hold.\n\n- It would be beneficial to include experiments with more recent KGE models, if possible.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OdfEuQPq1d", "reviewer": "Reviewer_VhgB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. Novel Method. EMU introduces a novel and effective method for generating hard negative samples by mutating embedding vectors. This approach is different from conventional methods that focus on identifying challenging negatives within the training data.\n\n2. Simplicity and Compatibility. EMU is designed to be simple and easy to integrate with existing KGE models and negative sampling strategies.\n\n3. Significant Performance Improvement. The experimental results consistently show substantial performance improvements with EMU across various KGE models, datasets, and negative sampling methods.\n\n4. Theoretical Foundation: The paper provides a theoretical analysis of the conditions for optimal negative sampling in KGE, which gives a solid basis for the proposed method, moving beyond purely empirical approaches.\n\n5. Comprehensive Experimental Evaluation. The experiments are comprehensive, covering several datasets (FB15k-237, WN18RR, YAGO3-10) and multiple KGE models (ComplEX, DistMult, RotatE, TransE, HAKE), along with comparisons to several baselines.\n\n### Weaknesses\n\n1. Computational Overhead: The additional gradient flow through negative sample components due to mutation results in a larger GPU memory usage and training time, although the method tends to reach maximum performance faster than other methods.\n\n2. Lack of generalizability: EMU did not perform well on WN18RR dataset, which requires further analysis.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Embedding Mutation (EMU), a framework for generating negative samples in knowledge graph embedding (KGE) link prediction. EMU mutates negative embeddings using components from positive embeddings, guided by theoretical conditions for optimal embedding. It is simple, compatible with existing methods, and consistently improves link prediction performance, matching models with larger embedding dimensions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The paper claims: \"EMU is currently limited to knowledge graph link prediction models trained using the cross-entropy loss function.\" Can EMU be extended to other loss functions, such as margin-based loss functions, beyond cross-entropy?\n\n2. Are there more effective and parameter-free methods to determine the optimal amount of embedding mutation rather than random sampling?\n\n3. What further analysis can be done to understand why EMU performs differently on WN18rr compared to other datasets? Is there a link between the optimal distribution and the features of different knowledge graphs?\n\n4. How can we evaluate potential bias that may arise during the model training process due to feature mutation?\n\n5. The proposed EMU method offers a novel approach to generating high-quality negative samples, which may lead to integration with tools like KGTuner (arXiv:2205.02460) for enhanced knowledge graph learning. Considering that KGTuner is designed for efficient hyperparameter search in Knowledge Graph Learning, how can KGTuner and the proposed EMU method be effectively combined to achieve joint optimization?\n\n6. Given that the proposed EMU method focuses on improving the quality of negative samples, how can EMU be effectively integrated with various existing KGE models (e.g., NBFNet (arXiv: 2106.06935), AdaProp (arXiv:2205.15319),  A*net (arXiv:2206.04798) and PPR (arXiv:2403.10231)).", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the Embedding Mutation (EMU) framework for generating negative samples in knowledge graph embedding. By extending the Y20 framework, the authors derive conditions for optimal negative sample distributions and demonstrate that mutating embedding vectors with EMU markedly improves link prediction performance across multiple datasets and models, achieving results comparable to models with fivefold larger embeddings.

Strength
- The paper offers a robust theoretical foundation with rigorous derivations that establish sufficient conditions for effective negative sample distributions.
- EMU introduces a novel mechanism for generating negative samples through embedding mutation, which contrasts with traditional methods that simply corrupt positive triples.
- The simplicity of EMU and its seamless integration with existing KGE models enhance its practical applicability. 
- Extensive experiments across diverse datasets and models consistently demonstrate significant improvements in link prediction 
performance.


Weakness:
- EMU demonstrates diminished performance on WN18RR, likely due to intrinsic latent space isotropy; further analysis could better elucidate this phenomenon.
- The mutation ratio (α) requires careful tuning, and the lack of adaptive parameter adjustment strategies may limit EMU’s robustness in diverse scenarios.

Please revise the submission accordingly, and ***add color to the revised version to make easy check.***
Decision: Accept (poster)