Exploratory search on expert knowledge graphs

Abstract

Die Erkundung unserer Umgebung ist ein wichtiger Bestandteil der menschlichen Aktivtät. Beginnend in unserer frühesten Kindheit, wird diese mit lernen, kognitiver Entwicklung, sozialem Verhalten und Anpassungsfähigkeit assoziiert. Obwohl ein zentraler Bestandteil unseres Verhaltens, wird der Erkundung kein angemessener Stellenwert im derzeit dominierenden Such-paradigma beigemessen, welches sich auf die einmalige Extrahierung von Elementen zu einer gegebenen Menge von Schlüsselwörter konzentriert. Forschung im Bereich der \emph{explorativen Suche} versucht dies zu ändern, indem ein Augenmerk auf interaktives Suchverhalten wie das Lernen und die Erkundung der Suchergebnisse gelegt wird. Für Maschinen ist es jedoch schwierig solche komplexen menschlichen Verhaltensweisen zu unterstützen. Dennoch hätte ein exploratives Suchsystem einen enormen Einfluss. Unternehmen in der ganzen Welt haben Schwierigkeiten ihr intellektuelles Kapital zwischen Mitarbeitern zu transferieren. Ein System, welches Mitarbeiter bei der Exploration und dem Erlernen dieses impliziten Wissens hilft, ist nicht nur ein finanzieller Vorteil, sondern trägt auch dazu dabei, dass Wissen nicht verloren geht. Obwohl kürzlich vielversprechende Ergebnisse im Bereich des Semantic Web publiziert wurden, ist wenig über mögliche Basisalgorithmen für explorative Suchsysteme bekannt. Einer der hervorstechendsten Merkmale von Daten im Semantic Web ist deren Graph-Struktur. Die Diplomarbeit untersucht zwei Arten von Graphalgorithmen und deren Eignung für explorative Suche: Zentralitäts- und Ähnlichkeitsmetriken. Drei Algorithmen wurden im kürzlich publizierten Gather-Apply-Scatter Modell für die Verwendung mit Triple Stores neu formuliert. Zusätzlich wird eine neue Variation der auf Information Content basierenden Ähnlichkeitsheuristiken vorgeschlagen. Eine kürzlich publizierte und speziell für das Semantic Web entwickelte Ähnlichkeitsheuristik rundet den Mix ab. Die Algorithmen wurden auf eine Unterart von semantischen Graphen --- Expert Knowledge Graphs --- angewandt, welche domänenspezifisches aber komplexes Expertenwissen enthalten. Die Ergebnisse von zwei verschiedenen Expert Knowledge Graphs wurden statistisch, wie auch qualitativ, in Hinblick auf explorative Suche evaluiert und verglichen. Während die Zentralitätsmetriken relevante Knoten effektiv herausfiltern konnten, war die Differenzierung weniger relevanter Knoten kaum gegeben. Die Ähnlichkeitsmetriken zeichneten sich durch hohe Anforderungen an die Struktur des modellierten Wissens aus. Waren diese erfüllt, so wies die neu vorgeschlagene Ähnlichkeitsheuristik die vielversprechendsten Resultate aus.

Exploration of objects and the environment around us is an important part of human activity. Starting in our early infancy, it is closely associated with learning, cognitive development, education, social behavior and adaptability. Although exploration is such a vital trait, it did not receive proportional attention in today's dominating lookup-based search paradigms, which are typically only focused on the one-off retrieval of a set of items matching a set of keywords. Research in \emph{exploratory search} set out to change that by including interactive search activities like learning and investigation of the result space. But supporting such elaborate human traits is notoriously hard for machines to do. However, being able to build a system that assists users in exploratory search would have a tremendous impact. Businesses around the world are struggling with the transfer of hard-built intellectual capital between their employees. Helping them to explore and learn this expert knowledge is not only financially beneficial, but also prevents knowledge from getting lost or stale. Recent advances using semantic web technologies show promising results. Still, little is known about which algorithms could be used at the core of an exploratory search system. One of the distinguishing properties of data specified via semantic web standards is their graph structure. This diploma thesis investigates two groups of graph algorithms and their eligibility for exploratory search: centrality and similarity metrics. To that end, three well-known algorithms were redesigned in the recently published Gather-Apply-Scatter graph processing paradigm for use in triple stores. Additionally, a novel variation of information content based similarity metrics is suggested. The mix is completed by a recently published similarity heuristic specifically designed for the semantic web. The algorithms were applied to a special kind of semantic graphs --- Expert Knowledge Graphs --- featuring enterprise-scale, domain-specific but complex expert knowledge. The results from two different expert knowledge graphs were evaluated and compared statistically, as well as qualitatively, particularly with respect to exploratory search. While the evaluated centrality metrics turned out effective in suggesting high-profile nodes, they fell short on distinguishing between less important nodes. The tested similarity metrics were found to make high demands on the structuring of the encoded knowledge. If met, the newly suggested similarity heuristic turned out to yield the most promising results.