Optimizing Pseudo-Boolean Polynomials using Hypergraph Neural Networks

Unsupervised graph neural networks solve combinatorial optimization instances without labels, but a graph encodes only pairwise interactions. We present PB-HGNN, an unsupervised hypergraph neural solver for polynomial unconstrained binary optimization (PUBO). It couples an objective-centric hypergraph representation — every monomial, or every compact factor such as a cut indicator or a clause, is a hyperedge on its variables — with a training procedure built for that representation: recurrent logit feedback corrected for two-stage hypergraph aggregation (leave-one-out messages and noise-driven exploration), best-incumbent tracking, and exact evaluation of the loss on the factored objective without polynomial expansion. The representation alone is not sufficient: a feed-forward hypergraph solver on the same hypergraph falls behind classical metaheuristics at scale. Under equal wall-clock budgets, PB-HGNN outperforms simulated annealing, greedy local search and prior hypergraph-neural solvers (HypOp, BIPNN) on hypergraph Max-Cut with up to $10^6$ variables and on five real hypergraphs, matches or beats them on minimum hitting set, is competitive on Max-3-SAT, dominates quadratization-based GNNs on random higher-order PUBO, and handles instances whose PUBO expansion is infeasible.