Adversarial Robustness of Graph Transformers

Diese Arbeit schließt die Forschungslücke zur Robustheit von Graph-Transformern, indem sie die ersten adaptiven Angriffe für diese Architektur entwickelt und zeigt, dass sie in vielen Fällen katastrophal anfällig sind, was jedoch durch adversariales Training effektiv verbessert werden kann.

Das Wesentliche

Das große Problem: Der unsichtbare Riss im Netz

Stell dir vor, Graph Neural Networks (GNNs) sind wie große, vernetzte Städte. In diesen Städten wohnen Menschen (die Knoten) und sind durch Straßen verbunden (die Kanten). Diese Städte nutzen künstliche Intelligenz, um Dinge zu erkennen: "Ist diese Nachricht Fake-News?", "Welche Gruppe gehört dieser Nutzer an?" oder "Ist dieses Molekül gesund?".

Bisher wussten wir, dass die klassischen Städte (die sogenannten Message-Passing-Netzwerke) sehr anfällig sind. Ein kleiner Vandalismus – etwa das Schließen einer einzigen Straße oder das Hinzufügen einer falschen Brücke – kann das gesamte System durcheinanderbringen. Die KI verliert dann den Überblick.

Aber es gab eine neue, modernere Stadt: den Graph Transformer (GT). Diese Städte sind viel flexibler. Sie nutzen eine Art "Super-Aufmerksamkeit", bei der jeder Bürger jeden anderen direkt sehen kann, nicht nur seine direkten Nachbarn. Das ist super für komplexe Aufgaben. Aber die große Frage war: Wie stabil ist diese neue Stadt eigentlich? Wenn ein Hacker kommt, wie schnell bricht sie zusammen? Bisher war das ein Rätsel, weil es keine Werkzeuge gab, um diese neue Architektur zu testen.

Die Lösung: Der "Hacker-Test" für die neue Stadt

Die Autoren dieses Papiers haben genau das getan: Sie haben die ersten Werkzeuge gebaut, um diese neuen Graph-Transformer-Systeme gezielt zu attackieren.

Stell dir vor, du willst testen, wie stabil ein Schloss ist. Du könntest einfach zufällig gegen die Tür treten (das wäre ein "zufälliger Angriff"). Aber ein echter Einbrecher (ein "adaptiver Angriff") würde die Schwachstellen kennen, die Riegel genau dort aufhebeln, wo sie am schwächsten sind.

Die Forscher haben nun eine neue Art von Einbrecher entwickelt, der speziell für diese modernen Graph-Transformer-Systeme gebaut wurde. Das Schwierige daran: Diese Systeme haben viele Teile, die für Computer nicht "glatt" berechenbar sind (wie die genaue Anzahl der Nachbarn oder die kürzeste Route zwischen zwei Punkten). Um sie angreifbar zu machen, haben die Forscher diese Teile "geglättet" – wie wenn man einen zerklüfteten Bergpfad in eine sanfte Rampe verwandelt, damit man ihn mathematisch berechnen kann.

Was haben sie herausgefunden?

Das Ergebnis ist erschreckend, aber auch hoffnungsvoll:

1. Die neue Stadt ist extrem zerbrechlich:
   Wenn man die neuen Graph-Transformer mit diesen neuen, intelligenten Angriffen testet, brechen sie oft katastrophal zusammen.

   • Die Analogie: Stell dir vor, du hast ein hochmodernes, schwebendes Haus. Ein winziger Hauch von Wind (nur 2 % der Straßen werden verändert) reicht aus, damit das Haus einstürzt. In manchen Fällen sind diese neuen Systeme sogar anfälliger als die alten, klassischen Städte.

2. Der Angriff ist wie ein "Giftpilz":
   Die Forscher haben gezeigt, dass man nicht nur Straßen verändern muss, sondern auch neue, falsche Bürger (Knoten) in die Stadt "injizieren" kann. Wenn diese neuen Bürger nur wenige echte Straßen mit den alten verbinden, reicht das schon aus, um die KI zu täuschen. Es ist, als würde man einen einzelnen Lügner in eine Gruppe von Vertrauenspersonen stellen, der dann alle anderen manipuliert.

3. Die gute Nachricht: Man kann sie härten (Adversarial Training):
   Das ist der wichtigste Teil. Die Forscher haben gezeigt, dass man diese Systeme trainieren kann, indem man sie während des Trainings absichtlich attackiert.

   • Die Analogie: Stell dir vor, du trainierst einen Boxer. Wenn du ihn nur gegen einen schwachen Gegner trainierst, verliert er im echten Kampf. Aber wenn du ihn gegen die stärksten, cleversten Gegner trainierst (die "Adversarial Attacks"), lernt er, sich anzupassen, zu blocken und wird unbesiegbar.
   • Die Studie zeigt: Graph-Transformer sind wie Lernmaschinen. Wenn man sie richtig "quält" (durch diese Angriffe während des Trainings), werden sie extrem robust. Sie können sogar besser werden als die alten, starren Systeme, weil sie flexibel genug sind, um sich an die Angriffe anzupassen.

Zusammenfassung in einem Satz

Die Forscher haben entdeckt, dass die neuen, modernen Graph-KI-Systeme zwar extrem anfällig für kleine Manipulationen sind, aber genau diese Schwäche nutzen können, um durch gezieltes "Stress-Training" zu den robustesten Systemen überhaupt zu werden.

Warum ist das wichtig?
Weil wir diese Systeme bald überall einsetzen werden – von der Erkennung von Fake-News bis hin zur medizinischen Diagnose. Bevor wir sie in die reale Welt lassen, müssen wir wissen, wie sie auf Angriffe reagieren. Und diese Arbeit zeigt uns den Weg, wie wir sie nicht nur testen, sondern auch unzerstörbar machen können.

Technische Zusammenfassung

Problemstellung

Während die Anfälligkeit von Message-Passing Graph Neural Networks (MPNNs) wie GCNs gegenüber adversariellen Angriffen gut untersucht ist, bleibt die Robustheit von Graph Transformern (GTs) weitgehend unerforscht. Trotz ihrer wachsenden Bedeutung und ihrer Fähigkeit, Limitierungen von MPNNs (wie Over-Smoothing und Over-Squashing) zu überwinden, fehlt es an Werkzeugen, um deren Sicherheit zu bewerten.

Das Hauptproblem besteht darin, dass bestehende gradientenbasierte Angriffsmethoden (z. B. PGD, PRBCD) nicht direkt auf GTs anwendbar sind. GTs nutzen oft diskrete, nicht-differenzierbare Komponenten wie Positional Encodings (PEs) (basierend auf kürzesten Pfaden, Spektralzerlegung oder Random Walks) und spezialisierte Aufmerksamkeitsmechanismen. Da diese Komponenten nicht differenzierbar bezüglich der Eingabe-Adjazenzmatrix sind, können keine sinnvollen Gradienten für kontinuierliche Optimierungsverfahren berechnet werden, was eine realistische Einschätzung der Robustheit unmöglich macht.

Methodik

Die Autoren schlagen einen systematischen Ansatz vor, um diese Lücke zu schließen, indem sie adaptive Angriffe für GTs entwickeln.

1. Allgemeine Prinzipien für Relaxierungen:
   Um gradientenbasierte Angriffe zu ermöglichen, werden drei Prinzipien für die Konstruktion kontinuierlicher Relaxierungen ($\tilde{f}_\theta$) diskreter GT-Komponenten definiert:

   • Konsistenz: Für diskrete Eingaben muss das relaxierte Modell identisch zum Originalmodell sein.
   • Interpolation: Das Modell muss stetig und fast überall differenzierbar bezüglich der relaxierten Adjazenzmatrix sein.
   • Effizienz: Die Relaxierung darf die asymptotische Zeit- und Speicherkomplexität nicht übermäßig erhöhen.

2. Spezifische Relaxierungen für GT-Komponenten:
   Basierend auf diesen Prinzipien werden konkrete Relaxierungen für die fünf untersuchten Architekturen entwickelt:

   • Graphormer: Lineare Interpolation für Degree-Embeddings und kürzeste Pfade (SPD). Für SPD wird eine reziproke Adjazenzmatrix verwendet, um kontinuierliche Pfadlängen zu approximieren.
   • SAN (Spectral Attention Network): Nutzung der Matrix-Perturbationstheorie (Bamieh, 2022) zur Approximation der Eigenwerte und Eigenvektoren der Laplace-Matrix bei Störungen. Dies umgeht die Nicht-Differenzierbarkeit der Eigenzerlegung.
   • GRIT & GPS: Relaxierung der Adjazenzmatrix auf kontinuierliche Werte und Anpassung der Random-Walk-Embeddings bzw. der GatedGCN-Schichten entsprechend.
   • Polynormer: Umwandlung der spärlichen Aufmerksamkeitsmechanismen in eine kontinuierliche Form durch Hinzufügen von Log-Wahrscheinlichkeiten als Bias zu den Attention-Logits.

3. Node Injection Attack (NIA):
   Das Paper erweitert den Angriffsvektor um das Einfügen neuer Knoten in den Graphen. Anstatt neue Knotenmerkmale zu optimieren, werden existierende Knoten aus anderen Graphen des Datensatzes injiziert. Die Wahrscheinlichkeit eines Knotens, Teil des Graphen zu sein, wird iterativ basierend auf den Kantenwahrscheinlichkeiten berechnet, um eine stetige Optimierung zu gewährleisten.

4. Adversarial Training:
   Die entwickelten Angriffe werden genutzt, um eine effektive Verteidigungsstrategie durch adversarielles Training zu implementieren, basierend auf der „Free"-Methode.

Wesentliche Beiträge

1. Erste adaptive Angriffe für GTs: Formulierung allgemeiner Prinzipien zur Relaxierung nicht-differenzierbarer GT-Komponenten und Entwicklung der ersten gradientenbasierten Strukturangriffe für fünf repräsentative GT-Architekturen (Graphormer, SAN, GRIT, GPS, Polynormer).
2. Prinzipielle empirische Studie: Erste umfassende Analyse der adversariellen Robustheit von GTs. Die Studie zeigt, dass GTs in vielen Szenarien katastrophal anfällig sein können, teilweise sogar stärker als traditionelle MPNNs.
3. Verbindung von Flexibilität und Robustheit: Demonstration, dass die inhärente Flexibilität von GTs (durch Aufmerksamkeitsmechanismen) genutzt werden kann, um durch adversarielles Training signifikant robustere Modelle zu erstellen als bei statischen MPNNs.

Ergebnisse

Die Evaluation erfolgte auf mehreren Datensätzen (CLUSTER, Reddit Threads, UPFD Fake-News-Datensätze) für Aufgaben wie Knotenklassifizierung und Graphklassifizierung.

• Katastrophale Fragilität: Unter Verwendung der adaptiven Angriffe bricht die Genauigkeit vieler GT-Modelle bei sehr geringen Störungsbudgets (z. B. 2 % Kantenänderungen) drastisch ein. In einigen Fällen (z. B. Graphormer auf UPFD) ist die Anfälligkeit sogar höher als bei GCNs.
• Überlegenheit adaptiver Angriffe: Die entwickelten adaptiven Angriffe sind deutlich effektiver als Baselines wie zufällige Störungen, zufällige Suche oder Transfer-Angriffe von GCNs. Dies unterstreicht die Notwendigkeit, Angriffe an die spezifische Architektur des GTs anzupassen.
• Unterschiedliche Robustheit: Es gibt keine universell robuste Architektur. SAN zeigte sich auf den Fake-News-Datensätzen überraschend robust, während andere Modelle stark anfällig waren.
• Erfolg des Adversarial Trainings: Im Gegensatz zu MPNNs, bei denen adversarielles Training oft nur begrenzte Verbesserungen bringt, führt das Training mit den adaptiven GT-Angriffen zu einer drastischen Steigerung der Robustheit. GTs können durch ihre Flexibilität lernen, sich besser gegen Störungen zu schützen, und übertreffen dabei sogar adversariell trainierte GCNs.

Bedeutung und Ausblick

Das Paper schließt eine kritische Lücke im Verständnis der Sicherheit von Graph Transformern. Es zeigt, dass die Popularität von GTs nicht automatisch mit Robustheit einhergeht und dass bestehende Verteidigungsmechanismen ohne angepasste Angriffe nicht zuverlässig funktionieren.

Die vorgestellten Relaxierungen bieten einen allgemeinen Rahmen, der auf viele zukünftige GT-Architekturen übertragbar ist. Die Erkenntnis, dass GTs durch adversarielles Training potenziell robuster als MPNNs gemacht werden können, ist ein wichtiger Schritt für den Einsatz von Graph Transformers in sicherheitskritischen Anwendungen (z. B. Fake-News-Erkennung, Betrugserkennung). Zukünftige Arbeiten könnten sich auf die Optimierung dieser Relaxierungen und die formale Verifizierung der Robustheit konzentrieren.