Knowledge Graph Completion by Intermediate Variables Regularization
Authors: Changyi Xiao
Yixin Cao
Venue: NeurIPS 2024 poster (2024)
Keywords: Knowledge Graph Completion
Tensor Decomposition
Regularization
Primary area: graph_neural_networks
TL;DR: We propose a regularization to alleviate the overfitting problem of tensor decomposition based models for knowledge graph completion.

Abstract: Knowledge graph completion (KGC) can be framed as a 3-order binary tensor completion task. Tensor decomposition-based (TDB) models have demonstrated strong performance in KGC. In this paper, we provide a summary of existing TDB models and derive a general form for them, serving as a foundation for further exploration of TDB models. Despite the expressiveness of TDB models, they are prone to overfitting. Existing regularization methods merely minimize the norms of embeddings to regularize the model, leading to suboptimal performance. Therefore, we propose a novel regularization method for TDB models that addresses this limitation. The regularization is applicable to most TDB models and ensures tractable computation. Our method minimizes the norms of intermediate variables involved in the different ways of computing the predicted tensor. To support our regularization method, we provide a theoretical analysis that proves its effect in promoting low trace norm of the predicted tensor to reduce overfitting. Finally, we conduct experiments to verify the effectiveness of our regularization technique as well as the reliability of our theoretical analysis. The code is available at https://github.com/changyi7231/IVR.

Knowledge Graph Completion by Intermediate Variables Regularization
Changyi Xiao, Yixin Cao"
School of Computer Science, Fudan University
Shangyi_xiao@fudan edu. en, caoyixin2011@gmai1 com
Abstract
Knowledge graph completion (KGC) can be framed as a 3-order binary tensor completion task. Tensor decomposition- strong performance in KGC. In this paper, provide summary of existing TDB models and derive a general form for them, serving as a foundation for further exploration of TDB models. Despite the expressiveness of TDB models, they prone to overfitting. Existing regularization methods merely minimize the norms embeddings regularize the model, leading suboptimal performance. Therefore, we propose a novel regularization method for TDB models that addresses this limitation. The regularization applicable most TDB models and ensures tractable computation. Our method minimizes the norms of intermediate variables involved in the different ways of computing the predicted tensor. To support our regularization method, we provide a theoretical analysis that proves its effect in promoting low trace norm of the predicted tensor reduce overfitting. Finally, we conduct experiments to verify the effectiveness of our regularization technique as well as the reliability our theoretical analysis. The code is available https: //gttubb. www.coocccc...c. changy17231/IVR
(TDB) models have demonstrated
Introduction
knowledge graph (KG) can be represented a 3rd-order binary tensor, in which each entry corresponds triplet of the form (head entily, relation, tail entity). A value of 1 denotes known true triplet, while denotes a false triplet. Despite containing a large number of known triplets, KGs are often incomplete, with many triplets missing. Consequently, the 3rd-order tensors representing the KGs are incomplete. The objective of knowledge graph completion (KGC) is to infer the true false values of the missing triplets based on the known ones, i.c., predict which of the missing entries in the tensor are or O.
A number of models have been proposed for KGC, which can be classified into translation baased models, tensor decomposition- based (TDB) models and neural networks models [Zhang et al. [02T].
We only focus on TDB models in this paper due to their wide applicability and great performance
[acroix al. 2018 Zhang et al.) (2020). TDB models can be broadly categorized into two groups: CANDECOMPIPAR AFAC (CP) decomposition-
models, including CP [Lacroix et al. 2013 8), DistMult (Yang et al. 2014) and ComplEx [Troiiloon al. 2017), and Tucker decomposition models, including SimplE Kazemi and Poole 2018), ANALOGY [Liu et al., 2017]. QuatE (Zhang ct al. 2019) and TuckER Balažević et al.) 2019). J. To provide a thorough understanding TDB models, we present summary of existing models and derive general form that unifies them, which provides a fundamental basis for further exploration of TDB models.
"Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

TDB models have been proven to be theoretically fully expressive [Trouillon et al. 2017 Kazemi and Poole 2018 Balažević al. 2019 implying they can represent any real-valued tensor. However, in practice, TDB models frequently fall prey to severe overfitting. To counteract this issue, various regularization techniques have been employed in KGC. One commonly used technique is the squared Frobenius norm regularization [Nickel et al.) 2011 Yang et al. [014]) Trouillnn et al., [017]. Lacroix (ct al. [0188) proposed another regularization, N3 norm regularization, based on the tensor nuclear y-norm, which outperforms the squared Frobenius norm in terms of performance. Additionally, Zhang iet al. [2020) introduced DURA, a regularization technique based on the duality of TDB models and distance- based models that results in significant improvements
benchmark datasets. Nevertheless, N3 and DURA rely on CP decomposition, limiting their upplicability to CP [Lacroix et al., 2018) and ComplEx [Trouillon al. 2017]. .. As result, there is a pressing need for regularization technique that is widely applicable and can effectively alleviate the overfitting issue.
In this paper, we introduce a novel regularization method for KGC to improve the performance of TDB models. Our regularization focuses on preventing overfitting while maintaining the expressiveness of TDB models as much as possible. It is applicable to most TDB models, while also ensuring tractable computation. Existing regularization methods for KGC rely on minimizing the norms of embeddings to regularize the model (Yang al., 2014 Lacroix et al. 2018), leading to suboptimal performance. To achieve superior performance, we present an intermediate variables regularization (IVR) approach that minimizes the norms of intermediate variables involved in the processes of computing the predicted tensor of TDB models. Additionally, our approach fully considers the computing ways because different ways of computing the predicted tensor may generate different intermediate variables.
To support the efficacy of our regularization approach, we further provide theoretical analysis. We prove that our regularization is an upper bound of the overlapped trace norm [Tomioka et al. [011]. The overlapped trace norm is the sum of the trace norms of the unfolding matrices along each mode of a tensor [Kolda and Bader 2009], which can be considered as a surrogate measure the rank of a tensor. Thus, the overlapped trace norm reflects the correlation among entities and relations, which can pose constraint to jointly entities and relations embeddings learning. In specific, entities and relations in KGs are usually highly correlated. For example, some relations relations, or a relation may be a composition of another two relations [Zhang et al.) [021]. Through minimizing the upper bound of the overlapped trace norm, we encourage high correlation among entities and relations, which brings strong regularization and alleviates the overfitting problem.
mutual inverse
The main contributions of this paper are listed below:
1. We present a detailed overview of a wide range of TDB models and establish a general form to serve foundation for further TDB model analysis.
2. We introduce new regularization approach for TDB models based on the general form to mitigate the overfitting issue, which is notable for its generality and effectiveness.
We provide a theoretical proof of the efficacy of our regularization and validate its practical utility through experiments.
2 Related Work
Tensor Decomposition Based Models Research in KGC has been vast, with TDB models garnering attention due to their superior performance. The two primary TDB approaches that have been exten- sively studied are CP decomposition [Hitchcock] 1927] and Tucker decomposition [Tucker 1966). CP decomposition represents a tensor as a sum of n rank-one tensors, while Tucker dccomposition decomposes a tensor into a core tensor and a set of matrices. Kolda and Bader [2099] shows more details about CP decomposition and Tucker decomposition.
Several techniques have been developed for applying CP decomposition and Tucker decomposition in KGC. For instance, [acroix al. (2018) employed the original CP decomposition, whereas DistMult Yang et al. 2014), a variant of CP decompasition, made the embedding matrices of head entities and tail entities identical to simplify the model. SimplE [azemi and Poole 2018) tackled the problem of independence among the embeddings of head and tail entities within CP decomposition. ComplEx
(Trouiloon et al.] (0177] extended DistMult to the complex space to handle asymmetric relations.
QuatE [hhnn al. 2019 explored hypercomplex space to further enhance KGC. Other techniques

---

include HolE [Nickel et al. correlation, and ANALOGY Liu et al. 2017]. which explicitly utilizes the analogical structures of KGs. Notably, Liu et al. 2017 confirmed that HolE is equivalent to ComplEx. Additionally, Balažević al. (019 introduced TuckER, which based on the Tucker decomposition and has achieved state-of-the-ee performance across various benchmark datasets for KGC. Nickel et al. [2011] proposed three-way decomposition RESCAL over each relational slice the tensor. You can refer to Zhang et al. 2021 or Ji et al. 2021 for more detailed discussion about KGC models
2016 proposed by Nickel et al. [2016], which operates on circular
or TDB models.
Regularization Although TDB models highly expressive [Trouillon et al., 2017 Kazemi and Poole 2018 Balaževié et al. 2019]. they can suffer severely from overfitting in practice. Consequently, several regularization approaches have been proposed. A common regularization approach is to apply the squared Frobenius norm to the model parameters (Nickel et al. 2011 Yang et al. 2014 Trouillon et al. 2017]. However, this approach does not correspond to proper tensor norm, as shown by Lacroix et al.] [2018]. Therefore, they proposed a novel regularization method, N3, based the tensor nuclear 3-norm, which is an upper bound of the tensor nuclear norm. Likewise, Zhang et al.] [2200] introduced DURA, a regularization method that exploits the duality of TDB models and distance-based models, and serves
upper bound of the tensor nuclear 2-norm. However, both N3 and DURA are derived from the CP decomposition, and thus are only applicable CP and ComplEx models.
Methods
In Section 3.1 we begin by providing an overview of existing TDB models and derive general form for them. Thereafter, we present our intermediate variables regularization (IVR) approach in Section Finally, in Section we provide theoretical analysis to support the efficacy of our proposed regularization technique.
3.2
3.1 General Form
To facilitate the subsequent theoretical analysis, we initially provide a summary of existing TDB models and derive general form for them. Given a set of entities and set of relations R, a KG contains set of triplets = j( k)] C & x x E. Let X E {0, |||=|x|R|x((] represent the KG tensor, with X = 1 iff (i.j. k) E S, where [ and [R] denote the number of entities and relations, respectively. Let H E R IR R|xD and T E R be the embedding matrices of head entities, relations and tail entities, respectively, where
the embedding dimension.
Various TDB models can be attained by partitioning the embedding matrices into P parts. We reshape H E &|xD R R| and T R into H E [ R E T E RlEXx(D/PXXP respectively, where P is the number of parts we partition. For different P, can get different TDB models.
and
CP/DistMult Let P CP Lacroix 2018 can be represented as
D/P
XaJ (H R Tea) = Σ H R Tkd1
where () is the dot product of three vectors. DistMult Yang et al. 2014], particular case of CP, which shares the embedding matrices of head entities and tail entities, l.c., T.
ComplEx/HolE Let P 2, ComplEx (Truillon et al. 2017 can be represented
X ik = (H... R Taa) + HH Ry,, Tx:) + HHa. R22, Txa2) (H Ry2. Tka))
Liu et al. 2017 proved that HolE Nickel et al.
2011 is equivalent to ComplEx.
SimplE
Let P p 2, SimplE [azemi and Poole
2018 can be represented as
iik (Ha1, R R1 Tu:2) + HH2, 2, Tk.1)
3

---

ANALOGY Let P = 4, ANALOGY Liu et al 2017 can be represented as
Xish -Hai RJ Taa)) (H R 22 Tx:2) + (Ha3, Ry.3, Tka) (H.. Rj44, Tk.a)
+ (H44, R3:3 Teaa (H4 R3.4, Tea)
QuatE
Let P == 4, QualE Zhang et al. 2019
can be represented as
X tk (H,:1, R Tk:1)
H 1: R, Tk.1)
HH:3, R, Tk.)
(H Ry:1: Tk:1)
+ (H R3:2. Tw:2) + (H:: Ry:1, Tx22) + [H:,, Ry:4. Th:2)
(Ha:. R3:3, T2:2)
+ (#111 Rg Th:3) (H,2, 4j Tk:))
(H:3, R211 This) + (His, R. Tk.3)
+ HH Ry Twa)) + (H2,, R,33, kk4) [H43, R Tea) +
(Ha., R Tk:1)
TuckER
Let == D, TuckER Balažević et al.
2019 can be represented as
P Xisk ΣΣ
Σ
Winn H Hai Ry1m Tkin
where W E PxPxPP is the core tensor.
General Form Through our analysis, we observe that all TDB models can be expressed as linear combination of several dot product. The key distinguishing factors among these models are the choice of the number of parts P and core tensor W. The number of parts P determines the dimensions of the dot products of the embeddings, while the core tensor W determines the strength of the dot products. is important to note that TuckER uses a parameter tensor as its core tensor, whereas core tensors of other models predetermined constant tensors. Therefore, can derive general form of these models as
P
P ΣΣΣ
D/P Hia HiaBBja Tkdn) d=1
X ijı
Wimn Hig Rimms TemY
Wimn Σ
Im m== 1=
Im m=1 n=
D/P
P
P
P
Σ1Σ d=1
W Higl R. Rjdm Tkdn)
(1)
Iml m=ln=1
or
D/P X Σ X1 H.g. X2 R.d: X3 T.t:
where is the mode-n product (Kolda and Bader 2009 and W PPxxPP is the tensor, which can be a parameter tensor or a predetermined constant tensor. The general form Eq can of D TuckER decompositions, which is also called block-term
also be considered as decomposition [De Lathauwer 2008). Eq Q is block-term decomposition with a shared core tensor W. This general form is easy understand, facilitates better understanding of TDB models and paves the way for further exploration of TDB models. The general form presents a unified view of TDB models and helps the researchers understand the relationship between different TDB models. Moreover, the general form motivates the researchers to propose new methods and establish unified theoretical frameworks that are applicable most TDB models. Our proposed regularization in Section 3.2 and the theoretical analysis Section 3.3 are examples of such contributions.
The parameters of Eq. 2 come from two parts, the core tensor W and the embedding matrices H, R and T. The number of parameters of the core tensor W is equal to p3 if W is parameter tensor and otherwise equal to 0. The number of parameters of the embedding matrices is equal to |8 D + |R D if to 2 + D. The computational complexity of Eq. is equal to 0(DP2)E)) The larger the number of parts P, the more expressive the model and more the computation. Therefore, the choice of P is trade-off between expressiveness and computation.
The Number of Parameters and Computational Complexity
T and otherwise equal

---

mode
unteetin
X R
Xoy
mode-22 bers
untoliing
Xa. ge
fiters
mode:
seforing
Figure 1:
Left shows 3rd order tensor. Middle describes the corresponding mode-i fibers of the tensor. Fibers are the higher-order analogue of matrix rows and columns. A fiber is defined by fixing every index but one. Right describes the corresponding mode-i unfolding of the tensor. The mode-i unfolding of a tensor arranges the mode-i fibers to be the columns of the resulting matrix.
TuckER and Eq.(2) TuckER [Blaževvć et al. 2019] also demonstrated that TDB models can be represented Tucker decomposition by setting specific core tensors W. Nevertheless, stress that TuckER does not explicitly consider the number of parts P and the core tensor W. which pertinent the number of parameters and computational complexity of TDB models. Moreover, in Appendix A we demonstrate that the conditions for a TDB model to learn logical rules are also dependent on P and W. By selecting appropriate P and W, TDB models can be able learn symmetry rules, antisymmetry rules, and inverse rules.
must
3.2 Intermediate Variables Regularization
TDB models are theoretically fully expressive [Trouillon et al., 2017 Kazemi and Poole 2018 Balažević et al. 2019), which can represent any real-valued tensor. However, TDB models suffer from overfitting problem in practice [Lacroix al. 2018]. Therefore, several regularization methods have been proposed, such as squared Frobenius norm method (Yang et al. 2014] and nuclear 3-norm method [acroix et al. 2018), which minimize the norms the embeddings {H, R, T} to regularize the model. Nonetheless, merely minimizing the embeddings tends to have suboptimal impacts on the model performance. To enhance the model performance, we introduce new regularization method that minimizes the norms of the intermediate variables involved in the processes of computing X. To ensure the broad applicability of our method, our regularization is rooted in the general form of TDB models Eq.
To compute X in Eq. we can first compute the intermediate variable W X1 H X2 R.d: and then combine T.:: to compute X. Thus, in addition to minimizing the norm of Tat:, we also need to minimize the norm of W X1 H.g: X2 R.d:- Since different ways of computing X can result in different intermediate variables, we fully consider the computing ways of X. Eq. ( can also be written as:
D/P Σ
X
(W
x2 R.g. X3 T.d:) X1 Hatos
d=1
D/P
X
Σ
W X3 T.. X1 H.)) X2 R.d.
d=1
Thus, also need to minimize the norms of intermediate variables { R.d. X3 T.a W X3 Tal: X1 H.a:) and { HH.d: R.d.). }. In summary, we should minimize the (power of Frobenius) norms H. t 1x R. 17, [Ta:ll } and [ x, H. R.d. [ W x2 R. X; T.a 1 [W x T
H. }. where a is the power of the norms.
Since computing X is equivalent to computing X(1) or X (2) or X(3). we can also minimize the norms of intermediate variables involved in the processes computing X(1)- X(2) and X(3). where ((n) is the mode-n unfolding of tensor X [Kolda and Bader 2009]. See Figure I for an example
5

---

of the notation X (n). We can represent X X and (3) as [Kolda and Bader 2009]
DIP
X()) = Σ
(W x1 Hat) @ R.a:)"
d=1
DjP
(2) = Σ
(W X2 (T. Ha)"
d=1
D/P
(3) =
Σ
( X3 (3) (R. @ Ha))"
d=1
where @ is the Kronecker product. Thus, the intermediate variables include { X1 H.d. W X2 R.d W X3 T J and (T.d: R.d; T. Hid R.d: @ Hid: ). Therefore, we should minimize the
(power of Frobenius) norms [ X, H.a. W X2 y F. I X3 x | and { @ R.g. 1
aT. | R.a: 11.. J.. & H.a = TT H. P. R. H. I R. | | aa1))
Our Intermediate Variables Regularization (IVR) is defined as a combination all these norms:
D/P Σ
reg(x)
(1
:d:
R..d 11 + (TTa.113
A2 (T R.d
Th.: H dd: RR 1 H
+ A3 W 11 Ha + W X2 R I + W X3 Te ll
A4 W W X2 Rdd: X3 Ta + W X3 T.a: H.a: + W H.a X2 R.d:
where (A, > 0/i 1,2,33, 4) are the regularization coefficients.
In conclusion, our proposed regularization term the sum of the norms of variables involved in the different ways of computing the tensor X.
We easily get the weighted version of Eq.(3) , in which the regularization term corresponding to the sampled training triplets only [Lacroix et al. 2018 /Zhang et al. 2020]. For a training triplet (i,j, k), the weighted version of Eq. is follows:
D/P
reg( (jj))
Σ
1 + RBjd 11 + 1KT 11+) (I
d=1
+ A2( kel: 11 Radd: 1 + Tad: |
H idt 11 + R.R.Ra.l Hed:ll))
Ass X1 H.s 11% + W X2 Rja 18 + W X3 Ted: (19)
W X2 Rja: X3 Tea: 11 + I X3 Red: X1 Ha + I|W X1 His. X2 Rza:ll))
(4)
The computational complexity of Eq. 4) is the same that of Eq. [ D.i., i.e. O(DP2), which ensures that our regularization is computationally tractable.
The hyper-yaraee parameters A make IVR scalable. We can easily reduce the number of hyper-parameters by setting some of them zero or equal. The hyper-parameters make us able to achieve a balance between performance and efficiency as shown in Section 4.3 We set λ Xą and X2 X4 for all models to reduce the number of nyper-parameters. You can refer to Appendix C for more details about the setting of hyper papee-pprraeeers.
We use the same loss function, multiclass log-loss function, in Lacroix al. 2018 For a training
triplet (i, j. k), our loss function is
((Xijk) = - Xijk + log(
Σ exp X k5 )) + reg( (Xijk)
At test time, we use X.J.: to rank tail entities for a query (i,j,?). ?).
3.3 Theoretical Analysis
To support the effectiveness of our regularization IVR, we provide deeper theoretical analysis of its properties. The establishment of the theoretical framework of IVR is inspired by Lemma D in

---

Appendix [ which relates the Frobenius norm and the trace norm of a matrix. Lemma I shows that the trace norm of matrix is an upper bound of function several Frobenius norms of intermediate variables, which prompts us to establish the relationship between IVR and trace norm. Based on Lemma[ we prove that IVR serves as an upper bound for the overlapped trace norm of the predicted tensor, which promotes the low nuclear norm of the predicted tensor to regularize the model.
The overlapped trace norm Kolda and Bader 2009 for a 3rd-order tensor is defined as:
L(X;a)= == X |1 /10/2
+ X |0/2 + |X(a) (a) (a)1 1
where is the power coefficient in Eq. 3
+l and ||x (2) l Il are the matrix trace norms of x (2) and (3), respectively, which are the sums of singular values of the respective matrices. The matrix trace norm is widely used as a convex surrogate for matrix rank due to the
(2) [
non-differentiabiliy of matrix rank [Goldfarb and Qin, 2014, Lu et al.) 2016 Mu et al. 2014). Thus, L(X;a) a) serves as surrogate for rank (an)(X(1))
+ rank( X (2) )a/2 rank (3)) where
rank( (oll((((v)) ((1)) rank(X (2)) and (ann(((a)) are the matrix ranks of X ((2) and X X(3). respectively,
In KGs, each head entity, each relation and each tail entity uniquely corresponds to row of
(()) ((2) and (()), respectively. Therefore, rank(2 X (1)), rank( ((2) and rank(X (xs)) measure the correlation among the head entities, relations and tail entities, respectively. Entities or relations in KGs are highly correlated. For instance, some relations are mutual inverse relations or one relation may be composition of another two relations [Zhang al.) [021]. Thus, the overlapped trace norm L(X; can pose a constraint to the embeddings of entities and relations. Minimizing L(X; a) encourage high correlation among entities and relations, which brings strong regularization and reduces overfitting. We next establish the relationship between our regularization term Eq. and LXX; a) by Proposition I and Proposition 2
We will prove that Eq.3) is an upper bound of L(X:a). a)).
Proposition 1. For any X, and any decomposition of X, X = E W X1 H.d: X Re X Tad we have
D/P
2V ( & Σ
X1
H.l + |R 17 + TTall
d=1
+ W X2 Red X3 Fall + W X3 Ta X1 Hal + I X1 H.a. X2 Red:1())
(5)
If Xa) = -U VT, X(2) U2E V X(s U2E V are compact singular value decompo-
sitions of X(): X(2) X(3) (Bai et al. 2000%. respectively, then there exists a decomposition of X,
X EDI D/P W X1 H.s: X2 R.d. X3 Taa. such that the two sides of Eq. equal.
Proposition 2. For any X, and for any decomposition of X, X = Ed=l W H X2 R.s X TTdi.
we have
D/P
2/ X232 $ Σ
A2 T
Red:
Ta 11 H.d 11 + & Hall))
d=1
W X1 Hal. +
I X2
Rd
+ W X3 lT)
(6)
And there exists some X', for any decomposition of X', such that the two sides of Eq. Eq. can not achieve equality.
Please refer to Appendix B for the proofs. Proposition I establishes that the r.h.s. of Eq. 5 provides tight upper bound for 2 277x ci), while Proposition demonstrates that the r.h.s. of Eq. is an upper bound of 2 / ax). but this bound is not always tight. Our proposed regularization term, Eq. 3 combines these two upper limits by adding the r.h.s. of Eq. and the r.h.s. of (6. As result, minimizing Eq. can effectively minimize T. ox;;o)) to regularize the model.
The two sides of Eq 5 can achieve equality if P D, meaning that the TDB model is TuckER model [Balažević et al. 2019). Although L(X; a) may not always serve as a tight lower bound of the r.h.s. of Eq. 3 for TDB models other than TuckER model, it remains common lower bound for all TDB models. To obtain a more tight lower bound, the exact values of P and W are required. For example, in the case of CP model [Lacroix et al., 2018 (P 1 and W = 1), the nuclear 2-norm |||]], I|, is a more tight lower bound. The nuclear 2-norm is defined as follows:
|X|] == min
H. le R. | = Σ w X1 Han X2 Ran X3 Tenr
d=
7

---

Table 1: Knowledge graph completion results WN18RR, FB15k-237 and YGA03-10 datasets.
WNI8RR
FB15K-237
YAGO3-10
MRR
H@! 1
H@ 10
MRR
H@
H@
MRR
H@
H@ 10
0.438
0.416
0.485
0.332
0.244
0.507
0.567
0.495
0.696
CP-F2
0.449
0.420
0.506
0.331
0.243
0.507
0,570
0.499
0.699
CP-N3
0.469
0,432
0.541
0.355
0.261
0.542
0.575
0.504
0.703
CP-DURA
0.471
0,433
0.545
0.364
0.269
0.554
0.577
0.504
0.704
CP-IVR
0.478
0.437
0.554
0.365
0.270
0.555
0.579
0.507
0.708
ComplEx
0.464
0.431
0.526
0.348
0.256
0.531
0.574
0.501
0.704
ComplEx-F2
0.467
0.431
0.538
0.349
0.260
0.529
0.576
0,502
0.709
ComplEx-N3
0,491
0.445
0.578
0,367
0.272
0.559
0,577
0.504
0.707
ComplEX-DURA
0.484
0.440
0.571
0.372
0.277
0.563
0.585
0.512
0.714
ComplEx-IVR
0.494
0.449
0.581
0.370
0.275
0.561
0.586
0.515
0.714
SimplE
0.443
0.421
0,488
0.337
0.248
0.514
0.565
0.491
0.696
SimplE-F2
0.451
0,422
0,506
0,338
0.249
0,514
0.566
0.494
0.699
SimplF-IVR
0.470
0,436
0.537
0.357
0.264
0.544
0.578
0.504
0.707
ANALOGY
0.458
0.424
0.526
0.348
0.255
0.530
0.573
0.502
0.703
ANALOGY-F2
0.467
0.434
0.533
0.349
0.258
0.529
0.573
0,501
0.705
ANALOGY-IVR
0,482
0.439
0.568
0.367
0.272
0.558
0.582
0.509
0.713
QuatE
0.460
0.430
0.518
0.349
0.258
0.530
0.566
0.489
0.702
QuatB-F2
0.468
0.435
0.534
0.349
0.259
0.529
0.566
0.489
0.705
QuatE-IVR
0.493
0.447
0.580
0.369
0.274
0.561
0.582
0.509
0.712
TuckER
0.446
0.423
0.490
0.321
0.233
0.498
0.551
0.476
0.689
TuckER-F
0.449
0.423
0.496
0.327
0.239
0.503
0.566
0.492
0.700
TuckER-IVE
0.501
0,460
0.579
0.368
0.274
0.555
0.581
0.508
0.712
where W = 1. The following proposition establishes the relationship between X|| and L(X;2):
Proposition 3. For any for any decomposition of X. X Ed
Wx x1
H
x R X3
and W = 1, we have
D
2 21 S X
S
Σ
A1 (1
H. + R +
d=1
A W X2 Rai X3 T.a 12 + I X3 Tai
Hall + I X1 H. X2 R.a l
Although the r.h.s. 66 not always tight upper bound for 2 L aa) like the r.h.s. of (5). we observe that minimizing the combination of these two bounds, (3. can lead to better performance. The reason behind this is that the r.h.s. of (5. (5) is neither an upper bound nor lower bound of the r.h.s. of (q. for all X. We present Proposition T in Appendix B to prove this claim.
4 Experiments
We first introduce the experimental settings in Section 4.1 and show the results in Section 4.2 We next conduct ablation studies in Section 4.3 Finally, we verify the reliability of our proposed upper bounds in Section 4.4
Please refer to Appendix for more experimental details.
4.1 Experimental Settings
Datasets We evaluate the models on three KGC datasets, WN18RR Dettmers et al. 2018 FB15k-
237 [Toutanova et al. 2015 and YAGO3-10 [Dettmers et al. 2018
Models We use CP. ComplEx, SimplE, ANALOGY, QuatE and TuckER as baselines. We denote CP with squared Frobenius norm method Yang et al. 2014
CP-F2, CP with N3 method [Lacroix

---

Table 2: The results on WNI8RR and FB 15k-237 datasets with different upper bounds.
WNI8RR
FB15k-237
YAGO3-10
MRR
H@
H@ 10
MRR
H@ 1
H@ 10
MRR
H@
H@
TuckER
0.446
0.423
0.490
0.321
0.233
0.498
0.551
0.476
0.689
TuckER-IVR-
0.497
0.455
0.578
0.366
0.272
0.553
0,576
0.501
0.709
TuckER-IVE -V--22
0,459
0.423
0.518
0.336
0.241
0.518
0.568
0.493
0.700
TuckER-IVR
0.501
0.460
0.579
0.368
0.274
0.555
0.581
0.508
0.712
Table 3: The results on Kinship dataset with different upper bounds.
[x)]l
[x]l+
[Xax) I|
L(X)
TuckER
10,719
8,713
11,354
30,786
TuckER-IVE I
5,711
5,021
6,271
17,003
TuckER-IVR-2
6,145
5,441
6,744
18,330
TuckER-IVR 3,538
3,511
3,988
11,037
ct al. 2018 as CP-N3, CP with DURA method [Zhang et al. 2020 as CP-DURA and CP with IVR method CP-IVR. The notations for other models are similar to the notations for CP.
Evaluation Metrics We use the filtered MRR and @its@N N (H@N) [Bordes et al. 2013 as evaluation metrics and choose the hyper-paramenn with the best filtered MRR on the validation set. We run each model three times with different random seeds and report the mean results.
4.2 Results
See [ar the results. For CP and ComplEx, the models that N3 and DURA are suitable, the results show that N3 enhances the models more than F2, and DURA outperforms both F2 and N3, leading to substantial improvements. IVR achieves better performance than DURA on WN18RR dataset and achieves similar performance SimplE, ANALOGY, QuatE, and TuckER, the improvement offered by F2 is minimal, while IVR significantly boosts model performance. In summary, these results demonstrate the effectiveness and generality of IVR.
DURA on FB15k-237 and YAGO3-10 dataset. For
4.3 Ablation Studies
We conduct ablation studies to examine the effectiveness of the upper bounds. Our notations for the models are as follows: the model with upper bound Eq.(5) denoted as IVR-1, model with upper bound Eq. (6 as IVR-2, and model with upper bound Eq. (3) as IVR.
See Table 2 for the results. We TuckER the baseline. IVR with only regularization coefficient, IVR-1, achieves comparable results with vanilla IVR, which shows that IVR can still perform well with fewer hyper-parametery IVR-1 outperforms IVR-2 due the tightness of Eq.
4.4 Upper Bounds
We verify that minimizing the upper bounds can effectivvlyy minimize L(X; a)) L(X; a) can measure the correlation of X. Lower values of L(X; ; a) encourage higher correlations among entities and relations, and thus bring strong constraint for regularization. Upon training the models, we compute L(X:a) As computing L(X a:) for large KGs is impractical, we conduct experiments on a small KG dataset, Kinship [Kok and Domingos 2007), which consists of 104 entities and 25 relations. We use TuckER as the baseline and compare it against IVR-1 (Eq, (5) IVR-2 (Eq.(6). and IVR (3).
See Table 3 for the results. Our results demonstrate that the upper bounds are effective in minimizing L. XX;;; a)) All three upper bounds can lead a decrease of T. Tx(X;
(xxo) oi), achieving better performance (Table by more effective regularization. The L(X; a) of IVR-1 is smaller than that of IVR-2

---

because the upper bound in Eq.5) is tight. IVR, which combines IVR-1 and IVR-2, produces the reduction of (XX; a). This finding suggests that combining the two upper bounds can be more effective. Overall, our experimental results confirm the reliability of our theoretical analysis.
5 Conclusion
In this paper, we undertake an analysis of TDB models in KGC. We first offer summary of TDB models and derive general form that facilitates further analysis. TDB models often suffer from overfitting, and thus, propose regularization based our derived general form. It is applicable to most TDB models and improve the model performance. We further propose a theoretical analysis to support our regularization and experimentally validate our theoretical analysis. Our regularization limited to TDB models, hoping that more regularization will proposed other types of models, such translation-bart models and neural networks models. We also intend to explore how to apply our regularization to other fields, such as tensor completion [Song et al. 2019
Acknowledgements
This work is supported by the National Key Research and Development Program of China (2020AA0010600), the National Natural Science Foundation of China (U19A2079), and the CCCD Key Lab of Ministry of Culture and Tourism.
References
Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst. Templates for the solution of algebraic eigenvalue problems: practical guide. SIAM, 2000.
Ivana Balažević, Carl Allen, and Timothy Hospedales. Tucker: Tensor factorization for knowledge
graph completion. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 5185-5194 2019.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for dyper-paramedt optimization. Advances in neural information processing systems, 24, 2011.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Reexamining low rank matrix factorization for trace norm regularization. arXiv preprint 1706. 2017.
Lieven De Lathauwer. Decompositions of a higher-order tensor in block terms-part i: Lemmas for partitioned matrices. SIAM Journal Matrix Analysis and Applications, 30(3): 2008.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. Thirty-second AAAI conference on artificial intelligence, 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Donald Goldfarb and Zhiwei Qin. Robust low-rank tensor recovery: Models and algorithms. SIAM Journal on Matrix Analysis and Applications, 35(1):225-25 2014.
Frank I. Hitchcock. The expression of tensor polyadic as sum of products. Journal of Mathematics and Physics, 6(1-4):164-189, 1927.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE transactions on neural networks and 2021. 2021.
learning systems, 33(2):494-514,
10

---

Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4289-4300, 2018
Stanley Kok and Pedro Domingos. Statistical predicate invention. In Proceedings of the 24th international conference on Machine learning, pages 433 4400, 2007.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pages 2863-2872. PMLR, 2018.
Hanxiao Liu, Yuexin Wu, and Yiming Yang. Analogical inference for multi-relational embeddings. In International conference on machine learning, pages 2168-2178. PMLR, 2017.
Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimiza- tion. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5249-5257, 2016.
Cun Mu, Bo Huang, John Wright, and Donald Goldfarb. Square deal: Lower bounds and improved relaxations for tensor recovery. In International conference machine learning, pages 73-81. PMLR, 2014.
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In Proceedings of the 28th International Conference on International Conference Machine Learning, pages 809-816, 2011.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic embeddings of knowledge graphs. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
Qingquan Song, Hancheng Ge, James Caverlee, and Xia Hu. Tensor completion algorithms in big data analytics. ACM Transactions on Knowledge Discovery from Data (TKDD), 13(1):1-48, 2019.
Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima. Statistical performance of convex tensor decomposition. Advances in neural information processing systems, 24, 2011.
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 conference on empirical methods natural language processing, pages 1499-1509, 2015.
Théo Trouillon, Christopher R Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guil- laume Bouchard. Knowledge graph completion via complex tensor factorization. Journal of Machine Learning Research, 18:1-38, 2017.
Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3): 279-311. 1966.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv e-prints, pages arXiv-1412, 2014.
Jing Zhang, Bo Chen, Lingxi Zhang, Xirui Ke, and Haipeng Ding. Neural, symbolic and neural- symbolic reasoning on knowledge graphs. Al Open, 2:14-35, 2021.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 2735-2745. 2019.
Zhanqiu Zhang, Jianyu Cai, and Jie Wang. Duality regularizer for tensor factorization based knowledge graph completion. Advances Neural Information Processing Systems, 33, 2020.

---

A
Logical Rules
KGs often involve some logical rules to capture inductive capacity (Zhang et 2021] J. Thus,
analyze how to design models such that the models can learn the symmetry, antisymmetry and inverse rules. We have derived a general form for TDB models, Eq. Next, we study how enable Eq.4I to learn logical rules. We first define the symmetry rules, antisymmetry rules and inverse rules. We denote Xisk {( [::: R Tk::) as fh, r, t) for simplicity. We assume H T, which mainly aims to reduce overfitting Yang et al. (014)). Existing TDB models for KGC except CP [Lacroix
al. 2018 all forces H T.
relation r is symmetric if vh, 1, (h,r,)) E S + (1,r,)) E S. A model is able to learn the symmetry rules if
E E R. Ar + 0, Yh, t RR, ,(,, r, = r)),r,h)
A relation is antisymmetric if th, (h, r,t) E E - (1r $ S. A model is able to learn the antisymmetry rules if
3r P R Ar 0, Vh, E RD, f(h,r,, = =f(tr,,
relation r1 is inverse relation r2 if wh, t, (h, S (t, E S. model able to learn the inverse rules if
Vri E 3r2 ER Wh,tER' f(h, ri, st,,r,,1
We restrict r f 0 because 0 will result equal an identically zero function. By choosing different P and W, we can define different TDB models as discussed in Section Next, we give theoretical analysis establish the relationship between logical rules and TDB models.
Theorem 1. Assume model can be represented as the form of Eq. T. then a model is able to learn the symmetry rules iff (WT:
(2) SW < P. model is able learn the antisymmetry
(2) SW (2) < P. A model is able to learn the inverse rules iff rarraanW (WT) (2)) rules iff rank(W
(2). SW()) where S PP is permutation matrix with ((-1))+5(6--))++ ] = 1,2,.... P) and otherwise O, [WT) (2) SW()
rank( (WT
(2) is the concatenation of matrix W and
matrix SWT. (2)
Proof. According to the symmetry rules, for any triplet (i, k). we have that [(i k)) = fkk i). ie., [(H R Ts:) &H R Tx.) f(T k:, R2:, H..) (we use H T here). We replace Hg by h, replace R,, by r, replace Tg. by t, then we have f(h, r, = r))
Then we have that
P
P
P
P
ΣΣΣ
Σ
Wimn (ha, Pims tan)
ΣΣΣ
Wimn (fat Pems hen)
1=
=1m=la=
1=1 m= n=1
P
P M
Σ
Σ
Wimn (ha Tims tmm)
Σ
Σ
W nomd (he Tame t.x
P
P
P
Wtmn- W Wrmm) (1as Pims bin)
[=1 m=
P
(Wimn- W Wrmmi Tr (h. tim)
ΣΣ
Wiim Wnmm)rr ( (h: * t. 0
where the Hadamard product. Since the above equation holds for any h, t
D. we can get
Wimn W W am 0(1, n =
12

---

Therefore, model is able to learn the symmetry rules iff
3r E Ar+ O, ( Imn W nmd )
0
Therefore, the symmetry rule is transformed into system of linear equations. This system of linear equations have non-zero solution iff rank(W? SWT < <. Thus, model is able to learn the
symmetry rules rank ( - SW (2) P.
Similarly, model is able to learn the anti-symmetry rules iff rank + +SW < <.P. For the inverse rule:
Vri E RR, 3r2 E RR, Vh, E E s1h,, ri, s(,,
model is able to learn the symmetry rules iff the following equation
W r (
for any Ti E RD, there exists T2 E DRD such that the equation holds. Thus, the column vectors of W can be expressed linearly by the column vectors of SWT Since S is permutation matrix
and S ST, we have that & = I, thus
s (2) = W (2)
For any F1 E RRD, there exists E RDD such that the above equation holds. Thus, the column vectors of SW can be expressed linearly by the column vectors of W (2) Therefore, the column space of
(2)
W is equivalent to the column space of SWT, (2) thus we have
rank W (2)) rank(SnSS (SWT) (2)) rank (I (2) SW (2))
Meanwhile, if rank W rank([WZ (2), SW (2)), then the columns of WT linearly by the columns of SWT (2): thus
(2) can be expressed
Vrr E R WT (1) =SW? (2)
Thus, model is able to learn the inverse rules iff rank W W22) rank (
rank
(2): SWT
By this theoerm, we only need to judge the relationship between and the matrix rank about W (2)- ComplEx, SimplE, ANALOGYY and QuatE design specific core tensors to make the models enable learn the logical rules. We can easily verify that these models satisfy the conditions this theorem. For example, for ComplEx, we have that P = 2 and
0
0
0
1
0
T
0
1
SW
-1
(W2)
SWT
-1
(2)
0
-1
O
1
(2)
0
-1
0
1
0
I
0
2
rank(WT - -SWT (2) = rank
= < P
0
2
0
rank(W? + SWT T (2)
rank
0
1= P
0 0
2
rank WT) = rank (2),, (2), SWT)) =
Thus, ComplEx is able to learn the symmetry rules, antisymmetry rules and inverse rules.
13

---

B Proofs
To prove the Proposition and Proposition Lemma 1.
2 we first prove the following lemma.
1 CA 2cx + )1))))) )
1
min UVT 2
A
where > 0, >>> O and { UZU. V} are real matrices. If Z = ÚΣVT is a singular value decomposition of Z. then equality holds for the choice U X कक Ü E and V x V V. where E is the element-wise square root of Σ.
Proof. The proof of Lemma 1 is based on the proof of Lemma 9 in [Ciliberto et al., 2017]. Let the singular value decomposition of Z E R= be Z ÚEV". where U R Σ R V E Rexr, r rank ( Ú 1xr and VT Ixx-- We choose any U, V such that UVT, then we have Σ ÜUVVV. Moreover, since Ü, V have orthogonal columns,
UTTU| & | [| r 1 | Then
| (r 0 T'Ü' S (UTIIVIVI
1 ( 2a + |
s (VAlUU))))
[V = 2
where the first upper bound is Cauchy- inequality and the third upper bound is AM-GM inequality.
Let U = A and V = A E, we have that
2 (>||UT|)>
1
+  |ル 20
(
20 (
-
1 + = 2
In summary,
1 ==UV
(A 20 11)
1 =
min
Proposition 1. For any X, and for any decomposition of X = Ede W x1 H.s X2 Rea X3 Tatis have
D/P
2V (x & Σ
H.H + |R + Ta)l1
d=1
+ W X2 Red: X3 Taa + X3 Tea: X1 Had + W X1 H.a. X2 Rd
(7)
If X(1) U, Vf X(2) U2E2V X(3) VI are compact singular value de- compositions of X (1), X(2). X(3) respectively, then there exists a decomposition of X, X
ΣD/P W X1 H.d. X2 R.d: X3 Ted such that the two sides of 5 equal, where P = D.
H.. / VIV R.: Viihde U2 U2VE2, Ta: Vn UaVEn W
A Xx1 Σ Uf x2 v EJ X3 V UT.
Proof. Let the n-rank Kolda and Bader 2009 of X E R Xm2xXa be (ri, r2, ra). then U1 E
Roixri U2 E Tguxxrs E KS En
Rrx Eg Reaxr Eg E Rraxrs W
Brixrarrs
If O, the above proposition is obviously true, we define 0 = 0 here.
For any X + O, since X(1) EDip H (1)
(Win (Ta. R.,:) X (2)
D/P R.d. W (22) W(2)(Tas (Ta
d
H IT) (3) ΣDIP T.a. (W (33) (R.a & H.a)) )T), by applying Lemma l to X(1)- X (2): X(3).
14

---

have that
D/P
(Wa Raa:) + RI (W (2) (T. @ HI?
@ ))
D/P
X(| Ha:11 + |Raa::13 + TTa:: 11?))
d=1
(I) (T @ R + (2) (T.a @ 12 (R @ 19)
D/P
H| || + |Raa:1 + Taa
d=1
1
( X2 R X3 T W X3 Tet: X1 H W X1 H. X2 R.).11))
Let A V /1/Aa have that
D/P
2V ()
Σ x H + |R + [Ta:1
d=1
+ X2 Rud X3 Ta + W X3 Ta. Hal + IW X1 H.t X2 R
Since U, L L
I UfU
Laxrs thus we have X(1)
U,UT ((), X(2)= = U2? X(2): ((3) = U2Uy X X(3) then
X =X X1 (U.UT) (U.U2) X3 (U,U,)
-X (UIV Σi
X2 (U2v E2 ET x3 Σ3 UZ)
=X ET-UT X2 V U. xa / 1ز U U.VE, E x2 U2V U2V Eg x3 U3V Es
Let D and H. = VAlA UIVE R.. = VAI/d4 U2 Eo Ta:
/ U. W VA/M X X1 / E U X2 E U x3 Ex U.. then X
W X1 H. X2 R1: X3 T.. is a decomposition of X. Since
X(1) VAIAA, UI U.VE,W & RR) = U1V E, V
X VAIA U2 E, (T @ HT.) = U2V En EVEVV
X VAI/2 U (R @ HT.)* = UU3 Eg E3V,
thus
WO & R = V VEV
(T & HT.)² VA/Aii VEVV
W R.. @ H. = V\//ha" VEVV
15

---

P = D, we have that
D/P
Σ 1
+ | [+)
(D) (: & +2 (T.:: 8 H2 W (R.: @ Haa.)
= F + [
+ X2 R.:: X3 T1
X3 Ta: Ha.13 + IW X1 H.. X2 Ra::lp))
H [T.1)+
+ 2 R.1 1I
11 W (R.: @ 11))
|l E2113 + 11 ())
(x (2) (3) 11 (1)ll (2) f1 + (3)
(X;;a)))
Proposition 2. For any X, and for any decomposition of X, X, X DIj W X1 H.: X2 R.d: X3 Ted we have
DJP
2 2 12 & Σ T
R.d:
TT
H 1 +
H
d=1
+ + W.W X1 H +
W X2
W X3 Ted: lF)
(8)
And there exists some X", and for any decomposition of X', such that the two sides of Eq. can not achieve equality.
Proof. Since (1) EDI H W (T. @ Ra)) EDIP RR.d W ((2) (T.: &
H. )T, X (3) = EDPP(T (Ted: W (3)
R.d: & " and for any matrix A, B, || & B | B p. by applying Lemma to X(1), (()) X X(3), we have that
2L(X;a)
D/P
W()) @ R.).' + (R W (T @ 1 + (TT W ((a) @ H. 0/2
D/P
T....a & R. + 2 H.d. + R.s 8 Hall))
d=1
H.. (1) 18 R 1
T W (1))
D/P
Σ T. 11 Ra.l + T
R. H.
d=1
+ W H.a.1 + W X2 R.
W 12)
Let A = /22//a0 A3, we have that
D/P
2 tedg < Σ Xe (T R.a
T.. 11 H.a.
+
|| 11 H.a 11?)
+ W H + W X2 R 1
W X3 Taa 1%)
(9)
16

---

Let X' E R2x2xx Xi,1,1 2,,2, and X kk = 0 otherwise. Then
X(1 (1) = ((2) (2)
X (3) = 0 0
0
Thus rank (1)) = rank X (2)) = rank X (3) 2. In Lemma a necessary condition of the
equality holds is that rank(U)) rank V) rank Z). Thus, the equality holds only if P = D and
rank (x,)) = rank 1: @ R.1:) = 2, rank (2))) rank (Ta: @ Ha:) = 2
rank(X(1))
rank( (X = rank R: H 1: = 2
Since for any matrix A, B, rank(4 B) rank (A) rank( we have that
rank(T.)) rank R.1:) rank (T.1) rank(H.1)) 2, rank(R. rank H.::)
The above equations have no non-negative integer solution, thus there is no decomposition of X' such that
D/P Σ
2/ A2
A2 Ta
R.d:11
TTa:
H. + &R Ha.l))
d=1
+ As X1 Hall + W X2
R.
W X3 T.d:1T)
Proposition 3. For any X, for any decomposition we have
X, X Ed=1 W Wi Hid X2 Xa
D
2 2 (1x;)(( S 66 A, | S
Σ
A1 H aa + R 11 + (Taill?))
d=1
+ W W X2 R X3 Tail + W X3
Pai x H Hail 11 + I x Ha X2 Rad l1:)
where W =1
Proof. VX, let S (( H. X De W X1 H.t X2 R.d: X3 Ted: J, S2
((W H. R. X Eb W x1 Han X2 Ran X3 Tan, W = 1}. We have that
2 AAA
H Haall FF
da R.a 12 TTa 112) 1/2 Au H 12/
Σ A H. W X2 R.d T:a: l| d=1
where W = 1. The equality holds if and only if A Rad T 11 = A 1|a. i.e.,
V V Ai Ran Taa |la H 22. For CP decomposition of X, X Σb1 W x H.a X2
Raa X3 TaI, let H V
R 1e H R
H. ll
R, T
T. if
H.alla
R 1|a Tin 1a
Haalll * O, Raill * 0, Ta ll2 * and otherwise H = 0, R = 0, 0,T = 0. Then
x= Eb W x1 H .di Rign X3 T'n is another CP decomposition of X and R ||
|| 1l2. Thus
2 X = min
A H H
W X2 R.d. X3 Taall
d=
Similarly, we can get
min
A R
1 W X2 T.. X3 H.
82
d=1
17

---

2/ A111111 X
min
Au Tai Pp + + W X2 Hig X3 R..:Ip
By Propostion
1 we have that
D Σ
2 | (n)l+
A H 11 + da W X2 Red: X3 1F
d=1
Since S2 is a subset of S1, we have that
(()) 11+ I |X||- ||
Similarly, we can prove that | (2)ll= S || I and
| (3)]1++ S | ||-, thus
2 2) S < A | I+ S
Σ
A1 HlI + R 112 + |T
d=1
W X2 R. X3 Tanll + I X3 Tai
H Hall + W| x1 Han X2 Rai 12:)
Proposition 4. For any X, there exists decomposition of X = Edd W x1 Hid X2 Rud X3 Tidi such that
D/P Σ
X1 H.
|| 11))
+Xi(IIW X2 R.. x3 Tea 11 + W X3 F.a X Halli + || x1 H.. X2 Ra
D/P
<VALi/V/>>>s
Σ
A2 de a
R 1
| 11 1 + R 11 (
+ H. + W X2 1
W X3 T:d: 11)
Furthermore, for some X, there exists a decomposition of X, X EDIl W x1 H. X such that
D/P
Σ
+ || 17 + 1ia
d=1
+ X2 R.. X3 Paa + W X3 Taa x Hall W x1 H.a X2 R
D/P
Σ
22 T.. d: | R. 11 |T 11 H + R. (..l))
+>s(IIW X1 Ha X2 R. + W X3 T. (7)
Proof. To simplify the notations, we denote H.t H. Rud as R and T.a. as T. To prove the inequality, we only need to prove
/A H
IT
/ X2 R X3 T
+
X3 x1 H +
x1 x
( R
R H
+ x1 + X2
R
+
W X3 +
Let vA / A Az. for any X, X = Σ d=1
(cT
W) x1 (cr H.) X2 (c R.d:) X3 (c)T. is
a decomposition of X, thus we only need to prove
c2(
R
X3
T
W
X3 T
WW x1 H x2 R
>c
+
[||W
x1 0 + W X2 R W x3 T
18

---

where C2 = V V1222.
E let = X² + 100, H - R - T = c, W = X we have
+ - [ X2 R x3 + + I X3 T x1 H
22 ? +
| + |
IW x1 X X2 R13)
1
X²
=x2(X²2 + 100)2
X + 100
<<2( <T
1/
(IIW x1 H + W x2 R| + W X3 111
02
=x2(X² + 100)* + 1
X2
C2 X + 100)4
For any X E R2 max fn1. n2, n3} > 1, let W be a diagonal tensor, i.e. W = if = j= k and otherwise 0 and let W RM H R Xningna, R E RT T E R Him Xijk, R3.m m 1, Tu.m 1,m (i 1 122n3 + (j 1)m3 + k and otherwise
O. An example of X E 2xxx2 is follows:
A
X X1.11
X112
X
X
0
0
0
0
0
0
0
X2,1,1
X2,12
X2.2,1
X22,2
R2- =
1
00000000000000101111101011011111 0100
[10 0
0
0
Thus X = W x1 H x2 ft x T is a decomposition of for X = (c (c H (2) Xs
(c(T) we have
c2 (|| + | + 11 + 1
W X2 R x2 1 I
X3 T x1 H + W x H x2
=c2 [| + 1 +
2
ft)
18
H + 1 (
(T & T 1-
=02
111 H (1) || + RWW 2)) 11 (
C2
=02 1
(I x1 H + W X2 R W x3 T
C2
For any X E X let W = X/2v2, H = V2I n1 Xn1
R = V21 22 x22 T = 21 xns.
thus
<2
H g + R 0 +
+
W X2 R x3 T
W X3 T x1
H W x1 H X2 X 11))
1 [||
=c2(2n1 + 2m² + 2ma) +
/ +
X
1 +
X (3) 2
C[ g +
x1 H g + W x2 R
W x3 T11
1 X / /44 X 1 / /4 + X
=c2(4ng72 + 4 + 4n2m1)
+
Thus if [ m6 12 + 12271), ) we have
<2( H +
W X2 X3 1
+
W X3 T x1 H + || x1 A x2 R
>02 |
+ 22
- + W X2 R + W x3 r
end the proof.
19

---

C
Experimental details
Datasets
The statisties of the datasets, WN18RR, FB15k-237, YAGO3-10 and Kinship, are shown
in Table
Table 4: The statistics of the datasets.
Dataset
#entity
#relation
#train
#valid
#test
WN18RR
40,943
86,835
3,034
3,134
FB FB15k-237
14,541
237
272,115
17,535
20,466
YGA03-10
123,188
37
1,079,040
5,000
5,000
Kinship
104
8,548
1,069
1,069
Table 5: The settings for total embedding dimension D and number of parts P.
WN18RR
FB15k-237
YAGO3-10
D
P
D
P
D
CP
2000
2000
1000
ComplEx
4000
4000
2000
2
SimplE
4000
4000
2000
2
ANALOGY
4000
4000
2000
QuatE
4000
4000
2000
TuckER
256
256
256
Table 6: The settings for power a and regularization coefficients X4-
WNI8RR
FB15k-237
YAGO3-10
A1
A2
A1
A2
A1
Au
CP
3.0
05
0.07
2.25
0.005
0.07
2.25
0.0007
0.005
ComplEx
3.0
0.05
0.03
2.25
0.005
0.07
2.25
0.0005
0.007
SimplE
3.0
0.03
0.07
2.25
0.005
0.07
2.25
0.0007
0.007
ANALOGY
3.0
0.01
0.07
2.25
0.005
0.07
2.25
0.0007
0.007
QuatE
3.0
0.07
0.03
2.25
0.005
0.05
2.25
0.0005
0.005
TuckER
2.0
0.01
0.03
2.0
0.001
0.01
2.0
0.0003
0.003
Evaluation Metrics MR= 1 EN rank,, where rank, is the rank of ith triplet in the test set and N is the number of the triplets. Lower MR indicates better performance.
= EN I. Higher MRR indicates better performance.
rank,"'
Hits@N + EN I(rank, N), where I(() the indicator function. Hits@ N is the ratio of the ranks that no more than N, Higher Hits @ N indicates better performance.
We use heuristic approach choose the syper-parameters and reduce the computation cost with the help of Hyperopt, a hyper-parameter optimization framework based on TPE [Bersttra al. 201T].
Hyper-parameters
For the hyper Syper-paramettr a, we search for the best a {2.0, 2.25, 2.5, 2.0,,3.0,3... 3.5} with fixed hyper-parameters X; 0.0001.
For the hyper-parameter Àıo we set \₁ = λ and X2 = Aa for all models to reduce the number of
hyper-parameters because we notice that the first row of Eq.(4) H.s [ || + T l
equal to the third row of Eq. W x1 Hit (T..
W X2 Rza +
W Xg Te and the
second row of Eq.
+
TTa
dd
R
Haa is equal to the
20

---

Table 7: The results WN18RR dataset with different
2.0
2.25
2.5
2.75
3.0
3.25
3,5
MRR
0.483
0.486
0.485
0.486
0,494
0.486
0.487
H@@
0,443
0.445
0,441
0.442
0.449
0.443
0,444
@@@ 10
0.556
0.564
0.573
0.572
0.581
0.572
0.570
fourth row of Eq.(4 I X2 Rjd: 1 + I[ X3 Ted: X1 Hadly + I X1 Hid: X2 Rj for CP and ComplEx. We then search the regularization coefficients X and X2 in {0.001, 0.003, 0.005, 0.007, 0.01, 0.03, 0.05, 0.07} for WNI8RR dataset and FB 1513--337 dataset, and search A and 22 in {0.0001, 0.0003, 0.0005, 0.0007, 0.001, 0.003, 0.05, 0.007] for YAGO3-10 dataset. Thus, we need 64 runs for each model to find the best X; To further reduce the number of runs, we use Hyperopt, 2011 to tune syyper-parameten. In our experiments, only need 20 runs to find the best X
optimization framework based on TPE [Brrstrra et al.
We use Adagrad [Duchi et al.] 2011] with learning rate 0.1 the optimizer. We set the batch size to 100 for WN18RR dataset and FB15k-25 5k-237 dataset and 1000 for YAGO3-10 dataset. We train the models for 200 epochs. The settings for total embedding dimension D and number of parts are shown in Table The settings for power a and regularization coefficients X; are shown in Table 6
Random Initialization We run each model three times with different random seeds and report the mean results. We do not report the error bars because our model has very small errors with respect to random initialization. The standard deviations of the results are very small. For example, the standard deviations of MRR, H@1 and H@ 10 of CP model with our regularization are 0.00037784, 0.00084755 and 0. 0.00058739 on WNI8RR dataset, respectively. This indicates that our model not sensitive to the random initialization.
The pyper-parameter a We analyze the impact of the hyper-parameter, the power of the Frobe- nius norm We run experiments WNI8RR dataset with ComplEx model. We set to (2.0, 2.5, 2.75, 3.0, 3.5). See Table 7 for the results.
The results show that the performance generally increases as a increases and then decreases as increases. The best for WNISRR dataset is 3.0. Therefore, we should set more appropriate a value to obtain better performance.
The byper-parameter A We analyze the impact of the aaper-paramete, the regularization coefficient A; We run experiments on WNI8RR dataset with ComplEx model. We set A; to (0.001, 0.003, 0.005, 0.007, 0.01, 0.03, 0.05, 0.07, 0.13. See Table & and Table 9 for the results.
The experimental results show that the model performance first increases and then decreases with the increase of Å₁, without any oscillation. Thus, we can choose suitable regularization coefficients to prevent overfitting while maintaining the expressiveness of TDB models as much as possible.
The Number of Parts P In Section 3.1 expressiveness and computation. Thus, we study the impact of on the model performance. We evaluate the model
show that the number of parts P affect the
WNI8RR dataset. We the total embedding dimension D 256, and set the parts P to {1, 2, 4, 8, 16, 32, 64, 128, 256}. See Table 10 for the results. The time is the AMD Ryzen 7 4800U CPU running time the test set.
The results show that the model performance generally improves and the running time generally increases as P increases. Thus, the larger the part P. the more expressive the model and the more the computation.
A Pseudocode for IVR We present pseudocode of method in Alg. (.
21

---

Table 8: The performance of ComplEx on WN18RR dataset with different X1-
A
0.001
0.003
0.005
0.007
0.01
0.03
0.05
0.07
0.1
MRR
0.473
0,475
0,476
0.476
0,480
0.487
0,491
0,486
0.467
H@@
0.435
0,436
0.436
0.436
0.439
0,442
0.445
0.436
0.411
H@ 10
0.545
0.555
0.555
0.557
0.562
0.576
0.583
0.585
0.570
Table 9: The performance of ComplEx on WN18RR dataset with different A2.
0.001
0.003
0.005
0.007
0.01
0.03
0.05
0.07
0.1
MRR
0.464
0,464
0,464
0.465
0,465
0,467
0,471
0.473
0.472
H@ 1
0.429
0.430
0.430
0.430
0.432
0,432
0.435
0.437
0.435
H@ 10
0.528
0.528
0.529
0.529
0.530
0.536
0.540
0.540
0.540
Table 10:
The results on WNI8RR dataset with different P.
P
2
8
16
32
64
128
256
MRR
0.437
0.449
0.455
0.455
0.463
0.466
0.485
0.497
0.501
H@1
0.405
0.413
0.413
0.415
0.425
0.428
0.446
0.456
0.460
H@
0.499
0.520
0.536
0.533
0.536
0.539
0.565
0.574
0.579
Time
1.971s
2.096s
2.111s
2.145s
2.301s
2.704s
3.520s
6.470s
16.336s
Algorithm A pseudocode for IVR
Input:
Core tensor: W, embeddings: (H, R, T), triplet: (i,j,k)
Regularization coefficients: \y(1 = 1,2,3, 4), the number of parts P. power coefficients:
Output:
Output of model Eq.II X lkk. IVR regularization Eq. 6 reg( (i)k)
1: Initialization: reg == U, Fid == H 22a = Ryd: 3zd Tkd:
2: reg reg d=1 Xı (1
D/P
||a2d 11 + || 1):)
4: dd W X H || + || |1 paa 1 || 1 [
3: reg reg + Σ d=1 )2([|=1al122
D/P
W X2 Ryd: Fag = W X3 Thd:
5: reg reg + _d=1 >a([
D//
|
||
6: & : & id X Ryd F2d == 02 X3 Tha 333 = 3ad X1 Hid:
7: reg reg + Σ d=1 (a || + ||
D/P
8: x = ΣDP Tid X Ted-
9: return: x, reg
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims reflect well the effect of our proposed regularization on knowledge graph completion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We shortly discuss the limitations in the Conclusion Section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
We have provided the detailed assumptions and proofs in the Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have provided the experimental details in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification:
We have provided the code in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/dde/eee Cooeeeoodeesssseeeeeee 7/nips.com / casssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes] (See Appendix C Paragraph "Random Initialization")
Justification:
We have provided the experimental details in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have provided the information about the statistical significance of the experiments in Appendix Paragraph "Random Initialization".
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
25

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the related compute resources in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research complies in all respects with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "9a2LHV8Azk", "reviewer": "Reviewer_8dJT", "summary": "The paper considers the problem of knowledge graph completion where the knowledge graph is encoded as a 3rd-order binary tensor. The authors provide an overview of existing tensor decomposition based models for KGC and propose a unifying general form that enables representing each of these models by choosing the partitioning $P$ and a core tensor $\\boldsymbol{W}$ accordingly. Further, they introduce a novel regularization method called Intermediate Variables Regularization to handle overfitting in TBD models. In contrast to existing regularization approaches, the regularization term combines the norms of intermediate variables of different representations of $\\boldsymbol{X}$ including its unfoldings w.r.t. each mode. Lastly, a theoretical analysis is provided followed by experiments highlighting the efficacy of IVR.", "questions": "- Does the choice of $P$ and $\\boldsymbol{W}$ affect the performance of IVR? If yes, how?\n- The paper states that IVR is applicable to most TDB models. Could you specify to which models it is not (directly) applicable?\n- Are there (theoretical) cases in which IVR is expected to perform worse than existing regularization techniques?\n- The justifications in the checklist are missing.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and organized.\n- The paper addresses an important problem and gives a broad overview of existing solutions. I think the proposed general form will facilitate future research in this research area.\n- It is an intriguing approach to include and combine the norms of several intermediate variables for TDB model regularization.", "weaknesses": "- Currently, the paper starts directly with the main section. I think it would be beneficial to have a small (sub-)section either before or after related work to provide background on, e.g., tensors and CP/Tucker decomposition with one or two illustrating figures, and/or background on how the embedding matrices are usually obtained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.\n\n$\\textbf{Q1:}$ Currently, the paper starts directly with the main section. I think it would be beneficial to have a small (sub-)section either before or after related work to provide background on, e.g., tensors and CP/Tucker decomposition with one or two illustrating figures, and/or background on how the embedding matrices are usually obtained.\n\n$\\textbf{A1:}$ Thank you for your valuable suggestion. We will complement the related backgroud by using the extra page in the revision. You can also refer to [1] for more related backgroud.\n\n[1] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 341 455–500, 2009.\n\n$\\textbf{Q2:}$ Does the choice of $P$ and $\\mathbf{W}$ affect the performance of IVR? If yes, how? \n\n$\\textbf{A2:}$ Yes. We have provided an experiment in Page 22 Paragraph “The number of Parts $P$” to study the impact of $P$ on performance. The results indicate that the performance generally improves and the running time generally increases as $P$ increases.\n\nIt is difficult to theoretically demonstrate how the core tensor $\\mathbf{W}$ affects the performance. When $W$ is a predetermined tensor, as shown in Table 1, varying $\\mathbf{W}$ leads to different performance outcomes. Establishing a clear relationship between IVR performance and $\\mathbf{W}$ from Table 1 is not straightforward.\n\nWhen $\\mathbf{W}$ is a parameter tensor, as discussed in Page 22 Paragraph “The number of Parts $P$”, the performance of IVR generally improves as the size of $\\mathbf{W}$ (or $P$) increases.\n\n$\\textbf{Q3:}$ The paper states that IVR is applicable to most TDB models. Could you specify to which models it is not (directly) applicable? \n\n$\\textbf{A3:}$ As far as we know, IVR is applicable to all exsiting TDB models in knowledge graph completion field. However, we can not guarantee that we know all TDB models, so we claim that IVR is applicable to most TDB models.\n\n$\\textbf{Q4:}$ Are there (theoretical) cases in which IVR is expected to perform worse than existing regularization techniques? \n\n$\\textbf{A4:}$ Since IVR can be reduced to F2 or N3 by setting suitable hyper-parameters, IVR must perform better than F2 and N3. IVR may perform worse than DURA on some datasets or some metrics. For example, MRR metric of ComplEx-IVR is slightly worse than that of ComplEx-DURA on FB15k-237 dataset.\n\n$\\textbf{Q5:}$ The justifications in the checklist are missing.\n\n$\\textbf{A5:}$ We will add the justifications in the revision.", "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": "", "extra_scores": {}}, {"review_id": "tp2TUyzi0y", "reviewer": "Reviewer_fmAK", "summary": "The paper addresses the challenges in Knowledge Graph Completion (KGC) using Tensor Decomposition-Based (TDB) models. The authors present a detailed overview of existing TDB models and establish a general form for these models, which is intended to serve as a foundational platform for further research and enhancement of TDB models. In addition to the new regularization technique, the paper also contributes a theoretical analysis that supports the effectiveness of their method and experimental results that demonstrate its practical utility.", "questions": "1. Could you provide a more detailed explanation or theoretical basis for the division of the tensor decomposition into P parts? What are the implications of different values of P on the model's performance and how do you recommend choosing P for different scenarios?\n\n2. Given that Formula 2 closely resembles a block-term Tucker decomposition, can you elaborate on the specific innovations or unique advantages that your adaptation provides?\n\n3. How generalizable is the IVR method to other types of tensor decomposition models or even outside tensor-based approaches? Are there limitations in its applicability that should be considered?", "limitations": "The paper introduces parameters such as the number of parts (P) in the tensor decomposition but lacks a thorough analysis of how these parameters impact the overall model performance and stability. A deeper examination of the sensitivity of the model to these parameters would strengthen the discussion on limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of Intermediate Variables Regularization (IVR) is a significant original contribution. This new method addresses overfitting in tensor decomposition-based models for knowledge graph completion by focusing on the norms of intermediate variables, which is a novel angle in this field.\n2. The paper also offers a theoretical analysis to support the effectiveness of IVR, presenting a comprehensive mathematical foundation that is not commonly found in many practical applications-focused papers.\n3. The paper is well-organized, with clear sections dedicated to the introduction, methods, theoretical analysis, and experimental results. This structure facilitates easy understanding of the complex concepts discussed.", "weaknesses": "1. While the paper commendably unifies existing KGC methods through a comprehensive mathematical form, it significantly lacks an in-depth discussion on the rationale behind dividing the models into P parts, treating P more as a 'magic' parameter without a clear explanation of its theoretical or practical implications. This could leave readers questioning the basis of choosing a specific value of P and its impact on the model's performance and applicability.\n\n2. Although the paper acknowledges the increase in parameters with the Tucker model, it does not provide a detailed theoretical or empirical analysis of these parameters. A deeper exploration into how these additional parameters affect the model’s complexity, training time, and potential for overfitting could enhance the paper's contribution and provide more actionable insights for readers looking to implement or extend the proposed methods.\n\n3. Eq. 2 is essentially described as a special case of block-term Tucker decomposition where all Tucker's core tensors are consistent. This raises concerns regarding the originality of the design, as it may seem to be a slight variation of existing models rather than a fundamentally new approach. Expanding on how this adaptation provides unique benefits or differs in application from traditional Tucker decompositions could help in strengthening the originality aspect.\n\n4. There is a notable absence of discussion regarding the computational efficiency of the proposed methods. Given that the introduction of IVR and the handling of increased parameters could potentially lead to higher computational costs, it would be beneficial for the paper to address these aspects. Analysis or benchmarks on the computational load compared to other models could provide a clearer picture of the practicality of implementing the proposed methods in real-world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.\n\n$\\textbf{Q1:}$ Could you provide a more detailed explanation or theoretical basis for the division of the tensor decomposition into $P$ parts? What are the implications of different values of $P$ on the model's performance and how do you recommend choosing $P$?\n\n$\\textbf{A1:}$ Due to space constraints, we have to put some content into the appendix. Several of your questions have been addressed there.\n\nAs mentioned from Line 132 to Line 133, the number of parts $P$ determines the dimensions of the dot products of embeddings. If we treat dot product of three vectors with dimension $D/P$ as $D/P$ interactions between three vectors, then Eq.(1) results in $P^3 \\times D/P = DP^2$ interactions. Thus, $P$ can be considered as a hyperparameter that controls the expressiveness of TDB models.\n\nAs discussed from Line 150 to Line 154, the number of parameters in $\\mathbf{W}$ equals $P^3$, and the computational complexity of Eq.(1) is $\\mathcal{O}(DP^2)$. Thus, $P$ is related to expressiveness and computation. We have provided an experiment on Page 22 Paragraph “The number of Parts $P$” to study the impact of $P$ on performance. The results show that the performance generally improves and the running time generally increases as $P$ increases.\n\nTherefore, the choice of $P$ involves a trade-off between expressiveness and computation.\n\n$\\textbf{Q2:}$ Provide a detailed theoretical or empirical analysis of parameters in Eq.(2) and a deeper exploration into how the additional parameters affect the model’s complexity, training time, and potential for overfitting.\n\n$\\textbf{A2:}$ We have analyzed the impact of the parameter tensor $\\mathbf{W}$ on model performance. As stated in Line 150 to Line 154, the number of parameters of $\\mathbf{W}$ is equal to $P^3$ and the computational complexity of Eq.(1) is equal to $\\mathcal{O}(DP^2)$. Table 10 on Page 21 show that the performance generally improves and the running time generally increases as the size of $\\mathbf{W}$ (or $P$) increases. TuckER is a special case of Eq.(2) with $P=D$. The results show that TuckER has the best performance but the longest running time.\n\n$\\textbf{Q3:}$ How Eq.(2) provides unique benefits or differs in application from traditional Tucker decompositions? Given that Eq.(2) closely resembles a block-term Tucker decomposition, can you elaborate on the specific innovations or unique advantages that your adaptation provides?\n\n$\\textbf{A3:}$ The differences between traditional Tucker decomposition models and block-term Tucker decomposition Eq.(2) have been stated in Section 3.1 Paragraph “TuckER and Eq.(2)”. TuckER does not explicitly consider the number of parts $P$ and the core tensor $\\mathbf{W}$, which are pertinent to the number of parameters, computational complexity and logical rules.\n\nEq.(2) reveals the relationship between block-term TuckER decompostions and existing TDB models, which serves as a foundation for further analysis of TDB models. Although block-term Tucker decomposition has been proposed, it has not been introduced into knowledge graph completion (KGC) field. Just like exsiting TDB models only introduces tensor decomposition models into KGC field, they do not propose new tensor decomposition models. Eq.(2) presents a unified view of TDB models and helps the researchers understand the relationship between different TDB models. Moreover, the general form motivates the researchers to propose new methods and establish unified theoretical frameworks that are applicable to most TDB models.\n\nMost of your questions are about Eq.(2). We want to stress that the core contribution of our paper is the intermediate variables regularization rather than Eq.(2). Eq.(2) mainly serves as a foundation of IVR. Thus, we put more content on IVR.\n\n$\\textbf{Q4:}$ Provide an analysis on the computational load compared to other models.\n\n$\\textbf{A4:}$ We discuss the computational efficiency from three aspects.\n\nFirst, the regularization terms only increase the training time. The training time per epoch and MRR metric are shown in the following table. IVR slightly increases the running time but enhances performance.\n\nSecond, we show an approach to choose the hyper-parameters in Paragraph “Hyper-parameters” on Page 20. Our approach requires only a few runs to determine optimal hyper-parameters.\n\nThird, table 10 in Page 21 show that the performance generally improves and the running time generally increases as P increases. Further analysis of other hyper-parameters is provided on Page 22 Paragraph \"The hyper-parameter$\\alpha$\" and Paragraph \"The hyper-parameter$\\lambda_i$\".\n\nTable: The running time and MRR metric of ComplEx model on WN18RR dataset.\n|Model|Time|MRR|\n|-|-|-|\n|ComplEx|36s|0.464|\n|ComplEx-F2|39s|0.467|\n|ComplEx-N3|39s|0.491|\n|ComplEx-DURA|41s|0.484|\n|ComplEx-IVR|44s|0.494|\n\n$\\textbf{Q5:}$ How generalizable is the IVR method to other types of tensor decomposition models or even outside tensor-based approaches? Are there limitations in its applicability that should be considered?\n\n$\\textbf{A5:}$ As far as we are know, all existing TDB models for KGC can be represented by Eq. (2). As stated in the Conclusion section, we intend to explore regularizations that are applicable to other types of KGC models.\n\nOur regularization, IVR, can be directly extended to other types of KGC models such as translation-based models and neural network models by incorporating the intermediate variables in these models.\n\nOne limitation is the challenge of developing a theoretical framework for other types of KGC models. For TDB models, we offer a comprehensive theoretical analysis demonstrating that IVR serves as an upper bound for the overlapped trace norm. Establishing a similar theoretical foundation for other types of models remains challenging.", "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": "", "extra_scores": {}}, {"review_id": "OEl8EsJklE", "reviewer": "Reviewer_gAVe", "summary": "This paper proposes a general framework for tensor decomposition methods on knowledge graph completion. Based on the proposed framework, the authors further introduce a novel regularization method that regularizes the norms of intermediate variables in tensor decomposition. Theoretical analysis demonstrates that regularization on intermediate variables provably upper bounds the original loss, and empirical results on different data sets verify the theoretical analysis and show significant improvements of the proposed method when combined with various knowledge graph completion methods.", "questions": "- Despite the Frobenius norm, can IVR also use other matrix norms (e.g., the spectral norm, though the computation cost may be a problem)? Some additional experiments may be useful to better understand how the proposed regularization affect model training. \n- The captions of table 8 and 9 seem to contain an error. Should these tables be for different data sets?", "limitations": "This paper does not have direct potential negative societal impact from my perspective.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is clearly introduced and easy to understand\n- Theoretical analysis is sound and well supports the proposed method\n- Empirical results on different data sets demonstrate that the proposed method improves upon existing KG completion methods by tensor decomposition models", "weaknesses": "Several detail points about the proposed method are not clear enough", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.\n\n$\\textbf{Q1:}$ Several detail points about the proposed method are not clear enough.\n\n$\\textbf{A1:}$ We will make our statements clearer in the revision.\n\n$\\textbf{Q2:}$ Despite the Frobenius norm, can IVR also use other matrix norms (e.g., the spectral norm, though the computation cost may be a problem)? Some additional experiments may be useful to better understand how the proposed regularization affect model training.\n\n$\\textbf{A2:}$ We choose the Frobenius norm because it can be computed efficiently and is conducive to theoretical analysis. In Section 3.3, we leverage the relationship between the Frobenius norm and the trace norm to demonstrate that IVR serves as an upper bound for the overlapped trace norm of the predicted tensor.\n\nThe spectral norm, with its computational complexity of $\\mathcal{O}(n^3)$, poses challenges for practical computation. Establishing a theoretical framework for alternative norms may also be difficult.\n\nWe have conducted several experiments to show how IVR affect model training.\n\nFirst, in Section 4.4, we verify that minimizing the upper bounds IVR can effectively minimize the overlapped trace norm. Lower values of overlapped trace norm encourage higher correlations among entities and relations, and thus bring a strong constraint for training.\n\nSecond, we analyze the impact of hyper-parameters on model performance in Appendix C. You can refer to the Paragraph \"The hyper-parameter $\\alpha$\", \"The hyper-parameter $\\lambda_{i}$\" and “The Number of Parts $P$” on Page 22.\n\nFurthermore, we add an experiment to demonstrate the effect of IVR on training time. The regularization terms only increase the training time. The training time per epoch and MRR metric are shown in the following table. IVR slightly increases the running time but enhances performance.\n\nTable: The running time and MRR metric of ComplEx model on WN18RR dataset.\n|Model|Time|MRR|\n|-|-|-|\n|ComplEx|36s|0.464|\n|ComplEx-F2|39s|0.467|\n|ComplEx-N3|39s|0.491|\n|ComplEx-DURA|41s|0.484|\n|ComplEx-IVR|44s|0.494|\n\n$\\textbf{Q3:}$ The captions of table 8 and 9 seem to contain an error. Should these tables be for different data sets?\n\n$\\textbf{A3:}$ We will fix the errors in table 8 and table 9 in the revision. Since similar phenomena are observed in results on other datasets, we only present the results for the WN18RR dataset.", "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": "", "extra_scores": {}}, {"review_id": "B6ZFP2BSVa", "reviewer": "Reviewer_YvVe", "summary": "This paper proposes a general model for regularizing a variety of tensor-decomposition-based knowledge graph completion models (based on variants of real / complex CP decomposition, Tucker decomposition, and others). The authors first observe that all of these tensor decomposition models can be expressed as a block-term decomposition of a general dense tensor, with various restrictions placed on the block term core tensors / factor matrices. The authors then use their general tensor model structure to determine necessary (but not sufficient) rank-based conditions on whether a particular knowledge graph model can express symmetry, antisymmetry, and inverse relations. The authors then propose a regularization strategy for this general tensor decomposition model based on the norms of the factor matrices and various intermediate terms that arise when contracting the tensor diagram corresponding to the block term decomposition. The authors evaluate their regularization strategy on three well-known knowledge graph datasets and six different knowledge graph completion models, showing accuracy improvements resulting from their regularization strategy.", "questions": "1. There is an application of Theorem 1 for ComplEX (P=2), and I was able to follow both the proof of the theorem and its application. Can the authors also provide the corresponding analysis for ANALOGY and QuatE? I would like to see this theorem applied for cases P > 2 (and even an example for the case P = 1 would be helpful. I feel as if this theorem becomes more difficult to apply and less practical as the permutation matrix becomes larger. For P = 1, I believe the condition in Theorem 1 is exactly that W is a symmetric tensor. \n\n2. As the authors point out, DistMult forces H = T to enable the model to learn symmetric relations. TuckER is similar. Does Theorem 1 account for such restrictions? It would seem that Theorem 1 in its current form puts no conditions on H and T. \n\n3. Line 197: When you refer to the “asymptotic complexity of Equation 4, I presume this means the cost to compute the expression. Does the cost of computing the derivative of the expression with respect to a single (h, r, t) tuple also remain the same?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The rank-based justification of whether particular knowledge graph models can learn certain logical rules is interesting, since it explores these models from a linear algebraic perspective. The use of the hyperparameter tuner was a good idea as well, given that prior studies have established that careful hyperparameter tuning specifically for knowledge graph completion can significantly boost model performance (https://openreview.net/forum?id=BkxSmlBFvr). The knowledge graph regularization strategy appears to have non-negligible effects on accuracy, and the results are competitive with other state-of-the-art papers reporting results on the FB15K-237, YAGO, and WN18RR datasets. This experiments in this paper seem to suggest that many state of the art knowledge graph models can benefit (in significant ways) from regularization beyond what the literature currently suggests.", "weaknesses": "The utility of Theorem 1 is somewhat unclear to me, given that the proofs of the symmetry / anti-symmetry / inverse properties for individual models such as CP, ComplEX, etc. are sufficiently simple. For example, the fact that that CP decomposition can learn the symmetry rules follows from a single step from the commutativity of the three-vector dot product mentioned in this paper if any pair of arguments is exchanged. The symmetry / anti-symmetry proofs for ComplEX are similar. As the authors point out, the usefulness of Theorem 1 stems from its ability to give a unified proof and to prove whether other, more complex tensor decomposition models could learn such logical rules. Again, in this case, it’s not clear whether applying this rank-based theorem would be simpler than specialized proofs, or would provide any more insight into these models. Although this theorem is interesting by bringing a linear algebraic perspective to the problem, I would like to see a case where this theorem proves a property / gives a result that cannot be derived more simply through other means.\n\nI have a second question about Theorem 1 as it relates to DistMult and TuckER; see below.\n\nThe proposed regularizer has theoretical justification, although it adds a significant number of terms to the loss function. I'm somewhat skeptical about the novelty of the regularization method that arises from tacking on the variety of intermediate terms (while leaving out others), but I also acknowledge that the experiments indicate indicate that there is room for additional progress in knowledge graph model regularization. \n\nThe authors note that this does not increase the asymptotic complexity, but the number of terms added gives me some pause. I would like to see some data about the additional runtime, if any, required in practice by adding these regularization terms. The proposed regularizer appears to improve accuracy in most case, although at what cost in additional computational runtime in practice?\n\nOverall, the experiments in this paper are thorough. I am skeptical about the utility of Theorem 1 and the utility of viewing these models through the lens of a block-term decomposition. The experiments indicate that adding several regularization terms improves the accuracy of tensor completion models in general; this has some novelty in that it shows that knowledge graph models are heavily overparameterized. I would also like to see the runtime impact of adding several non-trivial terms to the loss function, even if the asymptotic complexity does not change.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful and constructive comments. We have addressed the questions that you raised as follows. Please let us know if you have any further concerns.\n\n$\\textbf{Q1:}$ It’s not clear whether applying this rank-based theorem would be simpler than specialized proofs, or would provide any more insight into these models. Although this theorem is interesting by bringing a linear algebraic perspective to the problem, I would like to see a case where this theorem proves a property/gives a result that cannot be derived more simply through other means.\n\n$\\textbf{A1:}$ Theorem 1 transforms the problem of learning logical rules in the TDB model into a linear algebraic problem. By Theorem 1, we only need to calculate the ranks of several matrices. We can calculate ranks through software such as PyTorch and Matlab without manually calculating them.\n\nPrevious proofs of the problem of learning logical rules involved complex algebraic expressions computations, such as those in the paper of QuatE [1], particularly challenging for large $P$. In contrast, matrix operations are generally simpler and can be performed in parallel, making the proofs utilizing Theorem 1 more straightforward and easier than previous proofs, especially for large $P$.\n\nOne potential application of Theorem 1 is to use these conditions as constraints in training to ensure that TDB models are capable of learning logical rules.\n\n [1] Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 2735–2745, 2019.\n\n$\\textbf{Q2:}$ Can the authors also provide the corresponding analysis of Theorem 1 for ANALOGY and QuatE? I would like to see this theorem applied for cases $P>2$. For $P=1$, I believe the condition in Theorem 1 is exactly that $\\mathbf{W}$ is a symmetric tensor. I feel as if this theorem becomes more difficult to apply and less practical as the permutation matrix becomes larger. \n\n$\\textbf{A2:}$\nFor $P=1$, $\\mathbf{W}\\in \\mathbb{R}^{1\\times 1\\times 1}$ is a scalar, then we have that $\\text{rank}(\\mathbf{W}\\_{(2)}^{T}-\\mathbf{S}\\mathbf{W}\\_{(2)}^{T})=0<1=P$, $\\text{rank}(\\mathbf{W}\\_{(2)}^{T}+\\mathbf{S}\\mathbf{W}\\_{(2)}^{T})=1=P$, $\\text{rank}(\\mathbf{W}\\_{(2)}^{T})=\\text{rank}([\\mathbf{W}\\_{(2)},\\mathbf{S}{W}\\_{(2)}^{T}])=1$, thus TDB model with $P=1$ is able to learn the symmetry rules and inverse rules.\n\nFor QuatE with $P=4$, $\\mathbf{W}\\in \\mathbb{R}^{4\\times 4\\times 4}$, then we have that $\\text{rank}(\\mathbf{W}\\_{(2)}^{T}-\\mathbf{S}\\mathbf{W}\\_{(2)}^{T})=3<4=P$, $\\text{rank}(\\mathbf{W}\\_{(2)}^{T}+\\mathbf{S}\\mathbf{W}\\_{(2)}^{T})=1<4=P$, $\\text{rank}(\\mathbf{W}\\_{(2)}^{T})=\\text{rank}([\\mathbf{W}\\_{(2)},\\mathbf{S}\\mathbf{W}\\_{(2)}^{T}])=4$, thus, QuatE is able to learn the symmetry rules, antisymmetry rules and inverse rules. ANALOGY is similar.\n\nThe permutation operation in Theorem 1 can be efficiently computed by permuating the dimensions of $\\mathbf{W}$. For example, we can use the “permuate()” function in PyTorch to compute it.\n\n$\\textbf{Q3:}$ As the authors point out, DistMult forces $\\mathbf{H} = \\mathbf{T}$ to enable the model to learn symmetric relations. TuckER is similar. Does Theorem 1 account for such restrictions? It would seem that Theorem 1 in its current form puts no conditions on $\\mathbf{H}$ and $\\mathbf{T}$.\n\n$\\textbf{A3:}$ Yes. Theorem1 involes the constraint $\\mathbf{H}=\\mathbf{T}$, which mainly aims to reduce overfitting [2]. Existing TDB models for KGC except CP all forces $\\mathbf{H}=\\mathbf{T}$. The proof of Theorem 1 has used this constraint. We may omit some details, leading to such misunderstandings. We add the following steps to make the proof complete.\n\nAccording to the symmetry rules, for any triplet $(i,j,k)$, we have that $f(i,j,k)=f(k,j,i)$, i.e., $f(\\mathbf{H}\\_{i:}, \\mathbf{R}\\_{j:}, \\mathbf{T}\\_{k:})= f(\\mathbf{H}\\_{k:}, \\mathbf{R}\\_{j:}, \\mathbf{T}\\_{i:})= f(\\mathbf{T}\\_{k:}, \\mathbf{R}\\_{j:}, \\mathbf{H}\\_{i:})$ (we use $\\mathbf{H}=\\mathbf{T}$ here). We replace $\\mathbf{H}\\_{i:}$ by $\\mathbf{h}$, replace $\\mathbf{R}\\_{j:}$ by $\\mathbf{r}$, replace $\\mathbf{T}\\_{k:}$ by $\\mathbf{t}$, then we have $f(\\mathbf{h},\\mathbf{r},\\mathbf{t})=f(\\mathbf{t},\\mathbf{r},\\mathbf{h})$, i.e., the first row of the proof of Theorem 1. We will make the proof clearer in the revision.\n\nFor CP model, which does not involve the constraint, we can easily proof that it is able to learn the symmetry rules, antisymmetry rules and inverse rules.\n\n[2] Kadlec, R., Bajgar, O., and Kleindienst, J. Knowledge Base Completion: Baselines Strike Back. In Proceedings of the 2nd Workshop on Representation Learning for NLP, pp. 69–74, 2017.\n\n$\\textbf{Q4:}$ I would like to see some data about the additional runtime, if any, required in practice by adding these regularization terms. The proposed regularizer appears to improve accuracy in most case, although at what cost in additional computational runtime in practice?\n\n$\\textbf{A4:}$ The regularization terms only increase the training time. The training time per epoch and MRR metric are shown in the following table. IVR slightly increases the running time but enhances performance. We also provide the running time regarding hyperparameter $P$ on Page 22.\n\nTable: The running time and MRR metric of ComplEx model on WN18RR dataset.\n|Model|Time|MRR|\n|-|-|-|\n|ComplEx|36s|0.464|\n|ComplEx-F2|39s|0.467|\n|ComplEx-N3|39s|0.491|\n|ComplEx-DURA|41s|0.484|\n|ComplEx-IVR|44s|0.494|\n\n$\\textbf{Q5:}$ Line 197: When you refer to the “asymptotic complexity of Equation 4, I presume this means the cost to compute the expression. Does the cost of computing the derivative of the expression with respect to a single $(h,r,t)$ tuple also remain the same?\n\n$\\textbf{A5:}$ Yes. Since $\\frac{\\partial ||\\mathbf{A}||\\_F^{\\alpha}}{\\partial \\mathbf{A}}=\\alpha ||\\mathbf{A}||\\_F^{\\alpha-2}\\mathbf{A}$, the cost of computing the derivative remains the same.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents an interesting perspective on enhancing Knowledge Graph Completion (KGC) with Tensor Decomposition-Based (TDB) models. During the rebuttal phase, the authors have addressed most of the concerns. After discussing with the SAC, we come to an agreement that the idea of regularizing intermediate variables is novel, and the performance improvements are significant. The community might get inspired by this paper to carry out future research in this direction.

Consequently, I recommend accepting this paper as an poster. Nonetheless, the authors are required to polish the main paper according to their response in the rebuttal phase.
Decision: Accept (poster)