CTQWformer: A CTQW-based Transformer for Graph Classification

Het artikel stelt CTQWformer voor, een nieuw hybride raamwerk dat continue-tijds kwantumwandelingen integreert met een Transformer-architectuur om zowel globale structurele afhankelijkheden als dynamische informatievoortplanting te vangen, waardoor superieure prestaties worden behaald in grafclassificatietaken vergeleken met bestaande GNN- en grafkernmethodes.

De kern

Stel je voor dat je probeert een complexe stad te begrijpen. Je hebt een kaart (de grafstructuur) die laat zien hoe straten met elkaar verbonden zijn, en je hebt een lijst met beschrijvingen voor elk gebouw (de knooppuntkenmerken).

Traditionele computerprogramma's (genaamd GNN's) proberen deze stad te begrijpen door een boodschapper van het ene gebouw naar zijn directe buren te sturen met de vraag: "Wat zie jij?" Ze blijven dit bericht doorgeven. Deze methode heeft echter twee grote problemen:

1. Het is te lokaal: De boodschapper raakt uitgeput na een paar blokken en vergeet wat er aan de andere kant van de stad gebeurt (ontbrekende langetermijnverbindingen).
2. Het is te statisch: Het behandelt de stad als een bevroren momentopname, en negeert hoe de stad zou kunnen veranderen of stromen in de loop van de tijd.

Hier komt CTQWformer: Een nieuwe, superslimme manier om deze "steden" (grafieken) te analyseren die het beste van drie werelden combineert: Kwantumfysica, Transformers (de technologie achter AI-chatbots) en Tijdsreizen.

Hier is hoe het werkt, opgesplitst in eenvoudige onderdelen:

1. De "Kwantumloper" (Het fysica-gedeelte)

In plaats van een uitgeputte boodschapper die één blok per keer loopt, stel je je een Kwantumloper voor.

• De magie: In de kwantumwereld loopt een deeltje niet alleen één straat af; het kan op veel plaatsen tegelijk zijn (superpositie) en kan met zichzelf interfereren zoals rimpelingen in een vijver.
• De innovatie: Meestal is deze "Kwantumloper" een vaste, stijve regel. Maar CTQWformer bouwt een op maat gemaakt, trainbaar gids (genaamd een Hamiltoniaan). Denk hierbij aan een GPS die leert het pad van de loper aan te passen op basis van zowel de straatindeling als het type gebouwen die het passeert.
• Het resultaat: Deze loper verkent de hele stad direct, en vangt complexe patronen en verbindingen op die een normale loper zou missen. Het creëert een "film" van hoe de loper door de stad beweegt in de loop van de tijd.

2. De twee gespecialiseerde teams

Zodra de Kwantumloper zijn film heeft voltooid, splitst CTQWformer de data op in twee teams om deze te analyseren:

• Team A: De "Momentopname"-analist (De Transformer)

  • Wat het doet: Het kijkt naar het laatste frame van de film van de Kwantumloper.
  • De analogie: Stel je voor dat je een foto maakt van waar de loper na 10 seconden is beland. Deze foto toont je het "grote plaatje" van de structuur van de stad.
  • Hoe het helpt: Het voert deze foto in bij een Transformer (het AI-brein). Het vertelt de AI: "Hé, besteed extra aandacht aan deze specifieke gebouwen omdat de kwantumfysica aangeeft dat ze sterk verbonden zijn." Dit helpt de AI om de globale vorm van de grafiek te begrijpen.

• Team B: De "Film"-analist (Het recurrente netwerk)

  • Wat het doet: Het bekijkt de hele film van de loper die beweegt van seconde 1 tot seconde 10.
  • De analogie: Waar Team A naar de laatste foto kijkt, kijkt Team B naar de dans. Het ziet hoe de loper oscilleert, heen en weer stuitert en stroomt.
  • Hoe het helpt: Het gebruikt een Recurrente Netwerk (een type AI dat goed is in sequenties) om het ritme en tempo van de stad te leren. Het vangt op hoe informatie stroomt en verandert in de loop van de tijd, iets wat een statische foto niet kan tonen.

3. De groots finale (Fusie)

Tot slot neemt het model de inzichten van de "Momentopname-analist" (de structuur) en de "Film-analist" (de tijd-gebaseerde stroming) en voegt ze samen.

• Het stapelt deze lagen bovenop elkaar, zoals het bouwen van een toren van begrip.
• Helemaal bovenaan neemt het een "gemiddelde" van alle geleerde informatie om de hele grafiek één label te geven (bijvoorbeeld: "Deze grafiek is een eiwit" of "Deze grafiek is een sociaal netwerk").

Waarom is dit een grote zaak?

Het artikel beweert dat door het mixen van Kwantumfysica (dat van nature goed is in het hanteren van complexe, globale verbindingen) met Deep Learning (dat goed is in leren van data), CTQWformer bestaande methoden verslaat.

• Oude methoden waren als het kijken naar een kaart met een vergrootglas (te lokaal) of een statische foto (geen tijd).
• CTQWformer is als het hebben van een drone die overal tegelijk kan vliegen (globaal), de stad in 3D ziet (structuur) en een high-speed video van het verkeersverkeer opneemt (dynamiek), terwijl het precies leert welke routes het belangrijkst zijn voor de specifieke taak.

Het oordeel:
De auteurs hebben dit getest op standaard datasets (zoals chemische moleculen en sociale netwerken) en ontdekten dat hun "Kwantum-Transformer"-hybride deze grafieken beter kon classificeren dan eerdere methoden. Dit bewijst dat het toevoegen van een beetje "kwantumdynamica" aan AI kan helpen om het bos en de bomen tegelijkertijd te zien.

Technische samenvatting

Technische Samenvatting: CTQWformer

Probleemstelling

Graph Neural Networks (GNN's) en op Transformers gebaseerde architecturen hebben het leren van grafen vooruitgebracht, maar staan voor specifieke beperkingen. Traditionele GNN's worstelen vaak met lokale receptieve velden, oververzachting in diepe netwerken en het onvermogen om lange-afstand afhankelijkheden te vangen. Omgekeerd, terwijl Transformers uitblinken in het modelleren van lange-afstand afhankelijkheden, slagen ze er vaak niet in om zowel lokale als globale structurele afhankelijkheden gelijktijdig effectief te vangen. Bovendien missen bestaande methoden mogelijk een fysisch onderbouwde mechanisme om de dynamische informatiepropagatie inherent aan grafstructuren te modelleren. Het artikel identificeert de behoefte aan een raamwerk dat gelijktijdig globale aandacht kan benutten, lokale structurele informatie behoudt en dynamische evolutiepatronen modelleert.

Methodologie

De auteurs stellen CTQWformer voor, een hybride raamwerk voor grafenleren dat Continuous-Time Quantum Walks (CTQW) integreert met GNN's. Het model is ontworpen om zowel statische fysische structurele bias als dynamische temporele evolutiepatronen van CTQW te vangen voor leeren op grafniveau. De architectuur bestaat uit drie kerncomponenten:

1. Quantum Walk Encoder (QWE)

In tegenstelling tot klassieke CTQW-modellen die vertrouwen op vaste Laplaciaan- of burenmatrices, hanteert CTQWformer een trainbare Hamiltoniaan ($H_\theta$).

• Constructie: De Hamiltoniaan fuseert grafentopologie en knooppuntkenmerken. Randgewichten worden geleerd door incidente knooppuntkenmerken te concateneren en deze door te geven via een multi-layer perceptron (MLP) met ReLU- en Sigmoid-activeringen om gebonden gewichten te garanderen.
• Dynamiek: Het systeem evolueert volgens de Schrödingervergelijking ($i \frac{d}{dt}|\psi(t)\rangle = H|\psi(t)\rangle$). Het model simuleert de evolutie van CTQW vertrekkend van orthonormale basisstaten (enkele-knooppunt initiële staten) over een reeks discrete tijdstappen $T$.
• Output: Dit proces genereert een temporeel evolutietensor $P \in \mathbb{R}^{T \times n \times n}$, die de waarschijnlijkheidsverdeling van de wandelaar over de grafiek op elke tijdstap encodeert.

2. Quantum Walk-Graph Transformer (QWGT) Module

Deze module adresseert de behoefte aan globaal structureel bewustzijn.

• Mechanisme: Het integreert de propagatiewaarschijnlijkheden op het eindtijdstip ($P^T$) uit de CTQW-simulatie als een statische structurele bias in het zelf-aandachtsmechanisme van een Graph Transformer.
• Integratie: De biasmatrix $B$ wordt afgeleid door $P^T$ te normaliseren en een log-transformatie toe te passen ($B = \log(1 + P^T)$), die wordt toegevoegd aan de aandachtscoresmatrix ($QK^T/\sqrt{d} + B$). Dit leidt het aandachtsmechanisme om de onderliggende grafentopologie en fysische structurele eigenschappen te respecteren, verder dan louter kenmerkenvergelijking.

3. Quantum Walk-Graph Recurrent (QWGR) Module

Deze module vangt de dynamische temporele evolutie van de quantum-wandeling.

• Mechanisme: Het verwerkt de volledige temporele reeks van de CTQW-evolutietensor. Specifiek worden de diagonaalelementen (knooppunt-specifieke zelf-propagatiewaarschijnlijkheden) uit de waarschijnlijkheidsmatrices over de tijdstappen gehaald.
• Architectuur: Deze reeksen worden ingevoerd in een Bidirectionele Gated Recurrent Unit (BiGRU) om temporele fluctuaties en afhankelijkheden in zowel voorwaartse als achterwaartse richtingen te modelleren.
• Output: De resulterende knooppuntrepresentaties worden geaggregeerd via gemiddelde pooling en een feedforward-netwerk om een embedding op grafniveau te produceren.

Fusie en Voorspelling

De QWGT- en QWGR-modules worden geïntegreerd in uniforme lagen. Hun outputs worden geconcateneerd en doorgegeven aan een feed-forward fusienetwerk. Het model ondersteunt het stapelen van meerdere lagen, waarbij embeddings op grafniveau worden uitgezonden naar representaties op knooppuntniveau om daaropvolgende lagen te sturen. Tot slot aggregeert globale gemiddelde pooling de uiteindelijke knooppunt-embeddings voor classificatie op grafniveau.

Belangrijkste Bijdragen

1. Trainbare Hamiltoniaan: Het ontwerp van een geparametriseerde Hamiltoniaan die zowel grafstructuur als knooppuntkenmerken integreert. Dit stelt de CTQW-dynamiek in staat om adaptief verbindingen te vangen op basis van knooppuntkenmerken, waardoor het model geschikt is voor classificatietaken op geattributeerde grafen.
2. Hybride Raamwerk (CTQWformer): Het voorstellen van de eerste hybride CTQW-gebaseerde Transformer. Het combineert uniek:
   • Statische Bias: Het gebruik van CTQW-waarschijnlijkheden op het eindtijdstip om het aandachtsmechanisme van de Transformer te sturen.
   • Dynamische Modellering: Het gebruik van bidirectionele recurrente netwerken om de temporele evolutie van CTQW te verwerken.
     Deze integratie stelt het model in staat om zowel statische fysische structurele bias als dynamische temporele evolutiepatronen te vangen.
3. Prestaties: Uitgebreide experimenten tonen aan dat het raamwerk traditionele grafkernels en diverse op GNN gebaseerde methoden (inclusief Graphormer en GraphGPS) overtreft op meerdere benchmarkdatasets.

Experimentele Resultaten

Het model werd geëvalueerd op zes benchmarkdatasets uit de TU-collectie (MUTAG, PTC(MR), PROTEINS, DD, IMDB-B, IMDB-M), die bio-informatica en sociale netwerken bestrijken.

• Vergelijking met Grafkernels: CTQWformer presteerde consistent beter dan zeven grafkernelmethodes, waaronder klassieke R-convolutiekernels en op CTQW gebaseerde informatie-theoretische kernels (bijv. JTQK, QJSK). Het behaalde de beste prestaties op vijf van de zes datasets.
• Vergelijking met GNN's: Het model behaalde concurrerende of superieure resultaten tegenover acht representatieve GNN's (bijv. GIN, GCN, GraphSAGE) en drie state-of-the-art Graph Transformers (Graphormer, GraphGPS, GRIT).
• Ablatiestudies: Het verwijderen van de QWGR-module (temporele modellering) resulteerde in een significante prestatiedaling (bijv. daalde de MUTAG-accuratesse van 92,54% naar 74,97%), wat de kritieke belangrijkheid van het modelleren van dynamische evolutie benadrukt. Het verwijderen van de QWGT-module (structurele bias) veroorzaakte een kleinere maar merkbaar afname, wat aangeeft dat beide componenten waardevol zijn.
• Hyperparametergevoeligheid: De studie vond dat gematigde tijdstappen (bijv. $T=4$ voor MUTAG) en netwerkdiepte (bijv. $L=2$) optimale prestaties opleverden, wat suggereert dat excessieve evolutietijd of netwerkdiepte kan leiden tot informatieverdunning of oververzachting.

Betekenis en Claims

Het artikel beweert dat CTQWformer een significante vooruitgang vertegenwoordigt door succesvol kwantumdynamica te integreren in trainbare deep learning-raamwerken.

• Fysische Grondslag: Het biedt een fysisch onderbouwde modellering van grafstructuren via de Schrödingervergelijking, waarbij ingewikkelde structurele informatie wordt vastgelegd via constructieve en destructieve interferentie-effecten inherent aan quantum-wandelingen.
• Complementaire Modellering: Door statische structurele bias te fuseren met dynamische temporele evolutie, overwint het model de beperkingen van modellen die uitsluitend vertrouwen op lokale aggregatie of statische aandacht.
• Eerste in zijn Soort: De auteurs stellen dat, naar hun kennis, dit de eerste hybride CTQW-gebaseerde Transformer is die CTQW-afgeleide structurele bias integreert met temporele evolutiemodellering om grafenleren vooruit te helpen.

De auteurs concluderen dat het werk het potentieel van quantum-wandeling-dynamica voor leeren van grafrepresentaties aantoont en suggereert dat toekomstig werk zich zal richten op het verbeteren van de computerefficiëntie en het uitbreiden van het raamwerk naar bredere grafenleren-taken.