On the Representation and Embedding of Knowledge Bases beyond Binary Relations

1 Introduction

The emerging of knowledge bases such as YAGO[Suchanek et al., 2007], DBpedia[Auer et al., 2007] and Freebase[Bollacker et al., 2008] has inspired intense research interest in this area, from completing and improving knowledge bases (e.g., [Baader et al., 2007; Angeli and Manning, 2013]) to developing applications that retrieve information from the knowledge data (e.g., [Marin et al., 2014; Xiong and Callan, 2015a; 2015b]). Recently knowledge base embedding[Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015b; Bordes et al., 2014b; 2011; Socher et al., 2013; Lin et al., 2015a] has stood out as an appealing and generic methodology to access various research problems in this area. Briefly, this methodology sets out to represent entities in a knowledge base as points in some Euclidean space while preserving the structures of the relational data. This approach turns the discrete topology of the relations into a continuous one, enabling the design of efficient algorithms and potentially benefitting many applications. For example, embedding can be applied to link prediction [Bordes et al., 2013] or question answering [Bordes et al., 2014a] in knowledge bases, in which the problems are usually of a combinatorial nature in their original discrete settings.

⇤Corresponding author: zhangrc@act.buaa.edu.cn

Despite their promising successes, existing embedding techniques are all developed based on the assumption that knowledge data are instances of binary relations, namely instances each involving two entities (such as "Beijing is the capital of China"). In reality, however, a large portion of the knowledge data are from non-binary relations (such as "Benedict Cumberbatch played Alan Turing in the movie The Imitation Game"). For example, we observe that in Freebase[Bollacker et al., 2008], more than 1/3 of the entities participate in non-binary relations. This calls for a careful investigation of embedding techniques for knowledge bases containing nonbinary relations.

In this paper, we first present a clean mathematical definition of multi-fold relations, also known as n-ary relation in the literature [Codd, 1970]. Using this notion, we propose a canonical representation for multi-fold (binary or non-binary) relational data, which we call instance representation. Existing knowledge bases usually organize their data using the W3C Resource Description Framework (RDF) [Nickel et al., 2015], in which relational data are represented as a collection of (subject, predicate, object) triples. Although such a triple representation, like the instance representation, is capable of capturing the structures of multi-fold relations [Codd, 1970; Nguyen et al., 2014; Rouces et al., 2015; Grewe, 2010; Krieger and Willms, 2015; W3C, 2016], we show that manipulating multi-fold relational data into triples (as in Freebase) results in an heterogeneity of the predicates, unfavourable for embedding. As such, we advocate that the starting point of embedding multi-fold relations should be recovering the relational data in its instance representation.

We then formulate the embedding problem on the instance representation and suggest that the heart of the problem is modelling each cost function that defines a constraint in the embedding space. We examine the popular FB15K[Bordes et al., 2013] datasets, used in all existing embedding models, and point out that the triple-based data format of FB15K results from applying a particular "star-to-clique" (S2C) conversion procedure to the filtered Freebase data. This procedure can be verified to be irreversible, which causes a loss of structural information in the multi-fold relations.

Interestingly, we discover that all existing embedding models on such S2C-converted datasets can be unified under a "decomposition" modelling framework. In this framework, the cost function associated with a J-fold relation is modelled as the sum of (J2 ) bi-variate functions. Suggesting that the decomposition framework is fundamentally limited, we propose a "direct modelling" framework for embedding multifold relations. As an example in this framework, we generalize TransH[Wang et al., 2014] to a new model for multi-fold relations. Although TransH is known to perform comparably to the best performing models but with lower time complexity, our experiments demonstrate that this new model, designated m-TransH, has even lower complexity, and outperforms TransH by an astonishing margin.

In summary, this paper takes a fundamental look at the knowledge base embedding problem when non-binary relations exist. We advocate the instance representation and the direct modelling framework on such representation. Constrained by the length requirement, we are unable to elaborate at places and certain details are omitted.

2 Multi-Fold Relations and Knowledge Base Representations

2.1 Multi-Fold Relations

A well-known algebraic concept, a binary relation [Hungerford, 2003] on a set N is defined as a subset of the cartesian product N ⇥N, or N 2 . This understanding allows an immediate generalization of binary relation to multi-fold relation (also known as n-ary relation, see, e.g. [Codd, 1970]) where N 2 is replaced with the J-fold cartesian product N J for an arbitrary integer J ≥ 2. From a knowledge base (KB) point of view, we argue however that such algebraic definitions are incomplete, in the sense that the role of each coordinate in the cartesian product is not specified. For example, let R be the binary relation relating a country with its capital city. Then ambiguity exists in whether the instance "Paris is the capital of France" should be written as (Paris↪ France) 2 R or as (France↪ Paris) 2 R. Although this issue is usually resolved by suitable data structures, we now formulate a clean mathematical notion of multi-fold relation which also specifies the roles of involved entities.

Throughout the paper, the following notations will be used. For any set A and B, we denote by BA the set of all functions mapping A to B, as is standard in mathematics [Hungerford, 2003]. For any function g 2 BA and any subset S ✓ A, we use g:S to denote the restriction of function g on S. We will use N to denote the set of all entities in a KB.

A multi-fold relation is then defined as follows. Let M be a set of roles in the KB, and a multi-fold relation, or simply, relation, R on N with roles M is a subset of N M. Given R, we also write the set M as M(R) and call R a J-fold (or J-ary) relation if ♣M(R)♣ = J. The value J is also referred to as the "fold" or "arity" of R. An element t 2 R is called an instance of the relation R.

Example 1 Let R be a 3-fold relation about "which actor played which character in which movie". Then M(R) := ¶ACTOR↪CHARACTER↪MOVIE♦▷ The function t :

M(R) ! N given below is then the instance of R stating "Benedict Cumberbatch played Alan Turing in the movie The Imitation Game":

t(ACTOR)

= BenedictCumberbatch↪

t(CHARACTER) = AlanTuring↪

t(MOVIE) = TheImitationGame▷

2.2 Instance Representation

Let R index a set of distinct multi-fold relations on N . More precisely put, for each r 2 R, there is a relation Rr on N with roles M(Rr). One may identify the index r of Rr with the type of the relation Rr, and in this view, R is a collection of relation types. Let Tr be the set of instances of relation Rr that are included in the KB, then the KB can be specified as (N↪R↪ ¶Tr↪ r 2 R♦). We call such specification an instance representation. Since a KB is usually incomplete, each set Tr is expected to be strictly contained in Rr. As a consequence, relation Rr is in fact unknown, and all information about Rr is revealed via the set Tr, sampled fromRr. Clearly, the instance representation contains all information in the KB pertaining to the structures of the relations and how they interact. Therefore, instance representations are legitimately canonical, at least from the embedding perspective, where only such information matters.

2.3 Fact Representation

For various implementation considerations, practical KBs such as Freebase [Fre, 2016] organize relational data in a different format, the core of which is a notion related to but different from the multi-fold relation we define. We call this notion meta-relation and define it next.

Given a set N of entities and a set M of roles, a (multifold) meta-relation Q on N with roles M is a subset of (2N )M, where 2N is the power set of N. That is, each element in the meta-relation Q, which will be called a fact of Q, is a function mapping M to 2N . Similar to relations, we call Q a J-fold meta-relation if ♣M♣ = J and often write M(Q) in place of M.

Example 2 Let Q be a 3-fold meta-relation about "who played what instruments in the recording of what music piece". The rolesM(Q) consists of RECORDING (i.e., the music piece), INSTRUMENT-ROLE (i.e., the music instrument), and CONTRIBUTOR (i.e., the person).

Let u1 and u2 be two facts of Q, which respectively state "Will McGregor played bass and bass guitar in Precious Things" and "Michael Harrison played violin in Pretty Good Year". As functions in (2N )M(Q) , u1 and u2 are given in Table 1.

For any given meta-relation Q, the number of entities involved in a fact u 2 Q may vary with u in general. Recall that in a J-fold relation, each instance involves exactly J entities. For later reference (in Section 2.6), a meta-relation Q is said to be degenerate if every u 2 Q is such that u(⇢) is a singleton set for every ⇢ 2M(Q).

Parallel to instance representations, one can similarly define the fact representation (N↪Q↪ ¶Uq : q 2 Q♦) for a KB: Q indexes a set ¶Qq : q 2 Q♦ of distinct meta-relations where each Qq is a meta-relation on N with roles M(Qq); and each Uq is a set of facts of Qq.

2.4 Graphical Representations

Both instance representations and fact representations can be associated with an edge-labelled bi-partite graph. For an instance (resp. fact) representation, its associated graph contains two sets of vertices, representing entities and instances (resp. facts) respectively; if an entity is involved in an instance (resp. fact), the corresponding entity vertex is connected to corresponding instance (resp. fact) vertex by an edge, and the edge label is the role of the entity in the instance (resp. fact). The reader is referred to Figures 1 and 2 for examples of such graphical notations. As such, we may sometimes use a graph-theoretic language when speaking of instance or fact representations.

2.5 Converting Facts to Instances

We now show that a fact representation F := (N↪Q↪ ¶Uq : q 2 Q♦) can be converted to an instance representation.

Let N 0 := N [ ⇣Sq2Q Uq ⌘ and let M0 (Q) :=M(Q) [ ¶FACT-ID♦ for any arbitrary meta-relation Q on N. That is, the ID (or name) of each fact in F is regarded as an "entity" and an additional "role" FACT-ID is generated. For any meta-relation Q on N and a fact u 2 Q, let Tid(u) be the set of all distinct functions in N 0M0 (Q) in which each function t maps a role ⇢ 2 M(Q) to an entity in u(⇢) and maps FACT-ID to the ID of the fact u. It is easy to see that Tid(u) contains precisely ∣∣∣Q⇢2M(Q) u(⇢)∣∣∣ functions. For any collection U of facts, let Tid(U) := Su2U Tid(u). Then for any meta-relation Q, Tid(Q) is a subset of N 0M0 (Q) , namely a relation on N 0 with roles M0 (Q).

Lemma 1 F can be recovered from Tid(F).

Denote Tid(F) := (N 0 ↪Q↪ ¶Tid(Uq) : q 2 Q♦). Clearly, Tid(F) is the instance representation of a KB "augmented" from F, where fact ID's in F are added to the entities, and FACT-ID is taken as an additional role.

If one only wishes for an instance representation of F without demanding the recoverability in Lemma 1, a simpler conversion can be defined: for a fact u 2 Q, T(u) := ¶t:M(Q) : t 2 Tid(u)♦. That is, T(u) is similar to Tid but having fact ID dropped. Similarly for any collection U of facts, let T(U) := Su2U T(u). Then for any meta-relation Q, T(Q) is a relation on N with roles M(Q). Denote T(F) := (N↪Q↪ ¶T(Uq) : q 2 Q♦). Then T(F) is an instance representation for F, but F can not be recovered from T(F) in general.

The reader is referred to Table 1 for an example converting a fact to instances using Tid(·) and T(·). Such conversions may also be viewed graphically as shown in Figure 3. Later in our experiments, we will investigate, relative to T (F), whether the fact-level information contained in Tid(F) (namely, that certain instances belong to the same fact) is useful for embedding.

2.6 Freebase

Freebase [Fre, 2016] is a large collaborative KB. The core of Freebase may be understood as a fact representation, con- FACT-ID

taining about 3 billion facts and involving 50 million entities. However, following the RDF [Nickel et al., 2015] format, Freebase organizes its data as a collection of triples, which deviates from the fact representation defined in this paper. Let F denote the underlying fact representation of Freebase. The essential format of Freebase can be obtained by manipulating F as follows.

Using the three kinds of triples, Freebase's data organization is equivalent to the fact representation F. However, the heterogeneity in the triple semantics makes this representation not as clean as the instance or fact representation, at least for embedding purpose.

For each fact in a binary degenerate meta-relation (defined in Section 2.3), apply the S2C conversion (Figure 4) to the fact vertex. This results in a collection of entity-predicateentity triples, which are equivalent to instances of binary relations. The remaining fact vertices are called CVT (Common Value Type) vertices in Freebase. Each labelled edge connected to a CVT vertex is represented as an entity-role-CVT triple. For each meta-relation Qq that is not binary degenerate, Freebase introduces a Mediator vertex to indicate the type q of Qq; then for each fact u 2 Qq, a Mediator-CONTAINSCVT triple is created, where CVT indicates u and Mediator indicates q, and CONTAINS is a fixed global token, independent of u and q, serving to mean u 2 Qq.

Star-to-Clique (S2C) Conversion

On an edge labelled graph G, let (u↪ r↪ v) denote the labelled edge connecting vertices u and v with label r, and let N(v) denote the set of all adjacent vertices of v. Then the star-to-clique conversion on a vertex s is defined by the following procedure.

(1) For every x1↪ x2 2 N(s) forming two labelled edges (x1↪ r1↪ s) and (x2↪ r2↪ s) where r1 6= r2, add a labelled edge (x1↪ r1▷r2↪ x2) to G.

(2) Delete s and all edges connecting to s.

The reader is referred to Figure 5 for an example.

Figure 4: Definition of Star-to-Clique Conversion

3 Embedding

3.1 ProblemFormulation

Instance representations, fact representations, and the RDFbased triple representations (e.g., that in Freebase) may all contain equivalent structural information about the relations contained in a KB. However, instance representations have a uniform semantics comparing with the RDF-based triple representations and are easier to deal with than fact representations. For this reason, we now formulate the KB embedding problem on an instance representation (N↪ R↪ ¶Tr : r 2 R♦).

Let a vector space U over the field R of real numbers be the chosen space for embedding. The objective of KB embedding is to construct a function φ : N ! U and a subset Cr ⇢ U M(Rr) for each relation Rr such that ideally the following properties are satisfied.

1. For every r 2 R and every instance t 2 Rr, φ ◦ t 2 Cr, where the symbol ◦ denotes function composition [Hungerford, 2003].
2. For every r 2 R and every function t 2 N M(Rr) ∩ Rr, φ ◦ t ◁2 Cr.

Here, the function φ, serving as a representation of N, maps an entity to its embedding vector. The subsets ¶Cr : r 2 R♦, serving as a representation of ¶Rr : r 2 R♦, define a set of constraints on the embedding vectors which preserve the intra-relational and inter-relational structures of ¶Rr : r 2 R♦.

Note that each constraint Cr may be identified with a nonnegative cost function fr : U M(Rr) !R such that

Denote ⇥ := ¶fr : r 2 R♦. The problem then translates to determining (⇥↪ φ). But ¶Rr : r 2 R♦ is unknown, and all we have is the observed instances ¶Tr : r 2 R♦ and possibly some "negative examples" ¶T - r : r 2 R♦, where each T - r ⇢ N M(Rr) ∩ Rr. Note that when the KB is large, for any t 2 Tr, if we replace its value t(⇢) for some role ⇢ 2 M(Rr) with a random entity, the resulting function falls in N M(Rr) ∩ Rr with high probability. This can be used to construct T - r ([Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015b]).

Treating the problem as learning (⇥↪ φ), we may not need the property 1 above to hold strictly. Then the equality "= 0"

in (1) is taken as "as close to 0 as possible". Towards a margin-based optimization formulation (which gives better discriminative power and robustness), the threshold 0 in (2) is raised to a positive value c. The problem can then be formulated as finding (⇥↪ φ) to minimize the following global cost function.

where [·]+ denotes the rectifier function [Glorot et al., 2011], namely, [a]+ :=max(0↪ a).

What remains is to choose a proper space of ⇥ for this optimization problem, which is at the heart of modelling.

3.2 FB15KDatasets

A popular dataset for training and testing embedding models is the FB15K datasets [Bordes et al., 2013], filtered from Freebase. When viewing Freebase as an edge-labelled graph (i.e., every triple as an labelled edge), we observe that to every CVT vertex in the filtered data, FB15K has applied the S2C conversion (Figure 4).

Lemma 2 After applying S2C conversions to a graph G, in general, G is no longer recoverable.

This suggests a loss of structural information in this conversion. Working with this dataset, for which the original fact or instance representation is no longer recoverable, one is left with no option for embedding multi-fold relations but to treat the triples as instances of binary relations. In addition, we observe that the S2C conversions applied in FB15K have also involved the Mediator vertices connected to the CVTs. This results in each Mediator vertex in FB15K connecting to a good number of entity vertices. This connectivity provides no information about the structures of the relations, arguably only serving as "noise" for embedding. For these reasons and since we want to work with multi-fold relational data in their intact form, FB15K no longer suits our purpose.

3.3 Prior Art of Modelling

To date, well-known models developed for KB embedding include TransE [Bordes et al., 2013], TransH[Wang et al., 2014], TransR [Lin et al., 2015b], the Unstructured Model (UE) [Bordes et al., 2014b], the Structure Embedding Model [Bordes et al., 2011], the Neural Tensor Network model[Socher et al., 2013] and the Single Layer Model[Socher et al., 2013]. All these models deal with datasets in a triple representation (such as FB15K) and treat each triple as an instance of a binary relation. This treatment is equivalent to regarding the triple representation as an instance representation where each relation Rr is binary. Consequently, each cost function fr may be regarded as a function on U 2 . For example, in TransH, the function fr is defined by

where nr a unit-length vector in U, dr is a vector in the hyperplane in U with normal vector nr, and Pnr : U ! U is the function that maps a z 2 U to the projection of z on the hyperplane with normal vector nr, namely,

Among these models, TransE is arguably the most influential, which has inspired the later models in the "Trans series". TransR is reportedly the best performing model [Lin et al., 2015b]. TransH slightly under-performs TransR on FB15K, but having much lower computation complexity.

Decomposition Framework: Let G := (N↪R↪ ¶Tr : r 2 R♦) be an instance representation. Let Γr be the set of all size-2 subsets of M(Rr). In the decomposition framework, every fr : U M(Rr) !R is parametrized as

Let S2C(G) denote the triple representation resulting from S2C-converting every instance vertex in G.

Lemma 3 The global cost function (3) for S2C(G) is equivalent to the global function (3) for G under the parametrization (5).

That is, models on a triple representation resulting from S2C conversion of an instance representation are equivalent to modeling the original instance representation using the decomposition framework. Noting that the FB15K data have undergone the S2C conversion, all afore-mentioned models on FB15K are, coincidentally, special cases of the decomposition framework. Since the S2C conversion distorts the structures of the relations in the KB (Lemma 2), the decomposition framework necessarily suffers from a loss of information.

In addition, it is possible to show that parametrization using the decomposition framework can result in large errors in approximating the function fr.

Recently another model PTransE[Lin et al., 2015a] has been proposed. An extension of TransE without considering multi-fold relations, PTransE performs comparably to TransR.

3.4 ProposedModel

As the decomposition framework is fundamentally limited, we advocate a direct modelling framework, namely, that the cost function fr is modelled directly without recourse to the decomposition in (5). We now present an example model in this framework, termed m-TransH, which generalizes TransH directly to multi-fold relations.

In m-TransH, each cost function fr is parametrized by two unit-length orthogonal vectors nr and br in U and a function ar 2 RM(Rr) . More specifically, the function fr is defined by

In addition, the orthogonality and unit-lengths constraints on the parameters br and nr is implemented as L2 penalizing terms added to the cost function fr in (6).

Lemma 4 If each Rr is a binary relation and P⇢2M(Rr) ar(⇢) = 0, the optimization problem of mTransH (specified via (3) and (6)) and that of TransH (specified via (3) and (4)) are identical.

Thus m-TransH reduces to TransH for binary relations.

4 Experiments

4.1 JF17KDatasets

The full Freebase data in RDF format was downloaded. Entities involved in very few triples and the triples involving String, Enumeration Type and Numbers were removed. A fact representation was recovered from the remaining triples. Facts from meta-relations having only a single role were removed. From each meta-relation containing more than 10000 facts, 10000 facts were randomly selected. Denote the resulting fact representation by F. Two instance representations 1 Tid(F) and T (F) were constructed. Further filtering was applied to T(F) such that each entity is involved in at least 5 instances. Denote the filtered T(F) by G. Then Tid(F) was filtered correspondingly so that it contains the same set of instances as G. Denote the filtered Tid(F) by Gid. Instance representation S2C(G) was constructed and is denoted by Gs2c. This resulted in three consistent datasets, G, Gid and Gs2c.

Dataset Gid was randomly split into training set GX id and testing set G ? id where every fact ID entity in G ? id was assured to appear in GX id . The corresponding splitting was then applied to G and Gs2c, giving rise to training sets GX and GX s2c , and testing sets G ? and G ? s2c . We call these datasets JF17K. Their statistics, in the same order as FB15K, are given in Table 2.

4.2 Training and Testing

We performed four kinds of experiments, termed m-TransH, m-TransH:ID, TransH:triple and TransH:inst, in which m-TransH and m-TransH:ID train an m-TransH model, and TransH:triple and TransH:inst train a TransH model. The training and testing datasets for the experiments are given in Table 3.

(GX↪ G? )

(GX

id↪ G?

(GX

s2c↪ G?

(GX

s2c↪ G?

In TransH:triple and TransH:inst, for each triple in GX sc , one random negative example is generated. In m-TransH and m-TransH:ID, for each instance in GX,

1 In the construction of Tid(F), when acting on facts of degenerate meta-relations, Tid is taken as T. Such facts each contain a single instance, and there is no need to keep their ID's.

(L2 ) random negative examples are generated. This way, the total number of negative examples used in every experiment is the same, assuring a fair comparison. Stochastic Gradient Descent is used for training, as is standard. Several choices of the dimension (DIM) of U are studied.

Testing Protocol: In m-TransH, m-TransH:ID and TransH:triple, for each testing instance/triple and for each entity x therein, assume that x is unknown; evaluate the cost function for the embedding of the instance/triple by replacing x with every x0 2 N, rank the cost of x0 from low to high, and record the rank for x0 = x. Hit@10 (HIT) and Mean Rank (RANK) are used as the performance metrics[Bordes et al., 2013]. Since the number of triples in G ? s2c is significantly larger than the number of instances in G ? id and G ? , it is questionable whether this testing protocol is fair to the TransH model used in TransH:triple. To assure fairness, in TransH:inst, the TransH model is interpreted as parametrizing the cost function for each relation type in G ? using the decomposition framework (5); then for each instance in G ? , each entity x therein is queried only once in TransH:inst, and the cost for each replacing entity is computed at the instance level instead, using (5) and (4).

4.3 Results and Discussions

The overall performances of the four kinds of experiments are shown in Table 4 and Figure 6.

With the two different testing protocols, TransH performs similarly, where the achieved HIT values are virtually identical and the instance-level test appears somewhat inferior in RANK. This suggests that using the triple-level test, TransH:triple, to compare with m-TransH at least won't depreciate TransH. Comparing with its reported performance on FB15K [Wang et al., 2014], TransH performs rather significantly better on JF17K. This, to an extent attributed to the intrinsic difference in the data, may also reflect that the filtering process of JF17K is more delicate. For example, JF17K contains no Mediator vertices, hence "cleaner".

Overall m-TransH on both G ? and G ? id outperforms TransH by a huge margin. We believe that this performance gain is solely due to the fact that multi-fold relations are treated properly with the direct modelling framework. It is pleasant to see that HIT above 80% can be achieved in this framework, significantly exceeding all reported embedding performances (which are about 50%). This leap perhaps signals that KB embedding is at the verge of prevailing in practice. The observation that m-TransH:ID consistently outperforms m-TransH in HIT implies that fact-level information can be useful for embedding, a direction certainly deserving further investigation. However, the RANK positions of two m-TransH settings are reversed: m-TransH:ID underperforms m-TransH, and the RANK gap decreases as DIM increases. This is because a large number (36201) of fact IDs, twice the number of entities, need to be embedded in m-TransH:ID. When DIM is low, there are not sufficient degrees of freedom to fit all the entities and the fact IDs. This makes a fraction of entities embedded particularly poorly and brings the overall RANK worse than m-TransH. As DIM increases, this problem becomes less severe, resulting in improved RANK.

For each kind of experiments, we select the dimension (DIM) at which it performs the best and break down its performance across relations with different fold J. We observe in Table 5 that for every fold value J, m-TransH outperforms TransH. Note that m-TransH is designed to handle multi-fold relations. However its improved embedding performance for non-binary relations clearly also has a global impact, allowing the binary relations to be embedded better as well.

Finally, we note that the time complexity of m-TransH is significantly lower than TransH. For example, at DIM=50, the training/testing times (in minutes) for TransH:triple and m-TransH:ID are respectively 105/229 and 52/135, on a 32-core Intel E5-2650 2.0GHz processor. This is because with the decomposition framework, an instance of a J-fold relation is S2C-converted to (J2 ) triples, greatly increasing the number of model parameters.

5 Concluding Remarks

This paper examines the fundamentals of multi-fold relations and advocates instance representations as a canonical representation for knowledge bases. We show that the widely adopted decomposition framework, which models multi-fold relations at the triple level, is fundamentally limited. Instead, we propose to model multi-fold relations at the instance level. With a simple example of such models, we demonstrate great advantages of this approach both in performance and in complexity. Outperforming TransH by a cheerful margin, this simple model, m-TransH, perhaps signals the arrival of a new performance regime in knowledge base embedding.

To inspire further research on the embedding of multi-fold relations, we have made our JF17K datasets publicly available. 2

6 Acknowledgement

This work is supported partly by China 973 program (No. 2014CB340305), partly by the National Natural Science Foundation of China (No. 61300070, 61421003), and partly by the Beijing Advanced Innovation Center for Big Data and Brain Computing.