Graphisches neuronales Netz

Graphneuronale Netze (GNNs) sind eine Klasse von künstlichen neuronalen Netzen, die für Aufgaben entwickelt wurden, deren Eingaben Graphen sind, wie etwa Molekülstrukturen, soziale Netzwerke oder Zitationsnetzwerke. Im Gegensatz zu standardmäßigen neuronalen Netzen, die von Eingaben fester Größe und Ordnung ausgehen, operieren GNNs auf Graphen beliebiger Größe und Topologie. Da Graphen im Allgemeinen keine kanonische Knotenreihenfolge besitzen, sind GNN-Architekturen typischerweise so konzipiert, dass sie permutationsäquivariant sind: Eine Neuordnung der Eingabeknoten ordnet die entsprechenden Knotenrepräsentationen in gleicher Weise neu. Für Vorhersageaufgaben auf Graphebene verwenden GNNs eine permutationsinvariante Readout-Funktion, die sicherstellt, dass die Ausgabe durch die Knotenreihenfolge unverändert bleibt.

Das zentrale Designelement von GNNs ist das paarweise Message Passing, bei dem Knoten ihre Repräsentationen iterativ aktualisieren, indem sie Informationen mit Nachbarn austauschen. Dies ermöglicht es dem Netzwerk, sowohl lokale als auch globale strukturelle Informationen zu erfassen. Eine prominente Anwendung ist das molekulare Medikamentendesign, bei dem Moleküle als Graphen mit Atomen als Knoten und Bindungen als Kanten dargestellt werden, oft einschließlich chemischer Eigenschaften als Merkmale. Aufgaben auf Graphebene umfassen die Vorhersage der Wirksamkeit eines Moleküls für eine bestimmte medizinische Verwendung, wie etwa die Beseitigung von E.-coli-Bakterien. GNNs wurden auch in der Verarbeitung natürlicher Sprache, der Analyse sozialer Netzwerke, der Physik und der NP-schweren kombinatorischen Optimierung eingesetzt.

Historische Entwicklung

Das Konzept, neuronale Netze auf graphstrukturierte Daten anzuwenden, entstand Ende der 1990er und Anfang der 2000er Jahre. Frühe Arbeiten von Forschern wie Franco Scarselli und Kollegen führten rekurrente neuronale Netze für Graphen ein, die Graphenstrukturen auf rekurrente Weise verarbeiteten. Etwa zur gleichen Zeit wurden Faltungsansätze entwickelt, die zu den ersten Graphfaltungsnetzwerken führten. Diese frühen Architekturen legten das Fundament für moderne GNNs, die durch Beiträge vieler akademischer und industrieller Forschungsgruppen weiterentwickelt wurden.

Ein bedeutender Meilenstein war die Einführung von Message-Passing-Neuronalen-Netzen (MPNNs) im Jahr 2017, die viele bestehende GNN-Varianten unter einem gemeinsamen Rahmenwerk vereinheitlichten. Seitdem wurden zahlreiche Architekturen vorgeschlagen, die jeweils unterschiedliche Varianten des Message Passing implementieren. Ein Positionspapier aus dem Jahr 2022 argumentierte, dass viele Architekturen, die als "jenseits" des Message Passing beschrieben werden, stattdessen als Message Passing über geeignet modifizierte Graphen interpretiert werden können, und prägte den Begriff "augmentiertes Message Passing" für solche Ansätze.

Architektur

Die Architektur eines generischen GNN umfasst typischerweise drei grundlegende Arten von Schichten: permutationsäquivariante Schichten, lokale Pooling-Schichten und globale Pooling-Schichten. Permutationsäquivariante Schichten, die oft über Message Passing implementiert werden, aktualisieren Knotenrepräsentationen, indem sie Nachrichten von unmittelbaren Nachbarn aggregieren. Jede solche Schicht erhöht das rezeptive Feld um einen Hop, sodass Knoten Informationen aus weiter entfernten Teilen des Graphen einbeziehen können.

Lokale Pooling-Schichten vergröbern den Graphen durch Downsampling, ähnlich dem Pooling in Faltungsnetzwerken für Bilder. Beispiele sind k-Nearest-Neighbors-Pooling, Top-k-Pooling und Self-Attention-Pooling. Globale Pooling-Schichten, auch als Readout-Schichten bekannt, erzeugen eine Repräsentation fester Größe des gesamten Graphen und müssen permutationsinvariant sein. Häufige Readout-Funktionen sind elementweise Summe, Mittelwert oder Maximum.

Standardmäßige Message-Passing-GNNs sind höchstens so ausdrucksstark wie der Weisfeiler-Lehman-Graphisomorphietest, was bedeutet, dass es unterschiedliche Graphenstrukturen gibt, die von solchen Netzwerken nicht unterschieden werden können. Leistungsfähigere GNNs, die auf höherdimensionalen Geometrien wie simplizialen Komplexen operieren, wurden vorgeschlagen. Stand 2022 bleibt offen, ob zukünftige Architekturen das Message-Passing-Primitiv überwinden werden.

Message-Passing-Schichten

Message-Passing-Schichten sind der Kern der meisten GNNs. Formal können sie als Message-Passing-Neuronale-Netze (MPNNs) ausgedrückt werden. Gegeben einen Graphen G = (V, E) mit Knotenmerkmalen x_u und Kantenmerkmalen e_uv, aktualisiert eine MPNN-Schicht die Repräsentation jedes Knotens h_u unter Verwendung einer differenzierbaren Funktion φ und einer Nachrichtenfunktion ψ:

h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))

Hier bezeichnet N_u die Nachbarschaft von Knoten u, und ⊕ ist eine permutationsinvariante Aggregationsfunktion wie Summe, Mittelwert oder Maximum. Die Nachrichtenfunktion ψ berechnet eine Nachricht von jedem Nachbarn, und die Aggregation kombiniert diese Nachrichten. Die Aktualisierungsfunktion φ kombiniert dann die eigenen Merkmale des Knotens mit den aggregierten Nachrichten, um die neue Repräsentation zu erzeugen.

Verschiedene GNN-Architekturen unterscheiden sich darin, wie sie ψ und φ definieren. Beispielsweise verwenden Graphfaltungsnetzwerke (GCNs) eine einfache normalisierte Summe der Nachbarmerkmale, während Graph-Attention-Netzwerke (GATs) Aufmerksamkeitsmechanismen einsetzen, um Nachbarbeiträge zu gewichten. Diese Variationen ermöglichen es GNNs, verschiedene Aspekte der Graphenstruktur zu erfassen.

Geometrisches Deep Learning

GNNs sind Teil des breiteren Feldes des geometrischen Deep Learnings, das darauf abzielt, neuronale Netze auf nicht-euklidische Domänen zu verallgemeinern. In diesem Kontext können viele bestehende Architekturen als GNNs interpretiert werden, die auf geeignet definierten Graphen operieren. Beispielsweise kann eine Faltungsschicht in der Computervision als ein GNN betrachtet werden, das auf Graphen angewendet wird, bei denen Knoten Pixel sind und Kanten benachbarte Pixel verbinden. Ebenso kann eine Transformer-Schicht in der Verarbeitung natürlicher Sprache als ein GNN angesehen werden, das auf vollständigen Graphen operiert, deren Knoten Wörter oder Token in einem Textabschnitt sind.

Diese Perspektive hat zu einer gegenseitigen Befruchtung zwischen den Feldern geführt. Techniken, die für GNNs entwickelt wurden, wie Aufmerksamkeitsmechanismen, haben Transformer-Architekturen beeinflusst, und Erkenntnisse aus Transformatoren haben das GNN-Design informiert. Die vereinheitlichte Sichtweise des geometrischen Deep Learnings wurde von Forschern wie Michael Bronstein und Joan Bruna unter anderem artikuliert.

Anwendungen

GNNs finden Anwendungen in einer Vielzahl von Domänen. In der Molekularbiologie und Chemie werden sie für die Wirkstoffforschung, die Vorhersage von Proteinfunktionen und das Materialdesign eingesetzt. Beispielsweise können GNNs molekulare Eigenschaften vorhersagen oder neuartige Moleküle mit gewünschten Eigenschaften erzeugen. In sozialen Netzwerken unterstützen GNNs Empfehlungssysteme, Gemeinschaftserkennung und Linkvorhersage. Zitationsnetzwerke, bei denen Papiere Knoten und Zitationen Kanten sind, profitieren von GNNs für Themenklassifikation und Einflussvorhersage.

In der Physik modellieren GNNs Teilcheninteraktionen und simulieren dynamische Systeme. Sie werden auch auf NP-schwere kombinatorische Optimierungsprobleme angewendet, wie das Problem des Handlungsreisenden oder die Graphfärbung, wo sie Heuristiken lernen können. In der Verarbeitung natürlicher Sprache werden GNNs für semantisches Parsing, Relationsextraktion und Wissensgraph-Argumentation verwendet. Darüber hinaus wurden GNNs in der Computervision für die Szenengraphen-Generierung und Punktwolkenverarbeitung eingesetzt.

Software-Bibliotheken

Mehrere Open-Source-Bibliotheken implementieren GNNs und machen sie für Forscher und Praktiker zugänglich. PyTorch Geometric, aufgebaut auf PyTorch, ist eine der am weitesten verbreiteten Bibliotheken und bietet eine umfangreiche Sammlung von GNN-Schichten und Datensätzen. TensorFlow GNN bietet ähnliche Funktionalität für das TensorFlow-Ökosystem. Die Deep Graph Library (DGL) ist framework-agnostisch und unterstützt sowohl PyTorch als auch TensorFlow. Für Benutzer von JAX bietet jraph GNN-Primitive. In der Sprache Julia bieten GraphNeuralNetworks.jl und GeometricFlux.jl GNN-Implementierungen.

Diese Bibliotheken haben die Forschung und Bereitstellung von GNNs beschleunigt, indem sie effiziente Implementierungen von Message Passing, Pooling und Readout-Operationen bereitstellen. Sie enthalten auch Hilfsmittel für die Handhabung von Graphdaten, wie Batching und Datenladen, die für das Training auf großen Graphen unerlässlich sind.

Herausforderungen und zukünftige Richtungen

Trotz ihres Erfolgs stehen GNNs vor mehreren Herausforderungen. Ein Hauptproblem ist die Skalierbarkeit, da Message Passing über große Graphen rechenintensiv sein kann. Techniken wie Graph-Sampling und Mini-Batch-Training wurden entwickelt, um dies zu adressieren. Eine weitere Herausforderung ist Oversmoothing, bei dem wiederholtes Message Passing dazu führt, dass Knotenrepräsentationen ununterscheidbar werden, was die Tiefe von GNNs begrenzt.

Ausdrucksstärke ist ein weiteres aktives Forschungsgebiet. Da Standard-GNNs durch den Weisfeiler-Lehman-Test begrenzt sind, haben Forscher GNNs höherer Ordnung, Graphtransformatoren und Architekturen, die auf simplizialen Komplexen oder Hypergraphen operieren, untersucht. Diese Ansätze zielen darauf ab, komplexere strukturelle Informationen zu erfassen. Stand 2022 ist die Frage, ob Message Passing das dominierende Paradigma bleiben wird, offen, mit laufender Arbeit an augmentiertem Message Passing und alternativen Primitiven.

Interpretierbarkeit und Robustheit sind ebenfalls wichtig. Zu verstehen, was GNNs lernen, und sie robust gegenüber adversarialen Angriffen auf Graphen zu machen, sind aktive Forschungsthemen. Da GNNs zunehmend in sicherheitskritischen Bereichen wie dem Gesundheitswesen und autonomen Systemen eingesetzt werden, wird die Bewältigung dieser Herausforderungen entscheidend für ihre breitere Akzeptanz sein.