TransINT: Embedding Implication Rules in Knowledge Graphs with Isomorphic Intersections of Linear Subspaces
Year: 2020

Abstract:
Knowledge Graphs (KG), composed of entities and relations, provide a structured representation of knowledge. For easy access to statistical approaches on relational data, multiple methods to embed a KG into f(KG) ∈ R have been introduced. We propose TransINT, a novel and interpretable KG embedding method that isomorphically preserves the implication ordering among relations in the embedding space. Given implication rules, TransINT maps sets of entities (tied by a relation) to continuous sets of vectors that are inclusion-ordered isomorphically to relation implications. With a novel parameter sharing scheme, TransINT enables automatic training on missing but implied facts without rule grounding. On two benchmark datasets, we outperform the best existing state-of-the-art rule integration embedding methods with significant margins in link prediction and triple classification. The angles between the continuous sets embedded by TransINT provide an interpretable way to mine semantic relatedness and implication rules among relations.

heading: 1. Introduction
text: Learning distributed vector representations of multi-relational knowledge is an active area of research [Bordes et al., 2013, Nickel et al., 2011, Kazemi and Poole, 2018a, Wang et al., 2014, Bordes et al., 2011]. These methods map components of a KG (entities and relations) to elements of Rdand capture statistical patterns, regarding vectors close in distance as representing similar concepts. One focus of current research is to bring logical rules to KG embeddings [Guo et al., 2016, Wang et al., 2015a, Wei et al., 2015]. While existing methods impose hard geometric constraints and embed asymmetric orderings of knowledge [Nickel and Kiela, 2017, Vendrov et al., 2015, Vilnis et al., 2018], many of them only embed hierarchy (unary Is a relations), and cannot embed binary or n-ary relations in KG’s. On the other hand, other methods that integrate binary and n-ary rules [Guo et al., 2016, Fatemi et al., 2018, Rocktäschel et al., 2015, Demeester et al., 2016] do not bring significant enough performance gains.
We propose TransINT, a new and extremely powerful KG embedding method that isomorphically preserves the implication ordering among relations in the embedding space. Given pre-defined implication rules, TransINT restricts entities tied by a relation to be
embedded to vectors in a particular region of Rd included isomorphically to the order of relation implication. For example, we map any entities tied by is father of to vectors in a region that is part of the region for is parent of; thus, we can automatically know that if John is a father of Tom, he is also his parent even if such a fact is missing in the KG. Such embeddings are constructed by sharing and rank-ordering the basis of the linear subspaces where the vectors are required to belong.
Mathematically, a relation can be viewed as sets of entities tied by a constraint [Stoll, 1979]. We take such a view on KG’s, since it gives consistency and interpretability to model behavior. We show that angles between embedded relation sets can identify semantic patterns and implication rules - an extension of the line of thought as in word/ image embedding methods such as Mikolov et al. [2013], Frome et al. [2013] to relational embedding.
The main contributions of our work are: (1) A novel KG embedding such that implication rules in the original KG are guaranteed to unconditionally, not approximately, hold. (2) Our model suggests possibilities of learning semantic relatedness between groups of objects. (3) We significantly outperform state-of-the-art rule integration embedding methods, [Guo et al., 2016] and [Fatemi et al., 2018], on two benchmark datasets, FB122 and NELL Sport/ Location.

heading: 2. TransINT
text: In this section, we describe the intuition and justification of our method. We first define relation as sets, and revisit TransH [Wang et al., 2014] as mapping relations to sets in Rd. Finally, we propose TransINT. We put ∗ next to definitions and theorems we propose/ introduce. Otherwise, we use existing definitions and cite them.

heading: 2.1 Sets as Relations
text: We define relations as sets and implication as inclusion of sets, as in set-theoretic logic.
Definition (Relation Set): Let ri be a binary relation and x, y entities. Then, a set Ri such that ri(x, y) if and only if (x, y) ∈ Ri always exists [Stoll, 1979]. We call Ri the relation set of ri.
For example, consider the distinct relations in Figure 1a, and their corresponding sets in Figure 1b; Is Father Of(Tom, Harry) is equivalent to (Tom, Harry) ∈ RIs Father Of.
Definition (Logical Implication): For two relations, r1 implies r2 (or r1 ⇒ r2) iff ∀x, y,
(x, y) ∈ R1 ⇒ (x, y) ∈ R2 or equivalently, R1 ⊂ R2.[Stoll, 1979]
For example, Is Father Of ⇒ Is Parent Of. (In Figure 1b, RIs Father Of ⊂ RIs Parent Of ).
h⊥ +
#»rj ≈
# »
t⊥ (b):
difference first, then projection - first subtracting #» h from #» t , and then projecting the difference ( # » t− h) to His parent of and requiring ( # » t− h)⊥ ≈ rj . All ( # »
t− h)⊥ belong to the red line, which is unique because it is when # »ris parent of is translated to the origin.

heading: 2.2 Background: TransH
text: Given a fact triple (h, rj , t) in a KG (i.e. (Harry, is father of, Tom)), TransH maps each entity to a vector, and each relation rj to a relation-specific hyperplane Hj and a fixed vector #»rj on Hj (Figure 2a). For each fact triple (h, rj , t), TransH wants
# » h⊥ + #»rj ≈ # » t⊥ · · · · · (Eq. 1)
where # » h⊥, # » t⊥ are projections on #» h , #» t onto Hj (Figure 2a).
Revisiting TransH We interpret TransH in a novel perspective. An equivalent way to put Eq.1 is to change the order of subtraction and projection (Figure 2b):
Projection of ( # » t− h) onto Hj ≈ #»rj .
This means that all entity vectors ( #» h , #» t ) such that their difference # »
t− h belongs to the red line are considered to be tied by relation rj (Figure 2b); Rj ≈ the red line, which is the set of all vectors whose projection onto Hj is the fixed vector
#»rj . Thus, upon a deeper look, TransH actually embeds a relation set in KG (figure 1b) to a particular set in Rd. We call such sets relation space for now; in other words, a relation space of some relation ri is the space where each (h, ri, t)’s # »
t− h can exist. We formally visit it later in Section 3.1. Thus, in TransH,
ri(x, y) ≡ (x, y) ∈ Ri (relation in KG) ∼= # »y − x ∈ relation space of ri (relation in Rd)
t− h’s of h, t tied by these relations
can exist. The blue and the red line lie on the green plane - is parent of ’s relation space includes the other two’s.

heading: 2.3 TransINT
text: We propose TransINT, which, given pre-defined implication rules, guarantees isomorphic ordering of relations in the embedding space. Like TransH, TransINT embeds a relation rj to a (subspace, vector) pair (Hj ,
#»rj). However, TransINT modifies the relation embeddings (Hj ,
#»rj) so that the relation spaces (i.e. red line of Figure 2b) are ordered by implication; we do so by intersecting the Hj ’s and projecting the
#»rj ’s (Figure 3a). We explain with familial relations as a running example.
Intersecting the Hj’s TransINT assigns distinct hyperplanesHis father of andHis mother of to is father of and is mother of. However, because is parent of is implied by the aforementioned relations, we assign
His parent of = His father of ∩His mother of . TrainsINT’s His parent of is not a hyperplane but a linear subspace of rank 2 (Figure 3a), unlike in TransH where all Hj ’s are hyperplanes (whose ranks are 1).
Projecting the #»rj’s TransINT constrains the #»rj ’s with projections (Figure 3a’s dotted orange lines). First, # »ris father of and # »ris mother of are required to have the same projection onto His parent of . Second, # »ris parent of is that same projection onto His parent of .
We connect the two above constraints to ordering relation spaces. Figure 3b graphically illustrates that is parent of ’s relation space (green hyperplane) includes those of is father of (blue line) and is mother of (red line). More generally, TransINT requires that
For distinct relations ri, rj , require the following if and only if ri ⇒ rj : Intersection Constraint: Hj = Hi ∩Hj . Projection Constraint: Projection of #»r1 to Hj is #»rj . where # » Hi, # » Hj and #»ri, #»rj are distinct.
We prove that these two constraints guarantee that an ordering isomorphic to implication holds in the embedding space: (ri ⇒ rj) iff (ri’s rel. space ⊂ rj ’s rel. space)
or equivalently, (Ri ⊂ Rj) iff (ri’s rel. space ⊂ rj ’s rel. space) .

heading: 3. TransINT’s Isomorphic Guarantee
text: In this section, we formally state TransINT’s isomorphic guarantee. We denote all d × d matrices with capital letters (e.g. A) and vectors with arrows on top (e.g. #» b ).

heading: 3.1 Projection and Relation Space
text: In Rd, there is a bijection between each linear subspace Hi and a projection matrix Pi; ∀ #»x ∈ Rd, Pix ∈ Hi [Strang, 2006]. A random point #»a ∈ Rd is projected onto Hi iff multiplied by Pi; i.e. Pia = #»
b ∈ Hi. In the rest of the paper, we denote P (or Pi) as the projection matrix onto a linear subspace H (or Hi). Now, we formally define a general concept that subsumes relation space (Figure 3b). Definition∗ (Sol(P, #»
k )) : Let H be a linear subspace and P its projection matrix. Then, given #» k on H, the set of vectors that become #»
k when projected on to H, or the solution space of P #»x = #» k , is denoted as Sol(P, #» k ).
With this definition, relation space (Figure 3b) is (Sol(Pi, #»ri)), where Pi is the projection
matrix of Hi (subspace for relation ri); it is the set of points # » t− h such that Pi( # » t− h) = #»ri.

heading: 3.2 Isomorphic Guarantees
text: Main Theorem 1 (Isomorphism): Let {(Hi, #»ri)}n be the (subspace, vector) embeddings assigned to relations {Ri}n by the Intersection Constraint and the Projection Constraint ; Pi the projection matrix of Hi. Then, ({Sol(Pi, #»ri)}n,⊂) is isomorphic to ({Ri}n,⊂).
In actual optimization, TransINT requires something less strict than Pi( # » t− h) = #»ri:
Pi( # » t− h)− #»ri ≈ #» 0 ≡ ||Pi( # » t− h− #»ri)||2 < ,
for some non-negative and small . This bounds # »
t− h − #»ri to regions with thickness 2 , centered around Sol(Pi,
#»ri) (Figure 4). We prove that isomorphism still holds with this weaker requirement. Definition∗ (Sol (P, k)) : Given any P , the solution space of ||P #»x − #»
k ||2 < (where ≥ 0) is denoted as Sol (P, #» k ). Main Theorem 2 (Margin-aware Isomorphism): ∀ ≥ 0, ({Sol (Pi, #»ri)}n,⊂) is isomorphic to ({Ri}n,⊂).

heading: 4. Initialization and Training
text: The intersection and projection constraints can be imposed with parameter sharing.

heading: 4.1 Parameter Sharing Initializaion
text: From initialization, we bind parameters so that they satisfy the two constraints. For each entity ej , we assign a d-dimensional vector #»ej . To each Ri, we assign (Hi, #»ri) (or (Ai,
#»ri)) with parameter sharing. Please see Appendix B on definitions of head/ parent/ child relations. We first construct the H’s.
Intersection constraint Each subspace H can be uniquely defined by its orthogonal subspace. We define the orthogonal subspace of the H’s top-down. To every head relation
Figure 4: Fig. 3(b)’s relation spaces when Pi( # » t− h)− #»ri ≈ #» 0 ≡ ||Pi( # »
t− h− #»ri)||2 < is required.
(a): Each relation space now becomes regions with thickness , centered around figure 3(b)’s relation space. (b): Relationship of the angle and area of overlap between two relation spaces. With respect to the green region, the nearly perpendicular cylinder overlaps much less with it than the other cylinder with much closer angle.
Rh, assign a d-dimensional vector # »ah as an orthogonal subspace for HRh , making HRh a hyperplane. Then, to each Ri that is not a head, additionally assign a new d-dimensional vector #»ai linearly independent to the bases of all of its parents. Then, Ri’s basis of the orthogonal subspace for HRi becomes [ # »ah, ..., #»ap, #»ai] where # »ah, ...,
#»ap are the vectors assigned to Ri’s parent relations. Projection matrices can be uniquely constructed given the bases [ # »ah, ..., #»ap, #»ai] [Strang, 2006]. Now, we initialize the #»ri’s.
Projection Constraint To the head relation Rh, pick any random xh ∈ Rd and assign #»rh = Phx. To each non-head Ri whose parent is Rp, assign #»ri = #»rp + (I − Pp)(Pi)xi for some random xi. This results in
Pp #»ri = Pp #»rp + Pp(I − Pp)(Pi) #»xi = #»rp + #» 0 = #»rp
for any parent, child pair.
Parameters to be trained Such initialization leaves the following parameters given a KG with entities ej ’s and relations ri’s: (1) a d-dimensional vector (
# »ah) for the head relation, (2) a d-dimensional vector ( #»ai) for each non-head relation, (3) a d-dimensional vector
#»xi for each head and non-head relation, (4) a d-dimensional vector #»ej for each entity ej . TransH and TransINT both assign two d-dimensional vectors for each relation and one d-dimensional vector for each entity; thus, TransINT has the same number of parameters as TransH.

heading: 4.2 Training
text: We construct negative examples (wrong fact triplets) and train with a margin-based loss, following the same protocols as in TransE and TransH.
Training Objective We adopt the same loss function as in TransH. For each fact triplet (h, ri, t), we define the score function
f(h, ri, t) = ||Pi( # »
t− h)− #»ri||2 and train a margin-based loss L:
L = ∑
(h,ri,t)∈G
max(0, f(h, ri, t) 2 + γ − f(h′, r′i, t′)2).
where G is the set of all triples in the KG and (h′, r′i, t ′) is a negative triple made from corrupting (h, ri, t). We minimize this objective with stochastic gradient descent.
Automatic Grounding of Positive Triples Without any special treatment, our initialization guarantees that training for a particular (h, ri, t) also automatically executes training with (h, rp, t) for any ri ⇒ rp, at all times. For example, by traversing (Tom, is father of, Harry) in the KG, the model automatically also traverses (Tom, is parent of, Harry), (Tom, is family of, Harry), even if they are missing in the KG. This is because PpPi = Pp with the given initialization (section 4.1.1) and thus,
f(h, rp, t) = ||Pp( # » t− h)− #»rp||2 2 = ||Pp(Pi(( # » t− h)− #»ri))||2 2
≤ ||(Pp + (I − Pp))Pi(( # » t− h)− #»ri))||2 2 = ||(Pi(( # » t− h)− #»ri))||2 2 = f(h, ri, t)
In other words, training f(h, ri, t) towards less than automatically guarantees training f(h, rp, t) towards less than . This eliminates the need to manually create missing triples that are true by implication rule.

heading: 5. Experiments
text: We evaluate TransINT on two standard benchmark datasets - Freebase 122 [Bordes et al., 2013] and NELL sport/ location [Wang et al., 2015b] and compare against respectively KALE [Guo et al., 2016] and SimplE+ [Fatemi et al., 2018], state-of-the-art methods that integrate rules to KG embeddings, respectively in the trans- and bilinear family. We perform link prediction and triple classification tasks on Freebase 122, and link prediction only on NELL sport/ location (because SimplE+ only reported performance on link prediction). All codes for experiments were implemented in PyTorch [Paszke et al., 2019].1

heading: 5.1 Link Prediction on Freebase 122 and NELL Sport/ Location
text: We compare link prediction results with KALE on Freebase 122 (FB122) and with SimplE+ on NELL Sport/ Location. The task is to predict the gold entity given a fact triple with missing head or tail - if (h, r, t) is a fact triple in the test set, predict h given (r, t) or predict t given (h, r). We follow TransE, KALE, and SimplE+’s protocol. For each test triple (h, r, t), we rank the similarity score f(e, r, t) when h is replaced with e for every entity e in the KG, and identify the rank of the gold head entity h; we do the same for the tail entity t. Aggregated over all test triples, we report for FB 122: (i) the mean reciprocal rank (MRR), (ii) the median of the ranks (MED), and (iii) the proportion of ranks no larger than n (HITS@N) which are the same metrics reported by KALE. For NELL Sport/ Location, we follow the protocol of SimplE+ and do not report MED. A lower MED, and a higher MRR and Hits HITS@N are better.
TransH, KALE, and SimplE+ adopt a “filtered” setting that addresses when entities that are correct, albeit not gold, are ranked before the gold entity. For example, if the gold entity is (Tom, is parent of, John) and we rank every entity e for being the head of (?, is parent of, John), it is possible that Sue, John’s mother, gets ranked before Tom. To avoid
1. Repository for all of our code: https://github.com/SoyeonTiffanyMin/TransINT
this, the “filtered setting” ignores corrupted triplets that exist in the KG when counting the rank of the gold entity. (The setting without this is called the “raw setting”).
TransINT’s hyperparameters are: learning rate (η), margin (γ), embedding dimension (d), and learning rate decay (α), applied every 10 epochs to the learning rate. We find optimal configurations among the following candidates: η ∈ {0.003, 0.005, 0.01}, γ ∈ {1, 2, 5, 10}, d ∈ {50, 100}, α,∈ {1.0, 0.98, 0.95}; we grid-search over each possible (η, γ, d, α/0. We create 100 mini-batches of the training set (following the protocol of KALE) and train for a maximum of 1000 epochs with early stopping based on the best median rank. Furthermore, we try training with and without normalizing each of entity vectors, relation vectors, and relation subspace bases after every batch of training.

heading: 5.1.1 Experiment on Freebase 122
text: We compare our performance with that of KALE and previous methods (TransE, TransH, TransR) that were compared against it, using the same dataset (FB122). FB122 is a subset of FB15K [Bordes et al., 2013] accompanied by 47 implication and transitive rules; it consists of 122 Freebase relations on “people”, “location”, and “sports” topics. Out of the 47 rules in FB122, 9 are transitive rules (e.g. person/nationality(x,y) ∧ country/ official language(y,z) ⇒ person/languages(x,z)) to be used for KALE. However, since TransINT only deals with implication rules, we do not take advantage of them, unlike KALE.
We also put us on some intentional disadvantages against KALE to assess TransINT’s robustness to absence of negative example grounding. In constructing negative examples for the margin-based loss L, KALE both uses rules (by grounding) and their own scoring scheme to avoid false negatives. While grounding with FB122 is not a burdensome task, it known to be very inefficient and difficult for extremely large datasets [Ding et al., 2018]. Thus, it is a great advantage for a KG model to perform well without grounding of training/ test data. We evaluate TransINT on two settings - with and without rule grounding. We call them respectively TransINTG (grounding), TransINTNG (no grounding).
We report link prediction results in Table 1; since we use the same train/ test/ validation sets, we directly copy from Guo et al. [2016] for baselines. While the filtered setting gives better performance (as expected), the trend is generally similar between raw and filtered. TransINT outperforms all other models by large margins in all metrics, even without
grounding; especially in the filtered setting, the Hits@N gap between TransINTG and KALE is around 4∼6 times that between KALE and the best Trans Baseline (TransR).
Also, while TransINTG performs higher than TransINTNG in all settings/metrics, the gap between them is much smaller than the that between TransINTNG and KALE, showing that TransINT robustly brings state-of-the-art performance even without grounding. The results suggest two possibilities in a more general sense. First, the emphasis of true positives could be as important as/ more important than avoiding false negatives. Even without manual grounding, TransINTNG has automatic grounding of positive training instances enabled (Section 4.1.1.) due to model properties, and this could be one of its success factors. Second, hard constraint on parameter structures can bring performance boost uncomparable to that by regularization or joint learning, which are softer constraints.

heading: 5.1.2 Experiment on NELL Sport/ Location
text: We compare TransINT against SimplE+, a state-of-the-art method that outperforms ComplEx [Trouillon et al., 2016] and SimplE [Kazemi and Poole, 2018b], on NELL (Sport/ Location) for link prediction. NELL Sport/ Location is a subset of NELL [Mitchell et al., 2015] accompanied by implication rules - a complete list of them is available in Appendix C. Since we use the same train/ test/ validation sets, we directly copy from Fatemi et al. [2018] for baselines (Logical Inference, SimplE, SimplE+). The results are shown in Table 2. Again, TransINTG and TransinTNG significantly outperform other methods in all metrics. The general trends are similar to the results for FB 122; again, the performance gap between TransINTG and TransINTNG is much smaller than that between TransINTNG and SimplE+.

heading: 5.2 Triple Classification on Freebase 122
text: The task is to classify whether an unobserved instance (h, r, t) is correct or not, where the test set consists of positive and negative instances. We use the same protocol and test set provided by KALE; for each test instance, we evaluate its similarity score f(h, r, t) and classify it as “correct” if f(h, r, t) is below a certain threshold (σ), a hyperparameter to be additionally tuned for this task. We report on mean average precision (MAP), the mean of classification precision over all distinct relations (r’s) of the test instances. We use the same experiment settings/ training details as in Link Prediction other than additionally finding optimal σ. Triple Classification results are shown in Table 3. Again, TransINTG and TransINTNG both significantly outperform all other baselines. We also separately analyze

heading: 6. Semantics Mining with Overlap Between Embedded Regions
text: Traditional embedding methods that map an object (i.e. words, images) to a singleton vector learn soft tendencies between embedded vectors with cosine similarity, or angular distance between two embddings. TransINT extends such a line of thought to semantic relatedness between groups of objects, with angles between relation spaces. In Fig. 4b, one can observe that the closer the angle between two embedded regions, the larger the overlap in area. For entities h and t to be tied by both relations r1, r2, # »
t− h has to belong to the intersection of their relation spaces. Thus, we hypothesize the following over any two relations r1, r2 that are not explicitly tied by the pre-determined rules:
Let V1 be the set of # »
t− h’s in r1’s relation space (denoted as Rel1) and V2 that of r2’s. (1) Angle between Rel1 and Rel2 represents semantic “disjointness” of r1, r2; the more disjoint two relations, the closer their angle to 90◦. When the angle between Rel1 and Rel2 is small, (2) if majority of V1 belongs to the overlap of V1 and V2 but not vice versa, r1 implies r2. (3) if majority of V1 and V2 both belong to their overlap, r1 and r2 are semantically related.
(2) and (3) consider the imbalance of membership in overlapped regions. Exact calculation of this involves specifying an appropriate (Fig. 3). As a proxy for deciding whether an element of V1 (denote v1) belongs in the overlapped region, we can consider the distance
between v1 and its projection to Rel2; the further away v1 is from the overlap, the larger the projected distance. Call the mean of such distances from V1 to Rel2 as d12 and the reverse d21. The imbalance in d12, d21 can be quantified with
1 2( d12 d21 + d21d12 ), which is minimized to 1 when d21 = d12 and increases as d12, d21 are more imbalanced; we call this factor imb.
For hypothesis (1), we verified that the vast majority of relation pairs have angles near to 90◦, with the mean and median respectively 83.0◦ and 85.4◦; only 1% of all relation pairs had angles less than 50◦. We observed that relation pairs with angle less than 20◦ were those that can be inferred by transitively applying the pre-determined implication rules. Relation pairs with angles within the range of [20◦, 60◦] had strong tendencies of semantic relatedness or implication; such tendency drastically weakened past 70◦. Table 4 shows the angle and imb of relations with respect to /people/person/place of birth, whose trend agrees with our hypotheses. Finally, we note that such an analysis could be possible with TransH as well, since their method too maps # »
t− h’s to lines (Fig. 2b). In all of link Prediction, triple classification, and semantics mining, TransINT’s theme of
assigning optimal regions to bound entity sets is unified and consistent. Furthermore, the integration of rules into embedding space geometrically coherent with KG embeddings alone. These two qualities were missing in existing works such as TransE, KALE, and SimplE+.

heading: 7. Related Work
text: Our work is related to two strands of work. The first strand is Order Embeddings [Vendrov et al., 2015] and their extensions [Vilnis et al., 2018, Athiwaratkun and Wilson, 2018], which are significantly limited in that only unary relations and their hierarchies can be modeled. While Nickel and Kiela [2017] also approximately embed unary partial ordering, their focus is on achieving reasonably competent result with unsupervised learning of rules in low dimensions, while ours is achieving state-of-the-art in a supervised setting.
The second strand is those that enforce the satisfaction of common sense logical rules for binary and n-ary relations in the embedded KG. Wang et al. [2015a] explicitly constraints the resulting embedding to satisfy logical implications and type constraints via linear programming, but it only requires to do so during inference, not learning. On the other hand, Guo et al. [2016], Rocktäschel et al. [2015], Fatemi et al. [2018] induce that embeddings follow a set of logical rules during learning, but their approaches involve soft induction instead of hard constraints, resulting in rather insignificant improvements. Our work combines the advantages of both Wang et al. [2015a] and works that impose rules during learning. Finally, Demeester et al. [2016] models unary relations only and Minervini et al. [2017] transitivity only, whose contributions are fundamentally different from us.

heading: 8. Conclusion
text: We presented TransINT, a new KG embedding method such that relation sets are mapped to continuous sets in Rd, inclusion-ordered isomorphically to implication rules. Our method is extremely powerful, outperforming existing state-of-the-art methods on benchmark datasets by significant margins. We further proposed an interpretable criterion for mining semantic similarity and implication rules among sets of entities with TransINT.

heading: Appendix A. Proof For TransINT’s Isomorphic Guarantee
text: Here, we provide the proofs for Main Theorems 1 and 2. We also explain some concepts necessary in explaining the proofs. We put ∗ next to definitions and theorems we propose/ introduce. Otherwise, we use existing definitions and cite them.
A.1 Linear Subspace and Projection
We explain in detail elements of Rd that were intuitively discussed. In this and later sections, we mark all lemmas and definitions that we newly introduce with ∗; those not marked with ∗ are accompanied by reference for proof. We denote all d× d matrices with capital letters (ex) A) and vectors with arrows on top (ex) #» b ).
A.1.1 Linear Subspace and Rank
The linear subspace given by A(x − #»b ) = 0 (A is d × d matrix and b ∈ Rd) is the set of x ∈ Rd that are solutions to the equation; its rank is the number of constraints A(x− #»b ) = 0 imposes. For example, in R3, a hyperplane is a set of #»x = [ x1, x2, x3] ∈ R3 such that ax1 + bx2 + cx3− d = 0 for some scalars a, b, c, d; because vectors are bound by one equation (or its “A” only really contains one effective equation), a hyperplane’s rank is 1 (equivalently rank(A) = 1). On the other hand, a line in R3 imposes to 2 constraints, and its rank is 2 (equivalently rank(A) = 2).
Consider two linear subspaces H1, H2, each given by A1( #»x − #»b1) = 0, A2( #»x − #»
b2) = 0. Then,
(H1 ⊂ H2)⇔ (A1( #»x − #» b1) = 0⇒ A2( #»x − #» b2) = 0)
by definition. In the rest of the paper, denote Hi as the linear subspace given by some Ai( #»x − #»bi) = 0.
A.1.2 Properties of Projection
Invariance For all #»x on H, projecting #»x onto H is still #»x ; the converse is also true. Lemma 1 P #»x = #»x ⇔ #»x ∈ H [Strang].
Orthogonality Projection decomposes any vector #»x to two orthogonal components - P #»x and (I − P ) #»x . Thus, for any projection matrix P , I − P is also a projection matrix that is orthogonal to P (i.e. P (I − P ) = 0) [Strang].
Lemma 2 Let P be a projection matrix. Then I − P is also a projection matrix such that P (I − P ) = 0 [Strang].
The following lemma also follows. Lemma 3 ||P #»x || ≤ ||P #»x + (I − P ) #»x || = || #»x || [Strang].
Projection onto an included space If one subspace H1 includes H2, the order of projecting a point onto them does not matter. For example, in Figure 3, a random point #»a in R3 can be first projected onto H1 at #» b , and then onto H3 at #»
d . On the other hand, it can be first projected onto H3 at #» d , and then onto H1 at still #»
d . Thus, the order of applying projections onto spaces that includes one another does not matter.
If we generalize, we obtain the following two lemmas (Figure 5): Lemma 4∗ Every two subspaces H1 ⊂ H2 if and only if P1P2 = P2P1 = P1. proof) By Lemma 1, if H1 ⊂ H2, then P2 #»x = #»x ∀ #»x ∈ H1. On the other hand, if H1 6⊂ H2, then there is some #»x ∈ H1, #»x 6∈ H2 such that P2 #»x 6= #»x . Thus,
H1 ⊂ H2 ⇔ ∀ #»x ∈ H1, P2 #»x = #»x ⇔ ∀ #»y , P2(P1 #»y ) = P1 #»y ⇔ P2P1 = P1.
Because projection matrices are symmetric [Strang],
P2P1 = P1 = P1 T = P1 TP2 T = P1P2.
Lemma 5∗ For two subspaces H1, H2 and vector #» k ∈ H2,
H1 ⊂ H2 ⇔ Sol(P2, #» k ) ⊂ Sol(P1, P1 #» k ).
proof) Sol(P2, #» k ) ⊂ Sol(P1, P1 #» k ) is equivlaent to ∀ #»x ∈ Rd, P2 #»x = #» k ⇒ P1 #»x = P1 #»
k . By Lemma 4, if H1 ⊂ H2 ⇔ P1P2 = P1. Since #» k ∈ P2, P2 #»x = #» k ⇔ P2(x− #» k ) = #» 0 ⇔
P1(P2 #»x − #»k ) = #»0 ⇔ P1P2 #»x = P1 #» k ⇔ P1 #»x = P1 #» k .
Partial ordering If two subspaces strictly include one another, projection is uniquely defined from lower rank subspace to higher rank subspace, but not the other way around. For example, in Figure 3, a point #»a in R3 (rank 0) is always projected onto H1 (rank 1) at point #» b . Similarly, point #»
b on H1 (rank 1) is always projected onto similarly, onto H3 (order 2) at point d. However, “inverse projection” from H3 to H1 is not defined, because
not only #» b but other points on H1 (such as #» b′ ) project to H3 at point #»
d ; these points belong to Sol(P3, #» d ). In other words, Sol(P1, #» b ) ⊂ Sol(P3, #»
d ). This is the key intuition for isomorphism , which we prove in the next chapter.
A.2 Proof for Isomorphism
Now, we prove that TransINT’s two constraints (section 2.3) guarantee isomorphic ordering in the embedding space.
Two posets are isomorphic if their sizes are the same and there exists an order-preseving mapping between them. Thus, any two posets ({Ai}n,⊂), ({Bi}n,⊂) are isomorphic if |{Ai}n| = |{Bi}n| and ∀i, j Ai ⊂ Aj ⇔ Bi ⊂ Bj Main Theorem 1 (Isomorphism): Let {(Hi, #»ri)}n be the (subspace, vector) embeddings assigned to relations {Ri}n by the Intersection Constraint and the Projection Constraint ; Pi the projection matrix of Hi. Then, ({Sol(Pi, #»ri)}n,⊂) is isomorphic to ({Ri}n,⊂). proof) Since each Sol(Pi, #»ri) is distinct and each Ri is assigned exactly one Sol(Pi, #»ri), |{Sol(Pi, #»ri)}n| = |{Ii}n|. 1 Now, let’s show
∀i, j, Ri ⊂ Rj ⇔ Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj).
Because the ∀i, j, intersection and projection constraints are true iff Ri ⊂ Rj , enough to show that the two constraints hold iff Sol(Pi,
#»ri) ⊂ Sol(Pj , #»rj . First, let’s show Ri ⊂ Ri ⇒ Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj). From the Intersection Constraint, Ri ⊂ Ri ⇒ Hj ⊂ Hi. By Lemma 5, Sol(Pi, #»ri) ⊂ Sol(Pj , Pj #»ri). From the Projection Constraint, #»rj = Pj #»ri. Thus, Sol(Pi, #»ri) ⊂ Sol(Pj , Pj #»ri) = Sol(Pj , #»rj). · · · · ·· 2
Now, let’s show the converse; enough to show that if Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj), then the
intersection and projection constraints hold true.
Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj)
⇔ ∀ #»x , Pi #»x = #»ri ⇒ Pj #»x = #»rj)
If Pi #»x = #»ri,
∀ #»x , PjPi #»x = Pj #»ri ∀ #»x , Pj #»x = #»rj
both have to be true. For any #»x ∈ Hi, or equivalently, if #»x = Pi #»y for some #»y , then the second equation becomes ∀ #»y , PjPi #»y = #»rj , which can be only compatible with the first equation if #»rj = Pj
#»ri, since any vector’s projection onto a subspace is unique. (Projection Constraint)
Now that we know #»rj = Pj #»ri, by Lemma 5, Hi ⊂ Hj (intersection constraint).· · · 3
From 1 , 2 , 3 , the two posets are isomorphic. In actual implementation and training, TransINT requires something less strict than Pi( # »
t− h) = #»ri: Pi( # » t− h)− #»ri ≈ #» 0 ≡ ||Pi( # » t− h− #»ri)||2 < ,
for some non-negative and small . This bounds # »
t− h − #»ri to regions with thickness 2 , centered around Sol(Pi,
#»ri) (Figure 4). We prove that isomorphism still holds with this weaker requirement. Definition∗ (Sol (P, k)) : Given a projection matrix P , we call the solution space of ||P #»x − #»k ||2 < as Sol (P, #»
k ). Main Theorem 2 (Margin-aware Isomorphism): For all non-negative scalars , ({Sol (Pi, #»ri)}n,⊂ ) is isomorphic to ({Ri}n,⊂). proof) Enough to show that ({Sol (Pi, #»ri)}n,⊂) and ({Sol(Pi, #»ri)}n,⊂) are isomorphic for all . First, let’s show
Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj)⇒ Sol (Pi, #»ri) ⊂ Sol (Pj , #»rj).
By Main Theorem 1 and Lemma 4,
Sol(Pi, #»ri) ⊂ Sol(Pj , #»rj)⇔ #»rj = Pj #»ri, Pj = PjPi.
Thus, for all vector #» b ,
Pi(x− #»ri) = #» b
⇔ PjPi( #»x − #»ri) = Pj #» b ⇔ Pj( #»x − #»ri) = Pj #» b (∵ Lemma 4) ⇔ Pj( #»x − #»rj) = Pj #» b (∵ Pj #»rj = #»rj = Pj #»ri)
Thus, if ||Pi( #»x − #»ri)|| < , then ||Pj( #»x − #»rj)|| = ||Pj(Pi( #»x − #»ri))|| < ||Pj(Pi( #»x − #»ri)) + (I − P )(Pi(
#»x − #»ri))|| = ||Pi( #»x − #»ri)|| < . · · · 1 Now, let’s show the converse. Assume ||Pi( #»x − #»ri)|| < for some i. Then,
||Pj( #»x − #»rj)|| = ||Pj( #»x − #»ri) + Pj( #»ri − #»rj)|| = ||Pj(Pi( #»x − #»ri) + (I − Pi)( #»x − #»ri)) + Pj( #»ri − #»rj)|| = ||PjPi( #»x − #»ri) + Pj(I − Pi)( #»x − #»ri) + Pj( #»ri − #»rj)|| ≤ ||PjPi( #»x − #»ri)||+ ||Pj(I − Pi)( #»x − #»ri)||+ ||Pj( #»ri − #»rj)||.
||Pi( #»x − #»ri)|| < bounds ||PjPi( #»x − #»ri)|| to at most epsilon. However, because P , (I − P ) are orthogonal(Lemma 3) it tells nothing of ||(I − Pi)( #»x − #»ri)|| < , and the second term is unbounded.(Figure 5) The third term ||Pj( #»ri − #»rj)|| is unbounded as well, since #»rj can be anything.
Thus, for ||Pi( #»x − #»ri)|| < to bound ||Pj( #»x − #»rj)|| at all for all #»x ,
Pj(I − Pi) = 0, Pj( #»ri − #»rj) = 0
need to hold. By Lemma 4 and 5,
Pj = PjPi ⇔ Hj ⊂ Hi ⇔ Sol(Pi, #»ri) ⊂ Sol(Pj , Pj #»ri) = Sol(Pj , #»rj) · · 2
|{Sol (Pi, #»ri)}n| = |{Sol(Pi, #»ri)}n| holds obviously; each Sol(Pi, #»ri) has a distinct Sol (Pi, #»ri) and each Sol (Pi, #»ri) also has a distinct “center” (Sol(Pi, #»ri)) · · 3
From 1 , 2 , 3 , the two sets are isomorphic.
Appendix B. Definition of ”Head”, ”Parent”, ”Child” relations (section 4.2)
Definition∗ (Parent/ Child Relations): For two relations r1, r2, if r1 ⇒ r2 and there is no r3 such that r1 ⇒ r2 ⇒ r2, then r1 is parent of r2; r2 is child of r1. For example, in Figure 1c of the submitted paper, is family of is is parent of ’s parent. Definition∗ (head): A relation r that has no parent is a head relation. For example, in Figure 1c of the submitted paper, is extended family of is a head relation and its max len is 4.

heading: Appendix C. Explanation on NELL Sport/ Location (section 5)
text: Here are the rules contained in NELL Sport/ Location, copied from [Wang et al., 2015a] and [Fatemi et al., 2018].

Review summaries:
The paper proposes the idea of a new knowledge graph embedding technique that builds on top of TransH and incorporate implication ordering. Results show that it outperforms the previous state-of-the-art method on link prediction and triple classification tasks on FB122. The idea and the new angle of looking at TransH are interesting, but the paper needs lots of revision in terms of clarity and formatting. More experiments could also be included to better show strength.

This work describes a new approach to learn KG embeddings by preserving the "implication ordering" among relations in the embedding space. The paper provides a cute new interpretation of TransH and then uses it to extend TransH to learn entity and relation representations. The crucial novelty of the approach is to map relations into linear subspaces whose parameters are tied using the implication ordering of relations.