Beyond Edge Deletion: A Comprehensive Approach to Counterfactual Explanation in Graph Neural Networks

In dit artikel wordt XPlore geïntroduceerd, een nieuwe methode die de interpretatie van Graph Neural Networks verbetert door een unificerend gradient-gebaseerd raamwerk te gebruiken dat niet alleen kanten verwijdert, maar ook kanten toevoegt en knoopkenmerken aanpast om zo effectievere en betekenisvollere contrafactuele verklaringen te genereren.

De kern

🕵️‍♂️ De "Waarom"-Vraag: Waarom is de computer zo'n raadsel?

Stel je voor dat je een superintelligente, maar zwijgzame arts hebt. Deze arts (een GNN of Graph Neural Network) kan met 99% zekerheid zeggen of een patiënt ziek is of niet. Maar als je vraagt: "Waarom denkt u dat hij ziek is?", dan haalt de arts alleen met zijn schouders. Hij werkt als een black box (een zwarte doos). Je ziet wat erin gaat en wat eruit komt, maar je ziet niet wat er binnenin gebeurt.

In belangrijke situaties – zoals het vinden van nieuwe medicijnen of het opsporen van fraude – willen we niet blindelings vertrouwen. We willen een uitleg. We willen weten: "Welke specifieke factor heeft deze beslissing veroorzaakt?"

🔄 De "Wat als"-Vraag: De Receptuur van de Verandering

De onderzoekers van dit paper introduceren een nieuwe methode genaamd XPlore. Om dit te begrijpen, gebruiken we een metafoor uit de keuken: Het Recept.

Stel dat de zwarte doos (de arts) een gerecht heeft geproefd en zegt: "Dit is te zout!"

• De oude manier (Edge Deletion): De vorige methoden waren als een kok die alleen zout uit het gerecht haalt. Ze dachten: "Als ik maar genoeg zout weghaal, wordt het minder zout." Maar wat als het gerecht te vet is? Dan helpt het weghalen van zout niets. Of wat als je juist een beetje peper nodig hebt om het evenwicht te herstellen? De oude methoden konden alleen dingen weghalen.
• De nieuwe manier (XPlore): XPlore is een slimme kok die alles kan doen. Hij kan:
  1. Ingrediënten weghalen (zoals de oude methode).
  2. Nieuwe ingrediënten toevoegen (zoals peper of kruiden).
  3. Bestaande ingrediënten aanpassen (bijvoorbeeld de hoeveelheid zout veranderen, in plaats van het helemaal te verwijderen).

XPlore zoekt naar de kleinste mogelijke verandering die het oordeel van de arts omkeert. Als het gerecht "te zout" is, wil XPlore weten: "Moet ik het zout weghalen, of moet ik juist een beetje suiker toevoegen om het te balanceren?"

🧩 Hoe werkt XPlore precies?

In de wereld van grafieken (netwerken van punten en lijnen, zoals moleculen of sociale netwerken) zijn er twee soorten dingen die je kunt veranderen:

1. De lijntjes (Edges): Wie is met wie verbonden? (Bijv. welke atomen zitten aan elkaar?).
2. De punten (Nodes): Wat zijn de eigenschappen van de punten zelf? (Bijv. wat voor soort atoom is het?).

De grote doorbraak van XPlore:
Vroeger konden computers alleen lijntjes weghalen om een verklaring te vinden. XPlore is de eerste die ook lijntjes kan toevoegen en de eigenschappen van de punten kan aanpassen.

• Voorbeeld: Stel je een chemisch molecuul voor dat giftig is.
  • Een oude methode zou zeggen: "Haal deze binding weg, dan is het niet meer giftig."
  • XPlore kan zeggen: "Nee, haal die binding weg is niet genoeg. Voeg juist een extra binding toe aan een ander punt, en verander de lading van dit atoom een klein beetje. Dan wordt het veilig."

Dit geeft een veel rijkere en eerlijkere uitleg. Het laat zien dat het antwoord soms ligt in het toevoegen van iets, niet alleen in het wegnemen.

🎯 Waarom is dit zo belangrijk? (De "Zin" van de verandering)

Soms maken oude methoden zulke grote, rare veranderingen dat het nieuwe resultaat eruitziet als een onzin-molecuul dat in de echte wereld niet bestaat. Dit noemen ze Out-of-Distribution (buiten de verdeling). Het is alsof de kok het zout vervangt door een steen; het is technisch "minder zout", maar het is geen gerecht meer.

XPlore gebruikt een slimme maatstaf (een Cosine Similariteit). Dit is als een "geurtest".

• De oude methoden kijken alleen naar het aantal veranderingen (hoeveel zout is er weg?).
• XPlore kijkt ook naar de geur (betekenis). Het zorgt ervoor dat het nieuwe gerecht (het tegenstrijdige voorbeeld) nog steeds op een echt gerecht lijkt, alleen dan met een andere smaak.

🏆 Wat zeggen de resultaten?

De onderzoekers hebben XPlore getest op 18 verschillende datasets (van moleculen tot sociale netwerken).

• Resultaat: XPlore slaagt veel vaker in het vinden van een geldig antwoord dan de beste concurrenten.
• Snelheid: Het is net zo snel als de andere methoden, dus het is niet traag.
• Betrouwbaarheid: De uitleggen die XPlore geeft, voelen "logischer" aan voor de mens, omdat ze rekening houden met zowel het toevoegen als het aanpassen van details.

📝 Samenvatting in één zin

XPlore is als een slimme detective die niet alleen kijkt naar wat er mist in een puzzel, maar ook begrijpt dat het toevoegen van een nieuw stukje of het aanpassen van de kleur van een bestaand stukje de oplossing kan zijn, waardoor hij de "zwarte doos" van de kunstmatige intelligentie eindelijk open en eerlijk kan maken.

Technische samenvatting

1. Probleemstelling

Graph Neural Networks (GNN's) worden steeds vaker ingezet in kritieke domeinen zoals moleculaire biologie (bijv. toxiciteitsvoorspelling) en financiële fraudeopsporing. Een groot nadeel is echter hun "black-box" aard, wat interpretatie en vertrouwen bemoeilijkt.

Bestaande methoden voor counterfactual explanations (verklaringen die aangeven welke minimale wijzigingen nodig zijn om een voorspelling te veranderen, bijv. van "giftig" naar "niet-giftig") hebben beperkingen:

• Te beperkte zoekruimte: De meeste bestaande methoden (zoals CF-GNNExplainer) focussen uitsluitend op het verwijderen van randen (edge deletions). Ze kunnen geen nieuwe randen toevoegen of knooppunt-kenmerken (node features) aanpassen.
• Out-of-Distribution (OOD) effecten: Door alleen randen te verwijderen, kunnen gegenereerde tegenwerelden (counterfactuals) vaak buiten de verdeling van de trainingsdata vallen. Dit leidt tot onbetrouwbare verklaringen die de modelvoorspelling veranderen door artefacten in plaats van betekenisvolle structurele wijzigingen.
• Gebrek aan semantische coherentie: Bestaande metrieken meten vaak alleen structurele afstand (zoals Graph Edit Distance), maar negeren of de betekenis van het graaf behouden blijft.

2. Methodologie: XPlore

De auteurs introduceren XPlore, een nieuwe techniek die de zoekruimte voor counterfactuals aanzienlijk uitbreidt binnen een unified gradient-based framework.

Kerncomponenten:

• Uitgebreide Perturbatie: In tegenstelling tot eerdere methoden, ondersteunt XPlore drie soorten wijzigingen gelijktijdig:
  1. Randverwijdering (Edge deletion).
  2. Randtoevoeging (Edge insertion): Dit is cruciaal voor scenario's waar het toevoegen van een verbinding nodig is om de voorspelling te veranderen.
  3. Knooppunt-kenmerk perturbatie (Node-feature perturbation): Het aanpassen van de attributen van knooppunten (bijv. chemische lading of eigenschappen).
• Gradient-Guided Optimization:
  • Het model behandelt de getrainde GNN als een vast "orakel".
  • Het gebruikt directe gradiënten van het verlies van het orakel om minimale perturbaties te sturen.
  • Er wordt geen extra surrogate-model of generatief model getraind; de explainer is lichtgewicht en direct gebaseerd op de bestaande classifier.
• Implementatie Details:
  • Randen: In plaats van een masker toe te passen op een bestaande adjacency-matrix, wordt de rol omgekeerd. Een continue matrix $\bar{P}$ wordt geïnitieerd met de originele randen en kan vrij worden geüpdatet. Een sigmoid-transformatie en drempelwaarde (thresholding) zetten dit om naar een binaire adjacency-matrix.
  • Knooppunten: Kenmerken kunnen ofwel "gegate" worden (verwijderd/behouden) of continu worden aangepast (waarde verhogen/verlagen).
  • Verliesfunctie: Het totale verlies bestaat uit een voorspellingsverlies (moet de label veranderen) en een afstandverlies (moet de wijziging minimaal houden), gewogen door een parameter $\beta$.
• Nieuwe Metriek (Cosine Similarity): Om het OOD-probleem aan te pakken, introduceren de auteurs een Cosine Similarity (CS) metriek op geleerde graaf-embeddings. Deze meet de semantische gelijkenis tussen de originele graaf en de counterfactual, wat waarborgt dat de verklaring binnen de relevante data-distributie blijft.

3. Belangrijkste Bijdragen

1. Comprehensieve Input Perturbatie: XPlore is de eerste methode die randen kan toevoegen én verwijderen, en knooppunt-kenmerken kan aanpassen binnen één raamwerk. Dit maakt het mogelijk om "truly counterfactual" patronen te vinden die met alleen randverwijdering onmogelijk zijn.
2. Gradient-Guided Optimalisatie: Door gebruik te maken van de gradiënten van het orakel, garandeert de methode dat de gevonden counterfactual lokaal het dichtst bij de oorspronkelijke graaf ligt in de loss-landschap, wat leidt tot consistente en minimale wijzigingen.
3. Mitigatie van OOD-effecten: De combinatie van randtoevoeging, kenmerkaanpassing en de Cosine Similarity-metriek vermindert het risico op het genereren van onrealistische, out-of-distribution voorbeelden.
4. Sterke Empirische Prestaties: De methode is getest op 13 real-world en 5 synthetische benchmarks en overtreedt de state-of-the-art (SoTA) methoden consequent.

4. Resultaten

De experimentele evaluatie toont aan dat XPlore superieur is aan bestaande methoden (zoals CF-GNNExpl, CF2, CLEAR, RSGG-CE, D4Explainer):

• Validiteit: XPlore bereikt tot +56,3% verbetering in validiteit (het vermogen om een geldige tegenwereld te vinden die de voorspelling verandert) ten opzichte van de beste concurrenten.
• Fideliteit: Er is een verbetering van +52,8% in fideliteit (hoe trouw de verklaring is aan de werkelijke beslissingsgrenzen van het model).
• Semantische Kwaliteit: Hoewel XPlore soms meer structurele bewerkingen (hoge Graph Edit Distance) uitvoert, behoudt het een hoge Cosine Similarity. Dit betekent dat de gegenereerde graaf semantisch dicht bij de oorspronkelijke klasse blijft, in tegenstelling tot concurrenten die vaak in "OOD-regio's" terechtkomen.
• Efficiëntie: De runtime is concurrerend met de state-of-the-art, wat aantoont dat de uitgebreide zoekruimte niet ten koste gaat van de snelheid.
• Node-Level Verklaringen: XPlore presteert ook beter bij node-level verklaringen, met een gemiddelde verbetering van +62,30% in validiteit.

5. Betekenis en Conclusie

Dit paper markeert een belangrijke verschuiving in het veld van GNN-interpreteerbaarheid. Het bewijst dat het beperken van counterfactual search tot alleen het verwijderen van randen onvoldoende is voor complexe grafen. Door randtoevoeging en kenmerkmanipulatie te integreren, biedt XPlore een realistischer en robuuster perspectief op hoe GNN's beslissingen nemen.

De methode is niet alleen effectiever in het vinden van geldige verklaringen, maar ook veiliger voor toepassingen in hoog-risico domeinen (zoals geneesmiddelenontwikkeling), omdat het de kans op het genereren van chemisch of logisch onmogelijke structuren verkleint. De introductie van Cosine Similarity als een kernmetriek voor semantische coherentie biedt een nieuwe standaard voor het evalueren van graaf-gegenereerde verklaringen.

Kortom, XPlore biedt een lichtgewicht, gradient-based oplossing die de interpretatie van GNN's aanzienlijk verbetert door een completere zoekruimte te verkennen zonder de betrouwbaarheid te verliezen.