Zum Inhalt springen
Zurück zu den Suchergebnissen

Graph Neural Network — GCN / GAT / GraphSAGE

Jahr
2017–2018 (major variants)
Typ
Deep learning on graph-structured data

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Ein Graph Neural Network (GNN) ist eine Deep-Learning-Architektur, die direkt auf graphenstrukturierten Daten operiert, indem sie Knotenmerkmale mit strukturellen Informationen durch iterative Nachbarschafts-Nachrichtenweitergabe kombiniert.

Die drei kanonischen Varianten – das Graph Convolutional Network (GCN), eingeführt von Kipf und Welling im Jahr 2017, das Graph Attention Network (GAT), eingeführt von Veličković et al. im Jahr 2018, und GraphSAGE – unterscheiden sich darin, wie sie Nachbarinformationen aggregieren: GCN wendet eine spektrale Faltung über die vollständige Adjazenz an, GAT gewichtet Nachbarn mit gelernten Aufmerksamkeitswerten und GraphSAGE sampelt und aggregiert lokale Nachbarschaften induktiv, was eine Generalisierung auf ungesehene Knoten ermöglicht.

Die Intuition hinter der Methode

Stellen Sie sich jeden Knoten in einem Graphen als Person in einem sozialen Netzwerk vor. Diese Person hat ihr eigenes Profil (Merkmale), aber auch, wen sie kennt, sagt viel über sie aus. Ein GNN ermöglicht es jedem Knoten, wiederholt Nachrichten von seinen Nachbarn zu sammeln, diese Nachrichten mit seinen eigenen Informationen zu vermischen und seine Repräsentation – Schicht für Schicht – zu aktualisieren. Nach einigen Runden dieses gossipartigen Austauschs spiegelt die Einbettung jedes Knotens nicht nur ihn selbst, sondern auch den lokalen Teilgraphen um ihn herum wider. GCN tut dies mit einem festen symmetrischen Durchschnitt der Nachbarn; GAT entscheidet, welche Nachbarn mehr Vertrauen verdienen, indem es Aufmerksamkeitsgewichte lernt; GraphSAGE sampelt eine feste Teilmenge von Nachbarn und lernt eine Aggregationsfunktion, die auf Knoten angewendet werden kann, die es noch nie zuvor gesehen hat.

Geschichte

Die Grundlagen der Anwendung von neuronalen Netzen auf Graphen wurden von Scarselli et al. (2009) gelegt, aber die moderne GNN-Ära begann mit dem Graph Convolutional Network (2017) von Kipf und Welling, das die spektrale Graphfaltung in eine effiziente Approximation erster Ordnung durch symmetrische normalisierte Adjazenzmultiplikation vereinfachte. Ein Jahr später führten Veličković et al. (2018) Graph Attention Networks ein, die das feste Mitteln von GCN durch lernbare Aufmerksamkeitskoeffizienten an jeder Kante ersetzten – wodurch das Modell Nachbarn selektiv gewichten konnte. Gleichzeitig schlugen Hamilton et al. (2017) GraphSAGE vor, einen induktiven Rahmen, der Nachbarschaften fester Größe sampelt und Aggregationsfunktionen lernt, die auf ungesehene Knoten übertragbar sind, was GNNs für große und dynamische Graphen praktikabel macht. Diese drei Arbeiten etablierten das Message-Passing-Paradigma, das heute die Mehrheit der GNN-Forschung untermauert.

Wann wird sie eingesetzt?

Verwenden Sie ein GNN, wenn Ihre Daten von Natur aus graphenstrukturiert sind – soziale Netzwerke, Zitationsnetzwerke, Molekülgraphen, Wissensgraphen oder jede Umgebung, in der Beziehungen zwischen Entitäten ein prädiktives Signal tragen. Sie benötigen eine Knotenmerkmalmatrix und eine Kantenliste. Eine Mindestanzahl von etwa 50 Knoten ist für ein sinnvolles Training erforderlich. GNNs sind anwendbar auf Knotenklassifizierung (Vorhersage eines Labels für jeden Knoten), Link-Vorhersage (Schlussfolgerung fehlender Kanten) und Graphklassifizierung (Zuweisung eines Labels zu einem ganzen Graphen). Die Homophilie-Annahme – verbundene Knoten teilen tendenziell dasselbe Label – wird implizit von GCN und Standard-GAT ausgenutzt; wenn Ihr Graph heterophil ist, sollten Sie Architekturen in Betracht ziehen, die dafür entwickelt wurden. Für große Graphen ist das Full-Batch-Training speicherintensiv und es ist ein Mini-Batch-Nachbarschafts-Sampling (im Stil von GraphSAGE) erforderlich. Wenn Ihr Graph weniger als 20 Knoten hat, sind traditionelle Zentralitätsmetriken eine geeignetere Wahl.

Grenzen und Hinweise

  • Übersmoothing: Das Stapeln vieler GNN-Schichten drängt alle Knoteneinbettungen zu einem gemeinsamen Wert, was die effektive Tiefe in der Praxis auf etwa 2–4 Schichten begrenzt.
  • Skalierbarkeit: Full-Batch-GCN und GAT erfordern das Halten der gesamten Adjazenzmatrix und Merkmalsmatrix im Speicher, was für sehr große Graphen ohne Sampling oder Partitionierung nicht machbar ist.
  • Die in der Standardaggregation verankerte Homophilie-Annahme verschlechtert die Leistung auf heterophilen Graphen, bei denen Nachbarn tendenziell unterschiedliche Labels haben.
  • Eine Mindeststichprobengröße von ca. 50 Knoten ist erforderlich; weniger Knoten lassen dem Modell nicht genügend Signal, um aussagekräftige Repräsentationen zu lernen.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Nutzt sowohl Knotenmerkmale als auch Graphentopologie gemeinsam und übertrifft Methoden, die nur eines davon verwenden.
  • Der Aufmerksamkeitsmechanismus von GAT liefert pro Kante Wichtigkeitswerte, was die Interpretierbarkeit der Aggregation erhöht.
  • GraphSAGE ist induktiv und kann auf Knoten und Graphen verallgemeinert werden, die während des Trainings nicht gesehen wurden, was den Einsatz in wachsenden Netzwerken ermöglicht.
  • Ein einheitlicher Message-Passing-Rahmen deckt Knotenklassifizierung, Link-Vorhersage und Graphklassifizierung mit demselben architektonischen Backbone ab.

Anwendungen

  • Knotenklassifizierung in Zitationsnetzwerken – Vorhersage des Themas einer wissenschaftlichen Arbeit basierend auf seinem Inhalt und seinen Zitationsverknüpfungen.
  • Wirkstoffentdeckung – Vorhersage von Moleküleigenschaften, indem Atome als Knoten und chemische Bindungen als Kanten behandelt werden.
  • Empfehlungssysteme – Modellierung von Benutzern und Artikeln als bipartiter Graph und Vorhersage von Benutzer-Artikel-Interaktionen durch Link-Vorhersage.
  • Betrugserkennung in Finanztransaktionsnetzwerken – Identifizierung anomaler Knoten basierend auf ihren Merkmalen und ihrer Nachbarschaftsstruktur.
  • Vervollständigung von Wissensgraphen – Schlussfolgerung fehlender Beziehungen zwischen Entitäten in großen Wissensdatenbanken.

So funktioniert es

So funktioniert es

1

Der Graph wird durch eine Knotenmerkmalmatrix X (eine Zeile pro Knoten, eine Spalte pro Attribut) und eine Kantenliste (oder Adjazenzmatrix) A definiert. Ungerichtete Kanten sind Standard für GCN und GAT; GraphSAGE unterstützt auch gerichtete Graphen. Selbstschleifen werden typischerweise zu A hinzugefügt, sodass jeder Knoten in seine eigene Aggregation einbezogen wird.

2

Rohe Knotenattribute werden normalisiert und, falls erforderlich, in einen kontinuierlichen Vektorraum eingebettet. Kantenattribute, falls vorhanden, können als zusätzliche Signale einbezogen werden. Das Ergebnis ist eine dichte Merkmalsmatrix, die jede GNN-Schicht transformieren wird.

3

Jede GNN-Schicht berechnet eine neue Knotendarstellung, indem sie die Merkmale der Nachbarn eines Knotens aggregiert und diese mit den eigenen Merkmalen des Knotens durch eine lernbare Gewichtsmatrix und eine nichtlineare Aktivierung kombiniert. GCN wendet eine normalisierte Adjazenzmultiplikation (spektrale Faltung) an; GAT berechnet Softmax-Aufmerksamkeitskoeffizienten für jede Kante, sodass einflussreiche Nachbarn stärker beitragen; GraphSAGE sampelt zufällig eine Nachbarschaft fester Größe und wendet einen differenzierbaren Aggregator (Mittelwert, LSTM oder Pooling) an. Das Stapeln von L Schichten ermöglicht den Informationsfluss über L Hops, aber das Stapeln zu vieler Schichten führt zu Übersmoothing, bei dem alle Knoteneinbettungen zum selben Wert konvergieren.

4

Die endgültigen Knoteneinbettungen werden in einen aufgabenspezifischen Kopf eingespeist. Für die Knotenklassifizierung weist eine Softmax-Schicht jedem Knoten Klassenwahrscheinlichkeiten zu. Für die Link-Vorhersage bewertet ein inneres Produkt oder ein MLP die Wahrscheinlichkeit einer Kante zwischen zwei Knoteneinbettungen. Für die Graphklassifizierung aggregiert ein globales Pooling (Summe, Mittelwert oder hierarchisch) alle Knoteneinbettungen zu einem einzigen Graphen-Level-Vektor vor der Klassifizierungsschicht.

5

Die Modellleistung wird auf einem zurückgehaltenen Testdatensatz mit Metriken gemessen, die für die Aufgabe geeignet sind: Genauigkeit oder F1 für Knoten- und Graphklassifizierung, AUC-ROC für Link-Vorhersage. Da Graphdatensätze oft eine begrenzte Größe haben, sollten transduktive Auswertungen (Trainings-/Validierungs-/Testmasken auf demselben Graphen) oder induktive Aufteilungen (disjunkte Teilgraphen) dem Einsatzszenario entsprechen.

Häufige Fallstricke

  • Das Hinzufügen zu vieler GNN-Schichten verursacht Übersmoothing: Alle Knoteneinbettungen konvergieren und das Modell verliert seine Unterscheidungsfähigkeit. Halten Sie die Anzahl der Schichten bei 2–4 und überwachen Sie die Varianz der Einbettungen.
  • Das Training auf dem vollständigen Graphen ohne Mini-Batches ist für große Netzwerke speicherintensiv; verwenden Sie GraphSAGE-ähnliches Nachbarschafts-Sampling oder Graph-Partitionierung für Graphen mit mehr als einigen tausend Knoten.
  • Die Anwendung eines transduktiv trainierten GCN zur Inferenzzeit direkt auf neue, ungesehene Knoten ist falsch; verwenden Sie eine induktive Methode wie GraphSAGE, wenn Ihr Einsatz eine Generalisierung auf neue Knoten erfordert.
  • Das Ignorieren der Homophilie-Annahme bei heterophilen Graphen führt zu schlechten Ergebnissen; prüfen Sie den Assortativitätskoeffizienten des Graphen, bevor Sie eine Standard-GNN-Variante wählen.
  • Bei weniger als 20 Knoten liefert das GNN-Training unzuverlässige Repräsentationen; bevorzugen Sie in diesem Regime die konventionelle Netzwerkanalyse basierend auf Zentralitätsmaßen.

Häufig gestellte Fragen

Welche GNN-Variante sollte ich zuerst verwenden – GCN, GAT oder GraphSAGE?

GCN ist die einfachste Basislinie und funktioniert gut auf kleinen bis mittleren homophilen Graphen, bei denen alle Knoten zum Zeitpunkt des Trainings bekannt sind. GAT ist vorzuziehen, wenn die Nachbarwichtigkeit variiert und Sie interpretierbare Aufmerksamkeitsgewichte wünschen. GraphSAGE ist die richtige Wahl, wenn Sie auf Knoten verallgemeinern müssen, die während des Trainings nicht gesehen wurden, oder wenn der Graph zu groß für die Full-Batch-Verarbeitung ist.

Was ist Übersmoothing und wie vermeide ich es?

Übersmoothing tritt auf, wenn viele GNN-Schichten dazu führen, dass alle Knoteneinbettungen zu demselben Wert konvergieren, wodurch diskriminierende Informationen verloren gehen. In der Praxis sind 2–4 Schichten normalerweise optimal. Techniken wie Residualverbindungen, Jumping Knowledge Networks und DropEdge können helfen, wenn tiefere Architekturen erforderlich sind.

Benötigen GNNs für alle Knoten gelabelte Daten?

Nein. GCN und GAT werden häufig in semi-überwachten Settings verwendet, in denen nur ein kleiner Bruchteil der Knoten Labels trägt; die Graphenstruktur propagiert Informationen von gelabelten zu ungelabelten Knoten. GraphSAGE kann je nach Aufgabe auch auf vollständig überwachte oder unüberwachte Weise trainiert werden.

Wie groß muss der Graph sein?

Eine Mindestanzahl von etwa 50 Knoten ist für ein sinnvolles GNN-Training erforderlich. Bei weniger als 20 Knoten kann das Modell keine zuverlässigen Repräsentationen lernen, und die traditionelle Analyse basierend auf Zentralitätsmaßen ist geeigneter. Für Graphen mit Millionen von Knoten sind Mini-Batch-Nachbarschafts-Sampling (wie in GraphSAGE) oder Graph-Partitionierungsmethoden erforderlich, um die Speichernutzung überschaubar zu halten.

Verwandte Methoden

Quellen

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    DOI-Referenz öffnen
    Kopiert.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    DOI-Referenz öffnen
    Kopiert.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    DOI-Referenz öffnen
    Kopiert.