CTQWformer: A CTQW-based Transformer for Graph Classification

Das Papier schlägt CTQWformer vor, ein neuartiges hybrides Framework, das kontinuierliche Quantenwalks mit einer Transformer-Architektur integriert, um sowohl globale strukturelle Abhängigkeiten als auch dynamische Informationsausbreitung zu erfassen, wodurch im Vergleich zu bestehenden GNN- und Graph-Kernel-Methoden eine überlegene Leistung bei Graphklassifizierungsaufgaben erzielt wird.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, eine komplexe Stadt zu verstehen. Sie haben eine Karte (die Graph-Struktur), die zeigt, wie die Straßen miteinander verbunden sind, und eine Liste von Beschreibungen für jedes Gebäude (die Knotenmerkmale).

Traditionelle Computerprogramme (sogenannte GNNs) versuchen, diese Stadt zu verstehen, indem sie einen Boten von einem Gebäude zu seinen unmittelbaren Nachbarn schicken und fragen: „Was siehst du?" Sie geben diese Nachricht weiter. Diese Methode hat jedoch zwei große Probleme:

1. Sie ist zu lokal: Der Bot wird nach ein paar Blocks müde und vergisst, was auf der anderen Seite der Stadt passiert (fehlende langreichweitige Verbindungen).
2. Sie ist zu statisch: Sie behandelt die Stadt als eingefrorenen Schnappschuss und ignoriert, wie sich die Stadt im Laufe der Zeit verändern oder entwickeln könnte.

Hier kommt CTQWformer ins Spiel: Eine neue, supersmart Art, diese „Städte" (Graphen) zu analysieren, die das Beste aus drei Welten kombiniert: Quantenphysik, Transformer (die Technologie hinter KI-Chatbots) und Zeitreisen.

So funktioniert es, aufgeteilt in einfache Teile:

1. Der „Quantenläufer" (Der physikalische Teil)

Statt eines müden Boten, der einen Block nach dem anderen geht, stellen Sie sich einen Quantenläufer vor.

• Die Magie: In der Quantenwelt geht ein Teilchen nicht nur eine Straße entlang; es kann sich an vielen Orten gleichzeitig befinden (Superposition) und kann sich wie Wellen in einem Teich mit sich selbst interferieren.
• Die Innovation: Normalerweise ist dieser „Quantenläufer" eine feste, starre Regel. Aber CTQWformer baut einen maßgeschneiderten, trainierbaren Führer (einen sogenannten Hamilton-Operator). Stellen Sie sich dies wie ein GPS vor, das lernt, den Weg des Läufers sowohl basierend auf dem Straßennetz als auch basierend auf der Art der Gebäude, an denen er vorbeikommt, anzupassen.
• Das Ergebnis: Dieser Läufer erkundet die ganze Stadt sofort, erfasst komplexe Muster und Verbindungen, die ein normaler Läufer verpassen würde. Er erstellt einen „Film" darüber, wie der Läufer im Laufe der Zeit durch die Stadt bewegt.

2. Die zwei spezialisierten Teams

Sobald der Quantenläufer seinen Film beendet hat, teilt CTQWformer die Daten in zwei Teams auf, um sie zu analysieren:

• Team A: Der „Schnappschuss"-Analyst (Der Transformer)

  • Was es tut: Es betrachtet den letzten Frame des Films des Quantenläufers.
  • Die Analogie: Stellen Sie sich vor, Sie machen ein Foto davon, wo der Läufer nach 10 Sekunden gelandet ist. Dieses Foto zeigt Ihnen das „große Ganze" der Struktur der Stadt.
  • Wie es hilft: Es speist dieses Foto in einen Transformer (das KI-Gehirn) ein. Es sagt der KI: „Hey, achte besonders auf diese spezifischen Gebäude, weil die Quantenphysik besagt, dass sie stark verbunden sind." Dies hilft der KI, die globale Form des Graphen zu verstehen.

• Team B: Der „Film"-Analyst (Das rekurrente Netzwerk)

  • Was es tut: Es schaut sich den gesamten Film des Läufers an, wie er von Sekunde 1 bis Sekunde 10 wandert.
  • Die Analogie: Während Team A das letzte Foto betrachtet, beobachtet Team B den Tanz. Es sieht, wie der Läufer oszilliert, hin und her springt und fließt.
  • Wie es hilft: Es verwendet ein rekurrentes Netzwerk (eine Art KI, die gut mit Sequenzen umgehen kann), um den Rhythmus und das Tempo der Stadt zu lernen. Es erfasst, wie Informationen im Laufe der Zeit fließen und sich verändern, was ein statisches Foto nicht zeigen kann.

3. Das große Finale (Fusion)

Schließlich nimmt das Modell die Erkenntnisse des „Schnappschuss-Analysten" (die Struktur) und des „Film-Analysten" (den zeitbasierten Fluss) und führt sie zusammen.

• Es stapelt diese Schichten übereinander, wie beim Aufbau eines Turms des Verständnisses.
• Ganz oben nimmt es einen „Durchschnittswert" aller gelernten Informationen, um dem gesamten Graphen eine einzelne Kennung zu geben (z. B. „Dieser Graph ist ein Protein" oder „Dieser Graph ist ein soziales Netzwerk").

Warum ist das eine große Sache?

Die Autoren behaupten, dass CTQWformer durch die Mischung aus Quantenphysik (die von Natur aus gut darin ist, komplexe, globale Verbindungen zu handhaben) und Deep Learning (das gut darin ist, aus Daten zu lernen), bestehende Methoden schlägt.

• Alte Methoden waren wie das Betrachten einer Karte mit einer Lupe (zu lokal) oder eines statischen Fotos (keine Zeit).
• CTQWformer ist wie eine Drohne, die überall gleichzeitig fliegen kann (global), die Stadt in 3D sieht (Struktur) und ein Hochgeschwindigkeitsvideo des Verkehrsflusses aufnimmt (Dynamik), während sie genau lernt, welche Routen für die spezifische Aufgabe am wichtigsten sind.

Das Fazit:
Die Autoren haben dies an Standarddatensätzen getestet (wie chemische Moleküle und soziale Netzwerke) und festgestellt, dass ihr „Quanten-Transformer"-Hybrid diese Graphen besser klassifizieren kann als frühere Methoden. Dies beweist, dass das Hinzufügen eines kleinen Bits „Quantendynamik" zur KI ihr helfen kann, sowohl den Wald als auch die Bäume gleichzeitig zu sehen.

Technische Zusammenfassung

Technische Zusammenfassung: CTQWformer

Problemstellung

Graph-Neuronale Netze (GNNs) und Transformer-basierte Architekturen haben das Graph-Lernen vorangebracht, stoßen jedoch auf spezifische Grenzen. Traditionelle GNNs kämpfen häufig mit lokalen rezeptiven Feldern, Überglättung in tiefen Netzen und der Unfähigkeit, langreichweitige Abhängigkeiten zu erfassen. Umgekehrt scheitern Transformer, obwohl sie bei der Modellierung langreichweitiger Abhängigkeiten hervorragend sind, oft daran, sowohl lokale als auch globale strukturelle Abhängigkeiten gleichzeitig effektiv zu erfassen. Darüber hinaus fehlt es bestehenden Methoden möglicherweise an einem physikalisch fundierten Mechanismus, um die in Graphstrukturen inhärente dynamische Informationsausbreitung zu modellieren. Die Arbeit identifiziert den Bedarf an einem Framework, das gleichzeitig globale Aufmerksamkeit nutzen, lokale strukturelle Informationen bewahren und dynamische Evolutionsmuster modellieren kann.

Methodik

Die Autoren schlagen CTQWformer vor, ein hybrides Graph-Lern-Framework, das Continuous-Time Quantum Walks (CTQW) mit GNNs integriert. Das Modell ist darauf ausgelegt, sowohl statische physikalische strukturelle Verzerrungen als auch dynamische zeitliche Evolutionsmuster von CTQW für das Graph-Level-Repräsentationslernen zu erfassen. Die Architektur besteht aus drei Kernkomponenten:

1. Quantum Walk Encoder (QWE)

Im Gegensatz zu klassischen CTQW-Modellen, die auf festen Laplace- oder Adjazenzmatrizen basieren, verwendet CTQWformer eine trainierbare Hamilton-Funktion ($H_\theta$).

• Konstruktion: Die Hamilton-Funktion fusioniert Graph-Topologie und Knotenmerkmale. Kantengewichte werden gelernt, indem inzidente Knotenmerkmale konkateniert und durch ein Multi-Layer-Perceptron (MLP) mit ReLU- und Sigmoid-Aktivierungen geleitet werden, um begrenzte Gewichte sicherzustellen.
• Dynamik: Das System entwickelt sich gemäß der Schrödinger-Gleichung ($i \frac{d}{dt}|\psi(t)\rangle = H|\psi(t)\rangle$). Das Modell simuliert die Evolution von CTQW ausgehend von orthonormalen Basiszuständen (Einzelknoten-Anfangszuständen) über eine Reihe diskreter Zeitschritte $T$.
• Ausgabe: Dieser Prozess erzeugt einen zeitlichen Evolutions-Tensor $P \in \mathbb{R}^{T \times n \times n}$, der die Wahrscheinlichkeitsverteilung des Walkers über den Graphen zu jedem Zeitschritt kodiert.

2. Quantum Walk-Graph Transformer (QWGT) Modul

Dieses Modul adressiert die Notwendigkeit globaler struktureller Awareness.

• Mechanismus: Es integriert die Propagationswahrscheinlichkeiten zum Endzeitpunkt ($P^T$) aus der CTQW-Simulation als statische strukturelle Verzerrung in den Selbst-Aufmerksamkeitsmechanismus eines Graph-Transformers.
• Integration: Die Verzerrungsmatrix $B$ wird durch Normalisierung von $P^T$ und Anwendung einer Logarithmus-Transformation abgeleitet ($B = \log(1 + P^T)$), die zur Aufmerksamkeits-Score-Matrix addiert wird ($QK^T/\sqrt{d} + B$). Dies lenkt den Aufmerksamkeitsmechanismus an, die zugrunde liegende Graph-Topologie und physikalische strukturelle Eigenschaften jenseits reiner Merkmalsähnlichkeit zu respektieren.

3. Quantum Walk-Graph Recurrent (QWGR) Modul

Dieses Modul erfasst die dynamische zeitliche Evolution des Quantenwalks.

• Mechanismus: Es verarbeitet die vollständige zeitliche Sequenz des CTQW-Evolutions-Tensors. Spezifisch extrahiert es die Diagonalelemente (knotenspezifische Selbst-Propagationswahrscheinlichkeiten) aus den Wahrscheinlichkeitsmatrizen über die Zeitschritte hinweg.
• Architektur: Diese Sequenzen werden in eine Bidirektionale Gated Recurrent Unit (BiGRU) eingespeist, um zeitliche Schwankungen und Abhängigkeiten sowohl in Vorwärts- als auch in Rückwärtsrichtung zu modellieren.
• Ausgabe: Die resultierenden Knotenrepräsentationen werden durch Mean Pooling und ein Feedforward-Netzwerk aggregiert, um eine Graph-Level-Einbettung zu erzeugen.

Fusion und Vorhersage

Die QWGT- und QWGR-Module werden in vereinheitlichten Schichten integriert. Ihre Ausgaben werden konkateniert und durch ein Feedforward-Fusionsnetzwerk geleitet. Das Modell unterstützt das Stapeln mehrerer Schichten, wobei Graph-Level-Einbettungen zurück auf Knoten-Level-Repräsentationen übertragen werden, um nachfolgende Schichten zu steuern. Schließlich aggregiert globales Mean Pooling die finalen Knoteneinbettungen für die Graph-Level-Klassifizierung.

Hauptbeiträge

1. Trainierbare Hamilton-Funktion: Das Design einer parametrisierten Hamilton-Funktion, die sowohl Graph-Struktur als auch Knotenmerkmale integriert. Dies ermöglicht es der CTQW-Dynamik, Verbindungen adaptiv basierend auf Knotenmerkmalen zu erfassen, was das Modell für Aufgaben der attributierten Graph-Klassifizierung geeignet macht.
2. Hybrides Framework (CTQWformer): Der Vorschlag des ersten hybriden CTQW-basierten Transformers. Er kombiniert einzigartig:
   • Statische Verzerrung: Verwendung von CTQW-Wahrscheinlichkeiten zum Endzeitpunkt zur Steuerung des Aufmerksamkeitsmechanismus des Transformers.
   • Dynamische Modellierung: Verwendung bidirektionaler rekurrenter Netze zur Verarbeitung der zeitlichen Evolution von CTQW.
     Diese Integration ermöglicht es dem Modell, sowohl statische physikalische strukturelle Verzerrungen als auch dynamische zeitliche Evolutionsmuster zu erfassen.
3. Leistung: Umfassende Experimente zeigen, dass das Framework traditionelle Graph-Kernel und verschiedene GNN-basierte Methoden (einschließlich Graphormer und GraphGPS) auf mehreren Benchmark-Datensätzen übertrifft.

Experimentelle Ergebnisse

Das Modell wurde auf sechs Benchmark-Datensätzen aus der TU-Sammlung (MUTAG, PTC(MR), PROTEINS, DD, IMDB-B, IMDB-M) evaluiert, die Bioinformatik und soziale Netzwerke abdecken.

• Vergleich mit Graph-Kerneln: CTQWformer übertraf konsistent sieben Graph-Kernel-Methoden, einschließlich klassischer R-Faltung-Kernel und informationstheoretischer Kernel basierend auf CTQW (z. B. JTQK, QJSK). Es erzielte die beste Leistung auf fünf der sechs Datensätze.
• Vergleich mit GNNs: Das Modell erzielte konkurrenzfähige oder überlegene Ergebnisse gegenüber acht repräsentativen GNNs (z. B. GIN, GCN, GraphSAGE) und drei State-of-the-Art Graph-Transformern (Graphormer, GraphGPS, GRIT).
• Ablationsstudien: Das Entfernen des QWGR-Moduls (zeitliche Modellierung) führte zu einem signifikanten Leistungsabfall (z. B. fiel die MUTAG-Genauigkeit von 92,54 % auf 74,97 %), was die kritische Bedeutung der Modellierung dynamischer Evolution unterstreicht. Das Entfernen des QWGT-Moduls (strukturelle Verzerrung) verursachte einen kleineren, aber spürbaren Rückgang, was darauf hindeutet, dass beide Komponenten wertvoll sind.
• Hyperparameter-Sensitivität: Die Studie ergab, dass moderate Zeitschritte (z. B. $T=4$ für MUTAG) und Netzwerktiefe (z. B. $L=2$) optimale Leistung erzielten, was darauf hindeutet, dass übermäßige Evolutionszeit oder Netzwerktiefe zu Informationsverdünnung oder Überglättung führen können.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass CTQWformer einen bedeutenden Fortschritt darstellt, indem es Quantendynamik erfolgreich in trainierbare Deep-Learning-Frameworks integriert.

• Physikalische Fundierung: Es bietet eine physikalisch fundierte Modellierung der Graph-Struktur durch die Schrödinger-Gleichung und erfasst komplexe strukturelle Informationen durch konstruktive und destruktive Interferenzeffekte, die Quantenwalks inhärent sind.
• Komplementäre Modellierung: Durch die Fusion statischer struktureller Verzerrungen mit dynamischer zeitlicher Evolution überwindet das Modell die Grenzen von Modellen, die sich ausschließlich auf lokale Aggregation oder statische Aufmerksamkeit verlassen.
• Erstmalige Umsetzung: Die Autoren stellen fest, dass dies nach ihrem Wissen der erste hybride CTQW-basierte Transformer ist, der CTQW-abgeleitete strukturelle Verzerrung mit zeitlicher Evolutionsmodellierung integriert, um das Graph-Lernen voranzutreiben.

Die Autoren schließen, dass die Arbeit das Potenzial von Quantenwalk-Dynamiken für das Graph-Repräsentationslernen demonstriert und zukünftige Arbeiten darauf fokussieren werden, die Recheneffizienz zu verbessern und das Framework auf breitere Graph-Lernaufgaben zu erweitern.