Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 30 of its 47 references that are in the map. First posted on arXiv 25 Sep 2025.
Builds on
30 of 47 references.
References · 30
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
- 2017Graph Attention Networkscited by 8,923
- 2020Benchmarking Graph Neural Networkscited by 680
- 2020A Generalization of Transformer Networks to Graphscited by 661
- 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
- 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
- 2019What graph neural networks cannot learn: depth vs widthcited by 201
- 2020Random Features Strengthen Graph Neural Networkscited by 186
- 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
- 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
- 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
- 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
18 more
- 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 61
- 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 49
- 2023A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programmingcited by 41
- 2022The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insightscited by 39
- 2022On Representing Linear Programs by Graph Neural Networkscited by 39
- 2023On the Stability of Expressive Positional Encodings for Graphscited by 33
- 2021Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradientcited by 32
- 2023Graph Positional Encoding via Random Feature Propagationcited by 31
- 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
- 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24
- 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
- 2024PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programmingcited by 17
- 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
- 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
- 2024SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimizationcited by 4
- 2025Towards Invariance to Node Identifiers in Graph Neural Networkscited by 4
- 2025When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approachcited by 3
- 2024On the Utilization of Unique Node Identifiers in Graph Neural Networkscited by 2
Built on by
Not cited yet.