We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.
We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.
Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to model various NP-hard Combinatorial Optimization problems (CO) in the form of binary variables. Ising Hamiltonian is used to model the energy function of a system. QUBO to Ising Hamiltonian is regarded as a technique to solve various canonical optimization problems through quantum optimization algorithms. Recently, PI-GNN, a generic framework, has been proposed to address CO problems over graphs based on Graph Neural Network (GNN) architecture. They introduced a generic QUBO-formulated Hamiltonian-inspired loss function that was directly optimized using GNN. PI-GNN is highly scalable but there lies a noticeable decrease in the number of satisfied constraints when compared to problem-specific algorithms and becomes more pronounced with increased graph densities. Here, We identify a behavioral pattern related to it and devise strategies to improve its performance. Another group of literature uses Reinforcement learning (RL) to solve the aforementioned NP-hard problems using problem-specific reward functions. In this work, we also focus on creating a bridge between the RL-based solutions and the QUBO-formulated Hamiltonian. We formulate and empirically evaluate the compatibility of the QUBO-formulated Hamiltonian as the generic reward function in the RL-based paradigm in the form of rewards. Furthermore, we also introduce a novel Monty Carlo Tree Search-based strategy with GNN where we apply a guided search through manual perturbation of node labels during training. We empirically evaluated our methods and observed up to 44% improvement in the number of constraint violations compared to the PI-GNN.
In recent years, there has been notable interest in investigating combinatorial optimization (CO) problems by neural-based framework. An emerging strategy to tackle these challenging problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms, a subject that has attracted considerable attention. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. The primary focus of our work is to formulate a more efficient and precise framework for CO by employing decision-focused learning on graphs. Additionally, we introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support. To realize an end-to-end approach, we have designed two cascaded modules: (a) an unsupervised trained graph predictive model, and (b) a solver for quadratic binary unconstrained optimization. Empirical evaluations are conducted on various classical tasks, including maximum cut, maximum independent set, and minimum vertex cover. The experimental results on classical CO problems (i.e. MaxCut, MIS, and MVC) demonstrate the superiority of our method over both the standalone GNN approach and classical methods.
Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to model various NP-hard combinatorial optimization problems in the form of binary variables. The Hamiltonian function is often used to formulate QUBO problems where it is used as the objective function in the context of optimization. Recently, PI-GNN, a generic scalable framework, has been proposed to address the Combinatorial Optimization (CO) problems over graphs based on a simple Graph Neural Network (GNN) architecture. Their novel contribution was a generic QUBO-formulated Hamiltonian-inspired loss function that was optimized using GNN. In this study, we address a crucial issue related to the aforementioned setup especially observed in denser graphs. The reinforcement learning-based paradigm has also been widely used to address numerous CO problems. Here we also formulate and empirically evaluate the compatibility of the QUBO-formulated Hamiltonian as the generic reward function in the Reinforcement Learning paradigm to directly integrate the actual node projection status during training as the form of rewards. In our experiments, we observed up to 44% improvement in the RL-based setup compared to the PI-GNN algorithm. Our implementation can be found in https://github.com/rizveeredwan/learning-graph-structure.
Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.
In recent years, the advantages of Graph Neural Networks (GNNs) in solving complex combinatorial optimization problems have become more and more obvious. Under this background, this paper demonstrates a method based on GNNs to solve large-scale Unconstrained 0–1 Quadratic Programming (UBQP) problems. Firstly, the UBQP problem models of different combinatorial optimization problems are converted into a unified graph model. This approach makes up for the shortcoming that GNNs cannot be effectively applied to combinatorial optimization problems not based on graph. Secondly, based on Graph Attention Network (GAT) algorithm, this study designs a general GNN model capable of solving UBQP problems. In addition, a random sampling scheme for the complete graph structure is devised, which greatly alleviates the pronounced over-smoothing phenomenon when the model is applied to complete graphs and speeds up the convergence rate. In this paper, a supervised learning approach is adopted to train and test a unified structured model (without changing network parameters) on UBQP problems of varying sizes, and to evaluate the model's generalization ability on high-dimensional UBQP problems. Furthermore, an unsupervised learning mechanism is utilized to train and solve individual sample problems of different dimensions. These experimental results consistently demonstrate that the model and strategy presented in this paper exhibit strong solving ability and generalization ability for combinatorial optimization problems.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.