Graph Neural Networks: eine praktische Einführung

1. Was ist ein Graph Neural Network?

Ein Graph Neural Network (GNN) ist ein Deep-Learning-Modell, das direkt auf Graphen arbeitet: Daten aus Knoten (Entitäten), die durch Kanten (Beziehungen) verbunden sind. Während ein Faltungsnetz ein regelmäßiges Pixelraster und ein rekurrentes Netz eine geordnete Sequenz voraussetzt, trifft ein GNN keine dieser Annahmen. Es arbeitet auf unregelmäßigen Strukturen, in denen jeder Knoten unterschiedlich viele Nachbarn haben kann und es keine natürliche Ordnung zum Ausnutzen gibt.

Das ist wichtig, weil so viele reale Daten von Natur aus Graphen sind: soziale Netzwerke, Moleküle, Wissensgraphen, Straßennetze, Zahlungsnetzwerke und das Web selbst. Ein GNN lernt eine Vektordarstellung, ein Embedding, für jeden Knoten, jede Kante oder einen ganzen Graphen. Dieses Embedding verbindet zwei Arten von Information zugleich: die eigenen Merkmale eines Knotens und die Struktur seiner Nachbarschaft. Die Embeddings speisen anschließend einen gewöhnlichen Prädiktor für die jeweilige Aufgabe.

Das Konzept geht auf Gori et al. (2005) und Scarselli et al. (2009) zurück, die „das Graph-Neural-Network-Modell" einführten. Es blieb eine Nischenidee bis zur Deep-Learning-Welle: Zwischen 2016 und 2019 machte eine Reihe von Architekturen, nämlich GCN, GraphSAGE, GAT und GIN, GNNs zugleich skalierbar und genau, und sie gehören heute zum Standardwerkzeug des maschinellen Lernens. Zu den linear-algebraischen Wurzeln eines wichtigen Zweigs siehe unseren Begleitartikel über spektrale Graphentheorie im Machine Learning.

2. Die Kernidee: Message Passing

Nahezu jedes moderne GNN folgt einem einzigen vereinheitlichenden Rezept namens Message Passing, formalisiert von Gilmer et al. (2017). Die Anschauung ist erfrischend einfach. Jeder Knoten beginnt mit einem Merkmalsvektor. Dann führt ein Knoten in jeder Schicht drei Schritte aus: Er sammelt Nachrichten von seinen Nachbarn, aggregiert sie zu einer einzigen Zusammenfassung und aktualisiert seinen eigenen Vektor mithilfe dieser Zusammenfassung zusammen mit seinem vorherigen Wert.

Der Aggregationsschritt hat eine harte Anforderung: Er muss permutationsinvariant sein. Da ein Graph keine inhärente Ordnung besitzt, darf das Ergebnis nicht davon abhängen, in welcher Reihenfolge die Nachbarn aufgelistet sind. Die üblichen Wahlmöglichkeiten sind Summe, Mittelwert oder Maximum. Der Aktualisierungsschritt ist typischerweise ein kleines neuronales Netz, eine gelernte lineare Transformation gefolgt von einer Nichtlinearität. Entscheidend: Alle Knoten einer Schicht teilen sich dieselben Gewichte, genau wie ein CNN einen Filter über das ganze Bild wiederverwendet. Diese Gewichtsteilung ist es, die ein einziges trainiertes GNN über alle Knoten eines Graphen und sogar auf nie gesehene Graphen verallgemeinern lässt.

Dieser Rhythmus aus „Nachbarn sammeln, dann aktualisieren" ist der ganze Motor. Ein nützliches Bild ist ein Gerücht, das sich durch eine Menschenmenge verbreitet: In jeder Runde verfeinert jeder, was er weiß, anhand der Personen neben sich, und nach wenigen Runden hat eine Nachricht aus der Ferne den ganzen Raum erreicht. Ein GNN macht diesen Aktualisierungsschritt einfach lernbar, sodass das Netz selbst herausfindet, welche Signale aus der Nachbarschaft für die Aufgabe wirklich zählen.

3. Im Inneren einer GNN-Schicht (und wie tief man gehen sollte)

Formal berechnet eine einzelne Schicht für jeden Knoten v ein neues Embedding:

h_v⁽ᵏ⁾ = UPDATE( h_v⁽ᵏ⁻¹⁾, AGGREGATE{ h_u⁽ᵏ⁻¹⁾ : u ∈ N(v) } )

Dabei ist N(v) die Menge der Nachbarn von v und h_v⁽ᵏ⁾ das Embedding von v nach k Schichten. Die Anzahl der Schichten steuert das rezeptive Feld. Nach einer Schicht hat ein Knoten nur von seinen unmittelbaren Nachbarn gehört. Nach zwei Schichten hat er indirekt von den Nachbarn seiner Nachbarn gehört, denn diese hatten sich in der vorigen Runde selbst aus ihren Nachbarn aktualisiert. Allgemein lassen k Schichten Information k Sprünge weit durch den Graphen wandern.

Das könnte nahelegen, dass tiefer immer besser ist, doch GNNs sind hier ungewöhnlich. Zu viele Schichten zu stapeln verursacht Oversmoothing: Das Embedding jedes Knotens driftet zum selben Wert, und das Netz verliert die Fähigkeit, Knoten zu unterscheiden. In der Praxis sind zwei bis vier Schichten üblich, und die Tiefe zu wählen ist eine echte Entwurfsentscheidung und nicht bloß eine Frage zusätzlicher Kapazität.

4. Vier Architekturen, die das Feld geprägt haben

Vier Modelle definierten die moderne Ära der GNNs. Sie teilen das Message-Passing-Gerüst und unterscheiden sich vor allem darin, wie sie aggregieren.

• GCN (Kipf und Welling, 2017) aggregiert mit einem gradnormalisierten Mittelwert der Nachbarn. Einfach, schnell und eine bemerkenswert starke Baseline, und es ging direkt aus der spektralen Graphentheorie hervor.
• GraphSAGE (Hamilton, Ying und Leskovec, 2017) stichprobt eine feste Zahl von Nachbarn und unterstützt Mittelwert-, Maximum- oder LSTM-Aggregatoren. Sein Schlüsselbeitrag ist induktives Lernen: Es verallgemeinert auf Knoten und Graphen, die im Training nie gesehen wurden, was im industriellen Maßstab unerlässlich ist.
• GAT (Veličković et al., 2018) führt Attention ein und lernt für jeden Nachbarn ein Gewicht, sodass das Modell sich auf die relevantesten konzentrieren kann, statt alle gleich zu behandeln.
• GIN (Xu et al., 2019) wurde entworfen, um maximal ausdrucksstark zu sein. Die Autoren zeigten, dass die Fähigkeit eines GNN, Graphen zu unterscheiden, durch den klassischen Weisfeiler-Lehman-Test begrenzt ist und dass GINs injektiver Summen-Aggregator diese Schranke erreicht.

Diese vier versteht man am besten als Ausgangspunkte und nicht als abgeschlossene Liste. Dutzende spätere Varianten ergänzen Residualverbindungen, Gating, Kantenmerkmale oder klügeres Sampling, doch fast alle behalten denselben Message-Passing-Kern. GCN, GraphSAGE, GAT und GIN zu verstehen, gibt dir daher das Vokabular, um nahezu jede moderne GNN-Arbeit zu lesen und einzuordnen.

Auf einen Blick: vier zentrale GNN-Architekturen

5. Was GNNs vorhersagen: drei Ebenen

Sobald ein GNN Embeddings erzeugt hat, erfolgen Vorhersagen auf einer von drei Ebenen, und dasselbe Grundgerüst dient ihnen allen.

• Knotenebene: einzelne Knoten klassifizieren oder bewerten, etwa ein Konto als betrügerisch markieren oder die Interessen eines Nutzers vorhersagen.
• Kantenebene (Link-Vorhersage): vorhersagen, ob zwischen zwei Knoten eine Kante existieren sollte. Das ist der Motor hinter Freundschaftsvorschlägen und Produktempfehlungen.
• Graphebene: einen ganzen Graphen zu einer einzigen Vorhersage zusammenfassen, etwa ob ein Molekül giftig ist. Dies fügt einen Readout-Schritt (Pooling) hinzu, der alle Knoten-Embeddings zu einem Graphvektor zusammenführt.

Diese Modularität ist Teil dessen, was GNNs so vielseitig macht: Tausche Ausgabekopf und Labels aus, behalte den Rest, und dieselbe Architektur wechselt vom Etikettieren von Nutzern zum Empfehlen von Verbindungen bis zum Screening von Molekülen.

6. Wo Graph Neural Networks eingesetzt werden

GNNs sind rasch von Forschungsarbeiten in Produktivsysteme gewandert, die täglich von Millionen Menschen genutzt werden.

• Empfehlungen: Pinterests PinSage und verwandte Systeme betreiben Empfehlungen im Web-Maßstab über Milliarden von Objekten, indem sie Nutzer und Inhalte als einen großen Graphen behandeln.
• Wirkstoffforschung und Chemie: Ein Molekül ist buchstäblich ein Graph aus Atomen (Knoten) und Bindungen (Kanten), daher sagen GNNs molekulare Eigenschaften, Toxizität und Reaktionen vorher. Das war die ursprüngliche Motivation hinter Message-Passing-Netzen.
• Betrug und Sicherheit: Zahlungs- und Kontographen legen koordinierte Missbrauchsringe offen, die isolierte Merkmale je Konto schlicht nicht sehen können.
• Verkehr und Logistik: Google Maps hat GNNs genutzt, um seine Ankunftszeit-Schätzungen über Straßennetze hinweg zu verbessern.
• Wissenschaft und Technik: Physiksimulation, Schlussfolgern über Wissensgraphen, Empfehlungen im E-Commerce und sogar Chip-Design bauen auf Graph-Lernen auf.

Allen Fällen gemeinsam ist ein einfacher Test: Lässt sich deine Daten natürlicher als Netz von Beziehungen denn als flache Tabelle zeichnen, kann ein GNN diese Struktur meist in einen messbaren Genauigkeitsgewinn verwandeln. Genau das kommt immer häufiger vor, weshalb sich Graph-Lernen so schnell über Industrie und Wissenschaft verbreitet hat.

7. Herausforderungen, Werkzeuge und der Einstieg

GNNs sind mächtig, aber nicht mühelos. Neben dem Oversmoothing ist die Skalierbarkeit eine echte Einschränkung: Ein Graph mit Milliarden Kanten passt nicht in den Speicher, und genau deshalb wurden Nachbar-Stichproben (GraphSAGE) und Graphpartitionierung erfunden. Weitere aktive Forschungsfragen sind das Oversquashing (zu viel Information, die durch eine einzige Engpass-Kante gepresst wird), die durch den Weisfeiler-Lehman-Test gesetzte Ausdrucksgrenze und der Umgang mit dynamischen oder heterogenen Graphen, deren Knoten und Kanten in vielen Typen vorkommen.

Der Einstieg ist erfreulicherweise dank ausgereifter Bibliotheken einfach. PyTorch Geometric (PyG) und die Deep Graph Library (DGL) liefern fertige GCN-, GraphSAGE-, GAT- und GIN-Schichten, Standard-Benchmark-Datensätze und effiziente dünnbesetzte Operationen. Ein gutes erstes Projekt ist die Knotenklassifikation auf einem Zitationsgraphen wie Cora, wo ein in wenigen Zeilen geschriebenes zweischichtiges GCN klassische Baselines bereits schlägt. Von diesem kleinen Beispiel aus skaliert dasselbe Werkzeug bis zu den obigen industriellen Anwendungen.