Graph Neural Networks for Binary Programming

We explore the connection between Graph Neural Networks (GNNs) and Binary Programming (BP) problems, paving the way for GNNs to approximate solutions to these challenges. By analyzing BP problem sensitivity, we frame solving BP problems as a heterophilic node classification task. We introduce Binary-Programming GNN (BPGNN), integrating graph representation learning with BP-aware features to efficiently approximate solutions. Additionally, we propose a self-supervised data generation mechanism for training, even for large-scale BP problems. Evaluations across various problem sizes demonstrate BPGNN's superiority over exhaustive search and heuristic approaches. Lastly, we discuss challenges in applying GNNs to BP problems.