Algorithmic building blocks for relationship analysis over large graphs

Abstract

Over the last decade, large-scale graph datasets with millions of vertices and edges have emerged in many diverse problem domains. Notable examples include online social networks, the Web graph, or knowledge graphs connecting semantically typed entities. An important problem in this setting lies in the analysis of the relationships between the contained vertices, in order to gain insights into the structure and dynamics of the modeled interactions. In this work, we develop efficient and scalable algorithms for three important problems in relationship analysis and make the following contributions: - We present the FERRARI index structure to quickly probe a graph for the existence of an (indirect) relationship between two designated query vertices, based on an adaptive compression of the transitive closure of the graph. - In order to quickly assess the relationship strength for a given pair of vertices as well as computing the corresponding paths, we present the PathSketch index structure for the fast approximation of shortest paths in large graphs. Our work extends a previously proposed prototype in several ways, including efficient index construction, compact index size, and faster query processing. - We present the ESPRESSO algorithm for characterizing the relationship between two sets of entities in a knowledge graph. This algorithm is based on the identification of important events from the interaction history of the entities of interest. These events are subsequently expanded into coherent subgraphs, corresponding to characteristic topics describing the relationship. We provide extensive experimental evaluations for each of the methods, demonstrating the efficiency of the individual algorithms as well as their usefulness for facilitating effective analysis of relationships in large graphs.

Im Laufe des letzten Jahrzehnts hat die Modellierung von direkt sowie indirekt verknüpften Entitäten in Form von Graphen – wie z. B. von Personen in sozialen Netzwerken oder semantisch annotierten Konzepten in Wissensbasen – eine wichtige Rolle in vielen Geschäfts- und Forschungsfragestellungen eingenommen. Der Umfang der in dieser Form modellierten Daten liegt in vielen Fällen in der Größenordnung von Millionen von Entitäten und Verknüpfungen. Ein wichtiges und vielversprechendes Problemfeld in diesem Bereich ist die effiziente und effektive Analyse der (indirekten) Beziehungen zwischen benutzerspezifizierten Entitäten, um Erkenntnisse über die Struktur und Dynamik der modellierten Interaktionen zu erhalten. In dieser Arbeit betrachten wir drei fundamentale Fragestellungen in der Analyse von Beziehungen in graphstrukturierten Daten und stellen die folgenden Beiträge vor: • Erreichbarkeitsanalyse befasst sich mit der effizienten (d. h. in Echtzeit ausführbaren) Überprüfung des Graphen auf die Existenz einer möglichen Beziehung zwischen zwei Entitäten. In dieser Arbeit stellen wir den Ferrari-Algorithmus zur schnellen Verarbeitung dieser Analysevariante vor, basierend auf einer adaptiven Form der Kompression der transitiven Hülle des Graphen. • Wir stellen die PathSketch Indexstruktur vor, ein System zur schnellen Approximation der Stärke einer Beziehung zwischen zwei Entitäten, sowie der Identifikation eines oder mehrerer zugehörigen Pfade. Das in dieser Arbeit vorgestellte System erweitert einen vorausgehend publizierten Prototyp hinsichtlich effizienter Durchführung des Indexaufbaus, Repräsentation der Indexeinträge sowie schnellerer Anfragebearbeitung. • Für die semantisch tiefergreifende Analyse von graphstrukturierten Wissensbasen stellen wir den Espresso-Algorithmus zur Charakterisierung der Beziehungen zwischen zwei Mengen von Entitäten vor. Espresso basiert auf der Identifikation wichtiger Ereignisse, welche anschliessend zu dem Lösungskonzept der dichten Teilgraphen erweitert werden. Diese Strukturen entspre- chen maßgeblichen Themenbereichen, die zur Beschreibung der wechselseitigen Beziehungen dienen. Die Effizienz und der praktische Nutzen der genannten Algorithmen und Ansätze werden in umfangreichen Experimenten evaluiert.