💻 computer science

A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks

Dit artikel stelt een nieuw, model-agnostisch framework voor het genereren van hoogwaardige contrafeitelijke verklaringen in Graph Neural Networks door feitelijke verklaarbaarheid te integreren met modellen voor het voorspellen van ontbrekende randen, waarbij superieure prestaties worden aangetoond ten opzichte van de huidige state-of-the-art baselines over diverse grafenclassificatie-benchmarks.

Oorspronkelijke auteurs: Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

Gepubliceerd 2026-06-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een super-slimme robot hebt (een Graph Neural Network) die naar een complex web van verbindingen kijkt—zoals een sociaal netwerk, een molecuul of een kaart van vriendschappen—en een beslissing neemt, zoals: "Dit molecuul is giftig" of "Deze tweet is boos."

Het probleem is dat de robot een "black box" is. Hij geeft je het antwoord, maar vertelt je niet waarom. Je wilt weten: "Wat kleine verandering zou de robot van gedachten doen veranderen?" Dit wordt een Counterfactual Explanation genoemd. Het is alsof je vraagt: "Als ik dat ene ding niet had gezegd, zou de uitkomst dan anders zijn geweest?"

Dit artikel introduceert een nieuwe tool genaamd DR-CFGNN om die vraag beter te beantwoorden dan eerdere tools. Hier is hoe het werkt, met behulp van eenvoudige analogieën:

Het probleem met oude tools

Eerdere tools probeerden de beslissing van de robot uit te leggen door:

Dingen weg te halen: Zoals een beeldhouwer die stukjes steen wegbeitelt om te zien welke vorm er overblijft. Ze konden alleen verbindingen (edges) verwijderen uit de graaf.
Willekeurig te gokken: Proberen verbindingen toe te voegen of te verwijderen door met blinddoek pijltjes te gooien.

De auteurs zeggen dat deze methoden beperkt zijn. Soms moet je om de mening van de robot te veranderen niet alleen een slechte verbinding verwijderen; moet je misschien juist een ontbrekende verbinding toevoegen. Het is alsof je een kapotte puzzel probeert te repareren; soms moet je een verkeerd stukje eruit halen, maar andere keren moet je het ontbrekende stukje vinden dat het plaatje compleet maakt.

De nieuwe oplossing: Het "Completion-Aware" Framework

De auteurs hebben een framework gebouwd dat de graaf behandelt als een puzzel met ontbrekende stukjes. Ze noemen het "Completion-Aware" omdat het weet hoe het de gaten moet opvullen.

Het proces vindt plaats in vier stappen, als een vierstaps werkplaats:

1. De ruisfilter (Denoising)

Echte gegevens zijn rommelig. Stel je een sociaal netwerk voor waarbij sommige vriendschappen per ongeluk zijn toegevoegd (spam).

Wat de tool doet: Voordat de graaf wordt geanalyseerd, gebruikt het een "ruisfilter" om de rommel op te schonen. Het verwijdert zwakke of onwaarschijnlijke verbindingen die waarschijnlijk niet belangrijk zijn. Dit maakt de puzzel duidelijker voordat je begint met werken.

2. De deconstructie (De schuldige vinden)

Nu kijkt de tool naar de schone graaf om het specifieke deel te vinden dat de robot ervan overtuigde om zijn oorspronkelijke beslissing te nemen.

De analogie: Stel je voor dat de robot een film "Eng" vond vanwege een specifieke scène. Deze stap isoleert die scène. Het kijkt niet naar de hele film; het focust alleen op het enge deel. Vervolgens probeert het die specifieende scène te "breken" door een paar belangrijke verbindingen te verwijderen om te zien of de robot niet meer bang is.

3. De reconstructie (De magie van Link Prediction)

Dit is de grote innovatie van het papier. In plaats van alleen dingen te breken, vraagt de tool: "Wat als we iets toevoegen om het verhaal te veranderen?"

De analogie: Denk aan een detective die de "regels van de buurt" kent. Als de robot denkt dat een molecuul giftig is, vraagt deze stap: "Wat als we een specifieke chemische binding toevoegen die normaal gesproken dingen veilig maakt?"
De tool gebruikt een techniek genaamd Link Prediction (meestal gebruikt om te voorspellen wie in de toekomst vrienden zullen worden) om intelligent nieuwe verbindingen voor te stellen. Het gokt niet zomaar willekeurig; het zoekt naar patronen die logischerwijs zouden leiden tot een andere conclusie van de robot (bijvoorbeeld van "Giftig" naar "Veilig").

4. Het sorteren (Post-Hoc Optimization)

De tool kan veel verschillende manieren genereren om de graaf te veranderen. Sommige veranderingen zijn minuscuul en precies; andere zijn groot en rommelig.

Wat de tool doet: Het rangschikt deze opties. Het geeft de voorkeur aan de "minimale" veranderingen—de kleinste, meest logische aanpassingen die de beslissing van de robot omgooien. Het is als een redacteur die de voorkeur geeft aan één woordwijziging boven het herschrijven van een hele paragraaf.

Waarom is dit beter?

De auteurs hebben hun tool getest op veel verschillende soorten grafen (van nep synthetische puzzels tot echte wereldgegevens zoals moleculen en tweets) en hebben het vergeleken met de beste bestaande tools.

Slimere aanpassingen: Hun tool vond de "ontbrekende stukjes" veel beter dan anderen. Het verwijderde niet alleen dingen; het wist precies wat het moest toevoegen om de uitkomst te veranderen.
Kleinere veranderingen: De verklaringen waren "compact". In plaats van te suggereren dat je 50 verbindingen moet veranderen, ontdekte het vaak dat het veranderen van slechts 2 of 3 genoeg was. Dit maakt de uitleg gemakkelijker voor mensen om te begrijpen.
Accurater: De veranderingen die het voorstelde, lagen zeer dicht bij de "ground truth" (de werkelijke reden waarom de robot zijn beslissing nam).
Sneller: Omdat het slimme sampling gebruikt (zoeken in de juiste plekken) in plaats van elke mogelijke mogelijkheid te controleren, draait het veel sneller dan de zware, trage tools die proberen alles te verkennen.

De kern

Dit artikel presenteert een nieuwe manier om de beslissingen van AI op grafen uit te leggen. In plaats van alleen de data weg te beitelen of willekeurig te gokken, handelt het als een bekwame puzzeloplosser: het maakt het bord schoon, vindt het cruciale stukje en voegt vervolgens intelligent het ontbrekende stukje toe om het uiteindelijke plaatje te veranderen. Dit resulteert in verklaringen die korter, nauwkeuriger en gemakkelijker te vertrouwen zijn voor mensen.

Technische Samenvatting: Een Completion-Aware Framework voor Impactvolle Counterfactual Explainability in Graph Neural Networks

Probleemstelling

Graph Neural Networks (GNN's) worden steeds vaker ingezet in diverse domeinen, maar hun "black-box"-aard vormt aanzienlijke uitdagingen voor de interpreteerbaarheid. Hoewel factuele explainers (die subgrafen identificeren die cruciaal zijn voor een voorspelling) goed gevestigd zijn, blijven Counterfactual Explanations (CfX'en)—die minimale wijzigingen aan een invoer-graaf suggereren om de voorspelling van een model te veranderen—onderontwikkeld.

Bestaande CfX-methoden kampen met verschillende beperkingen:

Alleen Randverwijdering: Veel vroege benaderingen (bijv. CF-GNNExplainer, CFExplainer) beperken verklaringen tot het verwijderen van randen (edges), wat hun expressieve kracht beperkt en vaak resultaten buiten de distributie (out-of-distribution, OOD) oplevert.
Efficiëntie en Generaliseerbaarheid: Methoden die zowel het toevoegen als het verwijderen van randen ondersteunen (bijv. LEGIT, MEG, D4Explainer), lijden vaak aan een hoge computationele complexiteit, vereisen uitgebreide domeinkennis of vertrouwen op specifieke causale modellen die niet altijd beschikbaar zijn.
Gebrek aan Vergelijkende Analyse: Er is een tekort aan uitgebreide evaluaties die state-of-the-art frameworks vergelijken die zowel randtoevoeging als -verwijdering ondersteunen.

De kernuitdaging die wordt aangepakt, is het genereren van generieke, model-agnostische, lokale-niveau CfX'en die efficiënt, robuust en intuïtief betekenisvol zijn (dat wil zeggen: het suggereren van plausibele structurele wijzigingen in plaats van willekeurige bewerkingen).

Methodologie: Het DR-CFGNN Framework

De auteurs stellen DR-CFGNN (De/Re-construction-driven Counterfactual GNN) voor, een pipeline die inzichten uit link-voorspelling integreert om de kwaliteit en robuustheid van de CfX-generatie te verbeteren. Het framework werkt in vier afzonderlijke fasen:

1. Denoising (Fase I)

Real-world grafen bevatten vaak ruis (irrelevante verbindingen). Het framework gebruikt een getraind link-voorspellingsmodel (zonder klasse-conditionering) om de waarschijnlijkheid van randen te schatten. Randen met de laagste waarschijnlijkheid worden verwijderd, mits hun verwijdering de oorspronkelijke voorspelling van de oracle niet verandert. Deze stap verfijnt de invoer-graaf ( $G_{DeN}$ ) vóór de generatie van de verklaring.

2. Deconstructie (Fase II)

In plaats van de gehele graaf af te zoeken naar randen om te verwijderen, extraheert het framework eerst een factuele subgraaf ( $G_F$ ) met behulp van een bestaande factuele explainer (bijv. SubgraphX). Vervolgens verwijdert het selectief randen alleen uit deze factuele subgraaf. Deze strategie verzwakt de ondersteuning voor de oorspronkelijke voorspelling zonder deze direct te veranderen, waarbij de focus wordt gelegd op de specifieke patronen die de beslissing van de oracle drijven.

3. Reconstructie (Fase III)

Dit is de kern van het "completion-aware" component. Het framework traint een graaf-expansiemodel (een encoder-decoder architectuur) om ontbrekende randen te voorspellen die zouden leiden tot een doel-counterfactual klasse ( $y_{CF}$ ).

Architectuur: Een Graph Convolutional Network (GCN) encoder genereert node-embeddings. Een klasse-specifieke embedding (afgeleid van een one-hot vector van de doelklasse) wordt geconcateneerd met de node-embeddings. Een Multi-Layer Perceptron (MLP) decoder voorspelt vervolgens de waarschijnlijkheid van randen tussen paren nodes.
Inductief Leren: In tegenstelling tot traditionele transductieve link-voorspelling, wordt dit model inductief getraind op een collectie grafen om te generaliseren naar ongeziene test-grafen en patronen.
Domeinrestricties: Het trainingsproces kan domeinkennis integreren door bepaalde randen (bijv. chemische bindingen) vast te leggen als altijd aanwezig of onmogelijk, wat zorgt voor plausibele verklaringen.
Inference: Het model schat de waarschijnlijkheid van niet-bestaande randen in de gedeconstrueerde graaf. Randen die een drempelwaarde overschrijden, worden toegevoegd om kandidaat-counterfactuals te genereren.

4. Post-hoc Optimalisatie (Fase IV)

Om de potentieel grote set gegenereerde CfX'en te beheren, gebruikt een scoringfunctie een balans tussen fidelity (vertrouwensverlies in de oorspronkelijke klasse) en verklaring grootte (aantal bewerkingen). Een vloeiende decay-functie straft grotere bewerkingssets af, waarbij de voorkeur wordt gegeven aan compacte en hoog-betrouwbare verklaringen zonder complexe restricties aan de optimalisatieloop zelf toe te voegen.

Sampling Strategie

Om efficiëntie te waarborgen, maakt het framework gebruik van een probabilistisch sampling-schema (gebaseerd op een Gaussian-achtige decay functie) om het aantal te verwijderen randen ( $r$ ) en toe te voegen randen ( $k$ ) te bepalen. Dit maakt domeinspecifieke afstemming mogelijk, waarbij doorgaans de voorkeur wordt gegeven aan minder verwijderingen (omdat de verwijdering van enkele kritieke randen al impactvol kan zijn) en meer flexibele aantallen toevoegingen.

Belangrijkste Bijdragen

Deconstructie/Reconstructie Methodologie: Een nieuwe pipeline die de taken van het verzwakken van de oorspronkelijke voorspelling en het versterken van de doelvoorspelling scheidt. Deze aanpak verbetert de prestaties voor in-distributie CfX-generatie en verhoogt aanzienlijk de compactheid en motif relevantie van de verklaringen.
Integratie van Link-voorspelling: De eerste studie die link-voorspellingsonderzoek expliciet koppelt aan GNN counterfactual explainability, waarbij gebruik wordt gemaakt van het vermogen van link-predictors om goed gerichte randplaatsingen op complexe grafen voor te stellen.
Efficiëntie en Controleerbaarheid: Het framework maakt afstemming mogelijk via sampling-parameters en domeinkennis-assertie, waardoor een hoge efficiëntie wordt bereikt zonder de prestaties op te offeren.
Uitgebreide Evaluatie: Het artikel presenteert de eerste veelzijdige vergelijkende studie van prominente lokale-niveau CF explainers (inclusclusief die randtoevoeging ondersteunen) over binaire en multi-label classificatietaken op zowel synthetische als real-world datasets.

Experimentele Resultaten

Het framework werd geëvalueerd op synthetische datasets (BA-Motifs), sentiment datasets (Graph-Twitter, Graph-SST5) en moleculaire datasets (BBBP).

Validiteit en Compactheid: DR-CFGNN varianten behaalden hoge validiteitsscores (vaak vergelijkbaar met globale baselines) terwijl ze aanzienlijk kleinere verklaringen genereerden. Zo behaalde het op de BBBP-dataset een validiteit van 0,81 met gemiddeld slechts 3 bewerkingen, terwijl baselines 3,5x tot 5,6x meer randen nodig hadden.
Motif Proximity: Het framework presteerde aanzienlijk beter dan de baselines op het gebied van motif proximity, wat betekent dat de voorgestelde bewerkingen geconcentreerd waren rond de grondwaarheid-motifs die verantwoordelijk zijn voor de oorspronkelijke voorspelling, in plaats van willekeurige verre bewerkingen.
Minimaliteit: DR-CFGNN behaalde uitzonderlijk hoge minimaliteitsscores (dicht bij 1,0), wat aangeeft dat de gegenereerde verklaringen alleen noodzakelijke bewerkingen bevatten en weinig redundante bewerkingen.
Robuustheid: Onder invloed van inputruis (rand/node perturbaties) vertoonde DR-CFGNN de meest consistente prestaties onder de lokale-niveau explainers, waarbij een hoge validiteit en structurele stabiliteit werd behouden (gemeten via Edge Consistency na Ruis).
Efficiëntie: Het framework vertoonde lage trainings- en inferentietijden vergeleken met diffusie-gebaseerde (D4Explainer) of exhaustieve zoekmethoden. De denoising-stap alleen al reduceerde de executietijd in sommige gevallen met wel 50%.

Betekenis en Claims

Het artikel beweert dat het completion-aware perspectief (integratie van link-voorspelling) cruciaal is voor het genereren van impactvolle counterfactuals. Door deconstructie en reconstructie te ontkoppelen, vermijdt het framework de valkuilen van end-to-end optimalisatie die vaak leidt tot OOD-bewerkingen of excessieve complexiteit.

De auteurs benadrukken dat hun aanpak een superieur evenwicht bereikt tussen coverage (validiteit), kwaliteit (fidelity, motif proximity, minimaliteit) en efficiëntie. Ze argumenteren dat hoewel een universeel best presterende aanpak moeilijk is vanwege de veelzijdige aard van het probleem, DR-CFGNN consequent zeer kwalitatieve, compacte en robuuste verklaringen produceert zonder complexe loss-functie engineering te vereisen. De studie onderstreept het belang van het beoordelen van diverse kwaliteitsmetrieken voorbij eenvoudige validiteit en suggereert dat toekomstig werk dit naar temporele grafen en neuro-symbolische AI kan uitbreiden voor formele verificatie.