Learning Branching Heuristics from Graph Neural Networks
This work provides a new method for enhancing classical backtracking algorithms in AI, specifically for combinatorial optimization problems like the dominating-clique problem, though it is incremental as it builds on existing GNN and backtracking techniques.
The paper tackles the problem of improving backtracking search efficiency for combinatorial optimization by learning branching heuristics from a graph neural network (GNN) model, resulting in a heuristic that reduces the number of branches in the search tree compared to the minimum-remaining-values heuristic.
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.