该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

Jun, 2022

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

Feb, 2023

Schuetz 等人提出了一种使用图神经网络作为启发式方法来解决各种组合优化问题的方案，该方法通过样例实例对网络进行训练，并应用广泛使用的技术来评估其成功的能力，尽管报告的结果只比梯度下降略有改善，但该方法承诺具有高度可伸缩性和计算成本线性。

Oct, 2022

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

Feb, 2023

该论文从理论角度研究了如何利用图神经网络解决组合问题的近似算法，并提出了一种新的 GNN 类别，揭示了 GNN 的相对近似比，并证明了在节点特征中添加染色可以提高学习算法的近似比。

May, 2019

本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。

Feb, 2021

近年来，图神经网络（GNNs）在解决 NP-hard 组合优化问题方面变得越来越流行。本文提出了一种名为 AutoGNP 的新型自动化 GNNs 类别，用于解决 NP-hard 问题，并通过图神经网络搜索算法自动查找给定 NP-hard 组合优化问题的最佳 GNNs，通过实验证明了我们提出模型的优越性。

Jun, 2024

图神经网络在解决节点分类、图分类和链接预测等任务方面取得了巨大成功。然而，将图神经网络和机器学习应用于组合优化问题的研究相对较少。本文引入了一种新颖的图神经网络架构，利用复杂的滤波器组和局部化注意机制来解决图上的组合优化问题。我们展示了我们的方法如何与以往基于图神经网络的组合优化求解器区别开来，并在自监督学习设置下有效地应用于最大团、最小支配集和最大割问题。除了证明在各项任务上具有竞争力的整体性能外，我们还为最大割问题建立了最新的研究结果。

May, 2024

图神经网络性能分析基于随机图理论，GCN 和 GAT 是关键研究领域，性能受到数据特征的影响，实验结果显示特定高阶结构对性能有负面影响。

Oct, 2023

我们的研究工作的重点是通过决策导向的图学习，在组合优化问题中采用神经网络框架，提出了一个更高效和精确的框架。此外，我们引入了一个决策导向的框架，利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明，我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。

Jun, 2024