AbstainGNN: Teaching Graph Neural Networks to Abstain for Graph Classification

Sintesi Tecnica: AbstainGNN

Definizione del Problema

La classificazione dei grafi è un compito fondamentale nel data mining di grafi con applicazioni nella predizione delle proprietà molecolari, nell'analisi dei materiali e nell'analisi delle reti sociali. Sebbene le Graph Neural Networks (GNN) abbiano ottenuto miglioramenti significativi nelle prestazioni, esse soffrono di un limite critico: sono tipicamente costrette a effettuare predizioni anche in condizioni di alta incertezza, evidenza strutturale ambigua o debole separazione delle classi. In domini critici per la sicurezza (ad esempio, la scoperta di farmaci o la valutazione del rischio finanziario), tali decisioni forzate possono portare a gravi errori a valle.

I metodi esistenti di "Apprendimento con Astensione" (o classificazione con rifiuto), che permettono ai modelli di differire le predizioni incerte a esperti umani, sono stati sviluppati principalmente per la computer vision. Questi metodi spesso non riescono a catturare la ricca informazione topologica e relazionale inerente ai dati strutturati a grafo. Inoltre, la maggior parte degli approcci esistenti si basa su progettazioni euristiche prive di una solida base teorica specificamente per i domini dei grafi, ostacolando lo sviluppo di meccanismi di astensione basati su principi per la classificazione dei grafi.

Metodologia

Gli autori propongono AbstainGNN, un nuovo framework guidato dalla teoria che equipaggia esplicitamente le GNN con la capacità di astenersi dal fare predizioni su campioni di grafi incerti. Il framework consiste in due componenti primarie: una funzione predittiva $f$ per la classificazione e una funzione di astensione $g$ per determinare se predire o rifiutare.

Fondamento Teorico

Il nucleo di AbstainGNN deriva da una prospettiva di generalizzazione PAC-Bayesiana. Gli autori caratterizzano teoricamente il compromesso tra errori di classificazione e costi di rifiuto.

• Limite di Generalizzazione: Il Teorema 4.1 stabilisce che le prestazioni di generalizzazione di AbstainGNN sono limitate superiormente dalla perdita empirica basata sul margine e dalla varianza intra-classe delle rappresentazioni a livello di grafo.
• Insight Chiave: Minimizzare la varianza intra-classe delle rappresentazioni a livello di grafo è cruciale per migliorare le prestazioni nella classificazione dei grafi con astensione.

Obiettivo di Apprendimento

Sulla base dell'analisi teorica, gli autori derivano un obiettivo di apprendimento unificato:
$$\mathcal{L}_{total} = \mathcal{L}_{ce} + \lambda_r \mathcal{L}_{icv}$$
Dove $\mathcal{L}_{ce}$ è la standard cross-entropy loss, e $\mathcal{L}_{icv}$ è una nuova loss di regolarizzazione progettata per ridurre la varianza intra-classe delle rappresentazioni a livello di grafo. L'analisi teorica (Teorema 4.2) dimostra che minimizzare questo obiettivo porta a una contrazione della varianza intra-classe, restringendo il limite di generalizzazione.

Strategia di Implementazione

Per ottimizzare questo obiettivo in modo efficiente, AbstainGNN impiega una strategia di addestramento in due fasi:

1. Warm-start della Funzione Predittiva: La funzione predittiva $f$ viene pre-addestrata utilizzando solo $\mathcal{L}_{ce}$ per spingere il modello in una regione a gradiente ridotto. Ciò stabilizza il processo di ottimizzazione prima di introdurre la regolarizzazione della varianza.
2. Calibrazione della Funzione di Astensione:
   • Regolazione dei Cluster Globali: Per mitigare il bias di stima causato dagli aggiornamenti per batch, il modello mantiene cluster di classe globali ($\mu_y$) durante l'addestramento tramite una strategia di media mobile. Ciò garantisce una stima accurata della varianza intra-classe.
   • Calibrazione: La funzione di astensione $g$ (implementata come GNN) è addestrata per predire se l'output della funzione predittiva $f$ sia corretto. Questo trasforma la calibrazione della confidenza in un compito di classificazione binaria, allineando i punteggi di confidenza con l'accuratezza della predizione.

Contributi Chiave

1. Definizione del Problema: Questo lavoro è il primo a investigare il problema della classificazione dei grafi con astensione, consentendo alle GNN di rifiutare campioni di grafi incerti o sconosciuti per migliorare l'affidabilità nei domini critici per la sicurezza.
2. Analisi Teorica: Gli autori derivano limiti di generalizzazione PAC-Bayesiani per AbstainGNN, rivelando che minimizzare la varianza intra-classe è teoricamente necessario per un'efficace astensione. Ciò porta a un obiettivo di apprendimento unificato.
3. Implementazione del Modello: Guidati dalla teoria, gli autori sviluppano un'implementazione efficiente caratterizzata da una strategia di addestramento in due fasi e un meccanismo di regolazione dei cluster di classe globale per alleviare il bias di stima.
4. Verifica Sperimentale: Esperimenti esaustivi su cinque dataset benchmark del mondo reale dimostrano la superiorità del metodo rispetto ai baseline di astensione esistenti.

Risultati Sperimentali

Gli autori hanno valutato AbstainGంNN su cinque dataset benchmark: PROTEINS, MUTAG, NCI1 (grafi chimici), e IMDB-BINARY, COLLAB (grafi sociali). Hanno confrontato il modello con baseline allo stato dell'arte tra cui SR, MC-Dropout, Deep Gamblers, SAT, CCL-SC, NCwR e GraphPPD.

• Prestazioni: AbstainGNN ha superato costantemente i metodi esistenti in tutti i dataset e i livelli di copertura.
• Riduzione del Rischio: Sotto lo stesso tasso di rifiuto, il modello ha ottenuto riduzioni del rischio relativo significative:
  • 16.8% su MUTAG
  • 15.8% su IMDB-BINARY
  • 9.8% su PROTEINS
  • 5.9% su COLLAB
  • 4.8% su NCI1
• Studi di Ablazione: Rimuovere la strategia di warm-start o la regolarizzazione della varianza intra-classe ($\mathcal{L}_{icv}$) ha costantemente degradato le prestazioni, confermando la necessità di entrambi i componenti.
• Efficienza: L'analisi del tempo di esecuzione ha mostrato che AbstainGNN comporta solo un carico computazionale moderato rispetto ai baseline, mantenendo un equilibrio accettabile tra efficacia ed efficienza.

Significato e Rivendicazioni

Il paper sostiene che AbstainGNN affronti una lacuna significativa nel data mining di grafi fornendo il primo framework basato su principi per la classificazione dei grafi con astensione. Passando da progettazioni euristiche ad un approccio guidato dalla teoria basato sui limiti di generalizzazione, il metodo offre un meccanismo di decisione più affidabile per le GNN. Gli autori sottolineano che il loro approccio è particolarmente prezioso per le applicazioni critiche per la sicurezza dove il costo di una decisione errata supera il costo dell'astensione. Il lavoro valida che la modellazione esplicita dell'informazione strutturale del grafo e la riduzione della varianza intra-classe sono chiavi per ottenere migliori compromessi tra copertura e rischio nei compiti di classificazione dei grafi.