用连续和混合整数设置的情况下，我们研究了图神经网络在二次规划任务中的表达或代表能力，证明了存在可靠地表示二次规划关键属性的消息传递图神经网络，并通过数值结果验证了我们的理论。

Jun, 2024

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

Oct, 2023

研究了 MPNN 在图分类和回归中的泛化误差，表明 MPNN 的复杂度越高，泛化差距越大；同时，不仅训练样本数，而且图中平均节点数对泛化差距也有影响。从统一收敛结果导出泛化界限，表明在图上应用 MPNN 可以逼近离散化的几何模型上的 MPNN。

Feb, 2022

本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

Jul, 2021

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

Oct, 2019

利用最近在精确和可微分的 k 子集采样中的进展，我们设计了一种概率重连的消息传递图神经网络（PR-MPNNs），该网络学习在省略不太有益的边的同时添加相关边。首次，我们的理论分析探索了 PR-MPNNs 如何增强表达能力，并且我们确定了它们优于纯随机方法的精确条件。经验证实，我们的方法有效地缓解了如过度压缩和预测能力不足等问题。此外，根据现有的真实世界数据集，我们的方法在预测性能上与传统的 MPNN 模型和最近的图变压器架构相比表现出有竞争力或更好的性能。

Oct, 2023

本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。

Jun, 2020

本文研究如何全面利用信息，从理论和实践上提高信息传递神经网络的表现力和可推广性，并提出一种新的名为 INGNN 的图神经网络模型，针对节点分类任务，与目前最先进的方法相比，实验证明其优越性（平均排名 1.78）。

Oct, 2022

此研究提出了一种基于全局和局部线性松弛的可扩展启发式方法，用于对训练后的神经网络模型进行建模和求解，具有与最先进的整数线性规划（MILP）求解器和之前的启发式方法相竞争，并且在输入、深度和神经元数量增加时能够产生更好的解。

Jan, 2024

通过利用输入向量的正交性，纯消息传递可以捕捉联合结构特征，我们引入了一种基于消息传递的链接预测模型（MPLP），它利用准正交向量来估计链接级结构特征，同时保留节点级复杂性。我们的方法在各个领域的基准数据集上对于基准方法有一致的优化效果。

Sep, 2023