Rethinking Identity in Knowledge Graph  Embedding
Authors: Jiayi Li
Jiaqi Sun
Yujiu Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Knowledge Graph Embedding
Knowledge Graph Completion
Bilinear Based Models

Abstract: Knowledge Graph Embedding (KGE) is a common method to complete real-world Knowledge Graphs (KGs) by learning the embeddings of entities and relations.
Beyond specific KGE models, previous work proposes a general framework based on group. A group has a special element identity that uniquely corresponds to the relation identity in KGs, which implies that identity should be represented uniquely. However, we find that this uniqueness cannot be modeled by bilinear based models, revealing the crack between the framework and models. To this end, we study the required conditions and propose a solution named Unit Ball Bilinear Model (UniBi). In addition to the theoretical superiority, UniBi is more robust and interpretable. Experiments demonstrate that UniBi models the uniqueness without the cost of performance and verify its a robustness and interpretability. 

RETHINKING IDENTITY IN KNOWLEDGE GRAPH EM- BEDDING
Anonymous authors Paper under double-blind review
ABSTRACT
Knowledge Graph Embedding (KGE) is common method to complete world Knowledge Graphs (KGs) by learning the embeddings of entities and relations. Beyond specific KGE models, previous work proposes a general framework based on group. group has special element identity that uniquely corresponds the relation identity in KGs, which implies that identity should be represented uniquely. However, we find that this uniqueness cannot be modeled by bilinear based models, revealing the inconsistency between the framework and models. To this end, we propose a solution named Unit Ball Bilinear Model (UniBi). In addition theoretical superiority, it has greater interpretability and improves performance by preventing ineffective learning with the least constraints. Experiments demonstrate that UniBi models the uniqueness and verify its interpretability and performance.
INTRODUCTION
Knowledge Graphs (KGs) store human knowledge in the form of triple r, r,,, which represents relation between a head entity h and a tail entity (Ji et al. (002)). KGs benefit a lots of downstream tasks and applications, e.g., recommender system (Zhang et al. 2016), dialogue system (He et al.. 2017) and question answering (Mohammed et al.] 2018). Since actual KGs are usually incomplete, researchers are interested predicting missing links to complete them. As a common solution, Knowledge Graph Embedding (KGE) completes KGs by learning low-dimensional representations of entities and relations.
Beyond the great advances in specific KGE models (Trouillon et al. 2016 Hitchcock 1927 Chami ct al. 2020; Liu et al. 20177; Nickel et al. 2011: Bordes et al. 2013) , several works also attempt to unify these models with general frameworks, such promising ones based group (Yang al. 2020 Xu & Li 2019 Ebisu & lchise 2018). Group is an abstraction of an operations on a set, like addition on integer. Just like such case has a special number 0, each group has unique element identity. From the perspective of group, such element requires that its correspondence in KGs, identity relation. should be represented uniquely. However, find that such uniqueness cannot be modeled by bilinear based models, which reveals the inconsistency between the framework and models.
To present the problem more clearly, we first need to introduce some notation. A model with a score function shh, t) can model the uniqueness of identity means that Yh + f,, s,, r. h) > s(h, r, t) holds if and only if r is identity and its universal representation is unique. In addition, the score function s(-) of bilinear based model is h Rt, where h, R, t are the representations
h, r, and
In terms of such uniqueness, bilinear based models have two flaws. On the one hand, Fig. ((a) demonstrates e Iei < e, Iez, which means that the relation matrices per se do not model identity perfectly. On the other hand, Fig. [(b) shows even if matrix, e.g. does. Its scaled one kI can also model identity and thus breaks the uniqueness.
Obviously, modeling this property requires both entities and relations to be restricted, which reduces expressiveness. To avoid this side effect, we make the cost negligible by minimizing the constraints, one per entity relation, while modeling the desired property. To be specific, vectors of the entities and the spectral radius of the matrices of the relations to 1. Since the model captures entities in unit ball shown in Fig. [(e) we name it Unit Ball Bilinear Model (UniBi)
normalize the

---

(a)
(b)
(c)
Figure 1: The flaws of bilinear based models and our solution terms of modeling the uniqueness of identity. (a) Identity matrix fails model identity. (b) Scaled identity matrix could also model identity. (c) An illustration of UniBi. All entities are embedded in the unit sphere and stay in the unit ball after relation specifie transformations.
In addition to the theoretical superiority. UniBi is more powerful and interpretable since modeling identity uniquely requires normalizing the scales that barely contain any useful knowledge. On the one hand, scale normalization prevents ineffective learning on scales and makes UniBi focus more on useful knowledge. On the other hand, reveals the connection between the relative ratio of singular values and the complexity of relations.
Experiments verify that UniBi models identity uniquely with improvement on performance and interpretability. Therefore, UniBi reconciles the framework and bilinear based models in terms of identity and paves the way for further studies both.
PRELIMINARIES
2.1 BACKGROUND
Knowledge Graph K. is set that contains the facts about sets of entities & and relations R. Each fact is stored by a triple (e,r ex) E x R x & where and ry denote the i -th entity and the j -th relation, respectively.
KGE aims to predict the missing links in K. by learning embeddings for each entity and relation via E - R. To verify the performance of KGE method, I. is first divided into Keroin and Ktestt Then, the method is trained on Kerain to learn the embeddings e and r (or R) for each entity E E and relation r Finally, the model expected to give a higher rank (es, (),,e) E K. while a lower rank if (ez, ex) & K, for each query (e,, hy, ?) from Ktest and the candidate entity eg E E.
score function & x R
In addition to the above tail prediction, models are also required to test on head prediction conversely. transform to tail prediction by introducing reciprocal relations following Lacroix al. (2018).
Group is the abstraction of an operation on a set. For example, additive group of integers is consists of addition and all integers, and identity element is O. Since we do not expand on this concept in the main text, put the formal definition in Appendix B To avoid confusion, we use bold to represent the element identity while italics to denote identity and other relations. And we gives the definition of modeling identity uniquely in the following.
Definition A KGE model can uniquely model identity means s(h, r, h) r,h,r,t), Wh,t E &, + t holds if and only if r is identity and its universal representation, i.e., it works in any KG, is unique.
2.2 OTHER NOTATIONS
We utilize É and jR to denote the set of all possible representations of entities and relations. And È and R Å to denote the embedding vector of the entity and the transformation matrix specific to the relation R. Furthermore, we use || Il to denote the L2 norm of the vectors, || ||r and p(-) represent the Frohenius norm and the spectral radius of matrix.
2

---

In this paper, we focus on n-dimensional real space IR, which means E R" and i R We also consider real vector spaces whose vectors are complex C" or hypercomplex space H since they are isomorphic to 2 or 12
RELATED WORK
Previous work of KGE can be roughly divided into the following three categories: distance, bilinear and others.
Distance based models choose Euclidean distance for their score functions. TransE (Bordes et al. 2013) inspired by Word2Vee (Mikolov et al. (013) in Natural Language Processing proposes the first distance based model, which translation the linear transformation s(h, r, () || r t|l- TransH (Lin et al. 2015) and TransR (Lin et al. 2015) find that TransE difficult to handle complex relations and thus apply linear projections before translation. Apart from translation, RotatE (Sun it al. (2019) first introduces rotation as the transformation. RotE (Chami et al. (0020) further combines translation and rotation. Some works also introduce hyperbolic spaces (Balazevic et 2209b) Chami et al. 2020) Wang al.] (22T). Apparently, distance based models are capable of uniquely modeling identity since the distance between vector and itself
In contrast, bilinear based models have score functions in the bilinear form r,,,,, = Rt. RESCAL (Nickel et al. 2011) is the first bilinear based model whose relation matrices are uncon- strained. Although RESCAL is expressive, it contains too many parameters and tends to overfitting. DistMult (Yang et al.] 2015) simplifies these matrices into diagonal ones. ComplEx (Trouillon
al. 2016) further introduces complex values to model the skew-symmetry pattern. Analogy (Liu 2017 uses block-diagonal to model the analogical pattern and subsumes DistMult, ComplEx,
et al.
and HolE (Nickel et al. 2016). Moreover, QuatE (Zhang et al.) 2019) extends complex values to quaternion and GeomE (Xu et al. (020)) utilizes geometric algebra to subsume all these models. However, these studies have noticed that bilinear based models fail uniquely model identity.
Corresponding to identity, identity is a special element in a group which first introduced by Dihedral (Xu Li 2019) and HolE (Nickel et al.) 2016)) Based on group. NagE (Yang al. 2020) proposes a general framework to incorporate previous methods. Although they believe that the matrix representation for identity they ignore the fact that identity may not be uniquely modeled by
specific models.
In addition, other works using black- box networks (Dettmers al. 2018 Nguyen al. 2018 Yao
et al. 20199 (Schlichtkrull et al.) 2018 Zhang et (0200)) or additional information (An et al. 2018 Ren al. 2016) are beyond the scope of this paper.
METHOD
In this section, we first discuss the relationship between the identity element in groups and the identity relation in KGs, and give the condition for bilinear based models to model identity uniquely in Section [.1 We then propose model named UniBi that satisfies with least constraint in Section and an efficient modeling for UniBi in Section 4.3 In addition, we also discuss its improvement on performance and interpretability via scale normalization in Section 4.4
4.1 IDENTITY AND IDENTITY
In previous work, framework based on group has been proposed (Yang al. 2020). It states that all relations should be embedded as elements of a group. Groups have special element identity. which corresponds the identity relation in KGs. This correspondence implies that identity should have a unique representation.
Sounter-intuitively, we find that in fact bilinear based models fail to model this uniqueness. We demonstrate two cases in which bilinear based models violate it. On the one hand, Fig. [(a] demonstrates e, Iej < el Ie2, which means that the matrix of a relation per se is not guaranteed for modeling identity. On the other hand, Fig. shows even if matrix, e.g., I, does. Its scaled one
We also prove this rigorously in Appendix
3

---

AI where & >> 0, k # 1 can also model identity, which contradicts the guantification of uniqueness. Therefore, we give formal definition based on definition as following to investigate how to modify bilinear based models model this uniqueness.
Definition 2. bilinear model can uniquely model identity means:
R E R Vh, E, h Rh Rt.
(I)
where 31 is the uniqueness quantification.
4.2 UNIT BALL BILINEAR MODEL
From the above examples, is clear that both embeddings of entities and relations needed to be constrained. Obviously, modeling identity requires both entities and relations be restricted, which will reduce expressiveness. solve this dilemma, we make the cost negligible by minimizing the constraints, per entity or relation, while modeling the desired property.
To be specific, we normalize the vectors of the entities and the spectral radius the matrices of the
relations to 1 by setting E {e ||e|| = 1, e E [²} and R (R p(R) = R, E [=x"). We
name the proposed model as Unit Ball Bilinear Model (UniBi), since captures entities in unit ball
as shown in Fig. ((c) The score function of UniBi i
s(h,r, r,
Rt,
||b]] ||t|| = 1, (R) =
(2)
We then have the following theorem. Theorem 1. UniBi is capable uniquely model identity in terms of definition 2
Proof. Please refer to the Appendix A.2
4.3 EFFICIENT MODELING
4.3.1 EFFICIENT MODELING FOR SPECTRAL RADIUS
Although the proposed model has been proven to model identity uniquely, it still has a practical disad- vantage, since it is difficult to directly represent all matrices whose spectral raidus are 1. In addition, also time-consuming to calculate the spectral radius p(-) via singular values decomposition (SVD).
To avoid unnecessary decomposition, where R R, are orthogonal matrices and Σ Diag(o] I....................... on is a positive semidefinite diagonal matrix. And we maintain the independence of these three components during training. Therefore, it
divide a relation matrix into three parts R R,
R. ER. And we transform the becomes simple to obtain matrices whose spectral radius is 1, that is, Gmax score function Eq. into the following form.
h R ER,
s(h, r,), Tmax h ||||||
(3)
where mmaz is the maximum among dg.
4.3.2 EFFICIENT MODELING FOR ORTHOGONAL MATRIX
In addition, we find that the calculation of the orthogonal matrix is still time-consuming (Tang et al. 2020). To this end, we only consider the diagonal orthogonal block matrix, where each block is low-dimensional orthogonal matrix. Specifically, R, and R, Taking R, as an example R₁ = Diag(SO(k) S),kk..)((())) g where SO(k), denotes the i-th special orthogonal matrix, that is, the rotation matrix.
use k-dimensional rotation matrices build
The rotation matrix only represents the orthogonal matrices whose determinant are and does not represent the ones whose determinant -1. To this end, we introduce two diagonal sign matrices of n-th order S,, S, E S where
+1, ifi= o, ifi
SS S
We present in more detail the similarities and differences between our constraints and those of our predeces- in the Appendix
4

---

Identity
Ineffective Learning
Removed
Scale
Performance
Scale Norm.
Performance
Expressiveness
Expressiveness
Scale
Other Factors
Other Ways
Other Factors
Other Ways
Figure 2: How modeling identity improves the performance. a) An illustration of how scale affects the performance. On the plus side, it has little effect on expressiveness, on the minus side, it causes the ineffective learning. b) Modeling identity requires scale normalization, which removes the effect of scales. c) UniBi improves the performance since it only deals with scales and not the other factors.
Thus, we could rewrite the score function Eq. to
h S, Tmax h /||/t|
sh, r, t)
(5)
However, the sign matrix S, and S, are discrete. To address this problem, notice that Sn, E, S. can be merged into matrix that
i 818,0 0
B
(6)
if j.
where = i.. sy = (St) i,j I,..., and E = Diag(En.....55 Thus, we incorporate the discrete matrices S,. S, into the continuous matrix E.
h R ER,t
s(h,r,t)
Emar
tt]
where [maa is the maximum among (5:).
4.4 OTHER BENEFITS FROM SCALE NORMALIZATION
In addition theoretical superiority, UniBi is more powerful and interpretable, since modeling identity requires normalizing the scales that barely contain any useful knowledge. On the one hand, obvious that modeling identity uniquely needs to avoid the cases in Fig. I(a) and Fig. ((b) which
requires normalizing the scales of entities and relations. On the other hand, is counter-intuitive that the scale information useless for bilinear based models.
Scale information is treated as useless because what really matters is not the absolute values but the relative ranks of scores. And scale contributes nothing to the ranks, since they remain the same after multiply these scores by factor greater than zero:
s' (h,, r,,t (ke h)) (ket) k,,,(h Rt) = k2k, s(h,r,
(8)
where ke, k O. Therefore, treat learning scales ineffective
4.4.1 PERFORMANCE
As illustrated in Fig. 2 UniBi has better performance, since it prevents ineffective learning with the least constraints. On the hand, by preventing ineffective learning, UniBi focuses more on learning useful knowledge, which helps improve performance. On the other hand, it pays negligible cost of expressiveness, since it adds only one equality constraint each entity or relation, which is ignorable when the dimension d is high.
In other words, although our scale normalization is a double-edged sword, its negative effect is negligible, and thus leads to better performance. It should be noticed that the loss expressiveness may outweighs the gain on learning, scale normalization is replaced by a sticker one. For example, if we constrain the matrix to be orthogonal, the cost of expressiveness is no longer negligible, since an orthogonal matrix requires that each of its singular values be 1, which is d equality constraints.
Further discussion in Appendix

---

hiper
tphr
complexity
h
IaParentyy
3
isSonny
e1 e2
Alice
David
(a)
(b)
Figure 3: Complexity and contraction. (a) A toy example to show how to calculate complexity. (2) the aggregation corresponds the singular values less than 1.
4.4.2 INTERPRETABILITY
In addition to performance, scale normalization also helps us to understand complex relations. Complex relations are defined by whither hptr (head per rail of relation) tphr (rail per head of relation) is higher than a special threshold 1.5 (Wang et al.] (011)). Therefore, all relations are divided into 4 types, i.e. 1-1, 1-N, N-1, and N-N. However, suggest fine- aie-ggained continuing metric complexity instead. To better demonstrate this idea, we gave an example in Fig. ((a] and the definition of complexity as follows.
think this division is too coarse-grained and
Definition 3. The complexity of a relation is the sum of its hptr and tphr.
Intuitively, complex relations are handled by aggregating entities through projection (Wang et al. 2014 Lin al., (015), which implies that the higher the complexity of relation, the stronger its aggregation effect, and vice versa.
We note that this aggregation effect can well characterized by the relative ratio, or imbalance degree, of singular values of UniBi. For any relation matrix R = UEVT, both U and V are isometry, and only the singular values the scaling matrix contribute to the aggregation. Moreover, the singular values of UniBi are less than or equal to since the spectral radius, i.e. the maximum singular value, are normalized. This shows promising correspondence between the singular values of our model and the aggregation and further to the complexity. demonstrated in Fig. 3(b) Therefore, could use singular values to represent the complexity of relations, which increases the interpretability of UniBi.
is worth mentioning that this interpretabity can be transferred to other bilinear based models they normalize the spectral radius of their relation matrix UniBi does.
EXPERIMENT
In this section, we give the experiment settings in Section 5.1 We verify that UniBi is capable to uniquely model identiry, while previous bilinear based models are not in Section 5.2 UniBi is comparable to previous SOTA bilínear models in the link prediction task, shown in Section 5.3 In addition, we demonstrate the robustness UniBi in Section 5.4 and the interpretability about complexity in Section 5.5
Table I: Statistics of the benchmark datasets.
Dataset
|3]
[
Training
Validation
Test
WNI 8RR
40,943
11
86,835
3,034
3,134
FB 237
14,541
237
272,115
17.535
20,466
YAGO3-10-DR
122,873
36
732,556
3,390
3,359
We discuss this characteristic in depth from the perspective of group in Appendix

---

5.1 EXPERIMENT SETTINGS
Dataset We evaluate models on three commonly used benchmarks, i.e. WNI8RR (Dettmers et al.
2018). FB15k-237 (Toutanova & Chen 2015) and YAGO3-IO-DR (Akrami al. 2020). They proposed by removing the reciprocal triples that cause data leakage in WNT8, FBI5K and YAGO3-10 respectively. Their statistics are listed in Tbl.
Evaluation metrics We use Mean Reciprocal Rank (MRR) and @its@k (k = 1, 3, 10) as the evaluation metries. MRR is the average inverse rank of the correct entities that are insensitive to outliers. Hits @k denotes the proportion of correct entities ranked above k.
Baselines Here we consider two specific versions of UniBi: UniBi-O(2), UniBi-O(3), which use rotation matrices in 2 and 3 dimensions to construct the orthogonal matrix. To be specific, we use the unit complex value and the unit quaternion to model the 2D and 3D rotations using the x 2 and 4 x 4 matrices, respectively. For more details, see the Appendix G.T
UniBi is compared with these bilinear models: RESCAL (Nickel et al. 2011). CP (Hitchcock) [927]. ComplEx (Trouillon et al., 2016). and QuatE (Zhang al. 2019). In addition, it also compared to other models: RotatE (Sun et al. 2019), MurE (Balazevic et al. 2019b) and RotE (Chami al.
2020), Turcker (Balazevic et al. 2019a) and ConvE (Dettmers al. 2018).
Optimization We adopt the reciprocal setting [acroix et al., 2018) ) which creates a reciprocal relation r' for each and a new triple (eg, e4) for each (e;, r,,, ex) K. Instead of using Cross Entropy directly (Lacroix et al., 20188] Zhang et al., 2020a] 2019). we add an extra scalar y > before softmax function. Since UniBi is bounded, it brings upper bound to loss that makes the model difficult to optimize as discussed by /aan et al. (2017).
exp(y exp(7,s(h,r,.)) s(h,r,t) Erec exp(y r(,,,, + A Re,
L= Σ log
(9)
where Reg(h, r, is the regularization term and > its factor. Specifically, we only take Reg(h, r, as DURA (Zhang et al. 2020a) in experiments, since it significantly outperforms other regularization terms. In addition, 7 is set to for previous methods and greater than for UniBi. And we set the dimension n to 500. For other details on the implementation, see Appendix G.2
5.2 MODELING IDENTITY UNIQUELY
In this part, we verify that 1) UniBi is capable to uniquely model identity while previous models fail, and 2) both constraints the embedding of entities and relations indispensable. We explicitly add identity as a new relation to benchmarks and use its corresponding matrix to determine whether the uniqueness is modeled. In particular, this matrix is supposed to converge the identity matrix I or a scaled one. To evaluate it, we introduce a new metric imbalance degree A
(Ei
1)2.
We first compare UniBi with CP (Hitchcock 1927) and RESCAL (Nickel et al. 2011), the least and most expressive bilinear model on FB15k- 2377. Besides, also apply DURA (Zhang al. 2020a) to models to explore whether these methods are able to uniquely model identity under extra regularization. As demonstrated in Fig. 4{a] the imbalance degree Á of UniBi converges to 0 while others fails, which verifies that UniBi is capable to uniquely model identity. In addition, the imbalance of other models decreases some extent when using DURA, yet they are still unable to uniquely model identity. Then, to show that UniBi can uniquely converge to identity, we use two matrices R, and R₂ model it independently. As shown in Fig. 4(b) the error between R,, and R₂ also converges to 0, which means that they all converge to I.
We then perform an ablation study to verify that both the entity constraint (EC) and the relation constraint (RC) are needed to model identity uniquely. The experiments show that only using either constraint not enough to model the uniqueness of identity, as illustrated in Fig. 4(c) And this
verify the existence of problems shown in Fig. [(a) and Fig. l(b)
5.3 MAIN RESULTS
In this part, we demonstrate that the constraints helps UniBi to achieve better performance. We mainly compared our model with previous SOTA models, i.e. CP (Hitcheock) 1927), ComplEx (Trouillon
7

---

(a) UniBi V.S. others.
(b) Error between different matrices converges.
(c) Abaltion of constrains.
Figure 4: UniBi capable to uniquely model identity. (a) the imbalance degree (A) of UniBi converges to 0 while others diverge. (b) The enrors between different matrices modeling identity converge to 0 on different datasets. (c) Both entity constrain (EC) and relation constrain (RC) are indispensable for UniBi model identity.
Table 2: Evaluation results on WN18RR, FB15k-231 237 and AAG03-10-DB datasets. We reimplement
RotE, CP, RESCAL, ComplEx with 500 and denoted by +, while we take results on WN18RK and FB 157-237 from the origin papers and YAG03-10-DR from Akrami et al. (2220) Best results
are in bold while the seconds are underlined.
FB15K-237
YAGO3-10-DR
Model
MRR
Hite01
Hiis
MRR
Hit@01
Hise@10
Hise
Hite@10
DistMult
0.43
0.39
0.49
0.241
0.155
0.419
0.192
0.133
0.307
ConvE
0.43
0.52
0.325
0.237
0,501
0,201
0,147
0.315
0.266
QualE
0,488
0.438
0,582
0,348
0.248
0.550
Roma:
0.476
0.428
0.571
0.338
0.241
0.533
0:214
0.153
0.332
Mur!
04481
0.110
0.566
0.335
0.213
0,518
RodE
0.346
CP
0.457
0.414g0.002
0.549
200612000
0.2001220011
43.200
0.176
0.370
ComplExt
0-487 2.487 2001022
0.4402g0..0
0.571
0.36120001
0.260
22.00
0.552
0.238
0.174gnom
0.3 0.300
RESCAL?
0.495
10452
0.576g0
0 0.364g000
0.272
0.547
0 0:23330000
0.108g0m0
0.360
UniBi-DI2)
a0.87
164600.00
0.56619ac2
0,370
20.001
10,000
3.247
wio consamint
0.488 c0.0
0.568
0.361 0.361
20
22.001
0.24240003
0.170
UniBi-O(3)
0 192
0.452
0.452
0.57
0.300
0.274 coate
(.56)
0 1.2
16200
0,180
0,180
2000
0.377
wro constraint
0. 0.488
44640.00
0.567.t
0.361
0.550
0.24 2000
0.175g0002
0.570
al. 2016) and RESCAL (Nickel et al. 2011 using DURA regularization. Although these models have been implemented by Zhang et al. 2020a), the dimensions of CP and ComplEx are very high and have not been tested YAGO3- 1--03-10-DD- DR, further remove the constraint of UniBi-O(n) as ablations to eliminate the influence of other factors.
reimplement them in this paper. In addition,
In Tbl. 2 UniBi achieves comparable results to previous bilinear based models and the unconstrained versions. UniBi only slightly and justifiably below RESCAL on WN18RR, since RESCAL needs require much more time and space")
5.4 UNIBI PREVENTS INEFFECTIVE LEARNING
In this part, we verify the superiority of UniBi comes from preventing ineffective learning. We conduct further comparisons without regularization. In addition, we also adopt EC and RC in Section 5.2 to study the effect of both constraints. All experiments implemented WN18RR.
On the one hand, UniBi decreases slightly, while others decrease significantly when the regularization term removed, as demonstrated in Fig. 5(a) It shows that learning of UniBi is less dependent on extra regularization, since it is better at learning by preventing the ineffective part. On the other hand, we illustrate the MRR metric of UniBi and ablation models on validation
as epoch grows in Fig, 5(b) It shows that either constrain alleviates overfitting to some extend but fails to prevent the downward sliding behind since the scale of the unconstrained part may diverge. Thus, both constraints are verified to be indispensable for preventing the ineffective learning and performance of UniBi
Detailed in Appendix
8

---

W DURA
M40 DURRA
0.40
0.33
0:30
025
UNIB:
Uniel (WO
compler
HANAAL
unte
untel
J00
124
200
spoch
(a) Ablation of regularization.
(b) Ablation of constrains.
Figure 5: UniBi benefits from preventing ineffective learning. (a) UniBi maintain its performance without regularization while other models not. (b) Neither entity constraint (EC) nor relation constrain (RC) alone stops the sliding of performance.
13.12 22
(a) WNI8RR
(b) FB15k-237
YAGO3-I0-DR
Figure 6: The imbalance degree (A) and complexity (# hptr # tphr) of relations in WN18RR FB15K-237 and YAGO3- 10-DR respectively. Two metric are highly correlated and the imbalance of relation (A,) and the imbalance of its reciprocal one (Apr) are very close.
5.5 CORRELATION TO COMPLEXITY
To verify the statement in Section the complexity of each relation three benchmarks, where complexity is calculated following definition Furthermore, we measure the singular values of a relation by the imbalance degree A. A, and A, denote them.
we study the connection between singular values and
To differentiate A of relation and its reciprocal relation r',
As demonstrated in Fig. 6, we find that singular values are highly correlated with the complexity of a relation. Furthermore, notice that A, and A,r are very close even if relation is unbalanced (1-N or N-1), which shows that complexity is handled by aggregation regardless of direction.
CONCLUSION
In this paper, we reveal that previous bilinear models fail model the uniqueness relation identity required by general frameworks based on group. To address this problem with negligible cost, we propose UniBi, which has been proven to handle it by capturing entities in a unit ball. Furthermore, UniBi benefits from scale normalization required by modeling the identity uniquely. On the one hand, scale normalization prevents ineffective learning and leads to better performance; on the other hand, it reveals that the relative ratio of singular values corresponds to the complexity of relations and improves interpretability. Therefore, UniBi reconciles the framework and bilincar based models in terms of identity and paves the way for further studies of both.

---

REFERENCES
Farahnaz Akrami, Mohammed Samiul Saeef, Qingheng Zhang, Wei Hu, and Chengkai Li. Realistic re-evaluation of knowledge graph completion methods: An experimental study. In SIGMOD, pp. 1995-2010. ACM, 2020.
Bo An, Bo Chen, Xianpei Han, and Le Sun. Accurate text-enhanced knowledge graph representation learning. In NAACL-HLT, pp. 745-755, 2018.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. In EMNLP/JCNNLP (1), pp. 5184-5193, 2019a.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Multi-relational poincaré graph embed- dings, In NeurIPS, pp. 4465-4475, 2019b.
Antoine Bordes, Nicolas Usunier, Alberto García-Durti Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NeurlPS, pp- 2787-2795, 2013.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. In ACL, pp. 6901-6914, 2020.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d
knowledge graph embeddings. In AAAI, pp. 1811-1818 2018.
Takuma Ebisu and Ryutaro Ichise. Toruse: Knowledge graph embedding on a lie group. In AAAI, pp. 1819-1826, 2018
He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings. In Regina Barzilay and Min-Yen Kan (eds.), ACL, pp. 1766-1776. Association for Computational Linguistics, 2017.
Frank L Hitcheock. The expression of tensor polyadic as sum of products. Journal of Mathematics and Physics, 6(1-4):164-18, 1927.
Nathan Jacobson. Basic algebra I. Courier Corporation, 2012.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip Yu. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Trans Neural Netw Learn Syst., pp. 1-21, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML., volume 80, pp. 1869-28778 2018.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In AAAI, pp. 2181-2187, 2015.
Hanxiao Liu, Yuexin Wu, and Yiming Yang. Analogical inference for multi multi-relational embeddings.
In ICML, volume 70, pp. (166-2178.,. 2017.
Tomás Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In NeurlPS, pp. 3111 3111-3119, 2013.
Salman Mohammed, Peng Shi, and Jimmy Lin. Strong baselines for simple question answering over knowledge graphs with and without neural networks. In NAACL-HILT (2), pp. 291-296, 2018.
Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Q. Phung. A novel embedding model for knowledge base completion based on convolutional neural network. In NAACL-HLT (2), pp. 327-333, 2018.
Maximilian Nickel, Volker Tresp. and Hans-Peter Kriegel. three-way model for collective learning on multi-relational data. In JCML, pp. 809-816, 2011.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowledge graphs. In AAAI, pp. 1955-1961, 2016.
10

---

Xiang Ren, Wenqi He, Meng Qu, Clare R. Voss, Heng Ji, and Jiawei Han. Label noise reduction in entity typing by heterogeneous partial-label embedding. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), SIGKDD, pp. 1825-1834. ACM, 2016.
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, volume 10843, pp. 593-607, 2018.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Yun Tang, Jing Huang, Guangtao Wang. Xiaodong He, and Bowen Zhou. Orthogonal relation transforms with graph context modeling for knowledge graph embedding. ACL, pp. 2713-2722, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionaliiy, pp. 57-66, Beijing, China, July 2015.
Théo Trouillon, Johannes Welbi, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48, pp. 2071-20088 2016.
Feng Wang. Xiang Xiang, Jian Cheng, and Alan Loddon Yuille. Normface: 1.2 hypersphere embedding for face verification. In Qiong Liu, Rainer Lienhart, Haohong Wang. Sheng-Wo Wein "Kuan- Ta" Chen, Susanne Boll, Yi-Ping Phoebe Chen, Gerald Friedland, Jia Li, and Shuicheng Yan (eds.), ACM MM, Mountain View, CA, USA, October 23-27, 2017, pp. 1041-1049. ACM, 2017.
Shen Wang, Xiaokai Wei, Cícero Nogueira dos Santos, Zhiguo Wang. Ramesh Nallapati, Andrew O. Amold, Bing Xiang, Philip S. Yu, and Isabel F. Cruz. Mixed-curvature multi-relational graph neural network for knowledge graph completion. In Jure Leskovee, Marko Grobelnik, Marc Najork, Jie Tang, and Leila Zia (eds.). WWW 21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pp. 1761-1771. WWW, 2021.
Zhen Wang, Jianwen Zhang, Jianlin Feng. and Zheng Chen. Knowledge graph embedding by translating hyperplanes. In AAAI, pp- 1112-1119, 2014.
Canran Xu and Ruijiang Li. Relation embedding with dihedral group in knowledge graph. In ACL (1), pp. 263-272, 2019.
Chengjin Xu, Mojtaba Nayyeri, Yung- Yu Chen, and Jens Lehmann. Knowledge graph embeddings in geometric algebras. In COLING, pp. $30-544, 2020.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
Tong Yang, Long Sha, and Pengyu Hong. Nage: Non-abelian group embedding for knowledge
graphs. In CIKM, pp. 1735-1742, 2020.
Liang Yao, Chengsheng Mao, and Yuan Luo. KG-BERT: BERT for knowledge graph completion, 2019.
Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei- Ying Ma. Collaborative knowledge base embedding for recommender systems. In KDD, pp. 353-362 2016.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In NewrlPS, pp. 2731-2741, 2019.
Zhanqiu Zhang, Jianyu Cai, and Jie Wang. Duality-induced regularizer for tensor factorization based knowledge graph completion. In NeurIPS, 2020a.
Zhao Zhang, Fuzhen Zhuang, Hengshu Zhu, Zhi-Ping Shi, Hui Xiong, and Qing He. Relational graph neural network with hierarchical attention for knowledge graph completion. In AAAI, pp. 9612-9619, 2020b.
11

---

APPENDIX
A PROOFS
A.1 UNIBI Is BOUNDED
Proposition UniBi is bounded that s(h, r,t) E [-
Proof. By the Cauchy-Schwand inequality and the fact that the spectral norm a generalization of the 1.2 norm, we have the following.
h Rtll s ||h R s
(10)
A.2 PROOF OF THEOREM 1
Proof. On the one hand, if R = I, it is easy to have vh, t E E, h + t that h Thh hTT from the property cosine.
On the other hand, VR E R. R + I. we can always give counterexample. Using singular value decomposition (SVD), we have R UEV where Σ Diag 0 ........ .,] with d; 2 0 and U, V are orthogonal matrices. Since (RR) = 1, we have Fmax = max( =
Besides, notice that since U, V are orthogonal matrices that do not change the norm of vectors, have |h U | t| and use h and f to denote U h and V t for mathematical simplicity.
We consider three scenarios and discuss them separately.
(1) If all singular values of R are equivalent, have Σ I, and have:
sh,, r,
ATT.
(11)
It is easy to notice that the above equation just goes back to the cosine function, and it has the maximum value when h = E and h t. If UVT = I. this contradicts the assumption that R * If UV * then we have h o t, since h (UT) ' -yyt=up UV t. It means Rh < h Rt in this situation.
(2) If not all singular values of R are equivalent and U V, there Di,j E 1,..., n that o; 1 oj. may be assumed that o; > oj. Then we take Vh E É that has h, = (=: e)h, where E (0, g. o, 1). Then we take
fig
k # i.j. k = i,
fx =
(12)
his
k j.
is easy to notice that f
h, f U
U and h + t, then we have
h T Rt = TURU
= h Ef
= =o, + oohhtt + Σ oxhif
(13)
-0,h, + +o, Σ onhi
12

---

similarly, we have
R' = h h'RRUh
Eh
(14)
o + oz + Conhi
kyi.
Then, we use Eq.
minus Eq.
and we have
h Rh h Rt
o,h + o, + Conti - (ashifiy + to,bi -
kpij
-o, h,h,)) + 0, (1) h,h)))
-o,b.(h, h,) - o, h (h; - h,))
=(a,h; h, h,)
(15)
o,,h: o -i jj
c)h:
h - - e)hi,
0j
(o,h, o, to,.h:)
0i + c h
1
jj
<c,hh(( +c)
jj
<0,
which means that h Rh h TR in this case.
(3) If not all singular values of R are equivalent and U * V, there exists E 1,..., n such that Jk Omar since p(R) 1. Then take the following.
h - i = 1, i i= k
(16)
0,
i i k.
should be noted that f é and h * t since + V. Then, we have
h T Rt T U
Tt
(17)
Tk
1.
Since Proposition 1 proves that UniBi bounded by [-1, 1]. we have h RRh h RR,, which means that shh, r, h) > s(h, r, does not always hold.
In summary, we can conclude that UniBi has o t. TRh h TRt iff. R I, which means that UniBi can model identity uniquely in terms of definition 2
A.3 PROOF OF THEBREM 3
Proof. if we have ||e|| 1, ((R) 1. The equation for the entity part obviously holds, and by
Proposition [ we have the following.
Re| s (R))[ee|| p(R.) 1
(18)
similarly, we have c
R
< 1.
Moreover, such a condition will become necessary and sufficient if 32 that either ||e T R = 1 or
|Rē| 1.
13

---

To prove it, if we have le
|eTR R|| < and |Rt] I 1, SVD to any R and get R UEV. Then we denote 5 = (i) where a the vector of singular values and we have Ve, l el| S 1.
If 3i, o 1. we take # j, 1, e, 0 to show that lle all is larger than 1. Therefore, we have Vi, o3 I 1. Moreover, Vi, 0; < 1, we take Vê
|1o a Σ पर o =1
(19)
which also violates p(R) =
|Re||
|o ēl Therefore, there 3k, 0k 1 and have |EVe|
A.4 PROOF OF PROPOSITION 2
Proof. If a relation r is invertible, it means there exists an inverse relation r- that ensure r identity. where is the composition of relations. Consider that identity relation means that no different entities will appear in triple under it, or KGs only contain triples like Ve E EE, (e, identity,
r-1 r-1
Consider complex relation that has multiple tail entities for head entity, that is, 3h, 12 (h, r, (1), (h, (2). In order to remap the entities i and l2 back to h, inverse relation r-1 has to contain triples that (41,r_1 - h), (22,r-1,, r Although r r- could map h to h, r- or, fails to map & t2 back to themselves separately since both (f,, o t1) and (t1, r o (2) are true. Similarly, if relation has multiple heads,
also obtain the above conclusion.
Therefore, all complex relations are inherently non-invertible.
B BACKGROUND OF GROUP AND MONOID
Definition 4 (Jacobson (012 ) A monoid is triple (M, p. 1 in which M is a non-vacuous set, p an associative binary composition (or product) in M, and 1 is an element of M such that p(1,a) p(a, 1) for all E M
Definition 5 (Jacobson (2012) ). group or (G,,,1) is monoid all of whose elements are invertible.
C DISCUSS OF DISTANCE BASED MODELS
We mention that distance based model could model identity uniquely, and here we give its cor- responding proof. Here, we only consider models that can be written in the basic form of s(h, r, f) = Rhh t||. Note that translation is also considered in such form if we take translation linear transformation. Furthermore, the model must ensure that I E I and E R". Other peculiar scenarios are not considered in this discussion.
Theorem 2. A distance based model s(h, r,t) Rh t|| with I E R and E R" can model identity uniquely.
Proof. On the one hand, R = I, it is easy to have
|Rh
t|| < - h h| 0,
(20)
where h *
On the other hand, R + I, if R is not a singular matrix, take t Rh and have
Rh hl R Rh RRh t/|.
(21)
Therefore, prove that listance-based models born uniquely model identity.
14

---

(a) RESCAL w/o reg.
(b) RESCAL Frobenius
(c) RESCAL w/ DURA
Figure Why learning on the scales are ineffective. We test RESCAL with 3 setting a) no regularization, b) use Frobenius norm as regularization, c) use DURA as regularization. We use index rather than name to denote different relations for simplicity. And we notice that non-convergence exists in every case, 2) the better the result, the more the scales converge, 3) Regularization cannot stop the fluctuation scales. (Better view in color, zoom in, note the difference in the vertical coordinates.)
D COMPARISON TO PREVIOUS RESTRICTIONS
Although it is true that entity normalization and of (R) = 1, are common in KGE models, our constraint differs from their approach as follows.
orthogonal matrices, which is special
(1) The constraint for relation based on the spectral radius, i.c., p(R) 1, is first proposed in our work, which is indispensable and irreplaceable to model the identity uniquely without the cost of the performance. If we set R to be orthogonal while keeping the normalization of entities, the performance will drop significantly, e.g.. MRR: 0.488 + 0.471 for UniBi-O(2) on WN18RR.
(2) Only the combination of entity and relation constraints succeeds to model identity uniquely, as shown in Figure 4(c) It suggests that constraints entity and relation should be treated as a whole rather than a combination of two unrelated things.
(3) At first glance, our constraint looks very similar to that of TransR (Lin et al. 2015), but in fact there is big difference. The constraint of TransR is ||h|| S 1, |hM, S 1, and [tM, s and has three differences from ours.
i) For TransR. ||M, S
1 and ||tM||| < is the constraint itself. In contrast, R h < 1 and Rt < 1 is deduction of our constraints ||e]| = 1 and (R) = 1.
ii) TransR does not normalize the entities, and we have shown in Fig. I(a) that normalization is necessary for a bilinear based method to uniquely model identity.
iii) TransR distance based model, and have shown in Appendix C distance based models do not need to consider the problem of identity, thus the proposal of TransR is difference to us.
Therefore, we believe that combination of constraints is novel, since it proposes constraint for the relation and the two parts are deliberately rather than arbitrarily combined.
E INEFFECTIVE LEARNING
Here, we demonstrate that ineffective learning does exist, which means the scale is not only redundant but also harmful. As shown in Fig. 7 we take RESCAL example show this phenomenon. And we notice that 1) non-convergence exists in every case, 2) the better the result, the more the scales converge, and 3) regularization cannot stop the fluctuation of scales.
We believe that these cases illustrate, on the one hand, the positive correlation between the constraint scale and the effect, on the other hand, the mere constraint cannot eliminate fluctuations that may interfere with the model learning. Therefore, we think scale is harmful and learning on is ineffective, and need hard constraint rather than regularization term prevent this completely.
15

---

Alice
Alice
Bill
Alice
Bill
olentty
David
Alice
(a)
(b)
(c)
Figure 8: Why relations non-invertible. (a) A toy example. (2) Truc case. (3) False case.
F FROM GROUP TO MONOID
Since the singular values are less than or equal to 1, some matrices do not have their corresponding inverse elements in I.. Therefore, UniBi violates the definition of group, which requires that each element has its inverse element inside. However, argue that invertible and misidentified by previous work (Yang et al. 2020; Sun et al. 2019 Xu & Li 2019).
relations are inherently
For example, in Fig. [(a) if two relations are inverse elements of each other, their composition must be identity. However, we find the combination of IsParentOf and IsChildOf is not the identity, since
the child of Alice's parent "Alice or David" rather than "Alice itself" as demonstrated in Fig. 8(b)
and Fig. 8(c)
It should be noted that we are saying that these two relations are irrelevant, but rather pointing out that their combination does not strictly fit our definition of identity. Moreover, the fact that they are both non-invertible does not mean that they cannot form the inversion pattern (Sun al. 2019). since definitions of the two concepts are different and do not conflict.
Beyond the specific example, we generalize (ei,r, e2) and (e1, r, e3) (or (e3, e2)), where e,, e2; E E, and el # 2 * eg. Furthermore, we have the following proposition.
all complex relations that appear in both triples
Proposition 2. Vr E R. r is complex relation, then is non-invertible.
Proof. Please refer to Appendix A.4
Since these non-invertible relations extensively present in KGs, the requirement that each element has its inverse element in the set should be abandoned. Thus, rather than group, we think monoid is better structure for relations by their definitions")
G IMPLEMENT DETAILS
G.1 ROTATION MATRICES OF UNIB1
In Section 5
we propose two variants of UniBi, i.e., UniBi-O(2) and UniBi-O(3). Here, we give the rotation matrix SO(k) they used specifically.
P
9
SO(2)
-
SO
v
-u U q
(22)
y
V
p
where x, v.U.P.4 u, IR and x² + 122 1, 2
92
2 1.
G.2 HYPERPARAMETERS
We fix the dimension of all models except RESCAL on WN18RR to 500, while RESCAL on WN18RR is set to 256 following Zhang al. 2020a). We choose Adam (Kingma & Ba 2015) as
Definition 4 and Definition
16

---

Table Hyperparameters found by grid search. À is the regularization coefficient, y is the scaling factor, b is the batch size.
WN18RR
FB15K237
YAG03-10-DR
Model
A
7
b
À
7
b
À
7
b
CP
le-1
100
5e-2
100
5e-3
1000
ComplEx
le-1
100
5e-2
100
le-2
1000
RESCAL
le-1
1000
5e-2
1000
5e-2
1000
UniBi-O(2)
2
20
100
2
25
1000
1.5
30
1000
w/o constraint
le-1
100
5e-2
1000
5e-2
1
1000
UniBi-O(3)
2
15
100
1.5
20
1000
1.5
30
1000
-/o constraint
le-1
100
5e-2
1000
5e-2
1000
the optimizer and fix the learning rate at le 3. We set the maximum epochs to 200 and apply the early stopping strategy.
We set the scaling factor y to 1 for all models except UniBi. And we search from 51 10, 15, 20, 25, 30) for UniBi. For the factor for regularization we search {1, 5e 1, 1e 1,5e 2, le - 5e 1e 3) for all models except UniBi and {0.5, 1,
3} for it. Fur- 2, 2.5, 5. 2, thermore, we do search for X and A2 in Eq. 25 as in the original paper DURA (Zhang et al.. 2020a). we adopt their settings and set ê1 = 0.5, X2 15 for ComplEx (Trouillon et al. 2016) and CP (Hitchoock) 1927). while X A for other cases. The search results are listed on the Tbl. We search for the batch size from {100, 1000].
In addition, we implemented the experiments in PyTorch with single NVIDIA GeForce RTX 1080Ti graphics card. We repeat each experiment five times and take their means and standard deviations.
For the experiments in Section 5.4 set y for UniBi without DURA in Section 5.4 to 10, 15, 25 for WNISRR, F515--237, and YAGO3-10-DR for UniBi, respectively.
H
TIME AND SPACE COMPLEXITY
Since UniBi needs calculate constraints, it spends space and time. Here, compare the time and space consumption UniBi and CP, ComplEx, and RESCAL on FB15k 237, and set the batch size to 1000.
As demonstrated in Fig. (a) and Fig. ( UniBi takes a little more time than CP and ComplEx, and more time to compute the regularization since is more complex. Nevertheless, noticed that UniBi occupies a space similar to that of CP and ComplEx.
In addition, note that in Section 5.3 UniBi outperforms all bilinear based models except RESCAL on WN18RR. And RESCAL needs significantly more time and space than other models. Therefore, it is not as efficient as other models.
In summary, although UniBi takes little longer, it is a good balance between complexity and performance.
In future work, we will consider finding other constraints on the relation instead of the spectral radius.
1 INHERENT REGULARIZATION TERM
Here we find necessary condition of UniBi and then deduce its corresponding Lagrangian function. Theorem 3. UniBi has a necessary condition that ||e]| = 1, |ee| S 1 and | T l $ 1.
Proof. Please refer to the Appendix A.3
17

---

evrrog
wet 102
6200
3000
2000
10-
3000
Lomplex
HBKAA
unisiitt oto
untii
Complex
HBMAA
untalut0
unteliost
(a) Comparison of time.
(b) Comparison of space.
Figure 9: UniBi takes little more time than other models with linear parameters (CP and ComplEx) and significantly efficient than ones with quadratic parameters (RESCAL).
If we ignore the other implicit constraints, the optimization of UniBi can be rewritten in the form of constrained optimization problem.
min
Σ
f(hs, (g,t))
(c)
(23)
8.1. [h, = | | =1
[R] h ~ 1, RRttx 1
where f(h, r,t) is loss function. Furthermore, Eq. corresponds Lagrangian function.
min b.r.
Σ f(h,, Fg. tx) + x
X
(1| -1)
(24)
+ + [R - (x
s.t. Me. 14 11 0.
We notice that if we factors X X1. A\1 and يي μ² Aل2 where X, A1, 0. we achieve the following expression from Eq. 24 by discarding constant terms.
Σ f(h,,T,,te) |Ar ( ||tx]]?) A2 R. h.l [
min b.r.t
(25)
which is equivalent to the optimization of a unconstrained model under DURA (Zhagg et al. 2020a the best regularization term for bilinear based model before. Therefore, can get general version of DURA (DURA-G for simplicity) from Equ. 24
DURA-G A1| 2 + As R h1 + A R
(26)
At first glance, this seems to be nothing more than worthless trick. However, in terms of DURA. DURA-G is nonsense and cannot deduce form its perspective of distance-based models (Please refer to Section 4.3 in the original paper for more details) while making sense in the perspective of Lagrangian function.
Although DURA-G has additional hyperparameter search and can lead better results, do not use this in experiments for three reasons: 1) for a more fair comparison with previous models, 2) the improvement is marginal, and 3) we prefer not to distract the reader from our key ideas.
18

---

CP-Fro
CP-DURA
RESCAL-Fro
RESCAL-DURA
UniBi
الااا
الالالللل
spectral radius
الايا
ا بoر الهبا
0
25
75
100
125
150
175
200
epoch
Figure 10: Bilinear based models learning identity have different scales. (Better zoom in to see the fluctuation of RESCAL-DURA.)
Dataset
#Identity
#Others(Avg.)
WN18RR
40,943
7,894
FB15k-237
14,514
1,148
YAGO3-I0-DR
122,873
20,348
Figure 11: Directly adding identity triples mayTable 4: Statistics of triples of identity and other hurt performance.
relations in benchmark datasets.
J EXTRA EXPERIMENTS OF SCALES
To demonstrate that the phenomenon Fig. [(b) happens, we carry out additional experiments by explicitly adding the identity relation explicitly and monitor its scales in different models. We run all experiments five times and take their means and variants. As shown in Fig. I0 we notice that all models except UniBi has fluctuation the spectral radius of identity, which verifies the phenomenon in Fig. [(b)
K
COMPARISON OF LEARNING AND MODELING IDENTITY
Readers may wonder why not add the identity relation to the training set and take this indirect approach. The reason is that learning identity per does not help the performance on other
19

---

relations, and may be harmful for the overall results as shown in Fig We think the reason is that the triples of identity are too much compared to the ones of other relations as shown in Tbl., and the model negligence in learning these relations.
20


Reviews:
[{"review_id": "sRs3uR0OYC", "reviewer": "Reviewer_52Mc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper targets the special element identity that uniquely corresponds to the relation identity in KGs and finds that bilinear-based models cannot model this uniqueness. This paper studies the required conditions and proposes a solution named Unit Ball Bilinear Model (UniBi). In addition to its theoretical superiority, UniBi is more robust and interpretable. Experiments demonstrate that UniBi models the uniqueness without the cost of performance and verify its robustness and interpretability.", "summary_of_the_review": "Overall, I think this paper do have some merit, but the writing can be improved and the more experiments  can make this paper stronger.", "strength_and_weaknesses": "Strength:\n\n1.This paper focuses on an interesting problem of KGE and finds a new problem for bilinear-based models.\n\n2.Experimental results show that the proposed method can obtain better performance. This work also provides ablation studies with analysis.\n\n3.The proposed approach also provides a theoretical analysis that demonstrates the superiority.\n\nWeaknesses:\n\n1.The introduction and the abstract can be carefully revised, which is hard to follow. Lots of background is missing, which makes the readers very confused.\n\n2.The experimental results show that the improvement is very small; why? And can you explain it? Could you provide some case studies？\n\n3.Some small typos such as  \", Several works also\" >, \"several works also\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dDHmRo41fX", "reviewer": "Reviewer_Nd46", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new approach to learning of graph embeddings. Namely, the theoretical shortcoming of the common bilinear models related to non-uniqueness of identity is addressed. A new theoretically well-grounded model is proposed. Experiments suggest viability fo the described approach. ", "summary_of_the_review": "The main drawback of the paper is that it addresses somewhat 'over researched' topic of link prediction. Yet it uses interesting technically and theoretically grounded approach. Maybe it can be generalised and applied to other less common and innovative task? ", "strength_and_weaknesses": "Strengths:\n\n- The approach is theoretically grounded.\n\n- Experiments are conducted in comparison with multiple strong baselines and show that the method outperforms or perform on par with them. \n\nWeaknesses:\n\n- The improvements are relatively small in absolute values. \n\n- No discussion of applications of the proposed method to other tasks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XsnvtrnhxI", "reviewer": "Reviewer_wvXh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a new bilinear knowledge graph embedding model named UniBi by learning a unique identity element in a group. The main idea is to constrain the norm and spectral radius of entity and relation embeddings, respectively. The authors provide thorough analyses to show that UniBi has theoretical superiority, strong robustness and interpretability, and competitive empirical results.", "summary_of_the_review": "The authors propose an interesting and effective KGE model. The submission is technically sound and easy to read. The experiments are extensive and most of them are convincing. However, I have some concerns about the motivation and some experiments (see Strength And Weaknesses). I am open to raising my score if the authors properly addressed my concerns.", "strength_and_weaknesses": "## Strength\n1. The proposed UniBi is simple but effective.\n2. UniBi has good theoretical properties and the proof seems to be technically sound.\n3. The authors conduct extensive experiments and ablation studies to demonstrate the effectiveness of UniBi.\n4. This paper is well-written and easy to follow.\n5. Detailed experimental settings and codes are provided, so the reproducibility looks nice.\n\n## Weaknesses\n1. **Motivation**   \n    I think the introduction to why we have to model the identity element can be further improved. Although many existing bilinear models cannot learn a unique identity element, is it necessary for a KGE model?  I have no idea about the relationship between this property and the final performance after reading the submission.\n2. **Experiments**    \n    In Section 5.2, the authors claim that results in Figure 3(c) verify the existence of problems shown in Figures 1(a) and 1(b). However, I am wondering that if this result can verify the problem in Figure 1(b), since the imbalance degree eliminates the impact of the scale of the identity matrix.\n3. **Presentation**    \n    It seems that Definitions 1 and 2 are not used in the main text. Can we move them to the appendix?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7zD0bTp3kTx", "reviewer": "Reviewer_VDJN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper examines the properties of identity in bilinear models for knowledge encoding. To satisfy the properties, a modified bilinear model is proposed, in which the entity and relation embeddings are normalized. This form a unit ball. It is shown that the desired properties of unity can be met.\nIn the experiments on 3 datasets for relation prediction, the proposed model outperforms slightly the existing bilinear models and other knowledge graph embedding models.\n", "summary_of_the_review": "The paper examines a specific property - identity. While theoretically interesting, its practical implication is not well explained. The experimental results are thus difficult to interpret. Compared to the literature (which also uses normalization), the novelty is limited, and the importance of the difference with the existing normalization approaches is unclear.", "strength_and_weaknesses": "The analysis of the identity properties is interesting. The proposed solution is simple, but makes sense.\nFrom a theoretical point of view, this investigation is interesting.\nFrom the perspective of experiments, the link between identity and better performance is not made. Despite the ablation studies, it is still difficult to see why satisfying identity would lead to better relation prediction performance. In other words, why the identity constraint would make the embeddings better representations of the entities and relations? It would be necessary to establish this connection for (1) a better understanding of the experimental results; (2) a better motivation for the proposed approach.\nAs stated in the paper (Appendix), normalization has been applied in some previous work. The only difference is that this paper uses a combination of entity normalization and spectral radius normalization for relations. In the demonstration that the existing methods do not satisfy identity, entities are not normalized. Does the demonstration still hold when entities are normalized?\nThe citations are in a form difficult to read. Instead of \"QuatE Zhang et al. (2019)\", it is better to write \"QuatE (Zhang et al. 2019)\".\nThe statements in the paper tend to be formal, which may make it more difficult to understand. \n\nAfter author's rebuttal:\n- In the rebuttal, the authors have explained some of the questions above. In particular, the motivation is better articulated.\nThe authors also mentioned the test about the impact of using the proposed normalization instead of another one. One experimental result is mentioned in appendix D, saying that MRR is reduced from 0.488 to 0.471 on WN18RR if spectral radius is replaced by orthogonal one. I think this should be one of the main results of the paper - showing the practical impact when the proposed normalization is replaced by another one. I would suggest to extend this experimental result to all the datasets, and incorporate them into the main body of the paper.\n- Despite the theoretical advantages, the overall effectiveness reported in Table 2 only shows marginal improvements. In particular, one can see that an existing approach RESCAL can obtain 0.495 in MRR on WN18RR. By comparing this with UniBi, it does not seem that the proper normalization, as proposed in this paper, is the most important (or the only key) factor that affect the effectiveness. \nIn summary, while the motivation is better explained, the experimental evidence about the importance of the proposed normalization is still weak.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject