acceptodds
Under review as a conference paper at ICLR 2027

Optimizing Pseudo-Boolean Polynomials using Hypergraph Neural Networks

Abstract

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 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Pseudo-Boolean Polynomials, Hypergraph Neural Networks, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_hNtgOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes PB-HGNN, an unsupervised hypergraph neural network framework for solving PUBO problems. It follows the same hypergraph modeling paradigm as prior work, while introducing training mechanisms aimed at enhancing HyperGNN's performance. The evaluation covers hypergraph max-cut, minimum hitting set, and max-3-sat problems.

Critical strengths

1.High-order combinatorial optimization on hypergraphs is an important challenge.

Critical weaknesses

1.The idea is incremental. This paper adopts BIPNN's hypergraph modeling for PUBO problems, while recurrent feedback has been explored in prior methods such as QRF-GNN. The main contributions therefore appear to lie in adapting these ideas to high-order hypergraph optimization, together with LOO messages and incumbent tracking. Although these adaptations may be useful, the authors should better clarify their novelty.

2.Important baselines are missing. The PUBO problem can be transformed into a QUBO formulation and solved with QUBO solvers such as PyQUBO. Since this paper focuses on unconstrained PUBO, comparisons against strong baselines like Gurobi and PyQUBO are absent and sorely needed.

Questions for authors

The core methodological contribution appears to be an integration and adaptation of existing ideas, and the distinction from BIPNN and prior recurrent neural optimization methods is not yet sufficiently compelling. I would encourage the authors to strengthen the novelty discussion and provide more comprehensive ablations and baseline comparisons.

Reviewer_xtimOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper offers a modeling method for compact factors in PUBO problems which treats each factor as one single hyperedge and evaluates corresponding loss without monomial expansion. It also develops an instance-specific, unsupervised yet recurrent logit feedback-driven solver for PUBO problems modelled by hypergraphs, where objective factors are represented by hyperedges. Finally, it validates the method on hypergraph Max-Cut, minimum hitting set, Max-3-SAT, and random PUBO instances, using solver comparisons and ablations to assess solution quality and the effect of its training mechanisms.

Critical strengths

The paper represents compact objective factors directly as hyperedges and computes the loss without polynomial expansion.

The paper extends feedback-driven method in QRF-GNN to hypergraphs, and introduces leave-one-out aggregation and noise injection for message passing.

Critical weaknesses

The feedback-driven solving method shares mechanistic similarities with evolutionary algorithms: it repeatedly perturbs the current state, generates and evaluates candidate solutions, and retains the best solution found. Further experiments are required to prove whether its gains stem primarily from the effective representation of the underlying problem by the GNN structure, or from this iterative process of perturbation, evaluation, and elite retention.

Questions for authors

What is the contribution of learned problem representation? Does PB-HGNN perform better than a solver that keeps the same recurrent perturbation and best-solution tracking but replaces the HGNN with a simpler, non-graph parameterization?

What is the contribution of the search process? How does PB-HGNN compare with an evolutionary algorithm that uses a matched budget for perturbation, candidate evaluation, and elite retention on the same instances?

What do the search trajectories show? Do the HGNN updates produce better candidate solutions per evaluation, or does their advantage emerge mainly from exploring more distinct candidates within the time budget?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.