Maximum Independent Set: Self-Training through Dynamic Programming
Lorenzo Brusca Lars C. P. M. Quaedvlieg Stratis Skoulakis Grigorios G Chrysos Volkan Cevher
This work presents a graph neural network (GNN) framework for solving the
maximum independent set (MIS) problem, inspired by dynamic programming (DP).
Specifically, given a graph, we propose a DP-like recursive algorithm based on
GNNs that firstly constructs two smaller sub-graphs, predicts the one with the
larger MIS, and then uses it in the next recursive call. To train our
algorithm, we require annotated comparisons of different graphs concerning
their MIS size. Annotating the comparisons with the output of our algorithm
leads to a self-training process that results in more accurate self-annotation
of the comparisons and vice versa. We provide numerical evidence showing the
superiority of our method vs prior methods in multiple synthetic and real-world
datasets.