Mar, 2019

图着色遇上深度学习：用于组合问题的有效图神经网络模型

HTML
PDF
TL;DR本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题，并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时，我们还展示了如何将节点嵌入在多维空间中进行聚类，从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距，并提供了符号推理与深度学习系统集成的可靠方法。
发现论文，激发创造
  • 图卷积网络与引导树搜索的组合优化

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

    Oct, 2018

  • 图上深度学习：一份综述

    该研究综述了将深度学习方法应用于普适图形数据的现有五类模型结构和训练策略：图循环神经网络、图卷积网络、图自编码器、图强化学习和图对抗方法，并提出了潜在的未来研究方向和应用领域。

    Dec, 2018

  • 图神经网络：方法和应用综述

    本文介绍了图神经网络（GNNs）的设计管道，详细讨论了其各个组成部分的变体，对其应用进行了系统分类，并提出了四个开放性问题供未来研究。

    Dec, 2018

  • 组合问题的图神经网络的近似比

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

    May, 2019

  • 重新思考图神经网络在图染色问题中的应用

    本研究分析了现有图嵌入神经网络（GNN）在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性；通过研究聚集-合并 GNN（AC-GNN）的性能以及其基于局部搜索的特性，我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则，并提出了一个简单的 AC-GNN 变体以验证我们的理论，并实现了比现有启发式算法更高质量和更快速运行的结果。

    Aug, 2022

  • 利用深度 Q 学习和图神经网络生成图着色启发式

    本文探讨了深度强化学习在解决图着色问题中的应用，提出了一个名为ReLCol的构造启发式方法，该方法结合了深度Q学习和图神经网络，通过一种新颖方法对图进行参数化，相对现有的构造算法性能有所提升。在标准基准图上进行了实验证明了强化学习是进一步研究图着色问题的一个有前途的方向。

    Apr, 2023

  • 通过图分割提升图神经网络的表达能力

    图分区神经网络（GPNNs）是一种新颖的GNN架构，通过对图进行分区以及顶点集和子图之间的结构相互作用的探索，提高了GNN的表达能力，并在各种图基准任务中展示了超越现有GNN模型的卓越性能。

    Dec, 2023

  • 图形 Q-Learning 用于组合优化

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

    Jan, 2024

  • 基于神经网络的高效图着色：一种面向大规模图的物理启发方法

    本研究解决了图着色问题，该问题是一个NP困难的优化问题，特别是在大规模图中。我们提出了一种新颖的算法，利用图神经网络及物理启发的方法来提高训练效率和算法性能。研究结果表明，该方法在传统方法难以解决的连通性区域中依然有效，具有广泛的应用潜力。

    Aug, 2024

  • 将图神经网络作为平行图着色的排序启发式

    本文解决了图着色问题，这是一种在无向图中为顶点分配不同颜色的NP难题。提出了一种基于图神经网络的排序启发式，显著提升了着色质量和执行效率。研究表明，在平行处理能力上，GNN模型在质量和性能上超越了现有的贪心排序启发式方法。

    Aug, 2024