  Combinatorial optimization (CO) problems are crucial in various scientific
and industrial applications. Recently, researchers have proposed using
unsupervised Graph Neural Networks (GNNs) to address NP-hard combinatorial
optimization problems, which can be reformulated as Quadratic Unconstrained
Binary Optimization (QUBO) problems. GNNs have demonstrated high performance
with nearly linear scalability and significantly outperformed classic
heuristic-based algorithms in terms of computational efficiency on large-scale
problems. However, when utilizing standard node features, GNNs tend to get
trapped to suboptimal local minima of the energy landscape, resulting in low
quality solutions. We introduce a novel algorithm, denoted hereafter as
QRF-GNN, leveraging the power of GNNs to efficiently solve CO problems with
QUBO formulation. It relies on unsupervised learning by minimizing the loss
function derived from QUBO relaxation. The proposed key components of the
architecture include the recurrent use of intermediate GNN predictions,
parallel convolutional layers and combination of static node features as input.
Altogether, it helps to adapt the intermediate solution candidate to minimize
QUBO-based loss function, taking into account not only static graph features,
but also intermediate predictions treated as dynamic, i.e. iteratively changing
recurrent features. The performance of the proposed algorithm has been
evaluated on the canonical benchmark datasets for maximum cut, graph coloring
and maximum independent set problems. Results of experiments show that QRF-GNN
drastically surpasses existing learning-based approaches and is comparable to
the state-of-the-art conventional heuristics, improving their scalability on
large instances.
