Was ist ein GNN (Graph Neural Networks)?

Graph Neural Networks(GNNs) sind eine tiefe neuronale Netzwerkarchitektur, die sowohl in praktischen Anwendungen als auch in der hochmodernen Forschung zum maschinellen Lernen beliebt ist. Sie verwenden ein neuronales Netzmodell, um Daten über Entitäten und deren Beziehungen darzustellen. Sie sind nützlich für das Data Mining in der Praxis, das Verständnis sozialer Netzwerke, Wissensdiagramme, Empfehlungssysteme und Bioinformatik.

Die Entwicklung von GNNs wurde von Deep-Learning-Algorithmen wie Convolutional Neural Networks (CNNs) und Recurrent Neural Networks (RNNs) inspiriert, aber sie weisen mehrere wesentliche Unterschiede auf. CNN sind für Daten konzipiert, die eine gitterähnliche Struktur wie die Pixel eines Bildes haben. Jedes Pixel kann mit höchstens acht anderen Pixeln verbunden sein. Im Gegensatz dazu sind RNN auf Sequenzstrukturen zugeschnitten, bei denen jedes Element höchstens mit zwei anderen Elementen verbunden werden kann, wie eine Wortfolge in einem Text. In graphstrukturierten Daten kann jedoch jedes Element eine oder mehrere Verbindungen haben und es kann sein, dass die Anzahl der Verbindungen für ein bestimmtes Element nicht konsistent ist.

Graph Neural Networks sind eine Implementierung des geometrischen Deep Learning¹, das in vier grundlegende Kategorien eingeteilt wird:

Graphbasiertes Lernen, das aus graphenähnlichen Daten lernt.

Rasterbasiertes Lernen, das datenähnliche Bilder und andere Datentypen kennenlernt, die durch Raster beschrieben werden können.

Gruppenbasiertes Lernen, bei dem gelernt wird, wie Informationen mit einer übergeordneten Gruppe in Beziehung stehen. Dies ist besonders effektiv, wenn Daten von einer Gruppe wie einer Kugel erfasst werden, z. B. geologische Daten aus verschiedenen Quellen auf der ganzen Welt.

Mesh-basiertes Lernen, bei dem gelernt wird, wie Informationen über ein unregelmäßiges Netz verteilt sind, beispielsweise durch die Analyse und Vorhersage von Elementen eines 3D-Modells eines Objekts.

GNNs sind ein Bereich der aktiven Forschung im Bereich künstlicher Intelligenz, werden aber von Bibliotheken und Toolkits, die in Python und Frameworks wie TensorFlow und PyTorch erstellt wurden, gut unterstützt.

Eine Reihe von Objekten und die Verbindungen zwischen ihnen können als Graph dargestellt werden. Informatforscher entwickelten neuronale Netze für die Verarbeitung von Graphdatenstrukturen.

Ein Graph stellt die Beziehungen, die als „Kanten“ bezeichnet werden, zwischen einer Menge von Entitäten, die als „Knoten“ bezeichnet werden, dar. Mathematisch ist ein Graph G definiert als ein Tupel aus einer Menge von Knoten und Eckpunkten V und einer Menge von Kanten und Verknüpfungen. E:G = (V, E). Jede Kante ist ein Paar aus zwei Eckpunkten und stellt eine Verbindung zwischen ihnen dar.

Um jeden Knoten, jede Kante oder den gesamten Graphen weiter zu beschreiben, können wir Informationen in jedem dieser Teile des Graphen speichern.

Diagramme können weiter beschrieben werden, indem jeder Kante eine Richtungsabhängigkeit zugewiesen wird. Ein Graph wird entweder als gerichtet oder ungerichtet beschrieben. Ein ungerichteter Graph stellt eine Beziehung dar, die bidirektional ist. Wenn Rosa ein Geschwisterkind Juan hat, dann hat Juan auch ein Geschwisterkind, Rosa. Die Beziehung zwischen Rosa und ihrem Geschwisterkind hat keine Richtung, sie verbindet sie nur beide. Ein gerichteter Graph stellt Beziehungen dar, die direktional sind. Wenn Rosa ein älteres Geschwisterkind Juan hat, dann geht die Beziehung „älteres Geschwisterkind“ nur in eine Richtung: Von Juan zu Rosa hat Juan kein „älteres Geschwisterkind“.

Eine Möglichkeit, die Konnektivität eines Graphen zu visualisieren, besteht in der Verwendung seiner Adjazenzmatrix. Dies ist eine matrixbasierte Darstellung der Eckpunkte eines Graphen, die sowohl ungerichtete als auch gerichtete Graphen darstellen kann.

Die Adjazenzmatrix eines gerichteten Graphs gibt alle Eckpunkte und die Richtung der Kante an, die sie erzeugt. Beispielsweise ist Knoten 0 im gerichteten Graphen mit Knoten 1 verbunden, aber das Gegenteil ist aufgrund der Richtung der Verbindung nicht der Fall. In der Adjazenzmatrix enthält [Zeile 0, Spalte 1] einen Wert, während [Zeile 1, Spalte 0] dies nicht tut.

Repräsentationen von Graphen sollten eine Permutationsinvarianz aufweisen. Das bedeutet, dass Repräsentationen des Graphen zu denselben Ergebnissen führen sollten, wenn die Graphstruktur dieselbe, aber die Knotenreihenfolge unterschiedlich ist. Dieser Ansatz stellt sicher, dass die Darstellung des Graphen dieselben Eigenschaften wie der Graph selbst aufweist.

GNNs verwenden in der Regel eine „Graph-in, Graph-out“-Architektur. Das bedeutet, dass diese Modelltypen ein Graph als Eingabe akzeptieren, mit Informationen, die in seine Knoten, Kanten und globalen Kontext geladen sind. Die Modelle transformieren diese Einbettungen schrittweise, ohne die Konnektivität des Eingabegraphen zu ändern. Einbettungen stellen die Knoten als Knoteneinbettungen und die Eckpunkte als Eckpunkteinbettungen dar. Durch diese Einbettungen lernt das Modell, welche Arten von Knoten an welcher Stelle im Diagramm auftreten sowie welche Arten und Positionen von Kanten es gibt.

Typischerweise erfolgt das Training eines neuronalen Netzes durch die Aktualisierung der Netzparameter mit Gradienten, die auf einer zufälligen Teilmenge der Trainingsdaten berechnet werden. Zum Trainieren von Graphnetzwerken erstellen neuronale Graphnetzwerke Untergraphen, die wesentliche Eigenschaften des übergeordneten großen Graphen beibehalten.

GNN verwenden einen Mechanismus zur Weiterleitung von Nachrichten, um Informationen von benachbarten Knoten zu aggregieren und so die komplexen Beziehungen in Graphen zu erfassen. Eine Herausforderung bei der Modellierung graphstrukturierter Daten ist die Erfassung der Interaktionen zwischen den Knoten. Die Weitergabe von neuronalen Nachrichten löst diese Herausforderung, indem sie ein Framework für die Modellierung von Abhängigkeiten und Interaktionen in Graphdaten zur Verfügung stellt. Knoten tauschen Informationen mit ihren benachbarten Knoten aus und aggregieren diese Informationen, um ihre eigenen Darstellungen zu aktualisieren. Dieser Prozess der Nachrichtenübergabe ähnelt dem Austausch von Nachrichten oder Signalen an Knoten in einem Graphen.

GNN ermöglichen mehrere verschiedene Arten der Analyse, von denen jede Erkenntnisse in unterschiedliche Elemente von Grafikdaten bietet.

Aufgaben auf Graphebene

Bei einer Aufgabe auf Graphebene sagt das GNN eine Eigenschaft eines gesamten Graphen voraus. Bei einem als Graph dargestellten Molekül möchte man beispielsweise vorhersagen, ob es an einen mit einer Krankheit assoziierten Rezeptor bindet. Für ein soziales Netzwerk können Sie vorhersagen, ob es wahrscheinlich mit einer bestimmten Institution wie einer Universität oder Hochschule verbunden ist. Diese Art der Mustererkennung kann als eine Form der Graphklassifizierung eingestuft werden, da sie den gesamten Graphen klassifiziert.

Aufgaben auf Knotenebene

Aufgaben auf Knotenebene befassen sich mit der Vorhersage der Identität oder Rolle jedes Knotens innerhalb eines Graphen. Ein Problem der Knotenklassifizierung in einem Datensatz für soziale Netzwerke könnte beispielsweise darin bestehen, vorherzusagen, ob ein Benutzer aufgrund der Verbindung mit seinem Freundesnetzwerk wahrscheinlich ein bestimmtes Interesse hat. Wenn man Freunde hat, die nur das gemeinsame Interesse am Golfsport teilen, aber keine anderen gemeinsamen Interessen, ist das ein guter Hinweis darauf, dass ein neuer Freund wahrscheinlich auch Freude am Golfsport haben wird. Diese Art von Knotenfunktionen kann oft mit einem GNN vorhergesagt werden.

Aufgaben auf Kantenebene

Die letzte Art von Vorhersageproblem in Graphen ist die Kantenvorhersage, manchmal auch Verknüpfungsvorhersage genannt.

Ein Beispiel für eine Inferenz auf Kantenebene ist das Verständnis von Bildszenen. Nach der Identifizierung von Objekten in einem Bild können Deep-Learning-Modelle auch die Beziehung zwischen ihnen vorhersagen. Es handelt sich hierbei um eine Klassifizierung auf Kantenebene, da die Knoten die Objekte im Bild darstellen und die Vorhersage angibt, welche dieser Knoten eine Kante teilen oder welchen Wert diese Kante hat. Wenn Sie Verbindungen zwischen Entitäten entdecken möchten, können Sie den Graphen als „vollständig verbunden“ betrachten und basierend auf ihrem vorhergesagten Wert die Kantenanzahl reduzieren, um einen dünn besetzten Graphen zu erhalten.

Graph Convolutional Networks⁴ (GCNs): Dieser Ansatz ist auf halbüberwachtes Lernen ausgerichtet und basiert auf einer Variante von Convolutional Neural Networks, die aus graphbasierten Daten lernen und Vorhersagen treffen können. Diese Modelle skalieren linear in der Anzahl der Graphkanten und eignen sich daher für große Datensätze. Die Modelle lernen auch die lokale Graphenstruktur und die Funktionen der Knoten.

Graph-Autoencoder²: Diese Varianten sind durchgängig trainierbare neuronale Netzmodelle für unüberwachtes Lernen, Cluster und Linkvorhersage in Graphen. Sie verwenden in der Regel ein GCN als Encoder, um Einbettungen zu erstellen, und verfügen über einen Decoder, der das Diagramm aus der erlernten latenten Darstellung rekonstruiert.

Graph Attention Networks³ (GAT): Eine neurale Netzarchitektur, die mit graphstrukturierten Daten arbeitet. GAT nutzen einen Aufmerksamkeitsmechanismus in Form von Selbstaufmerksamkeitsebenen, um die Mängel bisheriger Methoden, die auf Graphkonvolutionen oder deren Annäherungen basieren, zu beheben. Durch das Stapeln von Ebenen, in denen Knoten auf die Funktion ihrer Nachbarschaften zugreifen können, ermöglicht ein GAT (implizit) die Festlegung unterschiedlicher Gewichtungen für verschiedene Knoten in einer Nachbarschaft. Dies ist möglich, ohne dass kostspielige Matrixoperationen wie Inversion erforderlich sind oder die Graphenstruktur von vornherein bekannt ist.

Graphdarstellung: Lernen ist ein Forschungsbereich, der Graph Neural Networks erweitert, um eine sinnvolle, potenziell niedrigdimensionale Darstellung von Knoten aus den komplexen Beziehungen in einem Graph zu finden. Ein Beispiel für diese Erweiterung ist GraphSage⁶, ein Projekt der Stanford University, das niedrigdimensionale Vektordarstellungen für Knoten erstellt und damit für die Arbeit mit Daten geeignet ist, bei denen Knoten hochdimensionale Daten darstellen.

Als Beispiel dafür, wie ein GNN strukturiert sein kann, betrachten wir ein einfaches Graph Convolutional Network (GCN) zur Klassifizierung eines gesamten Graphen. Das einfachste GCN besteht aus drei Ebenen:

Konvolutionale Ebene– Diese Ebene führt die Konvolution an jedem Knoten durch, um seine Verbindungen zu lernen.

Nichtlineare Aktivierungsebene– Diese Ebene wendet eine Aktivierungsfunktion wie ReLU auf die Ausgabe der Konvolution an.

Lineare Ausgabeebene– Diese letzte Ebene summiert die Ausgaben, um eine endgültige Vorhersage zu generieren.

Zunächst wird eine Konvolution durchgeführt, indem jeder Knoten im Konvolutionsebenengraph verwendet wird. Diese konvolutionale Ebene verwendet Funktionsinformationen von den Nachbarn von jedem Knoten und aggregiert diese, wobei die mit jedem Knoten verknüpften Gewichtungen aktualisiert werden. Anschließend wird eine nichtlineare Aktivierungsfunktion, wie z. B. ReLU, auf die Ausgabe der Konvolutionsebene angewendet. Um die höchste Genauigkeit zu erzielen, kann ein Netzwerk mehrere übereinander gestapelte Konvolutionen und nichtlineare Aktivierungsebenen verwenden. Schließlich wird eine lineare Ausgabeebene verwendet, um vorherzusagen, zu welcher Klasse ein Graph am wahrscheinlichsten gehört.

GCN sind konzeptionell einfach, eignen sich für umfangreiche Graphen und sind leicht zu programmieren, haben aber auch einige entscheidende Nachteile. Zum einen unterstützen GCN keine Kantenfunktionen. Sie können nur die Knotenfunktion oder die Gesamtgraphenfunktion lernen und vorhersagen. Den Begriff der Nachrichtenübermittlung gibt es bei GCN nicht. Dieses Problem beschränkt die Verwendung auf Fälle, in denen alle erforderlichen Informationen im Knoten vorhanden sind und nicht in der Kante.

Ein Message Passing Neural Network (MPNN) ermöglicht jedoch die Darstellung von Kanten.⁵ Der Prozess der Nachrichtenübermittlung läuft grob wie folgt ab. Jeder Knoten im Graphen erhält eine anfängliche Einbettung als die ersten Eingabefunktionen des Knotens. Bei jedem Durchlauf der Nachrichtenübermittlung sammelt der Knoten Informationen von seinen benachbarten Knoten. Diese aggregierten Informationen werden dann mithilfe einer Aktualisierungsfunktion mit der aktuellen Einbettung des Knotens kombiniert. Die aktualisierten Einbettungen werden an die nächste Iteration der Nachrichtenübergabe weitergegeben. Nach mehreren Iterationen, die zur Darstellung der Komplexität des Graphen geeignet sind, werden die endgültigen Einbettungen verwendet, um jeden Knoten im Graphen darzustellen. Schließlich werden Aggregations-, Aktualisierungs- und Iterationsschritte von neuronalen Netzen durchgeführt, um komplexe Muster im gesamten Graphen zu lernen.

Die Nachrichtenübergabe ermöglicht eine komplexere Knotenklassifizierung, Klassifizierung von Kanten oder sogar die Vorhersage, wo Kanten im Graphen erscheinen könnten (eine sogenannte Linkvorhersage).

GNN finden viele Anwendungen in der Verarbeitung natürlicher Sprache (NLP). Bei der Dokumentenklassifizierung können GNN beispielsweise verwendet werden, um die Beziehungen zwischen Wörtern oder Sätzen in Dokumenten zu modellieren. Diese Funktion ermöglicht eine verbesserte Dokumentenklassifizierung und einen besseren Informationsabruf. GNNs können bei der Beantwortung von Fragen helfen, indem sie die Beziehungen zwischen den Wörtern einer Frage und den Antworten der Kandidaten in einem Wissensgraphen darstellen. GNN können kontextuelle Informationen und Stimmungsabhängigkeiten in Texten erfassen und so die Stimmungsanalyse in Situationen mit hoher Mehrdeutigkeit oder hochspezifischen Entitätsbeziehungen verbessern.

Sie finden auch viele Anwendungen im Bereich Computer Vision. Bei Bildsegmentierungsaufgaben können GNN für Bildsegmentierungsaufgaben auf Pixelebene verwendet werden, indem sie die Beziehungen zwischen benachbarten Pixeln als Graph modellieren. GNN können bei der Objekterkennung helfen, indem sie Kontextinformationen und Beziehungen zwischen Objekten in Bildern erfassen. Bei Aufgaben zum Verständnis von Szenen werden GNN verwendet, um komplexe Szenen zu verstehen und Szenengraphen zu erstellen, die räumliche Beziehungen zwischen Objekten in einem Bild darstellen.

GNN sind auch leistungsfähige Werkzeuge in der Bioinformatik. Bei der Genomsequenzanalyse können GNN Beziehungen zwischen Genen oder genetischen Sequenzen modellieren und so bei der Vorhersage der Genexpression und der Sequenzklassifizierung helfen. In der Wirkstoffforschung können GNN zur Vorhersage von Wechselwirkungen zwischen Wirkstoff und Zielmolekül sowie zur Vorhersage molekularer Eigenschaften eingesetzt werden, was in der pharmazeutischen Forschung von entscheidender Bedeutung ist.