Enhanced graph reconstruction using graph neural networks

Graphs are a widely used data structure to represent information, where each interconnected item typically comes with a description. This representation has recently gained significant relevance in a variety of disciplines, including chemistry (where it is used to describe molecular structures) and the social sciences (where it is used to describe social networks). Different Machine Learning techniques have been proposed for graph analysis, but these typically cannot be used directly in situations where some of the item descriptions are missing. Given how frequently this issue arises in actual databases, finding methods that enable analysis in the presence of partial missing descriptions is a crucial issue. In this thesis, we address this issue by introducing a Deep Learning-based approach to learn how to reconstruct missing data from the observable portion of the graph. The presentation of the solution is preceded by the formalisation of the task, a review of the relevant literature and the necessary technical background. After describing the process to enable unsupervised optimization, i.e. without necessarily having complete graphs, the architecture of the reconstruction model, which specifically belongs to the class of Graph Neural Networks, is described in detail. The proposed approach is mainly motivated by the possibility of efficiently exploiting the observable information contained in the graph. We highlight how this is precisely a critical issue in the solutions proposed in the literature. Finally, The proposed solution is tested in our experiments under various quality metrics and experimental conditions, and its performance is compared to the main methods that make up the state of the art. The gathered data shows the viability of the suggested strategy and its competitiveness compared to the main solutions in the literature.

I grafi sono una struttura dati ampiamente utilizzata per rappresentare le informazioni, in cui tipicamente ogni item interconnesso ha una descrizione associata. Negli ultimi anni questa rappresentazione è diventata particolarmente rilevante in ambiti come la chimica, per descrivere strutture molecolari, e le scienze sociali, in cui vengono utilizzate per descrivere reti sociali. Diverse tecniche di Machine Learning sono state proposte per l’analisi dei grafi, ma tipicamente queste non possono essere direttamente applicate nel caso in cui parte delle descrizioni degli item siano mancanti. Considerata la frequenza con cui questo problema si verifica nelle basi di dati reali, la ricerca di strategie che permettano l’analisi in condizioni di mancanza parziale delle descrizioni rappresenta un argomento di rilevanza critica. In questa tesi, affrontiamo il problema proponendo un approccio basato su Deep Learning per imparare a ricostruire i dati mancanti sulla base della parte osservabile del grafo. La presentazione della soluzione è anticipata dalla formalizzazione del problema, una revisione della letteratura rilevante e il background tecnico necessario. Dopo aver specificato la procedura per permettere un’ottimizzazione non supervisionata, ovvero senza disporre necessariamente di grafi completi, viene dettagliata l’architettura del modello di ricostruzione, che appartiene in particolare alla classe delle Graph Neural Networks. L’approccio proposto viene motivato principalmente in virtù della possibilità di sfruttare in maniera efficace l’informazione disponibile contenuta nel grafo da ricostruire, mettendo in luce come questo rappresenti appunto una criticità delle soluzioni proposte in letteratura. Infine, i nostri esperimenti mettono alla prova la soluzione proposta secondo diverse metriche di qualità e condizioni sperimentali, confrontandola con le principali strategie che costituiscono lo stato dell’arte. I risultati raccolti dimostrano la validità dell’approccio proposto e la sua competitività rispetto alle principali soluzioni presenti in letteratura.