In diesem Beitrag widmen wir uns zwei Themen, die in letzter Zeit häufig die Medien dominiert haben: Dies sind einerseits Neuronale Netze und Künstliche Intelligenz (KI), andererseits soziale Medien, wie Facebook, Twitter und Co.
Graph-strukturierte Daten mit neuronalen Netzen verarbeiten
Möchte man soziale Netzwerke mathematisch darstellen, so benutzt man häufig Graphen. Graphen sind ein Teilgebiet der diskreten Mathematik und theoretischen Informatik und bieten vielfältige Möglichkeiten verschiedene Daten darzustellen. Zum Beispiel können mit ihnen neben sozialen Netzen auch Telekommunikationsnetzwerke, chemische Verbindungen, wie Moleküle, oder Vernetzungen im Gehirn abgebildet werden. Ihre Einsatzmöglichkeiten sind also vielfältig.
Um Graph-strukturierte Daten mit Neuronalen Netzen zu verarbeiten, benötigen wir ein auf diese Daten angepasstes Neuronales Netz. Das Graph Attention Network (GAT) basiert auf Grundlagen des Graph Neural Networks (GNN) sowie dessen Weiterentwicklungen, wie beispielsweise dem Graph Convolutional Network (GCN). Dabei wird versucht Informationen über die einzelnen Knoten innerhalb des Graphen zu gewinnen und so ihre Eigenschaften zu erlernen, um später die Knoten automatisch kategorisieren zu können. Hierbei fallen die Eigenschaften aller Knoten in einer Nachbarschaft gleichwertig ins Gewicht. Dies ist jedoch nicht immer sinnvoll, da manche Knoten wichtiger in einer Beziehung sein können als andere. Um dies darzustellen, verwendet das Graph Attention Network die so genannte Attentional-Layer. Doch bevor wir zu der Theorie hinter dem Netz kommen, schauen wir uns zunächst das Datenset an, auf dem wir lernen möchten.
Ein Blick auf die Trainingsdatensätze
Soziale Netzwerke, wie Facebook und Twitter, bestehen aus gigantischen Datenmengen und wachsen täglich weiter. Die persönlichen Daten der Nutzerinnen und Nutzer sind geschützt und können nicht ohne weiteres verwendet werden. Deshalb werden wir stellvertretend einen kleineren Datensatz betrachten, um die Funktionsweise des GAT zu erläutern. Hierfür wählen wir die Publikationsnetzwerke Cora und CiteSeer. Beide Datensätze werden häufig als Beispiele in der Literatur verwendet und bieten so die Möglichkeit die erzielten Ergebnisse untereinander zu vergleichen.
Die Datensätze bestehen jeweils aus einem Graphen, der ein Publikationsnetzwerk repräsentiert. Die Knoten des Graphen stehen für die Publikationen und die (ungerichteten) Kanten für die Zitierungen der jeweiligen Artikel untereinander. Jeder Knoten besitzt zusätzlich noch einen Feature Vektor, der beschreibt, ob ein Wort aus einem gegebenen Wörterbuch in der Publikation enthalten ist (1) oder nicht (0). Des Weiteren werden die Knoten einer jeweiligen Klasse zugeordnet. Diese Klasse entspricht den verschiedenen Themengebieten der Veröffentlichungen. Es ergibt sich folgende Tabelle:
Alle dargestellten Kanten aus Abbildung 1 haben eine gleichstarke Verbindung zueinander. Dies bildet die Realität jedoch nicht immer zutreffend ab, weshalb wir wichtigen Kanten eine stärkere Gewichtung geben möchten und unwichtigen eine schwächere. Dies führt uns direkt zum Neuronalen Netz.
Das Graph Attention Network
Um die oben beschriebene variable Gewichtung in Zahlen auszudrücken, benutzen wir die so genannte Self-Attention Methode. Diese wird auch im Natural Language Processing (NLP) verwendet, also in der maschinellen Verarbeitung natürlicher Sprache, und beruht auf einem normalisierten Attention-Coefficient. Die Eingabe in das Graph Attention Network sind die verschiedenen Feature Vektoren. Die Ausgabe sind so genannte höhere Feature Vektoren, in unserem Fall die korrespondierenden Klassen der Knoten. Der Attention-Coefficient ergibt sich als Produkt aus den Feature Vektoren und der Gewichtsmatrix des Neuronalen Netzes. Um ihn vergleichbar innerhalb einer Nachbarschaft zu machen, muss der Koeffizient noch normiert werden.
Der beim Berechnen der Ausgabe des Netzes, dem Forward Pass, entstandene normalisierte Attention-Coefficient gibt uns nun einen numerischen Wert für die Wichtigkeit einer Knoten-Beziehung. Dieser Wert kann jedoch von Berechnung zu Berechnung variieren. Deshalb wollen wir ihn mehrmals berechnen, um eine möglichst genaue Schätzung zu erhalten. Die Anzahl der Berechnungen wird Attention-Heads genannt. Die Ergebnisse eines einzelnen Heads werden miteinander verbunden, wenn wir uns in einer verdeckten Schicht des Netzes befinden. Dies müssen wir bei der Größe der Hidden-Layer (der verdeckten Neuronen-Schicht, die beim Lernen nicht beobachtbar ist,) berücksichtigen. Die Anzahl der gewünschten Neuronen muss dann mit der Anzahl der Attention-Heads multipliziert werden. In der finalen Output-Layer bilden wir den Durchschnitt der Ergebnisse der Attention-Heads. Da der Self-Attention Mechanismus keine Informationen über die Struktur des Graphen selbst benötigt, kann das GAT auch für induktive Datensets verwendet werden, die während des Trainings unbeobachtet bleiben. Der Einfachheit halber beschränken wir uns in diesem Beispiel aber auf transduktive Datensets, die während des Trainings beobachtbar sind.
Training des Graph Attention Networks
Das Netz muss jetzt noch trainiert werden. Würden wir das Netz nicht trainieren, so würden dessen Ausgaben wie in Abbildung 2 aussehen. Die Knoten würden willkürlich und ohne eine erkennbare Struktur einer der Klassen zugeordnet werden.
Damit ein Auswendiglernen der Trainingsdaten beim Trainieren verhindert wird, benutzen wir einen Early-Stopping Mechanismus. Dieser sorgt dafür, dass das Training beendet wird, falls das bisher besterreichte Validierungs-Ergebnis in einem vorgegebenen Zeitraum nicht übertroffen wurde. Ist das Netz einmal trainiert, so erhalten wir beim Testen des Netzes die in Abbildung 3 dargestellte Ausgabe.
Die verschiedenen Knoten wurden nun größtenteils richtig ihrer entsprechenden Klasse zugeordnet. Die durchschnittliche Genauigkeit der Klassifizierung des GATs bei 100 Durchläufen auf den verschiedenen Datensätzen ist in folgender Tabelle dargestellt.
Zu erkennen ist, dass unser Modell auf dem Cora Datensatz ein besseres Ergebnis erzielt als bei CiteSeer. Ein Grund hierfür ist unter anderem, dass CiteSeer Knoten enthält, die keine Nachbarn besitzen, wohingegen Cora nur Knoten mit einem Grad ≥ 1 besitzt.
Aussicht und Fazit
Wir haben gezeigt, wie ein Graph Attention Network aufgebaut ist und angewendet werden kann. Dabei haben wir uns den normierten Attention-Coefficient zu Nutze gemacht, da dieser gezielt wichtige Knoten-Verbindungen in einem Graphen erlernen kann und so bessere Ergebnisse als herkömmliche Methoden erzielt. Beispielhaft wurde das GAT auf den Datensätzen Cora sowie CiteSeer trainiert und die Ergebnisse präsentiert. Da GATs auf induktiven Datensätzen angewendet werden können, eignen sie sich auch zur Analyse von großen Graphen, die während des Trainings unbeobachtet bleiben, und beispielsweise in sozialen Netzwerken eingesetzt werden. Aus diesem Grund ist das Anwendungsgebiet für GATs besonders weitreichend, was sie neben der Forschung auch in der Industrie zu einem wichtigen Machine Learning Werkzeug macht.
