沙丘社区
论文

将LLM与图神经求解器对齐以求解组合优化

Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization

Shaodi Feng, Zhuoyi Lin, Yaoxin Wu, Haiyan Yin, Yan Jin, Senthilnath Jayavelu, Xun Xu
模型架构混合架构

摘要

近期研究证明了大语言模型（LLM）通过以自然语言表示任务与实例来求解组合优化问题（COP）的有效性。然而，纯语言方法难以准确捕捉许多COP固有的复杂关系结构，使其在处理中等或更大规模实例时效果欠佳。为解决这些局限，我们提出AlignOPT，一种将LLM与图神经求解器对齐、以学习更具泛化性的神经COP启发式的新方法。具体而言，AlignOPT利用LLM的语义理解能力编码COP及其实例的文本描述，同时利用图神经求解器显式建模COP实例的底层图结构。我们的方法促成语言语义与结构表示之间的稳健整合与对齐，实现更准确、更具可扩展性的COP求解。实验结果表明，AlignOPT在多样的COP上取得最优结果，凸显其在语义与结构表示对齐上的有效性。特别是，AlignOPT展现出强泛化能力，可有效扩展到此前未见过的COP实例。

将LLM与图神经求解器对齐以求解组合优化：论文配图
图 1：AlignOPT 的总体工作流程。 (a) AlignOPT 首先对不同的 COP 执行多任务预训练，以将语义和结构节点表示与 TGC 和 TGM 损失对齐。 LLM 保持冻结状态并处理 TAI 以生成语义节点表示。 (b) 然后通过强化学习对编码器和解码器进行微调以解决 COP。值得注意的是，在此阶段排除了 LLM 以确保计算效率，因为编码器在预训练期间已与 LLM 派生的表示对齐。 (c) 基于图的编码器的模型架构，它应用混合注意机制，能够处理由图表示的 COP。