| 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.
|
|---|