Low Resource Quadratic Forms for Knowledge Graph Embeddings (2021)

Abstract: We address the problem of link prediction between entities and relations of knowledge graphs. State of the art techniques that address this problem, while increasingly accurate, are computationally intensive. In this paper we cast link prediction as a sparse convex program whose solution defines a quadratic form that is used as a ranking function. The structure of our convex program is such that standard support vector machine software packages, which are numerically robust and efficient, can solve it. We show that on benchmark data sets, our model’s performance is competitive with state of the art models, but training times can be reduced by a factor of 40 using only CPU-based (and not GPU-accelerated) computing resources. This approach may be suitable for applications where balancing the demands of graph completion performance against computational efficiency is a desirable trade-off.

## introduction digital representations of knowledge are essential to many machine learning domains including social networks, citation networks, question-answering, information retrieval, recommender systems, and natural language processing @xcite @xcite . multirelational data, when represented as a directed graph whose nodes (entities) are connected to each other by one or more edges (relations) are knowledge graphs. knowledge graphs are often both large and incomplete. as a result, the task of link prediction is a basic challenge. much recent work on knowledge graph representation has focused on constructing embeddings of the relations and entities of a graph to facilitate good performance on the link prediction problem. but training modern models on large graphs often consumes many hours of gpu time. in this paper, we formulate the link prediction problem as a sparse convex program that can be efficiently solved by off-the-shelf support vector machine (svm) software packages. we demonstrate performance that is competitive with state of the art methods, but our programs are solved in substantially shorter times and without requiring specialized gpu hardware. our approach takes advantage of existing svm technology: large-scale convex problems are routinely solved using an arsenal of first and second order methods, as well as decades of empirically-derived heuristics. solutions to convex problems are global, often unique, and in some cases (e.g. linear programs), solutions come with theoretical guarantees about program complexity. while we do not pursue this idea in the present work, it is possible to naturally incorporate external knowledge about relationships into convex programs @xcite . an unusual feature of our program is that the solution is not used as a binary classifier, but instead, the solution is used to define a symmetric quadratic form that ranks facts in the knowledge graph. the main contributions of this work include 1) a novel convex formulation of the link prediction problem 2) a scalable approach to link prediction that that can be efficiently solved using standard svm solvers and 3) a link prediction model that exhibits competitive performance. we now describe the remaining sections of this paper. in the next section we present notation and background information on svms and the transe model that we base our method on. in section 3 we present details of our svm formulation. in section 4 we comment on implementation. experiments are discussed in section 5. results are presented in section 6. related work and conclusions are in section 7 and section 8, respectively. given a set of entities e and relations r, a knowledge graph embedding (kge) model embeds the elements of e ∪ r as elements in r k for a fixed positive integer k. for brevity, we abuse notation and will represent the elements and the embeddings of the elements in e and r with the same symbol. thus, the expressions e + r, αe for any α ∈ r, and e are well-defined, and represent component-wise addition, scalar multiplication, and transposition, respectively. additionally, x p := ( |x i | p ) 1/p . unless otherwise specified, we assume @xmath0. for each (h, r, t) ∈ k, we define a set of corrupted triples as that is, k † (h,r,t) contains triples where either h or t is replaced by h † ∈ e or t † ∈ e so that the new triple is not in k. for ease of notation we will often write corrupted triples as (h † , r, t † ) ∈ k † (h,r,t) (where both h † and t † appear), but it is always the case that precisely one of h or t is replaced, not both. a link prediction model's score function is the function that distinguishes positive triples from corrupted triples. if f is a score function, then a wellperforming model satisfies f (h, r, t) ≤ f (h † , r, t † ) when (h, r, t) ∈ k and (h † , r, t † ) ∈ k † (h,r,t) . transe our approach is inspired by the "translational model", transe, introduced in @xcite . despite its age and simplicity, transe exhibits performance that is often competitive with state-of-the-art techniques, and our svm-based approach shares several key features with it. the goal of transe is to make h + r -t small whenever (h, r, t) ∈ k and large otherwise. to do this, one minimizes the loss function given an optimal solution w of this svm, the function φ : @xmath1, {x : w x -γ > 0} and {x : w x -γ < 0}. if y i (w x i + γ) > 0, for all @xmath2, . . . , n , then the data used to train the svm are linearly separable the function φ is the decision function of the svm. classification error is measured by ζ 2 . the term w 2 maximizes the margin between the bounding planes w @xmath3. one attractive feature of casting a problem as an svm is the wide availability of high quality svm software packages. such packages are numerically robust, and are capable of rapidly solving problems with massive scale. ## formulation we now describe how to express the link prediction problem as a convex variant of transe, and then we show how to write this convex problem as an svm. recall that our goal is to identify a score function for all (h, r, t) ∈ k and (h † , r, t † ) ∈ k † (h,r,t) . we will assume that f has the form, it is possible to represent the positive semi-definite condition on b as a convex constraint, but optimizing a loss function with this additional constraint is incompatible with an svm formulation. since our main goal is to create a score function, we omit the positive definite constraint from our program. the inequality expressed in (4) is quadratic in the problem data, but linear in the unknown, b. indeed, each side of the inequality (4) expresses a quadratic polynomial in the entries of h, r and t, while both expressions are linear in the entries of b. to make this more explicit, we introduce notation. let vec : r n×@xmath4. then for any x, @xmath5. when a is a symmetric matrix and @xmath6, then (5) can be adapted to apply to the upper-triangular portions of a and xx . just as vec maps square matrices to vectors, one may define symvec that maps symmetric matrices in r n×n to vectors in r n(n+1)/2 , and which satisfies with notation in hand, initialize the embeddings of h,r and t to be one-hot encoded. our task is to find @xmath7, r, t) ≤ w s(h † , r, t † ), for all (h, r, t) ∈ k and (h † , r, t † ), ∈ k † (h,r,t) . to guarantee that the feasible set of this program is nonempty, we introduce non-negative slack variables ζ i and minimize the residual. this construction is similar in nature to the well-known "pair-wise transform" @xcite where the ordinal ranking problem its transformed into a two-class classification problem by considering the difference of all comparable elements. if we define x (h,r,t),(h † ,r,t † ) := s(h † , r, t † ) -s(h, r, t), then this allows us to concisely express a convex program that is identical to the svm formulation described above, namely our proposed model has several distinguishing features: ## implementation we solve our programs using the linearsvc class from scikit-learn @xcite , which uses liblinear @xcite , numpy @xcite and scipy @xcite . in particular we rely heavily on scipy for its sparse array structures. the primary bottleneck is a onetime cost to build the set of negative triples which, fortunately, is an embarrassingly parallel workload. to reduce the cost in time to build the problem, we leverage the multiprocessing capability of the dataloader class of pytorch @xcite . one of the two main loops used to construct the data fed into the svm is presented in algorithm 1. the loop shown selects the negative triples where the head of a given positive is replaced. a separate, and nearly identical loop, builds the tail-corrupted triples. the returned values of algorithm 1 are problem data x with labels y. since the labels are selected with balanced probability, the expected bias of the optimal solution is 0, and the svm solver is instructed to set the intercept to 0. a naive implementation of the program does not scale due to large memory requirements. several tricks are employed when constructing the svm data and evaluating metrics. each relation and entity is 1-hot encoded as a vector in k := |e| + |r| dimensions, and we seek a symmetric matrix that acts on k-dimensional embeddings; our problem dimension is k(k + 1)/2. even for modest values of k, the problems passed to svm solvers can be quite large (see if b is a symmetric matrix, and w := vec b, then the entry of w that corresponds to entry @xmath8 if x and y are one-hot encoded and supported on indices i x and i y , then: this has an equivalent form using the function s, which was defined in (6). in this form that uses s, there is a space-savings gain of 1/2. additionally, one has the guarantee that the matrix b, when reconstructed from the coefficients of the svm, is symmetric. the feature x := h + r -t has at most three nonzero entries and is itself sparse. in practice, it is expensive to evaluate the outer product xx and project onto the upper-triangular portion millions of times. instead we simply evaluate the quadratic form directly using (7); at most 6 entries with fixed values are required: three on-diagonal entries and three off-diagonal entries. with such large investment for performance gains, one may ask whether it is possible to simply take advantage of gpu hardware, and the wellestablished gains that can be had beyond standard cpu processors. unfortunately, widely-available gpus do not effectively leverage sparse data structures for improved performance. indeed, commercial linear and quadratic solvers, which are commonly employed to solve sparse problems, do not support gpu hardware @xcite . ## experiments we use three knowledge graph datasets to benchmark our implementation; two are the standard link prediction benchmark datasets freebase @xcite and wordnet @xcite , and one is a new knowledge graph we introduce. we report performance on all three. for freebase (fb15k) and wordnet (wn18) we use the versions distributed in the software package released by the authors of rotate @xcite . we now briefly describe the data sets. wn18 wordnet is a knowledge graph that provides lexical relationships between words @xcite . it is designed to be machine readable, while being a usable dictionary and thesaurus. ## results since the model we use is very similar to that of transe, we expect similar performance characteristics. timings report build times using a 96 cpu core processor on a machine running ubuntu 18.04. as problem build is highly parallelizable, times are inversely-proportional to the number of available cores. since the svm solver we use is singlethreaded, the additional cores are not necessary for training; only sufficient memory is necessary. thus, it makes sense to build the program with a compute-optimized configuration and solve the problem with a memory-optimized configuration. multiple values of c may be fit simultaneously, provided local memory is sufficient. in the transe framework, the choice of solver and parameter settings @xcite has a dramatic impact on solver performance. hyperparameter complexity is in contrast to our use of the default parameter settings of the svm solver, which we use without modification. the svm solver that we use, which was distributed in @xcite , is singlethreaded. this, in turn, calls the lower-level library @xcite , which is tailored to large-scale and very sparse support vector problems. the developers of the liblinear solver have invested significant effort over many years to iden- the soft-margin support vector network that we use was introduced in @xcite . the idea of representing data quadratically and training an svm to derive a symmetric matrix was applied in @xcite to remove the need to choose a distance function by hand and instead define a distance function as the solution to a convex program. in that work, the distance function was the solution to a linear program, and extracting a distance from the solution was made possible by enforcing side condition that guaranteed the resulting set of coefficients satisfied diagonal dominance. this allowed the reconstructed matrix to be positive semidefinite, and the optimal distance could then be extracted using a matrix square root, found through a cholesky decomposition. in this work, we are representing data quadratically, but we do not have the side condition. a similar, but not quite equivalent idea, is to fit an svm using a quadratic kernel. our svm program is both sparse and convex. we note that very recent work @xcite in the space of extractive text summarization also leverages sparsity and convexity to efficiently solve an optimization program. in our program, when both terms in the objective are the 1-norm, the svm may be written as a linear program. this is attractive, for linear programs have the theoretical guarantee of a polynomial-time solution. knowledge graph link prediction relational learning and knowledge graph link prediction is a large field of machine learning research. one early model is rescal, which is a tensor decomposition method @xcite for learning relations in a knowledge graph. the idea of the model is to factorize a tensor into a core tensor multiplied by a matrix along each dimension. the core idea adapts the earlier dedicom @xcite tensor factorization scheme. this method was notable for scalability and improved training times. subsequent to transe, which was a landmark evolution in the performance of link prediction, there has been much research and analysis into the structure of links in knowledge graphs @xcite @xcite . relation paths, which are a compound structure, have also been used to extend the transe model @xcite . since its introduction, and case-based reasoning for knowledge graph completion was introduced in @xcite . the authors show that a k-nearest neighbor (knn) based approach for can be both efficient and scalable for this application. ## conclusion and future work we demonstrate feasibility of using off-the-shelf svm libraries to address the knowledge graph linkprediction problem. we present results on standard benchmarks that achieve parity with baseline models, while total wall clock time is measured in minutes rather than hours. the model structure we introduce is closely related to a well-established model with good performance characteristics, and it is elementary. the model we introduce has very few parameters to tune, and default solver settings typically yield satisfactory performance. with the increasing focus on the large time, cost and energy consumption required to train leading machine learning models, it seems reasonable to ask whether casting nonconvex programs as convex programs could provide a path towards more efficient model training without significant sacrifice in performance. one benefit of our convex formulation is the ability to add constraints to the program. future directions could introduce rules about the knowledge graph using this method, as proposed in @xcite . simple "if p then q" first order logic propositions, where p and q are linear predicates (equal, larger that, smaller than) can be represented by polyhedral sets of the form @xmath12. in this way, conditional information in the form of knowledge sets can be considered during the training process. one could also aim to adapt the model to yield proper embeddings by adding additional constraints such as diagonal dominance to the matrix b rather than just scores. another direction we would like to explore is how we can introduce nonlinear data models so our problem does not suffer from the same expressivity limitations as transe. it may be possible to adapt a model derived from rotate, for instance. finally, the model that we present scales quadratically in the number of entities and relations, and the dimensionality of the representation is a function of the problem. it would be useful to find a representation that has good performance without the quadratic growth in dimension.