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

Mar, 2019

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

Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems

Henrique Lemos, Marcelo Prates, Pedro Avelar, Luis Lamb

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

Abstract

deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. deep learning<

deep learning neural networks graph neural networks combinatorial problem symbolic reasoning

发现论文，激发创造

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

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

Aug, 2022

本地顶点着色图神经网络

最近几年来，有大量的研究专注于扩展图神经网络（GNNs）的表达能力，超越 Weisfeiler-Lehman (1-WL) 框架。在这项研究中，我们从图搜索的角度探讨了 GNNs 的表达能力，提出了一种新的顶点着色方案，并证明经典的搜索算法可以高效地计算超越 1-WL 的图表示。我们展示了这种着色方案从图搜索中继承的有用特性，可以帮助解决图的双连通性问题。此外，我们还展示了在某些条件下，GNNs 的表达能力随着搜索邻域的半径逐层递增。为了进一步研究所提出的方案，我们基于广度优先搜索和深度优先搜索开发了一种新类型的 GNN，突出了它们在 1-WL 之上所能捕捉到的图属性。

Mar, 2024

受物理启发的图神经网络中的图着色

利用图神经网络解决图着色问题，将图着色视为多类节点分类问题，利用基于统计物理学的 Potts 模型的无监督训练策略。我们展示了该方法在实际应用中的性能，并提供了数值基准结果。

Feb, 2022

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

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

Feb, 2021

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

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

May, 2019

超越 TSP 的神经组合优化：现有架构在图结构下表现不足

本文研究如何将深度强化学习和图神经网络应用于无线网络中的电力和信道分配问题，研究结果表明现有结构还不能很好地识别图的结构和特征，并且对于对图产生影响的问题不太适用，但研究还是取得了一些积极进展，比如通过距离编码来增强问题的表示方法。

Jan, 2022

学习解决 NP 完全问题 - 用图神经网络处理决策 TSP 问题

本文研究表明图神经网络可以通过可训练的可组装模块来解决含有符号和数值数据结构的 NP 完全问题，提供了一个解决 TSP 问题的高度自主的消息传递算法并且能够使用与目标成本 C 的偏差小于 2% 的决策实例进行训练。

Sep, 2018

图神经网络综述

该论文综述了图神经网络在数据挖掘和机器学习领域的广泛应用，提出了四种图神经网络的分类，并讨论了在各个领域中的应用以及图神经网络的开放源代码、基准数据集和模型评估，并提出了该领域的潜在研究方向。

Jan, 2019

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

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

Jun, 2024

图形 Q-Learning 用于组合优化

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

Jan, 2024