# Traversing Knowledge Graph in Vector Space

**Explanation of Research paper -> ****https://arxiv.org/pdf/1506.01094.pdf**

**What is Compositional Knowledge Base Representation?**

Compositionalization is the approach of using Vector Space Models to complete the Knowledge Base. A Base Vector Space model is considered as a Soft edge Traversal Operator through the Knowledge graph. Compositionalzation involves using base Vector Space models to traverse through the Knowledge Graph and predict the path for each and every path query.

Compositional Knowledge Base tries to reduce the Cascading errors by moving the entities close to the centroid; in other words, compositionalization of Knowledge Graph brings about structural regularization which helps avoiding the Cascading errors as we traverse from one entity to another in the Knowledge graph.

Let us consider Bilinear model for Knowledge Base Completion using Compositionalization. The path query is defined as q = (s/r) where s= entity, r=edge/relation. In order to determine if an entity “t” is connected to entity, “s”, the scoring is performed using the formula,

score(q,t) = (xs^T *Wr*xt)

In the above formula,

xs, xt = Vector representation of entities.

Wr = A Matrix of Relations.

In other words, in a Compositional Knowledge Graph, each of the entities are represented as Vector Entities and a Score is calculated for every path query to determine if an entity “t” belongs to the solution of path query. Score (q,t), where q= (s/r) basically calculates the number of unique paths in a knowledge graph to traverse from s to t through all of the existing edges or relations. In order to find out all the unique paths from entity s to entity t, traversal operator is applied. Initially when we start traversing through the Knowledge Graph, it starts with the Vector entity xs and as soon as a new entity is reached during the traversal phase, a set vector is created which consists of all the entities traversed until that point. The final step of Compositionalization of Knowledge Graph includes applying the Membership Operator which determines if the entity “t” belongs to one of the unique paths identified.

In order to summarize,

i) Compositionalizaion of a Knowledge Graph identifies the number of unique paths from vector entity “s” to vector entity “t” using the Score calculation.

ii) Converts Entities to Vector Entities and a matrix of edges or relations is calculated, a Membership Operator is finally applied to determine if the vector entity, “xt” belongs to the one of the unique paths connecting it to the source vector entity, “xs”.

**2) How does this paper improve a Compositional Knowledge Embedding Model such as TransE.**

TransE is one of the state of the Art model for Compositional Knowledge Embedding.

The TransE model using the scoring function, — || xs + wr -xt||. The Traversal Operator can be defined as (xs + wr). In TransE model, given a path query as we traverse from source entity S to target entity t, Cascading errors are added in each step of Traversal. These Cascading Errors can be termed as Noise. The paper suggests that training Compositional TransE pulls the Vector entities closer to the original arrangement which in turn reduces the Cascading Error generated with every step of traversal. The paper suggests, in order to reduce the Cascading error, a term objective(λ|| xs + wr -xt|| ) was introduced with the idea of reducing the distance between xsWr and Xt over different values of λ (0.001, 100) but there was no improvement in path query which implies Compositional Training is very effective in reducing Cascading Errors in TransE as well as Bilinear model.

**3) How would you improve upon this work?**

Upon going through the paper, I have the following suggestions/ improvements which can enhance the efficiency of Compositional Knowledge Graph. They are as follows:-

i) In the compositional technique, we have the concept of Scoring function which essentially calculates all the unique paths from source entity “s” to target entity “t” which has it’s own time complexity based on the number of edges/relations. An effective approach would be to analyze the semantic relationship and take into account semantic similarity between the Question and the edges in the Knowledge Graph could lead to a faster, efficient real-time traversal of the Knowledge graph. Inspired by https://arxiv.org/pdf/1609.00464.pdf

ii) The representation of sets obtained after Traversal can be represented by the order of Latent Semantic Density (The number of ideas represented through one path traversal from source entity “s” to target entity “t”). Continuing this way, we can perform Semantic Density Analysis for all the paths traversed and conduct Semantic coherence between the question and the solution which leads us to identifying the contextually correct solution irrespective of the number of unique paths from source entity “s” to target entity “t”.