Graph Neural Networks (GNNs) haben sich als Standard-Toolbox zum Lernen aus Graphendaten herausgestellt. GNNs sind in der Lage, Verbesserungen für hochwirksame Probleme in verschiedenen Bereichen wie Inhaltsempfehlung oder Wirkstoffentdeckung voranzutreiben. Im Gegensatz zu anderen Datentypen wie Bildern erfordert das Lernen aus Diagrammdaten bestimmte Methoden. Wie definiert durch Michael Bronstein:
[..] Diese Methoden basieren auf einer Form der Nachrichtenübermittlung, die es dem Knoten ermöglicht, Informationen auszutauschen.
Zur Ausführung spezifischer Aufgaben in Graphen (Knotenklassifizierung, Verbindungsvorhersage usw.) berechnet eine GNN-Schicht die Knoten- und Kantendarstellungen über die sogenannten rekursive Nachbarschaftsdiffusion (oder Nachrichtenübergabe). Nach diesem Prinzip empfängt und aggregiert jeder Graphknoten Merkmale von seinen Nachbarn, um die lokale Graphstruktur darzustellen: Verschiedene Arten von GNN-Schichten führen verschiedene Aggregationsstrategien durch.
Die einfachsten Formulierungen der GNN-Schicht, wie z. B. Graph Convolutional Networks (GCNs) oder GraphSage, führen eine isotrope Aggregation aus, bei der jeder Nachbar gleichermaßen zur Aktualisierung der Darstellung des zentralen Knotens beiträgt. In diesem Blogbeitrag wird eine Miniserie (2 Artikel) vorgestellt, die sich mit der Analyse von Graph Attention Networks (GATs) befasst und eine Anisotropieoperation in der rekursiven Nachbarschaftsdiffusion definiert. Unter Ausnutzung des Anisotropie-Paradigmas wird die Lernfähigkeit durch den Aufmerksamkeitsmechanismus verbessert, der dem Beitrag jedes Nachbarn unterschiedliche Bedeutung beimisst.
Diese Aufwärmphase basiert auf den von der Deep Graph Library gemeldeten GAT-Details Website .
Bevor wir das Verhalten der GAT-Schicht verstehen, lassen Sie uns die Mathematik hinter der von der GCN-Schicht durchgeführten Aggregation zusammenfassen.
GCN-Schicht - Aggregationsfunktion
N ist die Menge der One-Hop-Nachbarn des Knotens i. Dieser Knoten könnte auch durch Hinzufügen einer Selbstschleife zu den Nachbarn gehören.
c ist eine Normalisierungskonstante basierend auf der Graphstruktur, die eine isotrope Durchschnittsberechnung definiert.
σ ist eine Aktivierungsfunktion, die Nichtlinearität in die Transformation einführt.
W ist die Gewichtsmatrix der lernbaren Parameter, die für die Merkmalstransformation verwendet werden.
Die GAT-Schicht erweitert die grundlegende Aggregationsfunktion der GCN-Schicht und weist jeder Kante durch die Aufmerksamkeitskoeffizienten eine unterschiedliche Bedeutung zu.
GAT-Schichtgleichungen
Gleichung (1) ist eine lineare Transformation der Einbettung der unteren Schicht Hallo, und W ist seine lernbare Gewichtsmatrix. Diese Transformation trägt dazu bei, eine ausreichende Ausdruckskraft zu erreichen, um die Eingabemerkmale in hochrangige und dichte Merkmale umzuwandeln.
Gleichung (2) berechnet eine paarweise nicht normalisierte Aufmerksamkeitsbewertung zwischen zwei Nachbarn. Hier verkettet es zunächst das z Einbettungen der beiden Knoten, wobei || bezeichnet die Verkettung. Dann braucht es ein Punktprodukt einer solchen Verkettung und einen lernbaren Gewichtsvektor a. Am Ende wird eine LeakyReLU auf das Ergebnis des Punktprodukts angewendet. Die Aufmerksamkeitsbewertung gibt die Bedeutung eines Nachbarknotens im Rahmen für die Nachrichtenübermittlung an.
Gleichung (3) Wendet einen Softmax an, um die Aufmerksamkeitswerte an den eingehenden Kanten jedes Knotens zu normalisieren. Der Softmax codiert die Ausgabe des vorherigen Schritts in einer Wahrscheinlichkeitsverteilung. Infolgedessen sind die Aufmerksamkeitswerte über verschiedene Knoten hinweg viel vergleichbarer.
Gleichung (4) ähnelt der GCN-Aggregation (siehe Gleichung am Anfang des Abschnitts). Die Einbettungen von Nachbarn werden zusammengefasst und durch die Aufmerksamkeitswerte skaliert. Die Hauptfolge dieses Skalierungsprozesses besteht darin, von jedem Nachbarschaftsknoten einen anderen Beitrag zu lernen.
NumPy-Implementierung
Der erste Schritt besteht darin, die Zutaten (Matrizen) so vorzubereiten, dass sie einen einfachen Graphen darstellen und die lineare Transformation durchführen.
NumPy-Code
print('nn----- One-hot vector representation of nodes. Shape(n,n)n')
X = np.eye(5, 5)
n = X.shape[0]
np.random.shuffle(X)
print(X) print('nn----- Embedding dimensionn')
emb = 3
print(emb) print('nn----- Weight Matrix. Shape(emb, n)n')
W = np.random.uniform(-np.sqrt(1. / emb), np.sqrt(1. / emb), (emb, n))
print(W) print('nn----- Adjacency Matrix (undirected graph). Shape(n,n)n')
A = np.random.randint(2, size=(n, n))
np.fill_diagonal(A, 1) A = (A + A.T)
A[A > 1] = 1
print(A)
Die erste Matrix definiert eine One-Hot-codierte Darstellung der Knoten (Knoten 1 ist fett dargestellt). Anschließend definieren wir eine Gewichtsmatrix unter Ausnutzung der definierten Einbettungsdimension. Ich habe den 3. Spaltenvektor von hervorgehoben W denn wie Sie gleich sehen werden, definiert dieser Vektor die aktualisierte Darstellung von Knoten 1 (ein 1-Wert wird an der 3. Position initialisiert). Wir können die lineare Transformation durchführen, um ausgehend von diesen Bestandteilen eine ausreichende Ausdruckskraft für Knotenmerkmale zu erreichen. Dieser Schritt zielt darauf ab, die (One-Hot-codierten) Eingabemerkmale in eine niedrige und dichte Darstellung umzuwandeln.
Die nächste Operation besteht darin, die Selbstaufmerksamkeitskoeffizienten für jede Kante einzuführen. Wir verketten die Darstellung des Quellknotens und die Darstellung des Zielknotens zur Darstellung von Kanten. Dieser Verkettungsprozess wird durch die Adjazenzmatrix ermöglicht AHiermit werden die Beziehungen zwischen allen Knoten im Diagramm definiert.
GAT-Schicht (Gleichung 2)
NumPy-Code
# equation (2) - First part
print('nn----- Concat hidden features to represent edges. Shape(len(emb.concat(emb)), number of edges)n')
edge_coords = np.where(A==1)
h_src_nodes = z1[edge_coords[0]]
h_dst_nodes = z1[edge_coords[1]]
z2 = np.concatenate((h_src_nodes, h_dst_nodes), axis=1)
Im vorherigen Block habe ich die 4 Zeilen hervorgehoben, die die 4 mit Knoten 1 verbundenen Kanten darstellen. Die ersten 3 Elemente jeder Zeile definieren die Einbettungsdarstellung der Nachbarn von Knoten 1, während die anderen 3 Elemente jeder Zeile die Einbettungen von definieren Knoten 1 selbst (wie Sie sehen können, codiert die erste Zeile eine Selbstschleife).
Nach dieser Operation können wir die Aufmerksamkeitskoeffizienten einführen und sie mit der Kantendarstellung multiplizieren, die sich aus dem Verkettungsprozess ergibt. Schließlich wird die Leaky Relu-Funktion auf die Ausgabe dieses Produkts angewendet.
NumPy-Code
# equation (2) - Second part
print('nn----- Attention coefficients. Shape(1, len(emb.concat(emb)))n')
att = np.random.rand(1, z2.shape[1])
print(att) print('nn----- Edge representations combined with the attention coefficients. Shape(1, number of edges)n')
z2_att = z2.dot(att.T)
print(z2_att) print('nn----- Leaky Relu. Shape(1, number of edges)')
e = leaky_relu(z2_att)
print(e)
Am Ende dieses Prozesses haben wir für jede Kante des Diagramms eine andere Punktzahl erzielt. Im oberen Block habe ich die Entwicklung des mit der ersten Kante verbundenen Koeffizienten hervorgehoben. Um den Koeffizienten über verschiedene Knoten hinweg leicht vergleichbar zu machen, wird eine Softmax-Funktion auf die Beiträge aller Nachbarn für jeden Zielknoten angewendet.
Um die Bedeutung der letzten Matrix zu interpretieren, die die normalisierten Kantenwerte definiert, fassen wir den Inhalt der Adjazenzmatrix zusammen.
Wie Sie sehen können, haben wir anstelle von 1 Werten zum Definieren von Kanten den Beitrag jedes Nachbarn neu skaliert. Der letzte Schritt besteht darin, die Nachbarschaftsaggregation zu berechnen: Die Einbettungen von Nachbarn werden in den Zielknoten integriert, skaliert durch die Aufmerksamkeitswerte.
In dem zukünftigen Artikel werde ich die Mechanismen hinter der Multi-Head-GAT-Schicht beschreiben und einige Anwendungen für die Link-Vorhersage-Aufgabe sehen.
Bibliographie
Die laufende Version des Codes ist im Folgenden verfügbar Notizbuch. Dort finden Sie auch eine DGL-Implementierung, mit der Sie die Richtigkeit der Implementierung überprüfen können.
Das Originalpapier über Graph Attention Networks von Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò und Yoshua Bengiois ist am erhältlich arXiv.
Für eine ausführliche Erklärung des Themas schlage ich auch das Video von vor Alexa Gordić.
Dieser Artikel wurde ursprünglich veröffentlicht am Auf dem Weg zu Data Science und mit Genehmigung des Autors erneut auf TOPBOTS veröffentlicht.
Genießen Sie diesen Artikel? Melden Sie sich für weitere AI-Updates an.
Wir werden Sie informieren, wenn wir mehr technische Ausbildung veröffentlichen.
