Apprendimento dei grafici temporali nel 2024. Continua il viaggio per l’evoluzione… | di Shenyang(Andy) Huang | Gennaio 2024 | Intelligenza-Artificiale

“Einstein diceva che la freccia del tempo vola in una sola direzione. (…) E chi di noi, se ne avesse la possibilità, non rivivrebbe il giorno o l’ora in cui abbiamo conosciuto per la prima volta l’amore, o l’estasi, o fatto una scelta che ha cambiato per sempre il nostro futuro, negando una vita che avremmo potuto avere? Tali possibilità vengono raramente concesse”. — Greg Iles, Il gioco tranquillo

Uno dei motivi per cui l’apprendimento dei grafici temporali è interessante è che, a seconda dei dati a disposizione, richiede prospettive diverse. Ad esempio, si considerino i dati dei grafici temporali con timestamp ad alta risoluzione (possibilmente continui). In tali dati, le tecniche di apprendimento dei grafici a tempo discreto che utilizzano sequenze di grafici di istantanee richiedono una grana grossolana del tempo, in cui ciascuna istantanea è costituita da bordi che si verificano in un determinato intervallo di tempo. Questa grana grossolana consente di generalizzare le tecniche di apprendimento dei grafici (statici) ai dati di serie temporali. Ma introduce un problema importante: ogni istantanea scarta informazioni sull’ordine temporale in cui si sono verificati i bordi, che è il fondamento di causale O percorsi che rispettino il tempo (Kempe et al. 2000). Come i percorsi nei grafici statici, i percorsi che rispettano il tempo sono importanti poiché ci dicono quali nodi possono influenzarsi indirettamente a vicenda in modo causale. Di seguito, lo illustriamo in un semplice grafico temporale con due archi non orientati (a,b) E (avanti Cristo) che si verificano a volte t₁ E t₂ rispettivamente. Se (a,b) avviene prima (avanti Cristo), UN può influenzare causalmente C tramite un sentiero transitabile nel rispetto del tempo (segnalato in viola). B. Se l’ordine temporale dei bordi è invertito, UN non può influenzare causalmente Cpoiché qualsiasi influenza deve propagarsi all’indietro nel tempo. Si noti che la direzione dell’influenza da UN A C è dovuto alla freccia del tempo orientata e nonostante il fatto che entrambi i bordi non siano orientati. Inoltre, mentre due bordi (a,b) E (avanti Cristo) in un grafico statico e aggregato nel tempo implica un percorso transitivo da UN attraverso B A C (viola) e viceversa (arancione), questo non è vero per i grafici temporali.

Diversi lavori hanno dimostrato che, a causa della freccia del tempo, il topologia causale dei grafici temporalicioè quali nodi possono eventualmente influenzarsi causalmente a vicenda attraverso percorsi che rispettano il tempo, differisce fortemente dalle loro controparti statiche, con implicazioni interessanti per la diffusione dell’epidemia (Pfitzner et al. 2013), velocità di diffusione (Scholtes et al. 2014), centralità dei nodi (Rosvall et al. 2014) o rilevamento della comunità (Lambiotte et al. 2019). Possiamo rendere i metodi di deep learning consapevoli dei modelli nella topologia causale dei grafici temporali? I progressi presentati quest’anno mostrano che ciò può essere ottenuto sulla base di modelli che generalizzano le rappresentazioni statiche comunemente utilizzate dei grafici temporali. Considera un grafico ponderato aggregato nel tempo, in cui un bordo (diretto). (a,b) con il peso cinque lo cattura (a,b) si è verificato cinque volte in un grafico temporale. Tale grafico ponderato e aggregato nel tempo è illustrato nella parte inferiore del pannello 2 nella figura seguente.

Ogni arco nel grafico temporale è un percorso che rispetta il tempo con lunghezza uno. Un grafo ponderato aggregato nel tempo corrisponde quindi a un modello del primo ordine per la topologia causale di un grafo temporale, che cattura percorsi di lunghezza uno che rispettano il tempo. Trascura l’ordinamento temporale dei bordi, poiché contiamo solo la frequenza con cui si è verificato ciascun bordo. Una trasformazione del grafico a linee ci consente di generalizzare questa idea modelli consapevoli della causalità che facilitano l’apprendimento del grafo temporale: sostituiamo semplicemente gli spigoli nel grafo del primo ordine con i nodi in a secondo ordine grafico, cioè giriamo i bordi (a,b) E (avanti Cristo) in nodi “a→b” E “b→c”rispettivamente. Nel grafico del secondo ordine risultante (vedi il grafico in alto nel pannello 2 in figura), possiamo usare gli archi per rappresentare percorsi che rispettano il tempo di lunghezza due, cioè spigolo (a→b, b→c) indica che UN influenza causale C attraverso B. Tuttavia, l’ordine inverso dei bordi non è incluso. Se i bordi si presentano in ordine inverso, non li includiamo (a→b, b→c). È importante sottolineare che un grafico del secondo ordine di questo tipo è sensibile all’ordinamento temporale degli archi, mentre un grafico del primo ordine non lo è! In Scholtes, 2017questo è generalizzato agli ordini superiori, il che produce Modelli di grafi di De Bruijn del k-esimo ordine per la topologia causale di grafici temporali.

Qarkaxhija et al. hanno dimostrato che il messaggio neurale che passa in tali grafi di De Bruijn di ordine superiore produce a Architettura di rete neurale a grafo sensibile alla causalità per i grafici temporali. Basandosi su questi Reti neurali con grafico di De Bruijn (DBGNN)in un poster al workshop TGL di quest’anno, Heeg e Scholtes affrontare la sfida di prevedere la centralità temporale e la vicinanza dei nodi. Poiché sono influenzate dalla freccia del tempo, le centralità dei nodi temporali possono differire drasticamente dalle centralità statiche. Inoltre, calcolarli è costoso! Ciò viene risolto addestrando un modello DBGNN su un primo intervallo temporale di un grafico temporale, quindi utilizzando il modello addestrato per prevedere le centralità temporali nei dati rimanenti. L’approccio generale è illustrato sopra. Dal punto di vista empirico i risultati sono promettenti e hanno messo in luce il potenziale dell’apprendimento dei grafi consapevole della causalità. Ci auguriamo inoltre di vedere maggiore attenzione da parte della comunità nell’apprendimento della struttura causale sui grafici temporali nel 2024.

Ti interessa l’apprendimento del grafico temporale consapevole della causalità? Allora ci sono buone notizie! Le tecniche di cui sopra sono implementate nella libreria Open Source pathpyGsu cui si basa PyG. C’è un video introduttivo e tutorial disponibile. UN discorso registrato tenuto nel gruppo di lettura del grafico temporale fornisce un’introduzione approfondita della ricerca sottostante.