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

Mar, 2019

本文研究了图神经网络的表达能力，发现其存在局限性。作者提出为每个节点添加随机特征，这样GNN就能够学习一些最优多项式时间近似算法，同时该方法方便与其他GNN模型结合使用。经实验证明，加入随机特征的GNN能够解决一些无法被传统的GNN模型解决的问题。

Feb, 2020

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

Feb, 2021

我们设计了图神经网络架构，利用半定规划的强大算法工具，来获得一类组合优化问题的最优逼近算法。通过研究，我们证明了多项式大小的消息传递算法可以表示 Max Constraint Satisfaction Problems 的最强多项式时间算法（基于 Unique Games Conjecture）。我们利用这一结果构建了高效的图神经网络架构 OptGNN，在最大割和最大独立集等经典组合优化问题上获得了高质量的近似解。我们的方法在各种真实和合成数据集上取得了强有力的实证结果，超过了神经基准和传统算法。最后，我们利用 OptGNN 捕捉凸松弛的能力，设计了一个从 OptGNN 学习的嵌入中产生对优解的对偶证明的算法。

Oct, 2023

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

Jan, 2024

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

Feb, 2024

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

May, 2024

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

Jun, 2024

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

Jun, 2024

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

Jun, 2024