统一表示多类组合优化问题，无需标注直接训练。
UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization
- 设计统一异构图表示，融合问题结构与约束条件。
- 跨四类问题性能媲美顶尖无监督方法，支持快速启动商用求解器。
- 动态梯度加权缓解多任务学习中的梯度失衡问题。
无监督神经组合优化（NCO）通过不依赖真实解直接最小化实例目标和约束违反，提供了一种有吸引力的替代方案。然而，针对图节点子集选择问题（如最大团、最大独立集），现有无监督方法通常仅针对单一问题类别，依赖问题特异性代理损失，难以在统一框架下跨类别学习。本文提出UniHetCO，一种基于约束二次规划的统一异构图表示，将问题结构、目标项和线性约束统一编码为单个输入。该形式支持使用统一无标签目标在多个问题类别上训练单一模型。为提升多问题学习的稳定性，采用基于梯度范数的动态加权策略，缓解不同类别间的梯度不平衡。在多个数据集及四类约束问题上的实验表明，其性能优于或媲美当前最优无监督NCO基线，具备强大的跨问题适应能力，并能在严格时间限制下有效为商业经典求解器提供热启动。
原文摘要 · Abstract (English)
Unsupervised neural combinatorial optimization (NCO) offers an appealing alternative to supervised approaches by training learning-based solvers without ground-truth solutions, directly minimizing instance objectives and constraint violations. Yet for graph node subset-selection problems (e.g., Maximum Clique and Maximum Independent Set), existing unsupervised methods are typically specialized to a single problem class and rely on problem-specific surrogate losses, which hinders learning across classes within a unified framework. In this work, we propose UniHetCO, a unified heterogeneous graph representation for constrained quadratic programming-based combinatorial optimization that encodes problem structure, objective terms, and linear constraints in a single input. This formulation enables training a single model across multiple problem classes with a unified label-free objective. To improve stability under multi-problem learning, we employ a gradient-norm-based dynamic weighting scheme that alleviates gradient imbalance among classes. Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance with state-of-the-art unsupervised NCO baselines, strong cross-problem adaptation potential, and effective warm starts for a commercial classical solver under tight time limits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。