Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Il paper propone un framework di previsione conformale per output strutturati a grafo, che utilizza la distanza Z-Gromov-Wasserstein e una variante adattiva della regressione quantilica (SCQR) per fornire garanzie di copertura senza distribuzione, come dimostrato nei compiti di identificazione molecolare.

L'essenziale

Immagina di essere un detective che deve identificare un sospetto basandosi su una foto sfocata. Nel mondo dell'intelligenza artificiale, questo è il problema della predizione di grafi: l'AI deve trasformare un'immagine, un testo o un segnale (come uno spettro di massa chimica) in una struttura complessa chiamata "grafo" (una rete di nodi e collegamenti, come una mappa di relazioni o la struttura di una molecola).

Il problema? Spesso l'AI è sicura di sé, ma sbaglia. E in campi come la chimica o la medicina, sbagliare costa caro. Finora, l'AI ci dava una sola risposta: "È questa molecola". Ma non ci diceva: "Sono sicuro al 90% che sia questa, ma c'è anche il 10% di probabilità che sia quella lì".

Questo articolo propone un nuovo metodo per dare all'AI un "senso di incertezza" onesto e matematicamente garantito. Ecco come funziona, spiegato con metafore semplici.

1. Il Problema: L'AI che non sa quando è confusa

Immagina di dover riconoscere un volto in una folla. Se l'AI ti dice "È Mario", ma in realtà è Luigi, hai un problema.
Nel caso dei grafi (come le molecole), il problema è ancora più difficile perché i nodi (gli atomi) non hanno nomi fissi. Se cambi l'ordine in cui li scrivi, è sempre la stessa molecola, ma per un computer sono dati diversi. È come se avessi una ricetta scritta in ordine diverso: è sempre la stessa torta, ma sembra diversa.

2. La Soluzione: Il "Cerchio di Sicurezza" (Conformal Prediction)

Invece di dare una sola risposta, il nuovo metodo disegna un cerchio di sicurezza attorno alla risposta.

• L'idea: "Non ti dico solo che è la Molecola A. Ti dico che la risposta corretta è sicuramente dentro questo gruppo di 5 molecole simili".
• La garanzia: Il metodo promette: "Se chiedi questo cerchio al 90%, il 90% delle volte la risposta vera sarà dentro quel gruppo". È come un ombrello: se lo apri al 90%, ti bagna solo il 10% delle volte, anche se non sai se sta per piovere o no.

3. Il Righello Magico: La Distanza Z-Gromov-Wasserstein

Come fa l'AI a sapere quali molecole mettere nel "cerchio di sicurezza"? Deve misurare quanto una molecola candidata è "diversa" da quella che l'AI ha previsto.
Qui entra in gioco la distanza Z-Gromov-Wasserstein.

• L'analogia: Immagina di dover confrontare due città. Una è disegnata su un foglio di gomma, l'altra su un foglio rigido. Hanno strade e piazze diverse, ma la struttura è simile. Un righello normale non funziona perché le strade non sono allineate.
• La soluzione: Questo "righello magico" (la distanza Z-GW) è come un elastico intelligente. Riesce a deformare una città per adattarla all'altra, confrontando non solo le strade, ma anche come sono collegate tra loro e cosa c'è sopra (gli edifici, i colori). In questo modo, può dire: "Queste due molecole sono quasi identiche, anche se i loro atomi sono etichettati in ordine diverso".

4. L'Adattamento Intelligente: SCQR

Il metodo originale usa una regola fissa per tutti: "Se la differenza è maggiore di X, metti la molecola nel cerchio". Ma non tutte le domande sono uguali!

• L'analogia: È come chiedere a un guardiano di sicurezza: "Chi entra?". Se la domanda è facile (un volto chiaro), il guardiano dovrebbe essere severo e far entrare poche persone. Se la domanda è difficile (una foto sfocata), il guardiano dovrebbe essere più permissivo e far entrare più candidati per non perdere il colpevole.
• SCQR (Score Conformalized Quantile Regression): È il guardiano intelligente. Analizza la difficoltà del caso specifico.
  • Se l'immagine è chiara, restringe il cerchio (dà una risposta più precisa).
  • Se l'immagine è confusa, allarga il cerchio (dà più opzioni per essere sicuro di non sbagliare).
  • In questo modo, non spreca tempo con liste lunghe quando non serve, e non rischia di escludere la risposta giusta quando serve.

5. I Risultati: Chimica e Immagini

Gli autori hanno testato questo sistema su due fronti:

1. Un gioco sintetico: Ricostruire un grafo colorato da un'immagine. Qui il sistema ha funzionato benissimo, riducendo drasticamente il numero di opzioni da controllare.
2. Identificazione di molecole (Metaboliti): Questo è il caso reale. Dato uno spettro di massa (come un'impronta digitale chimica), l'AI deve indovinare quale molecola è. Usando il loro metodo, sono riusciti a ridurre la lista di candidati da centinaia a poche decine, mantenendo la certezza che la molecola giusta fosse sempre nella lista.

In Sintesi

Questo articolo ci insegna come rendere l'Intelligenza Artificiale più umile e affidabile. Invece di dire "So la risposta", dice "Ecco le opzioni più probabili, e ti garantisco che la risposta vera è qui dentro con una probabilità del 90%".

Grazie a un "righello magico" che confronta strutture complesse senza farsi ingannare dall'ordine dei pezzi, e a un sistema che si adatta alla difficoltà del compito, possiamo usare l'AI per scoprire nuove medicine o molecole con meno rischi di errore. È come passare da un tiro alla cieca a un tiro con un mirino che si regola da solo.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Conformal Graph Prediction with Z-Gromov Wasserstein Distances", presentata in italiano.

1. Il Problema: Predizione di Grafi e Incertezza

Il lavoro si concentra sulla Predizione Supervisionata di Grafi (SGP), un compito in cui un modello apprende a mappare input di qualsiasi modalità (testo, immagini, spettri) a grafi target strutturati di dimensione arbitraria. Applicazioni chiave includono l'identificazione di molecole (chimica) e la comprensione delle scene (visione artificiale).

Il problema centrale affrontato è la quantificazione dell'incertezza. Sebbene esistano metodi per la predizione di grafi, la maggior parte fornisce una singola previsione puntuale senza garantire la fiducia statistica. In contesti critici come la scoperta di farmaci, dove la validazione sperimentale è costosa, è fondamentale fornire all'utente un insieme di grafi plausibili (insieme di previsione) che contenga il vero grafo target con una probabilità garantita, piuttosto che una singola risposta.

Le sfide specifiche per i grafi includono:

• Lo spazio di output è non euclideo, altamente strutturato e combinatorio.
• I grafi sono definiti a meno di una permutazione dei nodi (l'etichettatura dei nodi è arbitraria), rendendo difficile definire metriche di errore standard.
• L'incertezza può variare notevolmente a seconda dell'input (eteroscedasticità), rendendo inadeguati i metodi che usano una soglia globale fissa.

2. Metodologia Proposta

Gli autori propongono un framework di Conformal Prediction (CP) adattato agli spazi di output grafici, basato su due pilastri principali:

A. Metrica di Non-Conformità: Distanza Z-Gromov-Wasserstein (Z-GW)

Per misurare la discrepanza tra un grafo predetto e un grafo candidato in modo invariante rispetto alla permutazione dei nodi, il paper utilizza la distanza Z-Gromov-Wasserstein.

• Concetto: I grafi sono modellati come Z-networks (spazi metrici misurabili con relazioni a coppie). La distanza Z-GW generalizza la classica Gromov-Wasserstein (GW) e la Fused Gromov-Wasserstein (FGW), permettendo di confrontare sia la struttura del grafo che le attribuzioni dei nodi e degli archi.
• Invarianza: La distanza è definita sullo spazio quoziente dei grafi (dove grafi isomorfi sono identificati), garantendo che il punteggio di non-conformità sia indipendente dal modo in cui i nodi sono etichettati.
• Implementazione Pratica: Viene utilizzata la Fused Gromov-Wasserstein (FGW), che combina informazioni strutturali (es. matrice di adiacenza o Laplaciano) e feature dei nodi/archi.

B. Adattatività Locale: Score Conformalized Quantile Regression (SCQR)

La CP standard utilizza una soglia globale calibrata su tutto il dataset, il che può portare a insiemi di previsione troppo conservativi per input facili e insufficienti per input difficili.

• Soluzione: Viene introdotto SCQR, un'estensione della Conformalized Quantile Regression (CQR).
• Funzionamento: Invece di calcolare un quantile globale dei residui, SCQR modella i quantili condizionati del punteggio di non-conformità in funzione di attributi specifici dell'input (es. la dimensione dell'insieme candidato o embedding spettrali).
• Vantaggio: Questo permette di generare insiemi di previsione adattivi: più piccoli per input facili e più ampi per input ambigui, mantenendo comunque la garanzia di copertura marginale.

3. Contributi Chiave

1. Framework Teorico: Definizione di un framework di Conformal Prediction per output a grafi basato su distanze Z-GW, con dimostrazione formale della validità (garanzia di copertura) nello spazio quoziente dei grafi.
2. SCQR per Grafi: Introduzione di un metodo di regressione quantilica adattivo specifico per spazi di output strutturati complessi, che supera i limiti delle soglie globali.
3. Validazione Empirica: Sperimentazione su due task distinti:
   • Un task sintetico "Image-to-Graph" (Coloring).
   • Un problema reale di identificazione di metaboliti da spettri di massa (MassSpecGym), dove l'obiettivo è recuperare la struttura molecolare corretta da una libreria di candidati.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti con un livello di copertura nominale del 90% ($1-\alpha = 0.9$).

• Validità della Copertura: Sia il metodo CP standard che SCQR hanno raggiunto una copertura empirica vicina al 90% (es. 89.0% - 90.3%), confermando la validità teorica del framework basato su Z-GW.
• Efficienza (Dimensione dell'Insieme):
  • Nel task sintetico (Coloring), SCQR ha mostrato prestazioni simili alla CP standard, riducendo la dimensione media dell'insieme di previsione di oltre il 95% rispetto alla libreria candidata.
  • Nel task reale (Metaboliti), SCQR ha dimostrato un vantaggio significativo. Condizionando la soglia sull'embedding spettrale (DREAMS), la dimensione media dell'insieme di previsione è scesa da 24 (CP standard) a 15, con una riduzione della libreria candidata dell'84.8% (contro il 77.1% della CP), mantenendo la copertura valida.
• Robustezza: L'uso di FGW con diverse inizializzazioni e matrici di costo (es. Laplaciano vs Adiacenza) ha mostrato che l'inclusione delle feature dei nodi riduce l'incertezza rispetto all'uso della sola struttura (GW pura).

5. Significato e Impatto

Questo lavoro è significativo perché:

• Colma un vuoto teorico: Fornisce per la prima volta garanzie di copertura distributive-free per la predizione di grafi, un problema aperto a causa della complessità combinatoria e dell'invarianza di permutazione.
• Praticità per la Scienza: Nel contesto dell'identificazione di molecole, ridurre la dimensione dell'insieme di candidati da centinaia a poche decine di molecole senza perdere la molecola corretta può accelerare drasticamente il processo di scoperta e ridurre i costi di validazione di laboratorio.
• Generalizzabilità: Il framework basato su Z-networks e Z-GW non è limitato ai grafi, ma può essere esteso ad altri spazi strutturati come mesh, nuvole di punti e distribuzioni, offrendo un approccio geometrico unificato per la quantificazione dell'incertezza nella predizione strutturata.

In sintesi, il paper combina geometria ottimale (Z-GW) e statistica conformale avanzata (SCQR) per creare strumenti di predizione affidabili ed efficienti per dati strutturati complessi.