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

Mar, 2019

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

Jul, 2021

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

Aug, 2022

本文通过引入颜色编码的方法，改进了消息传递神经网络（MPNNs）的表达能力，提出了一种使用颜色消除相同节点属性的图神经网络，名为 Colored Local Iterative Procedure (CLIP)，证明该方法是连续函数的通用逼近器，并实验验证了 CLIP 能够捕捉传统 MPNN 无法区分的结构特征，并且在基准图分类数据集中表现最佳。

Dec, 2019

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

Mar, 2024

介绍了图神经网络在粒子物理学中应用的各种情况，并探讨了它在粒子物理学中的潜在应用。

Jul, 2020

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

Apr, 2023

使用深度强化学习，本研究使用新的深度神经网络结构 FastColorNet，能在有效计算时间内更好地对大型图形进行着色，从而将计算转化为改进启发式方法，获得了新的图形着色启发式方法。

Feb, 2019

通过引导学习过程的精确同构求解器技术，我们的算法使消息传递图神经网络具有通用性，通过从根到叶子节点的搜索树中采样多个路径，并结合粒子滤波更新来学习更具辨别性的表示，从而在运行时间仅线性增加的情况下，在同构检测的合成基准和真实世界数据集上始终优于领先的图神经网络模型。

Jan, 2024

本文旨在使用热扩散框架解决图着色问题，并与传统方法进行比较，证明热扩散方法在图着色问题中的竞争力。

Apr, 2024