Sintesi Tecnica: Firme di Motivi Temporali per le Reti Neurali a Grafo Temporali

Definizione del Problema

I flussi di interazione temporale del mondo reale (ad esempio, comunicazioni sociali, trasferimenti finanziari, recensioni online) contengono strutture predittive all'interno di pattern di motivi a breve orizzonte, come ripetizione, reciprocità, diversità stellare e flusso triadico. Sebbene le moderne Reti Neurali a Grafo Temporali (TGNN) siano modelli sequenziali espressivi capaci di estrarre teoricamente qualsiasi funzione di un flusso temporale, i loro bias induttivi e i budget di addestramento limitati impediscono loro di catturare specifiche regolarità strutturali a breve orizzonte. Queste regolarità sono spesso semplici da calcolare analiticamente ma sono critiche per i task a valle; il documento affronta il divario tra ciò che le standard TGNN apprendono e le statistiche esplicite a breve orizzonte che caratterizzano i flussi temporali, chiedendosi se un potenziamento (augmentation) principato e indipendente dall'architettura possa colmare questo divario residuo.

Metodologia

1. Diagnostica Empirica e Identificazione delle Firme

Gli autori analizzano innanzitutto i conteggi dei motivi per candidato, su una finestra passata, attraverso un insieme diversificato di 13 dataset temporali reali e sintetici (inclusi MOOC, Bitcoin Alpha/OTC e benchmark TGB). Identificano che l'attività dei motivi si organizza coerentemente lungo tre assi stabili di scala:

• A1 (Reciprocità/Recenza Diadica): Cattura la tempistica e la frequenza delle interazioni dirette tra una coppia di candidati $(u, v)$.
• A2 (Diversità Stellare): Misura la diversità dei vicini che interagiscono con $u$ o $v$ entro una finestra temporale (ad esempio, il numero di elementi distinti con cui uno studente ha interagito).
• A3 (Flusso Triadico): Cattura il flusso di interazioni attraverso terze parti che collegano $u$ e $v$ (ad esempio, vicini comuni).

2. La Mappa di Caratteristiche dei Motivi $h(u, v, t)$

Sulla base di questi assi, gli autori progettano una mappa di caratteristiche dei motivi compatta, locale per il candidato, con 13 coordinate, $h(u, v, t) \in \mathbb{R}^{13}$. I vincoli chiave di progettazione includono:

• Sicurezza contro il Leakage: Le caratteristiche sono calcolate rigorosamente dalla finestra passata $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$, garantendo che nessuna informazione futura trapeli nella rappresentazione del candidato.
• Dimensione Fissa: Le 13 caratteristiche sono concatenate tramite una matrice di embedding lineare apprendibile $M$ in qualsiasi encoder statico o temporale senza modifiche all'architettura.
• Sotto-famiglie: Le 13 coordinate corrispondono ai tre assi:
  • A1 (5 caratteristiche): Conteggi degli eventi $u \to v$ e $v \to u$, eventi accoppiati, burstiness e tempo normalizzato dall'ultimo evento reciproco.
  • A2 (4 caratteristiche): Dimensioni degli insiemi di vicini distinti ($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$) all'interno della finestra, con un limite (cap) per gestire gli hub.
  • A3 (4 caratteristiche): Dimensioni delle intersezioni dirette di cross-wedge e bi-wedge tra gli insiemi di vicini di $u$ e $v$.
• Normalizzazione: Le coordinate di conteggio a coda pesante subiscono una trasformazione $\log_{10}(1+x)$ per garantire la comparabilità.

3. Posizionamento Teorico (Weisfeiler-Leman Temporale)

Il documento stabilisce un limite teorico per le standard GNN a passaggio di messaggi temporali (MP-GNN). Sotto una comune astrazione di scoring dei bordi, questi modelli sono limitati dal primo livello di una gerarchia Weisfeiler-Leman temporale ancorata al candidato (temporal-1-WL).

• Gli autori dimostrano che esistono flussi ancorati (ad esempio, un ciclo $C_6$ rispetto a due triangoli disgiunti $2K_3$) che il temporal-1-WL non può distinguere (collassandoli allo stesso colore), mentre la mappa di caratteristiche dei motivi $h$ li distingue perfettamente.
• Questo posiziona l'augmentation dei motivi strettamente al di sopra della potenza espressiva delle standard MP-GNN temporali, agendo come un "testimone" che rompe il collo di bottiglia del WL.

Contributi Chiave

1. Diagnostica (Sezione 4): Il documento articola che i conteggi dei motivi per candidato organizzano i flussi temporali lungo tre assi dominanti e stabili di scala (A1, A2, A3). Queste firme per dataset predicono dove l'augmentation dei motivi produrrà i maggiori guadagni di performance.
2. Espressività Temporale (Sezione 6): Gli autori forniscono un posizionamento teorico delle MP-GNN temporali standard all'interno di una gerarchia temporal-WL ancorata al candidato. Mostrano un caso specifico di coppie di flussi in cui le caratteristiche dei motivi distinguono i candidati che il temporal-1-WL collassa, dimostendo che l'augmentation eleva il modello oltre il primo livello di questa gerarchia.
3. Performance Empirica (Sezione 7): Il documento dimostra che l'augmentation dei motivi eleva costantemente le performance attraverso task eterogenei (predizione delle proprietà dei link TGB, classificazione dei bordi e classificazione a livello di grafo) rispetto a forti baseline TGNN. Il guadagno è interpretabile: è massimo dove la baseline fallisce nel catturare la struttura a breve orizzonte (es. MOOC) e trascurabile dove la baseline cattura già la struttura rilevante.

Risultati Sperimentali

Il framework è stato valutato su:

• TGB Link-Property Prediction: Su cinque baseline (TPNet, HyperEvent, DyGFormer, TNCN, TGN) e tre dataset (Wiki, Review, Coin).
  • Risultato: L'augmentation dei motivi ha migliorato le performance in tutte le coppie baseline-dataset valutate. Il guadagno più significativo è stato osservato su DyGFormer per il dataset tgbl-review-v2, dove il Mean Reciprocal Rank (MRR) è aumentato da 0.224 a 0.413.
  • Osservazione: I guadagni erano entro una deviazione standard dallo zero per baseline come TPNet su tgbl-coin-v2, coerentemente con il fatto che tali baseline catturano già la struttura pertinente a breve orizzonte per quel dataset specifico.
• Classificazione dei Bordi:
  • MOOC: Un task di classificazione binaria per predire l'abbandono degli studenti. Un encoder GraphSAGE vanilla ha ottenuto un PR-AUC di 0.0164. Aggiungendo il sottoinsieme di 4 caratteristiche del conteggio stellare (A2), questo è salito a 0.1430, e la mappa completa di 13 caratteristiche ha raggiunto 0.1659.
  • Bitcoin Alpha/OTC: I task di classificazione della fiducia hanno mostrato miglioramenti modesti ma costanti (ad esempio, SAGE PR-AUC da 0.9282 a 0.9667 su Alpha).
• Classificazione a Livello di Grafo: Su generatori temporali sintetici, l'augmentation dei motivi ha migliorato significativamente l'accuratezza, elevando notevolmente GAT da un valore collassato del 16.7% (predizione della classe maggioritaria) al 94.0% senza cambiamenti architettonici.

Ablazione e Controlli:

• L'analisi "leave-one-out" ha confermato che nessuna coordinata è uniformemente ridondante; diversi dataset dipendono da diversi assi (ad esempio, MOOC dipende fortemente dalla diversità stellare A2, mentre Bitcoin Alpha dipende dalla reciprocità A1).
• I controlli hanno escluso che il guadagno derivasse da una "capacità extra" (caratteristiche casuali non hanno replicato il miglioramento) e hanno confermato che il guadagno non è semplicemente un proxy per i semplici conteggi dell'attività dei nodi.

Significato e Rivendicazioni

Il documento sostiene che le firme dei motivi temporali forniscono un metodo compatto, interpretabile e indipendente dall'architettura per iniettare regolarità strutturali a breve orizzonte nelle TGNN.

• Potere Predittivo: La firma per dataset lungo gli assi A1/A2/A3 funge da strumento diagnostico per predire dove l'augmentation sarà più benefica.
• Fondamento Teorico: Posizionando l'augmentation rispetto alla gerarchia temporal-WL, il documento chiarisce perché le standard TGNN falliscono su certi task (sono limitate dal temporal-1-WL) e come l'augmentation superi questo limite.
• Utilità Pratica: Il metodo non richiede modifiche all'architettura dell'encoder sottostante, ma solo la concatenazione di un vettore di caratteristiche pre-calcolato, rendendolo facilmente implementabile in pipeline esistenti.

Gli autori mantengono una posizione modesta, notando che il raggio della finestra $\Delta$ è un iperparametro sensibile e che in flussi sparsi dove il flusso triadico è trascurabile, l'augmentation si riduce a un sottospazio a dimensione inferiore con guadagni corrispondentemente minori. Il framework è presentato come un modo principato per esporre segnali strutturali specifici che le vanilla TGNN spesso non riescono a esporre ai loro edge scorer.