Adversarial Robustness of Graph Transformers

Dit paper introduceert de eerste adaptieve aanvalsmethoden voor Graph Transformers, onthult dat deze modellen vaak catastrofaal kwetsbaar zijn voor structurele perturbaties, en demonstreert hoe deze aanvallen effectief kunnen worden gebruikt voor adversarial training om de robuustheid aanzienlijk te verbeteren.

De kern

Titel: Waarom slimme grafieken (Graph Transformers) zo kwetsbaar zijn – en hoe we ze sterker maken

Stel je voor dat je een superintelligente robot hebt die verhalen vertelt over vrienden en hun netwerken. Deze robot, een Graph Transformer, is een van de slimste tools die we hebben om data in de vorm van netwerken (zoals sociale media, verkeerskaarten of chemische verbindingen) te begrijpen.

Maar deze paper, geschreven door onderzoekers van de Technische Universiteit München, vertelt een verontrustend verhaal: deze superrobots zijn eigenlijk heel breekbaar. Net als een huis van kaarten dat instort bij de minste windvlaag.

Hier is wat ze hebben ontdekt, vertaald naar alledaags taal:

1. Het Probleem: De "Blinde" Robot

Vroeger gebruikten we een andere soort robot (MPNNs) die netwerken bestudeerde. We wisten al dat je deze robot makkelijk kunt bedotten door een paar lijntjes in het netwerk te veranderen. Maar de nieuwe, geavanceerdere robots (Graph Transformers) waren nog niet getest.

De onderzoekers dachten: "Misschien zijn deze nieuwe robots wel sterker?"
Het antwoord was een schokkend nee. Sterker nog: ze zijn soms zelfs nog kwetsbaarder dan hun oudere broers.

De analogie:
Stel je voor dat je een robot hebt die een foto van een hond herkent. Als je een paar pixels op de foto verandert, ziet de robot misschien ineens een kat. Dat is wat er gebeurt met deze grafieken. Maar bij de nieuwe "Transformers" is het alsof je de robot een bril opzet die hem dwingt om te kijken naar de afstand tussen de poten van de hond, of naar de kleur van de lucht eromheen. Als je die afstand of die kleur heel subtiel verandert (zonder dat een mens het ziet), raakt de robot volledig in de war en denkt hij dat het een auto is.

2. De Uitdaging: Hoe bedrieg je een robot die niet "rekenen" kan?

Het probleem was dat je deze nieuwe robots niet zomaar kon testen. De oude methoden om ze te testen (zoals het veranderen van lijntjes in een netwerk) werken niet omdat de robot bepaalde onderdelen gebruikt die niet "glad" zijn.

De analogie:
Stel je voor dat je een auto wilt testen op remmen. Maar de rempedaal is gemaakt van een blok steen. Je kunt er niet zachtjes op drukken om te zien wat er gebeurt; je kunt er alleen hard op slaan. De onderzoekers hadden een manier nodig om die "stenen rempedalen" (de complexe wiskunde in de robot) tijdelijk te vervangen door een zacht, flexibel rubber. Dan konden ze heel voorzichtig drukken om te zien waar de auto het eerst zou falen.

Ze hebben een nieuwe methode bedacht om die "stenen" tijdelijk "rubber" te maken, zodat ze precies konden zien welke veranderingen de robot het meest verwarren.

3. De Test: Het "Kleine Veranderings"-Experiment

De onderzoekers hebben vijf verschillende soorten van deze slimme robots getest. Ze hebben ze blootgesteld aan drie soorten aanvallen:

1. Het veranderen van vriendschappen: "Wat gebeurt er als we twee mensen die niet met elkaar praten, ineens laten vrienden worden?"
2. Het toevoegen van nieuwe mensen: "Wat gebeurt er als we een nieuwe persoon in het netwerk steken die met iedereen praat?"
3. Het verwijderen van lijnen: "Wat als we een paar belangrijke verbindingen doorknippen?"

Het resultaat:
Bijna alle robots faalden catastrofisch.

• Voorbeeld: Op een dataset over nepnieuws (waar mensen retweeten), volstond het om maar 2% van de verbindingen te veranderen om de nauwkeurigheid van de robot met de helft te laten zakken.
• De robot dacht ineens dat een nepnieuwsbericht waar was, terwijl het duidelijk nep was.

Het is alsof je een beveiligingscamera hebt die perfect werkt, maar als je één klein stukje tape op de lens plakt, denkt hij dat er een brand is.

4. De Oplossing: Trainen met "Tegenvoerders"

Als je weet dat je robot zo kwetsbaar is, wat doe je dan? Je maakt hem niet zwakker, je maakt hem sterker door hem te trainen tegen de aanval.

De analogie:
Stel je voor dat je een bokser traint. Als je hem alleen maar laat trainen tegen een zachte sparringpartner, zal hij in de ring verliezen. Maar als je hem laat trainen tegen de slechtste denkbare tegenstander (de aanval die we net hebben bedacht), dan leert hij hoe hij moet verdedigen.

De onderzoekers hebben hun robots getraind met deze "slechtste denkbare aanval".

• Het resultaat: De robots werden plotseling veel sterker. Ze leerden om niet zo snel in de war te raken door kleine veranderingen.
• De verrassing: De nieuwe robots (Transformers) bleken, als ze goed getraind waren, zelfs beter te kunnen leren dan de oude robots. Ze waren flexibeler en konden zich beter aanpassen.

Samenvatting in één zin

Deze paper laat zien dat de nieuwste, slimste AI-modellen voor netwerken (Graph Transformers) verrassend kwetsbaar zijn voor kleine manipulaties, maar dat we ze juist door die kwetsbaarheid te begrijpen en te trainen, kunnen omtoveren tot de meest robuuste verdedigers die we ooit hebben gehad.

De les voor de rest van ons:
Als je een nieuw, super-slim systeem bouwt, test het dan niet alleen op hoe goed het werkt in de normale wereld. Test het ook op hoe het reageert als iemand probeert het te bedriegen. Want zonder die test, is je systeem misschien net zo breekbaar als een huis van kaarten.

Technische samenvatting

Titel: Adversarial Robustness of Graph Transformers

Publicatie: Transactions on Machine Learning Research (09/2025)
Auteurs: Philipp Foth, Lukas Gosch, Simon Geisler, Leo Schwinn, Stephan Günnemann (TUM & MCML)

---

1. Het Probleem

Hoewel er uitgebreid onderzoek is gedaan naar de kwetsbaarheid van Message-Passing Graph Neural Networks (MPNNs) voor adversarial attacks (zoals het manipuleren van de grafstructuur), is de robuustheid van Graph Transformers (GTs) grotendeels onontgonnen terrein.

• De Gaping: Bestaande state-of-the-art aanvallen (zoals PGD of PRBCD) kunnen niet direct worden toegepast op GTs. Dit komt omdat GTs vaak gebruikmaken van Positional Encodings (PEs) (gebaseerd op kortste paden, random walks, of spectrale eigenschappen) en gespecialiseerde attention-mechanismen die discreet en niet-differentieerbaar zijn ten opzichte van de invoergraf.
• Het Risico: Zonder geschikte tools om de robuustheid te evalueren, is het onmogelijk om te bepalen welke GT-architecturen veilig zijn voor kritieke toepassingen of hoe men effectieve verdedigingsmechanismen (zoals adversarial training) kan toepassen.

2. Methodologie

De auteurs stellen een raamwerk op om adaptieve, op gradiënten gebaseerde aanvallen te ontwerpen voor GTs. De kern van hun methode ligt in het creëren van differentieerbare relaxaties voor de niet-differentieerbare componenten van GTs.

A. Drie Ontwerpprincipes voor Relaxatie

Om een effectieve continue relaxatie ($\tilde{f}_\theta$) te maken die dicht bij het originele model ($f_\theta$) blijft, hanteren ze drie principes:

1. Coincidentie: Voor discrete invoer (echte grafen) moet de relaxatie exact dezelfde voorspelling geven als het originele model.
2. Interpolatie: De relaxatie moet continu en bijna overal differentieerbaar zijn ten opzichte van de continue adjacency matrix ($\tilde{A}'$), zodat gradiënten kunnen worden berekend.
3. Efficiëntie: De relaxatie mag de rekencomplexiteit niet exponentieel verhogen.

B. Specifieke Relaxaties per Architectuur

De auteurs passen deze principes toe op vijf representatieve GT-architecturen:

• Graphormer:
  • Degree PEs: Lineaire interpolatie tussen de PE-vectoren van de dichtstbijzijnde gehele graadwaarden.
  • Shortest Path Distances (SPD): Gebruik van de reciproke van de continue adjacency matrix om een continue proxy voor de kortste paden te berekenen, gevolgd door interpolatie.
• Spectral Attention Network (SAN):
  • Attention: Conversie van gescheiden sparse attention-mechanismen naar een continue vorm waarbij log-probabiliteiten van randen worden toegevoegd als bias aan de attention logits.
  • Spectrale PEs: Toepassing van matrix-perturbatietheorie om de gradiënten van de eigenwaarde- en eigenvector-berekeningen (Laplacian decomposition) te benaderen, zelfs bij herhaalde eigenwaarden.
• GRIT:
  • Relaxatie van de continue adjacency matrix en het toestaan van fractionele graadwaarden in de random walk embeddings. Geen speciale behandeling nodig voor de PEs zelf.
• GPS (General, Powerful, Scalable):
  • Gebruik van dezelfde relaxaties als SAN voor spectrale PEs. Voor de lokale GatedGCN-component worden de edge gates geschaald met de connectieprobabiliteit.
• Polynormer:
  • Relaxatie van de lokale sparse attention (gebaseerd op GAT) door deze formeel om te zetten naar volledige attention met log-probabiliteit bias, vergelijkbaar met SAN.

C. Node Injection Attacks (NIA)

Naast structuurmanipulatie (edge flips) introduceren ze een methode voor het injecteren van nieuwe knopen. Ze modelleren dit als een structuur-aanval op een uitgebreide graf en gebruiken een iteratieve berekening om de "knoopprobabiliteit" te bepalen, zodat de output van het model continu blijft ten opzichte van de injectie.

3. Belangrijkste Bijdragen

1. Eerste Principiële Aanval op GTs: De ontwikkeling van de eerste adaptieve, op gradiënten gebaseerde structuur-aanvallen specifiek ontworpen voor Graph Transformers.
2. Algemene Relaxatie-Principes: Het formuleren van richtlijnen om niet-differentieerbare componenten (zoals PEs en attention masks) differentieerbaar te maken, wat breed toepasbaar is op verschillende GT-modellen.
3. Empirisch Onderzoek: Een grondige evaluatie van de robuustheid van vijf populaire GT-architecturen (Graphormer, SAN, GRIT, GPS, Polynormer) op diverse taken (node classificatie, graf classificatie) en datasets.
4. Adversarial Training: Het aantonen dat deze adaptieve aanvallen effectief kunnen worden gebruikt voor adversarial training, wat leidt tot aanzienlijk robuustere modellen.

4. Resultaten

De experimentele resultaten tonen een zorgwekkend beeld van de kwetsbaarheid van GTs:

• Catastrofale Fragiliteit: GTs blijken in veel gevallen extreem kwetsbaar. Bijvoorbeeld, bij een Node Injection Attack op de UPFD datasets kan het manipuleren van slechts 2% van de randen de nauwkeurigheid van het model halveren.
• Vergelijking met MPNNs: Hoewel GTs soms robuuster zijn dan traditionele MPNNs (zoals GCN) bij zeer kleine budgetten, kunnen ze bij grotere perturbaties catastraal falen, soms zelfs meer dan MPNNs.
• Effectiviteit van Adaptieve Aanvallen: De door de auteurs ontwikkelde adaptieve aanvallen zijn aanzienlijk sterker dan baselines zoals willekeurige perturbaties of transfers van GCN-aanvallen. Dit bevestigt dat specifieke kennis van de GT-architectuur noodzakelijk is voor een realistische robuustheidsevaluatie.
• Transferability: Aanvallen die op de ene GT-architectuur zijn gegenereerd, transfereren vaak goed naar andere GT-architecturen, maar minder goed naar GCN-modellen (en vice versa).
• Adversarial Training: Het toepassen van adversarial training met deze adaptieve aanvallen verbetert de robuustheid van GTs drastisch. Interessant genoeg presteren GTs na adversarial training vaak beter dan traditionele MPNNs, wat suggereert dat de flexibiliteit van attention-mechanismen een krachtig middel is voor het leren van robuuste representaties.

5. Betekenis en Impact

• Veiligheid: Het artikel waarschuwt dat het vertrouwen op Graph Transformers in veiligheidskritieke toepassingen (zoals fake news detectie of chemische analyse) zonder robuustheidstests gevaarlijk is.
• Methodologische Vooruitgang: Het biedt de community de eerste set tools om de "black box" van GT-robustheid te openen. Zonder deze relaxaties zou het onmogelijk zijn om gradiënt-gebaseerde optimalisatie toe te passen op deze modellen.
• Toekomstperspectief: Het onderzoek suggereert dat GTs, ondanks hun huidige kwetsbaarheid, potentieel hebben om robuuster te zijn dan MPNNs, mits ze correct worden getraind met adaptieve aanvallen. Dit opent de weg voor het ontwerpen van veiligere en betrouwbaardere graf-neurale netwerken.

Kortom, dit artikel vult een cruciale lacune in het onderzoek naar GNN-veiligheid door aan te tonen dat Graph Transformers, ondanks hun superioriteit in bepaalde taken, momenteel extreem gevoelig zijn voor adversarial attacks, maar dat deze kwetsbaarheid kan worden opgelost door middel van geavanceerde trainingstechnieken.