Knowledge Hypergraphs: Prediction Beyond Binary Relations

1 Introduction

Knowledge hypergraphs are graph structured knowledge bases that store facts about the world in the form of relations among any number of entities. They can be seen as one generalization of knowledge graphs in which relations are defined on at most two entities. Since accessing and storing all the facts in the world is difficult, knowledge bases are incomplete; the goal of link prediction in knowledge (hyper)graphs (or knowledge (hyper)graph completion) is to predict unknown links or relationships between entities based on existing ones. In this work, we are interested in the problem of link prediction in knowledge hypergraphs. Our motivation for studying link prediction in these more sophisticated knowledge structures is based on the fact that most knowledge in the world has inherently complex compositions.

Link prediction in knowledge graphs is a problem that is studied extensively, and has applications in several tasks such as automatic question answering [Ferrucci et al., 2010].

∗This paper with the supplementary material can be found at https://arxiv.org/abs/1906.00137.

†Contact Author

In these studies, knowledge graphs are defined as directed graphs having nodes as entities and labeled edges as relations; edges are directed from the head entity to the tail entity. The common data structure for representing knowledge graphs is a set of triples relation(head, tail) that represents information as a collection of binary relations. There exist a large number of knowledge graphs that are publicly available, such as FREEBASE [Bollacker et al., 2008]. Wen et al. (2016) observe that in the original FREEBASE more than 1/3rd of the entities participate in non-binary relations (i.e., defined on more than two entities). We observe, in addition, that 61% of the relations in the original Freebase are non-binary.

Embedding-based models [Nguyen, 2017; Kazemi et al., 2020] have proved to be effective for knowledge graph completion. These approaches learn embeddings for entities and relations. To find out if a triple relation(head, tail) is true, such models define a function that uses embeddings of relation, head, and tail and output the probability of the triple. While successful, such embedding-based methods make the strong assumption that all relations are binary.

Knowledge hypergraph completion is a relatively underexplored area. We motivate our work by outlining that converting non-binary relations into binary ones using methods such as reification or star-to-clique [Wen et al., 2016], and then applying known link prediction methods does not yield satisfactory results. Reification is one common approach of

reify a tuple having a relation defined on k entities e1, . . . , ek, we form k new binary relations, one for each position in this relation, and a new entity e for this tuple and connect e to each of the k entities that are part of the given tuple using the k binary relations. Another conversion approach is Star-toclique, which converts a tuple defined on k entities into (k2) tuples with distinct relations between all pairwise entities in the tuple.

Both conversion approaches have their caveats when current link prediction models are applied to the resulting graphs. The example in Figure 1a shows three facts that pertain to the relation flies between. When we reify the hypergraph in this example (Figure 1b), we add three reified entities. In terms of representation, the binary relations created are equivalent to the original representation and reification does not lose information during conversion. A problem with reification, however, arises at test time: because we introduce new entities that the model never encounters during training, we do not have a learned embedding for these entities; and current embedding-based methods require an embedding for each entity in order to be able to make a prediction.

Applying the star-to-clique method to a hypergraph does not yield better results, as star-to-clique conversion loses information. Figure 1c shows the result of applying star-toclique to the original hypergraph (Figure 1a), in which the tuple flies between(Air Canada, New York, Los Angeles) might be interpreted as being true (since the corresponding entities are connected by edges), whereas looking at the original hypergraph, it is clear that Air Canada does not fly from New York to Los Angeles.

In this work, we introduce two embedding-based models that perform link prediction directly on knowledge hypergraphs without converting them to graphs. Both proposed models are based on the idea that predicting the existence of a relation between a set of entities depends on the position of the entities in the relation; otherwise, the relation is symmetric. On the other hand, learning entity embeddings for each position independently does not work well either, as this does not let the information flow between the embeddings for the different positions of the same entity. The first model we propose is HSimplE. For a given entity, HSimplE shifts the entity embedding by a value that depends on the position of the entity in the given relation. Our second model is HypE, which in addition to learning entity embeddings, learns positional (convolutional) embeddings; these positional embeddings are disentangled from entity representations and are used to transform the representation of an entity based on its position in a relation. This makes HypE more robust to changes in the position of an entity within a tuple. We show that both HSimplE and HypE are fully expressive. To evaluate our models, we introduce two new datasets from subsets of FREEBASE, and develop baselines by extending existing models on knowledge graphs to work with hypergraphs.

The contributions of this paper are: (1) showing that current techniques to convert a knowledge hypergraph to knowledge graph do not yield satisfactory results for the link prediction task, (2) introducing HypE and HSimplE, two models for knowledge hypergraph completion, (3) a set of baselines for knowledge hypergraph completion, and (4) two new datasets containing multi-arity relations obtained from subsets of FREEBASE, which can serve as new evaluation benchmarks for knowledge hypergraph completion methods. We also show that our proposed methods outperform baselines.

2 RelatedWork

Existing methods that relate to our work in this paper can be grouped into the following three main categories.

Knowledge graph completion. Embedding-based models for knowledge graph completion such as translational [Bordes et al., 2013; Wang et al., 2014], bilinear [Yang et al., 2015; Kazemi and Poole, 2018], and deep models [Socher et al., 2013] have proved to be effective for knowledge graphs where all relations are binary. In Section 6 we extend some of the models in this category to knowledge hypergraphs, and compare their performance with the proposed methods.

Knowledge hypergraph completion. Soft-rule models [De Raedt et al., 2007; Kazemi et al., 2014] can easily handle variable arity relations and have the advantage of being interpretable. However, they can only learn a subset of patterns [Nickel et al., 2016]. Guan et al. (2019) propose an embedding-based method based on the star-to-clique approach. The caveats of this approach are discussed earlier. m-TransH [Wen et al., 2016] extends TransH [Wang et al., 2014] to knowledge hypergraph completion. Kazemi and Poole (2018) prove that TransH, and consequently m-TransH, are not fully expressive and have restrictions in modeling relations. In contrast, we prove that our proposed models are fully expressive.

Learning on hypergraphs. Hypergraph learning has been employed to model high-order correlations among data in many tasks, such as in video object segmentation [Huang et al., 2009] and in modeling image relationships and image ranking [Huang et al., 2010]. There is also a line of work extending graph neural networks to hypergraph neural networks [Feng et al., 2019] and hypergraph convolution networks [Yadati et al., 2018]. These models are designed for undirected hypergraphs, with edges that are not labeled (no relations), while knowledge hypergraphs are directed and labeled graphs. As there is no clear or easy way of extending these models to our knowledge hypergraph setting, we do not consider them as baselines for our experiments.

3 Definition and Notation

A world consists of a finite set of entities E, a finite set of relations R, and a set of tuples τ where each tuple in τ is of the form r(e1, e2, . . . , ek) where r ∈ R is a relation and each ei ∈ E is an entity, for all i = 1, 2, . . . , k. The arity |r| of a relation r is the number of arguments that the relation takes and is fixed for each relation. A world specifies what is true: all the tuples in τ are true, and the tuples that are not in τ are false. A knowledge hypergraph consists of a subset of the tuples τ ′ ⊆ τ . Link prediction in knowledge hypergraphs is the problem of predicting the missing tuples in τ ′ , that is, finding the tuples τ \ τ ′ .

An embedding is a function that converts an entity or a relation into a vector (or sometimes a higher order tensor) over a field (typically the real numbers). We use bold lower-case for vectors, that is, e ∈ Rk is an embedding of entity e, and r ∈ Rl is an embedding of a relation r.

Let v1, v2, . . . , vk be a set of vectors. The variadic function concat(v1, . . . , vk) outputs the concatenation of its input vectors. We define the variadic function ⊙() to be the sum of the element-wise product of its input vectors, namely ⊙(v1, v2, . . . , vk) = ∑ℓi=1 v1 (i)v2 (i) . . . vk (i) where each vector vi has the same length, and vj (i) is the i-th element of vector vj. The 1D convolution operator ∗ takes as input a vector v, a convolution weight filter ω, and a stride s and outputs the standard 1D convolution as defined in torch.nn.Conv1D function in PyTorch [Paszke et al., 2019].

For the task of knowledge graph completion, an embedding-based model defines a function φ that takes a tuple x as input, and generates a prediction, e.g., a probability (or score) of the tuple being true. Amodel is fully expressive if given any complete world (full assignment of truth values to all tuples), there exists an assignment of values to the embeddings of the entities and relations that accurately separates the tuples that are true in the world from those that are false.

4 Knowledge Hypergraph Completion: Proposed Methods

The idea at the core of our methods is that the way an entity representation is used to make predictions is affected by the role (or position) that the entity plays in a given relation. In the example in Figure 1a, Montreal is the departure city; but it may appear in a different position (e.g., arrival city) in another tuple. This means that the way we use Montreal's embedding for computing predictions may need to vary based on the position it appears in within the tuple. In general, when the embedding of an entity does not depend on its position in the tuple during prediction, then the relation has to be symmetric (which is not the case for most relations). On the other hand, when entity embeddings are based on position but are learned independently, information about one position will not interact with that of others. It should be noted that in several embedding-based methods for knowledge graph completion, such as canonical polyadic [Hitchcock, 1927; Lacroix et al., 2018], ComplEx [Trouillon et al., 2016], and SimplE [Kazemi and Poole, 2018], the prediction depends on the position of each entity in the tuple.

In what follows, we propose two embedding-based methods for link prediction in knowledge hypergraphs. The first model is inspired by SimplE and has its roots in knowledge graph completion; the second model takes a fresh look at knowledge completion as a multi-arity problem, without first setting it up within the frame of binary relation prediction.

HSimplE. HSimplE is an embedding-based method for link prediction in knowledge hypergraphs that is inspired by SimplE [Kazemi and Poole, 2018]. SimplE learns two embedding vectors e(1) and e(2) for an entity e (one for each possible position of the entity), and two embedding vectors r(1) and r(2) for a relation r (with one relation embedding as the inverse of the other). It then computes the score of a triple as φ(r(e1, e2)) = ⊙(r(1) , e(1) 1 , e(2) 2 ) +⊙(r(2) , e(1) 2 , e(2) 1 ).

In HSimplE, we adopt the idea of having different representations for an entity based on its position in a relation and updating all these representations from a single training tuple. We do this by representing each entity e as a single vector e (instead of multiple vectors as in SimplE), and each relation r as a single vector r. Conceptually, each e can be seen as the concatenation of the different representations of e based on every possible position. For example, in a knowledge hypergraph where the relation with maximum arity is α, an entity can appear in α different positions; hence e will be the concatenation of α vectors, one for each possible position. HSimplE scores a tuple using the following function.

Here, shift(v, x) shifts vector v to the left by x steps, len(e) returns length of vector e, and α = maxr∈R(|r|). We observe that for knowledge graphs (α = 2), SimplE is a special instance of HSimplE, with e = concat(e(1) , e(2) ) and r = concat(r(1) , r(2) ). The architecture of HSimplE is summarized in Figure 2a.

HypE. HypE learns a single representation for each entity, a single representation for each relation, and positional convolutional weight filters for each possible position. When an entity appears in a specific position, the appropriate positional filters are first used to transform the embedding of each entity in the given fact; these transformed entity embeddings are then combined with the embedding of the relation to produce a score, i.e., the probability of the input tuple to be true. The architecture of HypE is summarized in Figures 2b and 2c.

Let n denote the number of filters per position, l the filterlength, d the embedding dimension, and s the stride of a convolution. Let ωi ∈ Rn×l be the convolutional filters associated with position i, and let ωij ∈ Rl be the jth row of ωi. We denote by P ∈ Rnq×d the projection matrix, where q = ⌊(d - l)/s⌋ + 1 is the feature map size. For a given tuple, define f(e, i) = concat(e ∗ ωi1, . . . , e ∗ ωin)P to be a function that returns a vector of size d based on the entity embedding e and its position i in the tuple. Thus, each entity embedding e appearing at position i in a given tuple is convolved with the set of position-specific filters ωi to give n feature maps of size q. All n feature maps corresponding to an entity are concatenated into a vector of size nq and projected to the embedding space through multiplication by P. The projected vectors of entities and the embedding of the relation are combined by inner-product to define φ:

The advantage of learning positional filters disentangled from entity embeddings is two-folds: On one hand, learning a single vector per entity keeps entity representations simple and disentangled from its position in a given fact. On the other hand, unlike HSimplE, HypE learns positional filters from all entities that appear in the given position; overall, this separation of representations for entities, relations, and positions facilitates the representation of knowledge bases having facts of arbitrary number of entities. It also gives HypE an additional robustness, such as in the case when we test a trained HypE model on a tuple that contains an entity in a position never seen before at train time. We discuss this in Section 6.1.

Both HSimplE and HypE are fully expressive - an important property that has been the focus of several studies [Fatemi et al., 2019]. Amodel that is not fully expressive can embed assumptions that may not be reflected in reality.

Theorem 1 (Expressivity). For any ground truth over entities E and relations R containing |τ| true tuples and α = maxr∈R(|r|) , there exists a HypE and a HSimplE model with embedding vectors of size max(α|τ|, α) that represents that ground truth.

Proof Sketch. To prove the theorem, we show an assignment of embedding values for each of the entities and relations in τ such that the scoring function of HypE and HSimplE gives 1 for t ∈ τ and 0 otherwise.

4.1 Objective Function and Training

Both HSimplE and HypE are trained using stochastic gradient descent with mini-batches. In each learning iteration, we take a batch of positive tuples from the knowledge hypergraph. As we only have positive instances available, we need to also train our model on negative instances; thus, for each positive instance, we produce a set of negative instances. For negative sample generation, we follow the contrastive approach of [Bordes et al., 2013] for knowledge graphs and extend it to knowledge hypergraphs: for each tuple, we produce a set of negative samples of size N|r| by replacing each of the entities with N random entities in the tuple, one at a time. Here, N is the ratio of negative samples in our training set and is a hyperparameter.

Given a knowledge hypergraph defined on τ ′ , we let τ ′ train , τ ′ test , and τ ′valid denote the train, test, and validation sets, respectively, so that τ ′ = τ ′ train ∪ τ ′ test ∪ τ ′valid . For any tuple x in τ ′ , we let Tneg(x) be a function that generates a set of negative samples through the process described above. Let r and e represent relation and entity embeddings respectively. We define the following cross entropy loss:

5 Experimental Setup

5.1 Datasets

The experiments on knowledge hypergraph completion are conducted on three datasets. The first is JF17K proposed by Wen et al. (2016); as no validation set is proposed for JF17K, we randomly select 20% of the train set as validation. We also create two datasets FB-AUTO and M-FB15K from FREEBASE. For the experiments on datasets with binary relations, we use two standard benchmarks for knowledge graph completion: WN18 [Bordes et al., 2014] and FB15k [Bordes et al., 2013]. See Table 2 for statistics of the datasets.

5.2 Baselines

To compare our results to that of existing work, we first design simple baselines that extend current models to work with knowledge hypergraphs. We only consider models that admit a simple extension to higher-binary relations for the link prediction task. The baselines for this task are grouped into the following categories: (1) methods that work with binary relations and that are easily extendable to higher-arity, namely r-SimplE, m-DistMult, and m-CP; (2) existing methods that can handle higher-arity relations, namely m-TransH. Below we give some details about methods in category (1).

r-SimplE. To test the performance of a model trained on reified data, we convert higher-arity relations in the train set to binary relations through reification. We then use SimplE (that we call r-SimplE) on this reified data. In this setting, at test time higher-arity relations are first reified to a set of binary relations; this process creates new auxiliary entities for which the model has no learned embeddings. To embed the auxiliary entities for the prediction step, we use the observation we have about them at test time. For example, a higherarity relation r(e1, e2, e3) is reified at test time by adding a new entity e′ and converting the higher-arity tuple to three binary facts: r1(e′ , e1), r2(e′ , e2), and r3(e′ , e3). When predicting the tail entity of r1(e′ , ?), we use the other two reified facts to learn an embedding for entity e′ . Because e′ is added only to help represent the higher-arity relations as a set of binary relations, we only need to do tail prediction for reified relations. Note that we do not reify binary relations.

m-DistMult. DistMult [Yang et al., 2015] defines a score function φ(r(ei, ej)) = ⊙(r, ei, ej). To accommodate non-binary relations, we redefine this function as φ(r(ei, . . . , ej)) = ⊙(r, ei, . . . , ej).

m-CP. Canonical Polyadic decomposition [Hitchcock, 1927] is a tensor decomposition approach. We refer to the version that only handles binary relations as CP. CP embeds each entity e as two vectors e(1) and e(2) , and each relation r as a single vector r; it defines the score function φ(r(ei, ej)) = ⊙(r, e(1) i , e(2) j ). We extend CP to mCP, which accommodates relations of any arity. m-CP embeds each entity e as α different vectors e(1) , .., e(α) , where α = maxr∈R(|r|); it computes the score of a tuple as φ(r(ei, . . . , ej)) = ⊙(r, e(1) i , ..., e(|r|) j ).

5.3 EvaluationMetrics

Given a knowledge hypergraph on τ ′ , we evaluate various completion methods using a train and test set τ ′ train and τ ′ test . We use two evaluation metrics: Hit@t and Mean Reciprocal Rank (MRR). Both these measures rely on the ranking of a tuple x ∈ τ ′ test within a set of corrupted tuples. For each tuple r(e1, . . . , ek) in τ ′ test and each entity position i in the tuple, we generate |E| - 1 corrupted tuples by replacing the entity ei with each of the entities in E \ {ei}. For example, by corrupting entity ei, we would obtain a new tuple r(e1, . . . , eci , . . . , ek) where eci ∈ E \ {ei}. Let the set of corrupted tuples, plus r(e1, . . . , ek), be denoted by θi(r(e1, . . . , ek)). Let ranki(r(e1, . . . , ek)) be the ranking of r(e1, . . . , ek) within θi(r(e1, . . . , ek)) based on the score φ(x) for each x ∈ θi(r(e1, . . . , ek)). We compute theMRR as 1K ∑r(e1,...,ek)∈τ ′ test ∑ki=1 1 rankir(e1,...,ek) where K = ∑r(e1,...ek)∈τ ′ test |r| is the number of prediction tasks. Hit@t measures the proportion of tuples in τ ′ test that rank among the top t in their corresponding corrupted sets. We follow [Bordes et al., 2013] and remove all corrupted tuples that are in τ ′ from our computation of MRR and Hit@t.

6 Experiments

This section summarizes our experiments 1 .

1 Code and data available at https://github.com/ElementAI/HypE.

6.1 Knowledge Hypergraph Completion Results

The results of our experiments, summarized in Table 1, show that both HSimplE and HypE outperform the proposed baselines across the three datasets JF17K, FB-AUTO, and M-FB15K. They further demonstrate that reification for the r-SimplE model does not work well; this is because the reification process introduces auxiliary entities for which the model does not learn appropriate embeddings because these auxiliary entities appear in very few facts. Comparing the results of r-SimplE against HSimplE, we can also see that extending a model to work with hypergraphs works better than reification when high-arity relations are present.

The ability of knowledge sharing through the learned position-dependent convolution filters suggests that HypE would need a lower number of parameters than HSimplE to obtain good results. To test this, we train both models with different embedding dimensions. Figure 3a shows the MRR on the test set for each model with different embedding sizes. Based on the MRR result, we can see that HypE outperforms HSimplE by 24% for embedding dimension 50, implying that HypE works better under a constrained budget.

Disentangling the representations of entity embeddings and positional filters enables HypE to better learn the role of position within a relation because the learning process considers the behavior of all entities that appear in a given position at the time of training. This becomes especially important in the case when some entities never appear in certain positions in the train set, but you still want to be able to reason about them no matter what position they appear in at test time. In order to test the effectiveness of our models in this more challenging scenario, we created a missing positions test set by selecting the tuples from our original test set that contain at least one entity in a position it never appears in within the training dataset. The results on these experiments (Figure 3b) show that (1) both HSimplE and HypE outperform m-CP (which learns different embeddings for each entity-position pair), and more importantly, (2) HypE significantly outperforms HSimplE for this challenging test set, leading us to believe that disentangling entity and position representations may be a better strategy for this scenario.

6.2 Knowledge Graph Completion Results

To show that HSimplE and HypE work well also on the more common knowledge graphs, we evaluate them on WN18 and FB15K. Table 3 shows link prediction results on WN18 and FB15K. Baseline results are taken from the original papers except that of m-TransH, which we implement ourselves. Instead of tuning the parameters of HypE to get potentially better results, we follow the Kazemi and Poole (2018) setup with the same grid search approach by setting n = 2, l = 2, and s = 2. This results in all models in Table 3 having the same number of parameters, and thus makes them directly comparable to each other. Note that for knowledge graph completion (all binary relations) HSimplE is equivalent to SimplE, both theoretically and experimentally (as shown in Section 4). The results show that on WN18 and FB15K, HSimplE and HypE outperform all baselines.

6.3 Ablation Study on Different Arities

We break down the performance of models across different arities. As the number of test tuples in higher arities (4-5-6) is much less than in smaller arities (2-3), we used equivalent size bins to show the decomposed results for a reasonable number of test tuples. Table 4 shows the Hit@10 results of the models for bins of arity 2, 3, and 4-5-6 in JF17K. The proposed models outperform the state-of-the-art and the baselines in all arities. We highlight that r-SimplE and HSimplE are quite different models for relations having arity > 2.

7 Conclusions

Knowledge hypergraph completion is an important problem that has received little attention. Having introduced two new knowledge hypergraph datasets, baselines, and two new methods for link prediction in knowledge hypergraphs, we hope to kindle interest in the problem. Unlike graphs, hypergraphs have a more complex structure that opens the door to more challenging questions such as: how do we effectively predict the missing entities in a given (partial) tuple?