We present a general and novel framework for predicting links in multirelational graphs using a set of matrices describing the various instantiated relations in the knowledge base. We construct matrices that add information further remote in the knowledge graph by join operations and we describe how unstructured information can be integrated in the model. We show that e cient learning can be achieved using an alternating least squares approach exploiting sparse matrix algebra and low-rank approximations. We discuss the relevance of modeling nonlinear interactions and add corresponding model components. We also discuss a kernel solution which is of interest when it is easy to de ne sensible kernels. We discuss the relevance of feature selection for the interaction terms and apply a random search strategy to tune the hyperparameters in the model. We validate our approach using data sets from the Linked Open Data (LOD) cloud and from other sources.
There is a growing amount of data published in multirelational graphs where information elements are represented as subject-predicate-object (s, p, o) triples. Entities (i.e., subjects and objects) are represented as nodes and statements are represented as directed labeled links from subject node to object node. A machine learning task of some generality is the prediction of links between entities using patterns in known labeled links in the knowledge base.
We present a general framework for predicting links in multirelational graphs using a set of matrices describing the various instantiated relations in the knowledge base. We rst consider triples in the immediate neighborhood of the triple of interest and then construct matrices that add information further remote in the knowledge graph by performing join operations. We also consider the case that unstructured information is available that can support the link prediction task and we describe how unstructured information can be integrated in the model. Examples of unstructured information are textual documents describing the involved entities (e.g., from the entities' Wikipedia pages). We show that e cient learning can be achieved using an alternating least squares approach exploiting sparse matrix algebra and low-rank approximations. We discuss the relevance of modeling nonlinear interactions and add corresponding model components. We also discuss a kernel solution which is of interest when it is easy to de ne sensible kernels. We discuss the relevance of feature selection for the interaction terms and apply a random search strategy to tune the hyperparameters in the model. We validate our approach using data sets from the Linked Open Data (LOD) cloud and from other sources.
The paper is organized as follows. The next section discusses related work. Section 3 describes our basic approach. Section 4 describes the cost function and the alternating least squares solution for parameter learning. In Section 5 we discuss aggregation via joint operations, the inclusion of unstructured information and interaction terms. Section 6 contains our experimental results. Section 7 presents our conclusions. 2
One of the rst line of research where matrix representations were used for link
prediction in multirelational graphs is the SUNS framework [
The winning entries in the Net ix competitions are based on matrix
factorization [
Multi-relational graphs also map elegantly to a tensor representation. Tensor
models for relational learning have been explored in [
In this paper we assume that labeled links are represented as triples of the form (s, p, o) where subject s and object o stand for entities in a domain and where p is the predicate, i.e. the link label. We de ne a variable xi;j;k that is associated with the triple (s = i, p = j, o = k). We set xi;j;k = 1 when the triple is known to exist, otherwise xi;j;k = 0. In the multirelational graph, the entities form the nodes and the existing triples form labeled links.
We now consider a domain with N entities and P predicates. For the predicate p= j in the domain we de ne a relational adjacency matrix Xj 2 RN N where (Xj )i;k = 1 if xi;j;k = 1 and (Xj )i;k = 0 otherwise. The matrix of concatenated relational adjacency matrices X = (X1; : : : XP ) describes all existing and all potential triples involving all known entities in the knowledge base. In the basic model we assume that the truth value of a triple (s= i, p= j, o= k) can be estimated as a linear combination of directly related triples, de ned as all triples (s= i, p= j0, o= k0) where i is the subject, all triples (s= i0, p= j0, o= i) where i is the object, all triples (s= k, p= j0, o= k0) where k is the subject and all triples (s= i0, p= j0, o= k) where k is the object. Finally we consider triples with arbitrary predicates but where two entities from the target triple are involved, i.e., (s= i, p= j0, o= k), and (s= k, p= j0, o= i). If xi;j;k = 0, the predicted x^i;j;k 0 can then be interpreted as a likelihood that the triple is true based on the immediate context of the triple.
We now form the matrix M = (X; Xy) where Xy = (X1T ; : : : XPT ) denotes the in-place matrix transposed of X (Figure 1). Let (M )i;l = mi;l.
Following the discussion we form the model For further reference, we call the rst term in the sum in Equation 1 the subject term, the second one the object term, and the last one the subject-object term.3 The w:;:, r:;:, and h:;: are model parameters to be estimated. 3 Note that we get nontrivial solutions by using regularized parameter ts with lowrank constraints, as described in Section 4.
The subject term represents triples where i is the subject, when l = 1; : : : P or where i is the object, when l = P + 1; : : : 2P . Similar the object term represents triples where k is the subject, when l = 1; : : : P or where k is the object, when l = P + 1; : : : 2P . The subject-object term considers all triples that involve both i and k with any predicate (see Figure 2 (a)). 3.3
Note that we assume that the rows in M are exchangeable such that the weights in object term wl;k+(j 1)N are independent of i, and the weights in the subject term rl;i+(j 1)N are independent of k. The parameters hl;j in the subject-object term are independent of both i and k.
There are of course also other ways to segment the parameter space. For example, one might decide that the semantics of the predicate \like" is very di erent when subject is a person than if the subject is a dog and the object is a bone. Technically this could mean that, e.g., we write wl;k+(j 1)N;type(i) and the model correspondingly would have more parameters.
As a special case, we only have one predicate, i.e. "like\ and entity types users and movies. If we apply the learning procedure as described in Section 4 we obtain a solution that only exploit correlations between triples with the same predicate, i.e., intrarelational correlations. In e ect, we obtain a regularized lowrank approximation of the relational adjacency matrix which is a model often used in collaborative ltering applications. Additional relational adjacency matrixes, for example representing user and movie attributes, can then help to support the prediction of \like"-triples.
One might want to think of the last equation in terms of an if-then-rule where the right side of the equation describes the condition and the left side describes the conclusion. In this view the subject ?s and the object ?o would be variables4 and the subject term describes relations including the rst variable, the object term describes relations including the second variable, and the subjectobject term describes relations including both variables. All these variables are universally quanti ed, which means that the expression is valid for all subjects ?s and all objects ?o. We can introduce additional variables in the condition part for certain aggregation operations, as described in Section 5, and these variables would be existentially quanti ed (as in Horn clauses). 4 4.1
We can write the model of Equation 1 e ciently in matrix form as X^ = M W + (M R)y + matrix(N P N)
M~ H (2) Here, M~ = (vect(X1); : : : ; vect(XP ); vect(X1T ); : : : ; vect(XPT )) is an N 2 2P matrix where the column vector vect(:) contains all elements of the corresponding relational adjacency matrix. Furthermore, W 2 R2P N P N , R 2 R2P N P N , and H 2 R2P P are parameter matrices. The operation matrix(N P N)(:) transforms the result of the matrix product into a N P N matrix.
We de ne a penalized least squares cost function as kX
X^ k2F +
W kW k2F +
RkRk2F +
H kHk2F where kkF is the Frobenius norm. The last three terms are used to regularize the solution to avoid over tting. 4.2
We optimize the parameter matrices W , R, and H using an alternating least squares procedure as described in this subsection.
To reduce computation and to further regularize the solution, we rst decompose using singular value decomposition (SVD)
M = U DV T
M~ = U~ D~ V~ T and only use the leading singular values and corresponding singular vectors in the model. Another bene t of this low-rank approximation is that we implicitly 4 We use the common notation of indicating a variable by a question mark in front of a symbol. bene t from a sharing of statistical strengths leading to performance improvements, as it is well known from Latent Semantic Analysis (LSA).
We de ne X^ ( W ) as X minus the estimate in Equation 2 using the parameter estimates in the current iteration step, except that W = 0, i.e. we remove the subject term in the sum. Similarly, we de ne X^ ( R) as X minus the estimate in Equation 2 using the parameter estimates in the current iteration step, except that R = 0, i.e. we remove the object term in the sum. Finally, we de ne X^ ( H) as X minus the estimate in Equation 2 using the parameter estimates in the current iteration step, except that H = 0, i.e. we remove the subject-object term in the sum.
In the alternating least squares steps we iterate until convergence r M W = Ur diag M R = Ur diag M~ H = U~r~ diag di2 di2 di2 + di2 + ( ~2 di d~i2 + ~H
W i=1 r R i=1 )r~ i=1
UrT X^ ( W ) U T r
X^ ( R) y U~r~T X~ ( H) (3) (4) (5) where in X~ ( H) = matrixN2 P X( H) each relational adjacency matrix is written as a column vector. In particular for the update in Equation 5, a solution in terms of the V -matrices might be more e cient (see the Appendix). 4.3
Considering domains with several million entities, the computations seem to be expensive. Fortunately, in the computations one can explore the extreme sparsity of all relational adjacency matrices in many domains of interests. For example, due to type constraints, nonzero elements are often restricted to one or a small number of blocks in the matrices. For example if entities are users and movies and X stands for \likes" then only the submatrix with users as rows and movies as columns contains nonzero elements, re ecting the fact that users like movies but, e.g., movies do not like users. Also, if one is only interested to predict entries in one particular relational adjacency matrix, we only need to calculate the parameters relevant to predicting the entries in that particular matrix.
We also want to point out that one could also apply the SVD to each relational adjacency matrix separately or to blocks of relational adjacency matrices, instead of M ; essentially one should make this decision on the expected performance bene ts of the matrix decompositions and the computational costs. 5 5.1
The triples represented in Equation 2 only consider the immediate neighborhood of the triples (s, p, o) under consideration. It is easy to extend the formalism to also consider triples further away in the graph. As an example, consider the case that the likelihood that a person likes a movie is increased if at least one friend likes the movie. The latter information can be represented by the matrix, representing a join operation, formed by XfriendLikesMovie = min (1; XfriendOfXlikes) where min is applied component wise. Then XfriendLikesMovie (and its transposed) is simply added as an additional relational adjacency matrix. Now we can model (via the subject term in Equation 2) that a person might like \Action Hero 3" if at least one friend likes \Action Hero 3"; the subject-object term in Equation 2 can even model the more general dependency that a person likes any movie if at least one friend likes that movie.
The general form of an aggregated adjacency matrix is Xa = min (1; Qi Mi) where Mi 2 (X1; : : : XP ; X1T ; : : : XPT ). Naturally, it is not feasible to consider an in nite set of matrix products. Possible approaches are that the user de nes a small set of interesting candidates or that one applies structural search, e.g., by using approaches borrowed from the eld of Inductive Logic Programming. Many more forms of aggregation are possible. For example one might not apply the min operation and, e.g, count how many friends liked a movie, or what percentage of friends liked a movie.
Here are two interesting examples involving join operations. First, let's assume that a person tends to be rich if this person has a rich friend: The triple of interest is (?u, type, RichPerson). We join (?u, hasFriend, ?f) and (?f, type, RichPerson) and obtain a matrix that indicates if anybody of a person's friends is rich (see Figure 2 (b)). Second, let's assume that a person often prefers restaurants of the nationality of that person: The triple of interest is (?u, likes, ?r). We join (?u, hasNationality, ?c) and (?r, hasNationality, ?c) and obtain a matrix that indicates if the user and the restaurant have the same nationality. 5.2
Sometimes there is contextual information available, often in textual form, that
describe entities and relationships and can be exploited for link prediction [
In Equation 2 we used a linear system, which is suitable in many high-dimensional domains. Of course, one can apply more general models such as neural networks as predictive models. Often this is unsuitable since the computational costs would explode. In our approach we stay with a model linear in the parameters but add nonlinear interaction terms. As an example, assume that young users prefer action movies. We de ne a new triple (?u, YoungAction, ?m) that is true if (?u, hasAge, Young) is true and (?m, type, ActionMovie) is true (see Figure 2 (c)). In general, the subject-object term in Equation 1 can be expected to be most valuable here as well. To keep the number of these interaction terms small, we apply a feature selection procedure, as described in Section 6. 5.4
So far our discussion focussed on a representation in feature space. Here we
discuss a representation in kernel space. A kernel formulation is appropriate for
data in a multirelational graph and suitable kernels are described in [
From Equation 2 one can see that two kernels are involved in our approach, the rst one k(:; :) involving two entities, either two subjects k(s; s0) or two objects k(o; o0). The second kernel k~((s; o); (s0; o0)) involves two subject-object pairs. Given the corresponding kernel matrices K and K~ we can decompose using a singular value decomposition
K = U DDT U T
K~ = U~ D~ D~ T U~ T and use the resulting terms in the update Equations 3 to 5. 6 6.1
We have several hyperparameters that need to be tuned (rank of approximations;
regularization parameters). We follow the approach described in [
The synthetic data has been generated according to our modeling assumptions. We de ne a target predicate of interest and call the triples involving the target predicate the target triples. In addition we have triples related to the subject, i.e., describing subject attributes, and triples related to the object, i.e., describing object attributes. In addition we use interaction triples generated by conjunctions on subject and object triples.
Figure 3 shows the results of using di erent relational adjacency matrices.
The proposed model that uses all sources of information (Mglobal) performs best.
Also if we only exploit subject attributes and object attributes (Fall) we obtain
signi cant predictive power. A model only using intrarelational information MCF
is quite strong. The reason is that, if su cient amount of target triples are known
to be true, the information on subject and object attributes is implicitly modeled
in MCF as well. This is a result also con rmed in the remaining experiments: if
MCF is quite strong, adding subject and object information does not improve the
model further, even when the latter might have predictive power. The proposed
model (Mglobal) is signi cantly better than the reference model (MHBS) described
in [
We have 49801621 potential interaction terms which we reduced to 1132 by using a fast feature selection procedure evaluating the Pearson correlation between targets and interaction term.
Figure 4 (left) shows the results for predicting diseases for genes. Our proposed model gives very good results, although the reference model is slightly stronger. Figure 4 (right) shows the results for predicting genes for diseases. Due to sparsity, this task is more di cult and our proposed model performs best. We used 943 users and 1600 movies from the MovieLens data set5 and evaluated if a user has seen a movie or not. 99 user attributes were derived from age (5 classes), gender (2 classes), occupation (21 classes), and the rst two digits of the ZIP code. The 89 movie attributes were derived from genre, release month and release year. Figure 5 (left) shows the results. Although the attribute information on the movies and the users have predictive power (signi cantly above random), a model exploiting intrarelational correlations (MCF) gives very good performance and the proposed model and the reference model cannot improve beyond the performance of MCF. As in the experiment on the synthetic data,
there is information in the contextual data but this information is also represented in MCF. We have 8811 potential interaction terms which we reduced to 200 by using a fast feature selection procedure evaluating the Pearson correlation between targets and interaction term. We used the BookCrossing data set6 to predict if a user rated a book. The data set consisted of 105283 users and 340554 books. A user is described by 5849 attributes (derived from age and city, province and country) and a book is described by 24508 attributes (authors, publication year, publisher). The goal is to predict if a user would rate (i.e., read) a book. The results in Figure 5 (right) show that the proposed modeling approach gives best results. 7
We have presented a general framework for predicting links in multirelational graphs. We showed that e cient learning can be achieved using an alternating least squares approach.
The approach can be extended in several directions. First, for the entries in
the relational adjacency matrices one can use real numbers, e.g., between zero
and one, and the user can represent the certainty that a triple is true [
We only derive Equation 3. The derivations for Equations 4 and 5 are equivalent. We start with the regularizes least squares solution for estimating X^ ( W ) based on M
M W = M (M T M + W I) 1M T X^ ( W ) If we use the low-rank approximation M
UrDrVrT , where Dr = diag fdigir=1, we get
M W = UrDrVrT (VrDrUrT UrDrVrT + W I) 1VrDrUrT X^ ( W ) = Ur diag
di2 r di2 + W i=1
UrT X^ ( W ) = X^ ( W )Vr diag
di2 r di2 + W i=1