Eine freundliche Einführung in Graph Neural Networks

 (distill.pub)
1 Punkte von GN⁺ 2024-12-21 | 1 Kommentare | Auf WhatsApp teilen
  • Graph Neural Networks (GNNs) sind Modelle, die Knoten, Kanten, globalen Kontext und Verbindungsstruktur gemeinsam behandeln. Sie eignen sich für Daten, bei denen derselbe Graph unabhängig von der Reihenfolge der Knoten dieselbe Bedeutung haben soll.
  • Moleküle, soziale Netzwerke und Zitationsnetzwerke lassen sich ebenso als Graphen betrachten wie Pixelgitter in Bildern und Text-Token-Sequenzen. Graphen haben jedoch sehr unterschiedliche Größen und Konnektivitäten und sind daher schwer wie gewöhnliche Array-Eingaben zu behandeln.
  • Vorhersageprobleme mit GNNs lassen sich in Graph-, Knoten- und Kantenebene unterteilen. Modelle derselben Familie können die Eingabestruktur bewahren und Labels auf unterschiedlichen Ebenen vorhersagen.
  • Die zentrale Operation ist Message Passing: Informationen benachbarter Knoten und Kanten werden gesammelt und zur Aktualisierung genutzt. Stapelt man mehrere Layer, fließen auch Informationen weiter entfernter k-hop-Nachbarn in die Repräsentation ein.
  • Die tatsächliche Leistung hängt von Layer-Tiefe, Embedding-Dimension, Aggregationsfunktion und dem Nachrichtenfluss zwischen Knoten-, Kanten- und globalen Repräsentationen ab. Mehr Parameter oder größere Tiefe liefern nicht immer das beste Ergebnis.

Graphdaten und Grundkonzepte von GNNs

  • Ein Graph besteht aus Knoten (nodes) als Entitäten und Kanten (edges) als Beziehungen zwischen Knoten.
  • Knoten, Kanten und der gesamte Graph können jeweils zusätzliche Informationen speichern.
    • Knoten können Merkmale wie Atomart, RGB-Werte von Pixeln oder Dokument-Embeddings enthalten.
    • Kanten können Informationen wie Bindungstypen oder Beziehungstypen enthalten.
    • Der gesamte Graph kann einen globalen Kontext besitzen.
  • Kanten können als gerichtete Kanten (directed edges) oder ungerichtete Kanten (undirected edges) dargestellt werden.
  • Ein GNN transformiert Knoten, Kanten und globalen Kontext auf lernbare Weise und muss dieselbe Graphstruktur auch bei geänderter Knotenreihenfolge mit derselben Bedeutung verarbeiten.

Daten, die sich als Graphen darstellen lassen

  • Bilder werden normalerweise als Arrays wie 244×244×3 dargestellt, können aber auch als reguläre Graphen betrachtet werden, bei denen jedes Pixel ein Knoten ist und benachbarte Pixel durch Kanten verbunden sind.
    • Pixel, die nicht am Rand liegen, haben genau 8 Nachbarn.
    • In jedem Knoten ist ein dreidimensionaler Vektor mit RGB-Werten gespeichert.
  • Text lässt sich als gerichteter Graph auffassen, bei dem Zeichen, Wörter oder Token Knoten sind und Kanten zum nächsten Token zeigen.
    • Das knüpft an die Token-Sequenz-Repräsentation von RNNs an.
    • Ein Transformer kann als vollständig verbundener Graph betrachtet werden, der Beziehungen zwischen Token lernt.
  • Bilder und Text haben sehr regelmäßige Strukturen, sodass eine Graphdarstellung redundant sein kann.
    • Die Adjazenzmatrix eines Bildes hat wegen der Gitterverbindungen eine bandförmige Struktur.
    • Die Adjazenzmatrix von Text liegt nahe an einer diagonalen Struktur, da jedes Wort nur mit dem vorherigen und dem nächsten Wort verbunden ist.
  • Moleküle lassen sich gut als Graphen darstellen, bei denen Atome Knoten und kovalente Bindungen Kanten sind.
    • Abstände unterscheiden sich je nach Atompaar und Bindungstyp, etwa Einfach- oder Doppelbindung.
  • Soziale Netzwerke modellieren Menschen, Institutionen oder Organisationen als Knoten und Beziehungen als Kanten.
  • Zitationsnetzwerke stellen Paper als Knoten dar und die Beziehung, dass ein Paper ein anderes zitiert, als gerichtete Kante.
    • Jeder Paper-Knoten kann zusätzliche Informationen wie Wort-Embeddings des Abstracts enthalten.
  • Auch Szenenobjekte in Computer Vision, Machine-Learning-Modelle, Programmcode und mathematische Gleichungen können als Graphen dargestellt werden, bei denen Variablen oder Objekte Knoten und Operationen oder Beziehungen Kanten sind.

Drei Ebenen von Graph-Vorhersageproblemen

  • Eine Graph-level Task sagt eine einzelne Eigenschaft des gesamten Graphen voraus.
    • Beispiele sind die Vorhersage, welchen Geruch ein Molekülgraph hat oder ob er an einen krankheitsrelevanten Rezeptor bindet.
    • Wie bei Bildklassifikation oder Sentiment-Analyse von Sätzen erhält die gesamte Eingabe ein Label.
  • Eine Node-level Task sagt Eigenschaften oder Rollen einzelner Knoten im Graphen voraus.
    • Der Zach’s-karate-club-Datensatz ist ein Problem, bei dem persönliche Knoten danach klassifiziert werden, welchem der beiden Clubs sie nach einem politischen Konflikt treu bleiben.
    • Das ähnelt der Label-Vergabe für jede Pixelrolle in der Bildsegmentierung oder der Vorhersage der Wortart jedes Wortes in einem Satz.
  • Eine Edge-level Task sagt Eigenschaften oder die Existenz von Kanten voraus.
    • Ein Beispiel ist die Szenenverständnis-Aufgabe in Bildern, bei der Objekte Knoten sind und vorhergesagt wird, ob zwischen Objekten Beziehungen bestehen.
    • Man kann zunächst alle Knotenpaare vollständig verbinden und dann anhand der Vorhersagen Kanten entfernen, um einen dünn besetzten Graphen zu erzeugen.
  • Graphgenerierung und Erklärungen für Graphvorhersagen gehören ebenfalls zu verwandten Forschungsgebieten.

Schwierigkeiten bei der Nutzung von Graphen als neuronale Eingabe

  • Gängige Machine-Learning-Modelle sind auf rechteckige oder gitterförmige Array-Eingaben ausgelegt, sodass sich die Verbindungsstruktur eines Graphen nur schwer direkt einspeisen lässt.
  • Ein Graph kann bis zu vier Arten von Informationen enthalten:
    • Knoten
    • Kanten
    • globaler Kontext
    • Konnektivität
  • Knoten, Kanten und globaler Kontext lassen sich als Merkmalsmatrizen darstellen, die Darstellung der Konnektivität ist jedoch schwieriger.
  • Eine Adjazenzmatrix ist leicht zu tensorisieren, hat aber Grenzen.
    • Graphen können Millionen von Knoten haben.
    • Die Zahl der Kanten pro Knoten kann stark variieren.
    • Adjazenzmatrizen werden sehr dünn besetzt und sind dadurch wenig speichereffizient.
    • Dieselbe Graphkonnektivität kann durch mehrere Adjazenzmatrizen dargestellt werden, sodass nicht garantiert ist, dass ein neuronales Netz immer dasselbe Ergebnis liefert.
  • Adjazenzlisten eignen sich besser für dünn besetzte Graphen.
    • Die Information, dass eine Kante e_k die Knoten n_i und n_j verbindet, wird als Tupel (i, j) gespeichert.
    • Statt der O(n_nodes^2)-Darstellung einer Adjazenzmatrix ist eine O(n_edges)-Darstellung proportional zur Zahl der Kanten möglich.
  • In tatsächlichen Tensorrepräsentationen sind Knoten-, Kanten- und globale Werte keine Skalare, sondern Vektoren.
    • Der Knotentensor hat nicht die Form [n_nodes], sondern [n_nodes, node_dim].

GNN-Layer und Pooling

  • Das einfachste GNN nutzt die Graphkonnektivität noch nicht, sondern wendet auf Knoten, Kanten und globalen Kontext jeweils separate MLPs an, um neue Embeddings zu lernen.
    • Jeder Knotenvektor wird auf dieselbe Weise aktualisiert.
    • Auch jeder Kantenvektor wird aktualisiert.
    • Der globale Kontextvektor wird ebenfalls zu einem Embedding aktualisiert.
  • Ein GNN verändert die Konnektivität des Eingabegraphen nicht.
    • Der Ausgabegraph behält dieselbe Adjazenzliste und dieselbe Anzahl von Merkmalsvektoren.
    • Was sich ändert, sind die Embeddings von Knoten, Kanten und globalem Kontext.
  • Für Vorhersagen wird Pooling verwendet.
    • Die Embeddings der zu sammelnden Elemente werden per gather in einer Matrix zusammengeführt.
    • Die gesammelten Embeddings werden üblicherweise mit einer Operation wie sum aggregiert.
  • Wenn bei Knotenvorhersagen bereits Knoteninformationen vorhanden sind, kann auf jedes Knoten-Embedding ein linearer Klassifikator angewendet werden.
  • Wenn die für Knotenvorhersagen benötigte Information nur in Kanten vorhanden ist, muss die Kanteninformation per Pooling an Knoten weitergegeben werden.
  • Wenn die für Kantenvorhersagen benötigte Information nur in Knoten vorhanden ist, werden Knoteninformationen zur Kante hin gesammelt und für die Vorhersage genutzt.
  • Bei Vorhersagen für den gesamten Graphen werden alle Knoten- oder Kanteninformationen zu einer globalen Repräsentation aggregiert.
    • Das spielt eine ähnliche Rolle wie Global Average Pooling in CNNs.
    • Beispiele sind die Vorhersage von Molekültoxizität oder eines bestimmten Geruchs.

Verbindungsstruktur mit Message Passing nutzen

  • Ein einfaches GNN nutzt die Graphkonnektivität nicht innerhalb des Layers, sondern nur beim Pooling unmittelbar vor der Vorhersage.
  • Stärkere GNNs führen im Layer Message Passing aus und berücksichtigen so die Verbindungsstruktur bei der Aktualisierung der Embeddings.
  • Message Passing funktioniert in drei Schritten:
    • Jeder Knoten sammelt Embeddings oder Messages benachbarter Knoten.
    • Messages werden mit einer Aggregationsfunktion wie sum aggregiert.
    • Die gesammelten Messages werden durch eine lernbare Aktualisierungsfunktion geleitet.
  • Message Passing ähnelt einer Standard-Convolution.
    • In Bildern sammelt ein Pixel Informationen einer festen Zahl benachbarter Pixel.
    • In Graphen sammelt ein Knoten Informationen einer variablen Zahl benachbarter Knoten.
  • Stapelt man mehrere GNN-Layer, werden Informationen weiter entfernter Knoten berücksichtigt.
    • Nach 3 Layern kann ein Knoten Informationen von Knoten enthalten, die 3 Schritte entfernt sind.
  • Message Passing kann nicht nur zwischen Knoten, sondern auch zwischen Kanten sowie zwischen Knoten und Kanten erfolgen.

Kantenrepräsentationen und globale Repräsentationen

  • Datensätze enthalten nicht immer Informationen zu Knoten, Kanten und globalem Kontext zugleich.
  • Wenn nur Kanteninformationen vorhanden sind und Knotenvorhersagen benötigt werden, kann die Kanteninformation per Pooling an Knoten weitergegeben werden.
  • Knoten- und Kanteninformationen können unterschiedliche Größen oder Formen haben; die Art ihrer Kombination ist daher eine Designentscheidung.
    • Man kann eine lineare Abbildung vom Kantenraum in den Knotenraum oder umgekehrt lernen.
    • Man kann beide Repräsentationen aneinanderhängen und in eine Aktualisierungsfunktion geben.
  • Welche Grapheigenschaften in welcher Reihenfolge aktualisiert werden, ist Teil des GNN-Designs.
    • Man kann zuerst Knoten und danach Kanten aktualisieren.
    • Man kann zuerst Kanten und danach Knoten aktualisieren.
    • Auch ein Weave-Ansatz ist möglich, der Node-to-Node-, Edge-to-Edge-, Node-to-Edge- und Edge-to-Node-Repräsentationen kombiniert.
  • Knoten, die weit voneinander entfernt sind, können selbst nach mehrfachem Message Passing Schwierigkeiten haben, effizient Informationen auszutauschen.
    • Bei k Layern breitet sich Information höchstens über k Schritte aus.
  • Die globale Repräsentation U kann wie ein Master Node oder Kontextvektor wirken, der mit allen Knoten und Kanten verbunden ist.
    • Sie dient als Brücke für den Informationstransfer zwischen weit entfernten Knoten und Kanten.
    • Sie kann eine reichhaltigere Repräsentation des gesamten Graphen erzeugen.
  • Neue Knoten-Embeddings können auf Basis benachbarter Knoten, verbundener Kanten, globaler Informationen usw. konditioniert werden, indem man diese aneinanderhängt.
    • Auch Addition nach einer linearen Abbildung oder feature-wise modulation ist möglich.

GNN Playground und Beispiel zur Vorhersage von Molekülgerüchen

  • GNN Playground behandelt ein Graph-level-Vorhersageproblem für kleine Molekülgraphen.
  • Die Daten stammen aus dem Leffingwell Odor Dataset und enthalten Moleküle sowie Labels zur Geruchswahrnehmung.
  • Im Experiment wird klassifiziert, ob ein Molekülgraph einen „pungent“-Geruch hat, als einzelnes binäres Label.
    • Pungent bedeutet einen starken, hervorstechenden Geruch.
    • Beispiele sind Knoblauch und Senf, die Allylalkohol enthalten können, sowie Piperiton, das in Bonbons mit Pfefferminzgeschmack verwendet wird.
  • Moleküle werden mit Atomen als Knoten und Bindungen als Kanten dargestellt.
    • Knoten enthalten die Identität von Carbon-, Nitrogen-, Oxygen- und Fluorine-Atomen als One-hot-Encoding.
    • Kanten enthalten Bindungstypen single, double, triple und aromatic als One-hot-Encoding.
  • Das Modell-Template besteht aus sequenziellen GNN-Layern, gefolgt von einem linearen Modell mit Sigmoid-Aktivierung.
  • Die Designoptionen werden über vier Achsen gesteuert:
    • Anzahl der GNN-Layer, also die Tiefe
    • Embedding-Dimension jeder Eigenschaft
    • Aggregationsfunktion des Poolings: max, mean, sum
    • welche Eigenschaften unter Knoten-, Kanten- und globalen Repräsentationen aktualisiert werden und Message Passing durchführen
  • Der im Browser laufende Playground basiert auf tfjs.
  • Hochdimensionale Graph-Embeddings werden per PCA auf 2D reduziert, um Repräsentationen rund um die Entscheidungsgrenze zu visualisieren.

In Experimenten beobachtete GNN-Designtrends

  • Die Leistung hängt von den Daten, der Art der Graphkonstruktion und der Feature-Darstellung ab.
  • Eine größere Parameterzahl korrelierte mit der Leistung, doch GNNs konnten auch mit wenigen Parametern leistungsstarke Modelle finden.
    • Schon bei etwa 3k Parametern wurden leistungsstarke Modelle gefunden.
  • Höhere Embedding-Dimensionen tendierten zu besserer Durchschnittsleistung und besserer Untergrenze, doch die besten Modelle traten auch bei kleinen Dimensionen auf.
  • Mehr Layer tendierten zu höherer Durchschnittsleistung, doch das beste Modell hatte nicht 3 oder 4 Layer, sondern 2 Layer.
    • Bei 4 Layern sank die Leistungsuntergrenze.
    • Mehr Layer übertragen Information weiter, bergen aber das Risiko, dass Knotenrepräsentationen durch wiederholte Iterationen verwässert werden.
  • Bei den Aggregationsfunktionen wirkte sum in der Durchschnittsleistung minimal besser, doch auch max und mean konnten gleich gute Modelle erzeugen.
  • Je mehr Nachrichtenübertragung zwischen Knoten-, Kanten- und globalen Eigenschaften stattfand, desto besser tendierte die durchschnittliche Modellleistung zu sein.
    • Da die Aufgabe stark auf die globale Repräsentation ausgerichtet war, tendierte explizites Lernen globaler Eigenschaften zu besserer Leistung.
    • Knotenrepräsentationen wirkten nützlicher als Kantenrepräsentationen, weil mehr Information in den Knoteneigenschaften enthalten war.

Komplexere Graphen und Batch-Training

  • Das Message-Passing-Framework kann auch auf komplexere Graphstrukturen angewendet werden.
  • In einem Multigraph kann dasselbe Knotenpaar mehrere Arten von Kanten teilen.
    • In sozialen Netzwerken können Beziehungstypen wie acquaintance, friend und family als Kantentypen verwendet werden.
    • Für jeden Kantentyp kann es einen eigenen Message-Passing-Schritt geben.
  • In einem Nested Graph kann ein einzelner Knoten wiederum einen Graphen darstellen.
    • In Molekülnetzwerken kann ein Knoten ein Molekül darstellen und eine Kante eine Reaktion, die ein Molekül in ein anderes umwandelt.
    • Molekül-Level-GNNs und Reaktionsnetzwerk-Level-GNNs können abwechselnd trainiert werden.
  • In einem Hypergraph kann eine Kante nicht nur zwei, sondern mehrere Knoten verbinden.
    • Man kann Knotengemeinschaften identifizieren und Hyper-Edges setzen, die mit einer ganzen Community verbunden sind.
  • Da Graphen keine feste Zahl von Knoten und Kanten haben, ist gewöhnliches Mini-Batch-Training mit fester Größe schwierig.
  • Der Kern von Batch-Training für Graphen ist die Erstellung von Subgraphen, die wichtige Eigenschaften des großen Graphen bewahren.
    • In citation networks kann Subgraph-Sampling naheliegend sein.
    • Bei Molekülen kann ein Subgraph ein neues, kleineres Molekül bedeuten und damit ein starker Eingriff sein.
  • Graph-Sampling ist besonders wichtig, wenn ein großer Graph nicht in den Speicher passt.
    • Architekturen und Trainingsstrategien wie Cluster-GCN und GraphSaint hängen damit zusammen.

Induktive Biases für Graphen

  • Modelle können bessere Vorhersageleistung, kürzere Trainingszeit, weniger Parameter und bessere Generalisierung zeigen, wenn sie so entworfen sind, dass sie Symmetrien und Regularitäten der Daten nutzen.
  • Bildmodelle nutzen translation-invariante Convolutions, um die Eigenschaft auszuschöpfen, dass ein Objekt dasselbe Objekt bleibt, egal wo es im Bild erscheint.
  • In Text ist die Token-Reihenfolge wichtig; daher verarbeiten RNNs sequenziell, während Transformer-artige Modelle auf andere Teile des Satzes achten können.
  • In Graphen sind Beziehungen zwischen Kanten, Knoten und globalen Elementen wichtig, daher braucht es einen relationalen induktiven Bias.
    • Die explizite Beziehung der Adjazenzstruktur muss bewahrt werden.
    • Die Graphsymmetrie der Permutationsinvarianz muss bewahrt werden.
    • Das Modell muss unabhängig von der Reihenfolge von Knoten oder Kanten funktionieren und Eingaben variabler Anzahl verarbeiten.

Wahl der Aggregationsoperation

  • Das Pooling von Informationen benachbarter Knoten und Kanten ist ein zentraler Schritt leistungsfähiger GNN-Architekturen.
  • Da jeder Knoten eine andere Anzahl von Nachbarn hat und die Eingabereihenfolge irrelevant sein muss, wird eine differenzierbare, permutationsinvariante Aggregationsfunktion benötigt.
  • Typische Kandidaten sind sum, mean, max.
    • Alle akzeptieren eine variable Anzahl von Eingaben und erzeugen eine Ausgabe, die unabhängig von der Eingabereihenfolge ist.
  • Keine bestimmte Operation ist immer die beste.
    • mean ist nützlich, wenn sich die Nachbarzahlen stark unterscheiden oder eine normalisierte Sicht auf lokale Nachbarmerkmale benötigt wird.
    • max ist nützlich, wenn ein einzelnes auffälliges Merkmal in der lokalen Nachbarschaft betont werden soll.
    • sum zeigt die Verteilung lokaler Merkmale, ist aber nicht normalisiert und kann daher auch Ausreißer betonen.
  • In der Praxis wird häufig sum verwendet.
  • Principal Neighborhood Aggregation hängt mehrere Aggregationsoperationen aneinander und fügt eine Scaling Function hinzu, die vom Knotengrad abhängt.
  • Auch domänenspezifische Aggregationsoperationen wie Tetrahedral Chirality können entworfen werden.

GCN, Matrixmultiplikation und Graph-Walks

  • Ein GCN oder MPNN mit k Layern und 1-degree-Nachbarschaftsabfrage kann als neuronales Netz betrachtet werden, das auf Subgraph-Embeddings der Größe k arbeitet.
    • Die aktualisierte Repräsentation eines Knotens berücksichtigt begrenzt Informationen von Nachbarn innerhalb der k-distance.
    • Kantenrepräsentationen lassen sich auf dieselbe Weise interpretieren.
  • Das Produkt AX aus Adjazenzmatrix A und Knotenmerkmalsmatrix X implementiert einfaches Message Passing mit sum-Aggregation.
    • A_i,k ist positiv, wenn es eine Kante zwischen node_i und node_k gibt.
    • Matrixmultiplikation kann als Operation verstanden werden, die Werte bestimmter Merkmalsdimensionen benachbarter Knoten sammelt.
  • Bei dünn besetztem A ist eine Adjazenzliste effizienter, da nicht alle Nullterme addiert werden müssen.
  • Eine Implementierung auf Basis von Adjazenzlisten ist auch vorteilhaft, wenn andere Aggregationsoperationen als sum verwendet werden.
  • Potenzen der Adjazenzmatrix A^K hängen mit Walks der Länge K zusammen.
    • A^2_ij zählt die Zahl der Walks der Länge 2 von node_i zu node_j.
    • Diese Intuition setzt sich von A^3 bis A^k fort.

Attention, Erklärbarkeit und generative Modelle

  • Graph Attention Networks sammeln Nachbarinformationen nicht durch einfache Summation, sondern als gewichtete Summe.
    • Eine Score-Funktion f(node_i, node_j) berechnet die Relevanz zwischen zentralem Knoten und Nachbarknoten.
    • Per softmax werden die Gewichte normalisiert, sodass für die Aufgabe wichtige Nachbarn stärker gewichtet werden können.
    • Die paarweise Score-Berechnung bewahrt die Permutationsinvarianz.
  • Ein Transformer kann als GNN mit Attention-Mechanismus betrachtet werden.
    • Elemente wie Zeichentoken werden als Knoten eines vollständig verbundenen Graphen modelliert.
    • Attention berechnet Kanten-Embeddings und Gewichte für jedes Knotenpaar.
    • Der Unterschied liegt darin, dass GNNs sparse Verbindungsmuster annehmen, während Transformer alle Verbindungen modellieren.
  • Erklärbarkeit von GNNs kann für Modellvertrauen, Debugging und wissenschaftliche Entdeckungen wichtig sein.
    • Bei Molekülen kann die Existenz bestimmter Subgraphen wichtig sein.
    • In Zitationsnetzwerken kann der Vernetzungsgrad von Papers wichtig sein.
    • GNNExplainer geht vor, indem es für die Aufgabe relevante Subgraphen extrahiert.
    • Attribution-Techniken vergeben Wichtigkeitsrangfolgen an Teile eines Graphen.
  • Graphgenerierungsmodelle sampeln neue Graphen aus einer gelernten Verteilung oder vervollständigen einen Graphen ausgehend von einem Startpunkt.
    • Eine Anwendung ist das Design neuer Molekülgraphen mit bestimmten Eigenschaften als Wirkstoffkandidaten.
  • Die zentrale Schwierigkeit der Graphgenerierung ist die Modellierung der Graphtopologie.
    • Die Topologie variiert stark in der Größe und kann N_nodes^2 Terme haben.
    • Man kann die Adjazenzmatrix direkt wie ein Bild mit einem Autoencoder modellieren.
    • Man kann nur existierende Kanten und einen Teil nicht existierender Kanten vorhersagen, um die N_nodes^2-Last zu reduzieren.
    • Ein weiterer Ansatz ist, den Graphen sequenziell durch wiederholte diskrete Aktionen wie Hinzufügen oder Entfernen von Knoten und Kanten zu erzeugen.

Fazit

  • Graphen sind ein struktureller Datentyp mit anderen Stärken und Einschränkungen als Bilder und Text.
  • GNNs aktualisieren Knoten, Kanten und globalen Kontext eines Graphen und behandeln dabei Verbindungsstruktur und Permutationsinvarianz.
  • Pooling, Message Passing, Kantenrepräsentationen, globale Repräsentationen und die Wahl der Aggregationsfunktion sind Kernelemente des GNN-Designs.
  • Die tatsächliche Leistung hängt nicht nur von Tiefe, Dimension und Parameterzahl ab, sondern stark davon, welche Grapheigenschaften Nachrichten miteinander austauschen und wie der Graph konstruiert ist.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-12-21
Kommentare auf Hacker News

  • Es gibt viele Paper, die GNNs für Physiksimulationen einsetzen (z. B. numerische Strömungsmechanik). Der Grund ist, dass unstrukturierte Meshes, die den Problembereich diskretisieren, sehr gut zur Graphstruktur passen.
    In der Praxis wird jedes Mesh/jeder Graph oft nur einmal verwendet, um genau ein bestimmtes Problem zu lösen; ein GNN für einen bestimmten Graphen zu trainieren, ergibt daher nicht viel Sinn. Dass die meisten Paper es trotzdem so gemacht haben, liegt vermutlich daran, dass man noch nicht herausgefunden hat, wie man GNNs baut, die sich gut an unterschiedliche Meshes/Graphen und Simulationsparameter anpassen. Ich frage mich, ob bald ein Durchbruch kommt, der diese Generalisierung möglich macht.

    • Auch Wörter innerhalb und außerhalb eines Satzes scheinen sich wie Blattknoten zu verhalten, die auf andere Wörter verweisen oder von ihnen referenziert werden, und bilden damit eine Art Graph. Angesichts des Erfolgs des Attention-Mechanismus in modernen LLMs frage ich mich, wie gut LLMs wären, wenn man sie für echte Graphverarbeitung trainieren würde.
      Für optimale Leistung bräuchte man vermutlich einen anderen Tokenizer.
    • Ein universeller Graph-Löser müsste universelle Intelligenz sein. Schließlich könnte er sogar Kategorientheorie erfolgreich modellieren.

  • Die Qualität der Arbeit ist sehr hoch; schade, dass distill.pub keinen nachhaltigen Weg gefunden hat [1].
    Ein Grund, warum über GNNs weniger gesprochen wird, könnte der Mangel an Datensätzen sein [2]. Das war auch ein Problem, das den Bereich Semantic Web betroffen hat.
    [1] https://distill.pub/2021/distill-hiatus/
    [2] https://huggingface.co/datasets?task_categories=task_categor...

    • Mein persönlicher Trick ist, auf YouTube nach „explained“ zu suchen, bevor ich direkt in Paper aus einem unbekannten Gebiet einsteige.
      Wenn ein Bereich populär ist, gibt es viele Leute mit Anreiz, kurze und fesselnde Videos zu machen; selbst auf einem ziemlich abstrakten mathematischen Niveau ist die Qualität dann oft gut. Visualisierungen helfen enorm, ein Gefühl für abstrakte Konzepte zu bekommen, und 3Blue1Brown hat das bereits bewiesen. Auch bei GNNs reichen ein paar gute Videos unter zehn Minuten, um einen Einstieg in die Literatur zu bekommen.
    • Ehrlich gesagt hatte ich, als ich das auf der Titelseite sah, gehofft, dass distill einen Weg gefunden hätte weiterzumachen, aber das war nicht der Fall.

  • GNNs waren für mich persönlich ziemlich enttäuschend. Ich habe sie ein paar Mal in der Forschung angewendet, aber es hat nie wirklich funktioniert.
    Lange wurden GNNs als Verallgemeinerung von CNNs dargestellt, aber CNNs sind stärker, weil ihre „Nachbarschaftsgewichte“ mehr Bedeutung haben: Sie lernen relative Positionsbeziehungen. GNNs verlassen sich normalerweise, wie hier beschrieben, auf Pooling. CNNs können Bilder ausgeben, aber mit GNNs Graphen auszugeben ist nicht einfach. Die Topologie muss weiterhin vorab festgelegt werden, manchmal sogar während des Trainings. Der entscheidende Punkt ist die Performance: GNNs sind im Vergleich zu CNNs unglaublich langsam.
    Heutzutage fühlt es sich aus diesen Gründen so an, als habe Attention GNNs weitgehend ersetzt. Man kann zwar GNNs bauen, die statt Pooling Attention verwenden, aber das bringt nicht allzu viel. Der Graph wird normalerweise nur durchlaufen, um eine Maskenmatrix zu erzeugen, und der Rest ist dann ein gewöhnlicher Transformer. Wenn ohnehin schon ein Distanzmaß vorhanden ist, braucht man oft nicht einmal Graph-Adjazenz.
    Irgendwo sind GNNs für irgendwen sicher sehr nützlich, aber meiner Erfahrung nach waren sie eher ein Hammer auf der Suche nach Nägeln.

    • Es gibt mindestens einen Fall, in dem GNNs nützlich sind: wenn die Daten aus einer Menge von Atomen bestehen, deren Interaktionen ein einzelnes Datenelement definieren; wenn diese Menge so groß ist, dass man sie nicht einfach grob mit Attention erschlagen kann; wenn es innerhalb der Menge eine durch Interaktionen definierte Nachbarschaft/Geometrie gibt; und wenn die Daten bei Erhaltung dieser Struktur permutationsäquivariant sind, man aber keinen sinnvollen Weg findet, diese Geometrie implizit darzustellen. Ein Beispiel wären Fälle, in denen sich die Struktur von Sample zu Sample ändert, sodass man die Nachbarschafts-/Interaktionsstruktur als Eingabe übergibt und verarbeiten lässt.
      In fast allen anderen Fällen kann man zusätzliche Struktur nutzen, um effizienter zu werden. Wenn sich eine Ordnung definieren lässt, nimmt man ein sequenzielles Modell; bei euklidischer/riemannscher Struktur ein CNN oder ein mannigfaltigkeitsbewusstes Modell; wenn kein globaler Zustand nötig ist, ein Punktwolken-Netzwerk; bei expliziter Hierarchie eine U-Net-Version der jeweiligen Modalität usw.
      GNNs sind cool, weil sie 1) das Konzept von Beziehungen selbst encodieren und 2) gut zu vollständig allgemeinen diskretisierten Differentialgleichungen passen. Für jemanden aus dem Bereich komplexer Systeme/dynamischer Systeme ist das interessant, aber wenn man spezialisieren kann, gibt es eben einfachere Wege.
    • Ich frage mich, ob du mit regelmäßigen Daten wie in der Vision arbeitest.
      Aus den von dir genannten Gründen halte ich es nicht für Zufall, dass GNNs vor allem in Bereichen wie Empfehlungen beliebt sind, in denen sich das Domänenmodell selbst wie ein Graph anfühlt. Dort ist der Sprung zu einer nützlichen Topologie kleiner.
      Was mich persönlich noch mehr frustriert hat: Viele dieser graphartigen Domänen bestehen aus verhaltensbasierten Maschinen-/Menschendaten wie Logs und haben sehr viele kategoriale Dimensionen. Der Graphanteil hilft zwar, aber die kategorialen Dimensionen gut zu erfassen ist genauso wichtig; und um das gut hinzubekommen, landet man oft bei Ansätzen außerhalb des Modells, etwa Random Forests. Damit anzufangen ist einfacher, und der GNN-Teil erhöht den Aufwand stark für eine „etwas bessere Verbesserung“.
      Wenn das natürlich das Kerngeschäft ist und Millionen Dollar auf dem Spiel stehen, kann es gerechtfertigt sein. Für die meisten Betriebsteams ist es trotzdem schwierig. In der Praxis machen wir mit pygraphistry-Nutzern oft eher Dinge wie xgboost + umap und lassen es dabei. Schon ein RGCN zuverlässig zum Laufen zu bringen, ist eine Menge Arbeit.
    • Googles GraphCast ist ein GNN: https://deepmind.google/discover/blog/graphcast-ai-model-for...
    • Bei mir war es ähnlich. Ich habe viele Vorschläge gesehen, GNNs auf Probleme anzuwenden, bei denen man bisher „flache“ Modelle genutzt hatte, etwa indem man bei der Vorhersage von Seitenlabels die HTML-Struktur berücksichtigt. Selbst in Fällen, die oberflächlich wirklich gut passten, hat es nicht gut funktioniert.
    • Ich habe GNNs in der Biologie verfolgt und in einigen Domänen angewendet, aber die Ergebnisse waren bisher enttäuschend. Das war etwas überraschend, weil ich in der Biologie andere graphbasierte Ansätze erfolgreich eingesetzt habe.

  • GNNs scheinen auf einer festen Topologie zu arbeiten. Was sollte man tun, wenn man eine Transformation der Graphtopologie approximieren möchte? Zum Beispiel, wenn man ein Graph-Layout lernen oder den abstrakten Syntaxbaum eines Programms in einen Datenflussgraphen umwandeln will.

  • Der Kern von GNNs ist, dass sie den Begriff „Nachbarschaft“ explizit durch den Graphen konditionieren, der die Topologie vorgibt, und so auf beliebige Topologien generalisieren. Graph-Layout wurde hier versucht und bekam mit https://github.com/limbo018/DREAMPlace viel Aufmerksamkeit, zuletzt gab es dazu aber auch Kontroversen https://www.semanticscholar.org/paper/The-False-Dawn%3A-Reev...
    Auch Graph-Transformation wird erforscht https://arxiv.org/abs/2012.01470. Allerdings ist das ein schwieriges Problem, weil man implizit das Graph-Matching-Problem lösen muss.

    • Homologie könnte dabei vielleicht helfen. Wie eine Art Analysis für diskrete Strukturen: Man zählt, wie viele N-dimensionale Löcher es im Zeitverlauf gibt. Bei neuronalen Netzen weiß ich es nicht genau, aber für fMRI kann man sie so einsetzen.

  • Ich wünschte, distill würde zurückkommen.

  • Es ist wirklich schade, dass distill.pub keine neuen Einreichungen mehr annimmt.

  • Ich frage mich, welche interaktive Visualisierungssoftware das ist. D3.js?

  • Ich fühle mich ziemlich dumm. Auf der Seite gibt es ein Beispiel mit 4 Knoten (a,b,c,d), und es wird gezeigt, dass es insgesamt 24 mögliche Kombinationen gibt.
    Ich frage mich, wie die verallgemeinerte Formel dafür lautet, wenn die Anzahl der Knoten gegeben ist und man auch die Kanten berücksichtigen muss. Im Artikel scheint das nicht erklärt zu werden; vielleicht ist es einfach die Fakultät.

    • Kombinatorik lässt sich oft schnell mit Fakultäten berechnen. Wenn es 4 mögliche Auswahlen gibt und man in jedem Fall alle 4 genau einmal auswählt, ist das 4!. Intuitiv hat man bei der ersten Auswahl 4 Möglichkeiten, danach 3, dann 2 und zuletzt bleibt 1 übrig. Also ergibt sich 4 * 3 * 2 * 1 = 24.
      Wenn du dich damit vertrauter machen möchtest, bietet diese Seite offenbar einen recht guten Überblick: https://www.geeksforgeeks.org/mathematics-combinatorics-basi...
    • Das ließe sich vermutlich mit einem Binomialkoeffizienten oder verschachtelten Binomialkoeffizienten berechnen. Zum Beispiel etwas wie (n choose 4).
      Da jede Kante existieren oder nicht existieren kann, könnte man den Binomialkoeffizienten vielleicht auch mit 2 multiplizieren.