Dec, 2023

COMBHelper：减少图组合问题搜索空间的神经方法

PDF
TL;DR设计了一种名为 COMBHelper 的神经方法，借助图神经网络（GNN）识别有前景的节点，压缩搜索空间并提高传统组合优化算法的效率；包括知识蒸馏模块和问题特定增强模块以进一步提升效果，实验证明传统算法利用 COMBHelper 至少快于原始版本 2 倍。
combinatorial optimizationgraphsneural methodgraph neural networkefficiency
发现论文，激发创造
  • 图形 Q-Learning 用于组合优化

    本论文提出并证明了图神经网络可以应用于解决组合优化问题，通过将优化过程视为顺序决策问题，使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。

    Jan, 2024

  • 基于图神经网络的组合优化和推理

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

    Feb, 2021

  • 面向决策的图神经网络在组合优化中的应用

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

    Jun, 2024

  • 自动图神经网络的组合优化

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

    Jun, 2024

  • 通过深度强化学习在大规模图上学习启发式算法

    本文介绍了一种名为 GCOMB 的框架，利用概率贪心机制通过训练图卷积网络 (GCN) 预测一个节点的质量，以此解决图上的组合问题。实验表明，GCOMB 比学术界最先进的组合算法快 100 倍、质量略高。此外，GCOMB 在实际的 Influence Maximization（IM）组合问题上也展现了强大的性能。

    Mar, 2019

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 面向组合优化的通用图神经网络框架

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

    May, 2024

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

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

    Jul, 2021

  • 神经组合优化算法的泛化

    本文采用元学习技术来在多种任务中训练一个模型，以优化适应新任务的能力，从而提高两个最先进的模型的泛化能力，实验表明该方法在两个 CO 问题上都有显著改善。

    Jun, 2022

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

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

    Oct, 2022