Repeating link prediction over dynamic graphs through edge embeddings. New method optimizing node pair proximity in the embedding space for link prediction

Transactional graphs are networks made of money transactions and have gained particular attention from researchers thanks to their numerous applications in financial institutions. When considering the Link Prediction task over dynamic graphs, it is possible to use the evolutionary behavior of the network to predict which are the future links that will occur in the next future in the graph. Dynamic Link Prediction has been explored widely in the past years, however, the majority of these works focus on discovering new edges, while very few works focus on the repeating edges, i.e. links that continuously vanish and reappear in the network. In this work, we first study the literature for link prediction in the static settlement, then, we focus on dynamic link prediction, underlining the strengths and weaknesses of every approach studied. We discover that traditional methods do not work well with repeating links as they are unable to encode temporal patterns associated with the edges while also considering the topological graph features. We propose a novel method, Temporal Edge Embedding Neural Network (TEEN), which is based on a deep learning architecture able to jointly optimize the prediction of the correct edge labels and the proximity of two nodes' pairs in their latent space at every time step. Our solution benefits of node embeddings created with deep encoders from where an edge embedding is created for every time step. TEEN is able to outperform State of the Art models by over 8% on AUC and 7% on F1-Score. We conclude that our approach brings significant improvements in the scenario of transactional graphs. More future work should be done in different scenarios to validate the algorithm's effectiveness in the general case.

I grafi transazionali sono reti fatte di transazioni monetarie che negli ultimi anni hanno attirato l’attenzione di molti ricercatori grazie alle loro numerose applicazioni nelle istituzioni finanziarie. Quando si considera il task del Link Prediction su Dynamic Graphs, è possibile utilizzare il comportamento evolutivo della rete per prevedere quali sono i collegamenti futuri che si verificheranno nel prossimo futuro nel grafo. La Dynamic Link Prediction è stato esplorata ampiamente negli ultimi anni con molti lavori scientifici, tuttavia, la maggior parte di questi si concentra sulla scoperta di nuovi link mai osservati in precedenza nella rete evolutiva, mentre pochissimi lavori si concentrano su link che si ripetono, cioè connessioni che svaniscono e riappaiono continuamente nella rete. In questa tesi verrà studiata prima la letteratura scientifica per la previsione dei collegamenti per il Link Prediction su grafi statici, quindi, ci concentriamo sulla previsione dei collegamenti dinamici, sottolineando i punti di forza e di debolezza di ogni approccio studiato. Durante la ricerca abbiamo scoperto che i metodi tradizionali non funzionano bene con i collegamenti ripetuti in quanto non sono in grado di considerare sia i pattern temporali associati all’apparizione dei link considerando anche la caratteristiche globali del grafo. Per risolvere il problema proponiamo un nuovo metodo, Temporal Edge Embedding Neural Network (TEEN), che si basa su un’architettura Deep Learning in grado di ottimizzare congiuntamente sia la previsione delle labels associati ai collegamenti da prevedere ed anche la prossimità della coppie di nodi nel loro latent space ad ogni istante temporale. Il modello utilizza due Deep Encoders per proiettare ogni noto in uno spazio latente (Embedding space); questo viene fatto per ogni istante di tempo e permette di considerare features temporali e tipiche del grafo. TEEN è in grado di superare le performance ottenuti da modelli dello Stato dell’Arte di oltre 8% in Area Under the Curve (AUC) e del 7% in F1-Score. Concludiamo che il nostro approccio apporta miglioramenti significativi nello scenario dei grafici transazionali. Infine, riteniamo che debba essere svolto ulteriore lavoro per convalidare l’efficacia dell’algoritmo in caso di molteplici tipologie di grafo.