Graphische neuronale Netze (GNNs) sind eine Klasse künstlicher neuronaler Netze, die für die Verarbeitung von Daten in Graphstrukturen entwickelt wurden, wobei die Eingaben aus Knoten (Eckpunkten) und Kanten (Verbindungen) bestehen, die keine kanonische Reihenfolge aufweisen können. Im Gegensatz zu Standard-Neuronalen Netzen, die feste, geordnete Eingaben annehmen, sind GNNs darauf ausgelegt, Graphen unterschiedlicher Größen und Topologien zu verarbeiten, was sie für Bereiche wie Molekülchemie, soziale Netzwerkanalyse und kombinatorische Optimierung geeignet macht. Die Kerninnovation von GNNs liegt in ihrer Verwendung von paarweisem Nachrichtenaustausch, bei dem jeder Knoten seine Darstellung iterativ aktualisiert, indem er Informationen von seinen Nachbarn aggregiert, wodurch das Netzwerk lokale strukturelle Muster und Abhängigkeiten erfassen kann.
GNNs sind typischerweise so konzipiert, dass sie permutationsäquivariant sind, was bedeutet, dass eine Umordnung der Knoten im Eingabegraphen zu einer entsprechenden Umordnung der vom Netzwerk erzeugten Knotendarstellungen führt. Für Aufgaben auf Graphebene, wie die Vorhersage einer Eigenschaft eines gesamten Moleküls, verwenden GNNs eine permutationsinvariante Readout-Funktion, die Knotendarstellungen zu einer einzigen Ausgabe fester Größe aggregiert, wodurch sichergestellt wird, dass das Ergebnis unabhängig von der Knotenreihenfolge ist. Diese Eigenschaft ist wesentlich, da Graphen keine natürliche Knotenreihenfolge haben und die Ausgabe des Netzwerks konsistent sein sollte, unabhängig davon, wie der Graph dargestellt wird.
Historische Entwicklung
Das Konzept der GNNs entstand aus früheren Arbeiten zu neuronalen Netzen für strukturierte Daten, wobei grundlegende Ideen bis in die 1990er Jahre zurückreichen. Frühe Ansätze, wie rekurrente neuronale Netze, die auf gerichteten azyklischen Graphen angewendet wurden, legten den Grundstein für die Verarbeitung graphartiger Strukturen. Die moderne Formulierung von GNNs, basierend auf Nachrichtenaustausch und Permutationsäquivarianz, gewann jedoch in den 2010er Jahren mit dem Aufstieg des Deep Learnings an Bedeutung. Forscher an Institutionen wie MIT CSAIL und Stanford AI Lab trugen zur Entwicklung von Architekturen bei, die beliebige Graphen verarbeiten können, was zur Etablierung von GNNs als eigenständigem Teilgebiet innerhalb des maschinellen Lernens führte.
Bis Ende der 2010er Jahre waren GNNs zu einem Standardwerkzeug im Deep Learning geworden, mit zahlreichen Varianten, die vorgeschlagen wurden, um ihre Ausdruckskraft und Skalierbarkeit zu verbessern. Das Positionspapier "Weisfeiler and Leman Go Neural" aus dem Jahr 2022 und ähnliche Arbeiten formalisierten die Beziehung zwischen GNNs und Graphisomorphie-Tests, klärten ihre theoretischen Grenzen und inspirierten die Forschung zu leistungsfähigeren Architekturen.
Architektur
Die Architektur eines generischen GNN implementiert mehrere grundlegende Schichten, die zusammenarbeiten, um graphstrukturierte Eingaben zu verarbeiten. Diese Schichten umfassen permutationsäquivariante Schichten, lokale Pooling-Schichten und globale Pooling-Schichten, die jeweils einen bestimmten Zweck bei der Transformation der Graphdarstellung erfüllen.
Permutationsäquivariante Schichten sind der Kern von GNNs und werden über paarweisen Nachrichtenaustausch zwischen Graphknoten implementiert. In einer Nachrichtenaustauschschicht aktualisiert jeder Knoten seine Darstellung, indem er Nachrichten aggregiert, die von seinen unmittelbaren Nachbarn empfangen werden. Dieser Prozess erhöht das rezeptive Feld des GNN um einen Hop pro Schicht, sodass das Netzwerk Informationen aus zunehmend größeren Nachbarschaften einbeziehen kann. Die Nachrichtenaustauschoperation kann formal als eine Funktion ausgedrückt werden, die Knotenmerkmale, Nachbarmerkmale und Kantenmerkmale als Eingaben nimmt und eine aktualisierte Knotendarstellung erzeugt.
Lokale Pooling-Schichten vergröbern den Graphen durch Downsampling, wodurch die Anzahl der Knoten reduziert wird, während wichtige strukturelle Informationen erhalten bleiben. Dies ist analog zu Pooling-Schichten in Convolutional Neural Networks (CNNs) und hilft, das rezeptive Feld des GNN zu erhöhen. Häufige Beispiele sind k-nächste-Nachbarn-Pooling, Top-k-Pooling und Self-Attention-Pooling, die jeweils eine Teilmenge von Knoten basierend auf unterschiedlichen Kriterien auswählen, um sie beizubehalten.
Globale Pooling-Schichten, auch Readout-Schichten genannt, liefern eine Darstellung fester Größe des gesamten Graphen. Diese Schichten müssen permutationsinvariant sein, was bedeutet, dass jede Permutation der Knoten und Kanten des Graphen die endgültige Ausgabe nicht verändert. Elementweise Summen-, Mittelwert- und Maximumoperationen sind typische Wahlmöglichkeiten für globales Pooling, die Knotendarstellungen zu einem einzigen Vektor aggregieren, der für Vorhersagen auf Graphebene verwendet werden kann.
Nachrichtenaustauschschichten
Nachrichtenaustauschschichten sind die definierende Komponente von GNNs und implementieren permutationsäquivariante Transformationen durch einen Prozess, der als Message Passing Neural Networks (MPNNs) bekannt ist. Gegeben einen Graphen G = (V, E) mit Knotenmenge V und Kantenmenge E, hat jeder Knoten u in V zugehörige Merkmale x_u, und jede Kante (u, v) in E hat Merkmale e_uv. Die Nachbarschaft eines Knotens u, bezeichnet als N_u, besteht aus allen Knoten v, sodass (u, v) eine Kante in E ist.
Eine MPNN-Schicht aktualisiert die Darstellung jedes Knotens u unter Verwendung einer Nachrichtenaustauschfunktion. Die Schicht berechnet Nachrichten von jedem Nachbarn v zu u, wobei die Nachricht eine Funktion der Quellknotenmerkmale, Zielknotenmerkmale und Kantenmerkmale ist. Diese Nachrichten werden mit einer permutationsinvarianten Operation, wie Summe, Mittelwert oder Maximum, aggregiert und dann mit den eigenen Merkmalen des Knotens durch eine differenzierbare Aktualisierungsfunktion, typischerweise ein neuronales Netz, kombiniert. Dieser Prozess kann über mehrere Schichten wiederholt werden, sodass Informationen über den Graphen propagieren können.
Das Design von Nachrichtenaustauschfunktionen variiert zwischen verschiedenen GNN-Architekturen. Einige verwenden einfache lineare Transformationen, während andere komplexere Aufmerksamkeitsmechanismen oder Gated Recurrent Units einsetzen. Die Wahl der Aggregationsoperation beeinflusst auch die Ausdruckskraft des Netzwerks und seine Fähigkeit, verschiedene Arten struktureller Informationen zu erfassen.
Ausdruckskraft und Grenzen
Standard-Message-Passing-GNNs sind höchstens so ausdrucksstark wie der Weisfeiler-Lehman-Graphisomorphie-Test, ein klassischer Algorithmus zur Bestimmung, ob zwei Graphen isomorph sind. Dies bedeutet, dass es unterschiedliche Graphstrukturen gibt, die von Standard-GNNs nicht unterschieden werden können, da sie identische Darstellungen für nicht-isomorphe Graphen erzeugen können. Diese Einschränkung ergibt sich aus der lokalen Natur des Nachrichtenaustauschs, der auf der Aggregation von Informationen von unmittelbaren Nachbarn beruht und möglicherweise globale strukturelle Muster nicht erfassen kann.
Um diese Grenzen zu überwinden, haben Forscher leistungsfähigere GNNs vorgeschlagen, die auf höherdimensionalen Geometrien operieren, wie simplizialen Komplexen oder Hypergraphen, die Interaktionen höherer Ordnung über paarweise Kanten hinaus kodieren können. Stand 2022 bleibt offen, ob zukünftige Architekturen das Message-Passing-Primitiv vollständig überwinden werden, wobei laufende Arbeiten alternative Paradigmen wie Graph-Transformer und äquivariante neuronale Netze untersuchen.
Anwendungen
GNNs haben Anwendungen in einer Vielzahl von Bereichen gefunden, die ihre Fähigkeit zur Verarbeitung graphstrukturierter Daten nutzen. In der Molekularbiologie und Chemie werden Moleküle als Graphen mit Knoten für Atome und Kanten für chemische Bindungen dargestellt, wobei oft bekannte chemische Eigenschaften als Merkmale einbezogen werden. Aufgaben auf Graphebene umfassen die Vorhersage der Wirksamkeit eines Moleküls für eine bestimmte medizinische Anwendung, wie die Beseitigung von E. coli-Bakterien, oder die Schätzung physikalischer und chemischer Eigenschaften wie Löslichkeit und Toxizität. Dies macht GNNs zu wertvollen Werkzeugen im Wirkstoffdesign und in der Materialwissenschaft.
In der natürlichen Sprachverarbeitung können GNNs auf syntaktische Abhängigkeitsbäume oder semantische Rollengraphen angewendet werden, um Beziehungen zwischen Wörtern in einem Satz zu erfassen. Sie werden auch in der sozialen Netzwerkanalyse verwendet, um Benutzerinteraktionen zu modellieren, Gemeinschaften zu erkennen und Links vorherzusagen. Zitationsnetzwerke, in denen Knoten Papiere und Kanten Zitationen darstellen, sind eine weitere häufige Anwendung, die Aufgaben wie Papierklassifikation und Empfehlung ermöglicht.
GNNs sind auch in der Physik relevant, wo sie Teilcheninteraktionen modellieren oder dynamische Systeme simulieren können, sowie bei NP-schweren kombinatorischen Optimierungsproblemen, wo sie Heuristiken für Aufgaben wie Graphfärbung oder Traveling-Salesman-Probleme lernen können. Die Vielseitigkeit von GNNs hat zu ihrer Übernahme sowohl in der akademischen Forschung als auch in industriellen Anwendungen geführt.
Beziehung zu anderen neuronalen Netzarchitekturen
Im breiteren Kontext des geometrischen Deep Learnings können bestimmte bestehende neuronale Netzarchitekturen als GNNs interpretiert werden, die auf geeignet definierten Graphen operieren. Eine Convolutional Neural Network (CNN)-Schicht, die häufig im Computer Vision verwendet wird, kann als ein GNN betrachtet werden, das auf Graphen angewendet wird, deren Knoten Pixel sind, mit Kanten, die nur benachbarte Pixel verbinden. Diese Perspektive hebt die gemeinsamen Prinzipien lokaler Konnektivität und Merkmalsaggregation zwischen CNNs und GNNs hervor.
Ähnlich kann eine Transformer-Schicht, die weit verbreitet in der natürlichen Sprachverarbeitung und in großen Sprachmodellen ist, als ein GNN betrachtet werden, das auf vollständige Graphen angewendet wird, deren Knoten Wörter oder Token in einem Textabschnitt sind. In dieser Interpretation fungiert der Aufmerksamkeitsmechanismus in Transformatoren als eine Form des Nachrichtenaustauschs, bei dem jedes Token Informationen von allen anderen Token aggregiert. Diese Verbindung hat Forschung zur Vereinheitlichung dieser Architekturen und zur Anwendung von Erkenntnissen aus GNNs zur Verbesserung transformerbasierter Modelle inspiriert.
Softwarebibliotheken und Werkzeuge
Mehrere Open-Source-Bibliotheken wurden entwickelt, um die Implementierung und Bereitstellung von GNNs zu erleichtern. PyTorch Geometric, aufgebaut auf dem PyTorch-Framework, bietet eine umfassende Sammlung von Werkzeugen für die Verarbeitung von Graphdaten und Nachrichtenaustauschschichten. TensorFlow GNN bietet ähnliche Funktionalität innerhalb des TensorFlow-Ökosystems. Die Deep Graph Library (DGL) ist eine framework-agnostische Bibliothek, die mehrere Backends unterstützt, einschließlich PyTorch, TensorFlow und Apache MXNet. Für Benutzer von Google JAX bietet jraph eine leichtgewichtige Bibliothek für graphische neuronale Netze. In der Programmiersprache Julia bieten GraphNeuralNetworks.jl und GeometricFlux.jl GNN-Implementierungen, die auf dem Flux-Machine-Learning-Framework aufbauen.
Diese Bibliotheken haben die Einstiegshürde für Forscher und Praktiker gesenkt und ermöglichen schnelles Prototyping und Experimentieren mit verschiedenen GNN-Architekturen. Sie enthalten Implementierungen standardmäßiger Nachrichtenaustauschschichten, Pooling-Operationen und Dienstprogramme zum Laden und Verarbeiten von Graphdatensätzen, wodurch GNNs einem breiten Publikum zugänglich werden.
Zukünftige Richtungen
Die Forschung zu GNNs entwickelt sich weiter, mit aktiven Untersuchungsbereichen wie der Verbesserung der Ausdruckskraft, der Skalierbarkeit auf große Graphen und der Robustheit gegenüber verrauschten oder unvollständigen Daten. Die Entwicklung von Graph-Transformatoren, die Aufmerksamkeitsmechanismen mit Graphstruktur kombinieren, stellt eine vielversprechende Richtung zur Erfassung langreichweitiger Abhängigkeiten dar. Darüber hinaus wächst das Interesse an der Anwendung von GNNs auf dynamische Graphen, bei denen sich Knoten und Kanten im Laufe der Zeit ändern, sowie auf heterogene Graphen mit mehreren Typen von Knoten und Kanten.
Stand Anfang der 2020er Jahre sind GNNs zu einem Standardbestandteil des Machine-Learning-Werkzeugkastens geworden, mit laufenden Beiträgen von akademischen Institutionen und industriellen Forschungslabors. Das theoretische Verständnis ihrer Fähigkeiten und Grenzen vertieft sich weiter und leitet das Design von Architekturen der nächsten Generation, die zunehmend komplexe graphbasierte Probleme bewältigen können.