Graph Neural Networks anhand von CNNs verstehen

Ein Graph ist einfach eine Menge so genannter Ecken oder Knoten, die wir typischerweise als Punkte darstellen, zusammen mit einer Menge von Paaren von Knoten, genannt Kanten, die wir als Pfeile darstellen, welche die Knoten verbinden. (Die genauen Definitionen und die Terminologie variieren ziemlich stark, aber das soll hier keine Verwirrung stiften). Es ist auch sehr üblich, die Eckpunkte und Kanten mit Beschriftungen zu versehen.

Graphen sind ein grundlegendes Konzept in der Informatik und Kombinatorik, aber sie werden auch in praktischen Anwendungen häufig verwendet, um jede Art von Netzwerk von Entitäten darzustellen, wie z. B.

• soziale Netzwerke, in denen Knoten Personen darstellen und Kanten eine Freundschaftsbeziehung repräsentieren können;

• Webseiten und Hyperlinks zwischen ihnen, oder akademische Arbeiten und Zitate;

• Teilschritte eines komplexen Prozesses und Abhängigkeitsbeziehungen zwischen ihnen. 

Ein schönes Einführungsbuch über Graphen und Netzwerke ist "Linked: The New Science of Networks" von Albert-László Barabási.

Graph Neural Networks sind eine Kategorie von Modellen des maschinellen Lernens, die darauf zugeschnitten sind, aus Daten zu lernen, die in Graphform strukturiert sind.

Während es oft möglich ist, einen Graphen in eine Form zu bringen, die als Eingabe für andere ML-Methoden dienen kann, haben GNNs den Vorteil, direkt mit Graphdaten zu arbeiten und daher ein höheres Potenzial, feine Details von und über die Topologie des Netzwerks zu lernen.

Analogie zu CNNs

Um zu verstehen, wie GNNs funktionieren, und um einige der feineren Details der Geschichte schätzen zu können, lassen Sie uns eine Analogie zu den beliebten CNNs herstellen, die bei Computer-Vision-Aufgaben allgegenwärtig sind. Ein einzelnes Concolutional Layer ist einfach eine Prozedur, die für jedes Pixel $$p$$ eines Bildes eine Ausgabe oder ein Label $$\mathrm{out}(p)$$ berechnet, basierend auf den Eingaben oder Attributen $$\mathrm{in}(p)$$ des betreffenden Pixels und seiner unmittelbaren Nachbarn.

Betrachten wir nun dieses einzelne Convolutional Layer auf eine etwas seltsame Weise. Stellen wir uns ein kleines 3 × 3-Gitter in unserem Bild als einen kleinen Graphen vor; jedes Pixel wird durch einen Knoten repräsentiert, und die Tatsache, dass dieses Pixel 8 unmittelbare Nachbarn hat, wird durch Kanten des Graphen dargestellt.

Das gesamte Bild würde dann durch einen riesigen Graphen dargestellt, bei dem jeder Knoten 8 eingehende und 8 ausgehende Kanten hat, die jeweils mit einer Kardinalrichtung beschriftet sind. (Wir werden uns nicht um die Pixel in der Nähe des Bildrandes kümmern, für die die Situation natürlich etwas anders ist.)

Damit können wir uns nun ein Convolutional Layer wie folgt als Verfahren vorstellen:

• Jeder Knoten unseres Graphen (der ein Pixel darstellt) beginnt mit einigen Attributen. Um die Vorstellungen zu fixieren, nehmen wir an, dass dies die erste Schicht in einem tieferen neuronalen Netz ist und die Attribute des Knotens nur die RGB-Werte des Pixels sind.

• Jeder Knoten empfängt eine "Nachricht" von den mit ihm verbundenen Knoten (die in diesem Fall nur die benachbarten Pixel sind), also insgesamt 8 Nachrichten. Der Inhalt der Nachricht ist wiederum nur der RGB-Wert des Pixels, das durch den Ursprung der betreffenden Kante repräsentiert wird - andere Informationen, die es weitergeben könnte, "kennt" das Pixel ohnehin nicht.

• Für jeden Knoten wird eine feste Formel verwendet, um einen Ausgabewert in Bezug auf die Attribute des Knotens und den Inhalt der von ihm empfangenen Nachrichten zu berechnen.

Lassen Sie uns die Rolle der Kantenbeschriftungen in den obigen Ausführungen klären. Man kann sie sich als die "Umschlag" der Nachricht vorstellen. Wenn ein Pixel eine Nachricht empfängt, lernt es über den RGB-Wert eines Nachbarn in einer bestimmten Richtung. Wenn wir die Kanten nicht mit den Kardinalrichtungen beschriften würden, würde der Zielknoten nur erfahren, dass irgendein Nachbar den übergebenen RGB-Wert hat. Infolgedessen könnte die Ausgabe eines bestimmten Pixels nur in Bezug auf die (ungeordnete) Menge der RGB-Werte seiner Nachbarn berechnet werden - was, wie wir wissen, nicht die Funktionsweise von CNNs ist.

Eine Formel für das Convolutional Layer, geschrieben in graphischem Gewand, lautet wie folgt:

Dabei bezeichnen $$p$$ und $$q$$ Knoten, $$D \in \{N, S, W, E \dots \}$$ eine der 8 Kardinalrichtungen, $$w_D$$ ist ein Gewicht des Convolutional Layers (der Richtung $$D$$ zugeordnet), und das tiefgestellte Summenzeichen zeigt an, dass die Summe über alle mit $$p$$ verbundenen Knoten $$q$$ geht, wobei $$D$$ die sie verbindende Kante bezeichnet. Außerdem gibt es ein zusätzliches Gewicht $$w_O$$, das mit dem Eingangswert von $$p$$ selbst verbunden ist. Schließlich bezeichnet $$\sigma$$ eine Aktivierungsfunktion.

Graph neural networks

Ein Graph Neural Network ist eine Verallgemeinerung der Idee des obigen Unterabschnitts, bei der wir einfach einige der besonderen Merkmale des Bildbeispiels entfernen:  

• Ein Knoten muss nicht eine feste Anzahl von eingehenden oder ausgehenden Kanten haben.

• Es können mehrere Kanten einer bestimmten Art (oder auch gar keine) einen bestimmten Knoten erreichen.

• Einige GNN-Architekturen erlauben es, sowohl Kanten als auch Knoten Attribute zuzuweisen und die Knoten zu beschriften.

Eine Formel für ein grundlegendes GNN-Layer wäre  

wobei wir neben der in der vorherigen Formel verwendeten Notation auch einen Normalisierungsfaktor eingefügt haben, der in Bezug auf die Grade $$d_p$$, $$d_q$$ der Knoten berechnet wird, d.h. die Gesamtzahl der einfallenden Kanten. Wir haben die Attribute $$\mathrm{in}(p)$$ des Knotens $$p$$ selbst nicht explizit in die Formel für $$\mathrm{out}(p)$$ aufgenommen, aber dies kann durch Hinzufügen spezieller Kanten, z. B. mit dem Label $$O$$, die jeden Knoten mit sich selbst verbinden, erfolgen.

Dies ist natürlich nur ein erster Versuch, ein GNN-Layer zu definieren. Es sind viele Variationen und Verfeinerungen möglich, und es gibt auch Graph-Versionen von rekurrenten neuronalen Netzen, Gated Recurrent Units und Self-Attention-Layers. Beachten Sie auch, dass wir hier nur ein einzelnes GNN-Layer besprochen haben. Wie bei CNNs und Deep Learning im Allgemeinen beginnt die Magie, wenn wir mehrere dieser Schichten stapeln.

Gebrauchsfertige Implementierungen verschiedener GNN-Schichten finden sich in Bibliotheken wie dem PyTorch Geometric-Paket, DGL und Spektral. 

Zu den Klassen von Aufgaben, die durch GNNs gelöst werden können, gehören:

• Vorhersage von Knotenbeschriftungen: Hier geht es darum, eine Vorhersage über jeden Knoten eines Graphen zu treffen. Wir möchten zum Beispiel entscheiden, welche Knoten eines Verkehrsnetzes die Hauptknotenpunkte sind.

• Graph-Klassifizierung: Hier geht es darum, einem ganzen Graphen ein Label zuzuordnen. Ein Beispiel: Aus dem Graphen eines Moleküls, der die einzelnen Atome und die Bindungen zwischen ihnen darstellt, können wir die Eigenschaften des Moleküls vorhersagen. Ein anderes Beispiel: Klassifizierung von Industriekomponenten in verschiedene Kategorien anhand von Informationen über ihre Unterkomponenten und die Art und Weise, wie diese zusammengesetzt sind.

• Kantnenvorhersage: Dies bezieht sich auf das Auffinden potenzieller oder fehlender Kanten in einem Graphen. Beispiele sind Freundesempfehlungen in sozialen Netzwerken, Protein-Protein-Interaktionsvorhersagen und die Vervollständigung von Wissensgraphen.

Bei dida haben wir GNNs erfolgreich in NLP-Aufgaben eingesetzt, bei denen die physikalische Anordnung von Wörtern auf der Seite relevant ist, z. B. bei der Erkennung und dem Verständnis von Tabellen. Hier wird eine Seite eines Dokuments durch einen Graphen beschrieben, dessen Knoten Wörter, Zeilen oder Spalten von Text etc. sind. Die Attribute der Knoten können sowohl Informationen über ihren textuellen Inhalt als auch Informationen über ihre Positionierung enthalten. Die Kanten des Graphen schließlich stellen verschiedene Beziehungen zwischen diesen Seitenelementen dar, z. B. dass zwei Wörter benachbart sind oder ein Wort zu einer Zeile oder Spalte gehört.

Im Vergleich zu traditionelleren ML-Methoden haben wir herausgefunden, dass tiefe GNNs hervorragende Ergebnisse beim Verstehen von Tabellen liefern, ohne dass ein umfangreiches Feature-Engineering oder Ad-hoc-Segmentierungsalgorithmen für Tabellen erforderlich sind. Dies ist besonders wichtig, wenn man mit heterogenen Dokumentensammlungen mit viel Variabilität in der Formatierung arbeitet.