Predizione di link con codificatori profondi e non

Link prediction is the process of predicting missing connections in a graph on the basis of the current structure. This thesis aims to predict links in a network, in this context, an Online Social Network (OSN) called Steemit. The literature on link prediction methods is various, ranging from traditional approaches, such as looking at the neighborhood overlap between two nodes, to more advanced techniques like embeddings used as the first step in more complex architectures such as Graph Neural Networks (GNNs). Embedding techniques are increasingly popular, owing to their ability to learn low-dimensional vector representations of nodes (or links) in a graph that capture the underlying structural and semantic features. This thesis aims to investigate two different approaches to embedding-based link prediction. First, I employ the node2vec algorithm, which uses a shallow encoder to generate node embeddings by sampling random walks from the graph and therefore to predict links. Second, I use a Graph Neural Network (GNN) as a deep encoder to simultaneously build node embeddings and forecast the missing links. The primary objective of this study is to compare the performance of the two embedding-based link prediction techniques in this specific context. In particular, I seek to evaluate which of the two approaches, i.e., node2vec or GNN, yields better prediction performance. The performance comparison is carried out using different evaluation metrics. By evaluating the performance of node2vec and GNN, I aim to identify which of these techniques is more effective in predicting missing links in Steemit, and potentially in other similar networks. I show that node2vec performs better on the Steemit data set. The reasons could be that the data set is rather small and simple (we have no features) so that more complex techniques such as using a neural network are, under certain condition, unnecessarily more complicated and perform worse than the shallow encoder model. 

La predizione dei link consiste nel prevedere le connessioni mancanti in un grafo sulla base della sua struttura attuale. Questa tesi si propone di prevedere i link in una rete, in questo contesto, un Social Network Online (OSN) chiamato Steemit. La letteratura sui metodi di predizione dei link è varia, a partire da approcci tradizionali, come l'analisi del neighborhood overlap tra due nodi, fino a tecniche più avanzate come l'utilizzo degli embedding come primo passo in architetture più complesse come le Graph Neural Networks (GNNs). Le tecniche di embedding sono sempre più popolari, grazie alla loro capacità di apprendere rappresentazioni vettoriali a bassa dimensione di nodi (o link) in un grafo che catturano le caratteristiche strutturali e semantiche sottostanti. Questa tesi si propone di indagare due diversi approcci alla predizione dei link basati sugli embedding. In primo luogo, viene utilizzato l'algoritmo node2vec, che utilizza un codificatore superficiale per generare embedding di nodi campionando passeggiate casuali dal grafo e quindi per prevedere i link. In secondo luogo, viene utilizzata una Graph Neural Network (GNN) come codificatore profondo per costruire contemporaneamente gli embedding dei nodi e prevedere i link mancanti. L'obiettivo principale di questo studio è confrontare le prestazioni dei due metodi di predizione dei link basati sugli embedding in questo contesto specifico. In particolare, si cerca di valutare quale dei due approcci, ovvero node2vec o GNN, produca una migliore performance. Il confronto delle prestazioni viene effettuato utilizzando diverse metriche di valutazione. Valutando le prestazioni di node2vec e GNN, si cerca di identificare quale di queste tecniche sia più efficace nella previsione dei link mancanti in Steemit e potenzialmente in altre reti simili. Si dimostra che node2vec si comporta meglio sul set di dati di Steemit rispetto all'altro metodo. Le ragioni potrebbero essere che il set di dati è piuttosto piccolo e semplice (non abbiamo features) quindi tecniche più complesse come l'utilizzo di una rete neurale sono, in determinate condizioni, inutilmente più complicate e producono peggiori prestazioni rispetto al modello di codificatore superficiale.