Nov, 2022

从图神经网络中学习分支启发式算法

PDF
TL;DR本研究提出了一种新的基于图神经网络的分支启发式方法，用于求解组合优化问题中的最小支配团问题，实验结果表明，该方法相较于最小剩余量策略在分支数上表现更优，为使用图神经网络改进传统的 AI 回溯算法提供了新思路。
发现论文，激发创造
  • 图神经网络启发式算法无法在解决如 Max-Cut 等组合优化问题中超越贪婪算法

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

    Oct, 2022

  • 运用图指针网络在组合优化中的学习分支

    本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略，结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。

    Jul, 2023

  • 神经网络验证的神经网络分支

    通过训练图神经网络来设计一个有效的分支策略，能够在形式化验证神经网络的过程中减少验证时间并获得更好的验证结果。

    Dec, 2019

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

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

    Feb, 2021

  • 图卷积分支与界

    使用深度学习模型在优化流程中的有效性进行了论证，通过将图卷积分支限界与经典的分支限界算法相结合，实现了更快速的解决旅行商问题的路径的识别。

    Jun, 2024

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

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

    Mar, 2019

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

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

    Oct, 2018

  • 基于图神经网络的启发式学习：一种用于链接预测的统一框架

    利用统一矩阵公式和 HL-GNN 方法，本研究提出了一种整合了各类算启发式方法和传统图神经网络的学习模型，通过广泛的实验验证了其高效性和显著优于现有方法的预测性能。

    Jun, 2024

  • 重新考虑图神经网络在分支策略中的容量

    研究表明图神经网络能够有效地表示和学习基于混合整数线性规划的解决策略，其中包括强分支评分。另外，该研究还证明第二阶基因网络结构能够以高准确率和高概率近似强分支评分。

    Feb, 2024

  • 图形算法的神经执行

    通过在算法空间中训练 Graph Neural Networks 来解决基于图结构的问题，使用基于最大化的信息传递神经网络来实现离散决策，同时实现了任务迁移并提升学习效果。

    Oct, 2019