Knowledge Graph Completion by Intermediate Variables Regularization

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:58:06

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.

Main paper: 
 introduction: 
 A knowledge graph (KG) can be represented as a 3rd-order binary tensor, in which each entry corresponds to a triplet of the form (head entity, relation, tail entity). A value of 1 denotes a known true triplet, while 0 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 or false values of the missing triplets based on the known ones, i.e., to predict which of the missing entries in the tensor are 1 or 0.A number of models have been proposed for KGC, which can be classified into translation-based models, tensor decomposition-based (TDB) models and neural networks models (Zhang et al., 2021) . We only focus on TDB models in this paper due to their wide applicability and great performance (Lacroix et al., 2018; Zhang et al., 2020) . TDB models can be broadly categorized into two groups: CANDECOMP/PARAFAC (CP) decomposition-based models, including CP (Lacroix et al., 2018) , DistMult (Yang et al., 2014) and ComplEx (Trouillon et al., 2017) , and Tucker decomposition-based models, including SimplE (Kazemi & Poole, 2018) , ANALOGY (Liu et al., 2017) , QuatE (Zhang et al., 2019) and TuckER (Balažević et al., 2019) . To provide a thorough understanding of TDB models, we present a summary of existing models and derive a general form that unifies them, which provides a fundamental basis for further exploration of TDB models. Based on the general form, we show the conditions for TDB model to learn the logical rules.TDB models have been proven to be theoretically fully expressive (Trouillon et al., 2017; Kazemi & Poole, 2018; Balažević et 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., 2014; Trouillon et al., 2017) . Lacroix et al. (2018) proposed another regularization, N3 norm regularization, based on the tensor nuclear p-norm, which outperforms the squared Frobenius norm in terms of performance. Additionally, Zhang et al. (2020) introduced DURA, a regularization technique based on the duality of TDB models and distance-based models that results in significant improvements on benchmark datasets. Nevertheless, N3 and DURA rely on CP decomposition, limiting their applicability to CP (Lacroix et al., 2018) and ComplEx (Trouillon et al., 2017) . As a result, there is a pressing need for a 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 and incorporates the squared Frobenius norm method and N3 norm method, while also ensuring tractable computation. Existing regularization methods for KGC rely on minimizing the norms of embeddings to regularize the model (Yang et 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 a theoretical analysis. We prove that our regularization is an upper bound of the overlapped trace norm (Tomioka et al., 2011) . The overlapped trace norm is the sum of the trace norms of the unfolding matrices along each mode of a tensor (Kolda & Bader, 2009) , which can be considered as a surrogate measure of the rank of a tensor. Thus, the overlapped trace norm reflects the correlation among entities and relations, which can pose a constraint to jointly entities and relations embeddings learning. In specific, entities and relations in KGs are usually highly correlated. For example, some relations are mutual inverse relations, or a relation may be a composition of another two relations (Zhang et al., 2021) . Through minimizing the upper bound of the overlapped trace norm, we encourage a high correlation among entities and relations, which brings strong regularization and alleviates the overfitting problem.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 as a foundation for further TDB model analysis.2. We introduce a new regularization approach for TDB models based on the general form to mitigate the overfitting issue, which is notable for its generality and effectiveness.3. We provide a theoretical proof of the efficacy of our regularization and validate its practical utility through experiments. 
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 extensively 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 decomposition decomposes a tensor into a core tensor and a set of matrices.Several techniques have been developed for applying CP decomposition and Tucker decomposition in KGC. For instance, Lacroix et al. (2018) employed the original CP decomposition, whereas Dist-Mult (Yang et al., 2014) , a variant of CP decomposition, made the embedding matrices of head entities and tail entities identical to simplify the model. SimplE (Kazemi & Poole, 2018) tackled the problem of independence among the embeddings of head and tail entities within CP decomposition.ComplEx (Trouillon et al., 2017) extended DistMult to the complex space to handle asymmetric relations. QuatE (Zhang et al., 2019) explored hypercomplex space to further enhance KGC. Other techniques include HolE (Nickel et al., 2016) proposed by Nickel et al. (2016) , which operates on circular 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ć et al. (2019) introduced TuckER, which is based on the Tucker decomposition and has achieved state-of-the-art performance across various benchmark datasets for KGC. Nickel et al. (2011) proposed a three-way decomposition RESCAL over each relational slice of the tensor. You can refer to (Zhang et al., 2021) or (Ji et al., 2021) for more detailed discussion about KGC models or TDB models.Regularization Although TDB models are highly expressive (Trouillon et al., 2017; Kazemi & 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 a proper tensor norm, as shown by Lacroix et al. (2018) . Therefore, they proposed a novel regularization method, N3, based on the tensor nuclear 3-norm, which is an upper bound of the tensor nuclear norm. Likewise, Zhang et al. (2020) introduced DURA, a regularization method that exploits the duality of TDB models and distance-based models, and serves as an upper bound of the tensor nuclear 2-norm. However, both N3 and DURA are derived from the CP decomposition, and thus are only applicable to CP and ComplEx models. 
methods: 
 In Section 3.1, we begin by providing an overview of existing TDB models and derive a general form for them. Thereafter, we present our intermediate variables regularization (IVR) approach in Section 3.2. Finally, in Section 3.3, we provide theoretical analysis to support the efficacy of our proposed regularization technique.To facilitate the subsequent theoretical analysis, we initially provide a summary of existing TDB models and derive a general form for them. Given a set of entities E and a set of relations R, a KG contains a set of tripletsS = {(i, j, k)} ⊂ E × R × E. Let X ∈ {0, 1} |E|×|R|×|E| represent the KG tensor, with X ijk = 1 iff (i, j, k) ∈ S,where |E| and |R| denote the number of entities and relations, respectively. Let H ∈ R |E|×D , R ∈ R |R|×D and T ∈ R |E|×D be the embedding matrices of head entities, relations and tail entities, respectively, where D is the embedding dimension.Various TDB models can be attained by partitioning the embedding matrices into P parts. We reshapeH ∈ R |E|×D , R ∈ R |R|×D and T ∈ R |E|×D into H ∈ R |E|×(D/P )×P , R ∈ R |R|×(D/P )×Pand T ∈ R |E|×(D/P )×P , respectively, where P is the number of parts we partition. For different P , we can get different TDB models.CP/DistMult Let P = 1, CP (Lacroix et al., 2018) can be represented asX ijk = ⟨H i:1 , R j:1 , T k:1 ⟩ := D/P d=1 H id1 R jd1 T kd1where ⟨•, •, •⟩ is the dot product of three vectors. DistMult (Yang et al., 2014) , a particular case of CP, which shares the embedding matrices of head entities and tail entities, i.e., H = T .ComplEx/HolE Let P = 2, ComplEx (Trouillon et al., 2017) can be represented as Liu et al. (2017) proved that HolE (Nickel et al., 2011) is equivalent to ComplEx. (Liu et al., 2017) can be represented as (Zhang et al., 2019) can be represented asX ijk = ⟨H i:1 , R j:1 , T k:1 ⟩ + ⟨H i:2 , R j:1 , T k:2 ⟩ + ⟨H i:1 , R j:2 , T k:2 ⟩ -⟨H i:2 , R j:2 , T k:1 ⟩SimplE Let P = 2, SimplE (Kazemi & Poole, 2018) can be represented as X ijk = ⟨H i:1 , R j:1 , T k:2 ⟩ + ⟨H i:2 , R j:2 , T k:1 ⟩ ANALOGY Let P = 4, ANALOGYX ijk = ⟨H i:1 , R j:1 , T k:1 ⟩ + ⟨H i:2 , R j:2 , T k:2 ⟩ + ⟨H i:3 , R j:3 , T k:3 ⟩ + ⟨H i:3 , R j:4 , T k:4 ⟩ + ⟨H i:4 , R j:3 , T k:4 ⟩ -⟨H i:4 , R j:4 , T k:3 ⟩ QuatE Let P = 4, QuatEX ijk = ⟨H i:1 , R j:1 , T k:1 ⟩ -⟨H i:2 , R j:2 , T k:1 ⟩ -⟨H i:3 , R j:3 , T k:1 ⟩ -⟨H i:4 , R j:4 , T k:1 ⟩ + ⟨H i:1 , R j:2 , T k:2 ⟩ + ⟨H i:2 , R j:1 , T k:2 ⟩ + ⟨H i:3 , R j:4 , T k:2 ⟩ -⟨H i:4 , R j:3 , T k:2 ⟩ + ⟨H i:1 , R j:3 , T k:3 ⟩ -⟨H i:2 , R j:4 , T k:3 ⟩ + ⟨H i:3 , R j:1 , T k:3 ⟩ + ⟨H i:4 , R j:2 , T k:3 ⟩ + ⟨H i:1 , R j:4 , T k:4 ⟩ + ⟨H i:2 , R j:3 , T k:4 ⟩ -⟨H i:3 , R j:2 , T k:4 ⟩ + ⟨H i:4 , R j:1 , T k:4 ⟩TuckER Let P = D, TuckER (Balažević et al., 2019) can be represented asX ijk = P l=1 P m=1 P n=1 W lmn H i1l R j1m T k1nwhere W ∈ R P ×P ×P is the core tensor.General Form Through our analysis, we observe that all TDB models can be expressed as a linear combination of several dot product. The key distinguishing factors among these models are the choice of the number of parts P and the 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. It is important to note that TuckER uses a parameter tensor as its core tensor, whereas the core tensors of other models are predetermined constant tensors. Therefore, we can derive a general form of these models as XEQUATIONorEQUATIONwhere × n is the mode-n product (Kolda & Bader, 2009) , and W ∈ R P ×P ×P is the core tensor, which can be a parameter tensor or a predetermined constant tensor. The general form Eq.( 2) can also be considered as a sum of D/P TuckER decompositions, which is also called block-term decomposition (De Lathauwer, 2008) . Eq.( 2) is a block-term decomposition with a shared core tensor W . This general form is easy to understand, facilitates better understanding of TDB models and paves the way for further exploration of TDB models.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 P 3 if W is a parameter tensor and otherwise equal to 0. The number of parameters of the embedding matrices is equal to |E|D + |R|D if H = T and otherwise equal to 2|E|D + |R|D. The computational complexity of Eq.( 2) is equal to O(DP 2 |E| 2 |R|). The larger the number of parts P , the more expressive the model and the more the computation. Therefore, the choice of P is a trade-off between expressiveness and computation.TuckER and Eq.( 2) TuckER (Balažević et al., 2019) also demonstrated that TDB models can be represented as a Tucker decomposition by setting specific core tensors W . Nevertheless, we must stress that TuckER does not explicitly consider the number of parts P and the core tensor W , which are pertinent to 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 to learn symmetry rules, antisymmetry rules, and inverse rules.TDB models are theoretically fully expressive (Trouillon et al., 2017; Kazemi & Poole, 2018; Balažević et al., 2019) , which can represent any real-valued tensor. However, TDB models suffer from the overfitting problem in practice (Lacroix et al., 2018) . Therefore, several regularization methods have been proposed, such as squared Frobenius norm method (Yang et al., 2014) and nuclear 3-norm method (Lacroix et al., 2018) , which minimize the norms of 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 X(2) R n2 x (n3n1) X(3) R n3 x (n1n2) X R n1 x n2 x n3Figure 1 : Left shows a 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.a 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.( 2).To compute X in Eq.( 2), we can first compute the intermediate variable W × 1 H :d: × 2 R :d: , and then combine T :d: to compute X. Thus, in addition to minimizing the norm of T :d: , we also need to minimize the norm of W × 1 H :d: × 2 R :d: . Since different ways of computing X can result in different intermediate variables, we fully consider the computing ways of X. Eq.( 2) can also be written as: X = D/P d=1 (W × 2 R :d: × 3 T :d: ) × 1 H :d: or X = D/P d=1 (W × 3 T :d: × 1 H :d: ) × 2 R :d:{∥H :d: ∥ α F , ∥R :d: ∥ α F , ∥T :d: ∥ α F } and {∥W × 1 H :d: × 2 R :d: ∥ α F , ∥W × 2 R :d: × 3 T :d: ∥ α F , ∥W × 3 T :d: × 1 H :d: ∥ α F }, where α 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 of computing X (1) , X (2) and X (3) , where X (n) is the mode-n unfolding of a tensor X (Kolda & Bader, 2009). See Figure 1 for an example of the notation X (n) . We can represent X (1) , X (2) and X (3) as (Kolda & Bader, 2009) :X (1) = D/P d=1 (W × 1 H :d: ) (1) (T :d: ⊗ R :d: ) T , X (2) = D/P d=1 (W × 2 R :d: ) (2) (T :d: ⊗ H :d: ) T X (3) = D/P d=1 (W × 3 T :d: ) (3) (R :d: ⊗ H :d: ) Twhere ⊗ is the Kronecker product. Thus, the intermediate variables include{W × 1 H :d: , W × 2 R :d: , W × 3 T :d: } and {T :d: ⊗ R :d: , T :d: ⊗ H :d: , R :d: ⊗ H :d: }. Therefore, we should mini- mize the (power of Frobenius) norms {∥W × 1 H :d: ∥ α F , ∥W × 2 R :d: ∥ α F , ∥W × 3 T :d: ∥ α F } and {∥T :d: ⊗ R :d: ∥ α F = ∥T :d: ∥ α F ∥R :d: ∥ α F , ∥T :d: ⊗ H :d: ∥ α F = ∥T :d: ∥ α F ∥H :d: ∥ α F , ∥R :d: ⊗ H :d: ∥ α F = ∥R :d: ∥ α F ∥H :d: ∥ α F }. Our Intermediate Variables Regularization (IVR) is defined as a combination of all these norms: reg(X) = D/P d=1 λ 1 (∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + λ 2 (∥T :d: ∥ α F ∥R :d: ∥ α F + ∥T :d: ∥ α F ∥H :d: ∥ α F + ∥R :d: ∥ α F ∥H :d: ∥ α F ) + λ 3 (∥W × 1 H :d: ∥ α F + ∥W × 2 R :d: ∥ α F + ∥W × 3 T :d: ∥ α F ) + λ 4 (∥W × 2 R :d: × 3 T :d: ∥ α F + ∥W × 3 T :d: × 1 H :d: ∥ α F + ∥W × 1 H :d: × 2 R :d: ∥ α F ) (3)where {λ i > 0|i = 1, 2, 3, 4} are the regularization coefficients.In conclusion, our proposed regularization term is the sum of the norms of variables involved in the different ways of computing the tensor X.We can 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.( 3) is as follows:reg(X ijk ) = D/P d=1 λ 1 (∥H id: ∥ α F + ∥R jd: ∥ α F + ∥T kd: ∥ α F ) + λ 2 (∥T kd: ∥ α F ∥R jd: ∥ α F + ∥T kd: ∥ α F ∥H id: ∥ α F + ∥R jd: ∥ α F ∥H id: ∥ α F ) + λ 3 (∥W × 1 H id: ∥ α F + ∥W × 2 R jd: ∥ α F + ∥W × 3 T kd: ∥ α F ) + λ 4 (∥W × 2 R jd: × 3 T kd: ∥ α F + ∥W × 3 T kd: × 1 H id: ∥ α F + ∥W × 1 H id: × 2 R jd: ∥ α F ) (4)The first term of Eq.( 4) corresponds to the squared Frobenius norm when α = 2, and to the N3 norm when α = 3 (Lacroix et al., 2018) . Therefore, IVR generalizes both the squared Frobenius norm method and the N3 norm method. The computational complexity of Eq.( 4) is the same as that of Eq.( 1), i.e., O(DP 2 ), which ensures that our regularization is computationally tractable. The hyper-parameters λ i 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 λ 1 = λ 3 and λ 2 = λ 4 for all models to reduce the number of hyper-parameters. You can refer to Appendix C for more details about the setting of hyper-parameters.We use the same loss function, multiclass log-loss function, as in (Lacroix et al., 2018) . For a training triplet (i, j, k), our loss function isℓ(X ijk ) = -X ijk + log( |E| k ′ =1 exp(X ijk ′ )) + reg(X ijk )At test time, we use X i,j,: to rank tail entities for a query (i, j, ?).To support the effectiveness of our regularization, we provide a deeper theoretical analysis of its properties. Specifically, we prove that our regularization term Eq.( 3) serves as an upper bound for the overlapped trace norm (Tomioka et al., 2011) , which promotes the low nuclear norm of the predicted tensor to regularize the model.The overlapped trace norm for a 3rd-order tensor is defined as:L(X; α) := ∥X (1) ∥ α/2 * + ∥X (2) ∥ α/2 * + ∥X (3) ∥ α/2 *where α is the power coefficient in Eq.(3). ∥X (1) ∥ * , ∥X (2) ∥ * and ∥X (3) ∥ * are the matrix trace norms of X (1) , X (2) and X (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 non-differentiability of matrix rank (Goldfarb & Qin, 2014; Lu et al., 2016; Mu et al., 2014) . Thus, L(X; α) serves as a surrogate for rank(X (1) ) α/2 + rank(X (2) ) α/2 + rank(X (3) ) α/2 , where rank(X (1) ), rank(X (2) ) and rank(X (3) ) are the matrix ranks of X (1) , X (2) and X (3) , respectively. In KGs, each head entity, each relation and each tail entity uniquely corresponds to a row of X (1) , X (2) and X (3) , respectively. Therefore, rank(X (1) ), rank(X (2) ) and rank(X (3) ) 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 a composition of another two relations (Zhang et al., 2021) . Thus, the overlapped trace norm L(X; α) can pose a constraint to jointly entities and relations embeddings learning. Minimizing L(X; α) encourage a high correlation among entities and relations, which brings strong regularization and reduces overfitting. We next establish the relationship between our regularization term Eq.(3) and L(X; α) by Proposition 1 and Proposition 2. We will prove that Eq.( 3) is an upper bound of L(X; α). Proposition 1. For any X, and for any decomposition of X, X = (Bai et al., 2000) , respectively, then there exists a decomposition of X, X =D/P d=1 W × 1 H :d: × 2 R :d: × 3 T :d: , we have 2 λ 1 λ 4 L(X; α) ≤ D/P d=1 λ 1 (∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + λ 4 (∥W × 2 R :d: × 3 T :d: ∥ α F + ∥W × 3 T :d: × 1 H :d: ∥ α F + ∥W × 1 H :d: × 2 R :d: ∥ α F ) (5) If X (1) = U 1 Σ 1 V T 1 , X (2) = U 2 Σ 2 V T 2 , X (3) = U 3 Σ 3 V T 3 are compact singular value decom- positions of X (1) , X (2) , X (3)D/P d=1 W × 1 H :d: × 2 R :d: × 3 T :d:, such that the two sides of Eq.( 5) equal. Proposition 2. For any X, and for any decomposition of X, X =EQUATIONAnd there exists some X ′ , and for any decomposition of X ′ , such that the two sides of Eq.( 6) can not achieve equality.Please refer to Appendix B for the proofs. Proposition 1 establishes that the r.h.s. of Eq.( 5) provides a tight upper bound for 2 √ λ 1 λ 4 L(X; α), while Proposition 2 demonstrates that the r.h.s. of Eq.( 4) is an upper bound of 2 √ λ 2 λ 3 L(X; α), 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.( 5) and the r.h.s. of Eq.( 6). As a result, minimizing Eq.( 3) can effectively minimize L(X; α) 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; α) may not always serve as a tight lower bound of the r.h.s. of Eq.( 5) for TDB models other than TuckER model, it remains a 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 ∥X∥ * is a more tight lower bound. The nuclear 2-norm is defined as follows:∥X∥ * := min{ D d=1 ∥H :d1 ∥ F ∥R :d1 ∥ F ∥T :d1 ∥ F |X = D d=1 W × 1 H :d1 × 2 R :d1 × 3 T :d1 }where W = 1. The following proposition establishes the relationship between ∥X∥ * and L(X; 2): Proposition 3. For any X, and for any decomposition of X, X =D d=1 W × 1 H :d1 × 2 R :d1 × 3 T :d1 , and W = 1, we have 2 λ 1 λ 4 L(X; 2) ≤ 6 λ 1 λ 4 ∥X∥ * ≤ D d=1 λ 1 (∥H :d1 ∥ 2 F + ∥R :d1 ∥ 2 F + ∥T :d1 ∥ 2a F ) + λ 4 (∥W × 2 R :d1 × 3 T :d1 ∥ 2 F + ∥W × 3 T :d1 × 1 H :d1 ∥ 2 F + ∥W × 1 H :d1 × 2 R :d1 ∥ 2 F )Although the r.h.s. of Eq.( 6) is not always a tight upper bound for 2 √ λ 2 λ 3 L(X; α) like the r.h.s. of Eq.( 5), we observe that minimizing the combination of these two bounds, Eq.(3), can lead to better performance. The reason behind this is that the r.h.s. of Eq.( 5) is neither an upper bound nor a lower bound of the r.h.s. of Eq.( 6) for all X. We present Proposition 4 in Appendix B to prove this claim. 
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 C for more experimental details. 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) as CP-F2, CP with N3 method (Lacroix et al., 2018) as CP-N3, CP with DURA method (Zhang et al., 2020) as CP-DURA and CP with IVR method as CP-IVR. The notations for other models are similar to the notations for CP.Evaluation Metrics We use the filtered MRR and Hits@N (H@N) (Bordes et al., 2013) as evaluation metrics and choose the hyper-parameters with the best filtered MRR on the validation set. We run each model three times with different random seeds and report the mean results.See Table 1 for the results. For CP and ComplEx, the models that N3 and DURA are suitable, the results shows that N3 enhances the models more than F2, and DURA outperforms both F2 and N3, leading to substantial improvements. IVR achieve better performance than DURA on WN18RR dataset and achieve similar performance to DURA on FB15k-237 and YAGO3-10 dataset. For SimplE, ANALOGY, QuatE, and TuckER, the improvement offered by F2 is minimal, while IVR significantly boosts model performance on three datasets. Taken together, these results demonstrate the effectiveness and generality of IVR.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) is denoted as IVR-1, model with upper bound Eq.( 6) as IVR-2, and model with upper bound Eq.(3) as IVR. Additionally, the model with regularization coefficients λ i (i = 1, 2, 3, 4) in Eq.( 3) equal is denoted as IVR-3.See Table 2 for the results. We use TuckER as the baseline. IVR with only 1 regularization coefficient, IVR-1, achieves comparable results with vanilla IVR, which shows that IVR can still perform well with fewer hyper-parameters. IVR-1 and outperforms IVR-2 due to the tightness of Eq.( 5). IVR-3 requires fewer hyper-parameters than IVR but still deliver satisfactory results. Thus, choosing which version of IVR to use is a matter of striking a balance between performance and efficiency.We verify that minimizing the upper bounds can effectively minimize L(X; α). L(X; α) can measure the correlation of X. Lower values of L(X; α) encourage higher correlations among entities and relations, and thus bring a strong constraint for regularization. Upon training the models, we compute L(X; α) for the models. As computing L(X; α) for large KGs is impractical, we conduct experiments on a small KG dataset, Kinship (Kok & 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 (Eq.( 3)).See Table 3 for the results. Our results demonstrate that the upper bounds are effective in minimizing L(X; α). All three upper bounds can lead to a decrease of L(X; α), achieving better performance (Table 2 ) by more effective regularization. The L(X; α) 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 most reduction of L(X; α). This finding suggests that combining the two upper bounds can be more effective. Overall, our experimental results confirm the reliability of our theoretical analysis. 
conclusion: 
 In this paper, we undertake an analysis of TDB models in KGC. We first offer a summary of TDB models and derive a general form that facilitates further analysis. TDB models often suffer from the overfitting problem, and thus, we propose a regularization based on our derived general form.It is applicable to most TDB models and incorporates existing regularization methods. We further propose a theoretical analysis to support our regularization. Finally, our empirical analysis demonstrates the effectiveness of our regularization and validates our theoretical analysis. We anticipate that more regularization methods could be proposed in future research, which could apply to other types of models, such as translation-based 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) . 
 
 Appendix: KGs often involve some logical rules to capture inductive capacity (Zhang et al., 2021) . Thus, we 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.( 1). Next, we study how to enable Eq.( 1) to learn logical rules. We first define the symmetry rules, antisymmetry rules and inverse rules. We denote X ijk = f (H i:: , R j:: , T k:: ) as f (h, r, t) for simplicity.A relation r is symmetric if ∀h, t, (h, r, t) ∈ S → (t, r, h) ∈ S. A model is able to learn the symmetry rules if∃r ∈ R D ∧ r ̸ = 0, ∀h, t ∈ R D , f (h, r, t) = f (t, r, h) A relation r is antisymmetric if ∀h, t, (h, r, t) ∈ S → (t, r, h) / ∈ S.A model is able to learn the antisymmetry rules if∃r ∈ R D ∧ r ̸ = 0, ∀h, t ∈ R D , f (h, r, t) = -f (t, r, h) A relation r 1 is inverse to a relation r 2 if ∀h, t, (h, r 1 , t) ∈ S → (t, r 2 , h) ∈ S.A model is able to learn the inverse rules if∀r 1 ∈ R D , ∃r 2 ∈ R D , ∀h, t ∈ R D , f (h, r 1 , t) = f (t, r 2 , h)We restrict r ̸ = 0 because r = 0 will result in f equal to an identically zero function. By choosing different P and W , we can define different TDB models as discussed in Section 3.1. Next, we give a theoretical analysis to establish the relationship between logical rules and TDB models.Theorem 1. Assume a model can be represented as the form of Eq.( 1), then a model is able to learn the symmetry rules iff rank(W T(2) -SW T (2) ) < P . A model is able to learn the antisymmetry rules iff rank(W T(2) + SW T (2) ) < P . A model is able to learn the inverse rules iff rank(W T (2) ) = rank([W T(2) , SW T (2) ]), where S ∈ R P 2 ×P 2 is a permutation matrix with S (i-1)P +j,(j-1)P +i = 1(i, j = 1, 2, . . . , P ) and otherwise 0, [W T(2) , SW T (2) ] is the concatenation of matrix W T (2) and matrix SW T(2) .Proof. According to the symmetry rules:∃r ∈ R D ∧ r ̸ = 0, ∀h, t ∈ R D , f (h, r, t) = f (t, r, h)we have that Therefore, a model is able to learn the symmetry rules iff∃r ∈ R D ∧ r ̸ = 0, P m=1 (W lmn -W nml )r T :m = 0Therefore, the symmetry rule is transformed into a system of linear equations. This system of linear equations have non-zero solution iff rank(W T (2) -SW T (2) ) < P . Thus, a model is able to learn the symmetry rules iff rank(W T(2) -SW T (2) ) < P .Similarly, a model is able to learn the anti-symmetry rules iff rank(W T (2) + SW T (2) ) < P . For the inverse rule:∀r 1 ∈ R D , ∃r 2 ∈ R D , ∀h, t ∈ R D , f (h, r 1 , t) = f (t, r 2 , h)a model is able to learn the symmetry rules iff the following equationW T (2) r 1 = SW T (2) r 2for any r 1 ∈ R D , there exists r 2 ∈ R D such that the equation holds. Thus, the column vectors of W T(2) can be expressed linearly by the column vectors of SW T (2) . Since S is a permutation matrix and S = S T , we have that S 2 = I, thusSW T (2) r 1 = S 2 W T (2) r 2 = W T (2) r 2For any r 1 ∈ R D , there exists r 2 ∈ R D such that the above equation holds. Thus, the column vectors of SW T (2) can be expressed linearly by the column vectors of W T (2) . Therefore, the column space of W T(2) is equivalent to the column space of SW T (2) , thus we haverank(W T (2) ) = rank(SW T (2) ) = rank([W T (2) , SW T (2) ]) Meanwhile, if rank(W T (2) ) = rank([W T (2) , SW T (2) ]), then the columns of W T (2) can be expressed linearly by the columns of SW T(2) , thus∀r 1 ∈ R D , ∃r 2 ∈ R D , W T (2) r 1 = SW T (2) r 2Thus, a model is able to learn the inverse rules iff rank(WT (2) ) = rank([W T (2) , SW T (2) ]).By this theoerm, we only need to judge the relationship between P and the matrix rank about W (2) . ComplEx, SimplE, ANALOGYY and QuatE design specific core tensors to make the models enable to learn the logical rules. We can easily verify that these models satisfy the conditions in this theorem. For example, for ComplEx, we have that P = 2 andW T (2) =    1 0 0 1 0 -1 1 0    , SW T (2) =    1 0 0 -1 0 1 1 0    , [W (2) , SW T (2) ] =    1 0 1 0 0 1 0 -1 0 -1 0 1 1 0 1 0    rank(W T (2) -SW T (2) ) = rank(    0 0 0 2 0 -2 0 0   ) = 1 < P = 2 rank(W T (2) + SW T (2) ) = rank(    2 0 0 0 0 0 2 0   ) = 1 < P = 2 rank(W T (2) ) = rank([W (2) , SW T (2) ]) = 2Thus, ComplEx is able to learn the symmetry rules, antisymmetry rules and inverse rules.To prove the Proposition 1 and Proposition 2, we first prove the following lemma. Lemma 1.∥Z∥ α * = min Z=U V T 1 2 (λ∥U ∥ 2α F + 1 λ ∥V ∥ 2α F )where α > 0, λ > 0 and {Z, U , V } are real matrices. If Z = Û Σ V T is a singular value decomposition of Z, then equality holds for the choiceU = λ -1 2α Û √ Σ and V = λ 1 2αV √ Σ, where √ Σ is the element-wise square root of Σ.Proof. Let the singular value decomposition ofZ ∈ R m×n be Z = Û Σ V T , where Û ∈ R m×r , Σ ∈ R r×r , V ∈ R n×r , r = rank(Z), Û T Û = I r×r and V T V = I r×r . We choose any U , V such that Z = U V T , then we have Σ = Û T U V T V . Moreover, since Û , V have orthogonal columns, ∥ Û T U ∥ F ≤ ∥U ∥ F , ∥ V T V ∥ F ≤ ∥V ∥ F . Then ∥Z∥ α * = Tr(Σ) α = Tr( Û T U V T V ) α ≤ ∥ Û T U ∥ α F ∥V V T ∥ α F ≤ ( √ λ∥U ∥ α F )( 1 √ λ ∥V ∥ α F ) ≤ 1 2 (λ∥U ∥ 2α F + 1 λ ∥V ∥ 2α F )where the first upper bound is Cauchy-Schwarz inequality and the third upper bound is AM-GM inequality.Under review as a conference paper at ICLR 2024Let U = λ -1 2α Û √ Σ and V = λ 1 2α V √ Σ, we have that 1 2 (λ∥U ∥ 2α F + 1 λ ∥V ∥ 2α F ) = 1 2 (∥ Û √ Σ∥ 2α F + ∥ V √ Σ∥ 2α F ) = 1 2 (∥ √ Σ∥ 2α F + ∥ √ Σ∥ 2α F ) = ∥Z∥ α *In summary,∥Z∥ α * = min z=U V T 1 2 (λ∥U ∥ 2α F + 1 λ ∥V ∥ 2α F )Proposition 1. For any X, and for any decomposition of X, X =D/P d=1 W × 1 H :d: × 2 R :d: × 3 T :d: , we have 2 λ 1 λ 4 L(X; α) ≤ D/P d=1 λ 1 (∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + λ 4 (∥W × 2 R :d: × 3 T :d: ∥ α F + ∥W × 3 T :d: × 1 H :d: ∥ α F + ∥W × 1 H :d: × 2 R :d: ∥ α F ) (7) If X (1) = U 1 Σ 1 V T 1 , X (2) = U 2 Σ 2 V T 2 , X (3) = U 3 Σ 3 V T3 are compact singular value decompositions of X (1) , X (2) , X (3) , respectively, then there exists a decomposition of X, X = D/P d=1 W × 1 H :d: × 2 R :d: × 3 T :d: , such that the two sides of Eq.( 5) equal, where P = D,H :1: = λ 1 /λ 4 -1 α U 1 √ Σ 1 , R :1: = λ 1 /λ 4 -1 α U 2 √ Σ 2 , T :1: = λ 1 /λ 4 -1 α U 3 √ Σ 3 , W = λ 1 /λ 4 3 α X × 1 Σ -1 1 U T 1 × 2 Σ -1 2 U T 2 × 3 Σ -1 3 U T 3 . Proof. Let the n-rank (Kolda & Bader, 2009) of X ∈ R n1×n2×n3 be (r 1 , r 2 , r 3 ), then U 1 ∈ R n1×r1 , U 2 ∈ R n2×r2 , U 3 ∈ R n3×r3 , Σ 1 ∈ R r1×r1 , Σ 2 ∈ R r2×r2 , Σ 3 ∈ R r3×r3 , W ∈ R r1×r2×r3 .If X = 0, the above proposition is obviously true, we define 0 -1 := 0 here.For any X ̸ = 0, since X ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + 1 λ (∥W (1) (T :d: ⊗ R :d: ) T ∥ α F + ∥W (2) (T :d: ⊗ H :d: ) T ∥ α F + ∥W (3) (R :d: ⊗ H :d: ) T ∥ α F ) = D/P d=1 λ(∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + 1 λ (∥W × 2 R :d: × 3 T :d: ∥ α F + ∥W × 3 T :d: × 1 H :d: ∥ α F + ∥W × 1 H :d: × 2 R :d: ∥ α F ) Let λ = λ 1 /λ 4 , we have that 2 λ 1 λ 4 L(X; α) ≤ D/P d=1 λ 1 (∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) + λ 4 (∥W × 2 R :d: × 3 T :d: ∥ α F + ∥W × 3 T :d: × 1 H :d: ∥ α F + ∥W × 1 H :d: × 2 R :d: ∥ α F ) Since U T 1 U 1 = I r1×r1 , U T 2 U 2 = I r2×r2 , U T 3 U 3 = I r3×r3 , thus we have X (1) = U 1 U T 1 X (1) , X (2) = U 2 U T 2 X (2) , X (3) = U 3 U T 3 X (3) , then X =X × 1 (U 1 U T 1 ) × 2 (U 2 U T 2 ) × 3 (U 3 U T 3 ) =X × 1 (U 1 Σ 1 Σ -1 1 U T 1 ) × 2 (U 2 Σ 2 Σ -1 2 U T 2 ) × 3 (U 3 Σ 3 Σ -1 3 U T 3 ) =X × 1 Σ -1 1 U T 1 × 2 Σ -1 2 U T 2 × 3 Σ -1 3 U T 3 × 1 U 1 Σ 1 × 2 U 2 Σ 2 × 3 U 3 Σ 3 Let P = D and H :1: = λ 1 /λ 4 -1 α U 1 √ Σ 1 , R :1: = λ 1 /λ 4 -1 α U 2 √ Σ 2 , T :1: = λ 1 /λ 4 -1 α U 3 √ Σ 3 , W = λ 1 /λ 4 3 α X × 1 Σ -1 1 U T 1 × 2 Σ -1 2 U T 2 × 3 Σ -1 3 U T 3 , then X = W × 1 H :1: × 2 R :1: × 3 T :1: is a decomposition of X. Since X (1) = λ 1 /λ 4 -1 α U 1 Σ 1 W (1) (T :1: ⊗ R :1: ) T = U 1 Σ 1 Σ 1 V T 1 X (2) = λ 1 /λ 4 -1 α U 2 Σ 2 W (2) (T :1: ⊗ H :1: ) T = U 2 Σ 2 Σ 2 V T 2 X (3) = λ 1 /λ 4 -1 α U 3 Σ 3 W (3) (R :1: ⊗ H :1: ) T = U 3 Σ 3 Σ 3 V T 3 thus W (1) (T :1: ⊗ R :1: ) T = λ 1 /λ 4 1 α Σ 1 V T 1 W (2) (T :1: ⊗ H :1: ) T = λ 1 /λ 4 1 α Σ 2 V T 2 W (3) (R :1: ⊗ H :1: ) T = λ 1 /λ 4 1 α Σ 3 V T 3 If P = D, we have that D/P d=1 λ 1 (∥H :d: ∥ α F + ∥R :d: ∥ α F + ∥T :d: ∥ α F ) +λ 4 (∥W (1) (T :d: ⊗ R :d: ) T ∥ α F + ∥W (2) (T :d: ⊗ H :d: ) T ∥ α F + ∥W (3) (R :d: ⊗ H :d: ) T ∥ α F ) =λ 1 (∥H :1: ∥ α F + ∥R :1: ∥ α F + ∥T :1: ∥ α F ) +λ 4 (∥W × 2 R :1: × 3 T :1: ∥ α F + ∥W × 3 T :1: × 1 H :1: ∥ α F + ∥W × 1 H :1: × 2 R :1: ∥ α F )) =λ 1 (∥H :1: ∥ α F + ∥R :1: ∥ α F + ∥T :1: ∥ α F ) +λ 4 (∥W (1) (T :1: ⊗ R :1: ) T ∥ α F + ∥W (2) (T :1: ⊗ H :1: ) T ∥ α F + ∥W (3) (R :1: ⊗ H :1: ) T ∥ α F ) = λ 1 λ 4 (∥U 1 Σ 1 ∥ α F + ∥U 2 Σ 2 ∥ α F + ∥U 3 Σ 3 ∥ α F ) + λ 1 λ 4 (∥ Σ 1 V T 1 ∥ α F + ∥ Σ 2 V T 2 ∥ α F + ∥ Σ 3 V T 3 ∥ α F ) = λ 1 λ 4 (∥ Σ 1 ∥ α F + ∥ Σ 2 ∥ α F + ∥ Σ 3 ∥ α F ) + λ 1 λ 4 (∥ Σ 1 ∥ α F + ∥ Σ 2 ∥ α F + ∥ Σ 3 ∥ α F ) = λ 1 λ 4 (∥X (1) ∥ α * + ∥X (2) ∥ α * + ∥X (3) ∥ α * + ∥X (1) ∥ α * + ∥X (2) ∥ α * + ∥X (3) ∥ α * ) =2L(X; α)Proposition 2. For any X, and for any decomposition of X, X, X =EQUATIONAnd there exists some X ′ , and for any decomposition of X ′ , such that the two sides of Eq.( 6) can not achieve equality.Proof. Since X (1) = D/P d=1 (H :d: W (1) )(T :d: ⊗ R :d: ) T , X (2) = D/P d=1 (R :d: W (2) )(T :d: ⊗ H :d: ) T , X (3) = D/P d=1 (T :d: W (3) )(R :d: ⊗ H :d: ) T and for any matrix A, B, ∥A ⊗ B∥ α F = ∥A∥ α F ∥B∥ α F , by applying Lemma 1 to X (1) , X (2) , X (3) , we have that 2L(X; α) ≤ D/P d=1 ∥(H :d: W (1) )(T :d: ⊗ R :d: ) T ∥ α/2 * + ∥(R :d: W (2) )(T :d: ⊗ H :d: ) T ∥ α/2 * + ∥(T :d: W (3) )(R :d: ⊗ H :d: ) T ∥ α/2 * ≤ D/P d=1 λ(∥T :d: ⊗ R :d: ∥ α F + ∥T :d: ⊗ H :d: ∥ α F + ∥R :d: ⊗ H :d: ∥ α F ) + 1 λ (∥H :d: W (1) ∥ α F + ∥R :d: W (2) ∥ α F + ∥T :d: W (3) ∥ α F ) = D/P d=1 λ(∥T :d: ∥ α F ∥R :d: ∥ α F + ∥T :d: ∥ α F ∥H :d: ∥ α F + ∥R :d: ∥ α F ∥H :d: ∥ α F ) + λ(∥W × 1 H :d: ∥ α F + ∥W × 2 R :d: ∥ α F + ∥W × 3 T :d: ∥ α F ) Let λ = λ 2 /λ 3 , we have that 2 λ 2 λ 3 L(X) ≤ D/P d=1 λ 2 (∥T :d: ∥ α F ∥R :d: ∥ α F + ∥T :d: ∥ α F ∥H :d: ∥ α F + ∥R :d: ∥ α F ∥H :d: ∥ α F ) + λ 3 (∥W × 1 H :d: ∥ α F + ∥W × 2 R :d: ∥ α F + ∥W × 3 T :d: ∥ α F ) (9) Let X ′ ∈ R 2×2×2 , X ′ 1,1,1 = X ′ 2,2,2 = 1 and X ′ ijk = 0 otherwise. Then X ′ (1) = X ′ (2) = X ′ (3) = 1 0 0 0 0 0 0 1 Thus rank(X ′ (1) ) = rank(X ′ (2) ) = rank(X ′ (3) ) = 2.In Lemma 1, 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′ (1) ) = rank(T :1: ⊗ R :1: ) = 2, rank(X ′ (2) ) = rank(T :1: ⊗ H :1: ) = 2 rank(X ′ (3) ) = rank(R :1: ⊗ H :1: ) = 2Since for any matrix A, B, rank(A ⊗ B) = rank(A) rank(B), we have that rank(T :1: ) rank(R :1: ) = 2, rank(T :1: ) rank(H :1: ) = 2, rank(R :1: ) rank(H :1: ) = 2The above equations have no non-negative integer solution, thus there is no decomposition ofX ′ such that 2 λ 2 λ 3 L(X) = D/P d=1 λ 2 (∥T :d: ∥ α F ∥R :d: ∥ α F + ∥T :d: ∥ α F ∥H :d: ∥ α F + ∥R :d: ∥ α F ∥H :d: ∥ α F ) + λ 3 (∥W × 1 H :d: ∥ α F + ∥W × 2 R :d: ∥ α F + ∥W × 3 T :d: ∥ α F )Proposition 3. For any X, and for any decomposition of X, X =D d=1 W × 1 H :d1 × 2 R :d1 × 3 T :d1 , we have 2 λ 1 λ 4 L(X; 2) ≤ 6 λ 1 λ 4 ∥X∥ * ≤ D d=1 λ 1 (∥H :d1 ∥ 2 F + ∥R :d1 ∥ 2 F + ∥T :d1 ∥ 2 F ) + λ 4 (∥W × 2 R :d1 × 3 T :d1 ∥ 2 F + ∥W × 3 T :d1 × 1 H :d1 ∥ 2 F + ∥W × 1 H :d1 × 2 R :d1 ∥ 2 F ) where W = 1. Proof. ∀X, let S 1 = {(W , H, R, T )|X = D d=1 W × 1 H :d: × 2 R :d: × 3 T :d: }, S 2 = {(W , H, R, T )|X = D d=1 W × 1 H :d1 × 2 R :d1 × 3 T :d1 , W = 1}. We have that 2 λ 1 λ 4 ( D d=1 ∥H :d1 ∥ F ∥R :d1 ∥ F ∥T :d1 ∥ F ) ≤2( D d=1 λ 4 ∥R :d1 ∥ 2 F ∥T :d1 ∥ 2 F ) 1/2 ( D d=1 λ 1 ∥H :d1 ∥ 2 F ) 1/2 = D d=1 λ 1 ∥H :d1 ∥ 2 F + λ 4 ∥W × 2 R :d: × 3 T :d: ∥ 2 Fwhere W = 1. The equality holds if and only ifλ 4 ∥R :d1 ∥ 2 F ∥T :d1 ∥ 2 F = λ 1 ∥H :d1 ∥ 2 F , i.e., λ 4 /λ 1 ∥R :d1 ∥ 2 ∥T :d1 ∥ 2 = ∥H :d1 ∥ 2 . For a CP decomposition of X, X = D d=1 W × 1 H :d1 × 2 R :d1 × 3 T :d1 , we let H ′ :d1 = ∥R :d1 ∥2∥T :d1 ∥2 ∥H :d1 ∥2 H :i , R ′ :i = ∥H :d1 ∥2 ∥R :d1 ∥2∥T :d1 ∥2 R :i , T ′ :i = T :i if ∥H :d1 ∥ 2 ̸ = 0, ∥R :d1 ∥ 2 ̸ = 0, ∥T :d1 ∥ 2 ̸ = 0 and otherwise H ′ :d = 0, R ′ :d = 0, T ′ :d = 0. Then X = D d=1 W × 1 H ′ :d1 × 2 R ′ :d1 × 3 T ′ :d1 is another CP decomposition of X and ∥R ′ :d1 ∥ 2 ∥T ′ :d1 ∥ 2 = ∥H ′ :d1 ∥ 2 . Thus 2 λ 1 λ 4 ∥X∥ * = min S2 D d=1 λ 1 ∥H :d1 ∥ 2 F + λ 4 ∥W × 2 R :d: × 3 T :d: ∥ 2 F Similarly, we can get 2 λ 1 λ 4 ∥X∥ * = min S2 D d=1 λ 1 ∥R :d1 ∥ 2 F + λ 4 ∥W × 2 T :d: × 3 H :d: ∥ 2 F 2 λ 1 λ 4 ∥X∥ * = min S2 D d=1 λ 1 ∥T :d1 ∥ 2 F + λ 4 ∥W × 2 H :d: × 3 R :d: ∥ 2 FBy Propostion 1, we have that2 λ 1 λ 4 ∥X (1) ∥ * = D d=1 λ 1 ∥H :d1 ∥ 2 F + λ 4 ∥W × 2 R :d: × 3 T :d: ∥ 2 FSince S 2 is a subset of S 1 , we have that∥X (1) ∥ * ≤ ∥X∥ *Similarly, we can prove that ∥X (2) ∥ * ≤ ∥X∥ * and ∥X (3) ∥ * ≤ ∥X∥ * , thus2 λ 1 λ 4 L(X; 2) ≤ 6 λ 1 λ 4 ∥X∥ * ≤ D d=1 λ 1 (∥H :d1 ∥ 2 F + ∥R :d1 ∥ 2 F + ∥T :d1 ∥ 2 F ) + λ 4 (∥W × 2 R :d1 × 3 T :d1 ∥ 2 F + ∥W × 3 T :d1 × 1 H :d1 ∥ 2 F + ∥W × 1 H :d1 × 2 R :d1 ∥ 2 F )Proposition 4. For any X, there exists a decomposition of X =D/P d=1 Ŵ × 1 Ĥ:d: × 2 R:d: × 3 T:d: , such that D/P d=1 λ 1 (∥ Ĥ:d: ∥ α F + ∥ R:d: ∥ α F + ∥ T:d: ∥ α F ) +λ 4 (∥ Ŵ × 2 R:d: × 3 T:d: ∥ α F + ∥ Ŵ × 3 T:d: × 1 Ĥ:d: ∥ α F + ∥ Ŵ × 1 Ĥ:d: × 2 R:d: ∥ α F ) < λ 1 λ 4 / λ 2 λ 3 D/P d=1 λ 2 (∥ T:d: ∥ α F ∥ R:d: ∥ α F + ∥ T:d: ∥ α F ∥ Ĥ:d: ∥ α F + ∥ R:d: ∥ α F ∥ Ĥ:d: ∥ α F ) +λ 3 (∥ Ŵ × 1 Ĥ:d: ∥ α F + ∥ Ŵ × 2 R:d: ∥ α F + ∥ Ŵ × 3 T:d: ∥ α F )Furthermore, for some X, there exists a decomposition of X, X =D/P d=1 Ŵ × 1 Ĥ:d: × 2 R:d: × 3 T:d: , such that D/P d=1 λ 1 (∥ H:d: ∥ α F + ∥ R:d: ∥ α F + ∥ T:d: ∥ α F ) +λ 4 (∥ W × 2 R:d: × 3 T:d: ∥ α F + ∥ W × 3 T:d: × 1 H:d: ∥ α F + ∥ W × 1 H:d: × 2 R:d: ∥ α F ) > λ 1 λ 4 / λ 2 λ 3 D/P d=1 λ 2 (∥ T:d: ∥ α F ∥ R:d: ∥ α F + ∥ T:d: ∥ α F ∥ H:d: ∥ α F + ∥ R:d: ∥ α F ∥ H:d: ∥ α F ) +λ 3 (∥ W × 1 H:d: ∥ α F + ∥ W × 2 R:d: ∥ α F + ∥ W × 3 T:d: ∥ α F )Proof. To simplify the notations, we denote Ĥ:d: as Ĥ, R:d: as R and T:d: as T . To prove the inequality, we only need to proveλ 1 /λ 4 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + λ 4 /λ 1 (∥ Ŵ × 2 R × 3 T ∥ α F + ∥ Ŵ × 3 T × 1 Ĥ∥ α F + ∥ Ŵ × 1 Ĥ × 2 R∥ α F ) > λ 2 /λ 3 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ Ĥ∥ α F + ∥ R∥ α F ∥ Ĥ∥ α F ) + λ 3 /λ 2 (∥ Ŵ × 1 Ĥ∥ α F + ∥ Ŵ × 2 R∥ α F + ∥ Ŵ × 3 T ∥ α F ) Let c 1 = √ λ 1 λ 3 / √ λ 1 λ 3 , for any X, X = D/P d=1 (c -3 1 Ŵ ) × 1 (c 1 Ĥ:d: ) × 2 (c 1 R:d: ) × 3 (c 1 T:d:) is a decomposition of X, thus we only need to provec 2 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ Ŵ × 2 R × 3 T ∥ α F + ∥ Ŵ × 3 T × 1 Ĥ∥ α F + ∥ Ŵ × 1 Ĥ × 2 R∥ α F ) >c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ Ĥ∥ α F + ∥ R∥ α F ∥ Ĥ∥ α F ) + 1 c 2 (∥ Ŵ × 1 Ĥ∥ α F + ∥ Ŵ × 2 R∥ α F + ∥ Ŵ × 3 T ∥ α F )wherec 2 = λ 2 1 λ 3 / λ 2 λ 2 4 . If X ∈ R 1×1×1 , let c = X 2 + 100, Ĥ = R = T = c, Ŵ = X c 3 , we have c 2 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ Ŵ × 2 R × 3 T ∥ α F + ∥ Ŵ × 3 T × 1 Ĥ∥ α F + ∥ Ŵ × 1 Ĥ × 2 R∥ α F ) =c 2 (X 2 + 100) 2 + 1 c 2 X 2 (X 2 + 100) 2 <c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ Ĥ∥ α F + ∥ R∥ α F ∥ Ĥ∥ α F ) + 1 c 2 (∥ Ŵ × 1 Ĥ∥ α F + ∥ Ŵ × 2 R∥ α F + ∥ Ŵ × 3 T ∥ α F ) =c 2 (X 2 + 100) 4 + 1 c 2 X 2 (X 2 + 100) 4For any X ∈ R n1×n2×n3 , max{n 1 , n 2 , n 3 } > 1, let Ŵ be a diagonal tensor, i.e., Ŵi,j,k = 1 if i = j = k and otherwise 0 and letŴ ∈ R n1n2n3×n1n2n3 , Ĥ ∈ R n1×n1n2n3 , R ∈ R n2×n1n2n3 , T ∈ R n3×n1n2n3 , Ĥi,m = X ijk , Rj,m = 1, Tk,m = 1, m = (i -1)n 2 n 3 + (j -1)n 3 + k and otherwise 0. An example of X ∈ R 2×2×2 is as follows: Ĥ = X 1,1,1 X 1,1,2 X 1,2,1 X 1,2,2 0 0 0 0 0 0 0 0 X 2,1,1 X 2,1,2 X 2,2,1 X 2,2,2 R = 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 T = 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 Thus X = Ŵ × 1 Ĥ × 2 R× 3 T is a decomposition of X, for X = (c -3 1 Ŵ )× 1 (c 1 Ĥ)× 2 (c 1 R)× 3 (c 1 T ) we have c 2 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ Ŵ × 2 R × 3 T ∥ α F + ∥ Ŵ × 3 T × 1 Ĥ∥ α F + ∥ Ŵ × 1 Ĥ × 2 R∥ α F ) =c 2 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ Ŵ(1) ( T ⊗ R) T ∥ α F + ∥ Ŵ(2) ( T ⊗ Ĥ) T ∥ α F + ∥ Ŵ(3) ( R ⊗ Ĥ) T ∥ α F ) < 1 c 2 (∥( T ⊗ R) T ∥ α F + ∥( T ⊗ Ĥ) T ∥ α F + ∥( R ⊗ Ĥ) T ∥ α F ) + c 2 (∥ Ĥ∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) =c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ Ĥ∥ α F + ∥ R∥ α F ∥ Ĥ∥ α F ) + 1 c 2 (∥ Ĥ Ŵ(1) ∥ α F + ∥ R Ŵ(2) ∥ α F + ∥ T Ŵ(3) ∥ α F ) =c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ Ĥ∥ α F + ∥ R∥ α F ∥ Ĥ∥ α F ) + 1 c 2 (∥ Ŵ × 1 Ĥ∥ α F + ∥ Ŵ × 2 R∥ α F + ∥ Ŵ × 3 T ∥ α F ) For any X ∈ R n1×n2×n3 , let W = X/2 √ 2, H = √ 2I n1×n1 , R = √ 2I n2×n2 , T = √ 2I n3×n3 , thus c 2 (∥ H∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ W × 2 R × 3 T ∥ α F + ∥ W × 3 T × 1 H∥ α F + ∥ W × 1 H × 2 R∥ α F ) =c 2 (2n 1 + 2n 2 + 2n 3 ) + 1 c 2 (∥X (1) ∥ 2 F /2 + ∥X (2) ∥ 2 F /2 + ∥X (3) ∥ 2 F /2) c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ H∥ α F + ∥ R∥ α F ∥ H∥ α F ) + 1 c 2 (∥ W × 1 H∥ α F + ∥ W × 2 R∥ α F + ∥ W × 3 T ∥ α F ) =c 2 (4n 3 n 2 + 4n 3 n 1 + 4n 2 n 1 ) + 1 c 2 (∥X (1) ∥ 2 F /4 + ∥X (2) ∥ 2 F /4 + ∥X (3) ∥ 2 F /4) Thus if ∥X (1) ∥ 2 F > 16c 2 2 (n 3 n 2 + n 3 n 1 + n 2 n 1 ), we have c 2 (∥ H∥ α F + ∥ R∥ α F + ∥ T ∥ α F ) + 1 c 2 (∥ W × 2 R × 3 T ∥ α F + ∥ W × 3 T × 1 H∥ α F + ∥ W × 1 H × 2 R∥ α F ) >c 2 (∥ T ∥ α F ∥ R∥ α F + ∥ T ∥ α F ∥ H∥ α F + ∥ R∥ α F ∥ H∥ α F ) + 1 c 2 (∥ W × 1 H∥ α F + ∥ W × 2 R∥ α F + ∥ W × 3 T ∥ α F )end the proof.Datasets The statistics of the datasets, WN18, WN18RR, FB15k, FB15k-237, YAGO3-10 and Kinship, are shown in Table 4 . Hits@N = 1 N N i=1 I(rank i ≤ N ), where I(•) is the indicator function. Hits@N is the ratio of the ranks that no more than N , Higher Hits@N indicates better performance.We use a heuristic approach to choose the hyper-parameters and reduce the computation cost with the help of Hyperopt, a hyper-parameter optimization framework based on TPE (Bergstra et al., 2011) .For the hyper-parameter α, we experimentally find that the best value of α depends on the datasets, but not on the models or the values of λ i . Thus, we first search for the best α in {2.0, 2.25, 2.5, 2.75, 3.0, 3.25, 3.5} with fixed hyper-parameters λ i . Tables 6 and Tables 7 show the results of models with different α. The best α for WN18RR dataset is 3.0 and the best α for FB15k-237 dataset and YAGO3-10 dataset is 2.25. Thus, we only need 7 runs for each dataset to find the best value of α.For the hyper-parameter λ i , we set λ 1 = λ 3 and λ 2 = λ 4 for all models to reduce the number of hyper-parameters because we notice that the first row of Eq.( 4)∥H id: ∥ α F + ∥R jd: ∥ α F + ∥T kd: ∥ α F is equal to the third row of Eq.(4) ∥W × 1 H id: ∥ α F + ∥W × 2 R jd: ∥ α F + ∥W × 3 T kd: ∥ α F and the second row of Eq.(4) ∥T kd: ∥ α F ∥R jd: ∥ α F + ∥T kd: ∥ α F ∥H id: ∥ α F + ∥R jd: ∥ α F ∥H id: ∥ α F is equal to the fourth row of Eq.(4) ∥W × 2 R jd: × 3 T kd: ∥ α F + ∥W × 3 T kd: × 1 H id: ∥ α F + ∥W × 1 H id: × 2 R jd: ∥ αF for CP and ComplEx. We then search the regularization coefficients λ 1 and λ 2 in {0.001, 0.003, 0.005, 0.007, 0.01, 0.03, 0.05, 0.07} for WN18RR dataset and FB15k-237 dataset, and search λ 1 and λ 2 in {0.0001, 0.0003, 0.0005, 0.0007, 0.001, 0.003, 0.05, 0.007} for YAGO3-10 dataset. These ranges of hyper-parameters mainly follow the previous work DURA (Zhang et al., 2020) . Thus, we need 64 runs for each model to find the best λ i . To further reduce the number of runs, we use Hyperopt, a hyper-parameter optimization framework based on TPE (Bergstra et al., 2011) , to tune hyper-parameters. In our experiments, we only need 20 runs to find the best values of λ i . In summary, we only need a few runs to achieve good performance.We use Adagrad (Duchi et al., 2011) with learning rate 0.1 as the optimizer. We set the batch size to 100 for WN18RR dataset and FB15k-237 dataset and 1000 for YAGO3-10 dataset. We train the models for 200 epochs. The settings for the total embedding dimension D and the number of parts P are shown in Table 5 . 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.00058739 on WN18RR dataset, respectively. This indicates that our model is not sensitive to the random initialization.The hyper-parameter α We analyze the impact of the hyper-parameter, the power of the Frobenius norm α. We run experiments on WN18RR dataset with ComplEx model. We set α to {2.0, 2.25, 2.5, 2.75, 3.0, 3.25, 3.5}. See Table 6 and Table 7 for the results.The results show that the performance generally increases as α increases and then decreases as α increases. The best α for WN18RR dataset is 3.0 and the best α for FB15k-237 dataset is 2.25. Thus, we should set different values of α for different datasets. The hyper-parameter λ i We analyze the impact of the hyper-parameter, the regularization coefficient λ i . We run experiments on WN18RR dataset with ComplEx model. We set λ i to {0.001, 0.003, 0.005, 0.007, 0.01, 0.03, 0.05, 0.07, 0.1}. See Table 8 and Table 9 for the results.The experimental results show that the model performance first increases and then decreases with the increase of λ i , 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, we show that the number of parts P (number of subspaces) can affect the expressiveness and computation, we study the impact of P on the model performance. We evaluate the model on WN18RR datasets. We set the total embedding dimension D to 256, and set the part 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 on 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.Ablation Study We only conduct experiments with at least two λ i positive in Section 4.3 because these are the cases that have theoretical guarantees from Proposition 1 and Proposition 2. These propositions show that our regularization with at least two λ i positive can be upper bounds of the overlapped trace norm. For completeness, we report the results with only one λ i positive and the others zero in Table 11 . The results indicate that the first, the second and the third terms of our regularization have similar contributions to the model performance. The fourth term has the most contribution because it regularizes the predicted tensor X more directly.A Pseudocode for IVR We present a pseudocode of our method in Alg.(1). Models MRR H@1 H@10 λ1 > 0, λi = 0(i ̸ = 1) 0.454 0.426 0.506 λ2 > 0, λi = 0(i ̸ = 2) 0.451 0.424 0.501 λ3 > 0, λi = 0(i ̸ = 3) 0.454 0.429 0.504 λ4 > 0, λi = 0(i ̸ = 4) 0.477 0.444 0.541Algorithm 1 A pseudocode for IVR Require: Core tensor: W , embeddings: (H, R, T ), triplet: (i, j, k).Regularization coefficients: λ l (l = 1, 2, 3, 4), the number of parts P . power coefficients: α Ensure:Output of model Eq.( 1): X ijk , IVR regularization Eq.( 6): reg(X ijk ) 1: Initialization: reg := 0, x 1d := H id: , x 2d := R jd: , x 3d := T kd: 2: reg := reg + D/P d=1 λ 1 (∥x 1d ∥ α F + ∥x 2d ∥ α F + ∥x 3d ∥ α F ) 3: reg := reg + D/P d=1 λ 2 (∥x 1d ∥ α F ∥x 2d ∥ α F + ∥x 1d ∥ α F ∥x 3d ∥ α F + ∥x 2d ∥ α F ∥x 3d ∥ α F ) 4: x 1d := W × 1 H id: , x 2d := W × 2 R jd: , x 3d := W × 3 T kd: 5: reg := reg + D/P d=1 λ 3 (∥x 1d ∥ α F + ∥x 2d ∥ α F + ∥x 3d ∥ α F ) 6: x 1d := x 1d × 2 R jd: , x 2d := x 2 × 3 T kd: , x 3d := x 3d × 1 H id: 7: reg := reg + D/P d=1 λ 4 (∥x 1d ∥ α F + ∥x 2d ∥ α F + ∥x 3d ∥ α F ) 8: x := D/P d=1 x 1d × 3 T kd: 9: return: x, reg 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - Does the choice of $P$ and $\boldsymbol{W}$ affect the performance of IVR? If yes, how?
- The paper states that IVR is applicable to most TDB models. Could you specify to which models it is not (directly) applicable?
- Are there (theoretical) cases in which IVR is expected to perform worse than existing regularization techniques?
- The justifications in the checklist are missing.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. 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.

4. 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.
questions: 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?

2. 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?

3. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: Several detail points about the proposed method are not clear enough
questions: 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. 
- The captions of table 8 and 9 seem to contain an error. Should these tables be for different data sets?
limitations: limitations: This paper does not have direct potential negative societal impact from my perspective.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

I have a second question about Theorem 1 as it relates to DistMult and TuckER; see below.

The 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. 

The 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?

Overall, 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.
questions: 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. 

2. 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. 

3. 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: limitations: N/A

Comments: title: Thanks for the feedback
Acknowledging your responses
Response Acknowledged
The final day for discussions
The final day for discussions
Responses for Reviewers
comment: Dear reviewers:

We sincerely appreciate your insightful comments and valuable feedback.
Thank you for your response which clarifies my previous concerns. After checking reviews from other reviewers as well as corresponding rebuttal, I would like to keep my score towards acceptance.
I thank the authors for their response. I'm increasing my score to a 5, on the basis of the following: it does seem that even strong knowledge graph models can be improved by regularization, and the rank based analysis is intriguing. I echo the other reviewer's assessment that this framework can be viewed through the lens of a block term decomposition.
Dear reviewer:

Thank you once again for your meticulous comments. As today is the final day for discussions, we kindly request your feedback once more. We anticipate that our brief responses will not require much of your time. Your feedback is invaluable to us, and we eagerly await your response.
Dear reviewer:

Thank you once again for your meticulous comments. As today is the final day for discussions, we kindly request your feedback once more. We anticipate that our brief responses will not require much of your time. Your feedback is invaluable to us, and we eagerly await your response.
Thank you for your response. Based on your feedback, I have decided to raise my score.
I thank the authors for the response. After reading the rebuttal and the other reviews, I will keep my score.
Dear reviewers:

Thanks again for your constructive comments. We appreciate your time and effort in reviewing our paper. Since the final day of discussion is coming, we sincerely look forward to your further feedback. Due to our brief responses, it will not take up too much of your time. If you find that our responses have effectively addressed your concerns, can you give us feedback? Your feedback is crucial to us. We look forward to hearing from you.