Graph Neural Networks for Binary Programming
Moshe Eliasof Eldad Haber
This paper investigates a link between Graph Neural Networks (GNNs) and
Binary Programming (BP) problems, laying the groundwork for GNNs to approximate
solutions for these computationally challenging problems. By analyzing the
sensitivity of BP problems, we are able to frame the solution of BP problems as
a heterophilic node classification task. We then propose Binary-Programming GNN
(BPGNN), an architecture that integrates graph representation learning
techniques with BP-aware features to approximate BP solutions efficiently.
Additionally, we introduce a self-supervised data generation mechanism, to
enable efficient and tractable training data acquisition even for large-scale
BP problems. Experimental evaluations of BPGNN across diverse BP problem sizes
showcase its superior performance compared to exhaustive search and heuristic
approaches. Finally, we discuss open challenges in the under-explored field of
BP problems with GNNs.