Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems

AWS Center for Quantum Computing, Pasadena, CA 91125, USA (Dated: March 23, 2023) We provide a comprehensive reply to the comment written by Stefan Boettcher [arXiv:2210.00623] Conversely, we highlight the broader algorithmic development underlying our original work [1], 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.