  Backtracking has been widely used for solving problems in artificial
intelligence (AI), including constraint satisfaction problems and combinatorial
optimization problems. Good branching heuristics can efficiently improve the
performance of backtracking by helping prune the search space and leading the
search to the most promising direction. In this paper, we first propose a new
graph neural network (GNN) model designed using the probabilistic method. From
the GNN model, we introduce an approach to learn a branching heuristic for
combinatorial optimization problems. In particular, our GNN model learns
appropriate probability distributions on vertices in given graphs from which
the branching heuristic is extracted and used in a backtracking search. Our
experimental results for the (minimum) dominating-clique problem show that this
learned branching heuristic performs better than the minimum-remaining-values
heuristic in terms of the number of branches of the whole search tree. Our
approach introduces a new way of applying GNNs towards enhancing the classical
backtracking algorithm used in AI.
