大型语言模型增强型图神经架构搜索在二次无约束二元优化中的应用

《Knowledge-Based Systems》：Large Language Models Enhanced Graph Neural Architecture Search for Quadratic Unconstrained Binary Optimization

提出基于强化学习和大语言模型的图神经网络架构搜索模型GNAS4QUBO，通过设计融合QUBO反馈的学习函数和定制化LLM提示，动态优化GNN架构以提升QUBO求解性能，实验表明在最大切分、集合覆盖等基准任务中准确率和剪枝指标显著优于现有方法。

　　近年来，随着人工智能和计算技术的迅速发展，优化问题在多个领域得到了广泛关注。其中，二次无约束二元优化（Quadratic Unconstrained Binary Optimization, QUBO）作为一类重要的无约束组合优化问题，因其在解决复杂决策问题中的潜力而受到特别重视。QUBO问题的目标是优化一个二次多项式函数，其决策变量为二元变量，没有显式的约束条件。这类问题广泛应用于图分割、集合覆盖、组合拍卖、最大独立集等多个实际场景中。例如，最大割问题可以通过将目标函数定义为顶点分割上的边数最大化，从而被转化为QUBO问题。类似地，许多具有显式约束的组合问题也可以通过引入约束惩罚项，将其转换为QUBO形式进行求解。

QUBO问题在量子计算领域中具有重要意义，因为它提供了一个统一的优化框架，使得量子算法能够更有效地处理复杂优化任务。然而，传统的量子计算方法在处理大规模问题时往往面临计算资源不足和算法效率低下的挑战。近年来，图神经网络（Graph Neural Networks, GNNs）被引入到QUBO问题的求解中，取得了令人瞩目的成果。GNNs能够将QUBO问题建模为图结构，并通过学习图的表示来找到最优解。这种方法不仅能够处理大规模数据，还能够捕捉图中复杂的结构信息，从而提升优化效果。

尽管GNNs在QUBO问题求解中表现出色，但在实际应用中，如何设计最优的GNN模型仍然是一个关键问题。通常，GNN模型的参数（如层数、激活函数的选择、图操作的方式等）需要手动设置，这往往依赖于经验性的选择，缺乏系统性和自动化的方法。例如，一些近期的研究尝试使用简单的两层图卷积网络（GCN）来学习QUBO图的表示，但其效果通常不够理想，因为模型参数被固定，无法根据具体问题进行调整。因此，一个核心问题是如何设计一个能够有效学习QUBO图表示的GNN模型，以最小化优化过程中的准确率损失。

为了解决这一问题，研究者们提出了图神经网络架构搜索（Graph Neural Architecture Search, GNAS）的方法，旨在通过自动化的方式生成新的GNN架构。GNAS通常包括搜索空间、搜索策略和评估指标三个组成部分。搜索空间定义了可用于构建GNN的各种操作，如聚合函数、激活层和网络连接方式。搜索策略则用于探索搜索空间，例如使用强化学习算法、进化算法或微分搜索算法。评估指标用于衡量生成的GNN架构的性能。通过迭代地更新候选架构，GNAS能够找到最优的GNN模型，从而提升QUBO问题的求解效果。

然而，现有的GNAS方法主要针对传统的图学习任务，如节点分类和图分类，未能充分考虑QUBO问题的特殊性。因此，为了更有效地解决QUBO问题，有必要开发一种专门针对QUBO的GNAS模型。本研究提出了一种新的图神经网络架构搜索模型，称为GNAS4QUBO。该模型结合了QUBO框架和GNAS方法，旨在通过自动化的方式生成最优的GNN架构，以学习QUBO图的表示并求解优化问题。此外，我们还利用大型语言模型（Large Language Models, LLMs）来增强GNAS4QUBO模型，通过设计新的GNAS4QUBO提示（prompts）来帮助LLMs理解QUBO问题，并利用LoRA微调技术对LLMs进行优化，以生成更高效的GNN架构。

在设计GNAS4QUBO模型时，我们首先解决了第一个挑战：如何设计一个新的学习函数，使GNAS能够有效学习QUBO图的表示并收敛到最优解。该学习函数需要同时考虑QUBO问题和GNAS方法，如何将这两个目标统一为一个学习函数是关键。我们采用强化学习的方法，通过QUBO问题的反馈来指导GNAS的学习过程，从而找到最优的GNN架构。其次，我们解决了第二个挑战：如何让LLMs理解GNAS和QUBO问题，并生成最优的GNN模型。为此，我们设计了一套新的GNAS4QUBO提示，帮助LLMs理解搜索任务、搜索空间、搜索策略和反馈机制。然后，我们基于新的GNN架构对LLMs进行微调，以提升其在QUBO问题上的表现。

为了验证GNAS4QUBO模型的有效性，我们在多个QUBO基准数据集上进行了实验。我们测试了该模型在最大割、最大独立集、集合覆盖、组合拍卖和设施选址等典型QUBO问题上的性能。实验结果表明，GNAS4QUBO在这些任务上的表现优于现有的GNN模型。此外，我们还测试了该模型在GNAS搜索和LLMs微调方面的效果，以评估其在不同任务上的泛化能力。通过这些实验，我们验证了GNAS4QUBO模型在解决QUBO问题中的优势，包括更高的准确率和更优的割大小指标。

本研究的贡献主要体现在三个方面。首先，GNAS4QUBO是首个将大型语言模型与图神经网络架构搜索相结合，用于解决QUBO问题的模型。通过这种结合，我们不仅能够利用LLMs的强大语言理解能力，还能够借助GNAS的自动化搜索机制，找到最优的GNN架构，从而提升QUBO问题的求解效果。其次，我们提出了一个新的学习函数，该函数结合了QUBO框架和GNAS方法，通过强化学习的方式指导GNN架构的搜索。这一学习函数能够有效捕捉QUBO问题的特征，并提升模型的收敛速度和优化效果。最后，我们设计了一套新的GNAS4QUBO提示，帮助LLMs理解QUBO问题，并利用LoRA微调技术对LLMs进行优化，以生成更高效的GNN架构。

为了进一步验证GNAS4QUBO模型的性能，我们还进行了多组对比实验。我们比较了该模型与传统GNN模型在相同任务上的表现，包括准确率、计算效率和优化结果的质量。实验结果表明，GNAS4QUBO在这些指标上均优于传统方法，尤其是在处理大规模QUBO问题时，其表现更为突出。此外，我们还测试了该模型在不同数据集上的泛化能力，包括合成数据集和真实世界数据集。通过这些测试，我们验证了GNAS4QUBO模型在多种场景下的适用性。

在实验过程中，我们还关注了模型的可解释性和计算资源的使用情况。GNAS4QUBO模型不仅能够生成最优的GNN架构，还能够提供关于模型选择的解释，帮助研究人员理解为什么某些架构在特定任务上表现更好。此外，我们还评估了模型在不同计算资源下的表现，包括使用GPU和CPU进行训练和推理的效率。实验结果表明，GNAS4QUBO模型在计算资源有限的情况下仍然能够保持较高的性能，这为其在实际应用中的推广提供了有力支持。

总之，GNAS4QUBO模型的提出为解决QUBO问题提供了一种新的思路和方法。通过结合GNN架构搜索和LLMs，我们不仅能够提升模型的优化效果，还能够增强模型的适应性和可解释性。未来的研究方向包括进一步优化模型的搜索策略，提升其在不同任务上的泛化能力，以及探索更高效的微调方法，以减少计算资源的消耗。此外，我们还计划将GNAS4QUBO模型应用于更广泛的优化问题，如资源分配、路径规划和任务调度等，以验证其在更多实际场景中的适用性。通过这些努力，我们相信GNAS4QUBO模型能够在解决复杂优化问题方面发挥更大的作用。