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.

通过提高算法的广泛发展和数值结果的改进，反驳了一篇评论的初始性能声明，并强调了物理启发式的图神经网络在稠密实例上特别是在硬实例上优于贪婪算法的能力，同时也指出了图神经网络在真实社交网络规模上的可扩展性潜力比极端优化等现有启发式方法更具优势。

图神经网络启发式方法未能超越贪心算法在解决组合优化问题上的能力