Invariant Graph Representations for Continuous-Time Dynamic Graphs Under Distribution Shifts

Sintesi Tecnica: CIR per Rappresentazioni Invarianti in Grafi Dinamici a Tempo Continuo

Formulazione del Problema
I grafi dinamici a tempo continuo (CTDG) modellano sistemi relazionali in evoluzione in cui nodi e archi vengono aggiunti o rimossi in punti temporali arbitrari, catturando cambiamenti strutturali e temporali granulari. Sebbene i metodi esistenti di apprendimento delle rappresentazioni per i CTDG abbiano ottenuto successi in contesti in-distribuzione, essi mostrano una robustezza limitata sotto spostamenti fuori distribuzione (OOD). Nello specifico, i modelli standard spesso sfruttano correlazioni spurie — come pattern temporali specifici o motivi strutturali che appaiono frequentemente nei dati di addestramento ma che non sono causalmente legati all'interazione target. Quando queste correlazioni cambiano negli ambienti di test (ad esempio, a causa di cambiamenti nel processo di generazione dei dati sottostante), le prestazioni del modello degradano significativamente.

La sfida centrale affrontata in questo lavoro è la scarsità di metodi capaci di apprendere rappresentazioni invarianti per i CTDG sotto spostamenti OOD. Gli approcci causali esistenti, che si basano su modelli causali strutturali (SCM) e interventi, sono progettati principalmente per grafi statici o a tempo discreto. L'applicazione di questi ai CTDG è computazionalmente proibitiva a causa dell'esplosione combinatoria di possibili sottografi strutturali e temporali, rendendo inefficace l'intervento esaustivo.

Metodologia: Il Framework CIR
Per affrontare queste sfide, gli autori propongono CIR (Continuous-time Invariant Representation), un framework basato su un nuovo Modello Causale Strutturale (SCM) denominato Modello Causale Indipendente e Confuso (ICCM).

1. Il Framework ICCM:
   L'ICCM modella esplicitamente i meccanismi causali nei CTDG distinguendo tra:

   • Sottografi Causali Invarianti: $C_s$ (strutturale) e $C_t$ (temporale), che sono codificati in rappresentazioni latenti $H_S$ e $H_T$.
   • Confonditori: Strutturali ($D_s$) e temporali ($D_t$) che introducono correlazioni spurie, particolarmente negli ambienti OOD.
   • Meccanismi di Predizione: Il modello definisce una predizione in-distribuzione $Y^I$ basata esclusivamente su caratteristiche invarianti, e una predizione OOD $Y^C$ che tiene conto dei confonditori. L'obiettivo è eseguire interventi causali (usando l'operazione $do$ di Pearl) per bloccare i percorsi di backdoor indotti dai confonditori, isolando così l'effetto causale invariante.

2. Intervento Efficiente tramite NWGM:
   Intervenire direttamente su tutti i possibili sottografi strutturali e temporali è computazionalmente intrattabile. Per superare questo limite, CIR sfrutta l'approssimazione della Media Geometrica Pesata Normalizzata (NWGM). Questa tecnica consente al modello di approssimare efficientemente l'esito interventistico atteso spostando l'operatore di aspettativa all'interno della non-linearità (ad esempio, la sigmoide), evitando la necessità di una enumerazione esaustiva delle configurazioni dei sottografi.

3. Architettura Neurale:
   L'ICCM è istanziato all'interno di un'architettura di deep learning composta da:

   • Estrattori di Sottografi Duali: Moduli dedicati estraggono pattern causali strutturali e temporali.
     • Estrazione Temporale: Utilizza la codifica a tempo continuo (basata su coseno) e l'attenzione cross-nodo per identificare gli archi temporalmente rilevanti che supportano causalmente un link target, separandoli dal rumore temporale non causale.
     • Estrazione Strutturale: Codifica le caratteristiche dei nodi basandosi sui vicinati a $n$-hop entro una finestra temporale, utilizzando meccanismi di attenzione per filtrare i nodi di sfondo che introducono correlazioni spurie.
   • Environment Memory Bank (Banca della Memoria Ambientale): Per approssimare le distribuzioni dei confonditori latenti ($D_s, D_t$) senza osservarli direttamente, il modello mantiene una banca della memoria di vettori prototipo. Questi prototipi rappresentano cluster di sottografi non causali e fattori non osservati. La banca viene aggiornata tramite perdite di allineamento auto-supervisionato e di diversità per garantire che i prototipi catturino distinti modi di confondimento.
   • Fusione e Predizione: Un modulo di attenzione multi-testa aggrega le voci della banca della memoria per stimare il contributo atteso dei confonditori. Queste stime vengono fuse con le rappresentazioni invarianti ($H_S, H_T$) per produrre la predizione OOD finale. Il modello è addestrato per ottimizzare simultaneamente gli obiettivi in-distribuzione e interventistici (OOD).

Contributi Chiave

• Prima Investigazione di OOD nei CTDG: Il documento sostiene di essere il primo a investigare l'apprendimento di rappresentazioni invarianti specificamente per i CTDG sotto spostamenti OOD, affrontando una lacuna dove i metodi causali esistenti falliscono a causa della natura continua e non stazionaria dei dati.
• ICCM e Approssimazione NWGM: Gli autori introducono l'ICCM per caratterizzare i sottografi causali invarianti nei CTDG e sviluppano una strategia di intervento efficiente utilizzando NWGM. Ciò evita l'esplosione combinatoria associata ai tradizionali interventi causali in contesti dinamici.
• Il Framework CIR: È progettata un'architettura di deep learning pratica per istanziare l'ICCM, consentendo l'apprendimento congiunto di rappresentazioni strutturali/temporali invarianti e di caratteristiche specifiche dell'ambiente tramite un meccanismo di banca della memoria.

Risultati Sperimentali
Esperimenti estesi sono stati condotti su quattro dataset benchmark (MOOC, REDDIT, WIKI, UCI) con spostamenti di distribuzione simulati (introdotti tramite perturbazioni strutturali).

• Prestazioni: CIR supera costantemente i baseline allo stato dell'arte, inclusi i modelli specifici per CTDG (TGN, TGAT, GraphMixer) e i modelli robusti per DTDG (DIDA, EAGLE, Ada-DyGNN).
• Robustezza: Sotto livelli crescenti di spostamento della distribuzione (rapporti di shortcut da 0.2 a 0.6), i modelli esistenti subiscono una degradazione significativa delle prestazioni (ad esempio, l'AUC di GraphMixer scende di oltre il 50% su MOOC). Al contrario, CIR mantiene alti punteggi di AUC e AP con bassa varianza, dimostrando una capacità di generalizzazione superiore.
• Efficienza: CIR raggiunge un'alta efficienza di inferenza (circa $5.4 \times 10^{-4}$ secondi per arco su REDDIT), paragonabile o migliore rispetto a baseline complesse come TGAT e TGN, e significativamente più veloce di DIDA, che richiede la costruzione di set di intervento per ogni snapshot.
• Ablazione: Rimuovere componenti chiave (encoder strutturali/temporali, il ramo di predizione OOD $Y^C$ o la banca della memoria) porta a cali sostanziali delle prestazioni, validando la necessità dell'intera architettura.

Significato
Il documento posiziona CIR come un passo significativo verso lo sviluppo di Reti Neurali su Grafi robuste e auto-interpretabili per sistemi dinamici a tempo continuo. Spostando il focus dal semplice modellamento della dinamica temporale all'identificazione di strutture causali invarianti sotto spostamenti di distribuzione, il lavoro fornisce una soluzione teorica e pratica per scenari in cui le distribuzioni dei dati sono non stazionarie. Gli autori affermano che CIR mitiga efficacementamente le correlazioni spurie, garantendo che le predizioni si basino su meccanismi causali stabili piuttosto che su artefatti ambientali transitori, migliorando così l'affidabilità dei modelli di grafi dinamici nelle applicazioni del mondo reale.