Feb, 2021

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

PDF
TL;DR本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。
combinatorial optimizationoperations researchmachine learninggraph neural networksinductive bias
发现论文，激发创造
  • 图形 Q-Learning 用于组合优化

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

    Jan, 2024

  • 在图上学习组合优化问题：一份调查及其在网络中的应用

    介绍了解决图上组合优化问题的现有方法存在的问题，调查了与计算复杂性相关的机器学习研究的发展，并组织和比较了解决组合优化问题的学习结构。

    May, 2020

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

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

    Jun, 2024

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

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

    Jul, 2021

  • 神经组合优化：领域的新玩家

    本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

    May, 2022

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

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

    Jun, 2024

  • 带时序注意力图神经网络的精确组合优化

    通过替换启发式成分，结合机器学习算法的时间特征与注意力机制，优化了组合优化求解器在变量选择方面的性能。

    Nov, 2023

  • 图机器学习基础的未来方向

    机器学习与图神经网络，尤其是使用图神经网络（GNN）的机器学习，在各个领域的图数据广泛应用中受到了广泛关注。然而，对于 GNN 的性质仍存在理论上的不完备性。最近的理论进展主要集中于阐明 GNN 的粗粒度表达能力，主要使用组合技巧。然而，这些研究与实践并不完全一致，特别是在理解使用随机一阶优化技术训练时 GNN 的泛化行为方面。在本文中，我们将论证图机器学习社区需要将关注点转向发展一个更加平衡的图机器学习理论，重点研究表达能力、泛化和优化的相互作用。

    Feb, 2024

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

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

    May, 2024

  • 基于图神经网络的组合优化统一框架

    基于图神经网络 (GNNs) 的统一框架，解决组合优化问题 (COPs)，包括 COPs 的图表示、非图结构 COPs 转换为图结构 COPs 的等效转换、图分解和图简化，利用 GNNs 有效捕获关系信息和提取 COPs 图表示的特征，为 COPs 提供了通用解决方案，能够解决非图结构和高度复杂图结构的 COPs 限制。

    Jun, 2024