Graph-Neuronale Netze (GNNs) sind eine Klasse von künstlichen neuronalen Netzen, die für Aufgaben entwickelt wurden, deren Eingaben Graphen sind. Ein Graph besteht aus Knoten (Eckpunkten) und Kanten (Verbindungen), die Entitäten und ihre Beziehungen darstellen können, wie etwa Atome in einem Molekül oder Benutzer in einem sozialen Netzwerk. Anders als Bilder oder Texte haben Graphen keine kanonische Reihenfolge ihrer Knoten, daher sind GNN-Architekturen typischerweise so konzipiert, dass sie permutationsäquivariant sind: Eine Neuanordnung der Knoten in der Eingabe ordnet die entsprechenden Knotenrepräsentationen auf dieselbe Weise neu. Für Vorhersageaufgaben auf Graphebene verwenden GNNs eine permutationsinvariante Readout-Funktion, deren Ausgabe durch die Knotenreihenfolge unverändert bleibt.
Das zentrale Designelement von GNNs ist der paarweise Nachrichtenaustausch (Message Passing), bei dem Graphknoten ihre Repräsentationen iterativ aktualisieren, indem sie Informationen mit ihren Nachbarn austauschen. Dies ermöglicht es dem Netzwerk, lokale strukturelle Muster und Abhängigkeiten zu erfassen. GNNs sind zu einem Eckpfeiler des maschinellen Lernens auf relationalen Daten geworden, mit Anwendungen, die Deep-Learning-Bereiche wie Molekularbiologie, Chemie, Physik, soziale Netzwerke und natürliche Sprachverarbeitung umfassen.
Historische Entwicklung
Das Konzept, neuronale Netze auf Graphen anzuwenden, entstand in den späten 1990er- und frühen 2000er-Jahren. Frühe rekursive und konvolutionäre Ansätze legten das Fundament, aber das Feld gewann in den 2010er-Jahren mit dem Aufkommen leistungsfähigerer Rechenressourcen und dem Erfolg des Deep Learnings in anderen Bereichen erheblich an Dynamik. Ein Positionspapier aus dem Jahr 2022 argumentierte, dass viele Architekturen, die als "über" Message Passing hinausgehend beschrieben werden, stattdessen als Message Passing über geeignet modifizierte Graphen interpretiert werden können, und schlug den Begriff "augmentiertes Message Passing" für solche Ansätze vor. Dies unterstreicht die zentrale Rolle des Message Passings im GNN-Design.
Architektur
Die Architektur eines generischen GNN implementiert mehrere grundlegende Schichten. Permutationsäquivariante Schichten bilden eine Repräsentation eines Graphen auf eine aktualisierte Repräsentation desselben Graphen ab, typischerweise über Message Passing. Lokale Pooling-Schichten vergröbern den Graphen durch Downsampling und vergrößern das rezeptive Feld ähnlich wie Pooling in konvolutionären neuronalen Netzen. Globale Pooling-Schichten, auch Readout-Schichten genannt, liefern eine Darstellung mit fester Größe des gesamten Graphen und müssen permutationsinvariant sein. Beispiele für globales Pooling sind elementweise Summe, Mittelwert oder Maximum.
Standard-Message-Passing-GNNs sind höchstens so ausdrucksstark wie der Weisfeiler-Leman-Graphisomorphietest, was bedeutet, dass es unterschiedliche Graphstrukturen gibt, die von solchen Netzwerken nicht unterschieden werden können. Leistungsfähigere GNNs, die auf höherdimensionalen Geometrien wie simplizialen Komplexen operieren, können entworfen werden. Stand 2022 bleibt es eine offene Forschungsfrage, ob zukünftige Architekturen die Message-Passing-Primitive überwinden werden.
Message-Passing-Schichten
Message-Passing-Schichten sind permutationsäquivariante Schichten, die einen Graphen auf eine aktualisierte Repräsentation desselben Graphen abbilden. Formal können sie als Message-Passing-Neuronale-Netze (MPNNs) ausgedrückt werden. Sei G = (V, E) ein Graph, wobei V die Knotenmenge und E die Kantenmenge ist. Für einen Knoten u in V sei N_u seine Nachbarschaft, x_u seine Merkmale und e_uv die Merkmale der Kante (u, v). Eine MPNN-Schicht berechnet eine aktualisierte Knotenrepräsentation h_u als:
h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))
wobei φ und ψ differenzierbare Funktionen sind (z. B. künstliche neuronale Netze) und ⊕ ein differenzierbarer, permutationsinvarianter Aggregator wie Summe, Mittelwert oder Maximum ist. Der Aggregator kombiniert Nachrichten von Nachbarn, und φ aktualisiert die Repräsentation des Knotens. Jede Message-Passing-Schicht vergrößert das rezeptive Feld um einen Hop, sodass Informationen über den Graphen propagieren können.
Mehrere GNN-Architekturen implementieren verschiedene Varianten des Message Passings. Beispielsweise verwenden Graph-Convolutional-Networks (GCNs) eine einfache Mittelung der Nachbarmerkmale, während Graph-Attention-Networks (GATs) Aufmerksamkeitsmechanismen einsetzen, um Nachbarbeiträge zu gewichten. Diese Variationen beeinflussen die Kapazität und den induktiven Bias des Modells.
Geometrisches Deep Learning
GNNs sind Teil des breiteren Themas des geometrischen Deep Learnings, das versucht, neuronale Netzwerkarchitekturen auf nicht-euklidische Bereiche zu verallgemeinern. In diesem Rahmen können bestimmte bestehende Architekturen als GNNs interpretiert werden, die auf geeignet definierten Graphen operieren. Beispielsweise kann eine konvolutionäre neuronale Netzwerkschicht in der Computer Vision als ein GNN betrachtet werden, das auf Graphen angewendet wird, deren Knoten Pixel sind, mit Kanten, die benachbarte Pixel verbinden. Ebenso kann eine Transformer-Schicht in der natürlichen Sprachverarbeitung als ein GNN betrachtet werden, das auf vollständige Graphen angewendet wird, deren Knoten Wörter oder Token in einem Textabschnitt sind. Diese Perspektive vereinheitlicht scheinbar disparate Architekturen unter einem gemeinsamen mathematischen Rahmen.
Anwendungen
GNNs wurden auf eine Vielzahl von Bereichen angewendet. Im molekularen Wirkstoffdesign werden Moleküle als Graphen mit Knoten für Atome und Kanten für Atombindungen dargestellt, wobei oft bekannte chemische Eigenschaften als Merkmale einbezogen werden. Eingaben können aufgrund unterschiedlicher Anzahlen von Atomen und Bindungen in der Größe variieren. Eine Aufgabe auf Graphebene könnte darin bestehen, die Wirksamkeit eines Moleküls für eine bestimmte medizinische Anwendung vorherzusagen, etwa zur Eliminierung von E.-coli-Bakterien. GNNs wurden auch in der Analyse sozialer Netzwerke, in Zitationsnetzwerken und Empfehlungssystemen eingesetzt. In der Physik können sie Teilchenwechselwirkungen modellieren, und in der kombinatorischen Optimierung wurden sie auf NP-schwere Probleme wie das Problem des Handlungsreisenden angewendet.
Implementierungen und Bibliotheken
Mehrere Open-Source-Bibliotheken implementieren GNNs und machen sie Forschern und Praktikern zugänglich. PyTorch Geometric ist eine beliebte Bibliothek, die auf PyTorch aufbaut, während TensorFlow GNN ähnliche Funktionalität für TensorFlow bietet. Die Deep Graph Library (DGL) ist framework-agnostisch und unterstützt mehrere Backends. jraph ist für JAX entwickelt, und GraphNeuralNetworks.jl und GeometricFlux.jl bedienen das Julia-Ökosystem. Diese Bibliotheken bieten vorgefertigte Schichten, Pooling-Operationen und Hilfsfunktionen für die Verarbeitung von Graphdaten, was Entwicklung und Experimentieren beschleunigt.
Herausforderungen und zukünftige Richtungen
Trotz ihres Erfolgs stehen GNNs vor mehreren Herausforderungen. Die Begrenzung der Ausdrucksstärke relativ zum Weisfeiler-Leman-Test schränkt ihre Fähigkeit ein, bestimmte Graphstrukturen zu unterscheiden. Die Skalierbarkeit auf große Graphen ist ein weiteres Problem, da Message Passing rechenintensiv sein kann. Die Forschung wird zu ausdrucksstärkeren Architekturen fortgesetzt, etwa solchen, die Merkmale höherer Ordnung oder augmentiertes Message Passing verwenden. Darüber hinaus ist das theoretische Verständnis der Generalisierung und Robustheit von GNNs ein aktives Forschungsgebiet. Stand 2022 entwickelt sich das Feld rasant weiter, wobei regelmäßig neue Architekturen und Anwendungen entstehen.