Lorenzo Brusca
Applications of Machine Learning Techniques to Graph Neural Networks: Design of an Algorithm for the Maximum Independent Set and Minimum Vertex Cover Problems.
Rel. Giulia Fracastoro, Sophie Fosson. Politecnico di Torino, Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni), 2023

PDF (Tesi_di_laurea)
 Tesi
Licenza: Creative Commons Attribution Noncommercial No Derivatives. Download (1MB)  Preview 
Abstract: 
This study introduces an innovative framework for addressing the maximum independent set (MIS) and minimum vertex cover (MVC) problems using a graph neural network (GNN) approach inspired by dynamic programming (DP). The MIS problem finds important applications in Communication Networks, as it can help in optimizing the network's performance by ensuring noninterfering or nonconflicting communication between nodes. Instead, identifying an MVC in a network helps to minimize the number of resources needed for infrastructure deployment, which is crucial in applications like transportation or utility networks. Unfortunately, the MIS and MVC are NPhard problems, and classic heuristics, like the simplex or the ellipsoid methods, may take too much time to find a solution. For this reason, in the last few years, new methods involving Machine Learning (ML) models have been deployed. Since the MIS and MVC problems are NPhard, producing labels to train the MLlike approaches would be too difficult, thus unsupervised training is employed. If the ML models are properly trained, these approaches have the advantage of being faster than standard heuristics, as the complexity of the method is linked to the complexity of the ML model architecture. Unfortunately, MLlike approaches may lead to solutions of the MIS and MVC problems that are too far from the optimal value. The goal of this work is to produce a new algorithm that, by making use of an ML model, shares the low complexity of standard MLlike methods but outperforms them by making use of an ML model that is trained selfsupervised. Moreover, the architecture of the proposed ML model relies on Graph Neural Networks (GNNs), that leverage the concept of embeddings in order to capture diverse semantic meanings of graphs. The proposed algorithm employs a DPlike recursive structure. Each iteration of the algorithm considers a graph as input and outputs a graph of lower complexity (thus with fewer nodes or fewer edges) that is employed in the next iteration. The first step of each iteration consists of creating two smaller subgraphs. Both subgraphs have a lower complexity than the graph from which they were generated. Then, the second step is executed by an ML model that acts as a binary classifier, indicating which of the two graphs is chosen. Finally, in the third step, a check over the chosen graph is made. If the chosen graph has a specific structure, the algorithm stops, otherwise the chosen graph is used in the next iteration. To train the ML model effectively, annotated comparisons between different graphs in terms of their MIS and MVC sizes are leveraged. By annotating these comparisons with the outcomes generated by the algorithm, a selftraining process is established that results in improved selfannotation of the comparisons and vice versa. Theoretical results prove that if the ML model is effectively trained, then the proposed algorithm leads to solutions that are nearoptimal. Finally, numerical results show that the proposed method outperforms the stateoftheart approaches across various synthetic and realworld datasets. 

Relators:  Giulia Fracastoro, Sophie Fosson 
Academic year:  2023/24 
Publication type:  Electronic 
Number of Pages:  92 
Subjects:  
Corso di laurea:  Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni) 
Classe di laurea:  New organization > Master science > LM27  TELECOMMUNICATIONS ENGINEERING 
Ente in cotutela:  ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE  EPFL (SVIZZERA) 
Aziende collaboratrici:  EPFL 
URI:  http://webthesis.biblio.polito.it/id/eprint/28666 
Modify record (reserved for operators) 