Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization

Venue: NeurIPS_cc_2024_Workshop_MLNCP
Published: 2024-09-12 10:34:30

Abstract: While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits.

Main paper: 
 introduction: 
 Graph-based approaches are one of the most predominant techniques for learning combinatorial optimization solvers. Their distributed nature allows them to scale up to millions of nodes [33, 19] .Nevertheless, their probabilistic nature, which provides soft assignments to decision variables, may produce solutions at a different level than their classic counterparts [25] . Annealing Machines (AM), a concurrent line of research, is seen as a more immediate alternative to the expected advances of future fully quantum solutions, which are currently in use in several industries [30] . Their major drawback, similarly suffered by the fully quantum versions, is their scalability, handling a limited number of variables, sometimes forcing problem reformulations to fit hardware limitations [28] .We see these two approaches working towards the same goal: i) GNN-based methods enable scalability, but their solutions could be noisy; ii) AM-based methods provide high precision, yet they are limited in the number of variables they can handle. This apparent trade-off motivates us to design a framework to capture the best of each technology: high scalability and high precision. This work proposes a way to combine the solving capabilities of both graph and annealing-based methods into a single workflow that handles combinatorial optimization problems at scale. Given a combinatorial problem P and its associated graph G P = (V P , E P ), with node set V P and edge set E P , our framework considers a sequential compression step, that generates a list {G i } s an extra GNN-based solver that handles P on the original graph G. In that sense, the AM solves the combinatorial problem indirectly by infusing its knowledge into the GNN. We conducted an empirical study on three canonical optimization problems over various families of graphs. Our results show that the proposed solution is feasible, allowing the AM to solve problems of size beyond its initial scope, reduce the overall converge time, and, in some cases, even increase the solution quality. 
background and related work: 
 Annealing Machines for Combinatorial Optimization AM can operate based on various mechanisms, including both quantum and classical: superconducting flux qubits, degenerating optical parametric oscillators, and semiconductor CMOS integrated circuits. However, there are various types of AM since D-Wave released the first commercial quantum AM [18, 31, 23, 30, 12, 11, 14, 17, 1, 20] .AM requires to cast the target problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem [10, 8] . The QUBO formulation models the problem as a graph, with nodes as decision variables and edges as (energy) couplings that encode their relationships. This formulation has proven versatile, with AM covering a wide range of applications [7, 26, 6, 22, 24, 21, 16, 32] . We refer the reader to [10] for a comprehensive QUBO formulation tutorial. We consider the following problem: minimize x T Qx =: H QUBO (x), subject to x ∈ {0, 1} n , where H QUBO is the Hamiltonian associated with the QUBO matrix Q ∈ R n×n , which is the symmetric matrix that encodes the target problem, and x is the vector of binary assignments. In this work, we explore to what extent the GNNs can enable AMs to handle larger problems, hopefully without sacrificing accuracy. [25] exploited the relationship between GNNs and QUBO for solving combinatorial problems. This method relies on the QUBO formulation of a target problem, where a GNN takes the Hamiltonian as the cost function and minimizes it in an unsupervised way. Thus, for the k-th GNN layer and a given node v ∈ V, we obtain a node feature representation that depends on both of its previous representation at the (k -1)-th layer and the aggregated representations of the direct neighbors,h k v = Φ θ h k-1 v , h k-1 u ∀u ∈ N v , ∀k ∈ [K], where h k v ∈ R d k , d k is the dimension of the k-th representation, N vis the set of neighbors of v, and Φ θ a learnable function [15] . The resulting representation passes through a linear layer and an activation function to obtain a single positive real value and is then projected to integer values to obtain a final binary node assignment. 
methodology: 
 Problem Statement Our main goal is to assess AM and GNN complementarity. We assume a scenario where the target problem is large enough that it cannot be solved solely by the AM. Therefore, we propose a framework that divides the problem into smaller pieces so the AM can consume and solve, and the GNN can act as a bridge, aggregating information to achieve a global solution. We reduce the size of the original graph G P using Louvain decomposition for network community detection [2] . The output of this decomposition is a list of size-decreasing graphs{G i } s i=1 .For each G i = (V i , E i ), the algorithm admits a mapping back to the original graph. Thus, we can relate a single artificial node n ∈ G i with the corresponding set of actual nodes in the original graph G P . We ensure the size of all resulting graphs is smaller than the aforesaid feasibility limit exhibited by the AM. We chose Louvain decomposition because i) it is one of the most cited and well-understood methods for community detection ii) it is hierarchical, allowing reconstruction from a given granularity to the original graph, iii) among hierarchical models, Louvain provides the most homogeneous results, as literature shows [9] . Given the expected diversity of graphs our method should handle, we consider homogeneity to be a desirable factor.Multiresolution Guidance I : Locally-assisted Solvers Interaction We get a QUBO matrix Q i for each G i . We assume that while these derived matrices are not equivalent to G P , there should be certain alignment as they are working on different granularities of the original graph G P . As each G i is smaller than the AM's limit, we can apply it to solve them. This step outputs, for each G i , the solution found by the AM, in the form of a binary solution vectorx AM i ∈ R |Vi| .Multiresolution Guidance II : Guiding block (GB) We consider AM solutions a good source of be the GNN's partial solution.x GNN i,t denotes assignment scores. Thus, we haveθ i = arg min θ∈Θ ℓ x GNN i,t , x AM i ∀i ∈ [s],wherex GNN i,t = ψ ω (GNN θ (G i , F)). We set ℓ(a, b) = ∥a -b∥ 2 .Local GNNs can quickly converge for each compressed graph due to this guidance. While we check these local results' specific behavior and quality, we focus more on the final node representations. For each G i , this step gets a matrix Fi ∈ R |Vi|×d K (with d K a predefined vector dimensionality) with the node vectors after the GNN converged. Fig. 1b depicts this process for one compressed graph.Aggregating Partial Solutions The output of the previous step gives a node feature vector for each compressed graph G i . We reuse these feature vectors to initialize a larger GNN to solve P on the original graph G P , called Main GNN solver in Fig. 1a . We hypothesize that these feature representations associated with AM-guided solutions on compressed versions of G P may encode valuable information that, if passed as initial node vectors for the main solver, could benefit the solution-finding process, in contrast, to initialize those node vectors randomly (h 0 v is random).Mapping Module Let V n i denote the set of real nodes in the original graph G P associated with a given node n i ∈ G i , the i-th compressed version of G P . Thus,V n i = v ∈ V P | v ∈ Louvain map (n i ) ,where Louvain map is a lookup table (the Louvain mapping) that tracks back any artificial node to real nodes. We use the inverse degree as a normalization factor to distribute the learned feature representation associated with n i . Formally, let deg : V P → N 0 denote the degree function, then, given an artificial node n i ∈ G i with learned feature vector fn i = Fi n ∈ R d K , for each real node v ∈ V n i the associated feature vector will be riv = (deg(v)/ u∈V n i deg(u)) fn i . LetRi ∈ R |V P |×d K be the matrix of synthetic node features, where each row of Ri v corresponds to ri v for all v ∈ V i . These node features will be fixed from now on. We repeat the above process for all compressed versions G i for i ∈ [s], resulting in s feature vectors for each real node v ∈ V. Then, we obtain a single representation using any aggregation/pooling function. Our preliminary experiments showed that a simple average provided consistent results, R = 1 s s i=1Ri .Guided initialization At this point, we have obtained a feature vector associated with each node in the original graph, and we use them now to initialize a GNN-based solver that will be tasked to find a solution on the original graph G. This step is simple: we construct a node features matrix R ∈ R |V P |×d K and use it as initialization for the GNN. Then, the solution procedure follows the standard unsupervised way described in Sec. 2. At the end of such a procedure, we finally obtain binary value vectors representing each node's solution assignments. Therefore, we minimizeH QUBO (x GNN ), where x GNN = ψ ω (GNN θ (G P , R)).Algo. 1 summarizes this process. 
empirical study: 
 Data Generation We generated a set of synthetic random d-regular graphs of sizes n ∈[50 000, 100 000, 150 000] and node degree d ∈ [3, 4, 5] , leading to a total of nine graphs. Random graphs are used for testing, as they allow us to evaluate the generalizability of our approach without the bias of structured adjacency matrices. The current AM has a limit of 100k nodes/variables, x GNN ← ψω (GNN θ (G P , R)) ▷AM-guided GNN solutionθ ← θ -α∇ θ HQUBO(x GNN ) ▷Update parameters 14:ω ← ω -α∇ωHQUBO(x GNN )15: until Convergence 16: return x GNN so the selected range allows us to study before and after such a feasibility threshold. For each graph, Louvain decomposition available on Networkx [13] was used.Optimization Problems Let V and E be the set of all nodes and edges, respectively. Maximum Cut (MaxCut) finds a partition of nodes into two subsets such that the number of edges between different subsets is maximal. Its QUBO formulation is H MaxCut (x) := (i,j)∈E 2x i x j -x i -x j , where x i is 1 if node i is in one set and 0 otherwise. Maximum Independent Set (MIS) finds the largest subset of nodes that are not connected. Its QUBO formulation of is H MIS (x) := -i∈V x i +β (i,j)∈E x i x j , where x i is 1 if a node i belongs to the independent set and 0 otherwise; β > 0 is the penalty coefficient. We used β = 2. Graph Partition (GP) partitions a graph into two equal-sized parts such that the number of divided edges is minimized. It is a generalization of MaxCut and its QUBO formulation isH GP (x) := -H MaxCut (x) -β i∈V ((1 -|V|) x i + j>i 2x i x j ). We used β = 10.Graph Neural Network Both Local and Main GNN-based solvers have the same architecture: two convolutional layers (GraphConv) linked via ReLu activations. We pass the output from the second layer through a sigmoid function to get soft node assignments. Experiments were performed on a single GPU Tesla V100 with 32 GB of memory. Local solvers use as a loss function the sum of the Hamiltonian, see Sec. 2, and the Mean Squared Error (MSE) between the solution at time t and the AM solution. We tested several alternatives, but MSE had better consistency across graphs. For the Main GNN solver, the loss function is solely the Hamiltonian using the original QUBO matrix (per problem). Both solvers run until convergence, defined using a tolerance parameter or a maximum number of epochs. We set the maximum epochs to 10k and 1k for the Main and Local, respectively.Annealing Machine We used a CMOS-based AM that implements momentum annealing [23] .Unlike the standard simulated annealing that updates variables individually, momentum annealing updates all connected variables simultaneously. Momentum annealing executed on a GPU is much faster than the simulated annealing performed on a CPU. We used an NVIDIA Tesla V100 GPU to perform the momentum annealing. Our AM can handle up to 100k decision variables. Variables were updated 1k times during each run of the annealing process. The momentum annealing was performed 1k times, and the best solution was retrieved.Graph Solver Variants We compared three solver variants: i) Raw GNN (rGNN), a single GNN that takes as input the original graph, i.e., Main (global) solver; ii) Multiresolution GNN (mrGNN), a GNN-based local solver that receives the compressed versions of the original graph and solves the local QUBO problem. After convergence, the resulting node vectors are pooled following the Louvain schema to initialize the node vectors of the main GNN solver; iii) mrGNN+AM, a mrGNN with local guidance from the AM. 
results and discussion: 
 Solution Quality and Convergence We sampled solutions 50 times per target graph and obtained the final solution. We experimented on large graphs; therefore, no ground truth is available. Given this limitation, we used the final loss value as a measure of the quality of the solution, assuming that, in the absence of violations, a lower value means a better solution. Let loss be the evaluation of the Hamiltonian on a binarized solution; see Sec. 2. Unlike the relaxed version we used during training, this loss is our original optimization objective. We also checked violations based on the problem definition. In this scenario, a good solver achieves the lowest loss and, simultaneously, the minimum number of violations. For MIS, rGNN is faster than the other alternatives, reaching loss values 48% larger with 15% more violations on average. This pattern persists across problems, providing evidence that a single GNN block trained in a purely unsupervised way, while fast, seems unable to provide high-quality results. Between mrGNN and mrGNN +AM, while mrGNN is consistently faster, it also produces more violations across graphs, mainly for the largest graph. This behavior indicates that the information from the local GNN-based solver is indeed useful, compared to rGNN, but not enough to beat the contribution of an AM-based solver. We omit rGNN from the following analyses and focus on the trade-off between quality and speed of mrGNN and mrGNN +AM. Our comparison deals with i) a main GNN solver that received AM's information against and ii) a main GNN solver that received information only from the GNN-based solvers. Given the 4 presents the values of ∆ rel across all target graphs for the three selected problems. In addition, Table 2 provides insights into how well models handle constraints. For MIS, we present the number of violations and how balanced the resulting sets are in the case of GP (ratio of their number of nodes).Our approach is particularly effective for larger graphs. For smaller graphs (up to 100k nodes), mrGNN performs comparatively well. This performance reinforces our initial goal of using the GNN as a bridge to bring the accurate problem-solving capabilities of the AM to large-scale graphs. The quality of mrGNN degrades as we expand to more complex graphs (in terms of n and d), where violations increase compared to mrGNN+AM. Table 4 shows the relative differences in terms of total execution time, ∆ T = timemrGNN+AM-timemrGNN timemrGNN × 100. ∆T > 0 means mrGNN is faster than mrGNN+AM. Interestingly, if we look at the execution time comparison, there is a considerable difference depending on the combinatorial problem. This difference is evident when comparing MIS, where mrGNN is much faster. We hypothesize that the primary input discrepancy resides in the QUBO matrix's shape, as the underlying graph structures remain the same. Therefore, differences may be due to solver technicalities, such as the sparsity 1 . Note that, for a given graph, a local GNN-based solver is, on average, 9× faster than the local AM-based solver, ignoring solution quality aspects. This speed advantage of the GNN solver underscores its practicality in real-world scenarios.We report the total time: the sum of local AM and GNN global solver times; the price to pay for a better solution is the extra time the AM takes. It is worth noting that such time comparison assumes the Louvain compression has been performed in advance, a realistic scenario in the real world.We compared GCN against a Graph Attention Network (GAT) [29, 4] , as the latter automatically learns to weight incoming node vectors from the set of neighbors during the aggregation step. For MIS, we could see a slight decrease in the achieved loss by up to 100k nodes, but at the expense of 8× total time (average for all target graphs). Unfortunately for the other problems, no conclusive evidence was found across graphs, which may suggest the GNN layer could be problem-specific. Comparison Against other Baselines For ML-based solvers, most works operate only on small to medium-size graph benchmarks, such as [5] , which represents the state-of-the-art for MIS, considers benchmarks less than a hundred nodes (in average). The assumption is the same for classical (heuristic) solvers. While they can be very efficient on small to medium-sized graphs, they cannot provide comparable solutions as size increases. We conducted the same experimental setting for graphs with sizes 50K, 100K, and 150K varying degrees in [3, 4, 5] for the MIS problem to assess such an assumption. We selected two representative classical algorithms: Greedy Search (GS) and the HB algorithm [3] . Results confirm our central hypothesis on the difficulty of scaling up classical heuristics: GS finished within 2h only for the family of graphs with n=50K, with an MIS of size 17% lower than the one obtained by the proposed model. For larger graphs, we stopped the execution after 2h, considering that the total time for the proposed approach was, on average, 12 min. HB algorithm did not finish for n =50K. In light of this evidence, we consider our approach to be able to scale and provide suitable solutions where classical methods cannot. Finally, we considered a neural model (NM), as presented in [27] . In this case, we compare at MIS size obtained by MN and our proposed method. Out of the nine target graphs, NM only obtains higher MIS size for three: 50K, d= [3, 4] and 100K, d=3. For the rest, our approach obtains on average of 4.9% higher MIS values, at equal or less number of violations. 
conclusion and future work: 
 We explore how to combine the accuracy of AM and the flexibility of GNN to solve combinatorial optimization problems. Our approach was tested on canonical combinatorial problems, showing that the flexibility of GNNs can allow the transfer of the accurate capabilities of the AM to graphs that are initially out of its reach. For future work, we are interested in i) the reuse of partial solutions across similar problems and ii) an end-to-end differentiable framework. 
 
 Appendix: In fact, preliminary experiments showed that training time could be further optimized by using a sparse representation of the QUBO matrix 



Reviews: review: title: title: This novel approach attempts to combine annealing machines and graph neural networks to solve complex combinatorial problems.  Overall, this preliminary work is well-described and well-written.
main_review: main_review: This work seeks to combine the advantages of using graph neural network (GNN) approaches, which are they are generally faster and scalable, with annealing machine (AM) approaches, which are generally more accurate but don't scale as well, on complex combinatorial optimization problems.  In general, I find the concept of this work compelling, and the preliminary results are interesting.  If they are able to effectively combine these two approaches, it can help address issues with scalability of of the AM approaches while also improving GNN performance.

Pros: 

-- Novel approach to improve combinatorial optimization 

-- Well-written and well-described

-- Good comparison with other approaches as well

-- Appreciated the inclusion of both accuracy and time as metrics

Cons:

-- I would like to have seen results on real-world graphs

-- I would like to have seen more discussion about where the GNN+AM approaches are worse
title: title: Review
main_review: main_review: In this paper, the authors propose a way to combine graph neural networks (GNNs) with annealing machines (AMs) to solve large-scale combinatoric optimization problems. The idea is to compress the large graph into small chunks, execute annealing machines on the small chunks, and aggregate the resulting features as reference information for a main graph neural network solver. This enables solving problems that are too large to be solved with AM, while providing more accurate results than GNN thanks to the information given by AM. The authors conduct numerical experiments to evaluate the performance and computation time of the proposed GNN+AM scheme, in comparison with GNN alone.

Strengths:

1. The idea of combining GNN and AM is interesting and seems to indeed enable solving large scale combinatoric optimization problems.

2. The authors considered many prototypical optimization problems, including maximum cut, maximum independent set, and graph partition. They conducted extensive numerical experiments to evaluate the performance of different GNN modules.

Weaknesses and comments:

1. I think the performance gain of combining GNN and AM is not very convincing. As the authors also point out, the performance on maximum cut and graph partition does not show a consistent trend and seems model-specific. I understand that this is only preliminary results. But the authors should consider doing more experiments to analyze why this is the case.

2. The presentation of Algorithm 1 should be self-contained. In particular, every newly introduced variable should be given a way to calculate. For example, the calculation of $\bar{R}^i$ should be stated explicitly.