A Learning-Based Approach to Approximate Temporal Motif Counting

In recent years, temporal graph analysis has become increasingly important due to the presence of dynamic networks in many domains such as finance, biology, and social media. A key task in this area is temporal motif counting, which helps to uncover higher-order patterns of interactions. However, existing approaches rely heavily on exact counting methods, which are combinatorial in nature and become very slow when the motif structure is complex or the sampled subgraphs are dense. In this thesis, we propose WINE (Wedge-based Isomorphism Network), the first efficient learning-based algorithm for temporal motif counting. Unlike existing models that rely on edge-level message passing, WINE performs message passing over wedges, as the higher-order building blocks of motifs, allowing the model to capture the relational and temporal dependencies that define motif structures. This higher-order approach improves predictive accuracy and enables efficient processing. Extensive experiments on real-world temporal graph of Bitcoin transactions demonstrate that WINE achieves strong predictive accuracy across different motif types, while offering significant computational advantages over exact counting methods. Overall, this work introduces a scalable and accurate approach to temporal motif counting, enabling faster and more accurate analysis of complex temporal networks.

Negli ultimi anni, l'analisi dei grafi temporali è diventata sempre più importante a causa della presenza di reti dinamiche in molti ambiti, come finanza, biologia e social media. Un compito chiave in questo ambito è il conteggio dei motivi temporali, che consente di individuare schemi di interazione di ordine superiore. Tuttavia, gli approcci esistenti si basano fortemente su metodi di conteggio esatto, che sono di natura combinatoria e diventano molto lenti quando la struttura del motivo è complessa o i sotto-grafi campionati sono densi. In questa tesi, proponiamo WINE (Wedge-based Isomorphism Network), il primo algoritmo efficiente basato sull'apprendimento per il conteggio dei motivi temporali. A differenza dei modelli esistenti che si basano sul passaggio di messaggi a livello di archi, WINE esegue il passaggio di messaggi sui wedges, i blocchi fondamentali di ordine superiore dei motivi, permettendo al modello di catturare le dipendenze relazionali e temporali che definiscono le strutture dei motivi. Questo approccio di ordine superiore migliora l'accuratezza predittiva e consente un'elaborazione efficiente. Esperimenti estensivi su grafi temporali reali di transazioni Bitcoin dimostrano che WINE raggiunge un'elevata accuratezza predittiva su diversi tipi di motivi, offrendo al contempo vantaggi computazionali significativi rispetto ai metodi di conteggio esatto. Complessivamente, questo lavoro introduce un approccio scalabile e accurato al conteggio dei motivi temporali, permettendo un'analisi più rapida e precisa di grafi temporali complessi.