Proposta de Tese de Marcelo de Oliveira Rosa Prates

Aluno: Marcelo de Oliveira Rosa Prates
Orientador: Prof. Dr. Luis da Cunha Lamb

Título: Learning to Solve NP-Complete Problems
Linha de Pesquisa: Inteligência Artificial

Data: 22/03/2019
Horário: 16h
Local: Prédio 43412 – AUD-0 (Auditório Zero) do Instituto de Informática

Banca Examinadora:
– Prof. Dr. Roberto da Silva (UFRGS)
– Prof. Dr. André Grahl Pereira (UFRGS)
– Prof. Dr. Felipe Rech Meneguzzi (PUCRS)

Presidente da Banca: Prof. Dr. Luis da Cunha Lamb

Abstract: Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this thesis, we propose a new formulation for GNNs, which employs the concept of ‘types’ to partition the objects in the problem domain into many distinct classes, yielding the Typed Graph Networks (TGN) model and a Python / Tensorflow library for prototyping TGNs. This thesis is also concerned with the application of GNNs to the Traveling Salesperson Problem (TSP). We show that GNNs can learn to solve, with very little supervision, the decision variant of the TSP, a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in graph in which edges from the input graph communicate with vertices from the input graph for a number of iterations after which the model is asked to decide whether a route with cost <C exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost C*, we produce one decision instance with target cost (C) x% smaller and one with target cost x% larger than C*. We were able to obtain 80% accuracy training with -2%,+2% deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within 1.5% relative deviation from the ground truth.  In summary, our work shows that Graph Neural Networks are powerful enough to solve NP-Complete problems which combine symbolic and numeric data, in addition to proposing a modern reformulation of the meta-model.

Keywords: Artificial Neural Network. Deep Learning. Graph Neural Network. Typed Graph Network. Neural Symbolic Reasoning. Traveling Salesman Problem.