综述：基于现代神经网络图的着色问题研究综述

《Neural Networks》：A Survey of Modern Neural Network Based Methods for the Graph Coloring Problem

　　金一涵|凯安·辛|惠娜·楚

摘要
图着色问题是一种重要的NP难组合优化问题，广泛应用于调度、寄存器分配、频率分配和资源管理等领域。传统的启发式方法和精确算法在处理大型或动态图时往往效率低下，因此人们开始寻求基于学习的替代方案。近年来，将神经网络应用于图着色问题的研究日益增多，但目前尚无系统性综述总结这些进展。本综述旨在梳理将神经网络用于图着色问题的常见方法和架构，总结用于评估这些方法的基准数据集并分析其有效性，同时指出当前应用中存在的关键挑战。为达成这些目标，本文全面回顾了2019年至2025年间图神经网络出现后的相关研究，将这些方法分为监督学习、无监督学习和强化学习三类。综述介绍了目前的进展、基准数据集的作用，以及计算成本、可解释性以及过度依赖COLOR和DIMACS等有限基准数据等长期存在的挑战。最后，本文提出了提升模型泛化能力和实际应用价值的未来研究方向。

引言
图着色问题是由Formanowicz和Tana?在2012年提出的，它是数学和计算机科学领域中研究最为深入的组合优化问题之一。一般来说，图着色问题是NP难的（即难度至少与NP类中最难的问题相当，Tovey，2002），即便是在如判断三着色是否可能的受限情况下，也依然属于计算上难以解决的问题（Brandst?dt等人，1998）。尽管难度较大，图着色在现实世界中有着广泛的应用，包括调度、寄存器分配、频率分配和资源管理等领域（Assi等人，2018；De，2022；Park和Lee，1996；Saharan和Kumar，2016）。由于这类问题的复杂性，针对它们的精确算法在处理大规模实例时往往难以适用，因此研究人员转而使用启发式方法和近似算法作为实用替代方案（Li等人，2020）。

然而，手工设计的启发式方法通常需要深厚的领域知识，设计耗时，且在不同问题上的一般化能力较差（Branke等人，2015；Liu等人，2023b）。这促使人们研究能够以最少人工干预自动生成启发式规则的学习型方法（Bengio等人，2021；Jeon等人，2020；Liu等人，2023b；Mirshekarian和Sormaz，2018；Wu等人，2021）。在这一背景下，尽管存在可解释性方面的挑战，深度神经网络仍展现出巨大潜力（Samek等人，2021）。它们具备对未见输入进行泛化的能力（Zhang等人，2016），并能充当通用函数逼近器（Augustine，2024；Hornik等人，1989；Lu和Lu，2020），从而为问题的表述和算法设计提供了更大灵活性。对于图着色问题而言，这些优势尤为重要，因为该问题可以有多种表述方式，且应用场景极为广泛。作为研究最为深入的NP难问题之一，图着色问题的决策版本还是NP完全的（即既属于NP类又属于NP难问题，Karp，2009），因此在P与NP难题研究中占据核心地位（Garey和Johnson，1990）。它同时也是衡量实际优化算法性能的重要基准（Lewis，2021）。

如图1所示，根据IEEE Xplore、Scopus和ACM数据库的统计，过去十年中包含“图着色”和“神经网络”关键词的学术论文数量持续增长。尽管发展势头强劲，但这一领域仍处于起步阶段，目前尚未形成将神经网络有效应用于图着色问题的成熟方法，也不存在关于最佳实践的共识。这一增长趋势反映了机器学习和人工智能整体发展的态势（Tiwari，2024），也凸显出图着色问题在理论层面和实际应用层面的重要价值。其受欢迎程度的上升也与2017年左右图神经网络的出现相吻合，图神经网络使得基于图结构数据的自动表示学习成为可能。对于调度和资源分配等应用而言，高效的AI驱动解决方案对现代产业具有极高的实用价值（Bharadiya等人，2023；Enholm等人，2022）。

虽然已有几篇综述探讨了图上的机器学习及组合优化问题（见第2节），但尚未有综述专门系统地总结针对图着色问题的神经网络方法。神经网络支撑了当今人工智能领域的诸多重大进展，从图像识别（Rani等人，2022）、棋类游戏引擎（Sadmine等人，2023；Silver等人，2018）到生成式AI，如大型语言模型（Achiam等人，2023；Liu等人，2024）。在许多领域，基于深度神经网络的模型已经达到甚至超越了人类的表现水平（Berner等人，2019；Mathieu等人，2023；Mnih等人，2015；Silver等人，2018），这体现了它们在解决图着色等计算难度高的问题上的潜力。许多研究图相关问题的方法都需要将图嵌入到欧几里得空间中。关于图表示学习的最新方法，有兴趣的读者可参考相关综述（Chikwendu等人，2023；Ju等人，2024）。

鉴于图着色问题的理论意义和实际价值，以及深度学习近期的成功成果，本文对基于神经网络的图着色问题解决方法进行了全面综述。我们系统梳理了现有方法的优点与局限性，指出了文献中的研究空白，并提出了具有前景的研究方向。虽然本文主要聚焦于最具代表性的基于神经网络的研究，但也提及了一些与图着色相关的其他工作，但未作深入分析。基于此，本文围绕以下几个问题展开论述：
1. 将神经网络应用于图着色问题的常见方法有哪些？最常用的架构是什么？
2. 用于评估这些方法的基准数据集有哪些？神经网络方法在解决图着色问题方面的效果如何？
3. 在将神经网络应用于图着色问题时，还存在哪些关键挑战？

本文其余结构如下：第2节列举了与图着色问题和组合优化问题相关的现有综述；第3节简要介绍了本次综述所参考文献的来源及筛选标准；第4节给出了图着色问题的正式定义，并介绍了神经网络和图神经网络的基本背景；第5节阐述了图着色问题和神经网络的发展历程；第6节总结了2018年至2025年间将神经网络应用于图着色问题的研究成果，将这些方法分为监督学习、无监督学习和强化学习三类；第8节指出了当前存在的挑战及未来的研究方向；最后在第9节对整个综述进行总结。

相关研究
近年来，机器学习技术在图结构数据及组合优化问题中的应用迅速发展，已有不少综述记录了这一趋势，但侧重点各不相同。许多关于图学习的综述通常聚焦于节点分类、链接预测和推荐系统等预测任务（例如Nie等人，2023；Peng等人，2021；Xia等人，2021），而对以优化为导向的问题关注较少。相反，虽然也有关于机器学习的综述……

主要文献来源与检索词
本综述所选文献主要与神经网络和图着色问题相关，这些文献来自Google Scholar、Scopus和IEEE Xplore数据库。我们根据特定关键词及其同义词筛选文献，检索词包括：
•(“graph coloring” OR “combinatorial optimization”) AND “neural network”
•“graph coloring” AND (“supervised learning” OR “unsupervised learning” OR “reinforcement learning”)
•“graph coloring” AND “graph embeddings”

检索策略
为确保……

图着色问题
设G=(V,E)为一个简单的有限图，C为一组颜色。图的顶点着色是指将V映射到颜色集合C的函数，记为f: V?C。如果对于图E中的任意一条边uv，都有f(u)≠f(v)，则称这种着色是合法的（Formanowicz和Tana?，2012）。在学术文献中，通常用自然数集N来表示颜色集合。对于图G的某一种着色（不一定是合法的），我们将端点颜色相同的边数量定义为冲突数，即满足f(u)=f(v)的边数。

神经网络与图着色问题的简史
尽管神经网络在各个领域的发展速度极快且影响深远，但其在图着色等问题上的应用进展相对缓慢。为了便于理解本综述的内容，我们先简要介绍神经网络的发展历程以及图着色问题的演变过程，重点阐述其中的里程碑事件、其他替代方法，以及神经网络在该领域日益重要的地位。

神经网络和图着色问题的发展大致是独立进行的……

方法综述
在本节中，我们回顾了近期利用神经网络解决图着色问题的方法。这些方法大致可分为三类：监督学习、无监督学习和强化学习。这种分类反映了神经网络为应对图着色问题的特殊挑战而采取的主要适应方式，我们将在后续小节中分别详细讨论每种方法。对于一些早期研究中未在此详细阐述的案例，本文也将简要提及。

基准测试
本节汇总了本综述中所分析的各项研究的结果。由于大多数研究都是基于COLOR基准数据集中的图实例进行评估的（Trick，2004），因此我们的比较仅限于该数据集中的实例，那些仅基于其他图集进行研究的工作未被纳入考虑范围。此外需要说明的是，虽然有些研究报告了求解时间，但由于硬件和实现方式的差异，很难进行有意义的横向时间对比，因此……

讨论
目前针对图着色问题的神经网络方法呈现出方法多样化的特点，同时也存在一些持续的局限性。在监督学习、无监督学习和强化学习这三种方法中，关于这些方法的发展趋势、评估方式以及实际应用面临的障碍，已经出现了一些共性的研究主题。

结论
将神经网络应用于图着色问题，是组合优化领域一个充满潜力但仍在发展中的方向。通过学习那些难以通过手动编码获取的结构规律，这类模型为解决传统算法难以处理的复杂问题提供了新的途径。不过，目前的证据表明，基于神经网络的方法更多是作为传统启发式方法的补充，而非竞争性替代品。

目前，最为实用的策略是……

AI工具使用声明
作者声明在撰写本文时未使用任何人工智能工具。

CRediT作者贡献说明
金一涵：写作——审稿与编辑，写作——初稿撰写，可视化，验证，方法论，研究设计，形式分析，概念构建。凯安·辛：写作——审稿与编辑，验证，指导，方法论，研究设计，概念构建。惠娜·楚：写作——审稿与编辑，验证，指导，方法论，研究设计，概念构建。

利益冲突声明
作者声明不存在任何可能影响本文研究结果的已知财务利益或个人关系。