# Prior Bilinear Based Models for Knowledge Graph Completion

Jiayi Li12 , Ruilin Luo1∗, Jiaqi Sun3, Jing Xiao4, Yujiu Yang1†

1Tsinghua Shenzhen International Graduate School, Tsinghua University
2Baidu Inc.
3Carnegie Mellon University
4Pingan Group
{lijy20<EMAIL_ADDRESS>Equal contribution. $\dagger$
Corresponding author<EMAIL_ADDRESS>
###### Abstract

Bilinear based models are powerful and widely used approaches for Knowledge
Graphs Completion (KGC). Although bilinear based models have achieved
significant advances, these studies mainly concentrate on posterior properties
(based on evidence, e.g. symmetry pattern) while neglecting the prior
properties. In this paper, we find a prior property named "the law of
identity" that cannot be captured by bilinear based models, which hinders them
from comprehensively modeling the characteristics of KGs. To address this
issue, we introduce a solution called Unit Ball Bilinear Model (UniBi). This
model not only achieves theoretical superiority but also offers enhanced
interpretability and performance by minimizing ineffective learning through
minimal constraints. Experiments demonstrate that UniBi models the prior
property and verify its interpretability and performance.

##  1 Introduction

Knowledge Graphs (KGs) store human knowledge in the form of triple $(h,r,t)$,
which represents a relation $r$ between a head entity $h$ and a tail entity
$t$ (Ji et al., 2021). 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 in predicting missing
links to complete them, termed as Knowledge Graph Completion (KGC). As a
common solution, Knowledge Graph Embedding (KGE) completes KGs by learning
low-dimensional representations of entities and relations.

As one typical category of KGE, bilinear based models have achieved great
advances (Trouillon et al., 2016; Hitchcock, 1927; Liu et al., 2017; Nickel et
al., 2011), these work only focus on posterior properties, which are based on
evidence of triples, such as relational patterns Xu and Li (2019); Liu et al.
(2017) and complex relations Gao et al. (2021); Tang et al. (2020). For
example, we treat a relation as symmetric based on the observation that
$(h,r,t)$ and $(t,r,h)$ are co-occurring. Here, we ask does a prior property
exist?

Our answer is the law of identity in Logic Wang (2016), which means that
everything is only identical to itself. In KGs, this rule implies that not
only the representations of entities are different but also the representation
of identity should be unique so that it can be decided without any facts, or a
priori. However, we find that the uniqueness of identity have not been
captured by previous bilinear based model, which prevents them to fully
capture the properties of KGs.

To present the problem more clearly, we first need to introduce some notation.
A model with a score function $s(h,r,t)$ can model the uniqueness of identity
means that $\forall h\neq t,s(h,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(\cdot)$ of bilinear based model is
$\mathbf{h}^{\top}\mathbf{R}\mathbf{t}$, where $\mathbf{h,R,t}$ are the
representations of $h$, $r$, and $t$.

In terms of such uniqueness, bilinear based models have two flaws. On the one
hand, Fig. 1 demonstrates
$\mathbf{e}_{1}^{\top}\mathbf{I}\mathbf{e}_{1}<\mathbf{e}_{1}^{\top}\mathbf{I}\mathbf{e}_{2}$,
which means that the relation matrices per se do not model $identity$
perfectly. On the other hand, Fig. 1 shows even if a matrix, e.g.
$\mathbf{I}$, does. Its scaled one $k\mathbf{I}$ can also model identity and
thus breaks the uniqueness.

Obviously, modeling this property requires both entities and relations to be
restricted, which reduces expressiveness. Yet, we make this cost negligible by
minimizing the constraints, one per entity or relation, while modeling the
desired property. To be specific, we normalize the vectors of the entities and
the spectral radius of the matrices of the relations to $1$. Since the model
captures entities in a unit ball as shown in Fig. 1, we name it Unit Ball
Bilinear Model (UniBi)

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, it shows the relationship between the complexity
of relations and the singular values in the matrices used to represent them.

Experiments verify that UniBi models the law of identity with improvement on
performance and interpretability. Therefore, UniBi is a prior KGE model and a
potential paradigm for bilinear based models.

Figure 1: The flaws of bilinear based models and our solution in terms of
modeling the uniqueness of identity. (a) Identity matrix fails to 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 specific transformations.

##  2 Preliminaries

###  2.1 Background

A Knowledge Graph $\mathcal{K}$ is a set that contains the facts about sets of
entities $\mathcal{E}$ and relations $\mathcal{R}$. Each fact is stored by a
triple $(e_{i},r_{j},e_{k})\in\mathcal{E}\times\mathcal{R}\times\mathcal{E}$
where $e_{i}$ and $r_{j}$ denote the $i$ -th entity and the $j$ -th relation,
respectively.

KGE learns embeddings for each entity and relation via a score function
$s:\mathcal{E}\times\mathcal{R}\times\mathcal{E}\to\mathbb{R}$. To verify the
performance of a KGE method, $\mathcal{K}$ is first divided into
$\mathcal{K}_{train}$ and $\mathcal{K}_{test}$. Then, the method is trained on
$\mathcal{K}_{train}$ to learn the embeddings $\mathbf{e}$ and $\mathbf{r}$
(or $\mathbf{R}$) for each entity $e\in\mathcal{E}$ and relation
$r\in\mathcal{R}$. Finally, the model is expected to give a higher rank if
$(e_{i},h_{j},e_{k})\in\mathcal{K}$ while a lower rank if
$(e_{i},h_{j},e_{k})\notin\mathcal{K}$, for each query $(e_{i},h_{j},?)$ from
$\mathcal{K}_{test}$ and the candidate entity $e_{k}\in\mathcal{E}$.

In addition to the above tail prediction, models are also required to test on
head prediction conversely. We transform it to tail prediction by introducing
reciprocal relations following Lacroix et al. (2018).

In logic, posterior and prior knowledge are distinguished by whether it holds
without evidence. In KGs, we say relational patterns and complex relations are
posterior because we cannot assign them to any of the relations without a
triplet or other information. For example, we need to observe that $(h,r,t)$
and $(t,r,h)$ are co-occurring to decide a relation $r$ has the symmetry
pattern or observe $(h,r,t_{1})$ and $(h,r,t_{2})$ to conclude $r$ is a 1-N
relation.

We claim that the law of identity is a prior property that is true for all
entities in any KGs. To be specific, the law of identity is one of the basic
prior rule in Logic Wang (2016), it means that everything is identical to
itself, or $\forall x,x=x$. And this law corresponds to the definition of
entity111Cambridge Dictionary defines it as ”Something that exists apart from
other things, having its own independent existence”..

###  2.2 Other Notations

We utilize $\hat{\mathbb{E}}$ and $\hat{\mathbb{R}}$ to denote the set of all
possible representations of entities and relations. And we use
$\mathbf{e}\in\hat{\mathbb{E}}$ and $\mathbf{R}\in\hat{\mathbb{R}}$ to denote
the embedding vector of the entity $e$ and the transformation matrix specific
to the relation $\mathbf{R}$. Furthermore, we use $\|\cdot\|$ to denote the L2
norm of the vectors, $\|\cdot\|_{F}$ and $\rho(\cdot)$ to represent the
Frobenius norm and the spectral radius of a matrix.

In this paper, we focus on $n$-dimensional real space $\mathbb{R}^{n}$, which
means $\mathbb{\hat{E}}\subseteq\mathbb{R}^{n}$ and
$\mathbb{\hat{R}}\subseteq\mathbb{R}^{n\times n}$. We also consider real
vector spaces whose vectors are complex $\mathbb{C}^{n}$ or hypercomplex space
$\mathbb{H}^{n}$, since they are isomorphic to $\mathbb{R}^{2n}$ or
$\mathbb{R}^{4n}$.

##  3 Related Work

Previous work mainly handle two kind of posterior properties, namely
relational patterns and complex relations. On the one hand, relational
patterns are the intrinsic properties of relations, and is formally introduced
by ComplEx Trouillon et al. (2016). Base on this, RotatE Sun et al. (2019)
proposes composition pattern, Analogy Liu et al. (2017) introduces analogy
pattern, or commutative pattern, and Dihedral Xu and Li (2019) adds non-
commutative pattern. On the other hand, complex relations are the extrinsic
properties of relation, and is introduced in TransH Wang et al. (2014) to
denote the relations that are not 1-1, or 1-N, N-1, N-N.

Beyond posterior properties, 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 Word2Vec (Mikolov et al., 2013) in
Natural Language Processing proposes the first distance based model, which
uses translation as the linear transformation
$s(h,r,t)=-\|\mathbf{h}+\mathbf{r}-\mathbf{t}\|$. 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 et al., 2019) first introduces rotation as the
transformation. RotE (Chami et al., 2020) further combines translation and
rotation. Some works also introduce hyperbolic spaces (Balazevic et al.,
2019b; Chami et al., 2020; Wang et al., 2021).

In contrast, bilinear based models have score functions in the bilinear form
$s(h,r,t)=\mathbf{h^{\top}Rt}$. RESCAL (Nickel et al., 2011) is the first
bilinear based model whose relation matrices are unconstrained. 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 et al., 2016) further introduces complex
values to model the skew-symmetry pattern. Analogy (Liu et al., 2017) uses
block-diagonal to model the analogical pattern and subsumes DistMult, ComplEx,
and HolE (Nickel et al., 2016). Moreover, QuatE (Zhang et al., 2019) extends
complex values to quaternion and GeomE (Xu et al., 2020) utilizes geometric
algebra to subsume all these models.

In addition, other works using black-box networks (Dettmers et al., 2018;
Nguyen et al., 2018; Yao et al., 2019; Schlichtkrull et al., 2018; Zhang et
al., 2020b) or additional information (An et al., 2018; Ren et al., 2016) are
beyond the scope of this paper.

##  4 Method

In this section, we first discuss prior property, and give the condition for
bilinear based models to model the law of identity in Section 4.1. We then
propose a model named UniBi that satisfies it with least constraint in Section
4.2 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 Prior Property and Identity Relation

In Section 2, we have shown that the law of identity means $\forall x,x=x$. We
consider how entities and identity relation, i.e. $x$ and $=$, are embedded,
and the fact the embedding of identity should be specified a priori, we find
that this is equivalent to the following definition:

######  Definition 1.

A KG model can model the law of identity, which means that the embeddings of
entities are different and the embeddings of the identity relation is unique.

We notice the differences in the embedding of entities are met effortlessly,
yet the uniqueness of identity cannot be modeled by bilinear based models. We
demonstrate two cases in which bilinear based models violate it. On the one
hand, Fig. 1 demonstrates
$\mathbf{e}_{1}^{\top}\mathbf{I}\mathbf{e}_{1}<\mathbf{e}_{1}^{\top}\mathbf{I}\mathbf{e}_{2}$,
which means that the matrix of a relation per se is not guaranteed for
modeling identity. On the other hand, Fig. 1 shows even if a matrix, e.g.,
$\mathbf{I}$, does. Its scaled one $k\mathbf{I}$ where $k>0,k\neq 1$ can also
model identity, which contradicts the quantification of uniqueness. Therefore,
we give a formal definition based on definition 1 as following to investigate
how to modify bilinear based models to model this uniqueness and the law of
identity.

######  Definition 2.

A bilinear model can model the law of identity means:

$\exists!\
\mathbf{R}\in\mathbb{\hat{R}},\forall\mathbf{h,t}\in\mathbb{\hat{E}},\mathbf{h}\neq\mathbf{t},\
\mathbf{h^{\top}Rh}>\mathbf{h^{\top}Rt},$ (1)

where $\exists!$ is the uniqueness quantification.

###  4.2 Unit Ball Bilinear Model

From the above examples, it is easy to see that modeling the law of identity
requires both entities and relations be restricted, which will reduce
expressiveness. To solve this dilemma, we make the cost negligible by
minimizing the constraints, one per entity or relation, while modeling the
desired property.

To be specific, we normalize the vectors of the entities and the spectral
radius of the matrices of the relations to $1$ by setting
$\mathbb{\hat{E}}=\\{\mathbf{e}\,|\,\|\mathbf{e}\|=1,\mathbf{e}\in\mathbb{R}^{n}\\}$
and
$\mathbb{\hat{R}}=\\{\mathbf{R}\,|\,\rho(\mathbf{R})=1,\mathbf{R}\in\mathbb{R}^{n\times
n}\\}$. We name the proposed model as Unit Ball Bilinear Model (UniBi), since
it captures entities in a unit ball as shown in Fig. 1. The score function of
UniBi is222We present in more detail the similarities and differences between
our constraints and those of our predecessors in the Appendix D:

$s(h,r,t)=\mathbf{h^{\top}Rt},\
\|\mathbf{h}\|,\|\mathbf{t}\|=1,\rho(\mathbf{R})=1.$ (2)

We then have the following theorem.

######  Theorem 1.

UniBi is capable to model the law of 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 the law of identity, it
still has a practical disadvantage, since it is difficult to directly
represent all matrices whose spectral raidus are $1$. In addition, it is also
time-consuming to calculate the spectral radius $\rho(\cdot)$ via singular
values decomposition (SVD).

To avoid unnecessary decomposition, we divide a relation matrix into three
parts $\mathbf{R}=\mathbf{R}_{h}\mathbf{\Sigma R}_{t}$ where
$\mathbf{R}_{h},\mathbf{R}_{t}$ are orthogonal matrices and
$\mathbf{\Sigma}=\text{Diag}[\sigma_{1},\dots,\sigma_{n}]$ is a positive
semidefinite diagonal matrix. And we maintain the independence of these three
components during training. Therefore, it becomes simple to obtain matrices
whose spectral radius is 1, that is,
$\frac{\mathbf{R}_{h}\mathbf{\Sigma}\mathbf{R}_{t}}{\sigma_{max}}$. And we
transform the score function Eq. 2 into the following form.

$s(h,r,t)=\frac{\mathbf{h}^{\top}\mathbf{R}_{h}\mathbf{\Sigma
R}_{t}\mathbf{t}}{\sigma_{max}\|\mathbf{h}\|\|\mathbf{t}\|},$ (3)

where $\sigma_{max}$ is the maximum among $\sigma_{i}$.

####  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 a low-dimensional orthogonal
matrix. Specifically, we use $k$-dimensional rotation matrices to build
$\mathbf{R}_{h}$ and $\mathbf{R}_{t}$. Taking $\mathbf{R}_{h}$ as an example
$\mathbf{R}_{h}=\text{Diag}[\mathbf{SO}(k)_{1},\dots,\mathbf{SO}(k)_{\frac{n}{k}}]$,
where $\mathbf{SO}(k)_{i}$ denotes the $i$-th special orthogonal matrix, that
is, the rotation matrix.

The rotation matrix only represents the orthogonal matrices whose determinant
are $1$ and does not represent the ones whose determinant are $-1$. To this
end, we introduce two diagonal sign matrices of $n$-th order
$\mathbf{S}_{h},\mathbf{S}_{t}\in\mathbb{S}$ where

$\mathbb{S}=\\{\mathbf{S}\ |\ \mathbf{S}_{ij}=\begin{cases}\pm 1,\ &if\
i=j,\\\ 0,\ &if\ i\neq j.\end{cases}\\}.$ (4)

Thus, we could rewrite the score function Eq. 3 to

$s(h,r,t)=\frac{\mathbf{h^{\top}R}_{h}{\mathbf{S}_{h}\mathbf{\Sigma}\mathbf{S}_{t}\mathbf{R}_{t}\mathbf{t}}}{\sigma_{max}\|\mathbf{h}\|\|\mathbf{t}\|}.$
(5)

However, the sign matrix $\mathbf{S}_{h}$ and $\mathbf{S}_{t}$ are discrete.
To address this problem, we notice that $\mathbf{S}_{h}$, $\mathbf{\Sigma}$,
$\mathbf{S}_{t}$ can be merged into a matrix $\mathbf{\Xi}$ that

$\mathbf{\Xi}_{ij}=\begin{cases}s_{i}s_{j}\sigma_{i},\ &if\ i=j,\\\ 0\ &if\
i\neq j.\end{cases}$ (6)

where $s_{i}=(\mathbf{S}_{h})_{ii}$, $s_{j}=(\mathbf{S}_{t})_{jj}$,
$i,j=1,\dots,n$ and $\mathbf{\Xi}=\text{Diag}[\xi_{1},\dots,\xi_{n}]$. Thus,
we incorporate the discrete matrices $\mathbf{S}_{h},\mathbf{S}_{t}$ into the
continuous matrix $\mathbf{\Xi}$.

$s(h,r,t)=\frac{\mathbf{h}^{\top}\mathbf{R}_{h}\mathbf{\Xi
R}_{t}\mathbf{t}}{|\xi_{max}|\|\mathbf{h}\|\|\mathbf{t}\|},$ (7)

where $|\xi_{max}|$ is the maximum among $|\xi_{i}|$.

###  4.4 Other benefits from scale normalization

In addition to theoretical superiority, UniBi is more powerful and
interpretable, since modeling the law of identity requires normalizing the
scales that barely contain any useful knowledge. On the one hand, it is
obvious that modeling the law of identity needs to avoid the cases in Fig. 1
and Fig. 1, which requires normalizing the scales of entities and relations.
On the other hand, it is counter-intuitive that the scale information is
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 we multiply these
scores by a positive factor:

$\displaystyle
s^{\prime}(h,r,t)=(k_{e}\mathbf{h})^{\top}(k_{r}\mathbf{R})(k_{e}\mathbf{t})=k_{e}^{2}k_{r}(\mathbf{h^{\top}Rt})=k_{e}^{2}k_{r}\cdot
s(h,r,t),$ (8)

where $k_{e},k_{r}>0$. Therefore, we treat learning on scales as
ineffective333Further discussion in Appendix E..

####  4.4.1 Performance

As illustrated in Fig. 11, UniBi has better performance, since it prevents
ineffective learning with the least constraints. On the one hand, by
preventing ineffective learning, UniBi focuses more on learning useful
knowledge, which helps improve performance. On the other hand, it pays a
negligible cost of expressiveness, since it adds only one equality constraint
to each entity or relation, which is ignorable when the dimension $n$ is high.

In other words, although our scale normalization is a double-edged sword, its
negative effect is negligible, and thus leads to a better performance. It
should be noticed that the loss on expressiveness may outweighs the gain on
learning, if 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 $n$ equality constraints.

####  4.4.2 Interpretability

Figure 2: Complexity and contraction. (a) A toy example to show how to
calculate complexity. (2) the aggregation corresponds to the singular values
less than 1.

In addition to performance, scale normalization also helps us to understand
complex relations. Complex relations are defined by whither hptr (head per
tail of a relation) or tphr (tail per head of a relation) is higher than a
special threshold 1.5 (Wang et al., 2014). Therefore, all relations are
divided into 4 types, i.e. 1-1, 1-N, N-1, and N-N. However, we think this
division is too coarse-grained and suggest a fine-grained continuing metric
complexity instead. To better demonstrate this idea, we gave an example in
Fig. 2 and the definition of complexity as follows.

######  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 et al., 2015), which implies that the
higher the complexity of a relation, the stronger its aggregation effect, and
vice versa.

We note that this aggregation effect can be well characterized by the relative
ratio, or imbalance degree, of singular values of the matrices of relations.
For any relation matrix $\mathbf{R}=\mathbf{U\Sigma V^{\top}}$, both
$\mathbf{U}$ and $\mathbf{V}$ are isometry, and only the singular values of
the scaling matrix $\mathbf{\Sigma}$ contribute to the aggregation. Moreover,
the singular values of UniBi are less than or equal to 1444We discuss this
characteristic in more depth from the perspective of group in Appendix F.,
since the spectral radius, i.e. the maximum singular value, are normalized.
This shows a promising correspondence between the singular values of our model
and the aggregation and further to the complexity, as demonstrated in Fig. 2.
Therefore, we could use singular values to represent the complexity of
relations, which increases the interpretability of UniBi.

It is worth mentioning that this interpretabity can be transferred to other
bilinear based models if they normalize the spectral radius of their relation
matrix as UniBi does.

##  5 Experiment

In this section, we give the experiment settings in Section 5.1. We verify
that UniBi is capable to model the law of identity, while previous bilinear
based models are not in Section 5.2. UniBi is comparable to previous SOTA
bilinear models in the link prediction task, as shown in Section 5.3. In
addition, we demonstrate the robustness of UniBi in Section 5.4 and the
interpretability about complexity in Section 5.5.

Table 1: Statistics of the benchmark datasets. Dataset | $|\mathcal{E}|$ | $|\mathcal{R}|$ | Training | Validation | Test
---|---|---|---|---|---
WN18RR | 40,943 | 11 | 86,835 | 3,034 | 3,134
FB15k-237 | 14,541 | 237 | 272,115 | 17,535 | 20,466
YAGO3-10-DR | 122,873 | 36 | 732,556 | 3,390 | 3,359

###  5.1 Experiment Settings

Dataset We evaluate models on three commonly used benchmarks, i.e. WN18RR
(Dettmers et al., 2018), FB15k-237 (Toutanova and Chen, 2015) and YAGO3-10-DR
(Akrami et al., 2020). They are proposed by removing the reciprocal triples
that cause data leakage in WN18, FB15K and YAGO3-10 respectively. Their
statistics are listed in Tbl. 1.

Evaluation metrics We use Mean Reciprocal Rank (MRR) and Hits@k (k = 1, 3, 10)
as the evaluation metrics. 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 $2\times 2$ and
$4\times 4$ matrices, respectively. For more details, see the Appendix G.1.

UniBi is compared with these bilinear models: RESCAL (Nickel et al., 2011), CP
(Hitchcock, 1927), ComplEx (Trouillon et al., 2016), and QuatE (Zhang et al.,
2019). In addition, it also compared to other models: RotatE (Sun et al.,
2019), MurE (Balazevic et al., 2019b) and RotE (Chami et al., 2020), Turcker
(Balazevic et al., 2019a) and ConvE (Dettmers et al., 2018), PairRE Chao et
al. (2021), TripleRE.

Optimization We adopt the reciprocal setting (Lacroix et al., 2018), which
creates a reciprocal relation $r^{\prime}$ for each $r$ and a new triple
$(e_{k},r^{\prime}_{j},e_{i})$ for each $(e_{i},r_{j},e_{k})\in\mathcal{K}$.
Instead of using Cross Entropy directly (Lacroix et al., 2018; Zhang et al.,
2020a, 2019), we add an extra scalar $\gamma>0$ before softmax function. Since
UniBi is bounded, it brings an upper bound to loss that makes the model
difficult to optimize as discussed by Wang et al. (2017).

$L=-\sum_{(h,r,t)\in\mathcal{K}_{train}}\log\left({\frac{\exp(\gamma\cdot
s(h,r,t))}{\sum_{t^{\prime}\in\mathcal{E}}{\exp(\gamma\cdot
s(h,r,t^{\prime}))}}}\right)+\lambda\cdot Reg(h,r,t),$ (9)

where $Reg(h,r,t)$ is the regularization term and $\lambda>0$ is its factor.
Specifically, we only take $Reg(h,r,t)$ as DURA (Zhang et al., 2020a) in
experiments, since it significantly outperforms other regularization terms. In
addition, $\gamma$ is set to $1$ for previous methods and greater than $1$ for
UniBi. And we set the dimension $n$ to $500$. For other details on the
implementation, see Appendix G.2.

###  5.2 Modeling Prior Property

In this part, we verify that 1) UniBi is capable to model the law of identity
while previous models fail, and 2) both constraints on the embedding of
entities and relations are 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, since entities are different,
modeling the law means model the uniqueness of identity, which requires the
matrix of identity relation is supposed to converge to the identity matrix
$\mathbf{I}$ or a scaled one. To evaluate it, we introduce a new metric
imbalance degree $\Delta=(\sum_{i}\frac{\sigma_{i}}{\sigma_{max}}-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-237. Besides, we
also apply DURA (Zhang et al., 2020a) to models to explore whether these
methods are able to model the law of identity under extra regularization. As
demonstrated in Fig. 3(a), the imbalance degree $\Delta$ 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 to 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
$\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ to model it independently. As shown in
Fig. 3(b), the error between $\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ also
converges to $0$, which means that they all converge to $\mathbf{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 is not enough to model
the uniqueness of identity, as illustrated in Fig. 3(c). And this verify the
existence of problems shown in Fig. 1 and Fig. 1.

###  5.3 Main Results

(a) UniBi V.S. others.

(b) Error between different matrices converges.

(c) Abaltion of constrains.

Figure 3: UniBi is capable to uniquely model identity. (a) the imbalance
degree ($\Delta$) of UniBi converges to $0$ while others diverge. (b) The
errors between different matrices modeling identity converge to $0$ on
different datasets. (c) Both entity constrain (EC) and relation constrain (RC)
are indispensable for UniBi to model identity. Table 2: Evaluation results on
WN18RR, FB15k-237 and YAGO3-10-DR datasets. We reimplement RotE, CP, RESCAL,
ComplEx with $n=500$ and denoted by †, while we take results on WN18RR and
FB15k-237 from the origin papers and YAGO3-10-DR from Akrami et al. (2020).
Best results are in bold while the seconds are underlined.

| WN18RR | FB15K-237 | YAGO3-10-DR
---|---|---|---
Model | MRR | Hits@1 | Hits@10 | MRR | Hits@1 | Hits@10 | MRR | Hits@1 | Hits@10
DistMult | 0.43 | 0.39 | 0.49 | 0.241 | 0.155 | 0.419 | 0.192 | 0.133 | 0.307
ConvE | 0.43 | 0.40 | 0.52 | 0.325 | 0.237 | 0.501 | 0.204 | 0.147 | 0.315
TuckER | 0.470 | 0.443 | 0.526 | 0.358 | 0.266 | 0.544 | 0.207 | 0.148 | 0.320
QuatE | 0.488 | 0.438 | 0.582 | 0.348 | 0.248 | 0.550 | - | - | -
RotatE | 0.476 | 0.428 | 0.571 | 0.338 | 0.241 | 0.533 | 0.214 | 0.153 | 0.332
MurP | 0.481 | 0.440 | 0.566 | 0.335 | 0.243 | 0.518 | - | - | -
RotE | 0.494 | 0.446 | 0.585 | 0.346 | 0.251 | 0.538 | - | - | -
PairRe | - | - | - | 0.351 | 0.256 | 0.544 | - | - | -
TripleRE | - | - | - | 0.351 | 0.251 | 0.552 | - | - | -
CP† | $0.457_{\pm 0.001}$ | $0.414_{\pm 0.002}$ | $0.549_{\pm 0.003}$ | $0.361_{\pm 0.001}$ | $0.266_{\pm 0.001}$ | $0.551_{\pm 0.001}$ | $0.241_{\pm 0.001}$ | $0.175_{\pm 0.002}$ | $0.370_{\pm 0.003}$
ComplEx† | $0.487_{\pm 0.002}$ | $0.445_{\pm 0.001}$ | $\underline{0.571}_{\pm 0.002}$ | $0.363_{\pm 0.001}$ | $0.269_{\pm 0.001}$ | $0.552_{\pm 0.002}$ | $0.238_{\pm 0.001}$ | $0.174_{\pm 0.002}$ | $0.360_{\pm 0.004}$
RESCAL† | $\textbf{0.495}_{\pm 0.001}$ | $\textbf{0.452}_{\pm 0.002}$ | $0.575_{\pm 0.002}$ | $0.364_{\pm 0.003}$ | $\underline{0.272}_{\pm 0.003}$ | $0.547_{\pm 0.002}$ | $0.233_{\pm 0.003}$ | $0.168_{\pm 0.004}$ | $0.360_{\pm 0.004}$
UniBi-O(2) | $0.487_{\pm 0.002}$ | $0.46_{\pm 0.002}$ | $0.566_{\pm 0.002}$ | $\textbf{0.370}_{\pm 0.001}$ | $\textbf{0.274}_{\pm 0.001}$ | $\textbf{0.561}_{\pm 0.002}$ | $\textbf{0.247}_{\pm 0.001}$ | $\underline{0.179}_{\pm 0.002}$ | $\underline{0.376}_{\pm 0.002}$
\- w/o constraint | $0.488_{\pm 0.001}$ | $\underline{0.447}_{\pm 0.002}$ | $0.568_{\pm 0.003}$ | $0.361_{\pm 0.001}$ | $0.267_{\pm 0.001}$ | $0.550_{\pm 0.001}$ | $0.242_{\pm 0.001}$ | $0.176_{\pm 0.001}$ | $0.372_{\pm 0.002}$
UniBi-O(3) | $0.492_{\pm 0.001}$ | $\textbf{0.452}_{\pm 0.001}$ | $\underline{0.571}_{\pm 0.001}$ | $\underline{0.369}_{\pm 0.001}$ | $\textbf{0.274}_{\pm 0.001}$ | $\underline{0.561}_{\pm 0.001}$ | $\underline{0.246}_{\pm 0.001}$ | $\textbf{0.180}_{\pm 0.001}$ | $\textbf{ 0.377}_{\pm 0.001}$
\- w/o constraint | $0.488_{\pm 0.001}$ | $0.446_{\pm 0.002}$ | $0.567_{\pm 0.003}$ | $0.361_{\pm 0.001}$ | $0.265_{\pm 0.001}$ | $0.550_{\pm 0.001}$ | $0.241_{\pm 0.001}$ | $0.175_{\pm 0.002}$ | $0.370_{\pm 0.003}$

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 (Hitchcock, 1927), ComplEx (Trouillon et 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 on YAGO3-10-DR, so we reimplement them in this
paper. In addition, we further remove the constraint of UniBi-O(n) as
ablations to eliminate the influence of other factors.

In Tbl. 2, UniBi achieves comparable results to previous bilinear based models
and the unconstrained versions. UniBi is only slightly and justifiably below
RESCAL on WN18RR, since RESCAL needs require much more time and
space555Detailed in Appendix H..

###  5.4 UniBi prevents ineffective learning

(a) Ablation of regularization.

(b) Ablation of constrains.

Figure 4: UniBi benefits from preventing ineffective learning. (a) UniBi less
relies on regularization and other models are not. (b) Neither entity
constraint (EC) nor relation constrain (RC) alone stops the sliding of
performance.

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 are implemented on WN18RR.

On the one hand, UniBi decreases slightly, while others decrease significantly
when the regularization term is removed, as demonstrated in Fig. 4(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 its ablation models on
validation set as epoch grows in Fig. 4(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 improving performance of UniBi.

###  5.5 Correlation to Complexity

To verify the statement in Section 4.4.2, we study the connection between
singular values and the complexity of each relation on three benchmarks, where
complexity is calculated following definition 3. Furthermore, we measure the
singular values of a relation by the imbalance degree $\Delta$. To
differentiate $\Delta$ of a relation $r$ and its reciprocal relation
$r^{\prime}$, we use $\Delta_{r}$ and $\Delta_{r^{\prime}}$ to denote them.

As demonstrated in Fig. 5, we find that singular values are highly correlated
with the complexity of a relation. Furthermore, we notice that $\Delta_{r}$
and $\Delta_{r^{\prime}}$ are very close even if a relation is unbalanced (1-N
or N-1), which shows that complexity is handled by aggregation regardless of
direction.

(a) WN18RR

(b) FB15k-237

(c) YAGO3-10-DR

Figure 5: The imbalance degree ($\Delta$) and complexity ($\\#$ hptr + $\\#$
tphr) of relations in WN18RR, FB15k-237 and YAGO3-10-DR respectively. Two
metric are highly correlated and the imbalance of a relation ($\Delta_{r}$)
and the imbalance of its reciprocal one ($\Delta_{r^{\prime}}$) are very
close.

##  6 Conclusion

In this paper, we propose a new perspective, prior property, on analysis and
modeling KGs beyond posterior properties. We discover a prior property named
the law of identity. Moreover, We notice that bilinear based models fail to
model this property and propose a proved solution named UniBi. Specifically,
UniBi applies well-designed normalization on the embedding of entities and
relations with minimal constraints.

Furthermore, UniBi gains other advantages through the normalization. On the
one hand, the 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.

In summary, we believe the question of prior property and the paradigm of
UniBi can provide interesting and useful directions for the studies of
bilinear based models.

###  6.1 Retrieval of style files

The style files for NeurIPS and other conference information are available on
the World Wide Web at

http://www.neurips.cc/

The file `neurips_2022.pdf` contains these instructions and illustrates the
various formatting requirements your NeurIPS paper must satisfy.

The only supported style file for NeurIPS 2022 is `neurips_2022.sty`,
rewritten for LaTeX 2ε. Previous style files for LaTeX 2.09, Microsoft Word,
and RTF are no longer supported!

The LaTeX style file contains three optional arguments: `final`, which creates
a camera-ready copy, `preprint`, which creates a preprint for submission to,
e.g., arXiv, and `nonatbib`, which will not load the `natbib` package for you
in case of package clash.

##### Preprint option

If you wish to post a preprint of your work online, e.g., on arXiv, using the
NeurIPS style, please use the `preprint` option. This will create a
nonanonymized version of your work with the text “Preprint. Work in progress.”
in the footer. This version may be distributed as you see fit. Please do not
use the `final` option, which should only be used for papers accepted to
NeurIPS.

At submission time, please omit the `final` and `preprint` options. This will
anonymize your submission and add line numbers to aid review. Please do _not_
refer to these line numbers in your paper as they will be removed during
generation of camera-ready copies.

The file `neurips_2022.tex` may be used as a “shell” for writing your paper.
All you have to do is replace the author, title, abstract, and text of the
paper with your own.

## References

  * Akrami et al. [2020] 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_ , pages 1995–2010. ACM, 2020.
  * An et al. [2018] Bo An, Bo Chen, Xianpei Han, and Le Sun.  Accurate text-enhanced knowledge graph representation learning.  In _NAACL-HLT_ , pages 745–755, 2018.
  * Balazevic et al. [2019a] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  Tucker: Tensor factorization for knowledge graph completion.  In _EMNLP/IJCNLP (1)_ , pages 5184–5193, 2019a.
  * Balazevic et al. [2019b] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  Multi-relational poincaré graph embeddings.  In _NeurIPS_ , pages 4465–4475, 2019b.
  * Bordes et al. [2013] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  In _NeurIPS_ , pages 2787–2795, 2013.
  * Chami et al. [2020] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré.  Low-dimensional hyperbolic knowledge graph embeddings.  In _ACL_ , pages 6901–6914, 2020.
  * Chao et al. [2021] Linlin Chao, Jianshan He, Taifeng Wang, and Wei Chu.  Pairre: Knowledge graph embeddings via paired relation vectors.  In _ACL/IJCNLP(1)_ , pages 4360–4369, 2021.
  * Dettmers et al. [2018] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel.  Convolutional 2d knowledge graph embeddings.  In _AAAI_ , pages 1811–1818, 2018.
  * Gao et al. [2021] Haipeng Gao, Kun Yang, Yuxue Yang, Rufai Yusuf Zakari, Jim Wilson Owusu, and Ke Qin.  Quatde: Dynamic quaternion embedding for knowledge graph completion, 2021\.
  * He et al. [2017] He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang.  Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings.  In _ACL_ , pages 1766–1776. Association for Computational Linguistics, 2017.
  * Hitchcock [1927] Frank L Hitchcock.  The expression of a tensor or a polyadic as a sum of products.  _Journal of Mathematics and Physics_ , 6(1-4):164–189, 1927.
  * Jacobson [2012] Nathan Jacobson.  _Basic algebra I_.  Courier Corporation, 2012.
  * Ji et al. [2021] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu.  A survey on knowledge graphs: Representation, acquisition, and applications.  _IEEE Trans Neural Netw Learn Syst._ , pages 1–21, 2021.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Lacroix et al. [2018] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski.  Canonical tensor decomposition for knowledge base completion.  In _ICML_ , volume 80, pages 2869–2878, 2018.
  * Lin et al. [2015] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu.  Learning entity and relation embeddings for knowledge graph completion.  In _AAAI_ , pages 2181–2187, 2015.
  * Liu et al. [2017] Hanxiao Liu, Yuexin Wu, and Yiming Yang.  Analogical inference for multi-relational embeddings.  In _ICML_ , volume 70, pages 2168–2178, 2017.
  * Mikolov et al. [2013] Tomás Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean.  Distributed representations of words and phrases and their compositionality.  In _NeurIPS_ , pages 3111–3119, 2013.
  * Mohammed et al. [2018] Salman Mohammed, Peng Shi, and Jimmy Lin.  Strong baselines for simple question answering over knowledge graphs with and without neural networks.  In _NAACL-HLT (2)_ , pages 291–296, 2018.
  * Nguyen et al. [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)_ , pages 327–333, 2018.
  * Nickel et al. [2011] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel.  A three-way model for collective learning on multi-relational data.  In _ICML_ , pages 809–816, 2011.
  * Nickel et al. [2016] Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio.  Holographic embeddings of knowledge graphs.  In _AAAI_ , pages 1955–1961, 2016.
  * Ren et al. [2016] 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 _SIGKDD_ , pages 1825–1834. ACM, 2016.
  * Schlichtkrull et al. [2018] 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, pages 593–607, 2018.
  * Sun et al. [2019] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _ICLR_ , 2019.
  * Tang et al. [2020] Yun Tang, Jing Huang, Guangtao Wang, Xiaodong He, and Bowen Zhou.  Orthogonal relation transforms with graph context modeling for knowledge graph embedding.  In _ACL_ , pages 2713–2722, 2020.
  * Toutanova and Chen [2015] 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 Compositionality_ , pages 57–66, Beijing, China, July 2015.
  * Trouillon et al. [2016] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In _ICML_ , volume 48, pages 2071–2080, 2016.
  * Wang et al. [2017] Feng Wang, Xiang Xiang, Jian Cheng, and Alan Loddon Yuille.  Normface: L${}_{\mbox{2}}$ hypersphere embedding for face verification.  In _ACM MM_ , pages 1041–1049. ACM, 2017.
  * Wang [2016] Hao Wang.  _From Mathematics to Philosophy (Routledge Revivals)_.  Routledge, 2016.
  * Wang et al. [2021] Shen Wang, Xiaokai Wei, Cícero Nogueira dos Santos, Zhiguo Wang, Ramesh Nallapati, Andrew O. Arnold, Bing Xiang, Philip S. Yu, and Isabel F. Cruz.  Mixed-curvature multi-relational graph neural network for knowledge graph completion.  In _WWW_ , pages 1761–1771, 2021.
  * Wang et al. [2014] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen.  Knowledge graph embedding by translating on hyperplanes.  In _AAAI_ , pages 1112–1119, 2014.
  * Xu and Li [2019] Canran Xu and Ruijiang Li.  Relation embedding with dihedral group in knowledge graph.  In _ACL (1)_ , pages 263–272, 2019.
  * Xu et al. [2020] Chengjin Xu, Mojtaba Nayyeri, Yung-Yu Chen, and Jens Lehmann.  Knowledge graph embeddings in geometric algebras.  In _COLING_ , pages 530–544, 2020.
  * Yang et al. [2015] 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.
  * Yang et al. [2020] Tong Yang, Long Sha, and Pengyu Hong.  Nage: Non-abelian group embedding for knowledge graphs.  In _CIKM_ , pages 1735–1742, 2020.
  * Yao et al. [2019] Liang Yao, Chengsheng Mao, and Yuan Luo.  KG-BERT: BERT for knowledge graph completion, 2019.
  * Zhang et al. [2016] Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei-Ying Ma.  Collaborative knowledge base embedding for recommender systems.  In _KDD_ , pages 353–362, 2016.
  * Zhang et al. [2019] Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu.  Quaternion knowledge graph embeddings.  In _NeurIPS_ , pages 2731–2741, 2019.
  * Zhang et al. [2020a] Zhanqiu Zhang, Jianyu Cai, and Jie Wang.  Duality-induced regularizer for tensor factorization based knowledge graph completion.  In _NeurIPS_ , 2020a.
  * Zhang et al. [2020b] 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_ , pages 9612–9619, 2020b.

## Appendix

##  Appendix A Proofs

###  A.1 UniBi Is Bounded

######  Proposition 1.

UniBi is bounded that $s(h,r,t)\in\left[-1,1\right]$.

###### Proof.

By the Cauchy-Schwarz inequality and the fact that for a vector L2 norm is
equivalent to spectral norm, we have the following.

$\|\mathbf{h^{\top}Rt}\|\leq\|\mathbf{h^{\top}R}\|\|\mathbf{t}\|\leq\rho(\mathbf{R})\|\mathbf{h}\|\|\mathbf{t}\|=1.$
(10)

∎

###  A.2 Proof of Theorem 1

###### Proof.

On the one hand, if $\mathbf{R}=\mathbf{I}$, it is easy to have
$\forall\mathbf{h,t}\in\mathbb{\hat{E}},\mathbf{h}\neq\mathbf{t}$ that
$\mathbf{h^{\top}Ih}>\mathbf{h^{\top}It}$ from the property of cosine.

On the other hand,
$\forall\mathbf{R}\in\mathbb{\hat{R}},\mathbf{R}\neq\mathbf{I}$, we can always
give a counterexample. Using singular value decomposition (SVD), we have
$\mathbf{R}=\mathbf{U}\mathbf{\Sigma}\mathbf{V^{\top}}$, where
$\Sigma=\text{Diag}[\sigma_{1},\dots,\sigma_{n}]$ with $\sigma_{i}\geq 0$ and
$U,V$ are orthogonal matrices. Since $\rho(\mathbf{R})=1$, we have
$\sigma_{max}=\max(\sigma_{i})$ = 1.

Besides, we notice that since $U,V$ are orthogonal matrices that do not change
the norm of vectors, we have $\|\mathbf{h^{\top}U}\|=\|\mathbf{V^{\top}t}\|=1$
and use $\mathbf{\hat{h}}$ and $\mathbf{\hat{t}}$ to denote
$\mathbf{U^{\top}h}$ and $\mathbf{V^{\top}t}$ for mathematical simplicity. We
consider three scenarios and discuss them separately.

(1) If all singular values of $\mathbf{R}$ are equivalent, we have
$\mathbf{\Sigma}=\mathbf{I}$, and we have:

$s(h,r,t)=\mathbf{h^{\top}U\Sigma
V^{\top}t}=\mathbf{\hat{h}^{\top}I\hat{t}}=\mathbf{\hat{h}^{\top}\hat{t}}.$
(11)

It is easy to notice that the above equation just goes back to the cosine
function, and it has the maximum value when
$\mathbf{\hat{h}}=\mathbf{\hat{t}}$ and
$\mathbf{U^{\top}h}=\mathbf{V^{\top}t}$. If $\mathbf{UV^{\top}}=\mathbf{I}$,
this contradicts the assumption that $\mathbf{R}\neq\mathbf{I}$. If
$\mathbf{UV^{\top}}\neq\mathbf{I}$, then we have $\mathbf{h}\neq\mathbf{t}$,
since
$\mathbf{h}=\mathbf{(U^{\top})}^{-1}\mathbf{V^{\top}t}=\mathbf{UV^{\top}t}$.
It means $\mathbf{h^{\top}Rh}<\mathbf{h^{\top}Rt}$ in this situation.

(2) If not all singular values of $\mathbf{R}$ are equivalent and
$\mathbf{U}=\mathbf{V}$, there $\exists i,j\in 1,\dots,n$ that
$\sigma_{i}\neq\sigma_{j}$. It may be assumed that $\sigma_{i}>\sigma_{j}$.
Then we take $\forall\mathbf{h}\in\mathbb{\hat{E}}$ that has
$\mathbf{\hat{h}}_{j}=(\frac{\sigma_{i}}{\sigma_{j}}-\epsilon)\mathbf{\hat{h}}_{i}$
where $\epsilon\in(0,\frac{\sigma_{i}}{\sigma_{j}}-1)$. Then we take

$\mathbf{\hat{t}}_{k}=\begin{cases}\mathbf{\hat{h}}_{k},\ &k\neq i,j,\\\
\mathbf{\hat{h}}_{j},\ &k=i,\\\ \mathbf{\hat{h}}_{t},\ &k=j.\end{cases}$ (12)

It is easy to notice that
$\mathbf{\hat{h}}=\mathbf{U^{\top}h},\mathbf{\hat{t}}=\mathbf{U^{\top}t}$ and
$\mathbf{h}\neq\mathbf{t}$, then we have

$\displaystyle\mathbf{h^{\top}Rt}$
$\displaystyle=\mathbf{h^{\top}URU^{\top}t}$ (13)
$\displaystyle=\mathbf{\hat{h}^{\top}\Sigma\hat{t}}$
$\displaystyle=\sigma_{i}\mathbf{\hat{h}}_{i}\mathbf{\hat{t}}_{i}+\sigma_{j}\mathbf{\hat{h}}_{j}\mathbf{\hat{t}}_{j}+\sum_{k\neq
i,j}\sigma_{k}\mathbf{\hat{h}}_{k}\mathbf{\hat{t}}_{k}$
$\displaystyle=\sigma_{i}\mathbf{\hat{h}}_{i}\mathbf{\hat{h}}_{j}+\sigma_{j}\mathbf{\hat{h}}_{j}\mathbf{\hat{h}}_{i}+\sum_{k\neq
i,j}\sigma_{k}\mathbf{\hat{h}}_{k}^{2},$

similarly, we have

$\displaystyle\mathbf{h^{\top}Rh}$
$\displaystyle=\mathbf{h^{\top}URU^{\top}h}$ (14)
$\displaystyle=\mathbf{\hat{h}^{\top}\Sigma\hat{h}}$
$\displaystyle=\sigma_{i}\mathbf{\hat{h}}_{i}^{2}+\sigma_{j}\mathbf{\hat{h}}_{j}^{2}+\sum_{k\neq
i,j}\sigma_{k}\mathbf{\hat{h}}_{k}^{2}.$

Then, we use Eq. 14 minus Eq. 13, and we have

$\displaystyle\mathbf{h^{\top}Rh}-\mathbf{h^{\top}Rt}$ (15) $\displaystyle=$
$\displaystyle\left(\sigma_{i}\mathbf{\hat{h}}_{i}^{2}+\sigma_{j}\mathbf{\hat{h}}_{j}^{2}+\sum_{k\neq
i,j}\sigma_{k}\mathbf{\hat{h}}_{k}^{2}\right)-\left(\sigma_{i}\mathbf{\hat{h}}_{i}\mathbf{\hat{h}}_{j}+\sigma_{j}\mathbf{\hat{h}}_{j}\mathbf{\hat{h}}_{i}+\sum_{k\neq
i,j}\sigma_{k}\mathbf{\hat{h}}_{k}^{2}\right)$ $\displaystyle=$
$\displaystyle\sigma_{i}(\mathbf{\hat{h}}_{i}^{2}-\mathbf{\hat{h}}_{i}\mathbf{\hat{h}}_{j})+\sigma_{j}(\mathbf{\hat{h}}_{j}^{2}-\mathbf{\hat{h}}_{i}\mathbf{\hat{h}}_{j})$
$\displaystyle=$
$\displaystyle\sigma_{i}\mathbf{\hat{h}}_{i}(\mathbf{\hat{h}}_{i}-\mathbf{\hat{h}}_{j})-\sigma_{j}\mathbf{\hat{h}}_{j}(\mathbf{\hat{h}}_{i}-\mathbf{\hat{h}}_{j})$
$\displaystyle=$
$\displaystyle(\sigma_{i}\mathbf{\hat{h}}_{i}-\sigma_{j}\mathbf{\hat{h}}_{j})(\mathbf{\hat{h}}_{i}-\mathbf{\hat{h}}_{j})$
$\displaystyle=$
$\displaystyle\left(\sigma_{i}\mathbf{\hat{h}}_{i}-\sigma_{j}(\frac{\sigma_{i}}{\sigma_{j}}-\epsilon)\mathbf{\hat{h}}_{i}\right)\left(\mathbf{\hat{h}}_{i}-(\frac{\sigma_{i}}{\sigma_{j}}-\epsilon)\mathbf{\hat{h}}_{i}\right)$
$\displaystyle=$
$\displaystyle\left(\sigma_{i}\mathbf{\hat{h}}_{i}-\sigma_{i}\mathbf{\hat{h}}_{i}+\epsilon\sigma_{j}\mathbf{\hat{h}}_{i}\right)\left(1-\frac{\sigma_{i}}{\sigma_{j}}+\epsilon\right)\mathbf{\hat{h}}_{i}$
$\displaystyle=$
$\displaystyle\epsilon\sigma_{j}\mathbf{\hat{h}}_{i}^{2}(1-\frac{\sigma_{i}}{\sigma_{j}}+\epsilon)$
$\displaystyle<$ $\displaystyle 0,$

which means that $\mathbf{h^{\top}Rh}<\mathbf{h^{\top}Rt}$ in this case.

(3) If not all singular values of $\mathbf{R}$ are equivalent and
$\mathbf{U}\neq\mathbf{V}$, there exists $k\in 1,\dots,n$ such that
$\sigma_{k}=\sigma_{max}=1$ since $\rho(\mathbf{R})=1$. Then we take the
following.

$\mathbf{\hat{h}}_{i}=\mathbf{\hat{t}}_{i}=\begin{cases}1,\ &i=k,\\\ 0,\
&i\neq k.\end{cases}$ (16)

It should be noted that $\mathbf{\hat{h}}=\mathbf{\hat{t}}$ and
$\mathbf{h}\neq\mathbf{t}$ since $\mathbf{U}\neq\mathbf{V}$. Then, we have

$\displaystyle\mathbf{h^{\top}Rt}$ $\displaystyle=\mathbf{h^{\top}U\Sigma
V^{\top}t}$ (17) $\displaystyle=\mathbf{\hat{h}^{\top}\Sigma\hat{t}}$
$\displaystyle=\sigma_{k}$ $\displaystyle=1.$

Since Proposition 1 proves that UniBi is bounded by $[-1,1]$, we have
$\mathbf{h^{\top}Rh}\leq 1=\mathbf{h^{\top}Rt}$, which means that
$s(h,r,h)>s(h,r,t)$ does not always hold.

In summary, we can conclude that UniBi has $\mathbf{h}\neq\mathbf{t},\
\mathbf{h^{\top}Rh}>\mathbf{h^{\top}Rt}$ iff. $\mathbf{R}=\mathbf{I}$, which
means that UniBi can model identity uniquely. And considering that the
embedding of entities are differences, we conclude that UniBi can model the
law of identity in terms of definition 2

∎

###  A.3 Proof of Theorem 3

###### Proof.

if we have $\|\mathbf{e}\|=1,\rho(\mathbf{R})=1$. The equation for the entity
part obviously holds, and by Proposition 1, we have the following.

$\|\mathbf{Re}\|\leq\rho(\mathbf{R})\|\mathbf{e}\|=\rho(\mathbf{R})=1,$ (18)

similarly, we have $\|\mathbf{e^{\top}R}\|\leq 1$.

Moreover, such a condition will become necessary and sufficient if
$\forall\mathbf{R}\in\mathbb{\hat{R}}$, $\exists\hat{e}$ that either
$\|\mathbf{\hat{e}^{\top}R}\|=1$ or $\|\mathbf{R\hat{e}}\|=1$.

To prove it, if we have $\|\mathbf{e^{\top}R}\|\leq 1$ and
$\|\mathbf{Rt}\|\leq 1$, we use SVD to any $\mathbf{R}$ and get
$\mathbf{R}=\mathbf{U\Sigma V}$. Then we denote
$\mathbf{\sigma}=Diag(\mathbf{\Sigma})$ and we have
$\forall\mathbf{e},\|\mathbf{\sigma\cdot e}\|\leq 1$.

If $\exists i,\sigma_{i}>1$, we take $i\neq j,e_{i}=1,e_{j}=0$ to show that
$\|\mathbf{e\cdot\sigma}\|$ is larger than 1. Therefore, we have $\forall
i,\sigma_{i}\leq 1$. Moreover, if $\forall i,0<\sigma_{i}<1$, we take
$\mathbf{\bar{e}}=\mathbf{V\hat{e}}$

$\displaystyle\|\mathbf{\sigma\cdot\bar{e}}\|^{2}=\sum_{i}{\sigma_{i}^{2}\bar{e}_{i}^{2}}<\sigma_{i}\bar{e}_{i}^{2}=1,$
(19)

which also violates $\|\mathbf{Re}\|=\|\mathbf{\Sigma
V\hat{e}}\|=\|\mathbf{\sigma\cdot\bar{e}}\|=1$. Therefore, there $\exists
k,\sigma_{k}=1$ and we have $\rho(\mathbf{R})=1$.

∎

###  A.4 Proof of Proposition 2

###### Proof.

If a relation $r$ is invertible, it means there exists an inverse relation
$r^{-1}$ that ensure $r\circ r^{-1}=r^{-1}\circ r=identity$, where $\circ$ is
the composition of relations. Consider that identity relation means an entity
is itself, thus KGs only contain triples like $(e_{1},identity,e_{1})$ rather
than $(e_{1},identity,e_{2})$, $\forall e_{1},e_{2}\in\mathcal{E}$ and
$e_{1}\neq e_{2}$.

Consider a complex relation $r$ that has multiple tail entities for a head
entity, that is, $\exists h,t_{1},t_{2},t_{1}\neq t_{2}\
(h,r,t_{1}),(h,r,t_{2})$. In order to remap the entities $t_{1}$ and $t_{2}$
back to $h$, the inverse relation $r^{-1}$ has to contain triples that
$(t_{1},r^{-1},h),(t_{2},r^{-1},h)$. Although $r\circ r^{-1}$ could map $h$ to
$h$, the other order $r^{-1}\circ r$ fails to map $t_{1},t_{2}$ back to
themselves separately since both $(t_{1},r^{-1}\circ r,t_{1})$ and
$(t_{1},r^{-1}\circ r,t_{2})$ are true. Therefore $r$ is not invertible.
Similarly, if a relation has multiple heads, we can also obtain the above
conclusion.

Therefore, all complex relations are inherently non-invertible.

∎

##  Appendix B Background of Group and Monoid

######  Definition 4 (Jacobson [2012]).

A monoid is a triple $(M,p,1)$ in which $M$ is a non-vacuous set, $p$ is an
associative binary composition (or product) in $M$, and 1 is an element of $M$
such that $p(1,a)=a=p(a,1)$ for all $a\in M$

######  Definition 5 (Jacobson [2012]).

A group $G$ ( or (G,p,1)) is a monoid all of whose elements are invertible.

##  Appendix C Discuss of Distance Based models

We mention that distance based model could model identity uniquely, and here
we give its corresponding proof. Here, we only consider models that can be
written in the basic form of $s(h,r,t)=-\|\mathbf{Rh}-\mathbf{t}\|$. Note that
translation is also considered in such a form if we take translation as a
linear transformation. Furthermore, the model must ensure that
$\mathbf{I}\in\mathbb{\hat{R}}$ and $\mathbb{\hat{E}}=\mathbb{R}^{n}$. Other
peculiar scenarios are not considered in this discussion.

######  Theorem 2.

A distance based model $s(h,r,t)=-\|\mathbf{Rh}-\mathbf{t}\|$ with
$\mathbf{I}\in\mathbb{\hat{R}}$ and $\mathbb{\hat{E}}=\mathbb{R}^{n}$ can
model identity uniquely.

###### Proof.

On the one hand, if $\mathbf{R}=\mathbf{I}$, it is easy to have

$-\|\mathbf{Rh}-\mathbf{t}\|=-\|\mathbf{h}-\mathbf{t}\|\leq-\|\mathbf{h}-\mathbf{h}\|=0,$
(20)

where $\mathbf{h}\neq\mathbf{t}$.

On the other hand, if $\mathbf{R}\neq\mathbf{I}$ and $\mathbf{R}$ is not a
singular matrix, we take $\mathbf{t}=\mathbf{Rh}$ and have

$-\|\mathbf{Rh}-\mathbf{h}\|\leq
0=-\|\mathbf{Rh}-\mathbf{Rh}\|=-\|\mathbf{Rh}-\mathbf{t}\|.$ (21)

If if $\mathbf{R}\neq\mathbf{I}$ and $\mathbf{R}$ is a singular matrix, then
$\mathbf{Rx}=0$ has solutions that $\mathbf{x}\neq\mathbf{0}$, and by taking
$\mathbf{t}=\mathbf{x}+\mathbf{h}$ we have:

$\mathbf{h^{\top}Rt}-\mathbf{h^{\top}Rh}=\mathbf{h^{\top}R(t-h)}=\mathbf{h^{\top}Rx}=0,$
(22)

which means $s(h,r,h)=s(h,r,t)$.

Therefore, we prove that distance-based models are born to uniquely model
identity. ∎

##  Appendix D Comparison to previous restrictions

Although it is true that entity normalization and set $\mathbf{R}$ to
orthogonal matrices, which is a special case of $\rho(\mathbf{R})=1$, are
common in KGE models, our constraint differs from their approach as follows.

(1) The constraint for relation based on the spectral radius, i.e.,
$\rho(\mathbf{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 $\mathbf{R}$ to be orthogonal while keeping the
normalization of entities, the performance will drop significantly, e.g., MRR:
0.488 $\to$ 0.471 for UniBi-O(2) on WN18RR. Since orthogonal matrix requires
each singular value to be $1$, which means $n$ equality constraints and the
cost on expressiveness is no longer negligible.

(2) Only the combination of entity and relation constraints succeeds to model
identity uniquely, as shown in Figure 3(c). It suggests that constraints on
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 a big difference. The constraint of TransR
is $\|\mathbf{h}\|\leq 1$, $\|\mathbf{t}\|\leq 1$, $\|\mathbf{hM}_{r}\|\leq
1$, and $\|\mathbf{tM}_{r}\|\leq 1$, and has three differences from ours.

  1. i)

For TransR, $\|\mathbf{hM}_{r}\|\leq 1$ and $\|\mathbf{tM}_{r}\|\leq 1$ is the
constraint itself. In contrast, $\|\mathbf{R^{\top}h}\|\leq 1$ and
$\|\mathbf{Rt}\|\leq 1$ is deduction of our constraints $\|\mathbf{e}\|=1$ and
$\rho(\mathbf{R})=1$.

  2. ii)

TransR does not normalize the entities, and we have shown in Fig. 1 that
normalization is necessary for a bilinear based method to uniquely model
identity.

  3. iii)

TransR is a distance based model, and as we 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 our combination of constraints is novel, since it
proposes a new constraint for the relation and the two parts are deliberately
rather than arbitrarily combined.

(a) RESCAL w/o reg.

(b) RESCAL w/ Frobenius

(c) RESCAL w/ DURA

Figure 6: 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 1) non-convergence exists in
every case, 2) the better the result, the more the scales converge, 3)
Regularization cannot stop the fluctuation of scales. (Better view in color,
zoom in, note the difference in the vertical coordinates.)

##  Appendix 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. 6, we take
RESCAL as example to 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 it is
ineffective, and we need a hard constraint rather than regularization term to
prevent this completely.

##  Appendix 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 $\mathbb{\hat{R}}$. Therefore,
UniBi violates the definition of group, which requires that each element has
its inverse element inside. However, we argue that some relations are
inherently non-invertible and misidentified by previous work [Yang et al.,
2020, Sun et al., 2019, Xu and Li, 2019].

For example, in Fig. 7, 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 is "Alice or David" rather than "Alice itself" as demonstrated in Fig.
7 and Fig. 7.

It should be noted that we are not 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 et
al., 2019], since definitions of the two concepts are different and do not
conflict.

Beyond the specific example, we generalize it to all complex relations that
appear in two difference triples $(e_{1},r,e_{2})$ and $(e_{1},r,e_{3})$ (or
($e_{3},r,e_{2}$)), where $e_{1},e_{2},e_{3}\in\mathcal{E}$, and $e_{1}\neq
e_{2}\neq e_{3}$. Furthermore, we have the following proposition.

######  Proposition 2.

$\forall r\in\mathcal{R}$, if $r$ is a complex relation, then $r$ 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 a better structure for
relations by their definitions666Definition 4 and Definition 5..

Figure 7: Why some relations are non-invertible. (a) A toy example. (2) True
case. (3) False case.

##  Appendix G Implement Details

###  G.1 Rotation Matrices of UniBi

In Section 5, we propose two variants of UniBi, i.e., UniBi-O(2) and
UniBi-O(3). Here, we give the rotation matrix $\mathbf{SO}(k)$ they used
specifically.

$\mathbf{SO}(2)=\begin{bmatrix}x&-y\\\ y&x\end{bmatrix},\
\mathbf{SO}(3)=\begin{bmatrix}p&-q&-u&-v\\\ q&p&v&-u\\\ u&-v&p&q\\\
v&u&-q&p\end{bmatrix},$ (23)

where $x,y,p,q,u,v\in\mathbb{R}$ and
$x^{2}+y^{2}=1,p^{2}+q^{2}+u^{2}+v^{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 et al. [2020a]. We choose
Adam [Kingma and Ba, 2015] as the optimizer and fix the learning rate at
$1e-3$. We set the maximum epochs to $200$ and apply the early stopping
strategy.

We set the scaling factor $\gamma$ to $1$ for all models except UniBi. And we
search $\gamma$ from $\left\\{1,5,10,15,20,25,30\right\\}$ for UniBi. For the
factor for regularization $\lambda$ we search
$\\{1,5e-1,1e-1,5e-2,1e-2,5e-3,1e-3\\}$ for all models except UniBi and
$\\{0.5,1,1.5,2,2.5,3\\}$ for it. Furthermore, we do not search for
$\lambda_{1}$ and $\lambda_{2}$ in Eq. 26 as in the original paper of DURA
[Zhang et al., 2020a]. we adopt their settings and set
$\lambda_{1}=0.5,\lambda_{2}=1.5$ for ComplEx [Trouillon et al., 2016] and CP
[Hitchcock, 1927], while $\lambda_{1}=\lambda_{2}=1$ for other cases. The
search results are listed on the Tbl. 3. We search for the batch size from
$\\{100,1000\\}$.

In addition, we implemented all the experiments in PyTorch with a single
NVIDIA GeForce RTX 1080Ti graphics card. We repeat each experiment five times
and take their means and standard deviations.

Table 3: Hyperparameters found by grid search. $\lambda$ is the regularization coefficient, $\gamma$ is the scaling factor, $b$ is the batch size. | WN18RR | FB15K237 | YAGO3-10-DR
---|---|---|---
Model | $\lambda$ | $\gamma$ | b | $\lambda$ | $\gamma$ | b | $\lambda$ | $\gamma$ | b
CP | 1e-1 | 1 | 100 | 5e-2 | 1 | 100 | 5e-3 | 1 | 1000
ComplEx | 1e-1 | 1 | 100 | 5e-2 | 1 | 100 | 1e-2 | 1 | 1000
RESCAL | 1e-1 | 1 | 1000 | 5e-2 | 1 | 1000 | 5e-2 | 1 | 1000
UniBi-O(2) | 2 | 20 | 100 | 2 | 25 | 1000 | 1.5 | 30 | 1000
\- w/o constraint | 1e-1 | 1 | 100 | 5e-2 | 1 | 1000 | 5e-2 | 1 | 1000
UniBi-O(3) | 2 | 15 | 100 | 1.5 | 20 | 1000 | 1.5 | 30 | 1000
\- w/o constraint | 1e-1 | 1 | 100 | 5e-2 | 1 | 1000 | 5e-2 | 1 | 1000

For the experiments in Section 5.4, we set $\gamma$ for UniBi without DURA in
Section 5.4 to $10,15,25$ for WN18RR, FB15k-237, and YAGO3-10-DR for UniBi,
respectively.

##  Appendix H Time and Space Complexity

Since UniBi needs to calculate some constraints, it spends more space and
time. Here, we compare the time and space consumption of UniBi and CP,
ComplEx, and RESCAL on FB15k-237, and set the batch size to 1000.

As demonstrated in Fig. 8(a) and Fig. 8(b), UniBi takes a little more time
than CP and ComplEx, and more time to compute the regularization since it is
more complex. Nevertheless, we noticed that UniBi occupies a space similar to
that of CP and ComplEx.

In addition, we note that in Section5.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 a 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.

(a) Comparison of time.

(b) Comparison of space.

Figure 8: UniBi takes a little more time than other models with linear
parameters (CP and ComplEx) and significantly efficient than ones with
quadratic parameters (RESCAL).

##  Appendix I Inherent regularization term

Here we find a necessary condition of UniBi and then deduce its corresponding
Lagrangian function.

######  Theorem 3.

UniBi has a necessary condition that $\|\mathbf{e}\|=1$, $\|\mathbf{Re}\|\leq
1$ and $\|\mathbf{R^{\top}e}\|\leq 1$.

###### Proof.

Please refer to the Appendix A.3. ∎

If we ignore the other implicit constraints, the optimization of UniBi can be
rewritten in the form of a constrained optimization problem.

$\displaystyle\min_{\mathbf{h,r,t}}$
$\displaystyle\sum_{(h_{i},r_{j},t_{k})\in\mathcal{K}}f(h_{i},r_{j},t_{k})$
(24) $\displaystyle s.t.$
$\displaystyle\|\mathbf{h}_{i}\|^{2}=1,\|\mathbf{t}_{k}\|^{2}=1$
$\displaystyle\|\mathbf{R}_{j}^{\top}\mathbf{h}_{i}\|^{2}\leq
1,\|\mathbf{R}_{j}\mathbf{t}_{k}\|^{2}\leq 1,$

where $f(h,r,t)$ is a loss function. Furthermore, Eq. 24 corresponds to a
Lagrangian function.

$\displaystyle\min_{\mathbf{h,r,t},\lambda,\mu}$
$\displaystyle\sum_{(h_{i},r_{j},t_{k})\in\mathcal{K}}f(h_{i},r_{j},t_{k})+\lambda_{i}^{h}(\|\mathbf{h}_{i}\|^{2}-1)+\lambda^{t}_{k}(\|\mathbf{t}_{k}\|^{2}-1)$
(25)
$\displaystyle+\mu^{h}_{j}(\|\mathbf{R}_{j}^{\top}\mathbf{h}_{i}\|^{2}-1)+\mu^{t}_{j}(\|\mathbf{R}_{j}\mathbf{t}_{k}\|^{2}-1)$
$\displaystyle s.t.\lambda_{i}^{h},\lambda_{k}^{t},$
$\displaystyle\mu_{j}^{h},\mu_{j}^{t}\geq 0.$

We notice that if we set factors
$\lambda_{i}^{h}=\lambda_{k}^{t}=\lambda\lambda_{1}$ and
$\mu_{j}^{h}=\mu_{j}^{t}=\lambda\lambda_{2}$ where
$\lambda,\lambda_{1},\lambda_{2}>0$, we achieve the following expression from
Eq. 25 by discarding constant terms.

$\displaystyle\min_{\mathbf{h,r,t}}\
\sum_{(h_{i},r_{j},t_{k})\in\mathcal{K}}f(h_{i},r_{j},t_{k})+\lambda\left[\lambda_{1}(\|\mathbf{h}_{i}\|^{2}+\|\mathbf{t}_{k}\|^{2})+\lambda_{2}(\|\mathbf{R}_{j}^{\top}\mathbf{h}_{i}\|^{2}+\|\mathbf{R}_{j}\mathbf{t}_{k}\|^{2})\right],$
(26)

which is equivalent to the optimization of a unconstrained model under DURA
[Zhang et al., 2020a], the best regularization term for bilinear based model
before. Therefore, we can get a more general version of DURA (DURA-G for
simplicity) from Equ. 25.

$\textbf{DURA-G}:\lambda_{1}\|\mathbf{h}_{i}\|^{2}+\lambda_{2}\|\mathbf{t}_{k}\|^{2}+\lambda_{3}\|\mathbf{R}_{j}^{\top}\mathbf{h}_{i}\|^{2}+\lambda_{4}\|\mathbf{R}_{j}\mathbf{t}_{k}\|^{2}$
(27)

At first glance, this seems to be nothing more than a 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 an additional hyperparameter to search and can lead to
better results, we 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.

Extra experiments of Scales To demonstrate that the phenomenon in Fig. 1
happens, we carry out additional experiments on WN18RR 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. 9, we notice that all models except UniBi has fluctuation on the
spectral radius of identity, which verifies the phenomenon in Fig. 1.

Figure 9: Bilinear based models learning identity have different scales.
(Better zoom in to see the fluctuation of RESCAL-DURA.)

Figure 10: Directly adding identity triples may hurt performance.

Dataset | #Identity | #Others(Avg.)
---|---|---
WN18RR | 40,943 | 7,894
FB15k-237 | 14,514 | 1,148
YAGO3-10-DR | 122,873 | 20,348

Table 4: Statistics of triples of identity and other relations in benchmark
datasets.

##  Appendix J 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 on identity per se
does not help the performance on other relations, and may be harmful for the
overall results as shown in Fig .10. We think the reason is that the triples
of identity are too much compared to the ones of other relations as shown in
Tbl. 4, and the model negligence in learning these relations.

##  Appendix K Illustration of How the Performance is Improved

This is a more detailed illustration of how the ineffective learning is
prevented and enhance the performance as discussed in Section 4.4.

Figure 11: 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.