Solving the decision version of the Graph Coloring Problem : a neural-symbolic approach using graph neural networks

Abstract

Deep learning (DL) has consistently pushed the state-of-the-art in many fields over the last years. Still there is, however, a lack of understanding on how symbolic and relational problems can benefit from DL architectures. The most promising path towards this longdesired integration comprises deep learning architectures whose parameter sharing strategy is based over graphs and thus can be trained to learn complex properties of relational data. Several NP-Complete problems, such as the boolean satisfiability problem and the traveling salesperson problem, present such properties. In both cases, a meta-model called Graph Neural Network (GNN) can be directly fed with the graph representation of the problem and learn to produce a binary answer at hand. In this dissertation, we are specifically concerned with the application of a GNN model to tackle the graph coloring problem: our proposed model leverages the specific features of such problem by adding internal representations of vertices and colors to the GNN kernel and by performing messagepassing iterations over such representations. In this sense, our model’s architecture is able to reflect the relational structure of the original problem, with no need of polynomial time reductions, while it still employs parameter sharing over the graph vertices and colors. We also show how to train such model upon very hard instances, which were generated in an adversarial fashion: we generate pairs of instances comprising graphs that are on the verge of satisfiability – a positive and a negative-labeled instance that only differ by a single edge, such edge makes the second instance unsatisfiable given a fixed number of colors C. We were able to obtain 83% accuracy during training and to show that such model is able to generalize, to some extent, its performance to unseen instances coming from different distributions and sizes. We show that such performance defeats two heuristics and an allegedly generalist neural-symbolic approach. Finally, we explore the internal memory of our model and find evidence of how its reasoning is built upon its internal states (vertex and color representations). In summary, our results strongly suggests that GNNs are, indeed, powerful to tackle combinatorial problems but their performance can be largely enhanced when all problem’s features are integrated within the GNN neural architecture and no problem translation is required.

Técnicas baseadas em aprendizado profundo têm recorrentemente atingido desempenho de estado-da-arte em diversas áreas ao longo dos últimos anos. Ainda há, no entanto, uma certa falta de compreensão em como problemas simbólicos e relacionais podem se beneficiar de modelos cuja arquitetura é baseada em aprendizado profundo. O caminho mais promissor para essa tão desejada integração consiste em arquiteturas neurais cuja propriedade de compartilhamento de parâmetros baseia-se em grafos e, dessa forma, podem ser treinadas para aprender características complexas de dados relacionais. Diversos problemas NP-Completos, tais como satisfatibilidade booleana e problema do caixeiro viajante, apresentam esse tipo de característica. Em ambos casos, um metamodelo chamado Graph Neural Network (GNN) pode trabalhar diretamente com entradas em formato de grafos, que representam uma instância do problema, e aprender a produzir uma resposta binária para o problema em questão. Nessa dissertação, estamos particularmente focados em aplicar um modelo de GNN ao problema da coloração de grafos: o modelo que propomos se aproveita de propriedades específicas desse problema ao contemplar tanto vértices quanto cores com representações internas na sua arquitetura e ao fazer com que tais representações passem por diversas etapas de troca de mensagens. Nesse sentido, a arquitetura que propomos é capaz de refletir a estrutura relacional do problema original, sem necessidade de uma redução em tempos polinomial para outro problema, enquanto ainda emprega uma estratégia de compartilhamento de parâmetros em função de vértices e cores. Nós também demonstramos como treinar tal modelo com instâncias muito difíceis, geradas de uma maneira adversarial: nós geramos pares de instâncias que são grafos no limite da satisfatibilidade – uma instância positiva e outra negativa que diferem apenas por uma única aresta, tal aresta faz com que a segunda instância não seja colorável por um dado número de cores C, enquanto a primeira permanece sendo minimamente colorável com C. Obtivemos uma acurácia de 83% durante treinamento e verificamos que nosso modelo é capaz de generalizar, até certo ponto, esse desempenho para instâncias de teste – não-vistas durante treinamento e que foram amostradas de diferentes distribuições. Nós mostramos que esse desempenho superou o desempenho de duas heurísticas e o desempenho de uma suposta abordagem neuro-simbólica generalista. Por fim, nós exploramos a memória interna do nosso modelos e encontramos evidências de como o seu raciocínio é construído em volta dos valores de representação de vértices e cores. Em suma, nossos resultados sugerem fortemente que GNNs são, de fato, ferramentas poderosas para resolver problemas combinatoriais mas que seu aprendizado pode ser amplamente melhorado quando as propriedades de um problema são totalmente agregadas à arquitetura neural e nenhuma conversão de problema é feita.