Feb, 2023

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

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

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

    Jun, 2022

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

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

    Feb, 2023

  • 最大独立集：动态规划自学习

    本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。

    Oct, 2023

  • 物理启发图神经网络的组合优化

    本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

    Jul, 2021

  • 离散随机结构下图神经网络 (GNN) 性能的障碍 - 对文章 《Schuetz 等：组合方法的进展》、《Angelini 等：现代表面建模》、以及《Schuetz 的回复》的评论

    本文研究了图神经网络在解决随机图组合优化问题方面的局限性，发现由于 “Overlap Gap Property” 存在，即使是针对广泛选择的 GNN 体系结构，也很难超越已有算法的表现。

    Jun, 2023

  • 深度学习在组合优化树搜索中的问题

    本研究提出了一个开源基准套件，对最大独立集问题进行了深入分析，结果表明现有的机器学习算法未能学习最优解的结构，算法技术仍是获得有效解决方案的关键。

    Jan, 2022

  • 最大约束满足的图神经网络

    提出了一种解决组合优化问题的图神经网络体系结构，可运用于所有二元约束满足问题的训练，无监督训练，性能非常优秀。尽管是通用的，但其性能可超过大多数贪心和半定编程算法，有时甚至优于特定问题的最优启发式算法。

    Sep, 2019

  • 图神经网络启发式算法无法在解决如 Max-Cut 等组合优化问题中超越贪婪算法

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

    Oct, 2022

  • 使用无数据神经网络的可微组合优化方法

    本研究提出了一种基于神经网络的无数据训练方法，用于解决组合优化问题，特别是最大独立集和最大团的问题，并提出了通用的图缩小过程来处理大规模图形。这种方法在无需数据的情况下，可与有监督学习、强化学习和基于机器学习的现有方法相媲美或更优，具有广泛的适用性。

    Mar, 2022

  • 最大独立集问题的无数据二次神经网络

    通过引入一种新颖的无数据二次神经网络，该论文解决了最大独立集问题，并展示了与现有学习方法相比具有竞争力或更好性能的优势。

    Jun, 2024