We provide a comprehensive reply to the comment written by Chiara Angelini and Federico Ricci-Tersenghi [arXiv:2206.13211] and argue that the comment singles out one particular non-representative example problem, entirely focusing on the maximum independent set (MIS) 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 results, thereby refuting the comment's performance statements. We also provide results showing run-time scaling superior to the results provided by Angelini and Ricci-Tersenghi. Furthermore, we show that the proposed set of random d-regular graphs does not provide a universal set of benchmark instances, nor do greedy heuristics provide a universal algorithmic baseline. Finally, we argue that the internal (parallel) anatomy of graph neural networks is very different from the (sequential) nature of greedy algorithms and emphasize that graph neural networks have demonstrated their potential for superior scalability compared to existing heuristics such as parallel tempering. We conclude by discussing the conceptual novelty of our work and outline some potential extensions.

在回复评论者的回复中, 我们指出其关注的最大独立集（MIS）在稀疏图中和贪心算法优秀表现无关，我们还强调了原始框架中广泛的算法开发，并通过提供额外的数值结果证明了我们原来的结果的可观改进，进而驳斥了评论中的性能声明。我们同时通过实验证明了我们提出的随机d-正则图不提供用于基准测试的通用实例集，贪心算法不提供通用算法基线。最后，我们指出图神经网络的内在（并行）解剖与贪心算法的（顺序）本质非常不同，并强调图神经网络已经展示出了比现有启发式方法（如并行退火）更高的可扩展性潜力。这份工作的概念创新值得探讨并有潜力进一步拓展。

Reply to: Modern graph neural networks do worse than classical greedy
  algorithms in solving combinatorial optimization problems like maximum
  independent set

现代图神经网络在解决像最大独立集这样的组合优化问题时表现不及经典的贪心算法