Knowledge Graph Embeddings using Neural I to Process: From Multiple Walks to Stochastic Trajectories (2023)

Abstract: Knowledge graphs mostly exhibit a mixture of branching relations, e.g., hasFriend, and complex structures, e.g., hierarchy and loop. Most knowledge graph embeddings have problems expressing them, because they model a specific relation r from a head h to tails by starting at the node embedding of h and transitioning deterministically to exactly one other point in the embedding space. We overcome this issue in our novel framework ItCAREToE by modeling relations between nodes by relation-specific, stochastic transitions. Our framework is based on stochastic ItCARETo processes, which operate on low-dimensional manifolds. ItCAREToE is highly expressive and generic subsuming various state-of-the-art models operating on different, also non-Euclidean, manifolds. Experimental results show the superiority of ItCAREToE over other deterministic embedding models with regard to the KG completion task.

## introduction knowledge graphs (kgs) play a central role in many ai-related tasks @xcite such as recommendation systems @xcite and question answering @xcite . kgs represent real-world knowledge as a set of facts in the form of triples (entity, relation, entity), e.g., @xcite . entities are nodes of a graph and relations are the directed edges. kgs are highly incomplete which adversely affects the outcome of various kg-centered tasks. to tackle this problem, various link prediction approaches have been proposed to leverage the existing links for the prediction of new ones (a.k.a., knowledge graph completion). among existing approaches @xcite , kg embedding (kge) succeeded and became a popular line of work. kge models map entities and relations in kgs into a low dimensional geometric space and measure the plausibility of each triple (entity, relation, entity) by a scoring function f that uses the embedded vectors of this triple @xcite to gauge its plausibility by a real, positive value f (entity, relation, entity). prominent examples of kges include translational/rotational families @xcite , bilinear families @xcite and neural network families @xcite . however, these models are all defined in euclidean space that suffers from modeling complex structures such as hierarchies @xcite in low-dimensional vector space. therefore, kg embeddings based on non-euclidean geometric spaces such as hyperbolic space @xcite have been proposed. both lines of work often formulate the relationspecific transitions between subsequent nodes in a deterministic way and represent them, e.g., by translations or rotations, implying that with regard to a particular relation each node is connected to a single other node. in a broader view, this implies that starting from an embedded node with a given single relation type, there will be only one walk with the length m, which is m subsequent relation-specific transitions from the starting node, and this walk will lead to another specific embedded node. however, starting at any specific node and considering a branching relation such as hasfriend, there may be several relation-specific walks of length m. these walks define a group of nodes in distance m. figure 1 illustrates the limits of traditional embedding models based on translation or rotation with deterministic transitions (a) and contrasts it with the tree-like structure that unfolds in a non-deterministic model (b) able to represent a branching relationship. in this paper, we formalize probabilistic walks of length m -1 between two groups of nodes (ω t 1 , ω tm ) in order to represent branching relationships. each group of nodes ω t i from start ω t 1 to end ω tm is represented by a random variable x t i , which indicates a probabilistic distribution on the manifold x t i : ω t @xmath0, @xmath1, . . . , m. the sequence of random variables @xmath2, x t 2 , . . . , x tm } constitutes a stochastic process. a sample, also called realization, of the stochastic process s is a walk with m-1 transitions containing m entity representations {e t 1 , . . . , e tm } on the manifold, e t @xmath3. we model probabilistic transitions between groups of nodes using the itô process, which defines transitions between nodes through an integral containing drift and diffusion. drift models the deterministic nature of a transition, while diffusion captures stochastic variation. drift and diffusion operations are learned separately via a relationspecific neural network. owing to the probabilistic perspective, we develop a kge model, called itôe, that uses the itô process for stochastic transitions as well as various, also non-euclidean, manifolds (i.e., sphere, poincaré ball, hyperboloid) to support the modeling of heterogeneous graph structures on manifolds. we also provide an extensive theoretical investigation and prove that itôe: a) is fully expressive; b) is capable of encoding various structures as stochastic processes; c) subsumes various state-of-the-art kge models, including complex and quate, d) models various relational patterns, e.g., symmetric patterns. experimental results show the superiority of our model, especially in low-dimensional space. node2vec @xcite @xcite @xcite are among the models which perform a biased random walk in graph space and compute the low dimensional representation of nodes in such a way to maximize the likelihood of preserving network neighborhoods of nodes. the random walk-based models are not among state-of-the-art kge models in the link prediction task. in addition, in most cases, the random walk is performed in the graph space to obtain the sequences of nodes for embedding, but the notion of walk in the embedding space is neglected as there is no transition function in the embedding space to model this. non-euclidean kge models euclidean-based kge models are not capable of preserving complex graph structures in a low-dimensional space. however, embedding kgs on non-euclidean manifolds has shown promising performance in the preservation of a few structures, especially in lowdimensional spaces. @xcite @xcite showed the advantage of poincaré ball and other geometries for embedding graphs with various structures including hierarchical structures. 5 * e @xcite utilized the projective geometry with the five main transitions, namely translation, rotation, inversion, reflection, and homothety, to capture heterogeneous structures such as loop-path subgraphs. (nayyeri et al., 2021b) embedded kgs on the vector field. ultrae @xcite considers a mixture manifold-pseudo-riemannian space that generalizes hyperbolic and spherical spaces. other manifold-based kges can be found in @xcite . overall, the mentioned models suffer from the same problem mentioned for the euclidean counterpart, i.e., deterministic transitions between embedded nodes. ## preliminaries stochastic process let t be an arbitrary index set. a stochastic process is a collection of random variables @xmath4: @xmath5. all random variables x t : ω t -→ r d , e t -→ x t (e t ), @xmath6. a random experiment (realization) is a selection of an outcome x t (e t ) ∈ m at random considering the probability measure p. a sample path of a stochastic process @xmath7: @xmath8, giving us a random walk. figure 2b illustrates a random walk in the vector space with 50000 steps. brownian motion a stochastic process @xmath9, @xmath10, f, p) (f is a sigma algebra (events)) is a brownian motion if a) b(0) = 0; b) b has independent and stationary increment, i.e., b(t 1 ), b(t 2 )-b(t 1 ), . . . , b(t n )-b(t n-1 ) are independent random variables for 0 < t 1 < . . . < t n ; c) b has gaussian increments, i.e., b(t n + α) -b(t) ∼ n (0, α), ∀@xmath11, α > 0; and d) b has continuous sample paths, i.e., b is continuous in t. figure 2a shows the evolution of two tree structures via the brownian motion of several particles. brownian motion is suitable to model probabilistic branching in random walks as path diffusion when traversing the embedded kg in a vector space. in our setting, we will write interchangeably b(e t ) and b(e t ) for b(t). ## itôe: neural itô process embedding we introduce itôe, a novel kge model that utilizes the stochastic processes on manifolds for kg embedding. itôe is capable of preserving various graph structures and capturing branching relations by modeling the evolution of graph structures in the embedding space as a stochastic process. kge models have four essential components: entity and relation representation, score function, and loss function. in the following, these four components of itôe are explained. entity representation let's suppose that e represents the collection of all entities present in the knowledge graph (kg). each symbolic entity @xmath12, i.e., @xmath13. therefore, entity embeddings are points on the manifold. in the proposed model, we use poincaré ball, hyperboloid, euclidean, and sphere manifolds. relation representation each fact in a kg is represented by a triple (e t , r, e t+1 ). because the entities in a triple are subsequent but with arbitrary indexes, we use the notation (e tn , r, e t n+1 ) to represent the triple, where n is between 1 and |e| (number of entities in the kg). most kge methods model the transition from e tn to e t n+1 via a relation-specific transition (e.g., translation, or rotation). therefore, each relation is modeled as a point-wise deterministic transition. however, in a broader view, the relational dependencies between nodes are stochastic processes, i.e., a transition to a tail given a head node and a relation happens with a probability so that the sequence of such probabilistic transitions constitutes a stochastic process. each random variable in the stochastic process includes all the entities e, a few of which has a non-zero likelihood since the transition from a given entity is only possible to its neighbors. the group of neighbors at each step together with their likelihood in a probability space is considered a random variable. as a result, there is a relational mapping between two random variables x tn , x t n+1 , associated with the two groups of nodes ω tn , ω t n+1 at each step. in the following, we model a relation r (defining transitions between nodes) as a stochastic process s r . to explain this, let us view the notion of walks formed by a relation r from a stochastic processes angle. a sequence of symbolic entities, connected by a relation r forms a walk with a particular length. a walk of length n -1 includes n entities and is shown by p @xmath14, e t 2 , . . . , e tn }. assume that there are multiple walks from a set of given entities ω t 1 associated to x t 1 , to a set of entities in ω tn associated to x tn . the transition between the nodes in a walk is done randomly according to a distribution. during traversing the graph from a starting node taken from x t 1 to a target node, taken from x tn , and at each step t i , there are n i possible options for selecting the next node. therefore, traversing a graph with walks of length n -1 (with relation r) leads to a stochastic process s @xmath15, x t 2 , . . . , x tn }. consequently, each relation in the kg is represented by a stochastic process. in this paper, among various stochastic processes, we employ the itô process for modeling each relation r due to the simplicity of implementation and controlling drift and diffusion. the itô process is defined as therefore, each two subsequent sampled entities lie on a geodesic curve (shortest path). because the above equation is a stochastic process on a manifold, at each iteration of batch learning, a set of entities in batch triples are observed randomly to hold this equation (realization) as follows: note that x t i (e t i ) = e t @xmath16, @xmath17, . . . , n is entity embeddings. scoring function for a given triple (e tn , r, e t n+1 ), the score is as follows for positive (negative) triples, f (e tn , r, e t n+1 ) is a high (low) value. that is, the two sampled entities e tn , e t n+1 lie on a geodesic curve on a manifold. in the next section, we present important insights about our formulation, followed by theoretical justification for the core formulation of our model. ## insights and theoretical analysis memory complexity in itôe, the number of relation parameters grows linearly with the relation's dimensionality. hence, itôe's space complexity is o(n e × d e + n r × d r ), where n e and n r are the numbers of entities and relations, d e and d r are the embedding dimensionality of entities and relations, respectively. the additional parameters come from the neural network that approximates the itôe' process, which is in our case, shared across all entities. relational sub-structures here we show the capability of the stochastic process in equation ( 5 ) for modeling various graph sub-structures. to this end, let us have a sample walk from the stochastic process s r , which is {x t 1 (e t 1 ), . . . , x tn (e tn )} = {e t 1 , . . . , e tn }. a stochastic process s r inherently covers various graph structures such as hierarchy, loop, and path. this is due to the fact that various sample walks over a stochastic process generate different parts of a subgraph. figure 3 shows an example of a stochastic process for the relation connectedt o which forms several relational and structural patterns such as loop and path by sampling from the process in the airport example (airports are connected with various shapes). another example is a tree-like structure. for tree-like structures (see figure 1 ), x t 1 contains only a root node, and x tn contains all the leaves. x t i , @xmath18, . . . , n -1 generates the intermediate nodes from the root to the leaves. therefore, any walk from the root node to each of the leaves is a sample taken from the stochastic process. the relation-specific stochastic process generates various sample walks at random covering various parts of a sub-graph. as a consequence of theorem 1, itôe is fully expressive and capable of capturing various graph structures and relational patterns that each of the mentioned models is capable of. therefore, the following corollaries hold: corollary 1. itôe is fully expressive, i.e., for every ground truth over an arbitrary kg, there are assignments to the entities and relations embedding to capture the ground truth. ## conclusion this paper presented itôe, a knowledge graph embedding model that considers the stochastic transitions between nodes of a knowledge graph on a manifold. for doing so, itôe modeled the relations in a kg as stochastic processes so that the transitions between two nodes could only happen with an associated likelihood. such stochastic transitions allowed itôe to present multiple stochastic trajectories between any two embedded nodes and to capture more sophisticated structures in kgs, including loops connected to paths and is mathematically proved to be a generalization of several state-of-the-art models. experiments on the syn-thesized datasets showed that the proposed model can capture heterogeneous complex structures and patterns.