Riepilogo Tecnico: Spiegazione delle Reti Neurali su Grafi per la Similarità tra Nodi nei Grafi

Definizione del Problema

Il lavoro affronta una lacuna critica nella spiegabilità delle Reti Neurali su Grafi (GNN). Sebbene esista una vasta ricerca sulla spiegazione delle GNN per compiti supervisionati (ad esempio, classificazione dei nodi, previsione dei collegamenti), il problema di spiegare la similarità tra nodi in contesti non supervisionati rimane largamente irrisolto. In molte applicazioni, come le reti di citazioni o i grafi della conoscenza, le GNN sono addestrate per apprendere embedding dei nodi in cui la similarità è calcolata tramite metriche come la similarità del coseno. A differenza delle etichette di classificazione discrete, la similarità è una quantità continua, e i protocolli di valutazione esistenti per la spiegabilità non sono direttamente applicabili. Gli autori indagano come attribuire valori agli archi in un grafo per spiegare perché due nodi specifici abbiano un punteggio di similarità alto o basso, distinguendo questo compito da quelli in cui l'obiettivo è giustificare una previsione discreta.

Metodologia

Quadro e Criteri

Gli autori propongono un quadro per valutare le spiegazioni della similarità tra nodi basato su tre criteri derivati da principi generali di Intelligenza Artificiale Spiegabile (XAI):

1. Azionabilità: Una spiegazione dovrebbe permettere interventi (ad esempio, aggiungere o rimuovere archi) che risultino in un cambiamento prevedibile del punteggio di similarità.
2. Coerenza: L'effetto del mantenimento degli archi al di sopra di una soglia di spiegazione deve essere distinto dall'effetto del loro scarto (cioè, il mantenimento degli archi al di sotto della soglia). I due insiemi di archi non dovrebbero produrre effetti sovrapposti o indistinguibili sul punteggio.
3. Sparsità: Una spiegazione dovrebbe essere comprimibile; un piccolo sottoinsieme degli archi più rilevanti dovrebbe mantenere la maggior parte dell'effetto esplicativo osservato nell'insieme completo.

Metriche Basate su Interventi

Per operationalizzare questi criteri, gli autori introducono metriche indipendenti dal modello e basate su interventi:

• Fedeltà ($Fid$): Misura il cambiamento nel punteggio di similarità dopo l'intervento sul grafo basato sulla spiegazione. Nello specifico, calcolano $Fid_a$ (cambiamento quando si mantengono gli archi al di sopra di una soglia) e $Fid_b$ (cambiamento quando si mantengono gli archi al di sotto della soglia).
• Sovrapposizione dell'Effetto (EO): Una metrica di similarità di Jaccard generalizzata che quantifica la sovrapposizione tra i segni dei valori di fedeltà per i due interventi. Un EO basso indica che i due interventi hanno effetti distinti e complementari (ad esempio, uno aumenta la similarità, l'altro la diminuisce), soddisfacendo il criterio di coerenza.
• Valutazione della Sparsità: Gli autori simulano livelli crescenti di sparsità rimuovendo gli archi meno rilevanti dalle maschere di spiegazione e rivalutando fedeltà ed EO. Una spiegazione robusta mantiene le sue proprietà azionabili e coerenti anche mentre il numero di archi viene ridotto.

Impostazione Sperimentale

Lo studio valuta due famiglie di metodi di spiegazione:

1. Metodi di Informazione Mutua (MI): Nello specifico, GNNExplainer, che cerca un sottografo che massimizzi l'informazione mutua con la previsione.
2. Metodi Basati su Gradiente (GB): Calcolo diretto del gradiente rispetto alla matrice di adiacenza e Gradienti Integrati.

Questi metodi sono applicati agli embedding dei nodi generati da quattro algoritmi di apprendimento non supervisionato: Autoencoder su Grafi (GAE), Variational Graph Autoencoders (VGAE), Deep Graph Infomax (DGI) e Graph Contrastive Representation Learning (GRACE). Gli esperimenti sono condotti su sei dataset: reti di citazioni (Cora, Citeseer, Pubmed), grafi eterofili (Chameleon, Squirrel, Actor) e un grafo della conoscenza (DBpedia50k).

Risultati Chiave

Gli esperimenti producono tre risultati principali riguardanti le prestazioni dei metodi GB rispetto ai metodi MI nel contesto della similarità tra nodi:

1. Azionabilità: Le spiegazioni basate su gradiente sono costantemente azionabili. Gli interventi basati sulle spiegazioni GB (mantenendo gli archi al di sopra della soglia) aumentano prevedibilmente il punteggio di similarità, mentre gli interventi basati sugli archi al di sotto della soglia lo diminuiscono prevedibilmente. Al contrario, GNNExplainer (MI) mostra un comportamento incoerente; l'effetto del mantenimento degli archi ad alto valore dipende spesso dal modello di embedding specifico e dal dataset, non riuscendo a produrre una direzione di cambiamento prevedibile in tutti gli scenari.
2. Coerenza: I metodi GB raggiungono punteggi di Sovrapposizione dell'Effetto (EO) significativamente più bassi (spesso vicini a 0 o < 0,1) rispetto ai metodi MI (spesso > 0,4 o > 0,5). Ciò indica che le spiegazioni GB distinguono chiaramente tra gli archi che aumentano la similarità e quelli che la diminuiscono. Le spiegazioni MI risultano frequentemente in effetti sovrapposti dove sia gli archi ad alto valore che quelli a basso valore producono cambiamenti simili nel punteggio, fallendo il criterio di coerenza.
3. Sparsità: Le proprietà azionabili e coerenti delle spiegazioni GB sono preservate anche quando la spiegazione viene potata per mantenere solo il 10% degli archi superiori (90% di sparsità). Ciò suggerisce che le spiegazioni GB possono essere semplificate significativamente senza perdere il loro potere esplicativo, mentre le spiegazioni MI non mostrano questa robustezza.

Gli autori notano inoltre che, sebbene i metodi MI mostrino talvolta un EO inferiore in casi specifici (ad esempio, DGI con GraphSAGE), ciò è spesso dovuto a effetti vicini allo zero (bassa azionabilità) piuttosto che a una vera coerenza. In tali regimi, la mancanza di un impatto significativo sul punteggio rende difficile la separazione basata sul segno per qualsiasi spiegatore.

Significato e Affermazioni

Il lavoro afferma di essere il primo a definire e valutare formalmente il problema della spiegazione della similarità tra nodi nelle GNN. Il suo significato risiede in:

• Colmare una Lacuna: Si sposta oltre il focus dominante sui compiti supervisionati per affrontare la spiegabilità dei punteggi di similarità continui e non supervisionati.
• Quadro di Valutazione: Fornisce un insieme di metriche quantitative basate su interventi (Fedeltà, EO, Sparsità) necessarie per valutare la qualità delle spiegazioni di similarità, che le metriche standard basate sulla classificazione non possono catturare.
• Insight Metodologico: I risultati dimostrano che i metodi basati su gradiente sono superiori ai metodi basati sull'informazione mutua per questo compito specifico. I metodi GB forniscono spiegazioni che non sono solo azionabili e coerenti, ma anche sparse, offrendo uno strumento più pratico e interpretabile per comprendere perché i nodi sono simili.
• Generalizzabilità: Le metriche proposte sono indipendenti dal modello e applicabili a qualsiasi funzione di similarità definita sugli embedding dei nodi (ad esempio, distanza euclidea), offrendo una base per lo sviluppo futuro di sistemi di ricerca per similarità spiegabili.

Gli autori concludono che, sebbene il costo computazionale sia un fattore (i metodi GB sono generalmente più efficienti dell'ottimizzazione iterativa richiesta dai metodi MI), il vantaggio principale dei metodi GB in questo contesto è la loro capacità di fornire spiegazioni affidabili, direzionali e sparse per la similarità tra nodi.