Exploring Graph Traversal Algorithms for Knowledge Graphs
Sven Bulach · Repository KITopen (Karlsruhe Institute of Technology) · 2021
Knowledge Graphs (KGs) are semantic databases where entities that represent real world objects are related to each other.The entities are provided with attributes and put into thematic context or ontologies.Most KGs follow the RDF standard which makes the knowledge that is stored in such graph machine-understandable.Since KGs like DBpedia pursue the goal of collecting as much information as possible, they take on gigantic dimensions.The KG that is used for this thesis is DBpedia.One important aspect of graph theory is graph traversal which is generally very well studied, but not specifically for Knowledge Graphs.In this thesis, the two algorithms Dijkstra and A-star are used to find paths between two nodes in a KG.They are compared in terms of path length and search time.For the Dijkstra to work, the examined graph will be weighted based on the degrees of nodes.In order to apply the A-star algorithm, two heuristics are introduced which use the rdf:type information given by DBpedia.The rdf:type relation assigns entities that share common characteristics into a corresponding type.Finally, a feedforward neural network is used to predict the shortest distance between two nodes of a Facebook graph.Knowing the shortest distance between two nodes can be useful information that can be exploited for instance by the A-star algorithm.Average search time per path length for each approach set B . . . . . . . .Average time per path heuristic 1 set B . . . . . . .