Riepilogo Tecnico: GRAPHLCP

Enunciato del Problema

Le Reti Neurali su Grafi (GNN) sono sempre più implementate in ambiti ad alto rischio come la scoperta di farmaci, la previsione meteorologica e il rilevamento delle frodi, rendendo necessaria una quantificazione affidabile dell'incertezza (UQ). La Predizione Conformale (CP) offre un framework privo di distribuzione per costruire previsioni a valore di insieme con garanzie su campioni finiti. Tuttavia, l'applicazione della CP alle GNN presenta sfide uniche:

1. Dipendenze Strutturali: I nodi nei grafi sono naturalmente dipendenti, violando le ipotesi standard di indipendenza e distribuzione identica (i.i.d.) richieste dalla CP classica.
2. Limitazioni delle Embedding: I metodi CP localizzati esistenti per i grafi spesso si basano sulla vicinanza nello spazio delle embedding (ad esempio, stima della densità del kernel sulle embedding delle GNN) per definire i vicini locali. Questo approccio è frequentemente inaffidabile a causa di:
   • Sovra-lisciatura (Over-smoothing): Il passaggio di messaggi profondo riduce la varianza delle misure di similarità, rendendo le embedding indistinguibili.
   • Sovra-accoppiamento (Over-squashing): I colli di bottiglia topologici limitano il flusso di informazioni globali, in particolare sotto eterofilia.
   • Sotto-confidenza: Le GNN spesso mostrano una separabilità insufficiente nelle rappresentazioni apprese.
3. Inefficienza delle Soluzioni Esistenti: I metodi CP specifici per grafi attuali si affidano o all'addestramento di modelli ausiliari (aumentando il sovraccarico computazionale) o utilizzano partizioni strutturali rigide (ad esempio, clustering rigido) che non riescono a catturare l'eterofilia locale fine. Di conseguenza, i metodi esistenti spesso producono insiemi di previsione eccessivamente conservativi o scarsamente localizzati in topologie complesse.

Metodologia: GRAPHLCP

Gli autori propongono GRAPHLCP, un framework di Predizione Conformale localizzata basato sulla vicinanza, progettato per incorporare esplicitamente la topologia del grafo e le dipendenze inter-nodo nei passaggi di localizzazione e ponderazione. Il metodo opera in un setting trasduttivo in cui la GNN è pre-addestrata e congelata. Il framework consta di quattro fasi chiave:

1. Densificazione Consapevole delle Feature

Per mitigare il bias di località nei grafi sparsi e catturare le dipendenze semantiche a lungo raggio, gli autori introducono un passaggio di densificazione precedente al calcolo del kernel.

• Proiezione PCA: Le embedding dei nodi vengono prima proiettate tramite Analisi delle Componenti Principali (PCA) per disaccoppiare le dimensioni delle feature correlate e condensare lo spazio, affrontando il rumore e la ridondanza causati dalla sovra-lisciatura.
• Kernel Anisotropo Adattivo: Viene costruito un kernel Gaussiano anisotropo utilizzando le embedding trasformate tramite PCA. La banda è adattata in base ai valori propri della matrice di covarianza per tenere conto delle diverse scale lungo le dimensioni.
• Augmentation degli Archi: Nuovi archi vengono aggiunti alla matrice di adiacenza del grafo se la similarità tra nodi non connessi (calcolata tramite il kernel Gaussiano) supera una soglia dinamica $\tau_d$. Questa soglia è sintonizzata automaticamente in base al rapporto di omofilia del grafo per bilanciare l'aggiunta di archi informativi contro l'introduzione di rumore.

2. Kernel PageRank Personalizzato (PPR)

Invece di affidarsi esclusivamente alle distanze delle embedding, GRAPHLCP utilizza il PPR per modellare la vicinanza strutturale.

• Localizzazione: Il PPR cattura l'influenza multi-hop mantenendo la località tramite una probabilità di riavvio ($\beta$). Fornisce una nozione morbida e probabilistica di vicinanza che si allinea naturalmente con la CP ponderata.
• Campionamento: Per un nodo di test, un nodo di ancoraggio viene campionato dalla distribuzione indotta dal PPR centrata sul nodo di test. Ciò garantisce che i nodi vicini esercitino una maggiore influenza sulla stima della quantile.
• Ponderazione: I nodi di calibrazione e di test sono ponderati in base alla loro vicinanza strutturale al nodo di ancoraggio campionato. Gli autori sfruttano la simmetria normalizzata per grado del PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) per calcolare i pesi in modo efficiente, anche quando il numero di campioni di calibrazione supera il numero di campioni di test.

3. Integrazione della Predizione Conformale Localizzata Randomizzata (RLCP)

GRAPHLCP adatta il framework RLCP. Campionando un nodo di ancoraggio $\tilde{u}_{n+1}$ dalla distribuzione PPR del nodo di test $u_{n+1}$, il metodo costruisce un insieme di previsione basato su una quantile ponderata dei punteggi di non-conformità. I pesi sono derivati dai punteggi PPR relativi all'ancoraggio campionato, consentendo al metodo di adattarsi al contesto locale del grafo.

4. Costruzione della Previsione

L'insieme di previsione finale $\hat{C}_n(u_{n+1})$ è costruito come l'insieme di etichette $y$ tali che il punteggio di non-conformità $s(u_{n+1}, y)$ sia inferiore o uguale a una quantile ponderata $\hat{q}_{1-\alpha}$. Questa quantile è calcolata utilizzando i pesi derivati dal kernel PPR e i punteggi di non-conformità dell'insieme di calibrazione.

Contributi Chiave

1. Localizzazione Consapevole della Struttura: Il documento colma il divario tra localizzazione strutturale e basata sulle feature sostituendo la vicinanza basata solo sulle embedding con un kernel basato sul PPR. Ciò incorpora esplicitamente la topologia del grafo nel processo di ponderazione conformale.
2. Densificazione Consapevole delle Feature: Un passaggio di pre-elaborazione innovativo che arricchisce la topologia del grafo utilizzando la similarità delle embedding (tramite PCA e kernel anisotropi adattivi) per mitigare la sparsità e catturare le dipendenze a lungo raggio senza affidarsi alla ponderazione continua potenzialmente rumorosa delle embedding.
3. Schema di Ponderazione Efficiente: Il metodo fornisce un modo efficiente per calcolare pesi basati sul PPR per grafi non orientati sfruttando la simmetria normalizzata per grado, evitando l'inefficienza computazionale del calcolo di vettori PPR completi per grandi insiemi di calibrazione.
4. Validità Teorica: L'approccio mantiene le garanzie di scambiabilità richieste per la copertura marginale in setting trasduttivi, mirando al contempo a migliorare la copertura condizionata al test rilassata.

Risultati Sperimentali

Gli autori hanno valutato GRAPHLCP su sette dataset di regressione su nodi e otto dataset di classificazione su nodi (inclusi reti di citazioni, acquisto condiviso su Amazon e dataset geografici).

• Copertura Marginale: Tutti i metodi, incluso GRAPHLCP, hanno soddisfatto il tasso di mancato copertura target ($\alpha = 0.1$), confermando la validità dell'approccio.
• Copertura Condizionata (WSC): Nei diagnostici Worst-Case Slab (WSC), che cercano avversariamente la copertura minima attraverso le direzioni di proiezione, GRAPHLCP ha ottenuto i risultati migliori o secondi migliori nella maggior parte dei dataset, superando le linee di base come CalLCP, RLCP e SCP.
• Copertura Basata su Gruppi: GRAPHLCP ha dimostrato una copertura superiore attraverso partizioni basate su omofilia, clustering delle feature, coefficiente di clustering e grado del nodo. Il metodo è stato particolarmente efficace nelle regioni eterofile dove i metodi standard faticavano.
• Efficienza della Previsione: Mentre CalLCP spesso produceva insiemi di previsione eccessivamente grandi (sovra-copertura), GRAPHLCP ha raggiunto lunghezze di previsione normalizzate favorevoli, offrendo un migliore compromesso tra copertura e dimensione dell'insieme.
• Studi di Ablazione:
  • Sostituire il kernel PPR con un kernel Gaussiano (GSS) ha portato a una copertura inferiore e a insiemi di previsione più grandi, confermando l'importanza della localizzazione consapevole della struttura.
  • Il passaggio di densificazione è stato identificato come il componente più significativo, in particolare per le attività di regressione.
  • La proiezione PCA si è rivelata cruciale per mitigare gli effetti negativi delle feature delle embedding correlate.

Significato e Affermazioni

Il documento afferma che GRAPHLCP affronta con successo le limitazioni dei metodi CP per grafi esistenti modellando esplicitamente le dipendenze strutturali. Disaccoppiando i pesi dai codificatori GNN potenzialmente perdenti e utilizzando un kernel basato sul PPR, il metodo crea un "percorso residuo a basso rumore" per la quantificazione dell'incertezza.

Gli autori affermano che GRAPHLCP garantisce la copertura marginale con campioni finiti, ottenendo al contempo in modo efficiente una copertura condizionata al test favorevole attraverso vari scenari di condizionamento. Sottolineano che il metodo è particolarmente robusto in topologie complesse dove le similarità basate sulle embedding falliscono a causa di sovra-lisciatura o sovra-accoppiamento. Il lavoro sottolinea la necessità di una localizzazione consapevole della struttura per una UQ efficace sui grafi, andando oltre la sola dipendenza dalla vicinanza nello spazio delle feature. Gli autori notano modestamente che le direzioni future includono l'estensione di questo framework a grafi dinamici con topologie in evoluzione.