Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems
This is an incremental response defending the use of physics-inspired graph neural networks against criticism, relevant for researchers in combinatorial optimization and machine learning.
The authors respond to a critique by arguing that the comment focuses on a non-representative example (MaxCut on sparse graphs) where greedy algorithms excel, and they provide additional numerical results showing improvements over their original data, refuting the performance claims.
We provide a comprehensive reply to the comment written by Stefan Boettcher [arXiv:2210.00623] and argue that the comment singles out one particular non-representative example problem, entirely focusing on the maximum cut problem (MaxCut) on sparse graphs, for which greedy algorithms are expected to perform well. Conversely, we highlight the broader algorithmic development underlying our original work, and (within our original framework) provide additional numerical results showing sizable improvements over our original data, thereby refuting the comment's original performance statements. Furthermore, it has already been shown that physics-inspired graph neural networks (PI-GNNs) can outperform greedy algorithms, in particular on hard, dense instances. We also argue that the internal (parallel) anatomy of graph neural networks is very different from the (sequential) nature of greedy algorithms, and (based on their usage at the scale of real-world social networks) point out that graph neural networks have demonstrated their potential for superior scalability compared to existing heuristics such as extremal optimization. Finally, we conclude highlighting the conceptual novelty of our work and outline some potential extensions.