Applications of Machine Learning Techniques to Graph Neural Networks: Design of an Algorithm for the Maximum Independent Set and Minimum Vertex Cover Problems

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 non-interfering or non-conflicting 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 NP-hard 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 NP-hard, producing labels to train the ML-like 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, ML-like 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 ML-like methods but outperforms them by making use of an ML model that is trained self-supervised. 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 DP-like 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 sub-graphs. Both sub-graphs 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 self-training process is established that results in improved self-annotation 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 near-optimal. Finally, numerical results show that the proposed method outperforms the state-of-the-art approaches across various synthetic and real-world datasets.