ScaDS Logo

CENTER FOR
SCALABLE DATA ANALYTICS
AND ARTIFICIAL INTELLIGENCE

Graph Mining für fortgeschrittene Datenanalysen

Beitragsseiten

Um komplexe analytische Fragestellungen zu beantworten, werden Data Mining-Verfahren oft mit anderen Schritten der Datenverarbeitung kombiniert, zum Beispiel zur Vorbereitung des Suchraums oder zur Nachbearbeitung der Ergebnisse. Um die Kombination von Data Mining-Algorithmen mit anderen Operatoren zu ermöglichen, bieten produktive Lösungen zur Analyse relationaler oder multidimensionaler Daten meist umfangreiche Toolkits an. Anders ist das in Bezug auf die weniger etablierten Verfahren des Graph Mining. Hier existieren zwar Forschungsprototypen, aber keine Lösung, die komplexe analytische Programme aus mehren Graphoperationen unterstützt. Das an der Universität Leipzig und dem ScaDS Dresden/Leipzig entwickelte Open Source System Gradoop hat sich zum Ziel gesetzt, dies zu ändern. Gradoop ist das erste System, welches es ermöglicht, in einfachen Skripten ein oder mehrere Graph-Algorithmen mit weiteren vor- und nachgelagerten Graph-Operatoren zu kombinieren. Hierdurch werden neuartige Anwendungsfälle möglich, zum Beispiel die nachfolgend gezeigte Analyse von Geschäftsdaten. Durch den Einsatz aktueller Big Data-Technologie bietet Gradoop nicht nur einen einzigartigen Funktionsumfang, sondern ist auch out-of-the-box horizontal skalierbar. Zudem bietet es eine Schnittstelle für Plug in-Algorithmen und ist damit offen für anwendungsspezifische Erweiterungen.

Graphen für die Analyse von Geschäftsdaten

Das erste Graph Mining-Verfahren, welches in Gradoop verfügbar ist, dient dem Auffinden häufiger Muster (Frequent Subgraph Mining). Wie auch beim relationalen Pendant (Frequent Itemset Mining) werden häufig zusammen auftretende Entitäten ausgewertet. Im Beispiel der klassischen Warenkorbanalyse stellt ein Muster eine bestimmte Kombination von Produkten, wie etwa Brot, Butter und Milch, dar. In konkreten Anwendungsfällen sind analytische Fragestellungen jedoch selten so einfach wie im Lehrbuch. So können etwa bei der Optimierung von Webshops nicht generell häufig zusammen gekaufte Produkte von Interesse sein, sondern beispielsweise häufig zusammen auftretende Produktgruppen in abgebrochenen Bestellvorgängen. Um solche komplexeren Fragen zu beantworten sind mehrere Schritte der Datenverarbeitung notwendig. Bevor der eigentliche Algorithmus ausgeführt wird, müssen hier abgebrochene Bestellungen gefiltert und Produkte durch Repräsentanten Ihrer Gruppen ersetzt werden. Für relationale und multidimensionale Daten existieren bereits produktive Lösungen, die solche mehrstufigen Analysen in flexibler Art und Weise unterstützen. Anders ist das in Bezug auf Graphdaten. Doch welchen Vorteil bietet das Graphmodell?

Neben dem gemeinsamen Auftreten bestimmter Entitäten (Knoten) beinhalten Graphmuster zusätzlich auch deren Beziehungen (Kanten). Zur Analyse von Geschäftsdaten lassen sich beispielsweise alle Daten, die während der Ausführung von Geschäftsprozessen aufgezeichnet werden, als Menge von Graphen abbilden. Dabei stellt jeder Graph eine einzelne Prozessausführung dar. Ein Graph enthält dabei alle Daten rund um einen Online-Kaufvorgang beginnend von der kundenseitigen Bestellung, über Einkaufs- und Lagervorgänge bis hin zur Auslieferung. Knoten können hier sowohl Stammdaten, wie etwa Mitarbeiter und Produkte, als auch transaktionale Daten, wie Rechnungen oder Lieferscheine, sein. Die Kanten stellen dann zusätzlich Informationen über Beziehungen bereit, etwa welcher Mitarbeiter ein bestimmtes Paket gepackt hat. Durch diese Abbildung als Graphmenge lassen sich Muster erkennen, die sowohl das gemeinsame Auftreten bestimmter Stammdaten als auch deren Rollen im Prozess repräsentieren, d.h. wer oder was in welcher Form im Prozess involviert war.

Abbildung 1 : Graphmuster in Prozessdaten.

Derartige Musteranalysen werden vor allem im ökonomischen Kontext interessant, zum Beispiel der Zusammenhang von Mustern und Reklamationen. Doch welche Schritte müssen erfolgen um solche Muster zu finden? Zunächst müssen Graphen, die Reklamationen enthalten, identifiziert und gefiltert werden. Nehmen wir zudem an, dass Knoten Geschäftsobjekte mit Typen (z.B. Mitarbeiter, Rechnung oder Produkt) und Eigenschaften (z.B. Identifikatoren oder Preise) beschreiben. Dann sind vor allem jene Muster interessant, die eine Aussage darüber liefern, welche konkreten Stamm- und transaktionalen Daten in welchen Prozessschritten in welcher Art und Weise involviert waren. Dazu müssen die verbleibenden Graphen so transformiert werden, dass Identifikatoren von Stammdaten gemeinsam mit Typen von transaktionalen Knoten und Kanten ausgewertet werden können. Abbildung 1 zeigt zwei Beispiele für Graphmuster in Prozessdaten. Man sieht dabei, dass sowohl einfache Muster (i) aber auch komplexere Beziehungsgeflechte (ii) gefunden werden können. Mit Gradoop lassen sich Graphdaten in einem einzigen Programm entsprechend unseres Beispiels kategorisieren und filtern um anschließend häufige Muster zu identifizieren.


Gradoop – Funktionsumfang, Technologie und Erweiterung

Gradoop ist ein System für die fortgeschrittene Analyse von Graphdaten. Mit einer deklarativen Java API können flexibel analytische Skripte erstellt werden. In diesen lassen sich mehrere Graph-Operatoren und -Algorithmen kombinieren. Gradoop ist als Bibliothek der Big Data-Plattform Apache Flink implementiert. Die fundamentalen Konzepte von Plattformen wie Apache Flink oder auch Apache Spark sind verteilte Mengen von Datenobjekten (DataSets) und Transformationen zwischen DataSets (z.B. map und reduce). Ein Analyseprogramm in einem solchen System kann als gerichteter azyklischer Graph (DAG) dargestellt werden, wobei Knoten DataSets und Kanten Transformationen beschreiben. Im Vergleich zu Hadoop MapReduce bieten diese Plattformen eine Vielzahl weiterer Operatoren (z.B. join, groupBy, sort). Zusätzlich können Daten während der kompletten Programmausführung im verteilten Hauptspeicher vorgehalten werden. Gradoop-intern werden Graphdaten sowie deren Operatoren und Algorithmen auf Flink-DataSets und Flink-Transformationen abgebildet. Für die Deklaration analytischer Skripte wurde die DAG-Abstraktion auf die Graphanalyse übertragen, wobei DAG-Knoten Graphdaten und DAG-Kanten Graph-Operatoren bzw. Graph-Algorithmen darstellen. 

Zwar existieren für Big Data-Plattformen auch andere Bibliotheken zur Graphanalyse, jedoch arbeiten diese mit weitaus weniger ausdrucksstarken Graphmodellen.  Als ein Alleinstellungsmerkmal unterstützt das Datenmodell von Gradoop nicht nur einzelne Graphen sondern auch Graphmengen. Es basiert auf dem populären Property Graph Modell, wobei Nutzdaten (Bezeichner und Eigenschaften) nicht nur an Knoten und Kanten, sondern auch an Graphen gespeichert werden können. Das Datenmodell beinhaltet weiterhin verschiedene universell verwendbare Operatoren deren Ein- und Ausgabe entweder Graphen oder Graphmengen sind. Hierdurch können analytische Programme einfach deklariert werden und erfordern, im Gegensatz zu anderen Bibliotheken, keinen Entwicklungsaufwand für Datenmodellierung und Operatorimplementierung. Weiterhin bietet Gradoop zum Datenmodell passende Datenquellen und -senken an, die in Skripten verwendet werden können und zusätzlich Entwicklungsaufwand einsparen. Zudem existiert keine weitere Bibliothek, die von Haus aus Graphmengen unterstützt. Letzteres ist jedoch zwingend notwendig um graphübergreifende Analysen, wie etwa die Suche nach häufigen Mustern, zu ermöglichen.

Sollte ein Anwendungsfall neben den in Gradoop enthaltenen Operatoren zusätzliche Algorithmen erfordern, so bietet Gradoop mit dem generischen Call-Operator eine entsprechende Schnittstelle an. Ein kompatibler Algorithmus muss mit Apache Flink umgesetzt werden und ein passendes Java-Interface implementieren. Um verschiedenste Algorithmen zu unterstützen, bietet Gradoop mehrere solcher Interfaces, die alle Ein- und Ausgabekombinationen abdecken. Ein entsprechend implementierter Algorithmus kann somit nahtlos in Gradoop-Skripte integriert werden.


Entwicklungsstand

Die aktuelle Version 0.2 von Gradoop ist ein Forschungsprototyp, der bereits zeigt, wie sich verschiedene Operatoren und Algorithmen zur Beantwortung komplexer analytischer Fragen kombinieren und horizontal skalierbar ausführen lassen. Derzeitiger Forschungsschwerpunkt ist die effiziente Abbildung komplexer Graphalgorithmen auf das Programmiermodell von Big Data-Plattformen, insbesondere das von Apache Flink. Dabei sind vor allem solche Algorithmen interessant, die das NP-vollständige Teilgraph Isomorphie-Problem beinhalten, zum Beispiel Anfragen durch Mustergraphen (Pattern Matching) und das bereits erwähnte Frequent Subgraph Mining. Hier beinhaltet die aktuelle Version funktionsfähige Implementierungen, welche fortlaufend mit den Ergebnissen der Forschungsaktivität optimiert werden. Zudem ist geplant, den Funktionsumfang um spezielle Operatoren zur graph-basierten Datenintegration zu erweitern.

Weiterführende Links

Aktuelle Präsentation von der Data2Day 2016

Ausführlicher Artikel aus der JavaSPEKTRUM 05/2016

Liste der wissenschaftlichen Publikationen

Gradoop auf GitHub