Graph Neural Networks (GNN, deutsch Graph-Neuronale-Netze) sind neuronale Netze, die direkt auf Graphen operieren. Klassische Netze erwarten feste Eingabevektoren; ein GNN verarbeitet dagegen eine beliebig strukturierte Menge von Knoten und Kanten und lernt Repräsentationen (Embeddings) für jeden Knoten, jede Kante oder den ganzen Graphen.
Die Kernidee: Message Passing
Die grundlegende Operation eines GNN ist das Message Passing (Nachrichtenweitergabe): In jeder Schicht sammelt ein Knoten die aktuellen Repräsentationen seiner Nachbarn, aggregiert sie (zum Beispiel per Summe, Mittelwert oder Maximum) und kombiniert das Ergebnis mit der eigenen Repräsentation. Nach k Schichten kennt jeder Knoten damit Informationen aus seiner k-Hop-Umgebung. Diese iterative Nachbarschaftsaggregation ist das Pendant zu den Faltungen (Convolutions) in Bildnetzen — daher stammt auch der Name der bekanntesten Variante, der Graph Convolutional Network (GCN). Weitere verbreitete Architekturen sind GraphSAGE (effizientes Sampling statt voller Nachbarschaft) und Graph Attention Networks (GAT, gewichtet die Nachbarn per Aufmerksamkeitsmechanismus).
Expressivität und Grenzen
Wie mächtig ein GNN ist, hängt eng mit der Färbeverfeinerung des Weisfeiler-Lehman-Tests zusammen: Message-Passing-GNNs sind höchstens so unterscheidungsstark wie der 1-dimensionale Weisfeiler-Lehman-Algorithmus. Zwei nicht-isomorphe Graphen, die der WL-Test nicht unterscheiden kann, bekommen auch von einem klassischen GNN dieselbe Repräsentation. Mächtigere Varianten (höherdimensionale WL-Verfahren, Invarianten-basierte Modelle) umgehen diese Grenze, sind aber aufwendiger.
Anwendungen
GNNs sind dort stark, wo Daten natürlicherweise als Netzwerk vorliegen: Vorhersage von Moleküleigenschaften in der Chemie, Wirkstoff-Forschung, Empfehlungssysteme, soziale Netzwerke, Wissensgraphen und die Analyse von Verkehrs- oder Stromnetzen. Typische Aufgaben sind die Klassifikation von Teilgraphen oder ganzen Graphen, die Vorhersage fehlender Kanten (Link Prediction) und die Knotenklassifikation in maschinellen Lernverfahren. Gegenüber einem Deep-Learning-Modell auf flach gepackten Vektoren nutzt ein GNN die Adjazenzstruktur des Graphen direkt aus.