Graphdatenbanken und ihre Einsatzmöglichkeiten

Klug vernetzt ist gut genutzt – das Logistik-Startup „Shutl“ aus London bemerkte irgendwann zu Beginn der 2010er-Jahre, dass das relationale Datenbanksystem, mit dem die Routen seiner Fahrzeuge berechnet wurden, für bestimmte Berechnungen zu langsam wurde.
Das Logistik-Startup „Shutl“ aus London bemerkte irgendwann zu Beginn der 2010er-Jahre, dass das relationale Datenbanksystem, mit dem die Routen seiner Fahrzeuge berechnet wurden, für bestimmte Berechnungen zu langsam wurde. Die längste Berechnung dauerte genauso lang wie die kürzeste Fahrt, etwa 15 Minuten. Für ein Unternehmen, das sich die Auslieferung innerhalb 90 Minuten auf die Fahnen geschrieben hatte, war das kein haltbarer Zustand.
Mit der Umstellung auf eine Graphdatenbank konnte die Laufzeit des Algorithmus auf durchschnittlich eine 1/50 Sekunde reduziert werden, also auf 20 Millisekunden. Das ist gegenüber der längsten Abfrage 45000-mal schneller.

Im Juli 2010 gab Google bekannt, dass das Unternehmen die Firma Metaweb übernehmen würde. Metaweb betrieb eine Wissensdatenbank namens Freebase, in der Millionen von Einträgen gespeichert waren, die unter anderem aus Wikipedia und der Musikdatenbank MusicBrainz stammten und von einer User-Community fortwährend ergänzt und weiter vernetzt wurden.

Unter dem Motto „things, not strings“ kündigte Google dann am 16. Mai 2012 den „Knowledge Graph“ an, der teilweise auf den Inhalten von Freebase beruhte. Überdies wurden die Daten aus Freebase an WikiData weitergegeben.

Googles Knowledge Graph kommt insbesondere in den sogenannten „Knowledge Panels“ zum Einsatz; das sind die „Kästen“, die auf den Ergebnisseiten manchmal auftauchen und Suchergebnisse zu Personen, Firmen oder Institutionen („named entities“) mit strukturierter Information ergänzen. Die Panels enthalten häufig eine kurze Beschreibung, tabellarische, verlinkte Basisinformationen sowie – unter der Überschrift „Andere suchten auch nach“ – Links zu Kontextinformationen auf Googles Suchseiten, etwa ähnlichen Firmen, Institutionen oder im Suchkontext relevanten anderen Personen.

In diesen beiden sehr unterschiedlichen Anwendungsbeispielen ist viel von Graphen und Graphdatenbanken die Rede, was zu der Frage führt:

Was ist überhaupt ein Graph?

In der Mathematik spricht man von einem Graphen, wenn Objekte und die zwischen ihnen bestehenden Verbindungen durch eine Menge von sogenannten Knoten (Objekte) und Kanten (Verbindungen) repräsentiert werden. Die Kanten können eine Richtung haben, müssen das aber nicht. Ein paar Beispiele für Graphen sind etwa die schematische Darstellung von Molekülen, Taxonomien in der Biologie, Netzpläne im öffentlichen Nahverkehr oder die Darstellung der syntaktischen Struktur eines Satzes. Aus den Beispielen wird schon ersichtlich, dass die Knoten eines Graphen durchaus auch abstrakte Konzepte repräsentieren können, etwa die Nominalphrase eines Satzes. Und es wird auch deutlich, dass die Verbindungen, die Kanten für die Gesamtbedeutung des Graphen extrem wichtig ist.

Graphdatenbanken einfach erklärt – es geht immer um die Beziehungen

Eine Graphdatenbank ist in der Lage, große Graphen mit Millionen von Knoten und Kanten abzuspeichern und effizient abzufragen. Dadurch werden Projekte wie die eingangs genannten erst möglich. Google ist nicht der einzige große Player, der einen Knowledge Graph betreibt – das tut auch Apple (für das Weltwissen, aus dem Siri sich bedient), und Amazon kündigte zu Beginn des vergangenen Jahres einen eigenen Knowledge Graphen namens „Alexa Entities“ an.

Viele Berechnungen und Abfragen, die mit Graphdatenbanken ausgeführt werden können, lassen sich als Variante einer einzigen Operation beschreiben: der Navigation innerhalb der Beziehungsstruktur des Graphen. Ob man das „Mustererkennung“ (pattern matching) nennt oder „Traversieren“, letztlich läuft es immer darauf hinaus, Knoten und die Pfade zwischen ihnen nach bestimmten Kriterien aufzufinden.

Der kleine Beispielgraph hier mag das verdeutlichen:

Der Anschaulichkeit wegen sind in diesem Graphen Menschen und Haustiere beschrieben. Die Knoten, die gerichteten Kanten und nicht zuletzt die Eigenschaften der beiden sind in diesem Beispiel die Wissensbasis, mit der wir arbeiten. Jeweils zwei Knoten und die entsprechende Kante können auch als „Triple“ bezeichnet werden; das ist die aus natürlichen Sprachen bekannte Struktur Subjekt, Prädikat, Objekt (SPO). Der abgebildete Graph enhält 12 Triples, da die Pfeile mit zwei Spitzen zwei gerichtete Kanten und damit auch zwei Prädikate darstellen („Max kennt Ariela“ und „Ariela kennt Max“).

Die Frage „Wen kennt Max?“ kann man beantworten, indem man vom Knoten „Max“ der Beziehung „kennt“ folgt und die Knoten in der Objektposition der beiden Triples listet: Frank und Ariela. Rot eingefärbt sind die relevanten Kanten und die Ergebnisknoten.

Graphdatenbanken Beziehungen visualisiert

Auf die gleiche Weise können eine ganze Reihe von Fragen beantwortet werden: Wer kennt jemanden, der einen Hund hat? (Frank, Max.) Wer sind die Spielgefährten von Wuff? (Ariela, Tatze.) Gibt es jemanden, der drei andere kennt? (Nein.) Wessen Hund spielt mit einer Katze? (Ariela.) Dass jeder Mensch zumindest oberflächlich auch sich selbst kennt, ist in dem Graphen übrigens nicht ausgedrückt; daher gehört Ariela auch nicht zur Gruppe derjenigen, die jemanden kennen, die oder der einen Hund hat.

Gern werden Graphen benutzt, um topografische Netzwerke wie Straßen, U-Bahn-Netze, Versorgungsleitungen, die physischen Leitungen des Internets und Ähnliches abzubilden. Im ersten Beispiel oben war das der Fall. Dabei werden die Kanten gern gewichtet, um Durchflussgrößen oder andere Eigenschaften der jeweiligen Verbindungen zu modellieren. Navigationssysteme sind hier ein weiteres gutes Beispiel. Wie man an den vielfältigen Hinweisen zu den berechneten Routen ablesen kann, sind die Streckenabschnitte zwischen Start und Ziel mit einer Vielzahl von Eigenschaften versehen, die es nachher erlauben, die Gesamtroute zu qualifizieren: Sind Mautstraßen dabei? Wie schnell ist man im Durchschnitt auf dieser Strecke unterwegs? Mehr oder weniger Abbiegungen? Der „shortest path“-Algorithmus, einer der bekanntesten Graph-Algorithmen, wird daher nicht nur mit den reinen Streckenlängen, sondern auch mit den entsprechenden Zusatzinformationen bzw. Gewichten versorgt, so dass am Ende für mich als User mehrere „beste Wege“ errechnet werden, je nach den eigenen Präferenzen.

Schemafreiheit mittels Graphdatenbank

In einem relationalen Datenbanksystem wie Oracle oder MySQL muss ein bestimmtes Schema berücksichtigt werden, das festlegt, welche Daten in einer bestimmten Spalte abgelegt werden dürfen. Diese Einschränkung gilt bei einer Graphdatenbank in der Regel nicht, und das ist eine Eigenschaft, die sie mit der anderen großen Gruppe von NoSQL-Datenbanken, den Dokumentendatenbanken teilen. Sowohl bei Graph- als auch bei Dokumentendatenbanken ist in der Regel die Businesslogik einer Applikation dafür zuständig festzulegen, welche Datentypen und welche Datenstrukturen in der Datenbank Verwendung finden dürfen – oder dies eben offenzulassen.

Schemafreiheit bietet zunächst einmal eine gute Unterstützung agiler Entwicklungsmethoden. Besonders wichtig wird dieser Aspekt aber dann, wenn Daten aus verschiedenen Quellen an Bord genommen und deren Beziehungen modelliert werden.

Die führende Idee dabei ist, dass Daten, die auf diese Weise kombiniert werden, füreinander einen Kontext darstellen, der die Bedeutung der jeweiligen Datensätze klärt und erweitert und so den Wert der Information im Unternehmenskontext steigert: Das Ganze ist mehr als die Summe der Teile – das gilt besonders für Wissensgraphen, ganz gleich ob sie Weltwissen organisieren oder Daten innerhalb des Unternehmens verknüpfen.

Graphdatenbanken und die Visualisierung

Neben der Schemafreiheit und der „Betonung“ der Relationen gibt es eine dritte Eigenschaft von Graphen, die sie für die Wissensorganisation innerhalb und außerhalb des Unternehmens wertvoll macht. Graphen eignen sich hervorragend für die Visualisierung von Zusammenhängen. Wenn ich den Kundengraphen unserer Firma visualisiere, sehe ich sofort, welche Kunden ihrerseits große „Hubs“ sind (Wiederverkäufer, Fahrzeugbauer), wo kleine „Inseln“ sind und wer gegebenenfalls mit Kunden oder Lieferanten aus verschiedenen Branchen zu tun hat. Uns (allsafe) helfen diese Informationen, unseren Markt besser zu verstehen. Selbstverständlich können auch berechnete oder abgeleitete Informationen wiederum als Graph dargestellt werden, etwa die mit automatischen Verfahren berechneten Ähnlichkeiten zwischen Texten in einem Korpus. Wer Inspiration und Information zum Thema Graph-Visualisierung sucht, kann sich auf der Webseite des US-Physikers und Netzwerkforschers Albert Laszlo Barabasi umtun oder die Beispiele zur Visualisierungsbibliothek d3.js studieren.

Graphdatenbanken und auf ihnen aufbauende Informationssysteme wie Databrain Sherlock kommen in der Regel mit Visualisierungswerkzeugen an Bord, mit denen die Ergebnisse von ad-hoc-Queries dargestellt werden können, um eine spezifische Frage zu beantworten oder sich schrittweise mit einem Graphen vertraut zu machen. Zwar hat sich die Graph-Visualisierung mit simulierten Anziehungs- und Abstoßungskräften schon als Quasi-Standard etabliert, aber es gibt eine ganze Reihe von weiteren sehr aussagekräftigen Darstellungstypen, die sich je nach Anwendungsfall für die Visualisierung anbieten, darunter die Chord-Diagramme das sogenannte „Hierarchical Edge Bundling“.

Databrain Sherlock wartet auf Sie!

Der analytische Wert einer Graphdatenbank

Am 3. April 2016 gelangten die sogenannten Panama Papers an die Öffentlichkeit. 2,6 Terabyte (11,5 Millionen Dokumente) an vertraulichen Unterlagen eines panamaischen Offshore-Dienstleisters wurden mit Hilfe von Graphdatenbanken erschlossen und auf diese Weise Eigentumsverhältnisse, Geldflüsse, Strategien der Steuervermeidung von über 214.000 Briefkastenfirmen und tausenden beteiligten Personen sichtbar gemacht. Der analytische Wert eines Graphen liegt bei diesem Anwendungsfall auf der Hand. Die Frage „Wer steckt dahinter?“ lässt sich bei einem derartigen Korpus von Dokumenten nur mit Hilfe von Abfragen über mehrere Knoten hinweg beantworten, und dafür ist ein Graph-Modell hinsichtlich Flexibilität und Effizienz nicht zu überbieten.

Bei allsafe arbeiten wir gerade an einer eigenen Software zur strategischen Marktbearbeitung, die Verkaufsdaten und Kundenstammdaten aus dem ERP mit weiteren Datenquellen verknüpft, darunter externen Datenquellen, Resultaten von Machine-Learning-Algorithmen oder Daten aus anderen internen Systemen. Es ist überraschend, wie aussagekräftig unsere Stammdaten plötzlich werden, wenn sie auf diese Weise angereichert und dadurch neue Abfragen möglich werden.

Im Falle unseres Projekts werden im Lauf der Zeit weitere Daten hinzukommen, etwa Nutzungsdaten unserer Produkte im Feld. Neue Daten und Relationen, auch solche mit neuer Semantik, können der Datenbasis im laufenden Betrieb hinzugefügt werden, und jede neue „Schicht“ erhöht den analytischen Wert der bereits eingepflegten Informationen. Was hier entsteht, ist ein „Enterprise Knowledge Graph“, wobei das Akronym „EKG“ natürlich nur zufällig an medizinische Diagnostik erinnert.

Ein solcher Enterprise Knowledge Graph ist in aller Regel anwendungsorientiert, auch wenn die Mehrfachnutzung des Graphen, gesteuert über anwendungsspezifische Abfragen, im Graph-Modell schon angelegt und organisatorisch ausdrücklich erwünscht ist. Im Unterschied dazu dienen formale Ontologien und offene semantische Datensammlungen wie DBPedia oder Wikidata keinem vorher festgelegten (unternehmerischen oder organisatorischen) Zweck; sie sind als „open source“-Variante eines Knowledge Graph zu verstehen, deren Nutzungsmuster zur Entstehungszeit noch nicht festgelegt sind und die das „Weltwissen“ organisieren statt mit unternehmensspezifischen Informationen zu hantieren.

Der analytische Wert von Graphen und Graphdatenbanken erschöpft sich allerdings keineswegs in aussagekräftigen Abfragen auf geschickt kuratierten Wissensgraphen. Eine Gartner –Studie sagt Folgendes voraus:

„Graph-Technologien werden im Jahr 2025 bei 80 % aller Innovationen im Bereich Daten und Analytik verwendet werden – gegenüber 10 % im Jahr 2021 – und rasche Entscheidungsfindung im ganzen Unternehmen ermöglichen.“

Was die Zukunft bringt

Die Rede ist hier von Innovationen. Es ist davon auszugehen, dass hybride Methoden zur Anwendung kommen, die Graph-Technologien und andere ML- oder KI-Technologien kombinieren. Es wird sich lohnen, einen Blick auf bereits bestehende Ansätze zu richten, die sich an dieser „Kombinatorik“ versuchen.

Wie weiter oben schon beschrieben, kann ein Graph auch als Sammlung von „Triples“ oder Aussagen der Form Subjekt-Prädikat-Objekt aufgefasst werden. Insofern sind KI-Projekte im Kontext von Graphen zunächst einmal der symbolischen KI zuzuordnen. Mit dem Beispielgraph oben lassen sich Aussagen auf ihren Wahrheitswert überprüfen wie „Es gibt niemanden, der eine Katze besitzt“. Komplexere Graphen in Kombination mit Regeln können zu weiteren und vor allem nicht sofort ablesbaren Schlussfolgerungen führen.

Eine übliche Verwendung von Graphen in dieser Form betrifft den Output von Bild- oder Texterkennungsalgorithmen. Der Satz „Udo Samel erlernte seinen Beruf an der Schauspielschule in Frankfurt am Main ab 1974, nachdem er an der Goethe-Universität in Frankfurt ein Jahr lang Slawistik und Philosophie studiert hatte“ kann nach einer semantischen Analyse in einen Graph überführt werden, der die Person „Udo Samel“ mit den Institutionen „Schauspielschule“ und „Goethe-Universität“ verknüpft, diese wiederum mit der Stadt „Frankfurt am Main“ und mit den Fächern „Slawistik“ und „Philsophie“. Aufgrund von Regeln kann weiterhin darauf geschlossen werden, dass Udo Samel den Beruf des Schauspielers erlernt hat – von dem „Beruf“ ist ja in dem Satz die Rede, und das ist auch genau der Beruf, den man an einer Schauspielschule lernt.

Analog können auch die Ergebnisse von Bilderkennungsalgorithmen in Form eines Graphen zur Weiterverwendung gespeichert und umgekehrt bereits vorhandene Triples z. B. zur Plausibilitätsprüfung der Bilderkennung verwendet werden.

Graph Embeddings

In der automatischen Sprachverarbeitung haben sich die sogenannten „word embeddings“ als hilfreiches Verfahren für viele Problemstellungen bewährt. Word embeddings platzieren Wörter in einem mehrdimensionalen Vektorraum, und zwar üblicherweise so, dass Wörter mit ähnlicher Bedeutung in diesem Vektorraum näher beieinanderliegen.
Auf ähnliche Weise lassen sich sogenannte „graph embeddings“ erzeugen. Wie oben schon ausgeführt, lassen sich Graphen als Sammlungen von Triples interpretieren, die zur Wissensrepräsentation und zur Wissensverarbeitung („reasoning“), d. h. zur regelbasierten Ableitung von neuen Triples genutzt werden können. Graph embeddings lösen nun das Problem, wie man in der Domäne von Graphen von der symbolischen KI (Logik) zu numerischen Verfahren übergehen kann. Knoten werden (ähnlich wie die Wörter in word embeddings) zu mehrdimensionalen Vektoren, und zwar so, dass auch ihre Kanten sowie die Eigenschaften ihrer Nachbarknoten in dem Vektor kodiert werden. Dem Ursprungsgraphen wird auf diese Weise ein Vektorraum zugeordnet, in dem die Knoten inklusive ihrer Umgebungseigenschaften angeordnet sind. So lässt sich dann in einem weiteren Schritt ein Ähnlichkeitsmaß angeben, das die Knoten numerisch miteinander vergleichbar macht – mit den auf symbolischer Logik beruhenden Abfragesprachen lässt sich dergleichen nicht erreichen.

Graph Neural Network (GNN)

Ein GNN ist allgemein gesprochen ein künstliches neuronales Netz, das Daten verarbeitet, die in Form eines Graphen repräsentiert werden können. Wie auch in anderen Themenfeldern des „Deep Learning“ oder genauer „Geometric Deep Learning“ sind hier in den letzten Jahren entscheidende Fortschritte zu verzeichnen.

Das „Konstruktionsprinzip“ eines GNN ist das paarweise Austauschen von Nachrichten zwischen den Knoten, weshalb GNNs als eine Art von Message Passing Neural Networks (MPNN) gelten. Mithilfe des Informationsaustauschs mit den Nachbarknoten modifizieren die Knoten schrittweise ihre eigenen Repräsentationen.

GNNs werden in der kombinatorischen Optimierung (z.B. Ermittlung kürzester Pfade) und für die Auswertung sozialer Netzwerke, etwa für Recommendersysteme, verwendet. Der spektakulärste Anwendungsfall in den vergangenen Jahren dürfte jedoch AlphaFold sein, das Programm, mit dem es dem Unternehmen Deepmind in Zusammenarbeit mit dem EMBL-EBI gelang, die Faltung eines Proteins in überschaubarer Zeit aus seiner Aminosäuresequenz vorherzusagen. Das Programm hat großes Aufsehen erregt und in zwei Versionsstufen, 2018 und 2020, jeweils den Wettbewerb CASP gewonnen, der Techniken zu Vorhersage von Proteinstrukturen bewertet. Wichtig ist das u. a. deshalb, weil von den rund 200 Millionen in der Natur vorkommenden Proteinen erst von etwa 170000 die konkrete Struktur bekannt ist, also von weniger als 1%. Mit diesen bekannten Proteinen wird AlphaFold trainiert und sagt dann mit bemerkenswerter Genauigkeit die konkrete Faltung, also die Anordnung der Aminosäuren im Raum, von noch nicht untersuchten Proteinen voraus.

Grundsätzlich ist aber für noch ganz andere Daten, die sich für die Repräsentation als Graph anbieten, ein „analytischer Quantensprung“ durch die Verwendung von Graph Embeddings und GNNs zu erwarten – oder durch Methoden, die heute noch gar nicht bekannt sind. Wie gesagt, bei 80 % aller Innovationen in der Datenverarbeitung erwartet Gartner bereits in 3 Jahren die Beteiligung von Graph-Technologien der einen oder anderen Form, und ein nicht zu kleiner Teil davon dürfte mit einer Kombination aus symbolischen und numerischen Verfahren zu tun haben.

Wann eignen sich also Graphdatenbanken?

Wann also ist eine Graphdatenbank oder eine darauf beruhende Software wie das Informationssystem Sherlock für ein bestehendes Geschäftsproblem gut geeignet? Als Faustregel können, Stand heute, die folgenden Punkte dienen:

Die Daten weisen viele Beziehungen auf, sind also hochgradig vernetzt.

Ein flexibles Datenschema ist erwünscht oder sogar nötig.

Anreicherung durch neu hinzukommende Informationen ist intendiert.

Die auszuführenden Abfragen sollen Informationen aus unterschiedlichen Quellen integrieren können.

Die Abfragen sollen schnell sein und komplexe Muster in den Daten und ihren Beziehungen sichtbar machen.

Die Nutzung von Graph Embeddings oder Graph Neural Networks erscheint aussichtsreich.

Informieren Sie sich jetzt zu Databrain Sherlock!

Christoph Pingel ist Leiter der Softwareentwicklung bei allsafe GmbH & Co. KG. Allsafe ist ein international agierendes Unternehmen in der Ladegutsicherung. Mit 250 Mitarbeitern und Produkten in 10.000 Varianten sorgt allsafe für einen sicheren Transport, egal ob auf der Straße, in der Luft oder beim Schiffsverkehr. Als langjährige Kunden von Fischer nutzt allsafe erfolgreich Databrain Sherlock, um auf alle Daten über alle Quellsysteme hinweg über eine einheitliche Schnittstelle zuzugreifen und damit die digitalen Geschäftsmodelle ohne großen Entwicklungsaufwand umsetzen zu können. Mehr zur Erfolgsgeschichte allsafe & Sherlock finden Sie hier.