Meno:Mário
Priezvisko:Lipovský
Názov:Solving the Maximum Clique Problem Using Neural Networks
Vedúci:Mgr. Vladimír Boľa, PhD.
Rok:2019
Blok:INF
Kµúčové slová:maximum clique problem, branch and bound, deep learning, graph neural networks
Abstrakt:Inspired by recent initiatives to solve combinatorial optimization problems using deep learning and to process graphs with neural networks, in our work we try to solve the maximum clique problem using simple graph neural networks Structure2Vec and ChebNet. We use supervised learning in the first step of our approach -- we train graph neural networks on various types of random graphs to predict the maximum clique size in the neighbourhood of each vertex. In the second step we then use these predictions to guide a branch and bound tree search to construct the maximum clique. Our results show that graph neural networks can learn to predict clique sizes in small graphs, although our generalization experiments suggest that these models are not able to grasp the underlying concept of cliques. We also show that when the graph network is used as a branching heuristic function of branch and bound algorithm, it can outperform degree-based heuristic, but it does not achieve the effectiveness of a more advanced heuristic based on vertex coloring. In addition to our main results, we also provide valuable insights that may improve the methodology of solving combinatorial optimization problems using graph neural networks in the future.

Súbory diplomovej práce:

master-thesis-lipovsky.pdf
mcp-gnns.zip