Graph Neural Network (GNN)

Ein graph neuronales Netz (GNN) ist ein neuronales Netz, das direkt auf Graphen arbeitet: Mengen von Knoten, die durch Kanten verbunden sind und sowohl bei Knoten als auch bei Kanten Merkmale enthalten können. Moleküle (Atome und Bindungen), soziale Netzwerke (Benutzer und ihre Follow-Beziehungen), Straßennetze (Kreuzungen und Straßenabschnitte), 3D-Netze und die Gelenke eines menschlichen Skeletts sind allesamt Graphen. Ein Graph hat weder ein festes Raster noch eine feste Reihenfolge, und die Knoten haben unterschiedlich viele Nachbarn. Deshalb lassen sich die gleitenden Filter eines faltenden neuronalen Netzes (CNN) und das schrittweise Verarbeiten eines rekurrenten neuronalen Netzes (RNN) nicht direkt anwenden. GNNs lösen das durch Nachrichtenaustausch: Jeder Knoten aktualisiert wiederholt seinen Merkmalsvektor anhand der Merkmale seiner Nachbarn. So entstehen Knoten-Embeddings, die sowohl die eigenen Attribute eines Knotens als auch seine Position im Graphen erfassen.

So funktioniert der Nachrichtenaustausch#

Eine GNN-Schicht aktualisiert jeden Knoten in drei Schritten. Jeder Nachbar sendet eine Nachricht, meist eine gelernte Transformation seiner Merkmale. Der Knoten aggregiert die eingehenden Nachrichten mit einer Funktion, die ihre Reihenfolge ignoriert, etwa einer Summe, einem Mittelwert oder einem Maximum. Anschließend kombiniert er das Aggregat mit seinen eigenen Merkmalen, um seine neue Repräsentation zu bilden. Da die Aggregation die Reihenfolge ignoriert, hängt das Ergebnis nicht davon ab, wie die Knoten nummeriert sind. Justin Gilmer und Kollegen beschrieben 2017 viele GNNs als Instanzen dieses Message-Passing-Neuronale-Netze-Frameworks. Nach der letzten Schicht liest ein aufgabenspezifischer Kopf die Knoteneinbettungen aus, um Knoten zu kennzeichnen, fehlende Kanten vorherzusagen oder einen ganzen Graphen zu klassifizieren:

Jede Schicht erweitert den Blick eines Knotens um einen Hop. Daher hängt die Einbettung eines Knotens nach k Schichten von jedem Knoten innerhalb von k Kanten ab – von seinem rezeptiven Feld im Graphen. Der folgende PyTorch-Codeausschnitt erstellt einen Pfadgraphen mit sechs Knoten, wendet drei Graph-Faltungsschichten mit der Normalisierung aus dem GCN von Thomas Kipf und Max Welling an und verwendet autograd, um aufzulisten, welche Eingabeknoten den Knoten 0 nach jeder Schicht beeinflussen:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

Ausgegeben werden [0, 1], [0, 1, 2] und [0, 1, 2, 3]: Das rezeptive Feld von Knoten 0 wächst pro Schicht um genau einen Hop.

Gängige GNN-Architekturen#

• GCN: Das Graph Convolutional Network berechnet H′ = σ(D̃^(−1/2) à D̃^(−1/2) H W), wobei à die Adjazenzmatrix mit Selbstschleifen und D̃ ihre Gradmatrix ist: ein nach Grad gewichteter Mittelwert über jeden Knoten und seine Nachbarn, gefolgt von einer Gewichtsmatrix W, die für alle Knoten gleich ist.
• GraphSAGE: Stichproben einer festen Anzahl von Nachbarn pro Knoten und erlernt den Aggregator. So skaliert das Verfahren auf sehr große Graphen und kann Knoten einbetten, die erst nach dem Training auftauchen.
• GAT: Graph Attention Networks gewichten jeden Nachbarn anhand gelernter Aufmerksamkeits-Scores statt mit festen, gradbasierten Gewichten.
• GIN: Das Graph Isomorphism Network summiert die Nachbarn und wendet ein MLP an. Keyulu Xu und Kollegen bewiesen, dass es Graphen genauso gut auseinanderhalten kann wie der Weisfeiler-Lehman-Test, der die Obergrenze für standardmäßiges Message Passing darstellt.
• Graph-Transformer: Wenden Self-Attention auf alle Knoten an und ergänzen Positionskodierungen, die aus der Graphstruktur abgeleitet werden. Ein standardmäßiger Transformer ist selbst ein GNN auf einem vollständig verbundenen Graphen aus Tokens.

Das Stapeln vieler Schichten führt zu Übersmoothing: Wiederholte Mittelwertbildung zieht die Knoteneinbettungen einander an, bis sie nicht mehr zu unterscheiden sind. Deshalb verwenden viele GNNs nur zwei oder drei Schichten, wie schon das ursprüngliche GCN mit seinen zwei Schichten. PyTorch Geometric und die Deep Graph Library (DGL) implementieren diese Schichten effizient auf dünn besetzten Kantenlisten.

Anwendungen in der Praxis#

• Wettervorhersage: Google DeepMinds GraphCast, 2023 in Science veröffentlicht, führt Message Passing auf einem mehrskaligen Netz aus, das den gesamten Globus abdeckt. Das Modell erstellt 10-Tage-Vorhersagen mit einer Auflösung von 0.25° in weniger als einer Minute und übertrifft die genauesten operationellen deterministischen Systeme bei 90 % von 1.380 Verifikationszielen.
• Arzneimittelforschung: 2020 trainierten Forschende am MIT ein gerichtetes Message-Passing-Netzwerk, um die antibakterielle Wirkung anhand molekularer Graphen vorherzusagen. Damit identifizierten sie Halicin, eine Verbindung, deren Struktur sich deutlich von bekannten Antibiotika unterscheidet und die in Labortests viele arzneimittelresistente Bakterien abtötete.
• Empfehlungssysteme: Pinterest lernte mit PinSage Pin-Einbettungen aus einem Graphen mit 3 Milliarden Pins und Pinnwänden sowie 18 Milliarden Kanten. Das Training erfolgte mit 7,5 Milliarden Beispielen.
• Skelettbasierte Aktions erkennung: ST-GCN behandelt Körpergelenke als Knoten, verbindet sie innerhalb jedes Frames über Knochen und mit demselben Gelenk in benachbarten Frames und klassifiziert die Aktion anhand des resultierenden raumzeitlichen Graphen. YOLO26-Modelle zur Posenschätzung geben in jedem Frame 17 COCO-Schlüsselpunkte pro Person zurück – die Gelenkkoordinaten, aus denen ein solches Skelettdiagramm erstellt wird.

GNNs im Vergleich zu verwandten Konzepten#

• Wissensgraph: Eine Datenstruktur, die Fakten als Tripel aus Entität, Relation und Entität speichert. Ein GNN ist ein Modell, das daraus lernen kann, etwa um fehlende Verknüpfungen vorherzusagen.
• Geometrisches Deep Learning: Das übergeordnete Forschungsgebiet für Netzwerke, die auf den Symmetrien ihrer Daten aufbauen. Es umfasst CNNs auf Gittern, GNNs auf Graphen und Modelle auf Netzen und Mannigfaltigkeiten.
• CNN: Ein auf ein Bild angewendetes CNN ist ein Sonderfall von Message Passing auf einem Gittergraphen. Dort hat jedes Pixel dieselbe Anzahl von Nachbarn an festen relativen Positionen. Deshalb kann ein CNN für jede Nachbarposition ein eigenes Gewicht lernen, was ein GNN auf einem unregelmäßigen Graphen nicht kann.