Knowledge Graph Representation Learning using Ordinary Differential Equations (2021)

Abstract: Knowledge Graph Embeddings (KGEs) have shown promising performance on link prediction tasks by mapping the entities and relations from a knowledge graph into a geometric space. The capability of KGEs in preserving graph characteristics including structural aspects and semantics, highly depends on the design of their score function, as well as the inherited abilities from the underlying geometry. Many KGEs use the Euclidean geometry which renders them incapable of preserving complex structures and consequently causes wrong inferences by the models. To address this problem, we propose a neuro differential KGE that embeds nodes of a KG on the trajectories of Ordinary Differential Equations (ODEs). To this end, we represent each relation (edge) in a KG as a vector field on several manifolds. We specifically parameterize ODEs by a neural network to represent complex manifolds and complex vector fields on the manifolds. Therefore, the underlying embedding space is capable to assume the shape of various geometric forms to encode heterogeneous subgraphs. Experiments on synthetic and benchmark datasets using state-of-the-art KGE models justify the ODE trajectories as a means to enable structure preservation and consequently avoiding wrong inferences.

## introduction knowledge graphs (kgs) have a significant impact on machine learning approaches @xcite . a kg usually represents factual knowledge in triples of the form (entity, relation, entity) e.g., @xcite . the nodes of a kg represent entities and the links denote the relations. although quantitatively kgs are often large-scale with millions of triples, they are usually incomplete i.e. do not capture all knowledge within a domain of interest. to address this problem, various approaches have been used so far, among which link prediction using kg embeddings (kge) attracted growing attention. kge models map entities (e) and relations (r) of a kg from a symbolic domain to a geometric space (e.g. a vector space). such embedding models employ a score function to perform the link prediction task, which uses the learned embedding vectors (e t , r, e t+1 ) of a triple (e t , r, e t+1 ) to compute its plausibility. this allows to rank triples by their score, where a correct triple should obtain a higher score and a lower rank than an incorrect triple. kge models have been predominantly studied with a focus on the triple level. however, in a broader view, triples of a graph form specific subgraphs (i.e. structural patterns distributed in the graph) in local structures. the preservation of subgraphs in the learned representations is a major challenge. in this regard, the choice of geometry becomes crucial as the distribution of the corresponding embeddings for entities and relations depends on it. furthermore, within each geometry, the mathematical operations used in the score function lead to differences in the encoding capability of kges. several stateof-the-art kge models @xcite @xcite the figure illustrates a path and loop of the "influences" relation in a small excerpt of the yago kg for a chain of notable people who have influenced the other. the heat map shows that several other models incorrectly predict a loop for the chain of influencers at the bottom by assigning a high value for the triple p10 (marked red) as they model relations independent of entities. as an example, consider figure 1 , which contains both a loop/cycle and a path (without cycles) for the "influences" relation. many kge models incorrectly predict the path to be closed in such a scenario. the root cause of this problem lies in the entity-dependent nature of the "influences" relation. most of the kge models such as rotate (as well as transe, complex, quate) consider relations independent of entities. this problem can usually only be mitigated at the cost of increasing the dimensionality of the model, which leads to higher computational costs and may negatively impact the usefulness of learned representations in downstream machine learning tasks. for those kges with sophisticated geometry, only a limited number of structures such as hierarchical or tree-like have been studied by using hyperbolic geometry or poincaré ball models @xcite . in order to significantly improve the structure preservation capabilities of kge models, we propose a novel kge model named fielde which employs differential equations (des) for embedding kgs into a vector space. the use of differential equations allows to overcome the entityspecific nature of previous kge models. in this model, relations are viewed as trajectories connecting neighboring nodes in the graph, which implies a continuity of changes in the embedding space and consequently describes the underlying geometry. this is especially important, because the success of a kge model depends on the way it correctly specifies the underlying geometry that describes the natural proximity of data samples in a geometric space @xcite . designing fielde with a list of well-specified geometries (euclidean, poincare ball, hyperboloid, and spherical) a) improves generalization and b) increases the interpretability. this is due to capturing the natural proximity of entities from kg space to the geometric space. we employ first-order ordinary differential equations, which are a special class of des that represent a vector field on a smooth riemannian manifold. we selected first-order odes, because of their advantages over other classes of des: while being capable of capturing complex geometries, they are also efficiently implementable. to allow our approach to self-adapt to the complexity of the underlying knowledge graph, we developed a neural network based approach which learns a suitable geometry from the training graph itself. therefore, fielde combines substantial previous research and insights of des, embeddings and neural networks in order to provide a comprehensive model capable of representation learning on kgs with multiple heterogeneous subgraphs. ## related work we describe the kge models exploiting geometric properties for structure preservation. we also review odes in ml in general, as our model is, to the best of our knowledge, the first approach employing odes in kges. kges in euclidean geometry. apart from some discussions about encoding relational patterns, capturing structures is not directly targeted by most previous work in kge models. transe @xcite discussed simple 1-1 relational patterns and its follow up models @xcite @xcite considered 1-many, many-1, and many-many patterns. rotate @xcite uses rotational transformations for encoding more complex patterns such as symmetry, transitivity, composition, reflexivity and inversion. some other kges such as dismult @xcite , complex @xcite , only focus on effective choices of embedding by element-wise multiplication of transformed head and tail or angle transformation in quate @xcite , and rescal @xcite , kges in non-euclidean geometry. several works such as murp, roth, refh, atth @xcite use non-euclidean geometry for hierarchical structures only @xcite . in @xcite , random walk and heterogeneous skip-gram models are used to generate the embeddings of different structures without leveraging des. recently, @xcite used fréchet mean and geometries for capturing structures but not for link prediction task. ## preliminaries and background this section provides the preliminaries of the riemannian geometry @xcite and explains its key elements required to understand our model. the aim of our model is to embed nodes (entities) of a kg on trajectories of vector fields (relations) laid on the surface of a smooth riemannian manifold. therefore, we first provide the mathematical definitions for manifold, tangent space and vector field driving the dynamics of a de on the manifold. ## model analysis in this part, we analyse the characteristics of the core formulation of fielde compared to other models. we first show that while other models such as rotate, and complex face issues when learning relatively simple single-relational structures, fielde is able to overcome those issues. moreover, we show that fielde subsumes popular kges and consequently inherits their capabilities in learning various well-studied patterns e.g. symmetry/inversion. ## experiments and results in this section, we compare fielde foot_0 against transe, rotate, complex, quate, dismult, murp, atth, roth, and refh as those performed best on the presented benchmarks. the experiments are done over four benchmark datasets namely fb15k-237, wn18rr, yago3-10, and youtube. we presented two versions of fielde namely dfielde and sfielde. dfielde uses the distance function ( (5)) for score computation whereas sfielde uses the inner product (see equation ( 6 )). the comparisons are performed in low and high dimensions. we also considered the evaluations with and without data augmentation (adding reverse triples). evaluation metrics we use the standard metrics for link prediction: mean reciprocal rank (mrr), and hits@n (@xmath0, 3, 10). mrr is measured by nt @xmath1, where r j is the rank of the j-th test triple and n t is the number of triples in the test set. h@n is the number of test triples ranked less than n. ## conclusion we presented fielde -the first representation learning model for knowledge graphs based on ordinary differential equations. in contrast to previous models, fielde models relations as vector fields on a riemannian manifold and thereby overcomes the drawbacks of previous works, in which relations are entity-independent. furthermore, we developed a neural network based approach allowing to learn a suitable geometry from the training graph. we have both empirically and analytically shown that fielde can preserve subgraph structures in the embedding space better than state-of-the-art models. formally, fielde is a generalisation of several state-of-the-art kge models and we could formally show that it subsumes transe, rotate, com-plex and quate. evaluation on standard benchmark datasets shows competitive or superior performance of fielde across all datasets and metrics.