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

Mar, 2019

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

Feb, 2022

本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性，探讨了基于半环的代数方法，提出了组件双宽属性的 generalization。研究表明，在受限制的条件下，该方法在多种问题中取得了优秀算法复杂度上界。

Jul, 2022

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

Aug, 2022

本文研究了packing coloring在图论中的应用，提出了一种新的propositional encoding方法加速计算，最终证明了无限正方形网格的chromatic number为15。

Jan, 2023

我们提出了一种图同构的泛化方法，通过声明式规范来检查复杂的结构属性，其中规范以一种类似于正则表达式的图形形式给出，并且通过基于SAT的算法来检查目标图是否匹配给定的规范，并通过对CodeSearchNet数据集的广泛实验评估提出了一种优化算法的预处理技术。

Dec, 2023

使用图着色问题将寄存器分配问题作为Proximal Policy Optimization模型的图着色问题的解决方法，展示了标签重排的图的不变表示在机器学习模型中的应用。

Jan, 2024

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

Mar, 2024

本研究解决了图着色问题，该问题是一个NP困难的优化问题，特别是在大规模图中。我们提出了一种新颖的算法，利用图神经网络及物理启发的方法来提高训练效率和算法性能。研究结果表明，该方法在传统方法难以解决的连通性区域中依然有效，具有广泛的应用潜力。

Aug, 2024

本文解决了图着色问题，这是一种在无向图中为顶点分配不同颜色的NP难题。提出了一种基于图神经网络的排序启发式，显著提升了着色质量和执行效率。研究表明，在平行处理能力上，GNN模型在质量和性能上超越了现有的贪心排序启发式方法。

Aug, 2024