Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut

In Ref. [1], Schuetz et al provide a scheme to employ Among a variety of QUBO problems Ref. [1] consider The cut results for the GNN (for both, d = 3 and 5) are presented in Figure 1 of Ref. [1], whose flip (x After only fit to the GNN data obtained from averaging over 0.4n such flips, typically no further improvements were randomly generated instances of the problem for a progression possible and GD converged; very scalable and fast (done of different problem sizes n. Like in Ref. [1], I have also Figure 1(a), the results all look rather good, although it is included what they describe as a rigorous upper bound, already noticeable that results for GD are barely distinguishable cut While the GNN results To discern further details, it is essential to present appear impressively close to that upper bound, however, the data in a form that, at least, eliminates some of including two other sets of data puts these results in a its trivial aspects. The second set is achieved by a simple gradient for better comparison with Refs. Also, energy results (blue line) are systematical far (> 15% at any n) provides a fair reference point to assess relative error because from optimal (1-RSB, green line) and hardly provide any a purely random assignment of variables results in improvement over pure gradient descent (GD, maroon an energy of zero, the ultimate null model. It appears that the GNN learns what is indeed point is lacking for the errors quoted in Tab. 1 of the most typical about the energy landscape: the vast Ref. [1], for example.) Since we care about the scalability of the algorithm in In fact, extending GD by a subsequent 5n spin flips, say, the asymptotic limit for large problem sizes n, each flip adjusting one among the least-stable spins (even which in the form of Figure 1(a) is out of view, it expedient if not always unstable), allows this greedy local search to to visualize the data plotted for an inverse of the explore several local minima, still at linear cost.