Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update

Graph neural networks (GNNs) can solve combinatorial optimization (CO) problems in an instance-wise unsupervised way: a fresh network is trained on one instance with a continuous relaxation of the QUBO objective as the loss, with no labels, no pre-training and no training distribution. This regime assumes nothing about the instance and yields a stand-alone heuristic, but it is also the hardest one for a network, and existing methods of this kind (PI-GNN, CRA) are beaten by simple classical heuristics. We show that one change to the training loop closes most of this gap. At every iteration, QRF-GNN feeds the network’s own previous prediction back as a detached dynamic node feature, so each node adapts its de- cision to the current states of its neighbours; the input evolves together with the weights, and training becomes a guided search over binary configurations. We complement the mechanism with a two-branch GraphSAGE block and compact static features. On Max-Cut, Graph Coloring and Maximum Independent Set, QRF-GNN outperforms prior instance-wise unsupervised GNNs by a wide mar- gin, matches or exceeds pre-trained neural solvers evaluated on their own training distributions, and approaches the best dedicated heuristics, on graphs with up to a million nodes. An analysis of the training dynamics shows that the recurrent fea- ture turns a run that freezes early in one configuration into a walk over near-binary configurations that ends in a discrete local optimum.