Bridging Static and Temporal Graph Covering Problems with Deep Learning and Heuristics

Combinatorial issues that deal with network optimization problems have motivated several branches of computational science, also thanks to the huge real-world contexts on which they find application. Modern applications are increasingly incorporating new data abstractions that necessitate redefined approaches to data summarization and synthesis. Notably, with the widespread availability of temporal information, many datasets, traditionally modeled as networks, are now being treated as temporal networks. This leads to the need of bridging the algorithms traditionally applied in the static case to adapt for dynamic scenarios. Based on this, in this thesis we explore two NP-hard problems in graph theory: the widely studied Minimum Vertex Cover (MVC) problem in static graphs and the less explored Minimum Timeline Cover (MinTCover) problem in temporal graphs, which can be considered as an extension to the temporal dimension of the covering probelm on static instances. Both problems pose significant computational challenges and have wide-ranging applications in areas such as network management, social network analysis, and biological systems. The main objective of this research is to develop novel approaches that combine deep learning (DL) techniques with heuristic methods to improve both the accuracy and efficiency of solving MVC and MinTCover. Particularly, for the MVC problem, we propose to overcome the common limitations of recent DL-based models, leveraging an attention mechanism and a memory network to generate both local and global graph representations, thus improving solution quality over existing methods. The DL architecture proposed incorporates also graph’s complement information in the attention mechanism, with the aim of tailoring the methodology to the specific combinatorial problem setting. Results, besides demonstrating superior capabilities of the proposed model with respect to compared approaches in terms of solution quality, also proves the ability of the tailored DL-based model to properly represent data according to the combinatorial nature of the problem in a representation learning fashion. Moving to the temporal version of the problem, the MinTCover problem, the thesis introduces FastMinTC+, a new heuristic algorithm that iteratively constructs and optimizes timeline covers for temporal graphs, providing a more computationally feasible solution compared to traditional approaches. The algorithm is built considering a heuristic commonly adopted in the static case, showing that, with the proper adaptation, it can be effectively used also in the dynamic settings. Experimental results, besides providing theoretical guarantees on the validity and minimality of the proposed heuristic, sets a new benchmark and state-of-the-art results for such problem. The thesis advances further by proposing a DL-based solution aimed at addressing the MinTCover problem. Considering the proven effectiveness of these approaches in static cases and the evident lack of research in dynamic contexts, the objective is to assess the extent to which the application of data-driven models can prove effective in such complex environments. We, thus, presents DLMinTC+, a DL-based model, enforced with an iterative algorithm, for the MinTCover problem that integrates Transformer and graph-based neural network to manage temporal and structural information to enhance coverage accuracy. The proposed approach, thanks to the iterative procedure, grants to provide a valid solution. Experimental results highlight the effectiveness of the methodology which achieves better results with respect to FastMinTC+. This further demonstrates the potential of DL-based models, providing additional justification for their application in other combinatorial problems on temporal graphs.

I problemi di natura combinatoria legati all’ottimizzazione delle reti hanno stimolato diversi rami della scienza computazionale, anche grazie agli ampi contesti reali in cui trovano applicazione. Le applicazioni moderne stanno sempre più incorporando nuove astrazioni dei dati che richiedono di ridefinire gli approcci per la sintesi dei dati. Inoltre, con la diffusa disponibilità di informazioni temporali, molti dataset, tradizionalmente modellati come reti, sono ora trattati come reti temporali. Ciò porta alla necessità di adattare gli algoritmi tradizionalmente applicati nel caso statico a scenari dinamici. Sulla base di questo, in questa tesi esploriamo due problemi NP-difficili nella teoria dei grafi: il problema della Copertura Minima dei Vertici (MVC), ampiamente studiato nei grafi statici, e il meno esplorato problema della Minima Copertura Temporale (MinTCover) nei grafi temporali, che può essere considerato un'estensione alla dimensione temporale del problema di copertura su istanze statiche. Entrambi i problemi presentano significative sfide computazionali e hanno applicazioni vastissime in aree come la gestione delle reti, l'analisi delle reti sociali e i sistemi biologici. L'obiettivo principale di questa ricerca è quello di sviluppare nuovi approcci che combinano tecniche di deep learning (DL) con metodi euristici per migliorare sia l'accuratezza che l'efficienza nella risoluzione di MVC e MinTCover. In particolare, per il problema MVC, la tesi propone di superare i limiti dei recenti modelli basati su DL, sfruttando il meccanismo di attenzione e una rete di memoria per generare rappresentazioni del grafo sia locali che globali, migliorando così la qualità delle soluzioni rispetto ai metodi esistenti. L'architettura DL proposta incorpora anche informazioni complementari nel meccanismo di attenzione, con l'obiettivo di adattare la metodologia all'impostazione specifica del problema. I risultati dimostrano le superiori capacità del modello proposto rispetto agli approcci confrontati in termini di qualità della soluzione, e provano anche la capacità del modello basato su DL di rappresentare adeguatamente i dati secondo la natura combinatoria del problema. Passando alla versione temporale del problema, il problema MinTCover, la tesi introduce FastMinTC+, un nuovo algoritmo euristico che costruisce e ottimizza iterativamente le coperture temporali per i grafi temporali, fornendo una soluzione computazionalmente più semplice rispetto agli approcci tradizionali. L'algoritmo è costruito considerando un'euristica comunemente adottata nel caso statico, mostrando che, con i dovuti accorgimenti, può essere adottato efficacemente anche nei contesti dinamici. I risultati sperimentali, oltre a fornire garanzie teoriche sulla validità e sulla minimalità dell'euristica proposta, stabiliscono un nuovo benchmark per tale problema. Considerando l'efficacia provata di questi approcci nei casi statici e la mancanza di ricerca nei contesti dinamici, questa tesi si pone l'obiettivo ulteriore di valutare in che misura l'applicazione di modelli basati su DL possa risultare efficace in contesti così complessi. Presentiamo quindi DLMinTC+, un modello basato su DL, rafforzato con un algoritmo iterativo, per il problema MinTCover che integra Transformer e modelli basati su grafi per gestire informazioni temporali e strutturali al fine di migliorare l'accuratezza della copertura. L'approccio proposto, grazie alla procedura iterativa, garantisce di fornire una soluzione valida. I risultati sperimentali evidenziano l'efficacia della metodologia che produce risultati migliori rispetto a FastMinTC+. Ciò dimostra ulteriormente il potenziale dei modelli basati su DL, fornendo una motivazione aggiuntiva per la loro applicazione in altri problemi combinatori su grafi temporali.