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

Il paper presenta XPlore, un nuovo metodo basato su gradienti che amplia lo spazio di ricerca delle spiegazioni controfattuali per le Graph Neural Networks permettendo non solo la rimozione ma anche l'inserimento di archi e la modifica delle caratteristiche dei nodi, ottenendo risultati significativamente migliori in termini di validità e fedeltà rispetto alle tecniche esistenti.

L'essenziale

Immagina di avere una scatola nera magica (una Rete Neurale su Grafi, o GNN) che ti dice se una molecola è velenosa o se un post su Twitter è una truffa. Questa scatola è bravissima a fare previsioni, ma è muta: non ti spiega perché ha preso quella decisione. È come se un medico ti dicesse: "Hai la febbre, prendi questo farmaco" senza spiegarti quale sintomo l'ha fatto pensare.

In campi critici come la medicina o la finanza, non possiamo permetterci di fidarci ciecamente di una scatola nera. Dobbiamo capire il "perché".

Ecco dove entra in gioco questo paper, che presenta XPlore, un nuovo metodo per aprire quella scatola e vedere cosa c'è dentro.

Il Problema: I vecchi metodi erano come "forbici"

Fino a poco tempo fa, i metodi per spiegare queste decisioni funzionavano un po' come delle forbici. Se la scatola nera diceva "Questa molecola è velenosa", il metodo provava a tagliare dei legami (rimuovere connessioni tra gli atomi) per vedere se, togliendo qualcosa, la molecola diventava innocua.

Il problema? A volte, per cambiare la decisione della scatola nera, non basta togliere qualcosa. A volte bisogna aggiungere un nuovo legame o cambiare la natura di un atomo. Le vecchie "forbici" non potevano fare questo: potevano solo tagliare.

La Soluzione: XPlore è un "Kit di Modellazione"

XPlore è come un kit di modellazione completo invece di un semplice paio di forbici. Non si limita a tagliare; può:

1. Tagliare i legami esistenti (rimuovere connessioni).
2. Incollare nuovi legami (aggiungere connessioni che prima non c'erano).
3. Cambiare colore agli oggetti (modificare le caratteristiche dei nodi, come cambiare un atomo da neutro a positivo).

L'Analogia del Detective:
Immagina che la scatola nera sia un detective che ha arrestato un sospettato (la molecola velenosa).

• I vecchi metodi chiedevano: "Se togliamo il coltello dalla tasca del sospettato, è ancora colpevole?" (Solo rimozione).
• XPlore chiede: "E se gli mettessimo in tasca un passaporto falso? O se gli togliessimo il cappello e gli mettessimo una parrucca? O se gli dessimo un nuovo amico che lo accompagna?" (Aggiunta e modifica).

XPlore prova tutte queste combinazioni per trovare la modifica minima necessaria per far cambiare idea al detective. Se togliendo un solo legame la molecola diventa innocua, XPlore te lo dice. Ma se serve aggiungere un legame per renderla innocua, XPlore lo fa, mentre gli altri metodi fallirebbero.

Come funziona? (La "Bussola" Matematica)

XPlore non indovina a caso. Usa una bussola matematica (chiamata gradiente) che gli dice esattamente in quale direzione muovere i pezzi del puzzle per cambiare la previsione con il minimo sforzo possibile.
È come se avessi una mappa che ti dice: "Per arrivare alla porta dell'uscita (la nuova previsione), devi spostare questo mattoncino di un millimetro a destra e incollare un altro qui".

Perché è importante?

1. È più onesto: Trova spiegazioni che hanno senso nel mondo reale. Ad esempio, in chimica, a volte per rendere una molecola sicura non devi togliere un pezzo, ma aggiungerne uno per bilanciare la carica. XPlore lo capisce, gli altri no.
2. È preciso: Ha dimostrato su 13 diversi tipi di dati (dai farmaci ai social network) di essere molto più bravo a trovare queste spiegazioni "minime e giuste" rispetto alle tecnologie attuali.
3. Non crea mostri: A volte, i metodi vecchi creavano spiegazioni che erano tecnicamente corrette ma che assomigliavano a mostri impossibili (fuori distribuzione). XPlore cerca di mantenere le spiegazioni "naturali", simili a cose che potrebbero esistere davvero.

In sintesi

Il paper ci dice che per capire le intelligenze artificiali complesse, non basta guardare cosa togliere. Dobbiamo avere la libertà di aggiungere e modificare tutto ciò che serve. XPlore è lo strumento che ci dà questa libertà, rendendo le decisioni delle macchine più trasparenti, affidabili e comprensibili per noi umani.

È come passare dal dire "Non so perché, ma tagliando qui funziona" a dire "Ecco esattamente come e perché, modificando anche un piccolo dettaglio, la situazione cambia completamente".

Sommario tecnico

1. Il Problema

Le Reti Neurali su Grafi (GNN) sono sempre più utilizzate in settori critici come la biologia molecolare, l'analisi delle reti sociali e la rilevazione di frodi finanziarie. Tuttavia, la loro natura di "scatola nera" limita l'interpretabilità e la fiducia, specialmente in applicazioni ad alto rischio dove sono necessarie spiegazioni trasparenti.

Le spiegazioni controfattuali (Counterfactual Explanations - CF) offrono una soluzione: identificano le modifiche minime necessarie all'input per cambiare la previsione del modello.
Il problema principale affrontato da questo lavoro è che la maggior parte dei metodi esistenti per le GNN si concentra esclusivamente sulla cancellazione di archi (edge deletion). Questo approccio è limitante perché:

• Non permette di aggiungere nuovi archi, che potrebbero essere necessari per cambiare la classe di un grafo (es. creare un ciclo in una struttura molecolare).
• Ignora le perturbazioni delle caratteristiche dei nodi (node features), che sono cruciali in molti domini (es. cambiare la carica di un atomo in una molecola).
• Spesso genera esempi controfattuali che cadono fuori dalla distribuzione dei dati (Out-of-Distribution - OOD), rendendo le spiegazioni inaffidabili o fuorvianti.

2. Metodologia: XPlore

Gli autori introducono XPlore, un nuovo framework per la generazione di spiegazioni controfattuali che amplia significativamente lo spazio di ricerca rispetto ai metodi precedenti (come CF-GNNExpl).

A. Spazio di Perturbazione Completo

A differenza dei metodi basati solo sulla rimozione di archi, XPlore permette tre tipi di modifiche simultanee:

1. Rimozione di archi (Edge deletion).
2. Inserimento di archi (Edge insertion): Permette di aggiungere connessioni mancanti, essenziale per grafi dove la struttura deve essere arricchita per cambiare la classe.
3. Perturbazione delle caratteristiche dei nodi (Node-feature perturbations): Le caratteristiche possono essere modificate in modo continuo o tramite un meccanismo di "gating" (mascheramento binario).

B. Ottimizzazione Guidata dal Gradiente

Il metodo tratta la GNN target come un "oracolo" fisso. Utilizza un approccio basato su gradienti per ottimizzare direttamente le matrici di perturbazione:

• Matrice di Adiacenza ($\bar{P}$): Invece di iniziare con la matrice di adiacenza originale e cancellare archi, XPlore inizializza una matrice di perturbazione che può essere aggiornata liberamente. Permette l'inserimento di archi invertendo il ruolo della matrice di adiacenza originale e permettendo al gradiente di "accendere" le connessioni mancanti.
• Matrice delle Caratteristiche ($\bar{N}$): Una matrice continua che modula i valori delle feature dei nodi.
• Funzione di Loss: L'obiettivo è minimizzare una funzione di perdita composta da:
  • $L_{pred}$: Una perdita di previsione che incoraggia il cambiamento di classe ($\Phi(G) \neq \Phi(G')$).
  • $L_{dist}$: Una perdita di distanza che penalizza le modifiche eccessive, promuovendo la somiglianza tra il grafo originale e quello controfattuale.

C. Gestione dei Grafi e Thresholding

Per gestire la natura discreta degli archi (0 o 1) durante l'ottimizzazione continua, XPlore utilizza un Stima del Gradiente Rettilineo (Straight-Through Estimator - STE). Questo permette di calcolare i gradienti attraverso la funzione di soglia non differenziabile (sigmoid + threshold), trattando la binarizzazione come identità durante la backpropagation.

D. Nuova Metrica di Valutazione: Similarità Cosine

Per affrontare il problema OOD, gli autori introducono una metrica basata sulla Similarità Cosine (CS) tra gli embedding appresi dei grafi originali e quelli controfattuali. A differenza della distanza di edit (GED) che misura solo le modifiche strutturali, la CS valuta la coerenza semantica, assicurando che il grafo modificato rimanga vicino alla distribuzione della classe target.

3. Contributi Chiave

1. Perturbazione Completa dell'Input: Il primo framework che supporta nativamente l'aggiunta di archi, la rimozione di archi e la modifica delle feature dei nodi in un unico quadro unificato.
2. Ottimizzazione Guidata dal Gradiente: Un approccio che trova i controfattuali più vicini nel paesaggio di ottimizzazione della loss, garantendo che le modifiche siano minime e coerenti con i confini decisionali dell'oracolo.
3. Mitigazione degli Effetti OOD: L'uso combinato di inserimento di archi e perturbazione delle feature, insieme alla metrica di similarità cosine, riduce la generazione di esempi fuori distribuzione rispetto ai metodi basati solo su cancellazione.
4. Performance Empirica: Validazione su 13 dataset reali e 5 sintetici, dimostrando superiorità rispetto allo stato dell'arte (SoTA).

4. Risultati Sperimentali

Il paper presenta risultati su 18 dataset (inclusi MUTAG, ENZYMES, COLLAB, TCR, ecc.) confrontando XPlore con metodi SoTA come CF-GNNExpl, CF2, CLEAR, RSGG-CE e D4Explainer.

• Validità: XPlore raggiunge un 100% di validità in molti dataset (es. TCR, TG, BAS, COLORS-3) e supera i baselines in 17 su 18 dataset. In media, mostra un miglioramento del +56.3% nella validità rispetto ai metodi precedenti.
• Fedeltà (Fidelity): Il metodo produce spiegazioni più fedeli alla decisione reale del modello, con un miglioramento medio del +52.8%.
• Efficienza: XPlore mantiene un tempo di esecuzione competitivo, richiedendo un numero di chiamate all'oracolo inferiore rispetto a molti metodi basati su ricerca o generativi.
• Analisi Semantica: Le proiezioni t-SNE mostrano che i controfattuali generati da XPlore si posizionano correttamente nella distribuzione della classe target (es. nella distribuzione "Ciclo" per il dataset Tree-Cycle), mentre altri metodi spesso falliscono o rimangono nella distribuzione originale, sfruttando effetti OOD.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo avanti fondamentale nell'interpretabilità delle GNN.

• Superamento dei Limiti Strutturali: Dimostra che limitarsi a cancellare archi è insufficiente per spiegare decisioni complesse su grafi; la capacità di aggiungere connessioni e modificare attributi è essenziale per una spiegazione completa.
• Affidabilità: Riducendo gli effetti OOD, XPlore fornisce spiegazioni che sono non solo tecnicamente corrette (cambiano la previsione) ma anche semanticamente plausibili e robuste.
• Generalità: Essendo un metodo basato su gradienti che non richiede modelli surrogati o addestramento aggiuntivo, XPlore è leggero, veloce e applicabile a qualsiasi GNN pre-addestrata.

In sintesi, XPlore trasforma la spiegazione controfattuale da un esercizio di "rimozione" a un processo di "ricostruzione" flessibile, offrendo agli utenti una visione più chiara e affidabile del comportamento delle reti neurali su grafi.