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

Feb, 2021

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

Mar, 2019

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

Feb, 2020

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

Oct, 2023

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

May, 2024

本研究关注图神经网络的本质问题：无法仅仅依靠局部信息计算多个重要的图形特征；同时提出了信息传递图神经网络的第一个数据相关泛化界限，这一分析专门考虑了 GNN 局部置换不变性，该边界比现有的基于 VC 维度的 GNN 保证要紧密，与循环神经网络的 Rademacher 界限相当。

Feb, 2020

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

Oct, 2019

该论文提供了第一个针对具有一个隐层节点信息卷积的图神经网络（GNN）的可证明有效的学习算法，并开发了一种综合性框架来设计和分析 GNN 训练算法的收敛性。提出的算法适用于各种激活函数，包括 ReLU，Leaky ReLU，Sigmoid，Softplus 和 Swish，并对样本复杂度进行了特征化。数值实验进一步验证了理论分析。

Dec, 2020

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

Jun, 2024

在图神经网络中，提出用节点级异质性度量替代全局同质性系数来更好地表示网络节点的混合模式，进而设计了一种改进的计算图结构，并在此基础上提出一种自适应选择结构与接近度信息的模型，以取得更好的性能，其中针对半监督节点分类任务进行的实验也取得了良好的结果。

Jun, 2021