用局部唯一标识提升GNN求解整数规划，效果更好且泛化更强
Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
- 仅在节点邻域内保证标识唯一，避免全局伪相关
- 在多个ILP基准上性能显著提升，且更稳定
- 适合需要强泛化能力的优化学习任务
整数线性规划（ILPs）是现实世界优化的核心，但求解难度大。学习优化（L2O）成为新范式，图神经网络（GNNs）作为标准骨干。然而，标准匿名GNN对ILPs表达能力有限，而常用全局唯一标识（UID）增强会引入伪相关，严重损害泛化能力。为此，我们提出基于d-hop唯一着色的轻量级局部唯一标识（Local-UID）方案，确保标识仅在节点d跳邻域内唯一。在此基础上，提出ColorGNN，通过颜色条件嵌入融合颜色信息；以及ColorUID，一种轻量级特征级变体。理论证明：对于d层网络，Local-UID可达到与Global-UID相当的表达力，同时具备更强泛化能力。大量实验表明，该方法在多个ILP基准上均实现显著且稳健的性能提升。
原文摘要 · Abstract (English)
Integer Linear Programs (ILPs) are central to real-world optimizations but notoriously difficult to solve. Learning to Optimize (L2O) has emerged as a promising paradigm, with Graph Neural Networks (GNNs) serving as the standard backbone. However, standard anonymous GNNs are limited in expressiveness for ILPs, and the common enhancement of augmenting nodes with globally unique identifiers (UIDs) typically introduces spurious correlations that severely harm generalization. To address this tradeoff, we propose a parsimonious Local-UID scheme based on d-hop uniqueness coloring, which ensures identifiers are unique only within each node's d-hop neighborhood. Building on this scheme, we introduce ColorGNN, which incorporates color information via color-conditioned embeddings, and ColorUID, a lightweight feature-level variant. We prove that for d-layer networks, Local-UIDs achieve the expressive power of Global-UIDs while offering stronger generalization. Extensive experiments show that our approach yields substantial and robust gains across ILP benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。